ترکیب الگوریتم بهینه یابی کلونی مورچه و تکنیک برنامه‌نویسی پویا برای حل مسئله فروشنده پوششی

چکیده

کلید واژه ها

1. مقدمه

2. بیان مسئله

3. روش حل

الگوریتم1- چارچوب کلی الگوریتم ACO پیوندی پیشنهادی.

3-1- قالب‌بندی فرومن

3-2- تولید مورچه‌ها و به‌روزرسانی فرومن محلی

3-3- فرآیند اصلاح

3-3-1- اضافه کردن رأس

3-3-2- حذف رأس

3-3-3- انتخاب اکتشافی سه‌تایی

3-3-4- برنامه‌نویسی پویای اکتشافی

الگوریتم2- چارچوب کلی فرآیند اصلاح.

3-4- به‌روزرسانی فرومن جهانی

4. نتایج محاسباتی

شکل 1- مثال نمایشی از فرآیند DP اکتشافی.

جدول 1- مقادیر انتخابی برای پارامترهایACO

جدول 2- مقایسه الگوریتم‌های مختلف برای نمونه‌های با اندازه کوچک.

جدول 3- مقایسه الگوریتم‌های مختلف برای نمونه‌های بااندازه متوسط.

جدول 4- مقایسه الگوریتم‌های مختلف برای نمونه‌های بااندازه بزرگ.

5. نتیجه‌گیری

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

مسئله فروشنده پوششی (CSP)تعمیمی از مسئله فروشنده دوره‌گرداست که در بعضی از رئوس بازدید نشده باقی می‌مانند (کارنت و شیلینگ، 1989). به‌ویژه، هر رأس که i نامیده می‌شود، می‌تواندزیرمجموعه‌ای از رئوس واقع‌شده درون فاصله از پیش تعیین‌شدهri از خود را پوشش دهد. هدف از حل این مسئله ساخت چرخه همیلتونی با طول حداقل روی زیرمجموعه از رئوس است که در آن نیاز است تا رئوس بازدید نشده درون شعاع پوششی از حداقل یک رأس بازدید شده به‌وسیله تور قرار گیرد. نویسندگان به کاربردهای بالقوه این مسئله اشاره دارند که از مسئله برنامه مراقبت‌های بهداشتی نشئت‌گرفته است. در اصل، هدف بازدید از تعداد مشخصی از مناطق موردتقاضا است به‌طوری‌که انسان‌های مقیم در مناطق بازدید نشده مجبور شوند به نزدیک‌ترین منطقه بازدید شده بروند تا توابع همیلتونی را دریافت کنند (کارنت و شیلینگ، 1989). کارنت و شیلینگ (1989) الگوریتم ساده و اکتشافی برای این مسئله ارائه دادند. الگوریتم آن‌ها از دو گام تشکیل‌شده است. در گام اول، یک مسئله پوششی مجموعه (SCP) برای یافتن حداقل تعداد رئوسی که تمام رئوس مسئله را پوشش می‌دهند، حل می‌شود. در گام دوم، تور بهینه TSP روی مجموعه‌ای از رئوس گام اول محاسبه می‌شود. در حالتی که چندین پاسخ بهینه برای SCP داشته باشیم، تمام آن‌ها در گام دوم مورداستفاده قرار می‌گیرند وارزان‌ترین تور TSP انتخاب می‌شود. گلدن، ناجی-عظیمی، رغوان، سالاری و توث (2012) دو الگوریتم جست‌وجوی حلی برای CSP پیشنهاد دادند. الگوریتم‌های پیشنهادی آن‌ها از حرکت‌های زیادی همچون جانشینی، برگشت حذفی و انحراف برای فرار از پاسخ‌های بهینه محلی بهره می‌برند. اولین الگوریتم که با LS1 نشان داده می‌شود، کیفیت پاسخ‌ها را به‌وسیله اجرای مجموعه‌ای از حرکات حذفی و انتقال دوباره بهبود می‌بخشد. در اصل، در خلال گام اول الگوریتم LS1، برخی از رئوس بازدید شده از تور حذف می‌شوند و در گام دوم، پاسخ امکان‌پذیری به‌وسیله جایگزینی رئوس حذف‌شده با ترکیب بهتری از رئوس بازدید نشده (اگر موجود باشد) پیدا می‌شود. الگوریتم دوم که با LS2 نمایش داده می‌شود برای بهبود کیفیت پاسخ‌ها حرکات پیچیده‌تری انجام می‌دهد. به‌ویژه، فرآیندهای حذفی-انتقالی و انحرافی برای رسیدن به این هدف انجام می‌شوند. علاوه بر این، بحث اکتشافی لین-گرنیگهان (لین و کرینگهان، 1973) در خلال این الگوریتم به‌منظور یافتن ترکیب بهتری از رئوس بازدید شده مورداستفاده قرار می‌گیرد. یک الگوریتم اکتشافی بر پایه برنامه‌نویسی صحیح خطی (ILP) برای CSPارائه‌شده است (سالاری و ناجی-عظیمی، 2012). با ارائه یک پاسخ اولیه امکان‌پذیر، به‌منظور اصلاح طول تور این الگوریتم از یک الگوی کلی تخریب و تعمیر پیروی می‌کند. برای انجام این کار برخی از رئوس از تور حذف می‌شوند و دوباره چیده می‌شوند و یک پاسخ امکان‌پذیر جدید را تشکیل می‌دهند که باعث حل یک مدل بر پایه ILPبه‌صورت بهینه می‌شود. نتایج نشان می‌دهد که روش بر پایه ILP مؤثرتر از سایر الگوریتم‌هایCSP موجود است. برخی از محققین روی تغییرهندسی CSPکارکرده‌اند. در این متن، هر همسایگی مجموعه‌ای فشرده در صفحه است به صورتی که با تقسیم مجموعه، تمام تقاضاهایی که در همسایگی آن قرار دارند پوشش داده شوند. تعدادی الگوریتم تقریب نیز برای این مسئله پیشنهادشده است (آرکین و هسین 1995؛ گولزینسکی، هیث و پرایس 2006 و شاتل ورث، گلدن، اسمیت و وسیل 2008 را ببینید). بسیاری از گونه‌های دیگر CSP نیز موردمطالعه قرارگرفته‌اند. مسئله تور پوششی (CTP) توسط گندرو، لاپورته و سیمت (1997) تعریف شده است که در آن مجموعه‌ای از رئوس به سه گروه تقسیم می‌شوند، یعنی رئوسی که باید توسط تور بازدید شوند (S1)، رئوسی که باید پوشش داده شوند (S2) و رئوسی که می‌توانند بازدید یا پوشش داده شوند (S3). سایر فرضیات CTP مشابه با فرضیات ذکرشده برای CSP است.هدف CTP پوشش تمام رئوس S2 با ساخت توری روی تمام رئوس S1 و شاید زیرمجموعه‌ای از رئوس S3 است. گندرو و همکاران (1997) الگوریتم اکتشافی و روش شاخه‌شاخه شدن و بریدن دقیقی پیشنهاد دادند. تعمیمی با چند حامل برای CTP توسط هاچیچا، هاجسون، لاپورته و سیمت (2000) ارائه‌شده است که در آن مجموعه‌ای از حامل‌های قرارگرفته در مرکز انبار را می‌دهیم و هدف این است که یا بازدید صورت گیرد و یا تقاضای تمام رئوس موجود با حداقل هزینه پوشش داده شود. در این مسئله،طبقه‌بندی رئوس همانند CTP است درحالی‌که تنها تفاوت در این است که ما باید تقاضا را با استفاده از بیش از یک حامل پوشش دهیم. گلدن و همکاران (2012) تعمیمی طبیعی برای CSP ارائه دادند که در آن فرض بازدید یا پوشش یک رأس تنها برای یک‌بار تخفیف داده‌شده است. آن‌ها اشاره دارند به برخی کاربردهای نشئت‌گرفته از برنامه بهداشتی مراقبتی روستایی که برای آن ما باید یک رأس را بیشتر از یک‌بار بازدید کنیم یا پوشش دهیم تا تقاضای متناظر با آن ارضا شود. مسئله ستاره حلقوی (RSP) مسئله مرتبط دیگری می‌باشد که در شبکه‌های ارتباطی کاربرد دارد (لابه، لاپورته، مارتین و سالازار گنزالس، 2004). در این مسئله، هر رأس یا توسط تور بازدید می‌شود (متحمل شدن هزینه مسیریابی) و یا به تور اختصاص داده می‌شود (متحمل شدن هزینه تخصیص). هدف کمینه ساختن مجموع هزینه‌های مسیریابی و تخصیص است. همچنین تغییراتی در RSP وجود دارد که مسئله چرخه میانه نامیده می‌شود و در آن کرانه بالایی برای هزینه تخحیص حداکثر وجود دارد (لابه، لاپورته، مارتین و سالازار گنزالس، 2005). مسئله دیگر که بسیار زیاد به CSP مرتبط است مسئله تعمیم‌یافته فروشنده دوره‌گرد است (فیشتی، سالازار گنزالس و توث 1997؛ کاراپتیان و ریحانه 2012). در این مسئله، مجموعه رئوس در دسته‌های گسسته این تقسیم‌بندی می‌شوند. هدف یافتن کوتاه‌ترین تور همیلتونی است که دقیقاً یک رأس از هر دسته را بازدید کند. در حقیقت، مسئله تعمیم‌یافته فروشنده دوره‌گرد حالتی خاصی از CSP است که در آن هر رأس می‌توان تنها توسط رأس‌های دسته‌ای که به آن تعلق دارد پوشانده شود. در این مقاله، الگوریتم اکتشافی و پیوندی جدید و مؤثری برای CSP پیشنهاد داده‌ایم. روش پیشنهادی، بهینه‌سازی کلونی مورچه (ACO) (دوریگو و همکاران 1992؛ دوریگو، مانیزو و کولورنی 1996) و تکنیک برنامه‌نویسی پویا را به‌منظور اصلاح کیفیت پاسخ‌های باهم ترکیب می‌کند. به‌علاوه برای مسئله مطالعه شده فرمول ریاضی با اندازه چندجمله‌ای ارائه داده‌ایم. بقیه مقاله متشکل از موارد زیر است: بخش 2 توضیحاتی تفصیلی در مورد مسئله بیان می‌کند؛ در بخش 3 جزئیات الگوریتم اکتشافی و پیوندی پیشنهادی ارائه می‌گردد؛ در بخش 4، کارایی الگوریتم پیشنهادی به‌واسطه آزمایش‌های کامپیوتری وسیعی مورد ارزیابی قرار می‌گیرد؛ درنهایت در بخش 5 نیز نتیجه‌گیری مقاله را خواهیم داشت.