بهینهسازی، مسئله‌ای که به‌احتمال زیاد اسمش را تاکنون شنیده‌اید چرا که نه‌تنها در مطالعات علمی بلکه در فعالیت‌های روزمره ما هم ظاهر می‌شود؛ بهعنوان مثال، زمانی که شخصی می‌خواهد از یک مکان به مکان دیگر برود و چندین مسیر ممکن دارد، باید تصمیم بگیرد که کدام مسیر را طی کند. این تصمیم میتواند با هدف به حداقل رساندن زمان سفر، مصرف سوخت و... باشد مشکلاتی ازاین دست را تنها می‌توان با نگاه کردن به نتیجه هر مورد حل کرد ولی در مسائل واقعی نمی‌توان چنین کاری انجام داد برای همین روش‌های مختلفی برای دیگر مسائل پیشنهاد شده است.
از زمان معرفی الگوریتم‌های تکاملی، مطالعات زیادی بر روی الگوریتم‌های اکتشافی انجام شده است. معرفی‌های جدید یکی از زمینه‌های تحقیقاتی پیشرو بوده است. در حال حاضر، بیش از 40 الگوریتم فراابتکاری وجود دارد. بیشتر این الگوریتم‌های جدید با تقلید از یک سناریو از طبیعت معرفی می‌شوند؛ بهعنوان مثال، الگوریتم ژنتیک از نظریه داروین در مورد بقای بهترین‌ها الهام گرفته شده است. الگوریتم کرم شب تاب از نحوه سیگنال‌دهی کرم شب تاب به یکدیگر با استفاده از نور چشمکزن برای جفت‌گیری یا شناسایی شکارچیان الهام گرفته شده است. در این مقاله هدف این است که با الگوریتم کرم شب تاب آشنا شویم.
الگوریتم کرم شب تاب چیست؟
تعریف
الگوریتم کرم شب تاب یک الگوریتم بهینه‌ساز فراابتکاری است که از رفتار چشمکزن کرم‌های شب تاب الهام گرفته شده است. این الگوریتم یک الگوریتم فراابتکاری کارآمد است که از طبیعت الهام گرفته شده است و مبتنی بر جمعیت است و راه حل خود را بر اساس ویژگی‌های کرم شب تاب استخراج میکند. از این الگوریتم می‌توان برای حل مسائل بهینهسازی استفاده کرد.
الگوریتم کرم شب تاب یک سری ویژگی‌هایی دارد که باید به آنها توجه کرد:
- کرم‌های شب تاب تک جنسیتی هستند به‌طوری‌که یک کرم شب تاب بدون توجه به جنسیت آنها جذب سایر کرم‌های شب تاب می‌شود.
- جذابیت متناسب با روشنایی است و هر دوی اینها با افزایش فاصله کاهش می‌یابند.
- برای هر دو کرم شب تاب چشمکزن، کرم شب تاب کم‌نورتر به سمت پرنورتر حرکت میکند.
- درصورتی‌که روشن‌تر از یک کرم شب تاب خاص وجود نداشته باشد، به طور تصادفی حرکت میکند.
- روشنایی یک کرم شب تاب توسط تابع هدف تعیین می‌شود.
تاریخچه الگوریتم کرم شب تاب
الگوریتم کرم شب تاب اولین بار در سال 2007 توسط Xin-She Yang در دانشگاه کمبریج معرفی شد.
گام‌های الگوریتم کرم شب تاب
الگوریتم کرم شب تاب به ابزاری مهم برای حل سخت‌ترین مسائل بهینهسازی در تقریباً تمام زمینه‌های بهینهسازی و همچنین مسائل مهندسی تبدیل شده است. مراحل انجام این الگوریتم به شرح زیر است:
- مقداردهی جمعیت: جمعیت با راه‌حل‌های تصادفی مقداردهی اولیه می‌شود.
- ارزیابی شایستگی: میزان شایستگی هر راه‌حل ارزیابی می‌شود.
- به‌روزرسانی شدت نور: شدت نور هر کرم شب تاب بر اساس ارزش تناسب آن به‌روز می‌شود.
- حرکت کرم شب تاب: هر کرم شب تاب به سمت کرم شب تاب دیگری حرکت میکند که از خودش روشن‌تر است.
- به‌روزرسانی موقعیت: موقعیت هر کرم شب تاب بر اساس شدت نور جدید آن به‌روز می‌شود.
شبه کد الگوریتم کرم شب تاب
Problem Definition: Objective function f(x) #تابع هدف
Randomly generate an initial population of n fireflies #تولید جمعیت اولیه از کرم‌های شب‌تاب
Fitness calculation of each firefly #ارزیابی میزان شایستگی هر کرم شب‌تاب
while termination condition do
for i=1:N do
(all fireflies)
for j=1:N do
(all n fireflies)
if (fitness (yi) > fitness (yj)) then #کرم شب‌تاب j به سمت کرم شب‌تاب i حرکت میکند.
yi is brighter than yj
move yj firefly towards yi firefly
end
#مقدار پارامتر جذابیت بر اساس فاصله محاسبه و آپدیت می‌شود.
vary attractiveness with distance r between the fireflies
end
end
#کرم‌های شب‌تاب بر اساس میزان شایستگی مرتب می‌شوند و بهترین جواب مشخص می‌شود.
sort the fireflies and find the global best
end
کاربردهای الگوریتم کرم شب تاب
از الگوریتم کرم شب تاب برای مسائل مختلف بهینهسازی مانند انتخاب ویژگی، پردازش تصویر و خوشه‌بندی استفاده شده است. در اینجا چند مورد استفاده از الگوریتم کرم شب تاب آورده شده است:
- انتخاب ویژگی: برای انتخاب ویژگی در یادگیری ماشین استفاده شده است.
- پردازش تصویر: برای تقسیم‌بندی تصویر و تشخیص لبه استفاده شده است.
- خوشه‌بندی: برای تعیین تعداد بهینه خوشه‌ها در داده کاوی استفاده شده است.
- رباتیک: برای برنامه‌ریزی مسیر در رباتیک استفاده شده است.
- زمان‌بندی: مسائل زمان‌بندی برای تعیین زمان‌بندی بهینه استفاده شده است.
- زیست‌پزشکی و مراقبت‌های بهداشتی: در زمینه‌های مهم پزشکی مانند طبقهبندی سرطان سینه، تصاویر شبکیه انسان، طبقهبندی تومور سینه، تشخیص تومور مغزی، نظارت بر سلامت و غیره استفاده شده است.
پیاده‌سازی الگوریتم کرم شب تاب در پایتون
در نمونه کد ساده زیر الگوریتم کرم شب تاب برای پیداکردن نقطه بهینه سراسری به زبان پایتون پیاده‌سازی شده است:
قبل از استفاده از کد باید کتابخانه الگوریتم کرم شب تاب را نصب کنید:
pip install FireflyAlgorithm
کلاس مربوط به الگوریتم کرم شب تاب:
import numpy as np
from numpy.random import default_rng
class FireflyAlgorithm:
def __init__(self, pop_size=20, alpha=1.0, betamin=1.0, gamma=0.01, seed=None):
self.pop_size = pop_size
self.alpha = alpha
self.betamin = betamin
self.gamma = gamma
self.rng = default_rng(seed)
def run(self, function, dim, lb, ub, max_evals):
fireflies = self.rng.uniform(lb, ub, (self.pop_size, dim))
intensity = np.apply_along_axis(function, 1, fireflies)
best = np.min(intensity)
evaluations = self.pop_size
new_alpha = self.alpha
search_range = ub - lb
while evaluations <= max_evals:
new_alpha *= 0.97
for i in range(self.pop_size):
for j in range(self.pop_size):
if intensity[i] >= intensity[j]:
r = np.sum(np.square(fireflies[i] - fireflies[j]), axis=-1)
beta = self.betamin * np.exp(-self.gamma * r)
steps = new_alpha * (self.rng.random(dim) - 0.5) * search_range
fireflies[i] += beta * (fireflies[j] - fireflies[i]) + steps
fireflies[i] = np.clip(fireflies[i], lb, ub)
intensity[i] = function(fireflies[i])
evaluations += 1
best = min(intensity[i], best)
return best
برای اجرای کد، پارامترهای لازم را باید تعیین کنیم از جمله:
- تابع بهینه‌ساز
- حد بالا (ub) و پایین (lb)
- بیشینه تعداد تکرارهای لازم برای همگرایی به جواب بهینه (max_evals)
- تعداد ابعاد (dim)
قطعه کد زیر یک نمونه اجرا با استفاده از تابع بهینه‌ساز sphere در فضای دوبعدی است:
import numpy as np
from fireflyalgorithm import FireflyAlgorithm
def sphere(x):
return np.sum(x ** 2)
FA = FireflyAlgorithm()
best = FA.run(function=sphere, dim=2, lb=-5, ub=5, max_evals=10000)
print(best)
مزایا و معایب الگوریتم کرم شب تاب
مزایا:
- پیاده‌سازی آن آسان است و به پارامترهای کمی نیاز دارد.
- در یافتن بهینه جهانی مؤثر است.
- در برابر نویز مقاوم است و میتواند عملکردهای چندوجهی را انجام دهد.
- از نظر محاسباتی کارآمد است.
معایب:
- میتواند در بهینه محلی گیر کند.
- میتواند به انتخاب پارامترها حساس باشد.
- ممکن است در حل برخی از مسائل کند باشد.
الگوریتم کرم شب تاب تغییریافته
الگوریتم کرم شب تاب برای بهبود عملکرد آن با روش‌های مختلفی اصلاح شده است. در اینجا چند نمونه از الگوریتم‌های اصلاح شده کرم شب تاب آورده شده است:
- NMSA_FFA: این الگوریتم شامل خود تطبیق دادن پارامترهای کنترل، یک مدل جمعیت، و یک روش جستجوی محلی است که تلاش میکند اکتشاف و بهره‌برداری را با جمعیت نخبه و پارامتر خود تطبیق آلفا متعادل کند.
- MFA: الگوریتم کرم شب تاب اصلاح شده (MFA) یک الگوریتم بهینهسازی فراابتکاری الهام گرفته از طبیعت است که برای بهینهسازی طراحی سازه چندبعدی استفاده می‌شود.
جمع‌بندی
در این مقاله با یک الگوریتم فراابتکاری به‌نام الگوریتم کرم شب تاب آشنا شدیم. ابتدا مراحل اجرای الگوریتم کرم شب تاب را بررسی کردیم و یک نمونه کد ساده از این الگوریتم را مشاهده کردیم و در نهایت، موارد استفاده از الگوریتم کرم شب تاب و مزایا و معایب این الگوریتم را مورد بحث قرار دادیم.
الگوریتم کرم شب تاب در کجا استفاده می‌شود؟
روشنایی یا شدت نور یک کرم شب تاب با مقدار تابع هدف یک مسئله مشخص تعیین می‌شود. در حوزه‌های مختلفی این الگوریتم استفاده می‌شود از جمله: مسائل بهینهسازی، مسائل شبکه و مسائل پردازش تصویر.
منظور از الگوریتم کرم شب تاب برای استخراج ویژگی چیست؟
الگوریتم کرم شب تاب بر اساس اصل هدایت نور کمتر از شدت نور ساطع شده توسط کرم شب تاب در طبیعت کار میکند. الگوریتم میتواند بهصورت تطبیقی بهترین زیرمجموعه ویژگیها را انتخاب کند و دقت طبقهبندی را بهبود بخشد.
آیا الگوریتم کرم شب تاب یک الگوریتم فراابتکاری مدرن است؟
بله، الگوریتم کرم شب تاب یک الگوریتم فراابتکاری قدرتمند و کارآمد است که عملکرد مؤثری را در حل مسائل بهینهسازی مهندسی نشان داده است. این الگوریتم رفتار چشمکزن کرم شب تاب را تقلید میکند و راه حلها را بهصورت تصادفی تولید میکند و آنها را بهعنوان کرم شب تاب در نظر میگیرد.
مطالب مرتبط
همه مقالات
