適応型局所探索 GA の構造

この章では，na-GLS と a-GLS の詳細な実行手順を説明する。最初に，比較対象とし て，基本的な GA の手順を説明する。次に，２つの GLS の手順を説明する。

4.4.1 基本的な GA（CGA）

信頼性最適化問題を対象とした CGA による進化シミュレーションの手順を説明する。

これらの問題は次のようないくつかの特徴を持っている。①信頼性最適化問題では決定変 数がユニット数となる。②解を表す決定変数は整数値である。③信頼度を評価値とするた め，値は0.0から1.0に連続的に分布する。「山登り法」の適用が容易である。CGA を実 行するための詳細な手順は次の通りである。

Step 1： 初期集団の生成など：

最初の個体は制限範囲内でランダムな値で生成する^[43]。 Step 2： 遺伝的操作：

選択：親個体と子個体（交叉，突然変異で生成）からエリート戦略で次世代の親を 選択する^[51]。集団サイズまで選択して終了する。

交叉：算術交叉による操作^[44]。

突然変異：一様突然変異による操作^[44]。ランダムに遺伝子を選び，制限範囲内でラ ンダムに遺伝子を変異させる。

・・・・・・・ (4-4)

・・・・・・・ (4-3)

Step 3： 終了状態の判定：

あらかじめ定められた最大世代数に達するか，あるいは最適な解が得られているな ら停止する。それ以外は，Step 2を実行する。なお，最適な解とは，解の平均値の 変化が少なくなった状態を言う。

次に，最大化問題のためのCGA の処理手順のフローチャート（図4-1）を示す。

START

Initial population

Selection Crossover Mutation Evaluation

Stop condition

START No

Yes

Fig. 4-1 Flowchart of the CGA

図4-1 最大化問題のためのCGAの処理手順のフローチャート

4.4.2 na-GLS

na-GLS の手順は CGA に山登り法を組み合わせたものである。その組み合わせた進化

シミュレーションの手順は次の通りである。

Step 1： 初期集団の生成他

最初の個体は制限範囲内でランダムな値で生成する^[43]。 Step 2： 遺伝的操作：

選択：親個体と子個体（交叉，突然変異とLSで生成）からエリート戦略で次世代 の親を選択する^[51]。集団サイズまで選択して終了する

交叉：算術交叉による操作^[44]。ランダムに遺伝子を選び，制限範囲内でランダムに 遺伝子を変異させる。

突然変異：一様突然変異による操作^[44]。

Step 3： 第4.3.2で示した「山登り法」を実行する（常に局所探索が実行される）。

Step 4： 終了状態の判定：

あらかじめ定められた最大世代数に達するか，あるいは最適な解が得られているな ら停止する。それ以外は，Step 2を実行する。なお，最適な解とは，解の平均値の

変化が少なくなった状態を言う。

次に，最大化問題のためのna-GLS の処理手順のフローチャート（図4-2）を示す。

START

Initial population

Selection Crossover Mutation Evaluation Local Search

Stop condition

START No

Yes

Fig. 4-2 Flowchart of the na-GLS

図4-2 最大化問題のためのna-GLS の処理手順のフローチャート

4.4.3 a-GLS

a-GLS の処理手順は，na-GLSの手順のStep 3を変更した手順である。異なる部分は，

適合値の状態で局所探索（山登り法）を稼動させるか否かを制御する適応型スキームを組 み込んだところである。

Step 1： 初期集団の生成ほか

4.4.2と同じ手順である。

Step 2： 遺伝的操作

4.4.2と同じ手順である。

Step 3：局所探索（山登り法）を評価値の状態に適応させて実行するか否かを制御する。

もし,適合値比率 FVR(t)＞1 であるならば「山登り法」を実行する。そうでなけれ ば，実行しない。

Step 4： 終了状態の判定

4.4.2と同じ手順である。

次に，最大化問題のためのa-GLS の処理手順のフローチャート（図4-3）を示す。

START

Initial population

Selection Crossover &

Mutation Evaluation

Local Search

Stop condition

END Yes

Yes 1 ) (t >

FVR

No

No

Fig. 4-3 Flowchart of the a-GLS

図4-3 最大化問題のためのa-GLS の処理手順のフローチャート