概述
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$)
轮盘赌算法的基本实现思路为：通过区间长度来表示概率，再通过随机数选择。详细可参考：https://www.cnblogs.com/gaosheng12138/p/7534956.html
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]
