روش فراشناختی
در علوم رایانه و بهینه سازی ریاضی ، یک روش فراشناختی یک روش سطح بالاتر یا اکتشافی است که برای یافتن ، تولید یا انتخاب یک اکتشافی ( الگوریتم جستجوی جزئی ) طراحی شده است که ممکن است یک راه حل به اندازه کافی خوب برای یک مسئله بهینه سازی ، به خصوص با اطلاعات ناقص یا ناقص ارائه دهد. یا ظرفیت محاسبات محدود. [1] [2] استعاره از مجموعه ای از راه حل ها برای نمونه گیری کاملاً بزرگ ، بسیار بزرگ است. استعاره ممکن است فرضیات کمی درباره حل مسئله بهینه سازی ایجاد کند ، بنابراین ممکن است برای انواع مختلف قابل استفاده باشد. [3]
در مقایسه با الگوریتم های بهینه سازی و روش های تکراری ، فراشناختی تضمین نمی کند که یک راه حل بهینه در سطح جهانی در برخی از طبقه از مشکلات یافت شود. [3] بسیاری از فراشناخت ها نوعی بهینه سازی تصادفی را به کار می گیرند ، به طوری که راه حل موجود به مجموعه متغیرهای تصادفی تولید شده بستگی دارد . [2] در بهینه سازی ترکیبی ، با جستجوی مجموعه های بزرگی از راه حل های ممکن ، فراشناختی اغلب می تواند راه حلهای خوبی با تلاش محاسباتی کمتری نسبت به الگوریتم های بهینه سازی ، روش های تکراری یا اکتشافی ساده پیدا کند. [3]به همین ترتیب ، آنها رویکردهای مفیدی برای مشکلات بهینه سازی هستند. [2] چندین کتاب و مقاله نظرسنجی در این زمینه منتشر شده است. [2] [3] [4] [5] [6]
بیشتر ادبیات مربوط به فراشناختی ماهیت آزمایشی دارد و نتایج تجربی را بر اساس آزمایش های رایانه ای با الگوریتم ها توصیف می کند. اما برخی از نتایج نظری رسمی نیز موجود است ، غالباً در همگرایی و امکان یافتن بهینه جهانی. [3] بسیاری از روشهای فراشناختی با ادعای جدید بودن و اثربخشی عملی منتشر شده است. در حالی که این زمینه همچنین دارای تحقیقات با کیفیت بالا است ، بسیاری از انتشارات از کیفیت پایین برخوردار نبوده اند. نقص ها شامل مبهم بودن ، عدم تفسیر مفهومی ، آزمایش های ضعیف و ناآگاهی ادبیات قبلی است. [7]
فهرست
خواص [ ویرایش ]
اینها خصوصیاتی هستند که بیشترین فراشناختی را توصیف می کنند: [3]
- استعاره ، استراتژی هایی هستند که فرایند جستجو را راهنمایی می کنند.
- هدف این است که به طور موثر فضای جستجو را جستجو کنید تا بتوانید راه حلهای تقریبا بهینه پیدا کنید.
- تکنیک هایی که الگوریتم های استعاره ای را تشکیل می دهند ، از روشهای ساده جستجوی محلی تا فرآیندهای یادگیری پیچیده متغیر است.
- الگوریتم های استعاره نزدیک و معمولاً غیر قطعی هستند.
- استعاره ها مسئله خاص نیستند.
طبقه بندی [ ویرایش ]
نمودار اویلر از طبقه بندی های مختلف استعاره. [8]
انواع گسترده ای از فراشناختی [2] و تعدادی از خواص با توجه به طبقه بندی آنها وجود دارد. [3]
جستجوی محلی در مقابل جستجوی جهانی [ ویرایش ]
یک رویکرد برای توصیف نوع استراتژی جستجو است. [3] یکی از انواع استراتژی های جستجو ، بهبود در الگوریتم های جستجوی محلی ساده است. یک الگوریتم جستجوی محلی مشهور ، روش کوهنوردی است که برای یافتن بهینه های محلی استفاده می شود. با این وجود ، کوهنوردی یافتن راه حلهای بهینه جهانی را تضمین نمی کند.
برای یافتن راه حلهای بهتر ، ایده های فراشناختی زیادی برای بهبود اکتشاف پذیری جستجوی محلی ارائه شده است. چنین فراشناختی شامل بازپخت شبیه سازی شده ، جستجوی تابو ، جستجوی محلی تکرار شده ، جستجوی متغیرهای محله و GRASP است . [3] این استعاره ها هر دو را می توان به عنوان روش جستجوی محلی یا متاوریولوژی جستجوی جهانی طبقه بندی کرد.
دیگر فراشناختی جستجوی جهانی که مبتنی بر جستجوی محلی نیستند ، معمولاً فراشناختی مبتنی بر جمعیت هستند. چنین فراشناختی شامل بهینه سازی کلونی مورچه ها ، محاسبه تکاملی ، بهینه سازی ازدحام ذرات و الگوریتم های ژنتیکی است . [3]
تک راه حل در مقابل مبتنی بر جمعیت [ ویرایش ]
بعد طبقه بندی دیگر ، راه حل واحد در برابر جستجوهای مبتنی بر جمعیت است. [3] [6] رویکردهای یک راه حل تنها بر اصلاح و بهبود یک راه حل نامزد واحد تمرکز دارد. استعاره راه حل واحد شامل پنهان سازی شبیه سازی شده ، جستجوی محلی تکرار شده ، جستجوی متغیر محله و جستجوی محلی است . [6] رویکردهای مبتنی بر جمعیت ، چندین راه حل نامزدی را حفظ و بهبود می بخشند ، که اغلب از ویژگیهای جمعیت برای هدایت جستجو استفاده می کنند. استعاره مبتنی بر جمعیت شامل محاسبه تکاملی ، الگوریتم های ژنتیکی و بهینه سازی ذرات ذرات است . [6]دسته دیگر از فراشناختی هوش Swarm است که یک رفتار جمعی از عوامل غیر متمرکز و خود سازمان یافته در یک جمعیت یا ازدحام است. بهینه سازی کلونی مورچه ها ، [9] بهینه سازی ذرات ذره ای ، [6] بهینه سازی شناختی اجتماعی نمونه هایی از این دسته هستند.
هیبریداسیون و الگوریتم های حافظه [ ویرایش ]
یک استعاره ترکیبی یکی از روشهای فراشناختی با سایر روشهای بهینه سازی مانند الگوریتم های برنامه نویسی ریاضی ، برنامه نویسی محدودیت و یادگیری ماشین است . ممکن است هر دو مؤلفه یک متاستوریستی ترکیبی به طور هم زمان اجرا شوند و اطلاعات را برای هدایت جستجو مبادله کنند.
از طرف دیگر ، الگوریتم های حافظه [10] نشان دهنده هم افزایی رویکرد تکاملی یا هر رویکرد مبتنی بر جمعیت با یادگیری جداگانه فردی یا روش های بهبود محلی برای جستجوی مشکل است. نمونه ای از الگوریتم های حافظه استفاده از الگوریتم جستجوی محلی به جای یک عملگر جهش اساسی در الگوریتم های تکاملی است.
استعاره موازی [ ویرایش ]
یک فراتحوری موازی راهی است که از تکنیک های برنامه نویسی موازی برای انجام چندین جستجو متاوریستیکی به صورت موازی استفاده می کند. اینها ممکن است از طرح های توزیع شده ساده تا اجرای همزمان جستجو که در تعامل هستند برای بهبود راه حل کلی باشد.
استعاره طبیعت و استعاره مبتنی بر استعاره [ ویرایش ]
مقالات اصلی: هوش Swarm و لیست استعاره الهام گرفته از استعاره
یک منطقه تحقیقاتی بسیار فعال ، طراحی استعاره الهام گرفته از طبیعت است. بسیاری از استعاره های اخیر ، به ویژه الگوریتم های مبتنی بر محاسبات تکاملی ، از سیستم های طبیعی الهام گرفته شده اند. طبیعت به عنوان منبع مفاهیم ، مکانیسم ها و اصول برای طراحی سیستم های محاسبات مصنوعی برای مقابله با مشکلات پیچیده محاسباتی عمل می کند. [11] چنین فراشناختی شامل بازپردازی شبیه سازی شده ، الگوریتم های تکاملی ، بهینه سازی کلونی مورچه ها و بهینه سازی ذرات ذرات است . تعداد زیادی از متاوریسم جدید الهام گرفته از استعاره ، به دلیل پنهان کردن عدم جدید بودن در پشت استعاره دقیق ، شروع به جلب انتقاد در جامعه تحقیق کرده اند . [7]
برنامه ها [ ویرایش ]
Metaheuristics برای بهینه سازی ترکیبی مورد استفاده قرار می گیرد که در آن یک راه حل بهینه در یک فضای جستجوی گسسته جستجو می شود. یک مشکل مثال ، مشکل فروشنده مسافرتی است که با افزایش اندازه مشکل ، فضای جستجوی راه حل های کاندیدایی سریعتر از حد تصاعدی رشد می کند ، که باعث می شود یک جستجوی جامع برای بهینه راه حل غیرمترقبه باشد. علاوه بر این ، مشکلات ترکیبی چندبعدی ، از جمله بیشتر مشکلات طراحی در مهندسی [12] [13] [14] مانند فرم یافتن و یافتن رفتار ، از لعنت ابعادی رنج می برند که همین امر باعث می شود آنها برای جستجوی جامع یا غیرقابل نفوذ باشند.روش های تحلیلی . Metaheuristics همچنین به طور گسترده ای برای برنامه ریزی کارگاه و مشکلات انتخاب شغل مورد استفاده قرار می گیرد. [ استناد به نیاز ] استعاره محبوب برای مشکلات ترکیبی شامل بازپرداخت شبیه سازی شده توسط کرکپاتریک و همکاران ، [15] الگوریتم های ژنتیکی توسط هلند و همکاران ، [16] جستجوی پراکنده [17] و جستجوی تابو [18] توسط گلور است. بررسی ادبیات در مورد بهینه سازی فراعرض آمیز ، [19] اظهار داشت که این فرد گولور بود که کلمه استعاره را ترجیح داد. [20]
مشارکت ها [ ویرایش ]
بسیاری از استعاره های مختلف وجود دارد و به طور مداوم انواع جدیدی ارائه می شود. برخی از مهمترین مشارکت ها در این زمینه عبارتند از:
- 1952: رابینز و مونرو روی روشهای بهینه سازی تصادفی کار می کنند. [21]
- 1954: باریکلی اولین شبیه سازی فرایند تکامل را انجام داده و از آنها در مشکلات بهینه سازی کلی استفاده می کند. [22]
- 1963: رستریگین جستجوی تصادفی را پیشنهاد می کند . [23]
- 1965: ماتیاس بهینه سازی تصادفی را پیشنهاد می کند . [24]
- 1965: نلدر و میاد یک اکتشافی ساده را پیشنهاد می کنند ، که توسط پاول نشان داده شد تا در برخی از مشکلات به نقاط غیر ثابت نزدیک شود. [25]
- 1965: اینگو رگنبرگ اولین الگوریتم استراتژی های Evolution را کشف کرد . [26]
- 1966: Fogel و همکاران. برنامه نویسی تکاملی را پیشنهاد کنید [27]
- 1970: هاستینگز الگوریتم Metropolis-Hastings را پیشنهاد می کند . [28]
- 1970: کاویشیو سازگاری پارامترهای کنترل را برای بهینه ساز پیشنهاد می کند. [29]
- 1970: کرنیگان و لین روش تقسیم بندی نمودار را در رابطه با جستجوی عمق متغیر و جستجوی مبتنی بر ممنوعیت (تابو) پیشنهاد می دهند . [30]
- 1975: هلند الگوریتم ژنتیک را پیشنهاد می کند . [16]
- 1977: گلوور جستجوی پراکنده را پیشنهاد می کند. [17]
- 1978: مرسر و سمپسون پیشنهاد metaplan برای تنظیم پارامترهای بهینه ساز با استفاده از بهینه ساز دیگری است. [31]
- 1980: اسمیت برنامه نویسی ژنتیک را توصیف می کند . [32]
- 1983: کرکپاتریک و همکاران. پیشنهاد بازپخت شبیه سازی شده . [15]
- 1986: گلوور جستجوی تابو را پیشنهاد می کند ، ابتدا به اصطلاح فرااگرایی اشاره می کند . [18]
- 1989: Moscato الگوریتم های حافظه را پیشنهاد می کند . [10]
- 1990: Moscato و Fontanari [33] و Dueck و Scheuer [34] ، به طور مستقل یک قانون به روزرسانی قطعی را برای بازپخت شبیه سازی شده پیشنهاد دادند که باعث تسریع در جستجو شد. این منجر به آستانه پذیرش استعاره شد.
- 1992: دوریگو در پایان نامه دکترا بهینه سازی کلونی مورچه را معرفی می کند. [9]
- 1995: ولپرت و مکرون بدون قضیه ناهار رایگان را اثبات می کنند . [35] [36] [37] [38]
منبع