Genetic Algorithms

Advanced programming

In computer science and operations research, a genetic algorithm (GA) is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA). Genetic algorithms are commonly used to generate high-quality solutions to optimization and search problems by relying on biologically inspired operators such as mutation, crossover and selection

• Please first review the characteristics of algorithms.
• Please then review the characteristics of heuristics.

The basic pattern of genetic algorithms

1. A random set of solutions would be generated on the sample documents
2. And tested against the human labelling
3. Best fit solutions retained
4. New generation created by mutating/crossing
5. Algorithm repeated
6. Until a good fit obtained

Use of genetic algorithms

• Click here for a fairly good list
• Click here for several good examples (scroll down)
• here are some short examples of GA

Helpful resources

• This article is a good place to get started
• a good game: https://andymakes.itch.io/combat-genetics
• a better game to help you understand genetic algorithms: https://david-birge-cotte.itch.io/evolution-sandbox

Terms associated with genetic algorithms

• Brute force approach
• Computational intractability
• Convergence
• Crossover / crossover operator
• Elitism
• Exploration vs exploitation
• Fitness / fitness function / fitness landscape
• Heuristics
• Optimization
• Population
• Premature convergence
• Problem space
• Ranking
• Roulette wheel selection
• Selection strategy
• Simulated annealing
• Stochastic universal sampling
• Termination condition
• Tour
• Tournament selection
• Truncation selection

Apply knowledge or rules to put theory into practice.