دانشگاه آزاد اسلامی- واحد مشهد
کلونی مورچگان
(Ant Colony)
استاد راهنما:
جناب آقای مهندس کاظمی
تنظیم کنندگان:
سعیده حدادی - هانیه مستور
تابستان86
Preface:
مساله فروشنده دوره گرد جزء مسائل مشهور و کلاسیک تحقیق در عملیات می باشد . بسیاری از فعالیت های علمی را می توان به صورت مسئله فروشنده دوره گرد در آورد و سپس حل نمود . روشهای بهینه یابی موجود برای حل مسائل سخت ( همچون مسئله فروشنده دوره گرد ) بطور عمده شامل تعداد بسیار زیادی متغیر و محدودیت می باشند که از کارایی عملی آنها در حل مسائل با ابعاد واقعی می کاهد بدین علت در دهه های اخیراستفاده ازالگوریتم های ابتکاری و فوق ابتکاری مورد توجه قرار گرفته است . در این بین الگوریتم های فوق ابتکاری بدلیل ساختار ساده وتوانایی هایی که از خود نشان داده اند مورد استفاده محققین تحقیق در عملیات قرار گرفته است .
در این تحقیق با ترکیب دو الگوریتم کلونی مورچگان و الگوریتم ژنتیک سعی شده است الگوریتم ترکیبی ساخته شود که تور بهتری را برای مسئله فروشنده دوره گرد بدست آورد . پس از طراحی الگوریتم، تنظیم پارامترهای آن با حل مسائل متعدد صورت گرفته است و برای مقایسه روش پیشنهادی با روشهای الگوریتم ژنتیک و مورچگان برخی از مسائل فروشنده دوره گرد موجود در سایت TSP حل شده است . نتایج بدست آمده نشان می دهد که روش ترکیبی پیشنهادی در اغلب مسائل قادر است جواب بهتری بدست آورد.
چکیده :
بهینه یابی کلونی مورچگان یکی از روشهای فرا ابتکاری است که به ساختن جواب مسایل بهینه یابی ترکیبی سخت می پردازد.
که برگرفته از رفتار مورچگان در پیروی از مسیرهای پیموده شده توسط مورچه های قبلی شکل گرفته وبرای یافتن جواب
مسایل بهینه یابی ترکیبی بکار میرود. مسایل بهینه یابی ترکیبی گونه ای از مسایل میباشندکه تعداد جوابهای موجه متناهی
لیکن زیاد دارند وبه صورت طبیعی شمارش همه آنها مقدور و یا به صرفه نیست.
در سالهای اخیر یکی از مهمترین زمینه های تحقیقاتی کشف رو شهای ابتکاری از طبیعت بوده است که از آنها برای بدست
آوردن نتایج خوب در مسایل بهینه سازی ترکیبی استفاده شده است .روش های ابتکاری با انجام چندین تکرار ویا با انجام
میزان مشخصی آزمایش ویا بکارگیری یک یا چندین عامل نظیر عصب ها- کروموزوم ها- مورچه ها ومانند آن بدست می آیند.
مقدمه:
بهینه یابی کلونی مورچگان یکی از روشهای فرا ابتکاری است که با الهام از طبیعت به ساختن جواب مسایل بهینه یابی ترکیبی
سخت می پردازد.
این سیستم اولین بار توسط مارکودوریگو در سال 1991برای حل مسایل مذکور معرفی گردید و اولین کاربرد آن در مورد
شناخته شده ترین مسئله بهینه یابی مسایل ترکیبی یعنی مسئله فروشنده دوره گرد بود.
مشاهده جستجوی مورچگان واقعی جهت یافتن غذا و انتخاب کوتاه ترین مسیر با مشارکت جمعی مورچگان یک کلونی ,
سر منشا پیدایش این روش برای حل مسایل بهینه یا بی ترکیبی بود.مورچه های واقعی قادر به تبادل اطلاعات مربوط به منابع
غذایی ازطریق ماده ای شیمیایی به نام فرمون می باشد.
آنها با به جا گذاشتن فرومون در مسیر ی که طی می کنند باعث میشوند تا دیگر مورچه ها با مشاهده اثرات فرومون بجامانده
در مسیر به آن جذب می شوند و همان راه رابرای رسیدن به منابع غذایی دنبال کنندبا افزایش حرکت مورچه ها در یک مسیر
میزان اثر فرومون افزایش یافته وخود عاملی برای جذب بیشتر مورچه ها به پیمودن این مسیر می گردد.
بیان رفتار مورچه های واقعی می تواند با شبیه سازی مناسب برای حل مسایل بهینه یابی ترکیبی استفاده گردد.سیستم
مورچگان تا کنون برای حل مسایل ترکیبی گوناگونی از جمله مسئله برنامه ریزی کارگاه- مسئله رنگ آمیزی گراف- مسئله کوادراتیک ومسئله مسیریابی وسیله نقلیه به کار رفته است.
در این تحقیق به بیان روش بهینه یابی توسط کلونی مورچگان میپردازیم .ودر ابتدا به ذکر مقدمات و فلسفه به وجود آمدن این روش پرداخته و سپس حالت عمومی آن در حل مسئله TSPبه عنوان عمومی ترین مساله ترکیبی ذکر می شود .
))بهینه یابی توسط کلونی مورچه((
Ant colony optimization(ACO)
مسایل بهینه سازی ترکیبی:
گونه ای از مسایل بهینه سازی هستند که در آن تعداد جواب های موجه تشکیل یک مجموعه متناهی می دهند وهدف بدست آوردن بهترین جواب در مساله است.
پیچیدگی زمانی یک الگوریتم:
هر الگوریتم از یک سری عملیات مقدماتی از جمله ضرب- تقسیم-تخصیص و... تشکیل میشود .پیچیدگی یک الگوریتم به صورت یک چند جمله ای تعریف میشود.با توجه به زمان انجام هر عمل مقدماتی پیچیدگی زمانی الگوریتم در بدترین حالت بدست آمده وملاک قرار می گیرد[ 3]
مسایل P و NP
مسایلی که میتوانند به وسیله الگوریتمی که پیچیدگی زمانی بدترین حالت آن چند جمله ای است،حل شوند را مسایل P
( (polynomialمی نامندو نیز مسایلی وجود دارند که با احتمال بالایی نمی توان الگوریتمی با پیچیدگی زمانی چند جمله ای در بدترین حالت برای آنها بدست آورد،این مسایل را NP(Nodetermiutictic polynomial)می گویند.
با وجود مسایل NP،ضرورت وجود ،روش های ابتکاری و فرا ابتکاری برای حل مسایل نمایان می شود. این روشها را می توان از طرق مختلف بدست آورد.یکی از این طرق،الهام از طبیعت برای خلق این روشهاست.
به طور خلاصه برخی از الگوریتم های بدست آمده از طبیعت به شرح زیر است:
- الگوریتم های ژنتیک
- شبیه سازی آنیلینگ
- نمونه یابی و دسته بندی
- جستجوی ممنوعه
- شبکه های عصبی.شناخته شده ترین مثال که اولین بار توسط (Mc culloch,pitts,1943)پیشنهاد شدوبوسیله هوپ فیلد در سال 1985برای مساله فروشنده دوره گرد ارائه شد.
- سیستم مورچگان(colorni,dorgio,maniezzo,1991).روشی که در سال 1991توسط بعضی نویسندگان مقاله مذکور برای مسئله فروشنده دوره گرد پیشنهاد شد.
سیستم مورچه یکی از جدید ترین هیورستیک هایی است که برای حل مسایل NP ارائه شده است. در این بخش برآنیم تا این روش را شرح داده و رویه آن را مرور کنیم.
سیستم مورچگان(AS):
فلسفه سیستم مورچگان:
قلمرو حیوانات موارد مختلف ومتفاوتی از سیستم های اجتماعی را به نمایش می گذارد.که در مقایسه با رفتارهای جمعی پیچیده،توانایی های فردی ضعیفی دارند.این سیستم ها از باکتری تا مورچه،کرم درختی نرم تن دیگر را شامل میشود.
یکی از بهترین موارد طبیعی مطالعه شده در فعالیت ها ونوآوریهای علمی ،استفاده از کلونی مورچه هاست. [6]
مورچه های واقعی قادر به یافتن کوتاهترین مسیر از منبع غذا تا خانه شان هستندکه اینکار بدون استفاده از حس بشری می باشد.این سؤال مطرح است که چطور حیوانات کور برای ثبت کوتاهترین مسیراز منبع غذا به کلونی خود مدیریت میشوند؟
اثرات فرومون
یک مورچه هنگامی که از محلی به محل دیگر حرکت می کندمقداری فرومون (در مقادیر مختلف)در روی زمین به جای می گذارد.فرومون یک ماده ی شیمیایی است که مورچه ها برای تعیین مسیر سایر مورچگان و همچنین برای تشخیص راه برگشت
خود در مسیر حرکت خود بجای میگذارند.لذا راهی که اینها دنبال کرده اند ،به وسیله اثر این ماده علامت گذاری می شوند.هر چه مورچه بیشتری در یک راه حرکت کند فرومون بیشتری به جای می ماندوهمین عاملی می شود تا تعداد بیشتری مورچه به آن مسیر جذب شوند.لذا احتمال انتخاب یک مسیر توسط مورچه با تعداد مورچه هایی که آن مسیر را انتخاب کرده اند، افزایش می یابند.یک شمای کلی از رفت وآمد مورچه ها از لانه تا منبع غذا در زیر نشان داده شده است [7]
در حالت (a)مورچه ها در مسیرAEدر حال آمدوشد می باشند.سپس با قرار دادن یک مانع بر سر راه AEعملا دوراه از سمت چپ وراست مانع ایجاد میشود که می دانیم مسیر سمت راست کوتاهتر است.با احتمال یکسان وبرابر 50% برخی از سمت راست وبرخی از سمت چپ حرکت می کنند. ازآنجا که مسیر سمت راست کوتاهتر است مورچه هایی که از آن سمت حرکت میکنند زودتر به E میرسندولذا در زمان ثابت تعداد بیشتری در مسیر سمت راست حرکت کرده اند بنابراین فرومون بجای مانده در این مسیر بیشتر است واین خود بیشتر باعث جذب مورچه می شود. در این راستا فرآیند جستجوی غذا توسط مورچگان را شبیه سازی کرده اند.مشابه این نگرش (Ant colony )نیز برای حل مسایل بهینه سازی مورد استفاده قرار گرفته است.در آزمایشی که توسط گاس و همکاران وی انجام شد، با ایجاد دو مانع بین مبدا ومقصد مورچه ها به مشاهده وسپس شبیه سازی رفتار مورچه ها اقدام شد. [11]
بدین صورت بود که اولین مورچه هایی که به منبع غذا می رسیدندآنهایی بودند که هردو مسیر کوتاه را برگزیده بودند .بنابراین
وقتی این مورچه ها سفر برگشت خود را شروع می کردندفرومون بیشتری در شاخه کوتاهتر برجای می ماند ولذا در نهایت حدود 90% مورچه ها از مسیر کوتاهتر به مقصد خود می زسیدند وآن را انتخاب میکردند.
یک اثبات رسمی از چگونگی یافتن کوتاه ترین مسیر به وسیله فرومون در موارد عمومی توسط بروکستین و همکارانش ارائه شده است که این رفتار یک خاصیت ضروری کلونی می باشداین جالب است که بدانیم مورچه ها می توانند این رفتار مشخص را با بکار گیری یک شکل ساده از ارتباط غیر مستقیم که براساس به جای ماندن فرومون صورت می پذیرد وبه نام
(stigmergy) شناخته می شود،انجام دهند.
بکارگیری سیستم مورچگان:
اولین بار الگوریتم مورچگان توسط مارکودوریگو وهمکاران به عنوان یک نگرش با چندین عامل برای حل مسایل بهینه سازی ترکیبی مشکل مانند مسئله فروشنده دوره گرد(TSP)و مسئله تخصیص کوادراتیک(QAP)پیشنهادوارائه شد.
در حال حاضر فعالیت های بیشماری در جوامع علمی برای بسط کاربرد های این الگوریتم که بر اساس فلسفه سیستم مورچگان است انجام می شود.این الگوریتم ها نگرش هایی بر پایه جمعیت هستند که در مسایل مختلف بهینه سازی ترکیبی
NP-hard کاربرد دارند. [9]
نگرش بهینه یابی توسط کلونی مورچه
در روش فرا ابتکاری بهینه یابی توسط کلونی مورچه (ACO)،یک کلونی شامل مورچگان مصنوعی در یافتن جواب های خوب در مسایل بهینه سازی مشارکت می کنند.این مشارکت کلید طراحی الگوریتم های ACO است ومورچگان مصنوعی نقش اول را بازی می کنند.
شباهت ها و تفاوت ها با مورچه های واقعی:
بیشترین ایده ACO از مورچه های واقعی گرفته شده است . این موارد استفاده شامل موارد زیر است:
1-یک کلونی شامل افراد همکار و مشارکت جو است.
2-اثر فرومون برای ایجاد ارتباط محلی استیگمرجی وجود دارد.
3-ترتیبی از حرکت های محلی برای پیدا کردن کوتاهترین راهها وجود دارد.
1-کلونی موجودات مشارکت جو:
همانند کلونی واقعی مورچه ،الگوریتم های مورچگان مرکب از یک جمعیت یا کلونی می باشند که هر یک از اجزا برای یافتن جواب بهینه همکاری می کنند. اگر چه پیچیدگی هر مورچه مصنوعی آن چنان است که میتواند یک جواب قابل قبول بسازد
(مانند مورچگان واقعی که می توانند یک راه بین محل زندگی خود وغذا پیدا کنند) اما جواب های با کیفیت نتیجه مشارکت و همکاری میان افراد تمام کلونی است. [5]
2- اثر فرومون و استیگمرجی
مورچگان مصنوعی نیز مانند مورچگان واقعی محیط خود را اصلاح میکنند.درحالی که مورچگان واقعی با به جای گذاردن یک ماده شیمیایی مسیر خود را مشخص می کنند.مورچگان مصنوعی نیز اطلاعات عددی خودرا براساس حالت هایی که مشاهده
کرده اند،تغییر میدهند.این اطلاعات عددی را اثر فرومون می نامیم.در الگوریتم ACO اثرات فرومون مسیر تنها کانال ارتباطی بین مورچگان است.همچنین در الگوریتم ACO یک مکانیزم تبخیر ،مشابه تبخیر واقعی فرومون،اطلاعات فرومون را در زمان اصلاح میکند.تبخیر فرومون به مورچه اجازه می دهد تا کم کم تاریخ گذشته اش را فراموش کند تا بتواند مسیرهای جدید را نیز بیابد.
3-یافتن کوتاهترین راه حرکت های محلی
مورچه های واقعی ومصنوعی فعالیت مشترکی را انجام می دهند:پیدا کردن کوتاهترین (کم هزینه ترین) راه که یک منبع (کلونی)را به مقصد وصل کند. مورچگان مصنوعی نیز مانند مورچگان حقیقی با حرکت مرحله به مرحله جواب را می یابند.
همچنین مورچگان مصنوعی بعضی خصوصیاتی دارند که در مورچه های واقعی یافت نمی شوند:
- مورچه های مصنوعی در یک دنیای مجرد زندگی می کنند وحرکت هایشان شامل انتقالاتی از حالت های مجزا به حالت های مجزای دیگر است.
- مورچه های مصنوعی دارای حافظه اند.این خاصیت باعث نگهداری اطلاعات گذشته مورچه در حافظه می شود.
- مورچه های مصنوعی مقداری فرومون از خود به جای می گذارند که تابعی از کیفیت جواب یافته شده است.
- مورچه های مصنوعی اثرات فرومون را تنها بعد از تولید یک جواب بهنگام میکنند.
- برای اصلاح کارایی سیتم الگوریتم های ACO میتوانند با توانایی فوق العاده ای مانند بهینه سازی محلی تجهیز شوند که این امر در مورچه های واقعی یافت نمی شود.در خیلی از اجراها ،مورچه ها با رویه های بهینه سازی محلی پیوند زده می شوند.
بهینه یابی توسط کلونی مورچه(ACO)
درحال حاضر موارد موفق زیادی از اجرای ACO در حل تعدادی از مسایل بهینه سازی ترکیبی وجود دارد از جمله این مسایل، مسئله مسیر یابی وسیله نقلیه (VRP) است که با استفاده از این روش میتوان به حل آن پرداخت برای توضیح این روش ورونداجرای آن، ابتدایی ترین راه توضیح چگونگی انجام آن در یک مسئله فروشنده دوره گرد است. [4]
الف - تعریف مسئله فروشنده دوره گرد(TSP)
TSP مسئله یک فروشنده دوره گرد است که می خواهد مشریان خود در شهرهای مجاور را ملاقات کند وبه شهرخود باز گردد.در این میان می خواهد کوتاهترین مسیر ممکن را برای این کار انتخاب نماید.
این مسئله به صورت یک گرافG(N,A) نشان داده می شود که N مجموعه گره ها(نشان دهنده شهرها) میباشد و A
مجموعه کمان هاست که Nگره رابهم متصل می کند.به هر کمان یک ارزش d اختصاص داده میشود که طول کمان(i,j )
متعلق به Aاست را نمایش میدهد. به بیان دیگر این مسئله پیدا کردن طول دایره هامیلتونی از یک گراف است.
TSPدو حالت متقارن ونامتقارن دارد در حالت متقارن طول رفت وبرگشت در یک کمان مساوی است ومیتوان از iبهjرفت واز jبهiرفت وارزشها برابر میشوند اما در نامتقارن ارزشها برابر نیست. [2]
الگوریتم های ACO موجود برای TSP
در الگوریتم های ACO مورچه ها نماینده های ساده ای هستند که در مورد TSP تورها را بوسیله حرکت از شهری به شهر دیگر می سازند.ساختن جواب توسط مورچه ها به وسیله اثرات فرومون واطلاعات ابتکاری که از سابقه مسئله بدست می آید صورت می گیرد. هنگام کاربرد ACO برای TSP ،مقدار شدت فرومون با هر کمان ارتباط دارد که در هنگام اجرای الگوریتم بهنگام می شود وt شمارنده تکرار این اجراست.در کلونی مورچه ما m مورچه قرار دارند. در ابتدا هر یک از m در یک شهر به طور تصادفی انتخاب شده قرار میگیرند.هر مورچه یک تور کامل شامل سفر از شهری که در آن قرار گرفته به تمامی شهرهای موجود وسپس بازگشت به شهر خویش را به صورت زیر می سازد:
یک مورچه که در شهر i قرار دارد شهر j را که هنوز ندیده به صورت احتمالی انتخاب می کند.این احتمال از دو مورد یکی
(شدت فرومون)ودیگری اطلاعات ابتکاری (هیورستیک)موجود،(که تابعی از فاصله شهر iاز j است) اثر می پذیرد.بعد از آنکه تمام مورچه ها یک تور کامل ساختند،اثر فرومون ها بهنگام (update ) می شود.بهنگام کردن به این شکل انجام می گیرد که آن کمان هایی که در تورهای کوتاهتری جای دارند ویا بوسیله مورچه های بیشتری دیده شده اند ، مقدار فرومون بیشتری جذب کرده ولذا با احتمال بالاتری در تکرارهای الگوریتم انتخاب می شوند. [8]
ساده ترین حالت الگوریتم کلونی مورچه برای TSP
به منظور رفع کردن این محدودیت که یک مورچه تمام شهرها (nشهر) را برای یکبار ببیند ما به هر مورچه یک ساختار اطلاعاتی پیوند می زنیم که « لیست ممنوعه» نام دارد دراین لیست شهرهایی که تا لحظه t دیده شده است ،ضبط شده ،دیدن دوباره آن قبل از تمام شدن یک سیکل(تور) برای مورچه قدغن است.وقتی یک سیکل (تکرار ) کامل شده ،لیست ممنوعه(tabu list )خالی می شود ومورچه دوباره آزاد است که هر راهی (هر شهری) که میخواهد را انتخاب نماید.
به طور عمومی اکثر الگوریتم های ACOبرای TSP یک شمای الگوریتم مشخص را دنبال می کنند.این الگو در زیر بیان شده: [17]
- شروع
- پارامترها را تخصیص داده، اثرات فرومون را تخصیص دهید.
- تا وقتی عاملی باعث توفق نشده ادامه دهید.
- جواب هارا بسازید (تورها را بسازید)
- جستجوی محلی انجام دهید.
- اثرات فرومون را بهنگام کنید.
- پایان حلقه
- پایان
الگوریتم ACS (Ant colony system)
برای حل مسایل بزرگتر ومشکل تر سیستم کلونی مورچه (ACS) معرفی گردید؛ [gambardella,dorigo,1995,1997] و در ACS سه دیدگاه مطرح است:
- در ACS دستور تحویل وضعیت یک راه مستقیم برای بالانس بین جستجوی کمان های جدید واطلاعات گذشته (باقیمانده از اثر فرومون) مهیا می کند ودستور انتخاب احتمال آن مهاجمانه تر وفعال تر از AS است.
- دستور بهنگام کردن عمومی تنها برای کمانهایی که به بهترین تور مورچه تعلق دارد،به کار رفته میشود.
- هنگامی که مورچه ها یک جواب می سازند ، دستور بهنگام کردن محلی به کار می رود یعنی مقداری از فرومون آن کمان را پاک می کنند.
با مروری دوباره به اصول اساسی ACO وحالت کلی مسئله همانطور که قبل اشاره شد،داریم:
ویژگیهای متمایز ACS
الف-دستور تحویل وضعیت:
در ACS دستور تحویل وضعیت به صورت زیر می باشد : [14]
یک مورچه در گره r شهر s را انتخاب میکند تا به سمت آن حرکت نماید، این کار بر اساس فرمول زیر انجام میگیرید:
نمای عمومی از الگوریتم ACS به شکل زیر است :
- شروع
- حلقه(در این سطح هر حلقه یک تکرار نامیده میشود)
- هر مورچه در یک گره شروع قرار دارد
- حلقه(در این سطح هر حلقه یک مرحله نامیده میشود)
هر مورچه یک دستور تحول وضعیت را برای ساختن یک
جواب وبهنگام کردن فرومون محلی به کار میبرد.
- تا تمام مورچه ها یک جواب کامل بسازند(حلقه داخلی اجرا شود)
- تا شرط پایان حلقه بیرونی حاصل شود.
- پایان
ب- دستور بهنگام کردن عمومی ACS
در ACS تنها بهترین مورچه (یعنی مورچه ای کوتاهترین تور را می سازد.) اجازه دارد تا در مسیر ،ازخود فرومون به جای گذارد.مورچه ها در یک همسایگی بهترین تور پیدا شده در تکرار جاری جستجو می کنند.بعد از آنکه تمام مورچه ها تورشان را کامل کردندبهنگام کردن عمومی صورت می گیرد سطح فرومون به وسیله به کارگیری دستور بهنگام کردن عمومی بهنگام میشود بهترین تور عمومی ، بهترین توری است که از ابتدای حل حاصل شده است : [15]
بهنگام کردن عمومی متمایل به تخصیص فرومون بیشتر به تورهای کوتاهتر است .معادله قبلی این امر را دیکته میکند که تنها آن کمانهایی که بهترین تور عمومی تعلق دارند،این تجدید قوا را دریافت می کنند.
آزمایش دیگری که انجام شد بکارگیری دستور بهنگام کردن در بهترین تکرار بود(1)
همکاری میان مورچه ها:
با مقایسه دو حالت که در آنها مورچه ها به وسیله تبادل اطلاعات از طریق فرومون همکاری میکنندحالتی که مورچه ها نسبت به فرومون بی تفاوت هستند به طور تجربی دریافت شد که ACS به طور خیلی جدی به همکاری براساس فرومون وابسته است.
در این آزمایش که با قرار دادن سطح اولیه فرومون برای تمام کمانها انجام شد یک کلونی از مورجه هایی که با یکدیگر همکاری میکردند باکلونی که همکاری نمی کردند مقایسه ای انجام گرفت.
این مقایسه بر اساس زمان پردازش که برای محاسبه لازم است ،انجام گرفت در هر مورد آزمایش m=4 بود.
در آزمایش اول الگوریتم 1000 بار اجرا شد که ما بر روی نمودار توزیع احتمال با زمان پردازش مورد نیاز را گزارش کرده ایم شکل زیر نشان می دهد که همکاری به طور خیلی زیادی احتمال یافتن سریع یک جواب بهینه را بهبود می بخشد. [13]
در آزمایش دوم با تعداد 4 مورچه بعداز سیصد هزارم ثانیه مورچه هایی که همکاری می کردند جواب بهینه را می یافتند در حالی که مورچه هایی که همکاری نمی کردند بعد از هشتصد هزارم ثانیه جواب بهینه را پیدا می کردند. [14]
ب-مسأله مسیر یابی وسیله نقلیه
مسأله مسیر یابی وسیله نقلیه یکی از مفاهیم آشنا در زمینه تحقیق در عملیات می باشد که طی دو دهه اخیر تلاشها وبه تبع آن پیشرفتهای عظیمی در این زمینه انجام گرفته است .
مسأله مسیر یابی وسیله نقلیه(VRP) به مجموعه ای از مسایل اطلاق می شود که در ناوگانی متشکل از چندین وسیله نقلیه از یک یا چند قرارگاه به ارائه خدمت به مشتریان مستقر در نقاط مختلف جغرافیایی،می پردازدواین امر را به نحوی انجام می دهند که هزینه های انجام این کار به حداقل برسد .وسایل نقلیه با شروع از قرارگاههای مرکزی پس از ارائه خدمت به مشتریان به قرارگاه بر می گردند.هر وسیله دارای ظرفیت معینی است وحداکثر زمان در دسترس برای طی مسیر وارائه خدمت مشخص می باشد وجود ظرفیت ،حداکثر زمان ارائه خدمت ،نوع خدمت از جمله توزیع یا جمع آوری ،تنوع وسایل نقلیه و... همه وهمه می توانند بر پیچیدگی مسئله بیفزایند. [5]
کاربرد ACO در مسیر یابی وسیله نقلیه (VRP)
مسیر یابی وسیله نقلیه VRP
در این مسأله یک انبار مرکزی داریم و میخواهیم تقاضاهایی رادر شهرهای مختلف برآورده سازیم .در این میان از یک سری وسیله نقلیه با ظرفیت محدود Q استفاده میکنیم تا تقاضای هر مشتری را برآورده سازیم .
این مسئله به صورت زیر نشان میدهند:
VRP وtsp تقریبا با هم مرتبط اند به محض آنکه هر یک از مشتریان VRp به وسایل نقلیه تخصیص داده شوند،VRPبه چندین TSPتبدیل می شود.بدین لحاظ نگرش های موجود در مسئه VRPبه طور عمیقی از الگوریتم ASدرTSPمتأثر میشود.
به کارگیری ACO در VRP
فعالیت های انجام شده در این زمینه در چند مقاله وبا بکارگیری روشهای مختلف انجام یافته است.ابتدادر سال 1997 در مقاله ای تحت عنوان «کاربرد سیستم مورچگان در مسئله مسیر یابی وسیله نقلیه»توسط بالهمبر،هارتل واشتراوس در دومین کنفرانس بین المللی روشهای فرا ابتکاری در فرانسه ارائه گردید که با کاربرد برخی استراتژی های مناسب به بهبود الگوریتم اولیه AS پرداخته بود.
در سال 1999،گامبردلا،تیلارد و اگازی مقاله ای ارائه نمودند که طی آن با استفاده از الگوریتم ACO به مواجهه با این مسئله VRPپرداختند.حالت کلی وروند اجرایی این الگوریتم به صورت زیر است: [11]
با اتمام یک دور از اجرای الگوریتم وپایان عملیات هر یک از مورچه ها ،که به صورت جدا ومستقل از هم انجام میگیرد بنا به استراتژی موجود، بهنگام رسانی فرومون مسیر صورت می گیرد وبا اصلاح پارامترها دور جدید آغاز می شوذ.
به واسطه ماهیت الگوریتم مورچگان که الگوریتمی سازنده می باشد(با وجود حالتی که نظر به گذشته داشته وحالتی تکراری وتکرار پذیر را دنبال می کند ورفتاری یادگیرانه دارد.)استفاده از الگوریتمی که بهبود دهنده می باشد نیز ضروری است .بدین جهت در هنگام یافتن جواب های اولیه توسط مورچه ها وقبل از عملیات بهنگام سازی، عملیات بهبود مسیر با استفاده از یکی از ابزارهایو الگوریتم های بهبود انجام می پذیرد.
بکارگیری AS
