一種基于Jenetics的遺傳算法程序設(shè)計

王康

摘要：介紹了一個基于Java語言的遺傳算法庫Jenetics，分析了它的設(shè)計思想，原理以及整體架構(gòu)。針對使用計算機程序來模擬演化目標(biāo)圖片的問題，提出了一種基于Jenetics的遺傳算法的解決方案。

關(guān)鍵詞： 遺傳算法； 程序設(shè)計； Jenetics；

中圖分類號：TP18 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2018）22-0169-02

Abstract：Jenetics is a genetic algorithm library based on Java programing language.Its design principal and overall architecture is analyzed. A solution based on Jenetics and genetic algorithm is proposed to solve the problem of evolving images by computer program.

Key words：genetic algorithm； program； Jenetics

1 引言

遺傳算法是一種受自然選擇和進(jìn)化思想啟發(fā)的一種高效并行的全局搜索算法。它依賴于幾個生物遺傳算子，包括選擇，交叉以及變異等機制。自60年代初美國的密歇根大學(xué)的J.Holland教授提出以來，經(jīng)歷長期的發(fā)展，現(xiàn)在被廣泛應(yīng)用于人工智能的各個領(lǐng)域中。

遺傳算法的思想雖然簡單，但是實現(xiàn)遺傳算法的程序，與一般的算法相比，通常是比較復(fù)雜的，所以為了方便編寫遺傳算法程序，在實際應(yīng)用中，人們普遍會使用一些遺傳算法庫來解決問題。Jenetics是一個使用現(xiàn)代的Java面向?qū)ο蟪绦蛟O(shè)計語言的高級的遺傳算法庫。它很好地定義了遺傳算法的主要算法概念，包括基因（Gene），染色體（Chromosome），種群（Population）以及適應(yīng)度函數(shù)（Fitness Function）。

2 Jenetics的設(shè)計原理

2.1 算法設(shè)計

遺傳算法是一種通過模擬自然進(jìn)化的過程搜索最優(yōu)解的方法，使用遺傳算法的程序使用的算法基本上都是相通的，關(guān)鍵在于找到目標(biāo)問題的遺傳學(xué)表達(dá)，也就是為當(dāng)前的問題建立一個合適模型。Jenetics使用的是經(jīng)典的遺傳算法，其基本步驟如下：

（1）創(chuàng)建初始種群。

（2）計算適應(yīng)度。

（3）種群代數(shù)增加1。

（4）選擇幸存者和后代種群。

（5）被選擇的后代產(chǎn)生變異。

（6）去掉死亡的種群，結(jié)合幸存者種群和變異的后代種群形成新種群。

（7）反復(fù)執(zhí)行（3）至（6）直到一定的結(jié)束標(biāo)準(zhǔn)被滿足。

2.2 整體架構(gòu)設(shè)計

Evolution Stream是Jenetics的基本類，它實現(xiàn)了Java 8 Stream的應(yīng)用程序接口。 因此它不需要命令式的執(zhí)行演化的步驟。Evolution Stream是由Evolution Engine驅(qū)動的。Evolution Engine執(zhí)行每一代的演化的步驟。

圖1中的ES（i）代表EvolutionStart對象（第i代），而ER（i）代表 EvolutionResult（第i代）。一旦Evolution Engine被創(chuàng)建，它就可被用于多個EvolutionStreams。如果limit斷言返回真，則進(jìn)化過程會繼續(xù)，如果為假則EvolutionStream將中止。最后程序從EvolutionResult收集器收集EvolutionStream的結(jié)果。得到ER（best），也就是最終的演化結(jié)果。需要指出的是，Evolution Engine是非確定性的，也就是說，如果用同樣初始條件兩次調(diào)用前述過程，會產(chǎn)生不同的種群。

圖2顯示了演化相關(guān)的類的靜態(tài)結(jié)構(gòu)和它的依賴。因為Engine類是不可變的，而且創(chuàng)建后不能被修改，所以它是通過一個Builder來實例化和配置的。Engine可以被用于創(chuàng)建任意一個EvolutionsStream。EvolutionStream用于控制演化過程并收集最終的結(jié)果。就像普通的java.util.stream包里的Stream類一樣。Engine和EvolutionStream的分離，就像演化的定義和演化的執(zhí)行分離一樣。

2.3 基礎(chǔ)類

Jenetics的類庫可以被分為三大類別：

（1）領(lǐng)域類（Domain Classes）。這些類構(gòu)成了遺傳算法的領(lǐng)域模型，它們一般都是數(shù)據(jù)類。

（2）操作類（Operation Classes）。這些類主要用于操作領(lǐng)域類，可以產(chǎn)生變異和進(jìn)行選擇。

（3）引擎類（Engine Classes）。這些類用于實現(xiàn)遺傳算法。

Jenetics中的主要的Java類可總結(jié)如表1。

3 Jenetics的應(yīng)用

演化目標(biāo)圖片是一個遺傳算法的常見的應(yīng)用，它使用半透明的多邊形（也可采用三角形），來把目標(biāo)圖片盡可能準(zhǔn)確的畫出來。它實際上是一種用演化算法來逼近目標(biāo)圖片，作為一個近似最優(yōu)解。

3.1設(shè)計步驟

第一步，建立模型。首先，根據(jù)演化的對象的特點可知，一個多邊形就對應(yīng)一個基因，于是可定義一個實現(xiàn)了Gene接口的領(lǐng)域類PolygonGene。然后，由多個基因構(gòu)成染色體，于是可定義一個繼承了AbstractChromosome的PolygonChromosome，它的基因類型為PolygonGene。

第二步，設(shè)計適應(yīng)度函數(shù)，由于已經(jīng)有一個明確的演化標(biāo)準(zhǔn)，也就是目標(biāo)圖片，于是可以用多邊形近似產(chǎn)生的臨時圖片和目標(biāo)圖片進(jìn)行像素到像素的對比，差距越小表示適應(yīng)度越高。具體的，先產(chǎn)生一個Graphics2D對象，然后再使用PolygonChromosome將近似結(jié)果在這個對象上繪出，最后，將位于相同位置的像素點所對應(yīng)的顏色值相減得到差。

第三步，分配選擇器（Selector）。選擇器用于將種群分為幸存者和后代，可以為幸存者和后代分別指定自己的選擇器。Jenetics總共提供了10種選擇器，這里只介紹要在本應(yīng)用中使用到的TournamentSelector。在TournamentSelector的算法中，最佳的個體來自一個隨機抽取的s只個體，它的選取規(guī)則是，最佳個體的適應(yīng)度函數(shù)值要大于其他的s-1只個體的適應(yīng)度函數(shù)值。自然選擇的壓力可以通過調(diào)節(jié)s的值來實現(xiàn)。當(dāng)s的值較大時，弱個體被選擇的可能性比較小。在本應(yīng)用中，幸存者和后代的選擇器都設(shè)置為TournamentSelector。

第四步，選擇變化器（Alterer），變化器是Jenetics用于實現(xiàn)遺傳多樣化的措施，在Jenetics提供了兩種類型的變化器，一種是變異（Mutation），一種是重組（Recombination）。對于變異，類似于生物的變異，它在遺傳過程中主要起到了兩種作用：一是探索搜索空間，即通過小步的變化產(chǎn)生變異，但這種探索方式較重組會比較慢；二是保持多樣性，變異可以防止一個種群過于關(guān)聯(lián)。對于重組（或者說是），它的過程和生物的生殖過程類似，是通過組合親染色體來產(chǎn)生新的染色體。本應(yīng)用中使用到的重組類型為UniformCrossover。

3.2 運行參數(shù)設(shè)計

演化目標(biāo)圖片程序的主要參數(shù)如下表2所示，這些參數(shù)將保存在一個文本文件engine.properties中，運行程序時讀入。

3.3 運行結(jié)果

使用Java Swing設(shè)計的圖形界面，運行結(jié)果如圖3所示。左上為源圖片（目標(biāo)圖片），右側(cè)為通過多邊形演化產(chǎn)生的圖片?？梢钥闯瞿繕?biāo)圖片演化的結(jié)果基本的形狀和顏色已經(jīng)比較接近，但局部的細(xì)節(jié)的差異還是比較明顯。這主要是因為演化的年代數(shù)還比較少，如果再多演化一段時間，可得到更好的結(jié)果。

4 結(jié) 論

Jenetics是一個優(yōu)秀的遺傳算法庫，它基于主流的面向?qū)ο蟮腏ava語言實現(xiàn)，設(shè)計思路符合經(jīng)典的遺傳算法。在設(shè)計的各個環(huán)節(jié)，為應(yīng)用程序開發(fā)者提供了很多的選擇。同時它又是可擴展的，通過Java的類繼承機制，開發(fā)者可以根據(jù)自己的需要編寫符合自己需要的類，以滿足一些特殊情況下的要求。本文提供的演化目標(biāo)圖片程序，是一個基于Jenetics的較為復(fù)雜的應(yīng)用，但與遺傳算法相關(guān)的核心代碼只需要不到10行，可見Jenetics確實可以簡化遺傳算法的開發(fā)。

參考文獻(xiàn)：

[1] 劉大有，盧奕南，王飛，等.遺傳程序設(shè)計方法綜述[J].計算機研究與發(fā)展，2001（02）：213-222

[2] 馬永杰，云文霞.遺傳算法研究進(jìn)展[J].計算機應(yīng)用研究，2012，29（04）：1201-1206+1210.

[3] 邊霞，米良.遺傳算法理論及其應(yīng)用研究進(jìn)展[J].計算機應(yīng)用研究，2010，27（07）：2425-2429+2434.

[4] 朱燦，梁昔明，周書仁.基于物種選擇的遺傳算法[J].小型微型計算機系統(tǒng)，2009，30（03）：534-536.

[5] 吳力榮.基本遺傳算法遺傳策略優(yōu)化與Java實現(xiàn)[J].通化師范學(xué)院學(xué)報，2011，32（06）：30-31.

[6] Franz Wilhelmst?tter.Jenetics用戶指南[EB/OL] http：//jenetics.io/manual/manual-4.1.0.pdf.

【通聯(lián)編輯：唐一東】