تحقیق مقاله آشنائی با الگوریتم های ژنتیک

آشنائی با الگوریتم­های ژنتیک

همانطور که گفتیم یکی از شاخه­های پردازش تکاملی، الگوریتم­های ژنتیک می­باشد. این الگوریتم­ها با الهام از روند تکاملی طبیعت، مسائل را حل می­کنند. به این معنی که مانند طبیعت یک جمعیت از موجودات تشکیل می­دهند و درون این موجودات اقدام به انجام اعمالی چون انتخاب والدین، تولید مثل، جهش و ... می­کنند و این اعمال را آنقدر تکرار می­کنند تا به مجموعه بهینه و یا موجود بهینه برسند.

این الگوریتم­ها با توجه به خصوصیات خاصی که دارند، به خوبی از عهده حل مسائلی که نیاز به بهینه­سازی دارند و یا پارامترهای زیادی در آنها دخیل است، برمی­آیند. در این قسمت به معرفی این الگوریتم­ها می­پردازیم.

تشریح ساختار الگوریتم­های ژنتیک

روند اجرای الگوریتم­ های ژنتیک به صورت زیر است:

انتخاب والدین

همانطور که می­بینید، برای حل یک مساله با استفاده از الگوریتم­های ژنتیک بایستی مراحل زیر را طی کنیم:

1.     مدل سازی مساله یا بازنمائی

2.     تشکیل جمعیت اولیه

3.     ارزیابی جمعیت

4.     انتخاب والدین

5.     بازترکیبی

6.     جهش

7.     انتخاب فرزندان

8.     شرط خاتمه الگوریتم

در ادامه به تشریح هر یک از قسمتهای این الگوریتم­ها می­پردازیم.

مدلسازی مساله یا بازنمائی

بر خلاف بسیاری از روشهای حل مساله که از همان فرم کلی مساله برای حل مساله استفاده می­کنند، برای اینکه بتوانیم یک مساله را بوسیله الگوریتم­های ژنتیک حل کنیم، بایستی آنرا به فرم مخصوص مورد نیاز این الگوریتم­ها تبدیل کنیم.

در این روند ما بایستی راه حل مورد نیاز مساله را به گونه­ای تعریف کنیم که قابل نمایش بوسیله یک کروموزوم باشد. این کروموزوم می­تواند یک آرایه از اعداد، رشته­ها و یا بیتها باشد، یا اینکه یک عدد طبیعی، یا حقیقی و ... باشد. اما به طور کلی بایستی به گونه­ای تعریف شود که بتوانیم عملگرهای خاص الگوریتم­های ژنتیک که بازترکیبی، جهش و ارزیابی هستند را برروی کروموزوم­ها تعریف و اعمال کنیم.

به عنوان مثال در یک مساله مرتب سازی، کروموزوم را می­توانیم به این شکل تعریف کنیم که بعنوان مثال از چپ به راست، اندیس عناصر از کوچک به بزرگ را نگهداری کند. که در این حالت سمت چپ­ترین عنصر، اندیس کوچک­ترین و سمت ­راست­ترین عنصر، اندیس  بزرگترین عنصر آرایه باشد.

اینکه مساله خود را چگونه بازنمائی کنیم بسیار مهم است، چرا که یک بازنمائی خوب می­تواند سرعت پیدا شدن جواب را افزایش دهد. علاوه بر اینکه در میزان مصرف حافظه و سرعت اعمال عملگرهای ژنتیک تاثیر فراوانی دارد. علت این امر نیز این است که هر یک از عملگرهای ژنتیک بایستی هزاران بار، در طول اجرای الگوریتم بر روی کروموزوم­های مختلف اعمال شوند.

اینکه چه نوع بازنمائی را برای مساله استفاده شود، به شخص طراح و فرم مساله بستگی دارد. در زیر چند نمونه از بازنمائی­هایی  را که معمولاً استفاده می­شوند را تعریف می­کنیم:

< >اعداد صحیحرشته­­های بیتی اعداد حقیقی در فرم نقطه شناوراعداد حقیقی به فرم رشته های بیتییک مجموعه از اعداد حقیقی یا صحیحماشینهای حالت محدودهر فرم دیگری که بتوانیم عملگرهای ژنتیک را بر روی آنها تعریف کنیم 

تشکیل جمعیت اولیه

بعد از اینکه شکل کروموزومها را تعریف نمودیم، بایستی جمعیتی را تشکیل دهیم، که می­خواهیم عناصر آنرا تکامل دهیم. تعداد عناصر موجود در این جمعیت معمولاً ثابت است. به این معنی که هنگامی که تعدادی عنصر در جریان تولید مثل به این جمعیت اضافه می­کنیم، بایستی به همین تعداد عنصر نیز از جمعیت قبلی حذف کنیم.

قبل از اینکه الگوریتم بتواند آغاز به کار کند، بایستی یک جمعیت اولیه از کروموزوم­ها تشکیل بدهیم. در اکثر الگوریتم­ها این جمعیت اولیه به صورت تصادفی تشکیل می­شود. به این معنی که به اندازه طول جمعیت، کروموزوم تصادفی ایجاد می­کنیم و آنها را به جمعیت اولیه اضافه می­کنیم.

البته برای اینکه الگوریتم سریعتر به جواب برسد، می­توانیم بوسیله یکی از الگوریتم­های کم هزینه تعدادی از جوابهای تقریباً بهینه را محاسبه کرده و از آنها بعنوان جمعیت اولیه استفاده می­کنیم. دیده شده است که در بعضی مسائل انجام این عمل تاثیر بسزائی در سرعت همگرائی الگوریتم دارد. البته نباید فراموش کنیم که انجام این عمل در مواردی باعث می شود، الگوریتم در مینیمم­های محلی ناشی از جمعیت آغازی گیر افتاده و نتواند جوابهای بهتری را پیدا کند. برای جلوگیری از این مشکل علاوه بر جوابهای بهینه پیدا شده، تعدادی عنصر نیز به صورت تصادفی به جمعیت اضافه می­کنیم.

ارزیابی جمعیت

برای اینکه بتوانیم موجودات بهتر را درون جمعیت تشخیص بدهیم بایستی معیاری را تعریف کنیم که بر اساس آن موجودات بهتر را تشخیص دهیم.

به این کار، یعنی تعیین میزان خوبی یک موجود، ارزیابی آن موجود می­گویند. ارزیابی، اینگونه است که بر حسب اینکه موجود چقدر خوب است یک عدد به آن نسبت می­دهیم، این عدد که برای موجودات بهتر بزرگتر (یا کوچکتر) است را شایستگی آن موجود می­نامیم.

به عنوان مثال در صورتی که به دنبال مینیمم یک تابع هستیم، مقدار شایستگی را می­توانیم مقدار خروجی تابع به ازای ورودی مشخص باشد. همانطور که می­بینید، هدف ما پیدا کردن مینیمم تابع است، پس ورودیهایی که مقادیر تابع برای آنها کمتر است، ورودیهای بهتری هستند.

بسته به نوع مساله ما می­خواهیم شایستگی را بیشینه و یا کمینه کنیم. البته معمولاً در مطالعات تئوری فرض بر این گذاشته می­شود که می­خواهیم مقدار شاسیتگی را کمینه کنیم.

در مطالب این فصل تعاریف به گونه­ای ارائه شده­اند که در آنها سعی در مینیمم کردن یک تابع داریم، اما شایستگی عناصر به گونه­ای تعریف شده­ است که برای عناصر کوچکتر، مقادیر بزرگتری ارائه می­دهد.

انتخاب والدین

در هر نسل تعدادی از عناصر جمعیت این فرصت را پیدا می­کنند که تولید مثل کنند. به این عناصر که از میان جمعیت انتخاب می­شوند، والدین می­گویند. روشهای مختلفی برای انتخاب والدین وجود دارند. در زیر به چند مورد از این روشها اشاره می­کنیم:

< >انتخاب تمام جمعیت بعنوان والدین: در واقع هیچگونه انتخابی انجام نمی­دهیم.انتخاب تصادفی: بصورت تصادفی تعدادی از موجودات جمعیت را بعنوان والدین انتخاب می­کنیم، این انتخاب می­تواند با جایگذاری یا بدون جایگذاری باشد.روشهای مبتنی بر شایستگی: در این روشها عناصر با شایستگی بیشتر شانس بیشتری برای انتخاب شدن بعنوان والدین را دارند. سایر روشها: این روشها با استفاده از تکنیکهایی سعی می­کنند که انتخابهایی را ارائه دهند، که هم رسیدن به جواب نهایی را تسریع کنند و هم اینکه کمک می­کنند که جواب بهینه­تری پیدا شود.باز ترکیبی (Recombination)

همانطور که می­دانیم یک کروموزوم در طبیعت از تعداد زیادی ژن تشکیل شده است، که یک ژن یا ترکیبی از این ژنها یکی از خصوصیات موجود را معرفی می­نمایند. بعنوان مثال یک ژن رنگ چشم، ژن دیگر شکل چشم و ... را نشان می­دهند.

در حین عملیات تشکیل سلول تخم، کروموزوم­های والدین با یکدیگر ترکیب می­شوند و کروموزوم­های جدیدی را بوجود می­آورند، در جریان این کار به صورت اتفاقی بخشهایی از کروموزوم­ها با یکدیگر عوض می­شوند. این موضوع باعث می­شود که فرزندان ترکیبی از خصوصیات والدین خود را به همراه داشته باشند و دقیقاً مشابه یکی از والدین نباشند.

(نمودار و تصاویر در فایل اصلی موجود است)