多目的遺伝的アルゴリズムを用いた配管設計

A Pipe Arrangement using Multi Objective Genetic Algorithms
九州大学工学部
九州大学大学院工学研究院
九州大学大学院工学研究院○池平 怜史木村 元梶原 宏之○Satoshi IKEHIRA,
Faculty of Engineering, University of Kyushu
Hajime KIMURA,Graduate School of Engineering, University of Kyushu
Hiroyuki KAJIWARA, Graduate School of Engineering, University of Kyushu
Abstract: A pipe arrangement of ships has been enabled to be more efficient and economical by development and spread of CAD(Computer-Aided Design). But most of designing are designed by hand inshipyard. In this paper, we formulate the problem of pipe arrangement in a space such as engine room
where many pipes exist closely and are to avoid some obstacles. This problem is a compound problemof large-scale numeric optimization and combinatorial optimization. It is difficult to optimize it in usual
methods such as Random Search. Therefore we propose Multi Objective Genetic Algorithms suitable forthis problem. We demonstrate that those algorithms can efficiently optimize the pipe arrangement.

1

はじめに
近年，韓国ならびに中国における造船業の躍進は目覚ま

2配管問題の定式化

2.1

パイプの生成しく，日本の造船業をとりまく環境は一層厳しさを増しており，設計の最適化が求められている．船舶の配管設計は，ある３次元空間を指定し，その空間内で障害物を避け，CAD（Computer-Aided Design）の発達，普及により以前より効率的・経済的になったものの，未だ設計者の経験に頼る部分が大きい．特に本論文で対象としている造船所
では，エンジンルームの配管作業は大まかな部分は最初に設計されているものの、大部分は現場で実際に配管を行う作業者がその場で配管しており効率的ではない．

パイプの長さの総和が短くなるように配管する問題を考え

本研究では，エンジンルームのような，パイプが密に存経済的な面から考えると，パイプの長さはできるだけ短在し，障害物を避けて配管しなければならない空間での配くなることが求められ，工作上の面から考えると，できる管設計問題を定式化する．本問題は，大規模な数値最適化だけ工作の手間が省かれることが求められる．パイプ部材と組合せ最適化の複合問題かつ多目的最適化問題となってはＪＩＳ規格に定められており，その規格に基づいたパイおり，通常の最適化手法では解くのが困難である．

プ部材を使用するのが経済的にも好ましい．パイプを直角

多目的最適化問題は，実世界の問題は多目的なものが多く非常に重要な問題であり，一般に完全最適解を得ることはできないため，トレードオフを表す解の集合であるパレート最適解という別の概念を用いて解探索を行う [1, 2]．

る．配管設計では，まずパイプの始点，終点の位置を決め，その間をどういう道筋で配管するかが問題となる．そこで，始点，終点の座標，その点でのパイプの伸びる方向（方向ベクトル）が与えられた時に，配管経路を生成することを考える．に曲げる時は，ＪＩＳ規格で定められた部材で，２本のパイプを溶接して繋げる．それに対し，任意の角度に曲げる
時は，プレス機を用いて 1 本のパイプをその角度に曲げなければならない．この作業は非常に手間がかかるので，パイプは直角に曲がるものとし，設計上の要求（下水管等はGA は，自然界における生物の進化をモデル化した確率的自然に流れるようにある傾斜をつけて配管する）がある場最適化手法の一つであり，GA を多目的へ応用した多目的合は，方向ベクトルで与える．
GA では，評価項目の優先度を定義することなく，一度の始点，終点を結ぶ配管経路を設計するということは，折思考により幅広い領域の解候補を得ることができ，パレート解を効率的に求める強力な方法として注目されている． れ曲がる点（節点）を定めることである．方向ベクトルのそこで，本問題に適した多目的遺伝的アルゴリズム（Multi 値によって mode-1，mode-2，mode-3 に分け，節点の数，Objective Genetic Algorithms : MOGA）を提案し，実験 始点終点からの位置関係によって生成パターンを Fig.1，Fig.2，Fig.3 に示すように定める．パイプは生成パターンによりその有用性を示す．

と 3 個の実数ベクトル (x0 , x1 , x2 ) により一意に定まる．節

しかし実際の設計では，パイプを繋ぐ際フランジと呼ば点の数をさらに増やすことで生成パターンを増やすこともれる部材を用い，その大きさも考慮しなければならない．

考えられるが，工作上，節点の数は少ないほど好ましく， フランジの大きさはパイプの径によって定まっており，そパイプ同士の接触，障害物との接触を避けることができるの大きさを考慮して接触を判断する．

最小限の節点の数で設計する．

2.3

障害物との接触障害物は直方体で与え，直方体を有限個配置することで，複雑な形状の障害物も表現することができる．
RCVVGTP

空間内に障害物が存在する場合，それを避けて配管しな

RCVVGTP


ければならない．障害物と接触した場合は致死解として再生成する方法が考えられるが，実際の設計では，障害物の6JGTGKUCEQODKPCVKQPD[

配置やパイプの制約条件によって完全に避けることができMKPFUQHKPVQVCN

ない場合が存在する．例えば，パイプのメンテナンス等のために人間が通れるスペースなどがそれに当たる．この時，

RCVVGTP


完全に避けなくてもよいが，できるだけスペースを作らなければならない．そこで，障害物に対しての評価式を提案

Fig. 1 : mode-1

する．
［障害物に対する評価式］
パイプが障害物の中心を通過ほど，また障害物内を通過するパイプの長さが長いほど評価としては悪くなるという
RCVVGTP

観点から，以下の評価式を提案する．

RCVVGTPf obstacle =no np
XX(bkl − akl + Al )(2)

l=1 k=1

6JGTGKUCEQODKPCVKQPD[bkl : k 番目のパイプで l 番目の障害物内を通過している長さ
akl : k 番目のパイプで l 番目の障害物内を通過している部分を節点ごとに切断し，それぞれの重心との距離の平均MKPFUQHKPVQVCNRCVVGTP

Fig. 2 : mode-2

Al : l 番目の障害物の重心と頂点との距離
no : 障害物の数
6JGTGKUCEQODKPCVKQPD[np : パイプの本数MKPFUQHKPVQVCN

障害物と全く接触していない場合，評価式は 0 となる．

RCVVGTP

Fig.4 に評価式の計算例を示す．

Fig. 3 : mode-35RCEGYJGTGQDUVCENGGZKUVU㧦

2.2

パイプ同士の接触

２つのパイプの半径をそれぞれ r0 , r1 とする．また，そ

れぞれのパイプの中心線の間の最短距離を d とすると，それらのパイプが存在する範囲で，d ≤ r0 + r1の時，この２つのパイプは接触している．

(1)Fig. 4 An example calculation of the obstacle function

3

配管最適化のための多目的 GA の設 3.2 修正オペレータの必要性
計

3.1

本節では，修正オペレータの必要性を述べ，そのアルゴリズムの概要を示す．

コード化／交叉設計：
GA の配管問題への適用においては，パイプ本数の増加
Crossover with Two Gene（XTG）のにつれて，実行可能な初期解の生成が急激に困難になると提案いう問題が生じる．初期解の生成においては，生成パター関数最適化において伝統的に広く用いられてきたコード化／交叉はビットストリング上で定義されたバイナリーコーディングおよびグレイコーディングと，その上で定義された一点交叉，二点交叉，一様交叉である．近年では，表現型空間と遺伝子型空間の位相構造が一致した実数ベクトルをコード化の方法として採用し，その上で交叉方法

ンと実数ベクトルを一様乱数に従って，ランダムに生成するため，パイプ本数の増加に伴い，パイプがお互いに接触している可能性が高くなる．例えば，パイプの径にもよるが，5 本の配管問題の場合，ランダムに 100 個生成するのに数十秒だが，15 本の場合は，丸一日かけても生成できない．

を実装した実数値 GA が提案されている [3]．本問題では，GA は多様な実行可能解を生成し，交叉・突然変異・選択1 本のパイプは生成パターンと実数ベクトルにより一意に定まり，組合せ最適化と数値最適化の複合問題となっており，従来のコード化手法では困難である．そこで，染色体のコード化として生成パターンと実数ベクトルを組合せたもの（生成遺伝子）を遺伝子とする個体を生成する．

を繰り返すことで，解を改善していく．そこで，できるだ交叉方法としては，２遺伝子交叉（Crossover with Two

け短時間に一様ランダム性を保ったまま実行可能解を生成できる工夫が望まれる．そこで，ランダムに生成された実行不可能なパイプをもとの性質をできるだけ残すように，なるべく少ない修正で実行可能なパイプへ修正する修正オ
ペレータを提案する．

Gene; XTG）を提案する．XTG は，Fig.5 に示すように， ［パイプの接触点の数を考慮した修正オペレータ］
障害物との接触情報を持った遺伝子（障害物遺伝子）を用ランダムに生成されたパイプを実行可能解へ修正する修
いて 1 つの子を生成する．基本的には親の生成遺伝子の 正オペレータのアルゴリズムの概要を示す．
どちらかを引き継ぐか，新しい生成遺伝子が生成され，障1. 接触点の数が多い順にパイプに順番をつける．
害物遺伝子は子がどの生成遺伝子を持つようになるのか補
2. 1 番目に接触点の数が多いパイプをランダムに再生成助的に用いられる．あるパイプについて，両親共に障害物し、ステップ 1 へ戻る．この時，α 回連続で同じパイを避けている場合はどちらかの遺伝子を，両親の片方だけプの場合ステップ 3 へ進む．
が障害物を避けている場合はその親の遺伝子を，両親共に
3. 2 番目に接触点の数が多いパイプをランダムに再生成
障害物と接触している場合はランダムに生成する．XTGし，ステップ 1 へ戻る．この時，1 番目と 2 番目のパイは，障害物に対する評価値を優先的に改善することを目標
プが α 回連続で同じパイプの場合ステップ 4 へ進む．とした交叉方法である．障害物と接触していない生成遺伝
4. ステップ 2，3 と同様に最後のパイプまで繰り返す．
子を引き継ぐことで，そのパイプは再び障害物を避けるこ
5. 全てのパイプがお互いに接触しなくなるまで，ステッとになり，全体として障害物に対する評価値が改善される
プ 1 からステップ 4 まで繰り返す．
可能性が高くなると考えられる．パイプの長さはランダム
α : 脱却数（slip number）
的に変化し，良好なものを選ぶことになる．しかし，このこの修正オペレータが有効に働くことを確認するために，方法では生成遺伝子をそのまま引き継ぐので，ある生成遺伝子の組に収束し，解の改善が望まれなくなる可能性があ 3.4 節に示す配管問題への適用を行った．Fig.6 に，あるるが，次節に述べる修正オペレータの影響でその可能性は 2 種類の致死解から実行可能解に再生成した後の評価値の変化を示す．同じ致死解から 100 回生成した分布図となっ低くなる．
)GPGTCVKQPIGPGている．パイプ 15 本の配管問題で，α = 10 とし，交叉に 
2CTGPV XTG を用いた．どちらの図においても，致死解の評価値2CTGPV )GPGTCVKQPIGPGを基準に右上の方に分布している．これは XTG では，パETQUUQXGT1DUVCENGIGPG
イプ同士の接触を考えることなく，障害物に対する評価値
9JGPEQOKPIKPEQPVCEVYKVJVJGQDUVCENG

2CTGPV VJGXCNWGQH1DUVCENGIGPGKUQPG
がよくなるように交叉しているためで，接触しないように
2CTGPV   

9JGPPQVEQOKPIKPEQPVCEVYKVJVJGQDUVCENG
VJGXCNWGQH1DUVCENGIGPGKU\GTQ 再生成することでパイプが障害物と接する部分が増えたからであると考えられる．パイプの長さの変化がなかったり
Fig. 5 : Crossover with Two Gene; XTG㪽㪶㫃㪼㫅㪾㫋㪿

本研究で用いる多目的遺伝的アルゴリズムの手順を次に㪊㪇㪇㪉㪐㪌㪉㪐㪇㪉㪏㪌㪉㪏㪇㪉㪎㪌㪉㪎㪇㪉㪍㪌㪉㪍㪇㪉㪌㪌㪉㪌㪇示す：
1. 初期集団の生成
ランダムに複数個の解を生成し，それぞれに修正オペ㪸㪽㫋㪼㫉㩷㫉㪼㪾㪼㫅㪼㫉㪸㫋㫀㫅㪾㪽㫀㫉㫊㫋

除し，それらを初期集団とする．

㪇㪽㪶㫃㪼㫅㪾㫋㪿

レータを適用し，パレート解でないものを集団から削㪉㪇㪋㪇㪍㪇㪏㪇㪽㪶㫆㪹㫊㫋㪸㪺㫃㪼㪈㪇㪇㪈㪉㪇㪊㪇㪇㪉㪐㪌㪉㪐㪇㪉㪏㪌㪉㪏㪇㪉㪎㪌㪉㪎㪇㪉㪍㪌㪉㪍㪇㪉㪌㪌㪉㪌㪇㪸㪽㫋㪼㫉㩷㫉㪼㪾㪼㫅㪼㫉㪸㫋㫀㫅㪾㪽㫀㫉㫊㫋㪇㪉㪇㪋㪇㪍㪇㪏㪇㪽㪶㫆㪹㫊㫋㪸㪺㫃㪼㪈㪇㪇㪈㪉㪇

2. 複製選択
集団からランダムに交叉のための 2 つの親を選択する．
3. 子の生成ステップ 2 で選択された両親に対し，交叉を nc 回行いそれぞれに修正オペレータを適用し，子を nc 個生成する．
4. 生存選択ステップ 3 で生成された子集団と現世代の集団を合わせた集団から，パレート解でないものを集団から削除する．
5. ある評価回数まで，ステップ 2 からステップ 4 を繰り返す．

3.4

Fig. 6 : Change of evaluation value after regenerating

パイプ１５本の配管最適化

本節では，Table.1 に示す配管最適化問題に前節で示した多目的遺伝的アルゴリズムを適用し，自動設計を行った．

離散的に変化しているのは，一部のパイプのみの再生成， また，提案した交叉方法の有効性を確認するために一様交生成遺伝子の維持を示しているもので，修正オペレータを叉（Uniformal Crossover：UC）との比較実験を行った．実施しても修正前の生成遺伝子とほとんど変わらないことが験では，予備実験により，初期集団の生成回数を 100，修分かる．

正オペレータの α を 10，交叉回数を 100，一様交叉の突3.3

然変異率は 0.1 とした．
Table. 1 : outline of the problem

解法の構成

本節では，提案したコード化／交叉を用いて関数最適化のための多目的遺伝的アルゴリズムを設計する．多目的遺伝的アルゴリズムの世代交代モデルは，非パレート解淘汰
戦略 [4] に基づくモデルを採用する．非パレート解淘汰戦
略とは，交叉により生成された子個体を親個体と合わせてパレート解でない個体を淘汰し，パレート解（他の全ての解に対して，少なくとも１つの評価基準において勝っているような解）のみで次世代の集団とするものである．

Number of all valiables
Number of all combinations

mode-1531415537,824

mode-272614279,936

mode-331238

32
1,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}

੤෷ᶿ᳸

╙㨠਎ઍ

Number of pipes
Number of valiables
Number of combinations
Total of valiable
Total of combination╙㨠 㧝਎ઍ

Fig. 7 : generation alternation model

Fig.8，Fig.9，Fig10 はそれぞれ，初期のパレート解，第100 世代（1.0 × 104 の配管を評価）のパレート解，第 1000世代（1.0 × 105 の配管を評価）のパレート解である．XTG
では，第 100 世代で障害物を避けた解を得ているのに対し，一様交叉では第 1000 世代でも解は改善されているものの完全に障害物を避けた解を得ることが出来ていない．
XTG は第 1000 代でも値の改善はわずかで，十分収束していると考えられる．Fig.11 に Fig.10 の XTG で障害物に対する評価値が 0 となった解の結果を示す．中央の立方体が障害物であり，パイプが密集したなかで，パイプ同士がお互いに接触しないで障害物を避けて配管できていることが分かる．

㪊㪇㪇㪉㪐㪌㪉㪐㪇㪽㪶㫃㪼㫅㪾㫋㪿㪉㪏㪌㪉㪏㪇㪯㪫㪞㪬㪚㪉㪎㪌㪉㪎㪇㪉㪍㪌㪉㪍㪇㪉㪌㪌㪉㪌㪇㪇㪉㪇㪋㪇㪍㪇㪏㪇㪈㪇㪇㪈㪉㪇㪽㪶㫆㪹㫊㫋㪸㪺㫃㪼

Fig. 11 : Result of 15 pipes arranged

Fig. 8 : First pareto solution㪊㪇㪇㪉㪐㪌

は refmod 節で述べたが，それと同時に，障害物に対する㪉㪐㪇評価値がなかなか改善されない場合がある．そこで次に示㪽㪶㫃㪼㫅㪾㫋㪿

㪉㪏㪌

す修正オペレータを提案する．

㪉㪏㪇㪯㪫㪞
㪬㪚㪉㪎㪌㪉㪎㪇

［障害物との接触を考慮した修正オペレータ］
障害物と接触しているパイプを優先的に修正し，全ての㪉㪍㪌㪉㪍㪇

パイプが障害物を避ける解へ修正する修正オペレータのア㪉㪌㪌

ルゴリズムの概要を示す．

㪉㪌㪇㪇

㪉㪇

㪋㪇

㪍㪇

㪏㪇

㪈㪇㪇

㪈㪉㪇

㪽㪶㫆㪹㫊㫋㪸㪺㫃㪼

Fig. 9 : Pareto solution of the 100th generation㪊㪇㪇

1. 障害物と接触しているパイプを全て再生成する．
2. すべてのパイプが障害物を避けると終了．
3. ステップ 1，2 を β 回繰り返す．
β : 回避数（avoidance number）

㪉㪐㪌㪉㪐㪇

この修正オペレータを実行すると，実行不可能な解にな㪽㪶㫃㪼㫅㪾㫋㪿㪉㪏㪌

る可能性があり，パイプの接触点の数を考慮した修正オペ㪉㪏㪇㪯㪫㪞㪬㪚㪉㪎㪌㪉㪎㪇

レータと組み合わせることで，効果が発揮されると考えら㪉㪍㪌れる．そこで，2 つの修正オペレータを合成した新しい修㪉㪍㪇正オペレータを提案する．

㪉㪌㪌［パイプ同士と障害物との接触を考慮した修正オペレータ：㪉㪌㪇㪇㪉㪇㪋㪇㪍㪇㪏㪇㪈㪇㪇㪈㪉㪇㪽㪶㫆㪹㫊㫋㪸㪺㫃㪼

Fig. 10 : Pareto solution of the 1000th generation4

障害物に対する評価値を優先的に改善する修正オペレータの提案

Modification Operator with Contact（MOC）］
1. 障害物との接触を考慮した修正オペレータを実行する．
パイプ同士が接触していなければ終了．
2. パイプの接触点の数を考慮した修正オペレータを実行する．全てのパイプが障害物と接触していなければ終了．
3. ステップ 1，2 を γ 回繰り返す．
γ : 修正数（modification number）

GA の配管問題への適用において，パイプ本数の増加に ［パラメータの扱いについて］修正オペレータにパラメータを導入しており，任意に定つれて，実行可能な初期解の生成が急激に困難になることめる必要がある．脱却数 α は，パイプ同士の接触に関する㪊㪇㪇のでパイプの本数に関係している．親の遺伝子をできるだ

㪉㪐㪌
㪉㪐㪇

あるほうが好ましいが，大きすぎるとなかなか実行可能解

㪉㪏㪌を生成できない可能性がある．回避数 β は，１つのパイプと障害物との接触に関するのでパイプの本数に関係なく，

㪽㪶㫃㪼㫅㪾㫋㪿

け引き継いだままでいるためには，できるだけ大きい値で㪉㪏㪇㪯㪫㪞
㪬㪚

㪉㪎㪌
㪉㪎㪇
㪉㪍㪌

定めることができ，障害物の大きさ，配置に依存する．修㪉㪍㪇正率 γ は，全てのパイプがお互いに接触することなく，障㪉㪌㪌㪉㪌㪇

害物を避けて配管するためのパラメータで，パイプの本数㪇に大きく依存している．パイプの本数が増えるにつれ、大㪉㪇㪋㪇㪍㪇㪏㪇㪈㪇㪇㪈㪉㪇㪽㪶㫆㪹㫊㫋㪸㪺㫃㪼

きい値となるほうがよいが，探索に時間がかかる．いずれFig. 12 : First pareto solution with MOCのパラメータにしても，パイプの本数だけでなく径の大きさ・配置にも関係があり，問題設定に大きく依存し，実験㪊㪇㪇㪉㪐㪌

的経験的に求められるものと考えられる．

㪉㪐㪇㪽㪶㫃㪼㫅㪾㫋㪿㪉㪏㪌
MOC の有効性を確認するために，配管問題に修正オペ㪉㪏㪇㪯㪫㪞
レータ MOC を適用し，比較実験を行った．実験では，3.4
㪉㪎㪌
㪬㪚
㪉㪎㪇
節と同じ配管問題に対し，アルゴリズムは同じものとし，
㪉㪍㪌
予備実験によりパラメータは初期集団の生成回数を 20，交㪉㪍㪇㪉㪌㪌叉回数を 20 とする以外は同じものとした．MOC の β を㪉㪌㪇100，γ を 100 としている．Fig.12，Fig.13 に示すように
㪇㪉㪇
㪋㪇
㪍㪇
㪏㪇
㪈㪇㪇
㪈㪉㪇
㪽㪶㫆㪹㫊㫋㪸㪺㫃㪼
MOC の効果で初期集団で障害物を避けて解を発見できている．評価時間は MOC を適用した場合の第 100 世代まで
Fig. 13 : Pareto solution of the 100th generationの時間と適用しない場合の第 1000 世代までの時間が大体
with MOC同じであった．この時の評価の値を比較すると，MOC を適用しないほうが良好な解を得ている．また，MOC を適参考文献
用した場合において第 1000 世代のパレート解が第 100 世代のパレート解と同じであり解の改善が見られなかった．
[1] Coello, C. A. C.: An Updated Survey of Evolutionary
交叉方法に関しては，XTG，一様交叉共に差はなかった．
Multiobjective Optimization Techniques: State of the
これは MOC の効果が強力であるからだと考えられる．
Art and Future Trends, Proc. Congress on Evolutionary Computation 1999, pp.3-13.

5

おわりに

本論文では，空間における配管問題を定式化し，問題に適したコード化/交叉方法，致死解を実行可能解に修正する修正オペレータを提案した．パイプが密に存在し障害物[2] Corne, D.W., Knowles, J.D. and Oates, M.J.: ThePareto Envelope-Based Selection Algorithm for Multiobjective Optimization, Parallel Problem Solvingfrom Nature 6 (PPSN2000),pp.839-848.の存在する配管設計問題を設定し，提案手法の有効性を示した．また，障害物を避けて配管する違う手法も提案し効果を得られたことを示した．
障害物に対する評価値とパイプの長さを評価値として多目的最適化を行ったが，実際には，ただ接触しないように配管だけでなく，作業の効率も考え配管しなければならないので，それをいかに評価するかが問題となる．パイプの本数の増加につれて探索時間が増加するので，探索時間を短縮するアルゴリズム，パラメータの設定に関してさらなる知見，改良が必要である．本論文で示した知見は，実際の現場に適用する予定である．実際の現場における本提案手法の有効性の検証は今後の課題である．

[3] 小野 功, 佐藤 浩, 小林 重信：単峰性正規分布交叉 UNDXを用いた実数値 GA による関数最適化, 人工知能学会
誌, Vol.14, No6, pp.1146-1155（1998）[4] 小林重信, 吉田幸司, 山村雅幸：GA によるパレート最適な決定木集合の生成, 人工知能学会誌 Vol.11, No.5,
pp.778-785 （1996）