الگوریتم اجتماع مورچه (Ant Colony Algorithm)
6 – الگوریتم اجتماع مورچه (Ant Colony Algorithm)
6-1- معرفی
یکی از مسائلی که بهوسیلهی زیستشناسان مورد مطالعه قرار گرفته است درك این موضوع است که چگونه موجودات تقریبا کور مانند مورچهها کوتاهترین مسیر را از لانهی خود تا منبع غذا و بر عکس پیدا میکنند.آنها پی بردند که یک رسانه براي ابلاغ اطلاعات بین تکتک مورچهها مورد استفاده قرار میگیرد و براي تصمیمگیري درمورد اینکه کدام مسیر را انتخاب کنند بهکار میرود که آن رسانه عبارت است از بو(اثر) مادهاي بهنام فرومون[1].
الگوریتمهای لانهی مورچه از جمله روشهای فرامکاشفهای هستند که برای حل مسایل بهینهسازی سخت پیشنهاد شدهاند. این الگوریتمها در آغاز از رفتارهای اجتماعی پشت سرهم قرار گرفتن و تعقیب کردن الهام گرفته شد، که در جامعهی مورچگان مشاهده گردید. یک اجتماع از عاملهای[2] ساده (مورچهها) به طور غیر مستقیم از طریق تغییرات پویای (دینامیکی) محیط ارتباط برقرار میکنند (رد پاهایی از فرومون) و بنابراین بر اساس تجربهی اجتماعی آنها، یک راهحل برای یک مسئله ارائه میدهند.
نخستین الگوریتم از این نوع (سامانهی مورچه) برای مسئلهی فروشندهی دورهگرد طراحی شد، اما نتایجش چندان امیدبخش نبود.
6-2- ویژگیهای الگوریتم
این الگوریتم داراي ویژگیهاي زیر است:
· چند منظوره است، به عبارت دیگر میتواند براي انواع مشابه یک مسئله بهکار رود.
· قوي است، یعنی با کمترین تغییرات براي دیگر مسائل بهینهسازي ترکیبی به کار برده میشود.
· روشی مبتنی بر جمعیت است.
6-3- رفتار طبیعی مورچه
یک مورچه در حال حرکت مقداري فرومون دراندازههاي گوناگون از خود بر روي زمین باقی میگذارد و بدین ترتیب مسیر را بهوسیلهی بوي این ماده مشخص میسازد. هنگامی که یک مورچه بهطور تصادفی و تنها حرکت میکند با روبهرو شدن با مسیري که توسط مورچه یا مورچههاي قبلی انتخاب شده و داراي بوي فرومون است به احتمال زیاد آن را انتخاب میکند و با فرومونی که خود بر جاي میگذارد بوي آن را در مسیر مذکور تقویت مینماید.
وقتی رفتار جمعی پدید میآید، گونهای از رفتار خود تقویتی است، یعنی هرچه مورچه ها بو(اثر) مادهی مذکور را دنبال کنند آن بو براي مورچههاي پیرو آنها جذابتر خواهد بود. فرایند گفته شده به وسیلهی یک حلقه توصیف میشود، یعنی احتمال اینکه یک مورچه یک مسیر را انتخاب کند متناسب باتعداد مورچههایی که قبلا آن مسیر را انتخاب کردهاند افزایش مییابد.
ایده این است که اگر در یک نقطه معین یک مورچه مجبور است از بین مسیرهاي مختلف یکی را انتخاب کند، مسیرهایی را که توسط مورچههاي قبلی بیشتر انتخاب شدهاند، به عبارت دیگر سطح بوی آنها بالاتر است، با احتمال بیشتري انتخاب خواهد کرد. بهعلاوه سطح فرمون بالاتر معادل مسیرهاي کوتاهتر خواهد بود.
بدین ترتیب کوتاهترین مسیر توسط مورچهها انتخاب میشود. الگوریتمهایی که ارائه خواهد شد از اجتماع مورچهی واقعی سرچشمه گرفتهاند. سامانهی مورچهی ارائه شده با استفاده از اجتماع مورچهی مصنوعی چند تفاوت عمده با نوع طبیعی آن خواهد داشت:
1. مورچههاي مصنوعی مقداري حافظه خواهند داشت،
2. آنها کاملا کور نیستند،
3. آنها در محیطی زندگی میکنند که زمان گسسته است.
6-4- سامانهی مورچه[3]
در اين بخش سامانهی مورچه معرفي میشود و از مسئلهی فروشندهی دورهگرد بهعنوان معيار استفاده ميگردد. در مسئـلهی فروشندهی دورهگرد، يك فروشنده سفر خود را از يك شهر آغاز میکند و پس از يك سفر كامل دوباره به شهر خودش باز ميگردد و از هر شـهر فـقط يكبار عبور ميكند و در ضمن بايد از همهی شهرها عبور كند. هدف يافتن كوتاهترين مسير براي اين سفر است.
هر مورچه يك نمايندهی ساده باويژگيهاي زير است:
1. يك شهر را براي رفتن انتخاب ميكند كه تابعي از فاصلهی شهر و مقداربوی (اثر) موجود در آن مسير است.
2. براي واداركردن مورچهها جهت انجام سفرهاي منطقي، سفر به شهرهايي كه يكبار از آنها عبوركرده است ممنوع میشود.
3. هنگامي كه يك مورچه يك سفركامل انجام ميدهد مقداري فرمون برروي هرمسير و بر جای ميگذارد.
در ضمن در طبیعت هر چه از مدت زمان گذاشته شدن فرومون بگذرد بو و اثر آن کمتر میگردد، دلیل آن هم تبخیر این ماده است، پس در الگوریتم زمان نیز موجب کاهش اولویت برخی مسیرها و افزایش اولویت مسیرهای دیگر نسبت به آنها میگردد.
برای اینکه شرط تکراری نبودن شهرها و نیز گذشتن از همهی آنها برقرار گردد، به هر مورچه یک لیست ممنوع نسبت داده میشود که دارای شهرهای عبور کرده میباشد.
6-5- بیان الگوریتم
با توجه به تعاريف بخش پیش الگوريتمها معرفي ميشوند. در زمـان صفر يعني مرحله شروع، مورچهها درشـهرهاي مختـلف مستقر ميشوند و ارزش اوليهی شدت بو(اثر) بر روي مسيرها تعیین میگردد. شهر آغازين به عنوان اولين عنصر وارد ليست ميشود. سپس هرمورچه از شهر با تابع احتمال به سمت شهر حرکت میکند، كه خود تابعي از دو معيار مطلوبيت است: يكي احتمال اينكه در گذشته چه تعداد مورچه از مسير رفتهاند، ديگري قابليت رويت[4] كه ميگويد شهرهاي نزديك براي مورچهها مطلوبتراند.
بعد از تكرار همهی مورچهها يك سفر كامل انجام دادهاند وليست ممنوع آنها پرشده است. همچنين كوتـاهترين مسير يافتهشـده بهوسيلهی مورچهها ذخيره شده و ليستهاي ممنوع خالي ميشوند. اين فرايند تا زماني كه تعداد سيكلها به حداكثر خود برسد يا همه مورچهها يك سفر يكسان انجام دهند ادامه مييابد. اين حالت رارفتار ركودي مينامند زيرا الگوريتم جستجوي راهحلهاي ديگر را متوقف ميكند.
قابل ذکر است که سه نوع الگوریتم مورچه وجود دارد: 1. چگالی مورچه[5]، 2. تعداد مورچه[6]، 3. دور مورچه[7].
در دو الگوريتم اول مقدار فرمون در پايان هر تكرار تعديل ميشود. اما در الگوريتم سوم پس از پايان يك دور اين عمل انجام ميگيرد. پس از انجام شدن چند دور فقط به مورچهاي كه بهترين مسير را ميپيمايد اجازه ترشحكردن فرمون داده ميشود، اين عمـل به منظور جـهتدار كردن جستجو انجام ميگيرد يعني با اين كار مورچهها در همسايگي بهترين مسـيري كه تاكـنون پیدا شـده است بـه جستـجو مـيپردازند. دو الگوريتم اول دقيقا مثل هم هستند و فقط از لحاظ تعديلكردن (بهروزرسانی) فرومون با هم متفاوتاند .
6-6- حالت کلی الگوریتم
الگوریتم اجتماع مورچگان دارای سه بخش اصلی زیر است:
1. بخش مقداردهی اولیه، که عبارت است از تشکیل گرافی که بر اساس مسئلهی بهینهسازی ترکیبی در دست بررسی و پارامترها، با توجه به ارزشهای اولیهاشان، ساخته میشود،
2. بخش ایجاد راهحل، که در آن هر مورچه راهحل خودش را برای مسئله تولید میکند، و تا زمانی که همهی مورچهها راهحل خود را کامل کنند ادامه مییابد،
3. بخش بهروزرسانی فرومون، که طی آن دنبالهی فرومون متناظر با هر اتصال در گراف ساختمان بر اساس قانون به روز رسانی، به روز خواهد شد.
6-7- مقایسه با دیگر روشهای فرامکاشفهای
الگوریتم کلونی مورچه دارای ویژگیهایی در مقایسه با دیگر روشهای فرامکاشفهای است:
1. محاسبات گسسته در طبیعت،
2. فرایند تجزیهی واکنش توسط یکی از محصولات خودش[8]،
3. استفاده از جستجوی حریصانه و اطلاعات اکتشافی سازنده (آگاهانه).
[1] Pheromones
[2] agent
[3] Ant System
[4] Visibility
[5] Ant Density
[6] Ant Quantity
[7] Ant Cycle
[8] Autocatalytic
