Supporting material for the article:
Adaptive "Anytime" Two-Phase Local Search
By Jérémie
Dubois-Lacoste, Manuel López-Ibáñez and Thomas Stützle
January 2010 (last update: January 2010)
Jérémie Dubois-Lacoste, Manuel
López-Ibáñez, and Thomas Stützle. Adaptive “Anytime”
Two-Phase Local Search. In Learning and Intelligent Optimization,
4th International Conference, LION 4, volume 6073 of Lecture Notes in
Computer Science, pages 52–67. Springer, Heidelberg, Germany,
2010.
★ Best paper award
[ Bibtex ] [ doi: 10.1007/978-3-642-13800-3_5 ]
@Inproceedings{DubLopStu10:lion-bfsp,
author = { J{\'e}r{\'e}mie Dubois-Lacoste and Manuel L{\'o}pez-Ib{\'a}{\~n}ez and Thomas St{\"u}tzle },
title = "Adaptive ``Anytime'' Two-Phase Local Search",
pages = {52--67},
doi = {10.1007/978-3-642-13800-3_5},
crossref = "LION2010",
}
@Book{LION2010,
title = "4th International Conference, LION 4, Venice, Italy,
January 18-22, 2010. Selected Papers",
booktitle = "Learning and Intelligent Optimization, 4th
International Conference, LION 4",
year = 2010,
volume = 6073,
series = lncs,
editor = Blum #and# Battiti,
publisher = springer-lncs,
doi = {10.1007/978-3-642-13800-3},
}
1. Abstract:
Two-Phase Local Search (TPLS) is a general algorithmic framework for
multi-objective optimization. TPLS transforms the multi-objective problem into
a sequence of single-objective ones by means of weighted sum aggregations.
This paper studies different sequences of weights for defining the aggregated
problems for the bi-objective case.
In particular, we propose two weight setting strategies that show better
anytime search characteristics than the original weight setting strategy used
in the TPLS algorithm.
Keywords: Metaheuristics, Two-Phase Local Search, Anytime
property, Adaptive strategy, Scheduling, Flow-shop
2. Instances used for experiments
3. Development of the hypervolume over the number of
scalarizations
(i) Regular Anytime versus Classical strategies
These plots show the development of the hypervolume (mean over 15
runs) over the number
of scalarizations, for Regular Anytime (RA-TPLS) against the classical
strategies. |
|
Makespan and Sum of flowtimes
|
50x20_1
|
50x20_2
|
50x20_3
|
50x20_4
|
50x20_5
|
100x20_1
|
100x20_2
|
100x20_3
|
100x20_4
|
100x20_5
|
|
Makespan and Total Tardiness
|
50x20_1
|
50x20_2
|
50x20_3
|
50x20_4
|
50x20_5
|
100x20_1
|
100x20_2
|
100x20_3
|
100x20_4
|
100x20_5
|
(ii) Adaptive Strategies versus Double
| These plots show the development of the hypervolume (mean over 15
runs) over the number of scalarizations, for the Anytime strategies
(RA-TPLS, AN-TPLS and AF-TPLS) against Double (D-TPLS). |
|
Makespan and Sum of flowtimes
|
50x20_1
|
50x20_2
|
50x20_3
|
50x20_4
|
50x20_5
|
100x20_1
|
100x20_2
|
100x20_3
|
100x20_4
|
100x20_5
|
|
Makespan and Total Tardiness
|
50x20_1
|
50x20_2
|
50x20_3
|
50x20_4
|
50x20_5
|
100x20_1
|
100x20_2
|
100x20_3
|
100x20_4
|
100x20_5
|
3. Development of the hypervolume over the number of
scalarizations
(i) Regular Anytime versus Adaptive Anytime
| These plots show the difference of empirical attainment functions
(over 15 runs) for Regular Anytime and Adaptive Anytime. |
|
Makespan and Sum of flowtimes
|
50x20_1
|
50x20_2
|
50x20_3
|
50x20_4
|
50x20_5
|
100x20_1
|
100x20_2
|
100x20_3
|
100x20_4
|
100x20_5
|
|
Makespan and Total Tardiness
|
50x20_1
|
50x20_2
|
50x20_3
|
50x20_4
|
50x20_5
|
100x20_1
|
100x20_2
|
100x20_3
|
100x20_4
|
100x20_5
|
(ii) Adaptive Anytime versus Double
| These plots show the difference of empirical attainment functions
(over 15 runs) for Adaptive Anytime and Double TPLS. |
|
Makespan and Sum of flowtimes
|
50x20_1
|
50x20_2
|
50x20_3
|
50x20_4
|
50x20_5
|
100x20_1
|
100x20_2
|
100x20_3
|
100x20_4
|
100x20_5
|
|
Makespan and Total Tardiness
|
50x20_1
|
50x20_2
|
50x20_3
|
50x20_4
|
50x20_5
|
100x20_1
|
100x20_2
|
100x20_3
|
100x20_4
|
100x20_5
|
