دیدگاه فوق ابتکاری

واژه ابر هیوریستیک (Hyper Heuristic) برای اولین بار در سال 1997 توسط دینزینگر و همکارانش در مقاله ای استفاده شده است. دیدگاه ابر هیوریستیک (Hyper Heuristic) یک روش جستجوی ابتکاری است که به دنبال اتوماتیک عمل کردن می باشد. در اغلب موارد با ترکیب تکنیک های یادگیری ماشین، فرآیند انتخاب، ترکیب، تولید یا تطبیق چندین ابتکاری ساده برای حل کارای مسائل جستجوی محاسباتی مورد استفاده قرار می گیرد. ابر هیوریستیک ها (Hyper Heuristics) برخلاف الگوریتم های فراابتکاری که فقط برای حل یک مسئله مورد استفاده قرار می گیرند، یک سیستمی برای حل کلاس هایی از مسائل مختلف ایجاد می کنند. در واقع یک متدولوژی عمومی برای کاربردهای مختلف تولید می کند.

در دسته بندی قدیمی تر ابر هیوریستیک ها به دو دسته بدون یادگیری و با یادگیری تقسیم شده اند. در ابر هیوریستیک بدون یادگیری شامل دیدگاه هایی است که از چندین ابتکاری استفاده می کند اما انتخاب ابتکاری ها براساس ترتیب از پیش تعیین شده می باشد. بنابراین این دسته شامل دیدگاه هایی مانند جستجوی همسایگی متغیر می باشد که در هر بار یک همسایه انتخاب می شود. در دسته ابر هیوریستیک با یادگیری شامل روش هایی است که به طور اتوماتیک کارائی هر ابتکاری مبتنی بر  تاریخچه کارائی آن تغییر می کند. همچنین به کمک برخی از ماشین های یادگیری هدایت می شود.

دو دسته اصلی جدید ابر هیوریستیک، انتخاب ابتکاری (Heuristic Selection) و تولید ابتکاری (Heuristic Generation) می باشد. در دسته “انتخاب ابتکاری” متدولوژی گزینش یا انتخاب روش های ابتکاری موجود می باشد. در دسته “تولید فوق ابتکاری” متدولوژی برای تولید ابتکاری های جدید براساس ترکیب ابتکاری های موجود می باشد.

در ادامه دو مثال کاربردی ابر هیوریستیک شرح داده شده است:

مثال 1: فوق ابتکاری رنگ آمیزی گراف برای مسئله جدول زمانی – روش انتخاب ابتکاری جستجوی ممنوعه

در دسته انتخاب ابتکاری از روش های ابر هیوریستیک ، دو سطح استراتژی سطح بالا و ابتکاری سطح پایین وجود دارد. برای حل مسئله جدول زمانی که یکی از مسائل سخت می باشد، می توان برای سطح استراتژی سطح بالا از جستجوی ممنوعه و برای سطح پایین از انواع مختلف ابتکاری موجود استفاده کرد. در این مسئله امتحان های (کلاس های) مختلف باید در بازه زمانی مشخص و محدودی برنامه ریزی گردد. همان طور که در شکل 1 نشان داده شده است ترتیب امتحان های (کلاس های) موجود به کمک یکی از الگوریتم های ابتکاری در "لیست ابتکاری ها" حل می شود و اولین e رویداد در بازه زمانی مشخص می شود. همین روند برای رویدادهای دیگر تکرار پیدا می کند تا کلیه امتحان ها (کلاس ها) برنامه ریزی گردد.

شکل 1: تولید یک راه حل (جدول زمانی) که توسط ابتکاریی که در لیست نوبت آن می باشد. اولین e=5 رویداد نتیجه تخصیص در بازه زمانی جدول زمانی می باشد.

مثال 2: تولید سازوکار ابتکاری برای مسئله بسته بندی اقلام ظروف (Bin Packing) به کمک تولید ابتکاری روش برنامه نویسی ژنتیک:

یکی از روش های ابر هیوریستیک استفاده از برنامه نویسی ژنتیک می باشد که در آن از درخت برای حل مسئله استفاده می شود. مسئله بسته بندی اقلام در ظروف نیز جزو مسائل سخت می باشد که می توان آن را به کمک جستجوی فوق ابتکاری حل کرد. برای ایجاد یک ابتکاری جدید برای حل این مسئله از برنامه نویسی ژنتیک به صورت شکل 2 می توان استفاده کرد. که در آن سه ترمینال بنام های S (اندازه قطعه فعلی) ، C (ظرفیت ظرف)، F (میزان کامل بودن ظرف) در نظر گرفته شده است. تا زمانی که قطعه ای وجود داشته باشد الگوریتم کار خود را به طور اتوماتیک ادامه می دهد.

شکل 2: استنتاج یک بعدی بسته بندی ابتکاری به وسیله برنامه نویسی ژنتیک

منابع

High performance ATP systems by combining several AI methods ,IJCAI'97: Proceedings of the 15th international joint conference on Artifical intelligence - Volume 1,,Pages 102–107,1997.               

Gendreau and J-Y Potvin , Book, Handbook of Metaheuristics, Chapter, A classification of hyper-heuristic approaches, Springer, pp.449-468, 2010.