python實(shí)現(xiàn)簡(jiǎn)單遺傳算法
今天整理之前寫(xiě)的代碼,發(fā)現(xiàn)在做數(shù)模期間寫(xiě)的用python實(shí)現(xiàn)的遺傳算法,感覺(jué)還是挺有意思的,就拿出來(lái)分享一下。
首先遺傳算法是一種優(yōu)化算法,通過(guò)模擬基因的優(yōu)勝劣汰,進(jìn)行計(jì)算(具體的算法思路什么的就不贅述了)。大致過(guò)程分為初始化編碼、個(gè)體評(píng)價(jià)、選擇,交叉,變異。
以目標(biāo)式子 y = 10 * sin(5x) + 7 * cos(4x)為例,計(jì)算其最大值
首先是初始化,包括具體要計(jì)算的式子、種群數(shù)量、染色體長(zhǎng)度、交配概率、變異概率等。并且要對(duì)基因序列進(jìn)行初始化
pop_size = 500 # 種群數(shù)量 max_value = 10 # 基因中允許出現(xiàn)的最大值 chrom_length = 10 # 染色體長(zhǎng)度 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è)簡(jiǎn)單隨機(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è)編碼出來(lái)的list的值以及對(duì)應(yīng)帶入目標(biāo)式子的值。其實(shí)編碼出來(lái)的就是一堆2進(jìn)制list。這些2進(jìn)制list每個(gè)都代表了一個(gè)數(shù)。其值的計(jì)算方式為轉(zhuǎn)換為10進(jìn)制,然后除以2的序列長(zhǎng)度次方減一,也就是全一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)輪盤(pá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)輪盤(pá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)度空隙就越大,也就是說(shuō)他越容易被保留下來(lái)。
選擇完后就是進(jìn)行交配和變異,這個(gè)兩個(gè)步驟很好理解。就是對(duì)基因序列進(jìn)行改變,只不過(guò)改變的方式不一樣
交配:
# 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 # 染色體長(zhǎng)度 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)解的變化趨勢(shì)表現(xiàn)出來(lái)。
完整代碼可以在github 查看
以上就是本文的全部?jī)?nèi)容,希望對(duì)大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。
相關(guān)文章
分享7個(gè) Python 實(shí)戰(zhàn)項(xiàng)目練習(xí)
這篇文章主要介紹了分享7個(gè) Python 實(shí)戰(zhàn)項(xiàng)目代碼,經(jīng)過(guò)Python3.6.4調(diào)試通過(guò)的代碼,就具一點(diǎn)的參考價(jià)值,需要的小伙伴可以參考一下2022-03-03python連接kafka加載數(shù)據(jù)的項(xiàng)目實(shí)踐
本文主要介紹了python連接kafka加載數(shù)據(jù)的項(xiàng)目實(shí)踐,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-05-05詳解JavaScript編程中的window與window.screen對(duì)象
這篇文章主要介紹了JavaScript編程中的window與window.screen對(duì)象,是JS在瀏覽器中視圖編程的基礎(chǔ),需要的朋友可以參考下2015-10-10python中用Scrapy實(shí)現(xiàn)定時(shí)爬蟲(chóng)的實(shí)例講解
在本篇文章里小編給大家整理的是一篇關(guān)于python中用Scrapy實(shí)現(xiàn)定時(shí)爬蟲(chóng)的實(shí)例講解內(nèi)容,有興趣的朋友們可以學(xué)習(xí)下。2021-01-01Python實(shí)現(xiàn)多功能音樂(lè)播放器詳解
這篇文章主要介紹了如何通過(guò)Python制作一個(gè)簡(jiǎn)易的音樂(lè)播放器,文中的示例代碼講解詳細(xì),對(duì)我們學(xué)習(xí)或工作有一定價(jià)值,需要的可以參考一下2022-02-02Python+PyQt5實(shí)現(xiàn)網(wǎng)口功能測(cè)試詳解
這篇文章主要為大家詳細(xì)介紹了Python+PyQt5實(shí)現(xiàn)網(wǎng)口功能測(cè)試的相關(guān)知識(shí),文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2024-02-02聊聊python里如何用Borg pattern實(shí)現(xiàn)的單例模式
這篇文章主要介紹了聊聊python里如何用Borg pattern實(shí)現(xiàn)的單例模式,小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2019-06-06