⑴ 遺傳演算法的基本原理
遺傳演算法的基本原理和方法
一、編碼
編碼：把一個問題的可行解從其解空間轉換到遺傳演算法的搜索空間的轉換方法。
解碼（解碼）：遺傳演算法解空間向問題空間的轉換。
二進制編碼的缺點是漢明懸崖（Hamming Cliff），就是在某些相鄰整數的二進制代碼之間有很大的漢明距離，使得遺傳演算法的交叉和突變都難以跨越。
格雷碼（Gray Code）：在相鄰整數之間漢明距離都為1。
（較好）有意義的積木塊編碼規則：所定編碼應當易於生成與所求問題相關的短距和低階的積木塊；最小字元集編碼規則，所定編碼應採用最小字元集以使問題得到自然的表示或描述。
二進制編碼比十進制編碼搜索能力強，但不能保持群體穩定性。
動態參數編碼（Dynamic Paremeter Coding）：為了得到很高的精度，讓遺傳演算法從很粗糙的精度開始收斂，當遺傳演算法找到一個區域後，就將搜索現在在這個區域，重新編碼，重新啟動，重復這一過程，直到達到要求的精度為止。
編碼方法：
1、 二進制編碼方法
缺點：存在著連續函數離散化時的映射誤差。不能直接反映出所求問題的本身結構特徵，不便於開發針對問題的專門知識的遺傳運算運算元，很難滿足積木塊編碼原則
2、 格雷碼編碼滾如：連續的兩個整數所對應的編碼之間僅僅只有一個碼位是不同的，其餘碼位都相同。
3、 浮點數編碼方法：個體的每個基因值用某一范圍內的某個浮點數來表示，個體的編碼長度等於其決策變數的位數。
4、 各參數級聯編碼：對含有多個變數的個體進行編碼的方法。通常將各個參數分別以某種編碼方法進行編碼，然後再將他們的編碼按照一定順序連接在一起就組成了表示全部參數的個體編碼。
5、 多參數交叉編碼：將各個參數中起主要作用的碼位集中在一起，這樣它們就不易於被遺傳運算元破壞掉。
評估編碼的三個規范：完備性、健全性、非冗餘性。
二、選擇
遺傳演算法中的選擇操作就是用來確定如何從父代群體中按某種方法選取那些個體遺傳到下一代群體中的一種遺傳運算，用來確定重組或交叉個體，以及被選個體將產生多少個子代個體。
常用的選擇運算元：
1、 輪盤賭選擇（Roulette Wheel Selection）：是一種回放式隨機采樣方法。每個個體進入下一代的概率等於它的適應度值與整個種群中個體適應度值和的比例。選擇誤差較大。
2、 隨機競爭選擇（Stochastic Tournament）：每次按輪盤賭選擇一對個體，然後讓這兩個個體進行競爭，適應度高的被選中，如此反復，直到選滿為止。
3、 最佳保留選擇：首先按輪盤賭選擇方法執行遺傳演算法的選擇操作，然後將當前群體中適應度最高的大宏啟個體結構完整地復制到下一代群體中。
4、 無回放隨機選擇（也叫期望值選擇Excepted Value Selection）：根據每個個體在下一代群體中的生存期望來進行隨機選擇運算。方法如下
（1） 計算群體中每個個體在下一代群體中的生存期望數目N。
（2） 若某一個體被選中參與交叉運算，則它在下一代中的生存期望數目減去0.5，若某一個體未被選中參與交叉運算，則它絕配在下一代中的生存期望數目減去1.0。
（3） 隨著選擇過程的進行，若某一個體的生存期望數目小於0時，則該個體就不再有機會被選中。
5、 確定式選擇：按照一種確定的方式來進行選擇操作。具體操作過程如下：
（1） 計算群體中各個個體在下一代群體中的期望生存數目N。
（2） 用N的整數部分確定各個對應個體在下一代群體中的生存數目。
（3） 用N的小數部分對個體進行降序排列，順序取前M個個體加入到下一代群體中。至此可完全確定出下一代群體中M個個體。
6、無回放余數隨機選擇：可確保適應度比平均適應度大的一些個體能夠被遺傳到下一代群體中，因而選擇誤差比較小。
7、均勻排序：對群體中的所有個體按期適應度大小進行排序，基於這個排序來分配各個個體被選中的概率。
8、最佳保存策略：當前群體中適應度最高的個體不參與交叉運算和變異運算，而是用它來代替掉本代群體中經過交叉、變異等操作後所產生的適應度最低的個體。
9、隨機聯賽選擇：每次選取幾個個體中適應度最高的一個個體遺傳到下一代群體中。
10、排擠選擇：新生成的子代將代替或排擠相似的舊父代個體，提高群體的多樣性。
三、交叉
遺傳演算法的交叉操作，是指對兩個相互配對的染色體按某種方式相互交換其部分基因，從而形成兩個新的個體。
適用於二進制編碼個體或浮點數編碼個體的交叉運算元：
1、單點交叉（One－pointCrossover）：指在個體編碼串中只隨機設置一個交叉點，然後再該點相互交換兩個配對個體的部分染色體。
2、兩點交叉與多點交叉：
（1） 兩點交叉（Two－pointCrossover）：在個體編碼串中隨機設置了兩個交叉點，然後再進行部分基因交換。
（2） 多點交叉（Multi－pointCrossover）
3、均勻交叉（也稱一致交叉，UniformCrossover）：兩個配對個體的每個基因座上的基因都以相同的交叉概率進行交換，從而形成兩個新個體。
4、算術交叉（ArithmeticCrossover）：由兩個個體的線性組合而產生出兩個新的個體。該操作對象一般是由浮點數編碼表示的個體。
四、變異
遺傳演算法中的變異運算，是指將個體染色體編碼串中的某些基因座上的基因值用該基因座上的其它等位基因來替換，從而形成以給新的個體。
以下變異運算元適用於二進制編碼和浮點數編碼的個體：
1、基本位變異（SimpleMutation）：對個體編碼串中以變異概率、隨機指定的某一位或某幾位僅因座上的值做變異運算。
2、均勻變異（UniformMutation）：分別用符合某一范圍內均勻分布的隨機數，以某一較小的概率來替換個體編碼串中各個基因座上的原有基因值。（特別適用於在演算法的初級運行階段）
3、邊界變異（BoundaryMutation）：隨機的取基因座上的兩個對應邊界基因值之一去替代原有基因值。特別適用於最優點位於或接近於可行解的邊界時的一類問題。
4、非均勻變異：對原有的基因值做一隨機擾動，以擾動後的結果作為變異後的新基因值。對每個基因座都以相同的概率進行變異運算之後，相當於整個解向量在解空間中作了一次輕微的變動。
5、高斯近似變異：進行變異操作時用符號均值為P的平均值，方差為P2的正態分布的一個隨機數來替換原有的基因值。
⑵ matlab遺傳演算法求函數最小值問題！
如果你的函數是求maxf(x)的問題，要編程求最小值問題，那麼你需要對這個函數取負值求最小值即可
舉例來說：
求max(z)=ax+bx^2
等同於
求min(z)=-(ax+bx^2)
-----------------------------------------
我這里有一個使用matlab遺傳演算法工具箱的案例，你可以用來快速求解，如果你想自己編程實現遺傳演算法，可以加我QQ：34508855
核心函數： (1)function [pop]=initializega(num,bounds,eevalFN,eevalOps,options)--初始種群的生成函數 【輸出參數】 pop--生成的初始種群 【輸入參數】 num--種群中的個體數目 bounds--代表變數的上下界的矩陣 eevalFN--適應度函數 eevalOps--傳遞給適應度函數的參數 options--選擇編碼形式(浮點編碼或是二進制編碼)[precision F_or_B],如 precision--變數進行二進制編碼時指定的精度 F_or_B--為1時選擇浮點編碼，否則為二進制編碼,由precision指定精度) (2)function [x,endPop,bPop,traceInfo] = ga(bounds,evalFN,evalOps,startPop,opts,... termFN,termOps,selectFN,selectOps,xOverFNs,xOverOps,mutFNs,mutOps)--遺傳演算法函數 【輸出參數】 x--求得的最優解 endPop--最終得到的種群 bPop--最優種群的一個搜索軌跡 【輸入參數】 bounds--代表變數上下界的矩陣 evalFN--適應度函數 evalOps--傳遞給適應度函數的參數 startPop-初始種群 opts[epsilon prob_ops display]--opts(1:2)等同於initializega的options參數，第三個參數控制是否輸出，一般為0。如[1e-6 1 0] termFN--終止函數的名稱,如['maxGenTerm'] termOps--傳遞個終止函數的參數,如[100] selectFN--選擇函數的名稱,如['normGeomSelect'] selectOps--傳遞個選擇函數的參數,如[0.08] xOverFNs--交叉函數名稱表，以空格分開，如['arithXover heuristicXover simpleXover'] xOverOps--傳遞給交叉函數的參數表，如[2 0;2 3;2 0] mutFNs--變異函數表，如['boundaryMutation multiNonUnifMutation nonUnifMutation unifMutation'] mutOps--傳遞給交叉函數的參數表,如[4 0 0;6 100 3;4 100 3;4 0 0] 注意】matlab工具箱函數必須放在工作目錄下 【問題】求f(x)=x+10*sin(5x)+7*cos(4x)的最大值，其中0<=x<=9 【分析】選擇二進制編碼，種群中的個體數目為10，二進制編碼長度為20，交叉概率為0.95,變異概率為0.08 【程序清單】 %編寫目標函數 function[sol,eval]=fitness(sol,options) x=sol(1); eval=x+10*sin(5*x)+7*cos(4*x); %把上述函數存儲為fitness.m文件並放在工作目錄下 initPop=initializega(10,[0 9],'fitness');%生成初始種群，大小為10 [x endPop,bPop,trace]=ga([0 9],'fitness',[],initPop,[1e-6 1 1],'maxGenTerm',25,'normGeomSelect',... [0.08],['arithXover'],[2],'nonUnifMutation',[2 25 3]) %25次遺傳迭代 運算借過為：x = 7.8562 24.8553(當x為7.8562時，f（x）取最大值24.8553) 註：遺傳演算法一般用來取得近似最優解，而不是最優解。 遺傳演算法實例2 【問題】在－5<=Xi<=5,i=1,2區間內，求解 f(x1,x2)=-20*exp(-0.2*sqrt(0.5*(x1.^2+x2.^2)))-exp(0.5*(cos(2*pi*x1)+cos(2*pi*x2)))+22.71282的最小值。 【分析】種群大小10，最大代數1000，變異率0.1,交叉率0.3 【程序清單】 ％源函數的matlab代碼 function [eval]=f(sol) numv=size(sol,2); x=sol(1:numv); eval=-20*exp(-0.2*sqrt(sum(x.^2)/numv)))-exp(sum(cos(2*pi*x))/numv)+22.71282; %適應度函數的matlab代碼 function [sol,eval]=fitness(sol,options) numv=size(sol,2)-1; x=sol(1:numv); eval=f(x); eval=-eval; %遺傳演算法的matlab代碼 bounds=ones(2,1)*[-5 5]; [p,endPop,bestSols,trace]=ga(bounds,'fitness') 註：前兩個文件存儲為m文件並放在工作目錄下，運行結果為 p = 0.0000 -0.0000 0.0055
⑶ 什麼是遺傳演算法
遺傳演算法（Genetic Algorithm）是一類借鑒生物界的進化規律（適者生存，優勝劣汰遺傳機制）演化而來的隨機化搜索方法。它是由美國的J.Holland教授1975年首先提出，其主要特點是直接對結構對象進行操作，不存在求導和函數連續性的限定；具有內在的隱並行性和更好的全局尋優能力；採用概率化的尋優方法，能自動獲取和指導優化的搜索空間，自適應地調整搜索方向，不需要確定的規則。遺傳演算法的這些性質，已被人們廣泛地應用於組合優化、機器學習、信號處理、自適應控制和人工生命等領域。它是現代有關智能計算中的關鍵技術。
對於一個求函數最大值的優化問題(求函數最小值也類同)，一般可以描述為下列數學規劃模型：
遺傳演算法式中x為決策
變數，式2-1為目標函數式，式2-2、2-3為約束條件，U是基本空間，R是U的子集。滿足約束條件的解X稱為可行解，集合R表示所有滿足約束條件的解所組成的集合，稱為可行解集合。
遺傳演算法的基本運算過程如下：
a)初始化：設置進化代數計數器t=0，設置最大進化代數T，隨機生成M個個體作為初始群體P(0)。
b)個體評價：計算群體P(t)中各個個體的適應度。
c)選擇運算:將選擇運算元作用於群體。選擇的目的是把優化的個體直接遺傳到下一代或通過配對交叉產生新的個體再遺傳到下一代。選擇操作是建立在群體中個體的適應度評估基礎上的。
d)交叉運算：將交叉運算元作用於群體。所謂交叉是指把兩個父代個體的部分結構加以替換重組而生成新個體的操作。遺傳演算法中起核心作用的就是交叉運算元。
e)變異運算：將變異運算元作用於群體。即是對群體中的個體串的某些基因座上的基因值作變動。
群體P(t)經過選擇、交叉、變異運算之後得到下一代群體P(t 1)。
f)終止條件判斷:若t=T,則以進化過程中所得到的具有最大適應度個體作為最優解輸出，終止計算。
遺傳演算法是從代表問題可能潛在的解集的一個種群（population）開始的，而一個種群則由經過基因（gene）編碼的一定數目的個體(indivial)組成。每個個體實際上是染色體(chromosome)帶有特徵的實體。染色體作為遺傳物質的主要載體，即多個基因的集合，其內部表現（即基因型）是某種基因組合，它決定了個體的形狀的外部表現，如黑頭發的特徵是由染色體中控制這一特徵的某種基因組合決定的。因此，在一開始需要實現從表現型到基因型的映射即編碼工作。由於仿照基因編碼的工作很復雜，我們往往進行簡化，如二進制編碼，初代種群產生之後，按照適者生存和優勝劣汰的原理，逐代（generation）演化產生出越來越好的近似解，在每一代，根據問題域中個體的適應度（fitness）大小選擇（selection）個體，並藉助於自然遺傳學的遺傳運算元（genetic operators）進行組合交叉（crossover）和變異（mutation），產生出代表新的解集的種群。這個過程將導致種群像自然進化一樣的後生代種群比前代更加適應於環境，末代種群中的最優個體經過解碼（decoding），可以作為問題近似最優解。
⑷ 求一個關於人工智慧的小實驗
人工智慧第二次實驗報告
1．實驗題目：
遺傳演算法的設計與實現
2．實驗目的：
通過人工智慧課程的學習，熟悉遺傳演算法的簡單應用。
3．實驗內容
用遺傳演算法求解f (x) = x2 的最大值，x∈ [0,31]，x取整數。
可以看出該函數比較簡單，只要是為了體現遺傳演算法的思想，在問題選擇上，選了一個比較容易實現的，把主要精力放在遺傳演算法的實現，以及核心思想體會上。
4. 實驗過程：
1. 實現過程
（1）編碼
使用二進制編碼，隨機產生一個初始種群。L 表示編碼長度，通常由對問題的求解精度決定，編碼長度L 越長，可期望的最優解的精度也就越高，過大的L 會增大運算量。針對該問題進行了簡化，因為題設中x∈ [0,31]，所以將二進制長度定為5就夠用了；
（2）生成初始群體
種群規模表示每一代種群中所含個體數目。隨機產生N個初始串結構數據，每個串結構數據成為一個個體，N個個體組成一個初始群體，N表示種群規模的大小。當N取值較小時，可提高遺傳演算法的運算速度，但卻降低種群的多樣性，容易引起遺傳演算法早熟，出現假收斂；而N當取值較大時，又會使得遺傳演算法效率降低。一般建議的取值范圍是20—100。
（3）適應度檢測
根據實際標准計算個體的適應度，評判個體的優劣，即該個體所代表的可行解的優劣。本例中適應度即為所求的目標函數；
（4）選擇
從當前群體中選擇優良（適應度高的）個體，使它們有機會被選中進入下一次迭代過程，舍棄適應度低的個體。本例中採用輪盤賭的選擇方法，即個體被選擇的幾率與其適應度值大小成正比；
（5）交叉
遺傳操作，根據設置的交叉概率對交配池中個體進行基因交叉操作，形成新一代的種群，新一代中間個體的信息來自父輩個體，體現了信息交換的原則。交叉概率控制著交叉操作的頻率，由於交叉操作是遺傳演算法中產生新個體的主要方法，所以交叉概率通常應取較大值；但若過大的話，又可能破壞群體的優良模式。一般取0.4到0.99。
（6）變異
隨機選擇中間群體中的某個個體，以變異概率大小改變個體某位基因的值。變異為產生新個體提供了機會。變異概率也是影響新個體產生的一個因素，變異概率小，產生新個體少；變異概率太大，又會使遺傳演算法變成隨機搜索。一般取變異概率為0.0001—0.1。
（7）結束條件
當得到的解大於等於900時，結束。從而觀看遺傳的效率問題
⑸ 遺傳演算法
參考文獻： 知乎 遺傳演算法 編碼解碼知識
實現遺傳演算法的第一步就是明確對求解問題的編碼和解碼方式。對於函數優化問題，一般有兩種編碼方式，各具優缺點
實數編碼：直接用實數表示基因，容易理解且不需要解碼過程，但容易過早收斂，從而陷入局部最優
二進制編碼：穩定性高，種群多樣性大，但需要的存儲空間大，需要解碼且難以理解
對於求解函數最大值問題，我選擇的是二進制編碼。
以我們的目標函數 f(x) = x + 10sin(5x) + 7cos(4x), x∈[0,9] 為例。
假如設定求解的精度為小數點後4位，可以將x的解空間劃分為 (9-0)×(1e+4)=90000個等分。
2^16<90000<2^17，需要17位二進制數來表示這些解。換句話說，一個解的編碼就是一個17位的二進制串。
一開始，這些二進制串是隨機生成的。
一個這樣的二進制串代表一條染色體串，這里染色體串的長度為17。
對於任何一條這樣的染色體chromosome，如何將它復原(解碼)到[0,9]這個區間中的數值呢？
對於本問題，我們可以採用以下公式來解碼：
decimal( ): 將二進制數轉化為十進制數
一般化解碼公式：
lower_bound: 函數定義域的下限
upper_bound: 函數定義域的上限
chromosome_size: 染色體的長度
通過上述公式，我們就可以成功地將二進制染色體串解碼成[0,9]區間中的十進制實數解。
染色體，就是指由 DNA 組成的聚合體，DNA 上的每個基因都編碼了一個獨特的性狀，比如，頭發或者眼睛的顏色
可以將他看作是一個優化問題，它可以嘗試找出某些輸入，憑借這些輸入我們便可以得到最佳的輸出值或者是結果
遺傳演算法要點：
1.初始化
初始化候選全體，隨機初始化
2.查找適應函數
3.選擇：物競天擇，適者生存
先選擇能量強的個體，然後再進行隨機選擇，選出適應度雖然小，但是倖存下來的個體
4.交叉：
5.變異：根據需要進行選擇