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

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

(۳-۲۴)  
(۳-۲۵)  
(۳-۲۶)  
(۳-۲۷)  
(۳-۲۸)  

که در آن، k’ij، k’ji، k’ip، k’pi، k’jp و k’pi مقادیر جاری تخصیص خط هستند و kij و kji متغیرهای تخصیص خط برای دو کمان متناظر یال l هستند، Φi و Φj به ترتیب مجموعه گره­های مجاور i و j هستند، نامساوی­های (۳-۲۴) و (۳-۲۵) تضمین می­ کنند که دست­کم یک خط ورودی و یک خط خروجی برای گره i وجود داشته باشد و نامساوی­های (۳-۲۶) و (۳-۲۷) همین محدودیت را برای گره j برقرار می­ کنند. عبارت­های دوم در (۳-۲۴) و (۳-۲۷) تعداد کل خط­های خروجی از گره­های i وj به غیر از خط­های کمان­های (i, j) و (j, i) را محاسبه می­ کنند. عبارات دوم در (۳-۲۵) و (۳-۲۶)، همین نقش را برای خط­های ورودی به گره­های iوj ایفا می­ کنند. معادله (۳-۲۸) محدودیت کلی تخصیص خطهای یال l است. به منظور محاسبه دامنه مجاز، کافیست که همه نامساوی­ها برحسب متغیرkij نوشته شوند و سپس بیشترین و کمترین مقادیر ممکن برای آن محاسبه شوند. از آن­جایی­که ممکن است مقادیر بیشترین و کمترین مقدار مجاز بدست آمده کمتر از ۰ و یا بیشتر از تعداد کل خط­های یال باشند، این مقادیر نیز در محاسبه دامنه مجاز منظور می­شوند. کران پایینی LBij و کران بالایی UBij برای مقدار kijبه صورت روابط (۳-۲۹) و (۳-۳۰) خواهند بود. با حذف مقدار جاری متغیر kij از دامنه و انتخاب یک مقدار تصادفی برای kij، مقدار kji به­راحتی قابل محاسبه است.

(۳-۲۹)  
(۳-۳۰)  

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

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

    • محاسبه مقادیر برازندگی مربوط به هر کروموزم:
(۳-۳۱)  
موضوعات: بدون موضوع  لینک ثابت


فرم در حال بارگذاری ...