経路を形質とするGAによる配管設計自動化
木村

元1 , 三隅壮太

九州大学大学院工学研究院

1.

はじめに

近年造船業界では,情報処理技術の発達に伴い，設計と製造とのシステムの一元化が模索され，昨今の熟練技能労働者の不足，若年層の労働価値観の変化に対応するために，自動化の促進，作業の省力化を図ることが必然となってきている．設計現場においては,３次元CADの発達により，３次元データを取り扱った設計～解析～生産が普及してきた．特に配管設計においては，２次元平面図では中々困難であった空間上での配管のイメージを視覚化することで容易に配管経路を確認でき，作業の能率化,効率化につながっている．しかし作業の省力化が図られているものの，未だ熟練技術者の経験に頼る部分が大きく，設計の自動化とまでは至っていない．そのため熟練技術者の行っているのと同等の設計作業をコンピュータにより自動的に行わせ，設計のさらなる省力化，また技能継承問題を解決することが期待されている．
今まで多くの配管設計自動化問題において，進化的手法を適用する研究がいくつか提案されている．伊藤
ら1）の研究では２次元空間をメッシュ分割し，セルに配管経路の位置情報を保持させ，GAにより経路の最適化を行っている．配管経路の最適化は行えているが，問題点としては経路の分岐が考慮されていない，空間が２次元に限定されているなどがある．一方池平ら2)は３次元空間において配管経路の分岐も考慮した手法を提案している．この手法ではバルブの座標と向きのみをGAにより遺伝させ，一つの世代ごとにランダムにパイプの経路を決定している．しかしその方法では熟練設計者の行っている配管経路を決定した後に適切な位置にバルブを配置するという手順を自動設計アルゴリズムとしては実現できていないため, 探索性能に限界がある．また，ランダムに経路を決定していたため，
Automatic Pipe Arrangement Design Using GA Emphasized
Character of Piping RouteHajime Kimura (kimura@nams.kyushu-u.ac.jp)

  Sota Misumi (misumi-s@nams.kyushu-u.ac.jp)

Graduated School of Engineering, Kyushu University( )

良い解が求められていても，次の世代ではパイプの経路が引きなおされ，良い経路の形質が次世代に持ち越されないデメリットが存在している．
そこで本研究では池平らの研究を受け継ぎ，配管経路の形質を保持させたまま進化的計算を行うために，エルボ（elbow: 曲がり管）の座標を遺伝子として持つ可変長染色体の表現を提案する．また本問題に適した交叉方法を提案する．数値シミュレーションにより提案手法の性能について考察する．

2.

配管設計問題の定式化ある３次元空間を指定し，材料コストやバルブの操作性などを目的に応じて最適化するために，設計変数であるパイプやバルブの位置を障害物を避けながら決定する問題を考える．本研究では，系統図に基づき機器の配置が設計者によって定められたときに，それら機器を繋ぐパイプの経路の座標，それらの点でのパイプの伸びる方向が与えられたときに，パイプ同士が交わることなく，障害物を避けるように配管経路を自動的に生成する方法を提案する．
経済的な面から考えると，パイプの長さは出来るだけ短くなることが求められ，工作上の面から考えると，できるだけ工作の手間が省かれることが求められる．
パイプ部材はJIS規格に定められており，その規格に基づいたパイプ部材をしようするのが経済的にも好ましい．パイプを直角に曲げる時は，JIS規格で定められた部材で，２本のパイプを溶接して繋げる．それに対し，任意の角度に曲げる時は，プレス機を用いて一本のパイプをその角度に曲げなければならない．この作業は手間がかかるので，本研究では，パイプは直角に曲がるもののみを対象とする．
初期解の生成方法，パイプ同士の干渉回避，障害物との交わりの回避方法は池平らの方法を用いる．そこで生成された初期解を本研究で提案した手法により最適化する．

おける接続点から他の接続点，または分岐点までの染本章ではGAシミュレータの実装について説明する． 色体と交叉させる．分岐点が突然変異する場合，接続する経路上の他の位置に変異する．接続点は固定点の我々が提案する手法は染色体設計，交叉，突然変異のため，突然変異はさせてはならない．エルボ，分岐点方法，また交叉後のパイプを直角に繋げる修正オペレ
が突然変異されるとパイプの曲がりが直角ではなくなータである．経路を表現するために，パイプの屈折場るので，変異したエルボ，または分岐点への曲がりの所であるエルボの座標と個数に注目する．エルボの数は解ごとに変化するため，可変長の染色体を設計する． 修正は修正オペレータにより行う．修正後にパイプ同士，パイプと障害物との干渉が存在する場合がある．
そのために交叉については，可変長の染色体でも可能
干渉している解は致死解とし，解を再生成する．
な方式を設計する．

3. 配管経路最適化のためのＧＡの設計

3.1

経路の染色体表現の提案

本研究では経路を表現するためにエルボのリスト形式の可変長染色体を用いる．経路における１つの接続点，または分岐から，他の接続点または分岐までの１Fig. 2 Crossover operator (Cut and Splice)
本のパイプへ1つの染色体を対応付ける．染色体の左端，右端は必ず分岐点，もしくは接続点となる．ここで言う接続点とは，機器とパイプの接続点のことであり，3.3
修正オペレータ
分岐点とはパイプとパイプが分岐する点のことである．
提案した手法により交叉を行うと，パイプ同士，接表現型と遺伝子型は Fig.1 のようになっている．この染続点同士が必ずしも直角に繋がるとは限らない．その色体は各遺伝子が一つのエルボ，または接続点，分岐ためパイプとパイプ同士，接続点と接続点同士を直角点を表し，さらに遺伝子長が可変となっている．経路中のエルボの位置を表記する上で我々はMessy GAの手 につなげる修正が必要となる．交叉後の遺伝子の接続法を応用した．Messy GAはGoldbergら3)がGAのだまし 関係の場合分けはFig3のように大まかに次の４つに分類される：問題に対する弱さを克服するために考案した手法であ1． パイプ同士が平行に繋がる場合
り，染色体の遺伝子座の位置関係が固定されておらず，2． パイプ同士が直角に繋がる場合局所解に陥りにくいという特徴を持つ．また，Messy GA
3． 接続点同士が繋がる場合を用いることにより，元々の解の特徴を大きく残した4． パイプと接続点が繋がる場合まま，次世代の解を求められる利点がある．各遺伝子座は一つのエルボの座標と，経路の中で何番目のエルボかということを保持する．

Fig.1: Representation Path and Chromosomes

3.2 交叉・突然変異
交叉は Fig.2 のようにcut&spliceを用いる．突然変異
は染色体の一つの遺伝子，すなわち一つのエルボまたは経路の終点である分岐点の座標を変更するというものを用いた．交叉においては，他の解の同一の経路にFig.3: Patterns of Modification Operator
1の場合，両方のパイプが延長，または縮小され，エルボが最大１つ増加する．２の場合，両方のパイプが延長，または縮小される．３の場合，エルボが最大２つ増加する．４の場合，パイプが延長，または縮小され，エルボが最大１つ増加する．パイプの終点が異なる染色体同士を交叉させると子の経路の終点が親の経路の終点と異なってしまう問題がある．そのための修正を行う．修正の概要は，交叉後の終点の座標を元々の親の終点の遺伝子の座標に置き換え，修正オペレータのPattern4によって直角に繋げる．

3.4

配管設計上の制約について機器からはパイプの伸びる方向が指定されている．そのため終点が機器である場合，機器からパイプの伸びる方向も考慮に入れなければならない．その場合は，Pattern1，Pattern2の方式を用いてパイプと接続点を繋げる．また，配管の分岐は必ずT字分岐にならなければならない．そのために経路の終点がエルボの位置になる
場合は致死解として，解を再生成する．

Fig.4: Piping Diagram

Table 1: Fitness of each generation

4. 計算機シミュレーション
Fig.4 に示すように船舶のバラストポンプ室の系統図に基づく配管設計を対象とした．本実験では，提案するコード化・交叉・修正オペレータが機能することを4.2 結果と考察確認することを主目的としているため，集団サイズを Table.1 より探索が進んでいくと材料コストが改善され
４，突然変異率は 0.1 とした．計算環境はOSにMicrosoft ていく様子が観察できる．Fig.5 および Fig.6 からも初WindowsXPを使用し，CPUはPentium4 (2.4GHz)，メモ 期集団から経路の無駄が省かれたへと設計案が改善さ
リー2GB，プログラム言語はjavaを用いた．Fig.6，Fig.7 れている．Fig.5 の初期集団における個体の各染色体のはそれぞれ，初期の解集団，200世代目の解集団を示す． 遺伝子数は（5,6,3,5,2,5,6,2,2,8）の計54個で，材料コス適応度には材料コストを考慮したものを用いる．Fig.8， トすなわちパイプ長合計が 45.0 であるのに対し、Fig.6
Fig.9 は，初期解集団と200世代目の解集団のそれぞれ自動配管結果の３Dモデルである．３D化にはjava3Dを用いた．白のワイヤーフレームが配管すべき空間の大きさ，黒の直方体がポンプを表している．

4.1 適応度の計算
適応度はパイプの材料コストの総和を用いる．適応度の定義は式(1)のようになる：np

f material = ∑ W k Lk Dk

(1)

k =1

Wk : k 番目のパイプの材料メッキによる重み
Lk : k 番目のパイプの長さ
Dk : k 番目のパイプの直径
n k : パイプの本数
染色体の選択はルーレット選択によって行う．に示す200世代後の個体の各染色体の遺伝子数は（2,5,4,5,4,4,4,4,2,2）の計36個で，材料コストは 36.9 であり、初期解に対して18％のコスト削減を実現している。また遺伝子数はすなわちエルボの個数と等しく，
本実験ではコスト関数には反映されないが，実際にはコストとして加算されるので少ないほうが好ましい。
本実験では適応度に材料コストのみ，集団数４，また淘汰方法に単純なルーレット選択を用いたので，解の分布は広くない．そこで今後は集団数を増加させ，他の淘汰方法を採用し，バルブの操作性などを考慮した多目的最適化を行いたいと考えている．また，今回は集団数を４で行ったので解の多様性が無くなっている．また，最適化の結果として（当然だが）経路が短くなることでバルブの配置のためのスペースが減少していることがわかる．また，実際の配管設計においては，系統ごとに一定の距離を保持させなければならない制約が存在する．そのために今後はバルブが配置可能なスペースを保持させ，かつパイプごとの距離を制約として盛り込んでいく必要がある．

・Messy GAによる交叉方法
・パイプの曲がりを直角にする修正オペレータ
また，配管経路を設計変数，適応度を材料コストとし，ポンプを保持する系統図に基づいてシミュレーション実験を行い，有効性を示した．
今後の課題としては，バルブが配置可能なスペースを保持させ，かつパイプごとの距離を制約として盛り込み，パイプを配置するアルゴリズムの開発，またバルブ配置の表現方法を確立し，パイプの位置を決定した後に，バルブの位置を適切な個所に配置するアルゴリズムの開発などがあげられる．

謝 辞
福岡造船株式会社池崎英介様には，造船設計現場においての配管設計について，本研究を行う上で多くの貴重な助言を頂きました.また,エス・イー・エー創研からは貴重な研究資料やコメントをいただきました. 感謝申し上げます．

参考文献
Fig.5 : An example of the initial generation

[1]
[2]
[3]

[4]
[5]

伊藤照明,福田収一:遺伝的アルゴリズムを用いた配管経路探索法の検討, 人工知能学会誌, VOL13, No5, pp.791—802, 1998.
池平怜史, 木村元：バルブ操作性を考慮した配管自動設計手法の開発, 日本船舶海洋工学会論文集,第9号, pp.231-236, 2009.
D.E.Goldberg, K.Deb, H,Kapupta and G.Harik: Rapid, Accurate
Optimization Of Difficult Problems Using Fast Messy GeneticAlgorithms, Proc.5th Int.Joint Conf.On Genetic Algorithms, pp.56--64,1993.
池平怜史, 木村元：機器配置図・系統図に基づく配管自動設計手法の開発, 日本船舶海洋工学会論文集, 第9号, pp.223--229, 2009.
小野 功:形質遺伝を重視した遺伝的アルゴリズムによる最適化,
東京工業大学,博士論文, 1997.

付 録文献 2)に基づく初期集団を生成する方法をここにまとめる．
【パイプ経路のパターン化】

パイプ経路は,始点・終点を結ぶように線分を組みthFig.6 : An example of the 200 generation

5. おわりに
本論文では配管経路設計のために，以下の手法を用いてGAシステムを実装する方法を提案した：・エルボのリスト型の染色体表現合わせものであると考えることができる．ここで，パイプ経路の始点・終点は，位置座標と経路の延びる方向（方向ベクトルと呼ぶ）を持つ．始点・終点を結ぶことができる線分の長さ・数の組み合わせは無限に存在する．そこで，組み合わせの自由度を限定するために，パイプ経路の形をパターン化することを考える．
言い換えるならば，始点・終点を結ぶための線分の数・

位置関係をいくつかのパターンに限定することを考える．
まず，始点・終点の方向ベクトルの関係から，６つのパターンに分類する．次に，それぞれのパターンについて，節点の数を考慮して分類すると，始点・終点を結ぶパイプ経路の形を定めることができる．ここで，この経路の形を曲がり生成パターンと呼ぶ．節点の数の定め方に関して，節点の数が増加するとそれだけパイプ経路の自由度が増加し，それだけさまざまな形をとることができることになるが，探索するパラメータも増加することになる．また，工作性の観点から考えても節点の数はできるだけ少ないほうが好ましい．そこでパイプ同士の干渉および障害物との交わりを避けるパイプ経路を生成できると考えられる最小限の節点の数に限定する．この曲がり生成パターンとパイプ直線部長さを定める実数ベクトルを与えることで，パイプ経路を生成することが可能となる．
【パイプ分岐経路生成アルゴリズム】
Fig.7 に示すように，まず接続点の中から始点として1 点選択し，それ以外の接続点を終点とする．次に，終点を 1 点選択し，その点と始点を結ぶ配管経路を生成する．そして,生成した経路の屈曲点を新たな始点とし,始点と終点からそれぞれ 1 点ずつ選択し，それらを結ぶ配管経路を生成する．同様の手順を全ての終点が選択されるまで繰り返す．このような手順により，分岐を考慮した配管経路を効率的に生成することができる．

Fig. 7: A branch generation algorithm