بخشی از مقاله
چکیده:
دراین پژوهش قصد بررسی و ارائهي روشی کارا جهت حل مسائل کوتاهترین مسیر گردشگري مقید با استفاده از الگوریتم ژنتیک را داریم. این مسائل شامل مسائل کوتاهترین مسیر بین یک مبدأ و یک مقصد در یک گراف جهتدار است، بهطوري که یک سري شرایط برقرار گردد. در واقع علاوه بر محدودیتهاي اعمالشده به مسئله اصلی میخواهیم که مسیر مورد جستجو از دنبالهاي از گرههایی که به ترتیب ثابت مشخصشدهاند عبور کند ضمن اینکه این مسیر نباید از هیچ یال تکراري عبور کند. با توجه به اینکه مسئلهي اشارهشده یک مسئلهي -NPکامل میباشد الگوریتم فراابتکاري ژنتیک براي محاسبهي جوابهاي نزدیک بهینه انتخابشده است. این الگوریتم برروي سه نوع گراف کامل، شبکهاي و تصادفی در نظر گرفته شده است. ارزیابی روش با در نظرگرفتن دو معیار عملکرد زمانی - سرعت - وکیفیت جواب انجام گرفته است. درنهایت نتایج به دست آمده با نتایج حاصل از بکارگیري الگوریتم تطبیقی تصادفی حریصانه - GRASP - که تاکنون تنها الگوریتم بکارگرفته شده براي حل این نوع مسائل میباشند مقایسه شده تا کارایی و عملکرد روش پیشنهادي مشخص گردد.
کلمات کلیدي: مسائل کوتاهترین مسیر، مسائل جریان شبکه اي، الگوریتم فراابتکاري ژنتیک.
.1 مقدمه
مسئله کوتاهترین مسیر همیشه یکی از مهمترین مسائل مطالعه شده در نظریه شبکهها و کاربرديترین مسائل در آنالیزهاي مکانی و مهندسی صنایع بوده است. در نظریه گراف، مسئله یافتن کوتاهترین مسیر در واقع مسئله یافتن مسیري بین دو رأس - گره - در یک شبکه است به گونهاي که مجموع وزن یالهاي تشکیل دهنده آن کمینه شود. این مسائل براي اولین بار توسط فورد1در سال 1956، فرمولبندي شد. با توسعه و پیشرفت مدلهاي ریاضی، الگوریتمهاي مختلفی براي مسیریابی بهینه با توجه به پارامترها، خصوصیات و ساختار شبکه ارائه شده است. یکی از پایهاي ترین این الگوریتمها، الگوریتم دیجسترا2میباشد که توسط دانشمند هلندي در سال 1959 به همین نام ابداع گردید.
این الگوریتم که به روش نشانهگذاري نیز معروف است بر اساس تکنیک حریصانه نوشتهشده و یکی از الگوریتمهایی است که مسئله کوتاهترین مسیر از مبدأ واحد را براي گرافهاي وزنداري که یال با وزن منفی ندارند، حل میکند و درنهایت با ایجاد درخت کوتاهترین مسیر، کوتاهترین مسیر از مبدأ به همه رأسهاي گراف را به دست میآورد. همچنین میتوان از این الگوریتم براي پیدا کردن کوتاهترین مسیر از مبدأ تا رأس مقصد بهاینترتیب بهره جست که در حین اجراي الگوریتم بهمحض پیدا شدن کوتاهترین مسیر از مبدأ به مقصد، الگوریتم را متوقف نمود.[1] از انواع مسائل کوتاهترین مسیر میتوان مسائل کوتاهترین مسیر گردشگري - SPTP - 3 و مسائل کوتاهترین مسیر گردشگري مقید - CSPTP - 4 را نام برد. مسئله کوتاهترین مسیر گردشگري کلاسیک شامل یافتن کوتاهترین مسیر از یک گره مبدا به یک گره مقصد مشخص در یک نمودار هدایت شده با طولهاي قوس غیر منفی میباشد.
چنین مسیري نیاز به پیروي از یک زیرمجموعه گره دارد که در یک ترتیب ثابت آورده میشود. این زیرمجموعهها هیچ اشتراکی ندارند. در این مسائل میبایست حداقل یک گره از گرههاي موجود در زیرمجموعههاي ,…, پیموده شود.[2] در مسئله کوتاهترین مسیرگردشگري مقید اگر یک گراف جهتدار با طول یالهاي نامنفی مفروض باشد هدف یافتن کوتاهترین مسیر از یک مبدأ به یک مقصد میباشد بهطوري که باید از دنبالهاي از زیرمجموعههایی که شامل گرههاي مشخص میباشند و به ترتیب ثابت داده شدهاند عبور کنیم. این زیرمجموعهها جدا از هم بوده و داراي هیچ نقطهي اشتراکی نمیباشند بهعلاوه لازم است که کوتاهترین مسیر بهدستآمده شامل یالهاي تکراري نباشند .[3] این دو دسته مسئله اشاره شده که اخیراً معرفی شدهاند داراي کاربردهاي متعددي در یافتن مسیرهاي میان مکانهاي واقعی از قبیل راههاي عبور و مرور، نقشههاي اینترنتی مانند نرمافزار نقشه یاب گوگل، رباتیک، حملونقل، طراحی مدارهايVLSI5 و ... میباشد.[3] در این پژوهش با توجه به اینکه ثابت میشود مسائل کوتاهترین مسیر گردشگري مقید به دستهي مسائل -NP کامل تعلق دارند[3]
قصد داریم یک الگوریتم فراابتکاري مبتنی بر الگوریتم ژنتیک براي یافتن جواب بهینه اینگونه مسائل ارائه دهیم. الگوریتم ژنتیک، روشی براي حل مسائل بهینهسازي قید دار و بدون قید است که بر مبناي نظریه انتخاب طبیعی - فرآیندي که تکامل زیستشناسی را پیش میبرد - عمل میکند. این الگوریتم بهطور مداوم جمعیتی از جوابهاي منفرد را اصلاح میکند و در هر مرحله، به صورت تصادفی افرادي را از نسل فعلی به عنوان والدین انتخاب میکند و از آنها براي ایجاد فرزندان که خود اعضاي نسل بعد هستند استفاده میکند. در طول نسلهاي متوالی، جمعیت جوابها به سمت یک جواب بهینه »تکامل« پیدا میکند. از الگوریتم ژنتیک براي حل مسائل مختلف بهینهسازي که الگوریتمهاي استاندارد بهینهسازي براي حل آنها مناسب نیست و یا به دسته مسائل NP تعلق دارند، استفاده میشود.
به عنوان نمونهاي از این دست مسائل میتوان به مسائلی اشاره کرد که در آن تابع هدف ناپیوسته، مشتق ناپذیر، تصادفی و یا غیرخطی از مرتبه بالا میباشد. الگوریتم ژنتیک همچنین میتواند در حل مسائل برنامهریزي عدد صحیح مختلط که در آن برخی از اجزا محدود به مقادیر صحیح هستند نیز استفاده میشوند.[4] این الگوریتم توسط پژوهشگران در زمینه حل انواع مسائل کوتاهترین مسیر نیز بکار برده شده است که از جمله آنها میتوان به مراجع [4] اشاره نمود. در مقاله حاضر، براي اولین بار الگوریتم ژنتیک براي حل مسائل CSPTP بکار گرفته شده است. در این راستا، در بخش دوم پژوهش به معرفی و بیان شکل ریاضی مسائل CSPTP میپردازیم. در بخش سوم نحوه پیاده سازي الگوریتم ژنتیک براي ایندسته از مسائل ارائه خواهد شد. سپس در بخش چهارم به ارائه نتایج عددي حاصل از بکارگیري الگوریتم پیشنهادي پرداخته و خروجیهاي بدست آمده ضمن مقایسه با روش GRASP تجزیه و تحلیل میشوند.
.2 بیان مسئله
در این بخش ابتدا مدل ریاضی مسئله را بهمراه مثالی بیان کرده و در ادمه نحوه پیاده سازي الگوریتم ژنتیک را براي ایندسته از مسائل ارائه میکنیم. از آنجا که مسائل کوتاهترین مسیر گردشگري مقید به دستهي مسائل کامل-NP تعلق دارند و از ویژگیهاي این دسته مسائل، این است که براي حل کردن آنها ، الگوریتم حل چندجملهاي زمانی وجود ندارد لذا براي حل اینگونه مسائل از الگوریتمهاي ابتکاري یا فراابتکاري بهره گرفته شده است که در اینجا براي اولین بار از الگوریتم فراابتکاري ژنتیک جهت محاسبه بهترین و نزدیکترین جواب بهینه کمک میگیریم. در این بخش ابتدا نمودار مربوط به عملکرد الگوریتم ژنتیک طراحی شده بر روي مسائل CSPTP آورده شده است سپس در هر قسمت شبه کد مربوط به هر قسمت ارائه شده است.
