تکنیک اپسیلون محدود برای بهینه‌سازی دو هدفه

در خیلی از مسائل واقعی، یک هدف به‌تنهایی کافی نیست. یک شرکت هم می‌خواهد هزینه را کم کند، هم می‌خواهد کیفیت خدمات را بالا ببرد. یک برنامه‌ریز شبکه‌ی برق هم دنبال کمینه‌کردن هزینه‌ی سرمایه‌گذاری است، هم دنبال کمینه‌کردن ریسک. مشکل اینجاست که این دو هدف معمولاً با هم در تضادند: بهبود یکی، معمولاً به قیمت بدترشدن دیگری تمام می‌شود. در چنین شرایطی، عبارت «جواب بهینه» دیگر یک نقطه‌ی مشخص نیست؛ بلکه مجموعه‌ای از جواب‌هاست که هیچ‌کدام از دیگری از همه جنبه ها نیست. به این مجموعه، مرز پارتو (Pareto Front) می‌گویند.

سوال عملی این است: چطور می‌توان کل این مرز را، نه فقط یک نقطه‌ی دلبخواه روی آن، به‌صورت سیستماتیک به دست آورد؟ یکی از پرکاربردترین جواب‌ها، تکنیک اپسیلون محدود (Epsilon-Constraint Method) است.

چرا این روش را به روش وزن‌دهی ترجیح می‌دهیم

رایج‌ترین راهی که افراد ابتدا امتحان می‌کنند، ترکیب دو هدف در یک تابع وزن‌دار است:

$\min \; w_1 f_1(x) + w_2 f_2(x)$

این روش ساده است، اما دو ضعف مهم دارد. اول، انتخاب وزن‌ها ($w_1$, $w_2$) دلبخواهی است و معلوم نیست چه نسبتی از وزن‌ها، چه نقطه‌ای از مرز پارتو را نتیجه می‌دهد. دوم، و مهم‌تر، اگر مرز پارتو غیرمحدب (non-convex) باشد، هیچ ترکیبی از وزن‌ها نمی‌تواند بخش‌های فرورفته‌ی مرز را پیدا کند — آن نقاط برای این روش اصلاً «دیده نمی‌شوند». هر بار که اهمیت و وزن توابع هدف عوض شود باید مساله مجددا حل شود. تکنیک اپسیلون محدود این مشکل را دور می‌زند. ایده این است: به‌جای ترکیب دو هدف، فقط یکی را بهینه می‌کنیم و دیگری را به در یک قید محدود می‌کنیم:

$\max \; f_1(x) \quad \text{s.t.} \quad f_2(x) \geq \varepsilon,\ \ x \in \mathcal{X}$

با تغییر تدریجی $\varepsilon$ در بازه‌ی مقادیر ممکن $f_2$، هر بار یک نقطه‌ی جدید از مرز پارتو به دست می‌آید — از جمله نقاطی که روش وزن‌دهی از پیدا کردن آنها ناتوان است.

فرمول‌بندی ریاضی مسئله

برای این‌که ایده انتزاعی نماند، یک مثال کامل غیرخطی را حل می‌کنیم. دو متغیر تصمیم داریم:

$x_1, x_2 \in \mathbb{R}$

و دو تابع هدف متعارض:

$\text{of}_1 = 4x_1 - 0.5x_2^2$ $\text{of}_2 = -x_1^2 + 5x_2$

با این محدودیت‌ها:

$2x_1 + 3x_2 \leq 10$ $2x_1 - x_2 \geq 0$ $1 \leq x_1 \leq 2, \quad 1 \leq x_2 \leq 3$

چون هر دو تابع هدف شامل جمله‌ی درجه‌دوم‌اند ($x_1^2$ و $x_2^2$)، این یک مسئله‌ی برنامه‌ریزی غیرخطی (NLP) است، نه یک مسئله‌ی خطی ساده.

رویه‌ی اپسیلون محدود روی این مثال، سه گام دارد:

۱. ابتدا $\text{of}_1$ را به‌تنهایی بیشینه می‌کنیم (بدون توجه به $\text{of}_2$) تا سقف $\text{of}_1$ و مقدار متناظر $\text{of}_2$ (کف بازه‌ی $\varepsilon$) به دست بیاید.

۲. سپس $\text{of}_2$ را به‌تنهایی بیشینه می‌کنیم تا سقف بازه‌ی $\varepsilon$ مشخص شود.

۳. بازه‌ی به‌دست‌آمده برای $\text{of}_2$ را به تعداد دلخواه (مثلاً ۲۱ نقطه) به بازه‌های مساوی تقسیم می‌کنیم؛ برای هر مقدار $\varepsilon$، مسئله‌ی زیر را حل می‌کنیم:

$\max \; \text{of}_1 \quad \text{s.t.} \quad \text{of}_2 \geq \varepsilon$

هر بار حل این مسئله، یک نقطه‌ی جدید از مرز پارتو می‌دهد. کنار هم گذاشتن همه‌ی این نقاط، کل مرز را می‌سازد.

کد GAMS

همین رویه، در قالب کد GAMS این‌طور نوشته می‌شود:

Variable of1, of2, x1, x2;
Equation eq1, eq2, eq3, eq4;

eq1.. 4*x1 - 0.5*sqr(x2) =e= of1;
eq2.. -sqr(x1) + 5*x2    =e= of2;
eq3.. 2*x1 + 3*x2        =l= 10;
eq4.. 2*x1 -   x2        =g=  0;

x1.lo = 1; x1.up = 2;
x2.lo = 1; x2.up = 3;

Model pareto1 / all /;

Set counter / c1*c21 /;
Scalar E;
Parameter report(counter,*), ranges(*);

solve pareto1 using nlp maximizing of1;
ranges('OF1max') = of1.l;
ranges('OF2min') = of2.l;

solve pareto1 using nlp maximizing of2;
ranges('OF2max') = of2.l;
ranges('OF1min') = of1.l;

loop(counter,
   E = (ranges('OF2max') - ranges('OF2min'))*(ord(counter) - 1)/(card(counter) - 1) + ranges('OF2min');
   of2.lo = E;
   solve pareto1 using nlp maximizing of1;
   report(counter,'OF1') = of1.l;
   report(counter,'OF2') = of2.l;
   report(counter,'E')   = E;
);
display report;

نکته‌ی کلیدی خط of2.lo = E؛ است: همان جایی که هدف دوم را به یک کف (قید) تبدیل می‌کنیم و اجازه می‌دهیم سالور فقط $\text{of}_1$ را بیشینه کند. حلقه‌ی counter هم دقیقاً همان سوییپ ۲۱-نقطه‌ای روی $\varepsilon$ است.

نکات و دام‌های رایج این روش

مسئله‌ی این مثال فقط دو هدف دارد، اما در عمل ممکن است با سه یا چهار هدف هم روبه‌رو شوید. در آن حالت، می‌توان یک هدف را بیشینه کرد و بقیه را همگی به قید تبدیل کرد — به قیمت افزایش تعداد ترکیب‌های $\varepsilon$ که باید بررسی شوند (که به‌سرعت رشد نمایی پیدا می‌کند).

دام رایج دیگر، جواب‌های ضعیفاً کارا (weakly efficient) است: ممکن است نقطه‌ای قید $f_2 \geq \varepsilon$ را دقیقاً با تساوی برآورده کند، بدون این‌که واقعاً روی مرز پارتوی قوی باشد. نسخه‌ی پیشرفته‌تر این روش، به نام AUGMECON، با افزودن یک جمله‌ی کوچک از هدف دوم به تابع هدف اول، این مشکل را برطرف می‌کند.

پیاده‌سازی با پایتون

اگر مدل شما هم مثل این مثال غیرخطی است، می‌توانید دقیقاً همین رویه را با Pyomo پیاده‌سازی کنید: تابع هدف دوم را به‌عنوان یک Constraint با کران پایین متغیر تعریف کنید، داخل یک حلقه‌ی پایتون مقدار آن کران را تغییر دهید، و هر بار مدل را با یک سالور NLP مثل Ipopt حل کنید. اگر مدل شما خطی یا مختلط-عدد صحیح است، همین رویه با سالورهایی مثل CBC یا HiGHS هم به همان راحتی کار می‌کند. این دقیقاً همان مهارتی است که در دوره‌ی مدل‌سازی مسائل بهینه‌سازی قدم‌به‌قدم آموزش داده می‌شود.

این تکنیک صرفاً یک نکته‌ی تئوری نیست؛ در دوره‌ی پیشرفته‌ی بهینه‌سازی سیستم قدرت دقیقاً همین قدرت تکنیک اپسیلون محدود را روی مسائل واقعی سیستم قدرت دیدیم و آموزش مفصل پیاده‌سازی آن در پایتون هم در همان دوره داده شده است.

از نظر ساختار کد، تنها تفاوت نسخه‌ی پایتون با نسخه‌ی GAMS بالا، جای‌گذاری حلقه‌ی for به‌جای loop و بازتعریف کران قید در هر تکرار است — منطق ریاضی مسئله دقیقاً همان چیزی است که در فرمول‌بندی بالا آمد.

اجرای مدل روی سرور NEOS، بدون نصب سالور

احتمالا شما هم برای دستیابی به لایسنس گمز به مشکل بر خورد کرده اید. نکته‌ای که خیلی وقت‌ها نادیده گرفته می‌شود این است که برای حل این مدل‌ها، لزوماً نیازی به نصب GAMS یا یک سالور NLP تجاری روی سیستم خودتان نیست. سرور NEOS (Network-Enabled Optimization System) یک سرویس رایگان و دانشگاهی است که امکان اجرای مدل — از جمله همین مدل غیرخطی بالا — را روی سرورهای قدرتمند از راه دور فراهم می‌کند، با دسترسی به ده‌ها سالور مختلف (از جمله Ipopt، CONOPT، BARON و Knitro) بدون این‌که هیچ‌کدام را روی سیستم خودتان نصب کرده باشید. این ویژگی به‌خصوص برای دانشجویانی که به لایسنس سالورهای تجاری دسترسی ندارند، یا برای مدل‌های سنگین‌تر که به منابع محاسباتی بیشتری نیاز دارند، بسیار کاربردی است. مدل Pyomo یا فایل GAMS را می‌توان مستقیماً به NEOS ارسال کرد و نتیجه را دریافت کرد. این سرور حتی در صورتی که مدت شبیه سازی طولانی باشد نتایج را به شما ایمیل می کند. آموزش تصویری استفاده از NEOS برای این نوع مدل‌ها را اینجا ببینید: ویدیوی آموزشی اجرای مدل روی سرور NEOS

سوالات متداول

تفاوت اپسیلون محدود با روش وزن‌دهی (weighted sum) چیست؟

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

آیا این روش فقط برای دو هدف کار می‌کند؟

نه؛ می‌توان آن را به بیش از دو هدف هم تعمیم داد. در آن حالت یک هدف بهینه می‌شود و بقیه همگی به قید تبدیل می‌شوند. نکته این است که تعداد ترکیب‌های لازم برای سوییپ، با افزایش تعداد اهداف به‌سرعت رشد می‌کند.

چرا مثال این یادداشت یک NLP است، نه یک مسئله‌ی خطی ساده؟

چون هر دو تابع هدف شامل جمله‌ی درجه‌دوم‌ هستند. خودِ تکنیک اپسیلون محدود به نوع مسئله (خطی، غیرخطی، عدد صحیح) وابسته نیست و در هر سه حالت به همین شکل کار می‌کند؛ فقط باید سالور متناسب با نوع مسئله انتخاب شود.

برای پیاده‌سازی عملی این تکنیک از کجا شروع کنم؟

در دوره‌ی مدل‌سازی مسائل بهینه‌سازی مبانی تعریف متغیر، تابع هدف و قید در Pyomo از پایه آموزش داده می‌شود؛ پایه‌ی خوبی برای اضافه‌کردن حلقه‌ی سوییپ اپسیلون روی مدل خودتان.