求解广义最小生成树问题的元启发式算法

针对广义最小生成树问题,设计了2种改进的元启发式算法来求解:单亲遗传模拟退火算法和改进的禁忌搜索算法。通过综合遗传算法和模拟退火算法的优点,提出了单亲遗传和模拟退火的混合算法,并设计了自适应选择法和自适应基因重组操作;在改进的禁忌搜索算法中,通过在2种邻域进行搜索来避免陷入局部最优。数值实验验证了算法的有效性。

最小生成树算法在旅行商问题中的应用

如何在n个顶点之间的1/2(n-1)!巡回路径中选择距离最短的,这是一个典型的组合优化问题,也是解决旅行商问题的根本。在最小生成树的基本思想上进行了改进,成功地解决了旅行商问题。

最小生成树在城市高速公路问题中的应用

本文以最小生成树在城市高速公路问题中的应用为例,利用最小生成树的三种算法的分析和研究,阐明了最小生成树在最优化方面的作用。

度、半径约束最小生成树问题及其算法

提出了度、半径约束最小生成树问题,证明了该问题是NP-完全的.建立了该问题的数学规划模型.进一步给出了快速启发式求解算法,并分析了该算法的时间复杂性.分析和实例实验表明该算法具有良好的效果.

多阶段运输问题及求解运输问题的最小生成树算法

本文从物资供应管理实际问题中抽象出多阶段运输问题,并把它转化为一般的运输问题。采用本文提供的求解运输问题的最小生成树算法求解,极大地节省了内存,提高了运算速度。由于新算法的提出,使得在微机上做较大规模物资供应多阶段最优计划成为可能。

一种新的基于最小生成树的物流配送优化路线算法

提出一种基于树理论算法的物流配送线路优化决策,首先将复杂的道路网转化成最少生成树并建立优化转移策略,开发由最少生成树构造最小生成树的算法,通过对最小生成树进行标记的方法最后得到最优路径,使物流配送的周转总量最小。算法用Jbuilder 9开发,运行表明所提出的算法是有效的,简化以往算法的复杂程度。

基于最小生成树的异构传感器网络抗共谋优化方案

基于EBS(Exclusion Basis Systems)的密钥管理协议,以安全性高、动态性和扩展性好,较适用于异构传感器网络,但却存在共谋问题。该文提出了一种基于MST(Minimum Spanning Tree)的密钥共谋问题优化方案。该方案利用Prim算法对由簇内感知节点所构成的无向连通图进行最小生成树求解,并对该树进行遍历,根据所得节点遍历顺序进行密钥的指派与分配,使得相邻节点间所含的密钥重叠程度增大,发生共谋的可能性得到降低。实验结果表明:同比于密钥随机分配方案与SHELL方案,所提方案有效提高了网络的抗捕获能力。

改进的生成树算法求解旅行商问题

给出了一种基于最小生成树的TSP求解算法,该算法结合贪心算法和匹配算法,把传统近似算法的局部最优转化为全局最优,避免了最邻近算法中最后几步产生的较大的误差.文章最后分析了算法的复杂性,实验数据表明该算法有较高的有效性.

最小度生成树的一种近似算法

最小度生成树问题是一个NP难问题.本文给出了求最小度生成树的一种近似算法,这种算法得到的生成树的度数比最优解至多大1.

关于Steiner树问题

三年前,山于堵丁柱和黄光明两教授关于 Steiner 比猜想的文章发表的消息在纽约时报上刊登,该结果又接连在国内获奖,Steiner 树问题曾引起不少读者的兴趣和关注.但多数人对 Steiner 树的历史和发展了解甚少.本文作者在93年初就打算写篇介绍

扩展Steiner树问题的选址应用研究

提出扩展Steiner树问题的选址模型,给出了该模型基于最小生成树的启发式算法。在此基础上,分析了一个居民点只能与一家连锁店相关联的选址问题,并用算例验证了该选址方案的可行性。

融合均值榜样的反向互学习水母搜索算法

为解决水母搜索算法(jellyfish search algorithm,JS)的洋流运动缺乏多样性、群内运动缺乏引导性、种群间信息无交流,造成搜索速度慢、稳定性差及易早熟的问题,构建了一种融合均值榜样的反向互学习水母搜索算法(oppositional-mutual learning jellyfish search algorithm based on mean-value example,OMLJS).首先在水母跟随洋流运动(全局搜索)部分,利用前两代水母的平均位置代替只考虑上一代水母的平均位置来引导水母个体的位置更新,提高算法的全局搜索能力;其次在水母的群内主动运动(局部搜索)部分,利用最优个体代替随机个体来引导水母进行更有效的搜索,加快算法的收敛速度;然后在水母进入下一次迭代前增加对水母种群进行动态反向互学习步骤,增加种群多样性及增强种群间的信息交流,达到互补另外两个策略,提高算法的整体优化性能.选用12个经典的基准测试优化函数,将OMLJS与5个对比算法从解的平均值、最优值及方差进行对比分析,并用于求解最小生成树问题,OMLJS能够更快地找到最小生成树.实验结果表明,OMLJS的收敛速度、求解精度明显提高.

一种求解多目标最小生成树问题的有效离散粒子群优化算法

提出一种求解多目标最小生成树问题的有效离散粒子群优化算法.为获得更好的非劣前端,设计一个基于目标共享函数的适应度评价函数.引入遗传算法的变异和交叉算子,提高种群多样性并避免算法过早陷入局部最优解.基于种群的随机状态转移过程,理论分析算法的全局收敛性.实验结果表明该算法是有效的,且随着问题规模的扩大算法仍保持较好的性能.

货郎问题求解算法分析

介绍了求解货郎问题的 4个算法 :贪心算法、MST近似算法、MM近似算法和回溯搜索算法。分别使用各个算法对一个货郎问题的具体实例进行求解 ,并对各个算法的性能进行了分析比较。贪心算法的运行速度较快 ,但在大多数情况下该算法找到的是次优解而非最优解。MST和MM近似算法用以求解满足三角不等式的货郎问题 ,其近似性能比(即精确度 )分别为 :RMST(I) <2 ,RMM(I) <3 / 2。回溯搜索算法可以求出货郎问题的最优解 ,但随着城市数目的增加 。

求解TSP问题的一种启发式算法

TSP问题模型应用广泛,其求解策略的研究具有重要的理论和实践意义。根据TSP问题的特点,借鉴无向完全图上最小生成树的生成过程,设计了一种启发式算法对TSP问题进行求解。该算法的基本思想是以无向完全图上不同最小生成树为基础,采用启发式的方法构造不同闭合回路,最后取最短闭合回路作为最优解。文中采用C语言编程,同时分析了算法的性能和时间复杂度,并进行了大量仿真计算。结果表明设计的算法能够有效求得TSP问题的优化解。

基于运行距离最短的车队调度问题图解算法

对于一类基于运行距离最短的车队调度问题,构建了问题的数学规划模型。由于模型难以直接求解,构造网络图对车队问题进行表述。通过求解车队调度网路图的最小生成树,去除最小生成树中车辆和车辆之间连接线,从而将问题分解为一个个单车辆调度问题。对于单车辆调度问题的处理,设计了最小权奇点边添加法。该方法通过构造奇点边集合,使单车辆调度网络图成为所有顶点均为偶点的多重图;进而寻找欧拉环,并删除欧拉环中的重复中间点,最终得到问题的求解方案。最后设计了实例,分别采用图解算法和禁忌搜索算法进行求解。对比发现图解算法在求解车辆调度问题方面具有一定的优越性。

一种基于构建基因库求解TSP问题的遗传算法

在分析了已有的求解TSP问题的优化算法后，提出了一种将建立基因库(Ge)与遗传算法结合起来的新算法(Ge_GA)。该算法的目的是用基因库指导整个种群的进化，其核心问题是基因库的建立及如何将基因库运用到遗传算法中。试验结果表明，基因库有效地提高了群体演化的质量，局部搜索与全局搜索的结合大大提高了算法收敛速度。对于每个测试的实例，其结果与最优解的误差都不超过0.001%。特别是对难于求解的TSP问题，如pcb442和fl1577，都能够在理想的时间内找到最优解。

求解中国邮递员问题的一种思路

对于中国邮递员问题,可以利用奇度数结点的配对来进行求解。本文根据此思想给出了一种新的求解思路——通过去掉原始图中的偶度数结点并利用最小生成树来确定奇度数结点的配对。

多目标优化问题的研究

针对传统方法求解多目标优化问题的局限性,应用一种新的算法求解。遗传算法从问题解的串集开始搜索,覆盖面大,可以同时处理群体中的多个个体,利于全局择优,减少陷入局部最优的风险,而最小生成树具有过程简单清晰、适用性广泛的特点,结合两者的优点,构造了基于生成树的遗传算法。首先通过加权目标规划法求出最优解,然后通过遗传算法和基于生成树的遗传算法求解,结果表明,对于小规模的多目标优化问题,两种算法都可以求出最优解,在求解时间方面,基于生成树的遗传算法比遗传算法更优越。

基于DCMSTP问题的算法综述

DCMSTP(度限制最小生成树问题)是一个NP难问题,具有重要的实际应用价值。对于大规模的DCMSTP问题,至今还没有非常有效的求解方法。为此,本文对讨论了DCMSTP问题的数学模型和求解该问题的精确算法和启发式算法。