分形法与范例库推理相结合进化求解旅行商问题

旅行商问题（Traveling Salesman Problem，简称TSP）是一个典型的组合优化问题，而且是一个NP完全问题。遗传算法（Genetic Algorithm，简称GA）是求解组合优化问题的行之有效的算法。但遗传算法并不是一个完美无缺的算法，它最突出的问题是早熟现象。在解决像旅行商这类组合优化中的NP完全问题。是极易陷入早熟收敛，城市规模越大越难求得最优解。如何缓和旅行商问题中的早熟现象。使问题的解尽可能接近最优解．这是本文研究的主要内容。本文在分形法的基础上提出．了一种分形法与范例库推理相结合的改进方法用以求解TSP问题。首先建立范例库，选取其中优良的个体来指导城市规模大的旅行商问题进行合理的区域分割，由于优良个体与最优值的结构大体相同，相似度大，故可以有效地实施“分而治之”的策略。在寻优进化过程中，还要对范例库进行更新与维护。通过对TSPLIB测试库中的eil51、eil101、ch130和ch150问题的求解，说明该方法在求解TSP问题上是行之有效的。     

一种求解旅行商问题的交叉禁忌搜索

提出一种改进的禁忌搜索（TS）一交又禁忌搜索（CTS），并用于混合优化问题旅行商问题（TSP）的求解。CTS主要包括集中策略和分散策略，采用选择规律的改变促进移动的混合，集中策略增强了算法的局部搜索能力；分散策略是用于开辟新的搜索空间，在CTS中，采用遗传算法中的交叉算子作为分散策略，优解选择法作为集中策略。CTS、标准TS、带集中裳略的TS和蚁群算法用于求解相同的TSP例子，所用例子都是来自TSPLIB例子库和Fogel路径。求解结果显示了CTS的性能优于其它算法。     

车辆路径问题的改进遗传算法

通过引入新颖交叉算子 ,构造了一种改进遗传算法 ,此算法摆脱了对群体多样性的要求 ,不存在传统遗传算法常见的“早熟收敛”问题 .将该算法用于解决车辆路径问题 ,实验结果表明 ,此算法可以有效求得车辆路径问题的优化解 ,是求解车辆路径问题的一个较好方案 .     

基于改进遗传算法的物流配送路径优化

物流配送路径规划对于提高物流配送效率、节约配送成本具有重要意义。以物流配送路径总长度为优化目标,将其转换为经典TSP优化问题进行求解并建立了数学模型。基于该数学模型,提出改进的遗传算法,针对遗传算法的选择、交叉和变异分别提出了基于序的选择算子、基于最小代价树的交叉算子和基于随机点长度控制的变异算子。改进的遗传算法与简单遗传算法的对比仿真实验表明,所改进的遗传算法有较好的全局寻优能力,且其收敛速度快,是解决物流配送路径优化问题的有效方法。     

禁忌遗传算法在TSP中的应用

提出了带有禁忌交叉、变异的改进遗传算法,并将其应用于典型的TSP问题的求解.在求解过程中引入禁忌信息减小生成子代的模板空间的同时,加入张驰效应使得在禁忌操作中不丢失问题的最优解,从而改善了遗传算法的收敛速度.仿真数据表明,禁忌遗传算法比传统遗传算法在TSP问题中算法运行初期具备更好下降性,扩展了遗传算法在中、大规模NP-Hard问题快速求解中的应用.     

求解TSP的改进人工鱼群算法

利用遗传算法的交叉算子,并引入去交叉策略,对人工鱼群算法进行了改进,提出了一种改进型人工鱼群算法,并将该算法用于求解旅行商问题(traveling salesman problem,TSP)这一经典的NP难问题。通过实验仿真与目前TSP已知最优解进行对比分析,结果表明,改进后的人工鱼群算法在种群规模较小,迭代次数较少的情况下也可以收敛到已知最优解。     

具有感觉和知觉特征的蚁群算法

针对传统蚁群算法加速收敛与早熟、停滞现象的矛盾，模仿蚂蚁感觉和知觉行为提出一种新的蚁群优化算法，使蚂蚁受显意识和潜意识的相互作用选择路径，同时自适应地修改路径上的信息量，以多种不同规模的对称和不对称旅行商问题(TSP)为例进行的仿真结果表明算法具有较好的收敛速度和稳定性，比较适合求解城市数目较多的TSP问题。     

需求可拆分车辆路径问题的三阶段禁忌算法

需求可拆分车辆路径问题(SDVRP)是一类有待深入研究的车辆路径问题,其求解方法与需求不可拆分的VRP问题有较大的区别.针对该类问题,本文提供了一种新的求解思路——基于双层规划模型的三阶段禁忌算法.首先,将目标函数设定为大TSP路径成本加上切割增加路径成本,构建了SDVRP的双层规划数学模型;然后,根据双层规划的思路设计了三阶段禁忌启发式算法:先求包括车场和所有顾客的大TSP路径,再对大TSP进行切割和拆分,接着对备选方案进行子路径优化;最后,通过实验仿真,将所提出的三阶段禁忌算法与其他算法进行比较,结果表明了所提出的算法可以比较有效地求得需求可拆分车辆路径问题的优化解,是解决需求可拆分车辆路径问题的有效方法.     

多目标0—1规划问题的遗传算法

根据遗传算法的特点，提出了以排列为基础，以求出全部非劣解为目的的定义适应性值的方法，以便使其有能力求解多目标优化问题，并分析研究了算法进行到一定程度以后收敛于一个非劣解的原因和解决策略。     

一种基于子群杂交机制的粒子群算法求解旅行商问题

粒子群算法是在借鉴海鸥群落觅食行为基础上发展起来的仿生学优化算法，为求解复杂的组合优化问题提供了一种新的思路。本文提出一种结合粒子群算法结构和求解TSP问题蚁群算法特点的新算法，将多用于连续空间优化的粒子群成功扩展到TSP领域。算法通过杂交粒子选择机制，运用两种不同设计的杂交算子，成功模拟了自然界同物种不同种群间的协作与交流，将多子群策略和子群问杂交操作引入粒子群结构之中，增强算法的寻优能力。实验结果表明，该算法能有效地保证粒子问多样性差异，通过优化信息在子群间顺畅交流，有效地促进整个群落的进化收敛。该算法在解决TSP问题时．无论在收敛性和鲁棒性方面都优于一般的单群体、非杂交算法。是一种优秀的TSP问题解法。最终优化结果均达到TSPLIB中记录的已知最优解。     

基于蚁群优化算法的0-1背包问题求解

蚁群优化算法在求解旅行商问题、指派问题、Job-shop调度问题和网络路由问题等获得了极大的成功．将蚁群优化算法应用于0—1背包问题，首先将0—1背包问题表示成相应的构造图，并针对该图设计了两个状态转移公式，蚂蚁根据这两个状态转移公式在带权图中移动直到死亡．此时，蚂蚁所走过的路径即构成背包问题的一个可行解．仿真实验对该算法的参数进行了讨论，再与遗传算法进行比较，结果显示该算法具有较高的性能．     

一种基于能量熵的快速遗传算法研究

在分析标准遗传算法的优越性与存在不足的基础上,提出了对遗传算法的改进方法.将能量熵的选择加入到遗传算法的退火选择中,以充分地探索解空间,保持种群的多样性.将伪梯度搜索应用于对个体的邻域搜索,利用当前种群的有效信息及系统信息,提高寻优速度.对典型的TSP问题及一实际电力网络故障恢复的仿真研究表明,改进算法全局优化性能优于启发式遗传算法及标准、退火遗传算法,同时使收敛速度有了较大的提高.     

Improved ant colony optimization algorithm for the traveling salesman problems

Ant colony optimization (ACO) is a new heuristic algorithm which has been proven a successful technique and applied to a number of combinatorial optimization problems.The traveling salesman problem (TSP) is among the most important combinatorial problems.An ACO algorithm based on scout characteristic is proposed for solving the stagnation behavior and premature convergence problem of the basic ACO algorithm on TSP.The main idea is to partition artificial ants into two groups: scout ants and common ants.The common ants work according to the search manner of basic ant colony algorithm,but scout ants have some differences from common ants,they calculate each route's mutation probability of the current optimal solution using path evaluation model and search around the optimal solution according to the mutation probability.Simulation on TSP shows that the improved algorithm has high efficiency and robustness.     

对一类带聚类特征TSP问题的蚁群算法求解

蚁群算法是近几年提出的一种新型的模拟进化算法,初步的研究表明该算法具有极强的鲁棒性和发现较好解的能力,但同时也存在收敛速度慢的缺点。针对带聚类特征的TSP问题,提出了一种新型的蚁群算法。该算法利用TSP问题本身所具有的聚类特征,从数据域上将其分解成多个子问题,对每个子问题分别采用蚁群算法并行求解,最后将所有子问题的解按一定规则合并成问题的解。对带聚类特征TSP问题的仿真实验表明该算法的收敛速度得到了极大的提高。     

基于协同进化的航天测控资源优化调度

航天测控资源调度是一个具有很强工程背景的复杂问题,针对其特点,研究了一种基于协同进化的优化调度算法。在描述问题并给出调度模型的基础上,基于协同进化的思想,设计了和问题特征结合的遗传算法编码,对算法的算子和进化策略进行了描述,给出了算法的完整流程。通过算例表明,该算法整体上优于先到先服务（first coming first serving, FCFS）算法、任务综合优先度（task synthesis priority, TSP）算法和简单遗传算法（simple genetic algorithm, SGA）。     

KMG:考虑逆向物流的无人机路径规划策略研究

物流领域无人机派送正成为一种快捷高效的派件方式和应用热点.针对于正向、逆向的物流数据,无人机派送是国内外大型物流企业实施高效物流派送的重要手段.本文提出了一种融合拓展性K-Means++算法和遗传算法的路径动态规划模型(KMG),实现包含逆向物流的无人机调度策略.KMG模型将逆向物流路径融入正向物流路径之中,采用加权聚类算法确定不同属性包裹所需派送无人机的最小数量.在每一簇坐标数据的连通图中,采用遗传算法求解TSP问题,并对可行解进行编码,最终求解出最小欧拉回路.在仿真实验中,KMG模型比独立逆向物流派送的成本减少20.08%,使用拓展性K-Means++聚类计算的时间比传统K-Means算法缩短了298.85%.     

基于自适应遗传算法的无人机航迹规划方法研究

随着攻防系统的发展与完善,实现飞行器有效突防越来越困难,而采用航迹规划技术能够有效的提高飞行器的突防概率.基于此,首先研究了参考航迹的角度、高度以及航迹段长度等约束条件;其次对航迹编码方式进行了改进,采用全实数的双向链表的编码方式;对自适应遗传算法的交叉和变异概率的计算方法、交叉算子和变异算子进行了改进,并应用该算法在求解航迹规划问题上进行了仿真研究,对采用不同的变异算子所得结果进行了对比分析.仿真计算的结果表明,该算法能够规划出一条满足要求的参考航迹,采用组合变异算子能取得比采用单个变异算子更优的参考航迹.