多目的最適化とパレートフロント

工学的な問題の大多数は複数の特性を改善する多目的最適化問題です。最適化対象が複数ある場合、最適解は1つにはなりません。最適化対象が２つの場合は最適なトレードオフ曲線が解となり、3つ以上の場合はトレードオフ曲面が解になります。

パレートフロント

前述の通り、トレードオフ関係にある複数の応答（評価関数）を最適化すると、一意に定まらないため複数の最適解が得られます。これら複数の最適解をパレート解（pareto solution）、非劣解（non-dominated solution）と呼びます。これを評価関数空間にプロットしたときに得られる曲線をパレートフロントと呼称し、ようするに最適なトレードオフ曲線（曲面）を表します。

例として2目的の最小化を考えた時、得られたデータがFig.1のようであったとします。このときFig.2の赤線が最適なトレードオフラインになります。

f:id:OceanOne:20200629024543j:plain:w450 — Fig.1 データサンプル

f:id:OceanOne:20200629024609j:plain:w450 — Fig.2 トレードオフライン

パレートという言葉は、イタリアの経済学者であり社会学者のヴィルフレド・パレート（Vilfredo Federico Damaso Pareto、1848 - 1923）に由来します。彼が提唱したパレート効率性（Pareto efficiency）は、近代経済学の中で資源配分に関する概念のひとつです。資源配分に関する最適なトレードオフ曲面をパレート最適（Paretian optimum）と呼びました。

非劣解という言葉の方は実際に、データ集合からパレート解を抽出する計算手続きから来ています。[math]x_i[/math]における複数の評価関数値が[math]x_j[/math]の全ての評価関数値より劣っている場合、支配されている（dominated）と呼びます。一つでも劣っていない（non-dominated）解は、非劣解の候補となります。

f:id:OceanOne:20200629024918j:plain:w450 — Fig.3 [math]x_i[/math]と[math]x_j[/math]の支配関係

この手続きを全てのデータに対して行い、支配されていない解の集合が非劣解となります。

f:id:OceanOne:20200629025003j:plain:w450 — Fig.4 非劣解集合（赤線）

ここで言う評価関数については性能面をイメージする方が多いと思います。しかし、経済活動を考えるとかならず評価関数にコスト（対象工程の導入価格、スループット、維持費）が入っていきます。エンジニア実務をしたことがある方なら、誰しも性能とコストのトレードオフについて考えている（考えるべき）と思います。

多目的最適化問題

入力変数ベクトルXと複数の評価関数が与えられたとき、最適なトレードオフ曲線（曲面）を与えるアルゴリズムがあります。進化型多目的最適化アルゴリズム（Evolutionary Multi-criterion Optimization, EMO）などです。進化型アルゴリズムというのは確率的な探索を行うもので、進化を模した遺伝的アルゴリズム（Genetic Algorithms, GA）や動物の群れの動きを模した（Particle Swarm Optimization, PSO）など様々な手法が存在します。