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)

Table of Contents
  1. Abstract
  2. Instances
  3. Development of the hypervolume over the number of scalarizations
    1. Regular Anytime versus Classical strategies
    2. Adaptive Strategies versus Double
  4. Empirical Attainment Functions
    1. Regular Anytime versus Adaptive Anytime
    2. Adaptive Anytime versus Double



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 ]

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

experiments_instances.tar.gz






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_MSFT.png
50x20_1
50x20_2_MSFT.png
50x20_2
50x20_3_MSFT.png
50x20_3
50x20_4_MSFT.png
50x20_4
50x20_5_MSFT.png
50x20_5
100x20_1_MSFT.png
100x20_1
100x20_2_MSFT.png
100x20_2
100x20_3_MSFT.png
100x20_3
100x20_4_MSFT.png
100x20_4
100x20_5_MSFT.png
100x20_5
Makespan and Total Tardiness
50x20_1_MTT.png
50x20_1
50x20_2_MTT.png
50x20_2
50x20_3_MTT.png
50x20_3
50x20_4_MTT.png
50x20_4
50x20_5_MTT.png
50x20_5
100x20_1_MTT.png
100x20_1
100x20_2_MTT.png
100x20_2
100x20_3_MTT.png
100x20_3
100x20_4_MTT.png
100x20_4
100x20_5_MTT.png
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_MSFT.png
50x20_1
50x20_2_MSFT.png
50x20_2
50x20_3_MSFT.png
50x20_3
50x20_4_MSFT.png
50x20_4
50x20_5_MSFT.png
50x20_5
100x20_1_MSFT.png
100x20_1
100x20_2_MSFT.png
100x20_2
100x20_3_MSFT.png
100x20_3
100x20_4_MSFT.png
100x20_4
100x20_5_MSFT.png
100x20_5
Makespan and Total Tardiness
50x20_1_MTT.png
50x20_1
50x20_2_MTT.png
50x20_2
50x20_3_MTT.png
50x20_3
50x20_4_MTT.png
50x20_4
50x20_5_MTT.png
50x20_5
100x20_1_MTT.png
100x20_1
100x20_2_MTT.png
100x20_2
100x20_1_MTT.png
100x20_3
100x20_4_MTT.png
100x20_4
100x20_5_MTT.png
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_MSFT_RA-TPLS_AF-TPLS.png
50x20_1
50x20_2_MSFT_RA-TPLS_AF-TPLS.png
50x20_2
50x20_3_MSFT_RA-TPLS_AF-TPLS.png
50x20_3
50x20_4_MSFT_RA-TPLS_AF-TPLS.png
50x20_4
50x20_5_MSFT_RA-TPLS_AF-TPLS.png
50x20_5
100x20_1_MSFT_RA-TPLS_AF-TPLS.png
100x20_1
100x20_2_MSFT_RA-TPLS_AF-TPLS.png
100x20_2
100x20_3_MSFT_RA-TPLS_AF-TPLS.png
100x20_3
100x20_4_MSFT_RA-TPLS_AF-TPLS.png
100x20_4
100x20_5_MSFT_RA-TPLS_AF-TPLS.png
100x20_5
Makespan and Total Tardiness
50x20_1_MTT_RA-TPLS_AF-TPLS.png
50x20_1
50x20_2_MTT_RA-TPLS_AF-TPLS.png
50x20_2
50x20_3_MTT_RA-TPLS_AF-TPLS.png
50x20_3
50x20_4_MTT_RA-TPLS_AF-TPLS.png
50x20_4
50x20_5_MTT_RA-TPLS_AF-TPLS.png
50x20_5
100x20_1_MTT_RA-TPLS_AF-TPLS.png
100x20_1
100x20_2_MTT_RA-TPLS_AF-TPLS.png
100x20_2
100x20_3_MTT_RA-TPLS_AF-TPLS.png
100x20_3
100x20_4_MTT_RA-TPLS_AF-TPLS.png
100x20_4
100x20_5_MTT_RA-TPLS_AF-TPLS.png
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_MSFT_AF-TPLS_D-TPLS.png
50x20_1
50x20_2_MSFT_AF-TPLS_D-TPLS.png
50x20_2
50x20_3_MSFT_AF-TPLS_D-TPLS.png
50x20_3
50x20_4_MSFT_AF-TPLS_D-TPLS.png
50x20_4
50x20_5_MSFT_AF-TPLS_D-TPLS.png
50x20_5
100x20_1_MSFT_AF-TPLS_D-TPLS.png
100x20_1
100x20_2_MSFT_AF-TPLS_D-TPLS.png
100x20_2
100x20_3_MSFT_AF-TPLS_D-TPLS.png
100x20_3
100x20_4_MSFT_AF-TPLS_D-TPLS.png
100x20_4
100x20_5_MSFT_AF-TPLS_D-TPLS.png
100x20_5
Makespan and Total Tardiness
50x20_1_MTT_AF-TPLS_D-TPLS.png
50x20_1
50x20_2_MTT_AF-TPLS_D-TPLS.png
50x20_2
50x20_3_MTT_AF-TPLS_D-TPLS.png
50x20_3
50x20_4_MTT_AF-TPLS_D-TPLS.png
50x20_4
50x20_5_MTT_AF-TPLS_D-TPLS.png
50x20_5
100x20_1_MTT_AF-TPLS_D-TPLS.png
100x20_1
100x20_2_MTT_AF-TPLS_D-TPLS.png
100x20_2
100x20_3_MTT_AF-TPLS_D-TPLS.png
100x20_3
100x20_4_MTT_AF-TPLS_D-TPLS.png
100x20_4
100x20_5_MTT_AF-TPLS_D-TPLS.png
100x20_5

Valid HTML 4.01 Transitional Valid CSS!