Denis Pallez 
  
Paired Comparison-based Interactive Differential Evolution 高木英行

はじめに

差分進化 [START_REF] Storn | Differential Evolution -A Simple and Efficient Heuristic for global Optimization over Continuous Spaces[END_REF]は この10年で論文数が急増している進 化論的計算手法である. IECにとって差分進化手法には 2つの利点がある.第1は個体の比較が対比較である点 であり,第2は高速である点である.この差分進化技術 を最初にIECに応用したトルコチームの対話型差分進 化 [START_REF] Akbal | Interactive Nature-Inspired Heuristics for Automatic Facial Composite Generation[END_REF][START_REF] Kanlıkılıçer | Interactive Differential Evolution for Facial Composite Generation[END_REF][START_REF] Kurt | Active Appearance Model-Based Facial Composite Generation with Interactive Nature-Inspired Heuristics[END_REF] [START_REF] Johanson | Automated Fitness Raters for the GP-Music System[END_REF].文献 [START_REF] Johanson | Automated Fitness Raters for the GP-Music System[END_REF] では,単に勝敗情報を使うトーナメントだけでなく, 勝敗の程度をも考慮してフィットネスを調整するトー ナメント IEC も提案している.本論文でもこの 2 種類 のトーナメント IGA を比較対象とする. Tournament1 GA は勝ち残りトーナメントとかノッ クアウトトーナメントと呼ばれる典型的なトーナメン ト方式に基づいてフィットネスを決定し GA で進化さ せる方式である [START_REF] Angeline | Competitive Environments Evolve Better Solutions for Complex Tasks[END_REF][START_REF] Panait | A Comparison Of Two Competitive Fitness Functions[END_REF] 代までの探索を 100 試行行う.IGA では第 3.1 節で述べ たように 5 段階評価をシミュレーションする.トーナ メント IGA と対話型差分進化では,Fig. 3 

. 最初個体はランダムに並べられ て対比較を行い, 第 1 試合の勝個体間で第 2 試合を行う. 以後同様に最終勝者が得られるまでトーナメントを進 めて,勝ち進んだ対戦数に基づいてフィットネスを決 定する方式である. Tournament1 GA を IEC に用いると, 通常 IEC に比べて大幅な評価時の疲労軽減が期待でき る. Tournament2 GA は勝ち残りトーナメントに基づく ものの,勝負の程度情報を考慮してフィットネスを決 定する.例えば,最終勝者個体のフィットネスを 10 点 とし,この最終勝者個体と戦った個体のフィットネス は,最終勝者個体との評価差を 10 点から差し引いた値 とする.次に,最終戦で勝者個体に敗れた個体と戦っ た個体のフィットネスを同様に,この最終戦で勝者個 体に敗れた個体のフィットネスから対戦評価差を差し 引いた値にとする.以下同様に全個体のフィットネス を決定する.この方式の考え方の背景は,対戦組合せ の運不運の影響を少なくすることにある.例えば,最 強個体と第 2 最強個体が運悪く第 1 試合で対比較した 場合,Tournament1 GA では第 2 最強個体が全個体の中 での最悪個体にならざるを得ないため選択演算に悪影 響を与える,と考えられる.Tournament2 GA ではこの 点が改善される. トーナメント GA では全個体の比較を行わないので, その分, 通常 GA に比べてフィットネスの信頼性が劣る. 上述の例のように第 2 最強個体に最悪フィットネスが 割り振られることもある.したがってノイズを含むフ ィットネスに基づいて選択を行うトーナメント GA は, 原理的には通常 GA に比べて収束が劣ると考えられる. トーナメント IEC では,対比較方式による疲労軽減効 果とこの収束悪化による疲労増加との程度とのバラン スが問題であり,主観評価実験での評価が必要になる. 2.2 差分進化 差分進化[9]は数値最適化のための進化論的計算手 法で,アルゴリズムが容易であるにも関わらず収束が 高速であるであるという特長がある.SCOPUS 論文デ ータベースによると,1995-

評価タスク

擬似IECユーザ

IEC のアルゴリズム評価は,同一実験条件下で,パ ラメータを代えながら多くの比較評価実験を繰り返す 必要がある. 人間による IEC 実験では,必要実験回数, 同一実験条件の点で実験結果の信頼性に欠け,アルゴ リズム評価ができない.したがって,最終的には人間 による評価をするにしても,アルゴリズム評価実験に は擬似 IEC ユーザを構成して IEC シミュレーションを 行うことが望ましい[8]. 擬似 IEC ユーザを構成するためには,3 つの IEC の 特徴を組み込む必要がある. (1) 概して複雑ではない評価特性 (2) 世代毎の相対的フィットネス (3) n 段階の離散的フィットネス さらに,様々な評価特性を容易に実現するために,擬 似 IEC ユーザモデルはパラメトリックに制御できる必 要がある. 上記(1)は第 3.2 節で述べる混合ガウスモデルで実現 し,(2)は第 2.1 節で述べた競合フィットネス[7, 13, 14] で実現し,(3)は混合ガウスモデルで得られた最良フィ ットネスと最悪フィットネスを毎世代 n 段階に離散化 することで実現する. 実験では,4 つのガウス関数からなる混合ガウス関 数で IEC ユーザの心理的評価特性を表す.4 つのピーク からなる多峰性ではあるが大局的には大谷構造の評価 特性にすることで,単峰のような単純さではないもの の,騙し問題のベンチマーク関数のような極端な複雑 度はない上記(1)を実現する(Fig. 3.参照).これは,少 個体数と少世代数にもかかわらず, IEC ユーザが満足で きる解が得られることが上記(1)の背景理由である. 3.2 混合ガウスモデル 評価実験タスクには,第(1)式で表す 4 種類(n = 3, 5, 7, 10 次元)の混合ガウス関数を用いる.各次元とも k =4 個のガウス関数から成る混合ガウス関数にし,第 i 番目のガウス関数の(振幅,平均,標準偏差)=(a i , μ ij , σ ij )を 4 種類ともすべて同じにすることで,実験条件と してのタスクの複雑度は,次元数のみを変えることで 実現する. ∑ ∑ = = ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ - - = k i n j ij ij ij i n x a x x f 1 1 2 2 1 2 ) ( exp ) , , ( σ μ L (1) 本実験で用いた(1)式のパラメータ値を以下に示す. ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ = 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 σ , ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ = 3 4.1 3.4 3.1 a ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ = - - - - - - - - - - - - - - - - - - - - - 1 2 3 1 1 2 3 1 1 2 2 5 . 2 5 .
の Z 軸に相当 するフィットネス値域を 50 分割して弁別閾とした.す なわち,2 提示個体のフィットネス値差がこの 1 分割以 下であれば IEC ユーザはどちらが良いかの評価ができ ない状態を擬似 IEC ユーザとしてシミュレーションし, この場合は提示 2 個体のうちどちらかをランダムに選 択することにする.なお,差分進化には色々なバリエ ーションがあるが,本論文では DE/Best/1/bin アルゴリ ズムを用いた 個体数は 16 と 128 個体で行う.前者は通 常の IEC を,後者は通常の進化論的計算を意識した値 である.ただし,128 個体は,特性解析のために,本論 文の主題である対話型差分進化および他の IEC との比 較参照用に行う実験条件であり,現実的な個体数では ない.本実験ではトーナメント GA およびトーナメン ト IGA で不戦勝のシード個体を避けるため,2 のべき 乗の個体数(16 個体)としたが,この条件はトーナメ ント進化論的計算に必須の条件ではない. 4.2 参照実験:差分進化と他の3つの進化論的計算手法 との比較 一般論として,以下のようなことが言われている. • 進化論的計算の探索では,多数個体に比較して少 数個体の方が困難 • 次元数が高い(複雑度が高い)タスクはより困難 • 全個体を比較して親個体を選択する通常 GA に比 べてトーナメント GA は選択演算に利用する情報 の信頼度が少ないので,一般的には,トーナメン ト GA の収束速度は通常 GA よりも遅いと考えら れる • ここ 10 

結論

IEC ユーザの疲労軽減には,より良い IEC ユーザイ ンタフェースと収束の高速化が重要である.本論文で は,全個体評価が必要な通常の IGA に比べて大幅な疲 労軽減効果が期待できる対比較が可能な対話型差分進 化を提案し,収束速度を IEC シミュレーションで比較 した.対比較は,特に音や映像のように同時提示をし て空間的に比較できないような IEC タスクを評価する 際に効果が大きい. 従来の IGA に対するこの対比較の 効果は明確なので,もう 1 つのキーポイントである収 束速度について,対話型差分進化を IGA とトーナメン ト IGA について比較しその有効性を示した.これら 2 つの特長をもつ対比較ベースの対話型差分進化は IEC の有力なツールになるといえる. 次の研究ステップとして,人間の IEC ユーザによる 評価である.既にこの方向に着手しているので,次の 機会に報告したい. 謝辞 本研究は,H20年度卒研生の満安大樹君の予備研 究を基に,日仏共同研究で発展させたものである.デ ータ準備等で協力を得た満安君に感謝します. 参考文献

Fig. 2

 2 Fig. 2 GUI of Interactive Differential Evolution and displayed a pair of a target vector and a trial vector in a searching space.

  遺伝子は 12 bits からなる実数で,個数は混合ガウス 関数の次元数(3, 5, 7, または 10)である.GA 演算は, 個体 2 個のトーナメント選択と交差率 100%の多点交差 を行い,突然変異率は 5%とする.各実験では,100 世

Fig. 3 .

 3 Fig. 3. 3D view of a 4D Gaussian Mixture Model used in our experiments.

  年の急激な差分進化研究の増加は,通常 GA よりも高速という期待現れ この参照実験結果に対して統計検定を適用しては いないが,Fig.s 5-12 はこれらの一般的な観察すべてに 合致した結果が得られている.さらに,IGA やトーナ メント IGA に比べ,少数個体(16 個体)での探索でも 収束特性がよい. 4.3 対話型差分進化と他の3つのIEC手法との比較 応用タスクやユーザにも依るが,実用的な IEC の使 い方から見れば,IEC 探索世代数はせいぜい 10~20 世 代程度,頑張っても 30 世代程度まで,個体数もせいぜ い 20 個体程度まで,というのが現実的な利用方法であ ろう.しかし本実験では,IEC の一般的な収束特性を観 察するため,100 世代までシミュレーションを行う. 実用的なIEC条件 (個体数16個の少数個体) のFig.s 13-16 から, 極初期世代を除いて対話型差分進化はIGAやトー ナメントIGAに比べて収束特性がよい,と言える.個体 数を十分に増やした場合(個体数128個)のFig.s 17-20 ではIGAなども収束特性が対話型差分進化並みに良く なってくるがそれでもFig. 20の10次元タスクのように 複雑度が高くならないとIGAは対話型差分進化に対し て優位にならない. 実用的なIECの個体数から考えると, 対話型差分進化が今回比較した4種類のIECの中では収 束性が一番よいと言える. 5. 考察 100 試行に対して,差分進化または対話型差分進化 を他の 3 種類のアルゴリズムの中のベストアルゴリズ ムと比較した場合の符号検定結果を Fig. 4 に示す. 実用的な IEC の結果である 16 個体と実用的な世代 数での比較を見ると,対話型差分進化が有意に IGA か 2 種類のトーナメント IGA に劣るのはタスクの次元数 10 次元と最も複雑な場合だけである.この 30 世代近く まで有意に劣る場合であっても Fig. 16 を見て分かると おり,実質的にはほとんど差がない,というのが実態 に近いであろう. それに対して対話型差分進化が他の 3 種類の IEC のいずれよりも有意になる場合は,Fig.s 13-15 のように大きな収束差をつけている. IGA やトーナメント IGA が対話型差分進化に対して 有意になるのは,個体数 128 でタスク次元数が 10 次元 と最も複雑な場合だけである.もちろん,IEC としては 現実には使えない個体数条件である. IEC ではない差分進化であれば,どの場合でも(16 個体でも 128 個体でも,タスクの複雑度が高い場合で も低い場合でも) 差分進化が GA やトーナメント GA に 比較して,早い世代から有意になる. 10 次元タスクでのみ対話型差分進化と同等以上を 示している IGA ではあるが,IEC ユーザに全個体の相 互比較を強いるので,Fig. 16 に見られる程度の IGA と 対話型差分進化の差であれば,対比較が可能な後者の 方が IEC には適しているといえる.

Fig. 4 .

 4 Fig. 4. Sign test for DE and interactive DE (IDE); blue dots mean that DE (or IDE) is significantly better than any other three algorithms (p < 0.01), and the red dots mean that DE (or IDE) is significantly poorer than at least one of others (p < 0.01). Left axis shows experimental conditions with different population sizes and task dimensions, and marked four conditions are of IDE with 16 population size that is a practical condition.

Fig. 5 .

 5 Fig. 5. EC Task is 3-D Gaussian Mixture Model (16 individuals).

Fig. 6 .

 6 Fig. 6. EC Task is 5-D Gaussian Mixture Model (16 individuals).

Fig. 7 .

 7 Fig. 7. EC Task is 7-D Gaussian Mixture Model (16 individuals).

Fig. 8 .

 8 Fig. 8. EC Task is 10-D Gaussian Mixture Model (16 individuals).

Fig. 9 .

 9 Fig. 9. EC Task is 3-D Gaussian Mixture Model (128 individuals).

Fig. 10 .

 10 Fig. 10. EC Task is 5-D Gaussian Mixture Model (128 individuals).

Fig. 11 .

 11 Fig. 11. EC Task is 7-D Gaussian Mixture Model (128 individuals).

Fig. 12 .Fig. 13 .

 1213 Fig. 12. EC Task is 10-D Gaussian Mixture Model (128 individuals).

Fig. 14 .

 14 Fig. 14. IEC Task is 5-D Gaussian Mixture Model (16 individuals).

Fig. 15 .

 15 Fig. 15. IEC Task is 7-D Gaussian Mixture Model (16 individuals).

Fig. 16 .

 16 Fig. 16. IEC Task is 10-D Gaussian Mixture Model (16 individuals).

Fig. 17 .

 17 Fig. 17. IEC Task is 3-D Gaussian Mixture Model (128 individuals).

Fig. 18 .

 18 Fig. 18. IEC Task is 5-D Gaussian Mixture Model (128 individuals).

  Fig. 19. IEC Task is 7-D Gaussian Mixture Model (128 individuals).

  Fig. 20. IEC Task is 10-D Gaussian Mixture Model (128 individuals).

基底 vector に重み付けした差分 vector を加え,変異 vector を求める, (5) 目標 vector と変異 vector を交差させて比較参照 vector を生成する, (6) 目標 vector と比較参照 vector を比べ,良い方を次世

  

	収束特性が良いメカニズムは,収束に伴って狭まっ
	てくる個体分布の拡がり情報が差分ベクトルの長さに
	反映されるので,それに伴い次世代個体分布が調整さ
	れるからである.すわなち,広域探索と局所探索のバ
	ランスが自動的と取れるメカニズムを持っている.
	2.3 対話型差分進化
	IEC の視点から第 2.2 節のアルゴリズムを眺めると,
	疲労軽減の点で(6)の対比較が非常に魅力的であり,対
	比較ベース対話型差分進化が構築できる[18].目標
	vector, 比較参照 vector)の対を Fig. 2 のように提示して
	対話型差分進化ユーザにより良い個体を選択させる.
	これが前節の(6)に相当する.各世代には個体数分の比
	較対があるので,この二者択一選択を繰り返す.IGA
	のグラフィカルユーザインタフェース(GUI)では,提
	示された全個体を相互判断しないといけないので IEC
	ユーザの評価心労が大きいが,トーナメント IGA や対
	話型差分進化の二者択一 GUI ではこの点が大きく改善
	される.
	の 3 期間の論文数は 58, 265, 1,569 編と近年論文数が急
	増している.
	アルゴリズムの概要を Fig. 1 を使って以下のステッ
	プに述べる[9,16].
	(1) 1 個体を目標 vector として取り出す,
	(2) 残りの個体から 2 個体をパラメータ vectors としてラ
	ンダムに選択し両者の差分 vector を得る,
	(3) 残りの個体からランダムに,あるいは,ベスト個体
	を選び,基底 vector とする,
	(4) 代の個体とする.
	(7) 以下(1)に戻って他の個体についても同様に次世代
	個体を生成する.
	Fig. 1 Differential Evolution algorithm

1999,[2000][2001][2002][2003][2004]