遗传算法(Genetic Algorithm, GA),是一种通过模拟生物自然进化过程的随机搜索算法,主要思想是模拟生物进化论中自然选择和遗传学机理的生物进化过程。废话不多说,看看具体的实现过程。
这里列出几个算法的名词及定义:
基本操作:
花里胡哨一大堆,遗传算法核心思想说白了就一句话:把优秀的基因传递下去。换句话说,局部最优解不一定是最优解,但最优解一定是局部最优的,也就是说最优解一定包含了优秀的“基因”(这也是遗传算法最精髓的一点,很好的体现了“进化”的思想)
GA流程图:
Python代码:
import numpy as np
import random,time
import matplotlib.pyplot as plt
from GetData import *
class GA():
def __init__(self,disMatrix,MaxGens,pop_size,cross_rate,mutation_rate):
"pop_size > 1 "
self.disMatrix = disMatrix
self.gene_size = len(disMatrix) # 基因长度,路径长度,0为Depot
self.pop_size = pop_size #种群大小,每一代解的数量
self.MaxGens = MaxGens #最大迭代次数
self.cross_rate = cross_rate #交叉概率
self.mutation_rate = mutation_rate #变异概率
def get_init_solution(self):
init_routes = np.array([])
route = np.arange(1,self.gene_size) # 生成初始解
for i in range(self.pop_size):
np.random.shuffle(route)
init_routes = np.append(init_routes,route)
return init_routes.reshape(self.pop_size,self.gene_size-1).astype(int)
def get_route_distance(self,route):
routes = list(route)
routes = [0] + routes +[0]
total_distance = 0
for i,n in enumerate(routes):
if i != 0 :
total_distance = total_distance + self.disMatrix[last_pos][n]
last_pos = n
return total_distance
def get_fitness(self,pop_routes):
fitness = []
for route in pop_routes:
fitness.append(self.get_route_distance(route))
fitness = 1 - fitness/np.sum(fitness) # 归一化后取反
return np.array(fitness)
def select(self,pop_routes):
fitness = self.get_fitness(pop_routes)
#轮盘赌的形式进行选择,适应度高的被选中的概率就大
selected_label = np.random.choice(range(self.pop_size), size=self.pop_size, replace=True, p=fitness/np.sum(fitness))
return pop_routes[selected_label]
def crossover(self,pop_routes):
for i in range(self.pop_size):
if np.random.rand() < self.cross_rate :
obj = pop_routes[np.random.randint(self.pop_size)] #随机选一个交叉对象,也可以选到自己,生成新的一代
cross_point = np.random.randint(self.gene_size) #在DNA片段中随机选一个交叉点
new_one = np.hstack((pop_routes[i][0:cross_point],obj[cross_point::])) #从交叉点往后交换基因片段
if len(set(new_one)) < self.gene_size-1 : #交换片段后可能是无效解,即有重复元素,处理一下
new_one__ = []
for num in new_one:
if num not in new_one__:
new_one__.append(num)
else:
for j in range(1,self.gene_size):
if j not in new_one__:
new_one__.append(j)
pop_routes[i] = new_one__
continue
pop_routes[i] = new_one
return pop_routes
def mutate(self,pop_routes):
for i in range(self.pop_size):
if np.random.rand() < self.mutation_rate :
pos1 = np.random.randint(0,self.gene_size-1) # 随机选取某一个基因位置发生变异
pos2 = np.random.randint(0,self.gene_size-1)
pop_routes[i][pos1],pop_routes[i][pos2] = pop_routes[i][pos2],pop_routes[i][pos1] #交换位置,完成变异
return pop_routes
def ga_evolution(self):
routes = self.get_init_solution() #生成初始解
result=[] #记录迭代过程中的信息
while(self.MaxGens):
self.MaxGens -=1
routes = self.select(routes)
routes = self.crossover(routes)
routes = self.mutate(routes)
result.append(max(self.get_fitness(routes))) #记录一下迭代过程中的信息
plt.plot(range(len(result)),result)
plt.show()
idx = np.where(self.get_fitness(routes)==max(self.get_fitness(routes))) #挑出适应度最大的,可能不止一个
best_id = random.sample(list(idx[0]), 1) #从中拿一个
best_route = routes[best_id]
return np.squeeze(best_route).tolist()
if __name__ == "__main__":
data=GetData()
solomon_data = data.read_solomon(path ='R101.txt',customerNum=7) #定义多少个点
dismatrix = data.get_euclidean_distance_matrix(solomon_data.locations)
ga = GA(disMatrix=dismatrix,MaxGens=500,pop_size=100,cross_rate=0.3,mutation_rate=0.1)
best_route = ga.ga_evolution()
print('best_route:',best_route)
print('best distance:',ga.get_route_distance(best_route))
data.plot_route(solomon_data.locations,[0]+best_route+[0])
GetData.py 文件可在我的github或运小筹github上下载。R101.txt 为solomon数据集
结果:
这是最最最简单的实现,运行完你会发现好像每次运行结果都不太一样,有时候效果不是很好,尤其点数稍微增加... 4个参数需要反复调整,很是麻烦。
ga = GA(disMatrix=dismatrix,MaxGens=500,pop_size=100,cross_rate=0.3,mutation_rate=0.1)
在众多元启发式算法中遗传算法算是最灵活的一种了,可操作性高,适用各类问题,非常巧妙的模拟了生物“进化”的思想。GA虽然名字看起来花里胡哨,本质其实就是蒙特卡洛搜索。这里抛开花里胡哨的名字,看看每一步操作背后的含义。
def get_fitness(self,pop_routes):
fitness = []
for route in pop_routes:
fitness.append(self.get_route_distance(route))
fitness = 1 - fitness/np.sum(fitness) # 归一化后取反
return np.array(fitness)
def select(self,pop_routes):
fitness = self.get_fitness(pop_routes)
#轮盘赌的形式进行选择,适应度高的被选中的概率就大
selected_label = np.random.choice(range(self.pop_size), size=self.pop_size, replace=True, p=fitness/np.sum(fitness))
return pop_routes[selected_label]
self.cross_rate
对部分基因片段交换。当然,改进的地方有很多,比如换一种基因交换方式,增加领域搜索效率;不采用固定概率,用动态的概率对动态大小的基因片段进行交换。 def crossover(self,pop_routes):
for i in range(self.pop_size):
if np.random.rand() < self.cross_rate :
obj = pop_routes[np.random.randint(self.pop_size)] #随机选一个交叉对象,也可以选到自己,生成新的一代
....
有很多交叉方法,具体问题可根据问题特征进行设计或查阅相关文献例如:部分匹配法(Partially Matching Crossover, PMX) 循环交叉法(Cycle Crossover, CX) 次序交叉法1(Order Crossover, OX1) 次序交叉法2(Order Crossover, OX2) 基于位置的交叉法(Position Based Crossover, POS) 交替位置交叉法(Alternating Position Crossover,APX)
GA有其独特的优点:
局限性:
此外,也还有很多变种的遗传算法,如hybrid genetic algorithm,主要思想是设计可行种群和不可行种群,分别给予奖惩,这样做的好处是可以扩大种群多样性,从而避免局部最优。