بایگانی برچسب برای: v]i

3-5-انواع روش‌هاي فرا ابتكاري برگرفته از طبيعت

1-3-5-الگوريتم ژنتيك

الگوريتم ژنتيك (Genetic Algorithm) روشي عمومي از روش‌هاي فرا ابتكاري براي بهينه‌سازي گسسته مي‌باشد كه مسائل جدول زمانبندي را حل مي‌نمايد. روش شبيه‌سازي كه در ادامه مورد بحث قرار می‌گيرد، راهبرد تكاملي نام دارد. اين روش در سال 1975 به وسيله هولند (Holland) و در سال 1989 توسط  گولدبرگ (Goldberg) ابداع شده است.

اين روش نوعي روش جستجوي همسايه است كه عملكردي مشابه ژن دارد. در طبيعت، فرايند تكامل هنگامي ايجاد مي‌شود كه چهار شرط زير برقرار باشد:

الف) يك موجود توانايي تكثير داشته باشد (قابليت توليد مثل).

ب) جمعيتي از اين موجودات قابل تكثير وجود داشته باشد.

پ) چنين وضعيتي داراي تنوع باشد.

ت) اين موجودات به وسيله قابليت‌هايي در زندگي از هم جدا شوند.

در طبيعت، گونه‌هاي متفاوتي از يك موجود وجود دارند كه اين تفاوت‌ها در كروموزوم‌هاي اين موجودات ظاهر مي‌شود و باعث تنوع در ساختار و رفتار اين موجودات مي‌شود.

اين تنوع ساختار و رفتار به نوبه خود بر زاد و ولد تأثير مي‌گذارد. موجوداتي كه قابليت‌ها و توانايي بيشتري براي انجام فعاليت‌ها در محيط دارند (موجودات متكامل‌تر)، داراي نرخ زاد و ولد بالاتري خواهند بود و طبعاً موجوداتي كه سازگاري كمتري با محيط دارند، از نرخ زاد و ولد پايين‌تري برخوردار خواهند بود. بعد از چند دوره زماني و گذشت چند نسل، جمعيت تمايل دارد كه موجوداتي را بيشتر در خود داشته باشد كه كروموزوم‌هايشان با محيط اطراف سازگاري بيشتري دارد.

در طي زمان، ساختار افراد جامعه به علت انتخاب طبيعي تغيير مي‌كند و اين نشانه تكامل جمعيت است.

6- آنيلينگ شبيهسازي شده

اين روش توسط متروپوليس (Metropolis) و همكاران در سال 1953 پيشنهاد شده و جهت بهينه‌سازي به وسيله وچی (Vecchi)، گلات (Gelatt) و کرک‌پاتريک (kirkpatrick ) در سال 1983 مورد بازبيني قرار گرفته است. اين روش در مسائل تاكسي تلفني كاربرد دارد.

الگوريتم آنيلينگ شبيه‌سازي شده (Simulated Annealing) در شکل عمومي، بر اساس شباهت ميان سرد شدن جامدات مذاب و حل مسائل بهينه‌سازي تركيبي به وجود آمده است. در فيزيك مواد فشرده، گرم و سرد كردن فرايندي است فيزيكي كه طي آن يك ماده جامد در ظرفي حرارت داده مي‌شود تا مايع شود؛ سپس حرارت آن بتدريج كاهش مي‌يابد. بدين ترتيب تمام ذرات فرصت مي‌يابند تا خود را در پايين‌ترين سطح انرژي منظم كنند. چنين وضعي در شرايطي ايجاد مي‌شود كه گرمادهي كافي بوده و سرد كردن نيز به آهستگي صورت گيرد. جواب حاصل از الگوريتم گرم و سرد كردن شبيه‌سازي شده، به جواب اوليه وابسته نيست و مي‌توان توسط آن جوابي نزديك به جواب بهينه به دست آورد. حد بالايي زمان اجراي الگوريتم نيز قابل تعيين است. بنابراين الگوريتم گرم و سرد كردن شبيه‌سازي شده، الگوريتمي است تكراري كه اشكالات روش‌هاي عمومي مبتني بر تكرار را ندارد.

در روش آنيلينگ شبيه‌سازي شده، به صورت پي در پي از جواب جاري به يكي از همسايه‌هاي آن انتقال صورت مي‌گيرد. اين سازوکار توسط زنجيره ماركوف به صورت رياضي قابل توصيف است. در اين روش، يك مجموعه آزمون انجام مي‌گيرد؛ اين آزمون‌ها به نحوي است كه نتيجه هر يك به نتيجه آزمون قبل وابسته است. در روش آنيلينگ شبيه‌سازي شده، منظور از يك آزمون، انتقال به نقطه جديد است و روشن است كه نتيجه انتقال به نقطه جديد تنها وابسته به مشخصات جواب جاري است.

روش جستجوي همسايه و روش آنيلينگ شبيه‌سازي شده، هر دو روش‌هاي تكراري هستند. در الگوريتم آنيلينگ شبيه‌سازي شده، هر بار كه شاخص كنترل‌كننده به مقدار نهايي خود مي‌رسد، در حقيقت يك عمليات تكراري انجام شده است. در الگوريتم جستجوي همسايه، هنگامي كه تعداد تكرارها به سمت بي‌نهايت ميل مي‌كند، روش به جواب بهينه نزديك مي‌شود. اما عملكرد الگوريتم آنيلينگ شبيه‌سازي شده سريع‌تر است.

7-شبکه‌های عصبی

شبکه‌های عصبی (Neural Networks) مصنوعی سيستم‌هاي هوشمندی هستند که از شبکه‌هاي عصبي طبيعي الهام گرفته شده‌اند. شبکه‌هاي عصبي مصنوعي در واقع تلاشي براي حرکت از سمت مدل محاسباتي فون نيومن به سمت مدلي است که با توجه به عملکرد و ويژگي‌هاي مغز انسان طراحي شده است. مدل فون نيومن گرچه هم اکنون بسيار استفاده می‌شود، اما از کمبودهايي رنج مي‌برد که تلاش شده است اين کمبودها در شبکه‌هاي عصبي مصنوعي برطرف شود.

در سال 1943 مدلی راجع به عملکرد نورون‌ها (Neuron) نوشته شد که با اندکی تغيير، امروزه بلوک اصلی سازنده اکثر شبکه‌های عصبی مصنوعی می‌باشد. عملکرد اساسی اين مدل مبتنی بر جمع کردن ورودی‌ها و به دنبال آن به وجود آمدن يک خروجی است. ورودی‌های نورون‌ها از طريق دنريت‌ها که به خروجی نورون‌های ديگر از طريق سيناپس متصل است، وارد می‌شوند. بدنه سلولی کليه اين ورودی‌ها را دريافت می‌کند و چنانچه جمع اين مقادير از مقداری که به آن آستانه گفته می‌شود بيشتر باشد، در اصطلاح برانگيخته شده يا آتش می‌کند و در اين صورت، خروجی نورون روشن يا خاموش خواهد شد.

مدل پایه ای نرون

مدل پايه‌اي نورون به صورت شکل 1-3 تعريف می‌شود.

مدل پایه ای نرون

مدل پایه ای نرون

اين مدل و برخی از کارهای مربوط به آن را بايد به عنوان شروع مطالعات تحليلی در نظر گرفت. گر چه اين مدل ساده فاقد ويژگی‌های پيچيده بدنه سلولی نورون‌های بيولوژيکی است، اما می‌توان به آن به صورت مدلی ساده از آنچه که واقعاً موجود است نگريست.

جستجوي ممنوع

روشی عمومي است كه به وسيله گلوور (Glover) در سال 1989 پيشنهاد شده و در حل مسائل برنامه‌ريزي كاري ـ خريد کاربرد دارد.

روش جستجوي ممنوع (Tabu Search)، همانند روش آنيلينگ شبيه‌سازي شده بر اساس جستجوي همسايه بنا شده است. در اين روش عملكرد حافظه انسان شبيه‌سازي شده است. حافظه انسان با به كارگيري ساختماني مؤثر و در عين حال ساده از اطلاعات، آنچه را در قبل رؤيت شده، ذخيره مي‌كند. اين مركز همچنين فهرستی از حركات منع شده را تنظيم مي‌كند و اين فهرست همواره بر اساس آخرين جستجوها منظم مي‌شود. اين روش از انجام هر گونه عمليات مجدد و تكراري جلوگيري مي‌كند.

شكل نوين جستجوي ممنوع توسط گلوور مطرح شده است. روش جستجوي مبتني بر منع، با ايجاد تغييري كوچك در روش جستجوي همسايه به وجود مي‌آيد. هدف اين روش آن است كه بخش‌هايي از مجموعه جواب كه پيش از اين بررسي نشده است، مد نظر قرار گيرد. بدين منظور حركت به جواب‌هايي كه اخيراً جستجو شده، ممنوع خواهد بود.

ساختار كلي روش جستجوي ممنوع بدين صورت است كه ابتدا يك جواب اوليه امكان‌پذير انتخاب مي‌شود؛ سپس براي جواب مربوط، بر اساس يک معيار خاص مجموعه‌اي از جواب‌هاي همسايه امكان‌پذير در نظر گرفته مي‌شود.

در گام بعد، پس از ارزيابي جواب‌هاي همسايه تعيين شده، بهترين آنها انتخاب مي‌شود و جابه‌جايي از جواب جاري به جواب همسايه انتخابي صورت مي‌گيرد. اين فرايند به همين ترتيب تكرار مي‌شود تا زماني كه شرط خاتمه تحقق يابد.

در روش جستجوي ممنوع، فهرستي وجود دارد كه جابه‌جايي‌هاي منع شده را نگهداري مي‌كند و به فهرست تابو معروف است و كاربرد اصلي آن، پرهيز از همگرا شدن به جواب‌هاي بهينه محلي است. به عبارت ديگر، به كمك فهرست تابو جابه‌جايي به جواب‌هايي كه اخيراً جستجو شده‌اند، ممنوع خواهد شد. فقط بخش‌هايي از مجموعه جواب كه پيش از اين مورد بررسي قرار نگرفته، مد نظر خواهند بود. در واقع جابه‌جايي از جواب جاري به جواب همسايه امكان‌پذير زماني انجام مي‌شود كه در فهرست تابو قرار نداشته باشد. در غير اين صورت، جواب همسايه ديگري كه در ارزيابي جواب‌هاي همسايه در رده بعدي قرار گرفته است، انتخاب شده و جابه‌جايي به آن صورت مي‌گيرد.

در روش جستجوي ممنوع بعد از هر جابه‌جايي، فهرست تابو بهنگام مي‌شود، به نحوي كه جابه‌جايي جديد به آن فهرست اضافه شده و جابه‌جايي كه تا n  تكرار مشخص در فهرست بوده است، از آن حذف مي‌شود. نحوه انتخاب مي‌تواند با توجه به شرايط و نوع مسأله متفاوت باشد.

سيستم مورچه (Ant System)

اين روش در سال 1991 توسط مانيه‌زو (Maniezzo) دوريگو (Dorigo) و کولورنی (Colorni) پيشنهاد شده است كه در حل مسأله فروشنده دوره‌گرد و مسائل تخصيص چندوجهي کاربرد دارد.

الگوريتم بهينه‌سازي كلوني مورچه‌ها از عامل‌هاي ساده‌اي كه مورچه ناميده مي‌شوند، استفاده مي‌كند تا به صورت تكراري جواب‌هايي توليد كند. مورچه‌ها می‌توانند كوتاه‌ترين مسير از يك منبع غذايي به لانه را با بهره‌گيري از اطلاعات فرموني پيدا کنند. مورچه‌ها در هنگام راه رفتن، روي زمين فرمون مي‌ريزند و با بو كشيدن فرمون ريخته شده بر روي زمين راه را دنبال مي‌كنند؛ چنانچه در طي مسير به سوي لانه به يك دوراهي برسند، از آن جايي كه هيچ اطلاعي درباره راه بهتر ندارند، راه را به تصادف برمي‌گزينند. انتظار مي‌رود به طور متوسط نيمي از مورچه‌ها مسير اول و نيمي ديگر مسير دوم را انتخاب كنند.

فرض مي‌شود كه تمام مورچه‌ها با سرعت يكسان مسير را طي كنند. از آنجا كه يك مسير كوتاه‌تر از مسير ديگر است، مورچه‌هاي بيشتري از آن مي‌گذرند و فرمون بيشتري بر روي آن انباشته مي‌شود. بعد از مدت كوتاهي مقدار فرمون روي دو مسير به اندازه‌اي مي رسد كه روي تصميم مورچه‌هاي جديد براي انتخاب مسير بهتر تأثير مي‌گذارد. از اين به بعد، مورچه‌هاي جديد با احتمال بيشتري ترجيح مي‌دهند از مسير كوتاه‌تر استفاده كنند، زيرا در نقطه تصميم‌گيري مقدار فرمون بيشتري در مسير كوتاه‌تر مشاهده مي‌كنند. بعد از مدت كوتاهي تمام مورچه‌ها اين مسير را انتخاب خواهند كرد.

منبع


مقدمه ای بر بهینه سازی و الگوریتم های موجود

هدف از بهينه‌سازي يافتن بهترين جواب قابل قبول، با توجه به محدوديت‌ها و نيازهاي مسأله است. براي يك مسأله، ممكن است جواب‌هاي مختلفي موجود باشد كه براي مقايسه آنها و انتخاب جواب بهينه، تابعي به نام تابع هدف تعريف مي‌شود. انتخاب اين تابع به طبيعت مسأله وابسته است. به عنوان مثال، زمان سفر يا هزينه از جمله اهداف رايج بهينه‌سازي شبكه‌هاي حمل و نقل مي‌باشد. به هر حال، انتخاب تابع هدف مناسب يكي از مهمترين گام‌هاي بهينه‌سازي است. گاهي در بهينه‌سازي چند هدف  به طور همزمان مد نظر قرار مي‌گيرد؛ اين گونه مسائل بهينه‌سازي را كه دربرگيرنده چند تابع هدف هستند، مسائل چند هدفي مي‌نامند. ساده‌ترين راه در برخورد با اين گونه مسائل، تشكيل يك تابع هدف جديد به صورت تركيب خطي توابع هدف اصلي است كه در اين تركيب ميزان اثرگذاري هر تابع با وزن اختصاص يافته به آن مشخص مي‌شود. هر مسأله بهينه‌سازي داراي تعدادي متغير مستقل است كه آنها را متغيرهاي طراحي می‌نامند كه با بردار n  بعدي x  نشان داده مي‌شوند.

هدف از بهينه‌سازي تعيين متغيرهاي طراحي است، به گونه‌اي كه تابع هدف كمينه يا بيشينه شود.

مسائل مختلف بهينه‌سازي  به دو دسته زير تقسيم مي‌شود:

الف) مسائل بهينه‌سازي بي‌محدوديت: در اين مسائل هدف، بيشينه يا كمينه كردن تابع هدف بدون هر گونه محدوديتي بر روي متغيرهاي طراحي مي‌باشد.

ب) مسائل بهينه‌سازي با محدوديت: بهينه‌سازي در اغلب مسائل كاربردي، با توجه به محدوديت‌هايي صورت مي‌گيرد؛ محدوديت‌هايي كه در زمينه رفتار و عملكرد يك سيستم مي‌باشد و محدوديت‌هاي رفتاري و محدوديت‌هايي كه در فيزيك و هندسه مسأله وجود دارد، محدوديت‌هاي هندسي يا جانبي ناميده مي‌شوند.

معادلات معرف محدوديت‌ها ممكن است  به صورت مساوي يا نامساوي باشند كه در هر مورد، روش بهينه‌سازي متفاوت مي‌باشد. به هر حال محدوديت‌ها، ناحيه قابل قبول در طراحي را معين مي‌كنند.

فرايند بهينه ­سازي

فرموله كردن مسئله: در اين مرحله، يك مسئله ­ي تصميم ­گيري، همراه با يك ساختار كلي از آن تعريف مي‌شود. اين ساختار كلي ممكن است خيلي دقيق نباشد اما وضعيت كلي مسئله را، كه شامل فاكتورهاي ورودي و خروجي و اهداف مسئله است، بيان مي­ كند. شفاف­ سازي و ساختاردهي به مسئله، ممكن است براي بسياري از مسايل بهينه­ سازي، كاري پيچيده باشد.

مدل­ سازي مسئله:

در اين مرحله يك مدل رياضي كلي براي مسئله، ساخته مي­ شود. مدل­سازي ممكن است از مدل­ هاي مشابه در پيشينه ­ي موضوع كمك بگيرد. اين گام موجب تجزيه مسئله به يك يا چند مدل بهينه‌سازي مي­ گردد.

بهينه­ سازي مسئله:

پس از مدل سازي مسئله، روال حل، يك راه ­حل خوب براي مسئله توليد مي­ كند. اين راه‌حل ممكن است بهينه يا تقريباً بهينه باشد. نكته ­اي كه بايد به آن توجه داشت اين است كه راه ­حل به دست آمده، راه­ حلي براي مدل طراحي شده است، نه براي مسئله ­ي واقعي. در هنگام فرموله كردن و مدلسازي ممكن است تغييراتي در مسئله واقعي به وجود آمده و مسئله­ ي جديد، نسبت به مسئله­ ي واقعي تفاوت زيادي داشته باشد.

استقرار مسئله:

راه ­حل به دست آمده توسط تصميم گيرنده بررسي مي­ شود و در صورتي كه قابل قبول باشد، مورد استفاده قرار مي­ گيرد و در صورتي كه راه­حل قابل قبول نباشد، مدل يا الگوريتم بهينه­ سازي بايد توسعه داده شده و فرايند بهينه­ سازي تكرار گردد.

الگوریتم­ های بهینه­ سازی

هدف الگوریتم­ های اکتشافی، ارائه راه حل در چارچوب یک زمان قابل قبول است که برای حل مسئله مناسب باشد، ممکن است الگوریتم اکتشافی، بهترین راه حل واقعی برای حل مسئله نبوده ولی می­ تواند راه حل نزدیک به بهترین باشد. الگوریتم ­های اکتشافی با الگوریتم­ های بهینه­ سازی برای اصلاح کارایی الگوریتم می‌توانند ترکیب شوند. الگوریتم فرا اکتشافی ترکیبی است از الگوریتم ­های اکتشافی که برای پیدا کردن، تولید یا انتخاب هر اکتشاف در هر مرحله طراحی می­شود و راه حل خوبی برای مسائلی که مشکل بهینه‌سازی دارند ارائه می‌دهد. الگوریتم­ های فرا اکتشافی برخی از فرضیات مسائل بهینه­ سازی که باید حل شود را در نظر می ­گیرد.

 روش‌هاي فرا ابتكاري برگرفته از طبيعت

الگوريتم ­هاي فراابتكاري الگوريتم ­هايي هستند كه با الهام از طبيعت، فيزيك و انسان طراحي شده ­اند و در حل بسياري از مسايل بهينه­ سازي استفاده می­ شوند. معمولاً از الگوريتم­ هاي فراابتكاري در تركيب با ساير الگوريتم­ ها، جهت رسيدن به جواب بهينه يا خروج از وضعيت جواب بهينه محلي استفاده مي­گردد. در سال‌هاي اخير يكي از مهمترين و اميدبخش‌ترين تحقيقات، «روش‌هاي ابتكاري برگرفته از طبيعت» بوده است؛ اين روش‌ها شباهت‌هايي با سيستم‌هاي اجتماعي و يا طبيعي دارند. كاربرد ‌آنها برگرفته از روش‌هاي ابتكاري پيوسته می‌باشد كه در حل مسائل مشكل تركيبي (NP-Hard) نتايج بسيار خوبی داشته است.

در ابتدا با تعريفي از طبيعت و طبيعي بودن روش‌ها شروع مي‌كنيم؛ روش‌ها برگرفته از فيزيك، زيست‌شناسي و جامعه‌شناسي هستند و به صورت زير تشكيل شده‌اند:

–         استفاده از تعداد مشخصي از سعي‌ها و كوشش‌هاي تكراري

–          استفاده از يك يا چند عامل (نرون، خرده‌ريز، كروموزوم، مورچه و غيره)

–          عمليات (در حالت چند عاملي) با يك سازوکار همكاري ـ رقابت

–          ايجاد روش‌هاي خود تغييري و خود تبديلي

طبيعت داراي دو تدبير بزرگ مي‌باشد:

1-    انتخاب پاداش براي خصوصيات فردي قوي و جزا براي فرد ضعيف‌تر؛

2-     جهش كه معرفي اعضای تصادفي و امکان تولد فرد جديد را ميسر می‌سازد.

به طور كلي دو وضعيت وجود دارد كه در روش‌هاي ابتكاري برگرفته از طبيعت ديده مي‌شود، يكي انتخاب و ديگري جهش. انتخاب ايده‌اي مبنا براي بهينه‌سازي و جهش ايده‌اي مبنا براي جستجوي پيوسته مي‌باشد.

از خصوصيات روش‌هاي ابتكاري  برگرفته از طبيعت، مي‌توان به موارد زير اشاره كرد:

1-    پديده‌اي حقيقي در طبيعت را مدل‌سازي مي‌كنند.

2-     بدون قطع مي‌باشند.

3-     اغلب بدون شرط تركيبي همانند (عامل‌هاي متعدد) را معرفي مي‌نمايند.

4-     تطبيق‌پذير هستند.

خصوصيات بالا باعث رفتاري معقول در جهت تأمين هوشمندي مي‌شود. تعريف هوشمندي نيز عبارت است از قدرت حل مسائل مشكل؛ بنابراين هوشمندي به حلمناسب مسائل بهينه‌سازي تركيبي منجر می‌شود.

برخی الگوریتم های بهینه سازی مهم عبارت انداز:

 الگوریتم بهینه سازی ازدحام ذرات

در سال 1995 ابرهارت و کنیدی براي اولین بار PSOبه عنوان یک روش جستجوي غیر قطعی براي بهینه سازي تابعی مطرح گشت این الگوریتم از حرکت دسته جمعیپرندگانی که به دنبال غذا می­باشند، الهام گرفته شده است. گروهي از پرندگان در فضايي به صورت تصادفي دنبال غذا مي­گردند. تنها يك تكه غذا در فضاي مورد بحث وجود دارد. هيچ يك از پرندگان محل غذا را نمي­دانند. يكي از بهترين استراتژي­ها مي­تواند دنبال كردن پرنده­اي باشد كه كمترين فاصله را تا غذا داشته باشد.  ايناستراتژي در واقع جانمايه الگوريتم است. هر راه­حل كه به آن يك ذره گفته مي­شود،PSO  در الگوريتم معادل يك پرنده در الگوريتم حركت جمعي پرندگان مي­باشد.هر ذره يك مقدار شايستگي دارد كه توسط يك تابع شايستگي محاسبه مي­شود. هر چه ذره در فضا­ي جستجو به هدف – غذا در مدل حركت پرندگان-  نزدیكتر باشد،شايستگي بيشتري دارد. همچنين هر ذره داراي يك سرعت است كه هدايت حركت ذره را بر عهده دارد. هرذره با دنبال كردن ذرات بهينه در حالت فعلي، به حركت خوددر فضاي مساله ادامه مي­دهد.

الگوریتم کرم شب­ تاب

الگوریتم کرم شب ­تاب به عنوان الگوریتم ذهنی مبتنی بر ازدحام، برای وظایف بهینه­سازی محدود، ارائه شده است. در این الگوریتم از رفتار تابشی کرم­های شب تابالهام گرفته شده است. کرم­های شب تاب در طبیعت به طور دسته جمعی زندگی می­کنند و همواره کرم کم نورتر به سمت کرم پرنور تر حرکت می‌کند. این الگوریتم یکرویه تکراری مبتنی بر جمعیت را با عوامل بی­شمار (تحت عنوان کرم­های شب­تاب) به کار می‌گیرد. به این عوامل امکان داده می­شود تا فضای تابع هزینه را به صورتموثرتری نسبت به جستجوی تصادفی توزیع شده، بررسی کنند. تکنیک بهینه­سازی هوشمند، مبتنی بر این فرضیه است که راه­حل یک مشکل بهینه­سازی را، می­توان بهعنوان عاملی (کرم شب­تاب) در نظر گرفت که به صورت متناسب با کیفیت آن در یک محیط تابیده می­شود. متعاقباً هر کرم شب­تاب، همتایان خود را (صرف نظر ازجنسیتشان) جذب می­کند که فضای جستجو را به صورت موثرتری بررسی می­کند. الگوریتم­های کرم شب­تاب نورهای ریتمیک و کوتاه تولید می­کنند. الگوی نوری هر کدام از کرم­های شب­تاب با یکدیگر متفاوت می­باشند. الگوریتم­های کرم شب­تاب از این نورها به دو منظور استفاده می­کنند. 1- پروسه جذب جفت­ها 2- جذب شکار. به علاوه این نورها می­توانند به عنوان یک مکانیزم محافظتی برای کرم­های شب­تاب باشند.

الگوریتم کلونی مورچگان

بهینه‌سازی گروه مورچه‌ها یا ACO همانطور که می دانیم مسئله یافتن کوتاهترین مسیر، یک مسئله بهینه سازیست که گاه حل آن بسیار دشوار است و گاه نیز بسیار زمانبر. برای مثال مسئله فروشنده دوره گرد را نیز می‌توان مطرح کرد. در این روش(ACo)، مورچه‌های مصنوعی به‌وسیلهٔ حرکت بر روی نمودار مسئله و با باقی گذاشتن نشانه‌هایی بر روی نمودار، همچون مورچه‌های واقعی که در مسیر حرکت خود نشانه‌های باقی می‌گذارند، باعث می‌شوند که مورچه‌های مصنوعی بعدی بتوانند راه‌حل‌های بهتری را برای مسئله فراهم نمایند. همچنین در این روش می‌توان توسط مسائل محاسباتی-عددی بر مبنای علم احتمالات بهترین مسیر را در یک نمودار یافت.

 الگوریتم ژنتیک

الگوریتم‌های ژنتیک، تکنیک جستجویی در علم رایانه برای یافتن راه‌حل تقریبی برای بهینه‌سازی و مسائل جستجو است. الگوریتم ژنتیک نوع خاصی از الگوریتم‌های تکامل است که از تکنیک‌های زیست‌شناسی فرگشتی مانند وراثت و جهش استفاده می‌کند. این الگوریتم برای اولین بار توسط جان هنری هالند معرفی شد. در واقع الگوریتم‌های ژنتیک از اصول انتخاب طبیعی داروین برای یافتن فرمول بهینه جهت پیش‌بینی یا تطبیق الگو استفاده می‌کنند. الگوریتم‌های ژنتیک اغلب گزینه خوبی برای تکنیک‌های پیش‌بینی بر مبنای رگرسیون هستند. در هوش مصنوعی الگوریتم ژنتیک (یا GA) یک تکنیک برنامه‌نویسی است که از تکامل ژنتیکی به عنوان یک الگوی حل مسئله استفاده می‌کند. مسئله‌ای که باید حل شود دارای ورودی‌هایی می‌باشد که طی یک فرایند الگوبرداری شده از تکامل ژنتیکی به راه‌حلها تبدیل می‌شود سپس راه حلها بعنوان کاندیداها توسط تابع ارزیاب (Fitness Function) مورد ارزیابی قرار می‌گیرند و چنانچه شرط خروج مسئله فراهم شده باشد الگوریتم خاتمه می‌یابد. الگوریتم ژنتیک بطور کلی یک الگوریتم مبتنی بر تکرار است که اغلب بخش‌های آن به صورت فرایندهای تصادفی انتخاب می‌شوند.

منبع
بهينه‌سازی و معرفي روش‌های آن قسمت 1
بهينه‌سازی و معرفي روش‌های آن قسمت 2
بهينه‌سازی و معرفي روش‌های آن قسمت 3

الگوریتم کلونی مورچه‌ها

الگوریتم کلونی مورچه ها یا ACO همان‌طور که می‌دانیم مسئله یافتن کوتاهترین مسیر، یک مسئله بهینه سازیست که گاه حل آن بسیار دشوار است و گاه نیز بسیار زمانبر. برای مثال مسئله فروشنده دوره گرد را نیز می‌توان مطرح کرد. در این روش(ACo)، مورچه‌های مصنوعی به‌وسیلهٔ حرکت بر روی نمودار مسئله و با باقی گذاشتن نشانه‌هایی بر روی نمودار، همچون مورچه‌های واقعی که در مسیر حرکت خود نشانه‌های باقی می‌گذارند، باعث می‌شوند که مورچه‌های مصنوعی بعدی بتوانند راه‌حل‌های بهتری را برای مسئله فراهم نمایند. همچنین در این روش می‌توان توسط مسائل محاسباتی-عددی بر مبنای علم احتمالات بهترین مسیر را در یک نمودار یافت.

الگوریتم کلونی مورچه ها

روش که از رفتار مورچه‌ها در یافتن مسیر بین محل لانه و غذا الهام گرفته شده؛ اولین بار در ۱۹۹۲ توسط مارکو دوریگو (Marco Dorigo) در پایان نامهٔ دکترایش مطرح شد.

 مقدمه

الگوریتم کلونی مورچه ها

الگوریتم کلونی مورچه الهام گرفته شده از مطالعات و مشاهدات روی کلونی مورچه هاست. این مطالعات نشان داده که مورچه‌ها حشراتی اجتماعی هستند که در کلونی‌ها زندگی می‌کنند و رفتار آنها بیشتر در جهت بقاء کلونی است تا درجهت بقاء یک جزء از آن. یکی از مهمترین و جالبترین رفتار مورچه‌ها، رفتار آنها برای یافتن غذا است و بویژه چگونگی پیدا کردن کوتاهترین مسیر میان منابع غذایی و آشیانه. این نوع رفتار مورچه‌ها دارای نوعی هوشمندی توده‌ای است که اخیراً مورد توجه دانشمندان قرار گرفته است در دنیای واقعی مورچه‌ها ابتدا به طور تصادفی به این سو و آن سو می‌روند تا غذا بیابند. سپس به لانه بر می‌گردند و ردّی از فرومون (Pheromone) به جا می‌گذارند. چنین ردهایی پس از باران به رنگ سفید در می‌آیند و قابل رویت اند. مورچه‌های دیگر وقتی این مسیر را می‌یابند، گاه پرسه زدن را رها کرده و آن را دنبال می‌کنند. سپس اگر به غذا برسند به خانه بر می‌گردند و رد دیگری از خود در کنار رد قبل می‌گذارند؛ و به عبارتی مسیر قبل را تقویت می‌کنند. فرومون به مرور تبخیر می‌شود که از سه جهت مفید است:

مسیر حرکت مورچه ها برای یافتن غذا

  • باعث می‌شود مسیر جذابیت کمتری برای مورچه‌های بعدی داشته باشد. از آنجا که یک مورچه در زمان دراز راه‌های کوتاه‌تر را بیش تر می‌پیماید و تقویت می‌کند هر راهی بین خانه و غذا که کوتاه‌تر (بهتر) باشد بیشتر تقویت می‌شود و آنکه دورتر است کمتر.
  • اگر فرومون اصلاً تبخیر نمی‌شد، مسیرهایی که چند بار طی می‌شدند، چنان بیش از حد جذّاب می‌شدند که جستجوی تصادفی برای غذا را بسیار محدود می‌کردند.
  • وقتی غذای انتهای یک مسیر جذاب تمام می‌شد رد باقی می‌ماند.
یافتن کوتاه ترین مسیر بین غذا و لانه

لذا وقتی یک مورچه مسیر کوتاهی (خوبی) را از خانه تا غذا بیابد بقیهٔ مورچه‌ها به احتمال زیادی همان مسیر را دنبال می‌کنند و با تقویت مداوم آن مسیر و تبخیر ردهای دیگر، به مرور همهٔ مورچه‌ها هم مسیر می‌شوند. هدف الگوریتم مورچه‌ها تقلید این رفتار توسط مورچه‌هایی مصنوعی ست که روی نمودار در حال حرکت اند. مسئله یافتن کوتاه‌ترین مسیر است و حلالش این مورچه‌های مصنوعی اند.

از کابردهای این الگوریتم، رسیدن به راه حل تقریباً بهینه در مسئله فروشنده دوره‌گرد است. به طوری که انواع الگوریتم کلونی مورچه‌ها برای حل این مسئله تهیه شده. زیرا این روش عددی نسبت به روشهای تحلیلی و genetic در مواردی که نمودار مدام با زمان تغییر کند یک مزیت دارد؛ و آن این که الگوریتمی ست با قابلیت تکرار؛ و لذا با گذر زمان می‌تواند جواب را به طور زنده تغییر دهد؛ که این خاصیت در روتینگ شبکه‌های کامپیوتری و سامانه حمل و نقل شهری مهم است.
در مسئله فروشنده دوره گرد باید از یک شهر شروع کرده، به شهرهای دیگر برود و سپس به شهر مبدأ بازگردد بطوریکه از هر شهر فقط یکبار عبور کند و کوتاهترین مسیر را نیز طی کرده باشد. اگر تعداد این شهرها n باشد در حالت کلی این مسئله از مرتبه (n-1)! است که برای فقط ۲۱ شهر زمان واقعاً زیادی می‌برد:

روز۱۰۱۳*۷/۱ = S۱۰۱۶*۴۳۳/۲ = ms۱۰*۱۰۱۸*۴۳۳/۲ =!۲۰

با انجام یک الگوریتم برنامه سازی پویا برای این مسئله، زمان از مرتبه نمایی بدست می‌آید که آن هم مناسب نیست. البته الگوریتم‌های دیگری نیز ارائه شده ولی هیچ‌کدام کارایی مناسبی ندارند. ACO الگوریتم کامل و مناسبی برای حل مسئله TSP است.

الگوریتم کلونی مورچه ها بهترین روش برای حل مسئله ی فروشنده ی دوره گرد

مسئله فروشنده دوره گرد

مزیتهای الگوریتم کلونی مورچه ها

<تبخیر شدن فرومون> و <احتمال-تصادف>به مورچه‌ها امکان پیدا کردن کوتاهترین مسیر را می‌دهد. این دو ویژگی باعث ایجاد انعطاف در حل هرگونه مسئله بهینه‌سازی می‌شوند. مثلاً در گراف شهرهای مسئله فروشنده دوره گرد، اگر یکی از یالها (یا گره‌ها) حذف شود الگوریتم این توانایی را دارد تا به سرعت مسیر بهینه را با توجه به شرایط جدید پیدا کند. به این ترتیب که اگر یال (یا گره‌ای) حذف شود دیگر لازم نیست که الگوریتم از ابتدا مسئله را حل کند بلکه از جایی که مسئله حل شده تا محل حذف یال (یا گره) هنوز بهترین مسیر را داریم، از این به بعد مورچه‌ها می‌توانند پس از مدت کوتاهی مسیر بهینه (کوتاهترین) را بیابند.

کاربردهای الگوریتم کلونی مورچه ها

از کاربردهای الگوریتم کلونی مورچه ها می‌توان به بهینه کردن هر مسئله‌ای که نیاز به یافتن کوتاهترین مسیر دارد، اشاره نمود:

۱. مسیر یابی داخل شهری و بین شهری.

۲. مسیر یابی بین پست‌های شبکه‌های توزیع برق ولتاژ بالا.

۳. مسیر یابی شبکه‌های کامپیوتری. ۴-استفاده ازوب. ۵-استفاده ازACOدربهینه سازی شبکه‌های توزیع آب و…

الگوریتم

پروسهٔ پیدا کردن کوتاه‌ترین مسیر توسط مورچه‌ها، ویژگی‌های بسیار جالبی دارد، اول از همه قابلیت تعمیم زیاد و خود- سازمانده بودن آن است. در ضمن هیچ مکانیزم کنترل مرکزی ای وجود ندارد. ویژگی دوم قدرت زیاد آن است. سیستم شامل تعداد زیادی از عواملی است که به تنهایی بی‌اهمیت هستند بنابراین حتی تلفات یک عامل مهم، تأثیر زیادی روی کارایی سیستم ندارد. سومین ویژگی این است که، پروسه یک فرایند تطبیقی است. از آنجا که رفتار هیچ‌کدام از مورچه‌ها معین نیست و تعدادی از مورچه‌ها همچنان مسیر طولانی‌تر را انتخاب می‌کنند، سیستم می‌تواند خود را با تغییرات محیط منطبق کند و ویژگی آخر اینکه این پروسه قابل توسعه است و می‌تواند به اندازهٔ دلخواه بزرگ شود. همین ویژگی‌ها الهام بخش طراحی الگوریتم‌هایی شده‌اند که در مسائلی که نیازمند این ویژگی‌ها هستند کاربرد دارند. اولین الگوریتمی که بر این اساس معرفی شد، الگوریتم ABC بود. چند نمونه دیگر از این الگوریتم‌ها عبارتند از: AntNet,ARA,PERA,AntHocNet.

انواع مختلف الگوریتم بهینه‌سازی مورچگان

در پایین تعدادی از انواع شناخته شده از الگوریتم بهینه‌سازی مورچگان را معرفی می‌کنیم:

۱- سیستم مورچه نخبگان: در این روش بهترین راه حل کلی در هر تکرار فرمون آزاد می‌کند. همچنین این روش برای تمام مورچه‌های مصنوعی باید انجام شود.

۲- سیستم مورچه ماکسیموم – مینیمم: یک مقدار کمینه و بیشینه برای فرمون تعیین کرده و فقط در هر مرحله بهترین جواب این مقدار را آزاد می‌کند و تمام گره‌های مجاور ان به مقدار فرمون بیشینهمقدار دهی اولیه می‌شوند.

۳- سیستم کلونی مورچه: که در بالا توضیحات کافی داده شده است.

۴- سیستم مورچه بر اساس رتبه: تمام راه حل‌های بدست آماده بر اساس طول جواب رتبه‌بندی می‌شوند و بر اساس همین رتبه‌بندی مقدار فرمون آزاد سازی شده توسط آنها مشخص خواهد شد و راه حل با طول کمتر از راه حل دیگر با طول بیشتر مقدار فرمون بیشتری آزاد می‌کند.

۵ – سیستم مورچه متعامد مداوم: در این روش مکانیزم تولید فرمون به مورچه اجازه می‌دهد تا برای رسیدن به جواب بهتر و مشترک با بقیه مورچه‌ها جستجو انجام دهد با استفاده از روش طراحی متعامد مورچه می‌تواند در دامنه تعریف شده خود به صورت مداوم برای بدست آوردن بهترین جواب جستجو کند که این عمل به هدف رسیدن به جواب بهینه و صحیح ما را نزدیک می‌کند. روش طراحی متعامد می‌تواند به دیگر روش‌های جستجو دیگر گسترش پیدا کنند تا به مزیت‌های این روش‌های جستجو اضافه کند.

منبع


انسان هميشه براي الهام گرفتن به جهان زنده پيرامون خود نگريسته است. يکي از بهترين طرح هاي شناخته شده، طرح پرواز انسان است که ابتدا لئورناردو داوينچي(1519-1452) طرحي از يک ماشين پرنده را بر اساس ساختمان بدن خفاش رسم نمود. چهار صد سال بعد کلمان آدر ماشين پرنده اي ساخت که داراي موتور بود و بجاي بال از ملخ استفاده مي کرد.

هم اکنون کار روي توسعه سيستم هاي هوشمند با الهام از طبيعت از زمينه هاي خيلي پرطرفدار هوش مصنوعي است. الگوريتمهاي ژنتيک که با استفاده از ايده تکاملي دارويني و انتخاب طبيعي مطرح شده، روش بسيار خوبي براي يافتن مسائل بهينه سازيست. ايده تکاملي دارويني بيانگر اين مطلب است که هر نسل نسبت به نسل قبل داراي تکامل است و آنچه در طبيعت رخ مي دهد حاصل ميليون ها سال تکامل نسل به نسل موجوداتي مثل مورچه است.

الگوريتم کلونی مورچه براي اولين بار توسط دوريگو (Dorigo) و همکارانش به عنوان يک راه حل چند عامله (Multi Agent) براي مسائل مشکل بهينه سازي مثل فروشنده دوره گرد     (TSP :Traveling Sales Person) ارائه شد.

عامل هوشند(Intelligent Agent) موجودي است که از طريق حسگر ها قادر به درک پيرامون خود بوده و از طريق تاثير گذارنده ها مي تواند روي محيط تاثير بگذارد.

الگوريتم کلونی مورچه الهام گرفته شده از مطالعات و مشاهدات روي کلونی مورچه هاست. اين مطالعات نشان داده که مورچه ها حشراتي اجتماعي هستند که در کلونی ها زندگي مي کنند و رفتار آنها بيشتر در جهت بقاء کلونی است تا درجهت بقاء يک جزء از آن. يکي از مهمترين و جالبترين رفتار مورچه ها، رفتار آنها براي يافتن غذا است و بويژه چگونگي پيدا کردن کوتاهترين مسير ميان منابع غذايي و آشيانه. اين نوع رفتار مورچه ها داراي نوعي هوشمندي توده اي  است که اخيرا مورد توجه دانشمندان قرار گرفته است.بايد تفاوت هوشمندي توده اي(کلونی) و هوشمندي اجتماعي را روشن کنيم.

در هوشمندي اجتماعي عناصر ميزاني از هوشمندي را دارا هستند. بعنوان مثال در فرآيند ساخت ساختمان توسط انسان، زماني که به يک کارگر گفته ميشود تا يک توده آجر را جابجا کند، آنقدر هوشمند هست تا بداند براي اينکار بايد از فرغون استفاده کند نه مثلا بيل!!! نکته ديگر تفاوت سطح هوشمندي افراد اين جامعه است. مثلا هوشمندي لازم براي فرد معمار با يک کارگر ساده متفاوت است.

در هوشمندي توده اي عناصر رفتاري تصادفي دارند و بين آن ها هيچ نوع ارتباط مستقيمي وجود ندارد و آنها تنها بصورت غير مستقيم و با استفاده از نشانه ها با يکديگر در تماس هستند. مثالي در اين مورد رفتار موريانه ها در لانه سازيست.

جهت علاقه مند شدن شما به اين رفتار موريانه ها وتفاوت هوشمندي توده اي و اجتماعي توضيحاتي را ارائه مي دهم :

فرآيند ساخت لانه توسط موريانه ها مورد توجه دانشمندي فرانسوي به نام گرس قرار گرفت. موريانه ها براي ساخت لانه سه فعاليت مشخص از خود بروز مي دهند. در ابتدا صدها موريانه به صورت تصادفي به اين طرف و آن طرف حرکت مي کنند. هر موريانه به محض رسيدن به فضايي که کمي  بالاتر از سطح زمين قرار  دارد شروع به ترشح بزاق مي کنند و خاک را به بزاق خود آغشته مي کنند. به اين ترتيب گلوله هاي کوچک خاکي با بزاق خود درست مي کنند. عليرغم خصلت کاملا تصادفي اين رفتار، نتيجه تا حدي منظم است.

در پايان اين مرحله در منطقه اي محدود تپه هاي بسيار کوچک مينياتوري از اين گلوله هاي خاکي آغشته به بزاق شکل مي گيرد. پس از اين، همه تپه هاي مينياتوري باعث مي شوند تا موريانه ها رفتار ديگري از خود بروز دهند. در واقع اين تپه ها به صورت نوعي نشانه  براي موريانه ها عمل مي کنند. هر موريانه به محض رسيدن به اين تپه ها با انرژي بسيار بالايي شروع به توليد گلوله هاي خاکي با بزاق خود مي کند. اين کار باعث تبديل شدن تپه هاي مينياتوري به نوعي ستون مي شود. اين رفتار ادامه مي يابد تا زماني که ارتفاع هر ستون به حد معيني برسد. در اين صورت  موريانه ها رفتار سومي از خود نشان مي دهند. اگر در نزديکي ستون فعلي ستون ديگيري نباشد بلافاصله آن ستون را رها مي کنند در غير اين صورت يعني در حالتي که در نزديکي اين ستون تعداد قابل ملاحظه اي ستون ديگر باشد، موريانه ها شروع به وصل کردن ستونها و ساختن لانه مي کنند.

تفاوتهاي هوشمندي اجتماعي انسان با هوشمندي توده اي موريانه را در همين رفتار ساخت لانه مي توان مشاهده کرد. کارگران ساختماني کاملا بر اساس يک طرح از پيش تعيين شده عمل مي کنند، در حالي که رفتار اوليه موريانه ها کاملا تصادفي است. علاوه بر اين ارتياط مابين کارگران سختماني مستقيم و از طريق کلمات و … است ولي بين موريانه ها هيچ نوع ارتباط مستقيمي وجود ندارد و آنها تنها بصورت غير مستقيم و از طريق نشانه ها با يکديگر در تماس اند. گرس نام اين رفتار را Stigmergie گذاشت، به معني رفتاري که هماهنگي مابين موجودات را تنها از طريق تغييرات ايجاد شده در محيط ممکن مي سازد.

 بهينه سازي مسائل به روش کلونی مورچه ها (ACO) :

همانطور که مي دانيم مسئله يافتن کوتاهترين مسير، يک مسئله بهينه سازيست که گاه حل آن بسيار دشوار است و گاه نيز بسيار زمانبر. بعنوان مثال مسئله فروشنده دوره گرد(TSP). در اين مسئله فروشنده دوره گرد بايد از يک شهر شروع کرده، به شهرهاي ديگر برود و سپس به شهر مبدا بازگردد بطوريکه از هر شهر فقط يکبار عبور کند و کوتاهترين مسير را نيز طي کرده باشد. اگر تعداد اين شهرها n باشد در حالت کلي اين مسئله از مرتبه (n-1)! است که براي فقط 21 شهر زمان واقعا زيادي مي برد:

روز1013*7/1 =  S1016*433/2 = ms10*1018*433/2 = !20

با انجام يک الگوريتم برنامه سازي پويا براي اين مسئله ، زمان از مرتبه نمايي بدست مي آيد که آن هم مناسب نيست. البته الگوريتم هاي ديگري نيز ارائه شده ولي هيچ کدام کارايي مناسبي ندارند. ACO الگوريتم کامل و مناسبي براي حل مسئله TSP است.

مورچه ها چگونه مي توانند کوتاهترين مسير را پيدا کنند؟

مورچه ها هنگام راه رفتن از خود ردي از ماده شيميايي فرومون(Pheromone) بجاي مي گذارند البته اين ماده بزودي تبخير مي شد ولي در کوتاه مدت بعنوان رد مورچه بر سطح زمين باقي مي ماند. يک رفتار پايه اي ساده در مورچه هاي وجود دارد :

آنها هنگام انتخاب بين دو مسير بصورت احتمالاتي( Statistical)  مسيري را انتخاب مي کنند که فرومون بيشتري داشته باشد يا بعبارت ديگر مورچه هاي بيشتري قبلا از آن عبور کرده باشند. حال دقت کنيد که همين يک تمهيد ساده چگونه منجر به پيدا کردن کوتاهترين مسير خواهد شد :

همانطور که در شکل 1-1 مي بينيم مورچه هاي روي مسير AB در حرکت اند (در دو جهت مخالف) اگر در مسير مورچه ها مانعي قرار ديهم(شکل 2-1) مورچه ها دو راه براي انتخاب کردن دارند. اولين مورچه ازA  مي آيد و بهC  مي رسد، در مسير هيچ فروموني نمي بيند بنابر اين براي مسير چپ و راست احتمال يکسان مي دهد و بطور تصادفي و احتمالاتي مسير CED را انتخاب مي کند. اولين مورچه اي که مورچه اول را دنبال مي کند زودتر از مورچه اولي که از مسير CFD رفته به مقصد مي رسد. مورچه ها در حال برگشت و به مرور زمان يک اثر بيشتر فرومون را روي CED حس مي کنند و آنرا بطور احتمالي و تصادفي ( نه حتما و قطعا)  انتخاب مي کنند. در نهايت مسير CED بعنوان مسير کوتاهتر برگزيده مي شود. در حقيقت چون طول مسير CED کوتاهتر است زمان رفت و برگشت از آن هم کمتر مي شود و در نتيجه مورچه هاي بيشتري نسبت به مسير ديگر آنرا طي خواهند کرد چون فرومون بيشتري در آن وجود دارد.

نکه بسيار با اهميت اين است که هر چند احتمال انتخاب مسير پر فرومون ت توسط مورچه ها بيشتر است ولي اين کماکان احتمال است و قطعيت نيست. يعني اگر مسير CED پرفرومون تر از CFD باشد به هيچ عنوان نمي شود نتيجه گرفت که همه مورچه ها از مسيرCED  عبور خواهند کرد بلکه تنها مي توان گفت که مثلا 90% مورچه ها از مسير کوتاهتر عبور خواهند کرد. اگر فرض کنيم که بجاي اين احتمال قطعيت وجود مي داشت، يعني هر مورچه فقط و فقط مسير پرفرومون تر را انتخاب ميکرد آنگاه اساسا اين روش ممکن نبود به جواب برسد. اگر تصادفا اولين مورچه مسيرCFD(مسير دورتر) را انتخاب مي کرد و ردي از فرومون بر جاي مي گذاشت آنگاه همه مورچه ها بدنبال او حرکت مي کردند و هيچ وقت کوتاهترين مسير يافته نمي شد. بنابراين تصادف و احتمال نقش عمده اي در ACO بر عهده دارند.

نکته ديگر مسئله تبخير شدن فرومون بر جاي گذاشته شده است. برفرض اگر مانع در مسير  AB برداشته شود و فرومون تبخير نشود مورچه ها همان مسير قبلي را طي خواهند کرد. ولي در حقيقت اين طور نيست. تبخير شدن فرومون و احتمال به مورچه ها امکان پيدا کردن مسير کوتاهتر جديد را مي دهند.

1-1
پیدا کردن کوتاه ترین مسیر 1

2-1

پیدا کردن کوتاه ترین مسیر 2

3-1

پیدا کردن کوتاه ترین مسیر 3

4-1

پیدا کردن کوتاه ترین مسیر 4

مزيت هاي ACO :

همانطور که گقته شد «تبخير شدن فرومون» و «احتمال-تصادف» به مورچه ها امکان پيدا کردن کوتاهترين مسير را مي دهند. اين دو ويژگي باعث ايجاد انعطاف در حل هرگونه مسئله بهينه سازي مي شوند. مثلا در گراف شهرهاي مسئله فروشنده دوره گرد، اگر يکي از يالها (يا گره ها) حذف شود الگوريتم اين توانايي را دارد تا به سرعت مسير بهينه را با توجه به شرايط جديد پيدا کند. به اين ترتيب که اگر يال (يا گره اي) حذف شود ديگر لازم نيست که الگوريتم از ابتدا مسئله را حل کند بلکه از جايي که مسئله حل  شده تا محل حذف يال (يا گره) هنوز بهترين مسير را داريم، از اين به بعد مورچه ها مي توانند پس از مدت کوتاهي مسير بهينه(کوتاهترين) را بيابند.

کاربردهاي ACO :

از کاربردهاي  ACO مي توان به بهينه کردن هر مسئله اي که نياز به يافتن کوتاهترين مسير دارد ، اشاره نمود :

1. مسير يابي داخل شهري و بين شهري
2. مسير يابي بين پست هاي شبکه هاي توزيع برق ولتاژ بالا

3. مسير يابي شبکه هاي کامپيوتري

مسير يابي شبکه هاي کامپيوتري با استفاده از ACO :

اطلاعات بر روي شبکه بصورت بسته هاي اطلاعاتي کوچکي (Packet) منتقل مي شوند. هر يک از اين بسته ها بر روي شبکه در طي مسير از مبدا تا مقصد بايد از گره هاي زيادي که مسيرياب (Router) نام دارند عبور مي کنند. در داخل هر مسيرياب جدولي قرار دارد تا بهترين و کوتاهترين مسير بعدي تا مقصد از طريق آن مشخص مي شود، بنابر اين بسته هاي اطلاعاتي حين گذر از مسيرياب ها با توجه به محتويات اين جداول عبور داده مي شوند.

روشي بنام ACR : Ant Colony Routering پيشنهاد شده که بر اساس ايده کلونی مورچه به بهينه سازي جداول مي پردازيد و در واقع به هر مسيري با توجه به بهينگي آن امتياز مي دهد. استفاده از ACR به اين منظور داراي برتري نسبت به ساير روش هاست که با طبيعت ديناميک شبکه سازگاري دارد، زيرا به عنوان مثال ممکن است مسيري پر ترافيک شود يا حتي مسير يابي (Router) از کار افتاده باشد و بدليل انعطاف پذيري که ACO در برابر اين تغييرات دارد همواره بهترين راه حل بعدي را در دسترس قرار مي دهد.

الگوریتم کلونی مورچه ها قسمت 1
الگوریتم کلونی مورچه ها قسمت 2
الگوریتم کلونی مورچه ها قسمت 3