実数値遺伝的アルゴリズムにおけるドロネー三角形分割を用いた子個体生成方法の提案

下坂 久司，廣安 知之，三木 光範

ISDL Report   No. 20050509009

2006年 03月 18日

Abstract

本報告では，実数値遺伝的アルゴリズムにおいてある複数の親個体から多数の子個体を生成する際に，目的関数のランドスケープを考慮し，目的関数値の高い領域付近に集中的に子個体を生成できる手法を提案する．提案手法では，シンプレックス交叉を拡張し，ドロネー三角形分割を用いて子個体を生成する．実際に複数のテスト関数を用いて子個体を生成し図示した結果，目的関数のランドスケープに合わせた子個体の生成を行えていることを確認した．

1  はじめに

実数値遺伝的アルゴリズム ( Real-Coded Genetic Algorithm: RGA ) は，設計空間内の親個体の分布を直接的に取り扱って子個体を生成できるという特徴を持つ． RGAの交叉オペレータとして，UNDX[2]，UNDX-m[3]，SPX[1]などがすでに提案されており，いずれも比較的高い探索性能を持つことが知られている． これらの交叉オペレータの設計指針の1つに，機能分担仮説[4]がよく知られている． 機能分担仮説では，交叉オペレータは個体集団の分布を変化させない子個体を生成することが重要であり，個体集団の分布は世代交代モデルが変化させ，母集団を収束させるとしている． 機能分担仮説に基づくことで，比較的探索性能の高い交叉オペレータを容易に設計することが可能になると考えられている． また個体集団の分布に基づく子個体の生成は，確率モデル遺伝的アルゴリズム(Probabilistic Model-Building Genetic Algorithm: PMBGA)などにおいても非常に重要な考え方である．

一方で我々は，子個体を生成するための分布は，親個体の分布だけではなく，目的関数のランドスケープも考慮する必要があると考える． 例えば，RGAの交叉オペレータの1つであるSPXでは，親個体の分布から子個体を生成する範囲を決定し，決定した空間内に一様に子個体を生成する． ここで，子個体を生成する範囲内においては，目的関数値の高い領域により多くの子個体を集中させることで，探索性能をより高めることが可能であると考えられる．

本報告では，目的関数値の高い領域に子個体を生成させるために，ドロネー三角形分割を用いた子個体生成方法を提案する． 次章では，まず提案手法のもととなるSPXについて述べ，その後提案手法について述べる． 最後に，提案手法を用いて子個体を生成した際の，子個体の分布を視覚的に表現する．

2  シンプレックス交叉

樋口らによって提案されたシンプレックス交叉(Simplex Crossover: SPX)では，以下のアルゴリズムに基づき，子個体を生成する． n次元の探索空間において，個体はn次元の実数ベクトルで表現されている．

  1. 個体群から(n+1)個の親個体 P0, P1, ... ,Pnをランダムに選ぶ
  2. 親個体の重心Gを求める
  3. 以下の式に基づき，xkおよびCkを，K=0,..,nについて求める． ここで，εは正のパラメータで拡張率と呼ぶ． またu(0,1)は[0,1]の一様乱数を表し，k=0の場合Ckをゼロベクトルとする．
    4. eq
  4. 子個体Cを，C=xn+Cnによって得る．

2次元の探索空間(親個体は3個体)において，SPXの子個体生成範囲をFig.1に示す． 一般的に，Fig.1のグレーの領域に多数の子個体が生成される．

spx
Figure 1: SPXの子個体生成範囲 ( 出典 : 自作 )

3  ドロネー三角形分割 を用いた子個体生成方法

前述したように，RGAにおける交叉オペレータの役割として，個体集団の分布を変化させない子個体を生成することが挙げられる． 一方で，目的関数値の高い領域に子個体を集中させることが，高い探索性能を実現するために，必要不可欠であると考えられる． そこで提案手法では，SPXを用いて一部の子個体の先に生成し，その後，SPXにより生成された子個体の評価値から，残りの子個体を目的関数値の高い領域に生成する． その際に，ドロネー三角形分割を子個体の生成に応用する． D次元の探索空間において，(D+1)個の親個体からNc個の子個体を生成する際の，提案手法の子個体生成手順は以下のとおりである．またFig.2に，提案手法の概要を示す．

  1. SPXを用いて，あらかじめ定められた割合 (Rspx) の子個体 ( Nc * Rspx 個 )を生成する．
  2. あらかじめ定められた回数(Nd)，以下の(3) から(5)を繰り返す．
  3. 子個体の設計空間上の座標から，ドロネー三角形分割を行う．
  4. 子個体を評価し，各ドロネー三角形の評価値を計算する．ここで過去に評価した子個体は評価しない．またドロネー三角形の評価値は，対象とするドロネー三角形を構成する子個体の評価値の総和とする．
  5. 評価値の良い順に，( Nc * ( 1 - Rs ) / Nd ) 個 のドロネー三角形を選択し，その重心に子個体を生成する．
delaunay
Figure 2: Overview of offsprings generation using delaunay triangulation ( 出典 : 自作 )

提案手法においてRspxを1.0とした場合，ドロネー三角形分割によって子個体が生成されないため，SPXと同じ手法となる． また提案手法を用いることで，追加的な評価計算は発生しない．つまり，1世代の評価計算回数はNc回である．

4  生成される子個体の分布

2次元の探索空間において，3個の親個体から500個の子個体を生成した際の，子個体の分布をFig.3に示す．提案手法のパラメータであるRspxを0.5に，Ndを2とした．またSPXのパラメータである拡大率は1.0とし，親個体に構成される三角形の内側にのみ，子個体が生成されるようにした．これらにより，まずSPXによる子個体が250個生成される．ドロネー三角形分割を用いた子個体の生成は2回行われ，それぞれ125個の子個体を生成する．つまり最初のドロネー三角形分割は250個の子個体を用い，2回目は375個の子個体を用いる．

delaunay
Figure 3: Offsprings distributions ( 出典 : 自作 )

Fig.3より，最終的に生成されて500個の子個体の分布は，目的関数のランドスケープにより異なっていることがわかる．ここでSPXにより生成された最初の250個体は，親個体の分布のみを考慮しているため，目的関数のランドスケープによらず同じ子個体が生成されている．一方でドロネー三角形分割を用い，評価値の良いドロネー三角形に子個体を生成する提案手法では，目的関数のランドスケープを考慮した子個体の生成が行えている．また，ドロネー三角形分割による子個体生成を繰り返すことにより，目的関数の評価値の良い領域付近においてドロネー三角形が多数生成されることになり，より多くの子個体を集中して生成することが可能となる．

5  まとめ

本報告では，目的関数のランドスケープを考慮した子個体の生成を行うために，シンプレックス交叉を拡張し，ドロネー三角形分割を用いて子個体を生成する手法を提案した． 今後の課題として，シンプレックス交叉の拡張率などの重要なパラメータを検討する必要がある．

Reference

[1]
樋口隆英，筒井茂義，山村雅幸: 実数値GAにおけるシンプレックス交叉の提案 , 人工知能学会誌 , Vol.16 , No.1 , pp146-155 , 200
[2]
小野功, 佐藤浩, 小林重信.: 単峰性正規分布交叉UNDXを用いた実数値GAによる関数最適化. 人工知能学会誌, Vol. 14, No. 6, pp. 1146-1155, 1999.
[3]
喜多一, 小野功, 小林重信: 実数値GAのための正規分布交叉の多数の親を用いた拡張法の提案, 計算自動制御学会論文集 , pp875-883 , 2002
[4]
山村雅幸: モンテカルロ法による遺伝的オペレータの機能解析, SICE 自律分散システム・シンポジウム , pp115-120 , 1998

Copyright 

Copyright (C) 2005 Tomoyuki Hiroyasu, All rights reserved.
Copyright (C) 2005 Mitsunori Miki, All rights reserved.
Copyright (C) 2005 Hisashi Shimosaka, All rights reserved.

No part of this document may be reproduced, copied, distributed,
transferred, modified, or transmitted, in any form or by any means,
without the prior written permission of the authors.
In no event shall the authors be liable for any damages caused in any way
out of the use of this document．

Back to Top