Y@SiN
01-25-2010, 02:34 PM
الگوریتم تپه نوردی
الگوریتم تپه نوردی بدین صورت است که ابتدا جوابی به شکل تصادفی برای مساله تولید می شود. سپس در یک حلقه و تا زمانی که شرط توقف الگوریتم برقرار نشده است، به طور مکرر تعدادی همسایه برای حالت فعلی تولید شده و از میان حالت های همسایه بهترین آن ها انتخاب شده و جایگزین حالت فعلی می شود ( البته تالگوریتم په نوردی به شکل دیگری نیز تعریف شده است).
در حالت کلی بهینگی جوابی که این الگوریتم پیدا می کند محلی است. لازم بذکر است که منظور از بهینگی مینیمم سازی یا ماکزیمم سازی یک مسئله بهینه سازی می باشد. مفهوم محلی بودن بهینگی را در شکل روبرو شرح می دهیم . فرض کنید مسئله ای که می خواهیم به بهینه سازی آن بپردازیم ، یک مسئله ماکزیمم سازی باشد. ماکزیمم سازی در تصویر فوق بدین معنی است که شخص نشان داده شده در پایان اجرای الگوریتم بر روی بلندترین قله قرار گیرد.
http://pnu-club.com/imported/mising.jpg
در صورتی که از الگوریتم بهبود تکراری برای ماکزیمم سازی استفاده کنیم ، ممکن است تنها به جواب هایی دست یابیم که این جواب ها ماکزیمم های محلی هستند و نه ماکزیمم های سراسری. چرا که الگوریتم بهبود تکراری بهترین همسایه جواب فعلی را به عنوان جواب بهینه تر بر می گزیند. فرض کنید الگوریتم بهبود تکراری برای شروع نسمت چپ ترین نقطه تصویر را انتخاب می کند، در هربار تکرار حلقه ، همواره همسایه ای برای نقطه فعلی وجود دارد که بهینگی آن بهتر از جواب فعلی است. بنابراین در ابتدا الگوریتم اجرا شده و مرتبا به طرف بالا حرکت می کند. تا اینکه به نقطه ماکزیمم محلی می رسد ( قله ای که شخص در تصویر بر روی آن قرار دارد ). در این نقطه هیچ همسایه ای که بهتر از جواب فعلی باشد، وجود ندارد. از اینرو الگوریتم در این نقطه به پایان می رسد و جواب فعلی را به عنوان بهینه ترین جواب بر می گرداند.
بنابراین نقطه شروع در الگوریتم های جستجو محلی بسیار در ادامه اجرای الگوریتم تاثیرگذار خواهد بود. البته ممکن است با اجرای چندباره الگوریتم به جواب بهینه سراسری دست یابیم، اما در کل استفاده از روش بهبود تکراری برای مسایل پیچیده توصیه نمی شود. حال به نحوه استفاده از این الگوریتم برای حل مساله 8 وزیر می پردازیم و نشان می دهیم که الگوریتم بهبود تکراری حتی جوابگوی مسئله 8 وزیر نخواهد بود.
برای پیاده سازی روش تپه نوردی نیاز به دو تابع Objective و Neighbor داریم. تابع Objective میزان بهینگی جواب مسئله را تعیین می کند که در مورد مسئله 8 وزیر تعداد گاردهای جفت وزیرها بر روی صفحه شطرنج را بر می گرداند. تابع Neighbor نیز همسایه های حالت فعلی را تولید می کند که در مسئله 8 وزیر برای تولید حالت های همسایه، هریک از وزیرها را انتخاب کرده و یکبار به سمت بالا و باردیگر به سمت پایین حرکت می دهیم. این بدان معنی است که در بدترین حالت هر حالت، 16 حالت همسایه خواهد داشت که در هر تکرار از حلقه بهترین حالت همسایه به عنوان جواب جایگزین خواهد شد. الگوریتم نیز زمانی به اتمام می رسد که حالت بهتری نسبت به حالت فعلی تولید نشود. شبه کد زیر نحوه پیاده سازی الگوریتم تپه نوردی را نشان می دهد:
Procedure HillClimbing
Generate a solution ( s' )
Best = S'
Loop
S = Best
S' = Neighbors (S)
Best = SelectBest (S')
Until stop criterion satisfied
End
الگوریتم تپه نوردی بدین صورت است که ابتدا جوابی به شکل تصادفی برای مساله تولید می شود. سپس در یک حلقه و تا زمانی که شرط توقف الگوریتم برقرار نشده است، به طور مکرر تعدادی همسایه برای حالت فعلی تولید شده و از میان حالت های همسایه بهترین آن ها انتخاب شده و جایگزین حالت فعلی می شود ( البته تالگوریتم په نوردی به شکل دیگری نیز تعریف شده است).
در حالت کلی بهینگی جوابی که این الگوریتم پیدا می کند محلی است. لازم بذکر است که منظور از بهینگی مینیمم سازی یا ماکزیمم سازی یک مسئله بهینه سازی می باشد. مفهوم محلی بودن بهینگی را در شکل روبرو شرح می دهیم . فرض کنید مسئله ای که می خواهیم به بهینه سازی آن بپردازیم ، یک مسئله ماکزیمم سازی باشد. ماکزیمم سازی در تصویر فوق بدین معنی است که شخص نشان داده شده در پایان اجرای الگوریتم بر روی بلندترین قله قرار گیرد.
http://pnu-club.com/imported/mising.jpg
در صورتی که از الگوریتم بهبود تکراری برای ماکزیمم سازی استفاده کنیم ، ممکن است تنها به جواب هایی دست یابیم که این جواب ها ماکزیمم های محلی هستند و نه ماکزیمم های سراسری. چرا که الگوریتم بهبود تکراری بهترین همسایه جواب فعلی را به عنوان جواب بهینه تر بر می گزیند. فرض کنید الگوریتم بهبود تکراری برای شروع نسمت چپ ترین نقطه تصویر را انتخاب می کند، در هربار تکرار حلقه ، همواره همسایه ای برای نقطه فعلی وجود دارد که بهینگی آن بهتر از جواب فعلی است. بنابراین در ابتدا الگوریتم اجرا شده و مرتبا به طرف بالا حرکت می کند. تا اینکه به نقطه ماکزیمم محلی می رسد ( قله ای که شخص در تصویر بر روی آن قرار دارد ). در این نقطه هیچ همسایه ای که بهتر از جواب فعلی باشد، وجود ندارد. از اینرو الگوریتم در این نقطه به پایان می رسد و جواب فعلی را به عنوان بهینه ترین جواب بر می گرداند.
بنابراین نقطه شروع در الگوریتم های جستجو محلی بسیار در ادامه اجرای الگوریتم تاثیرگذار خواهد بود. البته ممکن است با اجرای چندباره الگوریتم به جواب بهینه سراسری دست یابیم، اما در کل استفاده از روش بهبود تکراری برای مسایل پیچیده توصیه نمی شود. حال به نحوه استفاده از این الگوریتم برای حل مساله 8 وزیر می پردازیم و نشان می دهیم که الگوریتم بهبود تکراری حتی جوابگوی مسئله 8 وزیر نخواهد بود.
برای پیاده سازی روش تپه نوردی نیاز به دو تابع Objective و Neighbor داریم. تابع Objective میزان بهینگی جواب مسئله را تعیین می کند که در مورد مسئله 8 وزیر تعداد گاردهای جفت وزیرها بر روی صفحه شطرنج را بر می گرداند. تابع Neighbor نیز همسایه های حالت فعلی را تولید می کند که در مسئله 8 وزیر برای تولید حالت های همسایه، هریک از وزیرها را انتخاب کرده و یکبار به سمت بالا و باردیگر به سمت پایین حرکت می دهیم. این بدان معنی است که در بدترین حالت هر حالت، 16 حالت همسایه خواهد داشت که در هر تکرار از حلقه بهترین حالت همسایه به عنوان جواب جایگزین خواهد شد. الگوریتم نیز زمانی به اتمام می رسد که حالت بهتری نسبت به حالت فعلی تولید نشود. شبه کد زیر نحوه پیاده سازی الگوریتم تپه نوردی را نشان می دهد:
Procedure HillClimbing
Generate a solution ( s' )
Best = S'
Loop
S = Best
S' = Neighbors (S)
Best = SelectBest (S')
Until stop criterion satisfied
End