NiCADa - Genetic Algorithms

Genetic Algorithms

Introduction of Genetic Algorithms (GA)

Genetic Algorithms (GA) is a stochastic search technique inspired by the biological phenomenon of the natural evolutionary process of survival of the fittest. It has been proven to be reliable and able to deal with complex combinatorial and multi-objective layout problems in a wide variety of application areas ranging from runner size optimisation and strip packing layout design to floor plan layout design and Very-Large-Scale-Integration (VLSI) circuit layout design. GA can deal with populations of solutions rather than a single solution. Therefore, GA can explore the neighbourhood of the whole population and does not strongly rely on the initial solution. Besides, GA can exchange the information of a large set of parallel solutions in the population through the evolutionary process. Thus GA appears to show great potential to support combinatorial layout design optimisation with its explorative and generative design process embodied in a stochastic evolutionary search.

Challenges of combinatorial layout design automation and optimisation using GA

However, Combinatorial layout design automation and optimisation using GA is full of challenges. This is because GA is very problem-specific. GA highly depends on a proper chromosome design and genetic operator design specially developed for a specific application problem. Traditionally, binary representations (e.g. 01001011011¡K¡K) are the most common representations for many combinatorial optimisation problems because the binary representation allows a direct and very natural encoding. Chromosomes in GA can also be represented in other forms, such as integer representations, real-valued representations, messy representations and direct representations. Chromosome design is very problem-specific. In some cases, it is not practical to encode a complex design problem using traditional chromosome representation methods. For example, combinatorial layout design involves grouping problems. Designers need to decide how many groups should be divided and which space elements should be grouped together to make a good layout solution. Most previous research using either standard or ordering chromosome design are not suitable for grouping problems because standard or ordering chromosome is object oriented rather than group oriented. Moreover, no previous research can deal with combinatorial layout design problems, which involves solving both grouping problems and space layout design problems at the same time. In fact, using different chromosome design can affect GA performance dramatically. Designing a proper chromosome remains the black art of GA research.

On the other hand, crossover is the most important genetic operator of GA. Crossover aims to combine pieces of genetic information from different individuals in the population. Every generation inherits traits from its parents through genes. In a fixed-length chromosome, the allele (parameter or feature value) for a particular gene (parameter or feature) is coded for at a particular locus (genotype position). It is simple for a standard crossover operator to exchange homologous segments divided by the same crossover point in each parent genotype. However, combinatorial layout design problems cannot be simply encoded into fixed-length chromosomes because numbers of groups and numbers of space elements in each group are variable and unknown beforehand. When variable-length chromosomes are used, no homologous segments divided by the same crossover point in each parent genotype can be exchanged to produce offspring that can inherit meaningful building blocks from both parents. It may produce invalid offspring because genes are combined independently from each of both parents in a cut-and-concentrate manner during a crossover process. A special chromosome requires a specialised crossover operator to inherit and recombine individuals' important genetic properties from generation to generation. Designing a crossover operator to produce valid offspring that can inherit meaningful building blocks from both parents with chromosomes containing grouping genetic information, space layout genetic information and so forth is very challenging.