الگوریتم فراابتکاری (Meta Heuristic) و تفاوت آن با الگوریتم‌های عادی

مدرس: مسعود کاویانی

MasoudKaviani.ir

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

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

در مثالِ بالا روشِ دوم، روش ابتکاری یا همان Heuristic بود. در واقع از دانشی که قبلاً داشتید استفاده کرده و به یک سطح از بهینگیِ معقول (به جای انتخابِ بهترین گزینه‌ی قطعی) رسیدید. در واقع روشِ اول (بازدید از همه‌ی خانه‌ها) به روشِ Brute Force معروف است و روشِ دوم، به ابتکاری (Heuristic) شهرت دارد. الگوریتم‌ها نیز این‌چنین هستند. یعنی یک سری الگوریتم داریم که با جستجو و مشاهده‌ی همه‌ی داده‌ها، می‌تواند پاسخِ کاملاً دقیق و قطعی را بدهد. این الگوریتم‌ها، سرعتِ پایینی دارند و طبیعتاً برای مسائلی با داده‌ها و ابعاد زیاد، کاربردِ چندانی ندارند. در مقابل یک سری دیگر از الگوریتم‌ها هستند که با استفاده از ابتکار، می‌توانند قسمت‌های مشخصی از داده‌ها را جستجو کنند و با این‌کار سرعت تولیدِ جواب را بالا می‌برند. این در حالی است که الگوریتم‌های ابتکاری، تضمین نمی‌دهند که جوابِ به دست آمده، بهترین جوابِ ممکن باشد. یعنی اگر بیشتر بگردید احتمالاً پاسخی بهتر نیز پیدا خواهید کرد.

همان‌طور که در مثالِ بالا دیدیم، یک روشِ ابتکاری نیاز به دانستنِ مسئله دارد. به زبان دیگر یک الگوریتمِ ابتکاری برای یک مسئله‌ی خاص پاسخگو خواهد بود. مثلاً در مثالِ بالا، روشِ پیدا کردنِ خانه‌ی مناسب برای خرید احتمالاً‌ با روشِ پیدا کردنِ یک اتومبیل مناسب برای خرید تفاوت داشته باشد. در واقع روشِ ابتکاریِ ارائه شده، فقط برای پیدا کردنِ خانه با قیمت مناسب کارا است. این‌جاست که یک سری دیگر از الگوریتم‌ها به وجود آمده‌اند که بدون دانستن مسئله می‌توانند به جستجو برای نقاط بهینه بگردند. این روش‌ها که موضوع دوره‌ی جاری است، الگوریتم‌های فراابتکاری یا همان Meta Heuristic می‌باشند. در واقع الگوریتم‌های فراابتکاری قادر هستند بدونِ دانستن مسئله، با ارائه‌ی یک راه حل عمومی (General) مسئله را با سرعت و دقتِ معقولی حل کنند. این روش‌ها در اصطلاح Problem Independent (مستقل از مسئله) هستند و تمرکز اصلی در دوره‌ی جاری بر روی این الگوریتم‌ها است.

الگوریتم‌هایی مانند جستجوی دودویی یا برنامه‌نویسی پویا، از دسته‌ی اول (Brute Force) هستند و الگوریتم‌هایی مانند ژنتیک یا کلونی مورچه‌ها در دسته‌ی الگوریتم‌های فراابتکاری قرار می‌گیرند.