遗传算法 python 简书_遗传算法(GA)介绍与Python实现

概述

GA算法可以运用在求解复杂的找最优解的问题上，但它不保证一定能找到全局最优解。

问题描述

定性描述

我们通过0-1背包问题来介绍GA算法，0-1背包问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。

定量描述

物体总数: N

背包可容纳总重量: W

第i件物体的重量：w[i]

第i件物体的价格: v[i]

进化论知识

GA算法参考了进化论，我们有必要来了解下相关知识：

种群(Population)：生物的进化以群体的形式进行，这样的一个群体称为种群。种群的生物学定义为：指在一定时间内占据一定空间的同种生物的所有个体。

个体：组成种群的单个生物。

基因(Gene)：DNA分子上的一个小片段，一个遗传因子。

染色体(Chromosome)：由DNA和蛋白质组成，包含一组基因。

进化过程：生物在繁殖过程中，会发生基因交叉( Crossover ) ，基因突变 ( Mutation ) ，适应度( Fitness )低的个体会被逐步淘汰，而适应度高的个体会越来越多。那么经过N代的自然选择后，保存下来的个体都是适应度很高的。

GA算法

简介

遗传算法是受达尔文的进化论的启发，借鉴生物进化过程而提出的一种启发式搜索算法。借鉴生物进化论，遗传算法将要解决的问题模拟成一个生物进化的过程，通过复制、交叉、突变等操作产生下一代的解，并逐步淘汰掉适应度函数值低的解，增加适应度函数值高的解。

算法步骤

编码

选择

交叉

变异

编码

编码是为了模拟进化论中的基因与染色体部分。这里每一个物体可以被取或者不被取，则染色体可以用长度为N的二进制表示，它有N个基因，每个基因有两个可能的状态(0 or 1)。

当N=4，则一个个体可以表示为：1(未编码) 0001(编码后)

# 假设一个未编码的个体表示为：取,取,不取,不取，可使用10进制数12表示

def encode(N, unit): # N：染色体长度(如4)；unit：个体表示(如12)

unit = int(unit)

unit_str = str(bin(unit))[2:].zfill(N) # 左侧补0

unit_list = []

for s in unit_str:

unit_list.append(s)

return unit_list

def decode(unit_list):

l = ll = len(unit_list) - 1

c = 0

while l>=0:

if unit_list[l] == '1':

c += pow(2, ll - l)

l -= 1

return c

print(encode(4, 1))

print(decode(['0', '0', '0', '1']))

['0', '0', '0', '1']

1

选择

按照某些策略选择个体来产生后代，常用的策略有如：轮盘赌算法(Roulette Wheel Selection), 锦标赛, 精英保留策略等。我们使用轮盘赌算法。

轮盘赌算法的思路为：个体被选中的概率与其适应度函数值成正比。

本题的适应度函数即为衡量总价值的函数：$f(x_i)$(其中$x_i$为第i个个体，它可能为:1100)

轮盘赌中每个个体被抽中的概率为：$p_i=\dfrac{f(x_i)}{\sum_{j=1}^{n}f(x_j)} $ (本文个体总数$n=2^N$)

import random

# 计算种群的适应性概率

def getRWSPList(population, w, v, W): # population：总群；w：物体重量list；v：物体价值list；W：背包的重量阈值

n = len(population) # 群体总数

v_list = [] # 价值list

for i in population:

unit_code = encode(N, i) # 获得编码

unit_w = 0 # 个体的总量

unit_v = 0 # 个体的价值

for j in range(N):

unit_w += int(unit_code[j]) * w[j]

unit_v += int(unit_code[j]) * v[j]

if unit_w <= W:

v_list.append(unit_v)

else:

v_list.append(0) # 超重

p_list = [] # 每一个个体的概率

v_all = sum(v_list)

for i in range(n):

p_list.append(v_list[i] * 1.0 / v_all)

return p_list

# 根据适应性概率随机选择一个个体

def RWS(population, plist): # plist为总群个体抽中概率list

random.seed()

r = random.random() # 获得随机数

c = 0

# print plist, r

for (index, item) in enumerate(plist):

c += item

if r < c:

return population[index]

N = 4

n = pow(2, N) # 种群个体总数

w = [2, 3, 1, 5]

v = [4, 3, 2, 1]

W = 6

population = []

# 初始化种群

for i in range(n):

population.append(i)

print("Original population:",population)

# 种群选择

plist = getRWSPList(population, w, v , W) # 获得总群概率list

new_population = []

for i in range(n): # 适者生存

new_population.append(RWS(population, plist))

new_population = list(set(new_population))

print("New population:",new_population)

Original population: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

New population: [3, 4, 6, 10, 12, 14]

交叉

交叉指的是两个个体交换染色体片段然后产生两个新的后代。其步骤如下：

随机匹配多对父母

每对个体按照一定概率一定规则交叉染色体

新产生的个体组成新的种群

交叉操作存在着多种方式，例如：多点杂交、均匀杂交，离散杂交、中间杂交、线性杂交和扩展线性杂交等算法

# 获得随机couple组

def getRandomCouple(n): # n:个体总数

random.seed()

selected = [0]*n # 是否被选择了

couples = [] # 配对list

for i in range(n//2):

pair = []

while len(pair) < 2:

unit_index = random.randint(0, n-1)

if not selected[unit_index]:

pair.append(unit_index)

selected[unit_index] = True

couples.append(pair)

return couples

couples = getRandomCouple(len(new_population)) # 获得随机配对

print("Random pair:", couples)

def crossover(population, couples, cross_p, N): # cross_p为交叉概率;N为编码长度

random.seed()

new_population = []

for pair in couples:

unit_one = encode(N, population[pair[0]])

unit_two = encode(N, population[pair[1]])

p = random.random()

if p >= (1 - cross_p):

# 交叉使用从随机位置交叉尾部

random_loc = random.randint(0, N-1) # 获得随机位置

new_population.append(unit_one[0:random_loc] + unit_two[random_loc:])

new_population.append(unit_two[0:random_loc] + unit_one[random_loc:])

else:

new_population.append(unit_one)

new_population.append(unit_two)

for (index, unit) in enumerate(new_population):

new_population[index] = decode(unit) # 解码

return list(set(new_population))

new_population = crossover(new_population, couples, 0.8, N)

print("After crossover:", new_population)

Random pair: [[1, 0], [4, 2], [6, 7], [5, 3]]

After crossover: [0, 3, 6, 8, 10, 12, 14]

变异

变异是指某一些个体的染色体上的基因发生突变，如个体1100->1000(单点突变)。

def mutation(population, N, mutation_p):

# print(population, N, mutation_p)

new_population = []

random.seed()

for unit in population:

unit_code = encode(N, unit)

p = random.random() # 获得随机概率

if p > (1 - mutation_p):

random_loc = random.randint(0, N-1)

v = unit_code[random_loc]

unit_code[random_loc] = '0' if v=='1' else '1'

new_population.append(decode(unit_code))

return list(set(new_population))

print("After mutation:",mutation(new_population, N, 0.1))

After mutation: [0, 3, 6, 8, 12, 14]

整体编码

下面展示整个代码流程。

# 变量设置

generation_count = 50 # 迭代次数

N = 4 # 物体总数

n = pow(2, N) # 种群个体总数

w = [2, 3, 1, 5] # 每个物体重量

v = [4, 3, 2, 1] # 每个物体价值

W = 6 # 重量阈值

population = []

# 初始化种群

for i in range(n):

population.append(i)

print("Original population:",population)

# 算法开始

c = 0 # 当前迭代次数

while c < generation_count:

print('-'*10+str(c)+'-'*10)

# 种群选择

plist = getRWSPList(population, w, v , W) # 获得总群概率list

new_population = []

for i in range(n): # 适者生存

new_population.append(RWS(population, plist))

new_population = list(set(new_population))

print("After selection:",new_population)

if len(new_population) == 1:

population = new_population

break

# 种群交叉

couples = getRandomCouple(len(new_population)) # 获得随机配对

new_population = crossover(new_population, couples, 0.8, N)

print("After crossover:", new_population)

if len(new_population) == 1:

population = new_population

break

# 种群变异

new_population = mutation(new_population, N, 0.1)

print("After mutation:"+ str(new_population))

if len(new_population) == 1:

population = new_population

break

population = new_population

c += 1

print(population)

Original population: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

----------0----------

After selection: [2, 4, 6, 8, 10, 14]

After crossover: [2, 6, 8, 12, 14]

After mutation:[2, 6, 8, 12, 14]

----------1----------

After selection: [2, 6, 8, 12, 14]

After crossover: [8, 2, 6, 14]

After mutation:[8, 2, 12, 14]

----------2----------

After selection: [2, 12, 14]

After crossover: [2, 14]

After mutation:[2, 14]

----------3----------

After selection: [2, 14]

After crossover: [2, 14]

After mutation:[2, 14]

----------4----------

After selection: [2, 14]

After crossover: [2, 14]

After mutation:[0, 14]

----------5----------

After selection: [14]

[14]