Evolutionary Design
Evolutionary Design in nature
Every living thing in the natural world is a masterpiece of evolved design. As shown in the upper part of Figure 1, evolutionary design in nature is the original and best evolutionary design system. In nature, a chromosome is an organised structure of Deoxyribonucleic Acid (DNA) and protein. A segment of DNA is called a "gene". Genes provide information that instructs an organism how to make an individual in many ways. The process of the generation of form in living systems involves the sequence of coded instructions for selecting and locating different kinds of protein in particular locations. Phenotype is an individual organism's actual observed physical properties decoded from its genotype. In nature, the fitness of an individual organism is measured by its ability to survive and produce offspring in its living environment. Evolution is the process of change in the inherited traits of a population of organisms from one generation to the next driven by three main mechanisms - natural selection, genetic drift and gene flow. Natural selection provides competition between organisms for survival and reproduction. Every generation inherits traits from its parents through genes. Consequently, stronger organisms' genes can be passed on to the next generation while weaker organisms die out. Gene flow is the transfer of genes within and between populations during reproduction through genetic recombination (crossover). Genetic drift is a random change (mutation) of gene information, also known as alleles, during reproduction. Taking the happy-face spider as an example, spiders with different colour patterns in many forms of smiles are generated through natural evolution because their predators (the Hawaiian Honeycreeper) are good at searching for the most common morph, the yellow morph. The main driving force behind evolutionary design in nature is "Survival of the Fittest".
Nature-Inspired Computing Applications for Design Automation and Optimisation
Research & Development Limited
Figure 1 The concept of our nature-inspired Evolutionary Combinatorial Layout Design
Challenges in combinatorial layout design using ED
Based on the principle of "Survival of the Fittest", the main concept of our invention is to simulate the natural evolutionary process to evolve combinatorial layout design using Shape Grammars (SG) and Genetic Algorithms (GA) (See the lower part of Figure 1). The GA coupled with SG-based chromosomes aims to allow for the generation of feasible and novel combinatorial layout design solutions and enable the GA to search for optimum solutions more efficiently. This approach can bring together the SG's design synthesis capability and the GA's capabilities of design space navigation and optimisation. However, implementation of ED using SG and GA for complex combinatorial layout design is full of challenges in practice. For example, GA's efficiency highly depends on a proper chromosome design for a specific problem. In addition, the usefulness of SG heavily relies on a well-crafted grammar for design representation and synthesis. Designing an SG-based chromosome for evolutionary combinatorial layout design from scratch is the first major challenge. Besides, GA's efficiency also depends upon genetic operators that fit the properties of the chromosome well. Designing efficient genetic operators for producing valid offspring that can inherit meaningful "building blocks" from both parents with a new and special SG-based chromosome is very challenging. More detailed discussions on SG and GA can be found in the sections of "Shape Grammars" and "Genetic Algorithms" respectively.
Our evolutionary combinatorial layout design using SG and GA
We developed a new hybrid SG-based chromosome that can encode not only the geometrical and topological layout design information but also the grouping design information with minimum redundancy. Analogous to the biological growth of form in living systems as mentioned previously, a gene's locus is represented by a SG rule while the genotype (recipe) and the combinatorial layout design solutions are represented by the plan (sequence of rules) and phenotype (blueprint) respectively. Each genotype ("control" part) corresponds to a unique phenotype (the body features - the "controlled" part) through the Genotype-Phenotype mapping process. A SG of combinatorial layout design incorporated with a specific design knowledgebase provides an encoding / decoding mechanism specially designed for evolving combinatorial layout design based on a specially designed hybrid SG-based chromosome. This approach can reduce the solution space because all individuals generated in the population are feasible solutions. The evolutionary process starts by receiving the user input and proceeds to generating a population using the knowledgebase which comprises shape grammars of the combinatorial layout design and corresponding domain-specific knowledgebase. Then the genotypes are transformed into phenotypes for the fitness evaluation process. A specific scoring scheme is used to quantify the fitness value of each individual in the population considering multiple mould design objectives and constraints. The fittest ("best") members of the population are then selected randomly to produce an offspring through a specially designed group-oriented SG-based crossover operation. This new crossover operator can inherit or combine meaningful features from both parents to reproduce a stronger offspring without violation of the design constraints and disruption of the useful parts (schemata) of the chromosome during recombination. A new group-oriented SG-based mutation introduces additional changes into the resulting genotype randomly to generate a new design solution. This new mutation operator can introduce new and feasible solutions into the population without violation of the design constraints. Fitness evaluation will be done again and weak individuals will be replaced by the better offspring and will disappear eventually during the natural evolutionary process. The selection, crossover and mutation operations are applied repeatedly to the population until the termination conditions are met. Finally, the program outputs the resulting population.
Copyright 2015. NiCADa Research & Development Company Limited. All Rights Reserved.
