کلمات کلیدیبهینه سازی هوشمند، الگوریتم های فرا ابتکاری، بهینه سازی سراسری، الگوریتم جستجوگر تکاملی، بهینه سازی پیوسته فهرست مطالبعنوانصفحه1- کلیات تحقیق .........11-1- مقدمه...........21 -2- تعریف مساله ............21 -3- هدف تحقیق .......31 -4- فرضیات تحقیق .......31 -5- اهمیت و ضرورت تحقیق ................................................................................31 -6- خلاصه فصل های آتی....................................................................................42- ادبیات و پیشینه تحقیق ............................................................................................52-1- مقدمه ......................................................................................................62-2- مرور ادبیات الگوریتم های فرا ابتکاری ...................................................................62-3- جمع بندی .................................................................................................153- زمینه های علمی تحقیق..........................................................................................163-1- مقدمه ......................................................................................................173-2- مسائل بهینه سازی ........................................................................................173-3- بررسي روشهاي جستجو و بهينهسازي .................................................................183-3-1-روشهاي شمارشي ...........................................................................193-3-2-روشهاي محاسباتي ..........................................................................203-3-3- روشهاي ابتكاري و فرا ابتکاری .............................................................213-4- مسائل بهينهسازي تركيبي .................................................................................213-5-روشهای حل مسائل بهينهسازي تركيبي ..................................................................233-5-1- روش های ابتکاری ...........................................................................243-5-1-1-آزادسازي .....................................................................243-5-1-2-تجزيه .........................................................................253-5-1-3-تكرار ..........................................................................253-5-1-4- روش توليد ستون............................................................253-5-1-5-جستجوي سازنده............................................................263-5-1-6-جستجوي بهبود يافته ........................................................263-5-1-7- روش جستجوي همسايه.....................................................273-5-2- روشهاي فرا ابتكاريبرگرفته از طبيعت ......................................................283-6- جمع بندی .................................................................................................294- ارائه الگوریتم جدید پیشنهادی...................................................................................304-1- مقدمه ......................................................................................................314-2- الگوریتم جستجوگر تکاملی............................... (Seeker Evolutionary Algorithm)314-3-اعتبار سنجی الگوریتم جستجوگر تکاملی.................................................................424-3-1- مسائل مورد استفاده برای ارزیابی الگوریتم پیشنهادی ........................................434-3-2- عملکرد الگوریتم جستجوگر تکاملی.........................................................554-3-3- مقایسه عملکرد الگوریتم جستجوگر تکاملی باICA,OICA,CICA3 ................654-3-4- مقایسه عملکرد الگوریتم جستجوگر تکاملی با RGA, PSO , GSA...................674-3-5- مقایسه عملکرد الگوریتم جستجوگر تکاملی با HS, IBA , ABS.......................684-3-6- مقایسه عملکرد الگوریتم جستجوگر تکاملی باBA, CS, LFA, FA...................704-4 فرایند تکاملی الگوریتم های فرا ابتکاری ..................................................................724-5 جمع بندی ..................................................................................................755- نتیجه گیری و پیشنهادها.........................................................................................765-1- نتیجه گیری ...............................................................................................775-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-1- مقدمهدر ریاضیاتو علوم رایانهیک مسأله بهینه سازی، مسأله یافتن بهترین راه حل از میان همه راه حل های عملی می باشد. مسأله های بهینه سازی می تواند به دو دسته تقسیم شود که متغیرها پیوسته یا گسسته باشند. روش های حل متفاوتی برای این گونه مسائل وجود دارند که به سه دسته روش های سنتی ریاضی، روش های ابتکاری و روش های فرا ابتکاری تقسیم می شوند. در اکثر مسائل بهینه سازی با افزایش ابعاد مساله زمان حل آن نیز به صورت نمایی افزایش پیدا می کند. به این گونه مسائل، مسائل بهینه سازی ترکیبیاتی گفته می شود. به همین علت یکی از بهترین گزینه های برای حل مسائل بهینه سازی استفاده از الگوریتم های فرا ابتکاری است. مهمترین علت استفاده از الگوریتم های فرا ابتکاری، بدست آوردن یک جواب مناسب در زمان مناسب است. از همین رو است که توسعه و میزان استفاده از الگوریتم های فرا ابتکاری به شدت رشد داشته است.1-2- تعریف مسالههدف از بهينهسازي يافتن بهترين جواب قابل قبول با توجه به محدوديتها و نيازهاي مسأله است. بهينهسازي يك فعاليت مهم و تعيينكننده در بسیاری ار زمینه های علمی، اقتصادی، صنعتی و غيره است. بسياري از مسائل بهينهسازي در مهندسي، طبيعتاً پيچيدهتر و مشكلتر از آن هستند كه با روشهاي مرسوم بهينه سازي نظير روش های برنامهريزي رياضي و نظاير آن قابل حل باشند. از جمله راه حلهاي موجود در برخورد با اين گونه مسائل، استفاده از الگوريتمهاي تکاملی است. دلیل دیگر استفاده از الگوریتم های تکاملی، زمان بسیار زیاد و غیر ممکن روش های دقیق ریاضی برای حل مسائلی با پارامتر های زیاد و پیچیده است. در سالهاي اخير يكي از مهمترين و اميدبخشترين تحقيقات،«روشهاي ابتكاري برگرفته از طبيعت» بوده است. اين روشها شباهتهايي با سيستمهاي اجتماعي و يا طبيعي دارند. ساختار آنها برگرفته شده از روند تکاملی موجود در آن سیستم می باشد كه در حل مسائل با ساختار پیچیده نتايج بسيار خوبی داشته است. در اکثر این گونه الگوریتم ها عملیات جستجو با تولید یک جمعیت تصادفی در ناحیه جستجو شروع می شود. سپس با استفاده هوش محاسباتی موجود در الگوریتم، جواب ها حرکت داده می شوند. این جابجایی به نحوی می باشد که بعد از گذشتن چند گام جمعیت به سمت نقطه بهینه همگرا می شوند. تفاوت اصلی الگوریتم های تکاملی در همین نحوه جابجایی جمعیت می باشد. در سال های اخیر توسعه و استفاده از الگوریتم های تکاملی رشد چشم گیری داشته است. هر یک از آن ها دارای نقاط ضعف و قوتی بوده است به طوری که هر از چند گاهی شاهد معرفی الگوریتمی جدید هستیم که برتری خود را نسبت به تعدادی از الگوریتم های قبلی نشان می دهد.در این پاياننامه، یک الگوریتم جدید برای حل مسائل بهینه سازی پیوسته معرفی شده است. این الگوریتم مبتنی بر یک منطق ساده جستجو است. برای ارزیابی عملکرد الگوریتم های فرا ابتکاری از مسائل ریاضی موجود در ادبیات استفاده می شود. برای این الگویتم نیز از 11 مساله ریاضی برای مقایسه و ارزیابی عملکرد الگوریتم پیشنهادی استفاده شده است. در این مقایسات نتایج الگوریتم پیشنهادی با نتایج یازده الگوریتم فرا ابتکاری مقایسه شده است. این الگوریتم ها جزء پر رجوع ترین الگوریتم های فرا ابتکاری در این زمینه هستند.1-3- هدف تحقیقهدف از این پایان نامه معرفی یک الگوریتم فراابتکاری کارا برای حل مسائل بهینه سازی پیوسته است که بتواند نسبت به اغلب الگوریتم های فراابتکاری مشهور دارای برتری باشد.1-4- فرضیات تحقیقدر اين پایان نامه، فرضيات مسأله وجود ندارد و طراحی الگوریتم تکاملی جستجوگر فقط برای مسائل بهینه سازی پیوسته صورت ميگيرد.1-5- اهمیت و ضرورت تحقیقگستره استفاده از الگوریتم های فراابتکاری در علوم مختلف به خصوص مهندسی صنایع در طی سال های گذشته بسیار زیاد بوده است.تعداد ارجاعات به مقالات اصلی این الگوریتم ها خود گواه این امر است. در ادامه به تعدادی از این موارد اشاره می شود.تعداد ارجاعات بسیار زیاد به مقالات الگوریتم های فراابتکاری نشان دهنده اهمیت فراوان این روش ها است. روش حل یا پدیده علمی که وسعت استفاده از آنها به این شکل باشد بسیار اندک است.1-6- خلاصه فصل های آتیدر فصل دوم به مرور ادبیات الگوریتم های فرا ابتکاری پرداخته خواهد شد. الگوریتم هایی که در این فصل مرور می شود شامل الگوریتم ژنتیک، الگوريتم آنيلينگ شبيهسازي، الگوریتم ایمنی مصنوعی، الگوریتم جستجوی ممنوعه، الگوریتم بهینهسازی کلونی مورچه، الگوریتم اجتماع ذرات، تکامل تفاضلی، الگوریتم جستجوی هارمونی، جستجوی فاخته، الگوریتم دستهی ماهیهاي مصنوعی، الگوریتم کرم شب تاب، الگوریتم خفاش، الگوریتم جستجوی گرانشی، الگوریتم کلونی زنبور عسل، الگوریتم رقابت استعماری، الگوریتم بهینه سازی فاخته است.در فصل سوم به زمینه های علمی تحقیق پرداخته می شود. در این فصل روش های مختلف جستجو و بهینه سازی مورد بحث قرار می گیرد. مسائل بهینه سازی ترکیبیاتی و روش های حل آن شرح داده می شود.در فصل چهارم ساختار الگوریتم جستجوگر تکاملی شرح داده خواهد شد و سپس با استفاده از چندین مساله ریاضی عملکرد آن با معروف ترین الگوریتم های فرا ابتکاری مورد مقایسه قرار خواهد گرفت.فصل پنجم مربوط به نتیجه گیری و پیشنهادات آتی تحقیق خواهد بود. فصل دومادبیات و پیشینه تحقیق 2-1- مقدمهدر سالهای دهه 1950 برنامه نویسی کامپیوترهای اولیه توسط تغییر سیم ها و تنظیم هزاران کلید و سوییچ انجام می شد. بعد از آن افراد به دنبال ابزارهای سریع تر و راحتتری برای برنامه نویسی بودند. در اواخر دهه 1950 مفسرهای زبان های طبیعی و کامپایلرهای پا به عرصه ظهور گذاشتند. در این سال ها بود که زبان های برنامه نویسیبه منظور استفاده در دنیای نرم افزارهای تجاری عرضه شدند. این امر باعث شد تا آشنایی با زبان های برنامه نویسی به صورت عام در بین متخصصان رواج پیدا کند. بعد از این رویداد مهم اکثر دانشمندان در زمینه های مختلف علمی سعی کردند از زبان برنامه نویسی استفاده کنند. یکی از موارد استفاده از زبان های برنامه نویسی، علم ریاضی و انجام محاسبات ریاضی بود. زمان حل بسیار کمتر این روش نسبت به حل دستی باعث شد تا سرعت استفاده از برنامه نویسی در شاخه های مختلف ریاضی یه شدت رشد کند. در دهه 1970 برای اولین بار دانشمندان برای حل مسائل بهینه سازی ترکیبیاتی از الگوریتم های فرا ابتکاری استفاده کردند. آن ها برای پیاده سازی الگوریتم ها از زبان برنامه نویسی استفاده کردند. نتیجه این کار بدست آمدن جواب های مناسب در زمان مناسب برای مسائل بهینه سازی ترکیبیاتی با اندازه بزرگ بود. تا آن زمان برای این گونه مسائل به دلیل زمان حل بسیار زیاد جواب مناسبی یافت نشده بود.
الگوریتم تکاملی جستجوگر ، یک الگوریتم جدید برای مسائل بهینه سازی پیوسته word
کلمات کلیدیبهینه سازی هوشمند، الگوریتم های فرا ابتکاری، بهینه سازی سراسری، الگوریتم جستجوگر تکاملی، بهینه سازی پیوسته فهرست مطالبعنوانصفحه1- کلیات تحقیق .........11-1- مقدمه...........21 -2- تعریف مساله ............21 -3- هدف تحقیق .......31 -4- فرضیات تحقیق .......31 -5- اهمیت و ضرورت تحقیق ................................................................................31 -6- خلاصه فصل های آتی....................................................................................42- ادبیات و پیشینه تحقیق ............................................................................................52-1- مقدمه ......................................................................................................62-2- مرور ادبیات الگوریتم های فرا ابتکاری ...................................................................62-3- جمع بندی .................................................................................................153- زمینه های علمی تحقیق..........................................................................................163-1- مقدمه ......................................................................................................173-2- مسائل بهینه سازی ........................................................................................173-3- بررسي روشهاي جستجو و بهينهسازي .................................................................183-3-1-روشهاي شمارشي ...........................................................................193-3-2-روشهاي محاسباتي ..........................................................................203-3-3- روشهاي ابتكاري و فرا ابتکاری .............................................................213-4- مسائل بهينهسازي تركيبي .................................................................................213-5-روشهای حل مسائل بهينهسازي تركيبي ..................................................................233-5-1- روش های ابتکاری ...........................................................................243-5-1-1-آزادسازي .....................................................................243-5-1-2-تجزيه .........................................................................253-5-1-3-تكرار ..........................................................................253-5-1-4- روش توليد ستون............................................................253-5-1-5-جستجوي سازنده............................................................263-5-1-6-جستجوي بهبود يافته ........................................................263-5-1-7- روش جستجوي همسايه.....................................................273-5-2- روشهاي فرا ابتكاريبرگرفته از طبيعت ......................................................283-6- جمع بندی .................................................................................................294- ارائه الگوریتم جدید پیشنهادی...................................................................................304-1- مقدمه ......................................................................................................314-2- الگوریتم جستجوگر تکاملی............................... (Seeker Evolutionary Algorithm)314-3-اعتبار سنجی الگوریتم جستجوگر تکاملی.................................................................424-3-1- مسائل مورد استفاده برای ارزیابی الگوریتم پیشنهادی ........................................434-3-2- عملکرد الگوریتم جستجوگر تکاملی.........................................................554-3-3- مقایسه عملکرد الگوریتم جستجوگر تکاملی باICA,OICA,CICA3 ................654-3-4- مقایسه عملکرد الگوریتم جستجوگر تکاملی با RGA, PSO , GSA...................674-3-5- مقایسه عملکرد الگوریتم جستجوگر تکاملی با HS, IBA , ABS.......................684-3-6- مقایسه عملکرد الگوریتم جستجوگر تکاملی باBA, CS, LFA, FA...................704-4 فرایند تکاملی الگوریتم های فرا ابتکاری ..................................................................724-5 جمع بندی ..................................................................................................755- نتیجه گیری و پیشنهادها.........................................................................................765-1- نتیجه گیری ...............................................................................................775-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-1- مقدمهدر ریاضیاتو علوم رایانهیک مسأله بهینه سازی، مسأله یافتن بهترین راه حل از میان همه راه حل های عملی می باشد. مسأله های بهینه سازی می تواند به دو دسته تقسیم شود که متغیرها پیوسته یا گسسته باشند. روش های حل متفاوتی برای این گونه مسائل وجود دارند که به سه دسته روش های سنتی ریاضی، روش های ابتکاری و روش های فرا ابتکاری تقسیم می شوند. در اکثر مسائل بهینه سازی با افزایش ابعاد مساله زمان حل آن نیز به صورت نمایی افزایش پیدا می کند. به این گونه مسائل، مسائل بهینه سازی ترکیبیاتی گفته می شود. به همین علت یکی از بهترین گزینه های برای حل مسائل بهینه سازی استفاده از الگوریتم های فرا ابتکاری است. مهمترین علت استفاده از الگوریتم های فرا ابتکاری، بدست آوردن یک جواب مناسب در زمان مناسب است. از همین رو است که توسعه و میزان استفاده از الگوریتم های فرا ابتکاری به شدت رشد داشته است.1-2- تعریف مسالههدف از بهينهسازي يافتن بهترين جواب قابل قبول با توجه به محدوديتها و نيازهاي مسأله است. بهينهسازي يك فعاليت مهم و تعيينكننده در بسیاری ار زمینه های علمی، اقتصادی، صنعتی و غيره است. بسياري از مسائل بهينهسازي در مهندسي، طبيعتاً پيچيدهتر و مشكلتر از آن هستند كه با روشهاي مرسوم بهينه سازي نظير روش های برنامهريزي رياضي و نظاير آن قابل حل باشند. از جمله راه حلهاي موجود در برخورد با اين گونه مسائل، استفاده از الگوريتمهاي تکاملی است. دلیل دیگر استفاده از الگوریتم های تکاملی، زمان بسیار زیاد و غیر ممکن روش های دقیق ریاضی برای حل مسائلی با پارامتر های زیاد و پیچیده است. در سالهاي اخير يكي از مهمترين و اميدبخشترين تحقيقات،«روشهاي ابتكاري برگرفته از طبيعت» بوده است. اين روشها شباهتهايي با سيستمهاي اجتماعي و يا طبيعي دارند. ساختار آنها برگرفته شده از روند تکاملی موجود در آن سیستم می باشد كه در حل مسائل با ساختار پیچیده نتايج بسيار خوبی داشته است. در اکثر این گونه الگوریتم ها عملیات جستجو با تولید یک جمعیت تصادفی در ناحیه جستجو شروع می شود. سپس با استفاده هوش محاسباتی موجود در الگوریتم، جواب ها حرکت داده می شوند. این جابجایی به نحوی می باشد که بعد از گذشتن چند گام جمعیت به سمت نقطه بهینه همگرا می شوند. تفاوت اصلی الگوریتم های تکاملی در همین نحوه جابجایی جمعیت می باشد. در سال های اخیر توسعه و استفاده از الگوریتم های تکاملی رشد چشم گیری داشته است. هر یک از آن ها دارای نقاط ضعف و قوتی بوده است به طوری که هر از چند گاهی شاهد معرفی الگوریتمی جدید هستیم که برتری خود را نسبت به تعدادی از الگوریتم های قبلی نشان می دهد.در این پاياننامه، یک الگوریتم جدید برای حل مسائل بهینه سازی پیوسته معرفی شده است. این الگوریتم مبتنی بر یک منطق ساده جستجو است. برای ارزیابی عملکرد الگوریتم های فرا ابتکاری از مسائل ریاضی موجود در ادبیات استفاده می شود. برای این الگویتم نیز از 11 مساله ریاضی برای مقایسه و ارزیابی عملکرد الگوریتم پیشنهادی استفاده شده است. در این مقایسات نتایج الگوریتم پیشنهادی با نتایج یازده الگوریتم فرا ابتکاری مقایسه شده است. این الگوریتم ها جزء پر رجوع ترین الگوریتم های فرا ابتکاری در این زمینه هستند.1-3- هدف تحقیقهدف از این پایان نامه معرفی یک الگوریتم فراابتکاری کارا برای حل مسائل بهینه سازی پیوسته است که بتواند نسبت به اغلب الگوریتم های فراابتکاری مشهور دارای برتری باشد.1-4- فرضیات تحقیقدر اين پایان نامه، فرضيات مسأله وجود ندارد و طراحی الگوریتم تکاملی جستجوگر فقط برای مسائل بهینه سازی پیوسته صورت ميگيرد.1-5- اهمیت و ضرورت تحقیقگستره استفاده از الگوریتم های فراابتکاری در علوم مختلف به خصوص مهندسی صنایع در طی سال های گذشته بسیار زیاد بوده است.تعداد ارجاعات به مقالات اصلی این الگوریتم ها خود گواه این امر است. در ادامه به تعدادی از این موارد اشاره می شود.تعداد ارجاعات بسیار زیاد به مقالات الگوریتم های فراابتکاری نشان دهنده اهمیت فراوان این روش ها است. روش حل یا پدیده علمی که وسعت استفاده از آنها به این شکل باشد بسیار اندک است.1-6- خلاصه فصل های آتیدر فصل دوم به مرور ادبیات الگوریتم های فرا ابتکاری پرداخته خواهد شد. الگوریتم هایی که در این فصل مرور می شود شامل الگوریتم ژنتیک، الگوريتم آنيلينگ شبيهسازي، الگوریتم ایمنی مصنوعی، الگوریتم جستجوی ممنوعه، الگوریتم بهینهسازی کلونی مورچه، الگوریتم اجتماع ذرات، تکامل تفاضلی، الگوریتم جستجوی هارمونی، جستجوی فاخته، الگوریتم دستهی ماهیهاي مصنوعی، الگوریتم کرم شب تاب، الگوریتم خفاش، الگوریتم جستجوی گرانشی، الگوریتم کلونی زنبور عسل، الگوریتم رقابت استعماری، الگوریتم بهینه سازی فاخته است.در فصل سوم به زمینه های علمی تحقیق پرداخته می شود. در این فصل روش های مختلف جستجو و بهینه سازی مورد بحث قرار می گیرد. مسائل بهینه سازی ترکیبیاتی و روش های حل آن شرح داده می شود.در فصل چهارم ساختار الگوریتم جستجوگر تکاملی شرح داده خواهد شد و سپس با استفاده از چندین مساله ریاضی عملکرد آن با معروف ترین الگوریتم های فرا ابتکاری مورد مقایسه قرار خواهد گرفت.فصل پنجم مربوط به نتیجه گیری و پیشنهادات آتی تحقیق خواهد بود. فصل دومادبیات و پیشینه تحقیق 2-1- مقدمهدر سالهای دهه 1950 برنامه نویسی کامپیوترهای اولیه توسط تغییر سیم ها و تنظیم هزاران کلید و سوییچ انجام می شد. بعد از آن افراد به دنبال ابزارهای سریع تر و راحتتری برای برنامه نویسی بودند. در اواخر دهه 1950 مفسرهای زبان های طبیعی و کامپایلرهای پا به عرصه ظهور گذاشتند. در این سال ها بود که زبان های برنامه نویسیبه منظور استفاده در دنیای نرم افزارهای تجاری عرضه شدند. این امر باعث شد تا آشنایی با زبان های برنامه نویسی به صورت عام در بین متخصصان رواج پیدا کند. بعد از این رویداد مهم اکثر دانشمندان در زمینه های مختلف علمی سعی کردند از زبان برنامه نویسی استفاده کنند. یکی از موارد استفاده از زبان های برنامه نویسی، علم ریاضی و انجام محاسبات ریاضی بود. زمان حل بسیار کمتر این روش نسبت به حل دستی باعث شد تا سرعت استفاده از برنامه نویسی در شاخه های مختلف ریاضی یه شدت رشد کند. در دهه 1970 برای اولین بار دانشمندان برای حل مسائل بهینه سازی ترکیبیاتی از الگوریتم های فرا ابتکاری استفاده کردند. آن ها برای پیاده سازی الگوریتم ها از زبان برنامه نویسی استفاده کردند. نتیجه این کار بدست آمدن جواب های مناسب در زمان مناسب برای مسائل بهینه سازی ترکیبیاتی با اندازه بزرگ بود. تا آن زمان برای این گونه مسائل به دلیل زمان حل بسیار زیاد جواب مناسبی یافت نشده بود.