２００５．３．１７

多目的遺伝的アルゴリズムを用いた配管設計
九州大学工学部地球環境工学科
船舶海洋システム工学コース○池平 怜史
池崎 英介

木村
元
梶原 宏之

アウトライン
１．研究の背景と目的
２．配管設計問題の定式化
３．多目的遺伝的アルゴリズムの提案
４．シミュレーションと結果
５．研究の成果と課題

研究背景

自動化の促進・作業の省力化

３次元CADの発達

試行錯誤が容易→ 作業の省力化・効率化

自動化までは到っていない

研究目的

配管設計の自動化

１．配管設計問題を定式化
大規模な多目的最適化問題
２．本問題に適した多目的遺伝的アルゴリズムの提案アウトライン
１．研究の背景と目的
２．配管設計問題の定式化
３．多目的遺伝的アルゴリズムの提案
４．シミュレーションと結果
５．研究の成果と課題

パイプの設計

・パイプ同士の交わり・障害物

設計者が始点・終点での制約条件を考慮して、座標・方向ベクトル経路を自動設計を定めた時

節点経路は無限に存在
始点

方向ベクトル終点

経路をパターン化

経路のパターン化
１．始点・終点の方向ベクトルの向きの関係
向き合う方向直角方向

同じ方向

mode-1mode-2mode-3

２．折れ曲がる点（節点）の数
３個

５個

節点数の増加２個
自由度の増加３個

４個３個

障害物を避けることができる
最小限の節点数に定める

x2

x1

pattern-8

pattern-11

mode-1

pattern-0

pattern-2

pattern-5

x0

pattern-1

pattern-3

pattern-6

pattern-9

pattern-12

pattern-4

pattern-7

pattern-10

pattern-13

x0

x0
節点：３個

組合せ：１４

節点：５個

変数：３

パイプを一意に定めることができるmode-2

pattern-0

x0

mode-3x1

pattern-1

pattern-3

pattern-2

pattern-4

x0

pattern-0

x0

pattern-1

pattern-5

節点：２個 節点：３個 節点：４個組合せ：6

変数：2

節点：３個

組合せ：2

変数：１

障害物（直方体）に対する評価式の提案（１）
人が通るようなスペースも指す
始点・終点の位置によっては、障害物を完全に避けることができない

できるだけ障害物を避けるように配管始点が障害物の中

評価式の提案

評価値を最小化

最適化問題

障害物（直方体）に対する評価式の提案（２）nonp

f _ obstacle = ∑∑ (bkl − akl + Al )l =1 k =1

bkl ： k 番目のパイプが l 番目の障害物内を通過している長さ
akl ： k 番目のパイプが l 番目の障害物内を通過している部分を節点ごとに切断しそれぞれの重心との距離の平均
Al ： l 番目の障害物の重心と障害物の頂点との距離
障害物の数
no ：評価値：８．３７
評価値：１１．２０
評価値：８．３７
評価値：１０．３７
n p ： パイプの本数

最小値

障害物の中心を通るほど、交わる部分 （障害物と交わらない）が長いほど評価値は悪く（大きく）なる＝ ０

障害物（直方体）に対する評価式の提案（２）nonp

f _ obstacle = ∑∑ (bkl − akl + Al )l =1 k =1

bkl ： k 番目のパイプが l 番目の障害物内を通過している長さ
akl ： k 番目のパイプが l 番目の障害物内を通過している部分を節点ごとに切断しそれぞれの重心との距離の平均
Al ： l 番目の障害物の重心と障害物の頂点との距離
障害物の数
no ：評価値：８．３７
評価値：１１．２０
評価値：８．３７
評価値：１０．３７
n p ： パイプの本数

最小値

障害物の中心を通るほど、交わる部分 （障害物と交わらない）が長いほど評価値は悪く（大きく）なる＝ ０

障害物（直方体）に対する評価式の提案（２）nonp

f _ obstacle = ∑∑ (bkl − akl + Al )l =1 k =1

bkl ： k 番目のパイプが l 番目の障害物内を通過している長さ
akl ： k 番目のパイプが l 番目の障害物内を通過している部分を節点ごとに切断しそれぞれの重心との距離の平均
Al ： l 番目の障害物の重心と障害物の頂点との距離
障害物の数
no ：評価値：８．３７
評価値：１１．２０
評価値：８．３７
評価値：１０．３７
n p ： パイプの本数

最小値

障害物の中心を通るほど、交わる部分 （障害物と交わらない）が長いほど評価値は悪く（大きく）なる＝ ０アウトライン
１．研究の背景と目的
２．配管設計問題の定式化
３．多目的遺伝的アルゴリズムの提案
４．シミュレーションと結果
５．研究の成果と課題

本問題の特徴
直接探索法である
GAによる探索

組合せ最適化と数値最適化の複合問題
従来の関数最適化手法では困難（アニーリング法・シンプレックス法など）

パイプの長さトレードオフ障害物に対する評価値

多目的最適化問題
多目的GAによる探索

多目的遺伝的アルゴリズム（多目的GA）
設計

非パレート解淘汰戦略
交叉（小林ら、東工大）

親パレート解のみを残す

突然変異
選択

子個体淘汰

コスト
２コスト１
第 t 世代 パレート解：
他の全ての解に対して少なくとも1つの評価基準において勝っているような解

第 t+1世代

探索対象（コード化）の提案
生成パターン（組合せ）

パイプが一意に定まる変数（実数値）組み合わせたものを 探索対象（コード化）
解の構造⎡ pattern1⎢ x10⎢
実数値ベクトル ⎢ x11⎢⎣ x12

pattern2x20
x21x22

１本目

２本目

生成パターン............
............
............
............

patternn ⎤xn 0 ⎥⎥xn1 ⎥⎥xn 2 ⎦n本目

２遺伝子交叉（Crossover with Two Gene;XTG)の提案
パイプ番号 ① ② ③
一様交叉

親１の解

3 0 96 0 4子の解

親２の解

6 5 4

ランダムに再生成

親１

１ １ ０

6 7 9

親２

０ １ ０

障害物と交わっていない ： ０
交わっている ： １

XTG

子の解障害物に対する評価値を優先的に改善

修正オペレータ（Modification Operator on Contact;MOC）の提案
パイプ同士が交わっている

致死解

接触点の多いパイプを優先的に再生成

修正オペレータ
パイプ同士が交わっていない

実行可能解

できるだけ元の解の形を維持する
変わっていない

多目的遺伝的アルゴリズム（多目的GA）
修正オペレータ
非パレート解淘汰戦略
交叉（小林ら、東工大）

親パレート解のみを残す

突然変異
選択

子個体淘汰

コスト
２
コスト１
第 t 世代 パレート解：
他の全ての解に対して少なくとも1つの評価基準において勝っているような解

第 t+1世代アウトライン
１．研究の背景と目的
２．配管設計問題の定式化
３．多目的遺伝的アルゴリズムの提案
４．シミュレーションと結果
５．研究の成果と課題パイプ１５本の配管自動設計
モード

本数 変数 組合せ 変数合計 組合せ合計

mode-1mode-2mode-3５７３

３２
１

障害物の存在する範囲

１４６２１５１４
３５３７，８２４
２７９，９３６
８

合計

３２

１兆２千億

パイプが密に存在し、比較的大きな障害物が存在する問題を設定

大規模な数値最適化と組合せ最適化の複合問題である！！

初期パレート解

f_length

パイプの長さPentium ４ 2.40GHz
512MB
計算環境
WindowsXP
プログラム言語：Java
XTG

一様交叉

40

60

280
275
270
265
260
255
250
245
240
020

障害物を完全に避けた解

f_obstacle

80

100120

障害物に対する評価値

１００世代目のパレート解4（ 1.0 ×10 個の解候補を評価）
探索に要した時間：約１０分

f_length

XTG
280
275
270
265
260
255250245240

一様交叉

交叉XTGを用いた場合は、障害物を完全に避けた解を得ている

0204060f_obstacle

80100120１０００世代目のパレート解5（ 1.0 ×10 個の解候補を評価）
探索に要した時間：約６０分

f_length

XTG
280275
270
265
260
255
250
245240一様交叉

交叉XTGを用いた場合は、１００世代目と値がほとんど変わっていない
収束

020406080
一様交叉では、障害物を避けることができていない
f_obstacle

100120

配管結果
Java3Dを用いて配管結果を３次元表示するプログラムを作成した

start

パイプ１５本 障害物２個

15_2

20_1
20_3

アウトライン
１．研究の背景と目的
２．配管設計問題の定式化
３．多目的遺伝的アルゴリズムの提案
４．シミュレーションと結果
５．研究の成果と課題

研究成果
 経路を自動設計する配管設計問題を定式化した．
 本問題に適した多目的遺伝的アルゴリズムを提案し，有効性を示した．

今後の課題
 実問題に適用し，有効性の確認．
 現場での作業の効率も考えたアルゴリズムの開発．

Auto Movie start