精华内容
下载资源
问答
  • 数组采用十个真实地点模拟tsp问题,在文件中以数组保存,可以自行添加或者修改,不过别忘了对基因序列的长度做一定
  • 围绕蚁群优化算法的理论及应用,针对蚁群算法在TSP规划中求解能力不足的难题,运用了一种基于自适应的蚂蚁算法,并对TSP规划进行了设计。为了提高路径规划的效率,将自适应与传统的蚂蚁算法相结合形成了自适应蚁群...
  • 在物流活动中,配送成本占据整个...本文提出了应用MATLAB软件,通过建立配送优化的TSP模型,运用基于遗传算法的优化算法解决TSP问题,并有相关实例进行验证,对物流企业实现科学快捷的配送调度和路径的优化有实际意义。
  • 根据以上对TSP的算法描述,可以写出用模拟退火算法解TSP问题的流程图2 所示: 3. Python实现 import numpy as np import matplotlib.pyplot as plt import pdb "旅行商问题 ( TSP , Traveling ...

    旅行商问题的几种求解:https://wenku.baidu.com/view/0579c5206294dd88d1d26b70.html
    模拟退火法解决TSP及Matlab实现:https://www.cnblogs.com/youngsea/p/7461977.html
    模拟退火法TSP问题的Python实现:https://blog.csdn.net/qq_34798326/article/details/79013338

    一、旅行商问题

    1. 问题描述:一名商人要到若干城市去推销商品,已知城市个数和各城市间的路程(或旅费),要求找到一条从城市1出发,经过所有城市且每个城市只能访问一次,最后回到城市1的路线,使总的路程(或旅费)最小。
    2. 问题分析:该问题是组合优化问题,属于NP难题,是诸多领域内出现的多种复杂问题的集中概括和简化形式,并且已成为各种启发式的搜索、优化算法的间接比较标准。
    TSP
    (图片来源https://www.cnblogs.com/youngsea/p/7461977.html

    二、 模拟退火算法

    1. 算法
    模拟退火算法可分为解空间、目标函数和初始解三部分,其基本思想是:
    (1)初始化:初始温度T(充分大),初始解状态s(是算法迭代的起点),每个T值的迭代次数L;
    (2)对k=1,……,L做第(3)至第6步;
    (3)产生新解s′;
    (4)计算增量cost=cost(s′)-cost(s),其中cost(s)为评价函数;
    (5)若t<0则接受s′作为新的当前解,否则以概率exp(-t′/T)接受s′作为新的当前解;
    (6)如果满足终止条件则输出当前解作为最优解,结束程序。终止条件通常取为连续若干个新解都没有被接受时终止算法;
    (7)T逐渐减少,且T趋于0,然后转第2步运算。

    2. 参数选择
    (1)温度T的初始值设置。
    温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一。初始温度高,则搜索到全局最优解的可能性大,但因此要花费大量的计算时间;反之,则可节约计算时间,但全局搜索性能可能受到影响。实际应用过程中,初始温度一般需要依据实验结果进行若干次调整。
    (2)温度衰减函数的选取。
    衰减函数用于控制温度的退火速度,一个常用的函数为:
    T(t+1)=aT(t)
    式中a是一个非常接近于1的常数,t为降温的次数。
    (3)马尔可夫链长度L的选取。
    通常的原则是:在衰减参数T的衰减函数已选定的前提下,L的选取应遵循在控制参数的每一取值上都能恢复准平衡的原则。

    三、TSP算法实现

    1. TSP算法描述
    (1)TSP问题的解空间和初始解
    TSP的解空间S是遍访每个城市恰好一次的所有回路,是所有城市排列的集合。TSP问题的解空间S可表示为{1,2,…,n}的所有排列的集合,即S = {(c1,c2,…,cn) | ((c1,c2,…,cn)为{1,2,…,n}的排列)},其中每一个排列Si表示遍访n个城市的一个路径,ci= j表示在第i次访问城市j。模拟退火算法的最优解与初始状态无关,故初始解为随机函数生成一个{1,2,…,n}的随机排列作为S0。
    (2)目标函数
    TSP问题的目标函数即为访问所有城市的路径总长度,也可称为代价函数:
    TSP目标函数
    现在TSP问题的求解就是通过模拟退火算法求出目标函数C(c1,c2,…,cn)的最小值,相应地,s*= (c*1,c*2,…,c*n)即为TSP问题的最优解。
    (3)新解产生
    新解的产生对问题的求解非常重要。新解可通过分别或者交替用以下2种方法产生:
    ①二变换法:任选序号u,v(设uvn),交换u和v之间的访问顺序,若交换前的解为si= (c1,c2,…,cu,…,cv,…,cn),交换后的路径为新路径,即:
    二变换法
    ②三变换法:任选序号u,v和ω(u≤vω),将u和v之间的路径插到ω之后访问,若交换前的解为si= (c1,c2,…,cu,…,cv,…,cω,…,cn),交换后的路径为的新路径为:
    这里写图片描述
    (4)目标函数差
    计算变换前的解和变换后目标函数的差值:
    这里写图片描述
    (5)Metropolis接受准则
    根据目标函数的差值和概率exp(-ΔC′/T)接受si′作为新的当前解si,接受准则:
    这里写图片描述

    2 TSP算法流程
    根据以上对TSP的算法描述,可以写出用模拟退火算法解TSP问题的流程图2 所示:
    这里写图片描述

    3. Python实现

    import numpy as np
    import matplotlib.pyplot as plt 
    import pdb
    
    "旅行商问题 ( TSP , Traveling Salesman Problem )"
    coordinates = np.array([[565.0,575.0],[25.0,185.0],[345.0,750.0],[945.0,685.0],[845.0,655.0],
                            [880.0,660.0],[25.0,230.0],[525.0,1000.0],[580.0,1175.0],[650.0,1130.0],
                            [1605.0,620.0],[1220.0,580.0],[1465.0,200.0],[1530.0,  5.0],[845.0,680.0],
                            [725.0,370.0],[145.0,665.0],[415.0,635.0],[510.0,875.0],[560.0,365.0],
                            [300.0,465.0],[520.0,585.0],[480.0,415.0],[835.0,625.0],[975.0,580.0],
                            [1215.0,245.0],[1320.0,315.0],[1250.0,400.0],[660.0,180.0],[410.0,250.0],
                            [420.0,555.0],[575.0,665.0],[1150.0,1160.0],[700.0,580.0],[685.0,595.0],
                            [685.0,610.0],[770.0,610.0],[795.0,645.0],[720.0,635.0],[760.0,650.0],
                            [475.0,960.0],[95.0,260.0],[875.0,920.0],[700.0,500.0],[555.0,815.0],
                            [830.0,485.0],[1170.0, 65.0],[830.0,610.0],[605.0,625.0],[595.0,360.0],
                            [1340.0,725.0],[1740.0,245.0]])
    
    #得到距离矩阵的函数
    def getdistmat(coordinates):
        num = coordinates.shape[0] #52个坐标点
        distmat = np.zeros((52,52)) #52X52距离矩阵
        for i in range(num):
            for j in range(i,num):
                distmat[i][j] = distmat[j][i]=np.linalg.norm(coordinates[i]-coordinates[j])
        return distmat
    
    def initpara():
        alpha = 0.99
        t = (1,100)
        markovlen = 1000
    
        return alpha,t,markovlen
    num = coordinates.shape[0]
    distmat = getdistmat(coordinates) #得到距离矩阵
    
    
    solutionnew = np.arange(num)
    #valuenew = np.max(num)
    
    solutioncurrent = solutionnew.copy()
    valuecurrent =99000  #np.max这样的源代码可能同样是因为版本问题被当做函数不能正确使用,应取一个较大值作为初始值
    #print(valuecurrent)
    
    solutionbest = solutionnew.copy()
    valuebest = 99000 #np.max
    
    alpha,t2,markovlen = initpara()
    t = t2[1]
    
    result = [] #记录迭代过程中的最优解
    while t > t2[0]:
        for i in np.arange(markovlen):
    
            #下面的两交换和三角换是两种扰动方式,用于产生新解
            if np.random.rand() > 0.5:# 交换路径中的这2个节点的顺序
                # np.random.rand()产生[0, 1)区间的均匀随机数
                while True:#产生两个不同的随机数
                    loc1 = np.int(np.ceil(np.random.rand()*(num-1)))
                    loc2 = np.int(np.ceil(np.random.rand()*(num-1)))
                    ## print(loc1,loc2)
                    if loc1 != loc2:
                        break
                solutionnew[loc1],solutionnew[loc2] = solutionnew[loc2],solutionnew[loc1]
            else: #三交换
                while True:
                    loc1 = np.int(np.ceil(np.random.rand()*(num-1)))
                    loc2 = np.int(np.ceil(np.random.rand()*(num-1))) 
                    loc3 = np.int(np.ceil(np.random.rand()*(num-1)))
    
                    if((loc1 != loc2)&(loc2 != loc3)&(loc1 != loc3)):
                        break
    
                # 下面的三个判断语句使得loc1<loc2<loc3
                if loc1 > loc2:
                    loc1,loc2 = loc2,loc1
                if loc2 > loc3:
                    loc2,loc3 = loc3,loc2
                if loc1 > loc2:
                    loc1,loc2 = loc2,loc1
    
                #下面的三行代码将[loc1,loc2)区间的数据插入到loc3之后
                tmplist = solutionnew[loc1:loc2].copy()
                solutionnew[loc1:loc3-loc2+1+loc1] = solutionnew[loc2:loc3+1].copy()
                solutionnew[loc3-loc2+1+loc1:loc3+1] = tmplist.copy()  
    
            valuenew = 0
            for i in range(num-1):
                valuenew += distmat[solutionnew[i]][solutionnew[i+1]]
            valuenew += distmat[solutionnew[0]][solutionnew[51]]
           # print (valuenew)
            if valuenew<valuecurrent: #接受该解
    
                #更新solutioncurrent 和solutionbest
                valuecurrent = valuenew
                solutioncurrent = solutionnew.copy()
    
                if valuenew < valuebest:
                    valuebest = valuenew
                    solutionbest = solutionnew.copy()
            else:#按一定的概率接受该解
                if np.random.rand() < np.exp(-(valuenew-valuecurrent)/t):
                    valuecurrent = valuenew
                    solutioncurrent = solutionnew.copy()
                else:
                    solutionnew = solutioncurrent.copy()
        t = alpha*t
        result.append(valuebest)
        print (t) #程序运行时间较长,打印t来监视程序进展速度
    #用来显示结果
    plt.plot(np.array(result))
    plt.ylabel("bestvalue")
    plt.xlabel("t")
    plt.show()
     
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
                <link href="https://csdnimg.cn/release/phoenix/mdeditor/markdown_views-095d4a0b23.css" rel="stylesheet">
                    </div>
    
    展开全文
  • 遗传算法解决10城市TSP问题程序源代码
  • 遗传算法在TSP问题中的应用 什么是TSP问题TSP问题是典型的组合优化问题,其也是遗传算法界中最为经典的优化问题之一。在遗算法成熟之前也一直困扰着科研人员,TSP问题又称为名旅行商问题,其定义为设有N个城市,...

    遗传算法在TSP问题中的应用

    什么是TSP问题?

    TSP问题是典型的组合优化问题,其也是遗传算法界中最为经典的优化问题之一。在遗算法成熟之前也一直困扰着科研人员,TSP问题又称为名旅行商问题,其定义为设有N个城市,推销员要从某一个城市前往另外N-1个城市,每个城市能去的次数有且仅有一次,最终回到出发的城市,要寻找的便是该推销人员走过的最短路径,也可以理解为给N个数目的城市附上一个加权完全图,每个城市都用一个顶点代替,每两个顶点之间一条无向加权边[2]。最终求解此无向加权完全图的最小哈米尔顿回路。

    研究意义?

    TSP问题不仅仅是解决了TSP问题,其可以延伸到了许多其他问题当中,如下城市市区下水管道的铺设路径,物流公司物流配送货物等实际与生活息息相关的问题,这些问题的求解方法都可以应用于很多现实生活中的组合优化问题,是都是相当经典的组合问题,遗传算法是一种全局随机搜索的算法,对于解决各种组合优化问题都有着十分有效的作用,因此用遗传算法来解决这两个经典组合优化问题(本人在毕业论文的另外一个组合优化问题是有关营销利润的,有兴趣的可以私聊或者评论)是一种不错的选择。

    算法在TSP中的实际应用步骤

    (1)设定N个城市,每个城市用一个自然数代替,每个城市之间的距离制定成加权数据,对所有定义的城市进行随机编码,TSP问题中的编码,科研人员往往采用的时二进制字符编码和实数编码;
    (2)确定好各类参数,初始化种群,采用随机的方法随机产生有限个初始群体;
    (3)第三步根据实际问题所处的环境制定合适的数学适应度函数,在TSP问题往往中采用f =1/T,T即代表解路径的总长度,T越大则表示适应度越小;
    (4)对每个个体对体进行适应度评估,通过比较适应度得出优秀的个体并且保留;
    (5)对每个个体进行适应度的评估后便根据适应度的大小进行选择算子的操作,以此来决定哪些个体基因需要进行交叉变异操作,使它们的基因得到优化,并对优化后的解的基因再进行适应度评估,保留优秀个体,对于非优秀的个体对其再进行选择,交叉,变异操作直到其适应度通过评估或迭代次数超过参数规定的最大迭代次数停止优化操作。
    ps:编码方式我这里采用的是实数制编码(编码方式的多性,欢迎讨论)
    交叉概率Pc:交叉算子进行基因优化的操作,取值范围在0.4-0.99。
    变异概率Pm:变异算子进行基因优化的操作,其取值范围为0.00001-0.1。
    该适应度函数表达式如下式所示:Fm = 1/T

    运行结果

    在种群数为55,交叉率为0.6,变异率为0.05,设定15个城市坐标为{84,9},{94,86},{87,43},{71,48},{76,65},{69,53},{82,61},{83,72},{69,62},{73,12},{71,72},{68,46},{73,66},{71,42},{78,66}依次编号为0到14,也可以根据自己的想法来设定目标城市坐标,将各个城市放入一个二维数组中,迭代次数设定为150次,当遗传操作的迭代次数超过这个数则强行停止算法。使用C语言进行编译后得到的运行结果如下:
    运行解面一
    运行界面二
    得到各个个体城市得遍历次序后得到第54号个体为近似最优解,最优路径为先后走完编号为0、5、11、3、13、14、8、10、12、6、7、1、4、2、9、0 这15个城市,在求解过程中,可以发现遗传算法可以使最优解收敛到某一个稳定的值,如在解决此实际问题中时它的最优解一直在250上下波动。根据收敛值可以得出近似最优解,这也是遗传算法得的特点之一。

    结语

    博主第一次写博客,如有不足指出请各位前辈多多指教,也希望对初学者有一定的帮助,如有毕业论文想写优化算法的欢迎借鉴。

    展开全文
  • 遗传算法在TSP问题上的应用matlab仿真实现

    千次阅读 多人点赞 2020-01-08 10:45:10
    遗传算法在TSP问题上的应用 本文采用遗传算法来求解TSP问题,将中国的35个省会级城市作为研究对象,设置西安为起点,历经其余34座城市后,最后回到西安的一条最短路径。 一、设计过程 1、适应度函数设计: TSP的...

    最近在做一个遗传算法应用的课程大作业,在网上找了一些TSP的算法,结合别人的算法进行更改和优化了下,得到了最终的仿真结果,感谢前人栽的树。

     

    遗传算法在TSP问题上的应用

    本文采用遗传算法来求解TSP问题,将中国的35个省会级城市作为研究对象,设置西安为起点,历经其余34座城市后,最后回到西安的一条最短路径。

    一、设计过程

    1、适应度函数设计:

    TSP的目标是路径总长度为最短,在进行选择时更具适应度值越大则被遗传到下一代的概率越大,适应度值与路径总距离呈反比关系,因此路径总长度的倒数就可以为TSP的适应度函数:

      

    2、序表达式编码

    序表达式是TSP问题的最自然的表达,其中城市是按访问的顺序排列的。例如,对于9个城市的TSP:3-2-5-4-7-1-6-9-8-3可简单表示为向量[3254716983],表示从城市3出发依次经过2,5,4,7,1,6,9,8然后返回城市3的一条路径。

    3、联赛选择算子设计

    联赛选择是基于个体适应度之间大小关系的选择方法,一般为两两比较,不需要满足f(x)>0,具体步骤为将群体中随机选N个个体进行适应度值大小比较,将大的个体遗传,将上述过程重复M次就可以得到M个个体。在本次设计中,随机从父代种群中选择4个路径个体,进行适应度值比较,将适应度最大的个体遗传到下一代,种群规模为200,则重复该选择步骤200次,得到新一代种群。

    4、顺序交叉算子设计

    顺序交叉(OX):从父代A随机选择一个编码子串片段,放到子代A的对应位置,子代A空余的位置从父代B中按照B的顺序选取(与已有的编码不重复)。同理可得子代B。设置父代A=872|139|0546,父代B=983|567|1420。交叉过程:对于父代A,选择139进行遗传到下一代,其余部分从父代B中按照期序随机选取,从父代B中选择的元素不能和1、3、9散字相同,依次放到子代的对应位置,得到下一代A1,子代B1的求解过程同上,求解过程如下。

                                    

    5、两点对换变异算子设计(Mutation)

    在本文中采用两点对换变异算子对种群进行变异操作,由于TSP问题的约束为路径中每个城市只能遍历一次,因此不能采用遗传算法常用的基于二进制编码的变异操作,不能由简单的变量进行翻转来实现变异。两点对换变异算子为在TSP问题中的个体编码是一系列城市的序列,随机在这个城市序列中抽取两个城市,然后交换他们的位置,这样就实现了个体的变异操作。


    二、仿真结果如下:
     1、遗传算法的基本运算步骤
     (1)初始化:设置进化代数计数器t=0,设置最大进化代数T,随机生成M个个体作为初始群体P(0)。(2)个体评价:计算群体P(t)中各个个体的适应度。(3)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。(4)交叉运算:将交叉算子作用于群体。遗传算法中起核心作用的就是交叉算子。(5)变异运算:将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。(6)终止条件判断:若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出,终止计算。


     2、初始种群路径图:


     

    3、迭代找到最优解的路径图



    4、收敛曲线图

     

     

     

     

     

    二、具体matlab代码如下:

     

    主函数main.c

    clear;
    clc;
    tStart = tic; % 算法计时器
    %************************初始化参数变量*******************************
        [Num,Txt,Raw]=xlsread('provincial_ capital_coordinate12.xlsx');  %经纬度数据
        cities = Num(:,5:6);
        cities=cities';
        [~,cityNum]=size(cities);
        
        
        maxGEN = 500;
        popSize = 300; % 遗传算法种群大小
        crossoverProbabilty = 0.95; %交叉概率
        mutationProbabilty = 0.33; %变异概率
    
        %********初始化种群***********
        % 计算上述生成的各个城市之间的距离断
        distances = calculateDistance(cities);
        % 生成种群,每个个体代表一个路径
        gbest = Inf;%行:Inf 无穷大
        parentPop = zeros(popSize, cityNum);
        % 随机打乱种群
        for i=1:popSize
         parentPop(i,2:cityNum-1) = randperm(cityNum-2); %randperm功能是随机打乱一个数字序列,将1-cityNum数字序列随机打乱
         for a=2:cityNum-1
             parentPop(i,a)=parentPop(i,a)+1;
         end
         parentPop(i,1)=1;
         parentPop(i,cityNum)=cityNum;
        end
        % 定义子代种群
        childPop = zeros(popSize,cityNum);
        
        %定义每代的最小路径
        minPathes = zeros(maxGEN,1);
        %****************************
      
    %**********************************************************************
    
    %*********************GA算法选择交叉变异执行过程************************
    for  genNum=1:maxGEN
     
        % 计算适应度的值,即路径总距离
        [fitnessValue, sumDistance, minPath, maxPath] = fitness(distances, parentPop);
        tournamentSize=4; %设置大小
        for k=1:popSize
        %% 以下为联赛选择法
            % 随机选择父代
            tourPopDistances=zeros( tournamentSize,1);
            for i=1:tournamentSize
                randomRow = randi(popSize);%行:返回一个介于1到popSize的伪随机整数
                tourPopDistances(i,1) = sumDistance(randomRow,1);
            end
     
            % 选择最好的,即距离最小的
            parent1  = min(tourPopDistances);
            [parent1X,parent1Y] = find(sumDistance==parent1,1, 'first');%选出随机的4个中最短距离种群序号
            parent1Path = parentPop(parent1X(1,1),:);%%选出随机的4个中最短距离种群路径
     
     
            for i=1:tournamentSize
                randomRow = randi(popSize);
                tourPopDistances(i,1) = sumDistance(randomRow,1);
            end
            parent2  = min(tourPopDistances);
            [parent2X,parent2Y] = find(sumDistance==parent2,1, 'first');
            parent2Path = parentPop(parent2X(1,1),:);
        %% 以上为联赛选择法
      
        %% 顺序交叉(OX)
            individual = crossover(parent1Path, parent2Path, crossoverProbabilty);%个体交叉
        %%
      
        %% 对换变异(由于路径不能出现重复元素,因此变异不能为随意变化,本实验采用随机交换两元素位置来实现变异)
            individual = mutate(individual, mutationProbabilty);%个体变异
        %%
            childPop(k,:) = individual(1,:);%行:保存下一代种群的个体
            
            minPathes(genNum,1) = minPath; %行:保留此代中最短路径
        end
        % 更新父代
        parentPop = childPop;%行:种群此时更新为最新子代
        
        %% 画图
    
        % 画出当前状态下的最短路径
        if minPath < gbest
            gbest = minPath;
            paint(cities, parentPop, gbest, sumDistance,genNum);%行:画出最新的最短路径轨迹
        end
        fprintf('代数:%d   最短路径:%.2fKM \n', genNum,minPath);
      
    %    fprintf('%s\n', Txt(Bestpath(1,0),2));
        %%
    end
    
    %% 迭代完成,进行最终结果显示
    figure 
    plot(minPathes, 'MarkerFaceColor', 'blue','LineWidth',1);
    title({'最短路径收敛曲线图';['最短路径距离为', num2str(minPath)]});
    set(gca,'ytick',0:10:450); 
    ylabel('路径总长度');
    xlabel('种群代数');
    grid on
    tEnd = toc(tStart);
    fprintf('时间:%d 分  %f 秒.\n', floor(tEnd/60), rem(tEnd,60));
    

    根据经纬度计算城市间距离函数:calculateDistance.m

    function [ distances ] = calculateDistance( city )
    %计算距离
     
        [~, col] = size(city);
        distances = zeros(col);
        for i=1:col
            for j=1:col
                distances(i,j)= distances(i,j)+ sqrt( (city(1,i)-city(1,j))^2 + (city(2,i)-city(2,j))^2  );           
            end
        end
    end

    交叉函数:crossover.m

    function [childPath] = crossover(parent1Path, parent2Path, prob)
    % 交叉
     
        random = rand();
        if prob >= random                     %行:随机生成一个01之前的数,和概率值比较,相当于一个轮盘赌的选择,来执行概率选择执行操作
            [l, length] = size(parent1Path);
            childPath = zeros(l,length);
            setSize = floor(length/2) -1;     %行:floor 朝负无穷大方向取整
            offset = randi(setSize);          %行:随机 产生1-setSize之间的整数
            parent1OXstart=offset;            %行:0X交叉,父代1遗传给子代的片段起点
            parent1OXend=setSize+offset-1;    %行:0X交叉,父代1遗传给子代的片段终点
            
            for i=parent1OXstart:parent1OXend
                childPath(1,i) = parent1Path(1,i);
            end
            
            childPath(1,1) = parent1Path(1,1);%行:将路径的起点和终点直接赋给子代,因为起点和终点不变
            childPath(1,length) = parent1Path(1,length);
            
            %行:parent2依顺序放入子代位坐标
            parent2Point=2;                
            for x=2:length-1
                if childPath(1,x)==0
                    for y=parent2Point:length-1
                        if ~any(childPath == parent2Path(1,y))%行:如果子代路径相应元素不等于父代元素
                            childPath(1,x)=parent2Path(1,y);
                            parent2Point=y+1;
                            break;
                        end
                    end
                end
            end
            
        else
            childPath = parent1Path;
        end
    end

    变异函数:mutate.m

    function [ mutatedPath ] = mutate( path, prob )
    %对指定的路径利用指定的概率进行更新
    %行:由于路径不予许存在相同的数,所以变异不能随意变,只能用随机互换位置的方法
        random = rand();
        if random <= prob         
            [l,length] = size(path);
            index1 = randi([2,length-1]);
            index2 = randi([2,length-1]);
            %交换
            temp = path(l,index1);
            path(l,index1) = path(l,index2);
            path(l,index2)=temp;
        end
            mutatedPath = path; 

    结果路径图片显示函数:paint.m

    function [ bestPopPath ] = paint( cities, pop, minPath, totalDistances,gen)
        gNumber=gen;
        [~, length] = size(cities);
        xDots = cities(1,:);
        yDots = cities(2,:);
        %figure(1);
        %行:先画城市的固定坐标
        plot(xDots,yDots, 'p', 'MarkerSize', 10, 'MarkerFaceColor', 'green');
        xlabel('经度');
        ylabel('纬度');
        axis equal
        
        [num,txt,raw]=xlsread('provincial_ capital_coordinate12.xlsx');  %经纬度数据% 
         text(xDots(1)+0.2,yDots(1)+0.2,txt(1+1,2),'FontSize',9.5,'Color','red','FontWeight','Bold') ; %先画起点,突出起点
        for i=2:length-1
            text(xDots(i)+0.2,yDots(i)+0.2,txt(i+1,2),'FontSize',8,'Color','blue','FontWeight','Bold') ; %加上0.01使标号和点不重合,可以自己调整
        end
        
        
        
        hold on
        [minPathX,~] = find(totalDistances==minPath,1, 'first');
        bestPopPath = pop(minPathX, :);
        bestX = zeros(1,length);
        bestY = zeros(1,length);
        for j=1:length
           bestX(1,j) = cities(1,bestPopPath(1,j));
           bestY(1,j) = cities(2,bestPopPath(1,j));
        end
       % title('当前代数%d 的路径图');
        title(['第', num2str(gNumber),'代种群的最优路径图']) ;
        %行:再画城市的路径连线
        plot(bestX(1,:),bestY(1,:), 'red', 'LineWidth', 1.25);
        legend('城市', '路径');
        axis equal%行:axis equal/将横轴纵轴的定标系数设成相同值。
        grid on
        %text(5,0,sprintf('迭代次数: %d 总路径长度: %.2f',gNumber, minPath),'FontSize',10);
        drawnow
        hold off
    end

    最后感谢前人的博客,然我这个小白从0 完成了遗传算法的作业,也希望此博客能帮助到大家。

    具体代码:https://download.csdn.net/download/qq_37271216/12089106

    有需要代码的朋友也可以把邮箱留下,免费发到邮箱!

    展开全文
  • Hopfield神经网络解决 TSP问题 利用神经网络解决组合优化问题是神经网络应用的一个重要方面。所谓组合优化问题,就是在给定约束条件下,使目标函数极小(或极大) 的变量组合问题。将Hopfield 网络应用于求解组合优化...
  • 压缩文件中包含了三种算法源码,打开即可直接运行,都是用的C或C++。论文中详细介绍了三种方法在旅行商问题上的应用,也对三种方法的效率进行了对比,并且对TSP问题进行了总结。
  • TSP问题中,蚁群算法的应用

    千次阅读 2016-04-01 17:00:38
     蚁群算法(Ant Clony Optimization, ACO)是一种群智能算法,它是由一群无智能或有轻微智能的个体(Agent)通过相互协作而表现出智能行为,从而为求解复杂问题提供了一个新的可能性。蚁群算法最早是由意大利学者...
    1. 蚁群算法简介
    


         蚁群算法(Ant Clony Optimization, ACO)是一种群智能算法,它是由一群无智能或有轻微智能的个体(Agent)通过相互协作而表现出智能行为,从而为求解复杂问题提供了一个新的可能性。蚁群算法最早是由意大利学者Colorni A., Dorigo M. 等于1991年提出。经过20多年的发展,蚁群算法在理论以及应用研究上已经得到巨大的进步。


          蚁群算法是一种仿生学算法,是由自然界中蚂蚁觅食的行为而启发的。在自然界中,蚂蚁觅食过程中,蚁群总能够按照寻找到一条从蚁巢和食物源的最优路径。图(1)显示了这样一个觅食的过程。


    image


    图(1)蚂蚁觅食


     


         在图1(a)中,有一群蚂蚁,假如A是蚁巢,E是食物源(反之亦然)。这群蚂蚁将沿着蚁巢和食物源之间的直线路径行驶。假如在A和E之间突然出现了一个障碍物(图1(b)),那么,在B点(或D点)的蚂蚁将要做出决策,到底是向左行驶还是向右行驶?由于一开始路上没有前面蚂蚁留下的信息素(pheromone),蚂蚁朝着两个方向行进的概率是相等的。但是当有蚂蚁走过时,它将会在它行进的路上释放出信息素,并且这种信息素会议一定的速率散发掉。信息素是蚂蚁之间交流的工具之一。它后面的蚂蚁通过路上信息素的浓度,做出决策,往左还是往右。很明显,沿着短边的的路径上信息素将会越来越浓(图1(c)),从而吸引了越来越多的蚂蚁沿着这条路径行驶。


    2. TSP问题描述


          蚁群算法最早用来求解TSP问题,并且表现出了很大的优越性,因为它分布式特性,鲁棒性强并且容易与其它算法结合,但是同时也存在这收敛速度慢,容易陷入局部最优(local optimal)等缺点。


          TSP问题(Travel Salesperson Problem,即旅行商问题或者称为中国邮递员问题),是一种,是一种NP-hard问题,此类问题用一般的算法是很大得到最优解的,所以一般需要借助一些启发式算法求解,例如遗传算法(GA),蚁群算法(ACO),微粒群算法(PSO)等等。


          TSP问题可以分为两类,一类是对称TSP问题(Symmetric TSP),另一类是非对称问题(Asymmetric TSP)。所有的TSP问题都可以用一个图(Graph)来描述:





    V={c1,c2,…,ci,…,cn},i=1,2,…,nV={c1,c2,…,ci,…,cn},i=1,2,…,n是所有城市的集合. cici表示第i个城市, nn为城市的数目;


    E={(r,s):r,s∈V}E={(r,s):r,s∈V}是所有城市之间连接的集合;


    C={crs:r,s∈V}C={crs:r,s∈V}是所有城市之间连接的成本度量(一般为城市之间的距离);


    如果crs=csrcrs=csr, 那么该TSP问题为对称的,否则为非对称的。


    一个TSP问题可以表达为:


    求解遍历图G=(V,E,C)G=(V,E,C),所有的节点一次并且回到起始节点,使得连接这些节点的路径成本最低。


    3. 蚁群算法原理


          假如蚁群中所有蚂蚁的数量为m,所有城市之间的信息素用矩阵pheromone表示,最短路径为bestLength,最佳路径为bestTour。每只蚂蚁都有自己的内存,内存中用一个禁忌表(Tabu)来存储该蚂蚁已经访问过的城市,表示其在以后的搜索中将不能访问这些城市;还有用另外一个允许访问的城市表(Allowed)来存储它还可以访问的城市;另外还用一个矩阵(Delta)来存储它在一个循环(或者迭代)中给所经过的路径释放的信息素;还有另外一些数据,例如一些控制参数(α,β,ρ,Q)(α,β,ρ,Q),该蚂蚁行走玩全程的总成本或距离(tourLength),等等。假定算法总共运行MAX_GEN次,运行时间为t。


    蚁群算法计算过程如下:


    (1)初始化


    设t=0,初始化bestLength为一个非常大的数(正无穷),bestTour为空。初始化所有的蚂蚁的Delt矩阵所有元素初始化为0,Tabu表清空,Allowed表中加入所有的城市节点。随机选择它们的起始位置(也可以人工指定)。在Tabu中加入起始节点,Allowed中去掉该起始节点。


    (2)为每只蚂蚁选择下一个节点。


    为每只蚂蚁选择下一个节点,该节点只能从Allowed中以某种概率(公式1)搜索到,每搜到一个,就将该节点加入到Tabu中,并且从Allowed中删除该节点。该过程重复n-1次,直到所有的城市都遍历过一次。遍历完所有节点后,将起始节点加入到Tabu中。此时Tabu表元素数量为n+1(n为城市数量),Allowed元素数量为0。接下来按照(公式2)计算每个蚂蚁的Delta矩阵值。最后计算最佳路径,比较每个蚂蚁的路径成本,然后和bestLength比较,若它的路径成本比bestLength小,则将该值赋予bestLength,并且将其Tabu赋予BestTour。




    (公式1)






    (公式2)


    其中p(t)ijpij(t)表示选择城市j的概率,kk表示第kk个蚂蚁,τ(t)ijτij(t)表示城市i,ji,j在第tt时刻的信息素浓度,ηijηij表示从城市i到城市j的可见度,


    ηij=1dijηij=1dij,dijdij表示城市i,ji,j之间的成本(或距离)。由此可见dijdij越小,ηijηij越大,也就是从城市ii到jj的可见性就越大。ΔτkijΔτijk表示蚂蚁kk在城市ii与jj之间留下的信息素。


    LkLk表示蚂蚁kk经过一个循环(或迭代)锁经过路径的总成本(或距离),即tourLength.α,β,Qα,β,Q 均为控制参数。


    (3)更新信息素矩阵


    令t=t+nt=t+nt,按照(公式3)更新信息素矩阵phermone。


    τij(t+n)=ρ⋅τij(t)+Δτijτij(t+n)=ρ⋅τij(t)+Δτij
    (公式3)


    τij(t+n)τij(t+n)为t+nt+n时刻城市ii与jj之间的信息素浓度。ρρ为控制参数,DeltaijDeltaij为城市ii与jj之间信息素经过一个迭代后的增量。并且有


    Δτij=∑k=1mΔτkijΔτij=∑k=1mΔτijk
    (公式4)


    其中ΔτkijΔτijk由公式计算得到。


    (4)检查终止条件


    如果达到最大代数MAX_GEN,算法终止,转到第(5)步;否则,重新初始化所有的蚂蚁的Delt矩阵所有元素初始化为0,Tabu表清空,Allowed表中加入所有的城市节点。随机选择它们的起始位置(也可以人工指定)。在Tabu中加入起始节点,Allowed中去掉该起始节点,重复执行(2),(3),(4)步。


    (5)输出最优值


    4. Java实现


          在该java实现中我们选择使用tsplib上的数据att48,这是一个对称tsp问题,城市规模为48,其最优值为10628.其距离计算方法如图(2)所示:




    图(2)att48距离计算方法


          实现中,使用了两个java类,一个Ant类,一个ACO类。


    具体实现代码如下(此代码借鉴了蚁群优化算法的JAVA实现):


    Ant类:


      1: import java.util.Random;
      2: import java.util.Vector;
      3: 
      4: /**
      5:  * 
      6:  * @author BIAO YU
      7:  *
      8:  */
      9: public class Ant implements Cloneable {
     10: 
     11:   private Vector<Integer> tabu; //禁忌表
     12:   private Vector<Integer> allowedCities; //允许搜索的城市
     13:   private float[][] delta; //信息数变化矩阵
     14:   private int[][] distance; //距离矩阵
     15:   
     16:   private float alpha; 
     17:   private float beta;
     18:   
     19:   private int tourLength; //路径长度
     20:   private int cityNum; //城市数量
     21:   
     22:   private int firstCity; //起始城市
     23:   private int currentCity; //当前城市
     24:   
     25:   public Ant(){
     26:     cityNum = 30;
     27:     tourLength = 0;
     28:     
     29:   }
     30:   
     31:   /**
     32:    * Constructor of Ant
     33:    * @param num 蚂蚁数量
     34:    */
     35:   public Ant(int num){
     36:     cityNum = num;
     37:     tourLength = 0;
     38:     
     39:   }
     40:   
     41:   /**
     42:    * 初始化蚂蚁,随机选择起始位置
     43:    * @param distance 距离矩阵
     44:    * @param a alpha
     45:    * @param b beta
     46:    */
     47:   public void init(int[][] distance, float a, float b){
     48:     alpha = a;
     49:     beta = b;
     50:     allowedCities = new Vector<Integer>();
     51:     tabu = new Vector<Integer>();
     52:     this.distance = distance;
     53:     delta = new float[cityNum][cityNum];
     54:     for (int i = 0; i < cityNum; i++) {
     55:       Integer integer = new Integer(i);
     56:       allowedCities.add(integer);
     57:       for (int j = 0; j < cityNum; j++) {
     58:         delta[i][j] = 0.f;
     59:       }
     60:     }
     61:     
     62:     Random random = new Random(System.currentTimeMillis());
     63:     firstCity = random.nextInt(cityNum);
     64:     for (Integer i:allowedCities) {
     65:       if (i.intValue() == firstCity) {
     66:         allowedCities.remove(i);
     67:         break;
     68:       }
     69:     }
     70:     
     71:     tabu.add(Integer.valueOf(firstCity));
     72:     currentCity = firstCity;
     73:   }
     74:   
     75:   /**
     76:    * 选择下一个城市
     77:    * @param pheromone 信息素矩阵
     78:    */
     79:   public void selectNextCity(float[][] pheromone){
     80:     float[] p = new float[cityNum];
     81:     float sum = 0.0f;
     82:     //计算分母部分
     83:     for (Integer i:allowedCities) {
     84:       sum += Math.pow(pheromone[currentCity][i.intValue()], alpha)*Math.pow(1.0/distance[currentCity][i.intValue()], beta);
     85:     }
     86:     //计算概率矩阵
     87:     for (int i = 0; i < cityNum; i++) {
     88:       boolean flag = false;
     89:       for (Integer j:allowedCities) {
     90:         
     91:         if (i == j.intValue()) {
     92:           p[i] = (float) (Math.pow(pheromone[currentCity][i], alpha)*Math.pow(1.0/distance[currentCity][i], beta))/sum;
     93:           flag = true;
     94:           break;
     95:         }
     96:       }
     97:       
     98:       if (flag == false) {
     99:         p[i] = 0.f;
    100:       }
    101:     }
    102:     
    103:     //轮盘赌选择下一个城市
    104:     Random random = new Random(System.currentTimeMillis());
    105:     float sleectP = random.nextFloat();
    106:     int selectCity = 0;
    107:     float sum1 = 0.f;
    108:     for (int i = 0; i < cityNum; i++) {
    109:       sum1 += p[i];
    110:       if (sum1 >= sleectP) {
    111:         selectCity = i;
    112:         break;
    113:       }
    114:     }
    115:     
    116:     //从允许选择的城市中去除select city
    117:     for (Integer i:allowedCities) {
    118:       if (i.intValue() == selectCity) {
    119:         allowedCities.remove(i);
    120:         break;
    121:       }
    122:     }
    123:     //在禁忌表中添加select city
    124:     tabu.add(Integer.valueOf(selectCity));
    125:     //将当前城市改为选择的城市
    126:     currentCity = selectCity;
    127:     
    128:   }
    129:   
    130:   /**
    131:    * 计算路径长度
    132:    * @return 路径长度
    133:    */
    134:   private int calculateTourLength(){
    135:     int len = 0;
    136:     for (int i = 0; i < cityNum; i++) {
    137:       len += distance[this.tabu.get(i).intValue()][this.tabu.get(i+1).intValue()];
    138:     }
    139:     return len;
    140:   }
    141:   
    142:   
    143:   
    144:   public Vector<Integer> getAllowedCities() {
    145:     return allowedCities;
    146:   }
    147: 
    148:   public void setAllowedCities(Vector<Integer> allowedCities) {
    149:     this.allowedCities = allowedCities;
    150:   }
    151: 
    152:   public int getTourLength() {
    153:     tourLength = calculateTourLength();
    154:     return tourLength;
    155:   }
    156:   public void setTourLength(int tourLength) {
    157:     this.tourLength = tourLength;
    158:   }
    159:   public int getCityNum() {
    160:     return cityNum;
    161:   }
    162:   public void setCityNum(int cityNum) {
    163:     this.cityNum = cityNum;
    164:   }
    165: 
    166:   public Vector<Integer> getTabu() {
    167:     return tabu;
    168:   }
    169: 
    170:   public void setTabu(Vector<Integer> tabu) {
    171:     this.tabu = tabu;
    172:   }
    173: 
    174:   public float[][] getDelta() {
    175:     return delta;
    176:   }
    177: 
    178:   public void setDelta(float[][] delta) {
    179:     this.delta = delta;
    180:   }
    181: 
    182:   public int getFirstCity() {
    183:     return firstCity;
    184:   }
    185: 
    186:   public void setFirstCity(int firstCity) {
    187:     this.firstCity = firstCity;
    188:   }
    189:   
    190: }
    191: 
    ACO类:


      1: import java.io.BufferedReader;
      2: import java.io.FileInputStream;
      3: import java.io.IOException;
      4: import java.io.InputStreamReader;
      5: 
      6: /**
      7:  * 
      8:  * @author BIAO YU
      9:  * 
     10:  *
     11:  */
     12: public class ACO {
     13: 
     14:   private Ant[] ants; //蚂蚁
     15:   private int antNum; //蚂蚁数量
     16:   private int cityNum; //城市数量
     17:   private int MAX_GEN; //运行代数
     18:   private float[][] pheromone; //信息素矩阵
     19:   private int[][] distance; //距离矩阵
     20:   private int bestLength; //最佳长度
     21:   private int[] bestTour; //最佳路径
     22:   
     23:   //三个参数
     24:   private float alpha; 
     25:   private float beta;
     26:   private float rho;
     27:   
     28:   
     29:   public ACO(){
     30:     
     31:   }
     32:   /** constructor of ACO
     33:    * @param n 城市数量
     34:    * @param m 蚂蚁数量
     35:    * @param g 运行代数
     36:    * @param a alpha
     37:    * @param b beta
     38:    * @param r rho
     39:    * 
     40:   **/
     41:   public ACO(int n, int m, int g, float a, float b, float r) {
     42:     cityNum = n;
     43:     antNum = m;
     44:     ants = new Ant[antNum];
     45:     MAX_GEN = g;
     46:     alpha = a;
     47:     beta = b;
     48:     rho = r;
     49:     
     50:   }
     51:   
     52:   @SuppressWarnings("resource")
     53:   /**
     54:    * 初始化ACO算法类
     55:    * @param filename 数据文件名,该文件存储所有城市节点坐标数据
     56:    * @throws IOException
     57:    */
     58:   private void init(String filename) throws IOException{
     59:     //读取数据  
     60:         int[] x;  
     61:         int[] y;  
     62:         String strbuff;  
     63:         BufferedReader data = new BufferedReader(new InputStreamReader(new FileInputStream(filename)));  
     64:         
     65:         distance = new int[cityNum][cityNum];  
     66:         x = new int[cityNum];  
     67:         y = new int[cityNum];  
     68:         for (int i = 0; i < cityNum; i++) {  
     69:             strbuff = data.readLine(); 
     70:             String[] strcol = strbuff.split("");  
     71:             x[i] = Integer.valueOf(strcol[1]);  
     72:             y[i] = Integer.valueOf(strcol[2]);  
     73:         }  
     74:         //计算距离矩阵 ,针对具体问题,距离计算方法也不一样,此处用的是att48作为案例,它有48个城市,距离计算方法为伪欧氏距离,最优值为10628 
     75:         for (int i = 0; i < cityNum - 1; i++) {  
     76:             distance[i][i] = 0;  //对角线为0
     77:             for (int j = i + 1; j < cityNum; j++) {  
     78:               double rij = Math.sqrt(((x[i] - x[j]) * (x[i] - x[j])+ (y[i] - y[j]) * (y[i] - y[j]))/10.0);
     79:               int tij = (int) Math.round(rij);
     80:               if (tij < rij) {
     81:                 distance[i][j] = tij + 1;  
     82:                     distance[j][i] = distance[i][j];  
     83:         }else {
     84:           distance[i][j] = tij;  
     85:                     distance[j][i] = distance[i][j]; 
     86:         }
     87:             }  
     88:         }  
     89:         distance[cityNum - 1][cityNum - 1] = 0;  
     90:         
     91:         //初始化信息素矩阵  
     92:         pheromone=new float[cityNum][cityNum];  
     93:         for(int i=0;i<cityNum;i++)  
     94:         {  
     95:             for(int j=0;j<cityNum;j++){  
     96:                 pheromone[i][j]=0.1f;  //初始化为0.1
     97:             }  
     98:         }  
     99:         bestLength=Integer.MAX_VALUE;  
    100:         bestTour=new int[cityNum+1];  
    101:         //随机放置蚂蚁  
    102:         for(int i=0;i<antNum;i++){  
    103:             ants[i]=new Ant(cityNum);  
    104:             ants[i].init(distance, alpha, beta);  
    105:         }  
    106:   }
    107:   
    108:   public void solve(){
    109:     
    110:     for (int g = 0; g < MAX_GEN; g++) {
    111:       for (int i = 0; i < antNum; i++) {
    112:         for (int j = 1; j < cityNum; j++) {
    113:           ants[i].selectNextCity(pheromone);
    114:         }
    115:         ants[i].getTabu().add(ants[i].getFirstCity());
    116:         if (ants[i].getTourLength() < bestLength) {
    117:           bestLength = ants[i].getTourLength();
    118:           for (int k = 0; k < cityNum + 1; k++) {
    119:             bestTour[k] = ants[i].getTabu().get(k).intValue();
    120:           }
    121:         }
    122:         for (int j = 0; j < cityNum; j++) {
    123:           ants[i].getDelta()[ants[i].getTabu().get(j).intValue()][ants[i].getTabu().get(j+1).intValue()] = (float) (1./ants[i].getTourLength());
    124:           ants[i].getDelta()[ants[i].getTabu().get(j+1).intValue()][ants[i].getTabu().get(j).intValue()] = (float) (1./ants[i].getTourLength());
    125:         }
    126:       }
    127:       
    128:       //更新信息素
    129:       updatePheromone();
    130:       
    131:        //重新初始化蚂蚁
    132:           for(int i=0;i<antNum;i++){  
    133:              
    134:               ants[i].init(distance, alpha, beta);  
    135:           }  
    136:     }
    137:     
    138:     //打印最佳结果
    139:     printOptimal();
    140:   }
    141:   
    142:   //更新信息素
    143:   private void updatePheromone(){
    144:     //信息素挥发  
    145:         for(int i=0;i<cityNum;i++)  
    146:             for(int j=0;j<cityNum;j++)  
    147:                 pheromone[i][j]=pheromone[i][j]*(1-rho);  
    148:         //信息素更新  
    149:         for(int i=0;i<cityNum;i++){  
    150:             for(int j=0;j<cityNum;j++){  
    151:                 for (int k = 0; k < antNum; k++) {
    152:           pheromone[i][j] += ants[k].getDelta()[i][j];
    153:         } 
    154:             }  
    155:         }  
    156:   }
    157:   
    158:   private void printOptimal(){
    159:     System.out.println("The optimal length is: " + bestLength);
    160:     System.out.println("The optimal tour is: ");
    161:     for (int i = 0; i < cityNum + 1; i++) {
    162:       System.out.println(bestTour[i]);
    163:     }
    164:   }
    165:   
    166:   public Ant[] getAnts() {
    167:     return ants;
    168:   }
    169: 
    170:   public void setAnts(Ant[] ants) {
    171:     this.ants = ants;
    172:   }
    173: 
    174:   public int getAntNum() {
    175:     return antNum;
    176:   }
    177: 
    178:   public void setAntNum(int m) {
    179:     this.antNum = m;
    180:   }
    181: 
    182:   public int getCityNum() {
    183:     return cityNum;
    184:   }
    185: 
    186:   public void setCityNum(int cityNum) {
    187:     this.cityNum = cityNum;
    188:   }
    189: 
    190:   public int getMAX_GEN() {
    191:     return MAX_GEN;
    192:   }
    193: 
    194:   public void setMAX_GEN(int mAX_GEN) {
    195:     MAX_GEN = mAX_GEN;
    196:   }
    197: 
    198:   public float[][] getPheromone() {
    199:     return pheromone;
    200:   }
    201: 
    202:   public void setPheromone(float[][] pheromone) {
    203:     this.pheromone = pheromone;
    204:   }
    205: 
    206:   public int[][] getDistance() {
    207:     return distance;
    208:   }
    209: 
    210:   public void setDistance(int[][] distance) {
    211:     this.distance = distance;
    212:   }
    213: 
    214:   public int getBestLength() {
    215:     return bestLength;
    216:   }
    217: 
    218:   public void setBestLength(int bestLength) {
    219:     this.bestLength = bestLength;
    220:   }
    221: 
    222:   public int[] getBestTour() {
    223:     return bestTour;
    224:   }
    225: 
    226:   public void setBestTour(int[] bestTour) {
    227:     this.bestTour = bestTour;
    228:   }
    229: 
    230:   public float getAlpha() {
    231:     return alpha;
    232:   }
    233: 
    234:   public void setAlpha(float alpha) {
    235:     this.alpha = alpha;
    236:   }
    237: 
    238:   public float getBeta() {
    239:     return beta;
    240:   }
    241: 
    242:   public void setBeta(float beta) {
    243:     this.beta = beta;
    244:   }
    245: 
    246:   public float getRho() {
    247:     return rho;
    248:   }
    249: 
    250:   public void setRho(float rho) {
    251:     this.rho = rho;
    252:   }
    253: 
    254: 
    255:   /**
    256:    * @param args
    257:    * @throws IOException 
    258:    */
    259:   public static void main(String[] args) throws IOException {
    260:     ACO aco = new ACO(48, 100, 1000, 1.f, 5.f, 0.5f);
    261:     aco.init("c://data.txt");
    262:     aco.solve();
    263:   }
    264: 
    265: }
    266: 
    5. 总结


          蚁群算法和其它的启发式算法一样,在很多场合都得到了应用,并且取得了很好的结果。但是同样存在着很多的缺点,例如收敛速度慢,容易陷入局部最优,等等。对于这些问题,还需要进一步的研究和探索,另外蚁群算法的数学机理至今还没有得到科学的解释,这也是当前研究的热点和急需解决的问题之一。注:TSP数据文件以及两篇早期的关于蚁群算法的文章包含在附件中,请点击此处
    展开全文
  • .tsp文件读入,模拟退火算法函数接口,测试文件,运行结果全在里面了 Simulated annealing is a greedy algorithm, but its search process introduces a random factor. Simulated annealing algorithm with a...
  • 以N个节点的TSP(旅行商问题问题为例,应用遗传算法进行求解,求出问题的最优解。
  • 陈灵佳文章首先对蚁群算法与TSP问题进行简要介绍,在此基础上对蚁群算法在解决TSP问题中的应用进行论述。期望通过本文的研究能够对TSP问题的解决有所帮助。【关键词】蚁群算法 TSP问题 最优解1 蚁群算法与TSP问题...
  • 模拟退火算法应用实例
  • MATLAB随机神经网络应用在模拟退火算法中解决TSP问题-一种随机神经网络应用在模拟退火算法中解决TSP问题.rar 一种随机神经网络应用在模拟退火算法中解决TSP问题
  • 本matlab代码是我的课程大作业代码,代码编写规范清晰、代码注释绝对非常清晰,零基础都可以看懂,直接运行可用,且包含了TSP城市的经纬度坐标数据集,欢迎大家下载。
  • 目前程序代码设置只支持不超过10个点的tsp问题,感兴趣的同学可以自己修改代码,使程序适应性更广泛。 使用方法: 每次运行前删除文件夹内的result.txt 1.在左侧区域内选取n(2)个点 2.选取完成后点击生成解决方案 ...
  • 提出一种改进的遗传算法,遗传算子是基于近邻选择策略设计的,另外还对评估函数、种群多样性以及保留精英算子等方面对遗传算法进行了改进,并将其应用到旅行商问题的求解上,实验结果表明提出的算法是有效的。
  • TSP(路径规划,最短路径问题

    千次阅读 2019-04-02 20:12:35
    转载:动态规划解决TSP(旅行推销员问题TSP问题(Travelling Salesman Problem)又译为旅行推销员问题、货郎担问题,即假设有一个旅行商人要拜访n个城市,从某个城市出发,每个城市只能访问一次且最后回到出发...
  • TensorFlow代码实现霍普菲尔德网络(Hopfield)解决20个城市旅行商问题(TSP),旅行商...但是,首先从应用上来说,很多实际应用问题,如印制电路板的、连锁店的货物配送路线等,经简化的处理后,均可转化为旅行商问题TSP
  • 人工神经网络实验 用CHNN算法求解TSP问题 算法:Hopfield神经网络 语言:Matlab
  • .tsp文件读入,模拟退火算法函数接口,测试文件,运行结果全在里面了 Tabu Search (TS) is a local search-based metaheuristic, which is proposed by Fred W. Glover, in 1986. Tabu Search is completely ...
  • 数学建模源码集锦-基于遗传算法的TSP算法应用实例
  • 同时TSP问题是经典的NP -C 问题,已被广泛应用于在VLSI芯片设计、网络路由和车辆选路等领域,对TSP问题的求解的突破意味着大量NPC问题的求解可以迎刃而解,因而有着重要的实际价值和理论意义。文章系统地介绍了TSP问题,...
  • 模拟退火算法在tsp问题中的应用研究 毕业设计
  • TSP问题测试程序

    2018-01-18 15:36:48
    遗传算法在商旅问题上的应用,非常有用的测试算法,我已经优化的很好了,希望对大家有帮助。
  • 这里提供本人的课程设计 包含对蚁群算法的分析与应用TSP旅行售货商问题上的具体实现 提供相关源码 和课程论文 供参考交流
  • 利用蚁群算法解决去掉回路的TSP问题。求得从起始点出发并遍历所有点的最短路径。
  • 利用遗传算法求解TSP问题,具有比较实际的应用价值
  • 神经网络在TSP问题中的应用 简单介绍旅行商问题解决

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,734
精华内容 3,093
关键字:

tsp问题应用

友情链接: HuffmanCodes.zip