پایان نامه ارشد : الگوریتم تکاملی جستجوگر ، یک الگوریتم جدید برای مسائل بهینه سازی پیوسته

دانلود متن کامل پایان نامه مقطع کارشناسی ارشد رشته مهندسی صنایع 

گرایش :  صنایع

عنوان : الگوریتم تکاملی جستجوگر ، یک الگوریتم جدید برای مسائل بهینه سازی پیوسته

وزارت علوم، تحقیقات و فناوری

دانشگاه علوم و فنون مازندران

 

پایان نامه

مقطع کارشناسی ارشد

رشته  : مهندسی صنایع – صنایع

موضوع  : الگوریتم تکاملی جستجوگر ، یک الگوریتم جدید برای مسائل بهینه سازی پیوسته

استاد راهنما  : دکتر نیکبخش جوادیان

استاد مشاور  : دکتر رضا توکلی مقدم

بهار 1392

برای رعایت حریم خصوصی نام نگارنده پایان نامه درج نمی شود

(در فایل دانلودی نام نویسنده موجود است)

تکه هایی از متن پایان نامه به عنوان نمونه :

(ممکن است هنگام انتقال از فایل اصلی به داخل سایت بعضی متون به هم بریزد یا بعضی نمادها و اشکال درج نشود ولی در فایل دانلودی همه چیز مرتب و کامل است)

چکیده

در سال های اخیر توسعه و استفاده از الگوریتم های تکاملی رشد چشم گیری داشته است. ساختار اغلب الگوریتم ها بر مبنای یک پدیده در طبیعت بوده است. هر یک از آنها دارای نقاط ضعف و قوتی بوده است به طوری که هر از چند گاهی شاهد معرفی الگوریتمی جدید هستیم که برتری خود را نسبت به تعدادی از الگوریتم های قبلی نشان می دهد.

در این پایان نامه یک الگوریتم جدید برای حل مسائل بهینه سازی پیوسته معرفی می شود. این الگوریتم مبتنی بر یک منطق ساده جستجو است. در این الگوریتم هر جستجوگر معرف یک جواب است. الگوریتم جستجوگر تکاملی در هر گام ناحیه جستجو و جستجوگرها را به چند قسمت تقسیم می کند و هر گروه جستجو را به ناحیه ای تخصیص می دهد. حرکت جستجوگرها در ناحیه ها بر اساس یک روند تکاملی ساده می باشد ولی هیچ کدام از جستجوگرها اجازه ورود به ناحیه های دیگر را ندارند. در مرحله بعد تعدادی از ناحیه ها  که بهترین مقدار تابع هدف را دارا هستند انتخاب و به چند ناحیه کوچکتر تقسیم می شوند و گروه های جستجوگر به آنها تخصیص داده می شوند. این مراحل تا برقراری شرط توقف ادامه پیدا خواهد کرد برای سنجش عملکرد این الگوریتم از مثال های موجود در مقالات پر رجوع ترین الگوریتم ها استفاده شده است. نتایج بدست آمده نشان دهنده برتری الگوریتم جستجوگر تکاملی بر این الگوریتم ها است.

کلمات کلیدی

بهینه سازی هوشمند، الگوریتم های فرا ابتکاری، بهینه سازی سراسری، الگوریتم جستجوگر تکاملی، بهینه سازی پیوسته

 

 

 

 

 

فهرست مطالب

عنوان صفحه
1-  کلیات تحقیق …………………………………………………………………………………………. 1
       1-1-  مقدمه ………………………………………………………………………………………. 2
1       -2-  تعریف مساله ………………………………………………………………………………… 2
1       -3-  هدف تحقیق …………………………………………………………………………………. 3
1       -4-  فرضیات تحقیق ………………………………………………………………………………. 3
1       -5-  اهمیت و ضرورت تحقیق …………………………………………………………………….. 3
1       -6-  خلاصه فصل های آتی………………………………………………………………………… 4
2-  ادبیات و پیشینه تحقیق ……………………………………………………………………………….. 5
      2-1-  مقدمه ………………………………………………………………………………………… 6
      2-2-  مرور ادبیات الگوریتم های فرا ابتکاری …………………………………………………………. 6
      2-3-  جمع بندی ……………………………………………………………………………………. 15
3-  زمینه های علمی تحقیق ……………………………………………………………………………… 16
      3-1-  مقدمه ………………………………………………………………………………………… 17
       3-2-  مسائل بهینه سازی ……………………………………………………………………………. 17
       3-3-  بررسي روش‌هاي جستجو و بهينه‌سازي ……………………………………………………….. 18
                3-3-1-  روش‌هاي شمارشي ………………………………………………………………… 19
                3-3-2-  روش‌هاي محاسباتي ……………………………………………………………….. 20
                3-3-3-  روش‌هاي ابتكاري و فرا ابتکاری ……………………………………………………. 21
      3-4-   مسائل بهينه‌سازي تركيبي ……………………………………………………………………… 21
      3-5-   روشهای حل مسائل بهينه‌سازي تركيبي ………………………………………………………… 23
                 3-5-1-  روش های ابتکاری ………………………………………………………………… 24
                               3-5-1-1-  آزاد‌سازي …………………………………………………………… 24
                               3-5-1-2-  تجزيه ………………………………………………………………. 25
                               3-5-1-3-  تكرار ……………………………………………………………….. 25
                               3-5-1-4-  روش توليد ستون …………………………………………………… 25
                                3-5-1-5-  جستجوي سازنده …………………………………………………… 26
                               3-5-1-6-  جستجوي بهبود يافته ……………………………………………….. 26
                               3-5-1-7-  روش جستجوي همسايه …………………………………………….. 27
               3-5-2-  روش‌هاي فرا ابتكاري برگرفته از طبيعت ……………………………………………… 28
      3-6-  جمع بندی ……………………………………………………………………………………. 29
4- ارائه الگوریتم جدید پیشنهادی ……………………………………………………………………….. 30
      4-1-  مقدمه ………………………………………………………………………………………… 31
      4-2-  الگوریتم جستجوگر تکاملی…………………………. (Seeker Evolutionary Algorithm) 31
      4-3-  اعتبار سنجی الگوریتم جستجوگر تکاملی……………………………………………………….. 42
                4-3-1-  مسائل مورد استفاده برای ارزیابی الگوریتم پیشنهادی …………………………………. 43
                4-3-2-  عملکرد الگوریتم جستجوگر تکاملی ………………………………………………… 55
                4-3-3-  مقایسه عملکرد الگوریتم جستجوگر تکاملی باICA, OICA , CICA3  ……………. 65
                4-3-4-  مقایسه عملکرد الگوریتم جستجوگر تکاملی با  RGA, PSO , GSA ………………. 67
                4-3-5-  مقایسه عملکرد الگوریتم جستجوگر تکاملی با  HS, IBA , ABS ………………….. 68
                4-3-6-  مقایسه عملکرد الگوریتم جستجوگر تکاملی با  BA, CS, LFA, FA ………………. 70
       4-4  فرایند تکاملی الگوریتم های فرا ابتکاری ………………………………………………………… 72
       4-5  جمع بندی …………………………………………………………………………………….. 75
5-  نتیجه گیری و پیشنهادها …………………………………………………………………………….. 76
       5-1-  نتیجه گیری ………………………………………………………………………………….. 77
       5-2-  پیشنهادها ……………………………………………………………………………………. 77
مراجع ……………………………………………………………………………………………………. 78
پیوست 1-  کد MATLAB حلقه اصلی الگوریتم جستجوگر تکاملی ………………………………………… 82
پیوست 2-  کد MATLAB حلقه فرعی الگوریتم جستجوگر تکاملی ………………………………………… 86
پیوست 3-  کد MATLAB مسائل ریاضی استفاده شده ……………………………………………………. 90

 

 

 

فهرست جداول

جدول 4-1  مقدار پارامتر های الگوریتم برای حل f Gol  و f Six  و f Bra  …………………………………….. 63
جدول 4-2  مقدار شاخص های ارزیابی عملکرد الگوریتم برای حل f Gol  و f Six  و f Bra  ……………………. 65
جدول 4-3  نتایج مقایسه عملکرد الگوریتم جستجوگر تکاملی  با  ICA, OICA , CICA3 ………………… 66
جدول 4-4  مقادیر برخی از پارامتر های الگوریتم جستجوگر تکاملی …………………………………………. 66
جدول 4-5  نتایج مقایسه عملکرد الگوریتم جستجوگر تکاملی  با   RGA, PSO , GSA …………………… 67
جدول 4-6  مقادیر برخی از پارامتر های الگوریتم جستجوگر تکاملی …………………………………………. 68
جدول 4-7  نتایج مقایسه عملکرد الگوریتم جستجوگر تکاملی  با  ABC, IBA, HS ……………………….. 69
جدول 4-8  مقادیر برخی از پارامتر های الگوریتم جستجوگر تکاملی …………………………………………. 70
جدول 4-9  نتایج مقایسه عملکرد الگوریتم جستجوگر تکاملی با LFA, FA, CS, BA ……………………… 71
جدول 4-10  مقادیر برخی از پارامتر های الگوریتم جستجوگر تکاملی ……………………………………….. 72

 

 

 

 

 

 

 

 

 

 

 

 

 

 

فهرست شکل ها

شكل 3-1  طبقه‌بندي انواع روش‌هاي بهينه‌سازي …………………………………………………………….. 19
شکل 4-1  فلوچارت الگوریتم جستجوگر تکاملی ……………………………………………………………. 33
شکل 4-2  نحوه حرکت جستجو گرها در ناحیه جواب ………………………………………………………. 34
شکل 4-3  حرکت جستجو گر به سمت بهترین جستجو گر ………………………………………………….. 39
شکل 4-4  شبه کد حلقه اصلی الگوریتم جستجوگر تکاملی ………………………………………………….. 41
شکل 4-5  شبه کد حلقه اصلی الگوریتم جستجوگر تکاملی ………………………………………………….. 42
شکل 4-6  نمودار سه بعدی تابع F1  ……………………………………………………………………….. 44
شکل 4-7  نمودار سه بعدی تابع  Goldstein-Price ……………………………………………………… 45
شکل 4-8  نمودار سه بعدی تابع  Six-hump camel back ………………………………………………. 46
شکل 4-9  نمودار سه بعدی تابع  Branins ………………………………………………………………… 47
شکل 4-10  نمودار سه بعدی تابع  Rosenbrock …………………………………………………………. 48
شکل 4-11  نمودار سه بعدی تابع  Sphere ……………………………………………………………….. 49
شکل 4-12  نمودار سه بعدی تابع  Schwefel …………………………………………………………….. 50
شکل 4-13  نمودار سه بعدی تابع  Ackley ……………………………………………………………….. 51
شکل 4-14  نمودار سه بعدی تابع  Rastrigin …………………………………………………………….. 52
شکل 4-15  نمودار سه بعدی تابع  Easom ……………………………………………………………….. 53
شکل 4-16  نمودار سه بعدی تابع  Griewank ……………………………………………………………. 54
شکل 4-17 موقعیت مکانی جستجوگرها قبل از عملیات جستجو در تکرار اول ……………………………….. 56
شکل 4-18 موقعیت مکانی جستجوگرها بعد از عملیات جستجو در تکرار اول ……………………………….. 56
شکل 4-19 موقعیت مکانی جستجوگرها قبل از عملیات جستجو در تکرار دوم ……………………………….. 57
شکل 4-20 موقعیت مکانی جستجوگرها بعد از عملیات جستجو در تکرار دوم ……………………………….. 57
شکل 4-21 موقعیت مکانی جستجوگرها قبل از عملیات جستجو در تکرار سوم ………………………………. 58
شکل 4-22 موقعیت مکانی جستجوگرها بعد از عملیات جستجو در تکرار سوم ………………………………. 58
شکل 4-23 موقعیت مکانی جستجوگر ها قبل از عملیات جستجو در تکرار چهارم ……………………………. 59
شکل 4-24 موقعیت مکانی جستجوگر ها بعد از عملیات جستجو در تکرار چهارم ……………………………. 59
شکل 4-25 موقعیت مکانی جستجوگرها قبل از عملیات جستجو در تکرار پنجم ………………………………. 60
شکل 4-26 موقعیت مکانی جستجوگرها بعد از عملیات جستجو در تکرار پنجم ………………………………. 60
شکل 4-27 عملکرد الگوریتم جستجوگر تکاملی برای تابع F1 ……………………………………………….. 62
شکل 4-28 عملکرد الگوریتم جستجوگر تکاملی برای تابع Six-hump camel back ……………………… 63
شکل 4-29 عملکرد الگوریتم جستجوگر تکاملی برای تابع Branins ………………………………………… 64
شکل 4-30 عملکرد الگوریتم جستجوگر تکاملی برای تابع Goldstein-Price ……………………………… 64
شکل 4-31  نمایش سه بعدی حراررتی تابع F2  از نمای بالا…………………………………………………. 74
شکل 4-32  نمایش سه بعدی حراررتی تابع F2 …………………………………………………………….. 74
شکل 4-33  نمایش سه بعدی حراررتی تابع F2   و نقطه بهینه این تابع ……………………………………….. 75

–  مقدمه

در ریاضیات و علوم رایانه یک مسأله بهینه سازی، مسأله یافتن بهترین راه حل از میان همه راه حل های عملی می باشد. مسأله های بهینه سازی می تواند به دو دسته تقسیم شود که متغیرها پیوسته یا گسسته باشند. روش های حل متفاوتی برای این گونه مسائل وجود دارند که به سه دسته روش های سنتی ریاضی، روش های ابتکاری و روش های فرا ابتکاری تقسیم می شوند. در اکثر مسائل بهینه سازی با افزایش ابعاد مساله زمان حل آن نیز به صورت نمایی افزایش پیدا می کند. به این گونه مسائل، مسائل بهینه سازی ترکیبیاتی گفته می شود. به همین علت یکی از بهترین گزینه های برای حل مسائل بهینه سازی استفاده از الگوریتم های فرا ابتکاری است. مهمترین علت استفاده از الگوریتم های فرا ابتکاری، بدست آوردن یک جواب مناسب در زمان مناسب است. از همین رو است که توسعه و میزان استفاده از الگوریتم های فرا ابتکاری به شدت رشد داشته است.

1-2–  تعریف مساله

هدف از بهينه‌سازي يافتن بهترين جواب قابل قبول با توجه به محدوديت‌ها و نيازهاي مسأله است. بهينه‌سازي يك فعاليت مهم و تعيين‌كننده در بسیاری ار زمینه های علمی، اقتصادی، صنعتی و غيره است. بسياري از مسائل بهينه‌سازي در مهندسي، طبيعتاً پيچيده‌تر و مشكل‌تر از آن هستند كه با روش‌هاي مرسوم بهينه ‌سازي نظير روش های برنامه‌ريزي رياضي و نظاير آن قابل حل باشند. از جمله راه ‌حل‌هاي موجود در برخورد با اين گونه مسائل، استفاده از الگوريتم‌هاي تکاملی است. دلیل دیگر استفاده از الگوریتم های تکاملی، زمان بسیار زیاد و غیر ممکن روش های دقیق ریاضی برای حل مسائلی با پارامتر های زیاد و پیچیده است. در سال‌هاي اخير يكي از مهمترين و اميدبخش‌ترين تحقيقات، «روش‌هاي ابتكاري برگرفته از طبيعت» بوده است. اين روش‌ها شباهت‌هايي با سيستم‌هاي اجتماعي و يا طبيعي دارند. ساختار ‌آنها برگرفته شده از روند تکاملی موجود در آن سیستم می باشد كه در حل مسائل با ساختار پیچیده نتايج بسيار خوبی داشته است. در اکثر این گونه الگوریتم ها عملیات جستجو با تولید یک جمعیت تصادفی در ناحیه جستجو شروع می شود. سپس با استفاده هوش محاسباتی موجود در الگوریتم، جواب ها حرکت داده می شوند. این جابجایی به نحوی می باشد که بعد از گذشتن چند گام جمعیت به سمت نقطه بهینه همگرا می شوند. تفاوت اصلی الگوریتم های تکاملی در همین نحوه جابجایی جمعیت می باشد. در سال های اخیر توسعه و استفاده از الگوریتم های تکاملی رشد چشم گیری داشته است. هر یک از آن ها دارای نقاط ضعف و قوتی بوده است به طوری که هر از چند گاهی شاهد معرفی الگوریتمی جدید هستیم که برتری خود را نسبت به تعدادی از الگوریتم های قبلی نشان می دهد.

در این  پايان­نامه، یک الگوریتم جدید برای حل مسائل بهینه سازی پیوسته معرفی شده است. این الگوریتم مبتنی بر یک منطق ساده جستجو است. برای ارزیابی عملکرد الگوریتم های فرا ابتکاری از مسائل ریاضی موجود در ادبیات استفاده می شود. برای این الگویتم نیز از 11 مساله ریاضی برای مقایسه و ارزیابی عملکرد الگوریتم پیشنهادی استفاده شده است. در این مقایسات نتایج الگوریتم پیشنهادی با نتایج یازده الگوریتم فرا ابتکاری مقایسه شده است. این الگوریتم ها جزء پر رجوع ترین الگوریتم های فرا ابتکاری در این زمینه هستند.

1-3–  هدف تحقیق

هدف از این پایان نامه معرفی یک الگوریتم فراابتکاری کارا برای حل مسائل بهینه سازی پیوسته است که بتواند نسبت به اغلب الگوریتم های فراابتکاری مشهور دارای برتری باشد.

1-4–  فرضیات تحقیق

در اين پایان نامه، فرضيات مسأله وجود ندارد و طراحی الگوریتم تکاملی جستجوگر فقط برای مسائل بهینه سازی پیوسته صورت مي­گيرد.

تعداد صفحه : 105

قیمت : 14700 تومان

———–

——-

پشتیبانی سایت :               [email protected]

در صورتی که مشکلی با پرداخت آنلاین دارید می توانید مبلغ مورد نظر برای هر فایل را کارت به کارت کرده و فایل درخواستی و اطلاعات واریز را به ایمیل ما ارسال کنید تا فایل را از طریق ایمیل دریافت کنید.

--  --