人工神经网络求解TSP问题新方法

本文在分析Hopfield/Tank方法的基础上提出一种新的人工神经网络方法,采用优化约束条件的能量函数,具有收敛速度快、不易陷入无效解、易获得亚优解等优点。     

基于函数变换的求解SAT问题的新算法

提出了一种基于函数变换的求解SAT问题的新算法,这个新算法利用SAT问题自身的特点将判定问题转化为连续函数的求极值问题。随机选取一组初始值,利用最速下降法求解变换后的连续函数在每个初始值邻域内所能达到的局部极值,如果这个局部极值为0,则该SAT问题就是可满足的。实验结果表明：与现有的求解SAT问题的算法相比,基于函数变换的求解算法在求解速度、成功率和求解问题的规模等方面都有明显的提高。     

基于变换函数与填充函数的模糊粒子群优化算法

本文提出了一种基于变换函数与填充函数的模糊粒子群优化算法（Fuzzy partical swarm optimization based on filled function and transformation function,FPSO-TF）.以基于不同隶属度函数的多回路模糊控制系统为基础,进一步结合变换函数与填充函数,使该算法减少了陷入局部最优的可能,又可以跳出局部极小值点至更小的点,快速高效地搜索到全局最优解.最后采用基准函数对此算法进行测试,并与几种不同类型的改进算法进行对比分析,验证了此算法的有效性与优越性.     

求无约束优化问题的无参数填充函数法

填充函数作为求解优化问题的有效方法之一,以填充函数的基本思想为基础,构造了新的无参数填充函数,该函数形式简单,便于计算。分析了该函数的相关性质并设计了相应的算法,最后通过数值实验,结果表明提出的算法是可行的、有效的。     

基于最优保留的CGA及其在TSP欺骗问题中的应用

本文在对CGA算法分析说明的基础上,运用改进CGA的方法来解决TSP欺骗问题。虽然CGA能够“快速、简单”的解决一些优化问题,但是由于其概率向量中基因的独立性,使得它在进化计算中会丢失基因之间的关联信息,从而可能无法解决如欺骗函数等复杂、困难问题。文中通过对CGA在TSP算法上的改进,以一定遗传尺度保留竞争最优个体,从而有效地解决TSP欺骗问题,并通过仿真结果验证了该算法,给出解决该类组合优化问题的一个有效例证。     

基于精确罚函数的神经网络优化方法求解TSP问题

利用精确罚函数方法结合神经网络来求解最优化问题,重点求解的是组合优化问题的TSP经典问题,重点讲述的是Hopfield神经网络基于精确罚函数求解组合优化问题TSP,在用Hopfield神经网络求解TSP问题时,人工神经网络的初始态对应着无约束优化问题的初始解,人工神经网络系统的稳态对应着无约束问题的优化解。在求解TSP问题中是利用能量函数来构造的。当人工神经网络系统达到稳定状态时的一个极小点也就是TSP问题的最优解。     

一种基于迭代局部搜索的和声搜索算法

为了改进原始和声搜索算法的全局搜索性能,提出了基于迭代局部搜索的和声搜索算法.该算法在充分利用和声记忆库中信息和提高搜索效率的同时,对于不满足停止准则的新和声采用基于改进kick策略移动的迭代局部搜索算法进行寻优,从而使新算法具有较强的"爬山"能力.针对4个benchmark函数对新算法做了测试,并与粒子群优化算法以及已有的几个算法进行了比较,结果表明该算法跳出局部极值点的能力较强、收敛速度更快、寻优精度较高;最后将新算法应用到焊接梁的优化设计问题中,仿真结果验证了该算法在求解焊接梁最小造价问题时优于原始的和声搜索算法、遗传算法等方法.     

基于连续Hopfield网络求解TSP的新方法

当连续Hopfield网络及其能量函数同时具有自反馈或不具有自反馈时,称之为一致连续Hopfield网络．在分析了一致连续Hopfield网络能量稳定性的基础上,进一步研究了当网络有自反馈,而其能量函数无自反馈的情况下,网络能量变化的性质,分别给出了使能量函数上升、下降和不变的条件．利用这一理论,可以克服由于梯度下降法所导致的网络能量函数总是下降,从而使网络陷入局部极小值或不可行解的现象．最后在这个理论的基础上我们给出了一种新的求解TSP(traveling salesman problem)的方法,仿真研究表明此方法对于求解TSP问题是很有效的．     

一类新的寻求全局最优解的填充函数

填充函数法是一种求解多变量、多极值函数全局最优化的有效方法,该方法最早由葛入溥在文献[1]中提出,这种方法的关键是构造填充函数.文中在无Lipschitz连续条件下,考虑用单参数填充函数求解无约束全局优化问题,给出了一类新的形式简单的单参数填充函数.容易证明该填充函数在参数充分小时就能保持其填充性质.根据这个填充函数还提出了一个求解无约束优化问题的填充函数算法,通过一些检验函数的数值运算结果验证了算法的可行性和有效性.     

一种基于构建基因库求解TSP问题的遗传算法

传统的遗传算法通常被认为是自适应的随机搜索算法．该文在分析其特点后针对TSP问题提出了一种将建立基因库(Ge)与遗传算法结合起来的新算法(Ge-GA)．该算法利用基因库指导种群的进化方向，并在此基础上使用全局搜索算子和局部搜索算子增强遗传算法的“探测”和“开发”能力．Ge-GA算法大大加快了遗传算法的收敛速度和寻优能力．作者测试了TSPLIB中的多个实例(城市数目从70～1577)，试验结果与最优解的误差都不超过0．001％．特别是对于难求解的TSP问题，如att532和fl1577，都能够在理想的时间内找到最优解．     

TSP问题的一种改进的GRASP算法

本文对Marinakis等提出的扩展邻域GRASP算法进行改进。首先使用最近α值方法构造初始TSP回路,然后运用混合的局部搜索即2-opt算法、双桥策略和3-opt算法来改进初始回路,并且引进α-nearness候选集和don’t-lookbit技术来提高搜索速度。实验结果表明,本文提出的GRASP能够在合理的时间内得到很好的解,并且解的质量优于M~rinakis等提出的扩展邻域GRASP算法得到的解。     

一种求解TSP问题的改进禁忌搜索算法

禁忌搜索算法作为一种新兴的智能搜索算法,已被广泛应用于各类优化问题。本文综合解向量的分量变化和目标值变化,提出一种新的候选解和当前解选择策略,并用改进的新算法求解TSP问题。实验表明新的算法具有良好的性能。     

一种求解旅行商问题的新型单亲遗传算法

论文针对旅行商问题,提出了一种新型的单亲遗传算法。它在同一条染色体上采用基因换位、基因段移位、基因段逆转和基因分组定界等操作进行基因重组,取消了传统遗传算法中的交叉算子,遗传操作简单,收敛速度快。但过早的收敛将影响结果精度,使全局最优解的出现机率很小。为此,该算法模拟自然界演化的周期性,使用基因插入操作增强算法的搜索能力,并提出运算终止的两个准则,使所得的解为全局最优解的可信度大为提高。给出了该算法的数值算例,实验结果表明,该算法较好地解决了收敛速度和寻优能力的矛盾,证明了该算法的有效性。     

混合算法求解着色瓶颈旅行商问题

基于着色旅行商问题(colored traveling salesman problem, CTSP),给出了一种适用性更加宽泛的组合优化问题模型：着色瓶颈旅行商问题(colored bottleneck traveling salesman problem, CBTSP).CBTSP可建模含有部分重合工作区域的规划问题,譬如有合作任务和单独任务的人员与车辆的路线规划,此类问题由于目标函数与旅行商问题不一样,因此不能够用CTSP模型来建模.由于CBTSP属于NP难问题,对于规模大的此类问题,自然启发式算法是个合适的选择.基于此,提出了一种自然启发式算法求解CBTSP,该算法是基于伊藤过程的粒子群算法(particle swarm optimization, PSO)、模拟退火算法(simulated annealing, SA)和遗传算法(genetic algorithm, GA)的混合算法(PSGA).PSGA首先用二重染色体编码来构建问题的解,然后运用遗传算法的交叉操作进行更新,其中交叉长度由伊藤过程的活动强度来控制,而活动强度由粒子半径和环境温度来决定.为了充分验证算法的有效性,使用小尺度到大尺度不同规模的数据进行实验,通过广泛的实验与分析表明:PSGA求解CBTSP问题的求解质量要优于对比算法.     

求解旅行商问题的混合蚂蚁算法

旅行商问题是一个经典的NP问题,文中给出了一个有效的求解旅行商问题的混合蚂蚁算法。算法设计了初始信息素量设置方案和信息素的更新方法,限制了蚂蚁转移的目标城市数,并使用2-Opt方法对路径进行优化。数据实验表明,该算法是有效的。     

应用LK算法求解旅行商问题的混合蚂蚁算法

目前求解TSP问题效果最好的混合算法是最大最小蚂蚁算法和局部搜索算法,文章通过对几种局部搜索的灵活运用,并结合改进的接受准则接受局部优化解,提出了一种高效的混合蚂蚁算法。算法前期使用3-opt这种简单高效的局部搜索的解初始化信息素矩阵,加快收敛速度,后期采用改进的Lin-Kernighan算法生成局部优化解然后依Metropolis接受准则概率接受,有效地避免陷入局部最优,理论分析和TSPLIB中部分实例仿真结果表明,此算法能比其他改进蚁群算法具有更多优越性。     

遗传算法在旅行商问题中的实践与探究

TSP问题是组合优化领域的经典问题之一,旨在求出遍历若干个城市的最短路径。本文通过遗传算法GA的选择和变异算子的确定和、交叉算子的改进,并在TSP问题中的实践来探索这个经典的NP(Nondeterministic Polynomial)难题。     

一种改进的求解TSP问题的演化算法

演化算法是解决组合优化问题的高效搜索算法．该文在现有求解TSP问题的演化算法的基础上,通过引入映射算子、优化算子以及增加一些控制策略,提出了一种高效的演化搜索算法．实验表明,该算法是有效的,通过对CHN144以及国际通用的TSPLIB中不同城市规模的数据进行测试表明,其中实例CHN144得到的最短路径为30353．860997,优于吴斌等运用分段算法得到的最短路径30354．3,亦优于朱文兴等人的结果,实例st70和kroB150得到的最短路径分别与运用分段算法得到的最短路径值相同,实例pr136得到的最短路径值为96770．924122,优于TSPLIB中提供的最短路径96772,对于其它实例也均能快速地得到和TSPLIB中提供的最优路径相同或更优的路径,该算法不仅很容易收敛到问题的最优解,而且求解速度极快．     

旅行商问题中巡回路径的数据结构

旅行商问题中巡回路径的数据结构对局部启发式算法的效率起着非常关键的作用。巡回路径的数据结构必须能够查询一条回路中每个城市的相对顺序,并且能够将一条回路中的部分城市逆序。分析了数组表示法、伸展树表示法和两级树表示法表示巡回路径时各种基本操作的实现过程及时间复杂度。数组表示法能够在常数时间内确定一条回路中每个城市的相对顺序,但是最坏情况下完成逆序操作需要Ω（n）时间,不适用于大规模的旅行商问题。伸展树表示法执行查询和更新操作的平摊时间复杂度是O（logn）,适用于极大规模的旅行商问题。而两级树表示法在最坏情况下每一个更新操作的时间复杂度是O（n^0.5）,适用于大规模的旅行商问题。     

旅行商问题的DNA算法

旅行商问题是求仅一次遍访指定城市并返回出发城市的最短旅行路线的问题,它是图论中一个经典的NP完全问题,用电子计算机需要指数级的时间才能得到解决,该文基于分子生物技术并利用Adleman-Lipton模型给出旅行商问题的DNA算法,这个DNA算法理论上能在多项式的时间内解决这个NP完全问题。具体地对n个城市的旅行商问题,首先将它视为一个具有顶点和边的图,并将顶点、边分别用DNA链编码表示,边的方向通过顶点的编码获得;再将这些DNA链投放在试管中进行生物化学反应,利用DNA计算的高效并行性,通过基本的生物实验操作最后得到旅行商问题的解,其过程的复杂度为O(n)。该算法的创新之处在于表示城市和路径的DNA链长度的设计,能使我们在合理小的范围内寻找旅行商问题的解,较大地简化了问题的复杂度。