Transcript Evolutionary Computation

Nature inspired modelling and
algorithms
Xiaodong Li
School of Computer Science and IT, RMIT University,
Melbourne, Australia
Email: [email protected]
URL: http://goanna.cs.rmit.edu.au/~xiaodong/
Topics
•
•
•
•
•
•
•
•
Introduction to Evolutionary Computation (EC)
Particle Swarm Optimization
Differential Evolution
Evolutionary Multiobjective Optimization
Optimization in dynamic environments
Coevolutionary models
Multimodal Optimization (Niching)
Large Scale Global Optimization
2
What is this course about?
• This course “Nature-inspired modelling and
algorithm” is mainly concerned with the use
of simulated biological and social evolution to
solve problems for which it can be difficult
using traditional methods. This course will
examine different models of evolutionary
computation and the kinds of problems they
can be used for.
3
Why “nature-inspired”?
Amazing colours and complex
patterns, at the Great Barrier Reef,
Australia.
4
Nature does the best
Human brain – a product of biological evolution over millions of years, is one of
the most complex and intelligent entity we ever know.
•
•
•
•
•
Number of neurons ~ 1010
Connections per neuron ~ 104-5
Neuron switching time ~ .001 seconds
Scene recognition time ~ .1 second
Massive parallel computation
5
Where it fits in Artificial Intelligence?
Web
Mining
Navigation
Vision
Planning
Lisp
Data
Mining
Factory
Robots
Games
Evolutionary
computation
Manipulation
Prolog
Machine
Learning
Robotics
Shells
Programming
Languages/Tools
KE Env.
Rules
Heuristic
Search
Problem
Solving
Hardware
SEARCH
Semantic Nets
Representation
Methods
Conceptual
Graph
Logic
Synthesis
AI
Knowledge
Acquisition
Applications
Neural
Networks
Vision
Medical
Imaging
Industrial
Inspection
Speech
Recognition
Written
Object
Recognition
Database
Query
Machine
Translation
Agents
Image
Processing
Applications
Pattern
Recognitions
Natural
Language
Knowledge
Representation
Knowledge
Engineering
Expert
Systems
Simulated
Annealing
Optimization
Mobile Agents
Softbots &
Games
Scene
Analysis
6
How do we run this course?
• This course runs in a mix of lecture/seminar mode where
key concepts are presented, and research articles are
discussed and analysed. Each class will consist of 1 hour
lecture and half hour discussion.
• Students are expected to read the prescribed research
papers before each class, and come to the class prepared
to discuss the concepts and issues involved.
• The class will be “interactive”. Students are encouraged
to ask questions at any time.
• Students are expected to participate actively in the
discussion, and sometimes take turns to lead the
discussion.
7
Pre-requisite and assumed knowledge
• Some knowledge of Artificial Intelligence;
• You are required to have programming skills in
Java, C, or C++, including basic data structures
and algorithms;
• Familiarity with Unix is strongly recommended.
8
Learning objectives
You will learn:
• The basic principles and techniques of evolutionary
algorithms and swarm intelligence.
• How to apply these techniques to optimisation
problems and problems that require machine
learning.
• How to compare different approaches to problems.
• How to read research papers in the area and lead a
discussion on current research issues.
9
Assessment
• Assignment#1: SGA-C programming and
experimentation (30%)
• Assignment#2: Research proposal (50%)
• Discussion leadership (10%)
• Discussion participation (10%)
• No exam (but group presentations)
10
Course website
• All course material, including lecture slides,
readings assignment specs are available for
download from the course website:
http://web.xidian.edu.cn/xlwang/course.html
• Lecture slides will be updated regularly as the
course proceeds.
• Discussion should happen in the QQ site
designed for this course.
11
Discussion and Participation
• Students encouraged to participate and lead the
discussion during the class. This involves preparing and
posting meaningful questions (related to the topic) to the
class QQ site, before the discussion takes place.
• Students will be assessed on:
-The quality of the focus questions proposed;
-The ability to involve classmates in a scholarly discussion;
-Evidence of careful preparation to facilitate useful discussion if
interaction is stalled;
• In the first class, we will provide an example of suitable
questions for a demonstration study topic, and lead an
example discussion.
12
Focus topic presentation
• The class will be divided into groups of 4 – 5 students,
and each group will be asked to prepare and give a
presentation on a focus topic.
• The presentation will be about 15 – 20 minutes, and all
group members should contribute to the content and
delivery of the presentation. There will be also 5 minutes
for the rest of class to ask questions.
• The focus topic for the presentation will be decided at
the start of the semester.
• The presentation will be assessed as part of participation
and leadership marks.
13
What is optimization?
• Optimization is the process of making
something better.
• An engineer or scientist conjures up a new idea
and optimization improves on that idea.
• Optimization consists in trying variations on an
initial concept and using the information gained
to improve on the idea.
14
Function to be optimized
Optimization is the process of adjusting the inputs to or characteristics
of a device, mathematical process, or experiment to find the minimum
or maximum output or result.
15
Examples of optimization problems
•
•
•
•
•
Aerodynamic design
Vehicle routing
Journey planning
University timetabling
etc
16
Airfoil Design
17
Journey planning
18
Vehicle routing
19
Warehouse storage
20
Six categories of optimization
21
Disadvantages of traditional
optimization methods
• Based on analytic forms, which require the
calculation of the gradient information.
• Need to know the mathematical formulation of
a problem first, and assume that its derivative
can be calculated. This is often not the case in
real world situations.
• Even with the gradient information, local
downhill direction often leads to a local
minimum.
22
Biological optimization
• Nature does computation the best!
• Natural Selection – survival of the fittest.
• Evolution Theory by Charles Darwin.
23
4 premises of Evolution Theory
• First, an offspring has many of the characteristics
of its parents. This premise implies that the
population is stable.
• Second, there are variations in characteristics
between individuals that can be passed from one
generation to the next.
• The third premise is that only a small percentage
of the offspring produced survive to adulthood.
• Finally, which of the offspring survive depends on
their inherited characteristics.
24
A Simple Flow chart of an EC
EC is an optimization and
search technique based
on the principles of genetics
and natural selection.
25
Advantages of EC
•
•
•
•
•
•
Optimizes with continuous or discrete variables,
Doesn’t require derivative information,
Simultaneously searches from a wide sampling of the cost surface,
Deals with a large number of variables,
Is well suited for parallel computers,
Optimizes variables with extremely complex cost surfaces (they
can jump out of a local minimum),
• Provides a list of optimum variables, not just a single solution,
• May encode the variables so that the optimization is done with
the encoded variables, and
• Works with numerically generated data, experimental data, or
analytical functions.
26
Binary Genetic Algorithms
27
Selection and Recombination
28
An example
We want to find the maximum of f(x) = x2 in [0, 31] where x is an integer
1. Encode the parameter(s) as a binary string:
5 bits are needed
2. Setup an initial population of random strings, such as
0 1 1 0 1
1 1 0 0 0
0 1 0 0 0
1 0 0 1 1
3. Compute fitness of each chromosome ...
*Note: this example is taken from the following book:
Goldberg, D. (1989), Genetic Algorithms in Search, Optimization and Machine Learning. Reading, MA: Addison-Wesley.
29
An example…
3. Compute fitness of each chromosome …
4. Select the fittest individuals.
5. Generate a new population using crossover and mutation based on
selected individuals.
30
Selection
Roulette wheel selection can be used during the selection of individuals for
reproduction.
- To each member of the population allocate space on the roulette
wheel in proportion to fitness.
- Spin the wheel and put string where it stops into the mating pool – a
tentative new population.
- Repeat until the mating is full.
This strategy ensures that the fittest individuals are more likely to be
selected for reproduction.
31
Crossover
The process of crossover:
- randomly select parent1 and parent2 from the mating pool without
replacement [This ensures that the string at each POSITION reproduces
exactly once]
- Randomly select crossover point k
- Swap genetic material
parent1: 0 0 0 0 0
child1: 1 1 0 0 0
parent2: 1 1 1 1 1
child2: 0 0 1 1 1
The above example is single point crossover
For a long chromosome use several ks (multi-point crossover)
32
Mutation
The process of mutation:
- Apply the MUTATION operator to the children.
Select and flip some bits with (very) low probability
- Place children in next generation
Example: Crossover point is 2
parent1: 0 0 0 0 0
child1: 1 1 0 0 0
parent2: 1 1 1 1 1
child2: 0 0 1 0 1
(Note: child2 has been changed by mutation operator)
33
An example (continues…)
We want to find the maximum of f(x) = x2 in [0, 31] where x is an integer
34
Flowchart of GA
35
Cost surface
36
Contour plot of the cost surface
37
An ‘kangaroo’ analogy
• Imagine that you fly a helicopter into Himalayas, and then
parachuted hundreds of kangaroos into the region at random
places. You hope that at least one of them will find Everest.
• A genetic algorithm begins like the following - these
kangaroos do not know that they are supposed to be looking
for the top of a mountain. Every few years, you shoot the
kangaroos at low altitudes and hope the ones that are left will
be fruitful, multiply, and ascend. Current research suggests
that fleas may be more effective than kangaroos in genetic
algorithms, since their faster rate of reproduction more than
compensates for their shorter hops.
38
De Jong function 2
39
Measuring performance
40
Questions for group presentation
•
•
•
•
•
•
What is Evolutionary Computation, and what is it about?
How does a Genetic Algorithm work? And Why?
What sort of applications GAs can be used for?
How to represent a problem?
What are the GA parameters?
How to setup a GA experiment and record the result?
41
Assignment 1
Due date: 9:30pm, Wednesday 25 March 2015
• You are required to use an existing program - SGA-C (see the handout) to
solve at least two optimization problems of your choice. Recommended
functions are De Jong’s test bed (see assignment#1 specs).
• You need to modify the original SGA-C code in order to complete the
required tasks.
• You need to show your experimental results on a plotted graph (say using
Excel spreadsheet, or gnuplot, jgraph). You should run your experiments
with various setups, e.g., a low or high mutation probability (or crossover
probability), a small or large population size.
• You should write a brief report on analysis of the experimental results.
• You need to hand in the assignment in hardcopy as well as a softcopy, to
your class representative. You may be required to demonstrate your GA
runs.
42
Readings on Genetic Algorithms
• Randy I. Haupt and Sue Ellen Haupt. Practical Genetic Algorithms,
Chapter 1 Introduction to Optimization, John Wiley and Sons New
York, 1998.
• Randy I. Haupt and Sue Ellen Haupt. Practical Genetic Algorithms,
Chapter 2 The Binary Genetic Algorithms, John Wiley and Sons
New York, 1998.
You can download the above two chapters from the course QQ site.
43