基于信息熵的改进蚁群算法求解TSP问题

针对蚁群算法求解精度低、易陷入局部最优的缺点,提出一种基于信息熵的自适应改进蚁群算法。通过算法自身特性定义结合熵值对种群参数进行自适应优化;采用分组合作的信息素更新策略,通过较活跃性个体引导整个种群,扩大搜索范围;通过对较优路径的奖励,平衡收敛速度和搜索范围之间的关系;在种群信息熵过低时,加入局部搜索策略,进一步提高算法精度。实验结果表明,相较于蚁群算法,改进算法具有较好的求解精度以及跳出局部最优的能力。

旅行商问题的一种插入交叉算子

求解TSP问题是遗传算法应用的一个重要领域,其本质是TSP问题中巡回路径编码串的组合最优化问题。对于符号编码方式的遗传算法,通常需要设计特定的交叉算子以提高算法的运行效率和性能。该文针对自然数编码的方式,提出了一种较适合于大规模TSP问题求解的遗传交叉算子:插入交叉(InsertCrossover,简称IX)算子。该算子以优良的交叉策略,保证了算法的快速收敛和全局寻优。仿真实验结果证明,IX算子对于大规模TSP问题具有比较好的性能。

竞争合作型协同进化免疫算法及其在旅行商问题中的应用

为提高人工免疫算法的收敛性能,提出了一种竞争合作型协同进化免疫优势克隆选择算法(CCCICA).把生态学中的协同进化思想引入到人工免疫算法中,考虑了环境和子群间相互竞争的关系,子种群内部通过局部最优免疫优势,克隆扩增,自适应动态高频混合变异等相关算子的操作加快了种群亲和度成熟速度.把信息熵理论引入到算法中完善了种群的多样性.所有子种群共享同一高层优良库,并将其作为抗体子种群领导集合,对高层优良种群进行免疫杂交操作,通过迁移操作把优良个体返回到各子种群,实现了整个种群信息交流与协作.针对旅行商问题(traveling salesman problem,TSP)多个实例结果表明:与其它智能算法相比较该算法具有较好的性能.

求解旅行商问题的离散型贝壳漫步优化算法

提出基于离散型贝壳漫步优化算法(DMWO)的旅行商问题(TSP)求解算法.在DMWO的计算框架下构造TSP相应的评估函数及个体差异度量算子.针对离散型算法整体调整容易破坏已形成的较优路径问题,采用简单的2-opt算子进行局部调整,增强算法在求解TSP时的局部搜索能力.实验中采用多组不同规模的标准TSPLIB数据,对比同样采用2-opt算子的萤火虫优化算法和蚁群优化算法,DMWO在稳定性、解的准确性及所需的迭代次数等方面具有更好的性能.

一种求解旅行商问题的禁忌搜索算法

提出了一种求解旅行商问题的禁忌搜索算法,并对几个实例进行了计算机模拟．实验结果表明,在求解中小规模的旅行商问题上,该算法具有良好的性能．

现实旅行商问题

提出一个新的旅行商问题,称之为现实旅行商问题(RLTSP).它更接近于现实生活中的旅行商问题,并且介于传统的旅行商问题(TSP)与图形旅行商问题(GTSP)之间.还给出现实旅行商问题的不完全计算机数学模型.

求解旅行商问题的一种改进遗传算法

采用三交换启发交叉变参遗传算法来研究典型的组合优化问题—TSP问题,并进行计算机仿真,结果表明,与标准遗传算法相比较,三交换启发交叉变参遗传算法计算量少,收敛速度快,所得解优于标准遗传算法,更接近于最优解.

基于遗传算法的旅行商问题的研究

巡回旅行商问题(TSP)是一个组合优化方面的问题,已经成为测试组合优化新算法的标准问题。应用遗传算法解决TSP问题,首先对访问城市序列进行排列组合的方法编码,这保证了每个城市经过且只经过一次。接着生成初始种群,并计算适应度函数,即计算遍历所有城市的距离。然后用最优保存法确定选择算子,以保证优秀个体直接复制到下一代。采用有序交叉和倒置变异法确定交叉算子和变异算子。最后用MATLAB来实现算法,仿真后,观察路径,得出最终结果。

浅谈旅行商问题与蚁群算法

蚁群算法是继模拟退火算法、遗传算法、禁忌搜索算法、人工神经网络算法等启发式搜索算法之后的又一种应用于组合优化问题的算法。根据蚁群算法的特性,求解旅行商问题,利用仿真实验程序对蚁群求解旅行商问题进行模拟。

求解复杂旅行商问题的混合粒子群算法

针对粒子群算法在解决组合优化时存在早熟和易陷入局部最优的问题,提出一种求解旅行商问题(TSP)的混合粒子群算法。将粒子群算法与遗传算法结合,引入遗传算法中的交叉和变异操作,通过个体极值和群体极值的交叉以及粒子自身变异的方式增加种群的多样性,避免粒子陷入局部最优,提高算法的局部搜索能力。仿真结果表明,新的混合粒子群算法在解决TSP问题时具有较好的收敛性及优化效果。

小窗口蚁群算法解决旅行商问题的应用与分析

本文先介绍基本蚁群算法模型,并应用此法对TSP(旅行商问题)进行了求解。然后运用小窗口蚁群算法解决TSP问题,通过与基本蚁群算法的比较,认为小窗口蚁群算法无论是在解的优化上还是运行时间上都优基本蚁群算法。

求解旅行商问题的自适应升温模拟退火算法

针对传统模拟退火算法在求解问题时容易陷入局部最优解的情况,本文通过设计一种自适应的升温控制因子,提出了一种求解旅行商问题(TSP)的自适应升温模拟退火算法,有效地控制局部寻优达到全局寻优能力,并证明了改进的自适应模拟退火算法收敛性.通过TSPLIB数据库对改进算法全局寻优效果的测试,结果表明改进后的算法具有全局寻优能力、泛化性强等特点:即在TSPLIB提供的绝大部分TSP问题数据中,均能找到全局最优解,且收敛速度快.

改进的人工蜂群算法求解旅行商问题

在利用标准人工蜂群算法求解全局最优解时,研究人员发现存在种群多样性降低、过早收敛、易陷入局部极值等问题。因此,在标准人工蜂群算法的初始化阶段,采用反向学习初始化种群,提高初始解的质量;在跟随蜂阶段,对适应度值不高的个体进行混沌扰动,以增加种群多样性,从而跳出局部极值。利用改进算法和标准人工蜂群算法分别对5个不同的旅行商问题(Traveling Salesman Problem,TSP)进行仿真实验,并对比两种算法的仿真结果。实验结果表明:利用改进的人工蜂群算法求解旅行商问题是可行且有效的;在稳定性方面,改进的人工蜂群算法优于标准人工蜂群算法。

论遗传算法在旅行商问题中的应用

旅行商问题是算法应用中的基本问题,遗传算法具有通用性、智能性、鲁棒性、全局性和并行性的特点,正好适合于该问题的求解。但基本遗传算法在解决旅行商问题时效率不高,并且容易陷于局部最优解。为了解决这一问题,提出了一种改进的遗传算法。文章首先对旅行商问题进行了描述,对遗传算法进行了介绍,对其中的个体选择、交叉算法等重要因素做了一定地改进。最后,用一个简单的实例对基本遗传算法和改进的遗传算法进行了比较,发现改进的遗传算法在解决旅行商问题上的效率问题上有了一定的提高。

基于旅行商问题的智能快递柜服务定价

为给智能快递柜服务合理定价,分析快递柜服务对快递员和不在宅收件人的价值,构建末端配送的旅行商问题模型,提出在不同的快递交件条款和收件人在家不确定性情况下的快递柜服务价值计算方法。基于快递柜服务价值确定收件人和快递员应支付的费用。以某快递员责任范围内的实际配送数据为例,分3种情形计算快递员的配送距离,根据节约的配送成本计算快递柜服务价值,根据受益者负担原则确定收件人和快递员需要支付的快递柜服务价格。当所有收件人都在宅但把全部快件投递入柜时,快递柜按0.274元/单收费;当41%的收件人不在宅但把全部快件投递入柜时,快递柜向快递员和不在宅收件人分别按0.273元/单和1.005元/单收费;当把不在宅收件人的快件投递入柜而在宅收件人的快件投递到户时,快递柜向不在宅收件人按1.077元/单收费。

旅行商问题最小搜索空间研究

TSP问题之所以复杂,一个很重要的方面就是搜索空间中有大量的冗余环路,降低了搜索的效率。通过对普通搜索空间中冗余环路表达出现原因的分析和研究,构造出了新的搜索空间——最小搜索空间(LSS),在最小搜索空间中每个环路的表达形式是唯一的,从而消除了环路表达冗余现象,使搜索得以在只相当于原搜索空间2N分之一(N为节点数目)的空间内进行。然后进一步的对最小搜索空间的构造展开研究,实现了基于问题规模递推的最小搜索空间获得方式,扫清了最小搜索空间的应用障碍。在TSP问题求取最优解的确定性算法中与常用的UniformcostSearch算法进行了对比,效率相应提高了2N倍。

改进的模拟退火和遗传算法求解TSP问题

对遗传算法和模拟退火算法的特点进行了比较,阐述了遗传算法与模拟退火算法集合的必要性。提出了一个用于求解TSP问题的改进的模拟退火和遗传算法。利用遗传算法的全局搜索能力弥补了模拟退火算法容易陷入局部最优的问题。在遗传算法中改进了传统的交叉机制,利用父代染色体与子代染色体进行交叉,解决了传统遗传算法中存在的"早熟"问题。针对模拟退火算法收敛速度慢等问题,提出了新的解生成机制和改良算法,提高了算法的收敛速度。实验测试的结果表明,该方法具有较好的收敛效果和更高的稳定性。

用混合遗传算法求解多目标TSP问题

针对多目标TSP问题,提出了非群体迭代型多目标遗传算法与局部阶段搜索算法相结合的混合遗传算法。其中非群体迭代型多目标遗传算法通过个体的被优越数和种群的分布情况计算个体适应度,采用基于路径表示的编码方法进行编码,使用竞争选择策略、部分匹配交叉和变换变异进行遗传操作。最后使用该算法对两个实例进行实验计算并分析其程序运行结果。结果表明该算法是很有效的。

求解TSP问题的改进混合蛙跳算法

针对TSP问题的特点,设计了一种求解TSP问题的改进的混合蛙跳算法。该算法改进了子种群青蛙个体优化的方式,而不仅是对最坏个体进行优化,这种方式可以有效提高算法的收敛速度。提出了青蛙个体翻转时依赖于全局最优解的"导优"概率和依赖于子种群局部最优解的"导次优"概率,进一步提高了算法寻找最优解的能力。在多个TSPLIB上的实验结果表明,该算法是可行有效的。

求解TSP问题的改进果蝇优化算法

基于求解TSP问题,提出一种改进果蝇优化算法(GFOA),该算法结合TSP问题的特点,把果蝇优化算法的连续空间对应到离散规划,利用轮盘赌法初始化路径,并把遗传算法的交叉、变异操作应用于路径的寻优,同时利用C2Opt算子对局部最优路径进行优化,加快局部搜索能力和收敛速度。通过对13个TSPLIB标准库的TSP算例进行仿真实验,实验结果表明,提出的算法在较小规模算例中能以较少的迭代次数和运行时间快速收敛到已知最优解,在较大规模算例中能接近理论最优解,具有较快的收敛速度和较高的收敛精度。