旅行商问题的遗传算法

旅行商问题属于ＮＰ问题，现在还没有找到有效的解法。本文应用遗传算法对解决此类问题的有效性作了探讨。文中对遗传算子的应用，编码，参数选择及其对收敛的影响等问题作了分析与探讨。     

基于仿真的遗传算法求解动态旅行商问题

以标准旅行商问题的扩展问题--动态旅行商问题为对象,分析了动态旅行商问题中由于道路流量实时变化所引起的标准旅行商问题的数学建模与优化求解的问题复杂性.通过建立其计算机仿真模型再现动态旅行商问题中众多复杂的非平稳、随机因子.进而提出了基于计算机仿真模型的遗传算法,即根据计算机仿真的结果,应用改造后的遗传算法搜索原问题的优化解.最后,在多智能体仿真平台上实现该优化算法,并以此求解20个城市的动态旅行商问题,计算结果验证了算法的有效性.     

混合递阶遗传算法优化小波神经网络的研究

在研究小波神经网络结构及其学习算法的基础上,提出了一种以混合递阶遗传算法优化小波神经网络的新方法,混合递阶遗传算法是递阶遗传算法和多元线性回归的结合。此方法可同时优化小波神经网络的结构及其参数,具有学习速度快,精度高的特点。并与传统的BP算法进行了对比,证明了本算法的有效性。     

一类多旅行商问题的计算及仿真分析

旅行售货商问题(TSP)是组合优化领域的经典问题之一,而考虑多个旅行商的多旅行商问题(MTSP)是经典的旅行商问题的扩展.多旅行商问题的特点使其符合许多实际问题,并且通过对多旅行商问题加入约束条件可以使其转化为车辆选择问题(VRPs).针对一类特殊的MTSP问题采用Lin-Kernighan算法进行求解分析,并在此基础之上针对访问城市数目均衡的多旅行商问题采用两阶段方法进行求解,计算仿真结果是令人满意的.     

解旅行商问题的一个新的遗传算法

对旅行商(TSP)问题设计了一个新的遗传算法.首先,对n个城市的旅行商问题设计了一个新的编码方法,并且对这种编码方法,给出了简便的解码方法.其次,针对编码的特点,设计了一种新的、有效的杂交算子和变异算子,这些算子均能直接产生可行的后代.为提高杂交算子的搜索能力,结合了一个局部搜索技术来改进杂交算子.在此基础上,提出了求解TSP的一个新的遗传算法,并证明了其全局收敛性.为了验证算法的有效性,对10个国际标准算例(城市规模从14到1000)进行了计算机仿真,结果表明算法是有效的.     

基于差分进化算法的多旅行商问题优化

针对所有旅行商路径最大值最小的多旅行商问题,提出改进的差分进化算法优化.在该优化方法中,编码采用实数编码;改进的差分进化算法采用轮盘赌选择;根据旅行商问题的特点,在差分进化算法中增加邻域搜索算子.该方法适于距离对称和非对称的多旅行商问题求解.以距离非对称的多旅行商问题的实例进行了仿真和比较,可以看出所提出的改进差分用来解决多旅行商这类离散组合优化问题是有效的.     

遗传算法求解旅行商问题时的基因片段保序

针对基于遗传算法的 TSP问题求解 ,尝试了多种遗传操作 ,分析了这些操作在遗传算法中的作用 ,讨论了基因片段保序在利用遗传算法求解 TSP问题中的重要性 .     

基于偏好信息的多目标旅行商问题Pareto优化求解

多目标旅行商问题(MOTSP)是经典旅行商问题的扩展,其优化目标包含了距离、成本、收益及风险等多个相互冲突的指标.本文提出了一种基于偏好的Pareto演化算法p-PEA用于建模并求解此NP-hard问题.该优化算法建立在MOTSP的智能体仿真模型之上,从而解决了数学建模不能真实再现实际MOTSP中众多影响因素的问题.通过仿真的方法,算法能够得到MOTSP可行解的各项评价指标值.在此基础士,通过设计演化算法搜索问题的Pareto优化解集.其中,将决策者的决策偏好信息引入到Pareto优化解集的求解过程中,所得结果将更合理.最后,以一个130个城市的旅行商问题为例验证了算法的有效性.     

基于改进递阶遗传算法的RBF神经网络分类器

针对通信信号调制类型识别,应用递阶遗传算法动态确定径向基神经网络分类器结构。建立了新的适应度函数,该函数简单直观,待定参数少;同时结合相关联赛选择方法对选择算子进行了改进,增加了种群进化的多样性,避免了早熟收敛。仿真结果表明改进算法能更好地确定分类器结构,分类准确率更高。     

基于Hopfield网络学习的多城市旅行商问题的解法

针对Hopfield神经网络(HNN) 学习算法难以求解大规模组合优化问题的不足，提出了基于HNN学习的多城市旅行商问题的示解算法。它是把HNN学习算法作基本算子，对城市群体按一定的规则进行有效的分割、计算攻连接，来寻找巡回路径的最优解或满意解。并以100城市的旅行商问题为例进行了仿真实验，骓证了算法的有效性。该算法不受求解问题的规模限制；还可通过并列运算实现高速化；同时因自满法简明，易于硬件实现。     

具有服务时长的在线TSP问题

针对城市快递揽件服务过程中,需求事先无法预知并且每个需求服务时长不确定的情形,提出具有服务时长的在线TSP问题.分别在一般网络图上和直线上证明了此问题的竞争比下界进而在一般网络上给出PAH-ST算法,在直线上给出PQR-ST算法,并对算法进行了竞争性能分析.本文提出模型是在线TSP问题的一般形式,结论可以为快递车辆的实时调度决策提供依据.     

求解TSP问题的最近邻域与插入混合算法

研究了求解旅行商问题(TSP)的构建型启发式算法中的最近邻域算法和插入算法的特点, 集最近邻域算法求解速度快、插入算法求解质量高的优点, 提出了一种最近邻域与插入混合算法. 分析了混合算法的合理性、复杂度及参数取值, 并分别采用以上三种算法求解了TSPLIB标准库中多个算例, 结果表明混合算法的求解速度接近最近邻域算法, 对城市数量小于1000的小规模TSP问题的求解质量与插入算法相当, 而对大规模TSP问题的求解质量明显优于插入算法.     

Improved ant colony optimization algorithm for the traveling salesman problems

Ant colony optimization (ACO) is a new heuristic algorithm which has been proven a successful technique and applied to a number of combinatorial optimization problems.The traveling salesman problem (TSP) is among the most important combinatorial problems.An ACO algorithm based on scout characteristic is proposed for solving the stagnation behavior and premature convergence problem of the basic ACO algorithm on TSP.The main idea is to partition artificial ants into two groups: scout ants and common ants.The common ants work according to the search manner of basic ant colony algorithm,but scout ants have some differences from common ants,they calculate each route's mutation probability of the current optimal solution using path evaluation model and search around the optimal solution according to the mutation probability.Simulation on TSP shows that the improved algorithm has high efficiency and robustness.     

基于预知信息和实时服务选择的在线TSP问题

现实生活中,提供外送服务的快餐店为了降低成本、提高效率,在接到顾客的订餐信息时,可能会因为距离等因素拒绝一些顾客的送餐要求,而拒绝顾客需求会带来一定的惩罚(如丧失部分客户).针对快餐店选择性提供送餐服务,同时送餐点信息被提前获知但是不能马上被服务的情形,提出了基于预知信息和实时服务选择的在线旅行商问题(traveling salesman problem,TSP).针对需求点在正半轴和直线上的情形分析了问题的下界,并设计了相应的算法,同时分析了每个算法的竞争性能.结果表明,算法的竞争性能会随着预知信息的增加而得到改善.     

基于信息素异步更新的蚁群算法

针对基本蚁群算法中蚂蚁速度无限且信息素同步更新的假定前提,提出一种基于信息素异步更新的改进蚁群算法。该算法以蚂蚁的速度有限为前提,采用异步更新规则来调整各个蚂蚁的信息素浓度,从而间接改变蚂蚁间合作方式。该算法更忠实于实际蚁群的寻路过程,算法具有更好的全局搜索能力。基于旅行商问题的实验验证了算法的有效性、鲁棒性及解的多样性。     

时变网络环境下旅行商问题研究

对时变旅行商问题进行描述,提出处理一般跨时段的新方法,并建立数学模型.在求解方法上构造动态搜索优化算法ds-k-opt(k=2,2.5,3)求解该问题.通过实验仿真,大部分动态搜索优化算法解质量优于动态规划启发式算法,且求解规模更大.动态搜索优化算法解随k值增大而更优,算法运行时间也随之增加.     

一种基于免疫遗传算法的认知决策引擎

为改善认知无线电的自适应参数调整功能,设计了一种基于免疫遗传算法的认知决策引擎。运用免疫遗传算法对无线电系统待优化的目标函数进行寻优,针对一种多载波系统对算法性能进行了仿真分析。结果表明,该认知无线电决策引擎在爬山能力、收敛精度和算法稳定度等方面要优于基于标准遗传算法和模拟退火遗传算法的决策引擎。