遗传算法 - 掘金

遗传算法 (Genetic Algorithm, GA) 是由 John Holland 提出，其学生 Goldberg 对整个算法进行了进一步完善。算法的整个思想来源于达尔文的进化论，其基本思想是根据问题的目标函数构造一个适应度函数 (Fitness Function)，对于种群中的每个个体 (即问题的一个解) 进行评估 (计算适应度)，选择，交叉和变异，通过多轮的繁殖选择适应度最好的个体作为问题的最优解。算法的整个流程如下所示：

一、初始化种群

在初始化种群时，我们首先需要对每一个个体进行编码，常用的编码方式有二进制编码，实值编码等。以二进制为例，对于 $p∈{0,1,…,100}$ 中 $p_i=50$ 可以表示为：

x_i=50_{10}=0110010_2

对于一个具体的问题，我们需要选择合适的编码方式对问题的解进行编码，编码后的个体可以称之为一个染色体。则一个染色体可以表示为：

x=(p_1,p_2,…,p_m)

其中， $m$ 为染色体的长度或编码的位数。初始化种群个体共 $n$ 个，对于任意一个个体染色体的任意一位 $i$ ，随机生成一个随机数 $rand∈U(0,1)$ ，若 $rand>0.5$ ，则 $p_i=1$ ，否则 $p_i=0$ 。

二、计算适应度

适应度为评价个体优劣程度的函数 $f(x)$ ，通常为问题的目标函数，对最小化优化问题 $f(x)=−min∑L(\hat{y},y)$ ，对最大化优化问题 $f(x)=max∑L(\hat{y},y)$ ，其中 $L$ 为损失函数。

三、选择

对于种群中的每个个体，计算其适应度，记第 i 个个体的适应度为 $F_i=f(x_i)$ 。则个体在一次选择中被选中的概率为：

P_i = \dfrac{F_i}{\sum_{i=1}^{n}{F_i}}

为了保证种群的数量不变，我们需要重复 n 次选择过程，单次选择采用轮盘赌的方法。利用计算得到的被选中的概率计算每个个体的累积概率：

CP_0=0 \\ CP_i=\sum_{j=1}^iP_i

对于如下一个示例：

指标 \ 个体	x1	x2	x3	x4	x5	x6
适应度 (F)	100	60	60	40	30	20
概率 (P)	0.322	0.194	0.194	0.129	0.097	0.064
累积概率 (CP)	0.322	0.516	0.71	0.839	0.936	1

每次选择时，随机生成 $rand∈U(0,1)$ ，当 $CP_{i−1}≤rand≤CP_i$ 时，选择个体 $x_i$ 。选择的过程如同在下图的轮盘上安装一个指针并随机旋转，每次指针停止的位置的即为选择的个体。

四、交叉

交叉运算类似于染色体之间的交叉，常用的方法有单点交叉，多点交叉和均匀交叉等。

单点交叉：在染色体中选择一个切点，然后将其中一部分同另一个染色体的对应部分进行交换得到两个新的个体。交叉过程如下图所示：

多点交叉：在染色体中选择多个切点，对其任意两个切点之间部分以概率 $P_c$ 进行交换，其中 $P_c$ 为一个较大的值，例如 $P_m=0.9$ 。两点交叉过程如下图所示：

均匀交叉：染色体任意对应的位置以一定的概率进行交换得到新的个体。交叉过程如下图所示：

五、变异

变异即对于一个染色体的任意位置的值以一定的概率 $P_m$ 发生变化，对于二进制编码来说即反转该位置的值。其中 $P_m$ 为一个较小的值，例如 $P_m=0.05$ 。

小结

在整个遗传运算的过程中，不同的操作发挥着不同的作用：

选择：优胜劣汰，适者生存。
交叉：丰富种群，持续优化。
变异：随机扰动，避免局部最优。

代码实现

# -*- coding: utf-8 -*-
import random
import math
import matplotlib.pyplot as plt
import numpy as np

#这两行代码让输出的图形中显示中文
plt.rcParams['font.sans-serif']=['SimHei']
plt.rcParams['axes.unicode_minus'] =False #减号unicode编码
import time


def initCities(firstCity):
    cities = []
    n=0

    file=open("data.txt","r", encoding='utf-8')   #读取文件
    for line in file:
        line = line.replace("\n"," ")  #替换换行符
        #print(line)
        line = line.split(",")         #按逗号分隔
        #print(line)
        cities.append([n,float(line[1]),float(line[2]),line[0]] )  #组装。集合中的每一个元组，第一个元素为城市编号（从0开始），第二三个元素为城市坐标，第四个元素为城市名字
        #print(cities)
        if line[0] == firstCity:       #判断当前城市是否为输入的城市。如果是，则将这个元组和集合的第一个元组互换位置下标，以将他放在旅行的起点
            cities[0][0]=n
            cities[n][0]=0
        n+=1
        
    cities = [x for x in sorted(cities)]   #经过位置互换后，cities集合中的编号序列不再有序，经过排序后才能真正地将输入的城市放在集合首位
  
    return cities    #返回城市列表



#求出给定个体（基因链条）（路径数组）的首元素绕一圈回到首元素所需要的路径长度   
def distance(order):
    distance = 0.0
    for i in range(len(order)-1):   #对每一组相邻的地点求距离，然后累加
        num1, num2 = order[i], order[i + 1]
        distance += city_distance[num1][num2]
    distance+=city_distance[num2][0]        #添加从最后一个城市回到原点的距离
    return distance         #返回整圈的距离



#将距离插入到lives中的首元素位置
def inserted(i):
    i.insert(0,distance(i))     
    return i




#交叉，将所选取的两个个体交叉，也就是一次性交换多个城市的位置
def cross(par1,par2):
    par1.pop(0)     #弹出首元素（此路径总长度）
    par2.pop(0)     #弹出首元素（此路径总长度）

    num1 = random.randint(2,len(par1)-1)  #选取交叉的起点
    num2 = random.randint(num1,len(par2)-1)     #选取交叉的终点
    crossGene = par2[num1:num2]     #执行交叉的片段
    #判断现在所处的位置
    flag = 0 
    Gene = []
    for life in par1:
        if flag == num1:        #到交叉的起点时，则直接添加片段crossGene到子代中。这个if语句只会执行一次
            Gene.extend(crossGene)
            flag += 1
        if life not in crossGene:   #如果当前元素不属于片段crossGene，则把它加到子代中。这个if语句会执行【个体基因长度（路径长度）-len(crossGene)】次
            Gene.append(life)
            flag += 1
    Gene=inserted(Gene)     #添加首元素（此路径总长度）
    return Gene     #返回下一代的基于（路径信息）



#变异，随机交换两个城市之间的位置
def mutation(Gene):
    gene=Gene.copy()
    num=gene.pop(0)     #弹出首元素（此路径总长度）
    #随机产生两个被交换的地点，并交换位置
    num1 = random.randint(1, len(gene)-1)
    num2 = random.randint(1, len(gene)-1)
    gene[num1],gene[num2] = gene[num2],gene[num1]       #交换动作
    gene=inserted(gene)     #添加首元素（此路径总长度）
    if gene[0]<Gene[0]:     #判断变异的效果。如果距离还没有之前短，则使这次变异无效；如果变异后距离变短了，则使这次变异生效
        return gene
    else:
        return Gene



#物竞天择，弱者死亡
#设置强者的定义概率，即种群前30%为强者
def dellist(lives):
    retain_rate=0.3     #前30%的个体绝对不会被淘汰
    num=int(retain_rate*len(lives))
    for i in range(num,len(lives)-1):   #在后70%的个体中随机淘汰三分之二的个体
        flag=random.randrange(0,3,1)
        if flag<2:       #因为flag的取值范围是[0,2]，有66.7%的可能性满足这个条件，以此达到三分之二概率的淘汰
            del lives[num-1]
    return lives





#自然选择算法
def nature(lives):
    var_time=0  #变异次数
    cro_time=0  #交叉次数（也就是一共产生多少次子代） 
    newlives1=[]
    newlives2=lives[0]

    breaktime=0
    #一共遗传1500次，越大效果越好
    for time in range(1500):
        if time == 0:
            for i in lives:
                if i != None:
                    newlives1.append(inserted(i))   #插入距离
        lives=[]
        newlives1=[x for x in sorted(newlives1)]    #对newlives1按首元素（路径总长度）排序，使得newlives1[0][0]为这一代的最优路径的总长度
       
        #ewlives2[0]初始时为lives[0][0]，一定是0，所以第一次if语句肯定不符合，会转到else中重新赋值，赋值一个上一次的最优路径。第二次判断if语句时，如果和第二次的最优路径一致，则说明出现了一次来连续的最优解
        if newlives1[0][0]==newlives2[0]:   #说明两次得到的最优解一致，成为一个连续相同的最优解。
            breaktime += 1
        else:
            breaktime = 0       #连续的最优解个数归零
            newlives2=newlives1[0]      #给newlives2赋值一个上一次的最优解（最短路径序列）。这个地方很关键，最开始的时候就纳闷为什么newlives2的值不是0了？
        if breaktime > 100 & time >= 500:   #当已经遗传到了500代之后并且有100个连续相同的最优解产生的时候进行break，说明进化的很好，不需要再进行淘汰、交叉、变异
            break
        
        
        #进行淘汰
        newlives1=dellist(newlives1)  

        num=count-len(newlives1)
        while num > 0:
            #在newlives1中随机选取两个个体进行交叉，最优的不进行
            a=random.randrange(1,len(newlives1),1)  #随机选择两个个体
            b=random.randrange(1,len(newlives1),1)
            if a!=b :
                par1=newlives1[a].copy()    #备份一下
                par2=newlives1[b].copy()    #备份一下
                life=cross(par1,par2)   #交叉
                cro_time += 1       #交叉次数加一
                #对交叉生成的子代进行变异(0.2的概率)
                flag=random.randrange(0,10,1)
                if flag<=1:     #因为flag的取值范围是[0,9]，只有20%的可能性满足这个条件，以此达到0.2的概率变异
                    newlives1.append(mutation(life))        #变异后再回到种群
                    var_time+=1     #变异次数加一
                else:
                    newlives1.append(life)      #比较幸运，免于变异，重新回到种群中生存
            num-=1

    print("遗传次数："+str(time+1))
    print("交叉次数："+str(cro_time))
    print("变异次数："+str(var_time))
    return newlives1



#firstCity=input("请输入出发城市： ")
firstCity='南京'


#读取城市信息，并计算相互间的距离
cities=initCities(firstCity)


geneLength=len(cities)
#生成距离矩阵city_distance，方便调用
city_distance=np.zeros([geneLength,geneLength])     #置零，初始化
for i in range(geneLength):
    for j in range(geneLength):
        city_distance[i][j]=math.sqrt((cities[i][1] - cities[j][1]) ** 2 +(cities[i][2] - cities[j][2]) ** 2)  #因为是用直角坐标系表示的城市的位置，所以直接使用两点距离公式



#刚开始时生成300个个体（种群数量为300）。放到大自然中
count=300
lives=[]
for i in range(count):
    aGene = [ x for x in range(1,geneLength) ]   #此时的aGene为一个从1到33的升序的数组，代表该个体的基因链条
    random.shuffle(aGene)   #将数组打乱。这个乱序，就有可能就是将来的旅行路径，当然，中间会经过进化变异
    aGene.insert(0,0)       #在数组的第一个位置插入0，表示开始的位置。此时基因的长度为34，即城市的数量
    lives.append(aGene)     #将该个体的基因保存到基因库中



#计算算法运行时间
start = time.time()
#执行繁衍进程
lives=nature(lives)  #返回的这个lives此时是一个大矩阵，每一行的第2到最后的元素为一条个体的基因链条（即候选的城市游览路线），第1个元素为该路径的长度。     并且第1个元素按列有序，即第一行为最佳路径，长度为最短长度
end = time.time()



print("运行时间："+str(end-start)+"s")
print("最优路径："+str(lives[0][1:]))
print("最短距离："+str(lives[0][0]))    #lives[0][0]代表最优路径的长度


#将cities按照lives下标的顺序排列。
list=[]
for i in lives[0][1:]:    #lives[0][1:]代表进化完后，适应性最强的那个个体的基因链条（即最优的城市游览路线） ；  lives[0][0]代表最优路径的长度
    list.append(cities[i])  #按照得到的下标，将城市加入到结果list中



print("\n遍历顺序为：")
for i in list:
    print(i[3],end=' ')     #第四个元素才为城市的名字，所以为i[3]



# 画图
p1=[]
p2=[]
p3=[]
for i in list:
    p1.append(i[1])     #横坐标
    p2.append(i[2])     #纵坐标
    p3.append(i[3])     #城市名字
p1.append(list[0][1])       #回到出发的城市，形成闭环
p2.append(list[0][2])       #回到出发的城市，形成闭环
plt.title('以'+firstCity+'为起始点的最短路线图')
plt.plot(p1,p2)  # plot绘制折线图

for i in range(len(p1)-1):    
    plt.text(p1[i],p2[i],p3[i])     #在指定的横纵坐标上标注城市名称

#显示绘图
plt.draw()  
#保存图象
plt.savefig('GA_Final.png')
plt.close()

data.txt文件内容为中国的34个城市的地理坐标：

北京,116.46,39.92
天津,117.2,39.13
上海,121.48,31.22
重庆,106.54,29.59
拉萨,91.11,29.97
乌鲁木齐,87.68,43.77
银川,106.27,38.47
呼和浩特,111.65,40.82
南宁,108.33,22.84
哈尔滨,126.63,45.75
长春,125.35,43.88
沈阳,123.38,41.8
石家庄,114.48,38.03
太原,112.53,37.87
西宁,101.74,36.56
济南,117,36.65
郑州,113.6,34.76
南京,118.78,32.04
合肥,117.27,31.86
杭州,120.19,30.26
福州,119.3,26.08
南昌,115.89,28.68
长沙,113,28.21
武汉,114.31,30.52
广州,113.23,23.16
台北,121.5,25.05
海口,110.35,20.02
兰州,103.73,36.03
西安,108.95,34.27
成都,104.06,30.67
贵阳,106.71,26.57
昆明,102.73,25.04
香港,114.1,22.2
澳门,113.33,22.13

运行结果

程序设定出发点为南京，当然，可以自定义。