Warning: copy(htaccessbak): failed to open stream: No such file or directory in /home/jtokkyo/public_html/header.php on line 10
遺伝的アルゴリズムの高速処理方法 - 特開平6−161980 | j-tokkyo
トップ :: G 物理学 :: G06 計算;計数




【発明の名称】 遺伝的アルゴリズムの高速処理方法
【発明者】 【氏名】江端 智一

【氏名】吉原 郁夫

【目的】 遺伝的アルゴリズムの高速な処理を行なう方法を提供する。
【構成】 遺伝的アルゴリズムで用いる遺伝子列を、その性質や情報を損なうことなく構成し、計算機アーキテクチャを利用し、計算機の資源を効率的に利用することにより、遺伝的アルゴリズムを高速に実行するものである。
【特許請求の範囲】
【請求項1】距離空間上で定義された評価関数の値を最小にする際に、定義域を記号ストリング集合に写像し、評価関数の値によって記号ストリングの個数を消滅させ、評価関数の値によって記号ストリングの個数を増加させ、複数の記号ストリングの中にある記号を部分的に交換し、記号ストリングの中にある、任意の1個あるいは複数の記号を変化させ、前述の手段を繰り返し行ない、最適な解を得る記号ストリングを探索する処理方法において、前述の写像が連続写像になるようにし、かつ、記号ストリングの長さを記号ストリングの構造が有する性質や情報を損なうことなく、計算機のビット数、レジスタ長、メモリ長、レジスタ数、メモリ数、演算器数などに適した形に変換して計算機の資源を効率的に利用することを特徴とする遺伝的アルゴリズムの高速処理方法。
【請求項2】請求項1の処理方法において、記号ストリングを中央制御装置上のレジスタ上にロードした後、前述した交叉及び突然変異の処理の間、記号ストリングをレジスタからメモリへ退避させず処理することを特徴とする遺伝的アルゴリズムの高速処理方法。
【請求項3】請求項1の記号ストリング集団の中の各々の記号ストリングの評価の処理方法に関して、評価値の良いものから順に並べて増殖、淘汰等の処理を行なうにあたり、実際の記号ストリングの並びかえを行なわずに順序のみを保持する手法として、記号ストリングのポインタアドレスを操作することで高速化を図ることを特徴とする遺伝的アルゴリズムの高速処理方法。
【請求項4】請求項1の処理方法において、請求項2の処理方法と請求項3の処理方法を併用して処理することを特徴とする遺伝的アルゴリズムの高速処理方法。
【発明の詳細な説明】【0001】
【産業上の利用分野】本発明は、遺伝的アルゴリズムを計算機で実行する方法に関する。
【0002】
【従来の技術】特開平2−236660は、拡張された種類の問題を解くための遺伝的アルゴリズムを提供するものであり、対象とする集団の大きさ、形、または複雑さに制約を加えることなく遺伝的アルゴリズムを行なう方法に関するものである。また、特開平3−10366では、修正された記号ストリングで表されるニューラルネットワークを学習し評価すると共に、記号ストリングの修正を繰り返し最適なニューラルネットワークを構成する方法に関するものである。
【0003】
【発明が解決しようとする課題】遺伝的アルゴリズムは確率的探索アルゴリズムであり、繰り返しの手続きを必要とするため時間がかかるが、前述の技術においては遺伝的アルゴリズムの処理に要する時間については特に言及されていない。
【0004】本発明は、遺伝的アルゴリズムを高速に処理をする手段を提供することを目的とするものである。
【0005】
【課題を解決するための手段】上記目的を達成するために、入力装置、出力装置、メモリ、CPU(中央制御装置)及びその他の周辺機器を有する計算機において、与えられた問題と計算機のアーキテクチャの両方に適する記号ストリングを生成して、それらの記号ストリングをポインタアドレスで操作する。また、その記号ストリングをレジスタ上に配置して、ビット演算を用いて遺伝子列の変換を行なう。
【0006】なお、遺伝的アルゴリズムの処理を説明するにあたって、上記の記号ストリングを遺伝子列と呼び、記号ストリングを構成する個々の記号を遺伝子と呼び、その遺伝子列の情報によって特徴が形成されるものを、個体と呼ぶことが一般的であり、以下本発明でもこれらの術語を用いることとする。
【0007】
【作用】本発明は、遺伝的アルゴリズムで用いる遺伝子列を、その性質や情報を損なうことなく構成し、計算機アーキテクチャを利用し、計算機の資源を効率的に利用することにより、遺伝的アルゴリズムを高速に実行するものである。
【0008】
【実施例】
(実施例1)本発明の一実施例を図1に示す。図1は、1入力1出力の非線形関数の最小値探索を遺伝的アルゴリズムで行なう場合の遺伝子列の構成を示す図である。
【0009】図2に本発明を実行するハードウェアの構成を示す。同図において中央制御装置CPU21は32ビット長のレジスタ群211を持ち、32ビット演算のためのシフト機能、ビット操作機能などの論理演算を行なう演算部212をもつ。また命令デコーダによって解読された結果に基づいて命令を実行させる制御部213を持つ。メモリ22に含まれるランダムアクセスメモリRAM221とCPU21とのデータ転送は、アドレスバス24によって32ビットのワードの境界ごとにアクセスされ、データバス23を経由してCPUあるいは、RAM自身とやりとりされる。また22に含まれるリードオンリーメモリROM222には、CPUが動作を開始すると真っ先に呼び出され初期設定動作を行なわせるプログラムが書き込まれている。IO27はデータの出入口であり、これを介して処理に用いるパラメータは入力装置25より入力され、処理の結果は出力装置26に出力される。なお、前述の32ビットは、本実施例で使用する計算機に合わせて設定されているが、特にこのビット数に限定されるものではない。
【0010】遺伝的アルゴリズムを用いて、与えられた関数の最小値を探索する手順を以下に述べる。
(1)複数の乱数を発生させて、各々を遺伝子列の形に表現し、遺伝子列の初期状態とする。
(2)これらの遺伝子列を交叉、突然変異に従って変化させる。なお、交叉とはある一対の個体に対しその個体の持つ遺伝子列の一部を互いに交換させる処理であり、突然変異とは遺伝子列の一部を変化させる処理である。
(3)変化した各々の遺伝子列を各々の数値に復元して、与えられた関数に入力する。そして各々の関数の値を得る。
(4)得られた各々の関数の値の全てを用いて全体の評価を行なう。その全体の評価に従って個々の関数の値を評価して、淘汰・増殖を行なう。なお、淘汰とは個体の評価が低い時に、その個体を消失させる処理であり、増殖とは個体の評価が高い時に、同じ遺伝子列を有する個体を発生させる処理である。
(5)与えられた終了条件を満たすまで(2)〜(4)の処理を繰り返す。
【0011】なお、上記の(2)〜(4)までの処理を世代、繰り返し回数を世代数と呼ぶ。このように世代を繰り返して、与えられた関数の最小値、あるいは最小に近い値を求めることができる。なお、具体的な詳細手順については後述する(図7)。なお、遺伝的アルゴリズムについては、以下の文献で詳しく説明されている。
Goldberg, D.E.: Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley (1989)図3には遺伝的アルゴリズムを用いて問題を解くための手続きの手順をPAD(Program Analysis Diagram)図で示す。下記の多峰性非線形関数の最小値を求める場合を例に本発明の処理方式を説明する。
【0012】
【数1】

【0013】ただし、定義域は0以上2未満(0≦x<2)である。そして、出力値の小さいものから優先順位をつけ、この順位をもって個体の評価とする。
【0014】31の遺伝子列の設定に関して、遺伝子列の設定数値から遺伝子列への変換手順を図5のPAD図を用いて、また遺伝子列から数値への変換手順を図6のPAD図を用いて各々説明する。図5及び図6に用いる記号の意味は次の通りである。
Gmax :全個体数di :i個めの入力値δi :diをη倍した値の整数部分Lmax :遺伝子列を構成する遺伝子の数Gene[i,k] :i個目の遺伝子列のk番目の遺伝子の値52において、i個目の入力値diをη倍し整数部分をδiとする。
【0015】なお、ηは定数であり、その値は変数をη倍した値が、0〜4294967295(2の32乗から1を引いた値)に含まれるように設定する。例えば、0≦x<2のとき、η=2147483648(2の31乗)である。54において、δiを2で割った余り、すなわち0か1の値を得て、55においてδiを2で割った商をδiとして更新する。これを53で遺伝子列の最大長まで繰り返すことで、バイナリ数列を得ることができる。このバイナリ列を遺伝子列とする。51において、各々の関数の入力値を各々遺伝子列に変換する。この手法では入力値の桁の大きい性質が遺伝子の左側(上位ビット)で表現され、入力値の桁の小さい性質になる程、右側(下位ビット)で表現されることになる。結果的にδiの2進数表現となっている。
【0016】例えば、η=2147483648(2の31乗)としたときには入力値d=0.571875では、δ=1228092211となり、遺伝子列は{01001001001100110011001100110011}
となる。
【0017】また、図6の63、64において遺伝子列の情報を数値に変換した後、65にてηで割って関数の入力値に戻す。61は上記の処理を全ての遺伝子列対しに施す制御を行なう。例えば、遺伝子列が{00101110000101110101110110111000}
の時、δ=739728568となり、入力値は、0.6889259となる。
【0018】次に、遺伝子列の構成方法について図1を用いて説明する。本実施例においては、遺伝子列をバイナリ列で表現するので、i番目の遺伝子列GENE[i,k](k=1,2,..,Lmax、ただしLmaxは遺伝子列を構成する遺伝子の個数)のように遺伝子列を構成する個々の遺伝子を図1の様に配置した時、メモリ上では最下位ビット以外の情報は不要となる。そこで、遺伝子列を配列では定義せず、最下位ビットだけを1ワードに集め1個の整数型の変数として使用する。 例えば、{00101101000101110101110110111000}
なる32個のバイナリ値の遺伝子から構成される遺伝子列は739728568という10進数一つで表すことが可能となる。
【0019】図3のパラメータの設定32では、任意の個体数と、それに対する交叉率、淘汰増殖率、突然変異率を設定する。これらは0〜100[%]の範囲にある値である。また繰り返しを打ち切る回数を適当に設定する。本実施例においては、個体数100、遺伝子長32、交叉率80%、淘汰増殖率10%、突然変異率5%、打ち切り世代数を200世代としたが、特にこの値に限定されるものではない。
【0020】下記の文献に上記のパラメータ値に関して詳しく記載されている。
Goldberg, D.E.: Genetic Algorithms in Search, Optimization and MachineLearning, pp.70-74,Addison-Wesley (1989)本実施例の、遺伝的アルゴリズムの処理手順をPAD図で示す。集団の発生71で、0から4294967295(2の32乗から1を引いた値)までの整数値の乱数を、個体数と同じ100個発生させメモリ上に配置する。これらの乱数が、各々の遺伝子列の初期状態となる。なお、処理の高速化を図るために、個々の遺伝子列が格納されている先頭アドレスを格納するアドレステーブルを用意して、遺伝子列の実体は動かさずポインタアドレスを移動させる。また、集団の発生71以降の手順で使用する乱数は、1〜個体数(100)までと、1〜遺伝子長(32)までの整数値の並びを無作為に入れ換えたものを使用するので、1世代ごとに無作為な整数値の並びを生成して、それを各処理で使用するものとする。
【0021】72は打ち切り判定で、200世代繰り返して処理を終了する。各個体の評価73では、各々の整数値で表される遺伝子列を前述の図4の手順を用いて与えられた関数の入力値に変換し、各々の遺伝子列から関数の出力値を得る。全個体の中で、その出力値が小さいものから順にソートし、この順位を個体の評価値とする。ただし、遺伝子列の実体はメモリ上では移動させず、遺伝子列のポインタアドレスを操作して、遺伝子列を昇順に指し示すようにする。
【0022】全体の評価74では、各解の評価73で行なった個々の解の評価の平均値が、適当なしきい値より小さくなったか否か判定する。小さいと判定した時は満足な解が得られたものとして結果を表示して処理を停止する。淘汰及び増殖75は、各個体の評価73で得られた評価に従って、昇順に並べ直した個体の中から、評価の低い遺伝子列を評価の高い遺伝子列に置き換える。これによって評価の高い個体が増えて、評価の低い個体が消されることになる。本実施例では、100個の解の淘汰増殖率10%にあたる、上位10個体の遺伝子列で、下位10個体の遺伝子列を置き換える。
【0023】交叉76の処理を図8、及び図9を用いて説明する。最初に、100個の中から80%にあたる80個の遺伝子列を、2つずつ40組重複なく選び出す。ただし、本実施例においては、重複して選ばないことにしているが、重複を許す方法であっても構わない。本実施例では、重複を避ける方法としてとして、1から個体数100までの数字の乱数順列を作成して配列に格納し、その順番に従って遺伝子列を抽出する。次に、遺伝子列データ81に配置されている遺伝子列の集団の中から、前述した乱数順列を用いて抽出されたポインタアドレス82が指し示す2個の遺伝子列Gene[i],Gene[j]を、各々レジスタ群83のレジスタx、レジスタyに格納する。
【0024】次に、乱数を用いて無作為に遺伝子列の交叉ビットkを決定する。交叉ビットkからLSB(最下位ビット)をマスクする整数型の変数である全てのマスクパターン84をあらかじめメモリ上に配置して、kビットからLSBまでマクスするマスクパターンmask[k]をレジスタ群83のレジスタzにロードする。図9にレジスタに配置した遺伝子列の交叉手順を示す。
(Step 1)Gene[i],Gene[j]とmask[k]を各々レジスタx,y,zに格納する。
(Step 2)レジスタxとレジスタz,レジスタyとレジスタzのビット論理積の結果を、各々レジスタa、及びレジスタbに格納する。
【0025】(Step 3)レジスタzをビット反転させる。
(Step 4)レジスタxとレジスタz,レジスタyとレジスタzのビット論理積の結果を、各々レジスタx、及びレジスタyに格納する。
(Step 5)レジスタxとレジスタb、及びレジスタyとレジスタaでビット論理和を行ない、それぞれをGene[i]とGene[j]のあった元のアドレスのメモリ上に返す。
【0026】こうして、kビットからLSBまでの遺伝子列の交叉が完了する。このようにして交叉の終了した遺伝子列は元のメモリ上に戻され、40組すなわち80個の遺伝子列の処理が全て終了するまで、整数値の並びを無作為に入れ換えたリストに従って、1対の遺伝子列を順次抽出して、上記の手続きを繰り返す。
【0027】突然変異77の処理を、図10及び図11を用いて説明する。最初に、図10に示すように、100個の遺伝子の中から5%にあたる5個の遺伝子列を選び出す。この重複を避ける方法としてとして、前述した乱数順列を用いる。整数値の並びを無作為に入れ換えたリストを用いて、選び出されたポインタアドレス群102の中の一つが指し示す1個の遺伝子列Gene[i]を、各々レジスタ群103のレジスタxに格納する。次に乱数を用いて無作為に遺伝子列の突然変異開始ビットk1、及び突然変異終了ビットk2を決定する。
【0028】図11で突然変異の手順について説明する。
(Step 1)突然変異を施す遺伝子列Gene[i]をレジスタxに、マスクパターンmask[k1],からmask[k2]をそれぞれレジスタy,zにロードする。
(Step 2)レジスタyとレジスタzのビット排他的論理和計算を行ない、その結果をレジスタyに格納する。
(Step 3)レジスタxとレジスタyのビット排他的論理和計算を行ない、その結果をレジスタxに格納後、その結果をGene[i]のあった元のアドレスのメモリ上に返す。
【0029】このように、レジスタx上のk1ビットからk2ビットまでのビット値を全て反転した後、再び元のアドレスのメモリ上に戻す操作を行う。こうして、k1ビットからk2ビットまでの遺伝子列の突然変異が完了する。
【0030】このようにして突然変異の終了した遺伝子列は元のメモリ上に戻され、5個の遺伝子列の処理が全て終了するまで、次の遺伝子列が乱数順列に従って抽出され上記の手続きを繰り返す。本方式と、従来法との処理速度の比較を行った結果を表1に示す。
【0031】従来法は、以下の点において本手法と異なっている。
・遺伝子列構成 整数型一次元配列の記号ストリング・遺伝子列移動方法 ポインタアドレスを使用しない。
なお、速度はクロックサイクル数で比較する。
【0032】
【表1】

【0033】ただし、遺伝子発生処理の比較の項目では、従来法では加算、乗算、及び除算を用いた乱数を使用するが、本手法では整数値の並びを無作為に入れ換えたリストを使用した結果を示している。また、それ以降の処理の比較の項目に関しては、従来法、提案法とも、この方法を用いている。
【0034】(実施例2)この発明を2入力1出力の非線形関数の最大値探索に適用した実施例について詳述する。遺伝的アルゴリズムを実行する計算機のハードウェアの構成は(実施例1)の図2に同じであり、問題解法の手順は(実施例1)の図3に同じである。
【0035】与えられた問題は下記の多峰性非線形関数である。
【0036】
【数2】

【0037】ただし、2つの入力値の定義域は共に0以上1未満(0≦x<1,0≦y<1)である。また、出力値の値域が0以上1未満(0≦z<1)であることが分かっているものとする。
【0038】上記の関数の出力値を以下の評価関数で評価する。
【0039】
【数3】

【0040】ただし、yiはi番目の非線形関数の出力値,ziはその出力値の評価関数の値である。
【0041】遺伝子列の設定31については、2つの入力値を2つの遺伝子で表現すること以外では(実施例1)と同じである。パラメータの設定32では、任意の個体数と、それに対する交叉率、突然変異率を設定する。これらは0〜100[%]の任意の値であり、また繰り返しを打ち切る回数を適当に設定する。本実施例においては、個体数500、遺伝子長32、交叉率80%、突然変異率5%、打ち切り世代数を200世代としたが、特にこの値に限定されるものではない。
【0042】また、淘汰増殖に関しては以下の式を用いて、その個数を決定する。
【0043】
【数4】

【0044】
【数5】

【0045】ただし、ziは、(数3)で算出したi番目の出力値の評価値、Gmaxは、個体数、ciは次の世代に、i番目の遺伝子列が生き残る個数である。また(数5)のinteger(x)は、xよりも大きくない最大の整数を算出する関数である。
【0046】遺伝的アルゴリズムの実行手順は(実施例1)図7のPAD図と同じである。集団の発生71で整数値の乱数を、個体1つに対して2つ、すなわち200個発生させる。以下は(実施例1)と同様の処理を行なう。打ち切り判定72では、200世代を繰り返して処理を終了する。各個体の評価73、全体の評価74、淘汰及び増殖75は(実施例1)と同様の処理を行なう交叉76の方法について以下に具体的に説明する。遺伝子列データに配置されている遺伝子列の集団の中から、乱数順列を用いて抽出されたポインタアドレスが指し示す2組4個の整数型の変数である遺伝子列Gene1[i]、Gene2[i]、Gene1[j]、Gene2[j]を、各々レジスタ群のレジスタx1、x2、y1、y2に格納する。無作為に選ばれた遺伝子列のマスクパターンmask[k1]を用いて、Gene1[i]、Gene1[j]の交叉を行なう。同様にマスクパターンmask[k2]を用いて、Gene2[i]、Gene2[j]の交叉を行なう。交叉方法の手順は(実施例1)図9で示したときと同様の方法で行なう。
【0047】突然変異77を施す方法について具体的に説明する。遺伝子列データに配置されている遺伝子列の集団の中から、乱数順列を用いて選び出されたポインタアドレス群の中の一つが指し示す2個の整数型の変数である遺伝子列の組のどちらかを、各々レジスタ群のレジスタに格納する。次に、無作為に遺伝子列の突然変異開始ビットk1、及び突然変異終了ビットk2を決定する。突然変異の手順は(実施例1)図11で示した時と同様な方法で行なう。図12に本実施例における、解の探索経過を示す。
【0048】(実施例3)この発明を巡回セースルマン問題(Traveling SalesmanProblem、以下単に「TSP」と略す)に適用した実施例について詳述する。通常TSPを遺伝的アルゴリズムで解く場合、単に都市の並びを遺伝子列として表現すると、交叉や突然変異を行なう時に巡回する都市を重複してしまう個体が大量に発生して、集団が死滅してしまう。この重複問題を解決する手法としてGrefenstetteらによって考えられた手法がある。その概要を以下に述べる(参考文献は後述)。
【0049】都市名をA,B,C,D,・・として、巡回する都市の順に都市名を並べたリストを作る。都市名Aがこの標準リストのなかで、左から何番目にあるかを数えて、その数字を記録する。そして標準リストからAを取り除く。次は都市名Bで同様の処理を施して、出てきた数字を先ほど記録した数字の右隣に記録する。同じ様にC,D,・・のように続けて行き、都市名が無くなるまで続けると、巡回路を数字のリストが出来上がる。
【0050】この様にして表現された5つの都市の巡回ルートの遺伝子列と、その遺伝子列による交叉の仕組みを示す。交叉3桁目を交叉した場合の例を示す。
交叉前BCAED→22121→22+(121)
DAECB→41321→41+(321)
交叉後22+(321)→22321→BCEDA41+(121)→41121→DABEC上記の方法によって変換された遺伝子列は、最上位の桁には1〜5の数字が入り最下位の桁には1しか入らないことがわかる。なお、この手法に関しては以下の文献に詳しく記載されている。
Grefenstette,J.J.et al.:"Genetic algorithms for the traveling salesman problem ", Proc. of an International Conference on Genetic Algorithms and Their Applications, pp. 160-168(1985)このGrefenstetteの手法による遺伝子列の作成方法について図13を用いて説明する。この遺伝子列のk桁目には1〜kの数字がはいることになり、k桁目の値を表現するのには、たかだかlog(k)/log(2)の小数部を切り上げた整数値分だけのビット列があれば表現できる。また最下位桁の数字は必ず1となるので表現する必要はない。このようにして巡回都市の情報を圧縮して1ワードの情報として扱う。
【0051】図14に遺伝子列の交叉方法を示す。交叉ついては、(実施例1)の図8、交叉76と同じ手順で行なうが、図15に示すように、マスクパターンを各々の都市の情報を損なわないようして遺伝子列の区切りが定位置に来るよう作成する。
【0052】突然変異については、(実施例1)の図8、突然変異77と同じ手順で行なう。この手順を図16を用いて詳しく説明する。遺伝子列のk桁目に突然変異を施す場合に即して説明する。
(Step 1)遺伝子列群からGene[i]をレジスタxに、マスクパターン群からmask[k−1]とmask[k]を、レジスタy、レジスタzに,ロードする。
(Step 2)レジスタyとレジスタzのビット論理積計算を行ない、その結果をレジスタyに格納する。
(Step 3)レジスタxとレジスタyのビット排他的論理和計算を行ない、さらにビット否定計算を行なって、その結果をレジスタxに格納する。
(Step 4)突然変異パターン群の中から、k桁目に対応するパターンを一つ無作為に選び、レジスタyにロードする。
(Step 5)レジスタxとレジスタyのビット論理和計算を行ない、その結果をレジスタxに格納した後、Gene[i]にこの結果を返す。
【0053】遺伝子列のk桁目には1〜kまでの数字しか入力できないので、突然変異パターン群のビットパターンは、それに対応する全てのものをあらかじめ作成しておく。本実施例においては、巡回都市数11なので、2から11までの総和、65パターンが必要となる。
【0054】
【発明の効果】本発明は、遺伝的アルゴリズムで用いる遺伝子列を、その性質や情報を損なうことなく、かつ計算機アーキテクチャに適するように作成する。これによってメモリが節約される。またメモリ・レジスタ間のロードやストアの頻度を少なくすることが可能である。その結果、遺伝的アルゴリズムの高速処理が可能となる。
【0055】また、本発明では、前述の遺伝子列の交叉・突然変異をレジスタ内のビット演算にて行なう。これによってメモリアクセスを行なわず、レジスタ内での処理が可能である。その結果、遺伝的アルゴリズムの高速処理が可能となる。また、前述の遺伝子列は、遺伝子を配置する場所の各々が個体の特徴を示す情報を有している。そこで、個体の特徴の性質が近いものを示す遺伝子の配置位置を、互いに近付く様にする。これによって、遺伝子列は前世代の個体の性質を維持しつつ処理することが可能となる。
【出願人】 【識別番号】000005108
【氏名又は名称】株式会社日立製作所
【出願日】 平成4年(1992)11月26日
【代理人】 【弁理士】
【氏名又は名称】小川 勝男
【公開番号】 特開平6−161980
【公開日】 平成6年(1994)6月10日
【出願番号】 特願平4−316797