# Genetic Algorithms (GAs)

Download 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?

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

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

## Categories

## You my also like

### Selection Methods of Genetic Algorithms

402 KB8.9K1.2K### Genetic Algorithm Approach to Optimize Test Cases

414.8 KB8.5K2.4K### COL106: Data Structures and Algorithms

131.8 KB27.7K10K### SCILOGEX Homogenizers Model : D500 Generator/Rotor Matching

145 KB76.3K13K### Physical Education Core 3 Syllabus

61.1 KB52.4K6.3K### DCAC International Fitness Education Conference

3.1 MB42.5K6.8K### FITNESS GRAM Jane Jogger

1.1 MB44K16.7K### Fitness effects and resistance mechanisms of beneficial

2.6 MB47.6K20.5K### Medical Fitness Centres

595.9 KB21.8K7.4K