68
4 Layout of a Single Floor
centres of i and j are connected by an edge in the Delaunay triangulation. We have
the following two requirements:
• If |x i − x j | ≥ |y i − y j | and x i ≥ x j , then we enforce that i is to the right of j , so
the second-stage model will include the linear constraint
x j +
1
2
w j ≤ x i −
1
2
w i .
However, if x i < x j , then we require that i is to the left of j , and we instead use
the constraint
x i +
1
2
w i ≤ x j −
1
2
w j .
• If |y i − y j | ≥ |x i − x j | and y i ≥ y j , then we want to place i above j , so we use
the constraint
y j +
1
2
h j ≤ y i −
1
2
h i ,
whereas if y i < y j , then we locate i below j :
y i +
1
2
h i ≤ y j −
1
2
h j .
4.4.2 First Stage: Method Based on Genetic Algorithm
An alternative approach to establish the relative positions between departments is
to use a genetic algorithm (GA). GAs are a type of evolutionary algorithm and are
based on the concepts of genetics and natural selection. They can be used to generate
high-quality solutions for optimization problems that are beyond the ability of exact
algorithms.
A GA works with a population of individuals and a set of rules to simulate
the process of natural selection in the sense that individuals with higher fitness
can generate more offspring than others can. Each individual is described by a
chromosome, which is mathematically represented as a vector with elements from a
suitable set. For example, for layout problems, a possible layout can be represented
using sequence-pairs, and the corresponding chromosome for that layout would be
a vector containing the sequences Γ + and Γ − from its sequence-pair representation.
A fitness score is given to each individual corresponding to its ability to compete.
In the layout application, the fitness is the value of the objective function for that
layout, i.e., the total connectivity cost between pairs of departments for the layout
encoded in the chromosome.
Starting with a given initial generation of individuals, the chromosomes of
each generation with better fitness scores are given more chance to reproduce
4 Layout of a Single Floor
centres of i and j are connected by an edge in the Delaunay triangulation. We have
the following two requirements:
• If |x i − x j | ≥ |y i − y j | and x i ≥ x j , then we enforce that i is to the right of j , so
the second-stage model will include the linear constraint
x j +
1
2
w j ≤ x i −
1
2
w i .
However, if x i < x j , then we require that i is to the left of j , and we instead use
the constraint
x i +
1
2
w i ≤ x j −
1
2
w j .
• If |y i − y j | ≥ |x i − x j | and y i ≥ y j , then we want to place i above j , so we use
the constraint
y j +
1
2
h j ≤ y i −
1
2
h i ,
whereas if y i < y j , then we locate i below j :
y i +
1
2
h i ≤ y j −
1
2
h j .
4.4.2 First Stage: Method Based on Genetic Algorithm
An alternative approach to establish the relative positions between departments is
to use a genetic algorithm (GA). GAs are a type of evolutionary algorithm and are
based on the concepts of genetics and natural selection. They can be used to generate
high-quality solutions for optimization problems that are beyond the ability of exact
algorithms.
A GA works with a population of individuals and a set of rules to simulate
the process of natural selection in the sense that individuals with higher fitness
can generate more offspring than others can. Each individual is described by a
chromosome, which is mathematically represented as a vector with elements from a
suitable set. For example, for layout problems, a possible layout can be represented
using sequence-pairs, and the corresponding chromosome for that layout would be
a vector containing the sequences Γ + and Γ − from its sequence-pair representation.
A fitness score is given to each individual corresponding to its ability to compete.
In the layout application, the fitness is the value of the objective function for that
layout, i.e., the total connectivity cost between pairs of departments for the layout
encoded in the chromosome.
Starting with a given initial generation of individuals, the chromosomes of
each generation with better fitness scores are given more chance to reproduce