遗传算法求解TSP问题python实现

文章目录

      • 1 遗传算法总体设计
      • 2 算子设计
        • 2.1 选择算子
        • 2.2 交叉算子
        • 2.3 变异算子
        • 2.4 将种群的个体按照里程排序,并返回当前种群中的最优个体及其里程
        • 2.5 设置种群数,变异概率及其进化次数
        • 2.6 主函数
      • 3 实验结果分析
      • 4 附python源码(完整版)

1 遗传算法总体设计

  • Step1: 初始化参数(种群数、进化次数、变异概率,此次实验并未用到交叉概率,交叉由保留的父代随机进行);

  • Step2: 初始种群由贪婪算法求得的个体以及其他随机生成的个体构成,评价每一个个体的适配值(路径里程决定);

  • Step3: 判断算法的收敛准则是否满足(此处为迭代次数)。若满足收敛准则,则输出搜索结果,否则执行Step(4~8);

  • Step4: 执行选择操作根据个体适配值随机选择作为父代;

  • Step5: 父代两两个体随机进行交叉操作生成子代;

  • Step6: 父代变异,子代按概率变异,只有变异后的个体优于变异前的个体才接受该个体变异;

  • Step7: 更新种群个体(变异后的父代+子代)对应的适配值,更新当前最优解;

  • Step8: 返回Step3 判断是否进行下一次迭代;

==注:==以下算法需要用到的数据均和禁忌搜索算法中的处理一致,因此这里不再阐述。

2 算子设计

2.1 选择算子

将种群个体按照里程由小到大排列,排列后的种群个体的适应度:fitness=1fitness = 1-\frac{位次}{种群规模}

采用random库中的random方法,随机生成0~1·之间的数p,若p<fitness则将该个体作为父代保留。

  • 代码实现
def selection(population):
    '''
    选出父代个体
    '''
    M = population_size
    parents = []
    for i in range(M):
        if random.random() < (1 - i/M):
            parents.append(population[i])
    return parents

2.2 交叉算子

POSITION BASED CROSSOVER(PX)与CYCLE CROSSOVER(CX)的混合。

  • POSITION BASED CROSSOVER

Step1: 从parent1中随机选择N个点

Step2: 在child1中的相同位置复制这N个点,其余位置为空。

Step3:将在parent2但未在child1中的点按照在parent2中的相对顺序填充到child1中的空位中。

Step4: parent1与parent2交换角色,重复以上步骤,得出child2。

==例:==路径parent1=【1、2、3、4、5、6、7、8、9】,parent2=【5、4、6、3、1、9、2、7、8】

从parent1中随机选取4个点如【2、5、6、9】

parent1:

p1

复制选中的点到child1:

c1空

parent2:

p2

将在parent2但未在child1中的点【4、3、1、7、6】按照在parent2中的相对顺序填充到child1中的空位中。

c1
  • CYCLE CROSSOVER

CX交叉方法与PX交叉方法的主要不同点就是第一步选点方式的不同,因此这里只介绍CX的选点方式,交叉方式同PX。

Step1: P1中的第一个点为起点start,P2中的第一个点为end,将start添加到cross_points中。

Step2:找寻P1中end的位置position,令P2中position对应的点为end

Step3:将end添加到cross_points中

Step4:重复step2,3直到end=start

  • 交叉算法流程图:
CPX
  • 代码实现
def CPX(parent1,parent2):
    '''
    交叉繁殖:CX与PX的混合双亲产生两个子代
    '''
    cycle = [] #交叉点集
    start = parent1[0]
    cycle.append(start)
    end = parent2[0]
    while end != start:
        cycle.append(end)
        end = parent2[parent1.index(end)]
    child = parent1[:]
    cross_points = cycle[:]
    if len(cross_points) < 2 :
        cross_points = random.sample(parent1,2)
    k = 0
    for i in range(len(parent1)):
        if child[i] in cross_points:
            continue
        else:
            for j in range(k,len(parent2)):
                if parent2[j] in cross_points:
                    continue
                else:
                    child[i] = parent2[j]
                    k = j + 1
                    break   
    return child

2.3 变异算子

采用inversion方法:随机选择两个索引为变异位点,将两个位点之间的数据倒置。

如:child = 【1、2、3、4、5、6、7、8、9】

选择变异位点为【2,5】

mutation

变异后:

变异后

算法思想:对子代的每一个个体进行概率性变异。若生成的随机数小于设定的变异率,则进行变异。若变异后的个体劣于变异前的个体,则拒绝该个体的变异,保持原状(接受法则)。

代码实现:

def mutation(children,mutation_rate):
    '''
    子代变异
    '''
    for i in range(len(children)):
        if random.random() < mutation_rate:
            child = children[i]
            new_child = child[:]
            index = sorted(random.sample(indexs,2))
            L = index[1] - index[0] + 1
            for j in range(L):
                new_child[index[0]+j] = child[index[1]-j]
            path = [origin] + child + [origin]
            a,b = index[0] + 1,index[1] + 1
            d1 = dis[path[a-1]-1][path[a]-1] + dis[path[b]-1][path[b+1]-1]
            d2 = dis[path[a-1]-1][path[b]-1] + dis[path[a]-1][path[b+1]-1]
            if d2 < d1:#只接受优良变异
                children[i] = new_child

    return children

此外,在程序中父代将进行整体变异(mutation_rate=1),变异仍然遵守接受法则。

2.4 将种群的个体按照里程排序,并返回当前种群中的最优个体及其里程

def get_best_current(population):
    '''
    将种群的个体按照里程排序,并返回当前种群中的最优个体及其里程
    '''
    graded = [[route_mile_cost(x),x] for x in population]
    graded = sorted(graded)
    population = [x[1] for x in graded]
    return graded[0][0],graded[0][1],population

2.5 设置种群数,变异概率及其进化次数

population_size = 100 #种群数
mutation_rate = 0.2 #变异概率
iter_count = 1000 #进化次数

2.6 主函数

  • 流程图
GA
  • 代码实现
def main(iter_count):
    #初始化种群
    population = [greedy_initial_route(remain_cities)]
    # population = []
    for i in range(population_size-1):
        #随机生成个体
        individual  = remain_cities[:]
        random.shuffle(individual)
        population.append(individual)
    mile_cost,result,population = get_best_current(population)
    record = [mile_cost] #记录每一次繁殖的最优值
    i = 0
    while i < iter_count:
        #选择繁殖个体群
        parents = selection(population)
        #交叉繁殖
        target_count = population_size - len(parents) #需要繁殖的数量(保持种群的规模)
        children = []
        while len(children) < target_count:
            parent1,parent2 = random.sample(parents,2)
            child1 = CPX(parent1,parent2)
            child2 = CPX(parent2,parent1)
            children.append(child1)
            children.append(child2)
        #父代变异
        parents = mutation(parents,1)
        #子代变异
        children = mutation(children,mutation_rate)
        #更新种群
        population = parents + children
        #更新繁殖结果
        mile_cost,result,population = get_best_current(population) 
        record.append(mile_cost) #记录每次繁殖后的最优解
        i += 1
    route = [origin] + result + [origin]
    return route,mile_cost,record
  • 绘制进化过程图
def fig():
    time_start = time.time()
    N = 1000 #进化次数
    satisfactory_solution,mile_cost,record = main(N)
    time_end = time.time()
    time_cost = time_end - time_start
    print('time cost:',time_cost)
    print("优化里程成本:%d" %(int(mile_cost)))
    print("优化路径:\n",satisfactory_solution)
    #绘制路线图
    X = []
    Y = []
    for i in satisfactory_solution:
        x = city_location[i-1][0]
        y = city_location[i-1][1]
        X.append(x)
        Y.append(y)
    plt.plot(X,Y,'-o')
    plt.title("satisfactory solution of TS:%d"%(int(mile_cost)))
    plt.show()
    #绘制迭代过程图
    A = [i for i in range(N+1)]#横坐标
    B = record[:] #纵坐标
    plt.xlim(0,N)
    plt.xlabel('进化次数',fontproperties="SimSun")
    plt.ylabel('路径里程',fontproperties="SimSun")
    plt.title("solution of GA changed with evolution")
    plt.plot(A,B,'-')
    plt.show()

3 实验结果分析

对berlin52,在不同的种群数和进化次数下每组做10次重复实验,得出组内平均gap值以及程序平均运行时间如下:

image-20200627103000717
平均gap值
image-20200627104223655
程序平均运行时间(秒)

==结果分析:==在进化次数相同的情况下,随着种群数的增加,GA的最终结果往往更趋近于最优解。种群数相同的情况下,进化次数的增加并不一定能够改善GA结果。这意味着在进化后期,算法陷入了局部最优。当然,无论种群数的增加还是进化次数的增加都会导致程序运行时间的增加。

以ch150为例,以下结果为GA运算中得出的ch150算例最好的满意解gap值为1.52%

image-20200624214027690
GA搜索路径结果
image-20200624214140208
GA进化过程

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nufS9CVa-1593592122144)(https://i.loli.net/2020/06/24/vn14rVskaoKzGgC.png)]

==结果分析:==GA算法中目标函数值(路径里程)刚开始下降得非常迅速,后期趋于平稳下降,随着进化次数的增加,目标函数值逐渐降低。而GA进化过程图呈现阶梯状的形式,表明在一定的进化代数内,程序陷入了局部最优。GA算法的效果与选择算子,交叉算子和变异算子密切相关,我曾尝试交叉算子采用OX,但是进化效果却远远不如本次实验最终采用的CPX。此外算法的效果还受到种群数和进化次数的影响。

4 附python源码(完整版)

import math,random,time
import matplotlib.pyplot as plt
#读取坐标文件
filename = '算例\\berlin52.txt' 
city_num = [] #城市编号
city_location = [] #城市坐标
with open(filename, 'r') as f:
    datas = f.readlines()[6:-1]
for data in datas:
    data = data.split()
    city_num.append(int(data[0]))
    x = float(data[1])
    y = float(data[2])
    city_location.append((x,y))#城市坐标
city_count = len(city_num) #总的城市数
origin = 1 #设置起点和终点
remain_cities = city_num[:] 
remain_cities.remove(origin)#迭代过程中变动的城市
remain_count = city_count - 1 #迭代过程中变动的城市数
indexs = list(i for i in range(remain_count))
#计算邻接矩阵
dis =[[0]*city_count for i in range(city_count)] #初始化
for i in range(city_count):
    for j in range(city_count):
        if i != j:
            dis[i][j] = math.sqrt((city_location[i][0]-city_location[j][0])**2 + (city_location[i][1]-city_location[j][1])**2)
        else:
            dis[i][j] = 0

def route_mile_cost(route):
    '''
    计算路径的里程成本
    '''
    mile_cost = 0.0
    mile_cost += dis[0][route[origin-1]-1]#从起始点开始
    for i in range(remain_count-1):#路径的长度
        mile_cost += dis[route[i]-1][route[i+1]-1]
    mile_cost += dis[route[-1]-1][origin-1] #到终点结束
    return mile_cost

#获取当前邻居城市中距离最短的1个
def nearest_city(current_city,remain_cities):
    temp_min = float('inf')
    next_city = None
    for i in range(len(remain_cities)):
        distance = dis[current_city-1][remain_cities[i]-1]
        if distance < temp_min:
            temp_min = distance
            next_city = remain_cities[i]
    return next_city

def greedy_initial_route(remain_cities):
    '''
    采用贪婪算法生成初始解:从第一个城市出发找寻与其距离最短的城市并标记,
    然后继续找寻与第二个城市距离最短的城市并标记,直到所有城市被标记完。
    最后回到第一个城市(起点城市)
    '''
    cand_cities = remain_cities[:]
    current_city = origin
    initial_route = []
    while len(cand_cities) > 0:
        next_city = nearest_city(current_city,cand_cities) #找寻最近的城市及其距离
        initial_route.append(next_city) #将下一个城市添加到路径列表中
        current_city = next_city #更新当前城市
        cand_cities.remove(next_city) #更新未定序的城市
    return initial_route

#物竞天择,适者生存
def selection(population):
    '''
    选出父代个体
    '''
    M = population_size
    parents = []
    for i in range(M):
        if random.random() < (1 - i/M):
            parents.append(population[i])
    return parents
def CPX(parent1,parent2):
    '''
    交叉繁殖:CX与PX的混合双亲产生两个子代
    '''
    cycle = []
    start = parent1[0]
    cycle.append(start)
    end = parent2[0]
    while end != start:
        cycle.append(end)
        end = parent2[parent1.index(end)]
    child = parent1[:]
    cross_points = cycle[:]
    if len(cross_points) < 2 :
        cross_points = random.sample(parent1,2)
    k = 0
    for i in range(len(parent1)):
        if child[i] in cross_points:
            continue
        else:
            for j in range(k,len(parent2)):
                if parent2[j] in cross_points:
                    continue
                else:
                    child[i] = parent2[j]
                    k = j + 1
                    break   
    return child

#变异
def mutation(children,mutation_rate):
    '''
    子代变异
    '''
    for i in range(len(children)):
        if random.random() < mutation_rate:
            child = children[i]
            new_child = child[:]
            index = sorted(random.sample(indexs,2))
            L = index[1] - index[0] + 1
            for j in range(L):
                new_child[index[0]+j] = child[index[1]-j]
            path = [origin] + child + [origin]
            a,b = index[0] + 1,index[1] + 1
            d1 = dis[path[a-1]-1][path[a]-1] + dis[path[b]-1][path[b+1]-1]
            d2 = dis[path[a-1]-1][path[b]-1] + dis[path[a]-1][path[b+1]-1]
            if d2 < d1:
                children[i] = new_child

    return children

def get_best_current(population):
    '''
    将种群的个体按照里程排序,并返回当前种群中的最优个体及其里程
    '''
    graded = [[route_mile_cost(x),x] for x in population]
    graded = sorted(graded)
    population = [x[1] for x in graded]
    return graded[0][0],graded[0][1],population

population_size = 100 #种群数
mutation_rate = 0.2 #变异概率
def main(iter_count):
    #初始化种群
    population = [greedy_initial_route(remain_cities)]
    # population = []
    for i in range(population_size-1):
        #随机生成个体
        individual  = remain_cities[:]
        random.shuffle(individual)
        population.append(individual)
    mile_cost,result,population = get_best_current(population)
    record = [mile_cost] #记录每一次繁殖的最优值
    i = 0
    while i < iter_count:
        #选择繁殖个体群
        parents = selection(population)
        #交叉繁殖
        target_count = population_size - len(parents) #需要繁殖的数量(保持种群的规模)
        children = []
        while len(children) < target_count:
            parent1,parent2 = random.sample(parents,2)
            child1 = CPX(parent1,parent2)
            child2 = CPX(parent2,parent1)
            children.append(child1)
            children.append(child2)
        #父代变异
        parents = mutation(parents,1)
        #子代变异
        children = mutation(children,mutation_rate)
        #更新种群
        population = parents + children
        #更新繁殖结果
        mile_cost,result,population = get_best_current(population) 
        record.append(mile_cost) #记录每次繁殖后的最优解
        i += 1
    route = [origin] + result + [origin]
    return route,mile_cost,record

def fig():
    time_start = time.time()
    N = 1000 #进化次数
    satisfactory_solution,mile_cost,record = main(N)
    time_end = time.time()
    time_cost = time_end - time_start
    print('time cost:',time_cost)
    print("优化里程成本:%d" %(int(mile_cost)))
    print("优化路径:\n",satisfactory_solution)
    #绘制路线图
    X = []
    Y = []
    for i in satisfactory_solution:
        x = city_location[i-1][0]
        y = city_location[i-1][1]
        X.append(x)
        Y.append(y)
    plt.plot(X,Y,'-o')
    plt.title("satisfactory solution of TS:%d"%(int(mile_cost)))
    plt.show()
    #绘制迭代过程图
    A = [i for i in range(N+1)]#横坐标
    B = record[:] #纵坐标
    plt.xlim(0,N)
    plt.xlabel('进化次数',fontproperties="SimSun")
    plt.ylabel('路径里程',fontproperties="SimSun")
    plt.title("solution of GA changed with evolution")
    plt.plot(A,B,'-')
    plt.show()
    return mile_cost,time_cost

# fig()
   
# record1 = [0]*10
# record2 = [0]*10
# for i in range(10):
#     record1[i],record2[i] = fig()
# print(min(record1))
# print(sum(record1)/10)
# print(record1)
# R = 10
# Mcosts = [0]*R
# Tcosts = [0]*R
# for j in range(R):
#     Mcosts[j],Tcosts[j] = fig()
# AM = sum(Mcosts)/R #平均里程
# AT = sum(Tcosts)/R #平均时间
# print("最小里程:",min(Mcosts))
# print("平均里程:",AM)
# print('里程:\n',Mcosts)
# print("平均时间:",AT)

热门文章

暂无图片
编程学习 ·

性能优化总结

性能优化方向流畅(启动速度、卡顿) 稳定(内存泄漏、崩溃) 功耗(耗电、网络) 安装包(包体积)一、 流畅 卡顿优化 1、 布局优化简单布局使用Java代码代替布局文件 Android加载Xml布局文件,并将其转换成View,需要经历XML解析,使用Java代码直接创建View可以省去这一过程使用标签…
暂无图片
编程学习 ·

提高复杂网络分析效率!中国科学家研发强化学习新框架

提高复杂网络分析效率!中国科学家研发强化学习新框架近日,中国国防科技大学、美国加州大学洛杉矶分校和哈佛医学院的研究人员研发了一个深度强化学习框架FINDER。相比于现有的解决方案,FINDER能够更快速、更高效地找到复杂网络中一组最关键的节点,进而使复杂网络以较高的效…
暂无图片
编程学习 ·

Vue&Element

Vue&Element Vue 快速入门 Vue 介绍Vue 是一套构建用户界面的渐进式前端框架。 只关注视图层,并且非常容易学习,还可以很方便的与其它库或已有项目整合。 通过尽可能简单的 API 来实现响应数据的绑定和组合的视图组件。 特点 易用:在有 HTML CSS JavaScript 的基础上,快…
暂无图片
编程学习 ·

解决vue项目在IE中请求缓存的问题

IE中如果本次请求和上次请求一样,会优先使用缓存我碰到的问题是,我删除了某列的数据,需要重新刷新列表,但是删除成功以后重新请求IE优先使用了缓存解决方法就是在每个url上添加一个随机数,使得每次请求不一样,就不存在缓存问题了PS:垃圾IE
暂无图片
编程学习 ·

一文详解土地增值税

在房地产开发的各个环节,所缴纳的税费不尽相同。其中在商品房销售环节需缴纳的税费比较多,土地增值税是一个主要税种,对企业来说负担比较重,涉及政策也比较复杂。如何确定土地增值税的纳税义务人,明确征税行为和范围;营改增后,土地增值税在应税收入、扣除项目金额、税款预…
暂无图片
编程学习 ·

Java使用poi将office文件转为html

一、前言 功能需求:上传office文档,并提供文件在线预览。 解决方案:使用Aspose.cells.jar包,将文档转换为pdf格式; 使用libreOffice,将文档转换为pdf格式; 使用poi将文档转换为html格式。方案一:通过Aspose的方式,该功能是付费版,需要破解,所以是能抛弃。 方案二,使…
暂无图片
编程学习 ·

程序员,职场上请远离这种人!

对有些职场人来讲,甩锅就是一种生存手段。01.从大学打篮球说起上大学的时候喜欢打篮球,然后我又特别喜欢抢篮板,经常是跳起来的时候没事,落下来的时候偶尔会踩到别人的脚上,于是左脚经常性崴脚,这是背景。我们班上有一个同学也喜欢打篮球,我俩水平都差不多因此也算能玩在…
暂无图片
编程学习 ·

Spring Boot, MySQL, JPA, Hibernate Restful CRUD API Tutorial

Spring Boot MySQL JPA Hibernate Restful CRUD API TutorialSpring Boot has taken Spring framework to the next level. It has drastically reduced the configuration and setup time required for spring projects. Spring Boot将Spring框架提升到了一个新的高度。它大大…
暂无图片
编程学习 ·

java面试-JVM内存区域划分

JVM内存划分说到Java内存区域,刚开始接触java的人会下意识说出“堆栈”。这里要明确堆栈不是一个概念,而是两个概念,堆和栈是两块不同的内存区域,简单理解的话,堆是用来存放对象而栈是用来执行程序的。其次,堆内存和栈内存的这种划分方式比较粗糙,这种划分方式只能说明大…
暂无图片
编程学习 ·

Java设计模式-5.适配器设计模式

在使用监听器的时候,需要定义一个类事件监听器接口,通常接口中有多个方法,而程序中不一定都用到,但又必须重写很繁琐,定义监听器时只要继承适配器,然后重写需要的方法。 适配器原理:适配器就是一个类,实现了监听器接口,所有抽象方法都重写了,但是方法都是空的,只重写…
暂无图片
编程学习 ·

2020年了,还不懂数据挖掘?数据挖掘工具有哪些?

一. 数据挖掘定义二. 数据挖掘特征三. 数据挖掘工具1 Weka2 SPSS3 Clementine4 RapidMiner5 其他数据挖掘软件一. 数据挖掘定义数据挖掘:严格的科学定义上,数据挖掘是从大量的、有噪声的、不完全的、模糊和随机的数据中,提取出隐含在其中的、人们事先不知道的、具有潜在利用…
暂无图片
编程学习 ·

Z字型变换(Go,LeetCode)

目录题目描述解决方案代码代码走读传送门题目描述将一个给定字符串根据给定的行数,以从上往下、从左到右进行Z字形排列。比如输入字符串为 LEETCODEISHIRING ,行数为3时,排列如下:L C I R E T O E S I I G E D H N之后,你的输出需要从左往右逐行读取,产生出一…
暂无图片
编程学习 ·

LeetCode 58. 最后一个单词的长度

目录结构1.题目2.题解2.1java split()函数2.2字符串遍历1.题目给定一个仅包含大小写字母和空格 的字符串 s,返回其最后一个单词的长度。如果字符串从左向右滚动显示,那么最后一个单词就是最后出现的单词。如果不存在最后一个单词,请返回 0 。说明:一个单词是指仅由字母组…
暂无图片
编程学习 ·

贪心算法经典例题

贪心算法:每次都取最佳 牛吃草 链接:https://ac.nowcoder.com/acm/problem/24867 来源:牛客网 Each of Farmer John’s N (1 <= N <= 50,000) cows likes to graze in a certain part of the pasture, which can be thought of as a large one-dimeensional number li…
暂无图片
编程学习 ·

大厂程序员因厌恶编程,辞去月薪2w+的工作去当司机?

世界好小啊,刚在一个 UP 主的群里看到一个视频,标题叫做:“失业了工作没找到,却稀里糊涂上了知乎热搜,2000 多万人围观,我…” 说实话,看到视频的封面,我的下巴当时就掉到了手机上,这不就是知乎热搜上那个视频的猪脚嘛——热搜的标题叫做“如何看待互联网大厂程序员因…
暂无图片
编程学习 ·

weblogic部署的项目代码自动更新

weblogic的项目如果放在非autodeploy目录下,如何实现启动服务后代码自动生效。 解决方案:将Servers下面的cache、tmp、stage删除后,启动服务,代码会重新同步到stage下,这样就不用在weblogic控制台里去更新项目了。
暂无图片
编程学习 ·

SpringBooot框架整合MyBatis框架

SpringBooot框架整合MyBatis框架 1.MyBatis框架概述 Mybatis是一个优秀的持久层框架,底层基于JDBC实现与数据库的交互。并在JDBC操作的基础上做了封装和优化,它借助灵活的SQL定制,参数及结果集的映射方式,更好的适应了当前互联网技术的发展 2.初始配置 2.1.在pom.xml文件中…