遗传算法
遗传算法是根据生物学的种群进化规律推导出来的随机化搜索算法
物竞天择 适者生存
在种群的进化过程当中，基因型决定表现型，而表现型则取决于当前生物能不在很好的在这个环境中生活下去，表现型不好的被淘汰(死亡)，表现型好的则生存下来，产生后代，将决定适应该环境的良好的基因遗传下去。在生物遗传演化当中，有遗传变异，变异是产生新物种的前提，同理，在算法当中，遗传变异产生新的表现型，而环境选择表现型，所以在经过无数次代数以后，物种的表现型趋于稳定，基因型相似，在算法中的表现就是，最后你所找到的最优序列或者说种群的数字编码趋向于一个数（收敛）
图片解释：
遗传算法的图解
用遗传算法解决商旅旅行的问题
商旅问题（Travel-Salesman Problem，TSP）：
设有n个可以相互直达的城市，某推销商准备从A城处罚，周游一圈以后，回到A城，要求为推销商规划一条最短的旅行线路。使用遗传算法
输入：
一个n*n半角矩阵Ai=j=0，定义两城市之间距离
A：两城市之间距离矩阵
以0到n-1表示A0到An-1 n个城市
现在应该是编码选择：两种，二进制和数值类型
此方法选择以数组保持先后到城市顺序【0，2，1】表示从A出发然后到A->A0->A2->A1->A
设置初始种群，就是生成Max个城市序列：
然后评价种群中的个体适应度，在本算法当中就是距离最短
选择两个最长的将其淘汰掉
选择距离最短的两个序列进行交叉和变异，交叉和变异都是有一定的概率
然会将新产生的两个个体加入原来种群，交叉变异之前的依然保留
然后构建一个新的种群，进行适应度选择评估，选择计算交叉变异
不断循环这个过程，直到找到解空间稳定
代码：
import random
import numpy as np
class geneticTravel():
def __init__(self):
self.distance_matix=self.inputDis();#初始化地图
self.maxNum=3#表示要走的城市个数是maxnum=,则总共有4个城市
self.populationNum=int(self.maxNum*(self.maxNum-1)/2)*2#种群数量
self.population=self.infoPopulation()#初始化种群
self.crossPro=0.7#只定义了交叉，暂时不考虑变异
#定义快排
def QuickSort(self,myList,myOtherList, start, end):
# 判断low是否小于high,如果为false,直接返回
if start < end:
i, j = start, end
base = myList[i]
base1= myOtherList[i]
while i < j:
# 如果列表后边的数,比基准数大或相等,则前移一位直到有比基准数小的数出现
while (i < j) and (myList[j] >= base):
j = j - 1
# 如找到,则把第j个元素赋值给第个元素i,此时表中i,j个元素相等
myList[i] = myList[j]
myOtherList[i] = myOtherList[j]
# 同样的方式比较前半区
while (i < j) and (myList[i] <= base):
i = i + 1
myList[j] = myList[i]
myOtherList[j] = myOtherList[i]
# 做完第一轮比较之后,列表被分成了两个半区,并且i=j,需要将这个数设置回base
myList[i] = base
myOtherList[i]= base1
# 递归前后半区
self.QuickSort(myList,myOtherList, start, i - 1)
self.QuickSort(myList,myOtherList, j + 1, end)
return myList
#定义距离矩阵,这个要从txt文件当中读取
def inputDis(self):
A = [[1,0,0], [1, 2,0], [1, 2, 3]]
return A
#初始化种群数，一共是maxNum！个城市，现在产生int（maxNum*(maxNUm-1)/2）*2个个体
def infoPopulation(self):
#随机产生populationNum个个人,每个都是0-maxNum的随机序列
temp=[]
for i in range(self.populationNum):
temp.append(list(np.random.permutation(range(self.maxNum))))
return temp
def max_list(self,lt):
temp = 0
max_str=lt[0]
temp-0
for i in lt:
if lt.count(i) > temp:
max_str = i
temp = lt.count(i)/len(lt)
return max_str,temp
#判断种群是否稳定
def judge(self):#还未写
max_str,pro=self.max_list(self.population)
print(pro)
if pro>0.3:
return max_str,True
else:
return max_str,False
def coutDistance(self,disList):
dis=self.distance_matix[disList[0]][0]
for i in range(len(disList)-1):
max1=max(disList[i],disList[i+1])
min1 = min(disList[i],disList[i+1])
dis+=self.distance_matix[max1][min1]
dis+=self.distance_matix[disList[len(disList)-1]][0]
return 0
#评价种群当中的个体适应度,并排序
def individualFitness(self):
#遍历每一个解决方案，进行排序
dis=[]
for i in range(self.populationNum):
dis.append(self.coutDistance(self.population[i]))
#现在要做的是根据距离排序
self.QuickSort(dis,self.population,0,len(dis)-1)
#这个地方应该是交叉变异，现在只考虑交叉
def crossoveVariation(self,list1,list2):
#交叉的主要随机产生连个不相同的数字maxNum/2,a,b,将a,换成a+b，将a+b换成a
a=random.randint(0,(int(self.maxNum/2)))
b = random.randint(0, int(self.maxNum/2))
for i in range(self.maxNum):
if list1[i]==a:
list1[i]=a+b
if list1[i]==a+b:
list1[i]=a
if list2[i]==a:
list2[i]=a+b
if list2[i]==a+b:
list2[i]=a
return list1,list2
def solve(self):
#当种群稳定是结束
judge=False
while not judge:
answer,judge=self.judge()
#如果种群不稳定，进行遗传演变
self.individualFitness()
#选择最前面两个进行交叉变异，将最后产生的结果把最后两个换掉
new1,new2=self.crossoveVariation(self.population[0],self.population[1])
self.population[self.populationNum-1]=new1
self.population[self.populationNum - 1] = new2
print(answer)
···
主函数
if __name__ == '__main__':
A=geneticTravel()
print("1111:"+str(A.population))
A.solve()
print(1111)
结果：
E:\Anaconda\python.exe F:/CODE/PYTHON/510466/geneticTravel.py
1111:[[0, 2, 1], [0, 1, 2], [0, 2, 1], [0, 1, 2], [0, 2, 1], [0, 2, 1]]
0.6666666666666666
[0, 2, 1]
1111
Process finished with exit code 0
