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

الگوریتم های فراابتکاری ، به طور وسیع در مسائل بهینه‌سازی علوم مختلف، از قبیل علوم کامپیوتر، هوش مصنوعی و مهندسی و مدیریت، کاربرد دارند. یکی از کاربردهای مهم الگوریتم های متاهیوریستیک، در مسائل بهینه‌سازی ترکیبیاتی است. به این دسته از مسائل، مسائل بهینه‌سازی گسسته، نیز می‌گویند. بسیاری از این مسائل، از نوع مسا‌ئل سخت NP-Hard می‌باشند. مسائل ترکیبیاتی، معمولا ظاهری ساده، دارند، اما به‌سختی می‌توانیم آن‌ها را حل کنیم. برای توصیف الگوریتم های متاهیوریستیک و یا فراابتکاری در ابتدا بایدبا مقدمه‌ای بحث را آغاز نماییم.

الگوریتم

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

پیچیدگی الگوریتم

منظور از پیچیدگی یک الگوریتم، تخمین میزان مصرف حافظه و زمانی است که یک الگوریتم برای حل یک مسئله مصرف می‌کند. هر چه‌قدر این مقدار بیشتر باشد، می‌گوییم پیچیدگی آن الگوریتم بیشتر است. مثلا در صورتی که یک الگوریتم دارای یک حلقه‌ی با مقدار n باشد، می‌گوییم پیچیدگی این الگوریتم از مرتبه‌ی n است. حال اگر یک الگوریتم با دو حلقه‌ی جدا از هم n مرتبه اجرا شود، مرتبه‌ی الگوریتم 2n می‌باشد. در صورتیکه این حلقه‌ها تودرتو باشند مرتبه‌ی اجرای الگوریتم n² خواهد بود.

پیچیدگی از نوع چندجمله‌ای

هر چه تعداد حلقه‌های تودرتو بیشتر شود، پیچیدگی زمانی الگوریتم، به صورت یک عبارت چند جمله‌ای یا polynomial افزایش می‌یابد. بسیاری از مسائل ریاضی را می‌توان با الگوریتم‌هایی با پیچیدگی زمانی چندجمله‌ای یا polynomial حل نمود. حال هرچند توان مرتبه‌ی n هم بزرگ باشد بازهم پیچیدگی از نوع چند جمله‌ای است.

مسائل غیر قطعی سخت (NP-Hard)

دسته‌ای از مسائل در ریاضیات و مهندسی وجود دارند که، الگوریتمی با پیچیدگی زمانی چندجمله‌ای، برای آن‌ها پیدا نشده‌است. این گونه مسائل را مسائل NP-Hard می‌گویند. در مسائل NP-Hard با افزایش ابعاد مسئله، زمان بدست آوردن جواب قطعی، به طور نمایی افزایش می‌یابد. به عنوان مثال مسئله‌ی فروشنده‌ی دوره‌گرد از جمله مسا‌ئل NP-Hard است. برای حل قطعی این‌گونه مسائل، سال‌ها و گاهی یک عمر زمان لازم داریم.

مسئله‌ی فروشنده‌ی دوره‌گرد

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

رشدنمایی مسئله‌ی فروشنده‌ی دوره‌گرد

شاید در ظاهر این یک مسئله‌ی ساده به نظر برسد، اما با افزایش تعداد شهرها، تعداد حالت‌های مختلفی که فروشنده می‌تواند برای مسافرت انتخاب کند، به صورت نمایی افزایش می‌یابد. مثلا در صورتی که تعداد شهرها 5 عدد باشد، برای پیدا کردن بهترین مسیر باید 120 حالت،که تمام حالت‌های ممکن است را بررسی نماییم. حال اگر تعداد شهرها به 10 شهر برسد، تعداد حالت‌های ممکن برای فروشنده، به 3/628/800 وضیت می رسد. برای تعداد 15 شهر، این عدد به ¹² 10 * 1/307674368 که عددی بسیار بزرگ است می‌رسد. برای حل این مسئله فرمول و یا قضیه‌ای کشف نشده است. پس باید تمام حالت‌ها بررسی شود، که زمان بسیار زیادی، برای جستجوی جواب بهینه، صرف خواهد شد.

داستانی از بزر گی رشد اعداد نمایی

برای این‌که بخواهیم بزرگی پیچیدگی مسائلی که رشد نمایی را دارند، توصیف کنیم، ذکر داستانی که در باره‌ی مخترع شطرنج گفته شده، خالی از لطف نیست.

وقتی وزیر شرهام شاه هندی، شطرنج را اختراع نمود، آن را به پادشاه هدیه داد. شرهام شاه از بازی شطرنج خوشش آمد و به وزیر گفت خواسته‌ای از من بخواه. وزیر شرهام شاه گفت: قربان خواسته‌ی من این است که در خانه اول 1 عدد گندم و در خانه‌ی دوم شطرنج 2 عدد گندم و در هر خانه دوبرابر خانه‌ی بعدی به من، گندم دهید. شاه گفت: این که خواسته‌ی زیادی نیست و دستور داد یک گونی گندم را آوردند. هنوز تعداد زیادی از خانه‌های شطرنج، طی نشده بود که، گندم‌های گونی تمام شد. شاه، دستور داد، گونی‌های گندم بیشتری آوردند. چند خانه شطرنج جلوتر، پادشاه دید که اگر به همین صورت پیش برود، در انبار دیگر هیچ گندمی نخواهد ماند. در اصل در خانه‌ی شصت و چهارم تعداد گندم‌ها 2⁶⁴ است که، عدد 18,446,744,073,709,551,616 می شود. این مقدار گندم، برابر محصول ده‌ها سال گندم جهان است. در این داستان، بزرگی رشد نمایی اعداد را، به وضوح، نشان می‌دهد.

اشتباه در تعریف NP-Hard

امکان دارد از تعریفی که از مسائل NP-Hard می‌گردد، به اشتباه برداشت گردد که NP-Hard به معنی None polynomial به معنای پیچیدگی، از نوع غیر چندجمله‌ای است. در صورتیکه NP-Hard مخفف None deterministic polynomial Hard problem است که، به معنی مسئله‌ی سخت غیرقطعی چندجمله‌ای می‌باشد. مفهوم NP-Hard، این است که، اگر بخواهیم تمام مجموعه‌ی داده‌ها را محاسبه نماییم، به علت مجموعه‌ی بسیار بزرگ داده‌ها، پیچیدگی از نوع چندجمله‌ای نخواهد بود. اما برای تعداد داده‌های محدود و غیرقطعی، پیچیدگی از نوع چندجمله‌ای خواهد بود.

قضیه‌ی اثبات نشده

خود این قضیه، که آیا، مسائل NP-Hard، قابل تبدیل به پیچیدگی از نوع چندجمله‌ای می‌باشند، یا خیر، جزو مسائلی است که تا کنون اثبات نشده است. اما اثبات شده است که اگر یکی از مسائل NP-Hard را بتوان با الگوریتم، با پیچیدگی چندجمله‌ی حل نمود آنگاه تمام مسائل NP-Hard قابل حل با الگوریتم‌های چندجمله‌ای خواهند بود.

الگوریتم‌های اکتشافی یا هیوریستیک

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

چند مثال عملی هیوریستیک در زندگی

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

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

مقایسه‌ی روش فراگیر با روش ابتکاری

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

مثال بعدی بازی شطرنج می‌باشد. شطرنج‌بازهای ماهر، در مسابقات، تمام حرکت‌های ممکن را محاسبه نمی‌کنند. بلکه بر اساس شواهد و قرائن، و روانشناسی و قدرت تخمین حرکت‌های بعدی حریف، اقدام به حرکت می‌نمایند. به همین علت نیز همیشه پیروز این میدان نیستند.

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

روش‌های هیوریستیک یا ابتکاری، برای حل یک مسئله‌ی مشخص، با شرایط خاص آن مسئله، مانند مثال‌های ذکر شده‌ی بالا طراحی شده‌اند و برای حل مسائل دیگر، معمولا کارامد نیستند. در صورتی‌که، الگوریتم‌های متاهیوریستیک معمولا به مسئله‌ی خاصی محدود نبوده و اصطلاحا problem independent می‌باشند و برای یک طیف از مسايل NP-Hard به‌کار می‌روند. از الگوریتم‌های فراابتکاری می‌توان به الگوریتم‌های ژنتیک، کلونی مورچگان، الگوریتم ازدحام ذرات(PSO)، الگوریتم کرم شب‌تاب و الگوریتم زنبور عسل، اشاره نمود.

دسته‌بندی الگوریتم‌های فراابتکاری

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

الگوریتم‌های مبتنی بر جمعیت و الگوریتم‌های مبتنی بر یک جواب

در الگوریتم های فراابتکاری مبتنی بر یک جواب، در حین اجرای الگوریتم، برای رسیدن به جواب بهینه، تنها یک جواب تغییر می‌کند. از این نوع الگوریتم‌ها می‌توان به الگوریتم‌های تبرید شبیه‌سازی شده و جستجوی ممنوعه اشاره کرد. در حالی که، الگوریتم‌های مبتنی بر جمعیت، مجموعه‌ای از جواب‌ها برای رسیدن به جواب بهینه تغییر می‌کنند. مثلا الگوریتم‌های ژنتیک، کلونی مورچگان، PSO، زنبور عسل و کرم شب‌تاب از الگوریتم‌های مبتنی بر جمعیت هستند.

الگوریتم‌هایی که از طبیعت الهام گرفته شده‌اند

بسیاری از الگوریتم های فراابتکاری، با الهام از فیزیک، یا رفتار موجودات زنده و جانوران، بوجود آمده‌اند. نام‌هایی که برای انواع الگوریتم‌های فراابتکاری گذاشته‌شده‌اند، با توجه به الگویی است که یک الگوریتم، از آن پدیده گرفته است. به عنوان مثال، الگوریتم‌های ژنتیک، وال‌ها و گرگ خاکستری از الگوریتم‌هایی هستند که از طبیعت الهام گرفته شده‌اند.

الگوریتم‌های دارای حافظه و الگوریتم‌های بدون حافظه

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