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

الگوریتم کلونی مورچگان یا الگوریتم بهینه سازی کلونی مورچه Ant Colony Optimization الهام گرفته شده از مطالعات و مشاهدات روی کلونی مورچه هاست. این مطالعات نشان داده که مورچه‌ها حشراتی اجتماعی هستند که در کلونی‌ها زندگی می‌کنند و رفتار آنها بیشتر در جهت بقاء کلونی است تا درجهت بقاء یک جزء از آن. یکی از مهمترین و جالبترین رفتار مورچه‌ها، رفتار آنها برای یافتن غذا است و به ویژه چگونگی پیدا کردن کوتاهترین مسیر میان منابع غذایی و آشیانه است.

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

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

از آنجایی که مورچه ها اصلا چشم ندارند، تعاملات آن ها از طریق ماده شیمیایی فرومون Pheromone که از آن برای نشان گذاری مسیر استفاده می شود، اانجام می گیرد. هرچه فرومن های بیشتری در مسیر قرار گیرد مابقی مورچه ها از این مسیر بیشتر استفاده می کنند؛ بنابراین، چنین کمیتی نشان می دهد که این مسیر به عنوان یکی از بهینه ترین و کوتاه ترین راه می باشد. اکنون نگاهی به یک نمونه عینی در شکل زیر می اندازیم. هدف پیدا کردن بهترین راه از نقطه آغازی N (آشیانه) به نقطه مقصد F (منبع غذا) می باشد.

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

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

مراحل الگوریتم کلونی مورچگان بصورت زیر است.

1- ارزش دهی مورچه ها (مقداردهی اولیه)

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

2- یافتن راه حل

چون الگوریتم ACO تلاش می کند تا به تقلید رفتار مورچه های واقعی با استفاده از فرایند شبیه سازی بپردازد، از یک تابع احتمال برای توصیف مسیر استفاده می گردد. احتمال دسترسی به نقطه j از نقطه i (احتمال انتقال) بر طبق به فرمول زیر محاسبه می شود.

که در این فرمول τ_ij مقدار ماده شیمیایی فرومن در نقاط (i,j) می باشد. که حس مورچه نیز نامیده می شود. η_ij نسبت دید نقاط (i, j) است که چشم مورچه نامیده می شود و هیورستیک مسئله می باشد، و بصورت η_ij=1⁄d_ij تعریف می شود که d_ij فاصله بین دو گره i و j است. α و β نیز پارامترهای سازگار، به معرفی اهمیت مسیر در برابر نسبت دید در زمان انتخاب نقطه بعدی برای حرکت می پردازد. tabuK فهرست گره های بازدید شده در مسیر کنونی که اصطلاحاً حافظه مورچه نامیده می شوند.

اگر α=0 باشد، الگوریتم حریصانه شده، به صورتی که انتخاب گره بعدی، کمیت فرومون ها را مد نظر قرار نداده به این ترتیب انتخاب نزدیک ترین مسیر اولویت پیدا می کند. اگر β=0 باشد الگوریتم تنها مقدار فرمون ها را بدون در نظر گرفتن طول مسیر، مد نظر قرار می دهد.

3- بروز رسانی فررمون ها

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

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

که در این فرمول τ_ij^k∆ کمیت فرومون های قرار داده شده بر روی نقاط پیموده شده (i, j) توسط مورچه k ام می باشد. و با استفاده از رابطه زیر قابل محاسبه است.

که در این فرمول Q مقدار ثابت، که به طور ساختگی فرمون ها را اضافه می کند؛ و L طول کلی مسیر می باشد هر چه مسیر بهتر باشد، فرومون های بیشتری در این مسیر قرار می گیرد. در کل، نقاطی که توسط بسیاری از مورچه ها مورد استفاده قرار می گیرد و بخشی از مسیرهای کوتاه را شامل می گردد، فرومن های بیشتری را دریافت کرده و به این ترتیب به احتمال بیشتری توسط مورچه ها در تکرار آبنده این مسیر الگوریتم انتخاب می گردد. فرایند تکرار زمانی متوقف می شود که حداقل یکی از نیازها برآورده گردد.

انواع مختلف الگوریتم کلونی مورچگان

در ادامه تعدادی از انواع الگوریتم کلونی مورچگان را معرفی می‌کنیم

1- سیستم کلونی مورچه Ant System

که در بالا توضیحات کافی داده شده‌است.

2- سیستم مورچه نخبگان Elitist Ant System

در این روش بهترین راه حل کلی در هر تکرار فرمون آزاد می‌کند. همچنین این روش برای تمام مورچه‌های مصنوعی باید انجام شود.

3- سیستم مورچه ماکس – مین Min-Max Ant System

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

4- سیستم مورچه بر اساس رتبه Ranked Ant System

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

5- سیستم مورچه متعامد مداوم Best-Worst Ant System

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

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

این سورس کد در محیط پایتون با استفاده از الگوریتم کلونی مورچگان برای حل مسئله فروشنده دوره گرد TSP نوشته شده است. برای اجرای این سورس کد نیاز به برخی از کتابخانه‌های پایتون می‌باشد. برای اطلاعات بیشتر و دریافت سورس کد می‌توانید بر روی لینک زیر کلیک نمایید.

همین الان کلیک کنید

فلوچارت الگوریتم