1 Université Libre de Bruxelles Institut de Recherches Interdisciplinaires et de Développements en Intelligence Artificielle Pareto Loca...

Author:
Rosamond Burke

0 downloads 55 Views 1MB Size

No documents

´ pez-Iba ´n ˜ ez and J´er´emie Dubois-Lacoste, Manuel Lo ¨ tzle Thomas Stu

IRIDIA – Technical Report Series Technical Report No. TR/IRIDIA/2011-024 December 2011

IRIDIA – Technical Report Series ISSN 1781-3794 Published by: IRIDIA, Institut de Recherches Interdisciplinaires et de D´eveloppements en Intelligence Artificielle

´ Libre de Bruxelles Universite Av F. D. Roosevelt 50, CP 194/6 1050 Bruxelles, Belgium Technical report number TR/IRIDIA/2011-024

The information provided is the sole responsibility of the authors and does not necessarily reflect the opinion of the members of IRIDIA. The authors take full responsibility for any copyright breaches that may result from publication of this paper in the IRIDIA – Technical Report Series. IRIDIA is not responsible for any use that might be made of data appearing in this publication.

Pareto Local Search Algorithms for Anytime Bi-Objective Optimization J´er´emie Dubois-Lacoste

[email protected]

´ pez-Iba ´n ˜ ez Manuel Lo

[email protected]

¨ tzle Thomas Stu

[email protected]

IRIDIA, Universit´e Libre de Bruxelles, Brussels, Belgium

December 2011 Abstract Pareto local search (PLS) is an extension of iterative improvement methods for multi-objective combinatorial optimization problems and an important part of several state-of-the-art multi-objective optimizers. PLS stops when all neighbors of the solutions in its solution archive are dominated. If terminated before completion, it may produce a poor approximation to the Pareto front. This paper proposes variants of PLS that improve its anytime behavior, that is, they aim to maximize the quality of the Pareto front at each time step. Experimental results on the bi-objective traveling salesman problem show a large improvement of the proposed anytime PLS algorithm over the classical one.

1

Introduction

Multi-objective optimization deals with problems for which solutions are evaluated according to multiple criteria. These multiple criteria are often in conflict and, hence, different solutions can show different possible trade-offs between the objectives that must be optimized. If there is no a priori knowledge about the preferences of the decision maker, multi-objective problems are usually tackled by determining the set of all Pareto optimal solutions from which the decision maker can select, a posteriori, one solution or extract some conclusions. Pareto local search (PLS) is an extension of iterative improvement algorithms for single-objective problems to the multi-objective case [14]. PLS produces high-quality results when used as a stand-alone algorithm [14], and even better results when used as a component of hybrid algorithms, where PLS starts from a good set of initial solutions. In fact, PLS is a crucial component of the best algorithms known for the multi-objective traveling salesman problem [13]

1

IRIDIA – Technical Report Series: TR/IRIDIA/2011-024

2

with two and three objectives, various bi-objective permutation flowshop problems [4], and the bi-objective multi-dimensional knapsack problem [12]. Even when starting from a good approximation to the Pareto front, PLS can require a long time to terminate based on its natural stopping criterion [14, 4]. Hence, many applications define an additional termination criterion, either in terms of a maximum number of solutions to be explored or computation time. In many real-life situations, however, the available computation time may be unknown, and it is therefore desirable to obtain the best possible output whenever the algorithm is stopped. Unfortunately, PLS was originally designed without taking into account its anytime behavior [17]. Although there is a large amount of work on anytime algorithms for single-objective optimization problems [17, 10], there is little research on anytime multi-objective optimization algorithms [5]. In this paper, we study alternatives to the algorithmic components of the classical PLS with the goal of improving its anytime behavior. In particular, we propose variants that switch strategies during the run of the algorithm. We consider the bi-objective traveling salesman problem (bTSP) as a case study. The traveling salesman problem (TSP) is a well-known N P-hard combinatorial problem widely used to assess the performance of optimization algorithms and meta-heuristics. In its bi-objective variant, two cost values are assigned to each edge of a graph, and each of the two objective functions is computed with respect to the corresponding cost value. The bTSP is a prominent benchmark problem in the study of multi-objective optimization algorithms [6, 16, 5].

2 2.1

Anytime Pareto local search Pareto local search

PLS is an iterative improvement method for solving multi-objective combinatorial optimization problems. The acceptance criterion in PLS is based on Pareto dominance. Given two vectors ~u, ~v ∈ R2 , we say that ~u dominates ~v (~u ≺ ~v ) iff ~u 6= ~v and ui ≤ vi , i = 1, 2, assuming without loss of generality that both objectives must be minimized. Algorithm 1 illustrates the PLS framework. Given an initial set of mutually nondominated solutions called the archive, which are initially marked as unexplored (line 2), PLS iteratively applies the following steps. First, a solution s is randomly chosen among all unexplored ones (selection step, line 5). Then, the neighborhood of s, N (s), is fully explored and all neighbors that are nondominated w.r.t. s and any solution in the archive A are added to A (lines 6 to 11). Solutions in A dominated by the newly added solutions are removed (procedure Update in line 9). Once the neighborhood of s has been fully explored, s is marked as explored (line 10). When all solutions have been explored, and thus, no more nondominated solutions can be discovered, the algorithm stops with a final set of solutions that are a Pareto local optimum [15]. The three main algorithmic components of PLS are (i) the selection step,

IRIDIA – Technical Report Series: TR/IRIDIA/2011-024

3

Algorithm 1 Pareto Local Search 1: Input: An initial set of nondominated solutions A0 2: explored(s) := false ∀s ∈ A0 3: A := A0 4: repeat 5: s := select randomly a solution from A0 // Selection step 6: for each s0 ∈ N (s) do // Neighborhood exploration 7: if s ⊀ s0 then // Acceptance criterion 8: explored(s0 ) := false 9: A := Update(A, s0 ) 10: explored(s) := true 11: A0 := {s ∈ A | explored(s) = false} 12: until A0 = ∅ 13: Output: A

(ii) the neighborhood exploration, and (iii) the acceptance criterion. In the next section, we present the original choices and the variants for these components that we implemented and tested.

2.2

PLS algorithmic components for anytime optimization

Selection step. In many combinatorial optimization problems, solutions that are close to each other in the solution space are also close in the objective space. Transferring this fact to multi-objective problems, we may expect to fill existing “gaps” around the image of a solution in the Pareto front by exploring the neighborhood of it. In the original PLS, the next solution to be explored is selected randomly among the ones not explored, without taking into account possibly existing “gaps”. Instead, PLS could select to explore the solution whose neighborhood has the largest potential of improving the quality of the current Pareto front approximation. A measure of the quality of a single solution is given by its hypervolume contribution. The hypervolume measures the volume of the objective space weakly dominated by a set of solutions [19]. The larger the hypervolume, the better the quality of the set. The hypervolume contribution of a single solution measures how much a solution contributes to the total hypervolume of a set. However, in the selection step of PLS we are not concerned about the hypervolume contribution of the solutions in the current archive, but on the potential hypervolume contribution of solutions that are generated by exploring the neighborhood of solutions in the archive. Since the actual hypervolume contribution that can be generated by neighborhood exploration is unknown, we “optimistically” estimate it. Given two solutions s and s0 (in the biobjective case), we define the optimistic hypervolume contribution (ohvc) as the hypervolume contribution of

IRIDIA – Technical Report Series: TR/IRIDIA/2011-024

4

Figure 1: Representation of the normalized objective space. The optimistic hypervolume improvement (OHVI) of a solution s is the sum of the two areas between s and the closest neighbors in the objective space, sinf and ssup . the local ideal point defined by s and s0 in the objective space: ohvc(s, s0 ) = (f1 (s) − f1 (s0 )) · (f2 (s0 ) − f2 (s)),

(1)

where f1 (·) and f2 (·) are the normalized objective values for the first and second objective, respectively. We expect to find new nondominated solutions in the region between the current solution and its closest neighbors in the objective space, and, thus, we define the optimistic hypervolume improvement (OHVI) of a solution s as if @sinf , 2 · ohvc(s, ssup ) (2) OHVI(s) = 2 · ohvc(sinf , s) if @ssup , ohvc(s, ssup ) + ohvc(sinf , s) otherwise, where ssup and sinf are the closest neighbors of s in the objective space from the current archive A0 defined as ssup = arg min{f2 (si ) | f2 (si ) > f2 (s)} si ∈A0

sinf = arg max{f2 (si ) | f2 (si ) < f2 (s)}.

(3)

si ∈A0

Either ssup or sinf may not exist if s is the best solutions for f2 () or f1 (), respectively. In such a case, we define the OHVI to be two times the existing ohvc, in order to avoid a strong bias against extreme solutions. Figure 1 graphically illustrates the computation of the OHVI of a solution. When using OHVI for selection, the unexplored solution with the maximum OHVI value is chosen. It is, however, important to note that the above definition of OHVI makes some implicit assumptions. First, it assumes that by exploring the neighborhood of a solution new solutions are obtained only between the selected solution and the closest solutions in the objective space. This may not be necessarily the case and if the correlation between the distance of solutions in the solution space and the distance in the objective space is small, OHVI may not work better than random selection. Second, the above definition does not consider the area that dominates the current solution, and, hence, it assumes that no solutions are found that dominate the current solution. Again, this is not necessarily true, but given a good enough initial set, it is more common to find nondominated solutions than dominating ones. Although the proposed OHVI selection is specifically designed for PLS, the concept of ohvc was previously proposed for improving the anytime behavior of

IRIDIA – Technical Report Series: TR/IRIDIA/2011-024

5

Two-Phase Local Search [5]. Moreover, the ohvc is related, but different to the hypervolume contribution used in some multi-objective evolutionary algorithms (MOEAs) [1, 8], where the hypervolume contribution of each solution with respect to the current archive is used to select or discard solutions. By contrast, ohvc estimates the potential contribution of solutions that could be found by the algorithm in the next iteration. The proposed OHVI selection is related to diversity measures used in other MOEAs, such as crowding distance [3] and the distance to the k-nearest neighbor [18], since it favors the exploration of the less crowded regions of the objective space. Acceptance Criterion. The original PLS accepts any new nondominated solution into its archive. This nondominating acceptance criterion favors exploration but it also leads to a fast archive growth, which in turn slows down the algorithm and makes it more difficult to select the best solutions for further exploration. By contrast, a dominating acceptance criterion, that is, accepting only neighbors that dominate the currently explored solution, may allow PLS to reach faster the optimal Pareto front. There are two reasons for this. First, the size of the archive stays more limited; second, the search becomes more focused on moving the current archive closer to the optimal Pareto front. The downside of a dominating acceptance criterion is that exploration is limited: by accepting only dominating solutions, nondominated solutions that may fill gaps between other solutions are not accepted and possible paths to other dominating or nondominated solutions are cut. To avoid poor quality solutions caused by early termination of PLS using the dominating acceptance criterion, we propose to change between the two acceptance criteria in the following manner. Initially, the dominating acceptance criterion is used as described above, that is, only neighbors dominating the current solution are accepted. If no dominating neighbor is found, the neighborhood of the current solution is explored again, this time accepting nondominated solutions. In this way, a switch from the dominating to the nondominated acceptance criterion happens on an adaptive, per-solution basis. Neighborhood exploration. The neighborhood exploration component decides when to stop exploring the neighborhood of the current solution. In the original PLS, the neighborhood of a solution is always fully explored. Alternatively, the exploration of the neighborhood may be stopped as soon as an “improved” solution is found, where the meaning of improved is defined by the acceptance criterion (see above) as being either a dominating or a nondominated solution. Different levels of neighborhood exploration may be defined by allowing a partial exploration of the neighborhood going beyond finding a first acceptable solution. Here, however, we focus on the two extreme cases of either having a full exploration or a first-accepted exploration. Independent of whether a full or first-accepted exploration rule is applied, in PLS a solution becomes marked as explored, as soon as the neighborhood exploration is stopped. When using first-accepted exploration, one may find improving solutions by completing the neighborhood exploration of solutions in the archive, even if they

IRIDIA – Technical Report Series: TR/IRIDIA/2011-024

6

are marked as explored. To account for this possibility, we propose the following combination of the two rules: When all solutions in the current archive have been explored using the first-acceptance rule, the whole archive is marked again as unexplored and the algorithm switches to full neighborhood exploration. Related work. To the best of our knowledge, there has been no study of the anytime behavior of PLS subject to some algorithmic variations. Liefooghe et al. [9] study the effect on the quality of restricting the overall exploration by limiting the number of solutions to be selected for exploration, and by limiting the neighborhood exploration itself. Nonetheless, there are significant differences with our proposals here. First, they do not make a distinction between acceptance criterion and neighborhood exploration. In particular, they do not examine the combination of the dominating acceptance criterion and full exploration. Second, when using the dominating acceptance criterion and the first-accepted neighborhood exploration, they propose to also add all nondominated solutions found during exploration to the current archive. Our dominating acceptance criterion is more aggressive, since we only add solutions dominating the current one, which keeps a smaller archive size and focuses the search on getting closer to the optimal Pareto front. Third, they do not consider any of the variants proposed here that switch strategies during a single run of PLS, e.g., from dominating to nondominated acceptance criterion and from first-accepted to full neighborhood exploration.

3 3.1

Experimental Analysis Experimental setup and performance assessment

We test the proposed PLS variants on the bTSP. We generate 10 bTSP instances of size 200, 300, and 500. The two distance matrices of each instance are generated independently of each other and correspond to symmetric, Euclidean TSP instances [5]. Due to the stochasticity of the algorithms, we repeat each experiment 10 times using a different random seed and a different initial set. The algorithms are implemented in C++, compiled with gcc 4.4, and the experiments were run on a single core of Intel Xeon E5410 CPUs, running at 2.33 Ghz with 6 MB of cache size under Cluster Rocks Linux version 4.2.1/CentOS 4. We use the hypervolume unary indicator as a measure of the quality of the Pareto front approximations. As the upper bounds used for normalization of the objective values, we sample 10 000 random solutions, and we record the worst objective value produced from this sampling. Note that we also check that the upper bounds are never attained in any result we obtained. The lower bounds are the optimal solutions for each distance matrix obtained from the exact Concorde solver, release 03.12.19. In order to study the anytime behavior of the algorithms, we store the approximation of the Pareto front at 100 steps during the run of each algorithm, where each step is the CPU time in seconds at the following points in time: ti = exp(i · ln(1001)/100) − 1, i ∈ 1, . . . , 100. We examine the anytime behav-

IRIDIA – Technical Report Series: TR/IRIDIA/2011-024

7

ior of each variant by plotting the hypervolume of its archive at each time step as follows. First, we normalize all the objectives values to the range [1, 2], using the bounds as described above. Next, we compute the hypervolume of each Pareto front approximation using the reference point [2.1, 2.1]. Finally, for each strategy, each instance and each time step, we plot the hypervolume averaged over the 10 independent runs of each variant and the 95% confidence intervals around the mean as a gray area. PLS starts from a given set of solutions, and this set has a large impact on PLS’ final results. We consider three common alternatives for this initial set: 1. A single random solution, which corresponds to using PLS as a stand-alone algorithm. 2. Two solutions, each of them of high quality for one single objective. This corresponds to a scenario where high-performing single-objective algorithms are available for each objective. Here, each solution is generated by running an iterated local search (ILS) algorithm using a 3-opt neighborhood for 2 seconds [7]. 3. A nondominated set of high-quality solutions. This setting corresponds to a scenario where we have an algorithm for generating a high-quality approximation to the Pareto front and we want to further improve this approximation by applying PLS [4]. Here, we generate such an initial set of 5 high-quality solutions by running the anytime two-phase local search (TPLS) algorithm [5]. Each weighted sum aggregation of the objective functions is tackled by the ILS algorithm during 2 seconds.

3.2

Experimental results

First, we graphically explore the impact of one component at a time. Later, we compare the best combinations on larger instances. For reasons of space, we only provide results on one instance for each comparison; other instances show very similar behavior, and their plots are available as supplementary material. As a last step, we carry out a statistical analysis over all instances. Selection step. We call the variant of PLS using a random selection PLShRNDi, and the variant using the OHVI for selection PLShOHVIi. We compare in Fig. 2 these two variants. When starting from a random solution (left) the two variants show a very similar evolution; no curve clearly dominates the other. When the initial set is either two (middle) or a set of high-quality solutions (right), the curve corresponding to PLShOHVIi is most of the time above the one corresponding to PLShRNDi, which shows that PLShOHVIi generates a significantly better approximation set during most of the running time. Therefore, we choose OHVI as the selection step in the remainder of the paper. Acceptance Criterion. We call the nondominated acceptance criterion PLSh⊀i, the dominating one PLShi, and the combination of both PLSh⊀i. All variants use OHVI as the selection step. We compare these three variants in Fig. 3.

IRIDIA – Technical Report Series: TR/IRIDIA/2011-024

8

When the initial set is a random solution (left), PLShi improves the quality of the archive in a very short time, after which it stops because the whole archive has been explored. On the other hand, PLSh⊀i improves its archive at a slower rate, but does not stop prematurely and yields much better final results. Interestingly, the combination of the two strategies for the acceptance criterion used by PLSh⊀i outperforms both individual strategies clearly: it combines the fast initial improvement of PLShi with the much better final performance of PLSh⊀i. When starting from two (middle) or a set of high-quality solutions (right), the behavior of PLShi is particularly bad: it is not able to improve the initial set at all, which results in the flat line at the bottom of the plots. On the other hand, PLSh⊀i is able to significantly improve the initial solutions. The fact that the anytime behavior of PLSh⊀i is better than the one of PLSh⊀i shows that the adaptive switching of the acceptance criteria on a per solution basis in PLSh⊀i is highly beneficial. Neighborhood exploration. In the following, PLSh∗i denotes the full neighborhood exploration in PLS, PLSh1i denotes the first-accepted neighborhood exploration; and PLSh1∗i denotes the PLS variant that switches from the firstaccepted to the full neighborhood exploration. All variants use OHVI selection and nondominating acceptance criterion. Fig. 4 shows that the anytime behavior of these three variants is very consistent, independently of the kind of initial set. PLSh1i improves very quickly the quality of the current archive in the first ten seconds, but then it terminates. PLSh∗i, on the other hand, requires more than ten seconds to reach the same quality as PLSh1i, but then improves further until the computation time limit. Finally, PLSh1∗i initially matches exactly the behavior of PLSh1i (being actually the same algorithm) but then continues to progress due to the switch in the rule of the neighborhood exploration. Therefore, we conclude that PLSh1∗i has a much better anytime behavior than each individual strategy for exploring the neighborhood. Interactions between PLS components. We now compare PLS variants that differ in more than one component in order to show interactions between components. In particular, PLShRND, ⊀, ∗i denotes the classical PLS using random selection, nondominated acceptance criterion and full neighborhood exploration; PLShOHVI, ⊀, ∗i denotes the best variant obtained above when analyzing the acceptance criterion; PLShOHVI, ⊀, 1∗i denotes the best variant obtained above when analyzing the neighborhood exploration rule; and PLShOHVI, ⊀ , 1∗i denotes the variant that combines the PLSh⊀i and PLSh1∗i strategies. These four PLS variants are compared in Fig. 5. First, the results obtained by PLShOHVI, ⊀, ∗i and PLShOHVI, ⊀, 1∗i confirm the results presented earlier, that is, the newly proposed algorithms improve the anytime behavior of PLS w.r.t. to the classical PLShRND, ⊀, ∗i. However, there is a somewhat surprising interaction between the components of PLShOHVI, ⊀, 1∗i, since its anytime behavior is worse than the one of PLShOHVI, ⊀, 1∗i in general, and also worse than PLShOHVI, ⊀, ∗i in the case of a high-quality initial set (right plot). Further work would be necessary to completely understand this behavior. We also compare these four variants on larger bTSP instances, 10 instances

1.1 1

10 Seconds

100

0.7

RND,⊀,* OHVI,⊀,*

1000

0.1

1

10 Seconds

100

1000

1.02

0.1

Hypervolume 1.06 1.10

Hypervolume 0.8 0.9 1.0

Hypervolume 0.2 0.4 0.6 0.8 1.0

RND,⊀,* OHVI,⊀,*

9

1.14

IRIDIA – Technical Report Series: TR/IRIDIA/2011-024

RND,⊀,* OHVI,⊀,* 0.1

1

10 Seconds

100

1000

1

10 Seconds

100

1000

0.1

1

10 Seconds

100

1000

Hypervolume 1.04 1.08 1.12

OHVI,≻,* OHVI,⊀,* OHVI,≻⊀,*

1.00

0.1

Hypervolume 0.8 1.0

OHVI,≻,* OHVI,⊀,* OHVI,≻⊀,*

0.6

Hypervolume 0.2 0.4 0.6 0.8 1.0

Figure 2: PLShRNDi vs PLShOHVIi, starting from a random seed (left), 2 solutions (middle), and a set of solutions (right), respectively. Note the different ranges on the y-axis.

OHVI,≻,* OHVI,⊀,* OHVI,≻⊀,* 0.1

1

10 Seconds

100

1000

1

10 Seconds

100

1000

0.1

1

10 Seconds

100

1000

Hypervolume 1.06 1.10

OHVI,⊀,* OHVI,⊀,1 OHVI,⊀,1*

1.02

0.1

Hypervolume 0.8 0.9 1.0

OHVI,⊀,* OHVI,⊀,1 OHVI,⊀,1*

0.7

Hypervolume 0.2 0.4 0.6 0.8 1.0

1.1

1.14

Figure 3: PLShOHVI, i vs PLShOHVI, ⊀i vs PLShOHVI, ⊀i, starting from a random seed (left), 2 solutions (middle), and a set of solutions (right), respectively. Note the different ranges on the y-axis.

OHVI,⊀,* OHVI,⊀,1 OHVI,⊀,1* 0.1

1

10 Seconds

100

1000

Figure 4: PLSh∗i vs PLSh1i vs PLSh1∗i, starting from a random seed (left), 2 solutions (middle), and a set of solutions (right). Note the different ranges on the y-axis.

IRIDIA – Technical Report Series: TR/IRIDIA/2011-024

10

of sizes 300 and 500, respectively. For these larger instances, we use candidate lists obtained by Pareto-ranking of the edges to speed-up the neighborhood exploration while keeping a similar quality [11]. We tested candidate lists of size 25, 50 and 100, but they resulted in similar performance, and, hence, we only present results with size 50. The results provided by Fig. 6 do not allow us to declare an overall winner variant. When the initial solution is random (left plots), PLShOHVI, ⊀, 1∗i progresses much faster than other variants, but it is eventually outperformed by other variants. When the initial set are two or a set of high-quality solutions, PLShOHVI, ⊀, 1∗i obtains the best hypervolume in the earlier and final stages, however, there is a range of time where other variants, in particular PLShOHVI, ⊀, ∗i, perform better. Nonetheless, the plots show clearly that the proposed PLS variants consistently outperform the classical PLShRND, ⊀, ∗i. Statistical Tests. We perform statistical tests to assess the behavior over the whole set of 10 instances of each size. We apply the Friedman test for analyzing non-parametric unreplicated complete block designs. Each block is a run using a particular seed (out of ten) on a single instance, and the different PLS variants are the treatment factor. Next, we rank the PLS variants per block according to the hypervolume, the lower the rank the better, and we calculate the difference (∆R) between the sum of ranks of each variant and the best ranked one (with the lowest sum of ranks). Finally, we calculate the minimum difference between the sum of ranks of two variants that is statistically significant (∆Rα ), given a significance level of α = 0.05, using the Friedman post-test for multiple comparisons [2]. We perform this test on the output of the algorithms at various time steps, for each instance size and each type of initial set, as shown in Table 1, where each row summarizes the result of one independent test. We indicate in bold face the best variant (the one having the lowest sum of ranks) and those that are not significantly different from the best one. The tests confirm our previous conclusions that PLShOHVI, ⊀, 1∗i is the best strategy overall for size 200. It is also often the best for sizes 300 and 500, but not always. Moreover, it shows that the classical PLShRND, ⊀, ∗i performs quite poorly when compared with the anytime PLS variants proposed here, being in some cases completely outranked (with a sum of ranks close to 300) by the other variants.

4

Conclusions

In this paper, we proposed alternative choices for algorithmic components of PLS that improve substantially its anytime behavior. In addition, we have proposed novel approaches that are based on switching strategies for the neighborhood exploration and the acceptance criterion; these switching strategies have proven to be essential for reaching the best possible anytime behavior. As a result, replacing the original PLS with one of our proposed variants in hybrid algorithms is likely to further improve the current state of the art in multi-objective optimization. However, none of the variants is clearly superior to all others, and further research is needed to understand in more detail the

10 Seconds

100

1000

0.1

1

10 Seconds

100

1000

Hypervolume 1.06 1.10 1.02

1

Hypervolume 0.8 0.9 1.0

1.1 0.1

RND,⊀,* OHVI,⊀,1* OHVI,≻⊀,* OHVI,≻⊀,1*

0.7

Hypervolume 0.2 0.4 0.6 0.8 1.0

RND,⊀,* OHVI,⊀,1* OHVI,≻⊀,* OHVI,≻⊀,1*

11

1.14

IRIDIA – Technical Report Series: TR/IRIDIA/2011-024

RND,⊀,* OHVI,⊀,1* OHVI,≻⊀,* OHVI,≻⊀,1* 0.1

1

10 Seconds

100

1000

0.0

RND,⊀,* OHVI,⊀,1* OHVI,≻⊀,* OHVI,≻⊀,1* 0.1

1

10 Seconds

100

1000

0.1

1

10 Seconds

100

1000

RND,⊀,* OHVI,⊀,1* OHVI,≻⊀,* OHVI,≻⊀,1*

Hypervolume 1.04 1.08 1.12

Hypervolume 0.8 1.0

1000

1.00

100

RND,⊀,* OHVI,⊀,1* OHVI,≻⊀,* OHVI,≻⊀,1* 0.1

1

10 Seconds

100

1000

RND,⊀,* OHVI,⊀,1* OHVI,≻⊀,* OHVI,≻⊀,1*

Hypervolume 1.00 1.05 1.10

10 Seconds

Hypervolume 0.6 0.8 1.0

1

Hypervolume 0.4 0.8

0.1

RND,⊀,* OHVI,⊀,1* OHVI,≻⊀,* OHVI,≻⊀,1*

0.6

RND,⊀,* OHVI,⊀,1* OHVI,≻⊀,* OHVI,≻⊀,1*

0.4

Hypervolume 0.2 0.4 0.6 0.8 1.0

Figure 5: PLShRND, ⊀, ∗i vs PLShOHVI, ⊀, 1∗i vs PLShOHVI, ⊀, ∗i and PLShOHVI, ⊀, 1∗i, starting from a random seed (left), 2 solutions (middle), a set of solutions (right).

0.1

1

10 Seconds

100

1000

0.1

1

10 Seconds

100

1000

Figure 6: PLShRND, ⊀, ∗i vs PLShOHVI, ⊀, 1∗i vs PLShOHVI, ⊀, ∗i and PLShOHVI, ⊀, 1∗i, starting from a random seed (left), 2 solutions (middle), a set of solutions (right), and for two instance sizes: 300 (top) and 500 cities (bottom).

IRIDIA – Technical Report Series: TR/IRIDIA/2011-024

12

Table 1: Statistical analysis of the best variants of PLS at different time steps. We chose 10.2 and 101.4 as they are the closest time steps from 10 and 100 seconds, respectively. For each time, PLS variants are ordered according to the sum of ranks obtained across all instances. The numbers in parenthesis are the differences of the sum of ranks relative to the best variant. PLS variants that are statistically significantly better than the best one are indicated in bold face. ∆Rα gives the difference of the sum of ranks that is significant. Time

∆Rα

Strategies (∆R)

1.0 10.2 101.4 1000.0

12.1 13.2 13.5 19.5

Instance size 200, initial set: random solution. hOHVI,⊀,1*i, hOHVI,⊀,*i (34), hOHVI,⊀,1*i (161), hRND,⊀,*i (265) hOHVI,⊀,1*i, hOHVI,⊀,*i (116), hRND,⊀,*i (192), hOHVI,⊀,1*i (284) hOHVI,⊀,1*i, hOHVI,⊀,*i (145), hOHVI,⊀,1*i (158), hRND,⊀,*i (293) hOHVI,⊀,1*i, hOHVI,⊀,1*i (81.5), hOHVI,⊀,*i (97), hRND,⊀,*i (259.5)

1.0 10.2 101.4 1000.0

3.9 11.6 10.6 13.1

Instance size 200, initial set: two high-quality solutions. hOHVI,⊀,1*i, hOHVI,⊀,1*i (103), hOHVI,⊀,*i (197), hRND,⊀,*i (300) hOHVI,⊀,1*i, hOHVI,⊀,1*i (139), hOHVI,⊀,*i (158), hRND,⊀,*i (299) hOHVI,⊀,1*i, hOHVI,⊀,1*i (131), hOHVI,⊀,*i (169), hRND,⊀,*i (300) hOHVI,⊀,1*i, hOHVI,⊀,1*i (115.5), hOHVI,⊀,*i (157.5), hRND,⊀,*i (291)

1.0 10.2 101.4 1000.0

17.2 10.7 15.1 16.1

Instance size 200, initial set: high-quality set. hOHVI,⊀,1*i, hOHVI,⊀,*i (117), hOHVI,⊀,1*i (138), hRND,⊀,*i (277) hOHVI,⊀,1*i, hOHVI,⊀,*i (76), hOHVI,⊀,1*i (194), hRND,⊀,*i (278) hOHVI,⊀,1*i, hOHVI,⊀,*i (130), hOHVI,⊀,1*i (191), hRND,⊀,*i (279) hOHVI,⊀,1*i, hOHVI,⊀,1*i (111.5), hOHVI,⊀,*i (125.5), hRND,⊀,*i (279)

1.0 10.2 101.4 1000.0

7.1 14.2 16.9 12.7

Instance size 300, initial set: random solution. hOHVI,⊀,*i, hOHVI,⊀,1*i (78), hOHVI,⊀,1*i (189), hRND,⊀,*i (289) hOHVI,⊀,1*i, hOHVI,⊀,*i (84), hRND,⊀,*i (171), hOHVI,⊀,1*i (277) hOHVI,⊀,1*i, hOHVI,⊀,*i (122), hOHVI,⊀,1*i (220), hRND,⊀,*i (254) hOHVI,⊀,1*i, hOHVI,⊀,1*i (142), hOHVI,⊀,*i (146), hRND,⊀,*i (296)

1.0 10.2 101.4 1000.0

12.4 11.5 3.2 10.4

Instance size 300, initial set: two high-quality solutions. hOHVI,⊀,1*i, hOHVI,⊀,1*i (102), hOHVI,⊀,*i (169), hRND,⊀,*i (289) hOHVI,⊀,*i, hOHVI,⊀,1*i (137), hOHVI,⊀,1*i (160), hRND,⊀,*i (299) hOHVI,⊀,1*i, hOHVI,⊀,*i (102), hOHVI,⊀,1*i (198), hRND,⊀,*i (300) hOHVI,⊀,1*i, hOHVI,⊀,1*i (129.5), hOHVI,⊀,*i (170.5), hRND,⊀,*i (300)

1.0 10.2 101.4 1000.0

22.3 13.4 9.9 10.9

Instance size 300, initial set: high-quality set. hOHVI,⊀,*i, hOHVI,⊀,1*i (35), hOHVI,⊀,1*i (37), hRND,⊀,*i (224) hOHVI,⊀,*i, hOHVI,⊀,1*i (101), hOHVI,⊀,1*i (175), hRND,⊀,*i (284) hOHVI,⊀,1*i, hOHVI,⊀,*i (100), hRND,⊀,*i (225), hOHVI,⊀,1*i (275) hOHVI,⊀,1*i, hOHVI,⊀,*i (135.5), hOHVI,⊀,1*i (164.5), hRND,⊀,*i (300)

1.0 10.2 101.4 1000.0

0 12 6.4 16

Instance size 500, initial set: random solution. hOHVI,⊀,1*i, hOHVI,⊀,1*i (100), hOHVI,⊀,*i (200), hRND,⊀,*i (300) hOHVI,⊀,*i, hOHVI,⊀,1*i (106), hOHVI,⊀,1*i (193), hRND,⊀,*i (285) hOHVI,⊀,1*i, hOHVI,⊀,*i (103), hRND,⊀,*i (196), hOHVI,⊀,1*i (297) hOHVI,⊀,1*i, hOHVI,⊀,*i (120), hOHVI,⊀,1*i (223), hRND,⊀,*i (257)

1.0 10.2 101.4 1000.0

9.1 22.4 13.8 0

Instance size 500, initial set: two high-quality solutions. hOHVI,⊀,1*i, hOHVI,⊀,1*i (71), hOHVI,⊀,*i (186), hRND,⊀,*i (283) hOHVI,⊀,1*i, hOHVI,⊀,*i (18), hOHVI,⊀,1*i (46), hRND,⊀,*i (220) hOHVI,⊀,*i, hOHVI,⊀,1*i (101), hOHVI,⊀,1*i (157), hRND,⊀,*i (286) hOHVI,⊀,1*i, hOHVI,⊀,*i (100), hOHVI,⊀,1*i (200), hRND,⊀,*i (300)

1.0 10.2 101.4 1000.0

14.5 19.4 11.7 8.4

Instance size 500, initial set: high-quality set. hOHVI,⊀,1*i, hOHVI,⊀,1*i (65), hOHVI,⊀,*i (154), hRND,⊀,*i (273) hOHVI,⊀,*i, hOHVI,⊀,1*i (63), hOHVI,⊀,1*i (105), hRND,⊀,*i (256) hOHVI,⊀,*i, hOHVI,⊀,1*i (59), hOHVI,⊀,1*i (169), hRND,⊀,*i (276) hOHVI,⊀,1*i, hOHVI,⊀,*i (100), hOHVI,⊀,1*i (216), hRND,⊀,*i (284)

IRIDIA – Technical Report Series: TR/IRIDIA/2011-024

13

behavior of the proposed variants. Finally, we want to test the proposed PLS variants on different problems such as MKP [12] and permutation flowshop [4].

References [1] Beume, N., Naujoks, B., Emmerich, M.: SMS-EMOA: Multiobjective selection based on dominated hypervolume. European Journal of Operational Research 181(3), 1653–1669 (2007) [2] Conover, W.J.: Practical Nonparametric Statistics. John Wiley & Sons, New York, NY, third edn. (1999) [3] Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6(2), 181–197 (2002) [4] Dubois-Lacoste, J., L´ opez-Ib´an ˜ez, M., St¨ utzle, T.: A hybrid TP+PLS algorithm for bi-objective flow-shop scheduling problems. Computers & Operations Research 38(8), 1219–1236 (2011) [5] Dubois-Lacoste, J., L´ opez-Ib´an ˜ez, M., St¨ utzle, T.: Improving the anytime behavior of two-phase local search. Annals of Mathematics and Artificial Intelligence 61(2), 125–154 (2011) [6] Ehrgott, M., Gandibleux, X.: Approximative solution methods for combinatorial multicriteria optimization. TOP 12(1), 1–88 (2004) [7] Hoos, H.H., St¨ utzle, T.: Stochastic Local Search—Foundations and Applications. Morgan Kaufmann Publishers, San Francisco, CA (2005) [8] Knowles, J.D., Corne, D.: Properties of an adaptive archiving algorithm for storing nondominated vectors. IEEE Trans. Evol. Comput. 7(2), 100–116 (April 2003) [9] Liefooghe, A., Mesmoudi, S., Humeau, J., Jourdan, L., Talbi, E.G.: On dominance-based multiobjective local search: design, implementation and experimental analysis on scheduling and traveling salesman problems. Journal of Heuristics (2011) [10] Loudni, S., Boizumault, P.: Combining VNS with constraint programming for solving anytime optimization problems. European Journal of Operational Research 191, 705–735 (2008) [11] Lust, T., Jaszkiewicz, A.: Speed-up techniques for solving large-scale biobjective TSP. Computers & Operations Research 37(3), 521–533 (2010) [12] Lust, T., Teghem, J.: The multiobjective multidimensional knapsack problem: a survey and a new approach. Arxiv preprint arXiv:1007.4063 (2010)

IRIDIA – Technical Report Series: TR/IRIDIA/2011-024

14

[13] Lust, T., Teghem, J.: Two-phase Pareto local search for the biobjective traveling salesman problem. Journal of Heuristics 16(3), 475–510 (2010) [14] Paquete, L., Chiarandini, M., St¨ utzle, T.: Pareto local optimum sets in the biobjective traveling salesman problem: An experimental study. In: Gandibleux, X., et al. (eds.) Metaheuristics for Multiobjective Optimisation, LNEMS, vol. 535, pp. 177–200. Springer (2004) [15] Paquete, L., Schiavinotto, T., St¨ utzle, T.: On local optima in multiobjective combinatorial optimization problems. Annals of Operations Research 156, 83–98 (2007) [16] Paquete, L., St¨ utzle, T.: Design and analysis of stochastic local search for the multiobjective traveling salesman problem. Computers & Operations Research 36(9), 2619–2631 (2009) [17] Zilberstein, S.: Using anytime algorithms in intelligent systems. AI Magazine 17(3), 73–83 (1996) [18] Zitzler, E., Laumanns, M., Thiele, L.: SPEA2: Improving the strength Pareto evolutionary algorithm for multiobjective optimization. In: Giannakoglou, K., et al. (eds.) Evolutionary Methods for Design, Optimisation and Control. pp. 95–100. CIMNE, Barcelona, Spain (2002) [19] Zitzler, E., Thiele, L.: Multiobjective optimization using evolutionary algorithms - A comparative case study. In: Eiben, A.E., et al. (eds.) PPSN V. LNCS, vol. 1498, pp. 292–301. Springer, Heidelberg, Germany (1998)

AZDOC.SITE | To ensure the functioning of the site, we use **cookies**. We share information about your activities on the site with our partners and Google partners: social networks and companies engaged in advertising and web analytics. For more information, see the Privacy Policy and Google Privacy & Terms. Your consent to our cookies if you continue to use this website. Accept