Çok Amaçlı Optimizasyon

Çok amaçlı optimizasyon, min/max f(x) = (f_1(x), f_2(x), ..., f_k(x)) biçiminde k≥2 amaç fonksiyonunun aynı kısıt kümesi (x ∈ X) üzerinde eş zamanlı optimize edildiği problem sınıfıdır. Tek bir global optimum yerine Pareto-etkin küme aranır: x* Pareto-optimal'dir ancak ve ancak hiçbir y ∈ X için her i'de f_i(y) ≤ f_i(x*) ve en az bir j'de katı eşitsizlik geçerli değilse (Pareto 1906). Skalerleştirme yaklaşımları beş ana kategoriye ayrılır: (1) Ağırlıklı toplam (weighted sum) — min Σ w_i f_i, dışbükey Pareto cephesi noktalarına ulaşır ancak iç-bükey bölgeleri kaçırır; (2) ε-kısıt yöntemi (Haimes ve diğerleri 1971) — bir amacı optimize ederken diğerleri f_i ≤ ε_i kısıdı olarak; tüm Pareto cephesini tarayabilir; (3) Leksikografik sıralama — amaçlar öncelik sırasına göre teker teker optimize edilir, önceki seviyenin optimum değeri kısıt olarak eklenir; (4) Hedef programlama (Charnes ve Cooper 1961) — her amaç için aspiration level, sapma değişkenleri minimize edilir; (5) Çok amaçlı meta-sezgiseller — NSGA-II (Deb ve diğerleri 2002), SPEA2 (Zitzler ve diğerleri 2001) genetik popülasyon ile Pareto cephesini paralel olarak yakınsar. Karmaşıklık: amaçlar lineer ise her skalerleştirme LP olarak çözülür; tam Pareto kümesinin sayım/temsil hesaplaması genelde NP-hard. Referans monografilar Miettinen (1999), Steuer (1986) ve Ehrgott (2005).