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

معمای هشت وزیر

معمای هشت وزیر یکی از مسایل کلاسیک و متداول برای سنجش توانایی الگوریتم‌های جستجو است. در این معمای قدیمی، باید هشت مهره وزیر شترنج به‌گونه‌ای بر صفحه چیده شوند، که هیچ‌یک در تیررس دیگری قرار نگیرند. شکل زیر یکی از این حالت‌ها را نمایش می‌دهد.

این مساله پاسخ‌های بسیار دارد. ابتدایی‌ترین راه‌حل برای حل چنین مساله‌ای استفاده از 8 حلقه تودرتو با شمارنده 64 تایی (برای هشت مهره که هر کدام امکان جایگیری بر هر یک از 64 خانه صفحه شترنج را دارند) برای تولید همه حالت‌های ممکن جانشانی مهره‌ها بر صفحه و سپس آزمون هر یک از آن حالت‌ها برای یافتن پاسخ‌های احتمالی است. اما روشن است که چنین روشی، انبوهی از حالت‌ها را پدید می‌آورد (1014*8/2 =648) حالت که بسیاری از آنها، مانند شکل زیر، به‌طور بدیهی پاسخ نیستند.

چنین مساله‌ای، با وجود آن‌که پاسخ‌های متناهی دارد، در زمره مسایل بی‌پایان(NP-Completeness)  می‌گنجد و اگر فرض کنیم که کامپیوتر برای تولید و مقایسه هر حالت، تنها به یک‌هزارم ثانیه زمان نیاز داشته باشد، باز هم به بیش از 9000 سال زمان برای آزمون کل حالت‌ها نیاز خواهد داشت!
افزودن یک آگاهی کوچک و ساده به برنامه، پاسخ را در دسترس قرار می‌دهد: این‌که در هر ستون تنها یک مهره قرار گیرد. بنابر این تعداد حالت‌ها را میلیون‌ها بار کاهش می‌دهد (  8107=1/7x8حالت) و مساله را قابل حل می‌سازد (این بار کامپیوتر ما به کمتر از 5 ساعت زمان نیاز دارد!). اما هنوز می‌توان با ارایه فنون ویژه، از این زمان کاست.
برای حل چنین مساله‌ای، روش‌ها و تکنیک‌های بسیاری پیشنهاد می‌شود. اما یکی از جالب‌ترین و البته سریع‌ترین روش‌ها برای دستیابی به یکی از پاسخ‌ها، همان الگوریتم ژنتیک است. بیایید مساله را با الگوریتم ژنتیک مدل‌سازی کنیم.

جمعیت آغازین‌

فرض کنید که 4 حالت اتفاقی از قرار گرفتن مهره‌ها بر صفحه (مشروط بر این‌که هیچ‌یک از آنها در ستون مهره دیگر قرار نگیرد.) مانند شکل‌های زیر تولید کرده‌ایم.

برای سادگی در نمایش، می‌توان هریک از این حالت‌ها را به‌صورت زیر نمایش داد و آن را ساختار ژنتیکی هر یک از اعضای گروه در نظر گرفت:

ghdbegca- 1

ddahfceg- 2

 caehffch- 3

 afddhafb- 4

اینها اعضای اولیه جامعه ما هستند که پی از آمیزش با یکدیگر، نسل‌های بعدی را به‌وجود می‌آورند؛ تا جایی که یکی از اعضا پاسخ دلخواه مساله باشد.

تابع برازندگی‌

تدوین تابع برازندگی، اغلب سخت‌ترین کار در حل مسایل به‌کمک الگوریتم ژنتیک است. طراحان، بسته به سلیقه یا توانایی فکری خود، ممکن است راه‌حل‌هایی گوناگون را برای طراحی تابع برازندگی چنین مساله‌ای ارایه دهند. در اینجا ما یک روش ساده را به‌کار می‌گیریم؛ به‌گونه‌ای که هر عضو به ازای هر یک از حالت‌های برخورد، یک نمره منفی دریافت کند. در زیر نمره منفی هر یک از کروموزوم‌ها به‌همراه نقشه یکی از آنه درج شده است.
 (5 [ghdbegca  (1]
 (6[ caehffch  (2]
 (3[ ddahfceg  (3]
 (7[ afddhafb  (4]

به‌یاد داشته باشید که بدترین حالت (همه مهره‌ها بر یک خط قرار گیرند) 28 نمره منفی خواهد داشت و هر یک از پاسخ‌ها صفر نمره منفی. با این حساب، روشن است که ساختار چهارم بهترین و ساختار سوم بدترین کروموزوم‌ها برای آمیزش هستند و می‌توان احتمال مشارکت در تولید نسل آینده را برای هر یک از آنها (بر پایه تابع برازندگی یاد شده در بالا) چنین نوشت:
(125[ ghdbegca  (%]
(224[ ddahfceg  (%]
(328[ caehffch  (%]
(423[ afddhafb  (%]

آمیزش‌

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

1[ ghd-begca + ]4[ cae-hffch  =]
5[ ghd-hffch  ]6[ cae-begca ]

2[ ddah-fceg + ]4[ caeh-ffch  =]
7[ ddah-ffch  ]8[ caeh-fceg ]

جهش ژنتیکی‌

اکنون فرض کنید که به‌طور تصادفی بر روی ژن هفتم از کروموزوم پنجم و ژن ششم از کروموزوم هفتم، یک جهش ژنتیکی نیز به‌صورت زیر رخ می‌دهد:

5[ ghd-hffgh  ]
7[ ddah-fbch  ]
حال 4 عضو نوپدید را به جمعیت اولیه می‌افزاییم و پس از به‌دست آوردن نمرات منفی (تعداد برخوردها)، مقادیر تابع برازندگی را مشخص می‌کنیم:

(5[ ghdbegca  (1]
(6[ ddahfceg  (2]
 (3[ caehffch  (3]
(7[ afddhafb  (4]
 (11[ ghd-hffgh  (5]
(6[ cae-begca  (6]
 (4[ ddah-fbch  (7]
(5[ caeh-fceg  (8]
این کار تا آنجا ادامه می‌یابد که یکی از تعداد برخورد مهره‌های یکی ازساختارها به‌صفر برسد. اما شگفت این است که الگوریتم ژنتیک این مساله را سریع‌تر از روش‌های دیگر به پاسخ می‌رساند. می‌گویید نه؟! امتحان کنید!

برای دریافت اطلاعات بیشتر ر.ک. به:

 Stuart J. Russell And PeterNorvig, -
Artificial Intelligence:A Modern Approach,
.1994 Prentice-Hall International Inc,
 Steven L. Tanimoto, The Elements of-
 Artificial  Intelligence Using Common Lisp,
  .1995nd Edition,2Computer Science Press, 
Mitchel T. M., Machine Learning,
.1997 McGraw-Hill,-
- http://en.wikipedia.org/wiki/Search-algorithm

امیرشهاب شاهمیری‌