Multi-objective optimization — بهینه‌سازی چندهدفه

بهینه‌سازی چندمعیاره (همچنین برنامه‌ریزی چندمعیاره، به انگلیسی multi-objective optimization, multi-criteria optimization) — شاخه‌ای از بهینه‌سازی ریاضی است که به مطالعهٔ مسائل بهینه‌سازی همزمان بر اساس دو یا چند تابع هدف (معیار) می‌پردازد که معمولاً با یکدیگر در تعارض هستند. به صورت رسمی، مسئله به‌صورت کمینه‌سازی تابع هدف برداری روی مجموعهٔ جواب‌های مجاز بیان می‌شود.

تعریف و اصطلاح‌شناسی

مسئلهٔ بهینه‌سازی چندمعیاره در حالت کلی به صورت زیر نوشته می‌شود: $\underset{x\in S}{\min }\{f_1(x),f_2(x),\dots ,f_k(x)\}$ که در آن $S\subseteq {\mathbb{ℝ}}^n$ — مجموعهٔ غیرتهی جواب‌های مجاز، و $f_i:S\to \mathbb{ℝ}$ — توابع هدف ($k\ge 2$) هستند. بردار $f(x)=(f_1(x),\dots ,f_k(x))$ را بردار هدف می‌نامند.

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

• جواب پارتو (جواب بهینهٔ پارتو یا جواب کارا): جواب مجاز $x^{*}\in S$ که برای آن جواب دیگری مانند $x\in S$ وجود ندارد به گونه‌ای که $f_i(x)\le f_i(x^{*})$ برای همهٔ $i=1,\dots ,k$، و در عین حال $f_j(x)<f_j(x^{*})$ برای حداقل یک اندیس $j$. به عبارت دیگر، جوابی بهینهٔ پارتو است که بهبود هیچ معیاری بدون بدتر شدن حداقل یک معیار دیگر امکان‌پذیر نباشد.
• جبههٔ پارتو (یا مجموعهٔ پارتو): مجموعهٔ تمام بردارهای هدف متناظر با جواب‌های بهینهٔ پارتو.
• جواب بهینهٔ ضعیف پارتو: جواب $x^{*}\in S$ که برای آن جواب دیگری مانند $x\in S$ وجود ندارد به گونه‌ای که $f_i(x)<f_i(x^{*})$ برای همهٔ $i$.

ویژگی‌ها و قضایای کلیدی

• قضیهٔ مجموع وزن‌دار: در مسائل محدب (که در آن‌ها همهٔ توابع $f_i(x)$ و مجموعهٔ $S$ محدب هستند) هر جواب بهینهٔ پارتو $x^{*}$ جواب مسئلهٔ اسکالر کمینه‌سازی مجموع وزن‌دار معیارها $\underset{x\in S}{\min }\sum _{i=1}^k{w}_i{f}_i(x)$ برای برخی مجموعهٔ وزن‌های نامنفی $w_i\ge 0$ است. اما در مسائل غیرمحدب، این روش ممکن است برخی بخش‌های جبههٔ پارتو را نیابد.

• شرایط بهینگی Karush-Kuhn-Tucker (KKT): شرایط لازم بهینگی برای مسائل هموار به حالت چندمعیاره تعمیم می‌یابند. در نقطهٔ بهینهٔ پارتو، مجموعهٔ غیرصفری از ضرایب نامنفی (وزن‌ها) وجود دارد که گرادیان‌های توابع هدف و قیدهای فعال به صورت خطی وابسته‌اند.

• ویژگی‌های مجموعهٔ جواب‌ها: جبههٔ پارتو دارای تعدادی مشخصهٔ کیفی مهم است. کران آن توسط نقطهٔ ایده‌آل (متشکل از کمینه‌های عنصر به عنصر همهٔ معیارها) و نقطهٔ نادیر (از بیشینه‌های عنصر به عنصر روی جبهه) تعیین می‌شود.

مثال‌ها

• مسئلهٔ خطی: کمینه کردن $f_1(x)=-x_1$ و $f_2(x)=-x_2$ با قید $x_1+x_2\le 1$، $x_1,x_2\ge 0$. در اینجا بهبود یک معیار (مثلاً افزایش $x_1$) ناگزیر به بدتر شدن معیار دیگر (کاهش $x_2$) منجر می‌شود. مجموعهٔ جواب‌های بهینهٔ پارتو یک پاره‌خط $x_1+x_2=1$ است.
• مسئلهٔ غیرمحدب: کمینه کردن $f_1(x)=x^2$ و $f_2(x)=(x-2{)}^2$ روی بازهٔ $[0,2]$. جبههٔ پارتو غیرمحدب است. روش مجموع وزن‌دار با وزن‌های مثبت نمی‌تواند جواب‌های داخل این بازه را بیابد (مثلاً در نقطهٔ $x=1$)، زیرا ترکیب خطی معیارها تنها در نقاط انتهایی $x=0$ یا $x=2$ به کمینه می‌رسد.

مفاهیم مرتبط و کاربردها

بهینه‌سازی چندمعیاره ارتباط نزدیکی با تصمیم‌گیری چندمعیاره (MCDM) دارد که به انتخاب بهترین گزینه با توجه به ترجیحات تصمیم‌گیرنده می‌پردازد. روش‌های اصلی تبدیل مسئلهٔ چندمعیاره به اسکالر (اسکالرسازی) عبارت‌اند از:

• روش مجموع وزن‌دار.
• روش قیدهای $\epsilon$: یک معیار بهینه می‌شود و بقیه به قیدهایی از نوع $f_i(x)\le {\epsilon }_i$ تبدیل می‌شوند. این روش قادر است جواب‌هایی روی بخش‌های غیرمحدب جبهه بیابد.

بهینه‌سازی چندمعیاره کاربرد گسترده‌ای در طراحی مهندسی، اقتصاد (مثلاً بهینه‌سازی سبد سرمایه‌گذاری)، مدیریت و محیط زیست دارد.

همچنین ببینید

• بهینگی پارتو
• بهینه‌سازی برداری
• نظریهٔ تصمیم‌گیری
• سیستم‌های پشتیبانی تصمیم‌گیری
• تحقیق در عملیات