۱۴۵
۲
۷
۲۵
۲
۸
برازندگی
۰۱۴. ۰
۰۳۳. ۰
۰۵۲. ۰
۶۹۰. ۰
۰۹۰. ۰
۰۳۳. ۰
۱۱۹. ۰
۰۹. ۰
۰۳۸. ۰
برازندگی کل
روش دیگری که مشکل فوق را حل کرده است، روش رتبه‌بندی است. در این روش انتخاب، کروموزوم‌ها براساس مقدار برازندگی آنها رتبه‌بندی شده و رتبه آنها به جای برازندگی آنها در چرخ رولت مورد استفاده قرار می‌گیرد. برای این منظور، ابتدا کروموزوم‌ها را به ترتیب از بدترین به بهترین مرتب می‌گردند، سپس کروموزوم‌ها، رتبه‌بندی می‌شوند. در این حالت، بدترین کروموزوم رتبه ۱، کروموزوم ماقبل بدتری رتبه ۲، و الی آخر تا اینکه به بهترین کروموزوم رتبه n اختصاص داده می‌شود (n تعداد کروموزومهای موجود در جمعیت است). احتمال انتخاب کروموزوم iام به صورت زیر محاسبه می‌شود:
۴-۳-۵-۴) روش انتخاب رقابتی:[۵۵]
در روش انتخاب رقابتی، یک زیرمجموعه کوچکی از کروموزوم‌ها (معمولاً دو یا سه) به صورت تصادفی انتخاب شده و به رقابت می‌پردازند. سرانجام در این رقابت، براساسی میزان برازندگی، یکی از آنها به پیروزی رسیده وانتخاب می‌شود. به عنوان مثال، مجموعه ۷ کروموزوم جمعیت را در نظر بگیرید. سه کروموزوم با ارزش‌های ۴، ۹ و ۷ انتخاب شده‌اند. در این رقابت، کروموزوم با ارزش ۹ به دلیل برازندگی بیشتر، برنده می‌شود. این عمل با برگرداندن دو کروموزوم شکست خورده و انتخاب چند کروموزوم دیگر برای تعیین جفت ادامه می‌یابد. ایرادی که به این روش میتوان گرفت این است که در این روش، هیچ‌گاه کروموزوم دارای کمترین ارزش، برنده نخواهد شد؛ زیرا در صورت انتخاب با هر کروموزوم دیگر، بازنده خواهد شد. ساختار انتخاب باید به نحوی باشد که تمامی کروموزوم‌ها شانس تولیدمثل حتی به مقدار کم را داشته باشند.
۴-۳-۵-۴) روش انتخاب بالتزمن:[۵۶]
قاعده بالتزمن، بیشتر در الگوریتم انجماد تدریجی مورد استفاده قرار می‌گیرد. در الگوریتم ژنتیک نیز میتوان از قاعده بالتزمن برای کنترل رویه انتخاب استفاده نمود. در این حالت، دما از یک مقدار بالا در ابتدای الگوریتم شروع می کند و معنای آن، این است که فشار رویه انتخاب پایین است. دما به مرور کاهش پیدا می‌کند و به دنبال آن، فشار رویه انتخاب به مرور افزایش پیدا می‌کند. در این حالت، در ابتدای الگوریتم گوناگونی افزایش یافته و در انتها، جستجوی محلی قوت می‌یابد.
۴-۳-۶) عملگر تقاطعی (ترکیب مجدد):[۵۷]
عملگر تقاطعی، فرایندی است که دو والد را در نظر گرفته و براساس آنها یک فرزند جدید تولید می کند. عمل تقاطعی روی حوضچه تولید مثل به این امید که فرزند بهتری تولید گردد، به کار گرفته می‌شود. این عملگر یک اپراتور ترکیب‌بندی است که در سه مرحله صورت می‌گیرد:
- اپراتور تولیدمثل (رویه انتخاب) یک زوج از والد را از حوضچه تولیدمثل انتخاب می کند.
- یک نقطه تقاطع به طور تصادفی در طول رشته انتخاب می‌شود.
- در نهایت، مقادیر رشته‌ها با توجه به نقطه تقاطع تعویض می‌گردند.
عملگر تقاطعی با یک احتمال از قبل تعیین شده (Pc)، بر روی کروموزومهای والد عمل می‌کند. بدین معنی که با این احتمال عمل تقاطع انجام می‌گیرد. اگر هیچ تقاطعی صورت نگیرد، فرزندان دقیقاً مشابه والدین خواهند بود. در صورتی که تقاطع صورت گیرد، فرزندان از قسمت‌های مختلف کروموزومهای والد ساخته می‌شوند. اگر احتمال تقاطع، ۱ باشد؛ تمامی فرزندان از طریق عمل تقاطعی ایجاد می‌شوند. عملیات تقاطع با این هدف انجام می‌شود که کروموزومهای جدید در بردارنده قسمت‌های مناسب و خوب کروموزومهای قبلی خواهند بود و شاید این کروموزومهای جدید عملکرد بهتری داشته باشند. اما بهتر است همیشه بهترین کروموزومهای نسل قبلی بدون هیچ تغییری به نسل جدید منتقل شوند.
روش‌های مختلفی برای عملکر تقاطع وجود دارد و در زیر بعضی از روش‌های متداول آن شرح داده می‌شود.
۴-۳-۶-۱) تقاطع تک نقطه‌ای:
عملگر تقاطعی تک نقطه‌ای، دو کروموزوم را به طور تصادفی از یک نقطه شکسته و بخش‌‌های شکسته شده دو کروموزوم را جابه‌جا می‌کند. بدین ترتیب، دو کروموزوم جدید به دست می‌آید، به کروموزومهای اولیه، کروموزومهای ” والد” و به کروموزومهای حاصل شده از عمل جابه‌جایی، کروموزوم “فرزند” می‌گویند. شکل ۴-۳ یک مثال از عملگر تقاطع تک نقطه‌ای را نمایش می‌دهد.
شکل۴-۳: نمونه‌ای از عملگر تقاطع تک نقطه‌ای [۱]
۴-۳-۶-۲) تقاطع دو نقطه‌ای:
در عملگر تقاطع دو نقطه‌ای، دو نقطه شکست در طول رشته جواب در نظر گرفته می‌شود. در این حالت، ابتدا دو مکان تصادفی را در طول رشته انتخاب شده و سپس به صورت یک در میان قسمت‌های والدها به فرزندان منتقل می‌شود. باید توجه داشت که، در صورتی که تعداد نقاط شکست افزایش یابد، عملکرد الگوریتم ژنتیک کاهش می‌یابد. از طرفی، در صورت افزایش تعداد نقاط شکست، فضای مسأله به صورت کامل‌تری جستجو می‌گردد.
در الگوریتم ژنتیک، معمولاً از عملگر تقاطع تک نقطه استفاده می‌گردید. اما در تقاطع تک نقطه‌ای این مشکل وجود دارد که هیچ‌گاه ابتدا و انتهای رشته جواب یک والد نمی‌تواند به یک فرزند به طور همزمان منتقل گردد؛ زیرا همواره یا ابتدای رشته (قبل از نقطه شکست) و یا انتهای رشته (بعد از نقطه شکست) به یک فرزند منتقل می‌شده است. اگر ژن‌های ابتدایی و انتهایی الگوریتم به طور همزمان خصوصیات خوبی را به وجود آوردند، در صورت استفاده از تقاطع تک نقطه‌ای، این خصوصیت به هیچکدام از فرزندان منتقل نمی‌گردد. استفاده از تقاطع دو نقطه‌ای، از این مشکل جلوگیری نموده و به طور کلی عملکردی بهتر نسبت به تک نقطه‌ای دارد. البته این مشکل، قابل تعمیم به هر نقطه از رشته کروموزوم خواهد بود. به عبارت دیگر، اینکه دو ژن (در هر موقعیت از کروموزوم) نتوانند به طور همزمان به یک فرزند، منتقل گردند، می‌تواند منجر به ایجاد یک محدودیت در تولیدمثل گردد. در این حالت استفاده از تقاطع چند نقطه‌ای یا تقاطع یکنواخت می‌تواند به حل این مشکل کمک کند. شکل ۴-۴ نمونه‌ای از عملگر تقاطع دو نقطه‌ای برای یک کروموزوم ترتیبی را نمایش می‌دهد. عملگر تقاطع بر آرایه ترتیبی به سادگی آرایه ۰-۱ نیست. همان‌طور که در شکل ۴-۵ مشاهده می‌گردد، برای آرایه ترتیبی، ابتدا قسمت‌های کناری از والد اول به فرزند منتقل شده و سپس بقیه ژن‌ها به ترتیب مشخص شده در والد دوم به فرزند منتقل می‌گردد. در صورتی که قسمت دوم کروموزوم فرزند عیناً از والد دوم انتخاب گردد، به دلیل تکرار مقادیر، یک کروموزوم غیرقانونی تولید می‌گردد. به همین دلیل، از والد دوم، مقادیر باقی مانده فرزند، به ترتیب ظهور در والد دوم، به فرزند منتقل می‌گردد.
شکل۴-۴: نمونه‌ای از عملگر تقاطع دو نقطه‌ای برای آرایه ۰-۱ [۱]
شکل۴-۵: نمونه‌ای از عملگر تقاطع دو نقطه‌ای برای آرایه ترتیبی [۱]
۴-۳-۶-۳) تقاطع چند نقطه‌ای:
