۱

۰

۱

۱

۲

۱

۱

۲

۱

شکل ‏۳‑۶- نمایش کروموزوم شبکه نمونه

عملگر تقاطع

عملگر تقاطع^[۳۶] مورد استفاده در این الگوریتم، از عملگر توسعه داده شده توسط درزنر و وسلوسکی ]۴۳[ در مورد طراحی شبکه با معابر یک و دوطرفه اقتباس شده و با اندکی تغییر مورد استفاده قرار گرفته است. عملگر مزبور رویه­ای کارآمد و موفق برای ترکیب دو والد است که از ساختار خاص خود مساله بهره جسته است. این عملگر دو والد را به گونه ­ای با هم ترکیب می­ کند که مجموعه­ یال­های انتخاب شده از هر والد حتی­الامکان یک زیر گراف همبند را تشکیل دهند. برای این منظور، با در نظر گرفتن یک گره به عنوان گره محور^[۳۷]، برای هر یال یک شماره تخصیص داده می­ شود، بدین ترتیب که شماره ۱ به یال­های متصل به گره محور، شماره ۲ به یال­های متصل به یال­های با شماره ۱، شماره ۳ به یال­های متصل به یال­های با شماره ۲ و … تخصیص داده می­شوند. سپس، میانه شماره یال­ها محاسبه می­ شود. یال­های با شماره کم­تر از میانه، از والد اول و یال­های با شماره بیشتر از میانه از والد دوم انتخاب می­شوند. برای یال­های با شماره برابر با میانه، به طور تصادفی همگی از یکی از والدها انتخاب می­شوند. در نسخه اصلی عملگر، هر یک از یال­های با شماره برابر با میانه، به طور تصادفی از والد اول یا دوم انتخاب می­شوند. پس از تولید فرزند اول، جهت کلیه یال­های یک طرفه جابه­جا می­ شود تا فرزند دوم بدست آید.

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

عملگر برای تعدادی از گره­ها که به طور تصادفی به عنوان گره­های محور انتخاب می­شوند اجرا می­ شود تا مجموعه ­ای از فرزندان بدست آید. در این مساله تعداد گره­های انتخابی برابر یک پنجم کل گره­های گراف در نظر گرفته شده است. در مثال زیر نحوه محاسبه شماره یال­ها و سپس نحوه اعمال عملگر تقاطع بر اساس شماره­های بدست آمده نشان داده شده است. در شکل ۳-۵ یال­های شبکه نمونه ۳-۷ با در نظر گرفتن گره ۱ به عنوان گره محور، شماره­دهی شده ­اند. میانه شماره­های یال­ها برابر با ۲ است. بنابراین برای فرزند اول یال­های با شماره ۱ از والد اول، یال­های با شماره ۳ از والد دوم و یال­های با شماره ۲ به طور تصادفی از یکی از والدین انتخاب می­شوند. در مورد فرزند دوم، جهت همه یال­های یک طرفه فرزند اول جابه­جا می­شوند. بر این اساس، با فرض داشتن دو والد طبق شکل ۳-۸ ، یال­ها به ترتیب مشخص شده برای ایجاد فرزندان انتخاب می­شوند.

شکل ‏۳‑۷- شماره‏دهی یال‏های شبکه نمونه برای گره محور ۱

۲

۲

۱

۱

۱

۱

۱

۰

۱

۱

۲

۱

۱

۰

۱

۱

۰

۱

۰

۰

۱