LAYOUT PROBLEM OPTIMIZATION USING GENETIC ALGORITHMS


Introduction
This work presents an application of genetic algorithm to a problem of finding of an optimal layout of objects on a material stripe with the aim to reduce the total length of material used.

The problem addressed here is defined so that we want to find an optimal layout of a set of two-dimensional objects such that
   (i) the objects cannot mutually overlap and
   (ii) the length of the used piece of the material is minimal.
The material stripe has defined its length L and width W. For the sake of simple representation and manipulation of the objects we consider only rectangular shapes, which use the same grid structure as the material stripe.

In order to reduce the total search space the problem was solved as an ordering problem. The algorithm generates sequences of objects and uses a localization algorithm according to which the objects are properly placed on the grid in the given order. So the goal is to find an optimal order, which makes the objects lay on the stripe in the most compact way.

Localization Algorithm
The localization algorithm searches the partially covered grid for a free space, where the next object can be placed - it tries to find the left-most and top-most available position on the grid.

              
Application of the localization algorithm to three different objects


Fitness
The primary goal is to find the shortest possible layout with the least scrap material. The measure is a compound of two components:
    - a total length of the layout, and
    - a total amount of unused pieces of the material inside the layout.

Genetic operators
This work focuses on representation issues of the problem and on designing of such crossover operators that would allow building blocks formation and facilitate their mixing.
Optimally the crossover should support useful inheritance and transfer of partial subsolutions from the parents to their offspring.

This can be hardly achieved here. Note that the adjacency of two objects in a chromosome does not necessarily imply the actual spatial adjacency of the objects on the grid.
For example see the links between objects in pairs J-B and P-N in the first parent in figure below. Objects J and B are neighbors in the chromosome while they are far away from each other on the grid. On the other hand P and N lie close together on the grid even though they are not directly linked in the chromosome.

        
Simple 1-point crossover


1-point crossover. Simple 1-point crossover works so that the offspring chromosome gets the head part of one parental chromosome and the rest is filled with the remaining objects in an order as they appear in the other parent.
Due to the reasons described above it does not work well regarding the inheritance of solution parts, see the figure.

Reordering algorithm. The situation described above can be improved to some extent when using an adjusted ordering of objects, which takes into account the actual linkage and ordering of objects on the grid. The main goal is to order the objects so that the compact parts of a layout will correspond to a compact sequence of objects within the chromosome.

        
Chromosome                                                Chromosome
A-B-C-D-E-F-G-H-I-J-K-L-M-N-O-P-Q-R-S        A-B-E-J-F-L-C-N-I-D-G-H-M-O-K-Q-R-P-S
Original vs. adjusted ordering of objects in chromosome


1-point crossover with hot-spots. This operator does not strictly inherit the beginning parts of the parental layouts. Instead the crossing point is chosen among the set of the top-most objects of the layout - hot-spots. From this object till the end of the chromosome all objects are inserted to the offspring.

2-point crossover with hot-spots. This operator is an extension of the previous one. It cuts out a "reasonable" part of one layout, uses it as a beginning of a new layout, and completes it with the objects from the other parent in a standard way. Here the reasonable part means a group of objects, which are chained in a column from the top to the bottom edge of the material stripe.

Experimental results
Figure below shows a successful resolving of the problem with 42 objects.

The best layout of the initial population (upper picture) and the final optimal layout (lower picture)


Publications:
  1)   Kubalik, J., Lazansky, J., Zikl, P.: Layout Problem Optimization Using Genetic Algorithms. In Knowledge and Technology Integration in Production and Services. New York: Kluwer Academic / Plenum Publishers, 2002, p. 493-500. ISBN 1-4020-7211-2.

   top

back to my research page