作者：金良([email protected]) csdn部落格：http://blog.csdn.net/u012176591
遺傳算法的基本概念
這是基于 進化論 而啟發出來的一種很特别的 機器學習 技巧。 我最近漸漸明白到它可能是破解 strong AI 的關鍵。 Ben Goertzel 和我見面的談話中也特别注重這一方向。 原來 Alan Turing 很早就看到 進化 和 machine learning 之間有明顯關系，而現時機器學習的一個很有名的研究者 Leslie Valiant 也在新書 (English version) 中談論這課題。
機器學習的目的就是要在浩瀚的 假設空間 (hypothesis space) 中尋找那些能正确地解釋現實的語句。 例如嬰孩可能用「有胡子就是爸爸」 來解釋身邊出現的人。
問題是假設空間太大，我們如同「在禾稈推裡找一隻針」，單靠 brute force 不是辦法。
進化算法就是在很大的空間裡 尋找某個 最佳答案 (optimal solution) 的一個很強的技巧。 它把需要尋找的 candidates 模拟成一個「人口」population，任由這些 candidates 在某個人工的環境下競争， 然後，每次選取得分最高的一小撮樣本，讓它們「交配」，即 基因重組 (genetic recombination)，那樣産生新一批的 candidates， 如此逐漸推向越來越優秀的 solutions。
舉個例子，研究者用進化算法進化出一些電子電路，例如用于音響的濾波器 (filter) ，其 performance 甚至比人手設計的還要優越。 而且，那電路很不規則而且難了解，人們不知道它是如何運作的，有些部分甚至有多馀的元件存在。 那是因為進化的過程中，有時一些表面上沒用的「器官」在組合之後或許變有用，是以進化的結果也常保留很多「廢物 junk」。
具體的算法怎樣？
初始時，預備一個 population，可以是随機産生的。
對每個 candidate 進行 估值 (evaluation)，即是讓這個 candidate 在人工的世界裡生存。 例如我們測試它在所需的功能的表現如何。 那計分的方法叫 objective function 「目的函數」。
選取表現最好的 N 個 candidates，進行 變種 mutation 或 重組 recombination。 變種是作用在單個 candidate 上的，重組則需要一對 candidates。 那就涉及到我們怎樣将設計空間的元素表示為「基因」，于是有所謂 表述 (representation) 的問題。 這編碼是要由研究者設計的。
在評分的時候，可以容許那些 candidates 在環境中互相合作亦同時競争，那叫 cooperative evolution。 我覺得 Genifer 有需要用這方法，因為在知識庫中的每個知識片段，是要和其他知識互相作用，那邏輯系統才能推導出有意思的結果。
待求解的問題
尋找最優解的函數表達式為
f(x,y)=−20e−0.2x2+y22√−ecos2πx+cos2πy2+20+e
該函數的最小值為
f(0,0)=0
其函數圖像
作圖源碼
from mpl_toolkits.mplot3d import Axes3D
import numpy as np
fig = figure()
ax = Axes3D(fig)
X = np.arange(-3.0, 12.1, 0.08)
Y = np.arange(-4.1, 5.8, 0.08)
X, Y = np.meshgrid(X, Y)
Z = -20*np.exp(-0.2*np.sqrt(np.sqrt((X**2+Y**2)/2)))+20+np.e-np.exp((np.cos(2*np.pi*X)+np.sin(2*np.pi*Y))/2)
ax.plot_surface(X, Y, Z, rstride=1, cstride=1, cmap='cool')
一個變量的二進制串位數的确定
包括斷點的區間[a,b]，精度p，共有N個數，則N=⌈a−bp⌉+1。用m表示二進制位數，分析：
當N=4時，m=2，
當N=5時，m=3。
觀察得 2m−1
在程式中可表示為
m=⌈log2N⌉=⌈log2(⌈a−bp⌉+1)⌉
程式代碼
import numpy as np
import matplotlib.pyplot as plt
# 函數定義
def func(x):
y = -20*np.exp(-0.2*np.sqrt(np.sqrt((x[0]**2+x[1]**2)/2)))-np.exp((np.cos(2*np.pi*x[0])+np.cos(2*np.pi*x[1]))/2)+20+np.e
return y
#适應度計算
def getfitness(pop2):
pop = trans2to10(pop2)
fitness = 20*np.exp(-0.2*np.sqrt(np.sqrt((pop[:,0]**2+pop[:,1]**2)/2)))+np.exp((np.cos(2*np.pi*pop[:,0])+np.cos(2*np.pi*pop[:,1]))/2)
return fitness
def getcumsumrate(fitness):
cumsumrate = fitness.cumsum()/sum(fitness)
return cumsumrate
#根據參數(本例有兩個參數)的取值範圍和精度要求獲得基因的個數
def getbitlength(range =((-3,12.1,0.0001),(-4.1,5.8,0.0001))):
N1 = np.ceil((range[0][1]-range[0][0])/range[0][2])+1
bitlength1 = np.int(np.ceil(np.log2(N1)))
N2 = np.ceil((range[1][1]-range[1][0])/range[1][2])+1
bitlength2 = np.int(np.ceil(np.log2(N2)))
return bitlength1,bitlength2
def getpop2(bitlength=(18,17),sizepop=20):
pop2 = np.random.rand(sizepop,sum(bitlength))
pop2[pop2>0.5] = 1
pop2[pop2<=0.5] = 0
return pop2
# 解碼
def to2_10(binlist):
val = 0
pow = 1
for i in range(len(binlist))[::-1]:
val += binlist[i]*pow
pow *= 2
return val
def trans2to10(pop2,leninfo = (18,17),rang = ((-3,12.1,0.0001),(-4.1,5.8,0.0001))):
row,column = pop2.shape
pop10 = np.zeros((row,2))
for i in range(row):
pop10[i][0] = rang[0][2]*to2_10(pop2[i][:leninfo[0]])+rang[0][0]
pop10[i][1] = rang[1][2]*to2_10(pop2[i][leninfo[0]:])+rang[1][0]
return pop10
def getselectpair(cumsumrate):#用轉盤算法根據累積機率選擇兩個個體
while True:
flag = cumsumrate-np.random.rand() #rand() [0,1)
sel0 = 0
while flag[sel0]<0 :
sel0 += 1
flag = cumsumrate-np.random.rand() #rand() [0,1)
sel1 = 0
while flag[sel1]<0 :
sel1 += 1
if sel0 != sel1:
break
return [sel0,sel1]
sizepop = 50 #種群規模
genermax = 100 #疊代次數
ratecross = 0.70 #染色體交配率
ratemutation = 0.12 #基因突變率
leninfo = getbitlength()
pop2 = getpop2(sizepop=sizepop)
fitnesslog = []
while genermax > 0:
genermax -= 1
pop2new = np.zeros(pop2.shape)
fitness = getfitness(pop2)
fitnesslog.append([max(fitness),mean(fitness)])
cumsumrate = getcumsumrate(fitness)
for i in range(0,sizepop,2):
selectpair = getselectpair(cumsumrate)
pop2new[i,:] = pop2[selectpair[0]].copy()
pop2new[i+1,:] = pop2[selectpair[1]].copy()
rand2 = np.random.rand(2)
if rand2[0]<=ratecross:#交叉操作，對應變量1
crossbit0 = np.int(np.random.rand()*leninfo[0])
pop2new[i,crossbit0:leninfo[0]],pop2new[i+1,crossbit0:leninfo[0]]=pop2new[i+1,crossbit0:leninfo[0]],pop2new[i,crossbit0:leninfo[0]]
if rand2[1]<=ratecross:#交叉操作，對應變量2
crossbit1 = np.int(np.random.rand()*leninfo[1])+leninfo[0]
pop2new[i,crossbit1:],pop2new[i+1,crossbit1:]=pop2new[i+1,crossbit1:],pop2new[i,crossbit1:]
rand4 = np.random.rand(4)
if rand4[0] < ratemutation:
mutationbit = np.int(rand4[1]*sum(leninfo))
pop2new[i,mutationbit] = np.abs(pop2new[i,mutationbit]-1)
if rand4[2] < ratemutation:
mutationbit = np.int(rand4[3]*sum(leninfo))
pop2new[i+1,mutationbit] = np.abs(pop2new[i+1,mutationbit]-1)
pop2 = pop2new
fitnesslog = np.array(fitnesslog)
bestlog = np.zeros(fitnesslog.shape[0])
bestlog[0] = fitnesslog[0,0]
for i in range(1,fitnesslog.shape[0]):
if(fitnesslog[i,0])>bestlog[i-1]:
bestlog[i]=fitnesslog[i,0]
else:
bestlog[i]=bestlog[i-1]
plt.plot(fitnesslog[:,0])
plt.plot(fitnesslog[:,1])
plt.plot(bestlog)
plt.legend(('max','mean','best'),loc='best')
進一步閱讀
HELLO，遺傳算法！，位址http://garfileo.is-programmer.com/2011/2/19/hello-ga.24563.html
python面向對象實作的遺傳算法，有源代碼