第７章 多目的 GA による通信システムの信頼性最適化設計
7.3 多目的遺伝的アルゴリズム
一般的にGA は多点探索による大域探索には優れているが，局所探索の機能は劣ってい る。このため厳密解法に比べ最終的に得られる解の精度が劣る可能性が高いという問題点 がある。また，GA は集団のサイズ，最大世代数，交叉率，突然変異率などのパラメータ を事前あるいは進化状況に適応（適応型スキーム）して調整することが必要である。さら に，多目的 GA では解がパレート最 適解となることから目的関数間でバ ランス（トレードオフ）の取れた多 数の解が存在する。パレート最適解 を効率よく求めるためには，多目的 に適した GA 手法が必要となる。本 論文では多目的GAの技法として，
① 選択手法では改良パレート解 保存戦略，
② 局所探索では適応型スキーム による指向性遺伝子法，
③ パレート解の均等分布を目的 とするシェアリング，
を提案する。なお，この多目的最適 化問題ではパレート最適解が不明な ので，評価方法として，提案の弓形 面積，被覆率，パレート解の数，正 規化によるパレート解の図示を用い ている。なお,パレート最適解が不明 な場合，誤差は使用できない。
START
Set GA parameters, Generate the initial population and Pareto set
Select and update of Pareto solution
Local search technique
Create Pareto Solution END
Termination condition Crossover and Mutation
No
Yes
Evaluation and Selection Update candidate set of Pareto solution
Crossover and Mutation
Fig.7-4 Procedure of the proposed hGA 図 7-4 提案した多目的 GA の探索手続き
Step 1：最初の親集団をランダムに生成する。
Step 2：評価計算を行いパレート解候補を更新する。
Step 3：交叉は一様交叉を使用する[84]。
Step 4：突然変異はランダムに選んだ遺伝子を指定範囲内でランダムに変異させる。
Step 5：局所探索は適応型スキームにより指向性遺伝子法を制御する(３章の3.4.7)。
Step 6：パレート解候補群(candidate set of Pareto solution)を更新して，シェアリングと 評価計算する(３章の3.4.3)。
Step 7：選択は改良パレート解保存戦略を用いる。パレート解候補から次世代親集団の 選択はエリート選択とする(３章の3.4.8, 3.4.9)。
Step 8：終了状態でなければ，次はStep３を実行する。
Step 9：パレート解候補群からパレート最適妥協解を生成する。
図7-6は提案した多目的GAの探索手続きの流れを示す。図7-7は提案した多目的GA に おける進化の流れを示す。
7.3.1 遺伝子の表現
この信頼性最適化設計では，サブシステムの予備回線数とケーブルの心線数の最適な組 合せを求める。そこで，これらの決定変数をGAにおける染色体の遺伝子とする。予備回
Fig.7-5 Outline flow of chromosome Chromosome of
parent population crossover mutation
Pareto solution
Local Search
Update
Offspring population offspring
chromosomes of LS
add to
add to Selection
add to offspring
candidate set of Pareto solution create
図 7-5 多目的 GA の染色体の流れ
線数と心線数はともに整数値などので，基本的には１つの染色体として取り扱う。つまり，
交叉や突然変異は１つの染色体として操作される。
] ,..., ,..., [
) , , 2 , 1 ( ] ,..., ,..., [
) ,
, 2 , 1 ( ] , [
1 1
kq kj k k
kq kj k
k
k k k
g g g
q j
m m m
popSize k
=
=
=
=
= g m
g m v
K K
ここで, vk：個体kの染色体，mk：個体ｋの予備回線数，
gk：個体kのケーブルの心線数，mkj：個体ｋのサブシステムｊの予備回線数，
gkj：個体ｋのサブシステムｊの心線数，popSize ：集団のサイズ，
ｋ：個体の番号，ｑ：サブシステムの数。
7.3.2 交叉
交叉は一様交叉を採用する[84]。２つの個体間でランダムに選んだ遺伝子座の遺伝子を 交換する方法である。交換する遺伝子数は任意に指定する。
7.3.3 突然変異
突然変異はランダムに選んだ遺伝子を指定範囲内でランダムに設定する。変異させる遺 伝子数は任意に指定する。一様突然変異とも呼ばれる方法である。
7.3.4 改良パレート解保存戦略
提案した改良パレート解保存戦略とは，多目的 GA の選択手法の一つである。この選択では 2 段階に選択が行われる。第 1 段階は，生成された子を使ってパレート解候補群を更新する。こ のとき，ランク法（第３章3.4.5）によるランク１の解を追加登録する。第２段階は，パレート解候補群 から次世代の親集団を，多様性を考慮した評価値（式 7-18）で選択する。パレート解候補群とは，
原則として，各世代での非劣解の累積と不可能解を実行解と見なした時の非劣解の累積である。
（１）パレート解候補群の更新
交叉や突然変異，局所探索で生成された子Vnをパレート解候補群Vに登録する手続き を説明する。登録の原則は，① 実行可能解でランクが１であれば，追加あるいは置き換 えとする。② 実行不可能解のとき，ランクが１であれば追加する。ただし，置き換え相 手が実行不可能解の場合は置き換える。具体的な手続きを次に示す。
procedure : Update candidate Pareto solutions table begin
for p = 1 to pcSize do
if Vpc< Vnc and Vpa< Vna then return;
end
･････････････ (7-17)
for p = 1 to pcSize do
if Vpc> Vnc and Vpa> Vna then
if Vn is execution possible solution then replace Vn in Vp;
else
if Vp is execution possible solution then
register Vn in Table (candidate Pareto solutions table);
else
replace Vn in Vp; else
register Vn in Table (candidate Pareto solutions table) ; end
end
ここで，V：パレート解候補群，Vp：p番のパレート解候補，Vn：ｎ番の被登録解，
Vnc：ｎ番の被登録解のコスト，Vna：ｎ番の被登録解の不稼働率，
Vpc：p番のパレート解候補のコスト，Vpa：p番のパレート解候補の不稼働率，
pcSize：パレート解候補の数。
（２）パレート解候補群からの選択
選 択 の 基 準 と な る 表 価 値ek は シ ェ ア リ ン グ 度skと 重 み 付 け 係 数 法 に よ る 評 価 値 )
(vk
eval を組み合わせる。選択の基準とする評価値ekは次のように計算する。
k k
k s
v
e =1−eval( ) (k=1,2,K,pcSize)
ここで，eval(vk)：重み係数法で求めた評価値，sk：遺伝子kのシェアリング度，
pcSize：パレート解候補の数。
多目的GAの選択は，評価値ekを基準としてエリート選択で求める。評価値の高い方か ら順に選択して，集団数に達したら終了とする。次に選択の手順を示す。
① pcSize ≧ popSize: パレート解候補の中から評価値ekの高い順に集団数 の数だけ選択する。
② pcSize ＜ popSize: パレート解候補をすべて選択し，
残りのpopSize - pcSize個の個体は現世代の個体集団と子個体集団の 中から評価値ekの高い順に集団数まで個体を選ぶ。
････････ (7-18)
ここで，pcSizeはパレート解（パレート解候補）のサイズ，popSizeは親個体の集団数で ある。
7.3.5 適応型スキームによる局所探索
局所探索技法(LS)の適応型スキームとは，①シェアリング度skが１の個体の中からラン ダムにひとつの個体を選択する。この個体を基にLSを実施する。②skが１の個体がない 場合は，LSを実行しない。LSの目的はパレート解の近傍を探索しながら，より多くのパ レート解を探しだすことにある。このLSは決定変数が整数の場合（非線形整数計画問題）
の局所探索法である。この LS を指向性遺伝子法と呼ぶ。あるパレート解（個体）を親と して，近傍と思われる子個体（解）を生成する。多目的で複数の決定変数を持つ場合，あ る遺伝子の増加・減少が複数の目的にどのように影響するかが不明である。このような場 合を想定して，決定変数を最小変化量の増加と減少に対応させて，決定変数×２の子個体 を生成する。基本的な操作は，最小変化量が1の場合，複数の遺伝子のひとつをランダム に選択し，+１した個体と-1した個体を生成する。この操作を決定変数ごとに実施する。
図7-6は，決定変数が２，遺伝子数が３，最小変化量が１，候補数が１の例である。LS で生成される染色体は２×２＝４である。