基于协同进化的多目标约束进化算法

针对约束多目标优化算法(COA:Constrained Optimization Algorithms)中存在的难以有效兼顾收敛性和多样性的问题,提出了采用协同进化策略的多目标优化算法(CoMaC)。首先,将一个COA转化为一个带动态约束处理的多目标进化算法。然后采用差分进化(DE:Differential Evolution)生成第1种群,并将其中的已知可行解选入第2种群,并与第1种群协同进化。第1种群通过保持原约束条件的全局搜索加快收敛。第2种群通过局部搜索进化,保持并获得更多可行解。最后采用标准约束多目标测试函数进行实验,以测试所提出算法的性能。实验结果表明,与使用惩罚函数处理约束问题(PF:Penalty Function)和使用动态处理约束边界方法(DCMaOP:Dynamic Constrained Many Objective optimization Problem)相比,所提算法在反向世代距离(IGD:Inverted Generational Distance)和超体积(HV:Hypervolume)两个指标上均取得了良好的结果,说明所提算法可以有效地兼顾收敛性和多...     

加强的混合遗传算法求解能力约束弧路径问题

为了在可接受的时间里求解具有NP-hard性质的能力约束弧路径问题(CARP),提出了加强的混合遗传算法(EHGA). 该算法是在遗传算法框架里嵌入加强的局域搜索算子来强化搜索,充分发挥了遗传算法的全局搜索能力和加强的局域搜索算子的局域搜索能力. 同时,在进行种群替代时,二元锦标赛替代被提出,并使用了种群管理来保持种群的多样性.测试了标准CARP算例,并给出了算法效果比较. 结果表明,加强的混合遗传算法胜出一般的Memetic算法,是有效的求解CARP的方法.     

多约束最优路径算法比较研究

针对多弧权网络路径寻优及其效率问题,提出了4种多约束最优路径算法,并对其进行了比较研究.基于经典Dijkstra算法,提出了多约束最优路径问题的D_MCOP算法;引入启发式搜索思想,设计了A*_MCOP算法和迭代加深搜索的IDA*_MCOP算法;为克服IDA* _MCOP算法每次迭代都要回到起始节点重新搜索的缺陷,提出了一种多约束边沿搜索算法——Fringe_MCOP算法.实例研究表明:三种启发式搜索算法扩展的节点数、边数以及算法的执行时间都远小于D_MCOP算法,而且Fringe_MCOP算法在三种启发式算法中性能最优;当给定的约束条件与最优路径的权值向量越接近时,算法的执行效率越高,当网络规模较大时,这一趋势更加明显;当约束条件过于严格而得不到满足约束条件的路径时,A*_MCOP和Fringe_MCOP的算法速度比IDA*_MCOP的算法速度更快,D_MCOP的算法速度最慢.     

有容量约束车辆路径问题的蒙特卡洛模拟算法

带容量约束的车辆路径问题是一个NP-hard问题,针对此问题将蒙特卡洛模拟方法与流行的节省算法结合,提出Flag-MCS-CWS算法,该方法通过对CWS算法得到的节省序列进行蒙特卡洛模拟,适用于不同节点数、不同车辆载重量的车辆路径问题.在标准数据集测试,相比当前最优解有平均0.75%的改进,为车辆路径问题提供了更加有效的解决方案.     

差分进化算法在多目标路径规划中的应用

针对差分进化算法其算法思想简明、实现方便而得到了国际进化计算研究领域的认可,多目标问题中,由于各目标之间经常是相互制约的,因此优化难度相当大。带时间窗的多目标物流配送车辆路径优化的多约束性使得它很难应用进化算法进行优化。为了解决这个问题,本文通过变异操作算子改进,成功将改进的差分进化算法应用于该问题。数值仿真实验结果表明:这种改进的差分进化算法得到了较稳定的非支配解集,实现了客户间的路径优化。     

基于免疫拉马克的道路洒水车路径问题优化

高效节能地完成道路洒水作业对改善城市环境、节约资源有着非常重要的意义.将道路洒水车路径问题转化为带容量约束的弧路径优化问题,并建立相应的数学模型.根据问题的NP难特性,提出了一种拉马克免疫算法进行求解.算法有效利用了免疫算法全局优化和拉马克学习局部搜索的优势;设计了适合问题求解的锦标赛选择法、顺序交叉法、自适应变异等免疫算子,并设计了拉马克局部搜索策略,避免算法陷入局部最优.实验结果表明,所提算法能得到代价最小的洒水路径.     

自适应混合蚁群算法求解带容量约束车辆路径问题

针对带容量约束车辆路径问题(capacitated vehicle routing problem, CVRP),提出了一种自适应混合蚁群算法.由蚁群算法生成子回路,为增强跳出局部最优能力,在蚁群算法的状态转移规则和信息素更新规则中引入了自适应机制.基于子回路组合,由遗传算法构造近似解,根据问题编码特性设计了适应度函数和遗传算子,提高了构造效率,并采用Clark和Wright节约算法将近似解修复成可行解.采用扫描法和2-opt局部优化方法提高可行解的质量.标准算例的实验结果表明,该算法在求解CVRP问题上具有良好的寻优精度和寻优效率.灵敏度分析结果表明蚂蚁数量对算法性能具有显著影响.     

带有异质固定车队的能力约束弧路径问题

研究了带有异质固定车队的能力约束弧路径问题(CARP).为了在可接受时间里求得较理想的解,提出了基于Route-First, Cluster-Second思想的两阶段启发式算法,并使用局域搜索(LS)和加强的局域搜索(ELS)进行改善. 基于标准CARP算例生成了 HFFCARP测试数据,算法结果表明了LS和ELS的有效性,且ELS具有更好的效果.     

一类针对带约束优化问题的进化规划算法

提出了一种适用于求解带约束优化问题的进化规划方法,其中关键的变异算子采用基于行为的架构,事先设计一系列子变异算子,如使得个体适应度函数值趋向最小方向的变异算子、逃避约束方向的变异算子、种群总体平均适应度函数值趋向最小方向的变异算子等,通过加权平均的方法决定总变异方向．结合小生境技术及最优个体保存的选择策略,该算法能在同时保证种群的多样性和个体的全局最优性的情况下快速地求得带约束条件下的最优解．仿真结果表明,该进化规划算法是可行的．     

多种进化算法混合解决约束工程优化问题研究

针对单一进化算法不适合解决所有优化问题的情况,提出了一种混合多种进化算法解决约束工程优化问题的算法.该算法混合了差分进化、粒子群优化和共生生物搜索等3种算法,首先利用差分进化算法产生和选择最优种群,然后利用粒子群优化算法寻找每一个最优解并进行更新,最后利用共生生物搜索算法对所有种群进行共生互动更新,选择出最优种群以进行...     

云自适应遗传算法有能力约束的车辆调度优化

针对与车辆调度成本密切相关的运输量和车辆利用率,建立油耗费用和固定费用最小的车辆调度模型.根据车辆调度问题实时性和复杂性的要求,提出云模型理论与遗传算法相结合的云自适应遗传算法,利用云模型云滴的随机性和稳定倾向性改进标准遗传算法中固定设置交叉和变异概率的方式,克服了标准遗传算法搜索速度慢及易早熟的缺陷,设计基于最大保留机制的交叉和变异算子,提高了算法的收敛性和鲁棒性.最后,结合算例对模型和算法的有效性进行验证.     

求解QoS路由优化的一种新进化算法

对网络中支持多个QoS参数路由的数学模型进行了形式化分析,提出了一种多目标进化算法（QMOEA）。该算法能有效地将多个优化目标统一起来,并在此基础之上引入“自适应退避”机制与贪心策略,保证了群体的多样性和快速收敛。仿真结果与理论分析验证了该算法的有效性与正确性。     

车辆路径问题(VRP)的一个启发式算法

提出了一个基于分区扫描方法和禁忌算法的车辆路径问题的启发式算法,并用一个例子说明其应用.     

求解车辆路径问题的改进遗传算法

在建立车辆路径问题数学模型的基础上,设计了求解该问题的改进遗传算法,即采用自然数编码,构造一定长度的遗传个体表,动态记录适应度以及引入新交叉算子。实验结果表明,该算法用于求解车辆路径问题,不但可以解决传统遗传算法在求解该问题所遇到的“早熟收敛”,而且大大提高算法的运行效率。     

新型遗传算法求解车辆路径问题研究

建立有时间窗车辆路径问题的数学模型,针对遗传算法在局部搜索能力方面的不足,提出将模拟退火算法与遗传算法相结合,从而构造有时问窗车辆路径问题的混合遗传算法,并进行实验计算.结果表明,用混合遗传算法求解该优化问题,可以在一定程度上克服遗传算法在局部搜索能力方面的不足和模拟退火算法在全局搜索能力方面的不足,从而得到质量较高的解.     

开放的车辆路线安排问题的模型与遗传算法

本文主要针对开放的车辆路线安排问题,建立了以车流为基础的数学模型。在模型中利用罚函数法来化简约束条件,并设计了基于自然数编码的遗传算法。最后给出一个简单的算例来说明该模型及算法的应用。     

Ant Colony Algorithm for Solving QoS Routing Problem

Based on the state transition rule, the localupdating rule and the global updating rule of ant colony algorithm, we propose an improved ant colony algorithm of the least cost quality of service (QoS) unicast routing. The algorithm is used for solving the routing problem with delay, delay jitter, bandwidth, and packet loss-constrained. In the simulation, about 52.33% ants find the successful QoS routing , and converge to the best. It is proved that the algorithm is efficient and effective.     

车辆路径问题的改进遗传算法研究

在现有的物流管理系统中,车辆路径问题(vehi-cle routing problem,VRP)研究在物流配送过程中的作用显得尤为重要.VRD最早是在1959年由Dan-ting和Ramser[1]提出,其研究的问题可以描述为:有n个商品需求点(可以称之为顾客),各个顾客之间的距离以及商品需求量事先已知,要求从中心仓     

一种求解QoS路由问题的半定规划算法

QoS路由的主要问题是求源节点到目的节点满足QoS多个约束的优化问题。由于半定规划在求解组合优化问题和NP-完全问题时具有收敛速度快,迭代步数少等优点。本文基于QoS路由问题的线性整数规划网络模型,利用半定规划方法研究了时延约束的代价最小问题。把QoS路由的一般模型松弛为半定规划的标准形式,利用半定规划内点方法进行求解,然后利用随机扰动方法得到原问题的近似最优解.数值试验表明了算法的有效性。