Genetic Algorithms

• Genetic algorithms are algorithms in nature

History of Genetic Algorithms

• John Holland's work in 1962 on adaptive systems provided a basis for future growth with genetic algorithms (GAs)
• The book Adaptation in Natural and Artificial Systems by Holland and his students was published in 1975
• From the early to mid-1980s, genetic algorithms were applied to many subjects
• John Koza used a genetic algorithm in 1992 to help generate programs to perform tasks and called it genetic programming (GP)

Genetic Algorithms Explained

• Genetic algorithm (GA) serve as a search technique to find or approximate solutions for optimization and search problems
• GAs are classified as global search heuristics
• GAs are a class of evolutionary algorithms which use evolutionary biology techniques of inheritance, mutation, selection, and crossover (recombination)
• Evolution starts from a population of random individuals and happens over many generations
• In each generation, individual fitness is assessed, multiple individuals are selected based on fitness from the current population, and modified to form a new population
• The new population is used in the next iteration of the algorithm
• The algorithm concludes when a maximum number of generations occurs, or a satisfactory fitness level is reached for the population

Vocabulary

• Individual: any possible solution to the algorithm
• Population: group of all individuals
• Fitness: target function we are optimizing where each individual has fitness
• Trait: possible aspect/feature of an individual
• Genome: the collection of all chromosomes (traits) for an individual

Basic Genetic Algorithms

• Algorithms start with a large "population" of generated "attempted solutions" to a problem
• Repeated actions include evaluating attempted solutions then probabilistically keeping a subset of the best solutions, and using these solutions to generate a new population
• Algorithms stop after a satisfactory solution is found or time runs out

MAXONE Problem

• Suppose the goal is to maximize the number of ones in a string of binary digits, the answer is known in advance
• It can be thought of as maximizing the number of correct answers
• An individual is encoded as a string of binary digits
• The fitness, f, of a candidate solution is the number of ones in its genetic code
• A population of n random strings is started, where l = 10 and n = 6 example where a coin is tossed 60 times to get initial population

The Genetic Algorithm Steps

• Step 1 is Selection
• Step 2 is Crossover
• Step 3 is Mutations

First Step: Selection

• Randomly using a biased coin, select a subset of the individuals based on fitness
• Individual i will have a probability to be chosen

Second Step: Crossover

• Mate strings for crossover by determining whether to perform the crossover or not using a predefined probability like 0.6
• Extract the crossover points randomly

Third Step: Mutations

• Apply random mutations where a small probability of error (for instance 0.1) is allowed for each bit copied to the new population
• Iterate to improve population fitness

Biological Motivation

• Genetic information is stored in the chromosomes
• Chromosomes are built of DNA
• Genes are encoded and code in the chromosomes
• Genes have a unique position on the chromosome
• The entire combination of genes is the genotype
• Genotype leads to a phenotype like eye color, height, or disease predisposition
• The phenotype is changed by changes to the underlying genetic code

Reproduction

• Reproduction of genetical information in both mitosis and meiosis
• Mitosis copies the same genetic information into a new offspring, without information exchange
• Mitosis is the normal way of expanding multicellular structures like organs
• Meiosis is the basis of sexual reproduction; meiotic division creates gametes
• Reproduction occurs between two gametes to create a new individual
• Crossovers lead to a new genotype

Mutations

• In any copying process, errors and single point mutations commonly occur
• Other errors affect longer regions (deletion, inversions, substitutions)

Natural Selection

• Natural selection is the "preservation of favorable variations and rejection of unfavorable variations"
• There are more individuals born than can survive, so there is a continuous struggle for life
• Individuals with an advantage have a greater chance for survival resulting in survival of the fittest

GA Operators

• Methods of representation, selection, and reproduction are GA operators

Common Representation Methods

• Binary strings
• Arrays of integers (usually bound)
• Arrays of letters
• etc

Selection Methods

• Roulette-wheel selection
• Elitist selection
• Fitness-proportionate selection
• Scaling selection
• Rank selection
• etc...

Roulette Wheel Selection

• This method acts as a game of roulette
• Each individual gets a slice of the wheel, but more fit ones obtain larger slices than less fit ones

Other Selection Methods

• Elitist selection: Chose only the most fit members of each generation
• Cutoff selection: Select only those that are above a certain cutoff for the target function

Methods of Reproduction

• Crossover and Mutation are primary methods

Reproduction by Crossover

• Two parents produce two offspring
• Chromosomes of the parents are copied to the next generation
• The parents are randomly recombined (crossed-over) to form the new offspring

Possible Crossover Strategies

• Randomly select a single point for crossover or multiple points
• Uniform crossover

Two-Point Crossover

• Avoids genes at the beginning and end of chromosomes from always being split among parents

Single vs. Multi Point Crossover

• Single point crossover involves one cross point
• Multi point crossover involves multiple cross points

Uniform Crossover

• A random subset is chosen
• The subset is taken from parent 1 while other bits come from parent 2

Reproduction by Mutations

• Generating new offspring from a single parent

Traveling Salesman Problem

• Find the shortest tour of a given set of cities by visiting each city only once and minimizing the total distance traveled
• Representation is a list of city numbers; an order-based GA
• Crossover combines inversion and recombination through a "Order1 crossover"
• Mutation may reorder the list

GA Applications

• Control (gas pipeline, missile evasion)
• Design (aircraft, keyboard, communication networks)
• Game playing (poker, checkers)
• Security (encryption/decryption)
• Robotics (trajectory planning)

Benefits of Genetic Algorithms

• Easy to understand conceptually
• Modular which is separate from application
• Supports multi-objective optimization
• Always an answer; the answer improves with time
• Easy to exploit previous or alternate solutions
• Flexible building blocks for hybrid applications