یکشنبه 30 شهریور 1399 | Sunday 20 th of September 2020 صفحه اصلی گروه الکترونیکی کامپیوتر
انواع الگوریتم‌های مکاشفه‌ای

در حالت کلی سه دسته از الگوریتم‌های مکاشفه‌ای قابل تشخیص است:

1)    الگوریتم‌هایی که بر ویژگی‌های ساختاری مسئله و ساختار جواب متمرکز می‌شوند و با استفاده از ان­ها الگوریتم‌های سازنده یا جستجوی محلی تعریف می‌کنند.

2)    الگوریتم‌هایی که بر هدایت مکاشفه‌ای یک الگوریتم سازنده یا جستجوی محلی متمرکز می‌شوند، به گونه‌ای که ان الگوریتم بتواند بر شرایط حساس (مانند فرار از بهینه محلی) غلبه کند. به این الگوریتم‌ها، فرا اکتشافی گفته می‌شود.

3)    الگوریتم‌هایی که بر ترکیب یک چارچوب یا مفهوم مکاشفه‌ای با گونه‌هایی از برنامه‌ریزی ریاضی (معمولاً روش­های دقیق) متمرکز می‌شوند.
مکاشفه‌ای‌های نوع اول می‌توانند خیلی خوب عمل کنند (گاهی اوقات تا حد بهینگی) اما امکان دارد در جواب‌های دارای کیفیت پایین، گیر کنند. یکی از مشکلات مهمی که این الگوریتم‌ها با ان روبرو می‌شوند، افتادن در بهینه‌های محلی است بدون این که هیچ شانسی برای فرار از ان­ها داشته باشند. برای بهبود این الگوریتم‌ها از اواسط دهه هفتاد، موج تازه‌ای از رویکردها اغاز شد. این رویکردها شامل الگوریتم‌هایی است که صریحاً یا به صورت ضمنی، تقابل بین ایجاد تنوع جستجو (وقتی علایمی وجود دارد که جستجو به سمت مناطق بد فضای جستجو می‌رود) و تشدید جستجو را (با این هدف که بهترین جواب را در منطقه مورد بررسی پیدا کند) مدیریت می‌کنند.

این الگوریتم‌ها فرا اکتشافی نامیده می‌شود.

در علم کامپیوتر، Metaheuristicیک روش محاسباتی را به منظور بهینه­سازی مشکل، با تلاش مکرر انتخاب می­کند که باعث بهبود مجموعه جواب با توجه به کیفیت ان شود.Metaheuristics  Metaheuristics make few or no assumptions about the problem being optimized and can search very large spaces of candidate solutions.تعداد کم یا هیچ فرض درباره مساله­ای که باید بهینه شود، در نظر می­گیرد و می­تواند در میان فضای بزرگی از مجموعه جواب جستجو کند.However, metaheuristics do not guarantee an optimal solution is ever found.با این حال، Metaheuristicsهمیشه پیدا کردن جواب بهینه را ضمانت نمی­کند. خیلی از روش­های فرا اکتشافی به فرم بهینه­سازی تصادفی عمل می­نمایند.

فرا اکتشافی­ها برای بهینه­سازی ترکیبی به کار می­روند، هنگامیکه جواب بهینه بر روی فضای جستجوی گسسته، مورد جستجو قرار می­گیرد. به عنوان مثال، در مساله فروشنده دوره گرد[1] فضای جستجوی جواب­های کاندید، بیشتر از اندازه مساله رشد می­کند که جستجوی کامل برای یافتن جواب بهینه را غیرممکن می­سازد.

فرا اکتشافی­ها رویکرد عمومی برای طراحی فرایند­های اکتشافی با کارایی بالا هستند. مفهوم فرا اکتشافی که برای اولین بار در سال 1986 پدید امد [Glov86]مرکب است از عبارت "متا" که به معنای فراتر می­باشد و همچنین عبارت "Heuristic". Heuristicبه طور خاص برای مساله­های بهینه­سازی جواب استفاده می­شود که حاصل یک کشف هستند.امروزه تعداد زیادی از رویکردهای شناخته شده می­توانند به عنوان فرا اکتشافی­ها دسته­بندی شوند  [Mich00].

روش‌ها و الگوریتم‌های بهینه‌سازی به دو دسته الگوریتم­های دقیق (exact) و الگوریتم‌های تقریبی (approximate algortithms) تقسیم‌بندی می‌شوند. الگوریتم‌های دقیق قادر به یافتن جواب بهینه به صورت دقیق هستند، اما در مورد مسایل بهینه سازی سخت کارایی ندارند و زمان حل انها در این مسایل به صورت نمایی افزایش می‌یابد.در علوم کامپیوتر الگوریتم­های تقریبی، الگوریتم­هایی برای پیداکردن راه حل­های تقریبی برای مسایل بهینه سازی هستند. این الگوریتم­ها اغلب برای حل تقریبی مسایل (NP-hard) به کار می‌روند، زیرا بسیاری از مسایل بهینه سازی NP-hardهستند (در واقع بررسی کردن درستی جواب این گونه مسایل با حل کلی انها معادل است). الگوریتم‌های تقریبی قادر به یافتن جواب‌های خوب (نزدیک به بهینه) در زمان حل کوتاه برای مسایل بهینه‌سازی سخت هستند.

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



[1] Travelling salesman problem

Compatability by:
آخرین به روز رسانی سایت: سه شنبه, 22 اسفند 1391 - 00:26