معرفی انواع الگوریتم‌های فراابتکاری/پایان نامه بهینه سازی شبیه سازی برنامه تولید

دانلود پایان نامه

معرفی انواع الگوریتم‌های فراابتکاری

2-14-1- الگوریتم نزول

یکی از انواع الگوریتم‌های فراابتکاری، یک الگوریتم ساده با نام الگوریتم نزول است که از کارایی پایینی برخوردار می‌باشد.

الگوریتم نزول روشی است که جستجو را از یک جواب اولیه شروع کرده و در هر تکرار جواب فعلی را با یک جواب بهتر که در همسایگی آن است، جایگزین می‌کند. این روش تنها حرکت به سمت جواب‌هایی را مجاز دانسته که تابع هدف فعلی را بهبود بخشد و هنگامی که دیگر جواب بهتری پیدا نشود، اجرای الگوریتم به پایان می‌رسد. جواب نهایی یافت شده توسط این الگوریتم، جواب بهینه محلی نامیده می‌شود. به‌طوری که این جواب یا خوب است یا دست کم از جواب‌های همسایگی خود بهتر است. یکی از نواقص آشکار الگوریتم نزول این است که با احتمال زیاد یک جواب بهینه محلی، بهینه مطلق نخواهد بود و تابع هدف را به ازای همه جواب‌های منطقه موجه بهینه نخواهد کرد.]8[

2-14-1-1- مراحل اجرای الگوریتم نزول

حل مسائل بهینه‌سازی شبیه‌سازی طبق مراحل زیر صورت می‌گیرد:

  1. تولید اعداد تصادفی
  2. انتخاب جواب اولیه
  3. انتخاب یک جواب در همسایگی
  4. پذیرش یا رد جواب جدید]8[

2-14-1-2- نقاط ضعف الگوریتم نزول

مهم‌ترین نقطه ضعف الگوریتم نزول این است که احتمال گرفتار شدن الگوریتم در دام نقاط بهینه محلی بسیار زیاد است. این موضوع ناشی از رویکرد حریصانه الگوریتم است که در پی‌یافتن نخستین جوابی است که از نقاط همسایگی خود بهتر است. الگوریتم‌های فراابتکاری به‌منظور گریز از چنین دام‌هایی از رویکردهای تمرکز و تنوع بهره می‌برند.]8[

 

2-14-2- شبیه‌سازی تبرید تدریجی

الگوریتم شبیه‌سازی تبرید تدریجی که در متون فارسی با عناوین شبیه‌سازی آنیل و الگوریتم شیشه یا کریستال نیز از آن یاد شده است را می‌توان از نظر سازوکار اجرا و فعالیت‌های برنامه‎نویسی موردنیاز، ساده‌ترین الگوریتم فراابتکاری دانست. این سادگی باعث نمی‌شود که کارایی این الگوریتم با دیده‌ تردید نگریسته شود. انتشارات متعددی را می‌توان ملاحظه کرد که از توانایی این الگوریتم در حل مسائل متنوع سود برده‌اند.]8[

2-14-2-1- تاریخچه و زمینه پیدایش

الگوریتم SA نخستین بار توسط کرک پاتریک در سال 1982 معرفی شد. این الگوریتم بر اساس مدل توسعه‌یافته توسط متروپلیس برای شبیه‌سازی فرآیند فیزیکی تبرید تدریجی شکل گرفته است. فیزیکدانان برای تغییر در وضعیت یک ماده از یک پارامتر مهم یعنی دما استفاده می‌کنند. تبرید تدریجی فرآیندی است که در آن رسیدن به وضعیت بهینه توسط کنترل دما صورت می‌پذیرد. در این فرآیند ابتدا ماده حرارت می‌بیند تا انرژی زیادی به آن وارد شود و پس از آن به آرامی سرد می‌شود به گونه‌ای که تا مدتی در هر سطحی از دما با قی بماند و سپس به سطح پایین‌تر دما برود. این استراتژی در سردکردن تدریجی باعث شکل‌گیری وضعیت جامد کریستالی می‌شود که وضعیتی پایدار است و متناظر با حداقل مطلق انرژی است. وضعیت متضاد آن زمانی است که ماده به سرعت سرد شود که منجر به وضعیت غیر متبلور خواهد شد. ساختار غیر متبلور متناظر با حداقل انرژی است.]8[

2-14-2-2- خط سیر الگوریتم تبرید تدریجی

الگوریتم تبرید تدریجی فرآیند حل مسئله را از یک جواب (معمولاً تصادفی) شروع می‌کند و برای یافتن جواب مسئله، در فضای منطقه موجه از یک نقطه به نقطه دیگر می‌رود تا زمانی که شرط توقف الگوریتم برقرار شود. طی جابجاشدن بین نقاط متفاوت، بهترین جواب به‌دست آمده توسط الگوریتم ذخیره شده و در آخر به‌عنوان جواب مطلوب مسئله ارائه می‌شود.]8[

یک تفاوت اساسی بین الگوریتم نزول و شبیه‌سازی تبرید تدریجی در این است که SA به جواب‌های بدتر از جواب جاری نیز شانس پذیرفته شدن می‌دهد. احتمال پذیرش جواب‌های بدتر، با افزایش تکرارهای حل مسئله کاهش می‌یاید.]8[

 

2-14-3- جستجوی ممنوع

الگوریتم جستجوی ممنوع (یا جستجوی ممنوعه) که ایده اساسی خود را از حافظه انسان گرفته است، در زمره الگوریتم‌های جستجو در همسایگی قرار می‌گیرد. این الگوریتم از نظر مفهومی همانند الگوریتم شبیه‌سازی تبرید تدریجی عمل می‌کند اما مجموعه قوانین و سازوکارهایی دارد که اجرای آن ‌را به عملکرد مغز شبیه می‌کند.]8[

 

2-14-3-1- تاریخچه و زمینه پیدایش

مشکلاتی که در مسائل بهینه‌سازی از جمله مسائل مربوط به حمل‌ونقل، لجستیک، برنامه‌ریزی مالی و برنامه‌ریزی تولید وجود دارد، باعث توسعه تکنیک‌های بهینه‌سازی مؤثر شده است. هدف از این تکنیک‌ها توسعه فرآیندهایی است که بتوانند با پیچیدگی مسائل بهینه‌سازی مواجه شوند. یکی از این روش‌ها الگوریتم جستجوی ممنوع است که توسط فرد گلاور معرفی شده است.]8[

واژه Tabu یا Taboo در لغت نامه وبستر[1] به معنی مفاهیمی است که دارای قدرت ماوراء الطبیعه بوده و استفاده و برقراری ارتباط با آن‌ها ممنوع می‌باشد. روش جستجوی ممنوع در ارتباط با ماوراءالطبیعه و ممنوعات آن نیست، بلکه ممنوعیت‌ها و محدودیت هایی را اعمال می‌کند تا یک فرآیند جستجو را به مناطقی هدایت کند که جواب‌های بهتری به دست می‌دهند. این روش بر اساس فرآیندهایی طراحی شده است که از مرزهای بهینگی محلی که به‌عنوان یک مانع عمل کرده، عبور می‌کنند و روش جستجوی ابتکاری را به گونه‌ای هدایت می‌کند که نقاط فراتر از بهینه محلی را مورد جستجو قرار دهند.]8[

2-14-3-2- خط سیر الگوریتم جستجوی ممنوع

الگوریتم جستجوی ممنوع همانند الگوریتم شبیه‌سازی تبرید تدریجی، مبتنی بر جستجو در همسایگی است. به گونه‌ای که در اطراف جواب جاری در پی یافتن جواب‌های جدید می‌باشد. شباهت دیگر دو الگوریتم در این است که الگوریتم جستجوی ممنوع نیز برای جواب‌های بدتر از جواب کنونی نیز شانس پذیرفته شدن قائل است. مهم‌ترین تفاوت دو الگوریتم در این است که SA در هر تکرار تنها به بررسی یکی از جواب‌های واقع در همسایگی می‌پردازد اما TS در هر تکرار چندین جواب را در اطراف جواب کنونی مورد بررسی قرار می‌دهد.]8[

به‌طور کلی و بدون درنظرگرفتن جزییات، در این الگوریتم فرآیند حل مسئله از یک نقطه منطقه موجه آغاز می‌شود و در هر تکرار از یک نقطه به نقطه دیگر منطقه مراجعه می‌شود تا شرط توقف برقرار شود. بهترین جوابی که در طی همه مراحل یافته شده است، ذخیره می‌گردد.]8[

2-14-4- الگوریتم مورچگان

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

2-14-4-1- تاریخچه و زمینه پیدایش

یکی از جالب‌ترین الگوهای رفتاری مورچگان توانایی گونه‌هایی از آن‌ها در پیدا کردن کوتاه‌ترین مسیر است. جمعیت (کلونی) مورچگان، زنبورهای عسل و یا به‌طور کلی گروهی از حشرات، سیستم‌های توزیع شده‌ای هستند که با وجود سادگی تک‌تک آن‌ها، یک سازمان اجتماعی ساختار یافته را به‌وجود می‌آورند. ایده اصلی الگوریتم مورچگان، قانون خود سازماندهی می‌باشد که اجازه می‌دهد رفتار بسیار موزون مورچه‌های واقعی در هماهنگ‎کردن مجموعه‌ای از کارگزارهای مصنوعی برای حل مسائل محاسباتی، مورد استفاده قرار گیرد. جنبه‌های مختلف رفتار کلونی مورچگان، الگوریتم‌های متفاوتی را به‌وجود آورده است. از این‌گونه رفتارها می‌توان به جستجو برای غذا، تقسیم کار، مرتب‌سازی در حین تخم‌گذاری و حمل‌ونقل مشارکتی اشاره کرد.]8[

2-14-4-2- خط سیر الگوریتم مورچگان

الگوریتم مورچگان برای حل یک مسئله، دارای روش خاص خود در جستجوی منطقه موجه می‌باشد. این الگوریتم یک نوع پردازش موازی را در ذات خود دارد. یعنی به‌طور هم‎زمان نواحی مختلفی را در منطقه مورد جستجو قرار می‌دهد. یعنی از این نظر مشابه با الگوریتم ژنتیک رفتار می‌کند و در هر تکرار، از یک مجموعه جواب به یک مجموعه جواب دیگر می‌رود. تفاوت الگوریتم ژنتیک و مورچگان در سازوکارهای تولید جواب‌های جدید است. در الگوریتم ژنتیک جواب‌های جدید مستقیماَ با ترکیب جواب‌های موجود حاصل می‌شوند (عملگر تقاطع). در حالی‌که در الگوریتم جمعیت مورچگان، جواب‌های تکرار جاری به‌طور غیر مستقیم یعنی به کمک فرمون، روی نحوه تولید جواب‌های جدید تاثیرگذار هستند.]8[

2-14-4-3- گونه‌های مختلف الگوریتم مورچگان

ایده‌های متفاوتی که برای قانون احتمال انتخاب مسیر، تبخیر و فرمون‌ریزی توسط محققان مختلف پیشنهاد شده است که به شکل‌های متنوعی از الگوریتم ACO انجامیده‌اند. رایج‌ترین شکل‌های این الگوریتم در ادامه معرفی می‌شوند:]8[

  1. سیستم مورچه
  2. سیستم مورچه نخبه‌گرا
  3. سیستم مورچه مبتنی بر رتبه‌بندی
  4. سیستم مورچه حداقل – حداکثر
  5. سیستم جمعیت مورچه‌ها

 

2-14-5Webster

دانلود پایان نامه