انتخاب استراتژی های تطبیقی ​​در تکامل دیفرانسیلی برای بهینه سازی عددی: یک مطالعه تجربی

Differential evolution (DE) is a versatile and efficient evolutionary algorithm for global numerical optimization, which has been widely used in different application fields. However, different strategies have been proposed for the generation of new solutions, and the selection of which of them should be applied is critical for the DE performance, besides being problem-dependent. In this paper, we present two DE variants with adaptive strategy selection: two different techniques, namely Probability Matching and Adaptive Pursuit, are employed in DE to autonomously select the most suitable strategy while solving the problem, according to their recent impact on the optimization process. For the measurement of this impact, four credit assignment methods are assessed, which update the known performance of each strategy in different ways, based on the relative fitness improvement achieved by its recent applications. The performance of the analyzed approaches is evaluated on 22 benchmark functions. Experimental results confirm that they are able to adaptively choose the most suitable strategy for a specific problem in an efficient way. Compared with other state-of-the-art DE variants, better results are obtained on most of the functions in terms of quality of the final solutions and convergence speed.

Differential evolution (DE), proposed by Storn and Price [35], is an efficient and versatile population-based direct search algorithm that implements the evolutionary generation-and-test paradigm for global optimization, using the distance and direction informations from the current population to guide the search. Among its advantages are its simple structure, ease of use, speed, and robustness, which enables its application on many real-world applications, such as data mining, IIR design, neural network training [29], power systems [43], financial market dynamics modeling [16], data mining [4], and so on. A good survey of DE can be found in [5], where its basic concepts and major variants, as well as some theoretical studies and application examples to complex environments, are reviewed in detail. In the seminal DE algorithm [35], a single mutation strategy was used for the generation of new solutions; later on, Price and Storn suggested nine other different strategies [29] and [36]. In addition, other mutation strategies are also proposed in the DE literature [50], [3], [6] and [8]. Although augmenting the robustness of the underlying algorithm, these many available strategies led the user to the need of defining which of them would be most suitable for the problem at hand – a difficult and crucial task for the performance of DE [31], [30] and [23]. Off-line tuning techniques, such as the F-Race [1], could be used to choose the mutation strategy to be used. However, besides being computationally expensive, such techniques usually output a static setting; while, in practice, the performance of each mutation strategy does not depend on the problem itself, but rather on the characteristics of the region of the search landscape being explored by the population at each generation. Based on this, thus, in order to be more efficient, the autonomous selection of the strategy to be used should be done in a continuous way, while solving the problem, i.e., dynamically adapting itself as the search goes on. In order to contribute on remedying this drawback, in this paper, we extend our recent work [15] on the use of adaptive strategy selection within DE for global numerical optimization. To do adaptive strategy selection, i.e., to be able to automatically select which is the best mutation strategy for the generation of each offspring while solving the problem, two elements need to be defined [48] and [18]: (i) how to select between the available strategies based on their recent performance (strategy selection); and (ii) how to measure the performance of the strategies after their application, and consequently update the empirical quality estimates kept for each of them (credit assignment). In this work, two strategy selection techniques, namely Probability Matching[12] and Adaptive Pursuit[41], are independently analyzed in combination with each of four credit assignment techniques based on the relative fitness improvement. In addition, a parameter sensitivity analysis is conducted to investigate the impact of the hyper-parameters on the performance of the resulting adaptive strategy selection technique. Experiments have been conducted on 22 widely used benchmark problems, including nine test functions presented in CEC-05 [37]. The results indicate that the analyzed approach is able to select the most suitable strategy, while solving a problem at hand. Compared with other state-of-the-art DE variants, better results are obtained on most of the functions in terms of quality of final solutions and convergence speed. Compared with our previous work in [15], the main contributions of this paper are twofold: (i) in order to pursuit the most suitable strategy at different search stages for a specific problem more rapidly, the Adaptive Pursuit technique is used and its performance is compared with the Probability Matching-based DE variant; and (ii) the comprehensive experiments are conducted to verify our approach and its performance is analyzed in detail. The remainder of the paper is organized as follows. Section 2 briefly introduces the background and related work of this paper. In Section 3, we describe the adaptive strategy selection approaches in detail, followed by the experimental results and discussions in Section 4. Finally, Section 5 is devoted to conclusions and future work.

Many mutation strategies have been proposed for generating new solutions within DE in different ways. Although allowing a very wide use of DE on many different fields of application, this number of available strategies creates an extra difficulty to the user: it is not trivial to define which strategy should be used on a given problem in order to achieve good performance. Besides, the strategies are not simply problem-dependent; indeed, their performance tends to vary as the search goes on, according to the characteristics of the region of the search space that is being explored by the current population. Motivated by this difficulty, in this paper we extend our recent work [15] on investigating the use of the adaptive strategy selection approach within DE, i.e., a method capable of automatically selecting which strategy should be applied at each instant of the search, while solving the problem, according to how well each of the available strategies have recently performed in the same search/optimization process, without any prior knowledge. In order to verify the performance of such approach, some different adaptive strategy selection combinations were coupled with JADE [50] and [49], a recently proposed DE variant; the final method being referred to as AdapSS-JADE. Experiments were conducted on 22 widely used benchmark functions. From the results and analysis previously mentioned, we can summarize that: • To implement adaptive strategy selection, credit assignment, i.e., how to assign a reward to a strategy after its application, is an important issue that needs to be addressed. In this work, four credit assignment methods based on the relative fitness improvement were presented and their performance was analyzed. Although there were no significant differences among these four methods on most of the functions, the normalized average reward method was able to obtain the best results in terms of the averaged ranking. The reason might be that the average reward is able to provide the reward for each strategy more exactly than the extreme reward in DE for continuous problems, while the normalization can efficiently eliminate the magnitude differences between the previous estimate qa(t) and the reward ra(t), and also between the very different fitness ranges (consequently rewards) that might be found in the considered problems. • The second and not less important issue in adaptive strategy selection is the strategy selection technique itself, i.e., how to select the next strategy to be applied based on the rewards recently received by each of the available ones. Two strategy selection techniques, the Probability Matching (PM) and the Adaptive Pursuit (AP), were analyzed to address this issue. According to their performance using the normalized average reward of relative fitness improvements as credit assignment, we can conclude that both PM and AP based AdapSS-JADE approaches are able to enhance the performance of DE and obtain better results than the baseline methods. In addition, the AP technique converges more rapidly and accurately to an efficient strategy probability distribution compared with the PM method, which is consistent with the conclusions presented in [41]. • According to the analysis of the strategy adaptation of the best resulting method, referred to as AP-AdapSS-JADE, our approach is capable of efficiently selecting the most suitable strategy while solving the problem, without any prior knowledge, performing consistently better than the JADE using a single strategy, for each of the four available strategies. This latter conclusion confirms the assumption that the competition and cooperation between the available strategies are important to provide a higher achievement. • Besides, AP-AdapSS-JADE obtains highly competitive results when compared to other recent advanced DEs, presenting a better performance on most of the functions, while not considerably augmenting the total computational complexity of the base JADE algorithm. • Based on the analysis on large-scale problems, when the synergy of different strategies in the pool is invalid, AP-AdapSS-JADE only obtains the second best results. It is reasonable because the Adaptive Pursuit technique needs some generations to pursuit the most suitable strategy for a specific problem. • Finally, the parameter analysis done shows that the AP-AdapSS-JADE approach is not sensitive to the setting of its three hyper-parameters, the minimal probability pmin, the adaptation rate α, and the learning rate β; several different parameter settings were able to achieve similar good performance. For further work, when tackling multimodal problems, the maintenance of a minimal level of diversity is also important for the search process, and thus should also be taken into account for the rewarding of the strategies; the Compass or the Pareto-based approaches, proposed in [22], could be analyzed for this purpose in the future. Additionally, using other strategy selection techniques, such as the approaches based on Multi-Armed Bandits [10], could also be an interesting direction for the strategy adaptation within DE. In addition, experimental results indicate that synergy of strategies is very important for multiple-strategy DE. Thus, another direction of future work is performing comprehensively empirical study to investigate how to select strategy to form the pool. Furthermore, in the future, we will try to improve the performance of our approach on large-scale problems [46], [39], [17] and [38].