下载  >  开发技术  >  其它  > 论文研究-求解TSP问题的一种改进蚁群算法 .pdf

论文研究-求解TSP问题的一种改进蚁群算法 .pdf 评分

求解TSP问题的一种改进蚁群算法,王峰峰 ,王仁明,TSP问题是典型的NP-hard组合优化问题,用蚁群算法求解此问题存在搜索时间长,容易陷入局部最优解的不足。本文提出了一种改进的蚁群��
中国科技论又在线 http:/www.paper.edu.cn 另外,本文采用蚁周模型进行信息素更新,即周中只有最短路径的蚂蚁才进行信息素 修改增加,而所有路径的轨迹更新方程均采用 z(+1)=p×x()∑△r() (24) 其中()为路径(i)在t时刻的信息素轨迹强度;△r()为蚂蚁k在路径(ij)上留下的 单位长度轨迹信息索薮量;ρ表示轨迹的持久性,0≤ρ<1,将(1-尸)理解为轨迹衰减度。 改进算法的流程图如图2.1所示。 问题 初姹化多数,根据优化屏A 定义目标函数动适应值 m只蚂置于个节点 随机生成一组完勤编码 1|计签母三思函下二节 的每三蚂蚁到下一苄点 限据适立区选择、Y 递归选代 进行交又计算 m蚂蚁遍以r个点之 后,最忧蚂蚁毒进行信 息素曾 根据适应值野数进行 逆特变异 友路空信息素更新 生成若干组最优铎 出最好解 图2.1改进蚁群算法流程图 2.2算法设计步骤 以卜为该算法的主要步骤 SIP1:利用遗传产生一个较优解,在这个路径留下信息素,令nc←0nc为迭代步数或 搜索次数),将m只蚂蚁置于n个顶点上 STFP2:将各蚂蚁的初始出发点置于当前解集中,对每只蚂蚁k(k=1,2,,m),按概率p 移至下个顶点j,将顶点j置于当前解集,完成‘次遍历 STEP3:根据交叉概率,选择若干组解,然后分组进行交叉的解,若新的目标函数交好, 接受新值,否则就拒绝。根据变异概率,判断是否变异,变异后的目标函数变好,接受新值; 否则就拒绝 STEP4计算各蚂蚁的路径长度(k-1,2,…,mn),记录当前的最好解,对路径长度小 于给定值的路径,按更新方程(2.3)修改轨迹强度; STEP5nc←ncl; STFP6:若nc<预定的迭代次数且无退化行为(即找到的都是相冋解)则转STFP1 STEP7:输出目前最好解。 中国科技论又在线 http:/www.paper.edu.cn 基于改进蚁群算法的旅行商问题求解 为了检验算法的有效性和优越性,分别将蚁群算法和改进算法用于30个城市TSP问题 进行仿真实验。其中,蚁群算法参数选为:α=1.5,β=2,卩=0.9,而将各路径信息素初值 z设为60。遗传算法的染色体个数、交叉概率和变异概率分别为30,0.2,0.5。基于本文 算法和基本蚁群算法的仿真结果如表1。 表1实验仿真结果 算法名称 β 最短路径长度进化代数 基本蚁群算法 1.5 0.9 442.8617 339 改进蚁群算法 1.5 0.9 429.4154 40 从表3.1可以看出,在相同的参数下,本文的优化算法不仅在进化代数上大大减少,而 且得到了更好的最优解。图1和图2分别为改进算法和蚁群算法在20次仿真中得到的最好 的解,其中利用本文算法得到的最短路径为4294154,而利用蚁群算法得到最好的解为 442.8617。 4050 图1改进算法随机迭代求得的最好结果(20次测试)图2蚁群算法随机迭代求得的最好结果(20次测试) 结论 本文利用蚁群算法和遗传算法特性,提出的算法吸收了两种算法的优点,采用遗传算法 生成信息素分布,利用蚁群算法求解凊確解。并将蚁群算法和夲文算法用到求解TSP中 分析和对比其仿真结果,可以看岀,本文算法无论是在求解性能还是时间性能方面都取得了 更好的结果,从而实现了对TSP问题的优化,为解决一些组合优化问题提供了一定的参考。 中国科技论文在线 http:/www.paper.edu.cn 参考文献 「II吴进波,熊盛武,徐宁温度可控的求舷TSP问题的模拟退火算法[J.计算机应用研究,2007、5) 21 Goldberg DE. Genetic algorithms in search, optimization and machine learning. MA: Addison-Wesley, Reading, 1989 [3] Jin HD, Leung ks, Wong ML, Xu ZB. An efficient self-organizing map designed by genetic algorithms for the traveling salesman problem. IEEE Trans Syst Man Cyber Part-B 2003: 33(6): 877-87 [4丁建立,陈増强,袁著祇.遗传算法与蚂蚁算法的融合J计算机硏究与发展,2003、09 l5]姜昌华,胡幼化.一种求解旅行商冋题的高效混合遗传算法山计算机「程与应用,2004;40(22):67-70 [6] Dorigo M, Birattari M, Stutzle T. Ant colony optimization: artificial ants as computational intelligence technique. IEEE Comput Intell Mag; 2006. p. 28-38 [门]叶志伟、郑肇葆.蚁群算法中参数α、β、ρ设置的研究—以TSP问题为例[J.武汊大学学报(信息科学 版),2004,07) Wang Fengfeng, Wang Renming, Wu Jia College of Electrical and New Energy, Three Gorges University Yichang(433002) TSP is a classical NP-hard combinatorial optimization. Some drawbacks such as long time searching and fall into local optimal solution are shown with ant colony algorithm is used for solving this problem As a result, this paper presents an optimized algorithm for solving TSP. The proposed algorithm combines the ant colony algorithm and genetic algorithm, which uses Ga to generate the distribution of pheromone. In addition, in the Ant colony algorithm, wc use the crossover and mutation strategics to improvc the quality of Tsp solution. Thc simulation result shows that the improved algorithm optimizes the tsp in time and performance Ant colony algorithm; Genetic Algorithm; TSP optimization 第一作者简介:工峰峰(1986),男,河南焦作人,峡大学电气与新能源学,在读研究生,主 要研究方向为智能控制。 第二作者简介:王仁明(1964),男,湖北仙桃人,三峡大学电气与新能源学院,博士,教授,主 要研究方向为切换系统,模糊控制。 第三作者简介:伍佳(1986),女,湖北洪淛人,三峡大学电气与新能源学院,在读枥究生,主要 研究方向为计算机控制、电力电子。

...展开详情
所需积分/C币:6 上传时间:2019-08-16 资源大小:789KB
举报 举报 收藏 收藏
分享 分享
论文研究-参数不确定的广义T-S模糊系统的最优保成本控制.pdf

论文研究-参数不确定的广义T-S模糊系统的最优保成本控制.pdf,  研究参数不确定的广义T-S模糊系统的最优保成本控制问题.对给定系统所容许的所有不确定参数,设计了状态反馈最优保成本控制器,使得闭环系统不仅渐近稳定而且具有最小性能指标上界.基于LMI处理方法,给出了该控制器存在的充分条件.通过矩阵分解把广义系统的非严格矩阵不等式约束转化为严格矩阵不等式,从而可以像正常系统那样使用LMI工具

立即下载
论文研究-基于实时信息的动态应急资源调度模型.pdf

为利用实时的道路信息、救援状态信息和应急资源配置信息,以提高应急响应能力,建立了一个动态的应急资源优化调度数学模型。针对任意时刻的静态应急资源调度模型,利用遗传算法进行求解。考虑算法的实时性,通过变换时间变量t进行迭代计算,提出模型的动态求解算法。通过一实例对模型的算法进行了验证分析,结果证明了动态应急资源调度模型及其求解算法的有效性。

立即下载
论文研究-控制理论在最优广告策略上的应用(Ⅱ).pdf

论文研究-控制理论在最优广告策略上的应用(Ⅱ).pdf,  本文考虑的是一个企业如何通过控制广告费用,以使企业的净收入最大的问题.本文以t时刻的广告费用作为控制变且,以t时刻的商誉值作为状态变量,建立了系统的动态模型,给出了目标泛函J.在求解最优控制的过程中,利用了最小二乘法进行函数拟合;利用黄金分割法求解衰减系数δ,在此基础上,利用极大值原理求出了最优控制,并给出了一具体应用实例.

立即下载
论文研究-改进的求解线性方程组的并行Arnoldi方法 .pdf

构造了一类新的模糊系统并应用它对非线性系统进行了辨识,而对新的模糊系统的性能作必要的分析研究。针对该系统进行分析,并将其与T-S模糊系统作比较,得出相关结论。

立即下载
论文研究-基于迭代变邻域下降算法求解TTRP问题.pdf

论文研究-基于迭代变邻域下降算法求解TTRP问题.pdf,  为了求解卡车带挂车的车辆路径问题(truck and trailer routing problem,TTRP),提出迭代变邻域下降算法(iterated variable neighborhood descent,IVND).该算法首先使用T-cluster算法求得一个初始可行解.然后,设计了基于多邻域算子的变邻域下降搜索算法.

立即下载
论文研究-基于.pdf

为了完善三角多项式样条的算法,基于空间span{1,sin t,cos t,sin2t}构造了三次代数三角Gβ样条曲线(三次AT-Gβ样条曲线),包括曲线的构造,几何连续的条件、求解等,推出AT-Gβ样条曲线的性质以及研究形状参数β1和β2对曲线的影响等,还通过曲线反推控制顶点,研究三次插值AT-Gβ样条。这种三次AT-Gβ样条曲线具有良好的局部性质和广泛的应用。

立即下载
论文研究-生命表理论与方法.pdf

论文研究-生命表理论与方法.pdf,  本文给出了寿命分布的极大似然估计, 从而给出了现时人口寿命各参数的严格的概率意义, 并利用1990年人口普查10%抽样数据, 求得中国人口寿命表和简略寿命表。

立即下载
论文研究-修理设备可更换的.pdf

论文研究-修理设备可更换的.pdf,  本文把“修理设备可发生故障”引入到N-策略M/G/1可修排队系统中,考虑了 修理设备可更换的N-策略M/G/1可修排队系统.通过引进服务台的“广义修理时间”、顾客的“广义服务时间”和修理设备的“广义忙期”,讨论了系统的排队指标和服务台的可靠性指标.同时,使用全概率分解方法,利用拉普拉斯变换工具,重点讨论了修理设备的不可用 度和在(0,t]时间内的平均更

立即下载
论文研究-球面l1-正则化逼近模型及其应用研究.pdf

基于不同的正则化算子的选取,建立了一类球面上带[l1]-正则项最小二乘逼近模型。通过选取好条件的球面[t]-设计点作为采样点,展示了求解此逼近问题的算法。最后,通过数值例子展现了满意的逼近效果—精确数据和噪声污染的情形。

立即下载
论文研究-带分段仓储能力决策的动态批量优化问题研究.pdf

论文研究-带分段仓储能力决策的动态批量优化问题研究.pdf,  本文考虑一个单一产品仓储能力决策和库存决策的动态批量集成优化问题.在这个模型中,长度为T个周期的计划期被划分成连续的若干段,每段初需制定该段的仓储能力决策,同一段中各期的期末库存水平均受限于该段仓储能力.假设每段仓储能力费用为仓储能力的非减函数,各期的产品订货费用为固定费用,库存保管费用是一个期末库存量的线性函数.利用分解技术和

立即下载
论文研究-基于禁忌搜索的人工蜂群算法.pdf

针对人工蜂群算法(Artificial Bee Colony,ABC)邻域搜索能力不强且容易陷入局部最优的不足,引入禁忌搜索的思想,提出了基于禁忌搜索的人工蜂群算法(TS_ABC)。TS_ABC算法在ABC算法的基础上加入两个禁忌表,分别记为禁忌表T1和禁忌表T2。禁忌表T1的长度是有限的,存储蜜蜂访问过的当前解;禁忌表T2的长度是无限的,存储优化[limit]次后没有改进的解。蜜蜂在蜜源位置搜索新解时要跳过禁忌表里的解,这样避免了重复搜索,增强了邻域搜索能力,克服了容易陷入局部最优。15个标准函数上实验结果表明:(1)TS_ABC的性能优于ABC算法;(2)在求解多峰函数最优解时,TS_AB

立即下载
论文研究-基于暗原色的单一图像去雾算法的研究.pdf

暗通道优先算法在处理单幅户外图像去雾方面有较好的效果,但是该算法处理的时间过长,算法速度较慢。在暗原色优先算法的基础上,提出了改进的方案,即使用指导性滤波代替暗原色优先中的软抠图算法,并增加盒子滤波以提高指导性滤波的处理速度。同时为提高图像的输出质量,采用了分块处理方法,使用3×3模板求解图像的暗原色,得到了更好的透过率t值。实验表明,该算法在提高速度的同时优化了图像输出效果,图像更加自然、真实。

立即下载
论文研究-双种群差分进化规划算法.pdf

标准差分进化算法(SDE)具有算法简单,控制参数少,易于实现等优点。但在难优化问题中,算法存在收敛速度较慢和容易早熟等缺陷。为克服此缺点,提出一种改进算法——双种群差分进化规划算法(BGDEP)。该算法将种群划分为两个子群独立进化,分别采用DE/rand/1/bin和DE/best/2/bin版本生成变异个体。每隔δt(取5~10)代,将两个子群合并为一个种群,再应用混沌重组算子将之划分为两个子群,以实现子群间的信息交流。在双种群协同差分进化的同时,应用非均匀变异算子对其最优个体执行进化规划操作,使得算法具有较快的收敛速度和较强的全局寻优能力。为测试BGDEP的性能,给出了4个30维bench

立即下载
论文研究-多核学习中基于复合梯度映射的学习算法研究.pdf

现有的多核学习算法大多假设训练样本分类完全正确,将其应用到受扰分类样本上时,由于分类存在差错,因此往往只能实现次优性能。为了解决这一问题,首先将受扰分类多核学习问题建模为随机规划问题,并得到一种极小极大表达式;然后提出基于复合梯度映射的一阶学习算法对问题进行求解。理论分析表明,该算法的收敛速度为O(1/T),大大快于传统算法的收敛速度O(1/T)。最后,基于五个UCI数据集的实验结果也验证了本文观点和优化算法的有效性。

立即下载
论文研究-噪声图像的快速二维Otsu阈值分割.pdf

为了提高二维阈值分割法处理速度, 提出了二维Otsu法的快速实现方法。基于二维随机变量的边缘概率分布, 将二维最佳阈值(s*, t*)的求解拆分成两个一维最佳阈值s*和t*的求解; 同时为了改善原算法的分割效果, 引入类内方差的定义, 提出了新的最佳阈值判别式。实验结果表明, 本方法不仅保留了原二维阈值法抗噪性强的特点, 其时间复杂度由O(L4)降为O(L), 空间复杂度由S(L2)降为S(L), 且分割错误率低于原二维Otsu法。该方法适合处理高斯噪声图像的快速阈值分割问题。

立即下载
论文研究-时滞Hopfield神经网络的随机稳定性分析.pdf

T-S模型提供了一种通过模糊集和模糊推理将复杂的非线性系统表示为线性子模型的方法。研究了时滞Hopfield神经网络的随机稳定性(SFVDHNNs)。首先描述了SFVDHNNs模型,然后用Lyapunov方法研究了SFVDHNNs全局均方指数稳定性,通过可以被一些标准的数值分析方法求解的线性矩阵不等式(LMIs)得出了稳定性标准。

立即下载
论文研究-商空间理论在产量预测中的应用.pdf

商空间理论是研究不同粒度世界的一种新的数学工具。它用三元组(X,f,T) 描述一个问题,其中X 表示问题的论域,f(.) 是论域属性,T 是论域的结构。通过分析求解问题(X,f,T) ,对论域X 及其有关的结构、属性进行深入分析和研究,从而完成不同粒度世界的描述,并有着完整的理论基础。该文主要描述了商空间粒度的构建和计算并应用于农作物产量的预测,通过实验取得了很好的确定结果。

立即下载
论文研究-一类离散非线性时延系统的滑模变结构控制研究.pdf

针对时变时滞的离散非线性系统, 利用Takagi-Sugeno模糊模型对其进行线性逼近, 将系统在滑模面上渐近稳定的时滞相关稳定性条件转换为线性矩阵不等式(LMI)的求解问题。由于证明中引入了松弛矩阵变量, 因而所得结果具有较小的保守性。进而采用变速趋近率方法得到滑模变结构控制律。最后, 对具有时变时延的小车—拖车自动倒车系统, 运用T-S模糊模型建模, 实现了小车—拖车系统的自动倒车控制。仿真结果验证了控制器的有效性。

立即下载
论文研究-基于多目标冲突度网格任务调度策略.pdf

针对网格计算中多目标之间存在冲突的独立任务调度问题,应用多目标线性规划为系统建模,通过求解多目标线性规划的梯度向量来确定多目标之间的冲突度,形成多目标冲突度网格独立任务调度模型。提出该模型预处理算法和多目标冲突度遗传算法,这两个算法确保网格用户在多目标维度下的效用值最大化。实验结果表明,在时间、安全性、可靠性维度和丢弃任务数等指标方面,该算法的综合性能优于Max-min和T-Sufferage算法。

立即下载
论文研究-改进AFSA算法优化SVM的变压器故障诊断.pdf

提出一种基于改进人工鱼群算法优化支持向量机(SVM)的变压器故障诊断方法。首先对基本人工鱼群算法进行改进,引入柯西变异优化觅食行为,并在算法的迭代过程中利用鱼群搜索到的信息和[t]分布变异的特点,对劣质个体鱼进行消亡与重生,提高鱼群算法的寻优效率和求解精度。然后,利用改进的人工鱼群算法优化SVM的核函数参数及惩罚系数,使SVM分类器获得最佳的分类精度。最后采用决策导向无环图(DDAG)方法建立变压器故障诊断SVM多分类决策模型。通过仿真实验将提出的方法与网格搜索法Grid-SVM、GA-SVM、PSO-SVM比较,所建模型具有更高的诊断正确率。

立即下载