Y@SiN
01-25-2010, 02:31 PM
روش های جستجوی متاهیوریستیکی
در مسائل NP زمانی که اندازه مسئله بزرگ باشد، استفاده از روش های جستجوی آگاهانه و ناآگاهانه میسسر نخواهد بود. چراکه در این رده مسائل فضای حالت مسئله چنان بزرگ می باشد که رسیدن به جواب مسئله در مدت زمان قابل قبول با استفاده این روش های جستجو غیرممکن خواهد بود. از اینرو نیاز به روش هایی داریم که بتواند در بخش های مختلف فضای حالت حرکت کرده و بتواند عمل جستجو را انجام دهد. در اینجا روش هایی جستجو مطرح می شوند که به آنها روش های جستجوی متاهیوریستیکی خواهیم گفت. به همه روش های جستجوی متاهیوریستیکی که در اینجا به بررسی آنها خواهیم پرداخت، در اصطلاح روش های تصادفی هدایت شده گوییم.
http://pnu-club.com/imported/mising.jpg
همانطور که از نام آنها پیداست هریک از این روش های جستجو به طور تصادفی در فضای حالت مسئله حرکت می کنند. البته باید گفت که انجام حرکات تصادفی با کنترل و هدایت الگوریتم انجام می پذیرد. ممکن است چنین تصور شود که به علت تصادفی بودن حرکت ، کارآیی این الگوریتم ها پایین باشد. در حالی در بیشتر مسائل بهینه سازی این روش های جستجو تنها روش حل مساله خواهند بود.
روش های جستجوی محلی
برای معرفی هریک از روش های جستجویی که در فصل به بررسی آن ها می پردازیم از مسئله 8 وزیر استفاده خواهیم کرد. در مسئله 8 وزیر هدف قرار دادن 8 وزیر بر روی صفحه شطرنج به گونه ای است که هیچیک از وزیرها همدیگر را گارد ندهند. تعمیم یافته مسئله 8 وزیر، مسئله n وزیر است که در آن بر روی یک صفحه شطرنج n*n باید n وزیر را به گونه ای قرار دهیم که هیچیک همدیگر را گارد ندهند. مسئله n وزیر از جمله مسائل NP در هوش مصنوعی است که روش های جستجوی معمولی قادر به حل آن ها نخواهد بود. از سوی دیگر می توان به مسئله 8 وزیر به عنوان یک مسئله بهینه سازی نیز نگریست که در آن هدف بهینه کردن تعداد گاردهای جفت وزیرها می باشد. به عنوان مثال فرض کنید در صفحه شطرنج معمولی ، 8 وزیر را به دو روش زیر قرار دهیم :
http://pnu-club.com/imported/mising.jpg http://pnu-club.com/imported/mising.jpg
در روش چینش سمت چپ 3 وزیر و در روش چینش سمت راست 4 وزیر همدیگر را گارد می دهند. بنابراین روش چینش قبلی بهینه تر از روش چینش فعلی است. در واقع می توان مسئله بهینه سازی را به صورت زیر تعریف کرد. فرض کنید S مجموعه همه جواب های ممکن برای مسئله باشد. در صورتی S* می تواند جواب مسئله باشد که به ازای همه جواب های موجود در S ، S* بهینه تر از دیگر جواب ها باشد. در مسئله 8 وزیر دیدیم که جوابی بهینه است که تعداد گاردهای جفت وزیر آن کمتر باشد.
روش های جستجوی محلی همگی حالت های همسایه حالت فعلی را برای رسیدن به بهینه ترین جواب بررسی می کنند. از این رو وجود دو تابع در همه این روش های جستجو الزامی است. اولین تابع میزان بهینگی جواب مسئله ارزیابی می کند و تابع دوم یکی از حالت های همسایه حالت فعلی را انتخاب می کند.
سخن آخر اینکه نحوه پیاده سازی و طراحی الگوریتم برای انتخاب حالت هسایه در این روش های جستجو از اهمیت ویژه ای برخوردار است. به عنوان مثال برای مسئله 8 وزیر می توان به شکل های زیر حالت های همسایگی را تولید کرد :
1) دو وزیر به تصادف انتخاب شده و جای آن دو باهم عوض گردد.
2) یکی از وزیر ها به تصادف انتخاب شده و شماره سطر آن به تصادف تغییر کند.
3) ویزیری به تصادف انتخاب شده و یک خانه به سمت بالا یا پایین حرکت کند
در مسائل NP زمانی که اندازه مسئله بزرگ باشد، استفاده از روش های جستجوی آگاهانه و ناآگاهانه میسسر نخواهد بود. چراکه در این رده مسائل فضای حالت مسئله چنان بزرگ می باشد که رسیدن به جواب مسئله در مدت زمان قابل قبول با استفاده این روش های جستجو غیرممکن خواهد بود. از اینرو نیاز به روش هایی داریم که بتواند در بخش های مختلف فضای حالت حرکت کرده و بتواند عمل جستجو را انجام دهد. در اینجا روش هایی جستجو مطرح می شوند که به آنها روش های جستجوی متاهیوریستیکی خواهیم گفت. به همه روش های جستجوی متاهیوریستیکی که در اینجا به بررسی آنها خواهیم پرداخت، در اصطلاح روش های تصادفی هدایت شده گوییم.
http://pnu-club.com/imported/mising.jpg
همانطور که از نام آنها پیداست هریک از این روش های جستجو به طور تصادفی در فضای حالت مسئله حرکت می کنند. البته باید گفت که انجام حرکات تصادفی با کنترل و هدایت الگوریتم انجام می پذیرد. ممکن است چنین تصور شود که به علت تصادفی بودن حرکت ، کارآیی این الگوریتم ها پایین باشد. در حالی در بیشتر مسائل بهینه سازی این روش های جستجو تنها روش حل مساله خواهند بود.
روش های جستجوی محلی
برای معرفی هریک از روش های جستجویی که در فصل به بررسی آن ها می پردازیم از مسئله 8 وزیر استفاده خواهیم کرد. در مسئله 8 وزیر هدف قرار دادن 8 وزیر بر روی صفحه شطرنج به گونه ای است که هیچیک از وزیرها همدیگر را گارد ندهند. تعمیم یافته مسئله 8 وزیر، مسئله n وزیر است که در آن بر روی یک صفحه شطرنج n*n باید n وزیر را به گونه ای قرار دهیم که هیچیک همدیگر را گارد ندهند. مسئله n وزیر از جمله مسائل NP در هوش مصنوعی است که روش های جستجوی معمولی قادر به حل آن ها نخواهد بود. از سوی دیگر می توان به مسئله 8 وزیر به عنوان یک مسئله بهینه سازی نیز نگریست که در آن هدف بهینه کردن تعداد گاردهای جفت وزیرها می باشد. به عنوان مثال فرض کنید در صفحه شطرنج معمولی ، 8 وزیر را به دو روش زیر قرار دهیم :
http://pnu-club.com/imported/mising.jpg http://pnu-club.com/imported/mising.jpg
در روش چینش سمت چپ 3 وزیر و در روش چینش سمت راست 4 وزیر همدیگر را گارد می دهند. بنابراین روش چینش قبلی بهینه تر از روش چینش فعلی است. در واقع می توان مسئله بهینه سازی را به صورت زیر تعریف کرد. فرض کنید S مجموعه همه جواب های ممکن برای مسئله باشد. در صورتی S* می تواند جواب مسئله باشد که به ازای همه جواب های موجود در S ، S* بهینه تر از دیگر جواب ها باشد. در مسئله 8 وزیر دیدیم که جوابی بهینه است که تعداد گاردهای جفت وزیر آن کمتر باشد.
روش های جستجوی محلی همگی حالت های همسایه حالت فعلی را برای رسیدن به بهینه ترین جواب بررسی می کنند. از این رو وجود دو تابع در همه این روش های جستجو الزامی است. اولین تابع میزان بهینگی جواب مسئله ارزیابی می کند و تابع دوم یکی از حالت های همسایه حالت فعلی را انتخاب می کند.
سخن آخر اینکه نحوه پیاده سازی و طراحی الگوریتم برای انتخاب حالت هسایه در این روش های جستجو از اهمیت ویژه ای برخوردار است. به عنوان مثال برای مسئله 8 وزیر می توان به شکل های زیر حالت های همسایگی را تولید کرد :
1) دو وزیر به تصادف انتخاب شده و جای آن دو باهم عوض گردد.
2) یکی از وزیر ها به تصادف انتخاب شده و شماره سطر آن به تصادف تغییر کند.
3) ویزیری به تصادف انتخاب شده و یک خانه به سمت بالا یا پایین حرکت کند