適応度関数

適応度関数は、与えられた候補ソリューションが設定された目標の達成にどれだけ近いかを単一の性能指数として要約するために使用される特定のタイプの目的関数またはコスト関数です。これは、遺伝的プログラミング、進化戦略、遺伝的アルゴリズムなどの進化アルゴリズム (EA)の重要なコンポーネントです。EA は、困難な最適化または計画タスクを少なくとも近似的に解決するために、コンピュータアルゴリズムとして生物学的進化の基本原理を再現するメタヒューリスティックです。この目的のために、多くの候補ソリューションが生成され、それらは適応度関数を使用して評価され、望ましい目標に向けた進化的発達を導きます。^{[ 1 ]}同様の品質関数は、アリコロニー最適化や粒子群最適化などの他のメタヒューリスティックでも使用されます。

EAの分野では、各候補解（個体とも呼ばれる）は、一般的に数値の列（染色体と呼ばれる）として表される。テストまたはシミュレーションの各ラウンドの後、最も悪いn個の個体を削除し、最も良い解からn個の新しい個体を繁殖させる という考え方である。したがって、各個体には、全体的な仕様にどれだけ近づいたかを示す品質番号を割り当てる必要があり、この品質番号は、候補解から得られたテストまたはシミュレーション結果に適応度関数を適用することによって生成される。^{[ 2 ]}

適応度関数には主に2つの種類があります。1つは、固定された関数の最適化や固定されたテストケースセットを用いたテストなど、適応度関数が変化しないものです。もう1つは、ニッチ分化やテストケースセットの共進化など、適応度関数が変化するものです。 ^{[ 3 ] [ 4 ]}適応度関数を別の視点から捉える方法として、適応度ランドスケープがあります。これは、考えられる各染色体に対する適応度を示します。以下では、適応度は最適化の実行中に変化しない評価に基づいて決定されるものと仮定します。

適応度関数は必ずしも絶対値を計算できる必要はありません。より良い候補を選択するためには、候補を比較するだけで十分な場合があるからです。トーナメント選択やパレート最適化など、 ^{[ 5 ]}のようなケースでは、相対的な適応度指標（候補aは候補bよりも優れている）で十分です。

評価と適合関数の要件

適応度関数の評価と計算の質は、EA最適化の成功の鍵となります。これはダーウィンの「適者生存」の原理を具体化したものです。配偶者選択と子孫の受容のための適応度に基づく選択メカニズムがなければ、EA探索は盲目的となり、モンテカルロ法とほとんど区別がつかなくなります。適応度関数を設定する際には、それが単に望ましい目標状態を記述するだけではないこと、つまり、適応度関数のみで既に最適化が行われていない限りにおいて、最適解への進化的探索も可能な限りサポートされるべきです（補助目的のセクションも参照）。適応度関数の設計が適切でない場合、アルゴリズムは不適切な解に収束するか、収束自体が困難になります。

適応度関数の定義は多くの場合単純ではなく、EAによって生成された最適解が期待通りでない場合は、反復的に実行されることがよくあります。対話型遺伝的アルゴリズム（ IA）は、評価を外部エージェント（通常は人間）にアウトソーシングすることで、この困難に対処します。

計算効率

適応度関数は、設計者の目標に忠実であるだけでなく、計算効率も高くなければなりません。典型的な進化アルゴリズムは、非自明な問題に対して使用可能な結果を​​生成するために何度も反復処理する必要があるため、実行速度は非常に重要です。

適応度近似^{[ 6 ] [ 7 ]}は、特に以下の場合に適切である可能性がある。

• 単一のソリューションの適合度計算時間は非常に長い
• 適応度計算のための正確なモデルが欠如している
• 適応度関数は不確実またはノイズが多い。^{[ 8 ]}

適応度近似の代わりに、あるいはそれに加えて、適応度計算を並列コンピュータに分散させることで実行時間を短縮することも可能です。使用するEAの個体群モデルによっては、EA自体と、ある世代のすべての子孫の適応度計算の両方を並列に実行することも可能です。^{[ 9 ] [ 10 ] [ 11 ]}

多目的最適化

実用化では、通常、複数の、そして少なくとも部分的には相反する目的を最適化することが目的となります。この目的のために、パレート最適化と、加重和を用いて計算される適応度に基づく最適化という、根本的に異なる2つのアプローチがよく用いられます。^{[ 12 ]}

加重和とペナルティ関数

加重和を用いて最適化を行う場合、まず各目的関数の個々の値を正規化し、比較できるようにします。これは、コストを用いて行うか、目標値を指定して現在の値を達成度として決定することで行うことができます。その後、コストまたは達成度を互いに比較し、必要に応じて均一な適応度尺度にマッピングすることもできます。一般性を損なうことなく、適応度は最大化すべき値を表すものと仮定されます。各目的関数にはパーセンテージ値の形で重みが割り当てられるため、全体的な生の適応度は加重和として計算できます。 ${\displaystyle O}$ ${\displaystyle o_{i}}$ ${\displaystyle w_{i}}$ ${\displaystyle f_{raw}}$

${\displaystyle f_{raw}=\sum _{i=1}^{O}{o_{i}\cdot w_{i}}\quad {\mathsf {with}}\quad \sum _{i=1}^{O}{w_{i}}=1}$

制約違反は、このようにして決定された適応度にペナルティ関数の形で含めることができる。この目的のために、各制約に対して、違反の程度に応じて からの間の値を返す関数を定義することができる。違反がない場合には、結果は となる。先に決定された生の適応度にペナルティ関数を乗じることで、最終的な適応度が得られる。^{[ 13 ]} ${\displaystyle R}$ ${\displaystyle r_{j}}$ ${\displaystyle pf_{j}(r_{j})}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle f_{final}}$

${\displaystyle f_{final}=f_{raw}\cdot \prod _{j=1}^{R}{pf_{j}(r_{j})}=\sum _{i=1}^{O}{(o_{i}\cdot w_{i})}\cdot \prod _{j=1}^{R}{pf_{j}(r_{j})}}$

このアプローチはシンプルで、任意の数の目的関数と制約条件を組み合わせることができるという利点があります。欠点は、異なる目的関数が互いに相殺し合う可能性があること、そして最適化の前に重みを定義する必要があることです。つまり、妥協点となる線を最適化前に定義する必要があるということです。そのため、重み付き和を用いた最適化は、事前法とも呼ばれます。^{[ 12 ]}また、特定の解が得られない場合もあります。詳細については、両方の最適化の比較に関するセクションを参照してください。

パレート最適化

ある目的を改善するには、少なくとも他の目的が1つ悪化するしかない場合、その解はパレート最適と呼ばれます。パレート最適解の集合（パレート集合とも呼ばれます）は、目的間のすべての最適な妥協点の集合を表します。下の右図は、最大化されるべき2つの目的のパレート集合の例を示しています。集合の要素はパレートフロント（緑の線）を形成します。人間の意思決定者は、この集合から望ましい妥協点を選択する必要があります。^{[ 12 ]}パレート最適化には制約が含まれており、制約違反のない解は、違反のある解よりも本質的に優れています。比較される2つの解がそれぞれ制約違反を持っている場合、それぞれの違反の程度が決定します。^{[ 14 ]} ${\displaystyle f_{1}}$ ${\displaystyle f_{2}}$

EAは、同時に考慮される解の集合が、パレート最適解を十分にカバーする解を1回の実行で見つけるのに適していることが早くから認識されていました。^{[ 14 ] [ 15 ]}そのため、EAは、最適化とパレート最適解の決定後に人間の意思決定者が最終決定を下す多目的最適化の事後手法として適しています。 ^{[ 12 ]} SPEA2の他に、^{[ 16 ]} NSGA-II ^{[ 17 ]}とNSGA-III ^{[ 18 ] [ 19 ]}が標準的な手法として確立されています。

パレート最適化の利点は、加重和とは異なり、目的に関して同等なすべての代替案を全体的な解として提示することです。欠点は、目的が4つ以上になると、代替案の可視化が困難になり、場合によっては不可能になることです。さらに、目的の数が増えると、作業量は指数関数的に増加します。^{[ 13 ]}目的が3つまたは4つを超える場合は、加重和やその他の集約方法を用いて、いくつかの目的を統合する必要があります。^{[ 12 ]}

両方の評価方法の比較

パレート面と加重和の関係。実行可能解の集合はパレート面（緑）によって部分的に囲まれる。^{[ 13 ]} ${\displaystyle Z}$

非凸パレートフロントの例^{[ 13 ]}

重み付き和を用いることで、適切な重みの選択によって全体のパレート面が得られる。ただし、凸面となることが前提となる。^{[ 20 ]}これは左隣の図に示されている。EAが最適解に収束する場合、重みとによって緑色のパレート面上の点に到達する。解集合の中で適応度ゲインが最大となる方向は、描かれた矢印で示されている。 ${\displaystyle {\mathsf {P}}}$ ${\displaystyle w_{1}}$ ${\displaystyle w_{2}}$ ${\displaystyle Z}$

しかしながら、非凸面の場合、加重和では非凸面セクションに到達できません。右隣の図では、これは点 と の間のセクションです。これは、加重和の拡張であるカスケード加重和を用いることで、ある程度まで改善できます。^{[ 13 ]} ${\displaystyle {\mathsf {A}}}$ ${\displaystyle {\mathsf {B}}}$

両方の評価アプローチを比較すると、タスクの可能な解決策がほとんど分かっていない場合、および最適化目標の数を3つ、多くても4つに絞り込める場合、パレート最適化の使用は確かに有利です。しかし、同一のタスクのバリエーションを繰り返し最適化する場合、望ましい妥協点は通常既知であり、パレート最適解面全体を決定する努力はもはや正当化されません。これは、自動化された意思決定プロセスなど、最適化後に人間の意思決定が望まれない、または不可能な場合にも当てはまります。^{[ 13 ]}

補助目標

最遅完了時間を満たすべき5つの作業ステップaからeまでからなるオーダーの2つのスケジュールの例^{[ 21 ]}

タスク自体から得られる主目的に加えて、1つ以上の主目的の達成を支援するために、評価に補助目的を含める必要がある場合があります。説明のために、スケジューリングタスクの例を示します。最適化の目標には、すべての注文を全体的に迅速に処理することだけでなく、最遅完了時間の遵守も含まれます。後者は、特に急ぎの注文のスケジューリングに不可欠です。2つ目の目標は、隣の図に示すように、初期スケジュールの例では達成されません。その後の突然変異はこれを変えず、作業ステップdを早めにスケジュールします。これは、注文の最後の作業ステップeを早めに開始するために必要な中間ステップです。ただし、最遅完了時間のみが評価される限り、突然変異したスケジュールの適合性は、注文を時間通りに完了するという目標に向けた重要なステップであるにもかかわらず、変化しません。これは、例えば、作業ステップの遅延を追加評価することで改善できます。新しい目標は、実際の最適化目標に加えて、それらの達成を支援するために導入されたため、補助的な目標です。このアプローチのより詳細な説明と別の例については、^{[ 21 ]を参照してください。}

参照

• 進化計算
• 最適化のためのテスト関数
• 損失関数

外部リンク

• 適応型ファジーフィットネス粒度分布 (AFFG) の優れた入門( PDF )。EA の収束速度を加速する有望なアプローチです。
• EA の収束速度を加速するように設計されたAdaptive Fuzzy Fitness Granulation (AFFG) のサイバー シャック。
• 進化ロボティクスにおける適応度関数: 調査と分析 (AFFG) ( PDF )、進化ロボティクスで使用される適応度関数のレビュー。
• フォード、ニール、リチャーズ、マーク、サダラージ、プラモッド、デガニ、ザマク。(2021) 『ソフトウェアアーキテクチャ：ハードパーツ』オライリーメディア社ISBN 9781492086895。

参考文献

1. Eiben, AE; Smith, JE (2015). 「評価関数（適応度関数）」.進化コンピューティング入門. Natural Computing Series (第2版). ベルリン、ハイデルベルク: Springer. p. 30. doi : 10.1007/978-3-662-44874-8 . ISBN 978-3-662-44873-1. S2CID  20912932 .
2. Eiben, AE; Smith, JE (2015). 「進化的アルゴリズムとは何か？」.進化的コンピューティング入門. Natural Computing Series. ベルリン、ハイデルベルク: Springer. pp.  25– 48. doi : 10.1007/978-3-662-44874-8 . ISBN 978-3-662-44873-1. S2CID  20912932 .
3. Popovici, Elena; Bucci, Anthony; Wiegand, R. Paul; De Jong, Edwin D. (2012), Rozenberg, Grzegorz; Bäck, Thomas; Kok, Joost N. (eds.), "Coevolutionary Principles" , Handbook of Natural Computing , Berlin, Heidelberg: Springer Berlin Heidelberg, pp.  987– 1033, doi : 10.1007/978-3-540-92910-9_31 , ISBN 978-3-540-92909-3、2023年1月8日取得{{citation}}: CS1 maint: ISBNによる作業パラメータ（リンク）
4. Eiben, AE; Smith, JE (2015). 「共進化システム」.進化コンピューティング入門. ナチュラルコンピューティングシリーズ. ベルリン、ハイデルベルク: Springer Berlin Heidelberg. pp.  223– 230. doi : 10.1007/978-3-662-44874-8 . ISBN 978-3-662-44873-1. S2CID  20912932 .
5. Bäck, Thomas; Fogel, David; Michalewicz, Zbigniew 編 (2000-11-20).進化計算 2: 高度なアルゴリズムと演算子. Taylor & Francis. doi : 10.1201/9781420034349 . ISBN 978-0-7503-0665-2。
6. Jin, Y. (2005年1月). 「進化計算における適応度近似の包括的調査」 .ソフトコンピューティング. 9 (1): 3– 12. doi : 10.1007/s00500-003-0328-5 . ISSN 1432-7643 . S2CID 7626092 .  
7. Jin, Yaochu; Wang, Handing; Chugh, Tinkle; Miettinen, Kaisa (2019年6月). 「データ駆動型進化的最適化：概要とケーススタディ」 . IEEE Transactions on Evolutionary Computation . 23 (3): 442– 458. Bibcode : 2019ITEC...23..442J . doi : 10.1109/TEVC.2018.2869001 . hdl : 10871/34011 . ISSN 1089-778X . S2CID 55809527 .  
8. Eiben, AE; Smith, JE (2015). 「非定常かつノイズのある関数の最適化」.進化計算入門. ナチュラルコンピューティングシリーズ（第2版）. ベルリン、ハイデルベルク：シュプリンガー. pp.  185– 194. doi : 10.1007/978-3-662-44874-8 . ISBN 978-3-662-44873-1. S2CID  20912932 .
9. Sudholt, Dirk (2015), Kacprzyk, Janusz; Pedrycz, Witold (eds.), "Parallel Evolutionary Algorithms" , Springer Handbook of Computational Intelligence , ベルリン, ハイデルベルク: Springer, pp.  929– 959, doi : 10.1007/978-3-662-43505-2_46 , ISBN 978-3-662-43504-5、 2023年2月27日取得{{citation}}: CS1 maint: ISBNによる作業パラメータ（リンク）
10. Khalloof, Hatem; Mohammad, Mohammad; Shahoud, Shadi; Duepmeier, Clemens; Hagenmeyer, Veit (2020-11-02). 「ポピュレーションベースメタヒューリスティックスの階層的並列化のための汎用的で柔軟かつスケーラブルなフレームワーク」 .第12回国際デジタルエコシステム管理会議議事録. バーチャルイベント アラブ首長国連邦: ACM. pp.  124– 131. doi : 10.1145/3415958.3433041 . ISBN 978-1-4503-8115-4. S2CID  227179748 .
11. ポール・イェーネ (2016).マイヤー、ハインリヒ・クリスチャン。ピンツガー、マーティン (編)。グラフィック カード上の進化的アルゴリズムの並列化に関する研究の現状の概要(PDF)。ボン: Gesellschaft für Informatik、FRG。ISBN 978-3-88579-653-4. OCLC  962381748 .
12. Miettinen, Kaisa (2008). 「多目的最適化入門：非対話型アプローチ」 Branke, Jürgen; Deb, Kalyanmoy; Miettinen, Kaisa; Słowiński, Roman (編).多目的最適化：対話型および進化型アプローチ. コンピュータサイエンス講義ノート. 第5252巻. ベルリン、ハイデルベルク：Springer. pp.  1– 26. doi : 10.1007/978-3-540-88908-3 . ISBN 978-3-540-88907-6. S2CID  15375227 .
13. Jakob, Wilfried; Blume, Christian (2014-03-21). 「パレート最適化またはカスケード加重和：概念の比較」 .アルゴリズム. 7 (1): 166– 185. arXiv : 2203.02697 . doi : 10.3390/a7010166 . ISSN 1999-4893 . 
14. Deb, Kalyanmoy (2008). 「進化的多目的最適化入門」. Branke, Jürgen; Deb, Kalyanmoy; Miettinen, Kaisa; Słowiński, Roman (編).多目的最適化：対話型および進化的アプローチ. コンピュータサイエンス講義ノート. 第5252巻. ベルリン、ハイデルベルク：シュプリンガー. pp.  58– 96. doi : 10.1007/978-3-540-88908-3 . ISBN 978-3-540-88907-6. S2CID  15375227 .
15. Fonseca, Carlos M.; Fleming, Peter J. (1995). 「多目的最適化における進化的アルゴリズムの概要」 .進化的計算. 3 (1): 1– 16. doi : 10.1162/evco.1995.3.1.1 . ISSN 1063-6560 . S2CID 8530790 .  
16. Eckart, Zitzler; Marco, Laumanns; Lothar, Thiele (2001). 「SPEA2: 強度パレート進化アルゴリズムの改良」.技術報告書, No. 103. コンピュータ工学・ネットワーク研究所 (TIK) . ETH Zürich 2001. doi : 10.3929/ethz-a-004284029 . S2CID 16584254 . 
17. Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T. (2002). 「高速かつエリート主義的な多目的遺伝的アルゴリズム：NSGA-II」. IEEE Transactions on Evolutionary Computation . 6 (2): 182– 197. Bibcode : 2002ITEC....6..182D . doi : 10.1109/4235.996017 . S2CID 9914171 . 
18. Deb, Kalyanmoy; Jain, Himanshu (2014). 「参照点ベースの非優越ソートアプローチを用いた進化的多目的最適化アルゴリズム、パートI：ボックス制約による問題の解決」. IEEE Transactions on Evolutionary Computation . 18 (4): 577– 601. Bibcode : 2014ITEC...18..577D . doi : 10.1109/TEVC.2013.2281535 . ISSN 1089-778X . S2CID 206682597 .  
19. Jain, Himanshu; Deb, Kalyanmoy (2014). 「参照点に基づく非優越ソートアプローチを用いた進化的多目的最適化アルゴリズム、パートII：制約条件の処理と適応型アプローチへの拡張」IEEE Transactions on Evolutionary Computation . 18 (4): 602– 622. Bibcode : 2014ITEC...18..602J . doi : 10.1109/TEVC.2013.2281534 . ISSN 1089-778X . S2CID 16426862 .  
20. Miettinen, Kaisa (1998).非線形多目的最適化. オペレーションズ・リサーチ＆マネジメント・サイエンス国際シリーズ. 第12巻. ボストン, マサチューセッツ州: Springer US. doi : 10.1007/978-1-4615-5563-6 . ISBN 978-1-4613-7544-9。
21. Jakob, Wilfried (2021), 「進化アルゴリズムの成功への適用：実世界の応用から得られたガイド」（KIT Scientific Working Papers, vol. 170）、カールスルーエ、ドイツ：カールスルーエ工科大学（KIT）、arXiv：2107.11300、doi：10.5445/ir/1000135763、S2CID 236318422 

「 https://en.wikipedia.org/w/index.php?title=Fitness_function&oldid=1328501415」より取得