Surrogate-Assisted Memetic Algorithm with Adaptive Patience Criterion for Computationally Expensive Optimization

Surrogate-assisted memetic algorithm (SAMA) has been recognized to be an effective tool for computationally expensive optimization. The termination criterion of the local search in SAMA determines the allocation of limited computational resources between global and local search, and has a tremendous impact on the optimization performance. The commonly used termination criterion based on setting a limit to the local search depth can lead to premature termination or excessive stagnation iterations of the local search. This paper proposes a SAMA with adaptive patience criterion (SAMA/APC) to improve the efficiency of traditional SAMA. The SAMA/APC consists of three main subprocedures, which are carried out iteratively. First, the operators of differential evolution (DE) are employed for global exploration. Then, the proposed Kriging-based patience allocation strategy (KPAS) is performed, which adaptively allocates a patience value to each individual of the population according to two basic principles. Third, the trust-region search (TRS) is carried out on each individual for local exploitation. The TRS is a process of consuming the patience, and it terminates when the patience value is reduced to zero. The local optimum obtained by the TRS is returned back to the population of DE in the spirit of Lamarckian learning. Experimental studies on the CEC' 14 expensive optimization test suite demonstrate the efficiency of the proposed SAMA/APC.