بخشی از پاورپوینت
اسلاید 1 :
چرا الگوریتمهای فرا ابتکاری؟
- برنامه‌ریزی غیر‌خطی
- Combinatorial explosion ( انفجار ترکیبی ) :کامپیوترها کمک چندانی نمی‌کنند!
- مسائل دشوار بهینه‌سازی امروزی
- بهینه محلی(Local Optimum)
اسلاید 2 :
مسائل ترکيبی(Combinatorial )
- ظاهر مسئله ساده ولی حل به سادگی امکان پذیر نیست (Combinatorial)
- Gary and Johnson(1970) به دشواری این مسائل اذعان کردند
- Nonpolynomial Problems مسائلی که با افزایش تعداد متغیرها بصورت نمایی رشد میکنند
- تابعی به نام تابع پیچیدگی زمانی (Time Complexity Function) در اینگونه مسائل مطرح می‌شود
- مثال : فروشنده دوره‌گرد ، دور همیلتونی،تخصیص n کار به m کارگر و...
اسلاید 3 :
مشکلات بهینه سازی مسائل ترکیبی
- بهینه سازی f(x1, x2,…, x100)
- xi متغیر صفر و یک و تابع f پیچیده است
- اندازه فضای جواب 2100 @ 1030
- امتحان کردن تمام اعضای فضای جواب نمی‌تواند جواب را بیابد
–با سرعت 1000 مقایسه در ثانیه
–اگر الگوریتم را در ابتدای آفرینش کره زمین نیز آغاز می‌کردیم
–تاکنون تنها 1 درصد فضای جواب را گشته بودیم!
اسلاید 4 :
جواب بهینه محلی نمی‌خواهیم...
procedure local search
begin
x = some initial starting point
while improve(x) ¹ ‘no’ do
x = improve(x)
return (x)
end
اسلاید 5 :
مثل کریستوف کلمب نباشیم!
- نمی‌دانست به کجا میرود!
- نمی‌دانست به کجا رسیده !
- نمی‌دانست از کجا برگشته!
- جستجو جهت یافتن جوابهای بهینه هرگز نباید این چنین باشند
- الگوریتمهای فراابتکاری راهنما و قطبنمای ما هستند
اسلاید 6 :
Tabu =?
- كلمه Tabu يا Taboo از زبان تانگان كه از شاخه هاي زبان پلي نزي مي باشد گرفته شده است.
- بوميان جزيره تانگا ازاين كلمه براي نشان دادن چيزهايي كه به علت مقدس بودن نبايد لمس شوند استفاده مي كردند.
اسلاید 7 :
جامع ترين منبع موجود در زمينه جستجوی ممنوع کتابی با همين عنوان مي باشد كه در ژوئن سال 1997 توسط فرد گلوور و مانوئل لاگونا و در 408صفحه منتشر شده است.
اسلاید 8 :
–Fred Glover : (1986)
–
–جستجوی ممنوع یک الگوریتم فرا ابتکاری است که بر روی یک الگوریتم ابتکاری دیگر اعمال می‌شود.رویکرد کلی الگوریتم جستجوی ممنوع ، جلوگیری از وقوع دور از طریق ممنوع کردن یا جریمه کردن حرکتهایی است که در تکرار بعدی ما را به نقطه‌ای تکراری در فضای جواب می‌برند.(که Tabu یا ممنوع نامیده می‌شوند)
اسلاید 9 :
اجزای جستجوی ممنوع
- کد کردن (بیان مسئله)
- تابع هدف
- جواب اولیه ( تصادفی یا بدست آوردنی)
- تعریف همسایگی
- اپراتور حرکت
- لیست ممنوع
- حافظه
- معیار آرمانی(Aspiration Criteria)
- معیار پایان دادن به جستجو
اسلاید 10 :
لیست ممنوعه
- هدف کلی جستجوی ممنوع فرار از دورهایی است که ما را در دام جوابهای بهینه محلی گرفتار میکنند
- طول لیست: ثابت یا دینامیک ( معمولا بین 7 تا 20)
- محتوای لیست: ویژگیهای ازاین جواب رفتن ، ویژگیهای به این جواب رسیدن ، ویژگیهای حرکت ... هرچه تعریف ممنوعیتها ریزتر باشد کمتر محدودکننده خواهد بود
