用人工智慧方法計算水果難題------遺傳演算法篇

這次我們暫且不寫爬蟲，動態爬蟲以後再寫，因為這幾天一直在糾結一個問題這個問題就是水果難題，如圖所示

題目大言不慚說百分之九十五的人不能解決此問題，問題要我們找出蘋果，香蕉，還有一個水果（是梨子？）的 正整數解（positive integer values），看清楚是正整數解。小學生都知道我們要設X未知數，所以我們把水果看成X1,X2,X3，我們可以得到式1：

式1

上面的例子我們把問題量化了，接下來怎麼辦？大學本科生都有可能不知道，因為我們去掉分母我們可以看出這是一個複雜的多元多次函數，而且只有一個式子看起來無法解（當然沒有我們的貝葉斯參數式子複雜），在這裡我們所需要做的就是找尋一種方法能讓我們的式子得到有效解集，要求的是正整數，所以負數和非正整數都不是有效的。學過數值解析的數學專業學生或者統計專業學生很快就能想到用數值方法來接，學保險和金融工程等工程方面的學生很快就能想到用運籌方法來解。從理論上來說有純數學方法來接，在計算機還沒發明的時代我們偉大的物理學家牛頓和數學家拉弗森發明了牛頓-拉弗森方法。這種方法是在理論上就是一步一步求函數的導數切線，一步步逼近真實解，在微積分方面就是要用泰勒級數展開，取前兩項來進行迭代計算，當然這兩種解釋都是一種方法，但是我們更多的採用泰勒級數的解釋方法，具體的可以參考網上各種牛頓-拉弗森方法（Newton-Raphson method）資料，這裡不再詳述，但是這一類方法有個最大的缺點就是函數可導還有計算量特別大，特別是當多元函數的時候我們必須要計算所有的黑塞矩陣（Hessian Matrix）這讓我們感到十分費時費力。在計算機發張的今天，我們有在人工智慧上的成就，早就了很大一部分科學家創造出了有效的演算法來解決一系列像這類問題一樣的數學難題，特別是我們的人工智慧演算法，個人以為人工只能演算法和數值方法還是有一系列區別的，人工智慧演算法很多都是仿生演算法，學習自然界的演算法，有的演算法數學理論基礎都還不是很完善，但是數值方法的數學理論基礎是建立在數學和數理統計方法上的，數學理論很充實，人工智慧演算法雖然有效但是人工智慧演算法就像我們實驗設計中或者質量控制中的田口弘一先生田口方法與設計的正交實驗設計表一樣，無法得到一個統一的原理認識，但是它的確有效。

人工智慧演算法有很多是求解無約束優化問題和NP難題的，當然也有很多種用途，人工智慧演算法是仿生演算法，所以大多數演算法的啟發來自自然界，也被稱作啟發式演算法，如演算演算法，遺傳演算法，群體智能演算法，蟻群演算法，蜂群演算法，人工神經網路演算法等，相比於我們的機器學習演算法，這一類演算法都比較複雜，但是一旦應用，就十分有效。拿我們的問題來說這裡我們就用遺傳演算法和群體智能演算法來解決問題。

1.問題量化

開始我們把問題量化成

這一種方法我們不能用於直接求解問題，因為我們要把問題轉換成無約束優化問題來求解，我們稍加改變就可以得到

這裡的取絕對值是因為我們需要把問題轉換成無約束優化問題，而取絕對值等於零，無疑就是轉化成了求這個式子的最小值，取絕對值就是最小值只能為0，也就是求x1，x2，x3取什麼值時等於4.這麼一來問題就被轉化為求無約束優化問題了。

2.遺傳演算法求解

在人工智慧演算法中，除了人工神經網路演算法，遺傳演算法是最有效而且比較成熟的方法之一，遺傳演算法的多變異性和遺傳運算元的設計能夠有效時遺傳演算法跳出局部解而找到全局最佳解，並且合適的遺傳運算元選擇設計能夠縮短演算法運行時間，是演算法更加有效。遺傳演算法的局限性也相當明顯，遺傳演算法最大的局限就在於演算法自身的編碼，對於一些問題來說遺傳演算法的編碼過程很複雜，而且遺傳運算元的設計也是必須要參考到很多現實問題因素，所以我個人認為遺傳演算法不僅僅以一個演算法來看待，而是應該像MCMC演算法一樣以一種系統方法來看待，遺傳演算法涉及的東西太多，大家有興趣可以去看看專門的書籍，了解演算法原理過程，演算法原理理解並不太難。這裡我們用R語言來進行演算法的實現，R語言有遺傳演算法的包，一共兩個。一個包叫作mcga包一個包叫做genalg包下面我們分別使用兩個包來求解。具體參數如下

mcga包

mcga(popsize, chsize, crossprob = 1.0, mutateprob = 0.01, elitism = 1, minval, maxval, maxiter = 10, evalFunc)

Arguments

popsize，個體數量，即染色體數目

chsize，基因數量，限參數的數量

crossprob，交配概率，默認為1.0

mutateprob，突變概率，默認為0.01

elitism，精英數量，直接複製到下一代的染色體數目，默認為1

minval，隨機生成初始種群的下邊界值

maxval，隨機生成初始種群的上邊界值

maxiter，繁殖次數，即循環次數，默認為10

evalFunc，適應度函數，用於給個體進行評價

因為需要得到精確值而不是近似值，所以我們要調整參數這裡我們給出調好的參數程序大家可以試試

library(mcga)library(GA)library(foreach)library(iterators)require("mcga")f<-function(x){ return (abs(x[1]/(x[2]+x[3])+x[2]/(x[1]+x[3])+x[3]/(x[1]+x[2])-4))}m <- mcga( popsize=2000, chsize=3, minval=0.0, maxval=999999999, maxiter=25000, crossprob=1, mutateprob=0.01, evalFunc=f)print(m$population[1,])cat("Cost: ",m$costs[1],"
")

這次我們得到的值為

853989867 189086360 38573036

大家可以看出非常大的數值

genalg包

rbga(stringMin=c(), stringMax=c(),

suggestions=NULL,

popSize=200, iters=100,

mutationChance=NA,

elitism=NA,

monitorFunc=NULL, evalFunc=NULL,

showSettings=FALSE, verbose=FALSE)

##

stringMin，設置每個基因的最小值

stringMax，設置每個基因的最大值

suggestions，建議染色體的可選列表

popSize，個體數量，即染色體數目，默認為200

iters，迭代次數，默認為100

mutationChance，突變機會，默認為1/(size+1)，它影響收斂速度和搜索空間的探測，低機率導致更快收斂，高機率增加了搜索空間的跨度。

elitism，精英數量，默認為20%，直接複製到下一代的染色體數目

monitorFunc，監控函數，每產生一代後運行

evalFunc，適應度函數，用於給個體進行評價

showSettings，列印設置，默認為false

verbose，列印演算法運行日誌，默認為false

這裡我們的程序為

l

ibrary(genalg)m2 = rbga(c(0,0,0), c(999999999,999999999,999999999), popSize=2000, iters=25000, evalFunc=f, mutationChance=0.01, verbose=F, #monitorFunc=monitor )print(m2$population[1,])plot(m2)

注意這裡我們的群體和迭代次數和我們上一個包一樣，但是運行時間很長，得到的結果

101041126 137623799 898526155

這裡近似4，真實值為4.000001，可以看出第二個包的效率明顯比第一個低

可以看出收斂到最小值非常緩慢25000次末端的時候才搜索到

下一次我們將會採取更簡單的例子群體演算法來解決這個難題。

推薦閱讀：