August 24th, 2005
ICCAS 2005 Busan, Korea

Satoshi IKEHIRA*Hajime KIMURA
Hiroyuki KAJIWARA* Department of Maritime Engineering
Graduate School of Engineering
Kyushu University
Fukuoka, Japan

Contents
1．Introduction
２．Formulating Pipe Arrangement
Design Problem
３．Designing Multi-objective Genetic
Algorithms
４．Experiments and Results
５．Conclusions and Remarks

Background
Advances in CAD

Reduce labor requirements• efficiency improvement• labor saving

Automation of pipe arrangement design has not yet achieved.

ObjectiveDesign pipe arrangement automatically

１．Formulating pipe arrangement design problem
Large-scale multi-objective optimization problem
２．Designing multi-objective genetic algorithms

Contents
1．Introduction
２．Formulating Pipe Arrangement
Design Problem
３．Designing Multi-objective GeneticAlgorithms
４．Experiments and Results
５．Conclusions and Remarks

Designing Pipe Arrangement
When both origin and endpoint coordinatesand direction vectors are provided,
Piping route is automatically designed.
Nodes
OriginConsideringinterference with pipes and obstacles

End-point

Direction vectors

An infinite number of piping route

A limit is imposed on the degrees-of-freedom for the route.

Generation pattern
１．According to direction vectors
OppositeRight-angled

Same

Mode-1Mode-2Mode-3

２．According to the number of nodes
３５２

The number of nodes increases

３４３

Degrees-of freedom expands

The number of nodes should be minimized
while avoiding interference with other pipes and obstacles.

Mode-1

pattern-0

pattern-2

pattern-5x2x1

pattern-8

pattern-11x0

pattern-1

pattern-3

pattern-6

pattern-9

pattern-12

pattern-4

pattern-7

pattern-10

pattern-13

x0x0
Node: 3

Node: 5The number of combination: 14
The number of variables:
3A pipe ischaracterized uniquely.

Mode-2

pattern-0

x0Mode-3x1

pattern-1

pattern-3

pattern-2

pattern-4x0

pattern-0x0

pattern-1

pattern-5

Node: 2

Node: 3

Node: 4

The number of combination: 6
The number of variables:2

Node: 3The number of combination: 2
The number of variables:1

Evaluation function for obstacle （１）A space set aside to allow for maintenance people to passThis space is considered as an obstacle.
Need not completely avoid the obstacle

Avoid the obstacle as much as possible

Evaluation function

Minimize the evaluation value

Optimization problem

Evaluation value for obstacle （２）nonp

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

bkl : The length of intersection when the pipe k intersects the obstacle l
akl : The averaged length between the center of the gravity ofthe obstacle k and the part divided by each node of the pipe l

Al : The length between the center of the gravity
no : The number of obstacles
n p : The number of pipes

and the top of the obstacle l

Minimum value ＝ ０（All pipes not interfering with obstacles）

Evaluation values are worse
when a pipe passes through the center of an obstacle
and the length of the intersection is long.

Contents
1．Introduction
２．Formulating Pipe Arrangement
Design Problem
３．Designing Multi-objective GeneticAlgorithms
４．Experiments and Results
５．Conclusions and Remarks

Characteristic of this problem
This problem includes
numerical optimization andcombination optimization problems.

Using GA, which isdirect search method

It is difficult to optimize this problem
using usual optimization techniques.
・ Annealing method
・ Downhill simplex method, etc.
The length of pipe

Trade-off

Multi-objective
optimization problem

The Evaluation value for obstacle

Multi-objective GA

Multi-objective genetic algorithms
Pareto optimal selection strategy

designCrossover（Kobayashi,Tokyo Institute of Technology）

Mutation

Pareto solutions selected

Selection for reproduction Children

Selection for survival

Parents

Cost2
Cost-1
Generation t Pareto solution：
Generation t+1
A solution that is superior to all othersolutions in at least one criterion.

Representation
Pattern of generation

A pipe is characterized by them
Numerical parameters

A combination of them are usedas the solution representation
Solution structurePattern of generation ⎡ pattern1⎢ x10⎢
Numerical parameters ⎢ x11⎢⎣ x12
pipe 1

pattern2 ............
x20............
x21
x22
pipe 2............
............

patternn ⎤xn 0 ⎥⎥xn1 ⎥⎥xn 2 ⎦pipe nCrossover with Two Gene: XTG
Index of pipe ①

Parent- 1② ③ Uniform Crossover

3 0 9

Parent- 2

6 5 4

Parent- 1

１ １ ０

Parent- 2

3 0 4
XTG

０ １ ０Child
Generated at random

6 7 9
Child

When a pipe not interfering with obstacles： ０
When a pipe interfering with obstacles：
1The evaluation value for obstacle can be expected to be improved.

Mutation② ③

Index of pipe

① ② ③

3 0 9

Parent- 2

6 5 4

Index of pipe ①

Parent- 1Selection① ② ③
The gene to which
the mutation is appliedis generated at random.

3 0 9
Mutation rate

8 0 1
Child

Modification operator on Contact: MOC
Pipes interferewith each other.
Infeasible solution

MOC
Pipes do notinterfere witheach other.
Feasible solution

Pipes having
a lot of interferences
are modified
Change the propertiesof the originalsolution candidates
as little as possible
Not changedMulti-objective
genetic
algorithms
MOCPareto optimal selection strategy
Crossover（Kobayashi,Tokyo Institute of Technology）

Mutation

Pareto solutions selected

Selection for reproduction Children

Selection for survival

Parents

Cost2
Cost-1
Generation t Pareto solution：
Generation t+1
A solution that is superior to all othersolutions in at least one criterion.

Contents
1．Introduction
２．Formulating Pipe Arrangement
Design Problem
３．Designing Multi-objective Genetic
Algorithms
４．Experiments and Results
５．Conclusions and Remarks

Experiments
Mode-1Mode-2Mode-3The number of pipes

573

The number of variables

32

1

The number of combinations

1462

The total number of variables

15143537,824

279,936

8

The total number of combinations
The number of all variables

32

The number of all combinations

Approximately 1.2 trillion

The space where a obstacle exists

Large-scale optimization problems

We set the problem where many pipes
exist closely and a big obstacle exists.

Initial Pareto solutions
The sum total of
the length of pipe

Calculation environment
Pentium ４ 2.40GHz
512MB
Windows XPJavaBetter!!

The evaluation
value for obstacle

Pareto solutions in 100th generation
4（ 1.0 ×10 solution candidates evaluated.）
About 10 minutes for searchingPareto solutions in 1000th generation（ 1.0 ×105 solution candidates evaluated.）
About 60 minutes for searchingResults

Programming language： Java3Dstart
The number of pipes:
15
The number of obstacles: 2

15_2

The number of pipes:
20
The number of obstacles: 1

20_1

The number of pipes:
20
The number of obstacles: 3

20_3

Contents
1．Introduction
２．Formulating Pipe Arrangement
Design Problem
３．Designing Multi-objective Genetic
Algorithms
４．Experiments and Results
５．Conclusions and Remarks

Conclusions
A design problem for pipe arrangement was formulated.
 A multi-objective Genetic Algorithms suitable for thisproblem was developed.
 The effectiveness of the proposed method was verified
through several experiments.
Future works
Applying this methodology to a practical design Improvements to the proposed algorithms