优化算法-遗传算法
优化算法-遗传算法
主要参考了集体智慧编程一书
之前已经实现过优化算法中的爬山法和模拟退火法，现在我们讨论一下另一种受自然科学启发的算法：遗传算法。借鉴生物进化论，遗传算法将要解决的问题模拟成一个生物进化的过程，通过复制、交叉、突变等操作产生下一代的解，并逐步淘汰掉适应度函数值低的解，留下适应度函数值高的解。这样进化N代后就很有可能会进化出适应度函数值很高的个体。
一. 遗传算法流程
1.首先我们要初始化一组解（数量为事先设定的种群大小）。
2.现在我们要使目标函数最小，那么我们要逐步淘汰掉使目标函数值高的解，留下使目标函数值小的解，再将留下来的解通过复制、交叉、突变等操作产生下一代的解（比如我们留下使目标函数值最小的20%解，然后基于这最小的20%解复制、交叉、突变等操作产生下一代解），恢复种群原来的大小。
3.然后开始重复第二步操作，直到达到结束条件。
二. 遗传算法的基本操作
使用遗传算法需要先将问题的解进行编码。最简单的一种编码方式是二进制编码，即将问题的解编码成二进制位数组的形式。例如，问题的解是整数，那么可以将其编码成二进制位数组的形式，当然也可以直接使用这些整数作为编码（适用于解的维度比较大的情况）。
遗传算法有3个最基本的操作：选择，交叉，变异。
-
1.选择： 我们将当前种群中最优的一部分解加入其所在的新种群中，而将当前种群中不属于最优的一部分解淘汰。选取最优一般是按比例选取，这个在前文已经有了介绍。
-
2.交叉： 这种方法是在新种群中选取之前步骤加入的最优解中的两个解，然后将它们按照某种方式结合。实现交叉的简单方法是：选出两个最优解后，从一个最优解中随机选取一个数，将此数之前的值作为新解的前面元素的值，而剩余的元素来源于另一个选出的最优解。
交叉操作python实现：
# 交叉操作
# vec1和vec2是选出两个最优解
# dismension是一个解的维度len(range_list)
def crossover(vec1, vec2, dimension):
# 选出交叉位置
i = random.randint(1, dimension-2)
return vec1[0:i]+vec2[i:]- 3.变异：
通常做法是对一个已有解进行微小的、简单的、随机的改变。
变异操作python实现：
# 变异操作
# vec是要变异操作的已有解,step是变异的幅度
# range_list是一个二维list构成的列表
# range_list指定了一个解中的每个变量的最大最小值，相当于定义域
def crossover(vec, range_list, step=1):
dimension = len(range_list)
i = random.randint(1, dimension - 1)
if random.random()<0.5 and vec[i]>range_list[i][0]:
return vec[0:i] + [vec[i]-step] + vec[i+1:]
elif vec[i]<range_list[i][1]:
return vec[0:i] + [vec[i]+step] + vec[i+1:]三. 遗传算法的python实现
# 遗传算法
# cost_func是代价函数，目标便是让代价函数最小
# range_list是一个二维list构成的列表
# range_list指定了一个解中的每个变量的最大最小值，相当于定义域
# 交叉操作
# vec1和vec2是选出两个最优解
# dismension是一个解的维度len(range_list)
def crossover(vec1, vec2, dimension):
# 选出交叉位置
i = random.randint(1, dimension-2)
return vec1[0:i]+vec2[i:]
# 变异操作
# vec是要变异操作的已有解,step是变异的幅度
def alter(vec, range_list, step=1):
dimension = len(range_list)
i = random.randint(1, dimension - 1)
if random.random()<0.5 and vec[i]>range_list[i][0]:
return vec[0:i] + [vec[i]-step] + vec[i+1:]
elif vec[i]<range_list[i][1]:
return vec[0:i] + [vec[i]+step] + vec[i+1:]
# 遗传算法主函数
# step是变异的幅度
# popsize是种群大小，vote是种群中应该留下不淘汰的比例
# generation是算法需要运行的代数，mix是种群中变异产生的概率
def gene_op(range_list, cost_func, step=1, popsize=50, vote=0.2, generation=100, mix=0.2):
dimension = len(range_list)
# 初始化种群
population = []
for i in range(popsize):
vec=[random.randint(range_list[j][0], range_list[j][1]) for j in range(dimension)]
population.append(vec)
top = popsize*vote # 每一代中应该留下的数量
for i in range(generation):
# 计算出种群中的解的cost并排序
cost_list = [(cost_func(vec), vec) for vec in population]
cost_list.sort()
para_list = [vec for (cost, vec) in cost_list]
# 更新种群，选出最优的top个解添加进新种群
population = para_list[0:top]
# 往新种群中添加变异和交叉所产生的后代
while len(population):
if random.random()<mix:
# 进行变异操作
vec = para_list[random.randint(0, top)] # 选出要变异的已在解
population.append(alter(vec, range_list))
else:
# 进行交叉操作
vec1 = para_list[random.randint(0, top)] # 选出要交叉的最优解
vec2 = para_list[random.randint(0, top)]
population.append(crossover(vec1, vec2, dimension))
# 打印出目前的最优解
print para_list[0]
# 返回最优解和最优解对应的目标函数值
return population[0], cost_func(population[0])如果对遗传算法还觉得不够了解，可以参考一下一篇博客：<>。这篇文章讲的很不错，对理解遗传算法思路很有帮助。