一.遺傳算法的基本概念

??????簡單而言，遺傳算法使用群體搜索技術，將種群代表一組問題解， 通過對當前種群施加選擇、交叉和變異等一系列遺傳操作來產(chǎn)生新-一代的種群，并逐步使種群進化到包含近似最優(yōu)解的狀態(tài)。由于遺傳算法是自然遺傳學與計算機科學相互滲透而形成的計算方法，所以遺傳算法中經(jīng)常會使用–些有關自然進化的基礎術語，其中的術語對應關系如下所示。

遺傳學術語遺傳算法操作

群體	可行解集
個體	可行解
染色體	可行解的編碼
基因	可行解編碼的分量
基因形式	遺傳編碼
適應度	評價函數(shù)值
選擇	選擇操作
交叉	交叉操作
變異	變異操作

群體和個體
??????群體是生物進化過程中的一個集團，表示可行解集。
個體是組成群體的單個生物體，表示可行解。

染色體和基因
??????染色體是包含生物體所有遺傳信息的化合物，表示可行解的編碼?；蚴强刂粕矬w某種性狀(即遺傳信息)的基本單位，表示可行解編碼的分量。

遺傳編碼
??????遺傳編碼將優(yōu)化變量轉(zhuǎn)化為基因的組合表示形式，優(yōu)化變量的編碼機制有二進制編碼、格雷編碼、實數(shù)編碼、符號編碼。
二進制編碼

?????? 這里介紹- .下二進制編碼的原理和實現(xiàn)。例如，求實數(shù)區(qū)間[0, 4]上函數(shù)f(x)的最大值，傳統(tǒng)的方法是不斷調(diào)整自變量x本身的值，直到獲得函數(shù)最大值；遺傳算法則不對參數(shù)本身進行調(diào)整，而是首先將參數(shù)進行編碼，形成位串，再對位串進行進化操作。在這里，假設使用二進制編碼形式，我們可以由長度為6的位串表示變量x從“00000”到“11111”， 并將中間的取值映射到實數(shù)區(qū)間[0， 4]內(nèi)。由于從整數(shù)上來看，6位長度的二進制編碼位串可以表示0~63，所以對應[0，4]的區(qū)間，每個相鄰值之間的階躍值為4/63≈0.0635，這個就是編碼精度。一般來說，編碼精度越高，所得到的解的質(zhì)量也越高，意味著解更為優(yōu)良:但同時，由于遺傳操作所需的計算量也更大，因此算法的耗時將更長。因而在解決實際問題時，編碼位數(shù)需要適當選擇。

格雷編碼
??????為改進二進制編碼兩個整數(shù)間海明距離過大的問題，提出了格雷編碼。格雷編碼是指連續(xù)的兩個整數(shù)所對應的編碼之間只有一個碼是不同的，其余碼位完全相同。二進制編碼轉(zhuǎn)格雷編碼的公式是：

?????? 式中：⊕是異或操作，a⊕b表示a和b值不相同則為1，否則為0.
?????? 例如，有一個二進制編碼為0110,下面演示成對應格雷編碼的步驟

二進制最右邊0和其左邊的1做異或，得到1，即得到格雷編碼的最右邊的數(shù)。

二進制右邊第二位的1和其左邊的1異或，得到0，即得到格雷編碼右邊第二位數(shù)。

二進制右邊第三位數(shù)1和其右邊的0異或，得到1，即得到格雷編碼的右邊第三位數(shù)。

最后最高位保持不變。

?????? 最終得到的格雷編碼為0101
?????? 格雷編碼相對于二進制編碼的改進，提升了局部瘦身能力。二進制編碼由于連續(xù)整數(shù)之間存在較大的海明距離，不適合進行連續(xù)函數(shù)的優(yōu)化問題，且局部搜索能力差。

實數(shù)編碼
?????? 基于二進制編碼的個體盡管操作方便，計算簡單，但也存在著一些難以克服的困難而無法滿足所有問題的要求。例如，對于高維、連續(xù)優(yōu)化問題，由于從一個連續(xù)量離散化為一個二進制量本身存在誤差，使得算法很難求得精確解。而要提高解的精度又必須加長編碼串的長度,造成解空間擴大，算法效率下降。同時，二進制編碼也不利于反映所求問題的特定知識，對問題信息和知識利用得不充分也會阻礙算法效率的進一步提高。 為了解決二進制編碼產(chǎn)生的問題，人們在解決一些數(shù)值優(yōu)化問題(尤其是高維、連續(xù)優(yōu)化問題)時，經(jīng)常采用實數(shù)編碼方式。實數(shù)編碼的優(yōu)點是計算精確度高，便于和經(jīng)典連續(xù)優(yōu)化算法結(jié)合，適用于數(shù)值優(yōu)化問題;但其缺點是適用范圍有限，只能用于連續(xù)變量問題。

符號編碼
?????? 在使用符號編碼時，由于使用符號表示不同的基因，不同的符號不能比較大小，但是符號的順序不同卻可以代表不同的意義。在求解TSP問題時，城市用不同的序號表示，城市之間不能比較大小，但是不同序號的順序表示經(jīng)過不同的路徑方案。因此在使用符號編碼時，交叉編譯的結(jié)果是對符號順序的改變，而不是改變符號本身所表達的意義。
符號編碼算例見鏈接：遺傳算法求最短路徑（旅行商問題）python實現(xiàn)

適應度
?????? 適應度即生物群體中個體適應生存環(huán)境的能力。在遺傳算法中，用來評價個體優(yōu)劣的數(shù)學函數(shù)，稱為個體的適應度函數(shù)。遺傳算法在進化搜索中基本上不用外部信息，僅以適應度函數(shù)為依據(jù)。它的目標函數(shù)不受連續(xù)可微的約束，且定義域可以為任意集合。對適應度函數(shù)的唯一要求是，針對輸入可計算出能進行比較的結(jié)果。這- -特 點使得遺傳算法應用范圍很廣。在具體應用中，適應度函數(shù)的設計要結(jié)合求解問題本身的要求而定。適應度函數(shù)評估是選擇操作的依據(jù)，適應度函數(shù)設計直接影響到遺傳算法的性能。常見的適應度函數(shù)構造方法主要有:目標函數(shù)映射成適應度函數(shù)，基于序的適應度函數(shù)等。

遺傳操作
?????? 遺傳操作是優(yōu)選強勢個體的“選擇”、個體間交換基因產(chǎn)生新個體的“交叉”、個體基因信息突變而產(chǎn)生新個體的“變異”這三種變換的統(tǒng)稱。在生物進化過程中，一個群體中生物特性的保持是通過遺傳來繼承的。生物的遺傳主要是通過選擇、交叉、變異三個過程把當前父代群體的遺傳信息遺傳到下一代(子代)成員。與此對應，遺傳算法中最優(yōu)解的搜索過程也模仿生物的這個進化過程，使用所謂的遺傳算子來實現(xiàn)，即選擇算子、交叉算子、變異算子。

選擇算子
?????? 選擇操作是指選擇種群中適應度較高的個體形成子代種群，常用的選擇操作有輪盤賭法 和精英策略。
輪盤賭法

其中，“輪盤賭”選擇法是遺傳算法中最早提出的一種選擇方法，它是一種基于比例的選擇，利用各個個體適應度所占比例的大小來決定其子孫保留的可能性。若某個個體i的適應度為fi,種群大小為NP，則它被選取的概率表示為

個體適應度越大,則其被選擇的機會也越大;反之亦然。為了選擇交叉?zhèn)€體，
需要進行多輪選擇。每- -輪產(chǎn)生一個[0，1]內(nèi) 的均勻隨機數(shù)，將該隨機數(shù)作為選擇指針來確定被選個體。
原理見代碼

#輪盤賭法 選擇1個 # -*- coding: utf-8 -*- import numpy as np s = [2, 3, 10, 5, 12, 19] # 6個個體的適應度值 s_sum = sum(s) # 所有適應度的和 m = 0 r = np.random.random() # 0-1之間的隨機數(shù) c = 0 for i in range(len(s)):m += s[i] / s_sumif r <= m:c = ibreak print(c) # 最后選中個體的序號#輪盤賭法 import numpy as np #個體[1,2,3,4,5,6] 抽3個出來， 歸一化適應度為p=[0.19,0.22,0.18,0.09,0.13,0.19] array=np.random.choice([1,2,3,4,5,6],size=3,p=[0.19,0.22,0.18,0.09,0.13,0.19]) print(array) #輸出[2 6 5]

精英策略

精英策略（最優(yōu)保存策略）是指把適應度最好的個體保留到下一代種群的方法。其基本思路是，當前種群中適應度最高的個體不參與交叉、變異運算，而是用它替換經(jīng)過交叉、變異等操作后所產(chǎn)生的適應度最低的個體。精英策略可以保證最優(yōu)個體不會被交叉變異操作所破壞，它是遺傳算法收斂性的一個保證，但是另一方面，它也容易使某個局部最優(yōu)解不易被淘汰而快速擴散，從而使算法的全局搜索能力不強，因此該方法通常與其他方法配合使用。

交叉算子
?????? 交叉算子:將群體P(t)中選中的各個個體隨機搭配，對每一 對個體，某一概率(交叉概率Pc)交換它們之間的部分染色體。通過交叉，遺傳算法的搜索能力得以飛躍提高。
交叉操作一般分為以下幾個步驟:首先，從交配池中隨機取出要交配的一對個體;然后，根據(jù)位串長度L，對要交配的一對個體，隨機選取[1，L-1]中的一個或多個整數(shù)k作為交叉位置;最后，根據(jù)交叉概率P。實施交叉操作，配對個體在交叉位置處，相互交換各自的部分基因，從而形成新的一對個體。

變異算子
?????? 變異算子:對群體中的每個個體，以某一概率(變異概率Pm)將某一個或某些基因座上的基因值改變?yōu)槠渌牡任换蛑?。根?jù)個體編碼方式的不同，變異方式有:實值變異、二進制變異。對于二進制的變異，對相應的基因值取反:對于實值的變異，對相應的基因值用取值范圍內(nèi)的其他隨機值替代。變異操作的一般步驟為:首先，對種群中所有個體按事先設定的變異概率判斷是否進行變異;然后，對進行變異的個體隨機選擇變異位進行變異。
算法流程

算例實現(xiàn)

?????? ?????? ?????? ?????? ?????? ?????? 算例1
求函數(shù)f(x) = x+10sin(5x)+7cos(4x)的最大值，其中x的取值范圍為[0，10]。 這是一個有多個局部極值的函數(shù)
python版求解

本算例 采取二進制編碼 輪盤賭選擇算子

函數(shù)畫圖

import numpy as np import matplotlib.pyplot as plt from pylab import * mpl.rcParams['font.sans-serif'] = ['SimHei'] mpl.rcParams['axes.unicode_minus'] = Falsex=np.arange(0,10,0.01) y=x+10*np.sin(5*x)+7*np.cos(4*x) plt.plot(x,y) plt.title('f(x)=x+10sin(5x)+7cos(4x)') plt.show() import numpy as np import matplotlib.pyplot as plt from pylab import * mpl.rcParams['font.sans-serif'] = ['SimHei'] mpl.rcParams['axes.unicode_minus'] = False####################初始化參數(shù)##################### NP=50 #種群數(shù)量 L=20 #二進制數(shù)串長度 Pc=0.5 #交叉率 Pm=0.1 #變異率 G=100 #最大遺傳代數(shù) Xs=10 #上限 Xx=0 #下限 f=np.random.randint(0,2,(NP,L)) #隨機獲得二進制 初始種群f.shape (50, 20) 數(shù)值為0,1 如[[0 1 1 1 0 1 1 1 1 1 0 0 0 1 1 0 1 1 0 1] x=np.zeros((NP,1))#存放種群的實數(shù)形式 #nf=f.copy() nf=np.zeros((NP,L))#下一代種群 Fit=np.zeros((NP,1))#存放適應度值 fitneess_value_list = [] # 每一步迭代的最優(yōu)解####################適應度函數(shù)##################### def func1(x):fit = x + 10 * np.sin(5 * x) + 7 * np.cos(4 * x)return fit####################遺傳算法循環(huán)##################### for k in range(G):#遍歷每一代### 將二進制解碼為定義域范圍內(nèi)十進制 ###for i in range(NP):#遍歷每一個個體U=f[i,:]#當前個體m=0for j in range(L):#L二進制數(shù)串長度 # np.power(x1, 3)m = U[j] * np.power(2,j) + m #np.power(2,j)求2的j次方x[i] = Xx + m * (Xs - Xx) / (np.power(2,L) - 1) #已經(jīng)將二進制編碼轉(zhuǎn)換到0-10之間的實數(shù)啦Fit[i] = func1(x[i]) #計算當前個體的適應度值maxFit = np.max(Fit) # 適應度最大值minFit = np.min(Fit) # 適應度最小值rr = np.argwhere(Fit == maxFit)[0][0]#查找適應度最大值所對應的個體索引fBest = f[rr,:] # 歷代最優(yōu)個體 二進制形式xBest = x[rr] #歷代最優(yōu)個體 實數(shù)形式Fit = (Fit - minFit) / (maxFit - minFit) #歸一化適應度值################# 基于輪盤賭的復制操作 #################sum_Fit = sum(Fit)fitvalue = Fit/ sum_Fit #歸一化適應度fitvalue = np.cumsum(fitvalue) #累積求和適應度ms = np.random.random((NP, 1))ms = sort([i for i in ms[:, 0]]) #ms為生成NP個 0-1之間的隨機數(shù),按從小到大排列fiti = 0newi = 0while newi < NP:#遍歷每一個個體if ms[newi] < fitvalue[fiti]: #nf[newi,:]=f[fiti,:] #newi = newi + 1else:fiti = fiti + 1################# 基于概率的交叉操作 ##################思路 ：交換相鄰兩個個體的部分元素 。如01個體交換 23個體之間交換for i in range(0,NP,2):p=np.random.random()#生成一個0-1之間的隨機數(shù)if p<Pc:q=np.random.randint(0,2,(1,L)) #生成一個長度為L的01數(shù)組 shape(1,20)for j in range(L):#遍歷個體每一位元素if q[:,j]==1:temp=np.int(nf[i+1,j]) #下一個個體(i+1) 的第j個元素nf[i+1,j]=nf[i,j]nf[i,j]=temp################# 基于概率的變異操作 #################i=0while i <=np.round(NP*Pm): #np.round(NP*Pm)指定變異個體數(shù)h=np.random.randint(0,NP,1)[0]#隨機選擇一個（0-NP）之間的整數(shù)for j in range(int(np.round(L*Pm))):#指定變異元素個數(shù)g=np.random.randint(0,L,1)[0] #隨機選擇一個(0-L）之間的整數(shù)nf[h,g]=np.abs(1- nf[h,g])#將該元素取反i+=1f=nff[0,:]=fBest#保留最優(yōu)個體在種群中fitneess_value_list.append(maxFit)#存儲歷代最優(yōu)適應度plt.plot(np.array(fitneess_value_list)) plt.title('迭代曲線') plt.show()print('最優(yōu)解',fBest)m=0 for j in range(L): # L二進制數(shù)串長度 # np.power(x1, 3)m = fBest[j] * np.power(2, j) + m # np.power(2,j)求2的j次方 x = Xx + m * (Xs - Xx) / (np.power(2, L) - 1) print('最優(yōu)x(十進制）',x)

從圖中看出最優(yōu)解為24.5左右，參照前面的函數(shù)圖，發(fā)現(xiàn)解正確

精英策略求解代碼

import numpy as np import matplotlib.pyplot as plt from pylab import * mpl.rcParams['font.sans-serif'] = ['SimHei'] mpl.rcParams['axes.unicode_minus'] = False####################初始化參數(shù)##################### NP=50 #種群數(shù)量 L=20 #二進制數(shù)串長度 Pc=0.5 #交叉率 Pm=0.1 #變異率 G=100 #最大遺傳代數(shù) Xs=10 #上限 Xx=0 #下限 f=np.random.randint(0,2,(NP,L)) #隨機獲得二進制 初始種群f.shape (50, 20) 數(shù)值為0,1 如[[0 1 1 1 0 1 1 1 1 1 0 0 0 1 1 0 1 1 0 1] x=np.zeros((NP,1))#存放種群的實數(shù)形式nf=np.zeros((NP,L))#下一代種群 k1=4#Fit=np.zeros((NP,1))#存放適應度值 fitneess_value_list = [] # 每一步迭代的最優(yōu)解####################適應度函數(shù)##################### def func1(x):fit = x + 10 * np.sin(5 * x) + 7 * np.cos(4 * x)return fit####################遺傳算法循環(huán)##################### for k in range(G):#遍歷每一代### 將二進制解碼為定義域范圍內(nèi)十進制 ###for i in range(NP):#遍歷每一個個體U=f[i,:]#當前個體m=0for j in range(L):#L二進制數(shù)串長度 # np.power(x1, 3)m = U[j] * np.power(2,j) + m #np.power(2,j)求2的j次方x[i] = Xx + m * (Xs - Xx) / (np.power(2,L) - 1) #已經(jīng)將二進制編碼轉(zhuǎn)換到0-10之間的實數(shù)啦Fit[i] = func1(x[i]) #計算當前個體的適應度值maxFit = np.max(Fit) # 適應度最大值minFit = np.min(Fit) # 適應度最小值rr = np.argwhere(Fit == maxFit)[0][0]#查找適應度最大值所對應的個體索引fBest = f[rr,:] # 歷代最優(yōu)個體 二進制形式xBest = x[rr] #歷代最優(yōu)個體 實數(shù)形式Fit = (Fit - minFit) / (maxFit - minFit) #歸一化適應度值########精英策略選擇個體############maxkindex=np.argsort(Fit.ravel())[-k1:]#找出適應度值最大的k1個個體索引nf=f #將當代傳到下一代################# 基于概率的交叉操作 ################## 思路 ：交換相鄰兩個個體的部分元素 。如01個體交換 23個體之間交換for i in range(0, NP, 2):if i not in maxkindex and i+1 not in maxkindex:#如果不是最優(yōu)那幾個個體p = np.random.random() # 生成一個0-1之間的隨機數(shù)if p < Pc:q = np.random.randint(0, 2, (1, L)) # 生成一個長度為L的01數(shù)組 shape(1,20)for j in range(L): # 遍歷個體每一位元素if q[:, j] == 1:temp = np.int(nf[i + 1, j]) # 下一個個體(i+1) 的第j個元素nf[i + 1, j] = nf[i, j]nf[i, j] = temp################# 基于概率的變異操作 #################i=0while i <=np.round(NP*Pm): #np.round(NP*Pm)指定變異個體數(shù)h=np.random.randint(0,NP,1)[0]#隨機選擇一個（0-NP）之間的整數(shù)if h not in maxkindex:#如果選中的不是最優(yōu)那幾個個體for j in range(int(np.round(L*Pm))):#指定變異元素個數(shù)g=np.random.randint(0,L,1)[0] #隨機選擇一個(0-L）之間的整數(shù)nf[h,g]=np.abs(1- nf[h,g])#將該元素取反i+=1f = nff[0, :] = fBest # 保留最優(yōu)個體在種群中fitneess_value_list.append(maxFit) # 存儲歷代最優(yōu)適應度plt.plot(np.array(fitneess_value_list)) plt.title('迭代曲線') plt.show()print('最優(yōu)解',fBest)m=0 for j in range(L): # L二進制數(shù)串長度 # np.power(x1, 3)m = fBest[j] * np.power(2, j) + m # np.power(2,j)求2的j次方 x = Xx + m * (Xs - Xx) / (np.power(2, L) - 1) print('最優(yōu)x(十進制）',x)

?????? ?????? ?????? ?????? ?????? ?????? 算例2
求解Z=2a+xx-acos2πx+yy-acos2πy的極小值

import numpy as np import matplotlib.pyplot as pltdef fitness_func(X):# 目標函數(shù)，即適應度值，X是種群的表現(xiàn)型a = 10pi = np.pix = X[:, 0]y = X[:, 1]return 2 * a + x ** 2 - a * np.cos(2 * pi * x) + y ** 2 - a * np.cos(2 * 3.14 * y)def decode(x, a, b):"""解碼，即基因型到表現(xiàn)型"""xt = 0for i in range(len(x)):xt = xt + x[i] * np.power(2, i)return a + xt * (b - a) / (np.power(2, len(x)) - 1)def decode_X(X: np.array):"""對整個種群的基因解碼，上面的decode是對某個染色體的某個變量進行解碼"""X2 = np.zeros((X.shape[0], 2))for i in range(X.shape[0]):xi = decode(X[i, :20], -5, 5)yi = decode(X[i, 20:], -5, 5)X2[i, :] = np.array([xi, yi])return X2def select(X, fitness):"""根據(jù)輪盤賭法選擇優(yōu)秀個體"""fitness = 1 / fitness # fitness越小表示越優(yōu)秀，被選中的概率越大，做 1/fitness 處理fitness = fitness / fitness.sum() # 歸一化idx = np.array(list(range(X.shape[0])))X2_idx = np.random.choice(idx, size=X.shape[0], p=fitness) # 根據(jù)概率選擇X2 = X[X2_idx, :]return X2def crossover(X, c):"""按順序選擇2個個體以概率c進行交叉操作"""for i in range(0, X.shape[0], 2):xa = X[i, :]xb = X[i + 1, :]for j in range(X.shape[1]):# 產(chǎn)生0-1區(qū)間的均勻分布隨機數(shù)，判斷是否需要進行交叉替換if np.random.rand() <= c:xa[j], xb[j] = xb[j], xa[j]X[i, :] = xaX[i + 1, :] = xbreturn Xdef mutation(X, m):"""變異操作"""for i in range(X.shape[0]):for j in range(X.shape[1]):if np.random.rand() <= m:X[i, j] = (X[i, j] + 1) % 2return Xdef ga():"""遺傳算法主函數(shù)"""c = 0.3 # 交叉概率m = 0.05 # 變異概率best_fitness = [] # 記錄每次迭代的效果best_xy = []iter_num = 100 # 最大迭代次數(shù)X0 = np.random.randint(0, 2, (50, 40)) # 隨機初始化種群，為50*40的0-1矩陣for i in range(iter_num):X1 = decode_X(X0) # 染色體解碼fitness = fitness_func(X1) # 計算個體適應度X2 = select(X0, fitness) # 選擇操作X3 = crossover(X2, c) # 交叉操作X4 = mutation(X3, m) # 變異操作# 計算一輪迭代的效果X5 = decode_X(X4)fitness = fitness_func(X5)best_fitness.append(fitness.min())x, y = X5[fitness.argmin()]best_xy.append((x, y))X0 = X4# 多次迭代后的最終效果print("最優(yōu)值是：%.5f" % best_fitness[-1])print("最優(yōu)解是：x=%.5f, y=%.5f" % best_xy[-1])# 最優(yōu)值是：0.00000# 最優(yōu)解是：x=0.00000, y=-0.00000# 打印效果plt.plot(best_fitness, color='r')plt.show() ga()

?????? ?????? ?????? ?????? ?????? ?????? 算例3
前面都是講解的二進制編碼，下面講解下實數(shù)編碼
例子見鏈接：
https://blog.csdn.net/kobeyu652453/article/details/109527260

本文通過源代碼 和算例介紹了遺傳算法基本流程、以及二進制編碼、實數(shù)編碼、輪盤賭和精英策略選擇算子、基于概率的交叉和變異算子。下篇博客通過源碼介紹遺傳算法如何求解帶約束問題
遺傳算法求解帶約束優(yōu)化問題（源碼實現(xiàn)）

作者：電氣 余登武

總結(jié)

以上是生活随笔為你收集整理的万字字符长文带你了解遗传算法（有几个算例源码）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。