第３章 多目的遺伝的アルゴリズム
3.4 多目的遺伝的アルゴリズム
3.4.7 適応型スキームによる局所探索技法
局所探索技法(LS)の目的はパレート解の近傍を探索しながら，より多くのパレート解を 探しだすことにある。この LS の一方法である指向性遺伝子法の対象は非線形整数計画問 題（nIP）である。あるパレート解（個体）を親として，近傍と思われる子個体（解）を 生成する方法である。多目的で複数の決定変数を持つ場合，ある遺伝子の増加・減少が複 数の目的にどのように影響するかが不明である。このような場合を想定して，決定変数を 最小変化量の増加と減少に対応させて，決定変数×２の子個体を生成する。基本的な操作 は，最小変化量が 1 の場合，複数の遺伝子のひとつをランダムに選択して，+１した個体 と-1した個体を生成する。この操作を決定変数ごとに実施する。
f2
f1
Rank : 2 Rank : 1
Rank : 3
Fig.3-６ compute numbers of Rank 図3-６ ランク度の計算
なお，複数の遺伝子を+1，-1する場合，複数の決定変数を+1，-1する場合も考えられる。
前者は，目的から20％以内とするなどの制限が 必要である。後者は，各決定変数で１つの遺伝 子を操作するのが良いようである。
この局所探索（LS）の場合，親の選択と稼動 に関して調整が必要である。親の選択は，集団 のどの個体（解）を選ぶかで，パレート解の均 等な分布に悪影響がある。分布の薄い部分や中 心部を選ぶ仕組みが必要である。本論文では，
シェアリングの結果を使い選択関数を作成して いる（3.2.3を参照）。後者の場合，LSの動作を パレート解の分布状況で制御する適応型スキームを使用している。この LS の手続きを次 に説明する。
なお，集団の個体は，パレート解あるいはパレート解候補から選択されているので，シェ アリング度が個体に記録されているものとする。
Step 0: 集団におけるすべての個体の評価値ekを求める。eval(vk)は重み係数法で求めた 評価値である。skは遺伝子kのシェアリング度である。
k k
k s
v
e =1−eval( ) (k=1,2,K,popSize)
この評価値ekは個体vkを選択するための基準値である。
Step 1: 評価値ekの最も大きな個体をひとつ選択する。これをLSの親個体vkとする。
vk =max{v1,v2,K,vpopSize} (k =1,2,K,popSize)
Step 2: 親個体vkの遺伝子をひとつランダムに選ぶ。この遺伝子に最小変化量を加算と減
算して，２つの個体を生成する。
Step 3: 決定変数が複数あれば，Step2 を決定変数の数だけ繰返し，決定変数×２の子個
体を生成する。
適応型スキームは LS を制御するものと，交叉や突然変異を制御するものがある。単目 的GAの交叉や突然変異の制御方法は第５章で，多目的GAは第６章で採用している。
単目的GAのLSも制御は第４章で，多目的GAは第７章で採用している。提案してい る多目的GAにおけるLSの適応型スキームとは，①シェアリング度skが１の個体群の中 からランダムにひとつの個体を選択し，この個体を基にLSを実施する。②もし，skが１ の個体がひとつもない場合は，LS を実行しない，と言うアルゴリズムである。この適応 型スキームは，LS の欠点のひとつである局所解を優先しすぎる傾向を抑制して，必要な 領域を優先的に探索する効果がある。
f2
f1
offspring of LS
Pareto solution
Fig.3-7 Generation offspring in LS 図3-7 LSによる近傍解の生成
････････(3-10)
3.4.8 パレート解候補の保存と更新
パレート解候補の保存と更新とは，2段階で行う遺伝操作（改良パレート解保存戦略等）におけ る選択の1次選択である。1次選択は図3-2の処理(2)である。2次選択は図3-2の処理(3)であ る。単目的GAでは，1回の処理で行われているが，提案する多目的GAの選択技法では 2段 階で行われる。
多数の評価関数がある場合は，解がパレート解となることから選択の対象としてパレー ト解候補を処理の中間で蓄積する方法がある。この中間で蓄積する解群は，①パレート解 を中間で保存する方法をパレート解保存戦略と呼ぶ[37]。②新しいパレート解と元のパレー ト解等を残す方法を改良パレート解保存戦略と呼ぶ。第６章では，前者の方法を提案，第 ７章では，後者の方法を提案している。後者の方が，高い探索効果を上げている。ただし，
欠点は個体数が世代と共に増加することである。一定の基準で最大数を制限する必要があ る。
改良パレート解保存戦略の更新方法
交叉，突然変異，局所探索で生成された子個体がランク１であるとき，パレート解候補 群に登録する。その結果，パレート解候補にはランク１の解が蓄積される。登録は，次の ルールで実行する。x′をパレート解候補群に登録する例で説明する。xはすべてのパレー ト解候補とする。
◎ A領域に解がないかの判定：
) , , 2 , 1 ( ) ( )
(x f x i n
fi ≥ i ′ = K
すべての fiに対して式3-11が成り立つようなxがなければ，A領域に解はない。
◎ C領域に解がないかの判定：
) , , 2 , 1 ( ) ( )
(x f x i n
fi < i ′ = K
すべての fiに対して式3-12が成り立つようなxがなければ，C領域に解はない。
２目的を例（図3-8）にして説明する。原則として，登録の判定は，A領域とC領域に 解があるか否かで，置換え，新規登録，登録しないを判断する。B領域とD領域は判定に 使用しない。たとえば，図3-8の場合はC領域に解があるので，登録しません。
(1)新個体が実行可能解で，C領域に解がなく，
A領域に解がある場合は，置換える。
(2)新個体が実行可能解で，C領域に解がなく，
A領域にも解がない場合は，新規登録する。
(3)C 領域に解があっても実行不可能解の場合 はないものと見なす。
(4) 新個体が実行不可能解で，C領域に解がな く，A領域に解がある場合は，置換える。
(5)上記以外の場合： 新規登録する。ただし，
重複解は除く。
f2
f1
New individual
C area D area
A area B area
Fig.3-8 update new individual 図3-8 新個体による解候補群の更新
････････ (3-11)
････････ (3-12)
①パレート解保存戦略の特徴
パレート解保存戦略は進化過程で親個体を現在のパレート解から選択する方法である。
中間に保存する解群は常に最新の，パレート解とする。
長所： 現在のパレート解から選択を行うため前縁部に探索を集中できる。
短所： 実行不可能解やパレート解に近い解が除かれるため，複雑な非線形問題では 効果が薄れる。親個体の初期値により解の増加が大きく影響する。
②改良パレート解保存戦略の特徴
改良パレート解保存戦略は，現在のパレート解から選択するのではなく，実行不可能解 と以前のパレート解を含むパレート解付近の解（パレート解候補と呼ぶ）から次の親個体 を選択する方法である。
長所： 前縁部のパレート解候補を多くすることで，シェアリングを使った選択が効果的 となる。その結果，均等に分布したパレート解が得られる。
短所： パレート解候補が世代と共に増加するため，最大世代数を大きくして，進化を 進めることができない。また，計算時間も長くなる。
3.4.9 遺伝的操作（選択）
遺伝的アルゴリズムによる探索は学習機能付きの確率的探索であるが，この学習機能を 実現しているのが，選択淘汰である。提案の多目的GAの場合，現世代のパレート解候補 あるいはパレート解から次世代の親個体を選択する。この時点で，既に1次の選択（パレ ート解候補の更新，3.4.8参照）が行われている。ここでの選択は２次の選択と言える。
この２次の選択方法としては，次のような方法がある。なお，選択の基準となる基準値
ekはシェアリング度と重み付け係数法による評価値eval(vk)を組み合わせたものである。
本論文で提案する多目的GAは，エリート選択を採用する。エリート選択の基準は評価値 ekとする。なお，第６章の多目的GAはランダム選択を採用している。
① エリート選択[27]：パレート解候補の個体を評価値ekの順に整列して，先頭から集団の 数まで選択を行う方法である。この選択方法は，偏りが起こる可能性が高いので他の 方法と組み合わせて使用する。評価値ekの性質が選択に大きく影響する。
② ルーレット選択[27]：パレート解候補の個体の評価値ekから選択確率を求めて，サイコ ロを振る要領で，集団の数まで繰り返し選択を行う方法である。この方法は，エリー ト選択とランダム選択の良い機能を組み合せたような方法である。
③ ランダム選択：パレート解候補からランダムに集団の数を選択する。現在のパレート 解の分布の相似形の親個体群を作成する方法である。
選択の基準とする評価値ekは次のように計算する。集団におけるすべての個体の評価値
ekを求める。eval(vk)は重み係数法で求めた評価値である。skは遺伝子kのシェアリング