• اگر همه محدودیت­های (۳-۵) برقرارند، قرار ده µ_a=λ ، در غیر اینصورت قرار ده µ_b=λ.

تولید جواب‏های اولیه برای توپولوژی شبکه

جواب­های اولیه به استفاده از یک رویه ابتکاری تولید می­شوند که مرحله به مرحله گراف مورد نظر را می­سازند ]۳۰[. ابتدا ترکیبی تصادفی از گزینه­ های افزایش خط برای یال­های مختلف و با توجه به محدودیت بودجه انتخاب می­ شود. سپس خط­های موجود در شبکه و خط­های افزودنی جدید به یال­های شبکه تخصیص داده می­شوند. به منظور کاهش احتمال تولید گراف­های ناهمبند، تخصیص خط­ها در دو مرحله صورت می­گیرد.
در مرحله اول کم­ترین تعداد خط­های مورد نیاز برای برقراری شرط لازم همبندی به یال­ها تخصیص داده می­شوند، به این معنی که ابتدا یک خط به یکی از کمان­های هر یک از یال­ها تخصیص داده می­ شود تا محدودیت (۳-۸) برقرار شود. سپس، هر یک از گره­ها به ترتیب از نظر تعداد خط­های ورودی و خروجی بررسی می­ شود. در صورتی که گرهی فاقد خط ورودی یا خروجی باشد، بر حسب نیاز یک خط به صورت تصادفی به یکی از کمان­های ورودی یا خروجی آن تخصیص داده می­ شود. در مرحله دوم، بقیه خط­های یال­ها به صورت تصادفی به یال­ها تخصیص داده می­شوند. پس از تولید هر جواب اولیه جدید، ابتدا همبندی گراف بررسی می­ شود و در صورت ناهمبند بودن از جواب صرف­نظر می­ شود. این رویه تا زمانی­که تعداد جواب­های اولیه به اندازه مورد نظر برسد تکرار می­ شود.

بررسی جواب‏های از نظر همبندی گراف

هر جواب جدید تولید شده در الگوریتم، در دو مرحله از نظر همبندی گراف حاصل بررسی می­ شود. در مرحله اول، یک شرط لازم برای همبندی گراف و در مرحله دوم وجود مسیر بین هر جفت گره شبکه بررسی می­ شود. هدف از این کار غربال کردن بخشی از جواب­های ناشدنی و کاهش محاسبات غیر ضروری برای بررسی همبندی گراف­هاست.
مرحله اول: در وهله اول، وجود دست­کم یک خط خروجی و یک خط ورودی به هر گره (تنها نبودن و در بن بست قرارنداشتن گره­های گراف) به عنوان شرط لازم همبندی قوی گراف بررسی می­ شود. در صورت برآورده شدن این شرط، مرحله دوم بررسی انجام می­ شود، در غیر این صورت گراف همبند نیست.
مرحله دوم: در مرحله دوم، وجود دست­کم یک مسیر بین هر دو گره گراف بررسی می­ شود. برای این منظور از الگوریتم کوتاه­ترین مسیر دایسترا^[۳۵]]۵۲[ استفاده می­ شود. با هر بار اجرای الگوریتم، درخت کوتاه­ترین مسیر بین یک گره و بقیه گره­های گراف بدست می ­آید. در صورتی که گراف همبند نباشد، دست­کم یکی از گره­ها در درخت تشکیل شده حضور ندارد، به این معنی که بین دست­کم یک جفت گره هیچ مسیری یافت نشده است.

الگوریتم ژنتیک ترکیبی با شبیه‏سازی تبرید

رو­ش­ حل توسعه داده شده در این بخش الگوریتم ژنتیک است. در این روش، عملگر جهش با الگوریتم شبیه­سازی تبرید جایگزین می­ شود که آ­ن را به یک الگوریتم ترکیبی تبدیل می­ کند. عملگر جهش در الگوریتم­های ژنتیک معمول با احتمال معینی بر روی فرزندانی که جمعیت نسل بعدی را تشکیل می­ دهند اعمال می­ شود و هدف آن اعمال تنوع در هر دو نسل متوالی از جمعیت جواب­هاست. در این الگوریتم، شبیه­سازی تبرید به عنوان یک رویه بهبود دهنده، بر روی تعدادی از فرزندان نامزد برای ورود به جمعیت اعمال می­ شود. گام­های کلی الگوریتم توسعه داده شده به شرح زیر هستند:
مرحله اول: مجموعه ­ای از جواب اولیه را به تعداد جمعیت تولید کن و مقادیر برازش آنها را محاسبه کن.
مرحله دوم: گام های زیر را برای تعداد نسل­های مشخص تکرار کن:

• یک جفت والد را به طور تصادفی انتخاب کن.

• با عملگر تقاطع مجموعه فرزندان را تولید کن.

• گراف هر فرزند را بررسی کن و فرزندان با گراف ناهمبند را حذف کن.

• برقرار بودن محدودیت بودجه را برای هر فرزند بررسی کن و در صورت نیاز هزینه­ های افزایش خط­ در جواب­های ناشدنی را کاهش ده.

• شبیه­سازی تبرید را بر روی بهترین فرزند اعمال کن.

• جمعیت جدید را از ترکیب بهترین جواب­های جمعیت موجود و مجموعه جواب­های فرزند ایجاد کن.

تعریف کروموزوم‏ها

کروموزوم­ها برای متغیرهای تصمیم ­گیری y_l، z_ijو k_ij مسالهU تعریف می­شوند، زیرا متغیر µ از حل مدل سطح پایین قابل محاسبه است. هر کروموزوم نمایان­گر تعداد خطهای تخصیص داده شده در هر کمان است که به طور ضمنی جهت معابر، تعداد خط­های اضافه شده، و نحوه تخصیص خطها را مشخص می­ کند. هر کروموزوم به صورت یک ماتریس دو سطری تعریف می­ شود که ستون­های آن معرف یال­های شبکه و سطرهای آن متناظر با کمان­های هر یال هستند. مقادیر هر آرایه برابر است با تعداد خط تخصیص داده شده به کمان متناظر با یال مورد نظر. شکل ‏۳‑۳ و شکل ‏۳‑۴ یک شبکه نمونه با ۶ گره و ۹ یال و نمایش کروموزوم آن را نشان می­ دهند. یال­هایی که دو سر آنها دارای پیکان است، معابر دو طرفه و ترکیبی از دو کمان هستند. یال­هایی که فقط یک سر آنها دارای پیکان است، معابر یک طرفه هستند.

شکل ‏۳‑۵- یک شبکه نمونه

۹
۸
۷
۶
۵
۴
۳
۲
۱

۱
۲
۱
۱
۰
۱
۱
۰
۱