快捷導(dǎo)航

python實(shí)現(xiàn)高效的遺傳算法

更新時(shí)間：2021年04月07日 11:17:38 作者：哇哇咔咔MZ：y

這篇文章主要介紹了python實(shí)現(xiàn)高效的遺傳算法。想了解算法的同學(xué)，可以參考下

遺傳算法屬于一種優(yōu)化算法。

如果你有一個(gè)待優(yōu)化函數(shù)，可以考慮次算法。假設(shè)你有一個(gè)變量x，通過(guò)某個(gè)函數(shù)可以求出對(duì)應(yīng)的y，那么你通過(guò)預(yù)設(shè)的x可求出y_pred，y_pred差距與你需要的y當(dāng)然越接近越好，這就需要引入適應(yīng)度（fitness）的概念。假設(shè)

fitness = 1/(1+ads(y_pred - y)),那么誤差越小，適應(yīng)度越大，即該個(gè)體越易于存活。

設(shè)計(jì)該算法的思路如下：

（1）初始化種群，即在我需要的區(qū)間如[-100,100]內(nèi)random一堆初始個(gè)體[x1,x2,x3...],這些個(gè)體是10進(jìn)制形式的，為了后面的交叉與變異我們不妨將其轉(zhuǎn)化為二進(jìn)制形式。那么現(xiàn)在的問(wèn)題是二進(jìn)制取多少位合適呢？即編碼（code）的長(zhǎng)度是多少呢？

這就涉及一些信號(hào)方面的知識(shí)，比如兩位的二進(jìn)制表示的最大值是3（11），可以將區(qū)間化為4分，那么每一份區(qū)間range長(zhǎng)度range/4，我們只需要讓range/n小于我們定義的精度即可。n是二進(jìn)制需要表示的最大，可以反解出二進(jìn)制位數(shù) 。

（2）我們需要編寫(xiě)編碼與解碼函數(shù)。即code：將x1，x2...化為二進(jìn)制，decode：在交叉變異后重新得到十進(jìn)制數(shù)，用于計(jì)算fitness。

（3）交叉后變異函數(shù)編寫(xiě)都很簡(jiǎn)單，random一個(gè)point，指定兩個(gè)x在point位置進(jìn)行切片交換即是交叉。變異也是random一個(gè)point，讓其值0變?yōu)?,1變?yōu)?。

（4）得到交叉變異后的個(gè)體，需要計(jì)算fitness進(jìn)行種群淘汰，保留fitness最高的一部分種群。

（5）將最優(yōu)的個(gè)體繼續(xù)上面的操作，直到你定義的iteration結(jié)束為止。

不說(shuō)了，上代碼：

import numpy as np
import pandas as pd
import random
from scipy.optimize import fsolve
import matplotlib.pyplot as plt
import heapq
from sklearn.model_selection import train_test_split
from tkinter import _flatten
from sklearn.utils import shuffle
from sklearn import preprocessing
from sklearn.decomposition import PCA
from matplotlib import rcParams
 
 
 
# 求染色體長(zhǎng)度
def getEncodeLength(decisionvariables, delta):
 # 將每個(gè)變量的編碼長(zhǎng)度放入數(shù)組
 lengths = []
 for decisionvar in decisionvariables:
  uper = decisionvar[1]
  low = decisionvar[0]
  # res()返回一個(gè)數(shù)組
  res = fsolve(lambda x: ((uper - low) / delta - 2 ** x + 1), 30)
  # ceil()向上取整
  length = int(np.ceil(res[0]))
  lengths.append(length)
 # print("染色體長(zhǎng)度:", lengths)
 return lengths
 
 
# 隨機(jī)生成初始化種群
def getinitialPopulation(length, populationSize):
 chromsomes = np.zeros((populationSize, length), dtype=np.int)
 for popusize in range(populationSize):
  # np.random.randit()產(chǎn)生[0,2)之間的隨機(jī)整數(shù)，第三個(gè)參數(shù)表示隨機(jī)數(shù)的數(shù)量
  chromsomes[popusize, :] = np.random.randint(0, 2, length)
 return chromsomes
 
 
# 染色體解碼得到表現(xiàn)形的解
def getDecode(population, encodelength, decisionvariables, delta):
 # 得到population中有幾個(gè)元素
 populationsize = population.shape[0]
 length = len(encodelength)
 decodeVariables = np.zeros((populationsize, length), dtype=np.float)
 # 將染色體拆分添加到解碼數(shù)組decodeVariables中
 for i, populationchild in enumerate(population):
  # 設(shè)置起始點(diǎn)
  start = 0 
  for j, lengthchild in enumerate(encodelength):
   power = lengthchild - 1
   decimal = 0
   start_end = start + lengthchild
   for k in range(start, start_end):
    # 二進(jìn)制轉(zhuǎn)為十進(jìn)制
    decimal += populationchild[k] * (2 ** power)
    power = power - 1
   # 從下一個(gè)染色體開(kāi)始
   start = start_end
   lower = decisionvariables[j][0]
   uper = decisionvariables[j][1]
   # 轉(zhuǎn)換為表現(xiàn)形
   decodevalue = lower + decimal * (uper - lower) / (2 ** lengthchild - 1)
   # 將解添加到數(shù)組中
   decodeVariables[i][j] = decodevalue
   
 return decodeVariables
 
 
# 選擇新的種群
def selectNewPopulation(decodepopu, cum_probability):
 # 獲取種群的規(guī)模和
 m, n = decodepopu.shape
 # 初始化新種群
 newPopulation = np.zeros((m, n))
 for i in range(m):
  # 產(chǎn)生一個(gè)0到1之間的隨機(jī)數(shù)
  randomnum = np.random.random()
  # 輪盤(pán)賭選擇
  for j in range(m):
   if (randomnum < cum_probability[j]):
    newPopulation[i] = decodepopu[j]
    break
 return newPopulation
 
 
# 新種群交叉
def crossNewPopulation(newpopu, prob):
 m, n = newpopu.shape
 # uint8將數(shù)值轉(zhuǎn)換為無(wú)符號(hào)整型
 numbers = np.uint8(m * prob)
 # 如果選擇的交叉數(shù)量為奇數(shù)，則數(shù)量加1
 if numbers % 2 != 0:
  numbers = numbers + 1
 # 初始化新的交叉種群
 updatepopulation = np.zeros((m, n), dtype=np.uint8)
 # 隨機(jī)生成需要交叉的染色體的索引號(hào)
 index = random.sample(range(m), numbers)
 # 不需要交叉的染色體直接復(fù)制到新的種群中
 for i in range(m):
  if not index.__contains__(i):
   updatepopulation[i] = newpopu[i]
 # 交叉操作
 j = 0
 while j < numbers:
  # 隨機(jī)生成一個(gè)交叉點(diǎn)，np.random.randint()返回的是一個(gè)列表
  crosspoint = np.random.randint(0, n, 1)
  crossPoint = crosspoint[0]
  # a = index[j]
  # b = index[j+1]
  updatepopulation[index[j]][0:crossPoint] = newpopu[index[j]][0:crossPoint]
  updatepopulation[index[j]][crossPoint:] = newpopu[index[j + 1]][crossPoint:]
  updatepopulation[index[j + 1]][0:crossPoint] = newpopu[j + 1][0:crossPoint]
  updatepopulation[index[j + 1]][crossPoint:] = newpopu[index[j]][crossPoint:]
  j = j + 2
 return updatepopulation
 
 
# 變異操作
def mutation(crosspopulation, mutaprob):
 # 初始化變異種群
 mutationpopu = np.copy(crosspopulation)
 m, n = crosspopulation.shape
 # 計(jì)算需要變異的基因數(shù)量
 mutationnums = np.uint8(m * n * mutaprob)
 # 隨機(jī)生成變異基因的位置
 mutationindex = random.sample(range(m * n), mutationnums)
 # 變異操作
 for geneindex in mutationindex:
  # np.floor()向下取整返回的是float型
  row = np.uint8(np.floor(geneindex / n))
  colume = geneindex % n
  if mutationpopu[row][colume] == 0:
   mutationpopu[row][colume] = 1
  else:
   mutationpopu[row][colume] = 0
 return mutationpopu
 
 
# 找到重新生成的種群中適應(yīng)度值最大的染色體生成新種群
def findMaxPopulation(population, maxevaluation, maxSize):
 #將數(shù)組轉(zhuǎn)換為列表
 #maxevalue = maxevaluation.flatten()
 maxevaluelist = maxevaluation
 # 找到前100個(gè)適應(yīng)度最大的染色體的索引
 maxIndex = map(maxevaluelist.index, heapq.nlargest(maxSize, maxevaluelist))
 index = list(maxIndex)
 colume = population.shape[1]
 # 根據(jù)索引生成新的種群
 maxPopulation = np.zeros((maxSize, colume))
 i = 0
 for ind in index:
  maxPopulation[i] = population[ind]
  i = i + 1
 return maxPopulation
 
 
 
# 得到每個(gè)個(gè)體的適應(yīng)度值及累計(jì)概率
def getFitnessValue(decode,x_train,y_train):
 # 得到種群的規(guī)模和決策變量的個(gè)數(shù)
 popusize, decisionvar = decode.shape
 
 fitnessValue = []
 for j in range(len(decode)):
  W1 = decode[j][0:20].reshape(4,5)
  V1 = decode[j][20:25].T
  W2 = decode[j][25:45].reshape(5,4)
  V2 = decode[j][45:].T
  error_all = []
  for i in range(len(x_train)):
   #get values of hidde layer
   X2 = sigmoid(x_train[i].T.dot(W1)+V1)
   #get values of prediction y
   Y_hat = sigmoid(X2.T.dot(W2)+V2)
   #get error when input dimension is i
   error = sum(abs(Y_hat - y_train[i]))
   error_all.append(error)
 
  #get fitness when W and V is j
  fitnessValue.append(1/(1+sum(error_all)))
 
 # 得到每個(gè)個(gè)體被選擇的概率
 probability = fitnessValue / np.sum(fitnessValue)
 # 得到每個(gè)染色體被選中的累積概率，用于輪盤(pán)賭算子使用
 cum_probability = np.cumsum(probability)
 return fitnessValue, cum_probability
 
 
 
def getFitnessValue_accuracy(decode,x_train,y_train):
 # 得到種群的規(guī)模和決策變量的個(gè)數(shù)
 popusize, decisionvar = decode.shape
 
 fitnessValue = []
 for j in range(len(decode)):
  W1 = decode[j][0:20].reshape(4,5)
  V1 = decode[j][20:25].T
  W2 = decode[j][25:45].reshape(5,4)
  V2 = decode[j][45:].T
  accuracy = []
  for i in range(len(x_train)):
   #get values of hidde layer
   X2 = sigmoid(x_train[i].T.dot(W1)+V1)
   #get values of prediction y
   Y_hat = sigmoid(X2.T.dot(W2)+V2)
   #get error when input dimension is i
   accuracy.append(sum(abs(np.round(Y_hat) - y_train[i])))
  fitnessValue.append(sum([m == 0 for m in accuracy])/len(accuracy))
 # 得到每個(gè)個(gè)體被選擇的概率
 probability = fitnessValue / np.sum(fitnessValue)
 # 得到每個(gè)染色體被選中的累積概率，用于輪盤(pán)賭算子使用
 cum_probability = np.cumsum(probability)
 return fitnessValue, cum_probability
 
 
def getXY():
 # 要打開(kāi)的文件名
 data_set = pd.read_csv('all-bp.csv', header=None)
 # 取出“特征”和“標(biāo)簽”，并做了轉(zhuǎn)置，將列轉(zhuǎn)置為行
 X_minMax1 = data_set.iloc[:, 0:12].values
 # 前12列是特征
 min_max_scaler = preprocessing.MinMaxScaler()
 X_minMax = min_max_scaler.fit_transform(X_minMax1) # 0-1 range
 transfer = PCA(n_components=0.9)
 data1 = transfer.fit_transform(X_minMax)
 #print('PCA processed shape:',data1.shape)
 X = data1
 Y = data_set.iloc[ : , 12:16].values # 后3列是標(biāo)簽
 
 # 分訓(xùn)練和測(cè)試集
 x_train, x_test, y_train, y_test = train_test_split(X, Y, test_size=0.3)
 return x_train, x_test, y_train, y_test
 
 
def sigmoid(z):
 return 1 / (1 + np.exp(-z))

上面的計(jì)算適應(yīng)度函數(shù)需要自己更具實(shí)際情況調(diào)整。

optimalvalue = []
optimalvariables = []
 
# 兩個(gè)決策變量的上下界，多維數(shù)組之間必須加逗號(hào)
decisionVariables = [[-100,100]]*49
# 精度
delta = 0.001
# 獲取染色體長(zhǎng)度
EncodeLength = getEncodeLength(decisionVariables, delta)
# 種群數(shù)量
initialPopuSize = 100
# 初始生成100個(gè)種群,20,5,20,4分別對(duì)用W1，V1，W2，V2
population = getinitialPopulation(sum(EncodeLength), initialPopuSize)
print("polpupation.shape:",population.shape)
# 最大進(jìn)化代數(shù)
maxgeneration = 4000
# 交叉概率
prob = 0.8
# 變異概率
mutationprob = 0.5
# 新生成的種群數(shù)量
maxPopuSize = 30
x_train, x_test, y_train, y_test = getXY()
 
 
for generation in range(maxgeneration):
 # 對(duì)種群解碼得到表現(xiàn)形
 print(generation)
 decode = getDecode(population, EncodeLength, decisionVariables, delta)
 #print('the shape of decode:',decode.shape
 
 # 得到適應(yīng)度值和累計(jì)概率值
 evaluation, cum_proba = getFitnessValue_accuracy(decode,x_train,y_train)
 # 選擇新的種群
 newpopulations = selectNewPopulation(population, cum_proba)
 # 新種群交叉
 crossPopulations = crossNewPopulation(newpopulations, prob)
 # 變異操作
 mutationpopulation = mutation(crossPopulations, mutationprob)
 
 # 將父母和子女合并為新的種群
 totalpopulation = np.vstack((population, mutationpopulation))
 # 最終解碼
 final_decode = getDecode(totalpopulation, EncodeLength, decisionVariables, delta)
 # 適應(yīng)度評(píng)估
 final_evaluation, final_cumprob = getFitnessValue_accuracy(final_decode,x_train,y_train)
 #選出適應(yīng)度最大的100個(gè)重新生成種群
 population = findMaxPopulation(totalpopulation, final_evaluation, maxPopuSize)
 
 # 找到本輪中適應(yīng)度最大的值
 optimalvalue.append(np.max(final_evaluation))
 index = np.where(final_evaluation == max(final_evaluation))
 optimalvariables.append(list(final_decode[index[0][0]]))

fig = plt.figure(dpi = 160,figsize=(5,4)) 
config = {
"font.family":"serif", #serif
"font.size": 10,
"mathtext.fontset":'stix',
}
rcParams.update(config)
plt.plot(np.arange(len(optimalvalue)), optimalvalue, color="y", lw=0.8, ls='-', marker='o', ms=8)
# 圖例設(shè)置
plt.xlabel('Iteration')
plt.ylabel('Accuracy')
plt.show()