روش های جستجوی متاهیوریستیکی

روش های جستجوی متاهیوریستیکی
در مسائل 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) ویزیری به تصادف انتخاب شده و یک خانه به سمت بالا یا پایین حرکت کند

الگوریتم تپه نوردی
الگوریتم تپه نوردی بدین صورت است که ابتدا جوابی به شکل تصادفی برای مساله تولید می شود. سپس در یک حلقه و تا زمانی که شرط توقف الگوریتم برقرار نشده است، به طور مکرر تعدادی همسایه برای حالت فعلی تولید شده و از میان حالت های همسایه بهترین آن ها انتخاب شده و جایگزین حالت فعلی می شود ( البته تالگوریتم په نوردی به شکل دیگری نیز تعریف شده است).
در حالت کلی بهینگی جوابی که این الگوریتم پیدا می کند محلی است. لازم بذکر است که منظور از بهینگی مینیمم سازی یا ماکزیمم سازی یک مسئله بهینه سازی می باشد. مفهوم محلی بودن بهینگی را در شکل روبرو شرح می دهیم . فرض کنید مسئله ای که می خواهیم به بهینه سازی آن بپردازیم ، یک مسئله ماکزیمم سازی باشد. ماکزیمم سازی در تصویر فوق بدین معنی است که شخص نشان داده شده در پایان اجرای الگوریتم بر روی بلندترین قله قرار گیرد.

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

الگوریتم تپه نوردی تعمیم یافته

همانطور که در الگوریتم تپه نوردی بررسی کردیم، این روش جستجوی محلی دارای مشکل قرار گرفتن در بهینگی محلی است. این مشکل تا حدی است که حتی در مورد مسائل ساده ای همچون مسئله 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

روش جستجوی دیگری بر پایه جستجوی تپه نوردی به نام جستجو پرتو محلی نیز وجود دارد که در حل مسائل از قدرت بسیار بیشتری نسبت به جستجوی تپه نوردی برخوردار می باشد. در این روش برخلاف روش تپه نوردی ابتدا k جواب برای مساله تولید می کنیم. سپس برای هریک از این K حالت همسایه های آن ها را تولید کرده و از میان همه همسایه ها K تا از بهترین همسایه ها را انتخاب می کنیم که این فرآیند تا رسیدن به شرط توقف ادامه می یابد. بنابراین الگوریتم روش جستجوی پرتو محلی به را به صورت زیر می توان بیان کرد :

کد:

Procedure LoacBeamSearch Generate K solution Do For each solution generate its neighbors Select K best solution from whole neighbors Replace current solutions by selected solutions Loop until stop criterion satisfied End

الگوريتم جستجوی پرتو محلی
هرچند که الگوریتم جستجوی پرتو محلی در مقایسه با الگوریتم تپه نوردی از کارآیی بیشتری برخوردار است، با این حال هر دو این روش ها از قرار گرفتن در بهینگی های محلی مصون نیستند. از اینرو نیاز به روش های دیگری داریم که بتوانند از بهینگی های محلی گذر کرده و به سمت بهینگی سراسری حرکت کنند. از جمله این روش ها می توان به روش Simulated Annealing ، Tabu Search و Threshold Acceptance اشاره کرد که در مقالات دیگری به بررسی هریک از این روش ها پرداخته ایم.

الگوریتم Simulated Annealing
روش SA یکی از روش های متاهیوریستیکی احتمالی است که ایده آن از عمل سرد کردن تدریجی فلزات برای استحاکم بیشتر آن ها نشات گرفته است. همانند روش های تپه نوردی و تپه نوردی تعمیم یافته ، در این روش نیز مسئله از یک حالت مانند S در فضای حالت مسئله شروع کرده و با گذر از حالتی به حالت دیگر به جواب بهینه مسئله نزدیک می شود. انتخاب حالت شروع هم می تواند به صورت تصادفی انجام پذیرد و هم می تواند بر اساس یک قاعده حالت اولیه مسئله را انتخاب کنیم. در اینجا نیز تابع Objective میزان بهینگی حالت فعلی را محاسبه کرده و Neighbor یک حالت همسایه برای حالت فعلی تولید می کند.

http://pnu-club.com/imported/mising.jpg

روش کلی کار به این صورت است که در هر تکرار ، الگوریتم SA حالت همسایه ای مانند s' ایجاد می کند و بر اساس یک احتمال ، مسئله از حالت s به حالت s' می رود و یا اینکه در همان حالت s باقی می ماند . این روند تا زمانی تکرار می شود که به یک جواب نسبتا بهینه برسیم یا اینکه ماکزیمم تعداد تکرار ها را انجام داده باشیم. همانطور که قبلا نیز بررسی کردیم نحوه تولید حالت همسایه از اهمیت به سزایی برخوردار است.
در روش کلی الگوریتم بیان کردیم که قبولی حالت همسایه تولید شده بر اساس یک احتمال صورت می پذیرد . تابع ( P(e,e',T تعیین کننده احتمال قبولی حالت همسایه می باشد . e بهینگی حالت فعلی و e' بهینگی حالت همسایه می باشد . در صورتی که حالت همسایه از حالت فعلی بدتر باشد ، مقدار پارامتر T تعیین کننده احتمال قبولی جواب می باشد . در ابتدای امر مقدار پارامتر T را طوری انتخاب می کنیم که اکثر حالت های همسایه را مورد پذیرش قرار دهیم ، پارامتر T نشانگر دما بوده و مقدار این پارامتر به تدریج کاهش می یابد . مقدار پارامتر T را طوری انتخاب می کنیم که قبل از انجام گرفتن ماکزیمم تعداد تکرارها ، مقدار آن تقریبا صفر گردد . مستنداتی که برای الگوریتم SA وجود دارد، نشان می دهند که در ابتدای امر مقدار T بهتر است به گونه ای تعیین گردد که در ابتدا 80% جواب ها مورد پذیرش الگوریتم واقع شود. روش کلی این الگوریتم به صورت زیر خواهد بود :

کد:

Procedure Simulated Annealing C = Choose an initial solution T = Choose an initial temperature REPEAT S' = Generate a neighbor of the solution C ΔE = objective( S' ) – objective( C ) IF (ΔE > 0 ) THEN // S' better than C C = S' ELSE with probability EXP( ΔE/ T ) C = S' END IF T = lower the T using linear/ non-linear techniques UNTIL meet the stop criteria End

در روش تپه نوردی برای گریز از بهینگی های محلی عمل جهش در فضای حالت را انجام دادیم . اما در روش SA به شکل دیگری به مقابله با این مشکل می پردازیم. در این روش وجود پارامتر T باعث می شود حتی در صورتی که بهینگی جواب همسایه بدتر از حالت فعلی باشد بر اساس مقدار T احتمال قبولی همین حالت نیز وجود دارد . قبول کردن جواب های غیربهینه باعث می شوند که این الگوریتم با موفقیت از بهینگی های محلی عبور کند.

در صورتی که e'< e باشد ، تابع P مقدار 1 برمی گرداند ( یعنی احتمال قبولی حالت همسایه 100% است ) . در غیر این صورت ( e'>e ) تابع P بر اساس مقدار T و اختلاف بین e' و e مقداری بین صفر و یک بر می گرداند که نشان دهنده احتمال قبولی حالت همسایه است .

در روش سرد کردن تدریجی فلزات ، برای استحکام هرچه بیشتر فلز ، دما به تدریج کاهش می یابد . در روش SA نیز مقدار T را به تدریج کاهش می دهیم . مقدار T به هرمیزانی که زیاد باشد ، باعث می شود که احتمال قبولی جواب های بد نیز بالا باشد . اما چون مقدار T رفته رفته کاهش می یابد ، بنابراین زمانی که مقدار T به اندازه کافی کم شد ( دما به اندازه کافی پایین آمد ) احتمال قبولی جواب های بد نیز به صفر میل می کند . از این لحظه به بعد فقط حالت هایی مورد پذیرش قرار می گیرند که هزینه آن ها بهتر از هزینه حالت فعلی باشند . به عبارت دیگر زمانی که مقدار T به صفر نزدیک شود ، در صورتی حالت همسایه به عنوان حالت فعلی انتخاب می شود که e' < e باشد . مقدار T باید به گونه ای انتخاب گردد که هنگام رسیدن به دمای صفر ، الگوریتم از بهینگی های محلی عبور کرده و در نزدیکی بهینگی سراسری قرار گرفته باشد.

برای کاهش دما، T را در یک ضریب همانند r که مقدار بین 0 و 1 دارد، ضرب می کنیم. کاهش دادن سریع دما موجب خواهد شد که همچنان با مشکل بهینگی های محلی مواجه باشیم. بنابراین مقدار این پارامتر را همیشه نزدیک به عدد 1 انتخاب می کنیم. ( مثلا 0.998 ). در الگوریتم SA انتخاب دما نقس بسیار زیادی در موفقیت الگوریتم دارد. انتخاب دمای اولیه بسیار بزرگ موجب کندی الگوریتم و انتخاب دمای کم موجب قرار گرفتن در نقاط بهینگی محلی می شود. استفاده از دمای بسیار زیاد در صورتی که مدت زمان کافی برای حل مساله داشته باشیم ، بهتر به نظر می رسد. با این حال هنگام پیاده سازی الگوریتم SA برای یک مساله خاص بهتر آن است که دمای اولیه الگوریتم با توجه به بزرگی مساله تعیین گردد. با اینکه مشکل بهینگی های محلی در الگوریتم SA حل شده است، با این حال در برخی مسائل هنگام استفاده از این الگوریتم به مشکلاتی بر خواهیم خورد. در الگوریتم SA ممکن است هنگام تولید حالت همسایگی به حالتی گذر کنیم که قبلا یکبار این حالت را مشاهده کرده ایم. البته نمی توان برگشت به حالت تکراری را مشکلی برای الگوریتم تلقی کرد. چرا که در برخی موارد همین برگشت به حالت قبلی ممکن است موجب بهبود الگوریتم گردد. اما برای رفع این مشکل نیز روش جستجوی Tabu پیشنهاد گردید که در ادامه به بررسی آن نیز می پردازیم.

الگوریتم Threhsold Acceptance قبل از شرح این روش جستجو پیشنهاد می کنیم در صورتی که با الگوریتم SA آشنایی ندارید، ابتدا مقاله مربوط به این روش جستجو را مطالعه کنید. روش TA نیز همانند روش SA می باشد و تنها تفاوت آن در نحوه قبول کردن جواب های غیر بهینه است. شبه کد زیر نحوه اجرای الگوریتم TA را نشان می دهد:
کد:

نقل قول:

Procedure Threhsold Acceptance
C = Choose an initial solution
T = Choose a positive initial threshold
REPEAT
S' = Generate a neighbor of the solution C
ΔE = objective( S' ) – objective( C )
IF (ΔE > -T ) THEN // S' better than C
C = S'
END IF
T = lower the T using linear/ non-linear techniques
UNTIL meet the stop criteria
End

الگوریتم TA جواب هایی را می پذیرد که از جواب قبلی خیلی بدتر نیستند. همانند کاری که دما در اگوریتم SA انجام می دهد. همانطور که در روش SA بررسی کردیم، دما در این الگوریتم باید به گونه ای انتخاب شود که بیشتر جواب های غیربهینه در ابتدا توسط الگوریتم پذیرفته شوند. این اصل در مورد روش TA نیز صادق است و در این روش نیز مقدار آستانه ( T ) باید به نحوه انتخاب گردد که بیشتر جواب های غیربهینه در ابتدا توسط الگوریتم مورد پذیرش واقع شوند.