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

Start here to understand genetic algorithms

• Brute force approach
• Combinatorial optimization
• Computational intractability
• Convergence
• Crossover / crossover operator
• Elitism
• Exploration vs exploitation
• Fitness / fitness function / fitness landscape
• Heuristics
• Hill climbing
• Initialization parameters
• Local extrema
• Mating pool
• Mutation / mutation rate
• Novelty search
• Offspring
• Optimization
• Population
• Premature convergence
• Problem space
• Ranking
• Roulette wheel selection
• Selection strategy
• Simulated annealing
• Stochastic universal sampling
• Termination condition
• Tour
• Tournament selection
• Truncation selection