最近看到之前做的項目，是關(guān)于使用遺傳算法實(shí)現(xiàn)智能組卷的。所以這次為大家分享遺傳算法的基本原理，以及在實(shí)際場景中的應(yīng)用。
"揭開算法神秘的面紗"
在學(xué)習(xí)計算機(jī)相關(guān)知識時，我們必定會遇到算法的學(xué)習(xí)，我大學(xué)的老師說計算機(jī)中最值得學(xué)，最有價值的就是算法。以致于當(dāng)時懵懵懂懂的我就跟著小伙伴一起邊上數(shù)據(jù)結(jié)構(gòu)邊刷入門算法題了。以學(xué)習(xí)算法為目標(biāo)的同學(xué)，對于藍(lán)橋杯、ACM等比賽多少都有聽過，但卻相當(dāng)一部分人不了解算法的真實(shí)應(yīng)用，對此很是迷茫，甚至是覺得刷算法題就只是來參加比賽。對于算法的學(xué)習(xí)，應(yīng)該更有規(guī)劃，了解算法的實(shí)際應(yīng)用場景，學(xué)習(xí)如何將普通的題庫算法應(yīng)用到實(shí)際場景中來，這樣才能夠在算法學(xué)習(xí)路上走得更遠(yuǎn)。
"遺傳算法的基本原理"
在自然界中，人類以及動物的進(jìn)化，總體上都是朝著好的方向發(fā)展，這就是所謂的進(jìn)化，而遺傳算法就是基于這個特點(diǎn)設(shè)計的。換句話說遺傳算法是基于達(dá)爾文的進(jìn)化論，利用計算機(jī)模擬自然選擇，適者生存，通過遺傳變異等方式，不斷選擇優(yōu)良個體的算法。在自然界中，生物進(jìn)化的主要過程包括染色體的選擇，變異，交叉等，通過這些操作基本能夠保證之后的個體基本上是最優(yōu)的，畢竟只有適應(yīng)環(huán)境的個體才能生存下來。因此只要依照遺傳的原理再繼續(xù)進(jìn)化下去，原理上講就可以一直保持最優(yōu)。因此遺傳算法是用于求解某個場景下最優(yōu)解的算法。
比如對于動植物來說，外觀的長相很大程度上是由自身染色體中的基因決定的。我們可以類似地構(gòu)建模型，把動植物比作由50個正方形構(gòu)成的個體，換言之它是由這50個正方體的屬性和狀態(tài)決定的，因此這些正方體就可以看做個體的基因亦或是染色體。對于動植物個體而言，繁衍后代是產(chǎn)生新基因的主要方式，在計算機(jī)中我們利用算法模擬這個過程，選擇兩個原有的個體，可從兩個個體共100基因中選50條基因，或是交叉組成新基因。還需要定義一個函數(shù)用以判斷當(dāng)時個體是否符合條件，即個體是否符合環(huán)境條件，這個就是適應(yīng)度函數(shù)。
在現(xiàn)實(shí)自然界的群體進(jìn)化中，有諸多影響因素，但在算法的設(shè)計方面，不用面面俱到，只是做一個模擬的過程，能保證實(shí)現(xiàn)適者生存即可。算法實(shí)現(xiàn)的進(jìn)化和淘汰過程中，經(jīng)常會讓種群演變前后總體數(shù)目保持不變，這樣更便于我們的計算。演變的目的是使得適應(yīng)條件的個體存在時間更長，從而模擬適者生存的方式。
在自然界中，種群的演變是永無止境的，但算法不能這樣設(shè)計，需要根據(jù)擬定解決的問題設(shè)定合理的結(jié)束條件，滿足其中一個條件就輸出當(dāng)前最好結(jié)果并終止程序。最普遍的一個終止條件是設(shè)定演變次數(shù)上限，在實(shí)際算法中，有時候出于客觀條件無法達(dá)到既定適應(yīng)度或適應(yīng)度無明顯變化的時候，就該考慮終止算法的運(yùn)行。如設(shè)定演變次數(shù)上限200，個體滿足既定條件即終止，或達(dá)到進(jìn)化上限則輸出當(dāng)前最優(yōu)個體?；谶@個思想定義好個體屬性和相關(guān)的繁衍、適應(yīng)性、變異等函數(shù)并設(shè)定好終止條件后，定義一個數(shù)量較為合適的種群，讓其不斷進(jìn)化、繁衍下去即可，最后會得到一個較為合適的結(jié)果。
遺傳算法用Java代碼實(shí)現(xiàn)的主體部分如下：
此處實(shí)現(xiàn)的大致思路為：定義期望的基因序列，此處使用包含64位字符的數(shù)組，并同時初始化種群，定義一個包含50個個體的種群，個體包括64位隨機(jī)序列，并初始化個體適應(yīng)度，用個體隨機(jī)生成的序列跟期望序列比較得出個體適應(yīng)度，根據(jù)終止條件的不同，適應(yīng)度的計算不盡相同。在種群初始化之后就不斷進(jìn)行演變，模擬自然界進(jìn)化，直至找到符合條件的個體或者達(dá)到進(jìn)化上限選出最接近期望的個體，具體操作為利用已定義的淘汰數(shù)組選出兩個較為優(yōu)秀的個體，進(jìn)行交叉，隨機(jī)生成后代，生成新的群體，之后再根據(jù)先前定義的基于突變概率對種群進(jìn)行概率變異，因為此處的個體為01數(shù)組，變異的方式為隨機(jī)生成0或1。操作完成后，種群就完成了第一次進(jìn)化。種群不斷迭代進(jìn)化，直到滿足條件終止退出。
進(jìn)化終止可自定義條件，如本例中定義的終止條件為找到期望的序列，根據(jù)具體場景要求可以規(guī)定進(jìn)化次數(shù)，或規(guī)定適應(yīng)度上限。
"遺傳算法在組卷中應(yīng)用"
遺傳算法篩選問題最優(yōu)解的原理可應(yīng)用到實(shí)際很多功能中，本案例應(yīng)用其思路到組卷功能中。算法應(yīng)用的基本原理相同，但算法的各方面細(xì)節(jié)需要根據(jù)組卷的實(shí)際情況進(jìn)行調(diào)整。算法中的個體為試卷，根據(jù)不同題庫系統(tǒng)試卷的題型題量有所不同。
實(shí)際上現(xiàn)在網(wǎng)上已經(jīng)有不少關(guān)于組卷的應(yīng)用，對于組卷來說通用的屬性為知識點(diǎn)的覆蓋率、試卷難度系數(shù)等。試卷個體需要根據(jù)自定義組卷規(guī)則(RuleBean)進(jìn)行初始化，基本屬性包括個體期望難度系數(shù)、試卷總分、試卷所包含的知識點(diǎn)、單選題數(shù)量、單選題分?jǐn)?shù)等，初始化個體時，根據(jù)組卷規(guī)則從數(shù)據(jù)庫取出對應(yīng)試題隨機(jī)組成試卷，并計算試卷的適應(yīng)度、難度系數(shù)和知識點(diǎn)覆蓋率，根據(jù)實(shí)際問題中個體對象的不同，三者的計算方法也會隨著改變。
個體變異的操作為根據(jù)定義好的變異幾率進(jìn)行概率突變，變異對象為試題，個體中的試題有一定幾率突變成數(shù)據(jù)庫中科目相同、類型相同的其他試題。利用淘汰數(shù)組選取種群中較為優(yōu)秀的個體，具體操作為從種群中隨機(jī)選取5個個體組成淘汰數(shù)組，返回淘汰數(shù)組中最優(yōu)秀的個體。
組卷開始時，可定義進(jìn)化次數(shù)，期望適應(yīng)度，初始化種群后根據(jù)組卷規(guī)則進(jìn)行迭代進(jìn)化，由于數(shù)據(jù)庫數(shù)據(jù)的限制，也許無論進(jìn)化多少次都達(dá)不到期望的適應(yīng)度，因此需要設(shè)置一個進(jìn)化上限，例如100次，種群的初始數(shù)量不宜過多，在遺傳算法應(yīng)用組卷中，個體為試卷，在種群初始化時初始化個體，個體的初始化需要從數(shù)據(jù)庫中取數(shù)據(jù)，種群數(shù)量過多會導(dǎo)致組卷速度緩慢，效率降低。在依照自定義規(guī)則進(jìn)化過程中，當(dāng)種群中存在個體滿足要求時，則結(jié)束進(jìn)化。此時最優(yōu)個體即為符合的我們要求的個體，即一套試卷。
"總結(jié)"
此次實(shí)操是之前在網(wǎng)上零散的學(xué)習(xí)，也是第一次將算法應(yīng)用到web的開發(fā)當(dāng)中，算是對這方面的應(yīng)用有一定的了解，算法的設(shè)計和原理也是邊學(xué)習(xí)邊寫的，主要是根據(jù)算法的原理應(yīng)用到組卷的功能模塊。希望這篇文章能給其他小伙伴一點(diǎn)思路。
