Transcript EAs D2

Evolutionary Algorithms
Group D2
Evans-Thomson
Woods
Wei
Yuntian
Recap of Evolutionary Algorithms
Evolutionary Algorithms are :
• A family of search and optimization techniques that make use of principles of
Charles Darwin’s theory of biological evolution : the random chance of
variation (Mutation, Crossover), coupled with the law of selection (Fitness
function and selection), is a problem-solving technique of immense power
and nearly unlimited application.
Flowchart of Evolutionary Algorithms
•
Initialize a usually random population
of chromosome
•
Evaluate fitness of all initial individuals
of population
•
Test for termination criterion
•
Select parents for offspring production
•
Recombine the "genes" of selected
parents
•
Perturb the mated population
stochastically
•
increase the generation counter
Fitness Function
• A function which takes a candidate solution to the problem as input and
produces as output how “fit” or how “good” the solution is with respect to the
problem in consideration.
• Once the fitness values are evaluated, the chromosomes are arranged based
on their fitness values. The purpose behind this arrangement is to assign a
selection value.
Three Major Operations
Selection
• Parents are selected according to
their fitness.
• The better ( the higher fitness value
) the chromosomes are, the higher
the chances for that chromosome to
be selected as a parent of next
generation.
Three Major Operations
Crossover
• After selecting two parents from the
existing population, two randomly
selected crossing points are sampled
and two offspring generated as a
result of the crossover.
• Typically, crossover, which involves
two chromosomes swapping pieces,
leads near the beginning of the
optimization, while at later stages,
mutation drives the search.
Three Major Operations
Mutation
• Mutation is a genetic operator used
to maintain genetic diversity from
one generation of a population of
EAs chromosomes to the next.
Applications of Evolutionary Algorithms
• Dynamic Process Control
• Simulation of models of behavior and evolution
• Complex design of engineering structure
• Pattern Recognition
• Scheduling
• Transportation and Routing
• Layout and Circuit design
Sunlight Concentrator
Design
Using Evolutionary Algorithms
Source
Sunlight Concentrator Design Using a Revised Genetic Algorithm
Kung-Jeng Wang, Jheng-Wei Yang, 2014
Department of Industrial management, National Taiwan University of
Science and Technology
Problem Details
Design a matrix of square prisms that directs as much
of the incident sunlight to the guiding fibres as
possible while minimizing manufacturing complexity.
System Design Parameters:
● Which of the 7 prism types is placed in each
grid position.
● The number of guiding fibres.
● The position of the guiding fibres on the
perimeter.
Why Use an Evolutionary Algorithm?
• Combinatorial problem with a large search space.
• Current methods are computationally expensive and rely on the biased
experience of the operator.
• Easily Encodable Solution Format
• Efficient Quantization of Fitness
Genetic Encoding
Prisms
•
I x J matrix with values from 1 to 7.
Guiding Fibres
•
2I + 2J boolean array.
Fitness Function
Brightness
Symmetry
•
Amount of light reaching the guiding fibres.
•
Measure of manufacturability.
•
Calculated with a basic simulation.
•
Calculated by counting matches in corresponding
grid positions.
•
Weighted at 60%.
•
Diagonal symmetry was chosen.
•
Weighted at 40%.
Algorithm Overview
Evaluation → Fitness Function
Selection → Duplicate the Fittest
Reproduction
•
Roulette Wheel Duplication
•
Crossover [single-point, row/col, area, block]
•
Mutation
•
Random Selection
Merge Population with Fittest Members.
Crossover and Mutation
Multiple Experiments
•
Single-point Crossover
•
Row and Column Crossover
•
Area Crossover
•
Block Crossover
•
Single-point Mutation → Mutation Rate 0.1
Single-point
Row and Column
Area
Block
Results
Benchmarks
Score
Brightness
•
Original Design
•
53.11
Brightness (Lumen)
•
54.78
Score
•
Random Search
•
98.47
•
•
36.48
Score
Block Crossover
•
328.86
Brightness (Lumen)
•
127.86
Score
•
Area Crossover
•
337.48
Brightness (Lumen)
•
123.32
Score
Brightness (Lumen)
Maximized Score
Maximized Brightness
Results
Music
Composition
Using Evolutionary Algorithms
Source: Kaliakatsos–Papakostas, M. A., Floros, A., & Vrahatis, M. N.
(2013, April). EvoDrummer: Deriving rhythmic patterns through
interactive genetic algorithms. In International Conference on
Evolutionary and Biologically Inspired Music and Art (pp. 25-36).
Springer Berlin Heidelberg.
What is the Problem?
• Aim: Produce sounds that are both
pleasant and intriguing.
Source: http://www.rollingstone.com/music/artists/kiss
• Can we formulate music creation
processes?
• How do we teach a computer to produce
music that sounds “good”?
Source: http://blitz.arc.unsw.edu.au/2016/every-single-thing-thats-dumb-taylorswift/
Why Use an Evolutionary Algorithm?
• Think of all of the possible combination of notes and rhythms as a large search
space.
• EAs can search this space with an element of randomness (mutation) and
produce multiple solutions.
• There is no “optimum” solution in creative arts, but EAs can return a number of
“good” solutions.
Composing Music using Evolutionary Algorithms
Two key methods of music composition using evolutionary algorithms:
• Interactive Evolution - eg. CONGA
• Feature Based Evolution - eg. evoDrummer
Sometimes used in conjunction with Neural Networks
Composing Music Using Evolutionary Algorithms
Interactive Evolution:
• A human user is considered
the “fitness function”.
• Criticisms because it is
subjective depending on the
human
Source: http://www.generativeart.com/on/cic/2000/ga2000-tokui.htm
Case Study: evoDrummer
• Introduced at the EvoMUSART conference in 2013.
• Uses the idea of rhythm divergence to automatically create drum rhythms.
• Demonstration: https://www.youtube.com/watch?v=sLydFlm6m8c
EvoMUSART Conference - Amsterdam 2017
See information at:
http://www.evostar.org/2017/about_evostar.php
How does evoDrummer work?
• Input:
A. base rhythm
B. divergence rate
• Output: rhythm
• Algorithms: genetic algorithm
Genetic Encoding
How could we represent the drum rhythms?
Chromosome (individual drum rhythms) : rhythm matrix
•
row (the number of instruments i.e. hit-hat,kick drum)
•
column (certain time-division of a music measure)
Initial Population
How is the population initialised?
• A set of rhythm matrices is derived from the base rhythm using a blending
ratio from 0 to 1
• 0 : produces a set of completely random rhythms
• 1 : produces a set of exact copies of the base rhythm
Evolution Children
How to realize the evolution?
The evolution of the initial and the subsequent generations is realized through the
utilization of standard genetic operators.
Crossover : exchange of equally sized random parts between two chromosomes.
result is two new chromosomes(genotype), called children.
Mutation : acts on the chromosome by assigning a random value to a random
element.
Fitness Evaluation
How could we choose the children?
Rhythm Divergence
Feature array:
Characterizes each drum rhythm converted from
chromosome
Fitness Evaluation
Fitness function
Base rhythm with a feature array r
base and the novel rhythm
, novel rhythm with a feature array
. Then, the fitness of rhythm
is :
, desired divergence between
References
What is a Genetic Algorithm (EA). (n.d). Retrieved from https://www.cs.cmu.edu/Groups/AI/html/faqs/ai/genetic/part2/faq-doc-2.html
Dieterle, F. (2006). Variable Selection by genetic algorithms. Retrieved from http://www.frank-dieterle.de/phd/2_8_5.html
Obitko, F. (1998). Introduction to Genetic Algorithms: Selection. Retrieved from http://www.obitko.com/tutorials/genetic-algorithms/selection.php
Zad, D. D., Araabi, B. N., & Lucas, C. (2005). A Novel Approach to Automatic Music Composing: Using Genetic Algorithm. Information Systems, 551-555.
Biles, J. A. (1997). GenJam: An interactive genetic algorithm jazz improviser.The Journal of the Acoustical Society of America, 102(5), 3181-3181.
Al-Battaineh, H., & AbouRizk, S. Optimization of Intermediate-Level Budget Allocation Using a Genetic Algorithm. Architecture, Engineering and Construction, 144.
Burton, A. R., & Vladimirova, T. (1998). Genetic algorithm utilising neural network fitness evaluation for musical composition. In Artificial Neural Nets and Genetic
Algorithms (pp. 219-223). Springer Vienna.
Wang, K. J., & Yang, J. W. (2014). Sunlight concentrator design using a revised genetic algorithm. Renewable Energy, 72, 322-335.
Tokui, N., & Iba, H. (2000). Music composition with interactive evolutionary computation.
Kaliakatsos–Papakostas, M. A., Floros, A., & Vrahatis, M. N. (2013, April). EvoDrummer: Deriving rhythmic patterns through interactive genetic algorithms. In International
Conference on Evolutionary and Biologically Inspired Music and Art (pp. 25-36). Springer Berlin Heidelberg.