Powered by

# Evolutionary Computing Origins

# Introduction

  • A special flavor of computing, which draws inspiration from the process of natural evolution
  • The fundamental metaphor of evolutionary computing relates this powerful natural evolution to a particular style of problem solving – that of trial-and-error
  • Let us consider evolution as
    • A given environment is filled with a population of individuals that strive for survival and reproduction. (we have a collection of candidate solutions)
    • The fitness of these individuals is determined by the environment, and relates to how well they succeed in achieving their goals. (Their quality determines the chance that they will be kept and used as seeds for constructing further candidate solutions.)
  • ![[Pasted image 20240303204751.png]]

# Brief history

  • As early as 1948, Turing proposed genetical/evolutionary search
  • The contemporary terminology denotes the whole field by evolutionary computing, the algorithms involved are termed evolutionary algorithms
    • It considers evolutionary programming, evolution strategies, genetic algorithms, and genetic programming as subareas belonging to the corresponding algorithm variants.

# Inspiration from biology

# Darwin evolution

  • Darwin’s theory of evolution offers an explanation of the origins of biological diversity and its underlying mechanisms.
  • Natural selection favours those individuals that compete for the given resources most effectively, in other words, those that are adapted or fit to the environmental conditions best.
    • The first cornerstone in progress is the survival of the fittest
    • The second factor is phenotypic variations (behavioural and physical features of an individual that directly affect its response to the environment)
  • Multimodal problems are problems in which there are a number of points that are better than all their neighbouring solutions.
  • Population has a finite size and random choice made in selection/variation cause genetic drift whereby highly fit individuals may be lost from the population, or the population may suffer from a loss of variety concerning some traits

# Genetics

  • The microscopic view of natural evolution is offered by molecular genetics (beyond phenotypic features).
  • The fundamental observation from genetics is that each individual is a dual entity: its phenotypic properties (outside) are represented at a genotypic level (inside)
  • Genes are the functional units of inheritance encoding phenotypic characteristics and an allele is one of possible values a gene can have.
  • One gene might affect more phenotypic traits (pleitropy), and in turn one phenotypic trait can be determined by more than one gene (polygeny).
  • Genotype contains all the information necessary to build the particular phenotype
  • In evolutionary computing, the combination of features from two individuals in offspring is often called crossover.
  • We take inspiration from the process of meiosis
    • During meiosis a chromosome pair first aligns physically, that is, the copies of the paternal and maternal chromosomes, which form the pair, move together and stick to each other at a special position
    • In the second step the chromosomes double so that four strands (called chromatids) are aligned
    • The actual crossing-over takes place between the two inner strands that break at a random point and exchange parts
    • This results 4 copies of the chromosome.
    • ![[Pasted image 20240311133114.png]]
  • All variations happen at the genotypic level, while selection is based on actual performance in a given environment, that is, at the phenotypic level.
  • This cycle of production and evaluation is called generate-and-test method.

# Why evolutionary computing

  • Evolutionary algorithms are applicable to a wide range of problems, do not need much tailoring for specific problems, and deliver good (not necessarily optimal) solutions within acceptable time.
  • Learning more about evolutionary processes in general can help in designing better algorithms later
  • It is not limited by conventions, aesthetic considerations, or ungrounded preferences for symmetry. On the contrary, it is purely driven by quality, and thereby it can come to solutions that lie outside of the scope of human thinking, with its implicit and unconscious limitations.