4.4 Two-Stage Approaches
69
than others, and this biases the composition of the subsequent generations. The
algorithm mimics the evolution from one generation to another using the following
operators:
• Selection: Select two chromosomes, giving preference to the individuals with
higher fitness scores. Allow the selected chromosomes to pass their genes to
subsequent generations.
• Crossover: Given two chromosomes, choose portions of each chromosome
randomly and combine them so as to obtain a new valid chromosome.
• Mutation: Change portions of a chromosome randomly to increase the diversity
of the population and seek chromosomes with better fitness.
In this way, the overall fitness of consecutive generations improves. Once the
improvement in fitness between subsequent generations is sufficiently small, the
algorithm has converged to a final generation, which is a set of solutions for the
problem. In our application, this gives a population of layouts that includes the best
layouts found by the algorithm.
For the UA-FLP, given the final population and the corresponding chromosomes
with best fitness scores, if the chromosomes represent sequence-pairs, then we
directly have the relative positions of the departments, and we can proceed to the
second stage.
Sequence-pairs are not the only way to encode layouts in chromosomes. For
example, we can also use the absolute position (x i , y i ) and the shape parameter ρ i of department i as the information in the chromosome using the vector
(x 1 , y 1 , ρ 1 , x 2 , y 2 , ρ 2 , . . . , x n , y n , ρ n ). In this case, we need to recover the relative
position of the departments. One way to do this is to use the Delaunay triangulation
as described in Sect. 4.4.1. Alternatively, the variables (α ij , β ij ) can be assigned
values according to the positioning of department j in one of the four sectors around
department i, as depicted in Fig. 4.6.
Another possibility is to force the separation of departments in the direction in
which they overlap less. To do this, we compute
max{x i − x j , x j − x i , y i − y j , y j − y i }.
(4.34)
The expression giving the largest value establishes the direction in which we require
the departments to be separated. The relative positions of the departments are
obtained by making the variables (α ij , β ij ) equal to 0 or 1 according to Fig. 4.4.
Fig. 4.6 Relative position
given by the chromosomes
i
•
(1, 0)
(0, 1)
(0, 0)
( 1, 1)
69
than others, and this biases the composition of the subsequent generations. The
algorithm mimics the evolution from one generation to another using the following
operators:
• Selection: Select two chromosomes, giving preference to the individuals with
higher fitness scores. Allow the selected chromosomes to pass their genes to
subsequent generations.
• Crossover: Given two chromosomes, choose portions of each chromosome
randomly and combine them so as to obtain a new valid chromosome.
• Mutation: Change portions of a chromosome randomly to increase the diversity
of the population and seek chromosomes with better fitness.
In this way, the overall fitness of consecutive generations improves. Once the
improvement in fitness between subsequent generations is sufficiently small, the
algorithm has converged to a final generation, which is a set of solutions for the
problem. In our application, this gives a population of layouts that includes the best
layouts found by the algorithm.
For the UA-FLP, given the final population and the corresponding chromosomes
with best fitness scores, if the chromosomes represent sequence-pairs, then we
directly have the relative positions of the departments, and we can proceed to the
second stage.
Sequence-pairs are not the only way to encode layouts in chromosomes. For
example, we can also use the absolute position (x i , y i ) and the shape parameter ρ i of department i as the information in the chromosome using the vector
(x 1 , y 1 , ρ 1 , x 2 , y 2 , ρ 2 , . . . , x n , y n , ρ n ). In this case, we need to recover the relative
position of the departments. One way to do this is to use the Delaunay triangulation
as described in Sect. 4.4.1. Alternatively, the variables (α ij , β ij ) can be assigned
values according to the positioning of department j in one of the four sectors around
department i, as depicted in Fig. 4.6.
Another possibility is to force the separation of departments in the direction in
which they overlap less. To do this, we compute
max{x i − x j , x j − x i , y i − y j , y j − y i }.
(4.34)
The expression giving the largest value establishes the direction in which we require
the departments to be separated. The relative positions of the departments are
obtained by making the variables (α ij , β ij ) equal to 0 or 1 according to Fig. 4.4.
Fig. 4.6 Relative position
given by the chromosomes
i
•
(1, 0)
(0, 1)
(0, 0)
( 1, 1)