個体データベースと簡易評価を利用した遺伝的アルゴリズム
廣 安 知 之 †† 三 木 光 範 ††
片 浦 哲 平 † 谷 村 勇 輔 †
遺伝的アルゴリズムは，生物の進化を模倣した確率的な最適化手法であり，複雑かつ大規模な問題 を解くための手法として高く注目されている．遺伝的アルゴリズムは，大域的に効率よく探索を行え るが，多くの反復計算を必要とする．そのため，解析計算に時間を要する問題では，膨大な計算時間 が必要となる．
本研究では，膨大な反復計算の問題を解決するためにデータベースに解析計算の結果を格納し，結 果を再利用し簡易評価を行うことで計算時間の短縮と効率的な探索を図る手法を提案する．そして，
提案する手法を実装したシステムを構築し，数値計算例を通じてその有効性を検討している．
Genetic Algorithm using a Population Database and Simple Evaluation Tomoyuki Hiroyasu,
††Mitsunori Miki,
††Teppei Kataura
†and Yusuke Tanimura
†Genetic Algorithm is an optimization method, which imitates a mechanism of evolution.
It performs a probabilistic search to solve the complex problems efficiently. However, it is required high calculation cost and it takes long time to find an optimum.
In this paper, a new method of GA is proposed. It has the database to store results of the computational analysis and the function of temporary evaluation to show the approximate f(x). The proposed model performs effective search and find an optimum in short time. This method is evaluated by constructing the system and some experiments.
1. は じ め に
近年の最適化問題は要求される問題が複雑化，大規 模化しており，かつ目的関数の計算コストも格段に大 きくなっている．このような状況において，同じ解析 計算を繰り返し実行することは無駄である．そのため １度行った解析計算を保存し，それを有効に利用して，
より少ない計算回数で解探索を行うことが重要になっ てくる．
本論文では，解析計算を格納するデータベースと保 存された結果から別の解析計算を類推する近似手法を 用いた遺伝的アルゴリズムを提案する．提案手法では，
データベースに結果が保存されている解析計算は行わ ないため，その分の計算コストを削減できる．また，
近似手法により，最終的な解析計算の量を削減するこ とができる．本論文では数値実験を通じて，提案手法 の有効性について検討を行う．
†同志社大学大学院工学研究科
Graduate School of Engineering, Doshisha University
††同志社大学工学部
Department of Engineering, Doshisha University
2. データベースと簡易評価を用いた遺伝的ア ルゴリズム
2.1 提案する遺伝的アルゴリズム
最適化計算は，一般に解析計算を反復して行う必要 がある．特に GA などのヒューリスティックな最適化 手法では解析計算の繰り返しを多く必要とする．そし て，現実の問題において解析計算は GA の処理と比較 して多くの時間を要する．提案する GA は，評価計算 の結果をデータベースに保存し，何度も結果を利用で きるモデルである．提案する GA の流れを図 ?? に示 し，以下に説明する．
( 1 ) Initialize
GA の母集団を作成し個体の初期化を行う．
( 2 ) GA operator
各個体に対し遺伝的操作を適用する．
( 3 ) Search database
Database Server が染色体の検索を行う．染色 体は 0,1 の遺伝子で構成されており，検索は遺 伝子のマッチングにより行う．検索に成功した 場合には，評価計算を行わずに検索した染色体
1
GA operator
Terminal criterion
Initialize Start
Evaluation Insert database Approximation
Search databaseYes Yes No
No
End
図1 提案する
GA
の流れに対応した適合度を返す．失敗した場合には，
評価計算と簡易評価計算のための 2 つのプロセ スを同時に発生させる．
( 4 ) Evaluation
検索に失敗した染色体について評価を行う．
( 5 ) Insert Database
評価された染色体の適合度を対応する染色体と ともに格納する．この操作により同一の染色体 は今後，評価計算されることはない．
( 6 ) Approximation
簡易評価を行う．簡易評価は，検索に失敗した 染色体の適合度をデータベースに格納されてい る既存の染色体から近似によって適合度を求め る操作である．近似の詳細については後述する．
( 7 ) Terminal criterion
遺伝的操作の終了判定を行う．
2.2 データベース
データベースには，図 ?? に示すように個体の染色体 の情報とそれに対応した個体の適合度が格納されてい る．染色体は 0,1 の遺伝子で構成されており，検索は 遺伝子のマッチングにより行う．データベースに検索 対象となる染色体が存在した場合には，その染色体の 適合度を返す．失敗した場合には，検索対象となる染 色体の評価計算を行う．同時に，データベースに格納 されている染色体から一時的に検索対象となる染色体 の適合度を簡易評価して返す．データベースの利用は，
一度計算された個体の重複計算を省くことで計算時間 の短縮を図るためである．
2.3 簡 易 評 価
簡易評価は，データベースの検索に失敗した場合 に，検索対象となる染色体に近い染色体から近似を行 うことで何らかの適合度を返す操作である．これは，
Chromosome Fitness value
図2 データベースの内容
0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 Target gene
Approximation candidate 1 Approximation candidate 2
First search level
Second search level
図3 近似染色体の決定最適化計算の継続を目的とする．提案手法は，評価計 算，最適化計算などの処理を分散することが可能であ り， Grid やクラスタなどの並列計算環境を利用でき る．評価計算が分散された場合，評価計算の膨大な問 題では，関数の評価に多くの時間を要するため，それ 以外の処理に待ち時間が存在する．しかし，評価計算 を行っている間に，目的関数値の近似値を返し最適化 計算の操作を継続させることで有効な解探索を行うこ とができる．
2.4 提案する遺伝的アルゴリズムにおける簡易評 価方法
遺伝的アルゴリズムにおける簡易評価の方法を以下 に示す．
( 1 ) 「検索対象の染色体」の検索が失敗した場合，
検索に失敗した同位の逆遺伝子から検索を開始 する．
( 2 ) 同位の遺伝子の検索に失敗した場合には， 1 つ
上位の遺伝子を「検索対象の染色体」とハミン グ距離の等しい構成になるものから検索する．
( 3 ) 検索に成功した場合は，その染色体の適合度を
「近似染色体 1 」の適合度とする．
図 ?? に示すように「検索対象の染色体」が「 00001 」の 場合には，第 1 候補が「 00000 」，第 2 候補が「 00010 」 となる． 「近似染色体 2 」も「近似染色体 1 」と同様に 決定する． 2 つの染色体が選択されると，次に近似を 行う．近似は 2 つの染色体をもとに，以下の式にした がって行う．
Approx fitness = F
1× H
2H
1+ H
2+ F
2× H
1H
1+ H
2F
1… 「近似染色体 1 」の適合度 F
2… 「近似染色体 2 」の適合度
H
1… 「近似染色体 1 」とのハミング距離
2
Database
Client Side
Database Server Analysis Server
Server Side (Grid Environment) Approximation Server
Control Server Client
図4 提案する
GA
を実装するシステムH
2… 「近似染色体 2 」とのハミング距離
近似適合度は， 2 つの染色体の適合度のハミング距 離によって求められる．したがって，近似式は「検索 対象の染色体」とハミング距離が近い染色体が見つか るほどその適合度が反映される．
2.5 提案手法の利点
提案手法の利点を以下に述べる．
• データベースを利用することで個体の重複計算を 省くことができる．
• 簡易評価を行うことで計算時間の短縮を図ること ができる．
• GA は複数回の試行を行うことが一般的であるが，
その場合に，データベースを利用することで情報 が蓄積されていくので，試行ごとに処理時間を短 縮することができる．
• 評価計算，最適化計算など各コンポーネントが独 立に存在するため並列分散処理することができる．
3. 提案する遺伝的アルゴリズムを実装するシ ステム
提案する GA を実装するシステムを，図 ?? に示 す．提案するシステムは，解析計算結果を格納する Database Server ，簡易計算を行う Approximation Server ，解析計算を行う Analysis Server ，そして，そ れらをコントロールするための Control Server から 構成される．これらは別々のサーバとして用意するこ とができるため，並列負荷分散が可能となり計算時間 の短縮につながる．
4. 数 値 実 験 4.1 対 象 問 題
?? 節で説明した提案手法の利点のうち，複数試行で
表1 実験環境
CPU Pentium 3 1GHz x 20
Memory 512 MB x 20
Network Fast Ethernet
OS Kondara MNU Linux 2.0 Kernel 2.4.6
の計算時間の短縮，簡易評価の有効性を確認するため に数値実験を行った．対象問題には OneMax 問題を 用いた．
One Max 問題とは，遺伝子の 1 の合計数がそのま
ま適合度となる問題である．例えば，遺伝子長が 100 の問題では，遺伝子配列はすべて 1 となっている状態 が最適値であり，その場合の適合度は 100 となる．
4.2 実 験 内 容
本論文では以下の実験を行った．
( 1 ) データベースの効果を確認する実験 ( 実験 1) 複数試行した場合に各試行ごとに実行時間がど のように短縮されるかを調査した．
( 2 ) 簡易評価の効果を確認する実験 ( 実験 2) 簡易評価の効果を確認するために，データベー スで個体の検索のみを行い検索に失敗した場合 には，簡易評価を行わずに評価値を得るまで待 つシステムを構築した．提案手法のシステムと 解が求まるまでの実行時間の比較を行った．
実験 1 は，個体の遺伝子長に対するスケーラビリ ティを調査している．これにより，探索空間が広がる ので，複数試行した場合，全体的な検索成功率は下が ると予想されるので，時間の短縮に影響が出ると思わ れる．
実験 2 は問題負荷を変え 1 評価あたりの計算時間 を調整することで，様々なサイズの問題を想定してい る．問題負荷とは， 1 評価あたりの計算時間の指標で あり，問題負荷の最も低い問題を 1 とした場合に， 1 評価に何倍の計算時間を要するかを示している．
なお，実験は PC クラスタで行い，通信には MPI を 利用した．実験環境を表 ?? に，実験に用いたパラメー タを表 ?? に示す．
4.3 複数試行での実行時間の短縮
複数試行する場合，データベースによって実行時間 が短縮されているかを表 ?? の実験 1 のパラメータを 用いて調べた．実行結果を図 ?? に示す．
図 ?? は各試行ごとの最終的な実行時間を示している．
どの条件による実行結果も全体的に右下がりになって いるため，複数試行時に実行時間が短縮されているこ とが分かる．例えば，遺伝子長 50 の場合の実行結果 は， 1 試行目に 20 秒近くかかっていたのが， 20 試行
3
表2 実験
1,2
のパラメータExperiment 1 Experiment 2
Population 50 50
Gene length 50, 100, 200 100
Crossover rate 1.0 1.0
Mutation rate 0.02, 0.01, 0.005 0.01
Elite poplulation 20 20
Ploblem load 1 1, 10
Trial 20 20
Terminal
criterion 1000 generation Discover opt.
0 5 10 15 20
0 10 20 30 40 50 60 70
Time [s]
Trials
Gene Length 50 Gene Length 100 Gene Length 200
図5 複数試行による実行時間
(実験 1)
目では 10 秒前後にまで短縮し，およそ半分の時間で 1 試行を終えている．しかし，遺伝子長が大きくなる ほど実行時間の短縮率が低くなり，さらに，各試行ご とに実行時間にばらつきがあることが分かる．
4.4 簡易評価の有無による解探索性能の違い 次に，簡易評価を行わずに評価計算によって適合度 が求められるまで遺伝的操作を待つ手法 ( 簡易評価を 行わない手法 ) とデータベースの検索に失敗した場合 に，簡易評価を行い，評価計算待ちの個体が発生した 場合に，最新の個体を優先的に評価する手法 ( 簡易評 価を行う手法 ) の 2 種類の手法で，最適解を得られる までに要した時間を求めた．表 ?? の実験 2 のパラメー タを用いて， 20 回試行の平均値での実行結果を図 ??
に示す．計算量は， 1 回の計算につき評価関数を複数 回繰り返すことで人為的に大きくした．本問題の場合，
問題負荷 1 は 1 回の計算につき 10 万回の評価を行い，
問題負荷 10 は 100 万回の評価を行っている．
図 ?? から，簡易評価を行わない手法と比較して簡易 評価を行う手法がよい性能を示した．問題負荷の大き な問題でその差が顕著であることから，大規模な問題 においてはより優れた手法であるといえる．
No Approximation Approximation 0
20 40 60 80 100
Time [s]
Problem Load 1 Problem Load 10
図6 簡易評価の有無よる実行時間
