共查询到18条相似文献,搜索用时 125 毫秒
1.
本文考虑一类特殊的TSP,这种TSP中的城市可被分成若干组.这种将TSP分块处理的方式可降低规模.我们将这种特殊的TSP用0—1整数线性规划来描述,并进一步对其合理性及复杂性进行分析. 相似文献
2.
太原市小店区不同粒径大气颗粒物(PM2.5,PM5,PM10,TSP)浓度变化特征 总被引:2,自引:0,他引:2
对太原市小店区不同粒径的大气颗粒物(PM2.5,PM5,PM10,TSP)进行采集,并对其浓度变化特征进行详细分析,探讨了特殊天气对大气颗粒物浓度的影响.结果表明:在采样期间,不同粒径颗粒物的年平均浓度均超过了国家规定的二级标准,PM2.5,PM5,PM10,TSP随月份、季节的变化趋势基本一致,均为冬季最高,夏季最低.特殊气象条件对颗粒物的浓度影响较大. 相似文献
3.
一种混合遗传模拟退火算法及其应用 总被引:11,自引:0,他引:11
分析了遗传算法和模拟退火算法的优缺点,提出了一种混合遗传模拟退火算法,对其进行优化,并将该算法应用于TSP问题的求解之中,理论分析和实验结果表明了这种混合遗传模拟退火算法优于普通的遗传算法和模拟退火算法. 相似文献
4.
为探索求解大规模TSP(旅行商问题)有效实用方法,提出基于SFC(空间填充曲线)和or-opt混合算法来求解TSP,其中SFC方法能快速且有效地获得初始解,or-opt搜索算法可有效改进初始解。通过中国旅行商问题(CTSP)数据测试,无论是速度还是精度都能满足一定要求,证明这种混合算法能快速有效地解决TSP,并为解决大规模此类问题提供了一种新的思路。 相似文献
5.
宋海洲 《华侨大学学报(自然科学版)》2005,26(3):231-234
给出求解度约束最小生成树(DCMST)问题的一种快速近似算法.在此基础上.又给出求解TSP问题的一种快速近似算法,并在微机上实现且其数值试验的效果良好.最后,将求解TSP问题的近似快速算法作一些改进.应用于遗传算法的初始种群生成并进行数值实验.结果表明,用文中算法生成的初始种群.比起一般方法产生的初始种群性能有很大改进.该算法可以加速遗传算法的寻优速度. 相似文献
6.
求解TSP问题的并集搜索的新宏启发算法 总被引:4,自引:0,他引:4
利用TSP问题解的概率统计模型,分析了TSP问题的局部最优解并集的性质,发现局部最优解的并集规模较小且包含了绝大多数全局最优解的边.利用该性质,将局部最优解并集作为启发集,并调用局部搜索算子在其上求解TSP问题,由此得到一种称为并集搜索的新宏启发算法.利用该算法还改进了目前广泛使用的求解TSP问题的算法ILK、LKH,在TSPLIB中典型实例上的实验结果表明,新算法在解的质量上有了较显著的提高. 相似文献
7.
提出了一种求解TSP问题的近似算法一嵌套插队算法。这种算法结合了启发式算法和随机化算法以及局部寻优的思想。实验结果表明对于较小规模的TSP问题,直接用插队算法(QJA)就能以很大的概率获得巳知最优解。对于规模较大的TSP问题.嵌套插队算法(NQJA)能获得质量高于著名的启发式算法的解。另外,用嵌套插队算法找到的Chinal44的最短路径优于目前巳知的最短路径。嵌套插队算法是专门针对TSP问题而提出的,但其思想也可以给求解其他NP难解的组合优化问题以启发。 相似文献
8.
杨丽华 《曲靖师范学院学报》2009,28(3)
在大规模的TSP求解中,单一的使用蚁群算法会面临优化性能和时间性能这一问题,因此,应先把大规模的TSP按基于距离阈值的近邻聚类分区法划为小规模TSP优化问题来并行求解,再把各子区域中心找一条最佳路径连接起来. 相似文献
9.
分析动态TSP问题的特点,将n-OPT算法和遗传算法结合起来,设计并实现了一种解决动态TSP问题的算法.通过实验,用该算法对TSPLib中经典的TSP问题及其派生的动态TSP问题进行了求解,证明了该算法无论在静态环境还是动态环境中都可行、高效. 相似文献
10.
11.
针对旅行商问题,提出一种结合混沌优化和粒子群算法的新型混沌离散粒子群方法(CIPSO)。新算法根据此类组合优化问题解的固有地形特征,利用混沌运动的遍历性、随机性等特点进行求解,其基本思想是在求解过程中对粒子进行混沌扰动避免陷入局部最优,并引入群体间粒子的交叉作用来提高寻优效率。通过与遗传算法、蚁群算法和模拟退火算法等比较以及不同TSP问题的仿真实验发现,该方法是一种能进行有效优化的新方法。 相似文献
12.
为了探索噬菌体TSP4、栖热菌模式菌株Thermus thermophilus HB27中6种蛋白编码序列和Escherichia coli基因组遗传密码子使用偏嗜性,探索TSP4基因密码子偏嗜性对其基因异源表达的影响本研究利用生物学软件Editseq和RSCU算法统计噬菌体TSP4密码子使用频率并分析其偏嗜性,与栖热菌HB27的同源基因以及常温菌E.coli基因组的密码子使用偏嗜性进行对比分析.结果显示,噬菌体TSP4与栖热菌HB27优势密码子相似度高达85%,而与E.coli的相似性仅有65%.为了验证分析结果,选取TSP4基因组中一个潜在分子伴侣基因序列在E.coli BL21和E.coli Rosetta(补充了BL21菌株中缺失的6个稀有密码子)中进行异源表达.噬菌体TSP4与其宿主菌HB27之间密码子高相似性说明在长期的进化过程中TSP4在基因水平上形成对宿主的一种适应性机制.异源表达结果显示,分子伴侣基因在E.coli BL21中未见明显表达,但在Rosetta中高效表达,说明Rosetta中补充的 6个稀有密码子明显有助于分子伴侣基因的表达,该结果也进一步证明密码子偏嗜性是否一致在很大程度上影响基因的表达. 相似文献
13.
针对粒子群算法直接用于求解离散旅行商优化问题会存在诸多困难,通过分析粒子群算法、遗传算法各自优缺点,将粒子群算法、遗传算法有效结合组成混合算法用于求解离散旅行商问题.混合的目的在于保持两种算法各自的优点,并有效地避免各算法原有的不足.对3个不同规模的巡回旅行商问题进行实验,结果表明:混合算法提升了算法的局部搜索能力. 相似文献
14.
货郎问题求解算法分析 总被引:4,自引:0,他引:4
介绍了求解货郎问题的4个算法:贪心算法、MST近似算法、MM近似算法和回溯搜索算法。分别使用各个算法对一个货郎问题的具体实例进行求解,并对各个算法的性能进行了分析比较。贪心算法的运行速度较快,但在大多数情况下该算法找到的是次优解而非最优解。MST和MM近似算法用以求解满足三角不等式的货郎问题,其近似性能比(即精确度)分别为:RMST(I)<2,RMM(I)<3/2。回溯搜索算法可以求出货郎问题的最优解,随着城市数目的增加,其搜索效率会下降。 相似文献
15.
粒子群优化算法求解旅行商问题 总被引:92,自引:2,他引:90
首先介绍粒子群优化的搜索策略与基本算法, 然后通过引入交换子和交换序的概念, 构造一种特殊的粒子群优化算法, 并用于求解旅行商问题. 实验表明了在求解组合优化问题中的有效性. 相似文献
16.
在旅行商问题(TSP)的传统模型中,子回路消除约束的数量随着问题规模的增大具有指数增长的特性,极大地限制了TSP的求解效率。基于TSP的松弛问题,本文提出一种有效生成子回路消除约束的方法。该方法通过求解一系列线性整数规划,来实现TSP的精确快速求解。数值结果表明,本方法相比于采用Cplex直接求解,能够更快地找到TSP的最优解。 相似文献
17.
典型城市大气颗粒物无机组分源解析 总被引:1,自引:0,他引:1
采用CMB 8.2受体模型对吉林省4个典型城市大气总悬浮颗粒物(TSP)进行了无机组分源解析研究.共选取了10个采样点,在采暖期和非采暖期采集了环境空气中的总悬浮颗粒物及各类污染源样品156个.研究结果表明,吉林市和白城市对TSP影响较大的是土壤风沙尘;通化市大气主要污染源为道路尘;而四平市的扬尘对TSP的影响较大.研究结果有利于制定大气污染防治规划,对于治理大气环境、改善空气质量具有指导意义. 相似文献
18.
以遗传算法求解旅行商问题(TSP)为例,提出一种改进的交叉和变异算子,深入讨论了各个遗传算子的程序实现,并给出其算子的MATLAB程序编码,最后用5个城市的非对称TSP进行仿真分析.结果表明,改进的算法比传统算法收敛速度更快,适应值更优,说明改进算法是有效的,证实TSP问题是遗传算法得以成功应用的典型例子. 相似文献