Multiple Ant Colony Optimizations
وجود مشکلات پیچیده شبکه ای نظیر مسیریابی مناسب، تعادل وتنظیم میزان بار و کنترل تراکم و ازدهام نیاز به تکنولوژی هوشمند و پیشرفته را برای حل اینگونه مسائل برجسته می سازد. هم اکنون کار روی توسعه سیستم های هوشمند با الهام از طبیعت از زمینه های خیلی پرطرفدار هوش جمعی است. ایده تکاملی داروین بیانگر این مطلب است که هر نسل نسبت به نسل قبل دارای تکامل است وآنچه در طبیعت رخ می دهد حاصل میلیونها سال تکامل نسل به نسل موجوداتی مثل مورچه است. الگوریتم کلونی مورچه برای اولین بار توسط دوریگو (Dorigo) و همکارانش به عنوان یک راه حل چندعامله (Multi Agent) برای مسائل مشکل بهینه سازی ارائه شد.Ant Colony Optimization ،(ACO) ، که مدلهایی بر اساس هوش جمعی (توده ای) مورچه هاست، با تبدیل به تکنولوژی کارآمد، در شبکه های کامپیوتری کاربرد پیدا کرده است. گرچه مورچه یک موجود ساده است، اما یک کلونی از آنها توانایی انجام وظایف سودمندی همچون، یافتن کوتاه ترین مسیر به سمت منبع غذا و به اشتراک گذاشتن این اطلاعات با دیگر مورچه ها از طریق به جای گذاشتن ماده ای شیمیایی به نام فرومون (pheromone) را دارند.
این نوع رفتار مورچه ها دارای نوعی هوشمندی توده ای است که اخیرا مورد توجه دانشمندان قرار گرفته است. باید تفاوت هوشمندی توده ای (کلونی) و هوشمندی اجتماعی را روشن کنیم.
در هوشمندی اجتماعی عناصر میزانی از هوشمندی را دارا هستند. همچون ساختن یک ساختمان توسط انسانها، مجموعه ای از معماران وکارگران، که بر اساس یک طرح قبلی کار می کنند. ولی در هوشمندی توده ای عناصر رفتاری تصادفی دارند و بین آنها هیچ نوع ارتباط مستقیمی وجود ندارد و آنها تنها بصورت غیرمستقیم و با استفاده از نشانه ها با یکدیگر در تماس هستند. مثالی در این مورد رفتار موریانه ها در لانه سازی است. این رفتار توسط یک دانشمند فرانسوی به نام گرس مورد مطالعه قرار گرفت. گرس نام ین رفتار را Stigmergie گذشت، به معنی رفتاری که هماهنگی مابین موجودات را تنها از طریق تغییرات ایجاد شده در محیط ممکن است.
طرح ریزی بر اساس کلونی مورچه ها به عنوان اجتماعی متحرک تقدم در مسیرهای چندگانه را ایجاد می کنند، هدف از این تحقیقات این است که یک رویکرد جدید از ACO را برای مسیریابی درست با هدف تعادل بار در شبکه های به هم فشرده، و تطابق با شکست در انتخاب را طراحی کنند. سهم این تحقیقات ارائه یک Multiple Ant Colony Optimization (MACO) است که شیوه ای برای یافتن مقصد و منبع را در مسیرهای تناوبی جست و جو می کند.
شکل ۱ :
۱) در نقطه Ne، هیچ یک از مورچه ها اطلاعی در مورد مسیر غذا Fo ندارند. از اینرو آنها تصادفی یکی از مسیرهای (R1,R2) را انتخاب می کنند. فرض کنید A1,A2 مسیر R1 را انتخاب می کنند و A3,A4 هم مسیر R2.
۲) هنگامیکه A1,A2 در امتداد R1مسیر حرکت می کنند و A3,A4 در امتداد R2، آنها به ترتیب مقدار معینی از فرومون R1و 2 R را در مسیر خود برجای می گذارند.
۳) ار آنجا که R1> R2 مورچه های A3,A4 زودتراز A1,A2 به غذا Fo می رسند.هنگامیکه A3,A4 با طی مسیرR2 به Fo می رسند۲= ۲ R و چون A1,A2 هنوز به Fo نرسیده اند ۰= R1. برای بازگشت به Ne باید A3,A4 یکی از دو مسیررا انتخاب کنند و ار آنجا که۲=۲ R و۰= R1 ، R2 شانس بیشتری برای انتخاب دارد، و به عنوان مسیر بازگشت مورچه های A3,A4 انتخاب می شود.
۴) وقتی A3,A4 برای دومین بار به Ne می رسند 2 R به ۴ افزایش می یابد و مسیر R2 به عنوان مسیر کوتاهتر تثبیت می شود. وقتی A1,A2 به Fo می رسند ۴=۲ R و ۲= R1 بنابراین آنها نیز R2 را به عنوان مسیر باز گشت انتخاب می کنند.
شکل ۲:
شبکه ساده مسیر است.
تبخیر فرومون و احتمال-تصادف به مورچه ها امکان پیدا کردن کوتاه ترین مسیر را می دهد. این دو ویژگی باعث ایجاد انعطاف در هرگونه مسدله بهینه سازی می شوند.
کاربردهای ACO:
از کاربردهای ACO می توان به بهینه کردن هر مسئله ای که نیاز به یافتن کوتاهترین مسیر دارد، اشاره نمود:
۱. مسیریابی داخل شهری و بین شهری
۲. مسیریابی بین پست های شبکه های توزیع برق ولتاژ بالا
۳. مسیریابی شبکه های کامپیوری
در هوشمندی اجتماعی عناصر میزانی از هوشمندی را دارا هستند. همچون ساختن یک ساختمان توسط انسانها، مجموعه ای از معماران وکارگران، که بر اساس یک طرح قبلی کار می کنند. ولی در هوشمندی توده ای عناصر رفتاری تصادفی دارند و بین آنها هیچ نوع ارتباط مستقیمی وجود ندارد و آنها تنها بصورت غیرمستقیم و با استفاده از نشانه ها با یکدیگر در تماس هستند. مثالی در این مورد رفتار موریانه ها در لانه سازی است. این رفتار توسط یک دانشمند فرانسوی به نام گرس مورد مطالعه قرار گرفت. گرس نام ین رفتار را Stigmergie گذشت، به معنی رفتاری که هماهنگی مابین موجودات را تنها از طریق تغییرات ایجاد شده در محیط ممکن است.
طرح ریزی بر اساس کلونی مورچه ها به عنوان اجتماعی متحرک تقدم در مسیرهای چندگانه را ایجاد می کنند، هدف از این تحقیقات این است که یک رویکرد جدید از ACO را برای مسیریابی درست با هدف تعادل بار در شبکه های به هم فشرده، و تطابق با شکست در انتخاب را طراحی کنند. سهم این تحقیقات ارائه یک Multiple Ant Colony Optimization (MACO) است که شیوه ای برای یافتن مقصد و منبع را در مسیرهای تناوبی جست و جو می کند.
شکل ۱ :
۱) در نقطه Ne، هیچ یک از مورچه ها اطلاعی در مورد مسیر غذا Fo ندارند. از اینرو آنها تصادفی یکی از مسیرهای (R1,R2) را انتخاب می کنند. فرض کنید A1,A2 مسیر R1 را انتخاب می کنند و A3,A4 هم مسیر R2.
۲) هنگامیکه A1,A2 در امتداد R1مسیر حرکت می کنند و A3,A4 در امتداد R2، آنها به ترتیب مقدار معینی از فرومون R1و 2 R را در مسیر خود برجای می گذارند.
۳) ار آنجا که R1> R2 مورچه های A3,A4 زودتراز A1,A2 به غذا Fo می رسند.هنگامیکه A3,A4 با طی مسیرR2 به Fo می رسند۲= ۲ R و چون A1,A2 هنوز به Fo نرسیده اند ۰= R1. برای بازگشت به Ne باید A3,A4 یکی از دو مسیررا انتخاب کنند و ار آنجا که۲=۲ R و۰= R1 ، R2 شانس بیشتری برای انتخاب دارد، و به عنوان مسیر بازگشت مورچه های A3,A4 انتخاب می شود.
۴) وقتی A3,A4 برای دومین بار به Ne می رسند 2 R به ۴ افزایش می یابد و مسیر R2 به عنوان مسیر کوتاهتر تثبیت می شود. وقتی A1,A2 به Fo می رسند ۴=۲ R و ۲= R1 بنابراین آنها نیز R2 را به عنوان مسیر باز گشت انتخاب می کنند.
شکل ۲:
شبکه ساده مسیر است.
تبخیر فرومون و احتمال-تصادف به مورچه ها امکان پیدا کردن کوتاه ترین مسیر را می دهد. این دو ویژگی باعث ایجاد انعطاف در هرگونه مسدله بهینه سازی می شوند.
کاربردهای ACO:
از کاربردهای ACO می توان به بهینه کردن هر مسئله ای که نیاز به یافتن کوتاهترین مسیر دارد، اشاره نمود:
۱. مسیریابی داخل شهری و بین شهری
۲. مسیریابی بین پست های شبکه های توزیع برق ولتاژ بالا
۳. مسیریابی شبکه های کامپیوری
مترجم : ز هره عظیمی
سایت تخصصی مهندسی پزشکی ایران aghaeifar.ir
کپی برداری با ذکر نام مترجم و سایت aghaeifar.ir بلا مانع است .
