Outline of paper `Massive Multimodality, Deception, and Genetic Algorithms'

Abstract

• average-sense misleading (deceptive) and massively multimodalな問題におけるGAの利用について考察する．
• bipolar deceptive problemを定義し，そのような問題の一般的な構成を取るreflected trap functions と low-order Walsh coefficients を再検討する．
• Walshの構成は 30-bit (6-bitのbipolar functionsを5つ結合させた order-sixの関数)
• このテスト関数は5百万個オーバーの局所解と32個の最適解を持ち，simple and niched GA には困難な課題．
• それでも，適切なSN比となる集団サイズ(signal-to-noise-ratio population sizing)が取り入れられているならば，32個の最適解の一つを発見することが可能である．
• もし，その集団が予測されたniche分布に関して手荒に分けられて（is sized）おり，かつその関数が expense of suboptimimal ones に大域的解を強調するため適切にスケールされているならば，全32個の大域的解（global solutions）を同時に発見可能である．
• これらの結果は，適切な population sizing and scaling を用いた niched GA のアプリケーションについて忠告する．また，多数のだまし問題の一般的な考えのための成功への道を提案する．

Introduction

パラグラフ1
• GAにとって困難となる問題や関数としてdeception（だまし問題）が焦点を浴びている．
• 例えば，
  works ; to better define or classify deception,
  studies ; constructed examples of deceptive functions,
  investigations ; altered genetic algorithms to try to solve deceptive problems
• 大きな進展にもかかわらず，だまし問題において意味のあるものは何か，それが有意義なものであるのか，という問題が生じてきている．
• それらを要約すると，これらの研究者は「GAが，だまし問題よりも問題解決に困難を持つものが存在するかどうか」と言っているようにみえる．当然ながら，それは正しい．
• But who ever promised us a single, easy answer.
• 見かけ上単純であるにもかかわらず，GAは高次元・多面的・非線形・確率的な，無限の種類の問題とinteract可能な複雑系である．
• GAは，アルゴリズムの観点から少なくとも4つの挑戦（building block supply, growth, mixing, and decision making）がある．何故，GAを負かす問題クラスの魔法の解決策（silver bullet），single, simple を同定（identify）することを期待するべきなのか．

パラグラフ2
• 一方で，我々は，それらの質素な競争相手の代価（the expense of their lowly competitors）の点でそれらのスキマタを増加する傾向の結果，population sampling and redistributionによって最も高適応度のスキマタ（schemata）を強調すること（emphasizing）でGAが働くことを知っている．
  質素な競争相手は，最も高適応度の競争相手がベストポイントから大きく異なる文字列を含む関数において心配するための，重大な判断力を作る．
• これは，何故on average-sense misleading problems に関してそれほど膨大な時間と注目（attention）を浪費するのかを，説明するのを助ける．そして，本稿では， both deceptive and massively mulitmodal である imagining problems によるworkを構築する．
• sharing functions の紹介と共に crowding and continuing に関係する De Jongとの研究が開始され，GAが多峰性問題内の多数の最適を同時に安定して発見するために用いられることの可能性に関し，その認識が大きく（growing recognition）なっている．
• ここで，我々は，構築（constructing）と大規模な多峰性かつだまし問題問題解決により，これらの次元両方に沿ってより高いレベルを求める．

パラグラフ3
• 初めに，2つの大域的最適解（global optima）と大量のだまし最適解（deceptive optima）を有する両極型だまし関数（bipolar deceptive functions）を設計する．
• これらの両極型関数は，無数のoptimaを含む高だまし関数（high deceptive functions）を作るための building blocks として用いられる．
• 6ビット両極型問題を5つ加えることで30ビット問題を作成した．興味深いことに，シンプルGAの十分なシミュレーションは，もし適切なSN比（signal-to-noise-ratio）であるpopulation sizingが他（Goldberg, Deb, & Clark, 1991）で提案されているものを採用されるならば，シンプルGAはその問題の 32 global solutions の一つに安定して収束することが可能であることを示している．
• シェアリングをベースとした棲み分け（sharing-based niching）が採用されているとき，もしその集団が niching lines に沿って適切にサイズされ，かつ，その関数が local solutions の代価の点で global solutions を強調するためにぴったりスケーリングされているならば，そのGAは全ての 32 global optima の安定な subpopulations を同時に発見することができる．
• これらの結果は，現実面において（in practice）高多峰性問題を解決するために niched GA の使用法を直接サポートするだけでなく，その研究もまた，そのような問題や他の困難な問題（other types of difficult problems）の特性を示すためにdeceptionの考え（notion）を一般化するためのヒントを与える．

Imagining a massively multimodal and deceptive function

パラグラフ1
• 略

パラグラフ2
• 例として，図1に示す典型的な完全だまし関数（typical fully deceptive function）を考える．
• その変数はバイナリストリング内の1（or unitation）の数である．
• この関数は Liepings and Vose (1990) のものに似ており，average-sense deception のための十分な条件は，trap functions やより一般的な関数のために考察されている．
• 直感的に，unitation u=l にある大域的最適解は完全に分離され，u=0 にある局所的最適解は高い適応度の個体たちによって（ハミング距離で in a Hamming sense）囲まれている．
• 実際，これらの関数は，局所的最適解を含む全てのスキマタが，レベルl-1かそれ以下の点にある他の競争相手より優れており，レベルlにおいてのみ大域的最適解はその要素を示すように，通常デザインされる．

パラグラフ3
• deceptive and multimodal な関数を持つことを欲すると仮定する．
• 第一に，我々はそれを既に持っていることに気付く．
• deception は mulimodality を含むが，多峰性関数である限りは，a little peak poor にみえる2つのoptimaのみを有し続ける．
• ここで我々の問題の一つは，local deceptive attractor から遠い global attractor maximally を置くための選択である．
• さらに，我々は本当に1より大きい濃度を持つ global solution set を持ちたい．その上，我々は多くの成分を持つ deceptive attractor を探し出したい．
• 我々がすべきである全ての要求を満たす関数を得るため，deceptive attractor を u=l にシフトする．そして，図2に示したように， u=l についてその関数を反射させることで全体的な関数を高める．
• さて，我々は二点を含む global set と中間の点に deceptive point を有する関数を得た．
• もし，我々が deceptive attractor の増加を考えるならば，中点へのシフトの回数を非常に増加させることだ．
• 長さ2lの文字列中に，半分の0と1を得るための多くの手段があるので，deceptive attractor に属する (2l l) の点がある．
• 後に，我々は 2^5=32 の 22^5=5.15(10^6) のトータルのためのサブ関数につき，22 optima 全てを我々に与える，length-sixの5つのサブ関数を用いるだろう．これは大きな数である．
• 我々は，干草の中の針32個を同時に探索することに慣れていない．特に，ストックするための場所が他に500万もある場合．

パラグラフ4
• このセクションにおいて，我々はここで採用した bipolar deception の定義と，そのような関数における deception のための十分な条件の集合を再検討した．
• 次のセクションでは，我々はそのような関数の2例の構成を再検討する．一例は二峰性の trap functions，もう一つの例は order-limited Walsh coefficients から構築した deceptive functions である．

---

1. Defining bipolar deception

   パラグラフ1
   • 通常のだまし関数では，もしその deceptive optima を含むスキーマがその区画内の他の競合するスキーマよりも良いならば，一つのスキーマ区画（schema partition）は deceptive であると定義される．
   • 両極型関数では，2つの大域的最適解と多くのだまし最適解が存在する．
   • その問題サイズより少ないorderの全スキーマ区画は，だまし最適解のみならず大域的最適解を表現するスキマタを多数含む．
   • 例えば，スキマタ00*...*と11*...*は，共に大域的最適解とだまし最適解を含む．?
   • しかしながら，スキーマ10*...*は大域的最適解でないものを含んでいるが，多くのだまし最適解を含んでいる．?
   • 従って，これらの問題で deception を定義するため，我々は通常の定義を修正しなければならない．
   • 一般的な deception のより厳密な定義が containment probabilistically 法の拡張により調べられている間，
     この論文では，我々は，もし最大個数（maximum number）のだまし最適解を含むスキーマもしくはスキマタが他の競争するスキマタと同然ならば，bipolar deceptive であるスキーマ区画を簡単に定義する．
   • このスキーマ区画deceptionの定義は，通常のケースにおいて，通常の定義に減少する（reduce to ; 変形する）．
   パラグラフ2
   • だまし関数において，order λのスキーマ区画は，0〜λに変化する unitation のスキマタを含んでいる．?
   • unitation u のスキーマは (2l-λ l-u) のだまし最適解を含む．?
   • 従って，unitation u=[λ/2] のスキーマは最大個数のだまし最適解を含む．?
   • もし，unitation u=[λ/2]のスキマタがそのスキーマ区画内で他のスキマタより大きいか等しいならば，従って，上記の定義に従うと，order λのスキーマ区画は deceptive である．
   • このスキーマ区画 deception の定義と共に，我々は，全スキーマ区画が deceptive である関数，両極型だまし関数（bipolar deceptive function）を定義する．
   • 我々は，order-oneスキーマ区画内の both schemata は同じ数のだまし最適解を含み，そして同一の適応度を持つことを認める．
   • 従って，だまし関数においては，order-one スキーマ区画は厳密な deceptive でははい．
   • 次に，我々は，unitationの両極型だまし関数における deception の十分条件を見つける．

   ---

2. Sufficient condition for deception

   パラグラフ1
   • deception のための十分条件は，全スキーマ区画内の deception を強要することで発見されるかもしれない．
   • それをするために，我々は，order λのスキーマの適応度と，f(u,λ,2l) としてのunitation uを定義する．
     => f(u,λ,2l)における order λ，unitation u のスキーマの適応度を定義する．
   • このスキーマは，固定点で u個の1とλ-u個の0，そして 2l-λ個の don't care positions を持つ．
   • 一つのストリングが f(u,2l,2l)として表現されるかもしれない．しかし，我々は単純に f(u) を量（quantity）を示すために用いる．
   • そのスキーマ適応度は，ストリングの関数値のとして，次のように表現されるだろう．
   • 式（1）
     f(u,λ,2l) = ... (1)
   • 検討中の両極型関数は u=l で対称的だから，我々は f(u) = f(2l-u) と書いても差し支えない．
   • unitation の対称的両極型関数の性質の多くは[Deb, 1992]で記述されている．
   • 十分条件は，それらの性質とその関数の対称性を用いることに由来する．
   • このセクションでは，我々はその解析結果を簡潔に記述する．
   • unitation の対称性両極型関数において，もし奇数スキーマ区画（odd-order schema partition）が deceptive なら，すぐさまより小さい偶数スキーマ区画（even-order）もまた deceptive である．
   • この提案は，deception 条件を発見するためには，odd-orderスキーマ区画のみが考察されることが必要である．
   • 全ての odd-order スキーマ区画内に deception を課すことと，unitation 0<=u<=l の文字列の関数値の観点からスキーマ適応度値（schema fitness value）を書くことは，もし下記の条件が満足されているならばその関数が deceptive であることを発見されることになる．
   • 式（2）
     第一最適性条件：f(0) > f(l);
     第一だまし条件：f(l) > f(0) - [f(l-1) - f(1)];
     第二だまし条件：f(i) >= f(j), for [l/2] <= i <= l-1 and l-i <= j < i.
   • 他の研究[Deb & Goldberg, 1992]では，類似の十分条件が単一大域（uniglobal）のために発見された．
     uniglobal => unitation 0 and l の個々に文字列となる global and deceptive attractors と共に，サイズlの完全だまし関数 ?
   • 後のセクションでは，我々はそのような関数の二通りの作成方法を記述する．

Construction of bipolar functions

パラグラフ1
• unitationの両極型だまし関数を作成するための2つの異なる手法をこのセクションで説明する．
• 初めに，両極型関数は完全だまし単一大域関数（a fully deceptive uniglobal function）から作成され，次に両極型関数は low-order Walsh coefficients から作成される．
• 両手法は上述の deception 条件を満足する．

---

1. A folded deceptive function

   パラグラフ1
   • 前のセクションでは，両極型関数が，完全だまし関数である uniglobal のシフトと反射により作成されるのを見た．
   • パラメータ folded unitation e=|u-l| を定義することは，我々は folded unitation の中で表現されたこの両極型関数が unitation の単一大域的関数（uniglobal）によって同様に表現されることを観察する（oberve ; 認める）．
   • [Deb, 1992]で，uniglobal 関数から作成された両極型関数において，uniglobal function のための deception 条件は，deceptionを満足している．
   • 我々は，その uniglobal だまし関数が0〜lに変化する unitation u を有する g(u) によって表現されており，その関数が u=0 で大域的最適解，u=l でだまし最適解を持つ，と想定する．
   • 次に，我々は，f(e)=g(u) を要求する両極型だまし関数 f(u) を作成する．
   • その両極型関数 f(u) は u=0, 2l で大域的最適解を2つ，u=l で (2l l) のだまし最適解を持つ．
   パラグラフ2
   • 具体的な例を図示するため，a folded-trap 関数が，完全だましトラップ関数（a fully deceptive trap function）[Deb & Goldberg, 1991]から作成される．
   • trap 関数は，一つの大域的最適解と，大域的最適解から最大に離れて位置づけられた一つのだまし最適解を有する unitation の関数である．
   • 式（3）
     g(u) =
     if (u<=z) then b/z(z-u),
     otherwize a/(l-z)*(u-z)
   • この関数において，その大域的最適解は zero unitation (all zeros) となるストリングであり，関数値 b（function value b）を有する．また，そのだまし最適解は unitation l (all ones) となるストリングであり，関数値 a を有する．
   • その関数値は，unitation z となるストリングのために zero となる．
   • 我々は，上述の関数 g(u) により，unitation の対称性両極型関数 f(u) (folded-trap function) の2lビットを作成した．
   • [Deb & Goldberg, 1992]で，この trap 関数の deception のための十分条件が発見されている．
   • その上述の議論に従うと，同じ条件が folded-trap 関数の bipolar deception のために適用している．
   • 従って，2l-bit 両極型だまし関数 f(u) のための十分条件は，次のように与えられる．
   • 式（4）
     a/b >= {(2-1z) / (2-1/(l-z))}.
   • 図3は，a=0.95, b=1.00, z=2 となる 10-bit folded-trap 関数を示している．
   • これらの値は上記の条件を満足する．
   • 従って，trap 関数 g(u) から作成した folded-trap 関数は deceptive である．
   • order one to nine のスキマタの平均関数値も同様に示している．
   • この図は，unitation [λ/2] のスキマタが任意の区画における他の競争するスキマタより良いか等しいことを示す．
   • 従って，全てのスキーマ区画は，function bipolar deceptive を作る deceptive である．

   ---

2. Using low-order Walsh coefficients

   パラグラフ1
   • uniglobal だまし関数を作成するために用いられたもの[Goldbeg, 1990]に類似する手続きを利用した low-order Walsh coefficients から，unitation の両極型だまし関数を作成する．
   • Walsh coefficients から関数を作成することは，スキーマ適応度値の計算を簡単化させる．それによって，deception 解析を単純化する．
   • 詳細な解析は[Deb, 1992]に記述されている．
   • このサブセクションでは，low-order Walsh coefficients から両極型だまし関数を作成するために用いたステップをまとめ，両極型だまし関数を作るために Walsh coefficients の間の相関を発見する．
   パラグラフ2
   • 我々は，特定の order の全ての Walsh 係数が同一であると想定する．
   • order λで unitation u のスキーマの，そのスキーマ平均適応度値は次のように書かれる．
   • 式（5）
     f(u,λ,2l) = Σ^λ_i=0w_i*Φi'(u,λ),
   • 式（5）において，w_i は i-th order Walsh 係数，その関数 Φi' は総数 i-th order Walsh 係数によって増加した i-th order Walsh 関数を表現する．
   • 式（6）
     Φi'(u,λ) = Σ^I_j=0(-1)^j*(u j)*(λ-u i-j).
   • サイズ2lの関数の値は，λ=2l の代替により，式（5）から獲得されるだろう．
   • その両極型関数は対称性だから，全ての odd-order Walsh 係数は0であると証明される．
   • order 0, 2, 4 Walsh 係数のみを用いることで，我々は unitation の対称性両極型関数を作成する．
   • 式（7）
     f(u,λ,2l) = w_0 + w_2*[ … ] + w_4*[ … ].
   パラグラフ3
   • 両極型だまし関数を作成するため，上記の関数（7式）は，
     l-最適性条件: f(0) > f(u) for 1 <= u <= l,
     a number of だまし条件: f(k,2k+1,2l) > f(u,2k+1,2l) for 1 <= k <= l-1 and 0 <= u <= k-1
   • 全状態において（in each case）これらの条件を用いること，critical 条件を発見することで，unitation の関数における bipolar deception のための下記の条件を得る．
   • 式（8）
     -(l-1)(l-2)/3 < w_2/w_4 < -(l-2)²/3.
   • 上記の条件において，w_4 は正である．
   • 図4に，unitation の10ビット両極型関数をプロットした．
   • さらに，その関数値を示すため，order one to nine の全てのスキーマ区画のための適応度平均を示した．
   • 10ビット両極型だまし関数のため，w_2/w_4 比の下限と上限は，それぞれ-4と-3である．
   • その関数は，w_2/w_4 比が-3.1，全ての関数値が非零となるように， w_0=0.4350960, w_2=-0.0248397, w_4=0.0080128 で作成された．
   • その関数は， unitation u=[λ/2] のスキマタが order λのスキーマ区画において他のスキマタよりも良い，ことを示している．
   • しかしながら，order-one スキーマ区画における2つのスキマタは，同じ適応度地を持つ．
   パラグラフ4
   • その上記の条件は，前のセクションで発見した bipolar deceptive のための十分条件からも得られるであろう，[Deb, 1992]で示されている．
   • 以下で，我々はだまし関数から多峰性だまし関数を作成し，その関数を解くためにGAを適用する．

Simulation results

パラグラフ1
• このセクションでは，その最後のセクションの関数の一つを用いて作成した大規模多峰性だまし問題（a massively multimodal deceptive problem）上で，シンプルGAと niched GA を適用したシミュレーション結果を報告する．

パラグラフ2
• 30ビット問題は，6ビットのサブ関数，同一の5つを結びつけることで作成される．
• 各サブ関数は，low-order Walsh 係数（w_0=0.40036, w_2=-0.020048, w_4=0.060024）から作成された6ビット両極型だまし関数である．
• 各サブ関数は従って，2つの大域的最適解と (6 3)=20 のだまし最適解を持つ．
• 従って，30ビット関数全体では，(20+2)⁵=5,153,632 optima を持ち，2⁵=32 が global となる．
• さらに，そのサブ関数が deceptive ならば，low-order スキマタはその探索を最も低い適応度（lowest fitness）となる optima へと導く．
• 従って，明らかに，その問題は解くことが困難である．

パラグラフ3
• この問題で走らせる幾つかのGAの結果を下に示す．
• runs の最初の集合では，その集団が正しくサイズされている場合，シンプルGAは首尾よく32大域的最適解の一つに収束した．
• 32大域的最適解全てを同時に発見するために niching を伴うGAを用いることはより困難であり，興味深い結果へと導いた．
• deception 上の解析に集中するため，我々はこれらのサブ関数の堅いコーディング（tight coding）を用いた．
• mixing の高さを保つため，突然変異確率 0.9 の一点交叉を用いた．
• 突然変異確率0は失われた多様性の回復を妨げるために選ばれた．
• 選択は非オーバーラップの集団を用いている交換なしのバイナリトーナメント（binary tournament）によって成し遂げられた．
• その集団サイズは下記のように変化された．

---

1. Simple GAs without niching

   パラグラフ1
   • シンプルGAは，もしその集団が十分なサイズであるならば，deception に打ち勝ち，32大域的最適解の1つに収束できる．
   • その上記の30ビット問題のために，[Goldberg, Deb, & Clark, 1991]において推奨された population-sizing 式は，約391個の個体を保守的な下限を産出する．
   • この限度は，全ての関数値を知っているならば簡単に計算できる．
   • 我々は，サブ関数の適応度分散の正確な値 ρ²=0.0600721 を計算することが可能である．
   • 検出されるためのシグナルは，そのサブ関数の大域的最適解（global maximum）とだまし最適解（deceptive optima）間の違い（difference），従って d=1.0-0.640576=0.359424 ，サブ関数の数 m=5 ，そして各サブ関数の長さ k=6 ，である．
   • sizing 式 : n=2c(m-1)2^kρ²/d² を使うことで，n=238c を得る．
   • C=90% の信頼限界（c=1.64354）のための集団を sizingし，n=391.3を得た．
   パラグラフ2
   • 図5は，異なる集団サイズに対する収束結果を示す．
   • [Figure 5:] 30-bit Bipolar Deceptive ProblemをシンプルGAで解いたシミュレーションは，最適化された sub function のパーセンテージと，信頼度（confidence）と集団サイズによって計算された収束を示している．
     同図では，Confidence factor = 0.9〜0.99の時に収束度合いが1になっている．
   • ここでは，収束度合い（Convergence）は，最終集団内にGAによって大域的最適化された（global optimized） sub functionsの パーセンテージとして計算される．
   • 111111と000000は，両方とも各 subfunction における最適な substring であることに注意しなさい．
   • ランダムに作成された10セットの初期集団が，全てのプロットした集団サイズにおいて使用された．
   • 現在の世代における最大適応度と平均適応度の差が無視できるほど小さい場合，特別な実行は収束することを決定された．
   • ここで示した集団サイズにおいて，収束は通常50世代以内で生じた．
   パラグラフ3
   • [Goldberg, Deb, & Clark, 1991]で説明したように，ζの収束性ファクタと共に，収束性の（図5で``Expected LB''と印された）予想した下限もまたζである．?
   • 従って，そのシミュレーション結果は，population sizing 推定は慎重であるという主張を補助する．
   • 図5が示すように，集団サイズが十分に大きいならば，シンプルGAは deception に打ち勝ち， global optimum へ収束できる．
   • しかしながら，集団サイズが保証下限391よりも少ない場合，GAは時折騙された．
   • 誤りが生じたとき，1つかそれ以上の subfunctions は，三つの1と三つの0という解（局所解）に収束した．
   • これらの結果は，その問題が本当に deceptive であることを指し示す．
   • 集団数256個体でさえも，しばしば全32個の global optima から連れ去られてしまい，500万の deceptive optima の一つに収束する．
   • しかし，適切に保証される集団サイズならば，良い意思決定（decision-making）が促進され，シンプルGAが global optima の一つを発見することを高い確率で可能にしている．

   ---

2. GAs with niching

   パラグラフ1
   • シンプルGAが多くの global optima の一つを発見することは，興味深くそして如何に困難であるかを示すために有用である．しかし，よりやりがいのある目標は， global optima 全て，もしくは可能な限り発見することだ．
   • このセクションでは，我々は全ての global optima を発見するための``multimodal GAs''を用いた，異なる3つの手法を記述する．
     • conventional niche sizing,（従来のニッチ・サイジング）
     • large, overlapping niches, and（大きく，重なり合うニッチ）
     • fitness scaling.（適応度スケーリング）
   • 我々は，bipolar problem への各々のアプローチの限界を説明し，そして，この特別な multimodal deceptive function の困難さを図解する．
   パラグラフ2
   • 3つの multimodal GA は，全て適応度シェアリング関数[Goldberg & Richardson, 1987]を用いたニッチング（niching）を実装している．
   • niched GA では，一個体の objective function value が，すぐ近くにいる個体群の存在により下げられる．
   • 従って，このタイプのシェアリングは，個体群の表現型かもしくは遺伝型による距離関数を必要とする．
   • この研究では，我々は個体群のバイナリ・エンコード間のハミング距離を用いる．
   • もし，2個体 i,j がハミング距離 d_{ij} かつ， d_{ij} <= σ_{share} によって分けられているならば，我々は share value sh(d_{ij}) = 1 - (d_{ij}/σ_{share})^α を，各々のニッチ数 m_i, m_j に加える．
   • ここで，σ_{share} は，我々が見積もったニッチの範囲である．
   • σ_{share}よりも離れた個体群は，お互いの適応度を下げない（sh(d_{ij} = 0 for d_{ij} > σ_{share}）．
   • 通例， triangular sharing function をもたらす α=1である．
   • 個体 i のニッチ数 m_i は， m_i = Σ_{j=1}^{n} sh(d_{ij}) ，ただし n は集団サイズ，として計算される．
   • そして，個体 i の shared fitnes は (f_i)/(m_i) によって与えられる．
   パラグラフ3
   • セレクションの間 shared fitness を用いると，遺伝的浮動（genetic drift）を失わせる．そしてシェアリングは，複数のピーク（ニッチ）以上の集団を，ピークの高さに比例して拡散する傾向がある．
   • 比例した選択と fitness sharing を用いたGAは，種々の多峰性関数の解法に，首尾良く用いられた[Deb, 1989]．
   パラグラフ4
   • [Oei, Goldberg, & Chang, 1991] によると， fitness sharing の native な実装は，トーナメント選択とは上手く働いていない．
   • その研究は，ニッチングの実装方法も提案する．トーナメントは，連続して更新された新しい集団において計算された shared fitness を用いている，2つのランダムな個体とプレイされる．そのようなトーナメントをニッチングを実装する方法として提案する．
   • 我々は，このニッチング・テクニックを実装し，残りのセクションで用いた．

   ---

   1. Conventional niche sizing and deceptive niches

      パラグラフ1
      • 30-bit多峰性問題では， σ_{share} を見積もる現在の手法を用いた niched GA は，single copy of any optimum を保持することさえも困難だ.
      • その代わりに，その GA は多くの騙し niches を探索する．
      • このような事例の原因を理解するため，我々は，その両極型騙し問題におけるサイズ σ_{share} の量と質考察する．
      • 表1は，その 30-bit 問題における異なる6タイプの局所最適解を記入している．
      • Table 1: 30-bit 問題における optima の量と質
      パラグラフ2
      • 我々は， niched GA のための集団サイズの近似下限を計算するため，以下のように表1の情報を用いる．
      • k 個の同一の騙しサブ関数という問題においては， optima の集合は，サブ関数を最大化した数（結果として k+1 個のパーティション）に分割される．
      • インデックス i は，そのサブ関数を最大化した数を指し示す．
      • 従って，パーティション k は，全てのサブ関数を最大化した，大域的最適解に一致する．
      • パーティション 0 は，サブ関数を一つも最大化しておらず，最小値の optima 群に一致する．
      • 表1は， k=5 の 30-bit 問題におけるそのような分割を示す．また，その適応度と各パーティションの濃度を含む．
      パラグラフ3
      • 我々は，そのGAが各 global peaks 上の個体θに収束することを必要とする．
      • niched GA は，全個体の shared fitness values が等しい安定した状態に到達したとき，``収束する''だろう[Goldberg & Richardson, 1987]．
      • 安定状態の時点で，，パーティション i における optima の平均ニッチ数（average niche count）が m_i である，と想定しよう．
      • そうすると，タイプ i の一 optima における一個体のための予想 shared fitness value は f_i/m_i となる．
      • 安定状態では，全ての i, j に関して， f_i/m_i = f_j/m_j である．
      パラグラフ4
      • 第一の近似として，全ての optima が σ_{share} よりも離れて各々分割されていると仮定する．すると，各 optima は niches の重なり無く，自分の niche の中央に位置できる．
      • 次に，そのニッチ数 m_i は，パーティション i 内の各 optima の点にある予想個体数に等しい．
      • それゆえ， Σ_{i=0}^{k} m_i*μ_i = n ，ただし n は集団サイズである．？
        各タイプの optima に，ニッチ数による適応度減衰を与えた値（f_i/m_i）は，全ての i, j で等しい．
      • 再編成することで，我々は式（9）を引き出す．
      • 式（9）
        n = m_k/f_k * Σ_{i=0}^{k} f_i/μ_i, ただし， m_k は各大域最適解の点上の予想個体数である．
      • そして，各 global peak 上に個体θを要求された集団サイズの近似下限を求めるため，我々は単純に m_k の代りにθを用いる．
      • 30-bit 問題のために，表1の μ_i, f_i を式（9）に用いることで，我々は n=3,468,240*m_5 を得た．
      • もし，我々が安定状態の集団内で各大域解のコピーを最小の1個欲しいならば，我々は少なくとも集団サイズ 3,468,240 を用いるべきだ．
      • そのような大きな集団サイズは全探索空間の意味ありげな一部となっている：
        3,468,240 * 2^{-30} =/= 0.003
      • 従って，100世代の run もすると，総計算コストがその探索空間の列挙探索（enumerative search）と同じぐらいのオーダーだろう．
      • また，そのような集団数は， most serial implementation のGAには大きすぎる．
      • 3,500,000よりも非常に少ない集団で行った run の幾つかは， global peaks の一つの個体も産生し得なかった．
      パラグラフ5
      • そのような犠牲（price）のために，我々は，多くの non-global peaks の相対的な利点（merits）を示す，個体群の比例した（proportionate. バランスのとれた）分布を得る．
      • しかし，もし我々が global optima のみに興味があるならば，我々はつまらない解で，価値ある集団財産（valuable population real estate）を浪費している．

      ---

   2. Large niche size

      パラグラフ1
      • 月並みに（conventionally；慣習的に），我々は，少なくとも問題空間内の全ての global peak が自分のニッチを持つように σ_{share} を見積もる．
      • 騙し問題のために，大域最適解は各々6ビット異なるので，σ_{share} < 6となる．
      • しかしながら，（サブ関数を最適化していない）最も多い騙し解群は，各大域最適解から正確にl/2 = 30/2 = 15 bitsハミング距離に位置する．
      • 全ての optima の約62%，320万個がそのような騙し解がである．
      • 大域的最適解のニッチの外側でそれだけ多くの suboptima があり，集団の多くがそのような optima の周りに整列するニッチによって吸収されるだろう．
      • 従って，適切な fixed-point sizing を用いない従来の σ_{share}-sizing は，将来が有望とは思えない．
      パラグラフ2
      • この問題への別のアプローチは，その320万個の騙し解（必然的に，他の全ての騙し解）は大域的最適解の周囲に集まったニッチの範囲内に存在するように，そのニッチサイズ（σ_{share}）を大きくするかもしれない．
      • 最適解と騙し解が同じニッチ内で競合するなら，その最適解が優位となるだろう．
      • [l/2]と等しいか，それ以上の σ_{share} 値は，全ての騙し解が少なくとも一つの最適解が中心にあるニッチ（one global-centered niche）の範囲内に位置することを保証する．
      パラグラフ3
      • σ_{share} = [l/2] + 2とした実験は，幾つかの大域的最適解を発見し，重要なサブ集団を保持する，という結果を示した．
        （脚注：ニッチの端の外のシェアリング度合いを促進するため，power sharing function の指数部αを4に増加した）
      • 32個の大域的最適解を持つ5つのサブ関数問題のため，保持された（各々約2000コピー）．他の28が上下に広く振動した（0〜200）重要でない数のコピーを入手した間，4つの大域的最適解が発見された．
      パラグラフ4
      • 何故，32個の大域的最適解のうちただ4つが見つかったのだろう?
      • その答えは，大域的最適解を中心としたニッチの重なりにある．
      • 上記のの問題において [l/2] のニッチ半径（σ_{share}）を与えられ，我々は32個中最大4個の解を選択することが出来る．ただし，各々の解が，他の三つから少なくとも σ_{share} + 1 ビット異なるように．
        ＝＞ここでは l=30 であるから，16ビット以上異なるようにしなければならない．一つのサブ関数は6ビットであり，6*3 <= 16ビット <= 6*4=24 ビットとなるため，少なくとも互いに4つの関数における最適解が異なる必要がある．
        4つの解の例）
        • 00 00 00
        • 00 11 11
        • 11 11 00
        • 11 00 11
      • そのニッチ内の最適解群は互いに競合するだろう．
      • 遺伝的浮動や他の要因は，そのニッチが一つの大域的最適解へ収束する原因となるだろう．
      • 従って，この問題においては， σ_{share} >= [l/2] を用いて保持することを予測可能な大域的最適解の最大個数は，4である．
      • 確かに，我々の larege-σ_{share} による実験結果では，1000以上のコピーと共に4つの解が σ_{share} ビットよりも離れている．
      パラグラフ5
      • large-niche-size アプローチのこの欠点はシビア（severe）である．
      • 通常，そのようなサイズ l の両極型問題のために，過半数の騙し解は各大域的最適解から正確に [l/2] ビットの距離に位置し，その各大域的最適解は他の k の大域的最適解から，多く見て l_s ビット（サブ関数の長さ）離れているだろう．
      • 従って，我々はこのアプローチを用いて，大域的最適解の総数の一部分よりもよりものを得ることが出来ない．
        ＝＞局所解と最適解は l/2 = 15 ビット離れている．最適解同士は少なくても l_s = 6 ビット離れたものがある．すなわち，局所解を得ないように σ_{share}=15ビット 以上とした場合，全ての最適解を得ることが不可能．
      パラグラフ6
      • それ故，この問題は，騙しであることや騙しアトラクタの質のためだけではなく，大域的最適解間のこれらのアトラクタの配置のため，困難である．
      • その大域的最適解の間隔が与えられ，騙し解の過半数は大域的最適解から最も遠い点に配置される．
      • これは，極めて困難な niche sizing を作る．
      • 互いに競合し続ける大域最適解群が standard niched algorithm の増強（augmentation）を要求する間，騙し解は大域的最適解との競合を強制される．
      • 次のセクションでは，我々はこの問題のための全32個の解発見の成功を得る，一つの追加物（augmentation）を示す．

      ---

   3. Fitness scaling

      パラグラフ1
      • ここまでは，6ビット両極型関数により作成した30ビット問題への3つの手法が明らかにした分析は，困難であることを明らかにした．
      • GAの実験は，騙しスキーマ・パーティションの影響を実証した．
      • 従来の niche sizing 計算は，niched GA で問題となる，optima (niches) の完全な個数（the sheer number）を計算する方法を示した．
      • 最終的に， large niche size による実験と解析は，大域的最適解と騙し解の可分性（separability）の重要さを明らかにした．
      • 多峰性問題の困難さのこれらの3つの状況は，無関係ではなく，6ビット両極型関数による30ビット関数が3つ全て最大化するように見えるのは偶然の一致ではない．
      • しかし，このセクションでは，我々はこれらの困難さに打ち勝つ手段と32個全ての解を発見する手段に関心を持つ．
      パラグラフ2
      • 基本となるニッチング・アルゴリズムへの多くの補強が可能である．
      • 一つのシンプルなアプローチは，shared fitness の計算に先だって，関数のスケーリングすることである．
      • その目的関数をぴったり合う指数部（a suitably large exponent）へ上げることにより，我々は，騙しアトラクタに集中したニッチに比例して，大域的最適解に集中したニッチのキャパシティを増加させる．
      • その安定（steady. 規則的な）状態のニッチング式から，
        n = m_k * Σ_{i=0}^{k} μ_i * (f_i/f_k)^β.
      パラグラフ3
      • m_k を固定とする間，βを上げることで，（安定状態における，各大域的最適解にある予想個体数） m_k を保持するのに必要とされる集団サイズ n を減少させる．
      パラグラフ4
      • 特に，30ビット両極問題のため，我々は，β=15と集団サイズ5000を用いて，各々の大域的最適解の点で安定したサブ集団を獲得した．
      • 幾つかの実験は，以前に記述したシンプルGAの実験のために作成された初期集団群から引き出された初期集団を用いて実行された．
      • 図6は，そのような実行の一例を示す．
      • 図6：
        各200世代のための，32個の大域的最適解のためのサブ集団サイズの幅が斜線エリアで示される．黒線としてプロットしたものは，世代毎の32値の平均である．
      • 他の実行は，この様式でプロットした場合，とても似た結果を生じた．
      • 図6は，各世代における各々32個の global peaks 上の個体数の指標を与える．
      • 斜線エリアは，実際は全世代における optima のための値の範囲である．
      • 従って，斜線エリアの上限はその世代のための32optimaの幾つかの点におけるコピーの最大個数であり，下限はその値の最小である．
      • その実践実線は，各世代における，1ピークあたりの平均個体数のグラフである．
      • その2つのプロットは，ピークからピーク，世代から世代への重要な変動を指し示すが，それは明らかに，サブ集団が約40から80個体の範囲内で保持されている．
      • この個数は，32個全ての解を発見するために大きく，そして十分に安定して見える．また，ノイズの入った安定状態の幾つかで保持されている．
      パラグラフ5
      • fitness-scaling アプローチは，これらの問題点の最初の2つに直接取り組むことで，そして，3番目を避けることで成功する．
      • 第一に，スケーリングは騙しスキーマ・パーティションの数を減じる．
      • 第二に，適応度のスケーリングにより，大域的最適解の予想個数が，騙し解の支出の点で高められている．
      • 低い予測ニッチ数と共に，討論する点のより良い可分性を作成するため，多数の騙し解が消去へと効率よく移動されている．

Conclusions

パラグラフ1
• この論文は，騙しを含む大規模な多峰性関数の構成と最適解について考察を行った．
• 特に，両極型騙し関数は2つの大域的最適解と多数の騙しアトラクタを持つと定義される．
• 両極型関数における騙しの十分条件を設定し，そして特定の騙し関数が2つの異なる手法（using a uniglobal deceptive function and the idea of folded unitation, and using low-order Walsh coefficients）によって構成された．

パラグラフ2
• 30ビット関数は，6ビット両極型関数を5つ結合することによって形成される．
• その関数は，500万以上の optima 中，32個が大域的最適解である．
• シンプルGAは，その集団がノイズからのシグナルを検出するために適切にサイズされるならば，32個中1個の大域的最適解を発見することが可能である．
• シェアリングを用いたGAは， fitness scaling と appropriate fixed-point sizing を用いた場合，32個全ての大域的最適解を同時に発見した．

パラグラフ3
• 現実的な局面において，その研究は，種々のアプリケーションの大規模な多峰性問題という困難に対する，ありふれた解のためのドアを開く．
• 理論的な見地から，その研究は，一般化されているであろう deception のコンセプトに沿った目的達成のための手段を明らかにする．GAにとって困難な問題を意味するもの全てを取り囲む抽象化になりうるように．
• より上昇させた展望から，この論文は基礎的な効用と共通の良識（common sense）を確認するため，詳細にGA研究の計算を試行錯誤する．
• …，しかし，GA（と，その他全ての complex systems）は， no quicksort である．
• もし，我々が，我々の注目を待ち受ける問題の残像（problem spectrum）を越えて，それらを頼もしく使うのに十分理解しているならば，計算（computation）と解析（analysis）は連続的に相互作用しなければならない．
• その処理の一部分は， good questions を求められるけれども，直感的な良い答えや，理論と計算機実験のワン・ツー・パンチによる裏打ちは，約束された地へのチケットである．
• （以下略…）