بخشی از پاورپوینت

--- پاورپوینت شامل تصاویر میباشد ----

اسلاید 1 :

الگوریتم های جستجوی محلی

  • الگوريتم های قبلی، فضای جست و جو را به طور سيستماتيک بررسی ميکنند

–تا رسيدن به هدف يک يا چند مسير نگهداری ميشوند

–مسير رسيدن به هدف، راه حل مسئله را تشکيل ميدهد

  • در بسياري از مسائل بهينه سازي، مسير راه حل اهميت ندارد؛ خود حالت هدف پاسخ مسأله مي باشد.

–مانند 8 وزیر

  • در چنين مواردي مي توان از الگوريتم هاي جستجوي محلي بهره گرفت.
  • ایده جستجوی محلی: یک حالت (حالت فعلی) را در نظر بگیر، سعي كن آن را بهبود بخشي.
  • جستجوي محلي = استفاده از يك حالت فعلي و حركت به حالت هاي همسايه
  • • مزايا:
  • – استفاده از حافظه بسيار كم
  • – يافتن راه حل هاي معقول در اغلب موارد در فضاهاي حالت بزرگ و يا نامحدود
  • • مفيد براي مسائل بهينه سازي محض
  • يافتن بهترين حالت بر طبق تابع هدف: (objective function)

اسلاید 2 :

جست و جوی تپه نوردی

حلقه اي که در جهت افزايش مقدار حرکت ميکند(بطرف بالای تپه)

رسيدن به بلندترين قله در همسايگی حالت فعلی، شرط خاتمه است.

ساختمان داده گره فعلی، فقط حالت و مقدار تابع هدف را نگه ميدارد

جست و جوی محلی حريصانه نيز نام دارد

بدون فکر قبلي حالت همسايه خوبي را انتخاب ميکند

تپه نوردی به دلايل زير ميتواند متوقف شود:

بيشينه محلي

برآمدگي ها

فلات

اسلاید 3 :

انواع تپه نوردی:

تپه نوردی غيرقطعی،  تپه نوردی اولين انتخاب،  تپه نوردی شروع مجدد تصادفی

 

مثال: مسئله 8 وزير

مسئله 8 وزير با استفاده از فرمولبندی حالت کامل

در هر حالت 8 وزير در صفحه قرار دارند

تابع جانشين: انتقال يک وزير به مربع ديگر در همان ستون

تابع اکتشاف: جفت وزيرهايي که نسبت به هم گارد دارند

مستقيم يا غير مستقيم

اسلاید 4 :

مشکل اصلی تپه نوردی: بسته به حالت اوليه مسأله ممكن است در ماكزيمم محلي گير كند.

تپه نوردی به دلايل زير ميتواند متوقف شود:

بيشينه محلي: قله ای است که از تمام همسایه ها بلندتر است اما از قله اصلی، کوتاهتر است.

دماغه ها (مانند شکل بعد): دنباله ای از بیشینه های محلی که عبور از آنها مشکل است.

فلات: ناحیه ای است که در آن، تابع ارزیاب، ثابت است. یعنی همسایه بهتر وجود ندارد. ممکن است نتواند راه عبور از فلات را بیابد.

اسلاید 5 :

  • حالت فعلی، هر کدام از دایره های مشکی می باشند

اسلاید 6 :

جست و جوی تپه نوردی

  • انواع تپه نوردی

–تپه نوردی اتفاقی

  • به طور تصادفی از میان حرکت های رو به بالا یکی را انتخاب می کند. احتمال این انتخاب می تواند بر اساس شیب حرکت های رو به بالا تغییر کند.

–تپه نوردی اولین گزینه

  • اگر یک همسایه بهتر از حالت فعلی باشد به سمت آن حرکت می کند و به بررسی دیگر همسایه ها نمی پردازد (پس بهترین همسایه را انتخاب نمی کند)

–تپه نوردی با شروع مجدد تصادفی

  • چند حالت شروع تصادفی در نظر می گیرد و جستجو را در اطراف تک تک آنها انجام می دهد. هنگامی که یک هدف پیدا شد متوقف می شود.
  • موفقیت تپه نوردی بستگی به دورنمای فضای حالت دارد

– اگر تعداد کمی بیشینه محلی و فلات وجود داشته باشد، تپه نوردی با شروع مجدد تصادفی خیلی سریع یک راه حل خوب پیدا می کند.

اسلاید 7 :

جست و جوی سخت سازی شبيه سازی شده

  • ایده: از بهینه های محلی، با انجام حرکت های بد، فرار کن. اما به تدریج اندازه و تعداد حرکات بد را کم کن.
  • ترکیبی از تپه نوردی با حرکت تصادفی
  • پيشروي مانند تپه نوردي مي باشد، اما در هر مرحله حالت بعدي به طور تصادفي انتخاب مي شود.

–اگر حالت بعدي انتخاب شده بهتر باشد، همواره به آن حالت بعدي خواهيم رفت.

–در غير اين صورت، تنها با يك احتمال به آن حالت خواهيم رفت و اين احتمال به صورت نمايي كاهش مي يابد.

  • شبيه سازی حرارت:

–در متالوژی، سخت سازی فرایندی است که برای آب دادن فلزات و شیشه ها به کار می رود. ابتدا آنها را با درجه بالا حرارت می دهند و سپس به تدريج آنها را سرد می کنند که به ماده اجازه می دهد به شکل مورد نظر دربیاید.

  • مقايسه با حرکت توپ

–اگر توپ را رها کنیم تا قل بخورد، در یک کمینه محلی گیر می کند. اگر سطح را تکان دهیم می توانیم توپ را از کمینه محلی در بیاوریم. تکان مجدد باید به حدی باشد که توپ را از کمینه محلی در بیاورد ولی نتواند توپ را از کمینه اصلی (سراسری) خارج کند.

–بنابراین

  • ابتدا تکان شدید به توپ می دهیم (دمای زياد)
  • بتدريج تکان های کمتر (به دمای پايين تر)

اسلاید 8 :

جستجوی پرتویی محلی

  • به جای يک حالت، k حالت را نگهداری ميکند

1- حالت اوليه:شروع جستجو با k حالت تصادفی

2- گام بعد: پسین همه k حالت توليد ميشود

3- اگر يکي از پسین ها هدف بود، تمام ميشود

4- وگر نه از بین k حالت اولیه و k حالت تولید شده، k حالت بهتر را انتخاب می کند و به مرحله 2 برمی گردد

–تفاوت عمده با جستجوی شروع مجدد تصادفی

  • در جست و جوی شروع مجدد تصادفی، هر فرايند مستقل از بقيه اجرا ميشود
  • در جست و جوی پرتو محلی، اطلاعات مفيدی بين k فرايند موازی مبادله ميشود

اسلاید 9 :

الگوريتم های ژنتيک

شکلی از جست و جوی پرتویی که حالتهای جانشين از طريق ترکيب دو حالت والد توليد ميشود

اسلاید 10 :

الگوریتم ژنتیک

  • یک حالت بعدی با ترکیب دو حالت پدر ایجاد می شود.
  • شروع با k حالت تصادفی (جمعیت اولیه)
  • نمایش یک عضو جمعیت: کروموزوم
  • تابع ارزیابی: fitness function)) : هر حالت از جمعیت فعلی را ارزیابی می کند و عددی تولید می کند.
  • نسل بعدی جمعیت با انجام اعمال زیر روی جمعیت فعلی تولید می شود:

–انتخاب (selection)

–آمیزش (crossover)

–جهش (mutation)

در متن اصلی پاورپوینت به هم ریختگی وجود ندارد. برای مطالعه بیشتر پاورپوینت آن را خریداری کنید