基于仿真的遗传算法求解动态旅行商问题

以标准旅行商问题的扩展问题--动态旅行商问题为对象,分析了动态旅行商问题中由于道路流量实时变化所引起的标准旅行商问题的数学建模与优化求解的问题复杂性.通过建立其计算机仿真模型再现动态旅行商问题中众多复杂的非平稳、随机因子.进而提出了基于计算机仿真模型的遗传算法,即根据计算机仿真的结果,应用改造后的遗传算法搜索原问题的优化解.最后,在多智能体仿真平台上实现该优化算法,并以此求解20个城市的动态旅行商问题,计算结果验证了算法的有效性.     

旅行商问题的遗传算法

旅行商问题属于ＮＰ问题，现在还没有找到有效的解法。本文应用遗传算法对解决此类问题的有效性作了探讨。文中对遗传算子的应用，编码，参数选择及其对收敛的影响等问题作了分析与探讨。     

解旅行商问题的一个新的遗传算法

对旅行商(TSP)问题设计了一个新的遗传算法.首先,对n个城市的旅行商问题设计了一个新的编码方法,并且对这种编码方法,给出了简便的解码方法.其次,针对编码的特点,设计了一种新的、有效的杂交算子和变异算子,这些算子均能直接产生可行的后代.为提高杂交算子的搜索能力,结合了一个局部搜索技术来改进杂交算子.在此基础上,提出了求解TSP的一个新的遗传算法,并证明了其全局收敛性.为了验证算法的有效性,对10个国际标准算例(城市规模从14到1000)进行了计算机仿真,结果表明算法是有效的.     

基因重组算法设计及多目标旅行商问题求解

遗传算法等启发式算法在求解旅行商问题时,存在收敛速度较慢、容易出现过早收敛及算法计算效率较低的问题。在模式理论基础上,提出一种新的基因重组算法。根据优良基因模式,设计模式重组算子,运用重构及进化规划的思想设计算法的个体重构算子和个体选择算子。建立一个多目标旅行商问题模型,分析每一轮计算旅行路线适应度值的差异性,采用熵值法确定路程和费用权重。系列实验表明,基因重组算法在求解多目标旅行商问题时,计算效率远高于比较的算法,收敛速度和求解精度也较一般启发式算法有明显改善。     

遗传算法求解旅行推销员问题时算子的设计与选择

主要讨论了在用遗传算法求解ＴＳＰ时,在算子的设计和选择方面应该注意的一些问题,并且给出了一些算子的分析和设计实例。     

基于递阶遗传算法的一类多旅行商问题优化

针对最小化单个旅行商路程的多旅行商问题,提出了一种递阶遗传算法和矩阵解码方法。该算法根据问题的特点,采用一种递阶编码方案,此编码与多旅行商问题一一对应。用递阶遗传算法优化多旅行商问题不需设计专门的遗传算子,操作简单,并且解码方法适于求解距离对称和距离非对称的多旅行商问题。计算结果表明,递阶遗传算法是有效的,能适用于优化多旅行商问题。     

自调节种群的演化算法求解旅行商问题

提出了一种自调节种群的演化算法(SaPEA)求解旅行商问题,算法根据当前最优适应度改进的情况提出一种更精细调节种群规模的模式,并根据演化的进程选择强化操作或者分化操作.这样不仅有利于保持种群的多样性开发新的解,还可以加快收敛速度探索到更好的解.同时,还对现有的启发式交叉算子和3-opt局部搜索算法进行了改进.通过对TSPLIB中实例进行测试,表明了SaPEA算法的优越性.     

求解配送＼收集旅行商问题的模拟退火算法

配送＼收集旅行商问题(TSPD)是一类重要的组合优化问题,与车辆路径问题等有着密切的联系.但与传统的旅行商问题(TSP)相比,人们对该问题的研究有限,而且大多假定必须在完成所有的配送需求后,才服务收集需求.文中放松这一约束条件,在扩展Metropolis接受准则的基础上,运用模拟退火算法求得该问题较好的结果.     

一类多旅行商问题的计算及仿真分析

旅行售货商问题(TSP)是组合优化领域的经典问题之一,而考虑多个旅行商的多旅行商问题(MTSP)是经典的旅行商问题的扩展.多旅行商问题的特点使其符合许多实际问题,并且通过对多旅行商问题加入约束条件可以使其转化为车辆选择问题(VRPs).针对一类特殊的MTSP问题采用Lin-Kernighan算法进行求解分析,并在此基础之上针对访问城市数目均衡的多旅行商问题采用两阶段方法进行求解,计算仿真结果是令人满意的.     

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

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

货郎担问题的人工智能──人机交换解法

针对大规模问题提出,利用人工智能,通过人机交换,逐步选择较优路径,再将选择的多个较优路径进行比较,寻求最优路径．通过许多算例以及和同样算例（CHN144）以往结果的比较,本法不仅省时、省力,且获得了更优的结果,说明本法的可行性和有效性.     

解旅行商问题的混沌蚁群算法

利用混沌运动的遍历性、随机性和规律性等特点,提出了一种求解旅行商问题的混沌蚁群(CACO)算法.该算法的思想是采用混沌初始化进行改善个体质量和利用混沌扰动避免搜索过程陷入局部极值.与模拟退火算法、标准遗传算法进行比较,仿真结果表明该方法是一种简单有效的算法.     

求解作业车间调度问题的改进自适应遗传算法

根据当前代种群中的最优个体应该保留,但也要一定交叉与变异概率的思想,提出了改进的自适应遗传算法,开发了工程应用软件包,应用于求解作业车间调度问题,显著提高了收敛速度.特别是在搜索过程中系统能够自动给定交叉概率和变异概率,符合工程实际需要.     

基于Hopfield网络学习的多城市旅行商问题的解法

针对Hopfield神经网络(HNN) 学习算法难以求解大规模组合优化问题的不足，提出了基于HNN学习的多城市旅行商问题的示解算法。它是把HNN学习算法作基本算子，对城市群体按一定的规则进行有效的分割、计算攻连接，来寻找巡回路径的最优解或满意解。并以100城市的旅行商问题为例进行了仿真实验，骓证了算法的有效性。该算法不受求解问题的规模限制；还可通过并列运算实现高速化；同时因自满法简明，易于硬件实现。     

一种求解TSP的生物信息启发式遗传算法

遗传算法是解决旅行商问题（traveling salesman problem,TSP）的通用路径优化算法之一。为解决传统遗传算法收敛速度慢且解不稳定的问题,提出一种生物信息启发式遗传算法（bioinformation heuristic genetic algorithm,BHGA）。通过优化适应度函数和初始种群,引入生物信息学中的基因序列对比手法进行交叉重组排序,采用基因逆转操作进行变异,对遗传算法进行改进,使算法能够加快收敛速度,得到更优路径解。利用BHGA对TSPLIB数据库中算例进行求解,实验仿真结果表明：该算法在中小型规模的TSP中求解效果好且结果稳定。     

基于基因权重动态调整遗传算法的编码

针对标准遗传算法中交叉算子容易破坏定义长度较长的优良模式的弱点，提出了一种动态排序编码方法，以提高交叉算子的效率。首先对当前代种群确定基因权重，然后根据基因权重对基因位置进行动态排序，使优良基因变得集中，从而克服了标准遗传算法中交叉算子的弱点。为了避免陷入局部最优，对变异算子进行了改进。最后做了大量实验，并根据实验结果对该方法进行了评述。