الگوریتم های فراابتکاری (Metaheuristic Algorithms)

20 مهر 1403 - خواندن 8 دقیقه - 87 بازدید

"در آفرینش آسمانها و زمین ، آمد و شد شب و روز ، کشتی هایی که برای مردم در دریا حرکت می کنند ، آبی که خداوند از آسمان نازل کرده و با آن زمین را زنده کرده است و انواع جنبندگان را در آن گسترده و همچنین در تغییر مسیر باد ها و ابرهایی که میان زمین و آسمان مسخرند نشانه هایی است برای کسانی که عقل دارند و می اندیشند!" (بقره،164)

...

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

تصور کنید برای خانه جدیدتان می خواهید یک فرش نو بخرید. احتمالا در تصمیم گیری به کیفیت و هزینه فرش جدید توجه خواهید کرد. شما با یک هدف خاص بدنبال خرید بهترین فرش در شهر خواهید گشت و با یک راه حل الگوریتمی ساده همه ی بازارهای شهر را می گردید تا بهترین مورد را پیدا کنید. شما با این روش به طور قطعی بهترین فرش را با توجه به بودجه و کیفیت درنظر گرفته شده پیدا خواهید کرد اما نکته مهم اینجاست که این راه حل بسیار زمانبر و خسته کننده خواهد بود و احتمالا شما این روش را انتخاب نمی کنید و به سراغ روش دیگری برای جستجو خواهید رفت.(روش جستجوی جامع یا Brute Force)


در روش دوم ممکن است شما با یک آمارگیری بصورت تلفنی از دوستان خود ، جستجوی اینترنتی و یا استفاده از پیج های تبلیغاتی اطلاعاتی را در مورد بهترین فروشگاه های شهر جمع آوری کنید تا فقط به آن فروشگاه ها برای خرید فرش مراجعه کنید. به بیان دیگر شما با استفاده از یک الگوریتم ابتکاری به جمع آوری اطلاعاتی می پردازید که به شما کمک می کند تا علاوه بر صرفه جویی در زمان جستجوبتوانیدنزدیکترین و بهینه ترین فرش موردنظر را با توجه به اهداف خود پیدا کنید.(الگوریتم ابتکاری یا Heuristic Algorithm)


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


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

1 - الگوریتم های فراابتکاری به « الگوریتم های الهام گرفته از طبیعت » معروف اند . این الگوریتم ها برای حل مسائل بهینه سازی و پیدا کردن بهترین راه حل از اکوسیستم و زیست بوم ها تقلید می کنند. به بیان دیگر الگوریتم های فراابتکاری از رفتارهای حیوانات ، پدیده های طبیعت و سیستم های طبیعی به عنوان یک مرجع برای یافتن بهترین راه حل الهام می گیرند تا حول یک محور طبیعی بهترین تصمیم را در یک طیف گسترده ای از راه حل ها پیدا کنند.

2 - فرایند طراحی و پیاده سازی الگوریتم های فراابتکاری دارای سه گام متوالی است : گام اول مرحله آماده سازی (preparation) است که در این مرحله باید ابتدا به شناخت مسئله پرداخته شود و سپس اهداف و فرضیات و روش الگوریتم مورد استفاده به طور شفاف بیان شود . گام دوم مرحله ساخت (construction) است که باید استراتژی حل مسئله و معیارهای اندازه گیری اهداف و عملکرد انتخاب شوند. گام سوم مرحله پیاده سازی (Implementation) است که بعد از تعاریف اهداف و پارامترها ، الگوی فراابتکاری پیاده سازی می شود و نتایج آن گزارش و جواب ها مورد تحلیل قرار می گیرند. برای حل مسائل الگوریتم های فراابتکاری ، سورس کد الگوریتم در زبان های برنامه نویسی نظیر پایتون یا متلب اجرا می شوند.

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

4 - تا کنون بیش از 100 الگوریتم برگرفته از طبیعت طراحی و در حل مسائل مختلف بکار گرفته شده اند که از مهمترین و پرکاربردترین آنها می توان به الگوریتم ژنتیک ، الگوریتم کلونی مورچگان ، الگوریتم ازدحام ذرات ، الگوریتم جست و جوی ممنوعه ، الگوریتم گرگ خاکستری ، الگوریتم شاهین هریس و ... اشاره کرد.


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

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




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

الگوریتم های فراابتکاری در زمینه های مختلف کاربردهای گسترده ای دارند. یکی از مهمترین کاربردهای این الگوریتم ها در بهینه سازی مسیرها و کاهش ترافیک شهری است. با استفاده از این الگوریتم ها، سیستم های حمل و نقل می توانند مسیرهای بهینه تری را پیشنهاد دهند و زمان سفر را بهینه سازی کنند.

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

در صنعت می توان از این الگوریتم ها برای بهینه سازی فرآیندهای تولید و کاهش هزینه ها استفاده کرد. به عنوان مثال در مدیریت زنجیره تامین، الگوریتم های فراابتکاری می توانند به بهینه سازی انبارداری و توزیع کالاها کمک کنند.


خلاصه که

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


منبع : مقالات و منابع داخلی و خارجی