Adaptive Speciation Genetic Algorithm (ASGA)

Get Complete Project Material File(s) Now! »

Crossover

The common characteristics of any crossover method are that they attempt to combine the qualities of two or more parents to create children with better qualities. Crossover methods differ in how they select parents, how many parents they select, how genes are recombined to create children, how many children are created, and how parents and children are incorporated into the next population. One simple and common approach is that two parents are selected using the same process for selection as in the selection operator. Half the genes from each parent are then used to create one child that is added to the next population. Any vacant places in the population are filled with individuals from the same source as the parents.

K-Point Crossover

K-point crossover divides individuals at k points along the chromosome and rearranges segments among the individuals to create children. An important aspect of K-Point Crossover is that adjacency of genes is more likely to be preserved than in Uniform Crossover. It is used when a problem is known to have substructures or “Building Blocks” [15] involving genes that can be identified as related or in cases when Inversion [15] is implemented. Inversion reorders genes on chromosomes without changing their function.

Mating Selection

A common but limiting implementation is to use the selection operator to pick parents for crossover. Doing this however restricts the ability to separate these processes. A selection operator uses the phenotype to pick individuals. A crossover operator manipulates the genotype. When the relationship of phenotype to genotype is not unique individuals picked using the selection operator can have a significant chance of including conflicting allele patterns. When the crossover operator is applied to them they can yield sub-optimal results. Active mating selection is where the chances of mating different individuals are not the same. Active mating selection includes assortative mating and inbreeding or outbreeding. Assortative mating can be positive assortative mating, or negative assortative mating.

Selecting Search Parameters

Typically, genetic algorithms require search parameters that determine how recombination is performed. In the case of a Simple Genetic Algorithm (SGA) [15] which has the same algorithm flow as in Figure 31 and several of its derivatives, a crossover rate and mutation rate must be given in advance. These control the probability of a pair of individuals being crossed or a gene changed. The ideal values for search parameters are determined by stochastic processes and the problem the algorithm is applied to. This situation is not ideal as it requires knowledge about the solutions in order to find them. This knowledge is usually substituted by an estimate or replaced with adaptive schemes.

Controlling the Balance of Exploration and Exploitation

Exploration and exploitation are the two primary processes in search and optimization algorithms [68]. Exploration explores new regions of the solution space to find better solutions. Exploitation attempts to accelerate the search process using knowledge gained from exploration. The balance of exploration and exploitation is crucial to the success of a search or optimisation algorithm [69]. If too much time is spent in exploration the algorithm becomes too time consuming. If too much time is spent on exploitation then an algorithm is unlikely to cover many solution options and yields a poor result. Determining the appropriate balance of exploration and exploitation requires the properties of the search space to be approximated based on incomplete knowledge. This approximation determines how exploitation is implemented.

Adaptive Speciation Genetic Algorithm (ASGA)

This chapter presents the proposed ASGA for use in the optimisation stage of the design framework given in Chapter 3. The ASGA is a type of genetic algorithm. Fundamental information on genetic algorithms may be found in Chapter 4. These changes were introduced because of the problem requirements of system design optimisation. Typically a designer must investigate what target costs and performance are feasible in large complex designs. A single design problem can have many niche designs each fulfilling different aspects of the problem to different degrees. In addition, computational resources are typically very limited with respect to the size of the design spaces involved.

Table of Contents :

• Abstract
• Acknowledgements
• Table of Contents
• List of Figures
• List of Tables
• Chapter 1. Introduction
  • 1.1. Motivation of the Research
  • 1.2. Selection of Case Studies
  • 1.3. Contributions of the Research
  • 1.4. Structure of the Thesis
• Chapter 2. Background Issues in the Design Process
  • 2.1. Overview
  • 2.2. Design Problems
    • 2.2.1 Combinational Optimization
    • 2.2.2 Historical Methods
    • 2.2.3 Design Framework
    • 2.2.4 Design Specifications
    • 2.2.5 Time Complexity of Design Problems
    • 2.2.6 Target Technology
  • 2.3. Multi-Objective Optimization
    • 2.3.1 Measuring Performance of Multi-Objective Optimisers
    • 2.3.2 An Improved Comparison Method
    • 2.3.3 Case Studies
  • 2.4. Evolutionary Algorithms
    • 2.4.1 Overview 
    • 2.4.2 Nomenclature
    • 2.4.3 Process
    • 2.4.4 Convergence
    • 2.4.5 Implementations
  • 2.5. Chapter Summary
• Chapter 3. System Design Framework
  • 3.1. Chapter Overview
  • 3.2. Introduction
  • 3.3. Design Optimization
  • 3.4. Motivating Examples
  • 3.5. Design Framework
    • 3.5.1 Overview
    • 3.5.2 Design Specification
    • 3.5.3 STR Example
    • 3.5.4 SAD Example
    • 3.5.5 EKF Example
  • 3.6. Chapter Summary
• Chapter 4. Genetic Algorithms
  • 4.1. Overview
  • 4.2. Algorithm Flow
  • 4.3. Genetic Operators in Genetic Algorithms
    • 4.3.1 Selection
    • 4.3.2 Crossover
    • 4.3.3 Mutation
  • 4.4. Issues in Genetic Algorithms
    • 4.4.1 Mating Selection
    • 4.4.2 Selecting Search Parameters
    • 4.4.3 Controlling the Balance of Exploration and Exploitation
• Chapter 5. Adaptive Speciation Genetic Algorithm (ASGA)
• Chapter 6. Algorithm Evaluation
• Chapter 7. Algorithm Comparison
• Chapter 8. Conclusions and Future Work

GET THE COMPLETE PROJECT
A Design Framework and Genetic Algorithm for Digital Design Optimisation on FPGAs