基于量子粒子群优化算法的车辆路径问题

针对粒子群优化算法的搜索空间有限、容易出现早熟现象的缺陷,提出将一种基于量子行为的粒子群优化算法用于求解车辆路径问题.车辆路径问题是组合优化问题中的NP-难问题.将量子粒子群算法用于车辆路径问题求解,用粒子的位置表示车辆路径,建立车辆路径的数学模型.与粒子群算法相比,量子粒子群算法提高了最优路径搜索的成功率,能更有效的求解问题.     

基于粒子群优化的考试时间安排问题的求解算法

粒子群优化算法是近年来发展起来的一种元启发式的搜索算法,是目前解决组合优化问题的最有效的算法之一.针对考试时间表问题(ETP),通过基于时间序列的粒子编码方式和新的更新算子,建立ETP问题的粒子群求解模型,并结合简化邻域搜索算法给出了改进策略.仿真实验结果表明所提算法及策略的有效性.     

粮食物流车辆路径问题的混合粒子群算法

研究粮食物流运输车辆路径问题.针对粮食物流过程批量大、点多、面广等特点,引入模拟退火思想,将粒子群优化算法与模拟退火算法结合,提出一种求解粮食物流车辆路径问题的混合粒子群算法.仿真结果表明,该算法可以快速地求得带时间窗的粮食物流车辆路径问题的优化解,进而降低粮食物流配送成本.     

车辆路径问题的改进混合粒子群算法研究

针对各种启发式算法在求车辆路径问题(VRP)中的缺陷,提出了改进的混合粒子群算法(MHPSO)的求解方法.分析了基于速度-位置更新策略传统粒子群算法在解决离散的和组合优化问题的不足.考虑到算法在求解过程中种群多样性的损失过快,引进了种群的多样性测度参数-平均粒距,以保持种群的多样性.同时利用混沌运功的随机性、遍历性和规律性等特性,采用混沌初始化粒子编码.详细讨论了该算法在车辆路径问题中的求解策略.针对同一个实例,将改进的混合粒子群算法与遗传算法从多个角度进行比较.仿真结果表明,论文所提出的算法性能较好,可以快速、有效求得车辆路径问题的优化解或近似优化解.     

应急物流车辆调度多目标鲁棒优化研究

针对应急物流车辆调度问题中对于经济性、时效性、可靠性和鲁棒性的多种要求，考虑了含有时间窗、不确定需求、不确定行驶时间，以及路段含有失效风险的多目标鲁棒车辆路径优化问题，通过定义新的成本函数、满意度函数、风险度函数和鲁棒度函数作为四个优化目标来构建模型，并基于鲁棒优化理论将不确定模型转化为确定性鲁棒对应模型求解，为解决不确定环境下优化问题提供了新的思路。算法方面，主要基于SPEA2算法框架求解该多目标模型，针对算法缺陷提出多种改进策略，并通过对比实验证明了改进策略的有效性。     

基于信息熵调整的自适应蚁群算法

针对基本蚁群算法在求解大规模旅行商问题进易导致搜索时间过长或陷入停滞的问题,提出一种基于信息熵调整的自适应蚁群算法.该算法通过优化过程中种群的信息熵来衡量演化的程度,自适应地调整路径选择策略和信息素更新策略.信息熵的计算以某条路径边上的信息素占总信息素量的比例为基础.对大规模城市数旅行商问题进行实验,实验结果表明,提出的基于信息熵调整的自适应蚁群算法能获得比基本蚁群算法更好的解,并且增加了算法的稳定性.     

基于粒子群算法的满载需求可拆分车辆路径规划

为了更加合理地规划车辆配送路径,尽可能使用最少的车辆数和最短路径长度来完成整个客户点的配送任务,提出一种基于粒子群算法的满载需求可拆分车辆路径(F-SDVRP)规划策略,在配送过程中通过确保任何一辆满载的配送车辆从配送点出发后均以“最优”的配送路径进行配送来达到配送的总路径“最优”要求,并通过粒子群算法不断优化整个客户点的配送顺序.仿真结果表明,在求解相关客户点配送问题时,所提出的车辆规划策略得到的结果优于对比文献中的求解方法,在配送车辆数相同的情况下,最大的路径长度减少率达到8.21%.此外,各算例的仿真结果表明,所提出的策略的寻优结果稳定,粒子群算法可以解决满载需求可拆分车辆路径规划问题.     

带硬时间窗模糊车辆路径问题的多目标优化

针对带硬时间窗车辆路径问题的多重模糊性,基于模糊可信性理论建立多目标模糊期望值模型,提出求解该问题的自适应混合多目标粒子群优化算法.该算法根据相位空间的思想给出一种实数编码方式,设计双存档机制,分别存储演化过程中产生的非支配解和有益不可行解,并引入自适应局部搜索、变异和粒子全局向导选择策略.仿真实验结果表明,与多目标进化算法相比,该算法可以获得更优的Pareto解集.     

基于混合元启发式算法的订单分批问题

订单拣选是仓库运营管理中一项高劳动强度与高成本的操作,拣货员在仓库中从货位拣选出满足订单需求的货物.订单分批问题(order batching problem, OBP)是订单拣选中的重要规划问题,该问题以最小化拣选批次路径时长为目标,将用户订单分配至拣选批次中.首先,为了优化订单分配构造高质量批次,提出一种混合元启发式算法,在自适应大邻域搜索框架中融入基于不可行下降的局部搜索,同时引入自适应惩罚机制和一批基于订单与基于批次的移除启发式以及新的算法组件;其次,为了优化拣选路径进一步降低批次旅行时间,提出单向启发式,利用动态规划优化组合多个路径策略.实验表明,在合理计算时间内,所提出算法的求解质量优于多重启变邻域搜索(MS-VNS)、混合自适应大邻域搜索及禁忌搜索(ALNS/TS),而且所提出算法的最大路径长度减少率达到22.36%.     

一种基于Voronoi图求解车辆路径问题的混合启发式算法

针对由多个配送中心和多个客户点组成的物流网络中的车辆路径问题,提出了一种基于“集群第一,路线第二”的路径优化策略,即首先使用Voronoi分割对配送区域进行划分,然后引入综合插入算法和变邻域搜索算法的混合启发式算法求解配送区域内车辆路径问题。通过算例和应用系统的分析与验证表明,该混合算法既能获取质量较优解,同时也具有较好的实时性,能较好地满足实际应用需求。     

一种多策略混合的粒子群优化算法

针对传统粒子群优化算法在解决一些复杂优化问题时易陷入局部最优且收敛速度较慢的问题,提出一种多策略混合的粒子群优化算法(Hybrid Particle Swarm Optimization with Multiply Strategies,HPSO)。该算法利用反向学习策略产生反向解群,扩大粒子群搜索的范围,增强算法的全局勘探能力;同时,为避免种群陷入局部最优,算法对种群中部分较差的个体实施柯西变异,以产生远离局部极值的个体,而对群体中较好的个体施以差分进化变异,以增强算法的局部开采能力。对这3种策略进行了有机结合以更好地平衡粒子群算法全局勘探和局部开采的能力。将HPSO算法与其他3种知名的粒子群算法在10个标准测试函数上进行了性能比较实验,结果表明HPSO算法在求解精度和收敛速度上具有较显著的优势。     

一种求解车间调度的混合算法

针对流水车间作业调度问题, 提出了一种基于``alldifferent'约束的混合进化算法(Hybrid particle and genetic algorithm, HPGA), 将粒子群算法、遗传操作及模拟退火策略有效地结合在一起. 为了提高算法的求解质量, 引入了一种随机邻域搜索策略. 最后将此算法在不同规模的实例上进行了测试, 并与其他几种最近提出的具有代表性的算法进行了比较. 结果表明, 无论是在求解质量还是收敛速度方面都优于其他几种算法.     

A heuristic particle swarm optimization method for truss structures with discrete variables

A heuristic particle swarm optimizer (HPSO) algorithm for truss structures with discrete variables is presented based on the standard particle swarm optimizer (PSO) and the harmony search (HS) scheme. The HPSO is tested on several truss structures with discrete variables and is compared with the PSO and the particle swarm optimizer with passive congregation (PSOPC), respectively. The results show that the HPSO is able to accelerate the convergence rate effectively and has the fastest convergence rate among these three algorithms. The research shows the proposed HPSO can be effectively used to solve optimization problems for steel structures with discrete variables.     

An effective hybrid PSO-based algorithm for flow shop scheduling with limited buffers

In this paper, an effective hybrid algorithm based on particle swarm optimization (HPSO) is proposed for permutation flow shop scheduling problem (PFSSP) with the limited buffers between consecutive machines to minimize the maximum completion time (i.e., makespan). First, a novel encoding scheme based on random key representation is developed, which converts the continuous position values of particles in PSO to job permutations. Second, an efficient population initialization based on the famous Nawaz–Enscore–Ham (NEH) heuristic is proposed to generate an initial population with certain quality and diversity. Third, a local search strategy based on the generalization of the block elimination properties, named block-based local search, is probabilistically applied to some good particles. Moreover, simulated annealing (SA) with multi-neighborhood guided by an adaptive meta-Lamarckian learning strategy is designed to prevent the premature convergence and concentrate computing effort on promising solutions. Simulation results and comparisons demonstrate the effectiveness of the proposed HPSO. Furthermore, the effects of some parameters are discussed.     

A hierarchical particle swarm optimizer with latin sampling based memetic algorithm for numerical optimization

Memetic algorithms, one type of algorithms inspired by nature, have been successfully applied to solve numerous optimization problems in diverse fields. In this paper, we propose a new memetic computing model, using a hierarchical particle swarm optimizer (HPSO) and latin hypercube sampling (LHS) method. In the bottom layer of hierarchical PSO, several swarms evolve in parallel to avoid being trapped in local optima. The learning strategy for each swarm is the well-known comprehensive learning method with a newly designed mutation operator. After the evolution process accomplished in bottom layer, one particle for each swarm is selected as candidate to construct the swarm in the top layer, which evolves by the same strategy employed in the bottom layer. The local search strategy based on LHS is imposed on particles in the top layer every specified number of generations. The new memetic computing model is extensively evaluated on a suite of 16 numerical optimization functions as well as the cylindricity error evaluation problem. Experimental results show that the proposed algorithm compares favorably with conventional PSO and several variants.     

电力系统经济负荷分配的混合粒子群优化算法

为解决电力系统中的经济负荷分配问题,提出一种将约束优化与粒子群优化算法相结合的混合算法,同时引入直接搜索方法。使得混合后的粒子群优化算法不但具有高效的全局搜索能力,而且具有较强的局部搜索能力,避免陷入局部最优,提高求解精度。对两个实例进行测试,与其他智能算法的结果比较,证明提出的算法可以有效找到可行解,避免陷入局部最优,实现问题的快速求解。     

An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem

Flexible job-shop scheduling problem (FJSP) is an extension of the classical job-shop scheduling problem. Although the traditional optimization algorithms could obtain preferable results in solving the mono-objective FJSP. However, they are very difficult to solve multi-objective FJSP very well. In this paper, a particle swarm optimization (PSO) algorithm and a tabu search (TS) algorithm are combined to solve the multi-objective FJSP with several conflicting and incommensurable objectives. PSO which integrates local search and global search scheme possesses high search efficiency. And, TS is a meta-heuristic which is designed for finding a near optimal solution of combinatorial optimization problems. Through reasonably hybridizing the two optimization algorithms, an effective hybrid approach for the multi-objective FJSP has been proposed. The computational results have proved that the proposed hybrid algorithm is an efficient and effective approach to solve the multi-objective FJSP, especially for the problems on a large scale.     

A Petri net-based particle swarm optimization approach for scheduling deadlock-prone flexible manufacturing systems

This paper proposes an effective hybrid particle swarm optimization (HPSO) algorithm to solve the deadlock-free scheduling problem of flexible manufacturing systems (FMSs) that are characterized with lot sizes, resource capacities, and routing flexibility. Based on the timed Petri net model of FMS, a random-key based solution representation is designed to encode the routing and sequencing information of a schedule into one particle. For the existence of deadlocks, most of the particles cannot be directly decoded to a feasible schedule. Therefore, a deadlock controller is applied in the decoding scheme to amend deadlock-prone schedules into feasible ones. Moreover, two improvement strategies, the particle normalization and the simulated annealing based local search, are designed and incorporated into particle swarm optimization algorithm to enhance the searching ability. The proposed HPSO is tested on a set of FMS examples, showing its superiority over existing algorithms in terms of both solution quality and robustness.     

An improved particle swarm optimization algorithm for flowshop scheduling problem

The flowshop scheduling problem has been widely studied and many techniques have been applied to it, but few algorithms based on particle swarm optimization (PSO) have been proposed to solve it. In this paper, an improved PSO algorithm (IPSO) based on the “alldifferent” constraint is proposed to solve the flow shop scheduling problem with the objective of minimizing makespan. It combines the particle swarm optimization algorithm with genetic operators together effectively. When a particle is going to stagnate, the mutation operator is used to search its neighborhood. The proposed algorithm is tested on different scale benchmarks and compared with the recently proposed efficient algorithms. The results show that the proposed IPSO algorithm is more effective and better than the other compared algorithms. It can be used to solve large scale flow shop scheduling problem effectively.     

简单高效耦合策略的粒子群混合算法

建立了评判耦合策略优劣的定量分析方法,发现了现有带中间启动局部搜索(local search,LS)的粒子群混合算法的不足,进而提出一种简单高效的耦合策略.基于该策略,在全局性能优异的综合学习粒子群(comprehensive learning particle swarm optimizer,CLPSO)算法中引入具有快速收敛性能的传统LS方法,提出了带LS的CLPSO混合算法(CLPSO hybrid algorithm with LS,CLPSO-LS).以10维、30维和50维的11个标准函数,对基于不同LS方法的4种混合算法的性能进行大量测试.结果表明,4种CLPSO-LS混合算法的性能均优于CLPSO算法,验证了混合算法的有效性.其中,基于BFGS拟牛顿方法的混合算法的综合性能最优.最后,与8种先进粒子群算法的对比,结果表明CLPSO-LS混合算法作为一种改进CLPSO算法,其性能优于包括已有CLPSO改进算法在内的对比算法,进一步验证了其优越性.