یکشنبه 30 شهریور 1399 | Sunday 20 th of September 2020 صفحه اصلی گروه الکترونیکی کامپیوتر
الگوریتم بهینه سازی جمعیت مورچگان (ACO)

در مسایل بهینه­سازی با تعداد پارامتر زیاد، روش­های کلاسیک کارایی چندانی ندارند. در این گونه موارد بهتر است به جای بررسی تمام فضای جواب، از روش­های دیگری استفاده شود که به صورت هوشمند،فضای گستره جستجو را کاهش می­دهند. یکی از این روش­ها، الگوریتم بهینه­سازی کلونی مورچه­ها (ACO)می­باشد.

ACOیک فرا اکتشاف الهام گرفته شده از رفتار مورچگان طبیعی، در یافتن کوتاهترین مسیر برای رسیدن به منابع غذایی است [Yumi10] که برای اولین بار در سال 1997 توسط Dorigoو Gambardellaارایه شد [Dori97]. الگوریتم­های بهینه­سازی فرا اکتشافی بر اساس ACOدر سال­های قبل از 1990ارایه شد [Dori99]. الگوریتم کلونی مورچگان، شاخه­ای از علم تازه توسعه­یافته­ هوش مصنوعی، به نام هوش ازدحامی[1] است که درباره هوش جمعی گروه­های عامل ساده، مطالعه می­کند [Bona99].

الگوریتم ACOاز رفتار جامعه مورچگان الهام گرفته شده است. مورچه­ها حشراتی اجتماعی هستند که در کلونی­ها زندگی می­کنند و رفتار ان­ها بیشتر از این که در جهت بقای یک جزء از ان باشد، در جهت بقای کلونی است. مورچه­ها حس بینایی ندارند و استعداد خوبی در یافتن کوتاهترین مسیر بین منبع غذایی و اشیانه خود دارند که این امر به وسیله ترشح ماده شیمیایی به نام فرومون[2] به هنگام حرکت انجام می­گیرد. این الگوریتم برای اولین بار در حل مساله فروشنده دوره­گرد (TSP)به کار گرفته شد [Dori96]. سپس به طور موفقیت­امیز به مسایل مشکلزیادی، نظیر مساله تخصیص منشور قائم[3] (QAP)[Mani99]، مسیریابی در شبکه­های ارتباطی، مسایل رنگ­امیزی گراف، زمان­بندی­ها و انتخاب ویژگی اعمال شد. اگر ویژگی­ها به صورت گراف نشان داده شوند، مورچه­ها می­توانند بهترین ترکیبات ویژگی را به هنگام پیمایش گراف، کشف کنند.

مورچه‌ها به صورت غیر مستقیم و از طریق ماده ای به نام فرومون با هم ارتباط بر قرار می‎‎‍‌کنند و اطلاعات مربوط به مسیر‎‎‍‌ها را در اختیار یکدیگر قرار می‎‎‍‌دهند. مورچه‌ها با ترشح مقدار معینی فرومون، مسیر خود را مشخص و علامت‎‎‍‌گذاری می‎‎‍‌کنند که البته این ماده به زودی تبخیر می‎‎‍‌شود، پولی در کوتاه مدت به عنوان رد مورچه بر سطح زمین باقی می‎‎‍‌ماند و مورچه‎‎‍‌های دیگر را به سمت خود جذب می­کند. سایر مورچه‌ها با بررسی و مشاهده فرومون موجود در مسیر، راه یافتن غذا را پیدا می‎‎‍‌کنند. به این ترتیب یک مورچه می‎‎‍‌تواند با استفاده از یک تابع احتمالی مسیر خود را انتخاب کند. هر چه تعداد مورچه‌های عبور کرده از یک مسیر بیشتر باشد یا فرومون بیشتری داشته باشد، ان‎‎‍‌گاه احتمال انکه ان مسیر توسط مورچه بعدی انتخاب شود، بیشتر است. در ابتدا مورچه‌ها پس از خارج شدن از لانه خود با احتمال مساوی به جهات مختلف، برای یافتن غذا حرکت می‎‎‍‌کنند. مورچه‌ها در مسیر‎‎‍‌های ناهموار، با سرعت مساوی حرکت می‎‎‍‌کنند و در مسیر خود فرومون ترشح می‎‎‍‌کنند. بعد از این که یک مورچه در مسیر خود غذایی پیدا کرد، به سرعت از همان مسیر به سمت لانه مراجعت می‎‎‍‌کند و میزان ترشح فرومون را در مسیر افزایش می‎‎‍‌دهد. به این ترتیب سایر مورچه‎‎‍‌ها که مسیرهای دیگر را تجربه کرده‎‎‍‌اند، به تدریج به یک مسیر هدایت خواهند شد.

پیدا کردن کوتاه­ترین مسیر، مراحلی دارد که روی شکل توضیح می­دهیم.

·        همان طور که در مرحله 1 مشاهده می­کنید، مورچه­ها ابتدا روی یک مسیر مستقیم در حال حرکت هستند (در ابتدا هیچ فرومون وجود ندارد).

·        در مرحله 2، در مسیر مورچه­ها مانعی قرار می­دهیم.

·         در مرحله 3، اولین مورچه از نقطه Aمی­اید و به Cمی­رسد و در مسیر حرکت هیچ فرومونی نمی­بیند. بنابراین دو راه برای انتخاب کردن دارد (یا به سمت بالا حرکت می­کند یا به سمت پایین).

اولین مورچه از مسیرCEDمی­رود. دومین مورچه ازمسیرCFD  می­رود، ولی اولین مورچه زودتر از دومی به مقصد می­رسد.

·         همانطور که در مرحله 4 مشاهده می­شود، تجمع مورچه­ها درمسیر CEDبیشتر است. بنابراین مسیر CEDبه عنوان مسیر کوتاه­تر و بهینه شناخته می­شود.

  نکته بسیار با اهمیت این است که هر چند احتمال مسیر پرفرومون توسط مورچه­ها بیشتراست، ولی این کماکان احتمال است و قطعیت نیست. اگر فرض کنیم که به جای این احتمال، قطعیت وجود می­داشت، ان­گاه اساسا این روش ممکن نبود به جواب برسد.

نکته دیگر مساله تبخیر شدن فرومون برجای گذاشته شده است. تبخیر شدن فرومون و احتمال، به مورچه­ها امکان پیدا کردن مسیر کوتاه­تر جدید را می­دهد.

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

1)    حافظه: برای مورچه­های مصنوعی می­توان یک حافظهدرنظرگرفت که مسیرهای حرکت را در خود نگه دارد.

2)    موانع ساختگی: تغییردادن جزییات مساله برای بررسی الگوریتم در رسیدن به جواب­های متنوع.

3)    حیات در محیط گسسته: مورچه­های واقعی نمی­توانند جدا از کلونی به حیات خود ادامه دهند.

چنانچهبتوانساختارمسالهرابهصورتیکگرافنمایشداد،انگاهمی­تواناز الگوریتم­های ACOبراییافتنکوتاه­ترینمسیردرگرافکههماناپاسخمسالهاست،استفادهکرد. هرمورچهبه صورتتکاملیاقدامبهتغییریاساختبخشیازپاسخ مسالهمی­نماید.


[1]Swarm Intelligence

[2]Pheromone

[3] quadratic assignment problem

Compatability by:
آخرین به روز رسانی سایت: سه شنبه, 22 اسفند 1391 - 00:26