التحسين متعدد الأهداف

يعالج التحسين متعدد الأهداف مسائل من الشكل min/max f(x) = (f_1(x), f_2(x), ..., f_k(x)) مع k≥2 من الأهداف على مجموعة قيود مشتركة x ∈ X. بدلاً من حل أمثل عام وحيد، تُطلب مجموعة باريتو الكفؤة: x* هو باريتو-أمثل إذا وفقط إذا لم يوجد y ∈ X يحقق f_i(y) ≤ f_i(x*) لكل i مع متباينة صارمة لـ j واحد على الأقل (Pareto 1906). تنقسم مناهج التحويل إلى دالة قياسية إلى خمس عائلات: (1) المجموع الموزون — min Σ w_i f_i، يستعيد نقاطاً على الغلاف المحدب لجبهة باريتو لكنه يفقد المناطق غير المحدبة؛ (2) طريقة ε-القيد (Haimes وآخرون 1971) — يُحسَّن هدف واحد بينما تُقيد الأهداف الأخرى f_i ≤ ε_i؛ يمكنها مسح كامل الجبهة؛ (3) الترتيب المعجمي — تُحسَّن الأهداف تسلسلياً حسب الأولوية وتدخل القيمة المثلى السابقة كقيد في المرحلة التالية؛ (4) البرمجة بالأهداف (Charnes و Cooper 1961) — مستوى طموح لكل هدف وتُقلَّل متغيرات الانحراف؛ (5) ميتاهيوريستيك متعدد الأهداف — NSGA-II (Deb وآخرون 2002)، SPEA2 (Zitzler وآخرون 2001) يطوران مجتمعاً يتقارب بالتوازي نحو جبهة باريتو. التعقيد: كل تحويل قياسي هو LP إذا كانت الأهداف خطية؛ تعداد أو تمثيل مجموعة باريتو الكاملة عموماً NP-صعب. مراجع أساسية: Miettinen (1999) و Steuer (1986) و Ehrgott (2005).