این عملگر شبیه به عملگر دو نقطهای است، با این تفاوت که به جای دو نقطه، چند نقطه برای تقاطع انتخاب میگردد. تقاطع در بخشهای شکسته شده دو کروموزوم به صورت یک در میان انجام میگیرد.
۴-۳-۶-۴) تقاطع یکنواخت:
براساس این عملگر، یک ژن از هر دو الد به طور مستقل از سایر ژنها، شانس برابر برای حضور در کروموزوم یک فرزند را دارند. در این حالت، براساس یک توزیع تصادفی باینری مشخص میگردد که یگ ژن از کدام والد انتخاب گردد. مثلاً اگر توزیع باینری ۱ را نشان داد، آن ژن از والد اول و اگر ۰ بود از والد دوم انتخاب میگردد. این عمل برای تمامی ژنهای یک فرزند انجام میگردد. در نتیجه، فرزندان ترکیبی از ژنهای والدین خواهند بود. شکل ۴-۶ یک مثال از تولید فرزندان با بهره گرفتن از عملگر تقاطع یکنواخت را نشان میدهد. در این شکل، در صورتی که عدد تصادفی ۱ باشد، ژن فرزند از والد اول و در صورتی که صفر باشد، از والد دوم انتخاب میگردد. برای فرزند دوم، عکس فرزند اول در نظر گرفته شده است.
۱ ۰ ۱ ۱ ۰ ۰ ۱ ۱ | والد ۱ |
۰ ۰ ۰ ۱ ۱ ۰ ۱ ۰ | والد ۲ |
۱ ۱ ۰ ۱ ۰ ۱ ۱ ۰ | مقدار تصادفی |
۱ ۰ ۰ ۱ ۱ ۰ ۱ ۰ | فرزند ۲ |
۰ ۰ ۱ ۱ ۰ ۰ ۱ ۱ | فرزند ۱ |
شکل۴-۶: نمونهای از عملگر تقاطع یکنواخت
۴-۳-۶-۷) تقاطع مرتب:[۵۸]
از تقاطع دو نقطهای مرتب زمانی استفاده میشود که مسأله مبتنی بر ترتیب (برای مثال، مسأله بالانس خط مونتاژ U شکل و غیره) باشد. با دو والد داده شده، دو نقطه تقاطع تصادفی انتخاب میگردد که آنها را به سه قسمت چپ، وسط و راست تقسیم میکند. عملگر به این ترتیب عمل می کند: فرزند ۱ سمت چپ و راست را از والد اول و قسمت وسط آن براساس ژنهای قسمت وسط والد ۱ به نحوی که ترتیب آن براساس والد ۲ باشد تعیین میگردد. فرایند مشابه برای فرزند دوم صورت میگیرد. یک مثال از تقاطع مرتب در شکل ۴-۷ نمایش داده شده است.
Parent 1 : 4 2 | 1 3 | 6 5 Child 1 : 4 2 | 3 1 | 6 5
Parent 2 : 2 3 | 1 4 | 5 6 Child 2 : 2 3 | 4 1 | 5 6
شکل۴-۷: نمونهای از عملگر مرتب [۱]
۴-۳-۷) جهش:
بعد از تقاطع، کروموزومها تحت اپراتور جهش قرار میگیرند. عملگر جهش از افتادن الگوریتم در بهینه محلی جلوگیری مینماید. اگر عملگر تقاطعی برای کاوش روی راه حل های اخیر در جهت یافتن راهحل بهتر به کار گرفته شده است، عملگر جهش برای کمک به جستجوی کل فضای جستو در نظر گرفته میشود. جهش موجبی میگردد که گوناگونی جمعیت حفظ شده و ساختار ژنتیکی جدیدی در جمعیت با تغییرات تصادفی بعضی از ژنها به وجود آید. عملگر جهش با حفظ گوناگونی جمعیت موجب میگردد که از افتادن الگوریتم در بهینه محلی جلوگیری گردد.
شکلهای متعددی از جهش برای انواع مختلف نمایش راهحل وجود دارد. برای یک نمایش باینری، یک جهش ساده میتواند به صورت عکس مقدار هر ژن با احتمال کوچکی تعریف گردد. احتمال جهش، معمولاً در حدود ۱ / L در نظر گرفته میشود که L طول کروموزوم است. در زیر بعضی از عملگرهای جهش شرح داده میشود.
۱) معکوسکردن:[۵۹]
۲) تعویض:[۶۰]
۴) احتمال جهش:
۴-۳-۸) جابهجایی:[۶۱]
جابهجایی آخرین مرحله از چرخه تولیدمثل است. دو والد از یک جمعیت با اندازه ثابت، انتخاب شده و دو فرزند را به وجود آوردهاند. نمیتوان کل این چهار کروموزوم را به جمعیت برگرداند و در نتیجه باید دو کروموزوم حذف گردد. به عبارت دیگر، زمانی که فرزندان تولید شدند، باید روشی تعریف گردد که براساس آن مشخص گردد که کدام یک از اعضاء فعلی جمعیت باید حذف شده و چه فرزندانی باید جانشین آنها شود. این روش بر همگرایی الگوریتم ژنتیک تأثیر زیادی خواهد داشت. روشهای مختلفی برای انتخاب جمعیت جدید وجود دارد که به طور مثال میتوان از دو روش زیر نام برد.
تمام اعضای جمعیت جدید از میان کروموزومهای فرزندان انتخاب شوند.
تعدادی از افراد جمعیت مرحله بعد، همان افراد جمعیت مرحله قبل بوده و بقیه از میان فرزندان جدید انتخاب گردند. البته در هر مورد، شایستهترین کروموزومها انتخاب میشود.
تحقیقات نشان داده است که حذف همه کروموزومهای جمعیت مرحله قبل و انتخاب جمعیت جدید از میان فرزندان، ممکن است بسیاری از جوابهای مناسب را که در میان جمعیت مرحله قبل وجود دارد، حذف نماید.
۴-۳-۸) قاعده توقف:
قواعد توقف متعددی برای الگوریتم ژنتیک وجود دارد که در زیر خلاصه به بعضی از آنها اشاره مینماییم.
حداکثر تولیدنسل. با بهره گرفتن از این قاعده، الگوریتم ژنتیک زمانی متوقف میگردد که تعداد مشخصی از تولید نسل اتفاق افتاده باشد. مثلاًٌ شمارنده تولید نسل به عدد خاصی مثل ۱۰۰ برسد.
زمان سپری شده. زمانی که فرایند الگوریتم ژنتیک زمان خاصی را سپری کرد، الگوریتم متوقف میگردد.
۴-۳ الگوریتم حرکت جمعی پرندگان (pso)
فرض کنید شما و گروهی از دوستانتان به دنبال گنج می گردید. هر یک از اعضای گروه یک فلزیاب و یک بی سیم دارد که می تواند مکان و وضعیت کار خود را به همسایگان نزدیک خود اطلاع بدهد. بنابراین شما می دانید آیا همسایگانتان از شما به گنج نزدیکترند یا نه؟ پس اگر همسایه ای به گنج نزدیکتر بود شما می توانید به طرف او حرکت کنید. با چنین کاری شانس شما برای رسیدن به گنج بیشتر می شود و همچنین گنج زودتر از زمانی که شما تنها باشید، پیدا می شود.