遺傳算法(genetic algorithm, GA)是一種進(jìn)化算法望薄，其基本原理是仿效生物界中的“物競天擇，適者生存”的演化法則。遺傳算法是把問題參數(shù)編碼為染色體，再利用迭代的方式進(jìn)行選擇撞蜂、交叉以及變異等運算來交換種群中染色體的信息盲镶，最終生成符合優(yōu)化目標(biāo)的染色體。
更好閱讀體驗請訪問（https://tianle.me/2017/04/19/GA/ ）
名詞解釋
在遺傳算法中蝌诡，染色體對應(yīng)的是數(shù)據(jù)或數(shù)組溉贿，通常是由一維的串結(jié)構(gòu)數(shù)據(jù)來表示，串上各個位置對應(yīng)基因的取值送漠⊥缯眨基因組成的串就是染色體(chromosome)，或者稱為基因型個體(individual)闽寡。一定數(shù)量的個體組成了群體(population)。群體中的個體數(shù)目稱為群體大小(population size)尼酿，也成為群體規(guī)模爷狈。而各個個體對環(huán)境的適應(yīng)程度叫適應(yīng)度(fitness)。
基本步驟
編碼
GA在進(jìn)行搜索之前先將解空間的解數(shù)據(jù)表示成遺傳空間的基因型串結(jié)構(gòu)數(shù)據(jù)裳擎，這些串結(jié)構(gòu)數(shù)據(jù)的不同組合便構(gòu)成了不同的點涎永。
初始群體的生成
隨機產(chǎn)生N個初始串結(jié)構(gòu)數(shù)據(jù)，每個串結(jié)構(gòu)數(shù)據(jù)稱為一個個體鹿响，N個個體構(gòu)成了一個群體羡微。GA以這N個串結(jié)構(gòu)數(shù)據(jù)作為初始點開始進(jìn)化。
適應(yīng)度評估
適應(yīng)度表明個體或解的優(yōu)劣性惶我。不同的問題妈倔，適應(yīng)度函數(shù)的定義方式也不同。
選擇
選擇的目的是為了從當(dāng)前群體中選出優(yōu)良的個體绸贡，使它們有機會作為父代為下一代繁殖子孫盯蝴。遺傳算法通過選擇過程體現(xiàn)這一思想，進(jìn)行選擇的原則是適應(yīng)度強的個體為下一代貢獻(xiàn)一個或多個后代的概率大听怕。選擇體現(xiàn)了達(dá)爾文的適者生存原則捧挺。
交叉
交叉操作是遺傳算法中最主要的遺傳操作。通過交叉操作可以得到新一代個體尿瞭，新個體組合了其父輩個體的特性闽烙。交叉體現(xiàn)了信息交換的思想。
變異
變異首先在群體中隨機選擇一個個體声搁，對于選中的個體以一定的概率隨機地改變串結(jié)構(gòu)數(shù)據(jù)中某個串的的值黑竞。同生物界一樣，GA中變異發(fā)生的概率很低酥艳，通常取值很小摊溶。
實例詳解
之前已經(jīng)使用matlab實現(xiàn)了一次，由于現(xiàn)在又布置了作業(yè)充石，正好現(xiàn)在對python不是特別熟悉莫换，那就寫個代碼練練手吧霞玄。
目標(biāo)函數(shù)
max f (x1, x2) = 21.5 + x1·sin(4 pi x1) + x2·sin(20 pi x2)
s. t. -3.0 <= x1 <= 12.1
4.1 <= x2 <= 5.8
def func(self):
self.decoding(self.code_x1, self.code_x2)
self.y = 21.5 + self.x1 * math.sin(4 * math.pi * self.x1) + self.x2 * math.sin(20 * math.pi * self.x2)
二進(jìn)制編碼
在剛剛提到的遺傳算法中，我們首先要將數(shù)據(jù)進(jìn)行編碼拉岁，這里我們采用二進(jìn)制的方式進(jìn)行編碼坷剧。第一步，我們根據(jù)題目的介紹可以得知該函數(shù)含有兩個變量喊暖，以及各自的定義域惫企。在二進(jìn)制編碼中，我們首先要先計算它的編碼長度陵叽。計算公式如下:
$${2^{{m_j} - 1}} < ({b_j} - {a_j})*precision \le {2^{{m_j}}} - 1$$
其中precision為精度狞尔，如小數(shù)點后5位，則precision=10^5巩掺，mj為編碼長度偏序，${x_j} \in [{a_j},{b_j}]$
二進(jìn)制解碼
解碼即編碼的逆過程:
$${x_j} = {a_j} + {\rm{decimal}}(substrin{g_j}) \times \frac{{{b_j} - {a_j}}}{{{2^{{m_j}}} - 1}}$$
def decoding(self, code_x1, code_x2):
self.x1 = self.bounds[0][0] + int(code_x1, 2) * (self.bounds[0][1] - self.bounds[0][0]) / (
2 ** self.code_x1_length - 1)
self.x2 = self.bounds[1][0] + int(code_x2, 2) * (self.bounds[1][1] - self.bounds[1][0]) / (
2 ** self.code_x2_length - 1)
種群初始化
編碼完成那我們就開始對種群初始化吧，為了簡便我采用了隨機地方式進(jìn)行初始化胖替。
def __init__(self, bounds, precision):
self.x1 = 1
self.x2 = 1
self.y = 0
self.code_x1 = ''
self.code_x2 = ''
self.bounds = bounds
temp1 = (bounds[0][1] - bounds[0][0]) * precision
self.code_x1_length = math.ceil(math.log(temp1, 2))
temp2 = (bounds[1][1] - bounds[1][0]) * precision
self.code_x2_length = math.ceil(math.log(temp2, 2))
self.rand_init()
self.func()
def rand_init(self):
for i in range(self.code_x1_length):
self.code_x1 += str(random.randint(0, 1))
for i in range(self.code_x2_length):
self.code_x2 += str(random.randint(0, 1))
選擇
選擇我們采用輪盤賭方式進(jìn)行選擇研儒，主要思想是適應(yīng)度高的，被選擇到的概率大独令。
沒怎么優(yōu)化端朵，用了一堆for循環(huán)。。。符喝。
def select(self):
"""
輪盤賭選擇
:return:
"""
# calculate fitness function
sum_f = 0
for i in range(self.pop_size):
self.pop[i].func()
# guarantee fitness > 0
min = self.pop[0].y
for i in range(self.pop_size):
if self.pop[i].y < min:
min = self.pop[i].y
if min < 0:
for i in range(self.pop_size):
self.pop[i].y = self.pop[i].y + (-1) * min
# roulette
for i in range(self.pop_size):
sum_f += self.pop[i].y
p = [0] * self.pop_size
for i in range(self.pop_size):
p[i] = self.pop[i].y / sum_f
q = [0] * self.pop_size
q[0] = 0
for i in range(self.pop_size):
s = 0
for j in range(0, i+1):
s += p[j]
q[i] = s
# start roulette
v = []
for i in range(self.pop_size):
r = random.random()
if r < q[0]:
v.append(self.pop[0])
for j in range(1, self.pop_size):
if q[j - 1] < r <= q[j]:
v.append(self.pop[j])
self.pop = v
變異
這里的變異，我們先以變異概率碗硬，從種群中選一個，然后對選中的個體瓢颅，隨機選一個變異位點進(jìn)行變異恩尾。
def mutation(self):
"""
變異
:return:
"""
for i in range(self.pop_size):
if self.pm > random.random():
pop = self.pop[i]
# select mutation index
index1 = random.randint(0, pop.code_x1_length-1)
index2 = random.randint(0, pop.code_x2_length-1)
i = pop.code_x1[index1]
i = self.__inverse(i)
pop.code_x1 = pop.code_x1[:index1] + i + pop.code_x1[index1+1:]
i = pop.code_x2[index2]
i = self.__inverse(i)
pop.code_x2 = pop.code_x2[:index2] + i + pop.code_x2[index2+1:]
交叉
這里采用單點交叉法。隨機從種群中選兩個個體挽懦，然后再隨機選一個交叉點翰意，交換位置⌒攀粒看圖 = . =
def cross(self):
"""
交叉
:return:
"""
for i in range(int(self.pop_size / 2)):
if self.pc > random.random():
# randon select 2 chromosomes in pops
i = 0
j = 0
while i == j:
i = random.randint(0, self.pop_size-1)
j = random.randint(0, self.pop_size-1)
pop_i = self.pop[i]
pop_j = self.pop[j]
# select cross index
pop_1 = random.randint(0, pop_i.code_x1_length - 1)
pop_2 = random.randint(0, pop_i.code_x2_length - 1)
# get new code
new_pop_i_code1 = pop_i.code_x1[0: pop_1] + pop_j.code_x1[pop_1: pop_i.code_x1_length]
new_pop_i_code2 = pop_i.code_x2[0: pop_2] + pop_j.code_x2[pop_2: pop_i.code_x2_length]
new_pop_j_code1 = pop_j.code_x1[0: pop_1] + pop_i.code_x1[pop_1: pop_i.code_x1_length]
new_pop_j_code2 = pop_j.code_x2[0: pop_2] + pop_i.code_x2[pop_2: pop_i.code_x2_length]
pop_i.code_x1 = new_pop_i_code1
pop_i.code_x2 = new_pop_i_code2
pop_j.code_x1 = new_pop_j_code1
pop_j.code_x2 = new_pop_j_code2
算法主流程
至此冀偶，遺傳的主要框架已經(jīng)完畢，下面展示主流程渔嚷，及畫圖部分代碼进鸠。
def ga(self):
"""
算法主函數(shù)
:return:
"""
self.init_pop()
best = self.find_best()
self.g_best = copy.deepcopy(best)
y = [0] * self.pop_size
for i in range(self.max_gen):
self.cross()
self.mutation()
self.select()
best = self.find_best()
self.bests[i] = best
if self.g_best.y < best.y:
self.g_best = copy.deepcopy(best)
y[i] = self.g_best.y
print(self.g_best.y)
# plt
plt.figure(1)
x = range(self.pop_size)
plt.plot(x, y)
plt.ylabel('generations')
plt.xlabel('function value')
plt.show()
實驗結(jié)果圖
總結(jié)
在編碼的時候，我偷懶了一下形病，把兩個變量拆開寫客年，x1和x2霞幅，導(dǎo)致之后的操作變得異常復(fù)雜，并且不利于代碼重構(gòu)量瓜。
程序中過多的使用了for循環(huán)司恳，并沒有對此進(jìn)行優(yōu)化。
針對上述兩個問題绍傲，在此記錄一下扔傅。
程序完整代碼
參考資料
《MATLAB智能算法-30個案例分析》
