多目的遺伝的アルゴリズムを用いた配管自動設計
平 怜 史****
正員 池 崎 英 介

学生員 池木正員 梶正員村原宏

元**
之**

Automatic Design for Pipe Arrangement using Multi-objective Genetic Algorithms
bySatoshi Ikehira， Student Member
Eisuke Ikezaki， Member

Hajime Kimura， Member
Hiroyuki Kajiwara， Member

SummaryThis paper presents an automatic design method for pipe arrangement. A pipe arrangement design problem is proposed for aspace in which many pipes and objects co-exist. This problem includes large-scale numerical optimization and combinatorial
optimization problems, as well as two criteria. For these reasons, it is difficult to optimize the problem using usual optimization
techniques such as Random Search. Therefore， multi-objective genetic algorithms (GAs) suitable for this problem are developed.
A pipe is characterized by both a pattern of generation and numerical parameters. The former describes the way the pipe
bends and the latter details the length of the straight parts. For this reason, a combination of the pattern of generation and thenumerical parameters is used for the solution representation and a new method of crossover is proposed that takes into accountinterference with obstacles. As the number of pipes increases, it becomes rapidly more difficult to find feasible solutions wherepipes do not interfere with each other. Therefore, two modification operators that transform infeasible solution candidates into
feasible ones are introduced. One operator modifies the pipe having a lot of interferences with other pipes so that it will notinterfere with them, and the other is related with the operation that modifies the pipe that travels through obstacles. Although there
are cases in which pipes cannot completely avoid obstacles in practical designs, this situation is taken into consideration by thisdesign process.
The proposed method for optimizing a pipe arrangement efficiently is demonstrated through several experiments, and remarks
are provided for applying this methodology to a practical pipe arrangement design.

未だ設計者の経験に頼る部分が大きく、自動化とまでは到っ1．緒

言ていないのが現状であり、配管自動化に関する研究はほとんど報告されていない。

近年造船業界では、情報処理技術の発達に伴い、設計と製本研究では、パイプが密に存在し、障害物を避けて配管し造とのシステムの一元化が模索され、昨今の熟練技能労働力なければならない空間での配管設計問題を定式化する。本問の不足、若年層の労働価値観の変化に対応するために、自動題は、大規模な数値最適化と組合せ最適化の複合問題かつ多化の促進、作業の省力化を図ることが必然となってきている。

目的最適化問題となっており、通常の最適化手法では解くの設計現場においては、3 次元 CAD の発達により、3 次元デが困難である。

ータを取り扱った設計～解析～生産が普及してきた。特に配多目的最適化問題は、多くの実問題で直面する非常に重要

管設計においては、2 次元平面図ではなかなか困難であったな問題であり、一般に完全最適解を得ることはできないため、空間上での配管のイメージを視覚化できることで、容易に配トレードオフを表す解の集合であるパレート最適解という管経路を試行錯誤でき、作業の能率化・効率化・省力化に繋概念を用いて解探索を行う1) 2)。GA 3) 4) は、自然界におけるがっている。しかし、作業の省力化が図られているものの、生物の進化をモデル化した確率的最適化手法の一つであり、脚注の余白を明けるには、マウス等によりこのレイアウト枠を選んだ後、メニューバーより「ツール」ー「マクロ」と実行し、マクロ一覧の中の「additem」マクロを実行してください。このテキストボックスは残りますが、印刷の際にこの上から上書きされるので、ご心配ありません。

GAを多目的へ拡張した多目的GAでは、評価項目の優先度を定義することなく、一度の試行により幅広い領域の解候補を得ることができ、パレート解を効率的に求める強力な方法として注目されている。そこで、配管設計問題に適した多目的遺伝的アルゴリズム（Multi-objective Genetic Algorithms :MOGA）を提案し、実験によりその有用性を示す。

イプは交わっている。
しかし実際の設計では、パイプを繋ぐ際フランジと呼ばれ2．配管設計問題の定式化る部材を用い、その大きさも考慮しなければならない。フランジの大きさはパイプの径によって定まっており、その大き2. 1 パイプの経路の生成さを考慮して交わりを判断する。

ある 3 次元空間を指定し、その空間内で障害物を避け、パイプの長さの総和（ f _ length ）が短くなるように配管する問
題を考える。本研究では、系統図に基づき機器の配置が設計者によって定められた時に、それら機器を繋ぐパイプの経路を自動設計することを考える。つまり、パイプの始点、終点の座標、それらの点でのパイプの伸びる方向（方向ベクトル）が与えられた時に、パイプ同士が交わることなく、障害物を避けるように配管経路を自動的に生成する方法を提案する。
経済的な面から考えると、パイプの長さはできるだけ短くなることが求められ、工作上の面から考えると、できるだけ工作の手間が省かれることが求められる。パイプ部材はＪＩＳ規格に定められており、その規格に基づいたパイプ部材をFig.1

Case-1 (opposite way).

使用するのが経済的にも好ましい。パイプを直角に曲げる時は、JIS 規格で定められた部材で、2 本のパイプを溶接して繋げる。それに対し、任意の角度に曲げる時は、プレス機を用いて 1 本のパイプをその角度に曲げなければならない。この作業は非常に手間がかかるので、パイプは直角に曲がるものとし、設計上の要求（下水管等は自然に流れるようにある傾斜をつけて配管する）がある場合は、方向ベクトルで与える。
始点、終点を結ぶ配管経路は 3 次元空間上に無限に存在する。そこで配管経路の自由度を限定するために、経路をパターン化することを考える。始点、終点を結ぶ配管経路を設計するということは、折れ曲がる点（節点）を定めることであ

Fig.2

Case-2 (right-angled way).

る。方向ベクトルの値によって Case-1（向き合う方向）、Case-2（直角方向）、Case-3（同じ方向）に分け、節点の数、始点終点からの位置関係によって生成パターン（経路の形状）を Fig.1、Fig.2、Fig.3 に示すように定める。パイプは生成パターンとパイプ直線部長さを特徴づける最大 3 個の実数値により一意に定まる。節点の数をさらに増やすことで生成パターンを増やすことも考えられるが、工作上、節点の数

Fig.3

Case-3 (same way).

は少ないほど好ましく、パイプ同士の接触を避け、障害物との交わりをできるだけ避けることができる最小限の節点の数で設計する。

2. 3 障害物との交わり
障害物は直方体で与え、直方体を有限個配置することで、複雑な形状の障害物も表現することができる。空間内に障害2. 2 パイプ同士の交わり物が存在する場合、それを避けて配管しなければならない。

2 つのパイプの半径をそれぞれ r0 , r1 とする。また、それぞ障害物と交わった場合は致死解として解を再生成する方法

れのパイプの中心線の間の最短距離を d とすると、それらが考えられるが、実際の設計では、障害物の配置やパイプののパイプが存在する範囲で、 d ≤ r0 + r1 の時、この２つのパ制約条件によって完全に避けることができない場合が存在する。例えば、パイプのメンテナンス等のために人間が通れトルを組合せたもの（生成遺伝子）を遺伝子とする個体を生るスペースなどがそれに当たる。この時、完全に避けなくて成する。交叉方法としては、2 遺伝子交叉（Crossover with Twoもよいが、できるだけスペースを作らなければならない。そGene; XTG）を提案する。XTG は、Fig.5 に示すように、障こで、障害物に対してのペナルティ関数を提案し、ペナルテ

害物との接触情報を持った遺伝子（障害物遺伝子）を用いてィ関数から与えられる評価値を最小化（最良化）することで1 つの子を生成する。基本的には親の生成遺伝子のどちらか障害物を避けて配管することを考える。

を引き継ぐか新しい生成遺伝子が生成され、障害物遺伝子は［障害物に対するペナルティ関数］

子がどの生成遺伝子を持つようになるのか補助的に用いらパイプが障害物の中心を通過ほど、また障害物内を通過すれる。あるパイプについて、両親共に障害物を避けている場るパイプの長さが長いほど評価としては悪くなるという観合はどちらかの遺伝子を、両親の片方だけが障害物を避けて点から、以下の評価式を提案する。

いる場合はその親の遺伝子を、両親共に障害物と接触していnpる場合はランダムに生成する。XTG は、障害物に対する評

nof _ obstacle = ∑∑ (bkl − akl + Al )価値を優先的に改善することを目標とした交叉方法である。

k =1 l =1

障害物と接触していない生成遺伝子を引き継ぐことで、そのk ：パイプの番号l ：障害物の番号
n p ：パイプの本数
no ： 障害物の数
bkl ：パイプ- k が障害物- l 内を通過している部分の長さ
a kl ：パイプ- k が障害物- l 内を通過している部分を節点

パイプは再び障害物を避けることになり、全体として障害物ごとに切断し、それぞれと重心との距離の平均に、2 つの親から 1 つの子を生成する。子の生成遺伝子は親に対する評価値が改善される可能性が高くなると考えられる。パイプの長さはランダム的に変化し、良好なものを選ぶことになる。XTG の有効性を確認するために，伝統的な交叉方法である一様交叉に基づく交叉（Uniform Crossover;UX）も設計する。UX は、Fig.6 に示すように、XTG と同様の生成遺伝子のどちらかを等しい確率で引き継ぐ。

Al ：障害物- l の重心と頂点との距離

しかし、これらの交叉方法では生成遺伝子をそのまま引き継ぐので、ある生成遺伝子の組に収束し、解の改善が困難となる可能性があるが、次に述べる突然変異、修正オペレータの効果によりその可能性は低くなる。

Fig.4

An example calculation of the obstacle function.

3．配管最適化のための多目的 GA の設計
Fig.5

Crossover with Two Gene; XTG.

3. 1 コード化／交叉設計：
Crossover with Two Gene (XTG) の提案
関数最適化において伝統的に広く用いられてきたコード化（coding）／交叉（crossover）はビットストリング上で定Fig.6 Uniform Crossover; UX.

義されたバイナリーコーディングおよびグレイコーディン
グと、その上で定義された一点交叉、二点交叉、一様交叉で3. 2 突然変異設計ある。近年では、表現型空間と遺伝子型空間の位相構造が一突然変異（mutation）は、解集団内に存在しない遺伝子を致した実数ベクトルをコード化の方法として採用し、その上発生させ、より広い探索空間内の探索、局所解からの脱却に

5)で交叉方法を実装した実数値GAが提案されている 。本問寄与し、GA の設計において非常に重要なオペレータである。

題では、1 本のパイプは曲がり生成パターンと直線部パイプ

Fig.7 に示すように、まず 2 つの親のどちらかが選ばれ、長さにより一意に定まり、組合せ最適化と数値最適化の複合選ばれた親に対し、ある突然変異率（mutation rate）で定め問題となっており、従来のコード化手法では困難である。

られた一定確率で突然変異が各遺伝子に適用され、新たに生そこで、染色体のコード化として生成パターンと実数ベク成遺伝子がランダムに生成される。

わせてパレート解でない個体を淘汰し、パレート解（他の全ての解に対して、少なくとも１つの評価基準において勝っているような解）のみで次世代の集団とするものである。
Fig.7

An example of mutation.

3. 3 修正オペレータ
3. 3. 1 修正オペレータの必要性
GA の配管問題への適用においては、パイプ本数の増加につれて、パイプ同士が交わっていない実行可能解の生成が急激に困難になるという問題が生じる。解の生成においては、生成パターンとパイプの直線部長さを特徴づける実数値を一様乱数に従って、ランダムに生成するため、パイプ本数の増加に伴い、パイプがお互いに交わっている可能性が高くな

Fig.8

Generation Alternation Model.

る。例えば、問題設定にもよるが、ある 5 本の配管問題の場合、ランダムに 100 個生成するのに数十秒だが、15 本の場

3. 5 パイプ 15 本の配管最適化合は、丸一日かけても生成できない。GA は多様な実行可能

本節では、Table 1 に示す配管最適化問題に前節で提案し解を生成し、交叉・突然変異・選択を繰り返すことで、解をた多目的遺伝的 GA を適用し、自動設計を行う。また、提案改善していく。そこで、できるだけ短時間に一様ランダム性した交叉 XTG の有効性を確認するために、一様交叉 UX とを保ったまま実行可能解を生成できる工夫が望まれる。そこの比較実験を行う。

で、パイプ同士の接触点の数を考慮することで、生成された実験では、予備実験により、初期集団の生成回数を 100、実行不可能なパイプをもとの性質をできるだけ残すように、

MOC の α を 10、交叉回数を 100、突然変異率は 0.1 とする。

なるべく少ない修正で実行可能解へ修正する修正オペレー

Fig.9、Fig.10、Fig.11 はそれぞれ、初期のパレート解、タ（Modification Operator on Contact; MOC）を提案する。

第 100 世代（ 1.0 ×104 の配管を評価）のパレート解、第 1000

3. 3. 2 MOC のアルゴリズムの概要

世代（ 1.0 × 105 の配管を評価）のパレート解である。XTG で生成された致死解を実行可能解へ修正する修正オペレー

は、第 100 世代で障害物を避けた解を得ているのに対し、タのアルゴリズムの概要を以下に示す。

UX では第 1000 世代でも解は改善されているものの完全に１．接触点の数が多い順にパイプに順番をつける。

障害物を避けた解を得ることが出来ていない。XTG は第２．1 番目に接触点の数が多いパイプをランダムに再生成

1000 代でも値の改善はわずかで、十分収束していると考えし、ステップ 1 へ戻る。この時、接触点が最も多いパイられる。Fig.12 に Fig.11 の XTG で障害物に対する評価値がプが α 回連続で同じパイプの場合ステップ 3 へ進む。

0 となった解の結果を示す。中央の立方体が障害物を表し、３．1 番目と 2 番目に接触点の数が多いパイプをランダムにパイプが密集したなかで、パイプ同士がお互いに接触しない再生成し、ステップ 1 へ戻る。この時、1 番目と 2 番目のパイプが α 回連続で同じパイプの場合ステップ 4 へで障害物を避けて配管できていることが分かる。
Table 1

Problem specification.

進む。
４．ステップ 2、3 と同様に最後のパイプまで繰り返す。
５．全てのパイプがお互いに接触しなくなるまで、ステップ1 からステップ 4 まで繰り返す。

α ：脱却回数（slip number）

Case-1Case-2Case-3The number of pipes

573

The number of variables

321

The number of combinations

1462

The total number of variables

15143537,824279,936

8

The total number of combinations

3. 4 解法の構成

The number of all variables

本節では、提案したコード化／交叉を用いて関数最適化のThe number of all combinations

ための多目的遺伝的アルゴリズムを設計する。多目的遺伝的Space where pipes arranged:

アルゴリズムの世代交代モデルは、Fig.8 に示すような非パ6)レート解淘汰戦略 に基づくモデルを採用する。非パレート解淘汰戦略とは、交叉により生成された子個体を親個体と合321,204,450,394,000{(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}

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

GA の配管問題への適用において、パイプ本数の増加につれて、実行可能な解の生成が急激に困難になることは 3.3 節で述べたが、それと同時に、障害物に対する評価値がなかなか改善されない可能性がある。そこで、障害物との交わりを考慮することで障害物に対する評価値を改善する修正オペレータ（Modification Operator on Obstacle; MOO）を提案する。
Fig.9

First pareto solutions with the MOC.
4. 1 MOO のアルゴリズムの概要
障害物と交わっているパイプを優先的に修正し、全てのパイプができるだけ障害物を避けるように解を修正する修正
オペレータのアルゴリズムの概要を以下に示す。
１．MOC を適用する。
ａ．すべてのパイプが障害物と交わっていなければ終了。
ｂ．そうでなければ、ステップ 2 へ。
２．障害物と交わっているパイプを全て再生成する。
ａ．すべてのパイプが障害物と交わっていなければステFig.10Pareto solutions in the 100th generation with the MOC.

ップ 3 へ。
ｂ．そうでなければ、このステップを繰り返す。このステップが β 回繰り返された場合、ステップ 3 へ。
３．このステップが γ 回繰り返された場合、MOC を適用して終了。そうでなければ、ステップ 1 へ。

β ：回避回数（avoidance number）
γ ：修正回数（modification number）
4. 2 有効性の確認
MOO の有効性を確認するために、3.5 節の配管問題に修Fig.11

Pareto solutions in the 1000th generation with the MOC.

正オペレータ MOO を適用し、比較実験を行った。実験では、アルゴリズムは同じものとし、予備実験によりパラメータは初期集団の生成回数を 20、交叉回数を 20 とする以外は同じものとした。MOO の β を 100、γ を 100 としている。Fig.13、Fig.14 に示すように、MOO の効果により初期集団で障害物を避けた解を発見できている。評価時間は MOO を適用した場合の第 100 世代までの時間と MOC を適用した場合の第1000 世代までの時間が大体同じであった。しかし、この時の評価値を比較すると、MOC を適用した場合のほうが良好な解を得ている。これは、探索のアルゴリズムの観点から考えると、障害物と交わっている解も有効な情報を保持している可能性があり、評価値を与えて実行可能解にすることで、探索の効率が上がる可能性を示している。また、MOO を適用した場合において第 1000 世代のパレート解が第 100 世代のパレート解と同じであり解の改善が見られなかった。交叉Fig.12

Result of 15 pipes arranged.

方法に関しては、XTG、一様交叉共に差はなかった。これ

は、交叉により生成された解候補に対して MOO を適用する

5．結言と再生成されるパイプの数が増加し、MOC に比べ交叉により引き継いだ性質を破壊してしまうからであると考えられ本論文では、パイプが密集し、障害物が存在する空間における配管設計問題を定式化した。本問題は大規模な組み合わる。

せ最適化、数値最適化の複合問題かつ多目的最適化問題になっており、一般的な最適化手法を適用するのは困難であった。
そこで、コード化/交叉方法、致死解を実行可能解に修正する修正オペレータを提案し、本問題に適した多目的 GA を設計した。次に、パイプが密に存在し、比較的大きな障害物が存在する配管設計問題を設定し、提案手法の有効性を示した。
また、障害物を優先的に避けるように解を修正する修正オペレータを提案し、効果を得られることを示した。
障害物に対する評価値とパイプの長さを評価値として多Fig.13

First pareto solutions with the MOO.

目的最適化を行ったが、実際の設計では、取り付け作業の効率、パイプの径、平行配管など他に考慮すべき項目が多数存在する。いかにそれらを評価し、アルゴリズムに取り組むかが今後の課題である。本研究では、機器の配置から始点・終点が与えられた場合に経路を自動設計する手法を提案したが、機器の配置も含めた最適化を行うことで、配管する空間の最小化も期待できる。また、探索時間を短縮するアルゴリ
ズム、パラメータの設定に関してさらなる知見、改良が必要である。本論文で示した知見は、実際の現場に適用する予定である。実際の現場における本提案手法の有効性の検証は今

Fig.14

Pareto solutions in the 100the generation with the MOO.

後の課題である。

参 考 文 献4. 3 パラメータの扱い
修正オペレータにパラメータを導入しており、任意に定める必要がある。そこで、それらに対する知見を述べる。
［脱却回数： α ］
パイプ同士の接触に関するのでパイプの本数に関係している。親の遺伝子をできるだけ引き継いだままでいるためには、できるだけ大きい値であるほうが好ましいが、大きすぎ

1) Coello, C. A. C., An Updated Survey of Evolutionary
Multiobjective Optimization Techniques, State of the Art andFuture Trends, Proc. Congress on Evolutionary Computation1999, pp.3-13.

2) Corne, D.W., Knowles, J.D. and Oates, M.J.:The Pareto

るとなかなか実行可能解を生成できない可能性がある。

Envelope-Based Selection Algorithm for Multiobjective［回避回数： β ］

Optimization，Parallel Problem Solving from Nature 6

１つのパイプと障害物との接触に関するのでパイプの本数に関係なく、定めることができ、障害物の大きさ、配置に依存する。
［修正回数： γ ］
全てのパイプがお互いに接触することなく、障害物を避け(PPSN2000)，pp.839-848.
3) 小野 功：形質遺伝を重視した遺伝的アルゴリズムによる最適化，東京工業大学，博士論文（1997）
4) 柳浦 睦憲， 茨木 俊秀：組合せ最適化―メタ戦略を中心として―， pp.79-85， 朝倉書店（2001）て配管するためのパラメータで、パイプの本数に大きく依存

5) 小野 功， 佐藤 浩， 小林 重信：単峰性正規分布交叉している。パイプの本数が増えるにつれ、大きい値となるほUNDX を用いた実数値 GA による関数最適化， 人工うがよいが、探索に時間がかかる。

知能学会誌， Vol.14， No.6， pp.1146-1155（1998）

いずれのパラメータにしても、パイプの本数だけでなく径

6) 小林重信， 吉田幸司， 山村雅幸：GA によるパレートの大きさ・配置にも関係があり、問題設定に大きく依存し、最適な決定木集合の生成， 人工知能学会誌 Vol.11，実験的経験的に求められるものと考えられる。

No.5， pp.778-785 （1996）