وبلاگ

مراحل اجرای الگوریتم ژنتیک
پس از بیان مفاهیم اولیه، مراحل مختلف در استفاده از الگوریتم ژنتیک مورد بررسی قرار می گیرد. ابتدا با توجه به صورت مساله، متغیرهایی که باید تعیین شوند، مشخص می شوند. سپس این متغیرها به نحو مناسبی کد گذاری شده و به شکل کروموزوم نمایش داده می شوند. براساس تابع هدف، یک تابع برازندگی برای کروموزوم ها تعریف می گردد و یک جمعیت اولیه دلخواه نیز بطور تصادفی انتخاب میشود. به دنبال آن، میزان تابع برازندگی برای هر کروموزوم جمعیت اولیه حساب می شود. سپس مراحلی که در شکل ۳-۱۰ نمایش داده شده است به ترتیب زیر انجام می گیرد. آنچه که تاکنون به عنوان ساختار کلی الگوریتم ژنتیک ارائه شده است، توسط بیکر^[۱۴] و گرفنستت^[۱۵] ارائه گردیده است و خلاصه آن به صورت شکل ۳-۱۰ می باشد:

( اینجا فقط تکه ای از متن فایل پایان نامه درج شده است. برای خرید متن کامل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )

شکل ۳- ۱۰: مراحل اجرای الگوریتم ژنتیک
مرحله ١:
در این مرحله، تعداد مناسبی از زوج کروموزوم ها بر اساس میزان برازندگی آنها انتخاب می شوند تا درمراحل بعدی مورد استفاده قرار بگیرند. کروموزوم هایی که دارای عدد برازندگی بالایی هستند، ممکن است چندین بار در مراحل تولید انتخاب شوند، در حالیکه کروموزوم هایی که برازندگی آن ها کم می باشد، ممکن است هیچگاه انتخاب نگردند. ساده ترین روش برای اجرای این مرحله، استفاده از مدل چرخ رولت^[۱۶] است. در این مدل، سطح چرخ به بخش هایی تقسیم می شود که تعداد آن ها برابر با تعداد اعضای جمعیت و سطح هر بخش متناسب با مقدار برازندگی هر کروموزوم است. سپس چرخ به گردش درمی آید تا در نقطه ای به تصادف متوقف گردد. این نقطه، کروموزوم انتخاب شده را مشخص می سازد.
شکل ۳-۱۱ شمایی از چرخ رولت را نشان می دهد:
شکل ۳- ۱۱:چرخ رولت
در این شکل کروموزوم های ١ و ٢ دارای برازندگی بیشتری نسبت به کروموزوم های ٣ و ۴ هستند و بنابراین در مرحله انتخاب، شانس بیشتری دارند. این شیوه انتخاب سبب می شود که با گذشت زمان، تعداد کروموزوم های مطلوب در جمعیت افزایش یابد بطوریکه میانگین مقدار برازندگی جمعیت، درمقایسه با جمعیت مرحله قبل، بیشتر می شود. پیاده سازی مدل چرخ رولت در کامپیوتر، می تواند شامل مراحل زیر باشد:
کروموزوم های جمعیت به شکل دنباله درآورده می شوند. سپس مجموع مقدار برازندگی هر کروموزوم با مقدار برازندگی تمام کرموزوم های قبل از آن محاسبه می گردد. یک عدد تصادفی n بین صفر و مجموع برازندگی تمام کروموزوم های جمعیت ایجاد می شود. از بین کروموزوم ها، اولین کروموزومی که مقدار برازندگی آن به اضافه مقدار برازندگی همه کروموزوم های قبل از آن، بیشتر از n باشد، انتخاب می گردد. جدول ۳-۱ نمونه ای از انتخاب کروموزوم ها با بهره گرفتن از مدل چرخ رولت را نشان می دهد.
جدول ۳- ۱: انتخاب کروموزوم ها با بهره گرفتن از مدل چرخ رولت

۹

۸

۷

۶

۵

۴

۳

۲

۱

شماره کروموزوم

۳

۷

۱۱

۱۲

۲

۷

۱۷

۲

۸

برازندگی

۶۹

۶۶

۵۹

۴۸

۳۶

۳۴

۲۷

۱۰

۸

برازندگی کل