Open nekonookangae opened 4 years ago
https://arxiv.org/abs/1706.02766
Yuan Yuan, Yew-Soon Ong, Liang Feng, A.K. Qin, Abhishek Gupta, Bingshui Da, Qingfu Zhang, Kay Chen Tan, Yaochu Jin, Hisao Ishibuchi
2017/1/8
入力される情報ストリームの多様性と量が爆発的に増加しているため、インテリジェントなシステムやアルゴリズムが効率的なマルチタスク処理が可能であることが非常に望まれています。 進化アルゴリズム(EA)は、母集団ベースの探索アルゴリズムの一種であり、複数の最適化タスクを一度に処理できる固有の能力を持っています。 進化的マルチタスク[1], [2]は、このEAの特性を利用して、進化的計算(EC)の新しいパラダイムとなっています。 進化的マルチタスクに関する最初のチュートリアル（"Evolutionary Multitasking and Implications for Cloud Computing"）は、IEEE Congress on Evolutionary Computation (CEC) 2015（仙台、日本）で発表されました。 それ以来、このトピックに関する一連の研究が様々な観点から行われ、進化的マルチタスクの可能性を示すだけでなく、このパラダイムがなぜ機能するのかをある程度説明しています。 進化的多目的最適化（Evolutionary Multi Objective Optimization: EMO）[11]-[13]は、過去20年以上にわたってECの分野で常に人気のあるトピックとなっています。 その理由は主に以下の2つの側面にあります。 一方で、実世界のアプリケーションにおける多くの最適化問題は、本質的に多目的最適化問題（Multi Objective Problem, MOP）として定式化することができます。 一方で、母集団ベースの性質から、EAはMOPのパレート集合（PS）またはパレートフロント（PF）全体を1回の実行で近似することができ、MOPを解くのに非常に適していると考えられています。 までは 現在では、多くのEMO技術が開発されており、パレート支配ベースのアルゴリズム、分解ベースのアルゴリズム、および指標ベースのアルゴリズムの3つに大別されます。
進化的マルチタスクは複数のタスクを同時に解くことに有望であり、EMOはECで注目されているトピックの1つであるため、2つのパラダイムの交差点でのアルゴリズムの動作を理解することは注目すべき意味合いがあるかもしれません。 この２つの異なるパラダイムの組み合わせを、ここでは多目的多因子最適化（MO-MFO）と呼びますが、これは、EAを用いて単一の個体群を進化させることにより、多数の多目的最適化タスクが同時に解かれることを意味します。 本論文では、MO-MFOのための9つのベンチマークを提案し、それぞれのベースラインは、同時に解く必要のある2つの多目的最適化タスクから構成されます。 ベンチマーク間の関係はベンチマークごとに異なり、MO-MFOアルゴリズムの総合的な評価に役立つと考えられる。 提案された試験問題がMO-MFO研究の発展に寄与することが期待される。 本論文の残りの部分の概要は以下の通りである。 第II節では、提案されたベンチマークの定義を示す。 第III節では、提案したベンチマークに対するアルゴリズムの性能評価方法について述べる。 第IV節では、MO-MFEAとその基礎となる基本的なMOEAを用いて、提案されているベンチマーク問題に対するMO-MFOアルゴリズムのベースライン結果を示す。
進化的（単一目的）マルチタスクに関する先行研究では、大域的最適値の交差の度合いとFitness landscape※1 の類似性が、異なる最適化タスク間の相補性を導く2つの重要な要素であることが分かっています。 これに基づき、今回紹介するテスト問題における多目的最適化タスクの特徴はq(x)関数に着目し、テスト問題における2つの多目的最適化タスクの関係をそれぞれのq(x)関数の関係に変換することで、多目的タスクのパレート最適解は、対応するq(x)がグローバル最小値に達した場合に達成されるという事実に基づいています。
2 つの多目的課題 T1 と T2 における q(x) 関数のグローバル最小値がそれぞれ x∗1 と x∗2 であるとします。 x∗1 と x∗2 の各次元を同じ範囲 [0, 1] に正規化すると、 ¯x∗1 と ¯x∗2 が得られます。 ¯x∗1 = ¯x∗2 の場合は、大域的最小値は完全な交差を意味します。 ¯x∗1 と ¯x∗2 の値が等しい次元が存在しない場合は交差なしを意味します。 ¯x∗1 と ¯x∗2 の他の全ての関係は部分交差を意味します。 q(x)関数のFitness landscape間の類似度を計算するには、 統一探索空間[1]から100万点を無作為にサンプリングし、 q(x)関数間のスピアマン順位相関係数を類似度として算出します。 (0, 1/3], (1/3, 2/3], (2/3, 1)にある類似度をそれぞれ高、中、低とします。 大域的最小値の3種類の交差 (完全交差、部分交差、交差なし)を考慮し、それぞれのカテゴリ内で、Fitness landscapeの類似度を高、中、低の3つのカテゴリに分けて考えます。 したがって、合計9つのテスト問題があります。 多くの実用的な設定では、潜在的なマルチタスク最適化設定を分類するための第3の条件、すなわち、決定変数の表現型の重複に基づいていることに注意してください[2]。 詳細に説明すると、異なるタスクからの変数のペアは、同じ意味的（または文脈的）な意味を持つかもしれないので、それらの間の知識伝達の範囲につながります。 しかし、合成ベンチマーク関数の場合には、実質的な文脈的意味がないため、タスク間の類似性/重複を記述するためのそのような条件は、本論文では適用されていません。 提案されたテスト問題の定義を以下に詳しく説明します。 5つの変位ベクトル（s_cm2、s_ph2、s_pm1、s_pl2、s_nl1）と4つの回転行列（M_cm2、M_pm1、M_pm2、M_nm2）が含まれ、オンラインでデータを利用できることに注意してください。
最初の多目的タスクT1は次のように定義されます。
2番目の多目的タスクT2は次のように定義されます。
このテスト問題では、決定変数の数nはT1とT2の両方で50に設定されており、T1とT2の類似度は0.97です。 T1のPSとPF、およびT2のPSとPFは次のとおりです。
このテスト問題では、決定変数の数nはT1とT2の両方で10に設定され、T1とT2の間の類似度は0.52です。 T1のPSとPF、およびT2のPSとPFは次のとおりです。
このテスト問題では、決定変数の数nはT1とT2の両方で50に設定されており、T1とT2の類似度は0.07です。 T1のPSとPF、およびT2のPSとPFは次のとおりです。
このテスト問題の場合、T1とT2の両方で決定変数の数nは50に設定され、T1とT2の類似度は0.99です。 T1のPSとPF、およびT2のPSとPFは次のとおりです。
このテスト問題では、決定変数の数nはT1とT2の両方で50に設定され、T1とT2の類似度は0.55です。 T1のPSとPF、およびT2のPSとPFは次のとおりです。
このテスト問題では、決定変数の数nはT1とT2の両方で50に設定され、T1とT2の類似度は0.002です。 T1のPSとPF、およびT2のPSとPFは次のとおりです。
このテスト問題では、決定変数の数nはT1とT2の両方で50に設定され、T1とT2の類似度は0.94です。 T1のPSとPF、およびT2のPSとPFは次のとおりです。
このテスト問題では、決定変数の数nはT1とT2の両方で20に設定され、T1とT2の類似度は0.51です。 T1のPSとPF、およびT2のPSとPFは次のとおりです。
このテスト問題では、決定変数の数nはT1とT2の両方で25に設定され、T1とT2の類似度は0.001です。 T1のPSとPF、およびT2のPSとPFは次のとおりです。
表Iは、提案されたテスト問題とその特性をまとめたものです。 sim（T1、T2）は、テスト問題の2つのタスク間の類似性を示します。 図1は、テスト問題における多目的最適化タスクの4種類のパレートフロントを示しています。
表1. 進化的多目的マルチタスクのために提案されたテスト問題の概要。
図1. 提案されたテスト問題に関する4つの異なる種類のパレートフロント。
※1 Fitness landscape: GAにおいて、突然変異がどのように器官の適応度を変化させ得るかを地形のように図示する方法。
この章では、提案されたテスト問題に対するアルゴリズムの性能を評価するために従うプロセスについて説明します。 すべてのテスト問題はブラックボックス問題として扱う必要があります。つまり、これらの問題の分析形式はアルゴリズムでは不明です。
反転世代間距離（Inverted Generational Distance, IGD）[24]は、検討対象のテスト問題の各タスクに対するアルゴリズムの性能を評価するために使用されます。 AをタスクTiに対してアルゴリズムによって得られる非支配目的ベクトルの集合、PをTiのPF上に均一に分布した目的ベクトルの集合とします。 AおよびPは、まずP*間の最大値と最小値を用いて正規化し、近似集合AのメトリックIGDを次のように計算します。
ここで、d（x、y）は、正規化された目的空間におけるxとyの間のユークリッド距離です。 |P|が PFを表すのに十分な大きさであれば、IGD（A、P）はある意味でAの収束と多様性の両方を測ることができます。 IGD（A、P）の値が小さいということは、AがP に非常に近く、Pのどの部分も見逃してはならないことを意味します。 各タスクのPのデータファイルとIGD計算のソースコードは、オンラインで提供されるzipパッケージからも入手できます。
多目的マルチタスク問題では、アルゴリズムの実行ごとに複数のIGD値が得られ、1つのタスクに対して1つのIGD値が得られます。 これらのIGD値に基づいて、MO-MFOアルゴリズムの総合的な性能を評価するための包括的な基準を提供し、各テスト問題に対するアルゴリズムのランク付けを行います。 テスト問題にK個のタスクT1,T2, ... TKが存在し、あるアルゴリズムがTi (i = 1, 2, ... K) に対して実行した際に得られるIGD値をIiとします。 さらに、Tiに対するIGD値の平均と標準偏差をそれぞれμiとσiとします。 このとき、得られたテスト問題のIGD値の平均標準スコア(MSS)は次のように計算されます：
実際には、µiとσiは、すべての実行でタスクTiのすべてのアルゴリズムによって取得されたIGDに従って計算されます。 MSSは包括的な基準として使用され、MSS値が小さいほど、テスト問題でのMO-MFOアルゴリズムの全体的なパフォーマンスが優れていることを示します。
1）近似集合内の非支配目的ベクトルの最大数： テスト問題でアルゴリズムを実行した後、IGDメトリックは問題のタスクごとに計算する必要があります。 IGDを計算するためのアルゴリズムによって生成される非支配目的ベクトルの最大数（つまり、|A|）は次のとおりです。 ・2目的を持ったタスクに対して100。 ・3目的を持つタスクの場合は120。 2）関数評価の最大数： すべてのテスト問題に対して200,000に設定されています。 なお、ここでの「関数評価」とは、タスクTiの目的関数の計算を意味し、異なるタスクの関数評価は区別しません。 3）独立実行回数： 各アルゴリズムは、各多目的マルチタスクテスト問題で独立して30回実行する必要があります。 4）アルゴリズムのパラメータ設定： テスト問題NIMSまたはNILSは、2目的のタスクと3目的のタスクで構成されています。 一方、残りの各テスト問題は、2つの2目的タスクで構成されています。 アルゴリズムはNIMSとNILSに共通したパラメータを使用し、他のテスト問題は共通したパラメータを使用する必要があります。
一言でいうと
論文リンク
https://arxiv.org/abs/1706.02766
著者/所属機関
Yuan Yuan, Yew-Soon Ong, Liang Feng, A.K. Qin, Abhishek Gupta, Bingshui Da, Qingfu Zhang, Kay Chen Tan, Yaochu Jin, Hisao Ishibuchi
投稿日付
2017/1/8
概要
入力される情報ストリームの多様性と量が爆発的に増加しているため、インテリジェントなシステムやアルゴリズムが効率的なマルチタスク処理が可能であることが非常に望まれています。 進化アルゴリズム(EA)は、母集団ベースの探索アルゴリズムの一種であり、複数の最適化タスクを一度に処理できる固有の能力を持っています。 進化的マルチタスク[1], [2]は、このEAの特性を利用して、進化的計算(EC)の新しいパラダイムとなっています。 進化的マルチタスクに関する最初のチュートリアル（"Evolutionary Multitasking and Implications for Cloud Computing"）は、IEEE Congress on Evolutionary Computation (CEC) 2015（仙台、日本）で発表されました。 それ以来、このトピックに関する一連の研究が様々な観点から行われ、進化的マルチタスクの可能性を示すだけでなく、このパラダイムがなぜ機能するのかをある程度説明しています。 進化的多目的最適化（Evolutionary Multi Objective Optimization: EMO）[11]-[13]は、過去20年以上にわたってECの分野で常に人気のあるトピックとなっています。 その理由は主に以下の2つの側面にあります。 一方で、実世界のアプリケーションにおける多くの最適化問題は、本質的に多目的最適化問題（Multi Objective Problem, MOP）として定式化することができます。 一方で、母集団ベースの性質から、EAはMOPのパレート集合（PS）またはパレートフロント（PF）全体を1回の実行で近似することができ、MOPを解くのに非常に適していると考えられています。 までは 現在では、多くのEMO技術が開発されており、パレート支配ベースのアルゴリズム、分解ベースのアルゴリズム、および指標ベースのアルゴリズムの3つに大別されます。
進化的マルチタスクは複数のタスクを同時に解くことに有望であり、EMOはECで注目されているトピックの1つであるため、2つのパラダイムの交差点でのアルゴリズムの動作を理解することは注目すべき意味合いがあるかもしれません。 この２つの異なるパラダイムの組み合わせを、ここでは多目的多因子最適化（MO-MFO）と呼びますが、これは、EAを用いて単一の個体群を進化させることにより、多数の多目的最適化タスクが同時に解かれることを意味します。 本論文では、MO-MFOのための9つのベンチマークを提案し、それぞれのベースラインは、同時に解く必要のある2つの多目的最適化タスクから構成されます。 ベンチマーク間の関係はベンチマークごとに異なり、MO-MFOアルゴリズムの総合的な評価に役立つと考えられる。 提案された試験問題がMO-MFO研究の発展に寄与することが期待される。 本論文の残りの部分の概要は以下の通りである。 第II節では、提案されたベンチマークの定義を示す。 第III節では、提案したベンチマークに対するアルゴリズムの性能評価方法について述べる。 第IV節では、MO-MFEAとその基礎となる基本的なMOEAを用いて、提案されているベンチマーク問題に対するMO-MFOアルゴリズムのベースライン結果を示す。
ベンチマーク問題の定義
進化的（単一目的）マルチタスクに関する先行研究では、大域的最適値の交差の度合いとFitness landscape※1 の類似性が、異なる最適化タスク間の相補性を導く2つの重要な要素であることが分かっています。 これに基づき、今回紹介するテスト問題における多目的最適化タスクの特徴はq(x)関数に着目し、テスト問題における2つの多目的最適化タスクの関係をそれぞれのq(x)関数の関係に変換することで、多目的タスクのパレート最適解は、対応するq(x)がグローバル最小値に達した場合に達成されるという事実に基づいています。
2 つの多目的課題 T1 と T2 における q(x) 関数のグローバル最小値がそれぞれ x∗1 と x∗2 であるとします。 x∗1 と x∗2 の各次元を同じ範囲 [0, 1] に正規化すると、 ¯x∗1 と ¯x∗2 が得られます。 ¯x∗1 = ¯x∗2 の場合は、大域的最小値は完全な交差を意味します。 ¯x∗1 と ¯x∗2 の値が等しい次元が存在しない場合は交差なしを意味します。 ¯x∗1 と ¯x∗2 の他の全ての関係は部分交差を意味します。 q(x)関数のFitness landscape間の類似度を計算するには、 統一探索空間[1]から100万点を無作為にサンプリングし、 q(x)関数間のスピアマン順位相関係数を類似度として算出します。 (0, 1/3], (1/3, 2/3], (2/3, 1)にある類似度をそれぞれ高、中、低とします。 大域的最小値の3種類の交差 (完全交差、部分交差、交差なし)を考慮し、それぞれのカテゴリ内で、Fitness landscapeの類似度を高、中、低の3つのカテゴリに分けて考えます。 したがって、合計9つのテスト問題があります。 多くの実用的な設定では、潜在的なマルチタスク最適化設定を分類するための第3の条件、すなわち、決定変数の表現型の重複に基づいていることに注意してください[2]。 詳細に説明すると、異なるタスクからの変数のペアは、同じ意味的（または文脈的）な意味を持つかもしれないので、それらの間の知識伝達の範囲につながります。 しかし、合成ベンチマーク関数の場合には、実質的な文脈的意味がないため、タスク間の類似性/重複を記述するためのそのような条件は、本論文では適用されていません。 提案されたテスト問題の定義を以下に詳しく説明します。 5つの変位ベクトル（s_cm2、s_ph2、s_pm1、s_pl2、s_nl1）と4つの回転行列（M_cm2、M_pm1、M_pm2、M_nm2）が含まれ、オンラインでデータを利用できることに注意してください。
1) Complete Intersection with High Similarity (CIHS)
最初の多目的タスクT1は次のように定義されます。
2番目の多目的タスクT2は次のように定義されます。
このテスト問題では、決定変数の数nはT1とT2の両方で50に設定されており、T1とT2の類似度は0.97です。 T1のPSとPF、およびT2のPSとPFは次のとおりです。
2) Complete Intersection with Medium Similarity (CIMS)
最初の多目的タスクT1は次のように定義されます。
2番目の多目的タスクT2は次のように定義されます。
このテスト問題では、決定変数の数nはT1とT2の両方で10に設定され、T1とT2の間の類似度は0.52です。 T1のPSとPF、およびT2のPSとPFは次のとおりです。
3) Complete Intersection with Low Similarity (CILS)
最初の多目的タスクT1は次のように定義されます。
2番目の多目的タスクT2は次のように定義されます。
このテスト問題では、決定変数の数nはT1とT2の両方で50に設定されており、T1とT2の類似度は0.07です。 T1のPSとPF、およびT2のPSとPFは次のとおりです。
4) Partial Intersection with High Similarity (PIHS)
最初の多目的タスクT1は次のように定義されます。
2番目の多目的タスクT2は次のように定義されます。
このテスト問題の場合、T1とT2の両方で決定変数の数nは50に設定され、T1とT2の類似度は0.99です。 T1のPSとPF、およびT2のPSとPFは次のとおりです。
5) Partial Intersection with Medium Similarity (PIMS)
最初の多目的タスクT1は次のように定義されます。
2番目の多目的タスクT2は次のように定義されます。
このテスト問題では、決定変数の数nはT1とT2の両方で50に設定され、T1とT2の類似度は0.55です。 T1のPSとPF、およびT2のPSとPFは次のとおりです。
6) Partial Intersection with Low Similarity (PILS)
最初の多目的タスクT1は次のように定義されます。
2番目の多目的タスクT2は次のように定義されます。
このテスト問題では、決定変数の数nはT1とT2の両方で50に設定され、T1とT2の類似度は0.002です。 T1のPSとPF、およびT2のPSとPFは次のとおりです。
7) No Intersection with High Similarity (NIHS)
最初の多目的タスクT1は次のように定義されます。
2番目の多目的タスクT2は次のように定義されます。
このテスト問題では、決定変数の数nはT1とT2の両方で50に設定され、T1とT2の類似度は0.94です。 T1のPSとPF、およびT2のPSとPFは次のとおりです。
8) No Intersection with Medium Similarity (NIMS)
最初の多目的タスクT1は次のように定義されます。
2番目の多目的タスクT2は次のように定義されます。
このテスト問題では、決定変数の数nはT1とT2の両方で20に設定され、T1とT2の類似度は0.51です。 T1のPSとPF、およびT2のPSとPFは次のとおりです。
9) No Intersection with Low Similarity (NILS)
最初の多目的タスクT1は次のように定義されます。
2番目の多目的タスクT2は次のように定義されます。
このテスト問題では、決定変数の数nはT1とT2の両方で25に設定され、T1とT2の類似度は0.001です。 T1のPSとPF、およびT2のPSとPFは次のとおりです。
表Iは、提案されたテスト問題とその特性をまとめたものです。 sim（T1、T2）は、テスト問題の2つのタスク間の類似性を示します。 図1は、テスト問題における多目的最適化タスクの4種類のパレートフロントを示しています。
表1. 進化的多目的マルチタスクのために提案されたテスト問題の概要。
図1. 提案されたテスト問題に関する4つの異なる種類のパレートフロント。
※1 Fitness landscape: GAにおいて、突然変異がどのように器官の適応度を変化させ得るかを地形のように図示する方法。
性能評価
この章では、提案されたテスト問題に対するアルゴリズムの性能を評価するために従うプロセスについて説明します。 すべてのテスト問題はブラックボックス問題として扱う必要があります。つまり、これらの問題の分析形式はアルゴリズムでは不明です。
A.性能メトリック
反転世代間距離（Inverted Generational Distance, IGD）[24]は、検討対象のテスト問題の各タスクに対するアルゴリズムの性能を評価するために使用されます。 AをタスクTiに対してアルゴリズムによって得られる非支配目的ベクトルの集合、PをTiのPF上に均一に分布した目的ベクトルの集合とします。 AおよびPは、まずP*間の最大値と最小値を用いて正規化し、近似集合AのメトリックIGDを次のように計算します。
ここで、d（x、y）は、正規化された目的空間におけるxとyの間のユークリッド距離です。 |P|が PFを表すのに十分な大きさであれば、IGD（A、P）はある意味でAの収束と多様性の両方を測ることができます。 IGD（A、P）の値が小さいということは、AがP に非常に近く、Pのどの部分も見逃してはならないことを意味します。 各タスクのPのデータファイルとIGD計算のソースコードは、オンラインで提供されるzipパッケージからも入手できます。
B. MO-MFOアルゴリズムのランキング
多目的マルチタスク問題では、アルゴリズムの実行ごとに複数のIGD値が得られ、1つのタスクに対して1つのIGD値が得られます。 これらのIGD値に基づいて、MO-MFOアルゴリズムの総合的な性能を評価するための包括的な基準を提供し、各テスト問題に対するアルゴリズムのランク付けを行います。 テスト問題にK個のタスクT1,T2, ... TKが存在し、あるアルゴリズムがTi (i = 1, 2, ... K) に対して実行した際に得られるIGD値をIiとします。 さらに、Tiに対するIGD値の平均と標準偏差をそれぞれμiとσiとします。 このとき、得られたテスト問題のIGD値の平均標準スコア(MSS)は次のように計算されます：
実際には、µiとσiは、すべての実行でタスクTiのすべてのアルゴリズムによって取得されたIGDに従って計算されます。 MSSは包括的な基準として使用され、MSS値が小さいほど、テスト問題でのMO-MFOアルゴリズムの全体的なパフォーマンスが優れていることを示します。
C.実験設定
1）近似集合内の非支配目的ベクトルの最大数： テスト問題でアルゴリズムを実行した後、IGDメトリックは問題のタスクごとに計算する必要があります。 IGDを計算するためのアルゴリズムによって生成される非支配目的ベクトルの最大数（つまり、|A|）は次のとおりです。 ・2目的を持ったタスクに対して100。 ・3目的を持つタスクの場合は120。 2）関数評価の最大数： すべてのテスト問題に対して200,000に設定されています。 なお、ここでの「関数評価」とは、タスクTiの目的関数の計算を意味し、異なるタスクの関数評価は区別しません。 3）独立実行回数： 各アルゴリズムは、各多目的マルチタスクテスト問題で独立して30回実行する必要があります。 4）アルゴリズムのパラメータ設定： テスト問題NIMSまたはNILSは、2目的のタスクと3目的のタスクで構成されています。 一方、残りの各テスト問題は、2つの2目的タスクで構成されています。 アルゴリズムはNIMSとNILSに共通したパラメータを使用し、他のテスト問題は共通したパラメータを使用する必要があります。
結果
コメント
実装