詳解用python實(shí)現(xiàn)簡單的遺傳算法

更新時(shí)間：2018年01月02日 11:43:49 作者：czrzchao

這篇文章主要介紹了詳解用python實(shí)現(xiàn)簡單的遺傳算法，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧

今天整理之前寫的代碼，發(fā)現(xiàn)在做數(shù)模期間寫的用python實(shí)現(xiàn)的遺傳算法，感覺還是挺有意思的，就拿出來分享一下。

首先遺傳算法是一種優(yōu)化算法，通過模擬基因的優(yōu)勝劣汰，進(jìn)行計(jì)算（具體的算法思路什么的就不贅述了）。大致過程分為初始化編碼、個(gè)體評(píng)價(jià)、選擇，交叉，變異。

遺傳算法介紹

遺傳算法是通過模擬大自然中生物進(jìn)化的歷程，來解決問題的。大自然中一個(gè)種群經(jīng)歷過若干代的自然選擇后，剩下的種群必定是適應(yīng)環(huán)境的。把一個(gè)問題所有的解看做一個(gè)種群，經(jīng)歷過若干次的自然選擇以后，剩下的解中是有問題的最優(yōu)解的。當(dāng)然，只能說有最優(yōu)解的概率很大。這里，我們用遺傳算法求一個(gè)函數(shù)的最大值。

f(x) = 10 * sin( 5x ) + 7 * cos( 4x ), 0 <= x <= 10

1、將自變量x進(jìn)行編碼

取基因片段的長度為10, 則10位二進(jìn)制位可以表示的范圍是0到1023。基因與自變量轉(zhuǎn)變的公式是x = b2d(individual) * 10 / 1023。構(gòu)造初始的種群pop。每個(gè)個(gè)體的基因初始值是[0, 1, 0, 1, 0, 1, 0, 1, 0, 1]

2、計(jì)算目標(biāo)函數(shù)值

根據(jù)自變量與基因的轉(zhuǎn)化關(guān)系式，求出每個(gè)個(gè)體的基因?qū)?yīng)的自變量，然后將自變量代入函數(shù)f（x），求出每個(gè)個(gè)體的目標(biāo)函數(shù)值。

3、適應(yīng)度函數(shù)

適應(yīng)度函數(shù)是用來評(píng)估個(gè)體適應(yīng)環(huán)境的能力，是進(jìn)行自然選擇的依據(jù)。本題的適應(yīng)度函數(shù)直接將目標(biāo)函數(shù)值中的負(fù)值變成0. 因?yàn)槲覀兦蟮氖亲畲笾?，所以要使目?biāo)函數(shù)值是負(fù)數(shù)的個(gè)體不適應(yīng)環(huán)境，使其繁殖后代的能力為0.適應(yīng)度函數(shù)的作用將在自然選擇中體現(xiàn)。

4、自然選擇

自然選擇的思想不再贅述，操作使用輪盤賭算法。其具體步驟：

假設(shè)種群中共5個(gè)個(gè)體，適應(yīng)度函數(shù)計(jì)算出來的個(gè)體適應(yīng)性列表是fitvalue = [1 ,3, 0, 2, 4] ，totalvalue = 10 ，如果將fitvalue畫到圓盤上，值的大小表示在圓盤上的面積。在轉(zhuǎn)動(dòng)輪盤的過程中，單個(gè)模塊的面積越大則被選中的概率越大。選擇的方法是將fitvalue轉(zhuǎn)化為[1 ， 4 ，4 , 6 ，10], fitvalue / totalvalue = [0.1 , 0.4 , 0.4 , 0.6 , 1.0] . 然后產(chǎn)生5個(gè)0-1之間的隨機(jī)數(shù)，將隨機(jī)數(shù)從小到大排序，假如是[0.05 , 0.2 , 0.7 , 0.8 ,0.9]，則將0號(hào)個(gè)體、1號(hào)個(gè)體、4號(hào)個(gè)體、4號(hào)個(gè)體、4號(hào)個(gè)體拷貝到新種群中。自然選擇的結(jié)果使種群更符合條件了。

5、繁殖

假設(shè)個(gè)體a、b的基因是

a = [1, 0, 0, 0, 0, 1, 1, 1, 0, 0]
b = [0, 0, 0, 1, 1, 0, 1, 1, 1, 1]

這兩個(gè)個(gè)體發(fā)生基因交換的概率pc = 0.6.如果要發(fā)生基因交換，則產(chǎn)生一個(gè)隨機(jī)數(shù)point表示基因交換的位置，假設(shè)point = 4,則：

a = [1, 0, 0, 0, 0, 1, 1, 1, 0, 0]
b = [0, 0, 0, 1, 1, 0, 1, 1, 1, 1]

交換后為：

a = [1, 0, 0, 0, 1, 0, 1, 1, 1, 1]
b = [0, 0, 0, 1, 0, 1, 1, 1, 0, 0]

6、突變

遍歷每一個(gè)個(gè)體，基因的每一位發(fā)生突變（0變?yōu)?,1變?yōu)?）的概率為0.001.突變可以增加解空間

以目標(biāo)式子 y = 10 * sin(5x) + 7 * cos(4x)為例，計(jì)算其最大值

首先是初始化，包括具體要計(jì)算的式子、種群數(shù)量、染色體長度、交配概率、變異概率等。并且要對(duì)基因序列進(jìn)行初始化

pop_size = 500  # 種群數(shù)量 
max_value = 10  # 基因中允許出現(xiàn)的最大值 
chrom_length = 10  # 染色體長度 
pc = 0.6   # 交配概率 
pm = 0.01   # 變異概率 
results = [[]]  # 存儲(chǔ)每一代的最優(yōu)解，N個(gè)二元組 
fit_value = []  # 個(gè)體適應(yīng)度 
fit_mean = []  # 平均適應(yīng)度 
pop = geneEncoding(pop_size, chrom_length)

其中g(shù)enEncodeing是自定義的一個(gè)簡單隨機(jī)生成序列的函數(shù)，具體實(shí)現(xiàn)如下

def geneEncoding(pop_size, chrom_length): 
 pop = [[]] 
 for i in range(pop_size): 
  temp = [] 
  for j in range(chrom_length): 
   temp.append(random.randint(0, 1)) 
  pop.append(temp) 
 return pop[1:]

編碼完成之后就是要進(jìn)行個(gè)體評(píng)價(jià)，個(gè)體評(píng)價(jià)主要是計(jì)算各個(gè)編碼出來的list的值以及對(duì)應(yīng)帶入目標(biāo)式子的值。其實(shí)編碼出來的就是一堆2進(jìn)制list。這些2進(jìn)制list每個(gè)都代表了一個(gè)數(shù)。其值的計(jì)算方式為轉(zhuǎn)換為10進(jìn)制，然后除以2的序列長度次方減一，也就是全一list的十進(jìn)制減一。根據(jù)這個(gè)規(guī)則就能計(jì)算出所有l(wèi)ist的值和帶入要計(jì)算式子中的值，代碼如下

# 0.0 coding:utf-8 0.0 
# 解碼并計(jì)算值 
import math 
def decodechrom(pop, chrom_length): 
 temp = [] 
 for i in range(len(pop)): 
  t = 0 
  for j in range(chrom_length): 
   t += pop[i][j] * (math.pow(2, j)) 
  temp.append(t) 
 return temp 
 
 
def calobjValue(pop, chrom_length, max_value): 
 temp1 = [] 
 obj_value = [] 
 temp1 = decodechrom(pop, chrom_length) 
 for i in range(len(temp1)): 
  x = temp1[i] * max_value / (math.pow(2, chrom_length) - 1) 
  obj_value.append(10 * math.sin(5 * x) + 7 * math.cos(4 * x)) 
 return obj_value

有了具體的值和對(duì)應(yīng)的基因序列，然后進(jìn)行一次淘汰，目的是淘汰掉一些不可能的壞值。這里由于是計(jì)算最大值，于是就淘汰負(fù)值就好了

# 0.0 coding:utf-8 0.0 
# 淘汰（去除負(fù)值） 
def calfitValue(obj_value): 
 fit_value = [] 
 c_min = 0 
 for i in range(len(obj_value)): 
  if(obj_value[i] + c_min > 0): 
   temp = c_min + obj_value[i] 
  else: 
   temp = 0.0 
  fit_value.append(temp) 
 return fit_value

然后就是進(jìn)行選擇，這是整個(gè)遺傳算法最核心的部分。選擇實(shí)際上模擬生物遺傳進(jìn)化的優(yōu)勝劣汰，讓優(yōu)秀的個(gè)體盡可能存活，讓差的個(gè)體盡可能的淘汰。個(gè)體的好壞是取決于個(gè)體適應(yīng)度。個(gè)體適應(yīng)度越高，越容易被留下，個(gè)體適應(yīng)度越低越容易被淘汰。具體的代碼如下

# 0.0 coding:utf-8 0.0 
# 選擇 
import random 
def sum(fit_value): 
 total = 0 
 for i in range(len(fit_value)): 
  total += fit_value[i] 
 return total 
def cumsum(fit_value): 
 for i in range(len(fit_value)-2, -1, -1): 
  t = 0 
  j = 0 
  while(j <= i): 
   t += fit_value[j] 
   j += 1 
  fit_value[i] = t 
  fit_value[len(fit_value)-1] = 1 
def selection(pop, fit_value): 
 newfit_value = [] 
 # 適應(yīng)度總和 
 total_fit = sum(fit_value) 
 for i in range(len(fit_value)): 
  newfit_value.append(fit_value[i] / total_fit) 
 # 計(jì)算累計(jì)概率 
 cumsum(newfit_value) 
 ms = [] 
 pop_len = len(pop) 
 for i in range(pop_len): 
  ms.append(random.random()) 
 ms.sort() 
 fitin = 0 
 newin = 0 
 newpop = pop 
 # 轉(zhuǎn)輪盤選擇法 
 while newin < pop_len: 
  if(ms[newin] < newfit_value[fitin]): 
   newpop[newin] = pop[fitin] 
   newin = newin + 1 
  else: 
   fitin = fitin + 1 
 pop = newpop

以上代碼主要進(jìn)行了3個(gè)操作，首先是計(jì)算個(gè)體適應(yīng)度總和，然后在計(jì)算各自的累積適應(yīng)度。這兩步都好理解，主要是第三步，轉(zhuǎn)輪盤選擇法。這一步首先是生成基因總數(shù)個(gè)0-1的小數(shù)，然后分別和各個(gè)基因的累積個(gè)體適應(yīng)度進(jìn)行比較。如果累積個(gè)體適應(yīng)度大于隨機(jī)數(shù)則進(jìn)行保留，否則就淘汰。這一塊的核心思想在于：一個(gè)基因的個(gè)體適應(yīng)度越高，他所占據(jù)的累計(jì)適應(yīng)度空隙就越大，也就是說他越容易被保留下來。

選擇完后就是進(jìn)行交配和變異，這個(gè)兩個(gè)步驟很好理解。就是對(duì)基因序列進(jìn)行改變，只不過改變的方式不一樣

交配：

# 0.0 coding:utf-8 0.0 
# 交配 
import random 
def crossover(pop, pc): 
 pop_len = len(pop) 
 for i in range(pop_len - 1): 
  if(random.random() < pc): 
   cpoint = random.randint(0,len(pop[0])) 
   temp1 = [] 
   temp2 = [] 
   temp1.extend(pop[i][0:cpoint]) 
   temp1.extend(pop[i+1][cpoint:len(pop[i])]) 
   temp2.extend(pop[i+1][0:cpoint]) 
   temp2.extend(pop[i][cpoint:len(pop[i])]) 
   pop[i] = temp1 
   pop[i+1] = temp2

變異：

# 0.0 coding:utf-8 0.0 
# 基因突變 
import random 
def mutation(pop, pm): 
 px = len(pop) 
 py = len(pop[0]) 
 for i in range(px): 
  if(random.random() < pm): 
   mpoint = random.randint(0, py-1) 
   if(pop[i][mpoint] == 1): 
    pop[i][mpoint] = 0 
   else: 
    pop[i][mpoint] = 1

整個(gè)遺傳算法的實(shí)現(xiàn)完成了，總的調(diào)用入口代碼如下

# 0.0 coding:utf-8 0.0 
import matplotlib.pyplot as plt 
import math 
from calobjValue import calobjValue 
from calfitValue import calfitValue 
from selection import selection 
from crossover import crossover 
from mutation import mutation 
from best import best 
from geneEncoding import geneEncoding 
print 'y = 10 * math.sin(5 * x) + 7 * math.cos(4 * x)' 
# 計(jì)算2進(jìn)制序列代表的數(shù)值 
def b2d(b, max_value, chrom_length): 
 t = 0 
 for j in range(len(b)): 
  t += b[j] * (math.pow(2, j)) 
 t = t * max_value / (math.pow(2, chrom_length) - 1) 
 return t 
pop_size = 500  # 種群數(shù)量 
max_value = 10  # 基因中允許出現(xiàn)的最大值 
chrom_length = 10  # 染色體長度 
pc = 0.6   # 交配概率 
pm = 0.01   # 變異概率 
results = [[]]  # 存儲(chǔ)每一代的最優(yōu)解，N個(gè)二元組 
fit_value = []  # 個(gè)體適應(yīng)度 
fit_mean = []  # 平均適應(yīng)度 
# pop = [[0, 1, 0, 1, 0, 1, 0, 1, 0, 1] for i in range(pop_size)] 
pop = geneEncoding(pop_size, chrom_length) 
for i in range(pop_size): 
 obj_value = calobjValue(pop, chrom_length, max_value)  # 個(gè)體評(píng)價(jià) 
 fit_value = calfitValue(obj_value)  # 淘汰 
 best_individual, best_fit = best(pop, fit_value)  # 第一個(gè)存儲(chǔ)最優(yōu)的解, 第二個(gè)存儲(chǔ)最優(yōu)基因 
 results.append([best_fit, b2d(best_individual, max_value, chrom_length)]) 
 selection(pop, fit_value)  # 新種群復(fù)制 
 crossover(pop, pc)  # 交配 
 mutation(pop, pm)  # 變異 
results = results[1:] 
results.sort() 
X = [] 
Y = [] 
for i in range(500): 
 X.append(i) 
 t = results[i][0] 
 Y.append(t) 
plt.plot(X, Y) 
plt.show()

最后調(diào)用了一下matplotlib包，把500代最優(yōu)解的變化趨勢表現(xiàn)出來。