بخشی از مقاله

چکیده

یافتن بهترین مسیري که از موقعیتهاي مشخصی عبور کند، از مسائل بسیار پرکاربرد در GIS است که میتواند نقش تاثیرگذاري در تصمیمگیريهاي حساس مکانی داشته باشد. به همین دلیل از دیرباز تحقیقات بسیاري روي بهینهسازي این مساله با استفاده از الگوریتمهاي مختلف صورت گرفته است. مساله فروشنده دورهگرد یکی از مسائل بسیار کهن در علوم کاربردي است که قبل از پیدایش GIS نیز مطرح بوده است. این مساله با ظهور تکنولوژي هاي جدید مانند GIS کاربردهاي بسیاري یافته است و روشهاي جدیدي نیز براي حل آن پیشنهاد شده است.

الگوریتمهاي تکاملی - ژنتیک - یکی از روشهایی هستند که براي حل مسائل بهینه سازي مختلف به کار گرفته می شوند. تحقیقات نشان داده است که تلفیق روشهاي جستجوي محلی - Local Search - با عملگرهاي ژنتیک میتواند منجر به نتایج بهتري در حل مساله فروشنده دورهگرد بشود. در این مقاله با استفاده از یک جستجوي محلی ژنتیک به حل مساله مسیریابی فروشنده دوره گرد پرداخته شده است و نتایج روشهاي مختلف تولیدمثل در تکرارهاي مختلف مورد بحث و بررسی قرار گرفته است.

-1 مقدمه

مساله فروشنده دوره گرد - - Traveling Salesman Problem، کوتاهترین مسیر را براي یک فروشنده دورهگرد می یابد به طوریکه از یک شهر شروع بشود از تمامی سایر شهرها به یک ترتیب خاص عبور کند و سرانجام به شهر مقصد برگردد با این شرط که از هر کدام از شهرها فقط و فقط یک بار عبور کند. هدف این مساله بهینهسازي هزینه ها می باشد.

مشخص است مسافتی که این فروشنده دوره گرد می پیماید بستگی به ترتیبی دارد که از شهرها عبور می نماید. بنابراین هدف این مساله، یافتن یک ترتیب بهینه براي عبور از شهرها است، به گونه اي که اهداف هزینه اي در نظر گرفته شده، بهینه سازي شوند. با وجودیکه درك این مساله نیاز به مهارت هاي ریاضی پیچیده ندارد و حتی بسیار ساده و قابل فهم است اما به عنوان یک مساله بهینهسازي ترکیبی سخت از آن نام برده می شود چرا که حل آن بسیار دشوار است.

اولین بار چنین مساله اي در سال 1759 از سوي اولر مطرح شد که در آن زمان با نام "مساله مسیر شوالیه ها" ارائه شد. یک "مسیر شوالیه" عبارت بود از یک دور هامیلتونی در گرافی که نودهاي آن 64 مربع صفحه شطرنج بودند که هر کدام با دو راس دیگر مجاور بودند و شوالیه هر بار تنها به یک مربع مجاور می توانست حرکت کند.

عبارت فروشنده دورهگرد اولین بار در یک کتاب آلمانی در سال 1932 به کار گرفته شد که مولف آن خود، یک فروشندهدورهگرد بود.[16] اولین کسی که این مساله را مورد مطالعه و بررسی قرار داد [16] Menger بود که با ارائه یک الگوریتم شبیه به "نزدیک ترین همسایگی" سعی در حل این مساله داشت اما نتوانست به جواب بهینه اي برسد. البته مطالعات اصولی روي TSP به عنوان یک مساله بهینه سازي ترکیبی Dantzing و همکاران [4] آغاز شد.

GoldBerg با مطالعاتی که روي الگوریتم هاي تکاملی انجام داد، آنها را به عنوان یکی از کاراترین الگوریتم هاي بهینه سازي معرفی نمود - . - [7] در مورد TSP، Johnson و همکاران تحقیق قدرتمندي روي جزئیات بهینه سازي این مساله با استفاده از الگوریتم هاي مختلف انجام دادند و به این نتیجه رسیدند که الگوریتم هاي تکاملی بهتر از سایر روشها به جواب می رسند.

به همین دلیل TSP یکی از مسائلی است که مطالعات بسیاري روي حل آن با استفاده از الگوریتم هاي تکاملی گوناگون صورت گرفته است. عملگرهاي ژنتیک مختلفی براي حل بهتر TSP پیشنهاد شده است که تعداد آنها همچنان در حال افزایش است مثلا عملگر inver-over در - [20] - ، عملگر DPX در - [6] - ، عملگر GX در - [17] - و عملگر SPX در - [19] - براي حل TSP مورد طراحی قرار گرفتهاند.

مشاهده شده است که ترکیب الگوریتم هاي تکاملی با روشهاي ابتکاري جستجوي محلی می تواند منجر به بهبود نتایج بشود. Johnson و همکاران به این نتیجه رسیدند که براي حل مسائل ترکیبی سختی مانند TSP با استفاده از الگوریتم هاي تکاملی، بایستی که این الگوریتمها با روشهاي جستجوي محلی تلفیق شوند. به چنین روشهایی معمولا الگوریتم هاي memetic یا "جستجوي محلی ژنتیک" گفته می شود. اولین بار TSP توسط Brady[3] با استفاده از روشهاي ترکیبی تکاملی حل شد. او از روش 2-opt به عنوان جستجوي محلی استفاده نمود. نتایج او نشان داد که این روش براي حل مساله TSP توانایی هاي مناسبی را ارائه می دهد.

در این مقاله پس از قسمت مقدمه که ملاحظه شد، در بخش دوم به تعریف مساله فروشنده دورهگرد پرداخته می شود. در بخش سوم از مقاله، الگوریتم هاي ژنتیک مورد بحث و بررسی قرار گرفته است. در ادامه و در بخش چهارم مقاله چگونگی پیادهسازي جستجوي محلی ژنتیکی تشریح شدهاست و سرانجام در انتها نتیجهگیري و پیشنهادات حاصل از این پژوهش ارائه خواهد شد.

-2 فرمولبندي مساله

فرض کنید G= - V,E - یک گراف باشد - جهتی یا غیر جهتی - که در آن مجموعه V={1,2,…,n} یک دسته از رئوس و مجموعه یک دسته از یالهاي گراف هستند. اگر به هر کدام از یالها یک مقدار به عنوان هزینه اختصاص بیابد - - Ce می توان گفت ماتریس C= - Cij - n×n یک ماتریس هزینه است که در آن Cij مقدار مربوط به هزینه یال متصل کننده راس i به j در G است. یک دور هامیلتونی از G دور ساده اي است که شامل تمامی راس هاي V می شود. هدف TSP یافتن یک دور - کوچکترین دور هامیلتونی - در G است به طوریکه مجموع هزینه هاي یالها تا حد ممکن کمترین باشد.

بنابراین TSP را می توان به عنوان یک مساله جایگشتی نیز مورد بررسی قرار داد. اگر Pn مجموع تمام جایگشت
هاي دسته{1,2,…,n} باشد، TSP به یافتن یک جایگشت    π  - π - 1 - , π - 1 - , ...,π - n - - در Pn می پردازد که در آن
Cπ - n - π - 1 - ∑in−11Cπ - i - π - i 1 -  کمترین است. در اینجا     - π - 1 - , π - 1 - , ..., π - n - -     ترتیب بازدید شهرها را ارائه می دهد که از شهر π - 1 - آغاز می شود. از آنجایی که با یک تغییر یک واحدي روي    π باز هم همان دور قبلی تشکیل خواهد شد می توان گفت که روي هر دور هامیلتونی به تعداد n جایگشت وجود دارند که نتیجهي آنها همان دور خواهد بود.

با توجه به ماهیت ماتریس هزینه و در واقع ماهیت G، TSP به دو دسته طبقه بندي می شود. اگر Cمتقارن باشد به این معنی است که G غیر جهتی است و مساله را بانام فروشنده دوره گرد متقارن می شناسند - . - SymmetricTSP اما اگر C متقارن نباشد به این معنی است که گراف G جهتدار است که در این حالت به مساله فروشنده دورهگرد غیرمتقارن تبدیل میشود - - AsymmetricTSP با توجه به اینکه هر گراف غیر جهتی با دو برابر کردن یالهایش و دادن هزینه اي برابر به هر دو یال رفت و برگشت، تبدیل به یک گراف جهتی میشود، پس STSP در واقع نوعی از ATSP است.

در بسیاري از کاربردها در جهان واقعی بایستی که بیش از دو هزینه، همزمان در نظر گرفته شوند . مثلا هنگامی که هدف تعیین مسیري براي مسافرت است علاوه بر مخارج سفر، زمان سفر نیز بایستی که مینیمم گردد. واضح است که این یک مساله ي دو هدفی است که علاوه بر کمینه سازي هزینه ها، زمان نیز بایستی مینیمم گردد. در یک TSP چندهدفی، یک گراف کامل و وزندار G= - V,E,c - داده می شود که V در آن مجموعه رئوس، E مجموعه یالها و C تابعی است که یک بردار - C ij  - C ij1 , C ij2 ,..., C ijn به هر کدام از یالها اختصاص می دهد که هر کدام از المانهاي C ijk مطابق یک مقدار - هزینه ، مسافت، زمان و ... - براي هر یال است

-3 روش هاي ابتکاري حل TSP

روشهاي ابتکاري حل مسالهي TSP را میتوان به طور کلی به دو دسته تقسیمبندي نمود: - 1 - روش هاي تکمیلی متوالی - ایجادکننده مسیر - ، - 2 - روشهاي جستجوي محلی. روشهاي تکمیلی متوالی با یک فرآیند افزایشی یک دور هامیلتونی ایجاد می کند و با یافتن اولین جواب ممکن پایان مییابد. اما روش هاي جستجوي محلی روي یک جواب ممکن کار می کنند تا آن را بهبود ببخشند. روشهاي تکمیلی متوالی در سایر بهینه سازي هاي ترکیبی عملکرد ضعیف تري دارند. اما محققین مشاهده نموده اند که چنین روشهایی براي TSP عملکرد بهتري دارند و تقریبا 15-10 درصد از بهینه ها را در زمان نسبتا کوتاهی مییابند. البته روشهاي بهینهسازي بر مبناي جستجوي محلی کارکرد بهتري را ارائه میدهند

-1-3 روشهاي تکمیلی متوالی - ایجاد کننده مسیر -

همانطور که اشاره شد روشهاي "ایجاد کننده مسیر" به ساخت یک مسیر با استفاده از یکسري قوانین میپردازند و با یافتن اولین مسیر حائز شرایط اولیه متوقف میشوند. در این قسمت دو نوع از این روشهاي تکمیلی متوالی معرفی می شوند.

-1-1-3 الگوریتم نزدیکترین همسایه

این روش یکی از ساده ترین روشهاي حل TSP است. مبناي این روش بر این اصل استوار است که هنگام تعیین مسیر در هر مرحله همیشه نزدیکترین و ارزانترین مسیر انتخاب میگردند. از آنجایی که این الگوریتم به نوعی از الگوریتم هاي Greedy محسوب میشود، پیاده سازي آن ساده بوده و بسیار سریع نیز عمل می نماید. اگرچه این الگوریتم در بعضی مواقع جوابهاي مناسبی ارائه میدهد اما به طور کلی بسیاري ازمسیرهاي پرهزینه و نامناسب را نیز می تواند تولید بنماید.

در متن اصلی مقاله به هم ریختگی وجود ندارد. برای مطالعه بیشتر مقاله آن را خریداری کنید