دسته: مقالات ترجمه شده isi
بازدید: 328 بار
فرمت فایل: doc
حجم فایل: 884 کیلوبایت
تعداد صفحات فایل: 19
فصل 6
الگوریتمهای ژنتیک
6.1. اهداف
پس از مطالعهی این فصل بایستی بتوانید:
1) GA را توصیف کنید.
2) GA ساده را پیادهسازی کنید.
3) محدودیتهای GA ساده بدانید.
4) PBIL، جستجوی ممنوع و GA منظم را توصیف کنید.
5) دشواری کدنویسی مسائل خاص را بدانید.
6) نواحی مسالهی نوعی را توضیح دهید.
6.2. بهینه سازی
روشهای موجود در این فصل برای تامین نیازمندی روشهای با هدف کلی و به منظور حل مسائل بهینهسازی پیچیده ایجاد شدند. مسالهی خاصی که در اینجا بررسی میشود مساله فروشندهی دورهگرد هست که در آن فروشنده بایستی هر کدام از n شهر را یکبار و فقط یکبار به ترتیب بهینه ببیند – که مسافرت او را بهینه میکند. دو روش قدیمی برای کار بر روی مسائل بهینهسازی وجود دارد:
شمارهگذاری: اساسا تمام فضای جستجو برای برخی توابع بهینهسازی و برای یافتن بهترین نقطه با توجه به این تابع بررسی میشود. این امر ممکن استبرای مسائل اساسی فرآیند بسیار طولانی باشد.
روشهای مبتنی بر محاسبات: میتوانیم این روشها را به دو دسته زیر تقسیم کنیم:
- روشهای مستقیم که از گرادیان هر نقطه در فضا برای هدایت به جستجوی بعدی استفاده میکنند. این روشها قابل مقایسه با روشهای زیرشاخهی خطاست که قبلا استفاده کردیم و در مسائل با رفتار-مناسب کارا هستند (مسائلی که برای آنها هیچ مینیمم محلی وجود نداشته و دارای توابع هزینه پیوسته هستند).
- روشهای غیرمستقیم که تلاش میکنند مجموعهی معادلات دیفرانسیل غیر خطی را برای بدست آوردن نقاطی که در آنجا گرادیان برابر صفر است یعنی نقاط ثابت تابعِ ارزیابی حل کنند. یافتن چنین پاسخهایی اغلب دشوار و حتی غیر ممکن است.
6.1 Objectives
After this Chapter, you should
1. be able to describe the GA.
2. be able to implement a simple GA.
3. understand the limits to the simple GA.
4. be able to describe PBIL, Tabu search and the Structured GA.
5. understand the difficulty found coding certain problems.
6. describe typical problem areas.
6.2 Optimisation
The methods in this chapter were developed in response to the need for general purpose methods for solving complex optimization problems. A typical problem addressed is the Ravening Salesman Problem in which a salesman must visit each of n cities once and only once in an optimum order - that which minimizes his travelling. There are two traditional methods for tackling optimization problems: