Multi-objective optimization — التحسين متعدد الأهداف

التحسين متعدد الأهداف (يُعرف أيضًا باسم البرمجة متعددة الأهداف، بالإنجليزية: multi-objective optimization أو multi-criteria optimization) هو فرع من التحسين الرياضي يدرس مسائل التحسين المتزامن لدالتين أو أكثر من دوال الهدف (المعايير)، والتي تتعارض عادةً مع بعضها البعض. تُصاغ المسألة رسميًا على أنها تصغير (minimization) لدالة هدف متجهية على مجموعة الحلول الممكنة.

التعريف والمصطلحات

تُكتب مسألة التحسين متعدد الأهداف في شكلها العام على النحو التالي: $\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))$ اسم متجه الهدف.

على عكس التحسين القياسي (scalar optimization)، لا يوجد في العادة حل وحيد في مسائل التحسين متعدد الأهداف يحسّن قيم جميع المعايير في آن واحد. لذلك، يتم تعميم المفهوم التقليدي للأمثلية باستخدام مفهوم أمثلية باريتو (Pareto optimality).

• حل باريتو (حل أمثل وفق باريتو أو حل فعّال): هو حل ممكن $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$.

الخصائص والنظريات الرئيسية

• نظرية المجموع الموزون: في المسائل المحدبة (convex problems) (حيث تكون جميع الدوال $f_i(x)$ والمجموعة $S$ محدبة)، يكون أي حل أمثل وفق باريتو $x^{*}$ هو حل لمسألة قياسية تتمثل في تصغير المجموع الموزون للمعايير $\underset{x\in S}{\min }\sum _{i=1}^k{w}_i{f}_i(x)$ لمجموعة معينة من الأوزان غير السالبة $w_i\ge 0$. ومع ذلك، في المسائل غير المحدبة، قد لا تتمكن هذه الطريقة من العثور على أجزاء معينة من جبهة باريتو.

• شروط كاروش-كون-تاكر للأمثلية (KKT): يتم تعميم الشروط الضرورية للأمثلية في المسائل الملساء (smooth problems) لتشمل الحالة متعددة المعايير. عند نقطة أمثلية باريتو، توجد مجموعة غير صفرية من المضاعفات (الأوزان) غير السالبة التي تكون فيها تدرجات (gradients) دوال الهدف والقيود النشطة (active constraints) مرتبطة خطيًا.

• خصائص مجموعة الحلول: تتمتع جبهة باريتو بعدد من الخصائص النوعية الهامة. حدودها محصورة بين النقطة المثالية (ideal point) (المكونة من الحدود الدنيا لكل معيار على حدة) ونقطة النظير (nadir point) (المكونة من الحدود القصوى لكل معيار على الجبهة).

أمثلة

• مسألة خطية: صغّر $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)، وهو مجال يدرس كيفية اختيار البديل الأفضل مع مراعاة تفضيلات صانع القرار. تشمل الطرق الرئيسية لتحويل المسألة متعددة المعايير إلى مسألة قياسية (scalarization) ما يلي:

• طريقة المجموع الموزون.
• طريقة قيود $\epsilon$‏ (ε-constraint method): تتم أمثلة معيار واحد، بينما تُحوَّل المعايير الأخرى إلى قيود على شكل $f_i(x)\le {\epsilon }_i$. هذه الطريقة قادرة على إيجاد حلول في الأجزاء غير المحدبة من الجبهة.

يجد التحسين متعدد الأهداف تطبيقات واسعة في التصميم الهندسي، والاقتصاد (مثل تحسين المحافظ الاستثمارية)، والإدارة، والبيئة.

انظر أيضًا

• أمثلية باريتو
• التحسين المتجهي
• نظرية اتخاذ القرارات
• نظم دعم اتخاذ القرار
• بحوث العمليات