【摘 要】
：
组合优化是一类常见的最优化问题,特点是变量的取值是离散的.该类问题广泛应用于人工智能、机器学习、软件工程及生产管理等领域.旅行商问题(Traveling Salesman Problem,TSP
论文部分内容阅读
组合优化是一类常见的最优化问题,特点是变量的取值是离散的.该类问题广泛应用于人工智能、机器学习、软件工程及生产管理等领域.旅行商问题(Traveling Salesman Problem,TSP)和背包问题(Knapsack Problem,KP)都是典型的NP-难组合优化问题,流窜犯问题(Traveling Thief Problem,TTP)是这两类问题的复合模型.在TTP问题中,由于两类子问题间相互影响,使TTP问题的求解变得更有挑战性.另外,多目标旅行商问题(Multi-objective Traveling Salesman Problem,MOTSP)是在经典旅行商问题中考虑多个优化目标的类型,是单目标旅行商问题的拓展和延伸,其求解结果能为决策者提供更多的选择方案.本文在不确定信息下给出了TTP问题的一个新模型,并基于问题的信息设计了求解TTP问题和双目标TSP问题的遗传算法.1.TTP问题是旅行商问题和背包问题的一个复合问题,同时具有两个问题的计算复杂度.本文在现有TTP问题模型中考虑了小偷提前不知道物品具体位置的情况,给出了新的具有概率分布信息的优化模型;利用有效价值指标,给出了物品的选取方法;基于一个TSP的遗传算法框架和新设计的局部搜索策略,提出了求解该模型的混合遗传算法.数值仿真结果表明,提出的算法是可行有效的.2.针对行走路程最短和旅程费用最小的双目标TSP问题,首先考虑了边的距离权值和费用权值对路径选择的影响,定义了两个满意度.第一个满意度对每个路径的边进行“粗”筛选,第二个满意度对边进行“细”筛选;其次,通过两个满意度确定个体产生的方法;最后基于遗传算法框架给出了一个结合2-opt选择策略的复合遗传算法.仿真实验验证了算法的有效性.
其他文献
粉彩是康熙晚期在创烧五彩的基础上，受珐琅彩工艺的影响，由景德镇制瓷工匠创制的新品种。烧成温度比五彩低，色彩柔和淡雅，故又名“软彩”。清末寂园叟《陶雅》曰“软彩者，粉彩也。彩之有粉者，红为淡红，绿为淡绿，故曰软也。惟蓝、黄亦然。”歙县博物馆藏有部分粉彩瓷，现择其部分予以介绍，以飨读者。 清粉彩戏曲人物像（图1），一个高23.5厘米。此人物头戴官帽，身穿长袍，衣服补子为双鹤，脚蹬长靴，浓眉大眼，双手
该文对[-1,1]上的非光滑函数|x|的逼近问题进行了探讨,通过构造一系列具有不同分布特点的节点集,讨论它们对|x|插值时有理函数r(x)对|x|的逼近度,研究梳理‖|x|-r(x)‖收敛性
本文分两部分.第一部分,通过纽结与环链Jones多项式的导数性质,重点讨论了代数分离环链,特别是几何分离环链上的多项式不变量,且对于几何分离环链,更加严格地给出了的Ohtsuki
随着云存储的不断发展，云存储安全问题逐渐显现，一个完美的数据完整性检测协议可以有效的提高云存储的安全性，而且一个可靠地问责机制能够提高云平台的可信度。本文研究高效的数
语文学习进入初中阶段,学生间的学习成绩开始逐渐拉大,有些学生对于学习语文状态越来越好,学得高效而轻松,但是现实中仍然存在一部分学生,对于语文学习很苦恼,一直摸不着门路
该文给出Lawson和丘成桐的一个著名定理的证明.该定理断言任何紧流型如果具有一个紧、连通、非交换李群的有效作用,则必具有一个数量曲率为正的黎曼度量.该文首先给出Lawson
全文共分四章.第一章研究二阶椭圆型方程的高精度有限体积元方法及双调和方程的混合有限体积元方法.第二章考虑发展方程的有限体积元方法及其交替方向求解技术.第三章对对流
该文研究了数学物理中两类典型的具有耗散性的无穷维动力系统的渐近性理论.在第二章中,运用带权空间构造一类紧算子和算子分解的方法,研究了无界区域R上的KDV型方程,得到了该
Divide-and-Conquer方法是80年代提出并逐步发展起来求对称三角矩阵特征值和特征向量的方法.该文的"求对称三对角矩阵特征值的迭代解法"是在Divide-and-Conquer方法产生的(se
线性算子对赋范线性空间中函数逼近正逆定理的研究是逼近论中重要的研究课题之一,在理论和实际应用上都具有重要的意义.该文利用点态光滑模ω(f,t)来研究某些线性算子及逆中