مقاله به کار گیری الگوریتم کلونی مورچگان جهت حل مسئله بزرگترین دسته با تعریف اطلاعات ابتکاری

بخشی از مقاله

*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***

به کار گیری الگوریتم کلونی مورچگان جهت حل مسئله بزرگترین دسته با تعریف اطلاعات ابتکاری

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

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

-1 مقدمه
در مسئله بزرگترین دسته یک گراف بدون جهت G=(V,E) وجود داردکه در آن Vمجموعه گره ها و Eمجموعه یالها هستند. یک دسته یک زیر مجموعه V V از مجموعه گره هاست که در آن برای هر جفت از گره های مشخص در V  یک یال وجود دارد. یعنی برای , .[1]دسته ایی که بیشترین راس داشته باشد به عنوان بزرگترین دسته معرفی می شود شکل 1 یک گراف بزرگترین دسته با اندازه 4 بزرگترین دسته را با اندازه 4 را نمایش می دهد. این مسئله یک مسئله بهینه سازیNP-hard بوده ودر [1] نشان داده شده که اگرP  NP باشد آنگاه هیچ الگوریتمی با زمان چند جمله ای به ازای هر   0 قادر به تقریب دسته ماکزیمم با ضریبی از n1 نیست.[1 ]برای حل دقیق مسئله MCP2 روش هایی مانند الگوریتم های شاخه وقید ارائه شده اند 11].و[12ولی کارایی این روشها محدود به گراف های کوچک و یا گراف های اسپارس می باشد. از این رو الگوریتم های تقریبی زیادی برای حل این مسئله ارائه شده است. از جمله به الگوریتم های ابتکاری پروسیجر جستجو تطبیقی تصادفی حریصانه[2] ، شبکه های عصبی3]و[4 جستجو ممنوعه 5]و[6 و الگوریتم های ژنتیک7]و[8 ارائه شده اند از کاربردهای مربوط به بزرگترین دسته به مواردی نظیر انتخاب پروژه ، دسته بندی ، تحمل نقص، کد گذاری بینایی ماشین، شبکه های مبایل،بازیابی اطلاعات،انتقال سیگنال، وبیوشیمی اشاره کرد.برای یافتن اطلاعات بیشتر درباره کاربردهای مسئله دسته ماکزیمم به 11]و12و13و[14مراجعه کرد.

ادامه مقاله به صورت زیر سازمان داده شد است.در بخش 2 الگوریتم مورچگان معرفی می شود دربخش 3 الگوریتم سیستم کلونی مورچگانی که برای حل این مسئله موجود است شرح می دهیم .در بخش 4 الگوریتم پیشنهادی را برای حل مسئله بزرگترین دسته بیان می کنیم .در بخش 5 نتایج آزمایشی آورده خواهد شد وبخش آخر نتیجه گیری می باشد.

-2 الگوریتم مورچگان
بهینه سازی کلونی مورچگان، یک الگوریتم فرا ابتکاری است که در آن تعدادی مورچه برای یافتن جواب های خوب ،برای مسائل بهینه سازی سخت گسسته با هم همکاری می کنند. همکاری ، جز کلیدی در طراحی برای الگوریتم های ACO3است.مورچه ها به وسیله فرومون با یکدیگر در ارتباط هستند.و جواب های خوب از تعاملهای سازنده و همکاریهای مورچه ها حاصل می شود.[20]
الگوریتم های ACO، می توانند برای حل مسائل بهینه سازی ترکیبی استاتیک و دینامیک به کار روند.در مسائل استاتیک ، ویژگیهای مسئله ،یک بار و برای همیشه تعریف می شود و در حین حل مسئله ،تغییر نمی کند.نمونه ای از این مسائل ، مسئله TSP4است که در آن مکانهای شهرها ، و فاصله های بین آنها ، جزیی از تعریف مسئله است و در زمان اجرا تغییر نمی کند.در مقابل ، در مسائل دینامیک ،ویژگیهای مسئله در زمان اجرا تغییر می کند و الگوریتم های بهینه سازی باید قادر باشد که خود را با تغییرهای محیط ،تطبیق دهد.[20] قبل از بکار گیری الگوریتم ACO باید مسئله مورد مطالعه را به صورت یک گراف G  (C, L) تعریف کرد که در آن Cیک مجموعه متناهی از اجزا و L  C C مجموعه اتصالات بین اجزا است.جواب های بهینه مسئله را می توان به صورت مسیرهای شدنی در گراف G بیان کرد.بنابراین الگوریتم های ACOمی توانندبرای بافتن مسیرهای شدنی با مینیمم هزینه و محددویت مسئله استفاده شود.[20]
در الگوریتم های ACO جمعیت (کلونی ) از عاملها(مورچه ها)به صورت دسته جمعی ، مسئله مورد مطالعه را حل می کنند.اطلاعات جمع آوری شده توسط مورچه در طول فرآیند جستجو متناسب با یال lij در  ij کد می شود.دنباله های فرمون یک حافظه بلند مدت در مورد فرآیند کامل جستجوی مورچه را کد گذاری کرده و به وسیله خود مورچه ها به روزرسانی می شود.مقدار ابتکاری که اغلب اطلاعات ابتکاری نامیده می شود، اطلاعات قبلی در مورد نمونه مسئله یا اطلاعات زمان اجرا را نشان می دهد.در بساری از حالت ها اطلاعات ابتکاری ، یک هزینه یا هزینه تخمینی از اضافه کردن اجزا یا اتصالات به جواب در حال ساخت می باشد.این مقادیر به وسیله قوانین ابتکاری مورچه ها در تصمیم گیری های احتمالی برای حرکت روی گراف، استفاده می شوند.
هر مورچه k از کلونی خصوصیات زیر را دارد:[20]
(1 از گراف G=(C,L) در جستجو برای یافتن جواب های بهینه استفاده می کند.
(2 یک حافظه MK دارد که برای ذخیره اطلاعات در مورد مسیری که تاکنون پیموده است ،استفاده می کند،این حافظه می تواندبرای ساخت جواب های امکان پذیر ،محاسبه مقادیر ابتکاری ، ارزیابی جواب پیدا شده ،ردیابی مسیر به سمت عقب،مورد استفاده قرار می گیرد.
3) با استفاده از یک قانون تصمیم احتمالی ،حرکت مورد نظر را انتخاب می کند.قانون تصمیم تابعی از مسیرهای فرمون محلی در دسترس و مقادیر ابتکاری،حافظه شخصی مورچه که حالت جاری را ذخیره می کندو محدودیت های مسئله می باشد.
(4 زمان اضافه کردن یک جز به حالت جاری می تواند مسیر فرمون  مرتبط با آن یا اتصال متشابه را بروزرسانی کند.
(5 زمانی که به یک جواب رسید ،می تواند مسیر رو به عقب برگردد و مسیر فرمون اجزای موجود به کاررفته در جواب را بروزرسانی کند.

توجه کنیدکه مورچه ها به صورت همزمان و مستقل از هم عمل می کنند و اگر چه عملکرد هر مورچه به اندازه ی کافی برای پیدا کردن یک جواب برای مسئله پیچیده است ،بهترین جواب با کیفیت بالا تنها از طریق تعاملات دسته جمعی و گروهی در میان مورچه ها پدیدار خواهد شد.این تعانلات دسته جمعی از طریق ارتباطات غیر مستقیم میانی توسط خواندن و نوشتن اطلاعاتی که مورچه ها در متغییرهایی که مقادیر مسیر فرمون را ذخیره می کنند،حاصل می شود.[20]

-3 الگوریتم های ACOاولیه و بهبود یافته
اولین بار الگوریتمACO در سال 2003 توسط چریستین سالنون(Christine Solnon )برای حل مسئله بزرگترین دسته بکار گرفته شد.[16] این الگوریتم ابتدا بر روی راس های گراف یک مقدار یکسان فورمون تخصیص می دهد.پس از آن یک مورچه ، یک راس را به صورت تصادفی انتخاب و آن را به عنوان اولین راس دسته خود ذخیره می کند ، سپس بر اساس یک تابع احتمال راس های دیگر را به دسته خود اضافه می کند . این روند ادامه می یابد تا مورچه دسته ایی برای خود پیدا کندزمانی که همه مورچه ها دسته خود را ساختند فقط بهترین مورچه مقداری فورمون به راس های موجود در دسته خود اضافه می کند. این الگوریتم به دلیل اینکه فقط به بهترین مورچه اجازه فرمون ریزی می دهد بنابراین مورچه های دیگر نیز همان جواب بهترین مورچه را پیدا خواهند کرد .
چار چوب کلی الگوریتمACO برای حل مسئله[16] MCPدر شکل 2 بجز خط ii نشان داده شده است. که در شکل1خط 1، یک مقدار ثابت به عنوان فرومون اولیه به راس های گراف تخصیص می دهد. در خط 2 متغیر های m و sbs و maxIteration به ترتیب ، تعداد مورچه ها، بهترین جواب پیدا شده تاکنون وحداکثر تعدادی که حلقه باید تکرار شود مقدار دهی اولیه می شوند. خطوط 3 تا 4 ، تا زمانی که مورچه ها جواب بهینه پیدا نکرده باشند و یا تا زمانی که تعداد تکرار ها کمتر از مقدار maxIteration باشند اجرا می شوند.خطوط b تا c ، m مورچه m تا دسته می سازند ، در خط d ، بهترین جواب siter و si اندازه جواب مورچه i ام ،در خط e بهترین جواب تا کنون sbs مشخص می شود. در خط f فرومون ریزی عمومی روی راس های بهترین دسته پیدا شده توسط بهترین مورچه فراخوانی می شود.
هرچند که الگوریتم ACO ، برای نمونه های آسانی ازMCP راه حل های قابل قبولی پیدا کرده اند اما برای نمونه های بزرگ و سخت تر هنوز نیاز به بهبود دارند.
در سال 2010 الگوریتم ACO توسط شی جان رن ( Shijun (Ren را به نحوی بهبود دادند ، شکل 2، با در نظر گرفتن خط(( ii مرحله بروزرسانی فرمون محلی، که ابتدا فرمون اولیه همه راس های گراف با یک مقدار ماکزیمم و ثابت و برابر مقدار دهی اولیه می کنند.سپس به یک مورچه اجازه می دهند که ابتدا دسته ایی را بسازدوسپس مورچه بلافاصله مقدار فورمون راس های موجود در دسته خود را کم کند خط(.( ii این روند به تعداد مورچه های کلونی تکرار می شود تا همه مورچه ها دسته های را برای خود پیدا کنند. آنگاه فقط بهترین مورچه در هر کلونی اجازه دارد که مقداری فرمون به راس هاس دسته خود اضافه کند. این الگوریتم اگر چه نسبت به الگوریتم ACO نتایج بهتری بدست می آورد اما برای بعضی گراف ها نتایج با جواب بهینه فاصله زیادی دارد. این الگوریتم همانند الگوریتم کلونی قبلی برای یالهای گراف اطلاعات ابتکاری تعریف نکرده اند چون اطلاعات ابتکاری تاثیر بسزایی در تابع احتمال برای انتخاب یک راس توسط مورچه دارد بنابراین پیشنهاد می شودکه برای همه یالهای گراف ، متناسب با اشتراک راس های مجاور دو راس هر یال، اطلاعات ابتکاری تعریف شود .

-4 الگوریتم پیشنهادی

درالگوریتمACOکه درسال2003وACO )2010اولیه و بهبود یافته) برای مسئله MCP ارائه شدتوزیع فورمون نقش اصلی در ایجاد جوابهای یکسان دارند. بنابراین برای تضمین تنوع جواب ها پیشنهاد می شود که اولا اطلاعات ابتکاری برای یالهای گراف طبق رابطه (1)محاسبه شود دوما مورچه های یک کلونی روی راس های متمایز توزیع شوند ، هنگامی که یک مورچه دسته ایی را می سازد بلافاصله مقدار فورمون یالهای دسته خود را کم می کند ، این مقدار فورمون روی یالهای دسته متناسب بااندازه دسته(تعداد راس های دسته) کاهش می دهدتا بقیه مورچه ها در کلونی، برای کشف دسته های جدید به ناحیه های ملاقات نشده هدایت شوند. و هنگامی که همه مورچه ها دسته هایی را برای خود پیدا می کنند فقط بهترین مورچه اجازه فرمون ریزی روی یالهای دسته پیدا شده دارد. در ادامه الگوریتم پیشنهادی شکل 4 را به طور کامل بیان می کنیم :این الگوریتم به تعدادمشخصی تکرار می شود.تا جواب بهینه پیدا شود (1محاسبه اطلاعات ابتکاری
برخلاف الگوریتم ACO سال 2003 و2010 که در الگوریتم اطلاعات ابتکاری یالهای گراف یک مقدار یکسان تعریف کردند در الگوریتم پیشنهادی ، به یالهای گراف عددی متناسب با تعداد راس های مشترک دو راس یک یال و تعداد راس های گراف طبق معادله (1) محاسبه می شود.


که در رابطه (1) ، مجموعه C(i) برابر است با راس های
مجاورa و مجموعه C( j) برابراست با راس های مجاور b و تابع diff تعداد راس های غیر مشترک دو سر یال ij و n تعداد راس های گراف را نشان می دهدو ij مقدار اطلاعات ابتکاری یال ij را مشخص میکند.
بعد از اینکه همه یالهای گراف مقدارابتکاری طبق رابطه 1 در یافت کردند، در هر تکرار m تا مورچه بر روی m تا راس متمایز گراف توزیع می شوند سپس مورچه k ام بر اساس موقعیت خود برای ساخت دسته(شکل (3 اقدام می کند مورچه تمام همسایه های این راس را در یک مجموعه به نام کاندیدا ذخیره می کند.مورچه راس j ام را از مجموعه کاندیدا با احتمالی که در معادله ( 2)تعریف شده انتخاب و به دسته خود اضافه می کند. سپس راس هایی از مجموعه کاندیدا که با راس جدید اضافه شده به دسته ، یال مشترکی ندارند حذف می شوند و مجموعه راس های جدید را در مجموعه کاندیدا ذخیره میکند. این رویه ساخت دسته تا زمانی ادامه می یابد که مجموعه کاندیدا برابر صفر شوند.
احتمال انتخاب هر راس از مجموعه کاندیدا به صورت معادله رابطه((2 در زیر تعریف می شود:

که مقدار فرمون روی یالij و اطلاعات ابتکاری یال ij و اهمیت فرمون و اهمیت اطلاعت ابتکاری را مشخص می کند.رویه ساخت دسته در شکل 4 نمایش داده شده است. توجه در الگوریتم های قبلی تابع احتمال بر اساس فرومون روی راس های گراف ، اما در الگوریتم پیشنهادی تابع احتمال براساس اطلاعات ابتکاری روی یالهای گراف که منجر به تغییر تابع احتمال شکل 3 می شود و تابع احتمال به رابطه 2 تغییر می کند.
هنگامی که یک دسته sk توسط مورچه k ام ساخته می شود، مورچه مقداری فورمون ، طبق معادله (3) از یالهای دسته کم می کند. که اندازه دسته kام و sbs اندازه بهترین مورچه را مشخص می کند.

این مقدار فرومون متناسب با معکوس اندازه دسته ساخته شده توسط مورچه k ام کاهش می یابد.این عمل باعث می شود تا مورچه های دیگر را تشویق کنیم به انتخاب یالهایی که هنوز ملاقات نشده اند تا بتوانند جواب های متنوعی را ایجاد کنند. هنگامی که اندازه دسته ساخته شده توسط مورچه ، بزرگ باشد مقدار فرومون کمتری از یالهای دسته ساخته شده کم می شود و هنگامی که اندازه دسته ساخته