多维背包问题的一个蚁群优化算法

蚁群优化(ACO)是一种通用的启发式方法,已被用来求解很多离散优化问题.近年来,已提出几个ACO算法求解多维背包问题(MKP).这些算法虽然能获得较好的解但也耗用太多的CPU时间.为了降低用ACO求解MKP的复杂性,文章基于一种已提出但未实现过的MKP的信息素表示定义了新的选择概率的规则和相应的基于背包项的一种序的启发式信息,从而提出了一种计算复杂性较低、求解性能较好的改进型蚁群算法.实验结果表明,无论串行执行还是虚拟并行执行,在计算相同任务时,新算法耗用时间少且解的价值更高.不仅如此,在实验中,文中的新算法获得了ORLIB中测试算例5.250-22的两个"新"解.     

Binary trie coding scheme: an intelligent genetic algorithm avoiding premature convergence

The multi-dimensional knapsack problems (MKP) have a landscape called a rugged landscape, which may lead to local optima without any progress to optimal solution. Optimization requirement often involves searching amongst various solutions under multi-objective situations. Maintaining diversity and avoiding premature convergence while keeping the population size small and unique is one of the prime approaches to meet the requirements. In this paper, we propose a practical solution to the duplicity as well as premature convergence problem. We have introduced the concept of virtually compressed binary trie (VCBT) and tried to show that the VCBT can be naturally integrated with the genetic algorithm (GA) so that duplicates are completely eliminated while the trie size is kept reasonably small and practically feasible. Our binary trie coding scheme (BTCS) relies on problem-specific knowledge in fragmenting the search space into feasible and infeasible regions, and thus pruning the infeasible areas. Pruning of the trie occurs frequently and is dependent upon many parameters (other than the infeasibility) and the trie size is kept small throughout the whole process. Comparison tables are given for the performance of the BTCS and other good performing evolutionary algorithms found in literature for the MKP. Here, the optimization ability of the BTCS is compared against the GA given by Chu and Beasley; in particular, on a suite of standard MKP test instances from the OR library. The simulation results show that the proposed strategy significantly improves the computational efficiency of GA and generates robust and near-optimal solutions.     

一个蚁群优化模型的期望性能分析

用蚁群优化求解组合优化问题时, 信息素模型及其规则可能使问题的各组件之间的竞争失衡, 从而有可能使蚁群搜索停滞在最差解。 研究了蚁群优化求解k-最小生成树问题时的信息素模型及其更新规则对性能的影响,对原有的信息素模型作出了新的解释:直接表示k-最小生成树问题的边被选择的概率。基于新的信息素模型设计了一种新的解的构造过程,这种过程不仅产生可行解, 也产生不可行解;同时研究了使用可行解和全部解更新信息素模型时算法的迭代期望质量随时间的增减情况,其结果表明, 只使用可行解时迭代期望质量随时间连续降低, 而使用全     

改进二进制布谷鸟搜索算法求解多维背包问题

针对多约束组合优化问题--多维背包问题(MKP),提出了一种改进二进制布谷鸟搜索(MBCS)算法.首先,采用经典的二进制代码变换公式构建了二进制布谷鸟搜索(BCS)算法.其次,引入病毒生物进化机制和病毒感染操作,一方面赋予布谷鸟鸟巢位置自变异机制增加种群多样性;一方面将布谷鸟鸟巢位置所组成的主群体的纵向全局搜索和病毒群体的横向局部搜索进行动态结合,进一步提高了算法的收敛速度,降低了陷入局部极值的概率.再次,针对MKP特点设计了不可行解的混合修复策略.最后将MBCS算法同量子遗传算法(QGA)、二进制粒子群优化(BPSO)算法、BCS算法就来源于ELIB数据库和OR_LIB数据库的15个算例进行了仿真对比.实验结果表明,所提算法计算误差均小于1%,标准差小于170,相比这3种算法具有相对更好的寻优精度和求解稳定性,是一种求解多维背包等NP难问题有效的算法.     

改进的差分演化算法求解多维背包问题

多维背包（MKP）是组合优化中一个典型的NP难问题,广泛应用于工程和管理中。提出了一种改进的二进制差分演化算法（Modified Binary Differential Evolution algorithm,MBDE）求解MKP问题,算法关键步骤可分为两部分：二进制群体生成;得到候选可行解。提出了一种有效的衡量商品价值密度的方法用于对二进制个体修正和优化;设计了反向测试搜索和精英局部搜索策略来提高算法探索和开发能力,从而进一步提高了MBDE的求解精度和收敛速度。为验证MBDE算法的有效性,进行了三组实验,并和近期提出的解决MKP问题的其他启发式算法进行了比较,实验结果显示,MBDE算法求解精度更高。从算法运行时间看,求解速度快,非常适合求解大规模的MKP问题。     

一种求解多维背包问题的混合分布估计算法

针对多维背包问题（MKP）,提出一种基于分布估计算法的混合求解算法,该算法基于优势种群构建概率模型,并基于概率模型采样产生新个体;同时,提出一种基于MKP问题信息的修复机制,有效修复采样后种群中的不可行解．另外,设计了一种自适应的局部搜索操作,以增强算法的局部搜索能力,基于标准测试集的仿真结果和算法比较验证了所提出的混合算法的有效性和鲁棒性．     

A hybrid of Nested Partition, Binary Ant System, and Linear Programming for the multidimensional knapsack problem

This work presents a hybrid algorithm of Nested Partition (NP), Binary Ant System (BAS), and Linear Programming (LP) to solve the multidimensional knapsack problem (MKP). The hybrid NP+BAS+LP algorithm takes advantage of the global search strategies of the NP algorithm; the ability of BAS to quickly generate good solutions and incorporates information obtained from solving a LP relaxation of the MKP to help guide the search. It thus incorporates both the lower bounds (LB), found by the BAS, and the upper bounds (UB), found by solving the relaxed LP, into the search by embedding both in the NP framework. An adjustable computation budget is implemented where the number of samples increases if the LB and the UB point to different promising subregions. The proposed hybrid is compared to state-of-the-art solution techniques and is found to be one of the best algorithms in terms of the quality of solutions obtained and CPU time requirements.     

Reliability optimization of a series system with multiple-choice and budget constraints using an efficient ant colony approach

This paper deals with a reliability optimization problem for a series system with multiple-choice and budget constraints. The objective is to choose one technology for each subsystem in order to maximize the reliability of the whole system subject to the available budget. This problem is NP-hard and could be formulated as a binary integer programming problem with a nonlinear objective function. In this paper, an efficient ant colony optimization (ACO) approach is developed for the problem. In the approach, a solution is generated by an ant based on both pheromone trails modified by previous ants and heuristic information considered as a fuzzy set. Constructed solutions are not guaranteed to be feasible; consequently, applying an appropriate procedure, an infeasible solution is replaced by a feasible one. Then, feasible solutions are improved by a local search. The proposed approach is compared with the existing metaheuristic available in the literature. Computational results demonstrate that the approach serves to be a better performance for large problems.     

一种基于DLS和ACO的平台资源规划方法

平台资源规划方法是作战任务规划的重要组成部分,为作战提供资源分配方案。描述了作战任务、平台以及它们之间的关系,建立了以最小化全部任务完成的截止时间和最大化平台资源的利用率为目标的数学模型。设计了用于求解此模型的动态列表规划(Dynamic List Scheduling,DLS)与蚁群算法(Ant Colony Optimization Algorithm,ACO)相结合的算法,其描述了任务选择方法、ACO的二进制编码方案及候选解构造策略,设计了不可行候选解的修正策略和信息素更新方法,构造了包含任务选择平台的时间优先系数、平台功能能力优先系数和后续任务对平台需求程度3个因素的适应度函数。针对作战想定进行了仿真计算,结果表明,基于DLS和ACO的平台资源规划具有良好的规划效果,相比于他人算法,其具有更少的全部任务完成截止时间和更高的平台资源利用率。     

可控搜索偏向的二元蚁群算法

蚁群算法按照信息素轨迹产生的偏向对解空间进行搜索．当前改进蚁群算法性能的主要方法是提高种群的多样性,少有对搜索偏向进行控制．本文以可控搜索偏向作为研究的出发点,通过对至今最优信息素更新方式的分析,得出了从任意代到算法收敛没有发现较优解的概率下限．并以此为基础,把访问量与蚂蚁数量的关系作为控制偏向的依据,在兼顾提高种群多样性的前提下,设计了可控搜索偏向的二元蚁群算法．通过多个函数的测试以及0—1多背包问题的应用,其实验结果表明该算法有较好的搜索能力以及较快的收敛速度．     

贪心二进制狮群优化算法求解多维背包问题

针对经典的多约束组合优化问题——多维背包问题(MKP),提出了一种贪心二进制狮群优化(GBLSO)算法。首先,采用二进制代码转换公式将狮群个体位置离散化,得到二进制的狮群算法;其次,引入反置移动算子对狮王位置进行更新,同时对母狮和幼狮位置重新定义;然后,充分利用贪心算法进行解的可行化处理,增强搜索能力并进一步提高收敛速度;最后,对10个MKP典型算例进行仿真实验,并把GBLSO算法与离散二进制粒子群(DPSO)算法和二进制蝙蝠算法(BBA)进行对比。实验结果表明,GBLSO算法是一种有效的求解MKP的新方法,在求解MKP时具有相对良好的收敛效率、较高的寻优精度和很好的鲁棒性。     

求解多维背包问题的蚁群-拉格朗日松弛混合优化算法

针对多维背包问题(MKP) NP-hard、约束强的特点, 提出一种高效的蚁群-拉格朗日松弛(LR) 混合优化算法. 该算法以蚁群优化(ACO) 为基本框架, 并基于LR 对偶信息定义了一种MKP效用指标. ACO使得整体算法具有全局搜索能力, 所设计的效用指标将MKP的优化目标与约束条件有机地融合在一起. 该指标一方面可以用来定 义MKP核问题, 降低问题规模; 另一方面, 可以用作ACO的启发因子, 引导算法在有希望的解区域中强化搜索. 在大量标准算例上的测试结果表明, 所提出算法的鲁棒性较好; 与其他已有算法相比, 在求解质量和求解效率方面均具有很强的竞争力.

     

Two-stage updating pheromone for invariant ant colony optimization algorithm

Ant colony optimization (ACO) is a metaheuristic approach for combinatorial optimization problems. With the introduction of hypercube framework, invariance property of ACO algorithms draws more attention. In this paper, we propose a novel two-stage updating pheromone for invariant ant colony optimization (TSIACO) algorithm. Compared with standard ACO algorithms, TSIACO algorithm uses solution order other than solution itself as independent variable for quality function. In addition, the pheromone trail is updated with two stages: in one stage, the first r iterative optimal solutions are employed to enhance search capability, and in another stage, only optimal solution is used to accelerate the speed of convergence. And besides, the pheromone value is limited to an interval. We prove that TSIACO not only has the property of linear transformational invariance but also has translational invariance. We also prove that the pheromone trail can limit to the interval (0, 1]. Computational results on the traveling salesman problem show the effectiveness of TSIACO algorithm.     

求解旅行商问题的改进蚁群算法研究

针对蚁群算法收敛速度慢的问题,对蚁群算法信息素更新规则进行研究,提出一个基于迭代思想的信息素更新规则。对信息残留因子进行实验,确定在新的信息素更新规则下信息素挥发系数的最佳合理值。最后针对eil51问题和dantzig42问题两个例子的仿真实验对比基本蚁群算法。实验结果表明,改进的蚁群算法在收敛性和求得最优解方面都明显优于基本蚁群算法和其它人工智能算法。     

基于聚度的自适应动态混沌蚁群算法

针对蚁群算法收敛速度慢，容易陷入局部最优的问题，提出了一种基于聚度的自适应动态混沌蚁群算法（A_ACS）。在迭代前期利用聚度来衡量解的多样性，自适应调节局部信息素分布，同时引入混沌算子来增加种群多样性，避免算法陷入局部最优，从而提高解的精度；在迭代后期去掉混沌算子，减少混沌扰动性，来提高算法的收敛速度。将A_ACS用于TSP问题，仿真结果表明，该算法较ACS和MMAS算法减少了搜索时间，并且提高了解的质量，其平衡了多样性与收敛性之间的矛盾，整体性能优于其他两种算法。     

并行蚁群算法中的自适应交流策略

提出了并行蚁群算法中处理机间信息交流的两种策略,使得各处理机能够自适应地选择其他处理机以进行信息交换和相应信息素的全局更新.还提出了一种确定处理机之间进行信息交流的时间的策略,可以根据解的分布情况自适应地确定信息交流的时间,以取得全局收敛速度和解的多样性之间的平衡.在算法每一次信息交换后,采用自适应的更新策略,根据信息素的均匀度进行信息素的更新,从而避免了早熟和局部收敛.在MPP处理机曙光2000上对TSP问题的实验结果,表明了基于该自适应信息交换策略的并行蚁群算法比其他算法具有更好的收敛性、更高的加速比     

基于信息素的自适应连续域混合蚁群算法

针对连续域混合蚁群算法（HACO）易陷入局部最优和收敛速度较慢的问题,提出了基于信息素的自适应连续域混合蚁群算法（QAHACO）。首先提出了一种新的解更新方式,对档案中的解进行信息素挥发,扩大了搜索范围,提高了算法的全局搜索能力,并且自适应地调整信息素挥发速率,更好地平衡收敛速度和收敛精度,其次采用了一种信息分享机制,将当前解与其他所有解的平均距离和当前解与至今最优解的距离相结合,进一步加快收敛速度。通过对测试函数进行仿真实验,结果表明,和连续域蚁群及其改进算法相比,QAHACO算法的寻优能力明显提高,寻优速度有一定的优势。     

改进蚁群算法在热精轧负荷分配优化中的应用

本文尝试用改进的蚁群算法(IACA)求解热精轧机组负荷分配优化问题.首先,建立负荷分配优化的目标函数和约束条件.为了避免蚁群算法(ACS)在加速收敛中出现停滞现象,IACA通过局部和全局信息素浓度更新、引入约束条件的蚂蚁视觉启发函数和基于轧制理论的智力启发函数对状态转移规则进行改进计算;为了保证算法在迭代后期能够收敛,IACA动态更新状态转移规则中的阈值常数和局部信息素浓度挥发系数.基于实际生产数据的仿真结果表明,IACA能够按照目标函数的要求进行合理的负荷分配,且解的性能优于经验值;与其他优化算法比较,IACA具有较快的求解速度和较高的求解精度.     

基于混合行为的蚁群算法

针对基本蚁群算法易出现停滞、收敛速度慢的问题,在最大最小蚁群算法的基础上提出了一种基于混合行为的蚁群(HBAC)算法,通过引入停止蚂蚁来构造局部路线方式和增加全局调优策略,提高了算法的搜索能力和收敛速度,同时将蚂蚁所寻找的各条路径的信息素限定在一个可动态调整的范围之内,避免了算法过早陷于局部最优解.通过HBAC算法同其他蚁群算法在求解旅行商问题上的实验比较,发现该算法拥有较快的收敛速度,提高了全局最优解搜索能力,在性能上有了较大的提高.     

求解多背包问题的人工鱼群算法

多背包问题是出现在现实世界中许多领域的一个NP-hard组合优化问题。提出一种基于人工鱼觅食,追尾、聚群等行为的求解多背包问题的优化算法。针对多约束导致大量非可行解的产生而使算法性能劣化的问题,采用基于启发式规则的调整算子,使人工鱼始终在可行解域中寻优。数值实验结果表明,提出的算法能够快速搜索到最优解。算法对其他有约束组合优化问题也具有应用价值。