AM-77 - Genetic algorithms and global solutions

You are currently viewing an archived version of Topic . If updates or revisions have been published you can find them at .

Genetic algorithms (GAs) are a family of search methods that have been shown to be effective in finding optimal or near-optimal solutions to a wide range of optimization problems. A GA maintains a population of solutions to the problem being solved and uses
crossover, mutation, and selection operations to iteratively modify them. As the population
evolves across generations, better solutions are created and inferior ones are selectively
discarded. GAs usually run for a fixed number of iterations (generations) or until further
improvements do not obtain. This contribution discusses the fundamental principles of
genetic algorithms and uses Python code to illustrate how GAs can be developed for both
numerical and spatial optimization problems. Computational experiments are used to
demonstrate the effectiveness of GAs and to illustrate some nuances in GA design.

Topic Description: 

\begin{lstlisting}[caption={GA and parameters.}, label={list:bin:GA}, frame=single, numbers=left] class Parameters: def __init__(self, popsize, numgen, pcrossover, pmutation, elitism): self.popsize = popsize self.numgen = numgen self.pcrossover = pcrossover self.pmutation = pmutation self.elitism = elitism def GA(param): population,objs,fitnesses = initialization(param.popsize) for i in range(param.numgen): population, objs, fitnesses = generation( population, objs, fitnesses, param.pcrossover, param.pmutation, param.elitism) return max(objs), sum(objs)/param.popsize, population \end{lstlisting}



Learning Objectives: 
  • Describe the difficulty of finding globally optimal solutions for problems with many local optima
  • Explain how evolutionary algorithms may be used to search for solutions
  • Explain the important advantage that GA methods may offer to find diverse near-optimal solutions
  • Explain how a GA searches for solutions by using selection proportional to fitness, crossover, and (very low levels of) mutation to fitness criteria and crossover mutation to search for a globally optimal solution to a problem
  • Compare and contrast the effectiveness of multiple search criteria for finding the optimal solution with a simple greedy hill climbing approach