الگوریتم های بهینه سازی و جستجوی تصادفی و تکاملی روش های نوین و کارامدی هستند که به ویژه برای یافتن جواب های بهینه سراسری مسائل به کار می روند. ویژگی تصادفی بودن این الگوریتم ها مانع از گیر افتادن در نقاط بهینه موضعی می شوند. در مسائل بهینه سازی عملی مانند طراحی های مهندسی، مدیریت سازمان ها و سیستم های اقتصادی معمولاً توجه اصلی معطوف به بدست آوردن جواب های بهینه سراسری است. بسیاری از این الگوریتم ها الهام گرفته شده از سیستم های زیستی هستند که الگوریتم اجتماع کرم شب تاب از این دست می باشد. این الگوریتم با مدلسازی رفتار مجموعه ای از کرم های شب تاب و تخصیص مقداری مرتبط با برازندگی مکان هر کرم شب تاب به عنوان مدلی برای میزان رنگدانه های شب تاب و به روز کردن مکان کرم ها در تکرار های متوالی الگوریتم به جستجوی جواب بهینه مسئله می پردازد. در واقع دو فاز اصلی الگوریتم در هر تکرار فاز به روز کردن رنگدانه و فاز حرکت هستند. کرم های شب تاب به سمت کرم های شب تاب دیگر با رنگدانه بیشتر که در همسایگی آنها باشند حرکت می کنند. به این ترتیب طی تکرار های متوالی مجموعه به سمت جواب بهتر متمایل می گردد.
الگوریتم بهینه سازی اجتماع کرم شب تاب در سال 2005 توسط کریشناناند و گهوز ارائه شده است. کریشناناند و گهوز در سال های 2006 تا 2008 مبانی نظری این الگوریتم را توسعه داده اند.
هوش توده ای (Swarm Intelligence) به طوری که در اجتماعات طبیعی بروز پیدا می کند نتیجه عمل هایی از جانب افراد توده است که بر طبق اطلاعات محلی انجام می شوند. به طور معمول رفتار توده به اهدافی پیچیده تر و در سطح توده ای راه می برد. نمونه هایی از این پدیده شامل گروه های مورچگان، زنبورهای عسل ، پرندگان و … می باشد.
مکانیسم های تصمیم گیری غیرمتمرکز در این نمونه ها و سایر گونه های طبیعی دیگر الهام بخش طراحی الگوریتم های گسترده ای برای حل مسائل پیچیده مانند بهینه سازی ، تصمیم گیری چند عامله و روبوتیک شده است. در این بخش به بررسی الگوریتم طرح شده توسط کریشناناند و همکارانش بر اساس رفتار اجتماعی کرم های شب تاب پرداخته می شود.
الگوریتم GSO با قرار دادن جمعیتی n عضوی از کرم های شب تاب در نقاط مختلف فضای جستجوی مسئله بهینه سازی به صورت تصادفی آغاز می شود. در ابتدا همه ی کرم ها مقدار یکسانی از لوسی فرین به اندازه ی l در اختیار دارند. هر تکرار الگوریتم شامل یک فاز به روز کردن لوسی فرین و یک فاز به روز کردن مکان کرم ها می باشد:
به روز کردن لوسی فرین:
مقدار لوسی فرین هر کرم در هر تکرار با توجه به مقدار برازندگی مکان آن کرم تعیین می شود. به این ترتیب که در هر تکرار با توجه به مقدار برازندگی و متناسب با آن مقداری به لوسی فرین فعلی کرم افزوده می شود. ضمن اینکه به منظور مدل کردن افت تدریجی با زمان مقداری از لوسی فرین فعلی با ضریبی کمتر از 1 از آن کم می شود. بدین ترتیب رابطه ی به روز کردن لوسی فرین به صورت زیر مطرح شده است:
که در آن li(t)، li(t-1) ، J(xi(t)) به ترتیب مقدار جدید لوسی فرین، مقدار قبلی لوسی فرین و برازندگی مکان کرم i در تکرار t از الگوریتم بوده و ρ وγ اعداد ثابتی برای مدل کردن افت تدریجی و تاثیر برازندگی بر لوسی فرین می باشند.
حرکت کرم های شب تاب:
در خلال فاز حرکت، هر کرم به صورت احتمالاتی به سمت یکی از همسایگانش که لوسی فرین بالاتری دارد حرکت می کند. به این ترتیب کرم ها به سمت همسایگان با درخشندگی بیشتر حرکت می کنند. در شکل * نمایشی از همسایگی ها ،مفاهیم شعاع تصمیم و شعاع حسگری کرم ها مشاهده می شود. در قسمت b از این شکل کرم ها بر اساس میزان لوسی فرین رتبه بندی شده اند، به این صورت که کرم با شماره 1 بیشترین درخشش را دارد. شعاع تصمیم rd در واقع مشخص کننده ی محدوده ای است که کرم های در آن محدوده همسایه محسوب می شوند برای سطح لوسی فرین با کرم مورد نظر مقایسه می شوند. شعاع حسگری rs مشخص کننده ی حد بالایی برای شعاع تصمیم می باشد. در واقع در طی تکرار های الگوریتم GSO شعاع تصمیم کرم ها بسته به شرایطی که در آن قرار دارند تغییر می کند ولی به هر صورت شعاع تصمیم هر کرم از شعاع حسگری آن بیشتر نمی شود. شعاع حسگری مدل کننده حداکثر توانایی کرم ها برای مشاهده ی کرم های دیگر می باشد. در شکل 13 چهار کرم شبتاب a, b, c, d میزان لوسی فرین بیشتری نسبت به کرم شبتاب e دارند ولی کرم شبتاب e تنها در محدوده مشاهده کرم شبتاب های c و d قرار دارد و بنابراین دو جهت ممکن برای انتخاب به منظور حرکت به سمت کرم درخشنده تر پیش روی آن است.
شکل 13. (a) نمایش مفاهیم شعاع تصمیم rd و شعاع حسگری rd. برای کرم k-اُم و j-اُم نسبت به کرم i-اُم داریم: d(k,i)=d(j,i) <rs rdk < بنابراین با توجه به اینکه کرم i در شعاع حسگری هر دو کرم k و j قرار دارد ولی شعاع تصمیم کرم k کوچکتر از فاصله لازم است بنابراین تنها کرم j از اطلاعات کرم i استفاده می کند. (b) گراف جهت دار با توجه به نسبت لوسی فرین های کرم ها در همسایگی هم، که در آن کرم ها بر اساس میزان لوسی فرین مرتب شده اند و کرم با درخشش بیشتر با رتبه 1 نمایش داده شده است.
برای هر کرم شب تاب i احتمال حرکت به سمت همسایه درخشنده تر j به صورت زیر تعریف می گردد:
که در این رابطه .
Ni(t) مجموعه کرم های شبتاب همسایه کرم شبتاب i در زمان t ، dij(t) فاصله اقلیدسی بین کرم شبتاب i و j در زمان t و rdi(t) بیانگر برد همسایگی متغیر مربوط به کرم شب تاب i در زمان t است. با فرض انتخاب شدن کرم شبتاب j توسط کرم شبتاب i (با احتمال p که از رابطه * بدست می آید) معادله حرکت زمان-گسسته ی کرم شب تاب را می توان به شکل زیر نوشت:
که درآن xi(t) بردار m بعدی مکان کرم شب تاب i در زمان t است، ||.|| عملگر نرم اقلیدسی را نشان می دهد و s اندازه گام حرکت است.
به روز کردن برد همسایگی:
به هر کرم شبتاب i یک همسایگی تخصیص می یابد که برد شعاعی rid آن به طور طبیعی دینامیک است
(0 < rid ≤ rs). دلیل عدم استفاده از یک همسایگی ثابت نیاز به توجیه دارد، از آنجایی که کرم شب تاب ها تنها به اطلاعات محلی در همسایگی شان برای حرکت نیاز دارند، انتظار می رود تعداد قله هایی قابل شناسایی تابع برد حسگری شعاعی است. در واقع اگر برد حسگری هر کرم شبتاب کل فضای جستجو را پوشش دهد همه ی کرم ها به سمت بهینه ی سراسری حرکت می کنند و بهینه های محلی نادیده گرفته می شوند. از آنجا که اطلاعات از پیش دانسته درباره ی تابع هدف (به عنوان مثال تعداد قله ها و یا فاصله بین قله ها) برای مسئله فرض نمی شود به سادگی نمی توان برد همسایگی ثابتی مناسب برای تمامی تابع های هدف در نظر گرفت. به عنوان نمونه انتخاب برد همسایگی rd برای تابع هدف هایی با کمترین فاصله میان قله های بیشتر از rd نسبت به تابع هایی که این فاصله برای آنها کمتر از rd است مناسبتر است. بنابراین GSO از یک برد همسایگی تطبیقی برای شناسایی وجود قله های چندگانه در مسائل بهینه سازی توابع چند مد بهره می گیرد.
با فرض r0 به عنوان برد همسایگی اولیه برای هر کرم شبتاب (rid(0) = r0 )، در هر تکرار الگوریتم GSO برد همسایگی هر کرم شبتاب با توجه به رابطه زیر به روز می شود:
که در آن β پارامتری ثابت و nt پارامتری برای کنترل تعداد همسایگی ها می باشد.
پیشنهاد بهینه سازی تکاملی ترکیبی کرم شب تاب
[thrive_leads id='1265']