TSP问题简介旅行商问题, 也就是那个被错误打成了blem、正确答案应该是TSP的组合优化里的老掉牙的难题, 它经典的那个样子可以被这么来描述一下, 意思就是说有一个卖东西的小推销员, 他需要去好几座城市里去做生意, 这个推销员是从某一座城市出来的, 然后, 必须要把所有的城市都跑一遍, 最后再回到一开始出发的那个地方, 那么具体应该怎么样去选择那条走路的路线才会最好, 答案就是让总的行走距离变得最短。从图论的这扇门看过去, 这个事儿的里层意思, 说白了就是在找一个带着权的、全都是边的无方向性的大圆圈, 要让这个圆圈的权值和是最小的那个数。因为这个事儿的所有可能的做法, 就是把所有的顶点摆成各种各样的排列顺序。这样一来, 随着顶点的数量一点点变多, 产生的结果就会像爆炸一样几何级数地增长。因此它被归类为NP完全问题。因为这类问题在交通运输上能用, 在电路板线路设计上能用, 在物流配送的环节里也得用, 所以在国内外都有很多专家学者在埋头研究它。早期的研究者是使用精确算法来求解该问题的, 常用的方法包括: 分枝定界法、线性规划法、动态规划法等。但是呢, 随着问题规模是不断地增大的, 精确算法就将是变得无能为力了。因此, 在后来的研究中, 国内外学者是重点使用近似算法或者启发式算法的, 主要有遗传算法、模拟退火法、蚁群算法、禁忌搜索算法、贪婪算法和神经网络等。遗传算法简介遗传算法是一种用于搜索最优解的方法, 它能够模拟达尔文生物进化论中的自然选择机理以及遗传学机理, 进而来描述生物进化的全过程。这种计算模型是从代表问题可能存在的潜在解集所构成的一个种群出发进行操作的, 而该种群的内部则是由经过基因编码处理的、具有一定数目的个体所组成的集合体。需要特别说明的一点是, 在这里每一个单独的个体, 实际上都是拥有特征的、作为实体存在的染色体。染色体是遗传物质的主要载体, 它相当于多个基因的集合, 其内部的表现也就是基因型, 这是一种特定的基因组合方式。这种基因组合决定了个体的外部形状表现, 举个例子来说, 黑头发的特征就是由染色体中负责控制这一特征的某种特定基因组合来决定的。所以在最开始的时候, 我们需要完成一项工作, 这项工作的内容是实现从表现型到基因型的一个映射过程, 这个映射过程也被我们称为编码工作。因为参照基因编码来做事, 其难度相当高, 所以我们会对其实施简化手段, 例如采取二进制编码方式。在最初的种群完成生成这一动作之后, 便会依照适者能够存活、优胜者必将淘汰的那些基本法则, 在后续的各个阶段当中, 一步步地实现演进过程, 从而逐步孕育出愈发接近最终目标的答案内容。在每一次循环进行的步骤里, 都会根据所处问题环境范围内各个个体所能展现出的适应程度数值的高低大小, 来进行挑选操作, 进而选出那些相对优秀的个体实例, 并且同时依赖于属于自然遗传学框架内部所提供的各种变化处理工具, 去执行将不同部分进行合并拼接这类操作以及引发形态改变这类操作, 以此推动结果的形成, 最终生成出一个包含了全新解决方案集合在内的群体数据体系。这个过程会导致种群的后代发生类似自然进化的现象, 使得后来的一代比前一代能够更加适应周围的环境, 而在末尾那一代的群体里面表现最为出色的那个个体, 经过了解码操作, 就可以被看成是解决该问题时所求得的一个近似最优解。遗传算法, 它是一类方法。这个方法属于随机化的搜索方法。它是借鉴了生物界里面的进化规律发展出来的。具体来说, 就是借鉴了诸如适者生存、优胜劣汰以及一些关于遗传的机制这类东西。这个概念是由美国的J教授在1975年的时候首先提出来的, 它的主要特点是对结构对象进行直接的操作, 这里是不存在求导以及函数连续性的限定问题的, 它具有内在的隐并行性以及更好的全局寻优能力, 采用的是概率化的寻优方法, 能够自动地获取和指导优化的搜索空间, 自适应地调整搜索方向, 是不需要确定的规则的。人们已经广泛地把遗传算法的这些性质应用到了多个领域, 这些领域包括组合优化、机器学习、信号处理、自适应控制和人工生命。遗传算法是计算机科学和人工智能领域当中常用的一种用于解决问题的搜索启发式算法, 它属于最优化方向的一类方法, 同时也算是进化算法的一种, 这种启发式通常会用来生成一些有用的解决方案以实现对问题的优化和搜索工作, 进化算法最初是从生物学中的进化现象那里得到启发才发展出来的, 那些被借鉴的现象包括了遗传染色传递、基因突变、自然选择过程以及杂交操作等方式。当遗传算法在设定适应度函数的时候, 如果选择出现了偏差, 那么它就有可能会陷入到局部的最优解之中去, 进而导致其无法到达全局的最优状态。粒子群算法简介粒子群算法, 也叫做鸟群算法, 这一点能够看出来它是受到了鸟类在捕食时候的行为的启发。这个算法是属于遗传算法以及群智算法这一类的。粒子群算法主要关注到了粒子的两个属性, 一个是位置, 另一个是速度。每一个粒子都在空间里面进行单独的搜索, 它们既记得自己找到过的最优解, 同时也知道整个粒子群体在当前时刻找到的那个最优解是什么。下一步要去往哪, 这需要看粒子现在所处的方向, 还要看它此前找到的最优解所指向的方向, 以及整个粒子群目前最优解所指向的方向。粒子群算法流程蚁群算法简介蚁群算法也就是大家常说的ACO, 它是一种属于群智能范畴的计算方法, 这个方法主要是依靠数量众多的个体成员去相互配合以及共同作用, 从而展示出智能化的运作特征, 为处理那些非常复杂的难题提供了一种全新的可行思路, 该算法最初是由意大利的专家学者们在1991年的时候率先提出的。在经过了超过20多年的发展过程之后, 蚁群算法这个事物, 无论是在理论方面的研究上, 还是在实际应用研究的范围里, 都获得了非常巨大的进步与提升。蚁群算法这是一种仿生学的算法, 它是由自然界里面蚂蚁在寻找食物的行为给启发出来的, 在自然界的状况之下, 当蚂蚁们在开展觅食工作的时候, 蚁群总是能够寻找到一条从蚂蚁巢穴以及食物来源之间最合适的路径, 下面的这个图展示出来了这样一个寻找食物的过程。在图a里面, 存在一群蚂蚁, 假设A这个位置是蚁巢, 那么E就是食物源, 反过来也一样成立。这群蚂蚁就会沿着蚁巢和食物源之间那条直线的路径去爬行。倘若在A和E中间突然冒出一个障碍物, 就像图b展示的那样, 那么在B点或者D点上面的蚂蚁, 它们就需要做一个决定, 看看到底是选择向左行驶还是向右行驶? 由于在起初的时候, 路上没有前面那些蚂蚁留下的信息素, 所以, 蚂蚁朝着两个不同的方向去行进, 这种概率其实是相等的。但是, 当有蚂蚁走过之后, 它就能够在自己行进的这条路上释放出信息素。并且, 这种释放出来的信息素, 还会以一个一定的速率逐渐地散发掉。要知道, 信息素这个东西, 本来就是蚂蚁之间用于交流的办法之中的一个。那么, 跟在后面的那些蚂蚁, 就可以通过观察这条路上面信息素的浓度高低, 从而去做出决策, 来决定到底是往左边去, 还是往右边去。可以十分清楚地看到, 沿着那条靠近短边的路径, 信息素的味道会变得越来越厚重, 并且正如图c中所展示的那样, 这种变化会吸引数量越来越多的蚂蚁来沿着这条路线进行行进。蚁群算法一开始是用来解决TSP问题的, 而且表现出了很强的优越性, 主要是因为它的分布式特点, 鲁棒性很强, 而且还容易和其他算法结合起来, 不过在另一方面, 它也存在着收敛速度比较慢的情况, 还比较容易陷入局部的最优情况。TSP问题, 也就是我们常说的旅行商问题, 还有人把它叫作中国邮递员问题。这属于一种叫做NP-hard的难题类型。对于这类难题, 如果我们用一般的算法来处理, 是特别难得到最完美结果的。所以, 在大多数情况下, 我们常常需要靠一些有启发性的方法来尝试求解。比较常见的例子像遗传算法, 专业缩写叫GA。还有蚁群算法, 简称ACO。另外微粒群算法也是其中之一, 它的英文缩写是PSO等等。遗传算法的实现import mathimport random# 得到所需二进制的位数def get_bit(start,end,decimal)::param start: 区间左端点值:param end: 区间右端点值:param decimal: 有效位数:return: 所需二进制的位数# 求所需要的二进制数的位数need (end - start) * pow(10, decimal 1)# 对2取对数向上取整得到位数bit int(math.log(need, 2)) 1return bit# 编码函数def encode(start,end,decimal,bit,num)::param start: 区间左端点值:param end: 区间右端点值:param decimal: 有效位数:param bit: 所需二进制的位数:param num: 需要转化的十进制数:return: 22位二进制数# # 求所需要的二进制数的位数# need (end - start) * pow(10,decimal 1)# # 对2取对数向上取整得到位数# bit int(math.log(need,2)) 1# print(int(bit)1)# 将数转化为二进制binary bin(int((num 1) * pow(10,decimal 1)))# 除去前面的0bbinary str(binary)[2:]# 将其补为22位while len(binary) 22:binary 0 binaryreturn binary# 解码函数def decode(start,end,decimal,num)::param start: 区间左端点值:param end: 区间右端点值:param decimal: 有效位数:param num: 需要解码的二进制数:return: 原十进制数num 0b numnum int(num,2)num num / pow(10,decimal 1) -1# print(num)return num# 适应度函数def fitness(start,end,decimal,num)::param start: 区间左端点值:param end: 区间右端点值:param decimal: 有效位数:param num: 需要求适应度函数值的二进制数:return: 适应度函数值# 首先解码x decode(start,end,decimal,num)# 计算适应度函数值f x * math.sin(10 * math.pi * x) 2.0return f# 选择函数def select(start,end,decimal,population)::param start: 区间左端点值:param end: 区间右端点值:param decimal: 有效位数:param num: 需要求适应度函数值的二进制数:param population: 种群规模为M:return: 返回选择后的种群# 按照population顺序存放其适应度all_fitness []for i in population:all_fitness.append(fitness(start,end,decimal,i))# print(fitness(start,end,decimal,i))# 适应度函数的总和sum_fitness sum(all_fitness)# 以第一个个体为0号计算每个个体轮盘开始的位置position的位置和population是对应的all_position []for i in range(0,len(all_fitness)):all_position.append(sum(all_fitness[:i1])/sum_fitness)# print(all_position)# 轮盘赌进行选择# 经过选择后的新种群next_population []for i in range(0,len(population)):# 生成0-1之间的随机小数ret random.random()for j in range(len(all_position)):# 根据轮盘赌规则进行选择if all_position[j] ret:# print(ret)# print(all_position[j])next_population.append(population[j])breakreturn next_population# 判断是否超出范围的函数def whether_out(start,end,decimal,num):if start decode(start,end,decimal,num) end:return Trueelse:return False# 交叉函数def cross(M,Pc,bit,start,end,decimal,next_population1)::param M: 种群规模:param Pc: 交叉概率:param bit: 二进制的位数:param start: 区间左端点值:param end: 区间右端点值:param decimal: 有效位数:param next_population1: 选择后的种群:return: 交叉后的种群num M * Pc# 计数器判断是否交换次数达到num次count 0i 0# # 交叉后的种群# next_population2 []# 由于选择后的种群本来就是随机的所以让相邻两组做交叉从第一组开始直到达到交叉概率停止while(i M):# while(count num):# 随机产生交叉点position random.randrange(0,bit-1)# print(position)# print(position)# 将两个个体从交叉点断开tmp11 next_population1[i][:position]tmp12 next_population1[i][position:]tmp21 next_population1[i1][:position]tmp22 next_population1[i1][position:]# 重新组合成新的个体# print(next_population1[i])next_population1[i] tmp11 tmp22# print(next_population1[i])next_population1[i1] tmp21 tmp12# 判断交叉后的个体是否超出范围如果每超出则count1否则i不加count不加if (whether_out(start,end,decimal,next_population1[i]) and whether_out(start,end,decimal,next_population1[i1])):i 2count 1else:continueif count num:break# print(count)return next_population1# 取反字符串指定位置的数def reverse(string,position):string list(string)if string[position] 0:string[position] 1else:string[position] 0return .join(string)# 变异函数def variation(M,Pm,start,end,decimal,bit,next_population2):# i 0for i in range(M):ret random.random()# 生成0-1的随机数如果随机数if ret Pm:# 随机产生变异点position random.randrange(0, bit)next_population2[i] reverse(next_population2[i],position)# if (whether_out())while(whether_out(start,end,decimal,next_population2[i]) False):# 如果超出范围则重新随机产生变异点直到满足范围position random.randrange(0, bit)next_population2[i] reverse(next_population2[i], position)else:continuereturn next_population2# 寻找群体中的最优个体def search(start,end,decimal,population)::param start: 区间左端点值:param end: 区间右端点值:param decimal: 有效位数:param population: 最终迭代后的群体:return: 最优个体# 记录函数值fit []for i in population:fit.append(fitness(start,end,decimal,i))# 求出最大值所在的位置position fit.index(max(fit))return decode(start,end,decimal,population[position])# 测试函数def test(M,T,Pc,Pm,start,end,decimal):bit get_bit(start, end, decimal)# 全集包括所有编码后的个体all []for i in range(-1 * pow(10, 6), 2 * pow(10, 6) 1):all.append(encode(start, end, decimal, bit, i / pow(10, 6)))i 1# print(all)# 第一次随机选择种群规模为Tpopulation random.sample(all, M)# print(all)# print(population)# 进行选择操作next_population1 select(start, end, decimal, population)# print(next_population1)# 进行交叉操作next_population2 cross(M, Pc, bit, start, end, decimal, next_population1)# print(len(next_population2))# a 1011101# print(reverse(a,2))next_population3 variation(M, Pm, start, end, decimal, bit, next_population2)# print(next_population2)# print(next_population3)sum 0for i in range(len(next_population2)):if (next_population2[i] ! next_population3[i]):sum 1# print(sum)# print(len(next_population3))# 主函数def main(M,T,Pc,Pm,start,end,decimal):bit get_bit(start,end,decimal)# 全集包括所有编码后的个体all []for i in range(-1 * pow(10,6), 2 * pow(10,6) 1):all.append(encode(start,end,decimal,bit,i / pow(10,6)))i 1# 第一次随机选择种群规模为Tpopulation random.sample(all, M)for i in range(T):# 进行选择操作population select(start,end,decimal,population)# 进行交叉操作population cross(M,Pc,bit,start,end,decimal,population )# 进行变异操作population variation(M,Pm,start,end,decimal,bit,population )# 最优个体final search(start,end,decimal,population)print(%.5f % final)if __name__ __main__:# test()main(200,200,0.6,0.005,-1,2,5)粒子群算法的实现import randomimport copybirdsint(raw_input(Enter count of bird: ))xcountint(raw_input(Enter count of x: ))pos[]speed[]bestpos[]birdsbestpos[]w0.8c12c22r10.6r20.3for i in range(birds):pos.append([])speed.append([])bestpos.append([])def GenerateRandVec(list):for i in range(xcount):list.append(random.randrange(1,100))def CalDis(list):dis0.0for i in list:disi**2return disfor i in range(birds): #initial all birds pos,speedGenerateRandVec(pos[i])GenerateRandVec(speed[i])bestpos[i]copy.deepcopy(pos[i])def FindBirdsMostPos():bestCalDis(bestpos[0])index0for i in range(birds):tempCalDis(bestpos[i])if tempbest:besttempindexireturn bestpos[index]birdsbestposFindBirdsMostPos() #initial birdsbestposdef NumMulVec(num,list): #result is in listfor i in range(len(list)):list[i]*numreturn listdef VecSubVec(list1,list2): #result is in list1for i in range(len(list1)):list1[i]-list2[i]return list1def VecAddVec(list1,list2): #result is in list1for i in range(len(list1)):list1[i]list2[i]return list1def UpdateSpeed():#global speedfor i in range(birds):temp1NumMulVec(w,speed[i][:])temp2VecSubVec(bestpos[i][:],pos[i])temp2NumMulVec(c1*r1,temp2[:])temp1VecAddVec(temp1[:],temp2)temp2VecSubVec(birdsbestpos[:],pos[i])temp2NumMulVec(c2*r2,temp2[:])speed[i]VecAddVec(temp1,temp2)def UpdatePos():global bestpos,birdsbestposfor i in range(birds):VecAddVec(pos[i],speed[i])if CalDis(pos[i])CalDis(bestpos[i]):bestpos[i]copy.deepcopy(pos[i])birdsbestposFindBirdsMostPos()for i in range(100):#print birdsbestposprint CalDis(birdsbestpos)UpdateSpeed()UpdatePos()raw_input()蚁群算法的实现import numpy as npfrom tqdm import tqdm#进度条设置import matplotlib.pyplot as pltimport matplotlib as mplimport matplotlib; matplotlib.use(TkAgg)mpl.rcParams[font.sans-serif] [SimHei] # 指定默认字体mpl.rcParams[axes.unicode_minus] False # 解决保存图像是负号-显示为方块的问题#蚁群算法求函数极值#适应度函数def func(x,y):value 20*np.power(x*x-y*y,2)-np.power(1-y,2)-3*np.power(1y,2)0.3return value#初始化参数m20 #蚂蚁个数G_max200 #最大迭代次数Rho0.9 #信息素蒸发系数P00.2 #转移概率常数XMAX 5 #搜索变量x最大值XMIN -5 #搜索变量x最小值YMAX 5 #搜索变量y最大值YMIN -5 #搜索变量y最小值Xnp.zeros(shape(m,2)) #蚁群 shape(20, 2)Taunp.zeros(shape(m,)) #信息素Pnp.zeros(shape(G_max,m)) #状态转移矩阵fitneess_value_list[] #迭代记录最优目标函数值#随机设置蚂蚁初始位置for i in range(m):#遍历每一个蚂蚁X[i,0]np.random.uniform(XMIN,XMAX,1)[0] #初始化xX[i,1]np.random.uniform(YMIN,YMAX,1)[0] #初始化yTau[i]func(X[i,0],X[i,1])step0.1; #局部搜索步长for NC in range(G_max):#遍历每一代lamda1/(NC1)BestIndexnp.argmin(Tau) #最优索引Tau_bestTau[BestIndex] #最优信息素#计算状态转移概率for i in range(m):#遍历每一个蚂蚁P[NC,i]np.abs((Tau_best-Tau[i]))/np.abs(Tau_best)0.01 #即例最优信息素的距离#位置更新for i in range(m): # 遍历每一个蚂蚁#局部搜索if P[NC,i]P0:temp1 X[i, 0] (2 * np.random.random() - 1) * step * lamda # x(2 * np.random.random() - 1) 转换到【-1,1】区间temp2 X[i,1] (2 * np.random.random() - 1) * step * lamda #y#全局搜索else:temp1 X[i, 0] (XMAX - XMIN) * (np.random.random() - 0.5)temp2 X[i, 0] (YMAX - YMIN) * (np.random.random() - 0.5)#边界处理if temp1 XMIN:temp1 XMINif temp1 XMAX:temp1 XMAXif temp2 XMIN:temp2 XMINif temp2 XMAX:temp2 XMAX#判断蚂蚁是否移动(选更优if func(temp1, temp2) func(X[i, 0], X[i, 1]):X[i, 0] temp1X[i, 1] temp2#更新信息素for i in range(m): # 遍历每一个蚂蚁Tau[i] (1 - Rho) * Tau[i] func(X[i, 0], X[i, 1]) #(1 - Rho) * Tau[i] 信息蒸发后保留的indexnp.argmin(Tau)#最小值索引valueTau[index]#最小值fitneess_value_list.append(func(X[index,0],X[index,1])) #记录最优目标函数值#打印结果min_indexnp.argmin(Tau)#最优值索引minXX[min_index,0] #最优变量xminYX[min_index,1] #最优变量yminValuefunc(X[min_index,0],X[min_index,1]) #最优目标函数值print(最优变量x,minX,end)print(最优变量y,minY,end\n)print(最优目标函数值,minValue)plt.plot(fitneess_value_list,label迭代曲线)plt.legend()plt.show()出现的问题及解决方法1、粒子群算法优化离散问题需要重新定义速度和位置2、在计算最优值的时候, 出现了错误。计算一下更新之后的粒子的适应值, 更新每个粒子的局部最优的值, 以及整个粒子群的全局的最优的值。3、现在的问题是, 迭代这个过程的停止条件没办法确定。迭代终止条件得根据具体的问题情况来定, 通常来说当达到预先设定的最大迭代次数时, 又或者粒子群在这之前搜索得到的最优位置满足了针对目标函数的最小允许误差要求。4、信息素常量Q如果设置得过小, 那么就会使得蚁群的搜索范围变小, 这就容易造成过早的收敛, 会导致种群陷入局部最优的情况。过大每条路径上信息含量差别较小容易陷入混沌状态5、这个最大迭代次数tmax如果设置得过小, 就会导致可选的路径数量比较少, 从而让种群容易陷入到局部最优解的情况里。过大运算时间过长6、蚂蚁的数量m如果过小, 可能会导致一些已经经过采集和搜索并且积累了一定信息浓度的路径, 其信息浓度直接下降并且变为零, 这样的情况就会引发算法过早结束运行, 从而使得最终得到的解在全局最优性方面发生降低。这个情况出现过大的现象, 具体表现为在每一条路径上面, 信息素的数值都趋向于平均分配, 这样的话, 正反馈机制所起到的作用就会有所减弱, 最终导致的后果就是收敛的速度会明显减慢。7、在编程实现遗传算法的过程当中, 操作起来是挺复杂的, 一开始得先把问题做个编码处理, 然后再费点劲儿找到那个最优的结果, 之后还得再对问题进行一轮解码操作。8、另外三个算子的实现当中, 也存在着许多参数, 比如交叉率以及变异率。并且, 这些参数的选择会对解的品质造成严重影响。而目前针对这些参数的选择, 大部分是依赖于经验来进行决定的。9、该算法在对初始种群进行选择的工作上, 是存在一定程度的依赖性的。它还可以结合着一些启发式的算法, 来进行相应的改进优化处理。总结让自己对于遗传算法、粒子群算法, 还有蚁群算法的了解, 变得更加深入了一层。遗传算法属于一种智能优化算法, 它能够比较好地近似求解TSP问题, 遗传算法是一类随机优化算法, 不过它并不是简简单单的随机比较和搜索, 而是通过针对染色体的评估, 以及运用染色体里基因的功用, 从而有效地把已有的信息用上, 这样就能指导搜索那些可能有希望改善优化质量的方向了。蚁群算法ACO是一种概率型算法, 其主要用途是寻找优化路径。这种算法的特征包括分布计算、信息正反馈以及启发式搜索。从本质上看, 它是进化算法中的一种启发式全局优化算法。关于蚁群算法的终止条件, 需要判断是否已经达到最大迭代次数。粒子群优化算法PSO是一种利用群体智能进行问题求解的方法。在这个算法中, 粒子群里的每一个粒子都代表了一个可能的答案。这些粒子通过个体之间的简单行为, 以及群体内部的信息交流, 共同实现对问题的求解过程, 从而体现出这种方法的智能特性。粒子群算法和遗传算法是一样的, 都会出现不稳定现象, 所以每次跑出来的结果都不会完全一样。 不过, 这些结果之间的差距不会非常大, 最短距离的数据基本都保持在40左右, 这里只是简单给出了三次运行的结果数据。在进行最优解计算的时候, 粒子群算法有可能会陷入到局部最优的情况里面去, 但是它具备运行效率高的特点, 所以在实际使用场景中能够发挥出非常好的作用。欢迎大家加我微信交流讨论请备注csdn上添加