بخشی از مقاله
چکیده
با پیشرفت علم، بشر تلاش می کند تا با حل مسائل پیچیده در جهت ارتقاء دانش جهانی گام های اساسی بردارد. در دنیای امروز هم بشر با کمک رایانه توانسته مسائل گوناگونی را با راهکارهای مختلفی حل کند. یکی از راهکارهای حل مساله استفاده از الگوریتم های تکاملی می باشد. این روش که از سیستم تکاملی در طبیعت ناشی می شود با شبیه سازی سیستم تکامل، می تواند روشی برای حل مسائل سخت و پیچیده ارائه کند.
استفاده از روش های بهینه سازی می تواند برای حل مسائل سخت کمک بزرگی باشد زیرا باعث کاهش هزینه و زمان می شود.مسئله فروشنده دوره گرد یکی از مسائل بهینه سازی است که به دلیل قرارگیری در دسته ی مسائل NP HARD به راحتی قابل حل نمی باشد.
به همین دلیل برای حل آن از الگوریتمی تکاملی مانندالگوریتم ژنتیک کمک می گیریم. در مقاله ی حاضر ابتدا یک تعریف کلی از مفاهیم، ارائه می شود. همچنین به بررسی حل مسئله فروشنده دوره گرد به وسیله ی الگوریتمی تکاملی می پردازیم. در این مقاله که به روش مطالعه ای و مروری با بررسی منابع موجود جمع آوری می گردد ،در نهایت، امکان یا عدم امکان حل مسئله فروشنده دوره گرد توسط الگوریتم ژنتیک را مورد بررسی قرار می گیرد.
مقدمه
با پیشرفت تکنولوژی و گسترش جوامع نیاز به دنبال روش هایی برای کاهش هزینه ها و زمان برای حل مسائل هستیم.برای حل مسائل NP Hard راهکار مشخصی وجود ندارد.مسئله فروشنده دوره گرد نیز جزء دسته ی مسائل سخت است که در این مقاله راهکارهایی برای حل آن ارائه می شود. برای حل مسائل سخت سه دسته الگوریتم معرفی می شود : الگوریتم های تقریبی، احتمالی و ابتکاری. که الگوریتم های تکاملی جزء دسته ی الگوریتم های ابتکاری قرار می گیرند و در مقایسه با روش های تقریبی و احتمالی در عمل و در مسایل گوناگون نتایج قابل قبول تری را ارائه می دهند.
در مساله فروشنده دوره گرد که یکی از مسائل شناخته شده در زمینه ی بهینه سازی است ، یک فروشنده دوره گرد می خواهد ، به N شهر برود و کالای خود را بفروشد، به این صورت که تمام شهر ها را رفته، از هرشهرفقط یک بار عبورکند و در نهایت مسیری را با کمترین هزینه طی کند . برای حل اینگونه مسائل می توان از الگوریتم های تکاملی استفاده نمود .
در این تحقیق الگوریتم ژنتیک برای حل مسئله فروشنده دوره گرد مورد بحث قرار می گیرند.
تعاریف کلی
مسئله فروشنده دوره گرد - TSP - Travelling salesman problem
مسئله فروشنده دوره گرد یکی از مسائل معروف در حوزه ی بهینه سازی می باشد. مسئله به این صورت تعریف می شود که فروشنده ای در بین مجموعه ای از شهرها - گره های گراف - حرکت می کند. این فروشنده باید کوتاهترین مسیر را پیمایش کرده و در انتها به نقطه شروع بازگردد - سلطانی زاده،. - 1388 با زیاد شدن تعداد شهرها فضای حل مسئله افزایش می یابد و همین امر باعث شده تا مسئله ی فروشنده دوره گرد در دسته ی مسائل سخت - NP HARD - قرار گیرد.
حالت کلی مساله فروشنده دوره گرد شامل یافتن یک دور همیلتونی برای یک گراف دلخواه راسی با حداقل مسافت پیموده شده است،که هر یال درآن مسافت بین دو راس را نشان میدهد.
راه حل: - با در نظر گرفتن همه ی راس ها - به طور کلی ممکن است از هر راس به رئوس دیگر یک یال وجود داشته باشد . اگر همه ی تورهای ممکن را در نظر بگیریم راس دوم روی تور می تواند هر یک از - n-1 - راس باشد . راس سوم می تواند هر یک از - n-2 - راس باشد ..... و راس n ام روی تور، فقط می تواند یک راس باشد . بنابراین ، تعداد کل تورها به صورت زیر است که بدتر از نمایی است.
برای حل این مسئله تعدادکل راه حل ها برابراست با - - n-1 برای n>2 که n تعداد شهرها است . در واقع این عدد برابر است با تعداد دورها ی همیلتونی دریک گراف کامل باn رأس.
باید گفت که تنها روش حل این مسآله روش برنامه نویسی پویا است و با روش های دیگر به جواب نمی رسیم .
الگوریتم های تکاملی
همان طور که تاریخ الگوریتم های تکاملی نشان می دهد، گونه های زیادی از الگوریتم های تکاملی وجود دارند. ولی ایده همه آنها یکی است: با داشتن جمعیتی از گونهها، فشار محیطی باعث انتخاب می شود - القاء بهترین - و این افزایش شایستگی جمعیت را نتیجه می دهد. با داشتن یک تابع کیفیتی که می خواهیم بیشینه شود، می توان مجموعه ای از جواب های کاندید را به طور تصادفی تولید کرد و تابع کیفیت را به عنوان معیاری برای محاسبه شایستگی به کار برد - - هر چه بیشتر، بهتر - بر اساس این شایستگی ، بعضی از کاندیدهای بهتر انتخاب می شوند، تا به عنوان هسته ای برای تولید نسل بعد به کار روند. بر روی این کاندیدها ترکیب و یا جهش اعمال می شود. ترکیب برروی دو یا بیشتر کاندید اعمال می شود - والدین - و نتیجه آن تولید فرزند - فرزندانی - است
اعمال ترکیب و جهش باعث تولید مجموعه جدیدی می شود که با مجموعه قبلی - والدین - رقابت می کنند تا در نهایت برنده ها در نسل بعدی ظاهر شوند. این کار می تواند ادامه پیدا کند تا یک کاندید با ویژگی های کافی - جواب - به دست بیاید و یا اینکه محدودیتهایی که از قبل برای مسئله تعریف کرده ایم، ارضا شوند.
الگوریتم ژنتیک
زندگی در طبیعت دائماً در حال تکامل است. الگوریتم های ژنتیکی، الگوریتم های محاسباتی هستند که با توجه به تکامل ایجاد شده اند. به نظر می آید الگوریتم های ژنتیکی برای جستحو فضاهای بزرگ که به طور ضعیف توصیف شده اند، به کار میروند. محدوده کاری الگوریتم ژنتیک بسیار وسیع می باشد و هر روز با پیشرفت روزافزون علوم و تکنولوژی استفاده از این روش در بهینه سازی و حل مسائل بسیار گسترش یافته است.
الگوریتم ژنتیک یکی از زیر مجموعه های محاسبات تکامل یافته می باشد که رابطه مستقیمی با مبحث هوش مصنوعی دارد در واقع الگوریتم ژنتیک یکی از زیر مجموعه های هوش مصنوعی می باشد. الگوریتم ژنتیک را میتوان یک روش جستجوی کلی نامید که از قوانین تکامل بیولوژیک طبیعی تقلید میکند .الگوریتم ژنتیک برروی یکسری از جوابهای مساله به امید بدست آوردن جوابهای بهتر قانون بقای بهترین را اعمال می کند. درهر نسل به کمک فرآیند انتخابی متناسب با ارزش جوابها و تولید مثل جواب-های انتخاب شده به کمک عملگرهایی که از ژنتیک طبیعی تقلید شدهاند , تقریبهای بهتری از جواب نهایی بدست میآید. این فرایند باعث میشود که نسلهای جدید با شرایط مساله سازگارتر باشد.
تاریخچه
ایده اصلی الگوریتم های تکاملی را ریچنبرگ در سال 1965 مطرح کرد. الگوریتم ژنتیک که منشعب از این الگوریتم هاست براساس ساختار ژن ها و کروموزوم هاست که پروفسور هولند - - 1989 - - John Holland در دانشگاه میشیگان آن را مطرح کرد.
در سال 1992 نیز جان کوزا - John Koza - از الگوریتم ژنتیک - - GA برای حل و بهینه سازی مسائل مهندسی پیشرفته استفاده کرد و توانست برای اولین بار روند الگوریتم ژنتیک - - GA را به زبان کامپیوتر در آورد و برای آن یک زبان برنامه نویسی ابداع کندکه به این روش برنامه نویسی ,برنامه نویسی ژنتیک - GP - گویندو نرم افزاری که توسط وی ابداع گردید به نرم افزار LISP مشهور است که هم اکنون نیز این نرم افزار کاربرد زیادی در حل و بهینه سازی مسائل مهندسی پیدا کرده است .
تاریخچه بیولوژیکی
بدن هر موجود زنده ای از سلول تشکیل یافته است و هر سلول هم از کروموزوم تشکیل یافته است.کروموزومها نیز از رشته های DNA تشکیل یافته اند.کروموزومها هم از ژن تشکیل یافته اند.و به هر بلوک DNA یک ژن می گویند و هر ژن نیز از یک پروتئین خاص ومنحصر به فرد تشکیل یافته است.و به مجموعه از ژنها یک ژنوم - Genome - می گویند.
روند کلی بهینه سازی و حل مسائل در الگوریتم ژنتیک :
1. شروع - : - Start تولید تصادفی یک جمعیت - - Population که شامل تعداد زیادی کروموزم - روشهای حل مسئله است - می باشد.
2. صحت و درستی - : - Fitness ارزیابی صحت برای تابع f - x - به ازائ هر کروموزوم x درجمعیت.
شکل 6 نحوه ارزیابی تابع شایستگی در چرخ رولت
3. ایجاد یک جمعیت جدید - New Population - :تولید یک جمعیت جدید با انجام تمامی زیر گروههای زیر تا آنکه یک جمعیت جدید ایجاد گردد.
