چكيده
الگوريتم هاي بهينه سازي به دو دسته دقيق و تقريبي دسته بندي مي شوند. الگوريتم دقيق قادر به يافتن جواب دقيق است كه در مسائل سخت كارايي كافي ندارد و بسته به ابعاد مسئله, زمان اجراي آن افزايش مي يابد، اما الگوريتم تقريبي قادر به يافتن جواب نزديك به بهينه در زمان كوتاه براي مسائل سخت است.
الگوريتم هاي فراابتكاري نوعي از الگوريتم هاي تصادفي هستند كه براي يافتن پاسخ بهينه به كار مي روند. در واقع الگوريتم هاي فراابتكاري, يكي از انواع الگوريتم هاي بهينه سازي تقريبي هستند كه داراي راهكارهاي برون رفت از نقاط بهينه محلي هستند و قابليت كاربرد در طيف وسيعي از مسائل را دارند. اين الگوريتم ها توسط معيار هاي متفاوتي طبقه بندي مي شوند كه يكي از آن ها مبتني بر مسير و ديگري مبتني بر جمعيت است. در مبتني بر مسير در فرآيند جستجو, يك جواب را تغيير مي دهند و در الگوريتم مبتني بر جمعيت در حين جستجو, جمعيتي از جواب ها در نظر گرفته مي شود.مثال هايي از اين الگوريتم ها, الگوريتم بهينه سازي ماهي الكتريكي, الگوريتم كرم شب تاب و ... است.
براي مقايسه اين الگوريتم ها توابع تست يك هدفه يا چند هدفه اي موجود است كه سرعت همگرايي الگوريتم, ميزان دقت الگوريتم, قدرت و نيرومندي الگوريتم و عملكرد كلي الگوريتم را بررسي مي كند. يكي از اين توابع , تابع شانه تخم مرغي، تابع تست تك هدفه با چندين كمينه محلي است.
در اين پايان نامه رويكردهاي مبتني بر بهينه سازي فراابتكاري براي مسئله برنامه ريزي مسير ربات متحرك ارائه مي شود. به اين منظور چند الگوريتم مبتني برجمعيت ارائه و مفصلا توضيح داده مي شوند. بعد از مدل سازي الگوريتم ها با متلب كارايي هر الگوريتم با تابع تست شانه تخم مرغي ارزيابي مي شود و با مقايسه نتايج, مي توان الگوريتم ها را رتبه بندي كرد و براي مسائل مسير يابي ربات, مورد استفاده قرار داد.
