Powered by

# What Is An Evolutionary Algorithm

# Introduction

  • The idea behind all EA are -
    • Given a population of individuals within some environment that has limited resources, competition for those resources causes natural selection (survival of the fittest).
    • This in turn causes a rise in the fitness of the population. Given a quality function to be maximized, we can randomly create a set of candidate solutions, i.e., elements of the function’s domain.
    • We then apply the quality function to these as an abstract fitness measure – the higher the better.
    • On the basis of these fitness values some of the better candidates are chosen to seed the next generation.
    • This is done by applying recombination and/or mutation to them.
      • Recombination involves 2 parents producing one candidate
      • Mutation involves only 1 parent
    • This is iterated until a limit is reached or a candidate of sufficient quality is found
  • There are two main forces that form the basis of evolutionary systems:
    • Variation operators (recombination and mutation) create the necessary diversity within the population, and thereby facilitate novelty.
    • Selection acts as a force increasing the mean quality of solutions in the population.
  • We view this process as - evolution is optimising the fitness function
  • The general scheme of an EA ![[Pasted image 20240311205029.png]] ![[Pasted image 20240311205237.png]]
  • EA's are
    • Population based - process a bunch of solutions simultaneously
    • Stochastic
    • Involve recombination
  • Various dialects of EA follow the same but have some differences, mainly in the data structure used
    • Genetic algorithms - finite alphabet strings
    • Evol strategies - real valued vectors
    • Classic Evol programming - finite state machines
    • Genetic programming - trees

# Components of a EA

  • Representation (Definition of individuals)
    • We try to simplify/abstract away some aspects of real world to create a well defined problem context within which possible solutions exist and can be easily evaluated
    • Objects forming possible solutions within the original problem context are referred to as phenotypes, while their encoding, that is, the individuals within the EA, are called genotypes.
    • The space of all possible candidate solutions is commonly called the phenotype space and the space where evol search takes place is the genotype space
  • Evaluation function (fitness function)
    • Represents requirements that the population should adapt to meet and forms the basis for selection
    • We try to maximise this
  • Population
    • Holds possible candidate solutions - a multiset of genotypes.
    • Defining a population is as simple as defining its size which is constant usually
    • The diversity of a population is a measure of the number of different solutions present.
    • If only one genotype is present then this implies only one phenotype and fitness value are present but not the other way round.
  • Parent Selection Mechanism
    • An individual is a parent if it has been selected to undergo variation in order to create offspring.
    • It is stochastic wherein high quality has a better chance
    • Nevertheless, low-quality individuals are often given a small, but positive chance to prevent overly greedy search.
  • Variation operators
    • The role of variation operators is to create new individuals from old ones.
    • Mutation
      • Applied to one genotype and delivers a (slightly) modified mutant, the child or offspring.
      • It is stochastic and unbiased
    • Recombination
      • Merges information from two parent genotypes into one or two offspring genotypes and this is called recombination or crossover
      • It is stochastic and unbiased
      • More than 2 parents is possible but no biological equivalent exists
  • Survivor Selection Mechanism (Replacement)
    • Survivor selection or environmental selection is to distinguish among individuals based on their quality.
    • Called after creation of offspring and the decision of which individuals are selected is made from the fitness (sometimes the age is also used)
    • Deterministic compared to parent selection
    • Also called replacement strategy (usually used only if the number of children is very small compared to population)
  • Initialisation
    • First population is seeded by randomly generated individuals
  • Termination condition
    • If problem has known optimal fitness level, then a solution with this fitness is the terminating condition (might never be satisfied)
    • Other options include
      • CPU time
      • Total number of fitness evaluations
      • Fitness improvement remains under a threshold
      • Population diversity drops under a threshold

# An example

  • We look at Goldberg's problem
    • Population = integers from 0 to 31
    • Fitness function = f(x) = x^2
    • Representation = 5 bit binary string of number
    • Parent selection = some probability p_i = \frac {f(i)}{\sum_{j \in P}f(j)}
    • Survivor selection = replace all parent with new popl
    • Mutation = with some mutation rate (per bit position threshold), execute a bit flip randomly
    • Recombination = one point crossover
    • ![[Pasted image 20240407192629.png]]
    • ![[Pasted image 20240407192723.png]]
    • ![[Pasted image 20240407192732.png]]
  • 8 Queens problem