عنوان: الگوریتم مورچه گان
نویسنده: امیر افسر
آموزش:
الگوریتم مورچه گان از آزمایشی كه توسط Goss و همكارانش (Goss et al.,1989) با استفاده از یك كلونی ازمورچه های واقعی ترتیب داده بودند، الهام گرفته شد. آمد و شد یك كلونی آزمایشگاهی از مورچه های آرژانتینی كه از طریق یک پل با دو شاخه با طولهای متفاوت كه یك منبع غذایی را به لانه متصل می كرد، مورد مشاهده قرار گرفت. شكل 1 این ارتباط را به تصویر كشیده است. شاخه ها به صورتی قرار داده شده بودند كه مورچه ها درهر جهت (از لانه به منبع غذایی و یا برعكس) می بایست یكی از این دو شاخه را برای ادامه مسیر انتخاب می كردند.
مشاهدات تجربی نشان داد كه بعد از یك مرحله گذرا كه می تواند فقط چند دقیقه ادامه داشته باشد، اغلب مورچه ها مسیر كوتاهتر را انتخاب می كنند. همچنین مشاهده شده است كه احتمال انتخاب مسیر كوتاهتر توسط كلونی با تفاوت در طول بین دو شاخه افزایش می یابد. در حقیقت، مورچه های آرژانتینی درحالیكه از لانه به سمت منبع غذایی حركت می كنند و بالعكس، یك ماده شیمیایی كه فرومون نامیده می شود، بر روی مسیر از خود بر جای می گذارند. هنگامیكه آنها به یك نقطه تصمیم می رسند (نظیر تقاطع بین شاخه كوتاهتر وشاخه بلندتر)، بر پایه احتمال یك مسیر را انتخاب می كنند كه احتمال انتخاب هر شاخه متناسب با اثر مقدار فرمونی است كه روی آن شاخه باقی مانده است. میزان فرومون هر شاخه از طریق حس بویایی مورچگان تشخیص داده می شود. این رفتار مورچه ها، یك اثر خودشتابی دارد. زیرا واقعیت انتخاب یك مسیر توسط چند مورچه، احتمال آنکه مورچه های دیگر نیز آن مسیر را انتخاب نمایند، افزایش می دهد.
شکل 1: ارتباط دو شاخه از یک لانه موچگان به یک منبع غذایی
در ابتدای آزمایش هیچ فرومونی روی دو شاخه نیست. بنابراین مورچه هایی كه از لانه به سمت منبع غذایی حركت می كنند هر یك از شاخه ها را با احتمال 50 درصد انتخاب خواهند كرد. به دلیل تفاوت در طول شاخه ها، مورچه هایی كه شاخه كوتاهتر را انتخاب می كنند، اولین مورچه هایی خواهند بود كه به منبع غذایی دست پیدا خواهند كرد. هنگامیكه این مورچه ها در مسیر بازگشت خودشان به لانه، به نقطه تصمیم (محل انشعاب دو شاخه از مسیر اصلی) می رسند، مقداری فرومون روی شاخه كوتاهتر خواهند یافت (این در حقیقت همان فرومونی است كه آنها در هنگام عزیمت از لانه به منبع غذایی از خود بر جای گذاشته اند) و بنابراین مسیر كوتاهتر را با احتمال بیشتری نسبت به مسیر بلندتر انتخاب خواهند كرد. بنابراین فرومون جدیدی روی مسیر انتخاب شده رها خواهد شد و این خود دلیلی بری جذابتر شدن این مسیر برای مورچه های بعدی خواهد بود. درحالیكه این فرآیند تكرار می شود، فرومون روی شاخه كوتاهتر نسبت به شاخه بلندتر با نرخ بیشتری ریخته می شود، لذا مسیر كوتاهتر به دفعات بیشتر و بیشتری توسط مورچه ها انتخاب خواهد شد، تا سرانجام تمام مورچه ها از این مسیر استفاده كنند. در ادامه به این بحث خواهیم پرداخت كه چگونه این ایده ساده می تواند زمینه را برای جستجوی جواب مسایل بهینه یابی پیچیده به وسیله مورچه های مصنوعی فراهم نماید.
رئوس پایه ای
در این قسمت یك الگوریتم بسیار ساده مورچه مدار ارائه می شود تا بوسیله آن رفتار پایه ای روش فراابتكاری ACO بیان گردد و مؤلفه های اصلی آن نشان داده شود.
كار اصلی هر مورچه مصنوعی (مانند مورچه های طبیعی)، جستجوی كوتاهترین مسیر بین یك جفت گره در شبكه ایست كه مساله به طور مناسبی در قالب آن شبكه بیان شده است. G=(N,A) یك شبكه همبند با n=[N] گره است. الگوریتم ساده ACO یا S-ACO می تواند برای یافتن یك راه حل برای مساله كوتاهترین مسیر كه روی شبكه G تعریف شده باشد، مورد استفاده قرار گیرد. جواب مساله مسیری خواهد بود كه گره منبع f را به گره مقصد d متصل كند. در ضمن طول مسیر بوسیله تعداد پرشها در مسیر داده شده است.
شکل 2: مورچه ها مسیر پررنگ تر را برای عبور از مبدأ به مقصد انتخاب می کنند.
به هر سویه (i,j) از شبكه یك متغیر τij مرتبط شده است كه اثر فرمون مصنوعی نامیده می شود. از این پس ما فقط از عبارت "اثر فرومون" و یا برای تلخیص بیشتر از "فرومون " به جای "اثرفرومون مصنوعی" استفاده خواهیم كرد. اثرات فرومونی بوسیله مورچه ها نوشته (برجای گذاشته) می شود و خوانده (بوئیده) می شود. مقدار (شدت) اثر فرومون متناسب با مطلوبیت استفاده از آن سویه ایست كه برای ساختن جواب به كار می رود.
هر مورچه یك سیاست تصمیم گیری با ساختار گام به گام برای ساختن جوابهای مساله به كار می برد. در هرگره از اطلاعات محلی با یك روش احتمالی جهت تصمیم گیری برای حركت به گره بعدی استفاده می شود. اطلاعات محلی یا در خود گره و یا روی سویه خروجی از آن گره نگهداری می شود.
قانون تصمیم گیری مورچه k ام كه درگره i قرار گرفته، از اثرات فرومونی τij برای محاسبه احتمالی انتخاب گره به عنوان گره بعدی، استفاده می كند. لازم به ذكر است كه در ابتدای فرآیند جستجو، یك مقدار فرومون τij به تمام سویه ها اختصاص داده شده است. Ni مجموعه گره ها همسایه گرهi است كه می توان به آنها عزیمت كرد.
مورچه ها درحالیكه یك جواب ایجاد می كنند، در همان حالت اطلاعات فرومونی را بر روی سویه هایی كه از آنها تشكیل جواب استفاده شده، برجای می گذارند. در S-ACO مورچه ها یك مقدار ثابت از فرمون Δτ بر جای می گذارند. توجه داشته باشید كه هنگامیكه یك مورچه در زمان t از گره i به گره j حركت می كند، مقدار فرومون τij سویه (i,j) را به صورت زیر تغییر خواهد داد.
به وسیله این قانون (كه مورچه های واقعی نیز بطور مشابه به همین صورت عمل
می كنند) مورچه ای كه سویه متصل كننده گره i به گره j مورداستفاده قرار می دهد، باعث افزایش احتمال انتخاب سویه (i,j) توسط مورچه های بعدی خواهد شد. در حالتیكه مورچه ها واقعی باشند، اثر خودشتابی و تفاوت بین طول مسیرها، همگرایی به سوی مسیر كوتاهتر را میسر می سازند.
به منظور اجتناب از همگرایی سریع همه مورچه ها به سمت یك مسیر بهینه جزئی، یك مكانیزم كاوش در نظر گرفته شده است. فرومون به صورت تبخیر كاهش می یابد و كاوش سویه های مختلف در طی كل فرآیند جستجو را میسر می سازد. تبخیر فرومون بصورت ساده ای انجام می شود. در ضمن كاهش اثرات فرومونی بصورت تصاعدی انجام می پذیرد. در هر تكرار الگوریتم داریم:
آزمایش های مقدماتی انجام شده بوسیله S-ACO از یك مدل شبكه ساده استفاده می كرد كه در شكل 2 نشان داده شده است. الگوریتم عملاً كوتاهترین مسیر شبیه سازی شده بین لانه و منبع غذایی را پیدا می كند. همچنین آزمایشها نشان داده كه اگر پیچیدگی شبكه جستجو شده افزایش یابد، رفتار الگوریتم ناپایدار خواهد شد و مقادیر به دست آمده نیز یكسان نخواهد بود. در این حالت مقادیر پارامترها موضوع مهمی خواهند بود. به عنوان مثال اگر بین لانه و منابع غذایی راههایی بیشتر قرارداده شود، این نوع پیچیدگی بوجود خواهد آمد. به منظور درك بهتر مطالب ذكر شده توجه داشته باشید كه اگر مقدار فرومون بر جای گاشته شده بوسیله مورچه ها را متناسب با كیفیت جوابی كه ساخته اند، قرار دهیم در این صورت اطلاعات فرومونی برای هدایت جستجوی مورچه ها بسیار مفید واقع خواهد شد. همچنین بدلیل اینكه در خیلی از مسائل، انواع مختلفی از اطلاعات قابل تحصیل در گره ها در دسترس است، مطلوب خواهد بود كه مورچه ها توانایی استفاده از آنها را داشته باشند. نكته جالب توجه دیگر این است كه سطح مسائلی كه بوسیله ACO به آنها پرداخته می شود می تواند بزرگتر شود، در حالیكه S-ACO بدون در نظر گرفتن محدودیتهای اضافی، صرفاً برای مسائل كوتاهترین مسیر می تواند مورد استفاده قرار گیرد.
نویسنده: امیر افسر
آموزش:
الگوریتم مورچه گان از آزمایشی كه توسط Goss و همكارانش (Goss et al.,1989) با استفاده از یك كلونی ازمورچه های واقعی ترتیب داده بودند، الهام گرفته شد. آمد و شد یك كلونی آزمایشگاهی از مورچه های آرژانتینی كه از طریق یک پل با دو شاخه با طولهای متفاوت كه یك منبع غذایی را به لانه متصل می كرد، مورد مشاهده قرار گرفت. شكل 1 این ارتباط را به تصویر كشیده است. شاخه ها به صورتی قرار داده شده بودند كه مورچه ها درهر جهت (از لانه به منبع غذایی و یا برعكس) می بایست یكی از این دو شاخه را برای ادامه مسیر انتخاب می كردند.
مشاهدات تجربی نشان داد كه بعد از یك مرحله گذرا كه می تواند فقط چند دقیقه ادامه داشته باشد، اغلب مورچه ها مسیر كوتاهتر را انتخاب می كنند. همچنین مشاهده شده است كه احتمال انتخاب مسیر كوتاهتر توسط كلونی با تفاوت در طول بین دو شاخه افزایش می یابد. در حقیقت، مورچه های آرژانتینی درحالیكه از لانه به سمت منبع غذایی حركت می كنند و بالعكس، یك ماده شیمیایی كه فرومون نامیده می شود، بر روی مسیر از خود بر جای می گذارند. هنگامیكه آنها به یك نقطه تصمیم می رسند (نظیر تقاطع بین شاخه كوتاهتر وشاخه بلندتر)، بر پایه احتمال یك مسیر را انتخاب می كنند كه احتمال انتخاب هر شاخه متناسب با اثر مقدار فرمونی است كه روی آن شاخه باقی مانده است. میزان فرومون هر شاخه از طریق حس بویایی مورچگان تشخیص داده می شود. این رفتار مورچه ها، یك اثر خودشتابی دارد. زیرا واقعیت انتخاب یك مسیر توسط چند مورچه، احتمال آنکه مورچه های دیگر نیز آن مسیر را انتخاب نمایند، افزایش می دهد.
شکل 1: ارتباط دو شاخه از یک لانه موچگان به یک منبع غذایی
در ابتدای آزمایش هیچ فرومونی روی دو شاخه نیست. بنابراین مورچه هایی كه از لانه به سمت منبع غذایی حركت می كنند هر یك از شاخه ها را با احتمال 50 درصد انتخاب خواهند كرد. به دلیل تفاوت در طول شاخه ها، مورچه هایی كه شاخه كوتاهتر را انتخاب می كنند، اولین مورچه هایی خواهند بود كه به منبع غذایی دست پیدا خواهند كرد. هنگامیكه این مورچه ها در مسیر بازگشت خودشان به لانه، به نقطه تصمیم (محل انشعاب دو شاخه از مسیر اصلی) می رسند، مقداری فرومون روی شاخه كوتاهتر خواهند یافت (این در حقیقت همان فرومونی است كه آنها در هنگام عزیمت از لانه به منبع غذایی از خود بر جای گذاشته اند) و بنابراین مسیر كوتاهتر را با احتمال بیشتری نسبت به مسیر بلندتر انتخاب خواهند كرد. بنابراین فرومون جدیدی روی مسیر انتخاب شده رها خواهد شد و این خود دلیلی بری جذابتر شدن این مسیر برای مورچه های بعدی خواهد بود. درحالیكه این فرآیند تكرار می شود، فرومون روی شاخه كوتاهتر نسبت به شاخه بلندتر با نرخ بیشتری ریخته می شود، لذا مسیر كوتاهتر به دفعات بیشتر و بیشتری توسط مورچه ها انتخاب خواهد شد، تا سرانجام تمام مورچه ها از این مسیر استفاده كنند. در ادامه به این بحث خواهیم پرداخت كه چگونه این ایده ساده می تواند زمینه را برای جستجوی جواب مسایل بهینه یابی پیچیده به وسیله مورچه های مصنوعی فراهم نماید.
رئوس پایه ای
در این قسمت یك الگوریتم بسیار ساده مورچه مدار ارائه می شود تا بوسیله آن رفتار پایه ای روش فراابتكاری ACO بیان گردد و مؤلفه های اصلی آن نشان داده شود.
كار اصلی هر مورچه مصنوعی (مانند مورچه های طبیعی)، جستجوی كوتاهترین مسیر بین یك جفت گره در شبكه ایست كه مساله به طور مناسبی در قالب آن شبكه بیان شده است. G=(N,A) یك شبكه همبند با n=[N] گره است. الگوریتم ساده ACO یا S-ACO می تواند برای یافتن یك راه حل برای مساله كوتاهترین مسیر كه روی شبكه G تعریف شده باشد، مورد استفاده قرار گیرد. جواب مساله مسیری خواهد بود كه گره منبع f را به گره مقصد d متصل كند. در ضمن طول مسیر بوسیله تعداد پرشها در مسیر داده شده است.
شکل 2: مورچه ها مسیر پررنگ تر را برای عبور از مبدأ به مقصد انتخاب می کنند.
به هر سویه (i,j) از شبكه یك متغیر τij مرتبط شده است كه اثر فرمون مصنوعی نامیده می شود. از این پس ما فقط از عبارت "اثر فرومون" و یا برای تلخیص بیشتر از "فرومون " به جای "اثرفرومون مصنوعی" استفاده خواهیم كرد. اثرات فرومونی بوسیله مورچه ها نوشته (برجای گذاشته) می شود و خوانده (بوئیده) می شود. مقدار (شدت) اثر فرومون متناسب با مطلوبیت استفاده از آن سویه ایست كه برای ساختن جواب به كار می رود.
هر مورچه یك سیاست تصمیم گیری با ساختار گام به گام برای ساختن جوابهای مساله به كار می برد. در هرگره از اطلاعات محلی با یك روش احتمالی جهت تصمیم گیری برای حركت به گره بعدی استفاده می شود. اطلاعات محلی یا در خود گره و یا روی سویه خروجی از آن گره نگهداری می شود.
قانون تصمیم گیری مورچه k ام كه درگره i قرار گرفته، از اثرات فرومونی τij برای محاسبه احتمالی انتخاب گره به عنوان گره بعدی، استفاده می كند. لازم به ذكر است كه در ابتدای فرآیند جستجو، یك مقدار فرومون τij به تمام سویه ها اختصاص داده شده است. Ni مجموعه گره ها همسایه گرهi است كه می توان به آنها عزیمت كرد.
مورچه ها درحالیكه یك جواب ایجاد می كنند، در همان حالت اطلاعات فرومونی را بر روی سویه هایی كه از آنها تشكیل جواب استفاده شده، برجای می گذارند. در S-ACO مورچه ها یك مقدار ثابت از فرمون Δτ بر جای می گذارند. توجه داشته باشید كه هنگامیكه یك مورچه در زمان t از گره i به گره j حركت می كند، مقدار فرومون τij سویه (i,j) را به صورت زیر تغییر خواهد داد.
به وسیله این قانون (كه مورچه های واقعی نیز بطور مشابه به همین صورت عمل
می كنند) مورچه ای كه سویه متصل كننده گره i به گره j مورداستفاده قرار می دهد، باعث افزایش احتمال انتخاب سویه (i,j) توسط مورچه های بعدی خواهد شد. در حالتیكه مورچه ها واقعی باشند، اثر خودشتابی و تفاوت بین طول مسیرها، همگرایی به سوی مسیر كوتاهتر را میسر می سازند.
به منظور اجتناب از همگرایی سریع همه مورچه ها به سمت یك مسیر بهینه جزئی، یك مكانیزم كاوش در نظر گرفته شده است. فرومون به صورت تبخیر كاهش می یابد و كاوش سویه های مختلف در طی كل فرآیند جستجو را میسر می سازد. تبخیر فرومون بصورت ساده ای انجام می شود. در ضمن كاهش اثرات فرومونی بصورت تصاعدی انجام می پذیرد. در هر تكرار الگوریتم داریم:
آزمایش های مقدماتی انجام شده بوسیله S-ACO از یك مدل شبكه ساده استفاده می كرد كه در شكل 2 نشان داده شده است. الگوریتم عملاً كوتاهترین مسیر شبیه سازی شده بین لانه و منبع غذایی را پیدا می كند. همچنین آزمایشها نشان داده كه اگر پیچیدگی شبكه جستجو شده افزایش یابد، رفتار الگوریتم ناپایدار خواهد شد و مقادیر به دست آمده نیز یكسان نخواهد بود. در این حالت مقادیر پارامترها موضوع مهمی خواهند بود. به عنوان مثال اگر بین لانه و منابع غذایی راههایی بیشتر قرارداده شود، این نوع پیچیدگی بوجود خواهد آمد. به منظور درك بهتر مطالب ذكر شده توجه داشته باشید كه اگر مقدار فرومون بر جای گاشته شده بوسیله مورچه ها را متناسب با كیفیت جوابی كه ساخته اند، قرار دهیم در این صورت اطلاعات فرومونی برای هدایت جستجوی مورچه ها بسیار مفید واقع خواهد شد. همچنین بدلیل اینكه در خیلی از مسائل، انواع مختلفی از اطلاعات قابل تحصیل در گره ها در دسترس است، مطلوب خواهد بود كه مورچه ها توانایی استفاده از آنها را داشته باشند. نكته جالب توجه دیگر این است كه سطح مسائلی كه بوسیله ACO به آنها پرداخته می شود می تواند بزرگتر شود، در حالیكه S-ACO بدون در نظر گرفتن محدودیتهای اضافی، صرفاً برای مسائل كوتاهترین مسیر می تواند مورد استفاده قرار گیرد.
پیوند ها