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

y_1,1^1
y_1,2^1
y_1,3^1

y_(1,|J|)^1

y_2,1^1
y_2,2^1
y_2,3^1

y_(2,|J|)^1

y_3,1^1
y_3,2^1
y_3,3^1

y_(3,|J|)^1

y_4,1^1
y_4,2^1
y_4,3^1

y_(4,|J|)^1

y_5,1^1
y_5,2^1
y_5,3^1

y_(5,|J|)^1





y_(|I|,1)^1
y_(|I|,2)^1
y_(|I|,3)^1

y_(|I|,|J|)^1
Child
y_5,1^1
y_5,2^1
y_5,3^1

y_(5,|J|)^1





y_(|I|,1)^1
y_(|I|,2)^1
y_(|I|,3)^1

y_(|I|,|J|)^1

y_2,1^1
y_2,2^1
y_2,3^1

y_(2,|J|)^1

y_3,1^1
y_3,2^1
y_3,3^1

y_(3,|J|)^1

y_4,1^1
y_4,2^1
y_4,3^1

y_(4,|J|)^1

y_1,1^1
y_1,2^1
y_1,3^1

y_(1,|J|)^1
3-3-8- انتخاب47
انتخاب کروموزومهای واجد شرایط برای پیاده سازی عملگرهای تقاطع و جهش و تولید فرزندان جدید، ارائه شده در این تحقیق، بر اساس روش چرخه رولت میباشد. بدین ترتیب که هر جواب که تابع هدف بهتری داشت مقدار برازش48 بالاتر و در نتیجه شانس انتخاب بیشتری جهت انتخاب شدن خواهد داشت. از آنجا که تابع هدف مسئله تحقیق، کمینه سازC_Max است، پس هر جوابی که مقدار یابع هدف کمتری داشته باشد، برازندهتر است. بنابراین جهت تطابق مفهوم تابع هدف با برازش، تابع برازندگی برای کروموزوم K ام، به صورت مقابل تعریف میشود:
f(k)=1⁄(C_Max (k))
3-3-9- معیار توقف
شرط توقف الگوریتم، میتواند عدم تغیرجواب در چند تکرار متوالی، سپری شدن مدت زمان معینی از حل یا هر شرط خاص دیگر باشد. در الگوریتم ژنتیک پیشنهادی شرط توقف، تولید معینی نسل (Max-Gen) از جمعیت اولیه است.
فلوچارت الگوریتم ژنتیک پیشنهادی در شکل(3-3) آمده است.

شکل( 3- 3). فلوچارت الگوریت ژنتیک
3-4- آزادسازی لاگرانژ
3-4-1- مقدمه
بسیار از الگوریتمهای ابتکاری در حل مسائل مکانیابی- تخصیص بسیار موفق عمل میکنند. اگرچه، ما مطمئن نیستیم که این الگوریتمها یا هر الگوریتمهای ابتکاری دیگری به ما جواب خوب و قابل قبولی دهد. در بسیاری از موارد، حل بدست آمده ممکن است بهینه و یا خیلی نزدیک به جواب بهینه باشد. در دیگر موارد، حل بدست آمده خیلی دور از جواب بهینه باشد. حال یک الگوریتمی را فراخوانی میکنیم که به ما جواب بهینه و یا خیلی نزدیک به بهینه را دهد. از اینرو، ما الگوریتم آزاد سازی لاگرانژ برای مسئله مکانیابی- تخصیص را مورد بررسی قرار میدهیم. آزاد سازی لاگرانژ یکی از روش حل برای مسائل سخت از قبیل مسائل برنامه ریزی عدد صحیح میباشد.
روش آزاد سازی لاگرانژ بر اساس شناخت یک مجموعه از محدودیت های پیچیده در مدل میباشد. این محدودیت ها بوسیله ضریبی که به آن ضریب لاگرانژ49 گفته میشود به تابع هدف اضافه میشود. مسئله آزاد سازی لاگرانژ یک روش حل بر اساس تکرار است، که ضرایب لاگرانژ در جریان حل تعدیل میشود. از روش بهینه سازی گرادیان50 برای بهنگام کردن ضرایب لاگرانژ در هر تکرار مختلف استفاده میگیرد [49]. یکی از روشهای ارزیابی الگوریتم آزاد سازی لاگرانژ این است که به یک تعداد مشخصی از تکرار برسد. ارزیابیهای مختلفی برای این روش آزاد سازی لاگرانژ وجود دارد از جمله فیشر [50] و گئوفریون [51] میتوان نام برد.
3-4-2- مراحل الگوریتم آزاد سازی لاگرانژ
روش آزاد سازی لاگرانژ برای مسائل مکان یابی- تخصیص شامل مراحل زیر میباشد:
ساده کردن یک یا چند محدودیت بوسیله ضرایب لاگرانژ و بردن این محدودیت به تابع هدف.
حل مسئله ساده شده برای بدست آوردن مقدار بهینه برای متغیرهای تصمیم مسئله اصلی.
استفاده ازنتایج متغیرهای تصمیم از حل مسئله ساده سازی شده در مرحله (2) برای پیدا کردن حل شدنی برای مسئله اصلی.
استفاده از حل بدست آمده در مرحله(2) برای محاسبه حد پایینی که بهترین مقدار برای تابع هدف است.
بررسی حل بدست آمده در مرحله (2) و تعیین میزان تخلف محدودیت ساده شده. برای مثال، با استفاده از روش بهینهسازی شیبی با تغییر ضرایب لاگرانژ در هر تکرار، میزان تخلف محدودیتها در تکرار بعدی کمتر میشود.

3-4-3- شرط توقف
شرط توقف زمانی برای الگوریتم لاگرانژ اتفاق می افتد که یکی از شرایط زیر رخ دهد:
زمانی که الگوریتم به یک تعداد مشخصی از تکرار رسید.
حد پایین برابر با حد بالا (UB=L^n) و یاL^n خیلی نزدیک به UB باشد.
زمانی که هیچ تخلفی در محدودیت ساده شده نباشد(محدودیت ساده سازی شده برای مسئله اصلی صادق باشد).

3-4-4- رویه انجام الگوریتم آزاد سازی لاگرانژ
آزاد سازی لاگرانژ برای پیدا کردن حد پایینی برای مسئله مکانیابی- تخصیص با تقاضای برنولی پیشنهادی شده است. روش آزادسازی لاگرانژ لاگرانژ زمانی تاثیر گذار است که محدودیتی ساده سازی شده درست انتخاب شود. نتیجه ساده سازی باید حل مسئله اصلی را آسان کرده و یک حد پایین منطقی و خوبی را برای مسئله فراهم کند؛ در غیر این صورت ساده سازی هیچ گونه منفعتی برای مسئله ندارد. حال، ما محدودیت(3-20) که محدودیت تخصیص مسئله که یک محدودیت تاثیرگذار و کلیدی مسئله پیشنهادی ما است را انتخاب و ساده سازی میکنیم. یک ضریب لاگرانژ (μ_j≥0) برای این محدودیت استفاده کرده و آن را بصورت زیر به تابع هدف اضافه میکنیم.
∑_(j∈J)▒〖μ_j (∑_(i∈I)▒〖x_ij-1〗)〗
(3-33)
پس ساده سازی کردن محدودیت (23) و بردن آن به تابع هدف مسئله را می توان بصورت زیر نوشت:
min┬⁡〖 ∑_(i∈I)▒∑_(t=l_i)^|J|▒〖f_i y_it 〗+∑_(i∈I)▒∑_
(j
∈J)▒〖(pc_ij 〖+μ_j)x〗_ij 〗-∑_jϵJ▒μ_j +∑_(i∈I)▒[∑_(t=l_i)^|J|▒w_it [g_i ∑_(s=k_i+1)^t▒〖b_ts (s-k_i )+v_i 〗]] +∑_(i∈I)▒[∑_(t=l_i)^(|J|)▒y_it h_i [∑_(s=k_i+1)^t▒〖b_ts (s-k_i ) 〗]-∑_(t=l_i)^(|J|)▒w_it h_i [∑_(s=k_i+1)^t▒〖b_ts (s-k_i ) 〗]] 〗

(3-34)
محدودیت های (3-21)- (3-27) و (3-29)-(3-31).
ضرایب لاگرانژ در هر تکرار به وسیله روش بهینه سازی گرادیان استاندارد بهبود مییابد و این امر سبب رسیدن الگوریتم به جواب بهینه میشود. بعد انتخاب محدودیت(3-20) و بردن آن به تابع هدف باید طبق الگوریتم محاسباتی انجام میدهیم و مقدار دهی اولیهای برای بعضی از پارامترها در نظر میگیریم که بصورت زیر تعریف میکنیم. قبل آن اندازه قدم در هر تکرار از روش آزاد سازی لاگرانژ بصورت زیر محاسبه میشود:
t^n=(α^n (UB-Z_LR^n))/(∑_jϵJ▒〖(∑_(i∈I)▒x_ij -1)^2 〗)
(3-35)

〖،t〗^n
Setp size در تکرار n^th از روش آزاد سازی لاگرانژ.
،α^n
یک مقدار ثابت در تکرار n^th ، در تکرار اول مقدارα^1 ،2 میدهیم.
،UB
بهترین (کمترین) حد بالا مقدار تابع هدف برای مدل پیشنهادی.
،Z_LR^n
مقدار تابع هدف بدست آمده از روش ساده سازی لاگرانز در تکرارn^th.
،x_ij^n
مقدار بهینه از متعیر تخصیص،x_ij در هر تکرارn^th.
=MAX_n500

ساختار کلی یک الگوریتم آزاد سازی لاگرانژ را می‌توان به صورت ذیل بیان کرد :
جدول( 3- 7). روش بهینه سازی گرادیان
Step 1

n=0; Initialize multipliers μ_j∈[▁c_j,¯c_j], that ▁( c)_j=Min{c_ij}, ¯c_j=Max{c_ij}
Set lower bound LB=0 and upper bound UB=Z ̂
Where Z ̂ is any feasible solution, e.g., final solution obtained from Genetic Algorithm

Step 2

Calculate Z_LR^n=Z_LR ( μ_j) .
Set LB=max⁡{LB,Z_LR^n}.
If UB-LB≤ε or n=MAX_n then STOP else go to step 3.

Step 3

Compute subgradients and step size
Subgradients: ∑_jϵJ▒〖(∑_(i∈I)▒x_ij -1)^2 〗
Step size : t^n=(α^n (Z ̂-Z_LR^n))/(∑_jϵJ▒〖(∑_(i∈I)▒x_ij -1)^2 〗)
If Z_LR^n-Z_LR^(n-1)≤0 then use〖 α〗^n=〖1/2 α〗^(n-1), if not use〖 α〗^n=α^(n-1).

Step 4
Update each multiplier as μ_j^(n+1)=max⁡{0,μ_j^n-t^n (∑_iϵI▒〖x_ij^n-1〗)}.

Step 5
Set n=n+1 and go to Step 2.

فصل چهارم:

نتایج محاسباتی

4-1- مقدمه

                                                    .

ادمین

پاسخی بگذارید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

Next Post

پایان نامه با کلید واژگان رایزوسفر، رفسنجان، پتری، انار

ش دی ۸ , ۱۳۹۷
طوقه4صفائیه رفسنجان+رایزوسفر درخت پسته5صفائیه رفسنجان–خاک اطراف طوقه6کوثرریز-رفسنجان+رایزوسفر درخت پسته7کوثرریز رفسنجان–خاک اطراف طوقه8فردوسیه نوق+رایزوسفر درخت پسته9فردوسیه نوق–خاک اطراف طوقه10فردوسیه نوق–رایزوسفر درخت پسته11سه قریه نوق+خاک اطراف طوقه12سه قریه نوق–خاک اطراف طوقهادامه جدول1-313سه قریه نوق–رایزوسفر درخت پسته14عیش آباد+خاک اطراف طوقه15عیش آباد رفسنجان–رایزوسفر درخت پسته16عیش آباد رفسنجان+رایزوسفر درخت پسته17تاج آبادرفسنجان+خاک اطراف طوقه18تاج آباد رفسنجان–خاک […]