تکامل متفاوت در بهینه سازی عددی محدود: یک مطالعه تجربی
|کد مقاله||سال انتشار||مقاله انگلیسی||ترجمه فارسی||تعداد کلمات|
|10442||2010||40 صفحه PDF||سفارش دهید||20325 کلمه|
Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)
Journal : Information Sciences, Volume 180, Issue 22, 15 November 2010, Pages 4223–4262
Motivated by the recent success of diverse approaches based on differential evolution (DE) to solve constrained numerical optimization problems, in this paper, the performance of this novel evolutionary algorithm is evaluated. Three experiments are designed to study the behavior of different DE variants on a set of benchmark problems by using different performance measures proposed in the specialized literature. The first experiment analyzes the behavior of four DE variants in 24 test functions considering dimensionality and the type of constraints of the problem. The second experiment presents a more in-depth analysis on two DE variants by varying two parameters (the scale factor F and the population size NP), which control the convergence of the algorithm. From the results obtained, a simple but competitive combination of two DE variants is proposed and compared against state-of-the-art DE-based algorithms for constrained optimization in the third experiment. The study in this paper shows (1) important information about the behavior of DE in constrained search spaces and (2) the role of this knowledge in the correct combination of variants, based on their capabilities, to generate simple but competitive approaches.
Nowadays, the use of evolutionary algorithms  (EAs) to solve optimization problems is a common practice due to their competitive performance on complex search spaces . On the other hand, optimization problems usually include constraints in their models and EAs, in their original versions, do not consider a mechanism to incorporate feasibility information in the search process. Therefore, several constraint-handling mechanisms have been proposed in the specialized literature  and . The most popular approach to deal with the constraints of an optimization problem is the use of (mainly exterior) penalty functions , where the aim is to decrease the fitness of infeasible solutions in order to favor the selection of feasible solutions. Despite its simplicity, a penalty function requires the definition of penalty factors to determine the severity of the penalization, and these values depend on the problem being solved . Based on this important disadvantage, several alternative constraint-handling techniques have been proposed . In the recent years, the research on constraint-handling for numerical optimization problems has been focused mainly in the following aspects: 1. Multiobjective optimization concepts: A comprehensive survey of constraint-handling techniques based on Pareto ranking, Pareto dominance, and other multiobjective concepts has been recently published . These ideas have been recently coupled with steady-state EAs , selection criteria based on the feasibility of solutions found in the current population  and , real-world problems , pre-selection schemes  and , other meta-heuristics , and with swarm intelligence approaches . 2. Highly competitive penalty functions: In order to tackle the fine-tuning required by traditional penalty functions, some works have been dedicated to balance the influence of the value of the objective function and the sum of constraint violation by using rankings  and . Other proposals have been focused on adaptive ,  and  and co-evolutionary  penalty approaches, as well as alternative penalty functions such as those based on special functions  and . 3. Novel bio-inspired approaches: Other nature-inspired algorithms have been used to solve numerical constrained problems, such as artificial immune systems (AIS) , particle swarm optimization (PSO)  and , and differential evolution (DE) , , , , , , , , ,  and . 4. Combination of global and local search: Different approaches couple the use of an EA, as a global search algorithm with different local search algorithms. There are combinations such as agent-memetic-based , co-evolution-memetic-based , and also crossover-memetic-based  algorithms. Other approaches combine mathematical-programming based local search operators ,  and . 5. Hybrid approaches: Unlike the combination of global and local search, these approaches look to combine the advantages of different EAs, such as PSO and DE  or AIS and genetic algorithms (GAs) . 6. Special operators: Besides designing operators to preserve the feasibility of solutions , there are proposals dedicated to explore either the boundaries of the feasible and infeasible regions  and  or convenient regions close to the parents in the crossover process  and . 7. Self-adaptive mechanisms: There are studies regarding the parameter control in constrained search spaces, such as a proposal to control the parameters of the algorithm (DE in this case) . There is another approach where a self-adaptive parameter control was proposed for the DE parameters and also for the parameters introduced by the constraint-handling mechanism . The selection of the most adequate DE variant was also controlled by an adaptive approach in . Finally, fuzzy-logic has been also applied to control the DE parameters . 8. Theoretical studies: Still scarce, there are interesting studies on runtime in constrained search spaces with EAs  and also in the usefulness of infeasible solutions in the search process . Based on this overview of the recent research related with constrained numerical optimization problems (CNOPs), some observations are summarized: • The research efforts have been mainly focused on generating competitive constraint-handling techniques (1 and 2 in the previous list). • The combination of different search algorithms has become very popular (4 and 5 in the list). • Topics related to special operators and parameter control are important to design more robust algorithms to solve CNOPs (6 and 7 in the aforementioned list). • Besides traditional EAs such as GAs, Evolution Strategies (ES), and Evolutionary Programming (EP), novel nature-inspired algorithms such as PSO, AIS, and DE have been explored (3 in the list) • DE has specially attracted the interest from researchers due to its excellent performance in constrained continuous search spaces (last set of references in 3 in the list). Despite the highly competitive performance showed by DE when solving CNOPs, the research efforts, as it will be pointed out by a careful review of the state-of-the-art later in the paper, have been focused on providing modifications to DE variants instead of analyzing the behavior of the algorithm itself. This current work is precisely focused on providing empirical evidence about the behavior of DE original variants (without additional mechanisms or modifications) in constrained numerical search spaces. Furthermore, this knowledge is used to propose a simple combination of DE variants in a competitive approach to solve CNOPs. Different experiments are designed to test DE original variants by using, in all cases, an effective but parameter-free constraint-handling technique. Four performance measures found in the specialized literature are used to analyze the behavior of four DE variants. These measures are related with the capacity to reach the feasible region, the closeness to the feasible global optimum (or best known solution), and the computational cost. Twenty-four well-known test problems  recently used to compare state-of-the-art nature-inspired techniques to solve CNOPs are used in the experiments. Nonparametric statistical tests are used to provide more statistical support to the obtained results. It is known from the No Free Lunch Theorems for search  that using such a limited set of functions does not guarantee, in any way, that a variant which performs well on them, will necessarily be competitive in a different set of problems. However, the main objective of this work is to provide some insights about the behavior of DE variants depending of the features of the problem. Besides, another goal is to analyze the effect of two DE parameter values related with its convergence (the scale factor and the population size) on different types of constrained numerical search spaces. The last goal of this work is the use of the knowledge obtained in a simple approach which combines the strengths of two DE variants into a single approach which does not use complex additional mechanisms. The paper is organized as follows: In Section 2 the problem of interest is stated. Section 3 introduces the DE algorithm, while in Section 4 a review of the state-of-the-art on DE to solve CNOPs is included. Section 5 presents the analysis proposed in this work. After that, in Section 6 the first experiment on four DE variants in 24 test problems is explained and the obtained results are discussed. An analysis of two DE parameters on two competitive (but with different behaviors) DE variants is presented in Section 7. Section 8 comprises the combination of two DE variants into a single approach and its performance is compared with respect to some DE-based state-of-the-art approaches. Finally, in Section 9, the findings of the current work are summarized and the future paths of research are shown.
نتیجه گیری انگلیسی
The findings of this second experiment are summarized in the following list: • DE/rand/1/bin was clearly most competitive in the high-dimensionality test problem. • DE/rand/1/bin was the variant with less sensitivity to NP and F in all the six test problems. • DE/best/1/bin required less evaluations to reach the global feasible optimum in all the test problems, but it was less reliable than DE/rand/1/bin. • The most useful F values for both variants were 0.6 ⩽ F ⩽ 0.9, regardless the type of test problem. • DE/rand/1/bin/ performed better with small to medium size populations: 30 ⩽ NP ⩽ 90, while DE/best/1/bin required more vectors in its population to provide competitive results 90 ⩽ NP ⩽ 150. • Regarding the convergence behavior reported in unconstrained numerical optimization with DE, a different comportment was observed in the constrained case, because low scale factor values (F ⩽ 0.5) prevented both DE variants to converge, even with larger populations. The exception was the test problem with a low-dimensionality. Additional experiments were performed in test problems with similar features as those presented in the paper: g19 for high-dimensionality, g09 for medium-dimensionality, g08 for low-dimensionality, g07 with only inequality constraints, g17 with only equality constraints, and g05 with both type of constraints. Those results can be found in  and they confirmed the findings mentioned above. The summary of findings suggests that the ability of DE/rand/1/bin to generate search directions from different base vectors allows it to use smaller populations. On the other hand, larger populations were required by DE/best/1/bin, where the search directions are always based on the best solution so far. Regarding the scale factor, the convenient values found in the experiment showed that these two DE variants required a slow-convergence behavior to approach the vicinity of the feasible global optimum or best known solution. To speed up the convergence by decreasing the scale factor value does not seem to be an option, even with larger populations. The combination of larger populations and DE/rand/1/bin seems to be more suitable for high-dimensionality problems. Finally, DE/rand/1/bin presented less sensitivity to the two parameters analyzed. Meanwhile, DE/best/1/bin, which may require a more careful fine-tuning, can provide competitive results with a lower number of evaluations. Based on this last comment, the drawback found in DE/best/1/bin may be treated with parameter control techniques .