基于信息素的改进蚁群算法及其在TSP中的应用

针对基本蚁群算法收敛速度慢、易陷于局部最优从而导致搜索停滞的缺陷,提出了一种改进蚁群算法模型.改进算法引入信息素调节系数,避免算法初期各路径上信息素出现过大差异,导致算法"早熟".通过动态调整信息素挥发,在求解速度和寻找全局最优之间寻找平衡.对旅行商问题的仿真结果表明:改进算法的求解结果和求解效率都明显优于基本蚁群算法.     

求解图着色问题的量子蚁群算法

针对经典的图着色问题,在蚁群算法的基础上结合量子计算提出一种求解图着色问题的量子蚁群算法. 将量子比特和量子逻辑门引入到蚁群算法中,较好地避免了蚁群算法搜索易陷入局部极小的缺陷,并显著加快了算法的运算速度. 通过图着色实例的大量仿真实验,表明算法对图着色问题的求解是可行的、有效的,且具有通用性.     

求解旅行商问题的一种改进粒子群算法

本文研究了求解旅行商问题的粒子群算法。针对标准粒子群算法在求解旅行商问题过程中容易出现早熟和停滞现象的缺点,提出了一种改进的粒子群算法。首先,在初始种群的选取过程中,利用改进的贪婪策略直接获得具有较高性能的初始种群以提高算法的搜索效率。其次,通过引入次优吸引子,使粒子在搜索过程中可以更加充分地利用群体的信息来提高自身的性能,有效抑制收敛过程中的停滞现象,提高算法的搜索能力。最后为了验证所提出的方法的有效性和可行性,对TSPLIB标准库中的多个实例进行了测试,并给出了数值结果。     

求解全局优化问题的改进蝙蝠算法[英文]

蝙蝠算法(BA)是一类基于试探技巧的群智能优化算法,该算法已被广泛用于诸多领域问题的求解.本文提出一个改进的蝙蝠算法NIBA.在算法中,为了加强蝙蝠算法的局部和全局搜索能力,提出了三个改进策略.首先,为了改进蝙蝠的局部搜索能力,在当前最优解处给出了一个新的搜索方程.其次,为了改进算法的全局搜索能力,平衡算法的开发能力和探索能力,算法吸收并改进了和声搜索机制.最后,为了进一步提高NIBA算法的搜索能力,在当前最优解处,算法采用了混沌搜索机制.为了验证算法的性能,针对18个标准测试函数进行了数值实验.与其它算法的比较结果显示,NIBA算法具有更好的稳定性,且效率更高.     

经过改进的求解TSP问题的蚁群算法

介绍了一种求解TSP问题的算法—改进的蚁群算法,算法通过模拟蚁群搜索食物的过程,可用于求解TSP问题,算法的主要特点是:正反馈、分布式计算、与某种启发式算法相结合.通过对传统蚁群算法的改进可以得到较好的结果.计算机仿真结果表明了该算法的有效性.     

集装箱翻箱问题的蚁群算法改进

翻箱问题属于NP难问题,基本蚁群算法在求解该问题上收敛困难且寻优能力低。因此,本文提出了一种适合于翻箱模型的改进型蚁群算法,在概率决策机制、解的重构、信息素更新机制三个方面对基本蚁群算法进行改进。最后通过与其他算法的分析比较,验证了该改进算法的可行性与有效性。     

求解一般整数规划问题的改进蝙蝠算法

蝙蝠算法是一种新型的智能优化算法,本文针对基本蝙蝠算法易陷入局部最优、过早处于停滞阶段等不足之处,在蝙蝠速度更新公式中引入了惯性权重,并采用权值动态递减的方式变换权重,更好地平衡了算法的全局搜索能力和局部搜索能力.通过求解一系列经典整数规划问题,并与已有算法进行比较,结果表明:改进的蝙蝠算法在一般整数规划问题的求解中具有较高的计算效率和精度,以及较强的全局搜索能力.     

面向电商终端物流配送的电动车配置与路径集成优化

在电子商务终端物流配送方面,存在能力与需求的矛盾。一方面,电动车存在货物容量约束和电池电量约束,配送能力有限;另一方面,一个物流配送点需要为众多的消费者进行门到门的配送,配送任务繁重。针对电子商务环境下终端物流配送规模大、电动车货物容量和行驶里程有限的问题,建立电商终端物流配送的电动车配置与路径规划集成优化模型,并提出一种基于临近城市列表的双策略蚁群算法,实现物流配送电动车辆配置与配送路径集成优化。该模型以电动车辆数最少和总路径最短为目标,以电动车货物容量和电池续航里程为约束,是带容量的车辆路径问题的进一步扩展,属于双容量约束路径规划问题。双策略蚁群算法在货物容量和续航里程的约束下,将蚁群搜索策略分为两类,即基于临近城市列表的局部搜索策略和全局搜索策略,在提高搜索效率的同时防止陷入局部优化。最后,通过阿里巴巴旗下菜鸟网络科技有限公司在上海的30组真实配送数据进行了测试,验证双策略蚁群算法显著优于一般蚁群算法。     

一种新的混合蚁群算法

设计一种新的混合蚁群算法,该算法以一种新的加权二进制蚁群算法为基础,将分布估计算法PB IL的概率分布模型用来指导蚂蚁路径的选择,同时对不同位置的蚂蚁采用加权系数来控制信息素散发量,根据信息素得到的转移概率、PB IL的模型概率及二者融合的概率来产生新的个体,保证了个体的多样性,从而提高了算法的快速性和全局最优解的搜索能力.通过测试函数优化表明该算法具有良好的收敛速度和稳定性,改善了蚁群算法容易陷入局部最优而早熟的缺陷.     

基于量子粒子群算法的电力系统负荷多目标优化分配

针对电力系统经济负荷优化分配问题,提出了一种基于量子粒子群的多目标优化算法.该算法通过将改进后的量子进化算法融合到粒子群中,采用量子位对粒子的当前位置进行编码,用量子旋转门实现对粒子最优位置的搜索,用量子非门实现粒子位置的变异以避免早熟收敛.这种搜索机制能够遍历解空间,增强种群的多样性,并能用量子位的概率幅将最优解表述为解空间中的多种表述形式,从而增强全局最优的可能性.最后,通过算例进行仿真分析,结果表明算法的搜索能力和优化效率均优于普通粒子群算法.     

Heuristic approaches for solving transit vehicle scheduling problem with route and fueling time constraints

Electric bus scheduling problem can be defined as vehicle scheduling problem with route and fueling time constraints (VSPRFTC). Every vehicle’s travel miles (route time) after charging is limited, thus the vehicle must be recharged after taking several trips and the minimal charging time (fueling time) must be satisfied. A multiple ant colony algorithm (ACA) was presented to solve VSPRFTC based on ACA used to solve traveling salesman problem (TSP), a new metaheuristic approach inspired by the foraging behavior of real colonies of ants. The VSPRFTC considered in this paper minimizes a multiple, hierarchical objective function: the first objective is to minimize the number of tours (or vehicles) and the second is to minimize the total deadhead time. New improvement of ACA as well as detailed operating steps was provided on the basis of former algorithm. Then in order to settle contradiction between accelerating convergence and avoiding prematurity or stagnation, improvement on route construction rule and Pheromone updating rule was adopted. A group feasible trip sets (blocks) had been produced after the process of applying ACA. In dealing with the fueling time constraint a bipartite graphic model and its optimization algorithm are developed for trip set connecting in a hub and spoke network system to minimize the number of vehicle required. The maximum matching of the bipartite graph is obtained by calculating the maximum inflow with the Ford–Fulkerson algorithm. At last, an example was analyzed to demonstrate the correctness of the application of this algorithm. It proved to be more efficient and robust in solving this problem.     

An ant colony optimization approach for the multidimensional knapsack problem

Ant colony optimization is a metaheuristic that has been applied to a variety of combinatorial optimization problems. In this paper, an ant colony optimization approach is proposed to deal with the multidimensional knapsack problem. It is an extension of Max Min Ant System which imposes lower and upper trail limits on pheromone values to avoid stagnation. In order to choose the lower trail limit, we provide a new method which takes into account the influence of heuristic information. Furthermore, a local search procedure is proposed to improve the solutions constructed by ants. Computational experiments on benchmark problems are carried out. The results show that the proposed algorithm can compete efficiently with other promising approaches to the problem.     

Iterated local search for the quadratic assignment problem

Iterated local search (ILS) is a simple and powerful stochastic local search method. This article presents and analyzes the application of ILS to the quadratic assignment problem (QAP). We justify the potential usefulness of an ILS approach to this problem by an analysis of the QAP search space. However, an analysis of the run-time behavior of a basic ILS algorithm reveals a stagnation behavior which strongly compromises its performance. To avoid this stagnation behavior, we enhance the ILS algorithm using acceptance criteria that allow moves to worse local optima and we propose population-based ILS extensions. An experimental evaluation of the enhanced ILS algorithms shows their excellent performance when compared to other state-of-the-art algorithms for the QAP.     

Meta-heuristic algorithms for wafer sorting scheduling problems

Wafer sorting is usually regarded as the most critical stage in the whole wafer probing process. This paper discusses the wafer sorting scheduling problem (WSSP) with total setup time minimization as the primary criterion and the minimization of the number of machines used as the secondary criterion. Although the need to consider multiple criteria in real-world WSSPs is widely recognized, the present study is the first attempt to investigate this argument with setups consideration. In view of the strongly NP-hard nature of this problem, three meta-heuristic algorithms—an ant colony system algorithm, a Genetic algorithm, and a Tabu search algorithm are proposed. The proposed meta-heuristics are empirically evaluated by 480 simulation instances based on the characteristics of a real wafer testing shop-floor and found to be very effective in terms of finding good quality solutions.     

蚂蚁算法和小生境遗传算法的融合

蚂蚁算法是一种新型的模拟进化算法,也是一种随机型智能搜索算法.较为系统的总结了算法的基本理论,分析了其基本算法解决TSP问题的模型,针对蚂蚁算法易出现停滞的缺点,把小生境遗传算法和蚂蚁算法融合,仿真比较实验结果表明优于基本蚂蚁算法.     

A novel bee swarm optimization algorithm for numerical function optimization

The optimization algorithms which are inspired from intelligent behavior of honey bees are among the most recently introduced population based techniques. In this paper, a novel algorithm called bee swarm optimization, or BSO, and its two extensions for improving its performance are presented. The BSO is a population based optimization technique which is inspired from foraging behavior of honey bees. The proposed approach provides different patterns which are used by the bees to adjust their flying trajectories. As the first extension, the BSO algorithm introduces different approaches such as repulsion factor and penalizing fitness (RP) to mitigate the stagnation problem. Second, to maintain efficiently the balance between exploration and exploitation, time-varying weights (TVW) are introduced into the BSO algorithm. The proposed algorithm (BSO) and its two extensions (BSO–RP and BSO–RPTVW) are compared with existing algorithms which are based on intelligent behavior of honey bees, on a set of well known numerical test functions. The experimental results show that the BSO algorithms are effective and robust; produce excellent results, and outperform other algorithms investigated in this consideration.     

多目标0-1规划问题的蜂群算法

针对多目标0-1规划问题,本文给出一种新型的智能优化算法——蜂群算法进行求解,并通过实例验证,与遗传算法、蚁群算法和元胞蚁群算法作了相应比较。就多目标0-1规划问题而言,蜂群算法能得到更多的Pareto解,说明了蜂群算法在解决该类问题上的有效性。     

灾情巡视问题的蚁群两目标优化算法研究

分析目前灾情巡视问题求解方法存在的缺陷,归纳出灾情巡视问题两目标优化模型.针对灾情巡视问题模型特点,引入蚁群算法和多目标优化理论,提出两个灾情巡视问题的蚁群两目标优化算法:算法1将灾情巡视问题的道路网络转化为完全图,增加m-1个(m为巡视组数)虚拟巡视起点,将灾情巡视两目标优化问题转化为单旅行商两目标优化问题,然后使用蚁群算法和多目标优化理论进行迭代求解.算法2使用一只蚂蚁寻找一个子回路,m个子回路构成一个灾情巡视可行方案,采用罚函数法和多目标优化理论构建增广两目标优化评价函数,使用g组,共g×m只蚂蚁共同协作来发现灾情巡视问题的最优解.算法特点:①算法1将灾情巡视两目标优化问题转化为单旅行商两目标优化问题,可以充分利用已有蚁群算法求解单旅行商问题的研究成果;②两个算法引入蚁群算法,提高了算法效率;③两个算法克服目前灾情巡视问题的求解方法不严密性缺陷;④两目标优化算法可以为用户提供多个满足约束条件的Pareto组合解,扩大了用户选择范围,增强了算法的适用性.算法测试表明:灾情巡视问题的蚁群两目标优化算法是完全可行和有效的.     

启发式蚁群算法及其在高填石路堤稳定性分析中的应用

模仿蚁群之群体行为而发展起来的蚁群算法 ( ACA) ,目前多用于求解组合优化问题 .为了让 ACA能求解复杂边坡工程问题 ,本文对蚁群算法的结构和蚂蚁转移概率的确定方法进行改进 ,得到一个新的评价复杂边坡稳定性的方法——启发式蚁群算法 ( HACA) ,探讨了 HACA在高填石路堤稳定性分析中的应用 .