موازی سازی جمعیت مبتنی بر متا هیوریستیک چند هدفه : یک مطالعه تجربی
|کد مقاله||سال انتشار||مقاله انگلیسی||ترجمه فارسی||تعداد کلمات|
|8045||2006||15 صفحه PDF||سفارش دهید||6460 کلمه|
Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)
Journal : Applied Mathematical Modelling, Volume 30, Issue 7, July 2006, Pages 578–592
In single-objective optimization it is possible to find a global optimum, while in the multi-objective case no optimal solution is clearly defined, but several that simultaneously optimize all the objectives. However, the majority of this kind of problems cannot be solved exactly as they have very large and highly complex search spaces. Recently, meta-heuristic approaches have become important tools for solving multi-objective problems encountered in industry as well as in the theoretical field. Most of these meta-heuristics use a population of solutions, and hence the runtime increases when the population size grows. An interesting way to overcome this problem is to apply parallel processing. This paper analyzes the performance of several parallel paradigms in the context of population-based multi-objective meta-heuristics. In particular, we evaluate four alternative parallelizations of the Pareto simulated annealing algorithm, in terms of quality of the solutions, and speedup.
Solving real optimization problems requires efficient algorithms. When the complexity of the problem to solve is high, such as with NP-complete problems , it is often useful to employ heuristic methods. Heuristics often allow us to tackle large-size problems instances by delivering satisfactory solutions in a reasonable runtime. Meta-heuristics are general-purpose heuristics that split into a number of categories including evolutionary algorithms (EA) and local-search methods (LS). While EAs allow a better exploration of the search space, LS strategies have the power to intensify the search in a particular region. However both, EA and LS, have in common that the quality of the solutions depends on parametric settings, like population size, number of iterations, etc. In many cases, the use of a single-processor computer implies very large runtimes, which can be unacceptable for some real applications. One way to overcome this weakness is the use of parallel processing. Most real optimization problems entail simultaneous optimization of distinct and conflicting objectives. In recent years, the number of strategies proposed to solve complex multi-objective optimization problems has increased considerably. Population-based strategies are very frequently used in multi-objective meta-heuristics (MOMHs) , , , ,  and . In addition, the complexity of some of these methods ,  and  is even higher because they use a secondary population, which saves the promising solutions found in the search. These, and other parameters, such as the number of objectives to optimize, complicate even more the design of meta-heuristics in comparison with the single-objective case. In this context, the use of parallel and distributed strategies become a powerful tool to obtain good solutions in acceptable runtimes. Thus far, most of the parallel implementations in multi-objective optimization are related to EA-based MOMHs, while LS-based MOMHs have been studied to a lesser extent. This paper analyzes the behavior of four parallel paradigms in Pareto simulated annealing, a well known population-based MOMH. The remainder of the paper is organized as follows. Section 2 describes the multi-objective optimization concept, and reviews the main simulated annealing-based MOMHs proposed to date. Section 3 gives an overview of parallel and distributed strategies, and details how to extend them to the analysis of population-based MOMHs. Section 4 presents the results of the parallel models proposed in Section 3, in a multi-objective formulation of the graph-partitioning problem. Finally, Section 5 provides the conclusions of this empirical analysis.
نتیجه گیری انگلیسی
This paper analyzes the benefits of using parallel strategies to improve the Pareto simulated annealing algorithm. In concrete, we have implemented four parallelizations: multi-start, master–worker, island, and island with search space division. The multi-start paradigm consists of executing in parallel several local searches, without any information exchange. In the master–worker model, the master processor centralizes the population and manages the selection and the replacement steps, while the worker processors perform recombination and evaluation tasks. The island-based models divide the entire population into several sub-populations distributed among different processors. Each processor is responsible for the evolution of one sub-population, and occasionally individuals migrate among islands. The real problem we have used as basis of this analysis is a multi-objective formulation of the graph-partitioning problem. In terms of quality of the solutions, results denote that the multi-start model is not adequate in simulated annealing-based multi-objective meta-heuristics, due to the application of several independent runs for fewer iterations impacts negatively in the annealing schedule. The master–worker model maintains the sequentiality of Pareto simulated annealing, but obtains worse solutions than the island paradigm. On the other hand, we can remark that the island model that uses search space division obtains the best results in terms of domination and space covered. In terms of execution time, the island-based implementations obtain an important speedup gain. On average, the master–worker has the worst behavior, mainly when population size increases. Last but not least, solutions obtained for this problem are very close to those obtained by single-objective methods and can even improve on them. We hope that these conclusions can offer very useful guidelines for the parallelization of other population-based multi-objective meta-heuristics.