詳解用python實現簡單的遺傳算法
今天整理之前寫的代碼，發(fā)現在做數模期間寫的用python實現的遺傳算法，感覺還是挺有意思的，就拿出來分享一下。
首先遺傳算法是一種優(yōu)化算法，通過模擬基因的優(yōu)勝劣汰，進行計算（具體的算法思路什么的就不贅述了）。大致過程分為初始化編碼、個體評價、選擇，交叉，變異。
遺傳算法介紹
遺傳算法是通過模擬大自然中生物進化的歷程，來解決問題的。大自然中一個種群經歷過若干代的自然選擇后，剩下的種群必定是適應環(huán)境的。把一個問題所有的解看做一個種群，經歷過若干次的自然選擇以后，剩下的解中是有問題的最優(yōu)解的。當然，只能說有最優(yōu)解的概率很大。這里，我們用遺傳算法求一個函數的最大值。
f(x) = 10 * sin( 5x ) + 7 * cos( 4x ), 0 <= x <= 10
1、將自變量x進行編碼
取基因片段的長度為10, 則10位二進制位可以表示的范圍是0到1023?；蚺c自變量轉變的公式是x = b2d(individual) * 10 / 1023。構造初始的種群pop。每個個體的基因初始值是[0, 1, 0, 1, 0, 1, 0, 1, 0, 1]
2、計算目標函數值
根據自變量與基因的轉化關系式，求出每個個體的基因對應的自變量，然后將自變量代入函數f（x），求出每個個體的目標函數值。
3、適應度函數
適應度函數是用來評估個體適應環(huán)境的能力，是進行自然選擇的依據。本題的適應度函數直接將目標函數值中的負值變成0. 因為我們求的是最大值，所以要使目標函數值是負數的個體不適應環(huán)境，使其繁殖后代的能力為0.適應度函數的作用將在自然選擇中體現。
4、自然選擇
自然選擇的思想不再贅述，操作使用輪盤賭算法。其具體步驟：
假設種群中共5個個體，適應度函數計算出來的個體適應性列表是fitvalue = [1 ,3, 0, 2, 4] ，totalvalue = 10 ， 如果將fitvalue畫到圓盤上，值的大小表示在圓盤上的面積。在轉動輪盤的過程中，單個模塊的面積越大則被選中的概率越大。選擇的方法是將fitvalue轉化為[1 ， 4 ，4 , 6 ，10], fitvalue / totalvalue = [0.1 , 0.4 , 0.4 , 0.6 , 1.0] . 然后產生5個0-1之間的隨機數，將隨機數從小到大排序，假如是[0.05 , 0.2 , 0.7 , 0.8 ,0.9]，則將0號個體、1號個體、4號個體、4號個體、4號個體拷貝到新種群中。自然選擇的結果使種群更符合條件了。
5、繁殖
假設個體a、b的基因是
a = [1, 0, 0, 0, 0, 1, 1, 1, 0, 0]
b = [0, 0, 0, 1, 1, 0, 1, 1, 1, 1]
這兩個個體發(fā)生基因交換的概率pc = 0.6.如果要發(fā)生基因交換，則產生一個隨機數point表示基因交換的位置，假設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、突變
遍歷每一個個體，基因的每一位發(fā)生突變（0變?yōu)?,1變?yōu)?）的概率為0.001.突變可以增加解空間
以目標式子 y = 10 * sin(5x) + 7 * cos(4x)為例，計算其最大值
首先是初始化，包括具體要計算的式子、種群數量、染色體長度、交配概率、變異概率等。并且要對基因序列進行初始化
pop_size = 500 # 種群數量 max_value = 10 # 基因中允許出現的最大值 chrom_length = 10 # 染色體長度 pc = 0.6 # 交配概率 pm = 0.01 # 變異概率 results = [[]] # 存儲每一代的最優(yōu)解，N個二元組 fit_value = [] # 個體適應度 fit_mean = [] # 平均適應度 pop = geneEncoding(pop_size, chrom_length)
其中genEncodeing是自定義的一個簡單隨機生成序列的函數，具體實現如下
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:]
編碼完成之后就是要進行個體評價，個體評價主要是計算各個編碼出來的list的值以及對應帶入目標式子的值。其實編碼出來的就是一堆2進制list。這些2進制list每個都代表了一個數。其值的計算方式為轉換為10進制，然后除以2的序列長度次方減一，也就是全一list的十進制減一。根據這個規(guī)則就能計算出所有l(wèi)ist的值和帶入要計算式子中的值，代碼如下
# 0.0 coding:utf-8 0.0 # 解碼并計算值 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
有了具體的值和對應的基因序列，然后進行一次淘汰，目的是淘汰掉一些不可能的壞值。這里由于是計算最大值，于是就淘汰負值就好了
# 0.0 coding:utf-8 0.0 # 淘汰（去除負值） 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
然后就是進行選擇，這是整個遺傳算法最核心的部分。選擇實際上模擬生物遺傳進化的優(yōu)勝劣汰，讓優(yōu)秀的個體盡可能存活，讓差的個體盡可能的淘汰。個體的好壞是取決于個體適應度。個體適應度越高，越容易被留下，個體適應度越低越容易被淘汰。具體的代碼如下
# 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 = [] # 適應度總和 total_fit = sum(fit_value) for i in range(len(fit_value)): newfit_value.append(fit_value[i] / total_fit) # 計算累計概率 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 # 轉輪盤選擇法 while newin < pop_len: if(ms[newin] < newfit_value[fitin]): newpop[newin] = pop[fitin] newin = newin + 1 else: fitin = fitin + 1 pop = newpop
以上代碼主要進行了3個操作，首先是計算個體適應度總和，然后在計算各自的累積適應度。這兩步都好理解，主要是第三步，轉輪盤選擇法。這一步首先是生成基因總數個0-1的小數，然后分別和各個基因的累積個體適應度進行比較。如果累積個體適應度大于隨機數則進行保留，否則就淘汰。這一塊的核心思想在于：一個基因的個體適應度越高，他所占據的累計適應度空隙就越大，也就是說他越容易被保留下來。
選擇完后就是進行交配和變異，這個兩個步驟很好理解。就是對基因序列進行改變，只不過改變的方式不一樣
交配：
# 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
整個遺傳算法的實現完成了，總的調用入口代碼如下
# 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)' # 計算2進制序列代表的數值 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 # 種群數量 max_value = 10 # 基因中允許出現的最大值 chrom_length = 10 # 染色體長度 pc = 0.6 # 交配概率 pm = 0.01 # 變異概率 results = [[]] # 存儲每一代的最優(yōu)解，N個二元組 fit_value = [] # 個體適應度 fit_mean = [] # 平均適應度 # 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) # 個體評價 fit_value = calfitValue(obj_value) # 淘汰 best_individual, best_fit = best(pop, fit_value) # 第一個存儲最優(yōu)的解, 第二個存儲最優(yōu)基因 results.append([best_fit, b2d(best_individual, max_value, chrom_length)]) selection(pop, fit_value) # 新種群復制 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()
最后調用了一下matplotlib包，把500代最優(yōu)解的變化趨勢表現出來。
完整代碼可以在github 查看
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。
相關文章
在ubuntu16.04中將python3設置為默認的命令寫法
這篇文章主要介紹了在ubuntu16.04中將python3設置為默認python的方法，非常不錯，具有一定的參考借鑒價值，需要的朋友參考下吧2018-10-10
這篇文章主要為大家介紹了python?PyVCF文件處理VCF文件格式實例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-07-07
這篇文章主要介紹了python中os包的用法，文中給大家提到了python中os的常用方法,給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-06-06
本文給大家分享使用Python來做一個屏幕錄制工具,通過實例代碼給大家介紹的非常詳細，具有一定的參考借鑒價值，需要的朋友可以參考下2020-01-01
這篇文章主要為大家介紹了Django admin顯示json字段方法詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-06-06
這篇文章主要給大家介紹了關于python中對信號處理的相關資料, 計算機借助信號來接收和發(fā)送各種命令,操作系統(tǒng)針對其編程要接收或生成的每種命令列出了至少一個信號,需要的朋友可以參考下2021-07-07
這篇文章主要介紹了Python實現3行代碼解簡單的一元一次方程,很適合Python初學者學習借鑒,需要的朋友可以參考下2014-08-08
MongoDB是一個非常流行的NoSQL數據庫,常用于大規(guī)模數據存儲應用,下面這篇文章主要給大家介紹了關于NoSql數據庫及使用Python連接MongoDB的相關資料,需要的朋友可以參考下2023-06-06
之前學習編程語言大多也就是學的很淺很淺，基本上也是很少涉及到裝飾器這些的類似的內容?？偸怯X得是一樣很神奇的東西，舍不得學（嘿嘿）。今天看了一下書籍。發(fā)現道理還是很簡單的2012-01-01
這篇文章主要介紹了Python3實現的簡單工資管理系統(tǒng),涉及Python文件讀寫、數據遍歷、判斷等相關操作技巧,需要的朋友可以參考下2019-03-03