الگوریتم‌های فراابتکاری (Meta Heuristic)، تابع برازش (Fitness Function) و چند مثال

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

MasoudKaviani.ir

برای شروع بحث در مورد الگوریتم‌ها و روش‌های متداولِ فراابتکاری، ابتدا بهتر است به چند مثالِ کاربردی در این حوزه بپردازیم تا ببینیم یک الگوریتمِ فراابتکاری چگونه می‌تواند به حل مسائل کمک کند.

در علم کامپیوتر، مسائل مختلفی برای حل کردن موجود است. برای مثال، مسئله‌ی ضربِ ۱۰عدد با هم، یک مسئله‌ی بسیار ساده به نظر می‌رسد. برای حل این مسئله می‌توان از الگوریتم‌های قطعی استفاده کرد. به این دست از مسائل که آسان حل می‌شوند، مسائل دسته‌ی P می‌گویند. این مسائل هر چه قدر هم که بزرگ شوند، بلاخره قابل حل در یک زمان قابل قبول توسط کامپیوتر هستند. مثلاً ضرب ۱۰۰۰عدد با ضرب ۱۰هزار عدد، برای یک کامپیوتر خیلی تفاوتی ندارد. اما برخی از مسائل هستند که با زیادتر شدنِ حالت آن‌ها، زمانِ بسیار بیشتری از کامپیوتر برای حل کردن صرف می‌کنند. در واقع پیچیدگیِ محاسباتی آن‌ها، نمایی (Exponential) است. مثلاً اگر تعداد حالاتِ مسئله ۲برابر شود، محاسبات ۱۰برابر می‌شوند! و این، زحمتِ کامپیوتر را برای حلِ مسئله بسیار بیشتر می‌کند. به این دست مسائل، مسائل NP می‌گویند (حالت‌های NP-complete یا NP-hard هم هستند). برای مثال، فرض کنید می‌خواهید با توجه به بودجه‌ی خود، یک مجموعه‌ی سهام را در بورس انتخاب کنید. قطعاً می‌خواهید این انتخاب با ریسک کم و سوددهی بالا باشد. این مسئله به راحتی و در زمان قابل قبول توسط کامپیوتر حل نمی‌شود (با توجه به زیاد بودن تعداد شرکت‌ها و محدودیت‌های قانونی و محدودیت‌هایی که هر شرکت در خرید و فروش سهام دارد). در واقع این یک نوع مسئله‌ی NP است. به این معنی که برای به دست آوردنِ جواب قطعی (بهترین خرید سهام) که همان بهینه‌ی سراسری است مثلاً بایستی ۸۰سال محاسبات توسط کامپیوتر انجام شود. که این اصلاً برای خریدِ سهام معقول نیست. پس می‌توان با استفاده از الگوریتم‌هایی مانند فراابتکاری‌ها، یک بهینه‌ی محلی را در زمانی معقول (مثلاً ۱۰دقیقه) پیدا کرد و اقدام به خریدِ این مجموعه سهام نمود. در درس قبل اشاره‌ای به تابع برازش (Fitness Function) کردیم. در این مثال، میزانِ سودی که به شخصِ خریدار می‌رسد یک خروجی از تابعِ برازش (Fitness Function) می‌تواند باشد. در واقع الگوریتمِ فراابتکاری با استفاده از تابعِ برازش، می‌خواهد تا جایی که می‌تواند سودِ حاصل از خرید سهام را برای شخصِ خریدار افزایش دهد و با این‌کار تا جایی که می‌تواند به سمتِ بهینه‌ی سراسری حرکت کند. در بعضی از منابع از عبارت Cost Function یا تابع هزینه نیز استفاده می‌شود. تابع هزینه برای مسائل کمینه‌سازی به کار می‌رود و تفاوتی با تابع برازش ندارد. در واقع برعکس تابع برازش، تابع هزینه است یعنی ما به دنبال کم کردن هزینه (و ضررهای آن) هستیم.

نمونه‌ی دیگر نیز که یک مسئله‌ی سخت برای حل کردن در حوزه‌ی علم کامپیوتر است، مسئله‌ی پیش‌بینی رشد/کاهش شاخص سهامِ یک شرکتِ خاص با توجه به عناصر و عواملِ تاثیرگذار است. برای مثال، می‌خواهید قیمت سهام شرکت ایران‌خودرو را محاسبه کنید. عواملی مانند نرخ ارز، قیمت طلا، قیمت مسکن، قیمت بنزین و… از عوامل تاثیرگذار در حل این مسئله (پیش‌بینی شاخص سهام) هستند. خروجیِ تابع برازش (Fitness Function) در این‌جا می‌تواند مقدار نزدیکیِ پیش‌بینی با مقدار واقعی باشد. یعنی هر چقدر مقدارِ پیش‌بینی شده توسط الگوریتم با مقدارِ واقعی (که در آینده مشخص می‌شود)، نزدیک باشد، یعنی الگوریتم پاسخِ بهتری پیدا کرده است. پس الگوریتمِ فراابتکاری به دنبال پیدا کردن نزدیک‌ترین پیش‌بینی با پیش‌بینی واقعی (و پیدا کردن بهینه‌ی سراسری یا نزدیک به آن) در این مسئله هست.

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

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