فرادرسالگوریتم بهینهسازی جهش قورباغه – پادکست پرسش و پاسخ
«الگوریتم بهینهسازی جهش قورباغه» (Shuffled Frog-Leaping Algorithm | SFLA)، از جمله الگوریتمهای فراابتکاری (Meta-Heuristic) است که برای حل مسائل «بهینهسازی ترکیبیاتی» (Combinatorial Optimization) مورد استفاده قرار میگیرد. در زبان فارسی، از این الگوریتم با عناوین «الگوریتم قورباغه» و «الگوریتم جهش قورباغه» نیز یاد میشود. بنابراین، نباید آن را با «الگوریتم دروازه نوریِ مبتنی بر تفکیک فرکانسی» (Frequency-Resolved Optical Gating | FROG) اشتباه گرفت.
الگوریتم بهینهسازی جهش قورباغه (یا به اختصار الگوریتم قورباغه)، از رفتار اجتماعی قورباغهها الهام گرفته شده است و میتوان آن را در دسته «الگوریتمهای ممتیک» (Memetic Algorithm) نیز طبقهبندی کرد. در فرادرس، آموزشی به این الگوریتم اختصاص داده شده است. در همین راستا، یکی از دانشجویان این دوره، پرسشی را مطرح کردند که دکتر «سید مصطفی کلامی هریس»، در پادکستی که در ادامه آمده، به طور مشروح به آن پاسخ دادهاند. نسخه متنی این پادکست نیز در همین مطلب قرار دارد. البته، منبع اصلی همچنان فایل صوتی محسوب میشود.
پادکست پیرامون الگوریتم بهینهسازی جهش قورباغه
ذخیره کردن این فایل صوتی: لینک دانلود
نسخه نوشتاری
یکی از مخاطبین سوالی را مطرح کردند با این مضمون که میخواهند با استفاده از الگوریتم قورباغه که آموزش آن در فرادرس موجود است، مسالهای را حل کنند که در آن هدف بیشینه کردن «میزان برازش» (Fitness) است. در اغلب آموزشهایی که در فرادرس موجود هستند، مانند آموزشهای الگوریتمهای بهینهسازی و تکاملی گوناگون، مساله کمینهسازی حل شده است؛ یعنی یک تابع زیان (Cost Function) وجود داشته که هدف، کم کردن مقدار آن بوده است. اما اگر هدف، حل عکس این مساله باشد، چه میشود؟ اگر بخواهیم میزان برازش (میزان برازش) را در واقع بهبود بدهیم و بیشینه کنیم چه راهکاری وجود دارد؟ در واقع اگر مساله «بیشینهسازی» (Maximization) باشد، چه میشود؟
در چنین مواردی، چند راهکار میتواند مورد استفاده قرار بگیرد. یکی از این راهکارها این است که کاربر اصلا کد این مساله را دست نزند؛ یعنی کد الگوریتم همین طور باشد. در آن تابع زیان (Cost Function)، همین تابع میزان برازش ( Fitness Function)، تعریف شود، فقط قرینه میزان برازش (Fitness) به عنوان خروجی بازگردانده شود. زیرا، از نظر ریاضی میدانیم که بیشینه کردن تابع (F(x، مانند کمینه کردن منفی (F(x است. بنابراین، میتوان با ضرب کردن خروجی در یک منفی، خیلی راحت این کار را انجام داد.
یک راه کمی سختتر این است که کد را کمی دستکاری کرد؛ در قسمتی که بهتر و بدتر بودن را بررسی میکند، در واقع دو پاسخ با یکدیگر در رقابت هستند. در آنجا پیش از این گفته شده که هر چه کمتر باشد بهتر است؛ اکنون باید گفت هر چه بیشتر باشد بهتر محسوب میشود. در حالت خیلی کلیتر، آموزشی در فرادرس موجود است با عنوان «پیادهسازی الگوریتمهای فراابتکاری با استفاده از زبان برنامهنویسی #C»؛ در آن آموزش نوع مساله تعریف شده که کمینهسازی یا بیشنهسازی است و بر اساس نوع مساله، بهتر و بدتر تعریف میشود.
در واقع، نوع مساله بالاتر (در ابتدای کد #C) - در کد متلب هم این کار را میتوانیم انجام بدهیم - تعریف میشود و مشخص میشود که از چه نوعی است؛ بعد، آن پایین مقایسه به یک تابع سپرده میشود که این تابع، دو تا پاسخ الف و ب و نوع مساله را میگیرد. حالا نوع مساله اگر از نوع کمینهسازی باشد الف از ب بهتر است، به شرطی که کمتر از آن باشد. اما پارامتر سوم که نوع مساله است اگر که بیشنهسازی باشد، الف از ب اگر بیشتر باشد بهتر است. یعنی مقایسه را باید به داخل یک تابع برد، تا بتوان به این روش این کار را انجام داد که خیلی کلیتر هم میشود و در واقع فرد خیلی راحت میتواند در بالا فقط نوع مساله را تغییر بدهد تا عوض شود (بیشینهسازی یا کمینهسازی بشود).
حالا این نوع پیادهسازی به غیر از زبان #C، با زبان دیگری در فرادرس موجود نیست؛ ولی توصیه میشود افراد آن آموزش را مشاهده کنند، زیرا از یک روش خیلی پیشرفتهتر از برنامهنویسی در آن استفاده میشود و به هر حال یک تجربه متفاوت است. لزومی هم ندارد آموزش حتما خریداری شود، چون بخش زیادی از درسهای آن رایگان هستند. به نظر من، این سبک برنامهنویسی چیزی است که افراد در پروژههای بزرگ به آن احتیاج دارند. به طور خاص، اگر دوستانی که در مقطع دکتری تحصیل میکنند، با مسائل بزرگی درگیر هستند و یا سالها است که با متلب کار میکنند، یک نیم نگاهی هم به یک زبان برنامهنویسی کامپایل شده مانند #C یا جاوا داشته باشند که الگوی آن در همان آموزش داده شده، خیلی میتواند خوب باشد.
به هر حال، هدف کلا این بود که راه حلی برای مساله طرح شده بیان شود. این مساله را به سادگی، با قرینه کردن میتوان انجام داد. روشی که کار بیشتری میبرد و فقط مسائل بیشینهسازی را حل میکند، عوض کردن جهت نامساوی است. روش اصولی و درست این کار هم آن است که اساسا این مقایسه به یک تابع سپرده شود که نوع مساله نیز جز ورودیهای همین تابع باشد.
برای دانلود و شنیدن دیگر پادکستهای دکتر سید مصطفی کلامی هریس در مجله فرادرس، روی این لینک [+] کلیک کنید.
اگر نوشته بالا برای شما مفید بوده است، آموزشهای زیر نیز به شما پیشنهاد میشوند:
