概述
GA算法可以運用在求解復雜的找最優(yōu)解的問題上枚荣，但它不保證一定能找到全局最優(yōu)解屠列。
問題描述
定性描述
我們通過0-1背包問題來介紹GA算法，0-1背包問題可以描述為：給定一組物品畏吓，每種物品都有自己的重量和價格滚婉，在限定的總重量內(nèi)图筹，我們?nèi)绾芜x擇，才能使得物品的總價格最高让腹。
定量描述
- 物體總數(shù): N
- 背包可容納總重量: W
- 第i件物體的重量：w[i]
- 第i件物體的價格: v[i]
進化論知識
GA算法參考了進化論远剩，我們有必要來了解下相關知識：
- 種群（Population）：生物的進化以群體的形式進行，這樣的一個群體稱為種群骇窍。種群的生物學定義為：指在一定時間內(nèi)占據(jù)一定空間的同種生物的所有個體瓜晤。
- 個體：組成種群的單個生物。
- 基因（Gene）：DNA分子上的一個小片段腹纳，一個遺傳因子痢掠。
- 染色體（Chromosome）：由DNA和蛋白質(zhì)組成，包含一組基因嘲恍。
- 進化過程：生物在繁殖過程中足画，會發(fā)生基因交叉( Crossover ) ，基因突變 ( Mutation ) 佃牛，適應度( Fitness )低的個體會被逐步淘汰淹辞，而適應度高的個體會越來越多。那么經(jīng)過N代的自然選擇后俘侠，保存下來的個體都是適應度很高的象缀。
GA算法
簡介
遺傳算法是受達爾文的進化論的啟發(fā)，借鑒生物進化過程而提出的一種啟發(fā)式搜索算法爷速。借鑒生物進化論央星，遺傳算法將要解決的問題模擬成一個生物進化的過程，通過復制惫东、交叉莉给、突變等操作產(chǎn)生下一代的解，并逐步淘汰掉適應度函數(shù)值低的解凿蒜，增加適應度函數(shù)值高的解禁谦。
算法步驟
- 編碼
- 選擇
- 交叉
- 變異
編碼
編碼是為了模擬進化論中的基因與染色體部分。這里每一個物體可以被取或者不被取废封，則染色體可以用長度為N的二進制表示州泊，它有N個基因，每個基因有兩個可能的狀態(tài)（0 or 1）漂洋。
當N=4遥皂，則一個個體<取力喷，取，不取演训，不取>可以表示為：1(未編碼) 0001(編碼后)
# 假設一個未編碼的個體表示為：取,取,不取,不取弟孟，可使用10進制數(shù)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
選擇
按照某些策略選擇個體來產(chǎn)生后代样悟，常用的策略有如：輪盤賭算法(Roulette Wheel Selection), 錦標賽, 精英保留策略等拂募。我們使用輪盤賭算法。
輪盤賭算法的思路為：個體被選中的概率與其適應度函數(shù)值成正比窟她。
本題的適應度函數(shù)即為衡量總價值的函數(shù)：$f(x_i)$（其中$x_i$為第i個個體陈症，它可能為:1100）
輪盤賭中每個個體被抽中的概率為：$p_i=\dfrac{f(x_i)}{\sum_{j=1}^{n}f(x_j)} $ (本文個體總數(shù)$n=2^N$)
輪盤賭算法的基本實現(xiàn)思路為：通過區(qū)間長度來表示概率，再通過隨機數(shù)選擇震糖。詳細可參考：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) # 群體總數(shù)
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
# 根據(jù)適應性概率隨機選擇一個個體
def RWS(population, plist): # plist為總群個體抽中概率list
random.seed()
r = random.random() # 獲得隨機數(shù)
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) # 種群個體總數(shù)
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]
交叉
交叉指的是兩個個體交換染色體片段然后產(chǎn)生兩個新的后代论咏。其步驟如下：
- 隨機匹配多對父母
- 每對個體按照一定概率一定規(guī)則交叉染色體
- 新產(chǎn)生的個體組成新的種群
交叉操作存在著多種方式，例如：多點雜交颁井、均勻雜交厅贪，離散雜交、中間雜交雅宾、線性雜交和擴展線性雜交等算法
# 獲得隨機couple組
def getRandomCouple(n): # n:個體總數(shù)
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]
變異
變異是指某一些個體的染色體上的基因發(fā)生突變卦溢，如個體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 # 迭代次數(shù)
N = 4 # 物體總數(shù)
n = pow(2, N) # 種群個體總數(shù)
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 # 當前迭代次數(shù)
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]
