A memetic algorithm with adaptive hill climbing strategy for dynamic optimization problems

Dynamic optimization problems challenge traditional evolutionary algorithms seriously since they, once converged, cannot adapt quickly to environmental changes. This paper investigates the application of memetic algorithms, a class of hybrid evolutionary algorithms, for dynamic optimization problems. An adaptive hill climbing method is proposed as the local search technique in the framework of memetic algorithms, which combines the features of greedy crossover-based hill climbing and steepest mutation-based hill climbing. In order to address the convergence problem, two diversity maintaining methods, called adaptive dual mapping and triggered random immigrants, respectively, are also introduced into the proposed memetic algorithm for dynamic optimization problems. Based on a series of dynamic problems generated from several stationary benchmark problems, experiments are carried out to investigate the performance of the proposed memetic algorithm in comparison with some peer evolutionary algorithms. The experimental results show the efficiency of the proposed memetic algorithm in dynamic environments.     

A memetic particle swarm optimisation algorithm for dynamic multi-modal optimisation problems

Many real-world optimisation problems are both dynamic and multi-modal, which require an optimisation algorithm not only to find as many optima under a specific environment as possible, but also to track their moving trajectory over dynamic environments. To address this requirement, this article investigates a memetic computing approach based on particle swarm optimisation for dynamic multi-modal optimisation problems (DMMOPs). Within the framework of the proposed algorithm, a new speciation method is employed to locate and track multiple peaks and an adaptive local search method is also hybridised to accelerate the exploitation of species generated by the speciation method. In addition, a memory-based re-initialisation scheme is introduced into the proposed algorithm in order to further enhance its performance in dynamic multi-modal environments. Based on the moving peaks benchmark problems, experiments are carried out to investigate the performance of the proposed algorithm in comparison with several state-of-the-art algorithms taken from the literature. The experimental results show the efficiency of the proposed algorithm for DMMOPs.     

$$\beta$$ -Hill climbing: an exploratory local search

Hill climbing method is an optimization technique that is able to build a search trajectory in the search space until reaching the local optima. It only accepts the uphill movement which leads it to easily get stuck in local optima. Several extensions to hill climbing have been proposed to overcome such problem such as Simulated Annealing, Tabu Search. In this paper, an extension version of hill climbing method has been proposed and called \(\beta\)-hill climbing. A stochastic operator called \(\beta\)-operator is utilized in hill climbing to control the balance between the exploration and exploitation during the search. The proposed method has been evaluated using IEEE-CEC2005 global optimization functions. The results show that the proposed method is a very efficient enhancement to the hill climbing providing powerful results when it compares with other advanced methods using the same global optimization functions.

     

动态环境中的Memetic算法

针对近几年在进化计算领域被广泛关注的动态优化问题,提出了一种基于粒子群优化(PSO)的Memetic算法.在一种环状拓扑结构的局部PSO模型中,利用模糊认知局域搜索策略来改善部分粒子的质量,同时引入一种自组织随机移民策略来保持算法的种群多样性.通过对一组标准动态测试问题的仿真实验,能够证明所提出的算法在动态环境中的有效性和适应能力.     

A particle swarm optimization based memetic algorithm for dynamic optimization problems

Recently, there has been an increasing concern from the evolutionary computation community on dynamic optimization problems since many real-world optimization problems are dynamic. This paper investigates a particle swarm optimization (PSO) based memetic algorithm that hybridizes PSO with a local search technique for dynamic optimization problems. Within the framework of the proposed algorithm, a local version of PSO with a ring-shape topology structure is used as the global search operator and a fuzzy cognition local search method is proposed as the local search technique. In addition, a self-organized random immigrants scheme is extended into our proposed algorithm in order to further enhance its exploration capacity for new peaks in the search space. Experimental study over the moving peaks benchmark problem shows that the proposed PSO-based memetic algorithm is robust and adaptable in dynamic environments.     

A comparative study of local search within a surrogate-assisted multi-objective memetic algorithm framework for expensive problems

A comparative study of the impacts of various local search methodologies for the surrogate-assisted multi-objective memetic algorithm (MOMA) is presented in this paper. The base algorithm for the comparative study is the single surrogate-assisted MOMA (SS-MOMA) with the main aim being to solve expensive problems with a limited computational budget. In addition to the standard weighted sum (WS) method used in the original SS-MOMA, we studied the capabilities of other local search methods based on the achievement scalarizing function (ASF), Chebyshev function, and random mutation hill climber (RMHC) in various test problems. Several practical aspects, such as normalization and constraint handling, were also studied and implemented to deal with real-world problems. Results from the test problems showed that, in general, the SS-MOMA with ASF and Chebyshev functions was able to find higher-quality solutions that were more robust than those found with WS or RMHC; although on problems with more complicated Pareto sets SS-MOMA-WS appeared as the best. SS-MOMA-ASF in conjunction with the Chebyshev function was then tested on an airfoil-optimization problem and compared with SS-MOMA-WS and the non-dominated sorting based genetic algorithm-II (NSGA-II). The results from the airfoil problem clearly showed that SS-MOMA with an achievement-type function could find more diverse solutions than SS-MOMA-WS and NSGA-II. This suggested that for real-world applications, higher-quality solutions are more likely to be found when the surrogate-based memetic optimizer is equipped with ASF or a Chebyshev function than with other local search methods.     

A hybrid variable neighborhood search for solving the hybrid flow shop scheduling problem

This paper proposes a hybrid variable neighborhood search (HVNS) algorithm that combines the chemical-reaction optimization (CRO) and the estimation of distribution (EDA), for solving the hybrid flow shop (HFS) scheduling problems. The objective is to minimize the maximum completion time. In the proposed algorithm, a well-designed decoding mechanism is presented to schedule jobs with more flexibility. Meanwhile, considering the problem structure, eight neighborhood structures are developed. A kinetic energy sensitive neighborhood change approach is proposed to extract global information and avoid being stuck at the local optima. In addition, contrary to the fixed neighborhood set in traditional VNS, a dynamic neighborhood set update mechanism is utilized to exploit the potential search space. Finally, for the population of local optima solutions, an effective EDA-based global search approach is investigated to direct the search process to promising regions. The proposed algorithm is tested on sets of well-known benchmark instances. Through the analysis of experimental results, the high performance of the proposed HVNS algorithm is shown in comparison with four efficient algorithms from the literature.     

Improving fuzzy cognitive maps learning through memetic particle swarm optimization

Fuzzy cognitive maps constitute a neuro-fuzzy modeling methodology that can simulate complex systems accurately. Although their configuration is defined by experts, learning schemes based on evolutionary and swarm intelligence algorithms have been employed for improving their efficiency and effectiveness. This paper comprises an extensive study of the recently proposed swarm intelligence memetic algorithm that combines particle swarm optimization with both deterministic and stochastic local search schemes, for fuzzy cognitive maps learning tasks. Also, a new technique for the adaptation of the memetic schemes, with respect to the available number of function evaluations per application of the local search, is proposed. The memetic learning schemes are applied on four real-life problems and compared with established learning methods based on the standard particle swarm optimization, differential evolution, and genetic algorithms, justifying their superiority.     

A hybrid shuffled complex evolution approach with pattern search for unconstrained optimization

The difficulties associated with using classical mathematical programming methods on complex optimization problems have contributed to the development of alternative and efficient numerical approaches. Recently, to overcome the limitations of classical optimization methods, researchers have proposed a wide variety of meta-heuristics for searching near-optimum solutions to problems. Among the existing meta-heuristic algorithms, a relatively new optimization paradigm is the Shuffled Complex Evolution at the University of Arizona (SCE-UA) which is a global optimization strategy that combines concepts of the competition evolution theory, downhill simplex procedure of Nelder-Mead, controlled random search and complex shuffling. In an attempt to reduce processing time and improve the quality of solutions, particularly to avoid being trapped in local optima, in this paper is proposed a hybrid SCE-UA approach. The proposed hybrid algorithm is the combination of SCE-UA (without Nelder-Mead downhill simplex procedure) and a pattern search approach, called SCE-PS, for unconstrained optimization. Pattern search methods are derivative-free, meaning that they do not use explicit or approximate derivatives. Moreover, pattern search algorithms are direct search methods well suitable for the global optimization of highly nonlinear, multiparameter, and multimodal objective functions. The proposed SCE-PS method is tested with six benchmark optimization problems. Simulation results show that the proposed SCE-PS improves the searching performance when compared with the classical SCE-UA and a genetic algorithm with floating-point representation for all the tested problems. As evidenced by the performance indices based on the mean performance of objective function in 30 runs and mean of computational time, the SCE-PS algorithm has demonstrated to be effective and efficient at locating best-practice optimal solutions for unconstrained optimization.     

带时间窗车辆路径问题的文化基因算法

针对物流配送中带时间窗的车辆路径问题（Vehicle Routing Problem with Time Windows,VRPTW）,建立了数学模型,并设计了求解VRPTW的文化基因算法。种群搜索采用遗传算法的进化模式,局部搜索采用禁忌搜索机制,并结合可行邻域结构避免对不可行解的搜索,以提高搜索效率。与单纯的遗传算法和禁忌搜索算法进行对比实验,表明该算法是求解VRPTW的一种有效方法。     

一种求解动态优化问题的免疫文化基因算法

针对传统免疫网络动态优化算法局部寻优能力弱、寻优精度低及易早熟收敛的缺点,提出一种求解动态优化问题的免疫文化基因算法。基于文化基因算法基本框架,将人工免疫网络算法作为全局搜索算法,采用禁忌搜索算法作为局部搜索算子;同时引入柯西变异加强算法的全局搜索能力,并有效防止早熟收敛。通过对经典动态优化函数测试集在相同条件下的实验表明,该免疫文化基因算法相较于其他同类算法具有较好的搜索精度和收敛速度。     

A hybrid particle swarm optimization algorithm for high-dimensional problems

In recent years, particle swarm optimization (PSO) emerges as a new optimization scheme that has attracted substantial research interest due to its simplicity and efficiency. However, when applied to high-dimensional problems, PSO suffers from premature convergence problem which results in a low optimization precision or even failure. To remedy this fault, this paper proposes a novel memetic PSO (CGPSO) algorithm which combines the canonical PSO with a Chaotic and Gaussian local search procedure. In the initial evolution phase, CGPSO explores a wide search space that helps avoid premature convergence through Chaotic local search. Then in the following run phase, CGPSO refines the solutions through Gaussian optimization. To evaluate the effectiveness and efficiency of the CGPSO algorithm, thirteen high dimensional non-linear scalable benchmark functions were examined. Results show that, compared to the standard PSO, CGPSO is more effective, faster to converge, and less sensitive to the function dimensions. The CGPSO was also compared with two PSO variants, CPSO-H, DMS-L-PSO, and two memetic optimizers, DEachSPX and MA-S2. CGPSO is able to generate a better, or at least comparable, performance in terms of optimization accuracy. So it can be safely concluded that the proposed CGPSO is an efficient optimization scheme for solving high-dimensional problems.     

Balancing exploration and exploitation in memetic algorithms: A learning automata approach

One of the problems with traditional genetic algorithms (GAs) is premature convergence, which makes them incapable of finding good solutions to the problem. The memetic algorithm (MA) is an extension of the GA. It uses a local search method to either accelerate the discovery of good solutions, for which evolution alone would take too long to discover, or reach solutions that would otherwise be unreachable by evolution or a local search method alone. In this paper, we introduce a new algorithm based on learning automata (LAs) and an MA, and we refer to it as LA‐MA. This algorithm is composed of 2 parts: a genetic section and a memetic section. Evolution is performed in the genetic section, and local search is performed in the memetic section. The basic idea of LA‐MA is to use LAs during the process of searching for solutions in order to create a balance between exploration performed by evolution and exploitation performed by local search. For this purpose, we present a criterion for the estimation of success of the local search at each generation. This criterion is used to calculate the probability of applying the local search to each chromosome. We show that in practice, the proposed probabilistic measure can be estimated reliably. On the basis of the relationship between the genetic section and the memetic section, 3 versions of LA‐MA are introduced. LLA‐MA behaves according to the Lamarckian learning model, BLA‐MA behaves according to the Baldwinian learning model, and HLA‐MA behaves according to both the Baldwinian and Lamarckian learning models. To evaluate the efficiency of these algorithms, they have been used to solve the graph isomorphism problem. The results of computer experimentations have shown that all the proposed algorithms outperform the existing algorithms in terms of quality of solution and rate of convergence.     

A case study of memetic algorithms for constraint optimization

There is a variety of knapsack problems in the literature. Multidimensional 0–1 knapsack problem (MKP) is an NP-hard combinatorial optimization problem having many application areas. Many approaches have been proposed for solving this problem. In this paper, an empirical investigation of memetic algorithms (MAs) that hybridize genetic algorithms (GAs) with hill climbing for solving MKPs is provided. Two distinct sets of experiments are performed. During the initial experiments, MA parameters are tuned. GA and four MAs each using a different hill climbing method based on the same configuration are evaluated. In the second set of experiments, a self-adaptive (co-evolving) multimeme memetic algorithm (MMA) is compared to the best MA from the parameter tuning experiments. MMA utilizes the evolutionary process as a learning mechanism for choosing the appropriate hill climbing method to improve a candidate solution at a given time. Two well-known MKP benchmarks are used during the experiments.     

Real-coded memetic algorithms with crossover hill-climbing

This paper presents a real-coded memetic algorithm that applies a crossover hill-climbing to solutions produced by the genetic operators. On the one hand, the memetic algorithm provides global search (reliability) by means of the promotion of high levels of population diversity. On the other, the crossover hill-climbing exploits the self-adaptive capacity of real-parameter crossover operators with the aim of producing an effective local tuning on the solutions (accuracy). An important aspect of the memetic algorithm proposed is that it adaptively assigns different local search probabilities to individuals. It was observed that the algorithm adjusts the global/local search balance according to the particularities of each problem instance. Experimental results show that, for a wide range of problems, the method we propose here consistently outperforms other real-coded memetic algorithms which appeared in the literature.     

保持多样性的自适应动态粒子群算法及其应用

针对动态环境中的种群多样性问题,提出一种保持种群多样性的双子群粒子群优化算法。将群搜索算法中的游走者思想引入到粒子群优化算法中,基于群体多样性,子种群B采用不同的方法更新速度和位置,子种群A和子种群B交换最优信息,扩展种群的搜索范围,增强整个群体的多样性水平。将改进的算法应用于复杂变化的抛物线函数和群体动画的跟随效果中,结果表明该算法在动态环境中的有效性,并能够真实模拟群体跟随行为。     

带时间窗车辆路径问题的多目标文化基因算法

针对物流配送中带时间窗的车辆路径问题,以最小化车辆使用数和行驶距离为目标,建立了多目标数学模型,提出了一种求解该问题的多目标文化基因算法。种群搜索采用遗传算法的进化模式和Pareto排序的选择方式,局部搜索采用禁忌搜索机制和存储池的结构,协调两者得到的Pareto非占优解的关系。与不带局部搜索的多目标遗传算法和单目标文化基因算法的对比实验表明,本文算法的求解质量较高。     

A self-adaptive Multimeme Memetic Algorithm co-evolving utility scores to control genetic operators and their parameter settings

Memetic algorithms are a class of well-studied metaheuristics which combine evolutionary algorithms and local search techniques. A meme represents contagious piece of information in an adaptive information sharing system. The canonical memetic algorithm uses a fixed meme, denoting a hill climbing operator, to improve each solution in a population during the evolutionary search process. Given global parameters and multiple parameterised operators, adaptation often becomes a crucial constituent in the design of MAs. In this study, a self-adaptive self-configuring Steady-state Multimeme Memetic Algorithm (SSMMA) variant is proposed. Along with the individuals (solutions), SSMMA co-evolves memes, encoding the utility score for each algorithmic component choice and relevant parameter setting option. An individual uses tournament selection to decide which operator and parameter setting to employ at a given step. The performance of the proposed algorithm is evaluated on six combinatorial optimisation problems from a cross-domain heuristic search benchmark. The results indicate the success of SSMMA when compared to the static MAs as well as widely used self-adaptive Multimeme Memetic Algorithm from the scientific literature.     

Solving the team orienteering problem using effective multi-start simulated annealing

The team orienteering problem (TOP) is known as an NP-complete problem. A set of locations is provided and a score is collected from the visit to each location. The objective is to maximize the total score given a fixed time limit for each available tour. Given the computational complexity of this problem, a multi-start simulated annealing (MSA) algorithm which combines a simulated annealing (SA) based meta-heuristic with a multi-start hill climbing strategy is proposed to solve TOP. To verify the developed MSA algorithm, computational experiments are performed on well-known benchmark problems involving numbers of locations ranging between 42 and 102. The experimental results demonstrate that the multi-start hill climbing strategy can significantly improve the performance of the traditional single-start SA. Meanwhile, the proposed MSA algorithm is highly effective compared to the state-of-the-art meta-heuristics on the same benchmark instances. The proposed MSA algorithm obtained 135 best solutions to the 157 benchmark problems, including five new best solutions. In terms of both solution quality and computational expense, this study successfully constructs a high-performance method for solving this challenging problem.     

融合多向学习的混沌麻雀搜索算法

对于原始麻雀搜索算法（SSA）在迭代过程中表现出的种群多样性减小,易陷入局部最优等问题,提出一种融合多向学习的混沌麻雀搜索算法（MSSA）。利用Hénon混沌映射初始化种群,增加麻雀种群的多样性,扩大可行解的搜索范围,为全局寻优奠定基础;采用多向学习策略增加麻雀跟随者探索未知领域的机会,平衡算法的局部开发性能和全局搜索能力;当算法陷入局部最优时,引用遗传算法中的变异策略依据动态的变异概率对当前最优个体进行扰动变异;将MSSA算法应用到无线传感器网络节点覆盖优化问题。数值实验结果与Wilcoxon秩和检验结果均表明MSSA算法在收敛精度与收敛速度等方面具有更明显的优势。