تغییر کاملا تصادفی تخصیص خط­های یال­ها، ممکن است منجر به ایجاد یک گراف ناهمبند شود. برای کاهش احتمال وقوع چنین حالتی و با توجه به این که ایجاد یک گراف همبند به صورت کنترل شده از نظر محاسباتی بسیار مشکل است، تغییر تخصیص خط­ها به صورتی انجام می­ شود که در حداقل ممکن، یکی از شروط لازم همبندی برقرار بماند (مرحله اول، بررسی جواب­ها از نظر همبندی). برای این منظور، یک دامنه مجاز برای تغییرات تعداد خط­ها در دو طرف یال مورد نظر تعریف می­ شود. این دامنه کمترین و بیشترین تعداد خط مجاز در هر یک از کمان­های یک یال را مشخص می­ کند، به­گونه ­ای که تعداد خطهای ورودی و خروجی گره­های دو سر یال به صفر نرسد. دامنه مجاز برای کمان (i, j)، یال l تعریف می­ شود. برای این منظور، از یک مجموعه محدودیت­ها به صورت زیر بهره گرفته می­ شود:

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

(۳-۲۴)

(۳-۲۵)

(۳-۲۶)

(۳-۲۷)

(۳-۲۸)

که در آن، k’_ij، k’_ji، k’_ip، k’_pi، k’_jp و k’_pi مقادیر جاری تخصیص خط هستند و k_ij و k_ji متغیرهای تخصیص خط برای دو کمان متناظر یال l هستند، Φ_i و Φ_j به ترتیب مجموعه گره­های مجاور i و j هستند، نامساوی­های (۳-۲۴) و (۳-۲۵) تضمین می­ کنند که دست­کم یک خط ورودی و یک خط خروجی برای گره i وجود داشته باشد و نامساوی­های (۳-۲۶) و (۳-۲۷) همین محدودیت را برای گره j برقرار می­ کنند. عبارت­های دوم در (۳-۲۴) و (۳-۲۷) تعداد کل خط­های خروجی از گره­های i وj به غیر از خط­های کمان­های (i, j) و (j, i) را محاسبه می­ کنند. عبارات دوم در (۳-۲۵) و (۳-۲۶)، همین نقش را برای خط­های ورودی به گره­های iوj ایفا می­ کنند. معادله (۳-۲۸) محدودیت کلی تخصیص خطهای یال l است. به منظور محاسبه دامنه مجاز، کافیست که همه نامساوی­ها برحسب متغیرk_ij نوشته شوند و سپس بیشترین و کمترین مقادیر ممکن برای آن محاسبه شوند. از آن­جایی­که ممکن است مقادیر بیشترین و کمترین مقدار مجاز بدست آمده کمتر از ۰ و یا بیشتر از تعداد کل خط­های یال باشند، این مقادیر نیز در محاسبه دامنه مجاز منظور می­شوند. کران پایینی LB_ij و کران بالایی UB_ij برای مقدار k_ijبه صورت روابط (۳-۲۹) و (۳-۳۰) خواهند بود. با حذف مقدار جاری متغیر k_ij از دامنه و انتخاب یک مقدار تصادفی برای k_ij، مقدار k_ji به­راحتی قابل محاسبه است.

(۳-۲۹)

(۳-۳۰)

مکانیزم انتخاب

انتخاب تصادفی به وسیله چرخ رولت از جمله روش های انتخاب است که این روش انتخاب توسط هالند پیشنهاد شده است]۴۶[. ایده اصلی این روش تعیین احتمال انتخاب یا احتمال بقا برای هر کروموزوم، متناسب با مقدار برازش آن است. چرخ رولت به منظور نشان دادن این احتمالات است و فرایند انتخاب مبتنی بر چرخاندن هم زمان ارقام چرخ به تعداد اندازه­ جمعیت است. فرایند کلی به صورت زیر است:

• • محاسبه مقادیر برازندگی مربوط به هر کروموزم:

(۳-۳۱)