2005cec-tutorial

Informations

• Publié par: Nizur
• Nombre de lectures: 8
• Langue: English

Extrait

An Introduction to Time
Complexity of Evolutionary
Algorithms
Tutorial for CEC’2005
(Draft)
Jun He and Xin Yao
Centre of Excellence for Research in Computational Intelligence and Applications
School of Computer Science
The University of Birmingham
– p.1Aim and Outline
Aim
To give an intuitive introduction to time complexity of
EAs, rather than a rigorous mathematical proof, which
can be found in the relative references.
To raise questions, rather than answer them.
Outline
Part A: short introduction to time complexity
Part B: time complexity of EAs and research issues
Part C: selected works
Part D: open questions
– p.2

A1. Time Complexity
Time complexity is used to measure the efficiency of an
algorithm and hardness of a problem.
“The time complexity of a problem is the number of
steps that it takes to solve an instance of the problem,
as a function of the size of the input, (usually measured
a
in bits) using the most efficient algorithm”.
“To understand this intuitively, consider the example of
an instance that is bits long that can be solved in
steps. In this example we say the problem has a time
complexity of . Of course, the exact number of steps
will depend on exactly what machine or language is
a
being used”.
a
From Wikipedia.
– p.3A2. Decision Problems
So many different problems, however in theoretical
computer science,
“Much of complexity theory deals with decision
problems. A decision problem is a problem where the
a
answer is always YES/NO”.
“Decision problems are often considered because an
arbitrary problem can always be reduced to a decision
a
problem”.
So many algorithms, however in theoretical computer
science,
The Turing machine can simulate arbitrary algorithms. It
is taken as a formal model for algorithms.
a
From Wikipedia.
– p.4A3. Complexity Classes
“The complexity class P is the set of decision problems
that can be solved by a deterministic machine in
polynomial time. This class corresponds to an intuitive
idea of the problems which can be effectively solved in
a
the worst cases”.
e.g., maximum flow, maximum matching problems.
“The complexity class NP is the set of decision
problems that can be solved by a non-deterministic
machine in polynomial time. This class contains many
problems that people would like to be able to solve
a
effectively”.
e.g., TSP, subset sum.
a
From Wikipedia.
– p.5A5. Experiment vs Theory
Experimental study: run an algorithm.
Easy to implement, an intuitive guidance in practice.
Only cover limited instances.
Theory: make a mathematical analysis.
Cover all instances.
Analysis is difficult.
Note: some algorithms are exponential in theory, but
have a good performance in practice, e.g., the simplex
method for linear programming; in contrast, some
algorithms are polynomial in theory but impractically
a
slow, e.g., the ellipsoid algorithm.
a
Papadimitriou. Computation complexity. Addison-Wesley. 1994
– p.6B1. Time Complexity in EAs
Time complexity is,“in EAs, performance measure,
usually the expected value or the order of the number of
generations or evaluations of the objective function
required for locating or approximating the optimum of a
given objective function. The time complexity depends
on the problem size and the search space dimension,
a
respectively”.
Given a problem, the time complexity of the problem
to EAs is the number of steps needed by the most
efficient EA.
Given an EA for a problem, the time complexity of
the problem to the EA is the number needed of steps
needed by the EA.
a
From Glossary Evolutionary Algorithms. http://ls11-www.cs.uni-dortmund.de.
– p.7B2. Research Issues
Formal models of EAs: how to describe EAs and
understand them?
Worst-case analysis: what is the worst performance of
an EA for solving a problem?
Average-case analysis: what is the average
performance of an EA?
Approximate algorithm: can an EA find a satisfying
solution quickly?
Parallelism: what kind of speedup if run an EA in a
parallel computing system?
Complexity classes: what kind of problems are hard or
what kind of problems are easy to EAs?
– p.8B3. Formal models of EAs
Can we establish a unified formal model for EAs? If
does, how to model EAs?
“Evolutionary algorithm (EA) collective term for all
variants of (probabilistic) optimization and
approximation algorithms that are inspired by Darwinian
evolution. Optimal states are approximated by
successive improvements based on the
variation-selection-paradigm. Thereby, the variation
operators produce genetic diversity and the selection
a
directs the evolutionary search.”
Note: although a definition of EAs is given as above, it
is still difficult to formalize EAs.
a
From Glossary Evolutionary Algorithms. http://ls11-www.cs.uni-dortmund.de
– p.9B4. Markov Model of EAs
Markov chains is widely used in EAs as a mathematical
model of EAs: individuals or populations as the states
of Markov chain; crossover, mutation, selection
operators are described by probability transitions.
If the transition matrix is known, then the exact
expected number of generations of EAs to find a
a
solution can be obtained from Markov chain theory.
If the bounds of the transition matrix are known, then
the of expected number of generations of
a
EAs can be drawn out too.
Limitation: in most of cases, it is hard to obtain or
estimate the transition probabilities.
a
He and Yao. Artificial Intelligence , 145(1-2):59-97, 2003
– p.10