ترجمه طلایی کتاب فصل الگوریتم­های ژنتیک

فصل 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: