Fitness landscape analysis and memetic algorithms for the quadratic assignment problem

In this paper, a fitness landscape analysis for several instances of the quadratic assignment problem (QAP) is performed, and the results are used to classify problem instances according to their hardness for local search heuristics and meta-heuristics based on local search. The local properties of the fitness landscape are studied by performing an autocorrelation analysis, while the global structure is investigated by employing a fitness distance correlation analysis. It is shown that epistasis, as expressed by the dominance of the flow and distance matrices of a QAP instance, the landscape ruggedness in terms of the correlation length of a landscape, and the correlation between fitness and distance of local optima in the landscape together are useful for predicting the performance of memetic algorithms-evolutionary algorithms incorporating local search (to a certain extent). Thus, based on these properties, a favorable choice of recombination and/or mutation operators can be found. Experiments comparing three different evolutionary operators for a memetic algorithm are presented.     

一种基于模拟退火的多目标Memetic算法

为了改善多目标进化算法的搜索效率，提出了基于模拟退火的多目标Memetic算法．此算法根据Pareto占优关系评价个体适应值，采用模拟退火进行局部搜索，并结合交叉算子和基于网格密度的选择机制改善算法的收敛速度和解的均衡分布．flowshop调度问题算例的仿真结果表明，基于模拟退火的多目标Memetic算法能够产生更接近Pareto前沿的近似集．     

求解SAT问题的拟人退火算法

该文利用一个简单的变换，将可满足性（SAT）问题转换为一个求相应目标函数最小值的优化问题，提出了一种用于跳出局部陷阱的拟人策略，基于模拟退火算法和拟人策略，为SAT问题的高效近注解得出了拟人退火算法（PA），该方法不仅具有模拟退火算法的全局收敛性质，而且具有一定的并行性，继承性。数值实验表明，对于本文随机产生的测试问题例，采用拟人策略的模拟退火算法的结果优于局部搜索算法，模拟退火算法以及近来国际上流行的WALKSAT算法，因此拟人退火算法是可行的和有效的。     

An iterative local search approach based on fitness landscapes analysis for the delay-constrained multicast routing problem

This paper presents the first fitness landscape analysis on the delay-constrained least-cost multicast routing problem (DCLC-MRP). Although the problem has attracted an increasing research attention over the past decade in telecommunications and operational research, little research has been conducted to analyze the features of its underlying landscape. Two of the most commonly used landscape analysis techniques, the fitness distance correlation analysis and the autocorrelation analysis, have been applied to analyze the global and local landscape features of DCLC-MRPs. A large amount of simulation experiments on a set of problem instances generated based on the benchmark Steiner tree problems in the OR-library reveals that the landscape of the DCLC-MRP is highly instance dependent with different landscape features. Different delay bounds also affect the distribution of solutions in the search space. The autocorrelation analysis on the benchmark instances of different sizes and delay bounds shows the impact of different local search heuristics and neighborhood structures on the fitness distance landscapes of the DCLC-MRP. The delay bound constraint in the DCLC-MRP has shown a great influence on the underlying landscape characteristic of the problem. Based on the fitness landscape analysis, an iterative local search (ILS) approach is proposed in this paper for the first time to tackle the DCLC-MRP. Computational results demonstrate the effectiveness of the proposed ILS algorithm for the problem in comparison with other algorithms in the literature.     

Identifying and exploiting commonalities for the job-shop scheduling problem

For many combinatorial problems the solution landscape is such that near-optimal solutions share common characteristics: the so-called commonalities or building blocks. We propose a method to identify and exploit these commonalities, which is based on applying multistart local search. In the first phase, we apply the local search heuristic, which is based on simulated annealing, to perform a set of independent runs. We discard the solutions of poor quality and compare the remaining ones to identify commonalities. In the second phase, we apply another series of independent runs in which we exploit the commonalities. We have tested this generic methodology on the so-called job-shop scheduling problem, on which many local search methods have been tested. In our computational study we found that the inclusion of commonalities in simulated annealing improves the solution quality considerably even though we found evidence that the job-shop scheduling problem is not very well suited to the use of these commonalities. Since the use of commonalities is easy to implement, it may be very useful as a standard addition to local search techniques in a general sense.     

求解24数码问题的改进遗传退火算法

针对具有巨大搜索解空间的24数码问题,提出了一种基于改进遗传模拟退火算法的求解方法。依据问题特征,设计了个体编码方法、高效的适应度评价函数和遗传操作算子,通过在遗传算法中引入模拟退火的Boltzmann更新机制,克服了传统遗传算法易于过早收敛和易于“卡住”陷入局部极小的问题。仿真实验结果表明,提出的算法能够快速搜索到问题的解,算法对其他组合优化问题也具有应用价值。     

Genetic algorithms for flowshop scheduling problems

In this paper, we apply a genetic algorithm to flowshop scheduling problems and examine two hybridizations of the genetic algorithm with other search algorithms. First we examine various genetic operators to design a genetic algorithm for the flowshop scheduling problem with an objective of minimizing the makespan. By computer simulations, we show that the two-point crossover and the shift change mutation are effective for this problem. Next we compare the genetic algorithm with other search algorithms such as local search, taboo search and simulated annealing. Computer simulations show that the genetic algorithm is a bit inferior to the others. In order to improve the performance of the genetic algorithm, we examine the hybridization of the genetic algorithms. We show two hybrid genetic algorithms: genetic local search and genetic simulated annealing. Their high performance is demonstrated by computer simulations.     

TSP问题的禁忌模拟退火求解

提出了一种加入了禁忌表、并且采用了新的温度控制机制的用于求解TSP问题的模拟退火算法。新算法增加了搜索结束阶段进行“爬坡”移动的概率,吸收了禁忌搜索具有较强局部搜索能力的优点和模拟退火算法产生优质解的能力,并且对问题的依赖性低于传统的模拟退火算法。对标准的TSPLib中不同国家的城市数据进行测试的实验结果表明,新的算法比传统的模拟退火算法在求解TSP问题上有更快的收敛速度,在解的质量上也有一定程度的提高。     

正三角形容器内等圆Packing问题的启发式算法

等圆Packing问题研究如何将n个单位半径的圆形物体互不嵌入地置入一个边长尽量小的正三角形容器内,作为一类经典的NP难度问题,其有着重要的理论价值和广泛的应用背景.模拟退火算法是一种随机的全局寻优算法,通过将启发式格局更新策略与基于梯度法的局部搜索策略融入模拟退火算法,并与二分搜索相结合,提出一种求解正三角形容器内等圆Packing问题的启发式算法.该算法将启发式格局更新策略用来产生新格局和跳坑,用梯度法搜索新产生格局附近能量更低的格局,并用二分搜索得到正三角形容器的最小边长.对41个算例进行测试的实验结果表明,文中算法改进了其中38个实例的目前最优结果,是求解正三角形容器内等圆Packing问题的一种有效算法.     

求解圆形packing问题的拟人退火算法

Circles packing problem is an NP-hard problem and is difficult to solve. In this paper, a hybrid search strategy for circles packing problem is discussed. A way of generating new configuration is presented by simulating the moving of elastic objects, which can avoid the blindness of simulated annealing search and make iteration process converge fast. Inspired by the life experiences of people, an effective personified strategy to jump out of local minima is given. Based on the simulated annealing idea and personification strategy, an effective personified annealing algorithm for circles packing problem is developed. Numerical experiments on benchmark problem instances show that the proposed algorithm outperforms the best algorithm in the literature.     

A hybrid simulated annealing metaheuristic algorithm for the two-dimensional knapsack packing problem

The rectangle knapsack packing problem is to pack a number of rectangles into a larger stock sheet such that the total value of packed rectangles is maximized. The paper first presents a fitness strategy, which is used to determine which rectangle is to be first packed into a given position. Based on this fitness strategy, a constructive heuristic algorithm is developed to generate a solution, i.e. a given sequence of rectangles for packing. Then, a greedy strategy is used to search a better solution. At last, a simulated annealing algorithm is introduced to jump out of the local optimal trap of the greedy strategy, to find a further improved solution. Computational results on 221 rectangular packing instances show that the presented algorithm outperforms some previous algorithms on average.     

一种求解TSP问题的新算法

为了求解TSP问题,提出了一种新的遗传算法。它利用距离密集度和适应度定义了自适应的交叉和变异概率,采用改进的交换启发交叉算子,产生不差于父代的个体。根据最优和次优个体的差异,采用2变换法产生新个体或者进行模拟退火操作,局部搜索加快了算法向最优个体靠近的速度。仿真实验表明新算法是一种求解TSP问题的有效方法。     

基于融合算法的测试优化选择问题研究

测试优化选择是个集覆盖问题,而启发式算法是求解集覆盖问题的有效方法。文中将遗传算法、BP神经网络和模拟退火算法进行融合,提出了一种融合算法,该算法充分利用遗传算法全局搜索能力强、BP神经网络训练能力强和模拟退火算法搜索速度快的优点,既避免陷入局部最优的现象,又提高了搜索的效率和精度。该算法已应用于求解测试优化问题。实例证明,该算法能够快速有效地求得测试优化问题的最优解。     

一种改进遗传退火算法的图像分割方法

图像分割是图像处理和分析的基础,本文通过分析遗传算法（Genetic Algorithm, GA）在图像分割中的应用优劣,提出利用模拟退火思想的改进遗传退火（Genetic Simulated Annealing Algorithm, GASA）的图像阈值分割算法,算法整个运行过程由冷却温度进度表控制,使用改进的最大类间方差公式作为遗传算法的适应度函数,从而求得灰度图像的一个最佳阈值用于图像分割。实验结果表明,基于改进遗传退火算法的最大类间方差图像分割方法能较好提高算法的全局搜索能力,避免遗传算法陷入局部最优,并且能更快速、更稳定收敛到最佳的分割阈值,得到更好的图像分割效果。     

Two-dimensional equilibrium constraint layout using simulated annealing

This paper studies the layout optimization problem with equilibrium constraint. It is a two-dimensional packing problem with the industrial background of simplified satellite module layout design, and is known as NP-hard problem. By incorporating the heuristic neighborhood search mechanism and the adaptive gradient method into the simulated annealing procedure, a heuristic simulated annealing algorithm is put forward for this problem. The special neighborhood search mechanism can avoid the disadvantage of blind search in the simulated annealing algorithm, and the adaptive gradient method is used to execute local search and speed up finding the global optimal solution. Numerical examples are illustrated to verify the effectiveness of the proposed algorithm.     

Two-dimensional equilibrium constraint layout using simulated annealing

This paper studies the layout optimization problem with equilibrium constraint. It is a two-dimensional packing problem with the industrial background of simplified satellite module layout design, and is known as NP-hard problem. By incorporating the heuristic neighborhood search mechanism and the adaptive gradient method into the simulated annealing procedure, a heuristic simulated annealing algorithm is put forward for this problem. The special neighborhood search mechanism can avoid the disadvantage of blind search in the simulated annealing algorithm, and the adaptive gradient method is used to execute local search and speed up finding the global optimal solution. Numerical examples are illustrated to verify the effectiveness of the proposed algorithm.     

求解可满足性问题的改进的模拟退火算法

该文为可满足性问题的高效近似求解提出了改进的模拟退火算法。数值实验表明,对于该文随机产生的测试问题例,改进的模拟退火算法完全胜过局部搜索算法、模拟退火算法以及目前国际上流行的WSAT算法。     

A hybrid self-adaptive bees algorithm for examination timetabling problems

A hybrid self-adaptive bees algorithm is proposed for the examination timetabling problems. The bees algorithm (BA) is a population-based algorithm inspired by the way that honey bees forage for food. The algorithm presents a type of neighbourhood search that includes a random search that can be used for optimisation problems. In the BA, the bees search randomly for food sites and return back to the hive carrying the information about the food sites (fitness values); then, other bees will select the sites based on their information (more bees are recruited to the best sites) and will start a random search. We propose three techniques (i.e. disruptive, tournament and rank selection strategies) for selecting the sites, rather than using the fitness value, to improve the diversity of the population. Additionally, a self-adaptive strategy for directing the neighbourhood search is added to further enhance the local intensification capability. Finally, a modified bees algorithm is combined with a local search (i.e. simulated annealing, late acceptance hill climbing) to quickly descend to the optimum solution. Experimental results comparing our proposed modifications with each other and with the basic BA show that all of the modifications outperform the basic BA; an overall comparison has been made with the best known results on two examination timetabling benchmark datasets, which shows that our approach is competitive and works well across all of the problem instances.     

IT外包进度风险控制的自适应禁忌搜索算法

针对委托代理模式下的IT外包项目的进度风险控制问题构建了双层结构的优化模型.设计了自适应禁忌搜索算法对模型进行求解，该算法将多样化搜索机制与禁忌搜索相结合，在算法运行过程中，根据适应值的反馈自动调整禁忌搜索强度与多样化搜索力度；同时，应用贪婪策略构造初始解，循环交替应用两种邻域结构提高算法寻优能力.实验结果表明，进度风险控制显著地降低了IT外包项目的拖期风险，同时使委托方和代理商双方实现收益最大化.将自适应禁忌搜索算法的实验结果分别与遗传算法、模拟退火算法、禁忌搜索算法、自适应遗传算法和自适应模拟退火算法的实验结果进行了比较：在收敛程度和稳定性方面自适应禁忌搜索算法优于其它算法，并且随着问题规模的增加，该算法的优势更为明显.     

Genetic local search for multicast routing with pre-processing by logarithmic simulated annealing

Over the past few years, several local search algorithms have been proposed for various problems related to multicast routing in the off-line mode. We describe a population-based search algorithm for cost minimisation of multicast routing. The algorithm utilises the partially mixed crossover operation (PMX) under the elitist model: for each element of the current population, the local search is based upon the results of a landscape analysis that is executed only once in a pre-processing step; the best solution found so far is always part of the population. The aim of the landscape analysis is to estimate the depth of the deepest local minima in the landscape generated by the routing tasks and the objective function. The analysis employs simulated annealing with a logarithmic cooling schedule (logarithmic simulated annealing—LSA). The local search then performs alternating sequences of descending and ascending steps for each individual of the population, where the length of a sequence with uniform direction is controlled by the estimated value of the maximum depth of local minima. We present results from computational experiments on three different routing tasks, and we provide experimental evidence that our genetic local search procedure that combines LSA and PMX performs better than algorithms using either LSA or PMX only.