共查询到20条相似文献,搜索用时 125 毫秒
1.
《计算机应用与软件》2014,(2)
郭涛算法是目前求解TSP(traveling salesman problem)问题最为高效的进化算法之一。算法中提出一种求解TSP旅行商问题的高效Inver-over算子,该算子使基因序列以一定概率进行自适应的序列倒置,同时具有遗传算法中的变异算子以及杂交算子的特性。对Inver-over算子进行改进,使粒子编码得到更加充分的序列倒置;并引入粒子群优化算法的思想以加快算法收敛速度,提高了郭涛算法求解效率。将改进后的郭涛算法应用于钢卷自动优化组合堆垛问题,实验验证了改进郭涛算法的有效性。 相似文献
2.
使用逆转算子求解TSP的演化算法具有很强全局搜索能力,在求解TSP问题中显示了巨大的优势。但是,该算法同样存在执行效率低、最终得到的最优个体整体质量不高等缺陷。在对算法和TSP问题进行分析的基础上,对算法进行三方面的改进:就近选择;动态变异概率;基于较优个体的贪婪搜索。实验结果表明:经过改进的算法提高了执行效率,能够改善算法得到的最优个体的整体质量。 相似文献
3.
使用逆转算子求解TSP的演化算法具有很强全局搜索能力,在求解TSP问题中显示了巨大的优势。但是,该算法同样存在执行效率低、最终得到的最优个体整体质量不高等缺陷。在对算法和TSP问题进行分析的基础上,对算法进行三方面的改进:就近选择;动态变异概率;基于较优个体的贪婪搜索。实验结果表明:经过改进的算法提高了执行效率,能够改善算法得到的最优个体的整体质量。 相似文献
4.
求解TSP问题的一种混合遗传算法 总被引:7,自引:2,他引:7
文章针对TSP问题的特点,设计了一个求解TSP问题的混合遗传算法。该算法中设计了贪婪子路交叉算子,引入2OPT算子增强遗传算法的局部搜索能力,在选择算子设计中引入稳定状态选择机制。通过KroB100、pr136、pr144、kroB150、CHC144…问题的求解结果表明该遗传算法设计在求解TSP问题中是高效的。 相似文献
5.
基于遗传算法求解TSP问题的一种算法 总被引:12,自引:1,他引:12
TSP问题是一个经典的NP难度的组合优化问题,遗传算法是求解TSP问题的有效方法之一。利用交换启发交叉算子实现局部搜索加快算法的收敛速度和利用变换变异算子维持群体的多样性防止算法早熟收敛,给出了一种求解TSP问题的遗传算法。仿真实验结果表明了该算法的有效性和可行性。 相似文献
6.
十进制MIMIC算法是基于MIMIC二进制编码算法思想的可用来求解TSP的离散分布估计算法。着重考虑该算法在较大规模TSP问题上的算法缺陷,对其编码方式和概率模型进行了改进,提出了新的个体生成策略,在初始化种群阶段使用了贪心算法,在进化过程中引入了杂交算子、变异算子、映射算子、优化算子等演化算子,采用了动态调整方法来确定优势群体的规模。以上改进使得算法在小种群解大规模TSP问题的情况下仍可保持种群的多样性。实验结果表明,改进算法在求解规模、求解质量和寻优速度上都有明显提高。 相似文献
7.
旅行商问题的一种插入交叉算子 总被引:4,自引:4,他引:4
求解TSP问题是遗传算法应用的一个重要领域,其本质是TSP问题中巡回路径编码串的组合最优化问题。对于符号编码方式的遗传算法,通常需要设计特定的交叉算子以提高算法的运行效率和性能。该文针对自然数编码的方式,提出了一种较适合于大规模TSP问题求解的遗传交叉算子:插入交叉(InsertCrossover,简称IX)算子。该算子以优良的交叉策略,保证了算法的快速收敛和全局寻优。仿真实验结果证明,IX算子对于大规模TSP问题具有比较好的性能。 相似文献
8.
为了求解TSP问题,提出了一种新的遗传算法。它利用距离密集度和适应度定义了自适应的交叉和变异概率,采用改进的交换启发交叉算子,产生不差于父代的个体。根据最优和次优个体的差异,采用2变换法产生新个体或者进行模拟退火操作,局部搜索加快了算法向最优个体靠近的速度。仿真实验表明新算法是一种求解TSP问题的有效方法。 相似文献
9.
基于遗传算法的求解TSP(Traveling Salesman Problem)研究是近几年的研究热点.设计高效的遗传算法求解,有重要的理论意义和实用价值.本文考察了基于整数编码的遗传算法的选择算子、交叉算子、变异算子,运用选择性集成的思想,将几种算子集成,随进化的进程对交叉概率和变异概率做自适应调整,用Matlab编写遗传算法程序,求解中国31城市TSP问题,获得了优于目前同类工作的结果. 相似文献
10.
11.
针对蚁群算法在旅行商问题(Traveling Salesman Problem,TSP)求解中难以找到最优解、容易早熟的问题,提出一种基于信息熵的多种群博弈蚁群算法。首先,算法采用主从合作博弈机制,引入夏普里公式和信息熵,自适应调整各算子的使用权重,同时构造奖惩算子,提高算法收敛性;然后,对从种群引入针锋相对策略,进行协同学习,提高从种群多样性;进一步,根据帕累托最优原则,对从种群引入协调博弈机制进行自适应合作,提高算法性能。最后,以TSPLIB标准库中的多组TSP问题作为实验算例,进行算法性能分析。实验结果表明,对比传统算法,该算法具有良好的求解精度和求解稳定性。 相似文献
12.
13.
14.
蚁群算法存在对参数的依赖、早熟和停滞等缺点但具有与其他算法容易结合的特点,据此,将差分演化算法应用到蚁群算法的参数选取中,提出一种改进的蚁群算法。将蚁群算法的参数作为差分演化算法解空间的向量元素,在自适应地寻找蚁群算法最优参数组合的同时求解问题的最优解。改进算法对蚁群算法中的参数进行自适应调整,可避免大量盲目的测试,扩大蚁群算法的搜索空间,提高全局搜索能力。在典型的旅行商问题上进行对比实验,结果验证了改进算法的优化性能高于传统的蚁群算法。 相似文献
15.
16.
针对资源受限项目调度问题,提出了一种基于人工蜂群算法的优化方法。人工蜂群算法中每个食物源的位置代表一种项目任务的优先权序列,每个食物源的位置通过扩展串行调度机制转换成可行的调度方案,迭代中由三种人工蜂执行不同的操作来实现全局最优解的更新。实验结果表明,人工蜂群算法是求解资源受限项目调度问题的有效方法,同时扩展调度机制的引入可以加速迭代收敛的进程。 相似文献
17.
针对随机缺陷会降低多项目晶圆实际产出的问题,提出一种新的多项目晶圆布图规划算法。通过在布图规划中引入缺陷率模型的方法,增加芯片产量的裕量,降低因随机缺陷造成的产量损失。同时优化模拟退火流程,使得在布图尺寸约束条件下,布图规划过程能够跳出局部最优解陷阱。对工业实例进行布图规划的结果表明,该算法能够接受不满足布图尺寸约束条件的中间结果,从而遍历解空间,得到全局最优的布图,并且相对已有算法,使用相同数量晶圆进行切割时,算法的布图结果增加了137%的芯片产量的总裕量,同时,降低了25%的工作芯片所需要生产的晶圆数量。 相似文献
18.
针对基本MFO算法存在后期收敛速度较慢、收敛精度低等缺点,提出了一种基于差分进化的改进飞蛾优化算法(DEMFO)。该算法首先将差分进化算法融合到MFO算法中,使得飞蛾种群个体之间具有变异、交叉、选择机制,DEMFO算法拥有更强的全局和局部搜索能力;运用柯西变异算子对飞蛾最优位置进行变异更新产生新解,保持飞蛾种群的多样性,帮助算法跳出局部最优;再引入动态自适应权重因子,使飞蛾的更新方式更具灵活性,引导算法朝着正确的搜索方向进行,从而有效地提高了算法的收敛性和精度;对该算法用8个测试函数进行仿真实验,从实验结果可以看出DEMFO算法在收敛速度和收敛精度上有了显著提高。将该算法成功应用于求解电力系统负荷经济调度(Economic Dispatch,ED)模型,在Matlab平台对140台机组算例进行了仿真,相比基本MFO算法,提出的DEMFO算法能够获得更高质量的优化解,提供更好的负荷经济调度方案,从而有效降低发电成本,产生巨大的经济效益。 相似文献
19.
基于分段混合蛙跳算法的旅行商问题求解 总被引:1,自引:0,他引:1
针对旅行商问题(TSP)在搜索后期解的多样性和精度下降的问题,提出一种解决TSP问题的分段混合蛙跳算法(S-SFLA)。该算法在搜索初期利用逆转变异算子减少交叉路径,在搜索的后期引入邻域搜索(个体邻域,局部最优领域,全局最优邻域)增加种群多样性。在整个搜索过程中记忆全局历史最优解与局部历史最优解,进行全局更新和局部更新,避免迂回搜索。在局部更新中,每一个青蛙都有机会得到更新。实验结果表明,与遗传算法、蚁群算法、基本蛙跳算法相比,S-SFLA算法在求解中等规模的TSP问题上具有更快的搜索速度和更高的求解精度。 相似文献
20.
陈云志 《计算机工程与应用》2014,(7):56-61
为了求解单目标线性规划问题,提出了基于混沌优化(COA)算法的仿射尺度搜索(AFS)算法,即混沌AFS算法。使用混沌优化算法以迭代方式从随机初始点中得到优化的初始点;将得到的初始解点作为仿射尺度搜索算法的起始点来提高仿射尺度搜索算法的性能;通过搜索单目标线性规划决策变量域得到可行的近似最优解。实验结果表明,相比传统的AFS算法,在求解单目标线性优化问题时所提混沌AFS算法明显降低了目标值的偏差,同时大大地减少了迭代次数及CPU运行时间。 相似文献