3. 配管最適化のための多目的GAの設計
3.1 コード化/交叉設計:Crossover with Two Gene(XTG)の提案
関数最適化において伝統的に広く用いられてきたコード化(coding)/交叉(crossover)はビットストリング上で定義されたバイナリーコーディングおよびグレイコーディングと、その上で定義された一点交叉、二点交叉、一様交叉である。近年では、表現型空間と遺伝子型空間の位相構造が一致した実数ベクトルをコード化の方法として採用し、その上で交叉方法を実装した実数値GAが提案されている5)。本問題では、1本のパイプは曲がり生成パターンと直線部パイプ長さにより一意に定まり、組合せ最適化と数値最適化の複合問題となっており、従来のコード化手法では困難である。
そこで、染色体のコード化として生成パターンと実数ベクトルを組合せたもの(生成遺伝子)を遺伝子とする個体を生成する。交叉方法としては、2遺伝子交叉(Crossover with Two Gene; XTG)を提案する。XTGは、Fig. 5に示すように、障害物との接触情報を持った遺伝子(障害物遺伝子)を用いて1つの子を生成する。基本的には親の生成遺伝子のどちらかを引き継ぐか新しい生成遺伝子が生成され、障害物遺伝子は子がどの生成遺伝子を持つようになるのか補助的に用いられる。あるパイプについて、両親共に障害物を避けている場合はどちらかの遺伝子を、両親の片方だけが障害物を避けている場合はその親の遺伝子を、両親共に障害物と接触している場合はランダムに生成する。XTGは、障害物に対する評価値を優先的に改善することを目標とした交叉方法である。障害物と接触していない生成遺伝子を引き継ぐことで、そのパイプは再び障害物を避けることになり、全体として障害物に対する評価値が改善される可能性が高くなると考えられる。パイプの長さはランダム的に変化し、良好なものを選ぶことになる。XTGの有効性を確認するために、伝統的な交叉方法である一様交叉に基づく交叉(Uniform Crossover UX)も設計する。UXは、Fig. 6に示すように、XTGと同様に、2つの親から1つの子を生成する。子の生成遺伝子は親の生成遺伝子のどちらかを等しい確率で引き継ぐ。
しかし、これらの交叉方法では生成遺伝子をそのまま引き継ぐので、ある生成遺伝子の組に収束し、解の改善が困難となる可能性があるが、次に述べる突然変異、修正オペレータの効果によりその可能性は低くなる。
Fig. 5 Crossover with Two Gene; XTG.
Fig. 6 Uniform Crossover, UX.
3.2 突然変異設計
突然変異(mutation)は、解集団内に存在しない遺伝子を発生させ、より広い探索空間内の探索、局所解からの脱却に寄与し、GAの設計において非常に重要なオペレータである。
Fig. 7に示すように、まず2つの親のどちらかが選ばれ、選ばれた親に対し、ある突然変異率(mutation rate)で定められた一定確率で突然変異が各遺伝子に適用され、新たに生成遺伝子がランダムに生成される。
Fig. 7 An example of mutation.
3.3 修正オペレータ
3.3.1 修正オペレータの必要性
GAの配管問題への適用においては、パイプ本数の増加につれて、パイプ同士が交わっていない実行可能解の生成が急激に困難になるという問題が生じる。解の生成においては、生成パターンとパイプの直線部長さを特徴づける実数値を一様乱数に従って、ランダムに生成するため、パイプ本数の増加に伴い、パイプがお互いに交わっている可能性が高くなる。例えば、問題設定にもよるが、ある5本の配管問題の場合、実行可能解をランダムに100個生成するのに数十秒だが、15本の場合は、丸一日かけても生成できない。GAは多様な実行可能解を生成し、交叉・突然変異・選択を繰り返すことで、解を改善していく。そこで、できるだけ短時間に一様ランダム性を保ったまま実行可能解を生成できる工夫が望まれる。そこで、パイプ同士の接触点の数を考慮することで、生成された実行不可能なパイプをもとの性質をできるだけ残すように、なるべく少ない修正で実行可能解へ修正する修正オペレータ(Modification Operator on Contact; MOC)を提案する。
3.3.2 MOCのアルゴリズムの概要
MOCのアルゴリズムの概要を以下に示す。
1. 接触点の数が多い順にパイプに順番をつける。
2. 1番目に接触点の数が多いパイプをランダムに再生成し、ステップ1へ戻る。この時、接触点が最も多いパイプがα回連続で同じパイプの場合ステップ3へ進む。
3. 1番目と2番目に接触点の数が多いパイプをランダムに再生成し、ステップ1へ戻る。この時、1番目と2番目のパイプがα回連続で同じパイプの場合ステップ4へ進む。
4. ステップ2、3と同様に最後のパイプまで繰り返す。
5. 全てのパイプがお互いに接触しなくなるまで、ステップ1からステップ4まで繰り返す。
α:脱却回数(slip number)
3.4 解法の構成
本節では、提案したコード化/交叉を用いて関数最適化のための多目的遺伝的アルゴリズムを設計する。多目的遺伝的アルゴリズムの世代交代モデルは、Fig. 8に示すような非パレート解淘汰戦略6)に基づくモデルを採用する。非パレート解淘汰戦略とは、交叉により生成された子個体を親個体と合わせてパレート解でない個体を淘汰し、パレート解(他の全ての解に対して、少なくとも1つの評価基準において勝っているような解)のみで次世代の集団とするものである。
Fig. 8 Generation Alternation Model.
3.5 パイプ15本の配管最適化
本節では、Table 1に示す配管設計問題に前節で提案した多目的遺伝的GAを適用し、自動設計を行う。また、提案した交叉XTGの有効性を確認するために、一様交叉UXとの比較実験を行う。Table 1は、扱う配管問題の中身について、2.2節で示したPatternで分類した結果を表している。
実験では、予備実験により、初期集団の生成回数を100、MOCのαを10、交叉回数を100、突然変異率は0.1とする。Fig. 9、Fig. 10、Fig. 11はそれぞれ、初期のパレート解、第100世代(1.0×104の配管を評価)のパレート解、第1000世代(1.0×l05の配管を評価)のパレート解である。XTGでは、第100世代で障害物を避けた解を得ているのに対し、UXでは第1000世代でも解は改善されているものの完全に障害物を避けた解を得ることが出来ていない。XTGは第1000代でも値の改善はわずかで、十分収束していると考えられる。Fig. 12にFig. 11のXTGで障害物に対する評価値が0となった解の結果を示す。中央の立方体が障害物を表し、パイプが密集したなかで、パイプ同士がお互いに接触しないで障害物を避けて配管できていることが分かる。
Table 1 Problem specification.
|
Pattern-1 |
Pattern-2 |
Pattern-3 |
The number of pipes |
5 |
7 |
3 |
The number of variables |
3 |
2 |
1 |
The number of combinations |
14 |
6 |
2 |
The total number of variables |
15 |
14 |
3 |
The total number of combinations |
537,824 |
279,936 |
8 |
The number of all variables |
32 |
The number of all combinations |
l,204,450,394,000 |
|
Space where pipes arranged:
{(x,y,z)|0≤x≤10,0≤y≤10,0≤z≤10}
Space where obstacle exists:
{(x,y,z)|2≤x≤8,2≤y≤8,2≤z≤8}
|
Fig. 9 First pareto solutions with the MOC.
Fig. 10 |
Pareto solutions in the 100th generation with the MOC. |
Fig. 11 |
Pareto solutions in the 1000th generation with the MOC. |
Fig. 12 Result of 15 pipes arranged.
|