Genetic Algorithms (GAs)

Algorithms in Nature
Genetic algorithms

History

History of GAs
• As early as 1962, John Holland's work on adaptive systems laid the foundation for later developments.
• By the 1975, the publication of the book Adaptation in Natural and Artificial Systems, by Holland and his students and colleagues.

History of GAs
• early to mid-1980s, genetic algorithms were being applied to a broad range of subjects.
• In 1992 John Koza has used genetic algorithm to evolve programs to perform certain tasks. He called his method "genetic programming" (GP).

What is GA
• A genetic algorithm (or GA) is a search technique used in computing to find true or approximate solutions to optimization and search problems.
• (GA)s are categorized as global search heuristics. • (GA)s are a particular class of evolutionary
algorithms that use techniques inspired by evolutionary biology such as inheritance, mutation, selection, and crossover (also called recombination).

What is GA
• The evolution usually starts from a population of randomly generated individuals and happens in generations.
• In each generation, the fitness of every individual in the population is evaluated, multiple individuals are selected from the current population (based on their fitness), and modified to form a new population.

What is GA
• The new population is used in the next iteration of the algorithm.
• The algorithm terminates when either a maximum number of generations has been produced, or a satisfactory fitness level has been reached for the population.
No convergence rule or guarantee!

Vocabulary
• Individual - Any possible solution • Population - Group of all individuals • Fitness – Target function that we are optimizing (each
individual has a fitness) • Trait - Possible aspect (features) of an individual • Genome - Collection of all chromosomes (traits) for an
individual.

Basic Genetic Algorithm
• Start with a large “population” of randomly generated “attempted solutions” to a problem
• Repeatedly do the following: – Evaluate each of the attempted solutions – (probabilistically) keep a subset of the best solutions – Use these solutions to generate a new population
• Quit when you have a satisfactory solution (or you run out of time)

Example: the MAXONE problem
Suppose we want to maximize the number of ones in a string of l binary digits
Is it a trivial problem?
It may seem so because we know the answer in advance
However, we can think of it as maximizing the number of correct answers, each encoded by 1, to l yes/no difficult questions`
10