黑白二次分配问题

二次分配问题QAP(quadratic assignment problem)的变种问题是当前的研究热点.实际应用中存在一类不能用QAP及其现有变种描述的问题,该类问题在QAP问题的基础上增加了额外的约束条件:将设备分为黑白两色,其中白色设备要求与至少一个黑色设备的距离不超过预定阈值.文章将之定义为黑白二次分配问题BWQAP(Black and White QAP).文章首先分析了它的计算复杂性,指出该问题是NP-难解问题,不存在ε-近似度的多项式时间近似算法(ε>O).同时证明了其可行解的存在性与黑白图上的支配集问题等价,也属于NP-难解问题.为了能在可接受的时间内得到大规模实例质量可接受的近似解,提出了一种求解BWQAP的启发式算法GFO.该算法利用QAP现有算法得到初始解,然后利用局部搜索策略完成解的可行化和优化.大量实验表明,该启发式算法能够有效地求解BWQAP问题的实例.     

连续空间优化问题的自适应蚁群系统算法

蚁群算法是进化计算中一种新型优化算法,其基本算法用于求解排序类型的组合优化问题本文提出一种用于连续空间优化问题求解的蚁群算法,采用了新的基于目标函数值的启发式信息素分配算法,以及搜索过程中最优解的筛选方法.根据目标函数来自适应调整蚂蚁的路径搜索行为,从而保证算法快速找到全局最优解.一个多极值点的连续优化问题求解实例证明了该方法的有效性     

求解平衡约束圆形Packing问题的快速启发式并行蚁群算法

带平衡约束圆形Packing问题属于NP-hard问题,求解困难.提出一种求解该问题的快速启发式并行蚁群算法.首先提出一种启发式方法:在轮盘赌选择定序的概率公式中增加质量因子和外围逆时针排列定位待布圆,并用它构造出多样性种群个体(相交圆数不超过3的布局方案).然后将蚁群优化与并行搜索相结合,使种群个体快速收敛到最优解或迭代出存在少量干涉的近似最优解(1～3个相交圆).若为后者,则基于物理模型用最速下降法将其快速调整成最优解.所采用的启发式方法、并行蚁群搜索机制和快速调整策略有机结合提高了算法的搜索精度和效率.数值实验表明该算法在性能指标上优于已存在的算法.     

利用近似解加速求解SAT问题的启发式完全算法

结合DPLL完全算法能够证明可满足性(SAT)问题的不可满足性和局部搜索算法快速的优点,提出利用近似解加速求解SAT问题的启发式完全算法.首先利用局部搜索算法快速地得到一个近似解,并将该近似解作为完全算法的初始输入,用于其中分支变量的相位决策.该算法引导完全算法优先搜索近似解所在的子空间,加速解决器找到可满足解的过程,为SAT问题的求解提供了一种新的有效途径.实验结果表明,该算法有效地提高了决策的精度和SAT解决器的效率,对很多实例非常有效.     

一种求解TSP的混合遗传蚁群算法

结合遗传算法和蚁群算法,提出了一种求解TSP的基于启发式遗传信息的蚁群遗传算法。该算法由蚁群遗传算法和基于启发式遗传信息的蚁群算法两部分组成。蚁群遗传算法将蚁群算法和遗传算法结合起来,提高了遗传算法的种群的多样性;基于启发式遗传信息的蚁群算法是将启发式遗传信息加入到蚁群算法中,防止蚁群算法对信息素过分依赖,缩小最优解的搜索空间。HGI ACGA算法是将启发式遗传信息加入到蚁群遗传算法中,可以提高蚁群算法的收敛速度和寻优能力。实验结果表明,HGI ACGA算法在收敛速度和收敛精度上均优于ACGA和ACA算法。     

基于群智能的连续优化算法研究

在对蚁群优化算法(ACO)和粒子群优化算法(PSO)进行分析的基础上,提出一种解决函数连续优化的群智能混合策略-CA-PSO.在求解过程中,首先对解空间进行区域划分,进而利用ACO在优化初期具备的快速收敛性能,在整个解空间内搜索最优解的敏感区域.然后利用蚁群的搜索结果初始化PSO粒子,利用PSO快速和全局收敛性进行所在小区域内的搜索.种群更新时根据蚁群的拓扑结构和小区域间的阶跃规则,蚁群不断向最优解敏感区域聚集,使得敏感区域内粒子数增加,则局部的PSO搜索策略可以更细密的搜索最优.实例结果表明,CA-PSO既能保证解的分布性与多样性,又避免了在多峰值函数寻优过程中陷入局部最优解而停止运算,最终将收敛到全局最优解.     

用于求解旅行商问题的深度智慧型蚁群优化算法

启发式算法是求解组合优化问题求解的重要手段,其主要特征是能够以可接受的计算代价找到足够好的可行解.然而,设计良好的用于求解组合优化问题的启发式算法需要大量的专业领域知识以及大量的试错工作,且人工设计的启发式算法不能够保证在不同问题集上均具有一致性表现.另一方面,深度学习方法能够通过学习自动设计启发式规则,然而深度学习方法通常缺少在解空间内搜索的能力.为克服以上问题,提出了一种基于蚁群优化和深度强化学习的混合启发式算法框架.在该框架中,蚁群算法能够利用深度强化学习提取的启发式信息,而深度强化学习方法的解空间搜索性能也由于蚁群算法的加入而获得提高.采用经典的TSPLIB中的算例对该算法求解旅行商问题的效能进行了计算验证,结果表明采用深度学习方法能够极大地提升蚁群算法的计算表现,并降低其计算代价.     

改进的蚁群算法及其在弹道优化中的应用

针对连续空间的优化问题提出了一种改进蚁群算法及搜索空间的自适应调整方法,将搜索空间逐步缩小到最优解附近,并通过信息素扩散机制增强对最优解附近区域的搜索,这些改进措施有利于改善蚁群算法的收敛速度和提高算法的求解精度。将这种改进算法应用到弹道优化过程中,可以有效收缩搜索空间范围获得高精度的最优弹道,这说明了算法的有效性。     

基于MMAS的多目标优化算法研究

针对多目标优化问题求解过程中多个目标相互制约难以求解的特点,为了多目标的协调优化,提出了一种基于最大最小蚁群算法(MMAS)的多目标优化蚁群算法.将蚁群算法的离散搜索机制映射到连续空间,修改了离散蚁群算法的行进规则和信息素的存留策略,使蚁群算法能够应用于解决解空间连续的问题.最大最小蚂蚁系统信息素取值方式的引入,极大地改善了蚁群算法搜索过程中容易陷入停滞的问题,尤其改善了蚁群算法在解空间的全局搜索能力.通过对两组测试函数求解的结果与其它方法比较,仿真结果表明所获得的最优解更多,分布范围更广,所求得的最优解集更加逼近真实的最优前沿.     

改进蚁群算法在QoS组播路由中的应用

QoS组播路由是网络传输中的一项关键技术,蚁群算法是解决多QoS约束组播路由问题的一种启发式算法。针对蚁群算法的缺点,提出了一种双向蚁群算法对该问题进行求解,并改进了蚁群算法的信息素更新策略。仿真实验表明,该算法能快速搜索并收敛到全局（近似）最优解,且随着网络规模的增大,算法保持了良好的特性。     

针对QAP问题的改进型蚁群优化算法研究

本文结合二次分配问题(quadratic assignment problem,QAP)的特点,通过分析传统蚂蚁算法在解决QAP问题时收敛过快,精度不高的缺点,提出一种以ACS(ant colony system)为基础的改进蚁群算法――信息素迭代累积ACS(ACS with accumu-lated pheromone by iteration,ACS_API)。新方法通过对定义启发式信息和信息素更新规则的改进,扩大了搜索空间,从而避免过早收敛,陷入局部最优解中。该算法已应用于QAP标准测试数据,并通过与另外两种先前提出的改进蚂蚁算法(HAS_QAP,ACO_GLS)的比较分析得出了它在算法精度和执行时间上的优势。     

解决二次分配问题的改进蚁群算法

现有的解决二次分配问题的蚁群算法大都与局部搜索过程相结合,文章对其中的局部搜索过程做了修改:一方面结合利用包含全局信息的信息素来指导局部搜索,避免了快速陷入局部最优;另一方面加入了一个二次机会策略,充分搜索解邻域,增强了算法的搜索能力。运用该文给出的算法,针对QAPLIB(二次分配基准问题库)中的问题进行了计算,并将结果与原有蚁群算法进行了比较。实验结果表明该文提出的算法具有更优的性能。     

Backbone analysis and algorithm design for the quadratic assignment problem

As the hot line in NP-hard problems research in recent years, backbone analysis is crucial for phase transition, hardness, and algorithm design. Whereas theoretical analysis of backbone and its applications in algorithm design are still at a begin- ning state yet, this paper took the quadratic assignment problem （QAP） as a case study and proved by theoretical analysis that it is NP-hard to find the backbone, i.e., no algorithm exists to obtain the backbone of a QAP in polynomial time. Results of this paper showed that it is reasonable to acquire approximate backbone by inter- section of local optimal solutions. Furthermore, with the method of constructing biased instances, this paper proposed a new meta-heuristic -- biased instance based approximate backbone （BI-AB）, whose basic idea is as follows： firstly, construct a new biased instance for every QAP instance （the optimal solution of the new instance is also optimal for the original one）; secondly, the approximate backbone is obtained by intersection of multiple local optimal solutions computed by some existing algorithm; finally, search for the optimal solutions in the reduced space by fixing the approximate backbone. Work of the paper enhanced the research area of theoretical analysis of backbone. The meta-heuristic proposed in this paper provided a new way for general algorithm design of NP-hard problems as well.     

用蚁群算法求解带平衡约束的圆形布局问题

采用启发式方法结合演化算法的思路求解带平衡约束的圆形布局问题.首先对传统优化模型进行调整,并探讨了调整的合理性;然后设计一种分步定位的布局方法,在此基础上利用蚁群算法寻优;最后利用局部搜索技术,在传统模型意义下对布局进行了改进.数值实验表明,算法的性能比目前已有的结果有较大的提高.     

Upper and Lower Bounds for Randomized Search Heuristics in Black-Box Optimization

Randomized search heuristics like local search, tabu search, simulated annealing, or all kinds of evolutionary algorithms have many applications. However, for most problems the best worst-case expected run times are achieved by more problem-specific algorithms. This raises the question about the limits of general randomized search heuristics. Here a framework called black-box optimization is developed. The essential issue is that the problem but not the problem instance is knownto the algorithm which can collect information about the instance only by asking for the value of points in the search space. All known randomized search heuristics fit into this scenario. Lower bounds on the black-box complexity of problems are derived without complexity theoretical assumptions and are compared with upper bounds in this scenario.     

基于蚁群算法的QoS组播路由问题研究

提出一种基于蚁群算法的服务质量(QoS)多约束的组播路由算法,算法通过引入模拟退火思想和多行为蚂蚁,解决了常规蚁群算法搜索能力差,容易陷入局部最优的缺点.给出一个网络路由模型,给定相关参数进行仿真实验,实验结果表明,基于模拟退火思想的逆向蚂蚁算法性能优于常规蚁群算法,能更好地搜寻到全局最优解.     

混合二元蚁群算法求解集装箱装载问题

集装箱装载问题是一个具有复杂约束条件的组合优化问题,属于NP-hard问题。针对集装箱装载问题的特点,设计了空间三叉树,对可利用空间采用三叉树划分策略,利用二元蚁群算法结合启发式算法进行求解,即先利用二元蚁群算法确定预备装入货物集,再用启发式算法决定货物的装入优先级顺序,并给出了有效的装箱算法。实例结果表明该算法的有效性和实用性。     

Ant colony optimization combined with taboo search for the job shop scheduling problem

In this paper, we present a hybrid algorithm combining ant colony optimization algorithm with the taboo search algorithm for the classical job shop scheduling problem. Instead of using the conventional construction approach to construct feasible schedules, the proposed ant colony optimization algorithm employs a novel decomposition method inspired by the shifting bottleneck procedure, and a mechanism of occasional reoptimizations of partial schedules. Besides, a taboo search algorithm is embedded to improve the solution quality. We run the proposed algorithm on 101 benchmark instances and obtain competitive results and a new best upper bound for one open benchmark instance is found.     

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.     

GACO – A HYBRID ANT COLONY OPTIMIZATION METAHEURISTIC FOR THE DYNAMIC LOAD-BALANCED CLUSTERING PROBLEM IN AD HOC NETWORKS

We present the design of a novel hybrid genetic ant colony optimization (GACO) metaheuristic. Genetic ant colony optimization is designed to address the dynamic load-balanced clustering problem formulated from ad hoc networks. The main algorithm in GACO is ACO. Whenever an environment change occurs (i.e., nodes move), it makes use of a genetic algorithm to quickly achieve adaptation by refocusing the search process around promising areas of the search space induced by the new problem structure. Compared to other ACO approaches for dynamic problems, GACO does not depend on any problem-specific heuristics to repair or deconstruct solutions. Genetic ant colony optimization also does not require the knowledge of the specific changes that occurred. We compare GACO with three other adaptation methods, namely, P-ACO, PAdapt, and GreedyAnts. P-ACO is a population-based ACO approach that invokes a repair algorithm on its population of solutions when an environment change occurs. PAdapt works by adapting the values of major ACO parameters, while GreedyAnts employs a group of ants that construct solutions in a greedy manner. Empirical results show that GACO is able to react and recover faster from any performance degradation. Genetic ant colony optimization also produces better solutions within the allowable recovery window. These results are shown to be statistically significant.