Difference between revisions of "Genetic algorithms"

From Computer Science Wiki
Jump to navigation Jump to search
 
(10 intermediate revisions by 2 users not shown)
Line 2: Line 2:


The genetic algorithm is a method for solving both constrained and unconstrained optimization problems that is based on natural selection, the process that drives biological evolution. The genetic algorithm repeatedly modifies a population of individual solutions. At each step, the genetic algorithm selects individuals at random from the current population to be parents and uses them to produce the children for the next generation. Over successive generations, the population "evolves" toward an optimal solution. You can apply the genetic algorithm to solve a variety of optimization problems that are not well suited for standard optimization algorithms, including problems in which the objective function is discontinuous, nondifferentiable, stochastic, or highly nonlinear. The genetic algorithm can address problems of mixed integer programming, where some components are restricted to be integer-valued.<ref>https://www.mathworks.com/help/gads/what-is-the-genetic-algorithm.html</ref>
The genetic algorithm is a method for solving both constrained and unconstrained optimization problems that is based on natural selection, the process that drives biological evolution. The genetic algorithm repeatedly modifies a population of individual solutions. At each step, the genetic algorithm selects individuals at random from the current population to be parents and uses them to produce the children for the next generation. Over successive generations, the population "evolves" toward an optimal solution. You can apply the genetic algorithm to solve a variety of optimization problems that are not well suited for standard optimization algorithms, including problems in which the objective function is discontinuous, nondifferentiable, stochastic, or highly nonlinear. The genetic algorithm can address problems of mixed integer programming, where some components are restricted to be integer-valued.<ref>https://www.mathworks.com/help/gads/what-is-the-genetic-algorithm.html</ref>
<br />


[https://www.analyticsvidhya.com/blog/2017/07/introduction-to-genetic-algorithm/ This article is a good place to get started]
== Two videos to get you started ==
<html>
<iframe width="560" height="315" src="https://www.youtube.com/embed/05rEefXlmhI" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>
</html>
<br />
<html>
<iframe width="560" height="315" src="https://www.youtube.com/embed/1i8muvzZkPw" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>
</html>


== Use of genetic algorithms ==
* [https://en.wikipedia.org/wiki/List_of_genetic_algorithm_applications Click here for a fairly good list]
* [https://stackoverflow.com/questions/1538235/what-are-good-examples-of-genetic-algorithms-genetic-programming-solutions Click here for several good examples (scroll down)]
* [https://www.brainz.org/15-real-world-applications-genetic-algorithms/ here are some short examples of GA]
== The basic pattern of genetic algorithms ==
# A random set of solutions would be generated on the sample documents
# And tested against the human labelling
# Best fit solutions retained
# New generation created by mutating/crossing
# Algorithm repeated
# Until a good fit obtained
== Terms associated with genetic algorithms ==
=== Initial population ===
=== Initial population ===
Set of sub-optimal solutions which are provided as inputs to a genetic algorithm and from which an optimal solution evolves<ref>https://www.igi-global.com/dictionary/initial-population/14655</ref>
=== Fitness function ===
=== Fitness function ===
Fitness Function (also known as the Evaluation Function) evaluates how close a given solution is to the optimum solution of the desired problem. It determines how fit a solution is.
In genetic algorithms, each solution is generally represented as a string of binary numbers, known as a chromosome. We have to test these solutions and come up with the best set of solutions to solve a given problem. Each solution, therefore, needs to be awarded a score, to indicate how close it came to meeting the overall specification of the desired solution. This score is generated by applying the fitness function to the test, or results obtained from the tested solution.<ref>https://towardsdatascience.com/how-to-define-a-fitness-function-in-a-genetic-algorithm-be572b9ea3b4</ref>
=== Selection ===
=== Selection ===
Selection rules select the individuals, called parents, that contribute to the population at the next generation.
Selection rules select the individuals, called parents, that contribute to the population at the next generation.
Line 15: Line 43:
=== Mutation ===
=== Mutation ===
Mutation rules apply random changes to individual parents to form children.
Mutation rules apply random changes to individual parents to form children.
== Helpful resources ==
* [https://www.analyticsvidhya.com/blog/2017/07/introduction-to-genetic-algorithm/ 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


== Standards ==
== Standards ==

Latest revision as of 14:45, 6 February 2019

HL CONTENT: Modeling & Simulation[1]

The genetic algorithm is a method for solving both constrained and unconstrained optimization problems that is based on natural selection, the process that drives biological evolution. The genetic algorithm repeatedly modifies a population of individual solutions. At each step, the genetic algorithm selects individuals at random from the current population to be parents and uses them to produce the children for the next generation. Over successive generations, the population "evolves" toward an optimal solution. You can apply the genetic algorithm to solve a variety of optimization problems that are not well suited for standard optimization algorithms, including problems in which the objective function is discontinuous, nondifferentiable, stochastic, or highly nonlinear. The genetic algorithm can address problems of mixed integer programming, where some components are restricted to be integer-valued.[2]

Two videos to get you started[edit]


Use of genetic algorithms[edit]

The basic pattern of genetic algorithms[edit]

  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

Terms associated with genetic algorithms[edit]

Initial population[edit]

Set of sub-optimal solutions which are provided as inputs to a genetic algorithm and from which an optimal solution evolves[3]

Fitness function[edit]

Fitness Function (also known as the Evaluation Function) evaluates how close a given solution is to the optimum solution of the desired problem. It determines how fit a solution is.

In genetic algorithms, each solution is generally represented as a string of binary numbers, known as a chromosome. We have to test these solutions and come up with the best set of solutions to solve a given problem. Each solution, therefore, needs to be awarded a score, to indicate how close it came to meeting the overall specification of the desired solution. This score is generated by applying the fitness function to the test, or results obtained from the tested solution.[4]

Selection[edit]

Selection rules select the individuals, called parents, that contribute to the population at the next generation.

Crossover[edit]

Crossover rules combine two parents to form children for the next generation.

Mutation[edit]

Mutation rules apply random changes to individual parents to form children.

Helpful resources[edit]

Standards[edit]

  • Outline the use of genetic algorithms.

References[edit]