ژانویه 18, 2021

الگوریتم ژنتیک

فرمول‌بندی مدل نهایی VCTMS به صورت یک مسأله‌ی MILP دو سطحی به صورت زیر است:
‏(4-1)
مشروط به:
‏(4-2)-‏(4-23)، ‏(4-104) و ‏(4-105)
استفاده از الگوریتم ژنتیک برای حلّ مدل VCTMS
مدل نهایی VCTMS که به صورت یک مسأله‌ی بهینه‌سازی MILP دو سطحی است را می‌توان با روندی که در این قسمت توضیح داده می‌شود، با استفاده از الگوریتم ژنتیک (GA) حل کرد. در مدل دو سطحی VCTMS، مسأله‌ی سطح پایین همان مدل MWaW است که وضعیت تعمیرات معمولی خطوط کاندید به عنوان یک پارامتر ورودی به آن داده می‌شود. مدل MWaW را می‌توان با نرم‌افزارهای بهینه‌سازی نظیر نرم‌افزار GAMS شبیه‌سازی و حل کرد. برای حلّ مدل دو سطحی VCTMS می‌توان از ارتباط همزمان دو نرم‌افزار MATLAB و GAMS استفاده کرد. الگوریتم ژنتیک در نرم‌افزار MATLAB پیاده‌سازی می‌شود که در ادامه در خصوص چگونگی تنظیم بخش‌های مختلف این الگوریتم توضیحات کافی ارائه می‌شود.
انتخاب متغیّرها و تابع هدف
تابع هدفی که باید توسّط الگوریتم ژنتیک کمینه شود، تابع هدف مسأله‌ی سطح اوّل است. توضیح بیشتر این که الگوریتم حلّ مسأله به دنبال یافتن بهترین برنامه‌ی زمان‌بندی برای تعمیرات خطوط کاندید به گونه‌ای است که بتواند هزینه‌های تولید و قطع‌بار را کمینه کند. اطّلاعات بیشتر درخصوص این تابع هدف قبلاً در بخش ‏4-2 ارائه شده است.
هر کروموزوم در جمعیت اوّلیه از تعدادی ژن تشکیل شده است. تعداد این ژن‌ها به تعداد خطوط کاندید تعمیرات معمولی است. عددی که در این ژن‌ها قرار می‌گیرد یک عدد صحیح است که بیان‌گر زمان شروع تعمیرات معمولی خطّ کاندید متناظر است. در ادامه، از اعداد صحیح موجود در ژنها استفاده می‌شود تا بتوان یک زمان‌بندی تعمیرات معمولی برای هر خطّ کاندید تولید کرد. به عنوان مثال، اگر شبکهی مورد مطالعه دارای سه خطّ کاندید باشد و یکی از کروموزومهای موجود در جمعیت اوّلیه به صورت ‏شکل4-1 باشد، به این معنی است که زمان شروع تعمیرات خطوط کاندید، به ترتیب، زیربازهی t3، t12 و t9 است.
کدگذاری
عدد صحیحی که در هر ژن قرار می‌گیرد، عددی بزرگتر و یا مساوی با یک و کمتر و یا مساوی با تعداد زیربازه‌های موجود در افق زمانی مورد مطالعه است. به عنوان مثال اگر ISO بخواهد که تعمیرات معمولی خطوط شبکه در یک فصل آینده تعیین کند، این یک فصل به 13 هفته و هر هفته به دو زیربازه تقسیم می‌شود و در مجموع 26 زیربازه وجود خواهد داشت. زمان شروع تعمیرات هر خطّ کاندید تعمیرات معمولی باید عددی بین یک و 26 باشد.
از آن‌جا که تعمیرات معمولی باید به صورت پیوسته انجام شود، برای هر خطّ کاندید، با توجّه به عدد تولید شده در ژن متناظر و با توجّه به مدّت زمان لازم برای تعمیرات معمولی خط، یک بردار تولید می‌شود که
زمان‌بندی تعمیرات این خط را در افق زمانی مطالعه نشان می‌دهد. به عنوان مثال، اگر یکی از خطوط شبکه برای تعمیرات معمولی خود به دو زیربازه‌ی کاری و یک زیربازه‌ی غیرکاری نیاز داشته باشد (در مجموع، به سه زیربازه برای انجام تعمیراتش نیاز دارد) و عدد صحیح موجـود در ژن متناظر این خط برابر با 13 باشـد، باید یک بردار صفر و یک به اندازه‌ی تعداد زیربازه‌های موجود در افق زمانی مطالعه تولید شود که تمامی درایه‌های آن به جز درایه‌های 13، 14 و 15 آن صفر باشد. این بردار این گونه تعبیر می‌شود که ISO تصمیم گرفته است که تعمیرات معمولی خطّ مورد نظر را در زیربازه‌های 13، 14 و 15 اجرا کند. دقّت شود که زیربازه‌های با شماره‌های فرد متناظر با زیربازه‌های کاری هستند و زیربازه‌های با شماره‌های زوج متناظر با زیربازه‌های آخرهفته. بنابراین اگر عدد تولید شده برای خطّ بررسی شده در این مثال، عدد 14 بود، باید ابتدا این عدد به یک عدد فرد (13 و یا 15) تبدیل شود و بعد از آن می‌توان بردار بیان‌گر تعمیرات معمولی این خط را تشکیل داد.
9
12
3
یک کروموزوم نمونه برای شبکه‌‌ای که دارای سه خطّ کاندید برای تعمیرات معمولی است
تا به این‌جا، برای هر کروموزوم یک بردار و یک ماتریس بدست آمده است؛ بردار متناظر با هر کروموزوم، یک بردار به اندازه‌ی تعداد زیربازه‌های موجود در افق زمانی مورد مطالعه است که زمان شروع تعمیرات معمولی هر کدام از خطوط کاندید را با لحاظ آخرین تغییراتی که در این مرحله بر روی اعداد موجود در ژن‌ها صورت گرفته است، در خود ذخیره می‌کند. این بردار را بردار آغاز می‌نامیم. و امّا ماتریس متناظر با هر کروموزوم، ماتریسی است که تعداد سطرهای آن به اندازه‌ی تعداد خطوط کاندید است و هر سطر آن شامل بردار صفر و یک تولید شده در این مرحله برای تعمیرات معمولی خطّ متناظر با شماره‌ی سطر است. این ماتریس را ماتریس تعمیرات معمولی می‌نامیم.
جمعیت اوّلیه
جمعیت اوّلیه می‌تواند شامل تعداد دلخواهی کروموزوم باشد (به طور نمونه، 100کروموزوم). اعداد صحیح تولید شده برای ژن‌های کروموزوم‌های مربوط به جمعیت اوّلیه به صورت تصادفی تولید می‌شوند.
انتخاب
پس از تعیین و تشکیل جمعیت اوّلیه، باید برای هر کروموزوم، بردار آغاز و ماتریس تعمیرات معمولی متناظر با آن کروموزوم به نرم‌افزار GAMS ارسال شود تا بتوان بهترین نقشه‌ی حمله‌ی مهاجم را تعیین کرد. نرم‌افزار GAMS با داشتن برنامه‌ی تعمیرات معمولی خطوط کاندید و زمان شروع هر یک از این تعمیرات، مدل MWaW را اجرا کرده و علاوه بر مقدار تابع هدف بدست آمده برای این کروموزم، مقدار متغیّر cl را نیز به نرم‌افزار MATLAB با
زمی‌گرداند. متغیّر cl یک متغیّر صفرو یک است که برای خطوط کاندید تعریف می‌شود. اگر مقدار آن برای یک خطّ کاندید یک باشد به این معنی است که لااقل یک بار قبل از زمان شروع تعمیرات معمولی این خطّ کاندید به آن حمله شده است و بنابراین زمان‌بندی صورت گرفته برای تعمیرات این خط اعتبار ندارد. توضیحات بیشتر در خصوص این متغیّر، پیش‌تر در زیربخش ‏4-3 ارائه شده است.
در نرم‌افزار MATLAB باید ابتدا بردار حاوی مقادیر متغیّر cl به ازای خطوط کاندید شبکه تحلیل شود. این تحلیل به این گونه است که اگر لااقل یکی از عناصر بردار شامل مقادیر cl یک باشد، به این معنی است که ترکیب تعیین شده برای تعمیرات معمولی خطوط شبکه (ماتریس تعمیرات معمولی) متناظر با کروموزوم جاری نامناسب است و باید به گونه‌ای این پاسخ جریمه شود. برای جریمه کردن چنین پاسخ‌هایی می‌توان مقدار تابع هدف متناظر با آن‌ها را در یک عدد بزرگ (مثلاً 1000) ضرب کرد.
ترکیب
در این مرحله، باید براساس مقدار تابع هدف بدست آمده برای هر کروموزوم، این کروموزوم‌ها ارزش‌گذاری شوند تا بهترین کروموزوم‌ها برای تولید نسل بعد انتخاب شوند. روش‌های مختلفی برای ارزش‌گذاری کروموزوم‌ها وجود دارد [41] که یکی از این روش‌ها، رتبه‌بندی براساس مقدار تابع هدف متناظر با کروموزوم است. در این روش، کروموزوم‌هایی که تابع هدف متناظر با آن‌ها مقدار کمتری دارد، ارزش بیشتری دارند.
در این مرحله، دو کروموزوم به صورت تصادفی و با لحاظ ارزش هر کروموزوم، به عنوان والد انتخاب می‌شوند تا با ترکیب آن‌ها، دو فرزند برای نسل بعد تولید شود. چگونگی ترکیب این دو والد نیز می‌تواند با روش‌های مختلفی صورت گیرد [41] که یکی از این روش‌ها روش scattered است که مبتنی بر تولید عدد تصادفی و انتخاب ژن است.