الگوریتم بهینه سازی کرم شب تاب FA‏ ‏

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

الگوریتم های بهینه سازی و جستجوی تصادفی و تکاملی روش های نوین و کارامدی هستند که به ویژه برای یافتن جواب های بهینه سراسری مسائل به کار می روند.

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

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

کرم های شب تاب به سمت کرم های شب تاب دیگر با رنگدانه بیشتر که در همسایگی آنها باشند حرکت می کنند. به این ترتیب طی تکرار های متوالی مجموعه به سمت جواب بهتر متمایل می گردد.

الگوریتم بهینه سازی اجتماع کرم شب تاب در سال 2005 توسط کریشناناند و گهوز ارائه شده است.  کریشناناند و گهوز در سال های 2006 تا 2008 مبانی نظری این الگوریتم را توسعه داده اند.

هوش توده ای (Swarm Intelligence) به طوری که در اجتماعات طبیعی بروز پیدا می کند نتیجه عمل هایی از جانب افراد توده است که بر طبق اطلاعات محلی انجام می شوند. به طور معمول رفتار توده به اهدافی پیچیده تر و در سطح توده ای راه می برد. نمونه هایی از این پدیده شامل گروه های مورچگان، زنبورهای عسل ، پرندگان و … می باشد.

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

 الگوریتم کرم شب تاب FA‏ ‏

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

مشخصه اصلی کرم های شب تاب به منظور استفاده از آن در الگوریتم کرم شب تاب ، نور چشمک زن آن ها است. این  نورها دو عملکرد بنیادین دارند: جذب جنس مخالف و هشدار دادن دشمن.

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

تاریخچه الگوریتم کرم شب تاب

الگوریتم کرم شب تاب، نخستین بار توسط زین شی یانگ[1] در سال ۲۰۰۷ ارائه شد (یانگ[2]، ۲۰۰۸). یانگ، الگوریتم­های فرا ابتکاری زیادی از جمله الگوریتم فاخته، الگوریتم خفاش، الگوریتم گرده‌افشانی گل­ها[3] و الگوریتم کرم شب تاب را ارائه کرده است. وی فارغ‌التحصیل دکتری ریاضیات کاربردی از دانشگاه آکسفورد[4] بوده و تاکنون بیش از ۲۱ کتاب و ۱۴۰ مقاله علمی به چاپ رسانده است.

یانگ، در فصل ۱۷ یکی از کتاب های خود با نام بهینه‌سازی مهندسی[5] که در سال ۲۰۱۰ به چاپ رسیده، به معرفی و تشریح الگوریتم کرم شب تاب پرداخته است. در این فصل ابتدا به بحث نور و چگونگی تولید نور توسط کرم های شب تاب مطرح‌شده و سپس جذابیتی که کرم‌های شب تاب نسبت به هم دارند، مورد بحث قرار گرفته است. در ادامه فصلی، به پیاده‌سازی این الگوریتم می­پردازیم ( یانگ، ۲۰۱۰).

تشریح الگوریتم کرم شب تاب

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

از آنجا که رفتار طبیعی کرم­های شب تاب در طبیعت پیچیده و انعکاس دقیق آن‌ها در یک الگوریتم بسیار پیچیده است، یک سری قوانین کلی و ساده ساز برای FA تعریف می­شود (فیستر[6] و همکاران، ۲۰۱۵):

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

[1] Xin She Yang

[2] Yang

[3] Flower Pollination Algorithm

[4] Oxford University

[5] Engineering Optimization: an introduction with metaheuristic applications

[6] fister