Python實(shí)現(xiàn)簡(jiǎn)單遺傳算法(SGA)
本文用Python3完整實(shí)現(xiàn)了簡(jiǎn)單遺傳算法(SGA)
Simple Genetic Alogrithm是模擬生物進(jìn)化過(guò)程而提出的一種優(yōu)化算法。SGA采用隨機(jī)導(dǎo)向搜索全局最優(yōu)解或者說(shuō)近似全局最優(yōu)解。傳統(tǒng)的爬山算法(例如梯度下降，牛頓法)一次只優(yōu)化一個(gè)解，并且對(duì)于多峰的目標(biāo)函數(shù)很容易陷入局部最優(yōu)解，而SGA算法一次優(yōu)化一個(gè)種群(即一次優(yōu)化多個(gè)解)，SGA比傳統(tǒng)的爬山算法更容易收斂到全局最優(yōu)解或者近似全局最優(yōu)解。
SGA基本流程如下:
1、對(duì)問(wèn)題的解進(jìn)行二進(jìn)制編碼。編碼涉及精度的問(wèn)題，在本例中精度delta=0.0001,根據(jù)決策變量的上下界確定對(duì)應(yīng)此決策變量的染色體基因的長(zhǎng)度（m）。假設(shè)一個(gè)決策變量x0上界為upper,下界為lower,則精度delta = (upper-lower)/2^m-1。如果已知決策變量邊界和編碼精度，那么可以用下面的公式確定編碼決策變量x0所對(duì)應(yīng)的染色體長(zhǎng)度：
2^(length-1)<(upper-lower)/delta<=2^length-1
2、對(duì)染色體解碼得到表現(xiàn)形:
解碼后得到10進(jìn)制的值；decoded = lower + binary2demical(chromosome)*delta。其中binary2demical為二進(jìn)制轉(zhuǎn)10進(jìn)制的函數(shù)，在代碼中有實(shí)現(xiàn)，chromosome是編碼后的染色體。
3、確定初始種群,初始種群隨機(jī)生成
4、根據(jù)解碼函數(shù)得到初始種群的10進(jìn)制表現(xiàn)型的值
5、確定適應(yīng)度函數(shù)，對(duì)于求最大值最小值問(wèn)題，一般適應(yīng)度函數(shù)就是目標(biāo)函數(shù)。根據(jù)適應(yīng)度函數(shù)確定每個(gè)個(gè)體的適應(yīng)度值Fi=FitnessFunction(individual);然后確定每個(gè)個(gè)體被選擇的概率Pi=Fi/sum(Fi),sum(Fi)代表所有個(gè)體適應(yīng)度之和。
6、根據(jù)輪盤(pán)賭選擇算子，選取適應(yīng)度較大的個(gè)體。一次選取一個(gè)個(gè)體，選取n次,得到新的種群population
7、確定交叉概率Pc,對(duì)上一步得到的種群進(jìn)行單點(diǎn)交叉。每次交叉點(diǎn)的位置隨機(jī)。
8、確定變異概率Pm,假設(shè)種群大小為10，每個(gè)個(gè)體染色體編碼長(zhǎng)度為33，則一共有330個(gè)基因位，則變異的基因位數(shù)是330*Pm。接下來(lái)，要確定是那個(gè)染色體中哪個(gè)位置的基因發(fā)生了變異。將330按照10進(jìn)制序號(hào)進(jìn)行編碼即從0,1,2,.......229。隨機(jī)從330個(gè)數(shù)中選擇330*Pm個(gè)數(shù)，假設(shè)其中一個(gè)數(shù)時(shí)154，chromosomeIndex = 154/33 =4,
geneIndex = 154%33 = 22。由此確定了第154號(hào)位置的基因位于第4個(gè)染色體的第22個(gè)位置上，將此位置的基因值置反完成基本位變異操作。
9、以上步驟完成了一次迭代的所有操作。接下就是評(píng)估的過(guò)程。對(duì)變異后得到的最終的種群進(jìn)行解碼，利用解碼值求得每個(gè)個(gè)體的適應(yīng)度值，將最大的適應(yīng)度值保存下來(lái)，對(duì)應(yīng)的解碼后的決策變量的值也保存下來(lái)。
10、根據(jù)迭代次數(shù)，假設(shè)是500次，重復(fù)執(zhí)行1-9的步驟，最終得到是一個(gè)500個(gè)數(shù)值的最優(yōu)適應(yīng)度取值的數(shù)組以及一個(gè)500*n的決策變量取值數(shù)組（假設(shè)有n個(gè)決策變量）。從500個(gè)值中找到最優(yōu)的一個(gè)（最大或者最小，根據(jù)定義的適應(yīng)度函數(shù)來(lái)選擇）以及對(duì)應(yīng)的決策變量的取值。
對(duì)于以上流程不是很清楚的地方，在代碼中有詳細(xì)的注釋。也可以自行查找資料補(bǔ)充理論。本文重點(diǎn)是實(shí)現(xiàn)
本代碼實(shí)現(xiàn)的問(wèn)題是: maxf(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
初始種群的編碼結(jié)果如下圖所示:
初始種群的解碼結(jié)果如下圖所示:
適應(yīng)度值如圖所示:
輪盤(pán)賭選擇后的種群如圖所示；
單點(diǎn)交叉后的種群如圖所示:
基本位變異后的種群如圖所示；
最終結(jié)果如下圖所示；
源代碼如下；
# !/usr/bin/env python
# -*- coding:utf-8 -*-
# Author: wsw
# 簡(jiǎn)單實(shí)現(xiàn)SGA算法
import numpy as np
from scipy.optimize import fsolve, basinhopping
import random
import timeit
# 根據(jù)解的精度確定染色體(chromosome)的長(zhǎng)度
# 需要根據(jù)決策變量的上下邊界來(lái)確定
def getEncodedLength(delta=0.0001, boundarylist=[]):
# 每個(gè)變量的編碼長(zhǎng)度
lengths = []
for i in boundarylist:
lower = i[0]
upper = i[1]
# lamnda 代表匿名函數(shù)f(x)=0,50代表搜索的初始解
res = fsolve(lambda x: ((upper - lower) * 1 / delta) - 2 ** x - 1, 50)
length = int(np.floor(res[0]))
lengths.append(length)
return lengths
pass
# 隨機(jī)生成初始編碼種群
def getIntialPopulation(encodelength, populationSize):
# 隨機(jī)化初始種群為0
chromosomes = np.zeros((populationSize, sum(encodelength)), dtype=np.uint8)
for i in range(populationSize):
chromosomes[i, :] = np.random.randint(0, 2, sum(encodelength))
# print('chromosomes shape:', chromosomes.shape)
return chromosomes
# 染色體解碼得到表現(xiàn)型的解
def decodedChromosome(encodelength, chromosomes, boundarylist, delta=0.0001):
populations = chromosomes.shape[0]
variables = len(encodelength)
decodedvalues = np.zeros((populations, variables))
for k, chromosome in enumerate(chromosomes):
chromosome = chromosome.tolist()
start = 0
for index, length in enumerate(encodelength):
# 將一個(gè)染色體進(jìn)行拆分，得到染色體片段
power = length - 1
# 解碼得到的10進(jìn)制數(shù)字
demical = 0
for i in range(start, length + start):
demical += chromosome[i] * (2 ** power)
power -= 1
lower = boundarylist[index][0]
upper = boundarylist[index][1]
decodedvalue = lower + demical * (upper - lower) / (2 ** length - 1)
decodedvalues[k, index] = decodedvalue
# 開(kāi)始去下一段染色體的編碼
start = length
return decodedvalues
# 得到個(gè)體的適應(yīng)度值及每個(gè)個(gè)體被選擇的累積概率
def getFitnessValue(func, chromosomesdecoded):
# 得到種群規(guī)模和決策變量的個(gè)數(shù)
population, nums = chromosomesdecoded.shape
# 初始化種群的適應(yīng)度值為0
fitnessvalues = np.zeros((population, 1))
# 計(jì)算適應(yīng)度值
for i in range(population):
fitnessvalues[i, 0] = func(chromosomesdecoded[i, :])
# 計(jì)算每個(gè)染色體被選擇的概率
probability = fitnessvalues / np.sum(fitnessvalues)
# 得到每個(gè)染色體被選中的累積概率
cum_probability = np.cumsum(probability)
return fitnessvalues, cum_probability
# 新種群選擇
def selectNewPopulation(chromosomes, cum_probability):
m, n = chromosomes.shape
newpopulation = np.zeros((m, n), dtype=np.uint8)
# 隨機(jī)產(chǎn)生M個(gè)概率值
randoms = np.random.rand(m)
for i, randoma in enumerate(randoms):
logical = cum_probability >= randoma
index = np.where(logical == 1)
# index是tuple,tuple中元素是ndarray
newpopulation[i, :] = chromosomes[index[0][0], :]
return newpopulation
pass
# 新種群交叉
def crossover(population, Pc=0.8):
"""
:param population: 新種群
:param Pc: 交叉概率默認(rèn)是0.8
:return: 交叉后得到的新種群
"""
# 根據(jù)交叉概率計(jì)算需要進(jìn)行交叉的個(gè)體個(gè)數(shù)
m, n = population.shape
numbers = np.uint8(m * Pc)
# 確保進(jìn)行交叉的染色體個(gè)數(shù)是偶數(shù)個(gè)
if numbers % 2 != 0:
numbers += 1
# 交叉后得到的新種群
updatepopulation = np.zeros((m, n), dtype=np.uint8)
# 產(chǎn)生隨機(jī)索引
index = random.sample(range(m), numbers)
# 不進(jìn)行交叉的染色體進(jìn)行復(fù)制
for i in range(m):
if not index.__contains__(i):
updatepopulation[i, :] = population[i, :]
# crossover
while len(index) > 0:
a = index.pop()
b = index.pop()
# 隨機(jī)產(chǎn)生一個(gè)交叉點(diǎn)
crossoverPoint = random.sample(range(1, n), 1)
crossoverPoint = crossoverPoint[0]
# one-single-point crossover
updatepopulation[a, 0:crossoverPoint] = population[a, 0:crossoverPoint]
updatepopulation[a, crossoverPoint:] = population[b, crossoverPoint:]
updatepopulation[b, 0:crossoverPoint] = population[b, 0:crossoverPoint]
updatepopulation[b, crossoverPoint:] = population[a, crossoverPoint:]
return updatepopulation
pass
# 染色體變異
def mutation(population, Pm=0.01):
"""
:param population: 經(jīng)交叉后得到的種群
:param Pm: 變異概率默認(rèn)是0.01
:return: 經(jīng)變異操作后的新種群
"""
updatepopulation = np.copy(population)
m, n = population.shape
# 計(jì)算需要變異的基因個(gè)數(shù)
gene_num = np.uint8(m * n * Pm)
# 將所有的基因按照序號(hào)進(jìn)行10進(jìn)制編碼，則共有m*n個(gè)基因
# 隨機(jī)抽取gene_num個(gè)基因進(jìn)行基本位變異
mutationGeneIndex = random.sample(range(0, m * n), gene_num)
# 確定每個(gè)將要變異的基因在整個(gè)染色體中的基因座(即基因的具體位置)
for gene in mutationGeneIndex:
# 確定變異基因位于第幾個(gè)染色體
chromosomeIndex = gene // n
# 確定變異基因位于當(dāng)前染色體的第幾個(gè)基因位
geneIndex = gene % n
# mutation
if updatepopulation[chromosomeIndex, geneIndex] == 0:
updatepopulation[chromosomeIndex, geneIndex] = 1
else:
updatepopulation[chromosomeIndex, geneIndex] = 0
return updatepopulation
pass
# 定義適應(yīng)度函數(shù)
def fitnessFunction():
return lambda x: 21.5 + x[0] * np.sin(4 * np.pi * x[0]) + x[1] * np.sin(20 * np.pi * x[1])
pass
def main(max_iter=500):
# 每次迭代得到的最優(yōu)解
optimalSolutions = []
optimalValues = []
# 決策變量的取值范圍
decisionVariables = [[-3.0, 12.1], [4.1, 5.8]]
# 得到染色體編碼長(zhǎng)度
lengthEncode = getEncodedLength(boundarylist=decisionVariables)
for iteration in range(max_iter):
# 得到初始種群編碼
chromosomesEncoded = getIntialPopulation(lengthEncode, 10)
# 種群解碼
decoded = decodedChromosome(lengthEncode, chromosomesEncoded, decisionVariables)
# 得到個(gè)體適應(yīng)度值和個(gè)體的累積概率
evalvalues, cum_proba = getFitnessValue(fitnessFunction(), decoded)
# 選擇新的種群
newpopulations = selectNewPopulation(chromosomesEncoded, cum_proba)
# 進(jìn)行交叉操作
crossoverpopulation = crossover(newpopulations)
# mutation
mutationpopulation = mutation(crossoverpopulation)
# 將變異后的種群解碼，得到每輪迭代最終的種群
final_decoded = decodedChromosome(lengthEncode, mutationpopulation, decisionVariables)
# 適應(yīng)度評(píng)價(jià)
fitnessvalues, cum_individual_proba = getFitnessValue(fitnessFunction(), final_decoded)
# 搜索每次迭代的最優(yōu)解，以及最優(yōu)解對(duì)應(yīng)的目標(biāo)函數(shù)的取值
optimalValues.append(np.max(list(fitnessvalues)))
index = np.where(fitnessvalues == max(list(fitnessvalues)))
optimalSolutions.append(final_decoded[index[0][0], :])
# 搜索最優(yōu)解
optimalValue = np.max(optimalValues)
optimalIndex = np.where(optimalValues == optimalValue)
optimalSolution = optimalSolutions[optimalIndex[0][0]]
return optimalSolution, optimalValue
solution, value = main()
print('最優(yōu)解: x1, x2')
print(solution[0], solution[1])
print('最優(yōu)目標(biāo)函數(shù)值:', value)
# 測(cè)量運(yùn)行時(shí)間
elapsedtime = timeit.timeit(stmt=main, number=1)
print('Searching Time Elapsed:(S)', elapsedtime)
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
Python 中提供了一個(gè)官方的標(biāo)準(zhǔn)庫(kù)來(lái)處理這種文件類(lèi)型，那就是 CSV 庫(kù)，這篇文章主要介紹了Python中CSV文件的讀寫(xiě)庫(kù),需要的朋友可以參考下2022-12-12
本文主要介紹了Python list列表刪除元素的4種方法，主要包括del、pop、remove、clear，具有一定的參考價(jià)值，感興趣的可以了解一下2021-11-11
這篇文章主要介紹了Python文件時(shí)間操作步驟代碼詳解,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-04-04
Python實(shí)現(xiàn)字符串反轉(zhuǎn)的常用方法分析【4種方法】
這篇文章主要介紹了Python實(shí)現(xiàn)字符串反轉(zhuǎn)的常用方法,結(jié)合具體實(shí)例形式分析了4種常用的Python字符串反轉(zhuǎn)操作技巧,需要的朋友可以參考下2017-09-09
本文主要介紹了python中pywifi的具體使用，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-03-03
這篇文章主要介紹了Python循環(huán)結(jié)構(gòu)詳解,文中有非常詳細(xì)的代碼示例,對(duì)正在學(xué)習(xí)python的小伙伴們有很好的幫助,需要的朋友可以參考下2021-05-05
python分段函數(shù)的實(shí)現(xiàn)示例
分段函數(shù)是一種數(shù)學(xué)函數(shù),它將定義域分成若干個(gè)區(qū)間,每個(gè)區(qū)間對(duì)應(yīng)一個(gè)函數(shù),本文主要介紹了python分段函數(shù)的實(shí)現(xiàn)示例,具有一定的參考價(jià)值,感興趣的可以了解一下2023-12-12
Python3.5裝飾器原理及應(yīng)用實(shí)例詳解
這篇文章主要介紹了Python3.5裝飾器原理及應(yīng)用,結(jié)合具體實(shí)例形式詳細(xì)分析了Python3.5裝飾器的概念、原理、使用方法及相關(guān)操作注意事項(xiàng),需要的朋友可以參考下2019-04-04
python3 os進(jìn)行嵌套操作的實(shí)例講解
在本篇文章里小編給大家整理了關(guān)于python3 os進(jìn)行嵌套操作的實(shí)例內(nèi)容，有興趣的朋友們可以學(xué)習(xí)下。2020-11-11
python同時(shí)給兩個(gè)收件人發(fā)送郵件的方法
這篇文章主要介紹了python同時(shí)給兩個(gè)收件人發(fā)送郵件的方法,涉及Python使用smtplib包發(fā)送郵件的相關(guān)技巧,需要的朋友可以參考下2015-04-04