使用Python 实现 遗传算法 解决TSP问题

发布于 2019-09-17  212 次阅读


1.问题描述

假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。

2.各个模块

1.初始化种群

这个是创造第一波种群的函数,初始化种群的函数,并且把随机出来的种群保存在列表当中。

def initial_gene(population_size,city):
    #这个是创造第一波种群的函数,初始化种群的函数
    gene = []
    for i in range(population_size):
        temporary = []
        for j in range(city):
            temporary.append(j)
        random.shuffle(temporary)
        gene.append(temporary)
    return gene
#其实我们可以把面向过程变成提升成 面向对象编程

由于没有使用 Numpy ,使用纯列表运算,因此运算速度相比 C语言来说 有所下降
同时 我们使用 自然数(1~city) 来代表城市,种群的基因就是由 自然数来表示。

2.RNA翻译

path = [[6734,1453],[2233,10],[5530,1424],[401,841],[3082,1644],[7608,4458],[7573,3716],
        [7265,1268],[6898,1885],[1112,2049],[5468,2606],[5989,2873],[4706,2674],
        [4612,2035],[6347,2683],[6347,2683],[6107,669],[7611,5184],[7462,3590],
        [7732,4723],[5900,3561],[4483,3369],[6101,1110],[5199,2182],[1633,2809],
        [4307,2322],[675,1006],[7555,4819],[7541,3981],[3177,756],[7352,4506],
        [7545,2801],[3245,3305],[6426,3173],[4608,1198],[23,2216],[7248,3779],
        [7762,4595],[7392,2244],[3484,2829],[6271,2135],[4985,140],[1916,1569],
        [7280,4899],[7509,3239],[10,2676],[6807,2993],[5185,3258],[3023,1942]]

我们通过 path 列表保存了各个城市的坐标和索引值,这样就可以使得 DNA中的自然数 被tRna翻译成 City的各个点坐标二维数组

def abjust(path,gene):
    #这是传入地图信息和原始基因,并通过地图信息讲基因翻译成点的坐标
    list = []

    for gene_list in gene:
        temporay = []
        for i in gene_list:
            temporay.append(path[i])
        list.append(temporay)
    return list

这样我们就得到了包含CITY顺序的二维坐标点的 列表

翻译成PRO

我们拥有了包含坐标点的列表后,我们就可以通过

import math
s = math.sqrt((x1-x2)**2 + (y1-y2)**2)

这样就可以求出两个点之间的坐标了,通过遍历整个列表,将这个mRNA 翻译成PRO 这个蛋白质表现出来的性状 就是总距离。
一下是翻译成PRO的函数

def abjust(path,gene):
    #这是传入地图信息和原始基因,并通过地图信息讲基因翻译成点的坐标
    list = []

    for gene_list in gene:
        temporay = []
        for i in gene_list:
            temporay.append(path[i])
        list.append(temporay)
    return list

优胜劣汰--自然选择

当我们计算完当前种群的全部PRO后,我们就要通过选择,将总距离的淘汰,总距离的保存下来,让它们繁衍,产生第二代。
我们在这里选用 轮盘赌方法 进行挑选。

def slect(pro,gene,population_size):
    #这个函数是通过轮盘赌的方式将基因基因挑选出来
    #传入已经翻译的基因
    s = 0
    P = 0
    gene_c=[]
    gene_child = []
    slect_gene = []
    for i in pro:
        s += (1/i)**2
    for j in pro:
        p = (1/j)**2 / s
        slect_gene.append(p)
    while P=ran):
                gene_c.append(i)
            i += 1
        P += 1
    for g in gene_c:
        gene_child.append(gene[g])
    return gene_child

此处要插入图片

5.繁衍出下一代

通过选出的gene,是他们交叉互换各自的一段DNA

def XXOO(parents,population_size,city):
    #这是用于将已经选择出来的基因,让两个基因生四个孩子基因
    x = 0
    child_sum=[]
    i = random.randint(0,city-1)
    child = parents[0][:i+1]
    while (x

你知道雪为什么是白色的吗?因为她忘记了原来的颜色