الگوریتم ژنتیک یکی از الگوریتم های پرکاربرد در زمینه بهینه سازی مسائل مهندسی است. در این مطلب به ادامه آموزش این الگوریتم می پردازیم.
سرویس آموزش و آزمون برق نیوز:
اگر پیوند را از نقطه ۴ آغاز کنیم داریم
تذکر
عمل پیوندی که در فوق انجام شد به نام تقاطع یک نقطهای مینامند مکانیزمهای تقاطع را میتوان به صورت زیر بیان کرد:
- ۱ تقاطع ساده یا یک نقطه ای:
در این روش یک نقطه تقاطع انتخاب میشوند و بیتهای متناظر جابجا میشوند. که مثال آن آورده شد
- ۲ تقاطع n. نقطه ای: n> ۱
n. محل به طور تصادفی انتخاب میشود و هر والد را به n+ ۱ قطعه تقسیم میکند تکهای فرد از والد اول و تکه زوج از والد دوم در محلهای متناظر در فرزند قرار میگیرد. اکثر محققین مقدار زوج را برای n. ترجیح میدهند.
مثال: n. = ۲،
تذکر
عمل پیوندی که در فوق انجام شد به نام تقاطع یک نقطهای مینامند مکانیزمهای تقاطع را میتوان به صورت زیر بیان کرد:
- ۱ تقاطع ساده یا یک نقطه ای:
در این روش یک نقطه تقاطع انتخاب میشوند و بیتهای متناظر جابجا میشوند. که مثال آن آورده شد
- ۲ تقاطع n. نقطه ای: n> ۱
n. محل به طور تصادفی انتخاب میشود و هر والد را به n+ ۱ قطعه تقسیم میکند تکهای فرد از والد اول و تکه زوج از والد دوم در محلهای متناظر در فرزند قرار میگیرد. اکثر محققین مقدار زوج را برای n. ترجیح میدهند.
مثال: n. = ۲،
۳ -تقاطع یکنواخت
در این روش یک رشته به طول رشته والد انتخاب میشود. (mosk) و از اعداد تصادفی پرمی گردد.
اگر عدد از Pm کمتر باشد در (mosk) صفر قرار میگیرد و اگر بیشتر باشد یک قرار میگیرد. اگر بیت (mosk) صفر باشد رشته جدید از والد اول بیت بر میدارد؛ و اگر ۱ باشد از والد دوم برمی دارد. این روش روی تک تک بیتها اعمال میشود.
تقاطع در هم آمیخته
نتیجهای مانند تقاطع یکنواخت را میتوان به وسیله در هم آمیختن ژنها در رشتههای والد با استفاده از ترتیب شمارشی مشابهی و سپس انجام عمل تقاطع ساده بدست آورد فرزند با معکوس ترتیب شمارشی از درهم آمیختگی خارج میگردد.
برای بهتر بیان کردن مثال این مثال را با حروف آلفابت به جای صفر و یک مینویسیم:
حال دو کروموزوم فرزند را به روش تقاطع ساده با نقطه تقاطع مثلا ۵، تقاطع میدهیم:
قدم نهم: جهش (mutation)
جهش یکی از پدیدههای علم ژنتیک که به ندرت در برخی از کروموزومها رخ میدهد؛ و در طی آن فرزندان خصوصیاتی پیدا میکنند که متعلق به هیچ یک از والدین نمیباشد.
نقش جهش در الگوریتم ژنتیک بازگرداندن مواد ژنتیکی گم شده و یا پیدا نشده داخل جمعیت است. تا از همگرایی زودرس الگوریتم به جوابهای بهینه محلی جلوگیری شود. در جهش یکسری از ژنها را به طور تصادفی برگزیده صفرها را به یک و یکها را به صفر تبدیل میکنیم یکی از روشهای جهش بدین صورت است که ابتدا با توجه به یک عدد کوچکتر از یک به نام احتمال جهش برای هر ژن از جمعیت یک عدد تصادفی فراخوانی میشود اگر این عدد تصادفی از احتمال جهش کوچکتر بود در آن ژن جهش رخ میدهد.
تذکر ۱:، چون عمل جهش در طبیعت به ندرت رخ میدهد لذا در الگوریتم ژنتیک هم با احتمال بسیار کم کمتر از (0.5) عمل جهش را انجام میدهیم همان طور که گفته شد مزیت عملگر جهش اینست که توان دسترسی به همه فضای جستجو را به ما میدهد.تذکر ۲: در صورتی که کاراکترها اعداد پیوسته باشند جهش را میتوان به صورت نمو تصادفی مثبت یا منفی حول مقدار قبلی کاراکتر انجام داد این نوع جهش را جهش خزنده مینامند.
تذکر ۳: انواع دیگر جهش از نظر ژنتیک عبارتند از:
۱ - موتاسیون در ژنوم که در آن تعداد کروموزوم تغییر میکند.
۲ - موتاسیون در کروموزوم که در آن شکل کروموزوم تغییر میکند.
۱ - موتاسیون در ژن در روی کروموزومها ژن تغییر میکند.
قدم دهم: حفظ بهترین کروموزوم
تا اینجا تولید جمعیت جدید خاتمه مییابد اکنون برای آنکه بهترین کروموزوم نسل قبل را از دست ندهیم آنرا بطور دستی در جای بدترین کروموزوم نسل جدید قرار میدهیم.
رهیافت دیگری برای حفظ بهترین کروموزوم که در این پروژه از آن استفاده شده است اینست که جمعیت جدید و جمعیت قبلی را با هم در آمیخته کرده و سپس آنها را بر حسب برازندگیشان از بزرگ به کوچک طبقه بندی میکنیم سپس p. (برابر با تعداد جمعیت) کروموزوم اول جمعیت که از همه برازندگیشان بیشتر است به عنوان جمعیت جدید بر میگزینیم.
در این روش جمعیت با میانگین برازندگی بالاتری تشکیل میگردد و به جای انتقال بهترین کروموزوم و حذف بدترین کروموزوم دستهای از بهترین کروموزومها جای دستهای از بدترین کروموزومها را میگیرند. با این عمل همگرایی (converg) به سمت عدد بهینه در اجرای الگوریتم سریعتر و زمان اجرای برنامه (run time) تا یافتن جواب مناسب کاهش مییابد.
قدم یازدهم:
حال جمعیت جدید تولید شده است که میانگین برازندگی آن از نسل قبلی بهتر است حال با این جمعیت مجددا مراحل قبل را از قدم چهارم تا یازدهم تکرار کرده و این اعمال را آنقدر انجام میدهیم تا به مقدار بهینه دست پیدا کنیم.
لینک کوتاه
نظرات بینندگان
انتشار یافته: ۱
در انتظار بررسی: ۰
غیر قابل انتشار: ۰
بسیار عالی
کارم واقعا راه افتاد چون کاملا با جزئیات فرموده بودید که هر فرد مبتدیی هم متوجه میشه.
بسی سپاس
کارم واقعا راه افتاد چون کاملا با جزئیات فرموده بودید که هر فرد مبتدیی هم متوجه میشه.
بسی سپاس
ارسال نظر قوانین ارسال نظر
لطفا از نوشتن با حروف لاتین (فینگلیش) خودداری نمایید.
از ارسال دیدگاه های نا مرتبط با متن خبر، تکرار نظر دیگران، توهین به سایر کاربران و ارسال متن های طولانی خودداری نمایید.
لطفا نظرات بدون بی احترامی، افترا و توهین به مسئولان، اقلیت ها، قومیت ها و ... باشد و به طور کلی مغایرتی با اصول اخلاقی و قوانین کشور نداشته باشد.
در غیر این صورت، «برق نیوز» مطلب مورد نظر را رد یا بنا به تشخیص خود با ممیزی منتشر خواهد کرد.
از ارسال دیدگاه های نا مرتبط با متن خبر، تکرار نظر دیگران، توهین به سایر کاربران و ارسال متن های طولانی خودداری نمایید.
لطفا نظرات بدون بی احترامی، افترا و توهین به مسئولان، اقلیت ها، قومیت ها و ... باشد و به طور کلی مغایرتی با اصول اخلاقی و قوانین کشور نداشته باشد.
در غیر این صورت، «برق نیوز» مطلب مورد نظر را رد یا بنا به تشخیص خود با ممیزی منتشر خواهد کرد.