# Genetic Algorithms (GAs)

## Preview text

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?