تعریف
فراابتکاری یک چارچوب الگوریتمی مستقل از مسئله سطح بالا است که مجموعه ای از دستورالعمل ها یا استراتژی ها را برای توسعه الگوریتم های بهینه سازی ابتکاری ارائه می دهد. مثال‌های قابل‌توجهی از فراابتکاری عبارتند از الگوریتم‌های ژنتیک/تکاملی(genetic/evolutionary algorithms )، جستجوی تابوtabu search، شبیه‌سازی تبرید simulated annealing ، جستجوی همسایگی متغیر variable neighborhood search ، جستجوی همسایگی بزرگ (تطبیقی) (adaptive) large neighborhood search و بهینه‌سازی کلونی مورچه‌ها ant colony optimization ، اگرچه بسیاری از موارد دیگر نیز وجود دارند. یک پیاده‌سازی خاص از یک الگوریتم بهینه‌سازی ابتکاری با توجه به دستورالعمل‌های بیان شده در یک چارچوب فراابتکاری نیز به عنوان فراابتکاری نامیده می‌شود. این اصطلاح توسط Glover (1986) ابداع شد و پیشوند یونانی meta- (metá، فراتر به معنای سطح بالا از یونانی heuriskein یا euriskein، برای جستجو ترکیب می کند.
الگوریتم های فراابتکاری، به عنوان مثال، روش های بهینه سازی طراحی شده بر اساس استراتژی های ارائه شده در یک چارچوب فراابتکاری، – همانطور که از نام آن پیداست – همیشه ماهیت ابتکاری دارند. این واقعیت آنها را از روش‌های دقیق متمایز می‌کند، که با اثباتی همراه می‌شوند که راه‌حل بهینه در یک زمان محدود (اگرچه اغلب بسیار زیاد) پیدا می‌شود. بنابراین فراابتکاری به طور خاص برای یافتن راه حلی “به اندازه کافی خوب” در زمان محاسباتی “به اندازه کافی کوچک” توسعه یافته است. در نتیجه، آنها در معرض انفجار ترکیبی نیستند – پدیده ای که در آن زمان محاسبات مورد نیاز برای یافتن راه حل بهینه مسائل NP-hard به عنوان تابعی نمایی از اندازه مسئله افزایش می یابد.
فرا ابتکاری توسط جامعه علمی نشان داده شده است که جایگزینی قابل دوام و اغلب برتر برای روش های سنتی تر (دقیق) بهینه سازی اعداد صحیح مختلط مانند برنامه نویسی شاخه و کران و پویا است. به‌ویژه برای مسائل پیچیده یا نمونه‌های بزرگ، فراابتکاری اغلب می‌تواند بین کیفیت راه‌حل و زمان محاسبات تبادل بهتری ارائه دهد. علاوه بر این، فراابتکاری از دو جهت مهم نسبت به روش های دقیق انعطاف پذیرتر است. اول، از آنجایی که چارچوب های فراابتکاری به صورت کلی تعریف می شوند، الگوریتم های فراابتکاری را می توان برای مطابقت با نیازهای بیشتر مسائل بهینه سازی زندگی واقعی از نظر کیفیت راه حل مورد انتظار و زمان محاسبات مجاز، که می تواند در مسائل مختلف و موقعیت های مختلف بسیار متفاوت باشد، تطبیق داد. ثانیاً، فراابتکاری هیچ درخواستی برای فرمول‌بندی مسئله بهینه‌سازی نمی‌کند (مانند نیاز به قیود یا توابع هدف برای بیان توابع خطی متغیرهای تصمیم). با این حال، این انعطاف پذیری به قیمت نیاز به انطباق قابل توجه با مشکل برای دستیابی به عملکرد خوب است.
حوزه تحقیقاتی فراابتکاری خالی از منتقدان نیست – اکثر آنها به فقدان متدولوژی طراحی قابل اجرا جهانی، فقدان دقت علمی در آزمایش و مقایسه پیاده‌سازی‌های مختلف، و تمایل به ایجاد روش‌های بسیار پیچیده با بسیاری از اپراتورهای مختلف حمله می‌کنند. برخی از نویسندگان همچنین از روشی که در آن استعاره ها توسط برخی نویسندگان برای ایجاد انگیزه در توسعه روش های “بدین” استفاده می شود، انتقاد کرده اند (به بخش ۲.۵ “جنجال استعاره” مراجعه کنید). با وجود این انتقاد، بحث موفقیت سخت است. توانایی دستیابی به راه‌حل‌های خوب در جایی که روش‌های دیگر با شکست مواجه می‌شوند، فراابتکاری را به روش انتخابی برای حل اکثر مسائل بزرگ بهینه‌سازی زندگی واقعی، هم در تحقیقات دانشگاهی و هم در کاربردهای عملی تبدیل کرده است. در نتیجه، چندین فروشنده نرم افزار تجاری، فراابتکاری را به عنوان موتورهای بهینه سازی اولیه خود، هم در بسته های نرم افزاری تخصصی برای برنامه ریزی تولید، مسیریابی وسایل نقلیه (Sörensen et al., 2008) و پرستاران (Burke et al., 2004) و همچنین در بسته های بهینه سازی و شبیه سازی همه منظوره (آوریل و همکاران، ۲۰۰۳، فو، ۲۰۰۲، گلاور و همکاران، ۱۹۹۹).
مبانی اساسی فراابتکاری های مختلف به طور قابل توجهی متفاوت است. برخی فرآیند بهینه‌سازی را با استفاده از استعاره‌ای به ظاهر نامرتبط با بهینه‌سازی، مانند تکامل طبیعی (الگوریتم‌های ژنتیک/تکاملی)، خنک‌کردن یک جامد کریستالی (بازپخت شبیه‌سازی شده)، یا رفتار ازدحام حیوانات (مانند بهینه‌سازی کلونی مورچه‌ها) مدل‌سازی می‌کنند. دیگران، مانند جستجوی تابو، از چنین سطح واسطه ای از توضیح استفاده نمی کنند، بلکه بیشتر بر بهره برداری از ساختار مشکل برای بهبود جستجوی راه حل های خوب تمرکز می کنند. به طور کلی، چارچوب های فراابتکاری به شدت بر استفاده از تصادفی بودن تکیه می کنند، اگرچه برخی از استراتژی های کاملاً قطعی نیز پیشنهاد شده است. اکثر چارچوب‌های فراابتکاری منشأ خود را در دهه ۸۰ میلادی دارند (اگرچه در برخی موارد می‌توان ریشه‌های آن را در اواسط دهه ۶۰ و ۷۰ جستجو کرد) و از اوایل دهه ۸۰ از افزایش مداوم استفاده و محبوبیت برخوردار بوده‌اند. رشته فراابتکاری در حال حاضر موضوع تعدادی از مجلات و کنفرانس های اختصاصی است. EU/ME – جامعه فراابتکاری [۱] یک گروه کاری تحت حمایت EURO در زمینه فراابتکاری است و با حدود ۱۴۰۰ عضو، بزرگترین پلت فرم برای ارتباط بین محققان فراابتکاری در سراسر جهان است.
این مقاله بررسی سطح بالایی از حوزه‌ای را ارائه می‌کند که اکنون هزاران محقق، چندین مجله و مجموعه کنفرانس اختصاصی و تعداد قابل توجهی از انتشارات را در هر سال دارد. بنابراین از نظر طراحی ناقص است. این مقاله همچنین آموزشی در مورد فراابتکاری نیست، و ممکن است بینش کمی برای تازه واردان مطلق در این زمینه ارائه دهد. طراحی یک الگوریتم اکتشافی برای بهینه سازی ترکیبی چیزی است که به طور کلی از طریق تجربه آموخته می شود. نویسندگان توصیه می‌کنند که با یک جستجوی محلی ساده یا اکتشافی سازنده شروع کنید و پیچیدگی (حرکت اغتشاش، فهرست تابو، اپراتور جستجوی محلی دیگر، …) را در زمانی که این کافی نیست اضافه کنید.
طبقه بندی فراابتکاری
الگوریتم های فراابتکاری تلاش می کنند تا بهترین راه حل (امکان پذیر) را از بین همه راه حل های ممکن یک مسئله بهینه سازی بیابند. برای این منظور، آنها راه حل های بالقوه را ارزیابی می کنند و یک سری عملیات را روی آنها انجام می دهند تا راه حل های متفاوت و بهتری پیدا کنند. فراابتکاری بر روی نمایش یا رمزگذاری یک راه حل عمل می کند، یک شی که می تواند در حافظه کامپیوتر ذخیره شود و می تواند به راحتی توسط عملگرهای مختلف به کار گرفته شده توسط فراابتکاری دستکاری شود. بر اساس روشی که در آن راه حل ها دستکاری می شوند، می توان سه دسته اساسی از فراابتکاری را متمایز کرد. فراابتکاری جستجوی محلی به طور مکرر تغییرات کوچکی را در یک راه حل ایجاد می کند. فراابتکاری سازنده راه حل ها را از اجزای سازنده خود می سازد. فراابتکاری مبتنی بر جمعیت به طور مکرر راه حل ها را با راه حل های جدید ترکیب می کند. با این حال، این کلاس‌ها متقابلاً منحصر به فرد نیستند و بسیاری از الگوریتم‌های فراابتکاری ایده‌هایی را از کلاس‌های مختلف ترکیب می‌کنند. چنین روش هایی را فراابتکاری ترکیبی می نامند.
فراابتکاری جستجوی محلی
جستجوی محلی (LS) یا بهبود تکرار شونده، با ایجاد تغییرات مکرر در یک راه حل، که راه حل فعلی (یا فعلی) نامیده می شود، راه حل های خوبی پیدا می کند. این تغییرات حرکت نامیده می‌شوند و معمولاً «کوچک» هستند (به طوری که راه‌حل‌های مجاور با توجه به معیار طبیعی نسبتاً نزدیک به یکدیگر هستند)، از این رو نام این کلاس از فراابتکاری است. به مجموعه راه حل هایی که با اعمال یک حرکت روی یک جواب داده شده می توان به دست آورد، همسایگی آن راه حل نامیده می شود. بسته به نحوه نمایش راه حل، انواع مختلف حرکت را می توان تعریف کرد. هر نوع حرکت یک ساختار همسایگی را ایجاد می کند. در هر تکرار، راه حل فعلی با یک راه حل از همسایگی خود جایگزین می شود. قانون مورد استفاده برای انتخاب راه حل جدید، استراتژی حرکت یا استراتژی جستجو نامیده می شود. یک استراتژی جستجوی رایج، تندترین نزول یا تندترین راهبرد صعود است که در آن بهترین حرکت از محله انتخاب می شود. فراابتکاری هایی که از این استراتژی استفاده می کنند اغلب تپه نوردان نامیده می شوند. ملایم ترین استراتژی فرود/صعود راه حلی را انتخاب می کند که راه حل فعلی را با کمترین مقدار بهبود می بخشد. استراتژی های دیگر حرکت عبارتند از اولین بهبود، استراتژی، که در آن اولین حرکت انتخاب می شود که راه حل فعلی را بهبود می بخشد (که البته بستگی به ترتیب بررسی حرکات دارد).
فراابتکاری سازنده
فراابتکاری سازنده، همانطور که از نامش پیداست، به جای بهبود راه حل های کامل، راه حل ها را از عناصر تشکیل دهنده خود می سازد. این کار با افزودن یک عنصر در یک زمان به یک محلول جزئی انجام می شود. فراابتکاری سازنده اغلب اقتباسی از الگوریتم های حریصانه است که بهترین عنصر ممکن را در هر تکرار اضافه می کند. برای بهبود کیفیت راه حل های نهایی، اکثر فراابتکاری های سازنده شامل یک مرحله جستجوی محلی پس از مرحله ساخت و ساز می شود.
GRASP، مخفف روش جستجوی تصادفی تطبیقی حریصانه (Feo و Resende، ۱۹۹۵)، طمع یک فراابتکاری سازنده را با استفاده از تصادفی‌سازی کاهش می‌دهد. رایج ترین نوع GRASP از استراتژی زیر استفاده می کند. در هر تکرار، یک لیست نامزد محدود به روز می شود، که حاوی بهترین عناصر α است که می تواند به راه حل جزئی اضافه شود. یک عنصر تصادفی از این لیست برای افزودن انتخاب می شود، پس از آن لیست به روز می شود تا وضعیت جدید را منعکس کند. پارامتر α “طمع” بودن جستجو را تعیین می کند: اگر α برابر با ۱ باشد، جستجو کاملا حریصانه است در حالی که اگر α برابر با تعداد عناصری باشد که می توان اضافه کرد، جستجو کاملا تصادفی است. الگوریتم‌های GRASP اغلب با یک استراتژی پیوند مجدد مسیر ترکیب می‌شوند (که بعداً مورد بحث قرار خواهد گرفت)، به عنوان مثال، Commander et al. (2008)، ناسیمنتو و همکاران. (۲۰۱۰)، Resende و همکاران. (۲۰۱۰).
راه دیگر برای بهبود عملکرد فرآیند ساخت و ساز، بدون توسل به تصادفی، استفاده از حافظه است. نمونه های قابل توجهی از فراابتکاری که این کار را انجام می دهند را می توان در فلورنت و گلوور (۱۹۹۹) و گلاور و همکاران یافت. (۲۰۰۰). به طور مشابه، استراتژی‌های آینده نگری (پرل، ۱۹۸۴) عناصری را که می‌توان با در نظر گرفتن تأثیر حرکت بعدی، بلکه چندین حرکت در آینده، اضافه کرد، ارزیابی می‌کند. برای مثال، روش آزمایشی (Duin and Voß, ۱۹۹۹)، یک روش پیش بینی است که از یک اکتشافی سازنده برای تعیین مقدار یک عنصر بالقوه با تولید یک راه حل کامل از راه حل جزئی فعلی با اضافه شدن این عنصر استفاده می کند.
جستجوی محله بزرگ (LNS) در (شاو، ۱۹۹۸) معرفی شد و می توان آن را به عنوان همتای سازنده جستجوی محله متغیر مشاهده کرد. این کار با تخریب متناوب یک راه حل و بازسازی آن، معمولاً با استفاده از مجموعه گسترده ای از اکتشافات تخریب و تعمیر کار می کند. در جستجوی همسایگی بزرگ تطبیقی (پیسینگر و روپکه، ۲۰۰۷)، فرکانس استفاده از اکتشافی های مختلف تخریب و تعمیر (معمولاً به روش تصادفی) به عملکرد قبلی آنها بستگی دارد: آنهایی که جفت های اکتشافی را که در گذشته به خوبی منجر شده اند، تخریب/تعمیر می کنند. راه حل ها بیشتر از راه حل هایی که استفاده نمی کنند استفاده می شود.
بهینه‌سازی کلونی مورچه‌ها (ACO) (Dorigo et al., 1996, 2006) یک اصطلاح کلی برای مجموعه‌ای از فراابتکاری سازنده مرتبط است که با تقلید از رفتار جستجوی مورچه‌ها راه‌حل‌هایی می‌سازد. برای این منظور، یک پارامتر خارجی برای هر عنصر بالقوه (به نام سطح فرمون) معرفی شده است. فرمون یک عامل شیمیایی است که باعث واکنش اجتماعی به سایر حیوانات از همان گونه می شود. بهینه‌سازی کلونی مورچه‌ها از چندین عامل مصنوعی (موسوم به مورچه) استفاده می‌کند که هر کدام یک راه‌حل را به‌طور موازی می‌سازند. هنگامی که هر مورچه یک محلول ساخت، سطح فرمون هر عنصر در این محلول به روز می شود تا فرمون بیشتری به عناصری که در محلول های بهتر قرار دارند اختصاص یابد. سپس این اطلاعات در فرآیند ساخت ACO مورد استفاده قرار می گیرد که عناصر را بر اساس ترکیبی از مقدار آن عنصر و سطح فرمون آن انتخاب می کند. فرآیند ساخت محلول مورچه ها تکرار می شود و عناصری که در محلول های با کیفیت بالا وجود داشتند، در نتیجه سطوح فرمون بالاتر، احتمال بیشتری برای انتخاب خواهند داشت. به طور دوره ای، سطح فرمون همه عناصر کاهش می یابد تا تبخیر را منعکس کند. بهینه‌سازی کلونی مورچه‌ها توجه گسترده‌ای را در مطبوعات رایج (مثلاً Anonymous، ۲۰۱۰) به خود جلب کرده و همچنان به آن توجه می‌شود، احتمالاً به دلیل جذابیت شهودی این استعاره.
فراابتکاری مبتنی بر جمعیت
فراابتکاری مبتنی بر جمعیت با انتخاب مکرر و سپس ترکیب راه حل های موجود از مجموعه ای که معمولاً جمعیت نامیده می شود، راه حل های خوبی پیدا می کند. مهمترین اعضای این کلاس الگوریتم های تکاملی (EA) هستند زیرا از اصول تکامل طبیعی تقلید می کنند. ما از واژه الگوریتم های تکاملی به عنوان یک اصطلاح چتر استفاده می کنیم تا طیف وسیعی از فراابتکاری مبتنی بر تکامل را در بر گیرد. این شامل الگوریتم‌های ژنتیک (GA) (گلدبرگ و همکاران، ۱۹۸۹، هالند، ۱۹۷۵)، برنامه‌ریزی ژنتیکی/تکاملی (GP/EP) (کوزا، ۱۹۹۲)، محاسبات تکاملی (EC) (Fogel، ۲۰۰۶) استراتژی‌های تکامل (ES) است. بیر و شوفل، ۲۰۰۲) و بسیاری دیگر. وقتی برای مسائل بهینه‌سازی ترکیبی اعمال می‌شود، الگوریتم‌های تکاملی «خالص» نادر هستند و اغلب شامل برخی عملگرهای بهبود هستند، معمولاً به شکل جستجوی محلی.
الگوریتم‌های تکاملی بر روی مجموعه یا جمعیتی از راه‌حل‌ها عمل می‌کنند و از دو مکانیسم برای جستجوی راه‌حل‌های خوب استفاده می‌کنند: انتخاب راه‌حل‌های عمدتاً با کیفیت بالا از جمعیت و ترکیب مجدد آن راه‌حل‌ها به راه‌حل‌های جدید، با استفاده از عملگرهای تخصصی که ویژگی‌های دو را ترکیب می‌کنند. یا راه حل های بیشتر پس از ترکیب مجدد، راه‌حل‌های جدید مجدداً به جمعیت وارد می‌شوند و احتمالاً نیاز به برآوردن شرایطی مانند امکان‌سنجی یا حداقل نیازهای کیفیت دارند تا جایگزین راه‌حل‌های دیگر (معمولاً با کیفیت پایین) شوند. عملگرهای مورد استفاده در الگوریتم های تکاملی (انتخاب، ترکیب مجدد و درج مجدد) تقریباً بدون استثنا از تصادفی بودن استفاده زیادی می کنند. یک عملگر جهش که به طور تصادفی یک تغییر (کوچک) به یک محلول پس از ترکیب مجدد ایجاد می کند، نیز اغلب اعمال می شود. اکثر الگوریتم های تکاملی مراحل انتخاب، نوترکیب، جهش و درج مجدد را چندین بار تکرار می کنند و بهترین راه حل را در جمعیت گزارش می کنند. الگوریتم های تکاملی به طور کلی به نوعی از “مدیریت جمعیت” نیاز دارند تا اطمینان حاصل شود که بهترین راه حل ها از طریق تکرارهای مختلف زنده می مانند، در حالی که در همان زمان تنوع در جمعیت حفظ می شود.
جایگزین های قطعی مبتنی بر جمعیت برای الگوریتم های تکاملی عبارتند از جستجوی پراکنده و پیوند مجدد مسیر (گلاور و همکاران، ۲۰۰۰، ۲۰۰۳). جستجوی پراکندگی (SS) راه حل ها را به عنوان بردارهای با ارزش واقعی (گرد) رمزگذاری می کند و با ایجاد ترکیب های خطی محدب یا مقعر از این بردارها راه حل های جدیدی را پیدا می کند. پیوند مجدد مسیر مفهوم مسیری بین راه حل های با کیفیت بالا را معرفی می کند که اساساً تعمیم مفهوم ترکیب خطی است. مسیرها شامل حرکات ابتدایی مانند مواردی است که در فراابتکاری جستجوی محلی استفاده می شود. حرکات در یک مسیر، هر بار یک راه حل (به نام راه حل آغازگر) را به راه حل دوم (به نام راه حل راهنما) تبدیل می کند. بنابراین، پیوند مجدد مسیر را می‌توان یک اکتشافی جستجوی محلی در نظر گرفت که از یک استراتژی حرکت استفاده می‌کند که در آن حرکت برای اجرا بر اساس این واقعیت انتخاب می‌شود که این حرکت، راه‌حل را به راه‌حل راهنما «نزدیک‌تر» می‌کند. انتخاب راه‌حل‌های آغازگر و هدایت‌کننده از یک جمعیت (به نام مجموعه مرجع)، و همچنین به‌روزرسانی مجموعه مرجع پس از تولید راه‌حل‌های جدید، بر اساس قوانین قطعی در پیوند مجدد مسیر و جستجوی پراکنده انجام می‌شود.
فراابتکاری “هیربید”
در سال‌های اخیر، این تمایل وجود دارد که چارچوب‌های فراابتکاری به‌عنوان ارائه ایده‌ها یا مؤلفه‌های کلی که می‌توانند برای ساخت روش‌های بهینه‌سازی مورد استفاده قرار گیرند، به جای دستور العمل‌های کتاب آشپزی که باید به دقت دنبال شوند، مشاهده می‌شود (Michalewicz and Fogel, 2004). در نتیجه، اکثر الگوریتم‌های فراابتکاری اخیر ایده‌هایی را از کلاس‌های مختلف ترکیب می‌کنند و اصطلاح فراابتکاری ترکیبی بیشتر قدرت تمایز خود را از دست داده است. بسیاری از فراابتکاری های مدرن از اکتشافی های تخصصی برای حل کارآمد مسائل فرعی تولید شده توسط روش فراابتکاری استفاده می کنند (به عنوان مثال، Gendreau و همکاران، ۱۹۹۴). به طور مشابه، تعداد زیادی از فراابتکاری جستجوی محلی از مرحله ساخت و ساز برای یافتن یک راه حل اولیه (یا مجموعه ای از راه حل های اولیه) استفاده می کنند تا از آنجا جستجوی محله را شروع کنند. در واقع توصیف اصلی فراابتکاری GRASP (Feo و Resende، ۱۹۹۵) یک مرحله جستجوی محلی را برای دنبال کردن فاز ساخت و ساز تصادفی حریصانه تجویز می کند.
الگوریتم‌های متعلق به کلاس الگوریتم‌های ممتیک (تنها نوع فراابتکاری ترکیبی که نام خاصی به آن داده شده است) (Moscato، ۱۹۸۹) عملگرهای نوترکیبی را از کلاس الگوریتم‌های تکاملی با اکتشافات جستجوی محلی (متا) ترکیب می‌کنند.
فراابتکاری و روش های دقیق
پیشرفت‌های الگوریتمی در روش‌های فراابتکاری و دقیق اخیراً این دو زمینه را به هم نزدیک کرده است و ترکیب اجزای فراابتکاری (معمولاً جستجوی محلی) با روش‌های دقیق برای برنامه‌نویسی خطی (اعداد صحیح مختلط) در حال حاضر رایج است. گاهی اوقات ریاضیات نامیده می‌شود، روش‌های به‌دست‌آمده اغلب رویه‌های دقیق موجود را برای حل مشکلات فرعی ایجاد شده توسط یک استراتژی تجزیه، یک استراتژی محدودیت یا یک استراتژی آرامش ادغام می‌کنند (به عنوان مثال، گلوور و کلینگمن، ۱۹۸۸، رگو، ۲۰۰۵ را ببینید). نتایج حل این مسائل فرعی برای راهنمایی یک اکتشافی سطح بالاتر استفاده می شود (دومیترسکو و استوتزل، ۲۰۰۹، رایدل و پوچینگر، ۲۰۰۸).
چندین روش اضافی که در آنها روش های دقیق می توانند عملکرد فراابتکاری را بهبود بخشند گزارش شده است. روش های دقیق گاهی اوقات می توانند نمونه های کوچکی از یک مشکل پیچیده را به طور موثر حل کنند. یک فراابتکاری ممکن است با ساخت مجموعه‌هایی از چنین نمونه‌های کوچکی به‌عنوان یک استراتژی برای ایجاد «حرکات ساختاریافته» که از یک راه‌حل معین به یک راه‌حل جدید تبدیل می‌شود، عمل کند (به عنوان مثال، گلوور، ۲۰۰۵ را ببینید). همچنین، یک روش دقیق را می توان برای مدت بسیار طولانی برای به دست آوردن راه حل های بهینه (حداقل برای برخی از نمونه های یک کلاس مسئله) اجرا کرد و این راه حل های بهینه را می توان در رویکرد یادگیری به نام تحلیل هدف استفاده کرد (Glover, 1990, Glover and لاگونا، ۱۹۹۷) به عنوان راهی برای تولید قوانین تصمیم گیری بهبودیافته برای روش های فراابتکاری و دقیق.
نتیجه ترکیب یک روش فراابتکاری و یک روش دقیق لزوماً نباید یک روش ابتکاری باشد. فراابتکاری را می توان با روش های دقیق ادغام کرد تا عملکرد روش های دقیق را بهبود بخشد (فریدن و همکاران، ۱۹۸۹، گلوور، ۱۹۹۰، پوچینگر و همکاران، ۲۰۰۹).
به روشی مشابه، ایده‌ها و عملگرهای تکنیک‌های برنامه‌نویسی محدودیت با فراابتکاری، مانند رویکردی به نام جستجوی محلی مبتنی بر محدودیت (Van Hentenryck and Michel, 2009) ادغام شده‌اند.
نرم افزار فراابتکاری
بیشتر فراابتکاری ها قبل از دستیابی به عملکرد در سطح جهانی نیاز به طراحی و تنظیم قابل توجهی برای مسئله خاص دارند. اگرچه در حال حاضر تلاش‌های تحقیقاتی زیادی برای توسعه روش‌های قوی‌تر انجام می‌شود، اما نیاز به طراحی ویژه مسئله به منظور دستیابی به بهترین نتایج، مانع استفاده از فراابتکاری در نرم‌افزار بهینه‌سازی عمومی نشده است.
با این وجود، چندین فروشنده نرم افزارهای تجاری بهینه سازی همه منظوره، فراابتکاری را در بسته های خود گنجانده اند. پلتفرم حل ریسک Frontline Systems و مشتقات آن، توسعه حل کننده Microsoft Excel، شامل یک حل کننده تکاملی ترکیبی است. Tomlab/GENO بسته ای برای بهینه سازی ایستا یا پویا، تک یا چند هدفه بر اساس الگوریتم ژنتیک با کد واقعی است. هر دو LINDO/LINGO و CPLEX شامل جستجوی همسایگی ناشی از آزادی (RINS) فراابتکاری هستند.
کتابخانه COIN-OR دارای چندین بسته نرم افزاری فراابتکاری (متن باز) است: METSlib، یک چارچوب بهینه سازی فراابتکاری شی گرا، و Open Tabu Search (OTS)، چارچوبی برای ساخت الگوریتم های جستجوی تابو. علاوه بر این حل‌کننده‌ها برای بهینه‌سازی ترکیبی، اکثر بسته‌های شبیه‌سازی تجاری امروزه شامل یک ابزار بهینه‌سازی هستند (Fu، ۲۰۰۲). Autostat، موجود در AutoMod و Simrunner، موجود در ProModel، هر دو از الگوریتم‌های تکاملی استفاده می‌کنند. شرکت‌های مختلفی در صنعت شبیه‌سازی و همچنین شرکت‌های خدمات مدیریت عمومی و شرکت‌های مشاوره مانند Rockwell Software، Dassault Systemes، Flextronics، Halliburton، HP، Planview و CACI، از نرم‌افزار Opttek Systems, Inc. OptQuest استفاده می‌کنند که از جستجو و پراکندگی تابو استفاده می‌کند. جستجو کردن.
