Y@SiN
01-25-2010, 02:36 PM
همانطور که در الگوریتم تپه نوردی بررسی کردیم، این روش جستجوی محلی دارای مشکل قرار گرفتن در بهینگی محلی است. این مشکل تا حدی است که حتی در مورد مسائل ساده ای همچون مسئله 8 وزیر نیز این روش جستجو از درصد موفقیت بسیار پایینی برخوردار بود.
http://pnu-club.com/imported/mising.jpg
با این حال می توان تغییر کوچکی در این الگوریتم داد و تا حدودی میزان موقیت الگوریتم تپه نوردی را در حل مسائله بهینه سازی بالا برد. مشکل الگوریتم تپه نوردی این بود که هنگام قادر به تغییر حالت از یک محل بهینگی به محل بهینگی دیگر نبود. اما برای گریز از بهینگی های محلی می توانیم ترتیبی اتخاذ کنیم که هنگام قرار گرفتن در بهینگی های محلی به بخش دیگری از فضای حالت جهش کنیم و سپس در آنجا به جستجوی جواب با روش تپه نوردی بپردازیم و این عمل را تا رسیدن به یک ماکزیمم سراسری تکرار کنیم. شبه کد زیر نحوه اجرای این الگوریتم را نشان می دهد :
Procedure HillClimbing
Generate a solution ( s' )
Best = S'
Loop
S = Best
S' = Neighbors (S)
Best = SelectBest (S')
IF there is no changes in Best solution THEN
Jump to new state in state space
Until stop criterion satisfied
End
در این روش علاوه بر دو تابع Objective و Neighbor ، تابعی با نام Mutate نیز خواهیم داشت که وظیفه این تابع جهش در فضای حالت مسئله خواهد بود. همچنین باید بتوان نقطه بهینگی سراسری را تشخیص داد. به عنوان مثال بهینه ترین جواب برای مسئله 8 وزیر ، نقطه ای است که در آن تعداد گاردهای جفت وزیرها صفر عدد باشد. اما مسائلی نیز وجود دارند که از ابتدا نمی توان مقدار بهینگی سراسری مسئله را در آن ها تشخیص داد. لازم به ذکر است که برای مسائل مختلف می توانیم شرط پایان حلقه و نحوه اجرای الکوریتم را تغییر دهیم. لازم به ذکر است که تابع Mutate را به طور کلی می توان با دو استراتژی مختلف پیاده سازی کرد :
1. جهش در فضای حالت کوتاه باشد
2. جهش های بزرگ در فضای حالت انجام دهد
جهش کوتاه جهشی است که تعداد حالت های میان حالت فعلی و حالت جهش یافته کم باشد. نقطه مقابل جهش کوتاه نیز جهش بلند می باشد. استفاده از هرکدام از این روش ها بستگی به مسئله دارد و نمی توان در مورد ارجحیت یکی به دیگری اظهار نظر کرد. ما در این برنامه از جهش های کوتاه برای گریز از بهینگی های محلی استفاده کرده ایم.
http://pnu-club.com/imported/mising.jpg
با این حال می توان تغییر کوچکی در این الگوریتم داد و تا حدودی میزان موقیت الگوریتم تپه نوردی را در حل مسائله بهینه سازی بالا برد. مشکل الگوریتم تپه نوردی این بود که هنگام قادر به تغییر حالت از یک محل بهینگی به محل بهینگی دیگر نبود. اما برای گریز از بهینگی های محلی می توانیم ترتیبی اتخاذ کنیم که هنگام قرار گرفتن در بهینگی های محلی به بخش دیگری از فضای حالت جهش کنیم و سپس در آنجا به جستجوی جواب با روش تپه نوردی بپردازیم و این عمل را تا رسیدن به یک ماکزیمم سراسری تکرار کنیم. شبه کد زیر نحوه اجرای این الگوریتم را نشان می دهد :
Procedure HillClimbing
Generate a solution ( s' )
Best = S'
Loop
S = Best
S' = Neighbors (S)
Best = SelectBest (S')
IF there is no changes in Best solution THEN
Jump to new state in state space
Until stop criterion satisfied
End
در این روش علاوه بر دو تابع Objective و Neighbor ، تابعی با نام Mutate نیز خواهیم داشت که وظیفه این تابع جهش در فضای حالت مسئله خواهد بود. همچنین باید بتوان نقطه بهینگی سراسری را تشخیص داد. به عنوان مثال بهینه ترین جواب برای مسئله 8 وزیر ، نقطه ای است که در آن تعداد گاردهای جفت وزیرها صفر عدد باشد. اما مسائلی نیز وجود دارند که از ابتدا نمی توان مقدار بهینگی سراسری مسئله را در آن ها تشخیص داد. لازم به ذکر است که برای مسائل مختلف می توانیم شرط پایان حلقه و نحوه اجرای الکوریتم را تغییر دهیم. لازم به ذکر است که تابع Mutate را به طور کلی می توان با دو استراتژی مختلف پیاده سازی کرد :
1. جهش در فضای حالت کوتاه باشد
2. جهش های بزرگ در فضای حالت انجام دهد
جهش کوتاه جهشی است که تعداد حالت های میان حالت فعلی و حالت جهش یافته کم باشد. نقطه مقابل جهش کوتاه نیز جهش بلند می باشد. استفاده از هرکدام از این روش ها بستگی به مسئله دارد و نمی توان در مورد ارجحیت یکی به دیگری اظهار نظر کرد. ما در این برنامه از جهش های کوتاه برای گریز از بهینگی های محلی استفاده کرده ایم.