بخشی از مقاله
چکیده
هوش جمعی یکی از قوی ترین تکنیک های بهینه سازی می باشد که بر مبنای رفتارهای گروهی است. الگوریتم خفاش یک
الگوریتم الهام گرفته از رفتار جمعی خفاش ها در محیط طبیعی است که در سال 2010 توسط یانگ ارائه شد. این الگوریتم بر
مبنای استفاده از خاصیت انعکاس صدا توسط خفاش ها است. خفاش ها مسیر و محل دقیق طعمه خود را بوسیله فرستادن امواج صوتی و دریافت بازتاب آن، پیدا می کنند. زمانی که امواج صوتی به سمت فرستنده امواج (خفاش) باز می گردد، این پرنده می تواند یک تصویر صوتی از موانع روبروو محیط اطراف خود رسم کند و محیط اطراف را به خوبی ببیند. با استفاده از این سیستم، خفاش ها می توانند اجسام متحرک مثل حشرات و اجسام بی حرکت مثل درختان را تشخیص دهند. با بررسی و بهینه سازی این الگوریتم در سیستمها و شبکه های کامپیوتری و تطبیق آن با سیستمهای خبره و هوشمند میتوان به تکنیکهای نوین جهت مسیر
یابی و تخمین مسافت در کاربردهای هوا و فضا، بهینه سازی سیستمهای پرواز در دید کور با استفاده از خلبان خودکار، رانندگی توسط خودروهای هوشمند با قابلیت تشخیص موانع ثابت از موانع متحرک، تخمین مسافت و محاسبه تاخیر در گره های شبکه های کامپیوتری، تخمین بار و ترفیک شبکه و بهینه سازی الگوریتمهای هوشمند مسیریابی در روترها و... سایر کاربردهای فنی
×مهندسی پرداخت. این مقاله به توضیح عملکرد این الگوریتم و کاربردهای متنوع آن پرداخته است. کلمات کلیدی: هوش جمعی ، تکنیک های بهینه سازی ، الگوریتم خفاش
مقدمه
امروزه گرایش به استفاده از الگوریتم های الهام گرفته از طبیعت و مبتنی بر هوش جمعی حیوانات بسیار زیاد است. بخصوص در مقوله ی تکنیک های بهینه سازی این الگوریتم ها مورد استقبال زیادی قرار گرفته اند.
با نگاه دقیق به طبیعت و تنوع بسیار زیاد حیواناتی که بصورت جمعی در زندگی خود از روش ها و متدهای خاصی پیروی می کنند،
بدیهی است که الگوریتم های زیادی را می توان با الهام از آنها مطرح کرد.
1
برای مثال الگوریتم ژنتیک که برای اولین بار توسط جان هلند معرفی شد. این الگوریتم از اصول انتخاب طبیعی داروین برای یافتن
فرمول بهینه جهت پیش بینی یا تطبیق الگو استفاده می کنند. این الگوریتم از تکامل ژنتیکی به عنوان الگوی حل مساله کمک می
گیرد. مساله ای که باید حل شود ورودی است و راه حل ها طبق یک الگو کدگذاری می شوند که تابع برازش نام دارد. هر راه حل کاندیدا که به عنوان کروموزوم در نظر گرفته می شود را ارزیابی می کند که اکثرا به صورت تصادفی انتخاب می شوند. همچنین الگوریتم اجتماع ذرات که مبتنی بر رفتار جمعی پرندگان می باشد و در سال 1995 توسط کندی و ابرهارت ارائه شده است [1] و
در زمینه حل مسائل بهینه سازی پیوسته کاربرد فراوانی دارد.الگوریتم های بسیاری در این زمینه وجود دارد مثل الگوریتم فاخته،
الگوریتم کرم شب تاب و ... . لازم به ذکر است که یکی از مهمترین اکتشافات علم نوین که امروزه مرکز توجه بسیاری از علما و
دانشمندان قرار گرفته و منجر به حل بسیاری از مسائل لاینحل گردیده موضوع شبکه های عصبی مصنوعی میباشد که الهام گرفته از
طبیعت عصبی انسان است. با توجه به موارد و مثال های ذکر شده به این نتیجه می رسیم که روز به روز به الگوریتم های الهام گرفته
از طبیعت اضافه می شود.
الگوریتم خفاش مبتنی بر ویژگی پژواک یابی ریزخفاش ها است. [2] در حالت کلی دو نوع خفاش وجود دارد که نوع اول بزرگ
خفاش ها هستند و نوع دوم ریزخفاش ها نام دارند. ریزخفاش ها از این ویژگی برای پرواز در شب و شکار استفاده می کنند.
الگوریتم خفاش با استفاده از تکنیک تنظیم فرکانس، تنوع راه حل های موجود در جمعیت را افزایش می دهند. قسمت اول این مقاله در مورد ساختار کلی این الگوریتم و چگونگی کمک گرفتن ریزخفاش ها از پژواک یابی برای رسیدن به هدف می باشد، در قسمت دوم توضیحی اجمالی در مورد انواع مختلف این الگوریتم ارائه شده است. قسمت سوم مربوط به کاربردهای الگوریتم خفاش در زمینه های مختلف است.
ینه های مختلف است.
- 1 الگوریتم خفاش
الگوریتم خفاش بر مبنای ویژگی پژواک یابی است که توسط ریزخفاش ها مورد استفاده قرار می گیرد.
- 1 - 1 پژواک یابی ریزخفاش ها
در حدود 1240 گونه ی مختلف خفاش وجود دارد که روی هم رفته 20 درصد از گروه های پستانداران را از آن خود کرده است.
پژواک یابی ریزخفاش ها در عمل یک سامانه ادراکی است که در آن موج های فرا صوتی برای بدست آوردن پژواک، تولید می شوند. مغز و دستگاه عصبی خفاش با مقایسه ی موج های فرستاده شده و موج های بازتاب شده می تواند تصویری از فضای پیرامون
و جزئیاتش را برای خود بسازد. این توانایی به ریزخفاش ها اجازه می دهد تا در تاریکی مطلق شکارشان را شناسایی کنند. شدت موج تولیدی توسط خفاش 130 دسی بل است و برای شکار طعمه از فرکانس 15 کیلوهرتز تا 200 کیلوهرتز استفاده می کند. این
درحالی است که دامنه شنوایی انسان از 20 هرتز تا 20 کیلوهرتز است.خفاش برای آنکه داده های بدست آمده را شناسایی کند باید
بتواند صدای تولیدی توسط خودش را از پژواک آن جدا کند. [3] ریزخفاش ها برای این هدف دو روش دارند:
پژواک یابی با چرخه هایی با بازه ی زمانی کوتاه : این دسته از خفاش ها می توانند صدای فرستاده شده از سوی خود را با کمک زمان سنجی، از صدای بازتاب شده، شناسایی کنند.
2
پژواک یابی با چرخه هایی با بازه ی زمانی بلند : این خفاش ها صدایی پیوسته تولید می کنند و پالس ها و پژواک ها را با تغییر
بسامد از هم جدا می کنند. آنها می توانند بسته به سرعت پرواز، پالس هر بسامد تولیدی را تغییر دهند. به این ترتیب پژواک دریافتی
همچنان در بازه ی شنوایی مناسب قرار می گیرد. [3]
- 1 - 2 قوانین الگوریتم خفاش
با توجه به ویژگی پژواک یابی خفاش ها،Yang Xin-Sheدر سال [4] 2010 الگوریتم خفاش را بر مبنای سه قانون اساسی زیر بنا نهاد :
-1 تمامی خفاش ها با بکارگیری پژواک یابی می توانند مسافت را تخمین بزنند و تفاوت بین طعمه و موانع ثابت را تشخیص
دهند.
-2 خفاش ها به صورت تصادفی با سرعت vi در جهت xi، با فرکانس fmin، به طول موج و بلندی صدای A0 در جست و جوی شکار هستند. همچنین آنها می توانند طول موج پالس های منتشر شده را به طور اتوماتیک تنظیم کرده و نرخ انتشار پالس خود را طبق نزدیکی طعمه ی خود، مطابقت دهند.
-3 بلندی صدا می تواند به طرق مختلفی تغییر کند ولی فرض می کنیم که بلندی صدا از A0 تا Amin تغییر می کند.
- 1 - 3 حرکت خفاش ها
هر خفاش به سرعت vit و مکان xit با تکرار t در یک جست و جوی d بعدی و یا فضای راه حل وابسته است. در میان تمامی خفاش ها تنها یک راه حل بهینه ی x* وجود دارد[4]
بنابراین سه قانون ذکر شده درقسمت قبل را می توان از طریق فرمول های زیر محاسبه کرد:
(1) Fi= f min+ (f max - f min)
(2) Vit = v it-1 + (x it-1 - x*)fi
(3) Xit = xit-1 + vit
بطوریکه [0,1] یک بردار تصادفی از یک توزیع یکنواخت بدست آمده است.
همانطور که ذکر شد می توان از طول موج یا فرکانس نیز برای پیاده سازی استفاده کرد.در اینجا fmin = 0 و fmax = 100
در نظر گرفته شده است که بسته به اندازه ی مساله علاقه مندی دارد.
