بخشی از مقاله
چکیده
در این مقاله یک الگوریتم فرا ابتکاری جدید را برای حل مسئله فروشنده دوره گرد پیشنهاد میکنیم. مسئله فروشنده دوره گرد یکی از پر کاربردترین مسائل هوش مصنوعی میباشدکه شهرت بسیار زیاد آن به دلیل کاربردهای وسیع و گسترده آن میباشد. راه حلهای متعددی برای حل این مسئله پیشنهاد شده است که هر کدام آن ها معایب و مزیت هایی دارا می باشند. تا کنون الگوریتم ژنتیک و بهینه سازی کلونی مورچگان نتایج بهتری را برای حل این مسئله نسبت به الگوریتم های دیگر نشان دادهاند.این الگوریتم جدید، الگوریتم ژنتیک و سیستم مورچگان را با هم ترکیب می کند تا شانس بهتری را در رسیدن به راه حل های بهینه سراسری فراهم کند. ما این الگوریتم را با زبان برنامه نویسی متلب پیاده سازی کرده ایم و سپس با استفاده از داده های استاندارد TSPLIB ارزیابی کرده و نتایجی بدست آمده است. نتایج حاصل نشان می دهد که الگوریتم ترکیبی در پیدا کردن راه حلهای بهینه سراسری توانایی و پایداری قابل توجهی دارد.
واژگان کلیدی: الگوریتم ژنتیک، الگوریتم بهینه سازی کلونی مورچگان، سیستم مورچگان، مسئله فروشنده دوره گرد
مقدمه
مسئله فروشنده دوره گرد - Lawer, E. L et al, 1992 - یکی ازمسائل بهینه سازی ترکیبی است که در دسته مسائل NP کامل قرار دارد بنابراین نمی توان برای آن الگوریتمی یافت که در زمان چند جمله ای مسئله را به طور قطعی حل کند در نتیجه باید از الگوریتم های فرا ابتکاری برای حل این نوع مسائل استفاده کرد . تعریف مسئله بدین صورت میباشد که در محدوده جغرافیایی فروشنده دورهگرد، تعدادی شهر وجود دارد که بین هر دو شهر یک مسیر باید وجود داشته باشد و فاصله بین هر زوج از شهرها مشخص و عددی ثابت است. قرار است که فروشنده از یکی از شهرها شروع کرده و از همه آنها فقط یک بار عبور کرده و در نهایت به شهر مبدأ باز گردد.
هدف این مسئله، پیدا کردن ترتیبی از شهرها است که مجموع مسافت طی شده حداقل باشد . - Flood, M. M. 1955 - با توجه به کاربردهای وسیع و گسترده مسئله فروشنده دوره گرد، در دو دهه اخیر روشهای مختلفی برای حل آن ارائه شده است. از قبیل: شبکه های عصبی - Takahashi, Y. 1998 - ، تبرید شبیه سازی شده - Kirkpatric, S et al, 1983 - ، الگوریتم ژنتیک - Albayrak, M. and Allahverdi, N, 2011 - ، الگوریتم بهینه سازی کلونی مورچگان . - Dorigo, M, and Gambardella, L. M, 1997a - از میان این روش ها الگوریتم ژنتیک و الگوریتم بهینه سازی کلونی مورچگان تا کنون جواب های نسبتا بهینه ای را پیدا کرده اند.
الگوریتم ژنتیک یک تکنیک جستجوی تصادفی براساس فرضیه سیر تکامل انسان می باشد. هدف های متفاوتی باعث رشد الگوریتم های ژنتیک در دو دهه اخیر شده است. الگوریتم های ژنتیک در حقیقت تکنیک های جستجوی تصادفی هستند که به مکانیزم طبیعی و قوانین ژنتیکی ترکیب و جهش بستگی دارند. الگوریتم های ژنتیک با مجموعه اولیه ای از راه حل های تصادفی که جمعیت اولیه نامیده می شوند شروع می شود . هر عضو جمعیت یک کروموزوم است که به صورت رشته ای از ژن ها کد گذاری می شوند. کروموزوم ها طی چند دوره مکرر تکامل می یابند و یک نسل را بوجود می آورند. در هر دوره جمعیت تغییر می کند و نسل جدیدی ایجاد می گردد که از نظر نزدیکی به جواب بهینه از جمعیت قبلی قویتر است.
الگوریتم بهینه سازی کلونی مورچگان، یک سیستم چند عاملی الهام شده بوسیله رفتار جستجویی بعضی از انواع مورچه ها است. در بهینه سازی کلونی مورچگان، یک تعدادی از مورچه های مصنوعی راه حل هایی را برای مسئله بهینه سازی مطرح شده می سازند و اطلاعات را مبنی بر کیفیت این راه حل ها بوسیله یک طرح ارتباطی تغییر می دهند، مثل اینکه بوسیله مورچه های واقعی این کار ا نجام شده است. الگوریتم بهینهسازی کولونی مورچگان برای حل مسئله فروشنده دوره گرد به صورت زیر عمل میکند :ابتدا باید m مورچه را در n شهر به طور تصادفی قرار دهیم. به تمام مسیرها به مقدار یکسان فرمون اولیه نسبت دهیم.
مورچهها برای دستیابی به یک راه حل بین گرهها حرکت میکنند. در مسیر حرکت ماده ای به نام فرمون - pheromone - را بر جای میگذارند تا بعضی از مسیر های مطلوب علامت گذاری شوند و بوسیله اعضای دیگر کولونی دنبال شوند. فرمونهای به جا مانده در مسیر با نرخ ثابتی تبخیر میشوند و مورچه های دیگر را به سمت خود جذب میکنند. به طور همزمان تعداد زیادی از مورچهها به این کار پرداخته و مسیرهای مختلف را آزمایش میکنند. حرکت مورچه از گره i به گره j با توجه به یک مکانیزم احتمالی صورت میگیرد. با تکرار چند حرکت پیاپی یک دور مورچه کامل میشود و در هر دور، یک راه حل و با اتمام دور هر m مورچه تعدادی راه حل توسط مورچهها ساخته میشود و سپس برای تکرار بعدی مقدار فرمون ها بروز رسانی میشوند.
در این مقاله، ترکیب الگوریتم ژنتیک و بهینه سازی کلونی مورچگان برای حل مسئله فروشنده دوره گرد پیشنهاد می کنیم. در این الگوریتم ترکیبی ابتدا جمعیت اولیه الگوریتم ژنتیک از اولین راه حل ها در الگوریتم بهینه سازی مورچگان ایجاد می شود و سپس هر دو الگوریتم به طور همزمان اجرا می شوند و از راه حل های بدست آمده بهترین راه حل انتخاب شده و در تکرار بعدی در هر دو الگوریتم استفاده می شود.به طور خلاصه در این مقاله در بخش 2 به مروری کوتاه از الگوریتم ژنتیک می پردازیم، در بخش 3 الگوریتم سیستم مورچگان را توضیح می دهیم، در بخش 4 الگوریتم ترکیبی پیشنهاد شده را توضیح داده و در بخش آخر نتایج حاصل از الگوریتم پیشنهادی روی داده های استاندارد TSPLIB را نشان می دهیم.
-1 الگوریتم ژنتیک
در این قسمت به مفاهیم پایه ای الگوریتم ژنتیک می پردازیم. الگوریتم ژنتیک برای اولین بار در سال 1975 توسط جان هالند براساس تئوری تکامل داروین پیشنهاد شد - Holland, J. H, 1975 - ، مراحل الگوریتم ژنتیک به طور خلاصه به صورت زیر می باشد:
-1 با توجه به نوع مسئله و ساختار پاسخهای قابلقبول برای آن، ساختار کروموزومها را مشخص میسازیم.
-2 تابع ارزیابی مناسبی جهت ارزیابی کروموزومها طراحی میکنیم. این مرحله اهمیت بسیار زیادی دارد زیرا اگر نتوان تابعی مناسب جهت ارزیابی کروموزومهای تولیدشده در نسلهای مختلف طراحی کرد، به هیچوجه نمیتوان مسئله مورد نظر را با استفاده از الگوریتم ژنتیک حل کرد.
-3 مقادیر پارامترهای اولیه الگوریتم را با توجه به صورت مسئله تعیین میکنیم. مهمترین پارامترهای مورد استفاده عبارتند از: اندازه جمعیت اولیه - N - ، احتمال انتخاب - PS - ، احتمال ترکیب - PC - ، احتمال جهش - PM - ، نوع عملگر انتخاب، نوع عملگر ترکیب و نوع عملگر جهش، میباشند.
-4 یک جمعیت تصادفی با N کروموزوم تولید میشود، N اندازه جمعیت یا تعداد اعضای نسل آغازین بوده و هر کروموزوم نماینده یک جواب برای مسئله است.
-5 با استفاده از تابع ارزیابی، کیفیت تمام کروموزومهای نسل را محاسبه کرده و ذخیره مینماییم.
-6 با توجه به مقدار کمیت درصد انتخاب - PS - ، جفت کروموزومهایی را به عنوان والدها انتخاب میکنیم.
-7 هر جفت از والدها، با توجه به مقدار احتمال ترکیب - PC - ، با یکدیگر ترکیبشده و یک یا دو کروموزوم فرزند تولید میکنند.
-8 هر کروموزوم فرزند، با توجه به مقدار احتمال جهش - PM - ، جهش مییابد.
-9 تعدادی از فرزندان برای جایگزین شدن در نسل جدید انتخابشده و مابقی نسل جدید از کروموزومهای نسل قبلی انتخاب میگردند، سپس نسل جدید به جای نسل قبلی در برنامه جایگزین میشود.
-10 شرط توقف و خاتمه الگوریتم و همگرایی کروموزومها به پاسخ بهینه، بررسی میشود. در صورتی که شرط توقف برقرار نشده باشد، اجرای الگوریتم را از مرحله 5 از سر میگیریم، در غیر این صورت بهترین کروموزوم نسل فعلی به عنوان پاسخ نهایی انتخابشده و الگوریتم خاتمه مییابد.الگوریتم های ژنتیک با توجه به نوع عملگرهای انتخاب، ترکیب و جهش به کار رفته با یکدیگر متفاوت هستند. در الگوریتم ترکیبی از عملگر انتخاب چرخ رولت - Baker, J . E, 1985 - ، عملگر ترکیب تک نقطه ای - pilat, M. L., and White, T, 2002 - و عملگر جهش جابجایی - Banzhaf, W, 1990 - ، استفاده کرده ایم.
-2 الگوریتم سیستم مورچگان
الگوریتم بهینه سازی کلونی مورچگان در سال 1991 توسط دوریگو و کلورینی برای حل مسائل با قابلیت تفکیک پذیری پیشنهاد شد - Dorigo, M., et al, 1991a - ، الگوریتم های بهینه سازی کلونی مورچگان به ترتیب وقوع می تواند به سیستم مورچگان - AS - ، سیستم ماکس ومین مورچگان - MMAS - ، سیستم کلونی مورچگان - ACS - ، طبقه بندی شود. تفاوت اصلی این الگوریتم ها مبنی بر نحوه بروز رسانی فرمون ها و مکانیزم احتمالی انتخاب شهر بعدی می باشد. سیستم مورچگان، اولین
