Real-Coded Genetic Algorithm

第3章 カオスアニーリングの職場レイアウト問題への適用性 41

図3.10 SPXの交叉イメージ（親個体３個）.

3.3.2 SPX(Simplex Crossover)

 RCGAでは実数値を直接探索に用いるため，一点交叉などのビットストリング（0-1^{の文字列）のた} めに設計された遺伝的オペレータを用いることはできない．そのためRCGAのために設計された交叉を 用いる必要がある．本研究では,この実数値交叉としてシンプレクス交叉(SPX: Simplex crossover)[39]

を用いる．

SPX^とは,母集団から複数の個体を抽出し,その分布から一様乱数を発生させ新しい個体を生成する手 法である．その特徴として,探索性能が最適化対象関数の性質に影響されにくく,^{座標系の取り方に依存} しない点が挙げられる．図3.10^はSPXにおける交叉のイメージ（親個体3個）である．親個体の重心 から各個体 へのベクトルを延長した点 が構成するシンプレクス領域（本例では3角形）の中に，一様分 布に従い子個体を生成する.

3.3.3 SPX のアルゴリズム

SPX^{のアルゴリズムを下記} (1)∼(3) に示す．尚，ここでは簡単のため a^{k,i を} ai,c^{k,j を} cj と表記 し，a1· · ·anp からcj を生成する過程を示す．また，問題の次元数をd(FLP^の場合は2M)^{とすると，}

np=d+ 1^となる．

1. 親個体の重心を求める．

g= 1 d

∑d i=1

ai (3.12)

2. 式(3.13)から式(3.15)よりベクトルp1, p1,· · · , pd+1およびc⁽¹⁾_j , c⁽²⁾_j ,· · · , c^(d+1)_j を求める．

c⁽¹⁾_j = 0 (3.13)

pi=g+ε(ai−g) (3.14)

c_j =ri−1(pi−1−pi+c_j ) (3.15) 但しε^{は拡張率，}riは区間[0,1]^{の一様乱数}u^を式(3.16)で変換した乱数である．

ri= (u(0,1))ⁱ⁻¹¹ (3.16)

3. ^{子ベクトル}ciを式(3.17)^で得る．

cj =pd+1+c^(d+1)_j (3.17)

ここで，p1· · ·pd+1は，重心gからa1· · ·ad+1にε倍拡張した点であり，シンプレックスの各頂点とな る（図3.10^参照）．c⁽¹⁾_j , c⁽²⁾_j ,· · ·, c^(d+1)_j ^は，cj を計算するための部分的な計算過程であり，これらを漸 化的に求める事でp1· · ·pd+1から構成されるシンプレックス内に一様分布で新しい子個体cj を生成する 事が出来る．尚，式(3.13)^から式(3.17)^を通して1^つの個体cj が生成されるため，これら一連の流れを 実行可能解がnc個得られるまで繰り返す事とする．

3.3.4 拡張率

SPXにおける探索範囲はε(ai−g)で決定される．このうちai−g(以下Ri)は時間の経過とともに減 少傾向があり，問題によっては探索範囲が早期に縮小し，初期収束を引き起こしてしまう事が知られてい る[12]．実験的に調べてみたところ，FLPにおいても解の更新が行われなくなることが確認できた．図 3.11^は10^職場のFLP^に対し，ε=√

12で実験を行った結果である．（推奨値であるε=√

d^，即ち10 職場ではε=√

22 で行った場合，個体が発散したためこの値を用いた）．固体が収束するまでの世代数 は問題により異なるが，少なくとも37300世代程度が必要であることが報告されている [38]．ところが，

ε=√

12^{の場合，約}1000世代で解の更新が行われておらず，初期収束していることが分かる．

そこで本研究では，解の更新を行うためにε^{を探索の状態（}Riの値）に応じて増加することを提案す る．Riの取りうる範囲をT 個の小区間に分割し，その境界点を

0< R¹< R²<· · ·< R^T−1<∞

の様に取る．そして各区間に対し,ε=εt(R^t−1< Ri < R^t)と置き，εをRiに基づき選択する．これに より，探索の初期収束を防ぎ，解の多様性を維持することを指向する．

第3章 カオスアニーリングの職場レイアウト問題への適用性 43

0 500 1000 1500 2000 2500 3000 3500 4000 4500 5000

1.92 1.94 1.96 1.98 2 2.02 2.04 2.06 2.08

2.1x 10⁵

図3.11 ε=√

12のときの最良個体の評価値の推移.

3.3.5 実験結果

RCGAの適用結果を表3.5に示す．また,I62に対するレイアウト結果を図3.12に示す．また,I62に対 するレイアウト結果を図3.14^{に示す．図}3.12^より,得られたレイアウトは職場が建屋内に収まっており 物流量の多い物同士が近くに配置されている事がわかるが,^表3.5より計算時間が多くかかっており,^概ね PSOと同様の傾向を示していると言える．

この理由としては,実行不可能解が多い事が原因であると考えられる．これは表3.3より実行不可能解 の割合が9割を超えている事から確認できる．この原因としては,解の更新の過程で多くの職場同士の重 複が見られる事が原因であると考えられる．SPXではシンプレックスを生成する事で解の形質を維持す る工夫を加えているが,そのシンプレックス内においては各成分は乱数により決めている．ところが,^こ の様にランダムに配置した職場が他の職場と全く重複なく配置される事は非常に難しく,^{この点が実行不} 可能解を多くしている原因の1つであると考えられる．この傾向は職場数が増加するにつれ大きくなると 考えられる．

表3.5 RCGA適用結果まとめ

問題

RCGA

OFV CPU time ^{実行不可能解}

の割合(%)

O9 356 15039.6 95.6

VC10 24999 16775.2 99.7

Ba15 6461 24646.9 98.5

M15a 40275 24668.4 95.6

AB20 10441 31441.2 97.5

SC30 4579 47525.1 97.0

SC35 6721 58647.0 98.9

I62 1503 100410.0 97.5

−20 0 20 40 60 80 100 120 140 160 180

−20 0 20 40 60 80 100 120

図3.12 I62に対するRCGA適用後のアウトプット

第3章 カオスアニーリングの職場レイアウト問題への適用性 45