مساله معروف فروشنده دوره گرد کاربردهای فراوانی در توالی عملیات و زمان بندی دارد . الگوریتم های ابتکاری تعویض شاخه از جمله الگوریتمهای ابتکاری سریعی است که هنوز هم جهت بدست آوردن حل نزدیک به بهینه مساله متقارن فروشنده دوره گرد از آن استفاده می شود. در این مقاله روش جدیدی برای انتخاب شاخه ارائه شده که زمان محاسباتی الگوریتمهای تعویض شاخه را به یک سوم زمان مورد نیاز کاهش می دهد بدون آنکه از کیفیت حل مساله بکاهد .
مقدمه
مساله معروف فروشنده دوره گرد عبارت از پیدا کردن مسیری است که فروشنده دوره گرد از یک شهر شروع کند و از شهرهای باقی مانده فقط یکبار بگذرد و دوباره به شهر مبدا برگردد. مسیر بهینه ، مسیری است که کل مسافت طی شده یا هزینه سفر آن حداقل باشد . اگر فاصله یا هزینه سفر از شهر i به j برابر با فاصله یا هزینه سفر از شهر j به i باشد مساله را متقارن (SYMMETRIC) و در غیر این صورت نامتقارن (ASYMMETRIC) نامند .در یک مساله فروشنده دوره گرد با بعد n ( تعداد شهرها ) در حالت متقارن ۲/ !(۱-n) و درحالت غیر متقارن !(۱-n) مسیر وجود دارد .
بدلیل کاربردهای فراوان این مساله (بعنوان مساله بهینه سازی ترکیبی (Combinatorial Optmization problem) توجه محققین از چند دهه قبل به ا رائه راه حل هایی برای این مساله معطوف گشته است . حتی در سال ۱۹۹۵ نیز کتابی شامل خلاصه ای از گزارشات مقالات در زمینه فرموله کردن ، پیچیدگی های مساله ، روشهای توسعه داده شده برای بدست آوردن یک پاسخ خوب و پاسخ بهینه چاپ شده است [۸] . بطور کلی روشهای حل مساله فروشنده دوره گرد به دو دسته روشهای دقیق (EXACT) و روشهای ابتکاری (HEURISTIC) تقسیم می شود.
در روشهای دقیق مسیر بهینه ، ولی در روشهای ابتکاری ، مسیرهای نزدیک به بهینه یا بهینه بدست می آید . بدست آوردن پاسخ بهینه از طریق روشهای دقیق وقتی که بعد مساله افزایش می یابد ، با وجود توسعه کامپیوترها هنوز هم مشکل و مستلزم بکارگیری وقت زیادی از کامپیوتر است. بنابراین استفاده از الگوریتمهای ابتکاری (بخصوص با افزایش بعد مساله) که مسیرهای خیلی نزدیک به بهینه ایجاد می کنند و سرعت آنها نیز نسبت به روشهای دقیق بسیار کمتر می باشد ، هنوز معتبر است .
در این مقاله روش جدیدی برای سرعت دادن به عملیات محاسباتی الگوریتمهای ابتکاری تعویض شاخه که از روشهای خوب برای حل مساله متقارن فروشنده دوره گرد می باشد ، ارائه می شود و میزان تاثیر آن در کیفیت این حل و نیز کاهش زمان محاسباتی با روشی مشابه سنجیده می شود .
۱- روش های حل مساله
روش های حل مساله فروشنده دوره گرد به دو دسته تقسیم می شود :
الف – روش دقیق (EXACT)
در این روش محاسبات در صورتی متوقف می شود که مسیر بهینه بدست آمده باشد ]۱[.
الگوریتمهای دقیق عبارتند از :
الف ) برنامه ریزی پویا (Dynamic Programming)
ب ) برنامه ریزی عدد صحیح (Integer Programming) و انشعاب و تحدید
(Branch and Bound)
ب – روش ا بتکاری (HEURISTIC)
روشهای ابتکاری ز یادی برای حل مساله فروشنده دوره گرد ارائه شده است که بر حسب مورد هر یک قابلیت بیشتری نسبت به دیگری دارد . اصولاٌ معیار ارزیابی در مورد الگوریتمهای ابتکاری یکی میزان نزدیکی به پاسخ بهینه و دیگری کوتاه بودن زمان محاسباتی است . الگوریتمهای ابتکاری معمولاٌ به ساخت مسیر یا بهبود مسیر یا ترکیبی از این دو روش می پردازند [۳و۲].
یکی از بهترین روشهای ابتکاری برای حل مساله فروشنده دوره گرد ، روشهای تعویض شاخه بخصوص روشهای ابتکاری ۲-opt و ۳-opt می باشد . در سال ۱۹۸۲ اس. الون و ان کریستوفایدز الگوریتم جدیدی را برای تعویض شاخه r-opt مساله فروشنده دوره گرد ارائه کردند که زمان محاسباتی با زیاد شدن اندازه مساله افزایش کمی می یابد [۵] این الگوریتم امکان حل مسائل با ابعاد بزرگ را ممکن می سازد، همچنین ادعا می شود که هر تعویض r-opt معادل یک توالی محدود از ۲-opt می باشد و نیز با استفاده از نتایج محاسباتی نشان می دهند که حل بدست آمده از ۵-opt بهتر از حل بدست آمده از ۳-opt و نزدیکتر به حل بهینه می باشد.
در سال ۱۹۸۳ یک روش ابتکاری بسیار موثر برای بدست آوردن حل های بهینه یا نزدیک بهینه توسط اس .لین و همکاران ارائه شده است [۶]. اساس این الگوریتم بر پایه تعویض k شاخه از مسیر موجه فعلی است تامسیر موجه بهبود یافته بدست آید و این عمل تا آنجا ادامه می‌یابد که با یک چنین تعویضی هیچ بهبودی حاصل نشود و در این صورت حل بهینه موضعی بدست آمده است. در آزمایش دیگری، با چند بار اجرا از یک مساله شاخه های مشترک را ثابت نگه داشته و الگوریتم فوق را برای بقیه شاخه های مسیر بکار بردند که نتایج این روشها بسیار خوب بوده و زمان اجرا حدود تخمین زده شده است.
در سال ۱۹۹۲ مطالعه جامعی توسط بی.گلدن و همکاران انجام گرفت که در آن الگوریتمهای حل مساله فروشنده دوره گرد را در سه دسته روشهای ساخت مسیر، بهبود مسیر و ترکیبی مورد بررسی قراردادند و با انجام آزمایشات مختلف گزارش کردند که بسیاری از روشهای ساخت مسیر برای پیدا کردن مسیر در حدود %۹۵-۹۳ دارای بهینگی می باشد [۷] . روشهای بهبود مسیر، بویژه روش ۲-opt (بهترین آن از ۲۵ اجرا) و ۳-opt (فقط یکبار) با مسیر تصادفی ابتدایی ، مانند بهترین روشهای ساخت مسیر عمل می کنند . مسیر روش ترکیبی سه مرحله ای دارای %۹۸-۹۷ بهینگی است . برای بدست آوردن یک مسیر با %۹۹-۹۸ بهینگی، یک کاربرد تکراری از روش ترکیبی سه مرحله ای می تواند مناسب باشد . در این روش مسیر اولیه تور از روشهای دورترین جایگذاری (Farthest Insertion) یا جایگذاری دلخواه (Arbitrary Insertion) بدست آمده است . اگر این روش ترکیبی را با ۱۰ نقطه شروع اولیه مختلف تکرار کنیم ،نتیجه واقعا عالی و در خور توجه می باشد.
در سال ۱۹۹۵، دبیلیو استوارت نیز روشی را برای سریعتر کردن عملیات محاسباتی الگوریتمهای ابتکاری تعویض شاخه برای مساله فروشنده دوره گرد ارائه می دهد]۸[در این روش فقط شاخه هایی در نظر گرفته می شود که شانس خوبی برای بوجود آوردن یک حل بهتر را دارند، ولی این شاخه ها را از طریق حداقل درخت های پوشامی نیمال (Minimal Spanning Trees)انتخاب می کند . این روش در الگوریتم ابتکاری ۳-opt ، تعداد عملیات مورد نیاز را برای بدست آوردن یک مساله n گره‌ای فروشنده دوره گرد از به کاهش می دهد ، بدون آنکه از کیفیت پاسخ کاسته شود. محقق گزارش می دهد که برای یک مساله ۱۰۰ گره‌ای ، تعدادمراحل مورد نیاز حداقل درخت پوشامی نیمال گسترش یافته حدود۱۰ الی ۱۲ مرحله ( یعنی حدود ) می باشد .
۲- روش برخورد با مساله
در این مقاله روش جدیدی جهت انتخاب شاخه برای الگوریتمهای ابتکاری تعویض شاخه که هنوز هم از روشهای حل خوب برای مساله متقارن فروشنده دوره گرد است ارائه می شود . می توان ادعا نمود این روش از سرعت محاسباتی بسیار بالا برخوردار است و علاوه بر اینکه در کیفیت پاسخ مساله تاثیر منفی نمی گذارد، در خیلی از موارد نیز پاسخ را بهبود می دهد .
تاکنون روشهایی جهت انتخاب شاخه ( درنتیجه محدود کردن تعداد آزمایش‌های ممکن) ابداع شده است [۷،۶،۴] . هدف این است که انتخاب شاخه در کیفیت حل مساله تاثیری نگذارد و زمان محاسباتی را نیز بطور قابل توجهی کاهش دهد . بطوری که با افزایش بعد مساله (n) بتوانیم از الگوریتمهای ابتکاری تعویض شاخه برای بدست آوردن یک پاسخ خوب استفاده کنیم .
با یک نظر اجمالی به روشهای انتخاب شاخه که تاکنون ارائه شده است ، پی می بریم که زمان محاسباتی این روشها نسبت به زمان مورد نیاز برای تعویض شاخه قابل توجه می باشد، بعنوان مثال از روش درخت های پوشامی نیمال (MST) جهت انتخاب شاخه استفاده شده است ]۷[ در حالیکه این روش نیز وقتی که بعد مساله بطور قابل توجهی افزایش می یابد ، زمان نسبتاٌ زیادی نیاز دارد.
الگوریتم پیشنهادی زیر این نیاز زمانی را به طرز قابل توجهی کاهش می دهد . شرح الگوریتم به قرار زیر است :
۱-۲- الگوریتم پیشنهادی
الگوریتم پیشنهادی که آنرا میانگین شاخه ها (Average of Arcs) می نامیم ، همانطور که از نام آن نیز پیداست ، بر مبنای معدل گیری از شاخه ها استوار است . این الگوریتم فقط بخشی از شاخه هایی را که از یک گره خارج می شوند انتخاب می کند . فرض کنید که یک شبکه n گره ای داریم ، از هر گره n-1 شاخه خارج می شود و آنرا به ۱- n گره مرتبط می سازد. حال اگر یک گره مثلاٌ را در نظر بگیریم ومجموع طول ۱- n شاخه هایی که از این گره خارج می شوند بر ۱-n تقسیم کرده و آنرا حد بنامیم ، سپس شاخه هایی را از این گره انتخاب کنیم که طول آنها از این حد کمتر باشد ، آنگاه با این روش توانسته ایم حدود ۵۰% از کوتاهترین شاخه هایی که از این گره خارج می شوند را انتخاب نماییم و اگر حد را بر ۲ تقسیم کنیم حدود ۲۵% و اگر بر ۳ تقسیم کرده حدود ۱۷% و … شاخه انتخاب می شوند . حال اگر این عمل را برای بقیه گره ها نیز انجام دهیم به طرز بسیار ساده و باسرعت چشمگیری می توانیم حدود ۵۰% ، ۲۵% ، ۱۷%، و… کوتاهترین شاخه های یک مساله n تایی فروشنده دوره گرد را انتخاب کنیم . الگوریتم زیر مراحل مختلف محاسبات را نشان می دهد .
مرحله ۱ : فرض کنید ماتریس فواصل بین گره ها و ماتریس شاخه های انتخابی باشد . P ( درصد انتخاب شاخه ها ) را مساوی …. و ۱۷% و ۲۵%و ۵۰% قرار دهید .
مرحله ۲ : اولین سطر ( ۱= i) از ماتریس C را در نظر بگیرید .
مرحله ۳ : حد سطر یعنی را از رابطه ذیل بدست آورید .
مرحله ۴ : اگر به ازای هر j ، آنگاه قراردهید و
مرحله ۵ :اگر i=n است آنگاه توقف کنید در غیر اینصورت i را یک واحد افزایش داده و به مرحله ۳ بروید .
بعنوان مثال فرض کنید ماتریس زیر نشان دهنده فواصل بین گره ها در یک مساله (۱۰=n) متقارن فروشنده دوره گرد است .
۵
۷
۸۴
۹۱
۷۷
۲۰
۳۸
۴۰
۷۵
–
C=
۴۹
۶۶
۸۰
۹
۱۶
۵۲
۳۰
۶۲
–
۷۵
۷۱
۵۲
۶
۸۵
۷۶
۳۷
۹۹
–
۶۲
۴۰
۵۵
۸۰
۸۵
۲۵
۴۰
۸۲
–
۹۹
۳۰
۳۸
۸
۹۳
۹۱
۷۵
۸۰
–
۸۲
۳۷
۵۲
۲۰
۷
۲۲
۴۱
۷۸
–
۸۰
۴۰
۷۶
۱۶
۷۷
۳۶
۲۷
۸۱
–
۷۸
۷۵
۲۵
۸۵
۹
۹۱
۵۶
۵۲
–
۸۱
۴۱
۹۱
۸۵
۶
۸۰
۸۴
۵۱
–
۵۲
۲۷
۲۲
۹۳
۸۰
۵۲
۶۶
۷
–
۵۱
۵۶
۳۶
۷
۸
۵۵
۷۱
۴۹
۵
به ازای ۵/۰ = P خواهیم داشت :
۵
۷
–
–
–
۲۰
۳۸
۴۰
–
–
=
–
–
–
۹
۱۶
۵۲
۳۰
–
–
–
–
۵۲
۶
–
–
۳۷
–
–
–
۴۰
۵۵
–
–
۲۵
۴۰
–
–
–
۳۰
۳۸
۸
–
–
–
–
–
–
۳۷
۵۲
۲۰
۷
۲۲
۴۱
–
–
–
۴۰
–
۱۶
–
۳۶
۲۷
–
–
–
–
۲۵
–
۹
–
۵۶
۵۲
–
–
۴۱
–
–
۶
–
–
–
–
۵۲
۲۷
۲۲
–
–
۵۲
–
۷
–
–
۵۶
۳۶
۷
۸
۵۵
–
–
۵
و برای بقیه موارد نیز مانند حالات فوق می توان عمل کرد .
از این شاخه های انتخاب شده می توان در روشهای تعویض شاخه ۲-opt و ۳-opt استفاده نمود.
۳- نتایج محاسباتی
برای ارزیابی الگوریتم پیشنهادی و میزان تاثیر آن در الگوریتمهای تعویض شاخه ، از روش های ترکیبی استفاده می کنیم . این روشها از روشهای ابتکاری سریع و مسیر حاصل از اجرای آن خیلی نزدیک به مسیر بهینه ( در حد ۹۸% -۹۷ بهینگی) می باشد . اساس کار روشهای ترکیبی به صورت زیر است :
مرحله ۱ :یک مسیر ابتدایی پیدا کنید .
مرحله ۲ :الگوریتم ۲-opt را برای مسیر بدست آمده درمرحله ۱ بکار ببرید .
مرحله ۳ :الگوریتم ۳-opt را برای مسیر بدست آمده در مرحله ۲ بکار ببرید .
با توجه به اینکه از الگوریتم های خوب مسیر سازی یعنی دورترین جایگذاری و جایگذاری دلخواه و نیز از دو روش انتخاب شاخه ( الگوریتم MST و الگوریتم پیشنهادی )بهره می بریم ، پس روش کار برای مساله متقارن n گره ای فروشنده دوره گرد به قرار زیر می باشد .
۱- مسیر ابتدایی را بوسیله الگوریتم دورترین جایگذاری یا جایگذاری دلخواه ایجادکنید .
۲- الگوریتم ۲-۰pt را برای مسیر بدست آمده از ۱ با داشتن ماتریس انتخاب شاخه اجرا کنید (ماتریس انتخاب شاخه با استفاده از الگوریتم MST یا ا لگوریتم پیشنهادی تشکیل می شود و در غیر اینصورت ( در حالت کلی ) همان ماتریس فواصل بین گره ها در نظر گرفته می شود . )
۳- الگوریتم ۳-opt را برای مسیر بدست آمده در قدم ۲ و ماتریس انتخاب شاخه ای که در ۲ استفاده شده اجرا کنید .
برای تشکیل ماتریس انتخاب شاخه در یک مساله n بعدی ، MST را در ۱۰/k=n مرتبه انجام می دهیم ( به عبارت بهتر اگر بعد مساله ۴۰=n باشد الگوریتم MST را برای مرتبه اجرا می کنیم و از شاخه های انتخاب شده آن در الگوریتم ۲-opt و ۳-opt استفاده می کنیم ) و الگوریتم پیشنهادی را نیز در ۵ حالت مختلف ( ۱۰%،۱۲۵%، ۱۷%، ۲۵%، ۵%، = P) بررسی می کنیم . پس بنابر حالات مختلف استفاده از الگوریتمها در ماتریس انتخاب شاخه و نیز روشهای تورسازی ، الگوریتمهای تعویض شاخه را بکار می بریم .
برای مقایسه ، برای هر مسئله n بعدی فروشنده دوره گرد ( که n برابر با ۱۰۰،۸۰،۶۰،۴۰ ) ۵ مساله ایجاد کردیم . د رکل ۲۰ مساله آزمایش شد که نتایج این آزمایشات در جدول (۱-۳) و (
۲-۳) آورده شده است .
جدول (۱-۳) نتایج محاسباتی آزمایشات بعمل آمده با تور سازی FI
FI
(۱/۰=p) AV
MST(10/n)
(۱/۰=p)AV
FI
opt-2
opt-3
(۱۲۵/۰=p)AV
FI
opt-2
opt-3
(۱۷/۰=p)AV
FI
opt-2
opt-3
(۲۵/۰=p)AV
FI
opt-2
opt-3
(۵۰/۰=p)AV
FI
opt-2
opt-3
MST(10/n)
FI
opt-2
opt-3
FI
opt-2
opt-3
روش کار
متوسط ۵ مساله n بعدی
۲/۴۷۶
۳۰/۰
۰۸/۰
۹۱/۷
۲/۳۱۵
۲۱/۳
۲/۲۶۰
۸۱/۵
۴/۲۴۹
۹۶/۴
۶/۲۴۵
۰۷/۵
۸/۲۴۱
۳۳/۵
۴/۲۳۸
۸۸/۱۳
۸/۲۴۱
۱۱
۴۰=n
طول تور
زمان (s)
۲/۵۴۹
۹۷/۰
۱۶/۰
۱/۵۰
۴/۲۵۷
۱۹/۲۲
۲/۲۶۱
۸۰/۲۱
۲/۲۶۴
۲۳/۲۰
۲/۲۵۱
۰۳/۲۵
۲۵۶
۳۵/۳۲
۸/۲۵۸
۷/۷۱
۲۵۶
۷/۷۰
۶۰= n
طول تور
زمان (s)
۸/۷۴۲
۲۴/۴
۴۵/۰
۱۵/۵۴۹
۶/۲۹۷
۹۶/۱۸۹
۲/۳۰۱
۹۹/۱۶۳
۲/۲۹۴
۰۳/۱۵۹
۸/۲۹۰
۰۱/۱۸۶
۲۸۸
۶۸/۲۶۲
۸/۲۹۷
۶۲/۷۱۵
۲۸۸
۷۷/۵۸۰
۱۰۰= n
طول تور
زمان (s)
۶۶۱
۲۶/۲
۲۹/۰
۱۱/۱۸۹
۴/۲۷۹
۲۷/۷۵
۴/۲۶۵
۹۳/۷۱
۲۶۹
۵۸/۶۶
۲۶۷
۶۳/۷۷
۲/۲۶۸
۲۳/۱۰۰
۲۶۵
۰۳/۲۷۱
۲/۲۶۸
۲۶/۲۲۲
۸۰= n
طول تور
زمان (s)
جدول (۲-۳) نتایج محاسباتی آزمایشات بعمل آمده باتورسازی AI
AI
AV(C=5)
MST(10/n)
C=5) )AV AI
Opt-2
opt-3
C=4) )AV
AI
opt-2
opt-3
C=3) )AV
AI
opt-2
opt-3
C=2) )AV
AI
opt-2
opt-3
C=1) )AV
AI
opt-2
opt-3
MST(10/n)
AI
opt-2
opt-3
AI
opt-2
opt-3
روش کار
متوسط ۵ مساله n بعدی
۴۴۳
۰۲/۰
۰۸/۰
۹۱/۷
۴/۳۳۵
۶۶/۲
۸/۲۸۱
۷۸/۳
۲/۲۴۹
۲۷/۵
۶/۲۴۰
۴۲/۵
۸/۲۳۶
۱۱/۷
۲/۲۳۸
۲۴/۱۳
۶/۲۳۴
۵۹/۱۷
۴۰=n
طول تور
زمان (s)
۲/۵۸۴
۰۶/۰
۱۶/۰
۱/۵۰
۶/۲۷۸
۱۸/۲۴
۴/۲۵۷
۲۳/۲۵
۲۵۳
۱۴/۲۷
۶/۲۵۷
۲۶/۲۳
۲/۲۴۹
۸۲/۳۰
۶/۲۴۴
۰۲/۷۵
۲/۲۴۹
۳۸/۶۷
۶۰= n
طول تور
زمان (s)
۲/۶۶۶
۱۱/۰
۲۹/۰
۱۱/۱۸۹
۴/۲۷۶
۴۹/۶۳
۲۶۹
۳۵/۸۱
۸/۲۷۵
۳/۴۹
۶/۲۶۸
۹۷/۷۳
۶/۲۷۴
۸۶/۸۶
۲/۲۶۵
۳۸/۲۶۷
۶/۲۷۴
۷/۱۹۲
۸۰= n
طول تور
زمان (s)
۸/۷۵۰
۱۷/۰
۴۵/۰
۱۵/۵۴۹
۲/۲۹۳
۸۱/۱۵۷
۲/۲۹۰
۶۷/۱۳۸
۲۹۳
۸۹/۱۵۰
۳۰۱
۰۴/۱۴۵
۲۹۷
۴/۱۹۵
۲۹۳
۲۷/۷۱۰
۲۹۷
۸/۴۳۲
۱۰۰= n
طول تور
زمان (s)
۴- ارزیابی نتایج
همانطور که می دانیم روشهای ترکیبی مسیر را تا حد %۹۸-۹۷ بهینگی پیدا می کنند . نتایج جداول نیز نشان می دهد که مسیر روش MST در حد % ۱/۹۸ ، روش (۵/۰=p)AV در حد % ۹/۹۹ و روش (۲۵/۰ =p)AV در حد %۸/۹۷ ، روش (۱۷/۰=p) AV درحد %۷/۹۷ ، روش (۱۲۵/۰=p)AV در حد %۹/۹۰ و سرانجام روش (۱/۰=p)AV درحد %۲/۸۷ مسیر بدست آمده از روشهای ترکیبی می باشند البته در بیشتر موارد مسیر روشهای MST و (۲۵/۰=p)AV بهتر و مسیر (۵/۰ = p)AVمساوی با مسیر بدست آمده از روشهای ترکیبی می باشد ، الگوریتم پیشنهادی بخصوص در موارد(۵/۰ = p)AV و (۲۵/۰ = p)AV و (۱۷/۰ = p)AV نه تنها مانند روش MST از کیفیت پاسخ نمی کاهد بلکه در موارد زیادی نیز بر آن می افزاید . برای بررسی بهتر اثرات روشهای انتخاب شاخه بر الگوریتمهای تعویض شاخه (opt-3 ، opt-2 ) اجازه دهید که زمانهای محاسباتی کامپیوتر جهت ساخت تور ونیز انتخاب شاخه را از زمان کل ارائه شده حذف نماییم . جداول (۱-۴) و (۲-۴) این نتایج را در بر دارد .
جدول (۱-۴)- زمانهای محاسباتی الگوریتمهای تعویض شاخه با استفاده از تورسازی FI
(۱/۰=p)AV
FI
opt-2
opt-3
(۱۲۵/۰=p)AV
FI
opt-2
opt-3
(۱۷/۰=p)AV
FI
opt-2
opt-3
(۲۵/۰=p)AV
FI
opt-2
opt-3
(۵۰/۰=p)AV
FI
opt-2
opt-3
MST FI
opt-2
opt-3
FI
opt-2
opt-3
زمان های محاسباتی بر اساس روش کار
(s)
متوسط ۵مساله
N بعدی
ردیف
۸۳/۲
۴۳/۵
۵۸/۴
۶۹/۴
۹۵/۴
۶۷/۵
۷/۱۰
۴۰= n
۱
۰۶/۲۱
۶۷/۲۰
۱/۱۹
۹/۲۳
۲۲/۳۱
۱/۲۰
۱/۶۹
۶۰=n
۲
۷۲/۷۲
۳۸/۶۹
۰۳/۶۴
۰۸/۷۵
۶۸/۹۷
۶۶/۷۹
۲۲۰
۸۰= n
۳
۱۷/۱۸۵
۲/۱۵۹
۲۲/۱۵۴
۲۲/۱۸۱
۸۹/۲۵۷
۱۳/۱۶۲
۴/۵۷۶
۱۰۰= n
۴
جدول (۲-۴)- زمانهای محاسباتی الگوریتمهای تعویض شاخه با استفاده از تور سازی AI
(۱/۰=p)AV
AI
opt-2
opt-3
(۱۲۵/۰=p)AV
AI
opt-2
opt-3
(۱۷/۰=p)AV
AI
opt-2
opt-3
(۲۵/۰=p)AV
AI
opt-2
opt-3
(۵۰/۰=p)AV
AI
opt-2
opt-3
MST
AI
opt-2
opt-3
AI
opt-2
opt-3
زمان های محاسباتی بر اساس روش کار
(s)
متوسط ۵مساله
N بعدی
ردیف
۵۶/۲
۶۸/۳
۱۷/۵
۳۲/۵
۰۱/۷
۳۱/۵
۵۷/۱۷
۴۰= n
۱
۹۶/۲۳
۰۱/۲۵
۹۲/۲۶
۰۴/۲۳
۶/۳۰
۸۶/۲۴
۳۲/۶۷
۶۰=n
۲
۰۹/۶۳
۹۵/۸۰
۹/۴۸
۵۷/۷۳
۴۶/۸۶
۱۶/۷۸
۵۹/۱۹۲
۸۰= n
۳
۱۹/۱۵۷
۰۵/۱۳۸
۲۷/۱۵۰
۴۲/۱۴۴
۷۸/۱۹۴
۹۵/۱۶۰
۶۳/۴۳۲
۱۰۰= n
۴
با بررسی این جداول پی می بریم که الگوریتم انتخاب کمان (۵/۰=p)AV سبب کاهش زمان لازم محاسباتی به میزان کمتر از نصف و بقیه الگوریتمها نیز زمان محاسباتی را به حدود ۳/۱ زمان لازم تقلیل می دهند . یعنی شاخه های انتخابی از روش متوسط شاخه ها ، همان کاری را انجام می دهند که شاخه های انتخابی از الگوریتم MST انجام می دهند . جدول (۳-۴) و شکل (۱-۴) نشانگر این نتیجه می باشد .
جدول (۳-۴ ) – مقایسه طول تور و زمان محاسباتی الگوریتمهای تعویض شاخه با استفاده از روشهای انتخاب شاخه نسبت به عدم استفاده از آن در الگوریتمهای تعویض شاخه روشهای ترکیبی
درصد قدر مطلق انحراف از طول تور بهینه
درصد کاهش زمان محاسبات
روش
۹/۱
۶/۳۶
MST (10/n)
۰
۵/۵۵
(۵/۰ = p)AV
۲/۲
۶۵
(۲۵/۰=p)AV
۳/۲
۶۸
(۱۷/۰=p)AV
۱/۹
۶۶
(۱۲۵/۰= p)AV
۸/۱۲
۸/۶۹
(۱/۰=p)AV
۱
(N/10)MST
۲
AV(P=0.5)
۳
AV(P=0.25)
۴
AV(P=0.17)
۵
AV(P=0.125)
۶
AV(P=P=0.1)
شکل (۱-۴) – مقایسه طول تور و زمان محاسباتی الگوریتمهای تعویض شاخه با استفاده از روشهای انتخاب شاخه نسبت به عدم استفاده از آن در الگوریتمهای تعویض شاخه روشهای ترکیبی
حال به جدول (۴-۴) و شکل (۲-۴) که زمانهای محاسبه ا نتخاب شاخه الگوریتمهای MST و AV را مقایسه می کند توجه کنید .
شکل ۲-۴- مقایسه زمانهای محاسبه انتخاب کمان ( ثانیه ) از دو روش MST و AV
جدول (۴-۴) مقایسه زمانهای محاسبه انتخاب کمان (ثانیه) از دو روش MST ، AV
۲۵/۰ ، ۵/۰ =p() AV
( (۱/۰، ۱۲۵/۰ ، ۱۷/۰ ،
MST (10/n)
n
ردیف
.۰۸/۰
۹۱/۷
۴۰
۱
۱۶/۰
۱/۵۰
۶۰
۲
۲۹/۰
۱۱/۱۸۹
۸۰
۳
۴۵/۰
۱۵/۵۴۹
۱۰۰
۴
زمانهای محاسباتی الگوریتم پیشنهادی صدها بار کمتر از MST می باشد برای یک مسئله با مثلاٌ ۱۰۰=n زمان لازم برای پیدا کردن ۱۰مرتبه MST برابر با ۱۵/۵۴۹ ثانیه است در حالیکه روش متوسط شاخه ها این شاخه ها را حدود ۴۵/۰ ثانیه انتخاب می کند ، که این نکته بسیار قابل توجه و برجسته برای این الگوریتم می باشد ، زیرا با افزایش بعد مساله ، بکارگیری این الگوریتم جهت انتخاب شاخه ( که زمان لازم محاسباتی آن برای مسائل خیلی بزرگ نیز در حد چند ثانیه می باشد) برای سرعت دادن به محاسبات الگوریتمهای تعویض شاخه بسیار مشهود می باشد .
۵- جمع بندی
الگوریتم های ابتکاری تعویض شاخه از جمله الگوریتمهای ابتکاری سریعی است که هنوز هم جهت بدست آوردن حل نزدیک به بهینه مساله متقارن فروشنده دوره گرد از آن استفاده می شود ، روشهایی جهت انتخاب شاخه برای سریعتر کردن عملیات محاسباتی این الگوریتمها وجود دارد که هدف این روشها آن است که انتخاب شاخه جدا ازاینکه در کیفیت پاسخ مساله تاثیر منفی نگذارد ، زمان محاسباتی را نیز بطور قابل توجهی کاهش دهد تا بتوان از الگوریتمهای تعویض شاخه وقتی که بعد مساله افزایش می یابد براحتی استفاده نمود .
در این مقاله روش جدیدی (Average of Arcs ) برای انتخاب شاخه ارائه شد و نشان داد (در پاسخ مسائل آزمایشی ) که زمان محاسباتی الگوریتمهای تعویض شاخه را به ۳/۱ زمان مورد نیاز تقلیل میدهد بدون آنکه از کیفیت پاسخ بکاهد ، در موارد متعددی کیفیت جواب را نیز بهبود داده است . نکته برجسته و قابل توجه در مقایسه این روش با سایر روشهایی که تا کنون برای سریعتر کردن عملیات محاسباتی الگوریتمهای ابتکاری تعویض شاخه ارائه شده اند ، زمان محاسباتی بسیار کم این روش است که در مقایسه با روش درخت پوشا می نیمال (MST) صدها بار سریعتر عمل می کند و می تواند شاخه های انتخابی برای مسائل خیلی بزرگ را در حد چند ثانیه بدست آورد . لذا می توان برای بدست آوردن پاسخ نزدیک به بهینه مسائل خیلی بزرگ از این روش در الگوریتم های ابتکاری تعویض شاخه استفاده نمود . همچنین پیشنهاد می شود در الگوریتمهای دیگری که بطریقی از تعویض شاخه جهت بدست آوردن پاسخ نزدیک به بهینه مساله فروشنده دوره گرد استفاده می کنند از این روش استفاده شود .
ضمائم – شرح ا لگوریتمهای استفاده شده
۱- الگوریتمهای انتخاب شاخه
یکی از الگوریتمهای خوب انتخاب شاخه ، الگوریتم درخت پوشامی نیمال (Minimal Spanning Tree) است ، که بطور اختصار آنرا MST می نامیم. MST عبارت از پیدا کردن کوتاهترین مسیر در یک شبکه از ارتباطات می باشد . با هر بار اجرای MST تعداد ۱-n ( اگر بعد مساله n×n باشد ) شاخه انتخاب می شوند . به علت لزوم انتخاب شاخه های بیشتر ، MST را در k بار اجرا می کنیم ، تا (۱-n)k کمان انتخاب شوند . شرح الگوریتم به قرار زیر است :
مرحله ۱ : فرض کنید n× n : C ماتریس فواصل بین گره ها و n× n : C ماتریس شاخه های انتخابی باشد ۰ =k قرار دهید .