Course on
Metaheuristics
for Combinatorial Optimization Problems
Prof. Pablo Moscato
Comision de Investigaciones Cientificas
de la Provincia de Buenos Aires
CeTAD - Universidad Nacional de La Plata
Universidad Nacional del Centro de la Provincia de Buenos Aires
ARGENTINA
Textbook
The course will follow our book which deals with this subject
Optimizacion Heuristica y Redes Neuronales,
Editorial Paraninfo, Madrid, Espaņa, (1996), ISBN 84-283-2269-4.
In addition, we will also use some other papers, technical reports available
on-line, surveys, etc., which will cover some other topics not included
in the book.
Contents of the Course
Introduction to metaheuristics
Computational Complexity.
Heuristics and approximation algorithms.
Hill-climbing or iterative improvement heuristics,
can they take exponential
time ?
What is a metaheuristic ?
The new metaheuristics.
Simulated Annealing
Metropolis algorithm. Monte Carlo methods in Physics and Chemistry.
Physical analogies of Simulated Annealing (SA) and basic algorithm.
The annealing schedule, diferent theories for its selection.
Computational implementation.
Convergence.
The Number Partitioning problem, the chronicle of a failure of
SA. Applications of SA. Other acceptation functions.
Correlations between local minima.
GRASP
Introduction. GRASP, its strategies and components.
Design of a GRASP. Local search. Applications.
Genetic Algorithms
The analogies of Genetic Algorithms (GAs) with the true evolutionary processes.
Basic elements of a GA.
Selection of an initial population. ``Fitness'' and scaling problems
related with its selection regarding the true objective function.
Characteristics of good crossover operators.
Holland's Schema Theorem.
Forma Analysis.
Corner formae and the TSP.
The concept of ``deceptiveness'' and ``GA-Hardness''.
Tabu Search
Introduction. Basic techniques.
Short term memory. Long term memory. Estrategic Oscillation.
Path-relinking. Applications.
Memory structures. Recency and frequency based memory.
Path relinking and Scatter Search.
Memetic Algorithms
Memetic algorithms fundamentals.
Correlation of local optima reconsidered.
Application to the Euclidean TSP.
The National Hockey League schduling problem.
Application to graph coloring.
The binary perceptron learning problem.
Neural Networks
Biological facts. Artificial Neural Networks for
combinatorial optimization ? The TSP as a case study.
Hopfield's approach. Mean Field Theory. Kohonen's algorithm.
Elastic networks. The multiple salesman TSP.
Phase transitions on combinatorial optimation problems
The maximum satisfiability problem (MAX-SAT).
Approximation algorithm.
Integer programming formulation.
Markov Chains and Random Walks in graphs; a simple
algorithm for the 2-SAT problem.
Phase transitions on the RANDOM k-SAT problem.
Phase transitions on the Asymmetric Traveling Salesman Problem.
Phase transitions on the Two-Way Number Partitioning Problem.
On-Line problems
The online paging problem.
The k-server problem.
The list update problem.
The on-line routing problem in the plane.
Competitive Analysis.
Competitive Algorithms for the On-line Traveling Salesman.
Deterministic and randomized online algorithms.
Adversary models.
Adaptive adversaries.
Adaptive offline adversary.
Oblivious adversary.
Research Project
During the course, the students must complete a research project on
one NP-Hard Combinatorial Optimization problem.
A list of some of them and their
approximability status can be found in
A Compendium of NP Optimization Problems , by
P. Cresenzi and V. Kann.
The research project should involve a comparison of a good (hopefully the best)
heuristic or approximation algorithm for the problem, a metaheuristic
approach (like Tabu Search or Simulated Annealing,
for example) and a Memetic Algorithm.
For more information about the latter refer to
Memetic Algorithms' Home Page .
Since there will be no other practical work, we expect the students to
develop good projects on one problem of their selection and according with
their interests.
Guidelines for selecting a Research Project
Sudents must concentrate in developing good, clear tests, sound experimental
evidence, etc., so you should try to find a combinatorial problem that
is easy to state and minimize needed to have a code running and reach
results. If you are already involve in some research program
(working for a thesis, for example) then you may choose to select one
problem that is at the very core of the problem you are solving.
For example, if you are working in Timetabling, then it would be wise to
choose Satisfiability or Graph Coloring as your research problem project.
Conditions
For the purpose of the course, a ``good'' problem to study is one that
satifies most of the following conditions
Strong Conditions (highly required).
It is easy to state.
It is challenging to find near-optimal solutions.
It has relevance.
It has been the subject of many previous studies.
There are instances of the problem with known optimal solutions.
Weak Conditions (some preference).
It has some aspect where Geometry has some important role.
It is a core problem of others in Operations Research.
Candidate problems
Traveling Salesman Problem
One problem that satisfies all these requirements is the Traveling
Salesman Problem. For a comprehensive list of results you can
visit
TSPBIB Home Page.
Check in particular our recent papers and the memetic algorithms' page.
Graph Coloring
Another problem that fullfils most of the requirements is Graph Coloring.
It has application in Timetabling, Scheduling, Printed Circuit Board Testing,
Pattern Matching, among many others.
A good starting point to know about this is
Network Resources for Coloring a Graph , by Michael Trick.
but be aware that the Last Update of this page is was in October, 1994, and
many new results may be found somewhere else.
Number Partitioning
These is a simple problem, yet is very hard to address with heuristic
methods. Starting points, aside from the chapter of our textbook, are
"Problem Space Local Search for Number Partitioning",
H. Storer, S. Flanders, and S.D. Wu, to appear
in The Annals of Operations Research.
Phase transitions and annealed theories: Number partitioning as a case study
Ian Gent and Toby Walsh.
Proceedings of ECAI-96, pages 170-174, John Wiley and Sons 1996. Earlier
version available as
The Number Partition Phase Transition ,
Research Report 95-185, University of Strathclyde.
Other problems from Operations Research
If you are more interested in other
``real-life'' challenging problems, you should also try the
AI-OR Experimentalists Home Page
Steps to be taken
During the first two weeks, the students should find a research subject
they like such that they should satisfy most of the conditions detailed
above. We suggest that the students should also use some Internet browsers like
Altavista or
Lycos ;
to search for other information sites on the problem he/she is interested.
We expect the students to actively take part on Internet and Library
search.
After the first two weeks, the students must decide which particular problem
they would like to address. The name of the student and the problem she/he
is working in will appear on this page as well as links with relevant
information.
The next step will be to implement and test approximation algorithms (if they
are available for the problem) or the best heuristic known.
They can implement theoretical algorithms not previously
studied experimentally,
compare algorithms that performed well in earlier studies but had not
previously been directly compared,
test old algorithms on new instances, generate new classes of instances which
are hard to optimize, etc.
Then the student should also work on one of the techniques studied and
also to implement and test a memetic algorithm on the problem.
Results will be reported following the guidelines of
Designing and reporting on computational experiments with
heuristic methods,
by R. S. Barr, B. L. Golden, J. P. Kelly, M. G. C. Resende, and W.
R. Stewart,
Journal of Heuristics, vol. 1, pp. 9-32, 1995.
Candidate problems related with Geometry
There are many collections of open problems related with Geometry, some of
them involve NP-Hard optimization problems.
Application Challenges to Computational Geometry, by
The Computational Geometry Impact Task Force Report,
Tech. Rep. TR-521-96, Princeton University, April 1996.
Geometry in Action,
by David Eppstein.
The Geometry Junkyard ,
by David Eppstein.
Machine learning
Many aspects of Machine Learning involve geometric aspects and NP-Hard
optimization problems, a good starting point would be
A Geometric Framework for Machine Learning,
PhD Thesis by David Heath.
you can also see two other papers by the same author
Induction of Oblique Decision Trees,
by David Heath, Simon Kasif and Steven Salzberg.
Learning Nested Concept Classes with Limited Storage,
by David Heath,
Simon Kasif,
S. Rao Kosaraju,
Steven Salzberg,
and Gregory Sullivan.
The difficulty of teaching
can be found in another paper
The Complexity of Finding Minimal Voronoi Covers with
Applications to Machine Learning,
Computational Geometry Theory and Applications,
5:3, 1993, pp 289-305. We can read in their abstract
Our goal in this paper is to
examine the application of Voronoi diagrams, a fundamental concept
of computational geometry, to the nearest neighbor
algorithm used in machine learning. We
consider the question
``Given a planar polygonal tessellation T and an integer k, is there a set of
k points whose
Voronoi diagram contains every edge in T?'' We show that this question is
NP-hard. We encountered this problem
while studying a learning model in which we seek the
minimum sized set of training examples
needed to teach a given geometric concept to a nearest
neighbor learning program.
That is, given a concept which can be described by a planar
tessellation, we are seeking to construct the
smallest set of points whose Voronoi diagram is
consistent with the given tessellation.
In a sense, this question captures the difficulty of teaching
the nearest neighbor algorithm a simple structure,
using a minimal number of examples.
In addition, we consider the natural
inverse to the problem of computing Voronoi diagrams. Given
a planar polygonal tessellation T,
we describe an algorithm to find a set of points whose Voronoi
diagram is T, if such a set exists.
Finding Maximum Feasible Subsystems: A problem from Machine Learning and
other applicaitions
This problem has relevance for learning in artificial neural network systems
and many others, not only in the machine learning group. We select to
papers as starting points
The complexity and approximability of finding
maximum feasible subsystems of linear relations,
E. Amaldi, V. Kann,
Theoretical Computer Science 147:181-210, 1995.
NADA report TRITA-NA-9313, 1993.
On the approximability of some
NP-hard minimization problems for linear systems,
E. Amaldi, V. Kann,
Tech. report 95-7,
Cornell Computational Optimization Project, Cornell University, Ithaca, NY,
1995.
see also
Barycentric Correction Procedure - Efficient
Threshold Unit Training Method for
Constructive Algorithms,
Herve Poulard and Said Labreche,
Submitted for review to the IEEE
Transactions on Neural Networks.
Partial Shape Matching
Ender Ozcan has recently shown that a memetic algorithms is well-suited
for these problems. His paper on this subject is
Shape Recognition using Genetic Algorithms,
by Ender Ozcan and Chilukuri K. Mohan,
Proc. Int. Conf. on Evolutionary Computation, May '96.
Aircraft Routing
Another good starting point for those interested in NP-Hard optimization
problems and in particular in some Operations Research problems involving
routing is
Bernard Moret's list of publications
since many of them are available in postscript form.
Graph Drawing
Check this site for further references
GD96 Graph-Drawing Contest.
where you can find information about an on-going exciting challenge.
One of the graphs
represents the calls
made between a set of telephone numbers. Such graphs are used by the police in the investigation of
organized crime.
Covering points by rectangles
David Eppstein says about this problem:
Stan Shebs ,
discusses the problem of finding a minimum number of
copies of a given rectangle that will cover all points in some set,
and mentions an application to a
computer strategy game.
This is NP-hard, but I don't know how easy it is to approximate; most
related work I know of is on optimizing the
rectangle size for a cover by a fixed number of
rectangles.
Geometric methods for non-geometric problems
You can see D. Eppstein
page of publications
on the use of geometric-based methods for non-geometric problems.
See for example,
Choosing substs with maximum weighted average,
D. Eppstein and D. S. Hirschberg.
Tech. Rep. 95-12, ICS, UCI, 1995.
5th MSI Worksh. on Computational Geometry (1995) 7--8.
Simple models of protein folding
We are interested in the combinatorial optimization aspects of folding a
simple chain of hydrophobic-hydrophilic elements on a square lattice. The best
on-line reference we can give of this problem is
Fast Protein Folding in the Hydrophobic-Hydrophilic Model whithin
3/8 of Optimal, ,
by William E. Hart and Sorin Istrail.
many aspects of this model are yet unknown, for example, its computational
complexity. This is another challenging research area.
Please do not hesistate in contacting me about any further subject you
might be interested, as well as suggestions, additions and corrections
to this page.
Genetic Algorithms' Tutorials
Check
The GA Tutorials Notebook by Jaime J. Fernandez.
Mathematical Programming Glossary
Check
The Mathematical Programming Glossary,
by H.J. Greenberg.
Pablo Moscato
Comision de Investigaciones Cientificas de la Provincia de Buenos Aires
C.C. 75
1900 La Plata
ARGENTINA
email:
mos@ada.info.unlp.edu.ar
email:
pmoscato@volta.ing.unlp.edu.ar
Click
here
for my complete address and contact information.