|
فرمت فایل: ورد –Word و قابل ویرایش
تعداد صفحات: 17
بر خلاف بسیاری از روشهای حل مساله که از همان فرم کلی مساله برای حل
مساله استفاده می¬کنند، برای اینکه بتوانیم یک مساله را بوسیله
الگوریتم¬های ژنتیک حل کنیم، بایستی آنرا به فرم مخصوص مورد نیاز این
الگوریتم¬ها تبدیل کنیم.
در این روند ما بایستی راه حل مورد نیاز مساله را به گونه¬ای تعریف کنیم
که قابل نمایش بوسیله یک کروموزوم باشد. این کروموزوم می¬تواند یک آرایه
از اعداد، رشته¬ها و یا بیتها باشد، یا اینکه یک عدد طبیعی، یا حقیقی و ...
باشد. اما به طور کلی بایستی به گونه¬ای تعریف شود که بتوانیم عملگرهای
خاص الگوریتم¬های ژنتیک که بازترکیبی، جهش و ارزیابی هستند را برروی
کروموزوم¬ها تعریف و اعمال کنیم.
به عنوان مثال در یک مساله مرتب سازی، کروموزوم را می¬توانیم به این شکل
تعریف کنیم که بعنوان مثال از چپ به راست، اندیس عناصر از کوچک به بزرگ را
نگهداری کند. که در این حالت سمت چپ¬ترین عنصر، اندیس کوچک¬ترین و سمت
¬راست¬ترین عنصر، اندیس بزرگترین عنصر آرایه باشد.
اینکه مساله خود را چگونه بازنمائی کنیم بسیار مهم است، چرا که یک
بازنمائی خوب می¬تواند سرعت پیدا شدن جواب را افزایش دهد. علاوه بر اینکه
در میزان مصرف حافظه و سرعت اعمال عملگرهای ژنتیک تاثیر فراوانی دارد. علت
این امر نیز این است که هر یک از عملگرهای ژنتیک بایستی هزاران بار، در طول
اجرای الگوریتم بر روی کروموزوم¬های مختلف اعمال شوند.
اینکه چه نوع بازنمائی را برای مساله استفاده شود، به شخص طراح و فرم
مساله بستگی دارد. در زیر چند نمونه از بازنمائی¬هایی را که معمولاً
استفاده می¬شوند را تعریف می¬کنیم:
- اعداد صحیح
- رشته¬¬های بیتی
- اعداد حقیقی در فرم نقطه شناور
- اعداد حقیقی به فرم رشته های بیتی
- یک مجموعه از اعداد حقیقی یا صحیح
- ماشینهای حالت محدود
- هر فرم دیگری که بتوانیم عملگرهای ژنتیک را بر روی آنها تعریف کنیم
تشکیل جمعیت اولیه
بعد از اینکه شکل کروموزومها را تعریف نمودیم، بایستی جمعیتی را تشکیل
دهیم، که می¬خواهیم عناصر آنرا تکامل دهیم. تعداد عناصر موجود در این جمعیت
معمولاً ثابت است. به این معنی که هنگامی که تعدادی عنصر در جریان تولید
مثل به این جمعیت اضافه می¬کنیم، بایستی به همین تعداد عنصر نیز از جمعیت
قبلی حذف کنیم.
قبل از اینکه الگوریتم بتواند آغاز به کار کند، بایستی یک جمعیت اولیه
از کروموزوم¬ها تشکیل بدهیم. در اکثر الگوریتم¬ها این جمعیت اولیه به صورت
تصادفی تشکیل می¬شود. به این معنی که به اندازه طول جمعیت، کروموزوم تصادفی
ایجاد می¬کنیم و آنها را به جمعیت اولیه اضافه می¬کنیم.
البته برای اینکه الگوریتم سریعتر به جواب برسد، می¬توانیم بوسیله یکی
از الگوریتم¬های کم هزینه تعدادی از جوابهای تقریباً بهینه را محاسبه کرده و
از آنها بعنوان جمعیت اولیه استفاده می¬کنیم. دیده شده است که در بعضی
مسائل انجام این عمل تاثیر بسزائی در سرعت همگرائی الگوریتم دارد. البته
نباید فراموش کنیم که انجام این عمل در مواردی باعث می شود، الگوریتم در
مینیمم¬های محلی ناشی از جمعیت آغازی گیر افتاده و نتواند جوابهای بهتری را
پیدا کند. برای جلوگیری از این مشکل علاوه بر جوابهای بهینه پیدا شده،
تعدادی عنصر نیز به صورت تصادفی به جمعیت اضافه می¬کنیم.
ارزیابی جمعیت
برای اینکه بتوانیم موجودات بهتر را درون جمعیت تشخیص بدهیم بایستی معیاری را تعریف کنیم که بر اساس آن موجودات بهتر را تشخیص دهیم.
به این کار، یعنی تعیین میزان خوبی یک موجود، ارزیابی آن موجود
می¬گویند. ارزیابی، اینگونه است که بر حسب اینکه موجود چقدر خوب است یک عدد
به آن نسبت می¬دهیم، این عدد که برای موجودات بهتر بزرگتر (یا کوچکتر) است
را شایستگی آن موجود می¬نامیم.
به عنوان مثال در صورتی که به دنبال مینیمم یک تابع هستیم، مقدار
شایستگی را می¬توانیم مقدار خروجی تابع به ازای ورودی مشخص باشد. همانطور
که می¬بینید، هدف ما پیدا کردن مینیمم تابع است، پس ورودیهایی که مقادیر
تابع برای آنها کمتر است، ورودیهای بهتری هستند.
بسته به نوع مساله ما می¬خواهیم شایستگی را بیشینه و یا کمینه کنیم.
البته معمولاً در مطالعات تئوری فرض بر این گذاشته می¬شود که می¬خواهیم
مقدار شاسیتگی را کمینه کنیم.
در مطالب این فصل تعاریف به گونه¬ای ارائه شده¬اند که در آنها سعی در
مینیمم کردن یک تابع داریم، اما شایستگی عناصر به گونه¬ای تعریف شده¬ است
که برای عناصر کوچکتر، مقادیر بزرگتری ارائه می¬دهد.
انتخاب والدین
|