基于双种群两阶段变异策略的差分进化算法

针对差分进化算法差分策略优化问题上的不足, 解决DE/best/1策略全局探测能力差, DE/rand/1局部搜索能力弱而带来的鲁棒性降低及陷入局部最优等问题, 本文在差分策略上进行改进, 并且加入邻域分治思想提高进化效率, 提出一种基于双种群两阶段变异策略的差分进化算法(TPSDE). 第一个阶段利用DE/best/1的优势对邻域向量划分完成的子种群区域进行局部优化, 第二个阶段借鉴DE/rand/1的思想实现全局优化, 最终两阶段向量加权得到最终变异个体使得算法避免了过早收敛和搜索停滞等问题的出现. 6个测试函数的仿真实验结果表明TPSDE在收敛速度、优化精度和鲁棒性方面都得到了明显改善.     

基于统计分析的分阶段进行神经网络方法

基于统计分析和分阶段进化，提出一种新的进化神经网络设计方法，本文方法的进化过程分三个阶段：第一阶段，首先按训练样本统计特性设计较小规模的神经网络，第二阶段，引入所有训练样本，在第一阶段的基础上，逐步扩展网络结构，天加的神经元总是单独训练并以抵消原网络的输出误差为其训练目标，直至训练网络达到误差要求，第三阶段，利用统计方法，将网络中非线性变换作用相似的神经元合并，简化网络结构，本文方法一方面减轻了进化算法的压力，另一方面指出了网络进化的方向使得进化网络的学习过程不再是黑箱问题，计算机仿真实验表明，该方法是有效的。     

自适应混合粒子群优化算法求解大规模旅行商问题

基于随机搜索策略的改进增强型自探索粒子群优化算法难于获得大规模旅行商问题的高质量近似解。为此,引入变异和利用进化过程信息缩减问题规模等机制,提出自适应混合粒子群优化算法。进化搜索分多批次自适应进行,每个批次包括两个阶段。第一阶段,多次搜索获得多个不同的局部最优解,并记录于周游边结构中。第二阶段,学习记录的信息,获得多个关键边序列段,每个段归约为一个整体,以此重新初始化种群,并在其基础上进行下个批次的进化搜索。上述过程反复进行,直到在某第一阶段多次进化中都收敛于同一解为止。实验结果对比分析表明该算法能够获得比同类算法更高质量的近似解。     

基于多阶段搜索的约束多目标进化算法

现有约束多目标进化算法的约束处理策略无法有效解决具有大型不可行区域的问题，导致种群停滞在不可行区域的边缘；此外，约束条件下的不连续问题对算法的全局搜索能力以及多样性的维持提出了更高的要求。针对上述问题，提出了一种基于多阶段搜索的约束多目标进化算法（CMOEA-MSS），在该算法的3个阶段采用不同的搜索策略。为使种群快速穿越大型不可行区域并逼近Pareto前沿，所提算法在第一阶段不考虑约束条件，利用一种收敛性指标引导种群搜索；在第二阶段采用一组均匀分布的权重向量来维持种群的多样性，并提出一种改进的epsilon约束处理策略，以保留不可行区域中的高质量解；在第三阶段采用约束优先原则，将搜索偏好集中在可行区域以保证最终解集的可行性。CMOEA-MSS与NSGA-Ⅱ+ARSBX(NondominatedSortingGeneticAlgorithmⅡusingAdaptive Rotation-based Simulated Binary crossover)等算法在MW和DASCMOP测试集上对比的结果表明：在MW测试集上，CMOEA-MSS在7个测试问题上获得了最好的IGD(Inverte...     

第2类U型装配线平衡问题的双阶段蚁群算法

针对电子、汽车等行业中普遍存在的第2类U型装配线平衡问题(UALBP-2),提出了一种双阶段蚁群算法。强调全局搜索的第一阶段算法利用探路蚁,根据操作选择和分配策略以及迭代压缩机制快速得到问题的较优解,减小搜索空间;注重局部搜索的第二阶段算法利用搜索蚁,根据所提的信息素减小更新策略在包含最优解且不断减小的搜索空间中搜索各工位的不同精英负载,基于精英复制策略利用精英蚁将其组合为问题的可行解。对18个标杆算例的33个实例的求解结果验证了所提算法的有效性和稳定性。     

基于统计分析的分阶段进化神经网络方法

基于统计分析和分阶段进化，提出一种新的进化神经网络设计方法．本文方法 的进化过程分三个阶段：第一阶段，首先按训练样本统计特性设计较小规模的神经网络；第 二阶段，引入所有训练样本，在第一阶段的基础上，逐步扩展网络结构，新添加的神经元总 是单独训练并以抵消原网络的输出误差为其训练目标，直至训练网络达到误差要求．第三阶 段，利用统计方法，将网络中非线性变换作用相似的神经元合并，简化网络结构．本文方法 一方面减轻了进化算法的压力,另一方面指出了网络进化的方向使得进化网络的学习过程不 再是黑箱问题．计算机仿真实验表明，该方法是有效的．     

一种两级混合遗传算法的结构与性能

遗传算法的搜索能力很强,但容易陷入早熟。在遗传算法的基础上,提出一种将二级遗传算法混合使用的新算法。新算法用第一阶段的遗传搜索进行全解空间的搜索,第一阶段的搜索结果经过范围缩减策略后,为第二阶段的遗传搜索提供一个改善了的搜索空间,使第二阶段的搜索能够有效地接近全局最优点,克服了早熟现象。通过实例,与其它改进遗传算法相比,新算法在收敛精度上有所提高。     

求解最大割问题的多启动禁忌搜索算法

为了增强局部搜索算法在求解最大割问题上的寻优能力,提高解质量,提出了一种多启动禁忌搜索（MSTS）算法。算法主要包括两个重要组件:一是用于搜索高质量局部优化解的禁忌搜索算法;二是具有全局搜索能力的重启策略。算法首先通过禁忌搜索组件获取局部优化解;然后应用设计的重启策略重新生成初始解并重启禁忌搜索过程。重启策略基于随机贪心的思想,综合利用了“构造”和“扰动”这两种方法生成新的起始解,来逃离局部最优的陷阱从而找到更高优度的解。采用了国际文献中公认的21个算例作为本算法的测试实验集并进行实算, 并与多个先进算法进行比较,MSTS算法在18个算例上得到最好解值,高于其他对比算法。实验结果表明,MSTS算法具有更强的寻优能力和更高的解质量。     

一种基于混合遗传的贝叶斯网络分解算法

针对最优贝叶斯网络分解是一个NP-完全问题,提出了一种基于混合遗传贝叶斯网络分解算法PHGA.PHGA算法将进化过程划分为三个不同的阶段,在前期和中期阶段采用较大的种群规模和交叉率,以及较小的群体选择压力,来增强PHGA算法的全局探索能力,避免早熟现象;在后期采用较小的种群规模和交叉率,以及较大的群体选择压力,并引入爬山局部优化算子,以增强群体在进化后期中的局部寻优能力,提高算法的收敛速度.三个标准的贝叶斯网络上的实验表明该算法在最优解方面要优于遗传算法和模拟退火算法.     

基于势场引导的两阶段协同进化遗传算法

提出一种基于势场引导的两阶段协同进化遗传算法。第一阶段,各种群以有性繁殖为主进化,各种群进化停滞时,通过聚类形成重点搜索区域,缩小了搜索区域,提高了算法效率;第二阶段,各种群以无性繁殖为主进化,加强局部搜索,实现了基于个体适应度的定向进化,提高了算法收敛速度。同时,为了指导种群进化,实现种群间的协同,将环境势场引入至两阶段协同进化过程中。仿真实验表明,该算法具有精度高、收敛速度快等优点,一定程度上克服了目前进化算法的搜索低效性。     

An Adaptive Tradeoff Model for Constrained Evolutionary Optimization

In this paper, an adaptive tradeoff model (ATM) is proposed for constrained evolutionary optimization. In this model, three main issues are considered: (1) the evaluation of infeasible solutions when the population contains only infeasible individuals; (2) balancing feasible and infeasible solutions when the population consists of a combination of feasible and infeasible individuals; and (3) the selection of feasible solutions when the population is composed of feasible individuals only. These issues are addressed in this paper by designing different tradeoff schemes during different stages of a search process to obtain an appropriate tradeoff between objective function and constraint violations. In addition, a simple evolutionary strategy (ES) is used as the search engine. By integrating ATM with ES, a generic constrained optimization evolutionary algorithm (ATMES) is derived. The new method is tested on 13 well-known benchmark test functions, and the empirical results suggest that it outperforms or performs similarly to other state-of-the-art techniques referred to in this paper in terms of the quality of the resulting solutions.     

Quantum cooperative search algorithm for 3-SAT

Grover's search algorithm, one of the most popular quantum algorithms, provides a good solution to solve NP complexity problems, but requires a large number of quantum bits (qubits) for its functionality. In this paper, a novel algorithm called quantum cooperative search is proposed to make Grover's search algorithm work on 3-SAT problems with a small number of qubits. The proposed algorithm replaces some qubits with classical bits and finds assignments to these classical bits using the traditional 3-SAT algorithms including evolutionary algorithms and heuristic local search algorithms. In addition, the optimal configuration of the proposed algorithm is suggested by mathematical analysis. The experimental results show that the quantum cooperative search algorithm composed by Grover's search and heuristic local search performs better than other pure traditional 3-SAT algorithms in most cases. The mathematical analysis of the appropriate number of qubits is also verified by the experiments.     

Solving the quadratic assignment problem with clues from nature

This paper describes a new evolutionary approach to solving quadratic assignment problems. The proposed technique is based loosely on a class of search and optimization algorithms known as evolution strategies (ES). These methods are inspired by the mechanics of biological evolution and have been applied successfully to a variety of difficult problems, particularly in continuous optimization. The combinatorial variant of ES presented here performs very well on the given test problems as compared with the standard 2-Opt heuristic and results with simulated annealing and tabu search. Extensions for practical applications in factory layout are described.     

Effective three-phase evolutionary algorithm to handle the large-scale colorful traveling salesman problem

This paper proposes a novel evolutionary algorithm to handle the colorful traveling salesman problem. The proposed evolutionary algorithm is a three-phase algorithm and utilizes two types of a new crossover and an enhanced local search. In the first phase, quality of population is increased by applying the first crossover. After the first phase, a priority value is computed to each color, based on the best tour of the first phase. During the second phase, priority values are updated when a solution with better cost than existing solutions in population is found. Priority values are used by the second type of crossover, which is used in the second phase. After the second phase, the problem is converted to the classical traveling salesman problem ingeniously, and finally, the third phase is a hybrid genetic algorithm, for which an enhanced local search algorithm is applied. Applying the second type of crossover and updating priority values are continued in the third phase. The proposed algorithm is effective and finds new bounds for many large-scale instances and outperforms other state-of-the-art heuristic in terms of accuracy and speed. In many cases, gaps between results obtained by the proposed algorithm and the other methods are high. For some large-scale instances, proposed algorithm is 44 times faster than the other state-of-the-art competitor, which is the current most efficient algorithm.     

An evolutionary algorithm for large traveling salesman problems

This work proposes an evolutionary algorithm, called the heterogeneous selection evolutionary algorithm (HeSEA), for solving large traveling salesman problems (TSP). The strengths and limitations of numerous well-known genetic operators are first analyzed, along with local search methods for TSPs from their solution qualities and mechanisms for preserving and adding edges. Based on this analysis, a new approach, HeSEA is proposed which integrates edge assembly crossover (EAX) and Lin-Kernighan (LK) local search, through family competition and heterogeneous pairing selection. This study demonstrates experimentally that EAX and LK can compensate for each other's disadvantages. Family competition and heterogeneous pairing selections are used to maintain the diversity of the population, which is especially useful for evolutionary algorithms in solving large TSPs. The proposed method was evaluated on 16 well-known TSPs in which the numbers of cities range from 318 to 13509. Experimental results indicate that HeSEA performs well and is very competitive with other approaches. The proposed method can determine the optimum path when the number of cities is under 10,000 and the mean solution quality is within 0.0074% above the optimum for each test problem. These findings imply that the proposed method can find tours robustly with a fixed small population and a limited family competition length in reasonable time, when used to solve large TSPs.     

基于云模型的实数编码量子进化算法

针对量子进化算法易陷入局部最优和求解精度不高的缺点,利用云模型具有随机性和稳定倾向性的特点,提出了一种基于云模型的实数编码量子进化算法。该算法利用单维云变异进行全局快速搜索,利用多维云进化增强算法局部搜索能力,探索全局最优解。依据算法的进化过程动态调整搜索范围并复位染色体,可以加提高敛速度,并防止陷入局部最优。仿真结果表明,该算法搜索精度和效率得到提高,适合求解复杂函数优化问题。     

用于连续域寻优的分组蚁群算法

用蚁群算法进行多模函数优化时,容易陷入局部最优,从而影响了寻优精度和收敛速度。因此提出了一种用于求解连续空间优化问题的分组蚁群算法。该算法将连续空间优化问题的定义域划分成若干个子区域,并给每个子区域分配一组蚂蚁。每组蚂蚁在各自的区域里进行搜索,且在搜索过程采用“精英策略”并利用精英蚂蚁更新普通蚂蚁的位置信息,以加快算法的收敛速度。同时,当普通蚂蚁离精英蚂蚁之间的距离较长时,使用大步长搜索,以加快搜索速度,反之,采用小步长搜索,可提高搜索过程的精细程度。该方法使每组蚂蚁的搜索空间成倍地缩小并能有效地改善陷入局部最优的情况,从而能使收敛速度和精度大幅提高。计算机的仿真实验结果证实了这一结论。     

Multi-modal function optimization with the ZEDS (zoomed evolutionary dual strategy) algorithmzoomed evolutionary algorithm

This article introduces a new evolutionary algorithm for multi-modal function optimization called ZEDS (zoomed evolutionary dual strategy). ZEDS employs a two-step, zoomed (global to local), evolutionary approach. In the first (global) step, an improved ‘GT algorithm’ is employed to perform a global recombinatory search that divides the search space into niches according to the positions of its approximate solutions. In the second (local) step, a ‘niche evolutionary strategy’ performs a local search in the niches obtained from the first step, which is repeated until acceptable solutions are found. The ZEDS algorithm was applied to some challenging problems with good results, as shown in this article.     

一种自适应多策略行为粒子群优化算法

针对粒子群优化算法收敛速度慢、局部搜索能力差等缺点,提出一种自适应多策略行为粒子群优化算法.算法中每个粒子拥有4种行为进化策略,在迭代过程中通过计算每种进化策略的立即价值、未来价值和综合奖励来决定粒子的进化行为,并通过策略行为概率变异算法提升个体寻优速度或避免陷入局部最优解.在经典的基准测试函数上,对新算法与其他7个群智能进化算法的测试结果进行比较分析,结果表明所提出算法具有很好的求解精度和收敛速度,尤其适合应用于一些高维优化问题.     

基于多种编码的多群体遗传算法

为了有效地克服标准遗传算法（SGA）中的早熟收敛现象,提出了一种基于多种编码的多群体遗传算法,该方法是采用3个群体同时进行进化的策略,其中,第1个 本是采用浮点数编码方法,以使该群体具有较强的局部搜索能力,第2个群体是采用二进制编码方法,以使该群体具有较强的全局搜索能力。第3个群体为“精华种群”,用于保存算法在进化过程中产生的优秀个体,在进化过程中,还通过引入“移民”策略来交换3个群体中的优秀个体,以有效地增加群体的多样性,该算法不仅不易陷入局部收敛,还具有较强的跳出局部收敛的能力,且收敛速度较快,通过对一系列典型复杂多模函数进行的优化计算试验,结果证实了该方法的有效性和优越性。