Explicit Exploitation and Exploration Control in Evolutionary Optimization

演化計算中勘探與探索能力的顯式控制研究

Student thesis: Doctoral Thesis

View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Awarding Institution
Supervisors/Advisors
Award date7 Aug 2020

Abstract

Exploitation and exploration (EE) are two cornerstones of evolutionary optimization algorithms (EOAs), such as differential evolution (DE), evolution strategy (ES) and particle swarm optimization (PSO). Achieving a good balance between them have always been an important yet challenging issue. This thesis proposes three innovative explicit exploitation and exploration capabilities (EEC) control methods, which not only bring significant performance enhancements, but also provide deeper insight into how EEC affect the performance of EAs on different optimization problems.

The first method, named selective-candidate framework with similarity selection rule (SCSS), facilitates explicit EEC control at individual level. In SCSS, M (M > 1) candidates are first generated from each current solution with independent operations and parameters. Then, an EEC control approach, named similarity selection rule is designed to determine the final candidate. By considering the fitness ranking of the current solution and its Euclidian distance to each of these M candidates, superior current solutions prefer the closest candidates for efficient local exploitation while inferior ones favor the farthest for exploration purpose. In this way, the rule could synthesize exploitation and exploration, making the evolution more effective. When applied to various up-to-date EOAs from the branches of DE, ES and PSO, significant performance enhancement is achieved.

The second method, named multi-layer competitive-cooperative (MLCC) framework, facilitates explicit EEC control at group level. DE is recognized as one of the most powerful EOAs. Many DE variants were proposed in recent years, but significant differences in performances between them are hardly observed. Moreover, there is a lack of a flexible method that could easily incorporate complex variants. Therefore, MLCC framework is suggested to facilitate the competition and cooperation among multiple DEs, enhancing exploration and exploitation respectively. MLCC implements a parallel structure with the entire population simultaneously monitored by multiple DEs assigned to their corresponding layers. An individual can store, utilize and update its evolution information in different layers based on an individual preference-based layer selecting (IPLS) mechanism and a computational resource allocation bias (RAB) mechanism. The competitive IPLS and cooperative RAB mechanisms are respectively designed for superior and inferior groups to achieve the explicit EEC control at group level. Experimental studies verify the effectiveness of the mechanisms and show that the MLCC variants significantly outperform the baseline DEs.

The third method, named explicit adaptation (Ea) scheme controls EEC at population level. Strategy adaptation is efficient for EEC control. Existing methods commonly involve the trials of multiple strategies and then reward better-performing one based on their previous performance. However, the trials of an exploitative or explorative strategy may result in over-exploitation or over-exploration. To improve the performance, Ea scheme exempts strategy adaptation from traditional trial-and-error by separating multiple strategies and employing them on-demand. Specifically, it divides the evolution process into several SCSS generations and adaptive generations. In the SCSS generations, the exploitation and exploration needs are learnt by utilizing a balanced strategy. To meet these needs, in adaptive generations, two other strategies, exploitative or explorative is adaptively used. Experimental studies on benchmark functions demonstrate the advantage of the proposed method when compared with its variants and other adaptation methods. Furthermore, EaDE’s competitiveness is demonstrated by performance comparisons with state-of-the-art EOAs.