Literature
Introduction to evolutionary algorithms
Bioinspired and soft-computing Eiben A. E., Smith J. E., "Introduction to Evolutionary Computing", 2nd ed., Springer, 2015.
methods in data analysis and https://link.springer.com/book/10.1007/978-3-662-44874-8
optimization Evolutionary multiobjective optimization
Bechikh S., Datta R., Gupta A., "Recent Advances in Evolutionary Multi-objective
Optimization", Adaptation, Learning, and Optimization series vol. 20, Springer, 2017.
Introduction
https://link.springer.com/book/10.1007/978-3-319-42978-6
Estimation of Distribution Algorithms (EDAs)
Krzysztof Michalak Larrañaga P., Lozano J. A., "Estimation of Distribution Algorithms", Genetic Algorithms and
krzysztof.michalak@ue.wroc.pl Evolutionary Computation series vol. 2, Springer, 2002.
https://krzysztof-michalak.pl/
https://link.springer.com/book/10.1007/978-1-4615-1539-5
Literature Soft computing
A Handbook of Computational Intelligence Algorithms tolerant of imprecision, uncertainty,
Kacprzyk J., Pedrycz W., "Springer Handbook of Computational Intelligence", Springer
Handbooks series, Springer, 2015.
partial truth and approximation
https://link.springer.com/book/10.1007%2F978-3-662-43505-2 Many methods are non-deterministic
Able to provide acceptable solutions to complex
These books are free to download from the UEW network problems in a reasonable time
(http proxy, virtual machines or labs)
Examples of methods
Note, that on many slides additional sources are cited (books, neural networks
papers, web pages, etc.) fuzzy logic
evolutionary algorithms
probabilistic reasoning
3 4
Bio-inspired computing Bio-inspired computing
Computational methods based on the principles of The focus is on computing, not biology
biology and the natural world
Do not push the metaphors too far![1]
Artificial Algae Algorithm Frog Call Inspired Algorithm Reincarnation Concept Optimization
Inspired by African Buffalo Optimization Grey Wolf Optimizer Rhino Herd Behavior
Andean Condor Algorithm Jaguar Algorithm Shark Search Algorithm
Biological evolution (e.g. genetic algorithms) Ant Lion Optimizer Killer Whale Algorithm Shark Smell Optimization
African Wild Dog Algorithm Krill Herd Social Spider Optimization
Organism structure (e.g. neural networks) Bald Eagle Search Laying Chicken Algorithm Sperm Whale Algorithm
Organism behaviours (e.g. particle swarm optimization) Bison Behavior Algorithm Locust Swarms Optimization Spotted Hyena Optimizer
Binary Whale Optimization Algorithm Monarch Butterfly Optimization Squirrel Search Algorithm
Cheetah Based Algorithm Naked Moled Rat Swallow Swarm Optimization
Chicken Swarm Optimization Nomadic People Optimizer Wasp Colonies Algorithm
Not to be confused with bioinformatics (computatio- Cultural Coyote Optimization Algorithm Pity Beetle Algorithm Wolf Colony Algorithm
nal methods and software tools for understanding Egyptian Vulture Optimization Algorithm Red Deer Algorithm Zombie Survival Optimization
biological data) [1] Molina D. et al. "Comprehensive Taxonomies of Nature- and Bio-inspired Optimization: Inspiration Versus Algorithmic
5 Behavior, Critical Analysis Recommendations", Cognitive Computation, vol. 12, p. 897–939, Springer, 2020. 6
1
Bad practices Good practices
Too much focus on biological details Study general principles (e.g. evolution)
Are the flight patterns of the andean condor relevant?
Understand key components (e.g. selective pressure,
Seemingly "novel" methods[1] crossover, mutation)
Oh, the Cheetah Algorithm has already been published?
Perform abstraction of concepts (e.g. mutation a
Let's "invent" a Spotted Hyena Algorithm!
mechanism for increasing the diversity)
Lack of connection between the biological
phenomenon and the problem at hand Design new components with the solved problem in
mind
Why do you think the killer whale is good at solving a
schedule optimization problem? Think outside the (biological) box (e.g. differential
[1] Camacho Villalón Ch. L. et al. "Grey Wolf, Firefly and Bat Algorithms: Three Widespread Algorithms that Do Not Contain
evolution, EDAs)
Any Novelty", in: Dorigo M. et al. (eds) Swarm Intelligence. ANTS 2020. Lecture Notes in Computer Science, vol. 12421,
Springer, 2020. 7 8
Current trends Heuristics
Focus on mathematical foundations A heuristic is a problem-solving approach
A practical method
Study of the algorithmic behaviour
Not guaranteed to be optimal, perfect, or rational
Understanding of the connection between the
Often dedicated to a particular problem
problem and the method
More formally: a function that ranks alternatives in search
Study of optimization problem landscapes algorithms
Combining various approaches (e.g. evolutionary Examples:
optimization with machine learning) Packing problems: pack larger items first
The Knapsack Problem: sort items by the value-to-weight ratio
vi / wi
The Travelling Salesman Problem: always go to the nearest city
9 10
Metaheuristics Metaheuristics
High-level approaches Make few assumptions about the optimization
problem being solved
Algorithm design schemes
Usable for a variety of problems
Example – the Simple Genetic Algorithm (SGA) For a specific problem
initialize a population of solutions How to represent a solution? (e.g. a binary vector, a
while <stopping condition not met>
permutation)
select parents
reproduce How to evaluate a solution?
mutate
Note, that none of these For the chosen representation
steps is problem-specific!
How to implement the operators? (e.g. a single-point vs. a
11
uniform crossover) 12
2
Difficult optimization problems
Large search space, e.g. O(n ) = 2n or O(n ) = n !
Complex relationship between the input variables
and the evaluation of solutions. For example, in
some enginering problems.
Some application areas
Evolved X-band Antenna
For NASA's ST5 Mission[1]
[1] Gregory S. Hornby et al. "Automated Antenna Design with Evolutionary Algorithms"
https://ti.arc.nasa.gov/m/pub-archive/1244h/1244%20%28Hornby%29.pdf
13 14
Difficult optimization problems Simulation-based optimization
Multimodal functions, such as the Rastrigin function[1] Suitable for complex systems
Example: network phenomena
Epidemics
Financial contagion
Approach
Start with an outbreak
Apply countermeasures
(vaccination, social distancing)
Simulate the epidemic
Evaluate the solution by calculating the
costs of vaccinations, isolation, hospitalizations
[1] K. Michalak, M. Giacobini, "The Influence of Uncertainties on Optimization of Vaccinations on a Network of Animal
[1] https://en.wikipedia.org/wiki/Rastrigin_function 15 Movements", Soft Computing (IF2021 = 3.732), vol. 25, pp. 4907-4923, ISSN: 1432-7643, Springer, 2021. 16
Poorly understood problem domains Poorly understood problem domains
The relationship between the control parameters Example: generating hard Inventory Routing
and the outcome is complex and not well Problem instances[1]
understood IRP is a generalization of the TSP
Complex algorithms in which vehicle routes have to be
Simulations optimized along with delivery
schedules
Real-life problems
Goal: find such IRP instances
It is hard to predict which parameters make the which take a long time to solve
using commercial solvers
difference (e.g. CPLEX, Gurobi)
Given x we can calculate (simulate) f(x)
Note, that it is not about solving
We cannot calculate how to change x to improve f(x) IRP instances, but finding them
(as opposed to e.g. differentiable functions for which the gradient
[1] K. Michalak, "Generating hard inventory routing problem instances using evolutionary algorithms", GECCO '21 Proceedings
shows the direction of the fastest increase of the function value) of the Genetic and Evolutionary Computation Conference, Lille, France - July 10-14, 2021, ISBN: 978-1-4503-8350-9, pp. 243-
17 251, ACM New York, NY, USA, 2021. 18
3
Poorly understood problem domains Poorly understood problem domains
Example: generating hard Inventory Routing Example: generating hard Inventory Routing
Problem instances Problem instances
Problem: it is poorly understood what may cause an IRP Approach:
instance to be difficult
Describe each IRP instance
Another problem: commercial solvers use complex, as a vector of numbers
proprietary algorithms Start with a population of such
instances (real vectors)
Attempts so far: very regular, symmetric designs,
criticized as "artificial" Sit back, relax, and let the evolution do it's job (buy lots of
popcorn, it will take time!)
Result: the solving time dozens to thousands times longer than for
reference instances taken from the literature
Caveat: I have no idea why these instances are so hard
19 20
Cannot calculate the goal function? Cannot calculate the goal function?
Can we optimize even if we cannot calculate the Optimization of experiments, production processes
goal function? Start with some parameters
Not even using complex algorithms, not even Do the experiment (in real world)
simulations? Feed back the experiment results into the computer
Modify the solution
Can you think of such situations?
?
Interactive optimization
Interaction with the environment or with the user
The user evaluates proposed solutions
No known computational model for user behaviour!
21 22
Evolutionary art and design Evolutionary art and design
User-interactive approach Evolved Elbo chair[1]
Present the user with some proposed objects Known chair designs as examples
Get the feedback and select the best ones Physical requirements (e.g. load-bearing ability)
Crossover and mutate
User-interactive design
Example: customising fashion through evolution[1] selection
[1] Nuno Lourenco et al., "EvoFashion: Customising Fashion Through Evolution", in: J. Correia et al. (Eds.): EvoMUSART 2017,
LNCS 10198, pp. 176–189, 2017. DOI: 10.1007/978-3-319-55750-2 12 23 [1] https://www.wired.com/2016/10/elbo-chair-autodesk-algorithm/ 24
4
Advantages of soft-computing Advantages of soft-computing
Can provide good enough solutions relatively fast Useful for a wide range of problems
Large search spaces
Good when we prefer
Complex solution evaluation (computationally costly,
speed to precision
simulation-based, user-interactive)
Poorly understood problems (it suffices to calculate if the
Can work with
evaluation of a solution changes, not why)
imprecise information
source: https://www.mdpi.com/2227-7390/8/6/875/htm
Multi-objective, multi-modal, and dynamic (with the goal
function changing in time)
Can be applied to a variety of problems easily (e.g.
compared to mathematical solvers which require Noisy and stochastic optimization
detailed mathematical models)
25 26
Disadvantages of soft-computing Competitive exact methods
Often, no guarantees on solution optimality Good exact solvers for some problems (e.g. TSP)
Can be overcome by combining with exact methods The TSP has been solved to optimality
for n = 85900[1]
Hard to understand why a given solution was The PLA85900 problem from the TSPLib[2]
obtained Search space size: n ! = 9.61 10386526
Current research area: Explainable AI The Concorde solver[3]
Combination of a branch-and-bound search and problem-specific
For well-studied problems very efficient exact heuristics
methods are known, competitive to soft-computing 15 years of research![4]
ones Note, that this was a specific TSP instance (e.g. Euclidean,
symmetrical)
[1] https://www.math.uwaterloo.ca/tsp/pla85900/index.html
[2] http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/
[3] https://www.math.uwaterloo.ca/tsp/concorde.html
[4] https://www.math.uwaterloo.ca/tsp/pla85900/heur/heur.htm
27 28
Competitive exact methods Combining with exact methods
Good exact solvers for some problems (e.g. TSP) A drawback of approximate methods: in many cases
The TSP has been solved to optimality the optimality of a solution cannot be proven
for n = 85900[1]
On the other
The PLA85900 hand,
problem among
from the the best[2]
TSPLib results [4] there A possible approach to address that problem:
is a Hybrid Genetic Algorithm
Search space size: n ! = 9.61 10386526 Combine an inexact method with a branch-and-bound
Hybrid Genetic
The Concorde solver[3] Algorithm: 142,383,467 search
Lin-Kernighan-Helsgaun (LKH): 142,382,641
Combination of a branch-and-bound search and problem-specific Find an approximate solution fast
heuristics Gap: 0.00058%
Use the best known solution as a bound
15 years of research![4]
Note, that this was a specific TSP instance (e.g. Euclidean,
The branch-and-bound method can work on a smaller
symmetrical) search space
[1] https://www.math.uwaterloo.ca/tsp/pla85900/index.html Example: in the Travelling Salesman Problem knowing a
[2] http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/
[3] https://www.math.uwaterloo.ca/tsp/concorde.html
tour of a given length excludes many candidate solutions
[4] https://www.math.uwaterloo.ca/tsp/pla85900/heur/heur.htm
29 30
