اپراتورهای تعدیل[۲۵۹]
دو نوع تعدیل در این الگوریتم بکار گرفته شده است که یکی روی قسمت A و دیگری روی قسمت B از کروموزوم اعمال می شود:
اپراتور تعدیل کننده قسمت A
با اعمال هر یک از عملگرها بر روی قسمت A، ترکیب بندی تولید و الگوی نیروی کار تغییر مینماید که گاهی منجر به متجاوز شدن تعداد محصول تولید شده از میزان منابع در دسترس می شود که غیرموجه شدن کروموزوم را سبب می شود. بنابراین در این حالت یک اپراتور تعدیلی مورد نیاز است تا این جواب نشدنی را به یک جواب شدنی تبدیل نماید. در این قسمت یک اپراتور تعدیلی طوری طراحی شده است که بصورت تصادفی جواب را تغییر میدهد تا کروموزوم شدنی حاصل شود. نکته مهم این است که با قرار دادن یک شمارشگر، میتوان تنظیم نمود چنانچه با تکرار متوالی این عملگر بعد از تعداد معین، همچنان کروموزوم نشدنی باقی مانده باشد، کروموزوم را حذف نموده و مجدداً بر اساس استراتژی تولید جواب شدنی، اقدام به تولید کروموزوم جایگزین نماید.
اپراتور تعدیل کننده قسمت B
با اعمال اپراتورهای مختلف روی قسمت B، برخی محدودیتهای مربوط به مشتریان تحت سناریوهای مختلف ممکن است دچار تناقض گردد. بنابراین یک اپراتور تعدیل کننده در این قسمت تعبیه شده است که با تغییر تصادفی برخی درایههای این کروموزوم سعی در شدنی بودن آن نماید، ضمن اینکه جابجایی سناریوها نیز به عنوان یک استراتژی تعدیل مورد استفاده قرار میگیرد. به این ترتیب که یک کروموزوم تحت یک سناریو ممکن است نشدنی باشد اما تحت سناریوی دیگری شدنی شود به همین دلیل جابجایی سناریوها نیز آزمون می شود. اگر چنانچه با تکرار متوالی این اپراتور تعدیل کننده، کروموزوم مورد نظر همچنان نشدنی باقی بماند. با بهره گرفتن از استراتژی تولید جواب شدنی اولیه، بر اساس کروموزوم قسمت A مربوطه، نیازمندی ها و محدودیت ها تحت سناریوهای مختلف محاسبه شده و یک کروموزوم شدنی جایگزین کروموزم نشدنی موجود می شود.
قدم های الگوریتم ژنتیک پیشنهادی
پارامترهای کنترلی U (تعداد کروموزومهای هر نسل)، G (تعداد نسل ها)، θ (درصد عملگر جابجائی) و λ (درصد شایسته سالاری) را مقدار دهی نمائید.
جمعیت اولیه را تولید کن.
شمارندههای u= 1 (شمارنده جمعیت) و g = 1 (شمارنده نسل) را مقدار دهی اولیه کن.
تعداد کروموزومهایی که بایستی مستقیماً به نسل بعد منتقل شوند را از طریق فرمول زیر محاسبه کن.
Nelitism = (U-1) ×λ+۱
تعداد دفعاتی که هر عملگر (جابجائی و جهش) بایستی بکار رود را از طریق فرمول زیر محاسبه کن.
Ncrossover = (U- Nelitism) × θ + ۱, Nmutation = U - Nelitism - Ncrossover
مقدار تابع برازندگی جمعیت جاری را تحت عنوان F(X1g), F(X1g), …, F(XUg)محاسبه کن.
مقدار برازندگی جمعیت را تحت عنوان Z1, Z1, …, ZU نرمال سازی کن که در آن ( μg مقدار میانگین برازندگی و σg مقدار انحراف معیار برازندگی جمعیت میباشد).
به تعداد Nelitism بهترین کروموزومهای نسل قبل را مستقیماً به نسل جاری منتقل کن و قرار بده u = Nelitism – ۱٫
استخر ترکیب را انتخاب کن (جواب هایی از Xi که در آن Zi ≤ ۰)
دو کروموزوم را به صورت تصادفی از استخر ترکیب انتخاب کن.
یکی از عملگرهای سه گانه تعریف شده (ستونی، بلوکی و نامنظم) را بصورت تصادفی بر قسمت های مرتبط از کروموزومهای انتخاب شده اعمال کن.
کروموزومهای فرزند را تا رسیدن به یک کرموزوم شدنی تعدیل کن.
اگر مجموع مقادیر تابع برازندگی فرزندان از مجموع مقادیر تابع برازندگی والدین کمتر شد، هر دو را به نسل بعدی منتقل کن و قرار بده u = u + 2، در غیر اینصورت اگر تابع برازندگی یکی از فرزندان کمتر از والدین باشد تنها همین کروموزوم را به نسل بعد منتقل کن و قرار بده u = u + 1.
اگر u < Ncrossover + Nelitism برو به قدم ۱۰٫
یکی از کروموزومهای نسل قبل را به صورت تصادفی انتخاب کن.
یکی از عملگرهای جهش تعریف شده (ستونی، بلوکی و نامنظم) را بصورت تصادفی بر قسمت های مربوطه از کروموزوم انتخابی اعمال کن.
کروموزوم فرزند را تا رسیدن به جواب شدنی تعدیل کن.
کروموزوم فرزند شدنی را مستقیماً به نسل بعدی منتقل کن.
اگر u < U قرار بده u = u + 1 و برو به قدم ۱۵٫
اگر g < G یا معیار توقف برقرار نشد قرار بده g = g + 1 و برو به قدم ۶٫
الگوریتم را متوقف کن و بهترین جواب بدست آمده را گزارش کن.
معیار توقف الگوریتم
تعداد نسل ها؛ در این حالت، چنانچه تعداد نسل ها از یک عدد از پیش تعریف شده بیشتر گردد الگوریتم متوقف می شود و بهترین جواب بدست آمده تا آن لحظه را گزارش میدهد.
بازه زمانی؛ در این حالت، چنانچه زمان حل از یک مقدار تعیین شده برای آن بیشتر شود الگوریتم متوقف شده و بهترین جواب بدست آمده تا آن لحظه را گزارش میدهد.
بهبود تابع برازندگی؛ در این حالت، چنانچه بهبود در میزان تابع برازندگی در چند دوره مشخص متوالی از یک درصد از پیش تعیین شده ای کمتر باشد، الگوریتم متوقف می شود و بهترین جواب بدست آمده تا آن لحظه را گزارش میدهد.
الگوریتم ژنتیک پیشنهادی در حلقه داخلی الگوریتم اپسیلون-محدودیت تعبیه شده است و در تولید جدول عایدات و نیز تولید جوابهای پارتویی مسئله برنامه ریزی تک هدفه تصادفی به کار میرود. فلوچارت کلی الگوریتم پیشنهادی به صورت شکل ۴-۱۹ است.
N سناریو را با بهره گرفتن از روش مونت کارلوی توسعه یافته تولید نمائید
الگوریتم ژنتیک را برای تولید جدول عایدات اجرا کنید
Min Zj(x), k=1,…, K