基本框架
GA的流程圖
GA的流程圖如右圖所示
編碼
遺傳算法不能直接處理問題空間的參數,必須把它們轉換成遺傳空間的由基因按一定結構組成的染色體或個體。這一轉換操作就叫做編碼,也可以稱作(問題的)表示(representation)。
評估編碼策略常采用以下3個規範:
a)完備性(completeness):問題空間中的所有點(候選解)都能作為GA空間中的點(染色體)表現。
b)健全性(soundness):GA空間中的染色體能對應所有問題空間中的候選解。
c)非冗餘性(nonredundancy):染色體和候選解一一對應。
目前的幾種常用的編碼技術有二進制編碼,浮點數編碼,字符編碼,變成編碼等。
而二進值編碼是目前遺傳算法中最常用的編碼方法。即是由二進值字符集{0,1}産生通常的0,1字符串來表示問題空間的候選解。它具有以下特點:
a)簡單易行
b)符合最小字符集編碼原則
c)便于用模式定理進行分析,因為模式定理就是以基礎的。
适應度函數
進化論中的适應度,是表示某一個體對環境的适應能力,也表示該個體繁殖後代的能力。遺傳算法的适應度函數也叫評價函數,是用來判斷群體中的個體的優劣程度的指标,它是根據所求問題的目标函數來進行評估的。
遺傳算法在搜索進化過程中一般不需要其他外部信息,僅用評估函數來評估個體或解的優劣,并作為以後遺傳操作的依據。由于遺傳算法中,适應度函數要比較排序并在此基礎上計算選擇概率,所以适應度函數的值要取正值。由此可見,在不少場合,将目标函數映射成求最大值形式且函數值非負的适應度函數是必要的。
适應度函數的設計主要滿足以下條件:
a)單值、連續、非負、最大化
b)合理、一緻性
c)計算量小
d)通用性強。
在具體應用中,适應度函數的設計要結合求解問題本身的要求而定。适應度函數設計直接影響到遺傳算法的性能。
初始群體的選取
遺傳算法中初始群體中的個體是随機産生的。一般來講,初始群體的設定可采取如下的策略:
a)根據問題固有知識,設法把握最優解所占空間在整個問題空間中的分布範圍,然後,在此分布範圍内設定初始群體。
b)先随機生成一定數目的個體,然後從中挑出最好的個體加到初始群體中。這種過程不斷叠代,直到初始群體中個體數達到了預先确定的規模。
一般算法
遺傳算法是模拟達爾文的遺傳選擇和自然淘汰的生物進化過程的計算模型。它的思想源于生物遺傳學和适者生存的自然規律,是具有“生存+檢測”的叠代過程的搜索算法。遺傳算法以一種群體中的所有個體為對象,并利用随機化技術指導對一個被編碼的參數空間進行高效搜索。其中,選擇、交叉和變異構成了遺傳算法的遺傳操作;參數編碼、初始群體的設定、适應度函數的設計、遺傳操作設計、控制參數設定五個要素組成了遺傳算法的核心内容。作為一種新的全局優化搜索算法,遺傳算法以其簡單通用、魯棒性強、适于并行處理以及高效、實用等顯着特點,在各個領域得到了廣泛應用,取得了良好效果,并逐漸成為重要的智能算法之一。
遺傳算法是基于生物學的,理解或編程都不太難。下面是遺傳算法的一般算法:
創建一個随機的初始狀态
初始種群是從解中随機選擇出來的,将這些解比喻為染色體或基因,該種群被稱為第一代,這和符号人工智能系統的情況不一樣,在那裡問題的初始狀态已經給定了。
評估适應度
對每一個解(染色體)指定一個适應度的值,根據問題求解的實際接近程度來指定(以便逼近求解問題的答案)。不要把這些“解”與問題的“答案”混為一談,可以把它理解成為要得到答案,系統可能需要利用的那些特性。
繁殖(包括子代突變)
帶有較高适應度值的那些染色體更可能産生後代(後代産生後也将發生突變)。後代是父母的産物,他們由來自父母的基因結合而成,這個過程被稱為“雜交”。
下一代
如果新的一代包含一個解,能産生一個充分接近或等于期望答案的輸出,那麼問題就已經解決了。如果情況并非如此,新的一代将重複他們父母所進行的繁衍過程,一代一代演化下去,直到達到期望的解為止。
并行計算
非常容易将遺傳算法用到并行計算和群集環境中。一種方法是直接把每個節點當成一個并行的種群看待。然後有機體根據不同的繁殖方法從一個節點遷移到另一個節點。另一種方法是“農場主/勞工”體系結構,指定一個節點為“農場主”節點,負責選擇有機體和分派适應度的值,另外的節點作為“勞工”節點,負責重新組合、變異和适應度函數的評估。
2014年,英國的科學家正在嘗試用遺傳算法軟件,通過适者生存的“進化”過程得到更好的賽車設計方案。據了解,遺傳算法是利用進化論原則進行工程設計的方法。設計人員提出多種初步方案,在計算機上對不同方案的效果進行模拟。效果差的方案被淘汰掉,好的方案生存下來,互相“雜交”并發生“變異”,最終得到令人滿意的方案。遺傳算法已經被用于設計一級 8月,三星與您激情奧運鬥三國與衆将一拚高下海納百川候車亭媒體無限下載MP3你作K王方程式賽車的中途維修方案和某些零件。但一些專家對這種方法持保留态度,認為真實賽場上影響成績的因素非常複雜,假設中難以全面考慮到,根據遺傳算法得出的參數而設計的賽車有局限性。
術語說明
由于遺傳算法是由進化論和遺傳學機理而産生的搜索算法,所以在這個算法中會用到很多生物遺傳學知識,下面是我們将會用來的一些術語說明:
染色體(Chromosome)
染色體又可以叫做基因型個體(individuals),一定數量的個體組成了群體(population),群體中個體的數量叫做群體大小。
基因(Gene)
基因是串中的元素,基因用于表示個體的特征。例如有一個串S=1011,則其中的1,0,1,1這4個元素分别稱為基因。它們的值稱為等位基因(Alleles)。
基因地點(Locus)
基因地點在算法中表示一個基因在串中的位置稱為基因位置(GenePosITion),有時也簡稱基因位。基因位置由串的左向右計算,例如在串S=1101中,0的基因位置是3。
特征值(Feature)
在用串表示整數時,基因的特征值與二進制數的權一緻;例如在串S=1011中,基因位置3中的1,它的基因特征值為2;基因位置1中的1,它的基因特征值為8。
适應度(Fitness)
各個個體對環境的适應程度叫做适應度(fitness)。為了體現染色體的适應能力,引入了對問題中的每一個染色體都能進行度量的函數,叫适應度函數。這個函數是計算個體在群體中被使用的概率。
運算過程
遺傳操作是模拟生物基因遺傳的做法。在遺傳算法中,通過編碼組成初始群體後,遺傳操作的任務就是對群體的個體按照它們對環境适應度(适應度評估)施加一定的操作,從而實現優勝劣汰的進化過程。從優化搜索的角度而言,遺傳操作可使問題
的解,一代又一代地優化,并逼近最優解。
遺傳操作包括以下三個基本遺傳算子(geneticoperator):選擇(selection);交叉(crossover);變異(mutation)。這三個遺傳算子有如下特點:
個體遺傳算子的操作都是在随機擾動情況下進行的。因此,群體中個體向最優解遷移的規則是随機的。需要強調的是,這種随機化操作和傳統的随機搜索方法是有區别的。遺傳操作進行的高效有向的搜索而不是如一般随機搜索方法所進行的無向搜索。
遺傳操作的效果和上述三個遺傳算子所取的操作概率,編碼方法,群體大小,初始群體以及适應度函數的設定密切相關。
選擇
從群體中選擇優勝的個體,淘汰劣質個體的操作叫選擇。選擇算子有時又稱為再生算子(reproductionoperator)。選擇的目的是把優化的個體(或解)直接遺傳到下一代或通過配對交叉産生新的個體再遺傳到下一代。選擇操作是建立在群體中個體的适應度評估基礎上的,目前常用的選擇算子有以
下幾種:适應度比例方法、随機遍曆抽樣法、局部選擇法。
其中輪盤賭選擇法(roulettewheelselection)是最簡單也是最常用的選擇方法。在該方法中,各個個體的選擇概率和其适應度值成比例。設群體大小為n,其中個體i的适應度為,則被選擇的概率,為遺傳算法
顯然,概率反映了個體i的适應度在整個群體的個體适應度總和中所占的比例。個體适應度越大。其被選擇的概率就越高、反之亦然。計算出群體中各個個體的選擇概率後,為了選擇交配個體,需要進行多輪選擇。每一輪産生一個[0,1]之間均勻随機數,将該随機數作為選擇指針來确定被選個體。個體被選後,可随機地組成交配對,以供後面的交叉操作。
交叉
在自然界生物進化過程中起核心作用的是生物遺傳基因的重組(加上變異)。同樣,遺傳算法中起核心作用的是遺傳操作的交叉算子。所謂交叉是指把兩個父代個體的部分結構加以替換重組而生成新個體的操作。通過交叉,遺傳算法的搜索能力得以飛躍提高。
交叉算子根據交叉率将種群中的兩個個體随機地交換某些基因,能夠産生新的基因組合,期望将有益基因組合在一起。根據編碼表示方法的不同,可以有以下的算法:
a)實值重組(realvaluedrecombination)
1)離散重組(discreterecombination)
2)中間重組(intermediaterecombination)
3)線性重組(linearrecombination)
4)擴展線性重組(extendedlinearrecombination)。
b)二進制交叉(binaryvaluedcrossover)
1)單點交叉(single-pointcrossover)
2)多點交叉(multiple-pointcrossover)
3)均勻交叉(uniformcrossover)
4)洗牌交叉(shufflecrossover)
5)縮小代理交叉(crossoverwithreducedsurrogate)。
最常用的交叉算子為單點交叉(one-pointcrossover)。具體操作是:在個體串中随機設定一個交叉點,實行交叉時,該點前或後的兩個個體的部分結構進行互換,并生成兩個新個體。下面給出了單點交叉的一個例子:
個體A:1001↑111→1001000新個體
個體B:0011↑000→0011111新個體
變異
變異算子的基本内容是對群體中的個體串的某些基因座上的基因值作變動。依據個體編碼表示方法的不同,可以有以下的算法:
a)實值變異
b)二進制變異。
一般來說,變異算子操作的基本步驟如下:
a)對群中所有個體以事先設定的變異概率判斷是否進行變異
b)對進行變異的個體随機選擇變異位進行變異。
遺傳算法引入變異的目的有兩個:一是使遺傳算法具有局部的随機搜索能力。當遺傳算法通過交叉算子已接近最優解鄰域時,利用變異算子的這種局部随機搜索能力可以加速向最優解收斂。顯然,此種情況下的變異概率應取較小值,否則接近最優解的積木塊會因變異而遭到破壞。二是使遺傳算法可維持群體多樣性,以防止出現未成熟收斂現象。此時收斂概率應取較大值。
遺傳算法中,交叉算子因其全局搜索能力而作為主要算子,變異算子因其局部搜索能力而作為輔助算子。遺傳算法通過交叉和變異這對相互配合又相互競争的操作而使其具備兼顧全局和局部的均衡搜索能力。所謂相互配合.是指當群體在進化中陷于搜索空間中某個超平面而僅靠交叉不能擺脫時,通過變異操作可有助于這種擺脫。所謂相互競争,是指當通過交叉已形成所期望的積木塊時,變異操作有可能破壞這些積木塊。如何有效地配合使用交叉和變異操作,是目前遺傳算法的一個重要研究内容。
基本變異算子是指對群體中的個體碼串随機挑選一個或多個基因座并對這些基因座的基因值做變動(以變異概率P.做變動),(0,1)二值碼串中的基本變異操作如下:
基因位下方标有*号的基因發生變異。
變異率的選取一般受種群大小、染色體長度等因素的影響,通常選取很小
的值,一般取0.001-0.1。
終止條件
當最優個體的适應度達到給定的阈值,或者最優個體的适應度和群體适應度不再上升時,或者叠代次數達到預設的代數時,算法終止。預設的代數一般設置為100-500代。
演示學習
EA_demo,英國格拉斯哥大學1997年出版,至今仍廣泛使用,采用大學包括英國利物浦(Liverpool)大學、蘇塞克(Sussex)大學、北安普頓(Northampton)大學,德國烏爾姆(Ulm)大學,瑞士日内瓦(Geneva)大學,西班牙格林納達(Granada)大學,葡萄牙新裡斯本(NovadeLisboa)大學,美國加州大學戴維斯分校(UCDavies),加拿大卡爾加裡(Calgary)大學,澳大利亞墨爾本皇家理工大學(RMIT),新加坡國立大學,台灣國立清華大學,上海交通大學,巴西PUCRS大學等。EA_demo允許用戶直接在網頁上一代一代地手動運行,以看遺傳/進化算法是怎樣一步一步操作的,亦可在背景中批次運行,以觀察算法的收斂和染色體是否跳出局部最優。用戶可以改變終止代數,群體規模,交配率,變異率和選擇機制。也有其它自學課件收錄于AI中心網站和歐洲軟計算中心網站。
2021年4月24日星期六下午,北京大學經濟學院、北京大學金融工程實驗室主辦的“金工首席談量化”專題講座第五講在線上舉行。本次講座邀請到招商證券量化與基金評價首席分析師任瞳作為演講嘉賓,以“基于遺傳算法的個股分組與組合優化”為題,為經濟學院60餘位師生作了主題報告。講座由經濟學院研究員黎新平博士主持。