پاورپوینت مسئله ی بهینه سازی با چند تابع هدف

بخشی از پاورپوینت

اسلاید 1 :

مسئله ی بهینه سازی با چند تابع هدف

اسلاید 2 :

معرفی
کلیات
روش های تکاملی
بررسي روش SPEA
بررسی روش NSGA

اسلاید 3 :

معرفی

اسلاید 4 :

بهینه سازی توابع مختلف و گاه متضاد به طور همزمان
ترکیب مقادیر توابع هدف مختلف و به دست آوردن یک مقدار برازندگی (Fitness)
مسئله به یک تابع تک هدفی تبدیل می شود.
بدست آوردن جواب هایی که حداکثر تعداد توابع هدف را بهینه کند
مجموعه جواب بهینه ی پارتو (Pareto Optimal Set).

اسلاید 5 :

مجموعه جواب بهینه ی پارتو (Pareto Optimal Set)
مجموعه جواب های مسلط نشدنی در تمام فضای جستجو.
نمی توان در این دو مجموعه بین دو جواب مختلف یکی را به دیگری برتری داد.
الگوریتم سعی در رسیدن به جواب مختلف بهینه ی پارتو دارد.

اسلاید 6 :

دو اصل مهم برای بهینه سازی با چند تابع هدف:
هدایت مسیر جستجو در جهت رسیدن به منحنی جواب های بهینه پارتو
حفظ و تولید جواب های بهینه در طول جمعیت جواب ها

اسلاید 7 :

روش های قدیمی دارای اشکالات زیر هستند:
عدم پیدا کردن چندین جواب بهینه در طی یک بار اجرای الگوریتم
عدم تضمین برای یافتن جواب های بهینه مختلف و متفاوت
نمی توان برای مسائلی با متغیرهای گسسته و دارای چندین جواب بهینه به کار برد

اسلاید 9 :

Maximaze y = f(x) = (f1(x), f2(x),…, fk(x))
Subject to e(x) = (e1(x), e2(x),…, em(x))
Where x = (x1, x2,…,xn) X
y = (y1, y2,…,yk) Y
X: بردار تصمیم گیری با پارامترهای مورد جستجو در مســـئله (Dicision Vector)
X: فضای تصمیم گیری (Dicision Space)
Y: فضای هدف (Objective Space)

اسلاید 10 :

مجموعه ممکن(Feasible Set) : مجموعه متغیرهای قابل قبول برای مسئله
Xf = {x X | e(x) ≤ 0}
محدوده ممکن (Feasible Region):
Yf = f(Xf) = Ux Xf {f(x)}

اسلاید 11 :

u و v دو بردار هدف مربوط به دو بردار تصمیم گیری:

u = v iff i {1, 2,…, k} ui = v
u ≥ v iff I {1, 2,…, k} ui ≥ vi
u > v iff u ≥ v ^ u ≠ v

اسلاید 12 :

غلبه پارتو:
سه حالت وجود دارد:
f(a) ≥ f(b)
f(b) ≥ f(a)
f(a) ≥ f(b) ^ f(b) ≥ f(a)

a > b a dominates b iff f(a) > f(b)
a ≥ b a weakly dominates b iff f(a) ≥ f(b)
a ~ b a is indifferent b iff f(a) ≥ f(b) ^ f(b) ≥ f(a)

اسلاید 13 :

مجموعه و منحنی جوابهای مسلط نشدنی
a Xf is Non-Dominated iff S Xf| x S :x>a

a is Pareto Optimal iff x is Non-Dominated regarding S = Xf

اسلاید 14 :

مجموعه و منحنی جواب های مسلط نشدنی
x1 را بر x2 غالب می دانیم اگر:
f1(x1) ≥ f1(x2) for all objective
f1(x1) > f1(x2) for at least one
تابع P(S):
P(S) = {a S, S Xf| a is NonDominated regarding S}
P(S) تمام جواب های مسلط نشدنی را نسبت به مجموعه S باز می گرداند.
f(P(S)) منحنی مسلط نشدنی نسبت به زیر مجموعه S می باشد.
Xp = P(Xf) مجموعی بهینه پارتو است.
Yp = f(Xf) منحنی بهینه پارتو است.

اسلاید 15 :

تفاوت میان مجموعه مسلط نشدنی و بهینه پارتو
مجموعه جواب مسلط نشدنی در قسمتی از فضای جستجو نسبت به جوابهای دیگر بهینه است، اگر قسمت انتخاب شده برابر کل فضای جستجو باشد مجموعه مسلط نشدنی تبدیل به مجموعه بهینه پارتو می شود.

اسلاید 16 :

انتساب مقدار برازندگی و مرحله انتخاب
بر خلاف بهینه سازی با یک تابع هدف، در MOP بین مقادیر هر تابع هدف و مقدار برازندگی تفاوت وجود دارد:
روش هایی که توابع هدف را از یکدیگر مستقل فرض می نمایند
روش هایی که جهت حفظ پراکندگی در جمعیت جواب ها به کار برده می شوند

اسلاید 17 :

مسائل اساسی در جستجو با چند تابع هدف
دو نکته اساسی در الگوریتمهای تکاملی را باید درنظر گرفت تا بتوان روشهای بهینه سازی چندتابعی تکاملی داشت:
در الگوریتم تکاملی چگونه مراحل انتخاب و انتساب مقدار fitness انجام گردد تا مجموعه جوابهای بهینه پارتو بدست آید.
جهت بدست آوردن جوابهای متنوع و مختلف و جلوگیری از همگرایی زودرس چه تدبیری اندیشیده شود.

اسلاید 18 :

مراحل انتخاب و انتساب مقدار FITNESS
روشها را از دو جنبه بررسی می شود
روشهایی که توابع هدف را مستقل از هم فرض کند.
روشهایی در جهت حفظ پراکندگی

اسلاید 19 :

روشهایی با فرض توابع هدف مستقل از هم فرض
انتخاب بر اساس تمرکز کردن روی توابع هدف:
به جای ترکیب مقادیر توابع هدف در داخل یک fitness، روی یکی از توابع هدف تمرکز می کنیم و مقدار آن را به عنوان fitness در نظر می گیریم. مثلا اگر قرار باشد N عمل انتخاب انجام شود و K تعداد توابع هدف باشد، N/K عمل انتخاب بر اساس مقدار هر کدام از توابع هدف جداگانه انجام می شود.
عمل انتخاب به صورت یک ترتیب مشخص یا تصادفی
در نظر گرفتن یک احتمال برای هر کدام از هدف ها

اسلاید 20 :

روشهایی با فرض توابع هدف مستقل از هم فرض
انتخابگرهای ترکیبی:
ترکیب مقادیر توابع هدف طبق یک رابطه خاص، مثلا می توان از مجموع وزن دار مقادیر توابع هدف استفاده کرد. مقدار این مجموع به عنوان fitness در نظر گرفته می شود.

انتخاب بر اساس مفهوم پارتو:
یک رویه مرتب سازی(رتبه دهی Ranking) تکراری جهت رتبه بندی اعضای جمعیت انجام می پذیرد.
رتبه بندی بر اساس کل جمعیت انجام می شود.