【文献調査】実数値遺伝的アルゴリズムとは

平井　聡，廣安知之，三木光範

ISDL Report No. 20050706007

2005年 7月 5日

Abstract

本報告では，実数値遺伝的アルゴリズム（Real-coded Genetic Algorithms: RCGA)の概要について報告を行う． RCGAは，ビットストリング型ではなく，特有の遺伝的オペレータを適用する必要がある．そのため，本報告では，突然変異，交叉といったRCGA特有の操作も報告を行う．

1 はじめに

本報告は，実数値遺伝的アルゴリズム（Real-coded Genetic Algorithms: RCGA)の概要について報告を行う． RCGAは，探索に用いる個体を従来のGAのようなビットストリングでなく，実数ベクトルを用いて表現を行う．それにより，RCGA特有の遺伝的オペレータを用いなければならない．本報告では，RCGAに用いる遺伝的オペレータの説明を行う．

2 実数値遺伝的アルゴリズムの概要

実数値遺伝的アルゴリズム（Real-coded Genetic Algorithms: RCGA)は，探索に用いる個体を従来のGAのようなビットストリングでなく，実数ベクトルを用いて表現する．設計変数値が実数値である連続関数最適化問題の場合，RCGAは親個体の形質を効率よく引き継ぐことができる点で，ビットストリングGAと比較して，効率的な解探索が可能である．また実数値を直接探索に用いるため，ビットストリングのために設計された遺伝的オペレータを用いることはできない．そのため実数値GAのために設計された遺伝的オペレータを用いる必要がある．

RCGAの概要を以下のFig 2.1に示す．

Fig 2.1 RCGAの概要[出展:参考文献1]

3 RCGAにおける突然変異操作

実数値GAにおいて突然変異は以下のような手法がある．

3.1 一様突然変異（Uniform mutation）

設計変数ごとに，実行可能領域内に一様乱数により，新しい実数値を発生させる．一様突然変異の概要を以下のFig 3.1に示す．

Fig 3.1 一様突然変異の概要[出展:自作]

3.2 境界突然変異（Boundary mutation）

一様乱数とほぼ同様ではあるが，新しい値は実行可能領域の境界上にとる．つまり，設計変数値の取りうる値が 0から10であった場合，境界突然変異後の設計変数値の値は0か10のいずれかである．

実数値GAでは，境界上の個体を発生さる確率が低いため，境界上に個体を発生させる突然変異操作が必要となる．

境界突然変異の概要を以下のFig 3.2に示す．

Fig 3.2 境界突然変異の概要[出展:自作]

4 RCGAにおける交叉操作

4.1 ブレンド交叉(BLX-α)

ブレンド交叉(Blend Crossover: BLX-α)はEshelemanによって考案された交叉法であり，親個体の実数ベクトルの各変数の区間di を両側にαdi だけ拡張した区間から一様乱数に従ってランダムに子個体を生成する．すなわち，親個体の周辺の各辺が軸に平行な超直方体の領域が子個体の生成領域となる．Fig. 4.1に2次元におけるBLX-αによる子個体生成の例を示す．

Fig 4.1 BLX-αの概要(2次元)[出展:参考文献1]

BLX-αでは親個体が状態空間で離れて存在している場合には子個体も広い範囲に生成され，親個体が互いに近くに存在している場合には親個体の近傍付近に生成される特徴がある．この特徴により，ビットストリングGAと比較して，探索の中盤から終盤における探索効率の向上すると報告されている．(参考文献2)

4.2 単峰性正規分布交叉(UNDX)

4.2.1 UNDX

単峰性正規分布交叉（Unimodal Normal Distribution Crossover : UNDX）は小野らによって考案された交叉法であり， Fig 4.2に示すように，3 つの親個体によって決定される正規乱数を用いて2つの子個体を生成する．基本的には子個体は2 つの親個体を結ぶ軸の周辺に正規分布により生成され，第3 番目の親個体は正規分布の標準偏差を決定するために補助的に用いられる．正規分布の標準偏差は，その主軸成分，すなわち2 つの親個体間の距離に比例させ，それ以外の軸の成分は，第3 の親個体と主軸との距離に比例させる．ここで，主軸以外の標準偏差に1/√n .1 (n : Dimensions) をかけることで，次元が増加しても親個体から極端に離れた子個体を生成する可能性は減少する．

Fig 4.2 UNDXの概要[出展:参考文献5]

UNDXは，親個体が状態空間上において離れて存在している場合には子個体は広い範囲で生成される．また親個体が近くに存在している場合には子個体を親個体の近傍に生成する．親個体を結ぶ軸の周辺に正規分布にしたがって子個体を生成することから，親個体を結ぶ軸から遠く離れた子個体を生成する可能性は少ない．したがって，設計変数間に依存関係のある問題に対して効率的に探索を行う能力を持っていると考えられる．

4.2.2 UNDX-m

UNDXに多数(m+2)個の親個体を用いるように拡張(UNDX-m)する．m=1の場合が従来のUNDXに相当する． UNDXでは基本的には2つの親個体を結ぶ直線の近傍に子個体を生成する．そのため，探索空間上を網目状に覆った形でしか子個体が生成されない．これに対して，Fig 4.3のように， xA，xB，xCをすべて用いて主探索成分をより高次元空間上で生成すれば，探索空間をより蜜に覆うことが可能になる．これがUNDX-mのコンセプトである．

Fig 4.3 UNDX-mの概要[出展:参考文献6]

4.3 シンプレックス交叉(SPX)

シンプレックス交叉(Simplex Crossover: SPX)は，母集団から複数の個体を抽出し，抽出した個体の分布から一応乱数を発生させ新しい個体を生成する交叉である． SPXのアルゴリズムは以下のようになる．

個体群から(n+1)個の親個体[(P₀)],ｼ,[(P_n)]をランダムに選ぶ．
親個体の重心[G]を求める．

(2)
上記の式よりから，[(x_k)]，[(C_k)]をk=0,ｼ,nについて求める．eは正のパラメータで拡張率(Expansion Rate)とよぶ．r_kは区間[0,1]の一様分布乱数u(0,1)を次式で変換して得られる乱数である．

(3)

子個体Cを

(4)

によって得る．

また，Fig 4.4 にSPXによる子個体生成範囲を示す．

Fig 4.4 SPXの概要[出展:参考文献3]

4.4 Parent Centric Recombination(PCX)

UNDXでは，複数の親個体に正規乱数を用いて子個体を発生させていた．しかし，Parent Centric Recombination(PCX)では，親個体の周辺のみを発生させる交叉手法である．

Fig 4.5 個個体の発生状況(左：UNDX，右：PCX)[出展:参考文献7]

PCXでは，まず母集団内から任意のm個の個体数を選択する．その個体数の重心をgベクトルとする．次世代の個体は下記の式で求めることができる．

(5)

x_pは，母集団内から選択された同一の確率で選択された親個体であり，dはその選択された親個体と重心の距離ベクトルである．Dは距離ベクトルdと親個体の垂直ベクトルの平均である．直交する部分空間（副探索空間と呼ぶ）の正規直交基底とする． wは異なる正規乱数とである．

4.5 外挿的交叉(EDX)

従来の交叉は集団内部への探索バイアスが強いため，誤った領域に一度収束した場合，集団を適切な領域に移動させる能力が乏しい．これを補うためには外挿的な領域での探索を考慮する必要がある．外挿的交叉(Extrapolation-Directed Crossover: EDX)とは，UNDX-mやSPX等の交叉と併用するための，外挿的な探索領域を持つ新しい探索オペレータである．交叉による内挿的な探索とEDXによる外挿的な探索を分担するGAを設計する．

3つの親ベクトルx₁，x₂, x₃から，子ベクトルx_cをサンプリングする．ただし，f(x₁) > f(x₂)とする．fは適合度関数とする．また，x₁, x₂を主親，x₃を副親と呼ぶ．EDXは子個体を以下の式に従いサンプリングする．

(6)

ただし，nは問題の次元数，Dはx₁とx₂を結ぶ直線とx₃の距離，e_iはx₁ - x₂に直交する部分空間の任意の正規直交基底ベクトル，v_iは平均0，分散s²_hの正規分布からランダムサンプルされたベクトルである．s_hは喜多らによって推奨に従い[0.35/(ﾖn)]を採用する．EDXによる子個体の生成をx_c ← EDX(x₁, x₂, x₃)と書く．EDXのアルゴリズムを以下に示す．また，Fig:3 にEDXによる子個体生成の概念図を示す．

Step 1: x₁, x₂, x₃を入力

Step 2: x_c ← EDX(x₁, x₂, x₃)とする．もしf(x_c) > f(x₁)ならばx₁ ← x_cとする．

Step 3: 適用回数がn_EDXに達すればx₁を出力して終了．そうでなければStep 2へ．

Fig 4.6 EDXの概要[出展:参考文献4]

従来の交叉と，EDXを併用するGAの世代交代モデルを設計する．世代交代モデルは佐藤らMGGに基づいている．UNDX-mとEDXを併用した場合のアルゴリズムを以下に示す．

Step 1: 初期化領域中に一様ランダムなベクトルを生成し，初期集団とする．

Step 2: 集団からランダムに2つの主親個体と1つの副親個体を選択する．

Step 3: 確率p_EDXでEDXをn_EDX回適用しStep5へ．そうでなければUNDX-mをn_UNDX-m回適用しStep4へ．

Step 4: 生成個体に親個体を加えた家族から，最良個体を1つ，ルーレット選択により1つ選択し，それぞれ主親個体と交代する．

Step 5: 上記のStep2-5を終了条件が満たされるまで繰り返す．

4.6 各交叉手法の比較

各交叉手法をまとめた表をTable 4.1に示す．

Table 4.1: 交叉オペレータの比較

	形質遺伝性	変数間依存性	座標軸方向への依存性	スケールへの依存性	統計量の遺伝	子個体の分布
バイナリ	×	×	？	？	×	？
BLX-a	○	×	×	○	△	一様
UNDX	○	○	○	×	○	正規分布
UNDX-m	○	○	○	△	○	正規分布
SPX	○	○	○	○	○	一様
PCX	○	○	○	？	○	正規乱数

5 まとめ

本報告では，実数値遺伝的アルゴリズム（Real-coded Genetic Algorithms: RCGA)の概要について報告を行った．． RCGAは，特有の遺伝的オペレータを適用する必要があるため，本報告では，突然変異，交叉といったRCGA特有の操作も報告を行った．

Reference

[1]

福永隆宏
実数値遺伝的アルゴリズムにおける計算モデルの検討
同志社大学工学部知識工学科卒業論文 2002年3月 http://mikilab.doshisha.ac.jp/dia/research/pdga/pages/papers/fukunaga-grad.pdf

[2]

L.J Eshleman and J.D Scha.er.
Real-Coded Genetic Algorithms and Interval-Schemata.
Foundations of Genetic Algorithms, Vol. 2, pp. 187�202, 1993.

[3]

樋口隆英，筒井茂義，山村雅幸
実数値GAにおけるシンプレックス交叉の提案
人工知能学会誌 , Vol.16 , No.1 , pp146-155 , 2001

[4]

佐久間淳，小林重信
Proposal of Extrapolation-Directed Crossover for Real-coded GA and its Evaluation
実数値GAのための外挿的交叉EDXの提案と評価
自立分散シンポジウム pp251-256 2001年

[5]

小野，佐藤，小林
単峰性正規分布交叉UNDXを用いた実数値GAによる関数最適化
人工知能学会誌 , Vol.14 , pp1146-1155 , 1999

[6]

喜多，小野，小林
実数値GAのための正規分布交叉の多数の親を用いた拡張法の提案
計測自動制御学会論文集，Vol.36 , No.10 , pp875-pp883 , 2000

[7]

Kalyanmoy Deb, Dhiraj Joshi and Ashish Anand
http://www.iitk.ac.in/kangal/papers/tech_rep2001003.pdf

[8]

福永隆宏, 廣安知之, 三木光範
http://mikilab.doshisha.ac.jp/dia/research/person/takapy/report/report.html

Copyright

Copyright (C) 2005 Tomoyuki Hiroyasu, All rights reserved.
Copyright (C) 2005 Mitsunori Miki, All rights reserved.
Copyright (C) 2005 Satoshi Hirai, 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．