بهینه‌سازی چندمنظوره

بهینه‌سازی چندمنظوره (همچنین با نام‌های برنامه‌ریزی چندمنظوره، بهینه‌سازی برداری، بهینه‌سازی چندمعیاره، بهینه‌سازی چندشاخه یا بهینه‌سازی پارتو نیز شناخته می‌شود) حوزه‌ای از تصمیم‌گیری چندمعیاره است که به مسائل بهینه‌سازی ریاضی مربوط شده و شامل بیش از یک تابع هدف است که باید به‌طور همزمان بهینه شوند. بهینه‌سازی چندمنظوره در بسیاری از زمینه‌های علوم از جمله مهندسی، اقتصاد و لجستیک که در آن‌ها نیاز به اتخاذ تصمیم‌های بهینه در صورت وجود بده‌بستان میان دو یا چند هدف متضاد است، استفاده می‌شود. به حداقل رساندن هزینه در حین به حداکثر رساندن راحتی هنگام خرید خودرو، و به حداکثر رساندن عملکرد در حالی که مصرف سوخت و انتشار آلاینده‌های یک وسیله نقلیه به حداقل می‌رسد، نمونه‌هایی از مسائل بهینه‌سازی چندمنظوره هستند که به ترتیب شامل دو و سه هدف می‌باشند. در مسائل عملی، می‌تواند بیش از سه هدف وجود داشته باشد.

مقدار بهینه یا بهترین راه‌حل از طریق فرآیند بهینه‌سازی، قابل یافتن است. مسائل بهینه‌سازی شامل جستجو برای مقدار بیشینه یا کمینه و یا استفاده از یک هدف یا چند هدف می‌شود. مسائلی که بیش از یک هدف دارند به بهینه‌سازی چند هدفه ( multi-objective optimization) (MOO) معروف هستند.

برای یک مسئله بهینه‌سازی چندمنظوره غیربدیهی، راه‌حل واحدی وجود ندارد که به‌طور همزمان هر هدف را بهینه کند. در آن صورت گفته می‌شود که توابع هدف متضاد هستند. دو روش بهینه‌سازی چند هدفه وجود دارد که نیازی به معادلات ریاضی پیچیده ندارند، بنابراین مشکل ساده می‌شود. این دو روش شامل پارتو و مقیاس‌بندی هستند.

در روش پارتو، یک راه‌حل تسلط‌یافته(dominated solution ) و یک راه‌حل غیر تسلط‌یافته (non-dominated solution ) با استفاده از یک الگوریتم به‌روزرسانی مداوم به‌دست می‌آید. در صورتی که نتوان ارزش هیچ‌یک از توابع هدف را بدون کاهش برخی از مقادیر هدف دیگر بهبود بخشید، به آن بهینه پارتو (جواب نامغلوب، کارآمد پارتو یا noninferior) گفته می‌شود. بدون در اختیار داشتن اطلاعات اضافی، تمامی جواب‌های بهینه پارتو به یک اندازه خوب هستند و با یکدیگر برابر در نظر گرفته می‌شوند.

در همین حال، روش مقیاس‌بندی، توابع چند هدفه را به یک راه‌حل واحد با استفاده از وزن‌ها تبدیل می‌کند. در روش مقیاس‌بندی، سه نوع وزن وجود دارد که شامل وزن‌های مساوی (equal weights)، وزن‌های مرکز رتبه‌بندی (rank order centroid weights) و وزن‌های مجموع رتبه(rank-sum weights) می‌شوند.

مفهوم هم‌ارزی (Equivalency) یا عدم فرومایگی (Non-Inferiority) برای اولین بار توسط ویلفردو پارتو و فرانسیس یسیدرو اجورث و در حوزه اقتصاد معرفی شد. از آن زمان تاکنون، مفهوم بهینه‌سازی چندمنظوره، جای پای خود را در حوزه طراحی و مهندسی مستحکم کرده‌است. ترجمه تحقیقات ویلفردو پارتو به زبان انگلیسی در سال ۱۹۷۱ میلادی، منجر به پیاده‌سازی روش بهینه‌سازی چندمنظوره در حوزه مهندسی و ریاضیات کاربردی شد

روش های بهینه سازی

---

انواع مختلفی از بهینه‌سازی‌ها وجود دارند، اما در این بحث، فقط به بهینه‌سازی چند هدفه (MOO) خواهیم پرداخت. MOO یا بهینه‌سازی چند هدفه به یافتن مقادیر بهینه برای بیش از یک هدف مورد نظر اشاره دارد. استفاده از MOO به دلیل عدم نیاز به معادلات پیچیده در بهینه‌سازی و به‌تبع ساده‌تر شدن مسئله، اهمیت دارد. مسئله تصمیم‌گیری در بهینه سازی چند هدفه (MOO)  امکان توافق (tradeoff) در مورد برخی مسائل متناقض را فراهم می کند. همانطور که گفتیم، بهینه سازی چند هدفه (MOO) توسط ویلفردو پارتو معرفی شد. در . بهینه سازی چند هدفه (MOO) ، یک بردار از تابع هدف وجود دارد. هر بردار از تابع هدف، یک تابع از بردار راه‌حل است. در MOO، بهترین راه‌حل  یکتا برای همه اهداف وجود ندارد، بلکه چندین راه‌حل وجود دارد.

. از نظر ریاضی، معادلات مسئله MOO را می توان به صورت زیر نوشت:

$\qquad \max /\min \quad f_{1}(x),f_{2}(x),...,f_{n}(x)$

$subject\quad to:x\in U$

که در آن X پاسخ است و n تعداد توابع هدف می باشد و U مجموعه‌ی امکان‌پذیر می باشد. همچنین f(x) تابع هدف و max و min عملیات ترکیبی هستند.

در MOO یک فضای چند بعدی از بردار تابع هدف و فضای متغیر تصمیم بردار حل وجود دارد. در هر راه حل x در فضای متغیر تصمیم یک نقطه در فضای تابع هدف وجود دارد. با توجه به این نگاشت، تحدب فضای راه حل و فضای تابع هدف در تعیین الگوریتم حل مسئله بسیار مهم است. اگر مسئله MOO محدب باشد، الگوریتم های زیادی وجود دارد که می توان از آنها برای حل مشکل به خوبی استفاده کرد. اگر تمام توابع هدف و ناحیه حل نیز محدب باشند، به مسائل MOO گفته می شود که محدب هستند. در همین حال، تابع هدف در صورتی محدب گفته می شود که معادله زیر را برآورده کند.

$f(\theta x+(1-\theta )y)\leqslant \theta f(x)+(1-\theta )f(y)$

.راه حل مسئله MOO را می توان به دو دسته تقسیم کرد: روش پارتو و مقیاس بندی .

روش پارتو و مقیاس بندی متفاوت اند. روش پارتو در صورتی استفاده می‌شود که راه‌حل‌ها و شاخص‌های عملکرد مورد نظر مجزا باشند و یک راه‌حل سازش (tradeoff) تولید کنند و در قالب جبهه بهینه پارتو (POF) قابل نمایش باشند. در همین حال، روش مقیاس‌بندی جزء شاخص‌های عملکردی است که یک تابع اسکالر را تشکیل می‌دهد که در تابع تناسب اندام گنجانده شده است . در بخش زیر هر دو روش توضیح داده خواهد شد.

روش پارتو :

از نظر ریاضی، مسئله MOO با استفاده از روش پارتو را می توان به صورت زیر نوشت:

$f_{1}.opt=\min f_{1}(x)$

$f_{2}.opt=\min f_{2}(x)$

.

.

$f_{n}.opt=\min f_{n}(x)$

روش پارتو عناصر بردار راه حل را در طول بهینه سازی جدا (مستقل) نگه می دارد و مفهوم تسلط وجود دارد تا راه حل های غالب و غیر غالب را متمایز کند. راه حل تسلط و مقدار بهینه در MOO معمولاً زمانی به دست می آید که یک تابع هدف بدون کاهش تابع هدف دیگر نتواند افزایش یابد. این شرط بهینه پارتو نامیده می شود. به مجموعه راه حل های بهینه در MOO راه حل بهینه پارتو می گویند. اصطلاحی وجود دارد که به آن راه حل غیرمسلط یا کارآمد پارتو می گویند. راه حلی که در آن یک تابع هدف می تواند بدون کاهش تابع هدف دیگری بهبود یابد، راه حل بهینه غیرپارتو نامیده می شود.

روش مقیاس بندی:

روش مقیاس بندی باعث می شود که تابع چند هدفه یک راه حل واحد ایجاد کند و وزن قبل از فرآیند بهینه سازی تعیین شود. روش مقیاس بندی توابع چند هدفه را در تابع تناسب اسکالر مانند معادله زیر ترکیب می کند:

$F(x)=w_{1}f_{1}(x)+w_{2}f_{2}(x)+...+w_{n}f_{n}(x).$

وزن تابع هدف راه حل تابع تناسب را تعیین می کند و اولویت عملکرد را نشان می دهد. وزن بزرگی که به یک تابع هدف داده می شود نشان می دهد که تابع مذکور در مقایسه با تابع هایی که وزن کمتری دارند اولویت بیشتری دارد.

سه رویکرد برای تعیین وزن مقیاس بندی وجود دارد که وزن های مساوی، وزن های ROC و وزن های RS هستند.

وزن های مساوی:

وزن های مساوی را می توان از معادله زیر تعیین کرد:

$w_{i}={\frac {1}{n}}$

که در آن ...,n=1,2,3 و n تعداد تابع هدف است.

وزن‌های مرکز ترتیب رتبه (ROC)ک

معیارها را می‌توان با استفاده از وزن‌های ROC رتبه‌بندی کرد. وزن ROC را می توان با استفاده از معادله زیر تعیین کرد:

$w_{i}={\frac {1}{n}}\sum _{n}^{k}{\frac {1}{k}}$

وزن‌های مجموع رتبه (RS):

وزن‌های RS هر معیار را در موقعیتی متناسب قرار می‌دهند. وزن RS را می توان با استفاده از معادله زیر تعیین کرد:

$w_{i}={\frac {2(n+1-i)}{n(n+1)}}$

در طول سه دهه اخیر، به‌کارگیری روش‌های بهینه‌سازی چندمنظوره در بسیاری از حوزه‌های مهندسی و طراحی به رشد ثابت خود ادامه داده‌است.

کاربردها:

کاربرهای روش پرتو:

انتخاب رله ها در شبکه های ad hoc با MOO از روش پارتو استفاده می کند. مشکلاتی که باید بهینه شوند عبارتند از: توان عملیاتی، تعادل بار و مصرف برق

کاربرد روش مقیاس بندی (scalarization method):

بهینه‌سازی لایه متقاطع برای انتخاب رله بهینه در شبکه بی‌سیم ad-hoc چند هاپ(multi-hop) اعمال می‌شود. شاخص‌های عملکرد بررسی‌شده عبارتند از مصرف انرژی، SNR و تعادل بار که با استفاده از روش‌های مقیاس‌بندی بهینه شده‌اند.

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «Multi-objective optimization». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۶ دسامبر ۲۰۲۲.