Transcript [1, 0, 1, 1, 0, 1, 1] [1, 0, 0, 1, 1, 1, 1] [1, 0, 0, 1, 0, 1, 1

Applying natural evolution for solving
computational problems
First lecture: Introduction to Evolutionary Computation
Second lecture: Genetic Programming
Inverted CERN School of Computing 2017
Daniel Lanza - CERN
Agenda
• Introduction to Evolutionary Computation
• Introduction to Evolutionary Algorithms
• Use cases, practical examples
• Key concepts
• Representation of individuals
• Phases
• Evolutionary Computation research tool (ECJ)
2
Introduction to Evolutionary Algorithms
An evolutionary algorithm (EA) is a heuristic optimization algorithm
using techniques inspired by mechanisms from organic evolution such
as mutation, recombination, and natural selection to find an optimal
configuration for a specific system within specific constraints. [1]
• History
• Idea originated in the 1950s
• L. Fogel 1962 (San Diego, CA): Evolutionary Programming
• I. Rechenberg & H.-P. Schwefel 1965 (Berlin, Germany): Evolution Strategies
• When to use them
• When finding exact solution is computationally too demanding, but near-optimal solution is
sufficient
3
Use cases, practical examples
• Aircraft wing design [8][9]
4
Use cases, practical examples
• Electronic circuit design, known as evolvable hardware [2]
5
Use cases, practical examples
• Wireless sensor/ad-hoc networks [4].
6
Use cases, practical examples
• Vehicle routing problems (traveling salesman problem) [3].
• Feature selection used by machine learning algorithms. [6]
• Image processing (face recognition) [5].
• … [7]
7
Key concepts
• A population of individuals is evolved through generations
• Each individual’s genome describes a candidate solution
• The fitness function evaluates new individuals
• The evolutionary process is finished as soon as the optimal solution is
found
8
Representation of individuals
• It should be able to represent all the search space
• But should not able to represent impossible solutions
• Examples of solutions to different problems:
[1, 0, 1, 1, 0, 1, 1]
[4.5, 1, 100.3, 9, 21, 934, 1]
[“right”, “left”, “up”, ”up”, “left”, “left”, “down”]
[4.5, “left”, false, true, 9]
9
Representation of individuals: example
• Choose points of interest for face recognition [5]
10
Phases
• Similarly to how natural evolution works…
Initialization
Evaluation
Randomly generated
Calculate fitness for
each individual
Optimal solution
Breeding
Selection
Individuals are
crossed-over and
mutations take place
Choose individuals
for breeding
11
Phases: in detail by using an example
• “MaxOne” problem
• Starting from randomly generated strings of 0s and 1s
• Evolve to the optimal solution, a string of 1s
[1, 1, 1, 1, 1, 1, 1]
12
Phases: initialization
Evaluation
Initialization
Breeding
• The first population is filled up with individuals
• The individuals are randomly generated following problem’s criteria
• The population size is determined beforehand and remains fixed
Selection
[0, 0, 1, 1, 0, 1, 1]
[1, 0, 1, 1, 0, 1, 1]
[0, 0, 1, 1, 0, 0, 1]
[1, 0, 0, 1, 1, 1, 1]
[1, 1, 1, 1, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 1]
13
Phases: evaluation
Evaluation
Initialization
• Practically the fitness function defines the problem
• Get the fitness of each individual
• Fitness describes how well the individual solves the problem
Breeding
Selection
• In “MaxOne”, fitness is defined as the number of 1s in the individual
4
5 [0, 0, 1, 1, 0, 1, 1]
[1, 0, 1, 1, 0, 1, 1]
3
[0, 0, 1, 1, 0, 0, 1]
5
[1, 0, 0, 1, 1, 1, 1]
4
[1, 1, 1, 1, 0, 0, 0]
2
[0, 0, 0, 1, 0, 0, 1]
14
Phases: selection
Evaluation
Initialization
• A selection strategy is defined to choose the parents
Breeding
Selection
• Selected individuals, parents, will be used for breeding
• Fitness is taken into account (best individuals)
• But also some randomness affects the selection (simulating real life)
• Individuals with reduced fitness could have valuable features
• Elitism (optional): best individual is copied to the next generation
4
5 [0, 0, 1, 1, 0, 1, 1]
[1, 0, 1, 1, 0, 1, 1]
3
[0, 0, 1, 1, 0, 0, 1]
5
[1, 0, 0, 1, 1, 1, 1]
4
[1, 1, 1, 1, 0, 0, 0]
2
[0, 0, 0, 1, 0, 0, 1]
15
Phases: selection (techniques)
Evaluation
Initialization
Breeding
• Tournament [11]
Selection
• A fixed number of individuals are randomly selected
• Among them, the best one is selected
4
5 [0, 0, 1, 1, 0, 1, 1]
[1, 0, 1, 1, 0, 1, 1]
3
[0, 0, 1, 1, 0, 0, 1]
5
[1, 0, 0, 1, 1, 1, 1]
4
[1, 1, 1, 1, 0, 0, 0]
2
[0, 0, 0, 1, 0, 0, 1]
[0, 0, 1, 1, 0, 0, 1]
3
4
[1, 1, 1, 1, 0, 0, 0]
16
Phases: selection (techniques)
Evaluation
Initialization
Breeding
Selection
• Roulette-wheel [12]
• Selection probability is proportional to individual’s fitness
4
5 [0, 0, 1, 1, 0, 1, 1]
[1, 0, 1, 1, 0, 1, 1]
3
[0, 0, 1, 1, 0, 0, 1]
5
[1, 0, 0, 1, 1, 1, 1]
4
[1, 1, 1, 1, 0, 0, 0]
2
[0, 0, 0, 1, 0, 0, 1]
• Others… [13]
17
Phases: breeding
Initialization
Evaluation
Breeding
Selection
• Selected individuals cross-over
• New individuals fill up the next generation of individuals
• Selection and breeding phases are performed till next population is filled
Parents
[1, 0, 1, 1, 0, 1, 1]
[1, 0, 0, 1, 1, 1, 1]
Offspring
[1, 0, 0, 1, 0, 1, 1]
[1, 0, 1, 1, 1, 1, 1]
18
Phases: breeding (techniques)
Evaluation
Initialization
• Some times features cannot be mixed
Breeding
Selection
• Smarter operations need to be applied
• For example:
Parents
[4.5, “left”, false, true, 9] [1.2, “right”, true, true, 9]
• Depends on the problem
• Number: average, max, min, sum, ..
• Boolean: and, or, xor, …
• Strings: concatenate, replace, remove, split, …
19
Phases: mutation
• With a very little likelihood
• A random modification is applied
Evaluation
Initialization
Breeding
Selection
[1, 0, 0, 1, 0, 1, 1]
[1, 0, 0, 0, 0, 1, 1]
20
Phases: mutation (techniques)
• Any modification can be consider as a mutation
[1, 0, 0, 1, 0, 1, 1]
[1, 0, 0, 1, 0, 1, 1]
[1, 0, 0, 0, 1, 1, 1]
[1, 1, 0, 1, 0, 0, 1]
Evaluation
Initialization
Breeding
Selection
• More complex genomes could have their features modified to any
possible value
[4.5, “left”, false, true, 9]
[4.5, “right”, false, true, 9]
[0.5, “right”, false, true, 9]
[4.5, “right”, false, false, 9]
21
Phases: evaluation, selection, breeding, …
• The loop keep going till the optimal individual is found
[1, 1, 1, 1, 1, 1, 1]
7
Evaluation
Calculate fitness for
each individual
Breeding
Selection
Individuals are crossedover and mutations take
place
Choose individuals for
breeding
22
Evolutionary Computation research tool (ECJ)
• Developed at the George Manson University [10]
• Eliminates the need of implementing the evolutionary process
• Highly used in the community
• Main features:
•
•
•
•
•
•
Multi-platform: Java
Flexibility: easy to implement many kind of problems
Configuration files
Check points
Multi-threading
Pseudo-random number generator: reproduce results
23
Evolutionary Computation research tool (ECJ)
• Code architecture allows
pluggable and customized
components
• Several built-in
implementations for every
component
24
Evolutionary Computation research tool (ECJ)
• Configuring the MaxOne problem
breedthreads = 1
evalthreads = 1
seed.0 = 4357
state = ec.simple.SimpleEvolutionState
pop = ec.Population
init = ec.simple.SimpleInitializer
finish = ec.simple.SimpleFinisher
breed = ec.simple.SimpleBreeder
eval = ec.simple.SimpleEvaluator
stat = ec.simple.SimpleStatistics
exch = ec.simple.SimpleExchanger
pop.subpops = 1
pop.subpop.0 = ec.Subpopulation
pop.subpop.0.size = 10
pop.subpop.0.species = ec.vector.BitVectorSpecies
pop.subpop.0.species.fitness = ec.simple.SimpleFitness
pop.subpop.0.species.ind = ec.vector.BitVectorIndividual
pop.subpop.0.species.genome-size = 20
pop.subpop.0.species.mutation-type = flip
pop.subpop.0.species.mutation-prob = 0.01
pop.subpop.0.species.pipe = ec.vector.breed.VectorMutationPipeline
pop.subpop.0.species.pipe.source.0 = ec.vector.breed.VectorCrossoverPipeline
pop.subpop.0.species.pipe.source.0.source.0 = ec.select.TournamentSelection
pop.subpop.0.species.pipe.source.0.source.1 = ec.select.TournamentSelection
generations = 200
eval.problem = ec.app.tutorial1.MaxOnes
25
Evolutionary Computation research tool (ECJ)
• Implementing the MaxOne fitness function: ec.app.tutorial1.MaxOnes
26
Evolutionary Computation research tool (ECJ)
• Execution
27
Questions?
28
Applying natural evolution for solving
computational problems
First lecture: Introduction to Evolutionary Computation
Second lecture: Genetic Programming
References
• [1] https://en.wikipedia.org/wiki/Evolutionary_algorithm
• [2] W. Greenwood, Garrison; Tyrrell, Andrew M. (2006-10-20). Introduction to Evolvable Hardware: A
Practical Guide for Designing Self-Adaptive Systems (1 ed.). Wiley-IEEE Press. ISBN 978-0471719779.
• [3] Maimon, Oded; Braha, Dan (1998). "A genetic algorithm approach to scheduling PCBs on a single
machine" (PDF). International Journal of Production Research.
• [4] BiSNET/e – Distributed Software Systems Group, University of Massachusetts, Boston
• [5] D. Lanza, F. Chavez, F. Fernandez, C. Benavides-Alvarez and J. Villegase, Speeding up Evolutionary
Approaches to Face Recognition by Means of Hadoop. EVO 2016
• [6] Haleh Vafaie and Kenneth De Jong. Genetic Algorithms as a Tool for Feature Selection in Machine
Learning. Center for Artificial Intelligence, George Mason University
• [7] https://en.wikipedia.org/wiki/List_of_genetic_algorithm_applications#cite_note-56
• [8] Andre C. Marta. Parametric Study of a Genetic Algorithm using a Aircraft Design Optimization
Problem. Stanford University, U.S.A.
• [9] I. Kroo. Aeronautical Applications Of Evolutionary Design. Stanford University, U.S.A.
• [10] https://cs.gmu.edu/~eclab/projects/ecj/
30
References
• [11] Miller, Brad; Goldberg, David (1995). "Genetic Algorithms, Tournament Selection, and the
Effects of Noise". Complex Systems. 9: 193–212.
• [12] A. Lipowski, Roulette-wheel selection via stochastic acceptance (arXiv:1109.3627)
• [13] http://www.geatbx.com/docu/algindex-02.html
31