Tutorial 5
Memory and Evolution: Recent Advances in Metaheuristics Optimization
 |
Dr. César Rego E-mail: crego@bus.olemiss.edu |
Dr César Rego is Associate Professor of Management Information
Systems and Operations Management at the School of Business of the University
of Mississippi (http://faculty.bus.olemiss.edu/crego).
He received a degree in Computer Science and Applied Mathematics from
the Portucalense University in Portugal. a MSc in Operations Research
and Systems Engineering from the School of Engineering and Technology
(IST) of the University of Lisbon, and a Ph.D. in Computer Science from
the University of Versailles and INRIA - France.
He has held faculty posts in the Portucalense University and the Faculty
of Sciences of the University of Lisbon, and has served as an invited
professor in the IST. He has conducted research in the Operations Research
Center (CIO), the Centre for Urban and Regional Systems (CESUR) of the
University of Lisbon, and in the Hearin Center for Enterprise Science
of the University of Mississippi.
Dr. Rego's publications have appeared in books on metaheuristics and
in leading journals on optimization such as the European Journal of
Operational Research (EJOR), the Journal of the Operational Research
Society (JORS), Parallel Computing, Journal of Applied Mathematics and
Decision Sciences, Computers & OR, Annals of Operations Research,
OR Spectrum, and Management Science. In the practical realm, he has
designed and implemented computer software for solving real-world problems
for several major companies.
During the last four years he has been serving as principal investigator
and co-investigator in six major research grants from the U.S. Navy
Office of Naval Research (ONR) with total funding exceeding 2 million
dollars.
Dr. Rego is Associate Editor of the journal Operational Research: An
International Journal, Hellenic Operational Research Society, the Journal
of Heuristics, Kluwer Academic Publishers, and editor of the book Metaheuristic
Optimization via Memory and Evolution: Tabu Search and Scatter Search,
Kluwer Academic Publishers. He has served on several scientific committees
such as a review panel for the National Science Foundation (NSF) and
examiner of several doctoral dissertations in Europe, USA and Canada.
Dr. Rego has organized and chaired numerous sessions and clusters in
international conferences and has served as invited speaker in a number
plenary sessions. He is the chair of the EU/ME Special Interest Group
on Tabu Search and Scatter Search, in the European Chapter on Metaheuristics
of EURO. He is a member of APDIO and INFORMS, a Research Associate of
the Center for Research on Transportation (CRT) - Montreal, Canada,
and a Senior Research Consultant for OptTek Systems, Inc.
Scope:
Adaptive memory programming (AMP) has been the source of numerous important developments in metaheuristics throughout the last decade. The term refers to the appropriate integration of memory structures to permit search algorithm for optimization problems to explore the solution space effectively.
Because AMP is the foundation of tabu search (TS), which appeared as
the first method specially designed to exploit adaptive memory, the
terms TS and AMP have often been used interchangeably. However, more
recently the principles of AMP have likewise been used to enhance other
approaches as in the creation of hybrid algorithms that incorporate
tabu search components. Many important examples exist of methods that
integrate genetic algorithms and evolutionary computation methods with
adaptive memory, but perhaps the most prominent examples that successfully
use adaptive memory outside of tabu search are the recent developments
in scatter search and its generalization, the path-relinking approach,
whose origins share overlaps with tabu search.
On the other hand, relaxation techniques have been widely used in combinatorial
optimization to provide bounds for tree search procedures (such as branch
and bound) as well as to produce heuristic algorithms. These techniques
are based on solving an auxiliary (or relaxed) problem derived from
the original by dropping or diminishing the restrictiveness of some
constraints. Relaxation Adaptive Memory Programming (RAMP) is a new
metaheuristic that integrates these two key developments by proposing
a unified framework for the design of dual and primal-dual metaheuristics
that take full advantage of adaptive memory programming.
The purpose of this tutorial is to introduce fundamental principles
of mathematical relaxation and adaptive memory programming, as embedded
in state-of-the-art algorithms that are yielding new advances in the
field of metaheuristics. The practical significance of this work is
demonstrated by the ability to solve challenging problems more effectively,
over domains that include facility location, routing and distribution,
production scheduling, resource allocation, manpower planning, data
mining, classification and computational biology, just to cite a few.
Objective:
Illustrate the principles of mathematical relaxation, local search and metaheuristics, and discuss major optimization techniques that make effective use of these concepts with special emphasis to those that rely upon adaptive memory programming..
Duration: 3.00 HR
Program:
1. Fundamentals of Mathematical Relaxation
Linear Programming Relaxation
2. Local Search and Adaptive Memory Programming
3. Advanced Neighborhood Constructions
4. Applications: Illustrative examples
Target Audience:
Background: