الگوریتم های فرا ابتکاری (متاهیوریستیک)

تعریف
الگوریتم‌های فراابتکاری یا فراتکاملی یا فرا اکتشافی نوعی از الگوریتم‌های تصادفی هستند که برای یافتن پاسخ بهینه به کار می‌روند.
روش‌ها و الگوریتم‌های بهینه سازی به دو دسته الگوریتم‌های دقیق (exact) و الگوریتم‌های تقریبی (approximate algorithms) تقسیم‌بندی می‌شوند. الگوریتم‌های دقیق قادر به یافتن جواب بهینه به صورت دقیق هستند اما در مورد مسائل بهینه سازی سخت کارایی کافی ندارند و زمان اجرای آن ها متناسب با ابعاد مسائل به صورت نمایی افزایش می‌یابد. الگوریتم‌های تقریبی قادر به یافتن جواب‌های خوب (نزدیک به بهینه) در زمان حل کوتاه برای مسائل بهینه‌سازی سخت هستند.
الگوریتم‌های تقریبی نیز به سه دسته الگوریتم‌های ابتکاری (heuristic) و
فراابتکاری(meta-heuristic) و فوق ابتکاری (hyper heuristic) بخش بندی می شوند.
دو مشکل اصلی الگوریتم‌های ابتکاری، گیر افتادن آنها در نقاط بهینه محلی، همگرایی زودرس به این نقاط است.
الگوریتم‌های فراابتکاری برای حل این مشکلات الگوریتم‌های ابتکاری ارائه شده‌اند. در واقع الگوریتم‌های فراابتکاری، یکی از انواع الگوریتم‌های بهینه‌سازی تقریبی هستند که دارای راهکارهای برونرفت از نقاط بهینه محلی هستند و قابلیت کاربرد در طیف گسترده ای از مسائل را دارند.

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

     الگوریتم تبرید شبیه سازی شده Algorithm Simulated Annealing

     الگوریتم رقابت استعماری Imperialist Competitive Algorithm

     الگوریتم کلونی مصنوعی زنبور عسل  Artificial bee colony algorithm

     الگوریتم کلونی مورچگان Ant Colony Search Algorithm

     الگوریتم ازدحام ذرات Particle Swarm Optimization

     الگوریتم جستجوی ممنوع Tabu Search

     الگوریتم کرم شب تاب Firefly Algorithm

     الگوریتم جستجوی گرانشی (GSA) Gravitational Search Algorithm

     الگوریتم جستجوی هارمونی Harmony Search Algorithm

الگوریتم جستجوی گرانشی

نیروی گرانشی

گرانش تمایل اجسام برای شتاب گرفتن به سوی یکدیگر است. در قانون گرانش نیوتن هر ذره، ذره دیگر را با نیروی گرانشی جذب می‌کند.

قانون دو نیوتن  

 

نیروی گرانشی در کهکشان

نیروی-گرانشی

مراحل الگوریتم GSA
گام اول :
• تشکیل یک سیستم مصنوعی با زمان گسسته در محیط مسئله
• موقعیت یابی اولیه برای عامل ها (اجرام)
• وضع قوانین حاکم و تنظیم پارامترها
گام دوم:
• گذر زمان، حرکت اجرام و به روز رسانی پارامترها تا پیش آمدن زمان توقف
الگوریتم جستجوی گرانشی
در ابتدای تشکیل سیستم، هر جرم بصورت تصادفی در یک نقطه از فضا جستجو می‌شود. مقدار اجرام با توجه به برازندگی هر عامل تعیین می‌شود.

جرم هر سیاره ؟

نیروی گرانشی وارد بر هر سیاره؟

سرعت هر سیاره؟

الگوریتم جستجوی گرانشی

الگوریتم جستجوی گرانشی

ثابت گرانشی

  • ثابت گرانش بزرگتر موجب تقویت توانایی کاوش و ثابت گرانش کوچک موجب تقویت توانایی بهره وری می گردد.
  • پس بهتر است در شروع این مقدار زیاد و به مرور زمان کم شود.
  • آزمایشات نشان داده که رابطه ی نمایی، مناسب است:

الگوریتم جستجوی گرانشی

الگوریتم جستجوی هارمونی

  • شخصی به نام Zong Woo Geem الگوریتم جستجوی هارمونی را ارائه نمود که طرح کلی آن برگرفته از رفتار موسیقی دان ها در ساخت یک موسیقی است.
  • در سال های2006 به بعد این الگوریتم بسیارمورد توجه قرار گرفته.
  • هارمونی به معنای هم آهنگی است. نوازندگان برای تولید یک موسیقی جدید از آلات موسیقی مختلفی استفاده می‌کنند و زیبایی موسیقی به هماهنگی بین نت‌های سازهای مختلف است.
  • در ساخت یک موسیقی هدف یافتن بهترین هارمونی و تولید زیباترین موسیقی ممکن است.
  • نوازندگان در هر بار اجرا سعی می‌کنند نت‌های بهتری انتخاب کنند تا در هر بار اجرا موسیقی تکامل بیشتری داشته و زیباتر گردد.
  • نوازندگان قطعه های نواخته شده را به خاطر می‌سپارند تا در هر بار قطعه جدید را با قطعات قبلی مقایسه کنند.

استفاده از هارمونی در الگوریتم  HS

فرض کنید k هارمونی توسط n نوازنده ساخته شده.

هر هارمونی جدید می تواند از تغییر در نت های هارمونی های قبلی ایجاد شود. به این معنا که نوازنده نت های خود را کمی تغییر می دهد.

این تغییر می تواند به یکی از سه روش زیر انجام گیرد:

1- در نظر گرفتن نت های موجود در حافظه

– انتخاب تصادفی

3-تنظیم زیر و بمی

{Do Re Mi Fa Sol La Si}

∆x = 1

∆x = 2

الگوریتم HS

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

1- مقدار دهی اولیه مسئله بهینه سازی و پارامترهای اولیه

2- مقدار دهی حافظه هارمونی

3- ایجاد یک هارمونی جدید بهبود یافته

4- به روز کردن حافظه هارمونی

5- تکرار گام های 3و4 تا زمانی که شرط پایانی ارضا شود یا تکرارها تمام شود.

گام اول:

  • ابتدا مسئله به صورت زیر تعریف می گردد:

Minimize f(x) , xi is in  Xi , i=1,2,…,N

  • حال باید پارامترهای زیر مقدار دهی شوند:
  • اندازه حافظه هارمونی HMS
  • نرخ در نظر گرفتن حافظه هارمونی HMCR
  • نرخ تنظیم زیر و بمی PAR
  • ماکزیمم تعداد بهبود MaxImp
  • پهنای باند bw
  • گام دوم

در این مرحله ماتریس HM با مقادیر اولیه ای که به طور تصادفی تولید می‌شود پر می‌گردد.

  • گام سوم:

در این گام یک بردار هارمونی جدید براساس روش های در نظر گرفتن حافظه، انتخاب تصادفی و تنظیم زیر و بمی تولید می شود.

حال مقداری که در مرحله قبل از حافظه انتخاب شده است با احتمال  PAR به مرحله تنظیم زیروبمی می رود.

  • گام چهارم:

اگر بردار هارمونی جدید از بدترین هارمونی موجود در حافظه بهتر باشد جایگزین آن می شود.

  • گام پنجم:

تکرار گام های 3 و 4 تا زمانی که شرط پایانی ارضا شود یا تعداد تکرارها به پایان برسد.

حل مسئله 8 وزیر با HS و مقایسه آن با GA

  • در روش الگوریتم جستجوی هارمونی موقعیت وزیرها در صفحه توسط یک بردار 8تایی به عنوان یک هارمونی در نظر گرفته می‌شود
  • ابتدا به تعداد HMS بردارهای 8تایی تصادفی (هارمونی های تصادفی) ایجاد می‌شود.
  • سپس با تعیین پارامترها هارمونی‌های جدید تولید شده و با بدترین هارمونی موجود در حافظه مقایسه و در صورت بهتر بودن با آن جابجا می‌گردد.
  • در اینجا مسئله 8 وزیر با پارامترهای زیر حل گردیده است:

HMS=20   ,    HMCR=0.6   ,   PAR=0.4

  • همین مسئله با الگوریتم ژنتیک با جمعیت اولیه 50 ژن حل می شود.
  • اگر هر دو الگوریتم را تا رسیدن به جواب صحیح ادامه دهیم و نتایج را مقایسه کنیم، نمودارهای زیر حاصل می گردد.

  • مشاهده می شود که در هر بار اجرای الگوریتم تعداد تکرار HS بسیار بیشتر از GA است، باید توجه داشت که در هر بار تکرار HS یک هارمونی تولید می شود ولی در هر بار تکرار GA 50 ژن تولید می شود.
  • به عبارتی یک بار تکرار GA برابر با 50 تکرار HS است.
  • همچنین مشاهده می شود که HS سریع تر به جواب می رسد.

نتیجه گیری

  • در روند ایجاد هارمونی جدید وقتی انتخاب ها از حافظه انجام می گیرد به سبب اینکه از تمام داده های موجود در حافظه احتمال انتخاب وجود دارد می توان گفت که تمام هارمونی های موجود در حافظه در ساخت هارمونی جدید مشارکت دارند.
  • با توجه به ساختار الگوریتم در میزان حافظه مصرفی نسبتا بهینه عمل می‌کند.

این روش ساختار ریاضیات ساده ای نسبت به اکثر روش ها دارد که پیاده سازی آن را آسان می کند.

ساختار کلی جستجوی ممنوعه

  • برای رسیدن به جواب بهینه در یک مسئله بهینه‌سازی، الگوریتم جستجوی ممنوعه ابتدا از یک جواب اولیه شروع به حرکت می‌کند. سپس الگوریتم بهترین جواب همسایه را از میان همسایه‌های جواب فعلی انتخاب می‌کند. در صورتی که این جواب در فهرست ممنوعه قرار نداشته باشد، الگوریتم به جواب همسایه حرکت می‌کند؛ در غیراین‌صورت الگوریتم معیاری به نام معیار تنفس را چک خواهد کرد. بر اساس معیار تنفس اگر جواب همسایه از بهترین جواب یافت شده تا کنون بهتر باشد، الگوریتم به آن حرکت خواهد کرد، حتی اگر آن جواب در فهرست ممنوعه باشد.
  • پس از حرکت الگوریتم به جواب همسایه، فهرست ممنوعه بروزرسانی می‌شود؛ به این معنا که حرکت قبل که بوسیله‌ی آن به جواب همسایه حرکت کردیم در فهرست ممنوعه قرار داده می‌شود تا از بازگشت مجدد الگوریتم به آن جواب و ایجاد سیکل جلوگیری شود.
  • در واقع فهرست ممنوعه ابزاری در الگوریتم جستجوی ممنوعه‌است که توسط آن از قرار گرفتن الگوریتم در بهینه‌ی محلی جلوگیری می‌شود. پس از قرار دادن حرکت قبلی در فهرست ممنوعه، تعدادی از حرکت‌هایی که قبلاً در فهرست ممنوعه قرار گرفته بودند از فهرست خارج می‌شوند. مدت زمانی که حرکت‌ها در فهرست ممنوعه قرار می‌گیرند توسط یک پارامتر که زمان ممنوعه (tabu tenure) نام دارد تعیین می‌شود.
  • حرکت از جواب فعلی به جواب همسایه تا جایی ادامه می‌یابد که شرط خاتمه دیده شود. شرط‌ های خاتمه متفاوتی می‌توان برای الگوریتم در نظر گرفت. به طور مثال محدودیت تعداد حرکت به جواب همسایه می‌تواند یک شرط خاتمه باشد.

نمودار جریان الگوریتم جستجوی ممنوعه

استراتژی‌های پیشرفته‌ی جستجوی ممنوعه

  • ساختار کلی جستجوی ممنوعه اغلب جوابگوی مسائل بزرگ نیست. بنابراین به منظور افزایش قدرت الگوریتم از استراتژی‌های زیر که معروف به استراتژی‌های پیشرفته جستجوی ممنوعه هستند استفاده می‌شود:
  • استراتژی فهرست کاندید(Candidate List Strategy)
  • استراتژی تقویت (Intensification Strategy)
  • استراتژی تنوع بخشی (Diversification Strategy)
  • مجوز دادن به جوابهای نشدنی

استراتژی فهرست کاندید

  • در یک TS عادی، برای حرکت از یک جواب فعلی به یک جواب همسایه، باید مقدار تابع هدف برای هر عنصر از همسایه‌ها ارزیابی شود. این کار می‌تواند از لحاظ محاسباتی بسیار هزینه بر باشد. روشی دیگر، این است که به جای آن که تمامی همسایه‌ها بررسی شود، تنها یک زیرمجموعه‌ی تصادفی از همسایه‌ها در نظر گرفته شود، که در نتیجه هزینه‌ی محاسباتی به طور قابل ملاحظه‌ای کاهش می‌یابد. انتخاب زیرمجموعه‌ای از جوابهای همسایه به صورت تصادفی، می‌تواند به عنوان یک مکانیزم ضد چرخه عمل کند؛ این کار اجازه می‌دهد که از فهرست ممنوعه‌ی کوچکتری نسبت به کل همسایگی، استفاده شود. البته باید در نظر داشت که این کار یک عیب مهم دارد و آن احتمال از دست دادن جوابهای خوب است، بنابراین احتمال‌هایی را نیز می‌توان به کار برد تا معیارهای ممنوعه فعال شود.

استراتژی تقویت

  • استراتژی تقویت به معنای یافتن حرکت‌های خوب و افزایش انجام آن حرکت‌ها در الگوریتم است. تقویت، در بسیاری از پیاده‌سازی‌های TS استفاده می‌شود، اما همیشه ضروری نیست، زیرا حالت‌های بسیاری وجود دارد که در آنها جستجوی معمولی کفایت می‌کند.

استراتژی تنوع بخشی

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

مجوز دادن به جوابهای نشدنی

  • در حالت‌هایی که محدودیت‌های مسئله بسیار محدود کننده باشند و از جستجوی موثر فضای جواب جلوگیری کنند از این استراتژی استفاده می‌شود. طی این استراتژی محدودیت‌های مسئله آزاد شده و بجای آنها یک مقدار جریمه به تابع هدف اضافه می‌شود.

الگوریتم بهینه سازی ذرات

  • الگوریتم بهینه سازی ذرات (PSO) یک الگوریتم بهینه سازی فرا اکتشافی است که از حرکت گروهی پرندگان (و دیگر حیواناتی که به شکل گروهی زندگی می کنند) الگو گرفته است.
  • در این الگوریتم هر پاسخ مساله به صورت یک ذره که دارای یک مقدار و همچنین میزان تناسب است مدل می شود.
  • الگوریتم بهینه سازی ذرات اولین بار توسط Russell EberhartوJames Kennedy در سال 1995ارایه شد.

دسته بندی موضوعات

نوشته‌های تازه

آخرین نظرات

اطلاعات تماس

تهران، میدان هفت تیر، خیابان مفتح شمالی، نبش کوچه آرام، پلاک 349، ساختمان یثربی

تلفن: 42190 - 021 داخلی 160،161 | 9 – 5167 8831 021

فکس: 9171 8834 021

وب‌سایت: wWw.Yasrebigroup.Com

برچسب ها