GAFT-一個使用Python實現的遺傳演算法框架

前言

最近需要用到遺傳演算法來優化一些東西，最初是打算直接基於某些演算法實現一個簡單的函數來優化，但是感覺單純寫個非通用的函數運行後期改進運算元或者別人使用起來都會帶來困難，同時遺傳演算法基本概念和運行流程相對固定，改進也一般通過編碼機制，選擇策略，交叉變異運算元以及參數設計等方面，對於演算法的整體結構並沒有大的影響。這樣對於遺傳演算法來說，就非常適合寫個相對固定的框架然後給運算元、參數等留出空間以便對新演算法進行測試和改進。於是就動手寫了個遺傳演算法的小框架gaft，本文對此框架進行一些介紹並分別以一個一維搜索和二維搜索為例子對使用方法進行了介紹。

GitHub: https://github.com/PytLab/gaftPyPI: https://pypi.python.org/pypi/gaft

目前框架只是完成了最初的版本，比較簡陋，內置了幾個基本的常用運算元，使用者可以根據介面規則實現自定義的運算元並放入框架中運行。我自己也會根據自己的需求後續添加更多的改進運算元，同時改進框架使其更加通用.

正文

遺傳演算法介紹

這裡我對遺傳演算法的基本概念進行簡要的介紹，並闡述gaft的設計原則。

簡單而言，遺傳演算法使用群體搜索技術，將種群代表一組問題的可行解，通過對當前種群施加選擇，交叉，變異等一些列遺傳操作來產生新一代的種群，並逐步是種群進化到包含近似全局最優解的狀態。下面我將遺傳學和遺傳演算法相關術語的對應關係總結一下:

術語

演算法特點

1. 以決策變數的編碼作為運算對象，使得優化過程借鑒生物學中的概念成為可能
2. 直接以目標函數作為搜索信息，確定搜索方向很範圍，屬於無導數優化
3. 同時使用多個搜索點的搜索信息，算是一種隱含的並行性
4. 是一種基於概率的搜索技術
5. 具有自組織，自適應和自學習等特性

演算法流程

gaft 設計原則

由於遺傳演算法的流程相對固定，我們優化演算法基本上也是在流程整體框架下對編碼機制，運算元，參數等進行修改，因此在寫框架的時候，我便想把那些固定的遺傳運算元，適應度函數寫成介面，並使用元類、裝飾器等方式實現對介面的限制和優化，這樣便可以方便後續自定義算符和適應度函數定製。最後將各個部分組合到一起組成一個engine然後根據演算法流程運行遺傳演算法對目標進行優化.

這樣我們便脫離每次都要寫遺傳演算法流程的繁瑣，每次只需要像寫插件一樣實現自己的運算元和適應度函數便可以將其放入gaft開始對演算法進行測試或者對目標函數進行優化了。

GAFT文件結構

此部分我對自己實現的框架的整體結構進行下介紹.

.├── LICENSE├── MANIFEST.in├── README.rst├── examples│ ├── ex01│ └── ex02├── gaft│ ├── __init__.py│ ├── __pycache__│ ├── analysis│ ├── components│ ├── engine.py│ ├── operators│ └── plugin_interfaces├── setup.cfg├── setup.py└── tests ├── flip_bit_mutation_test.py ├── gaft_test.py ├── individual_test.py ├── population_test.py ├── roulette_wheel_selection_test.py └── uniform_crossover_test.py

目前的文件結果如上所示，

• /gaft/components中定義了內置的個體和種群類型，提供了兩種不同的遺傳編碼方式:二進位編碼和實數編碼。
• /gaft/plugin_interfaces中是插件介面定義，所有的運算元定義以及on-the-fly分析的介面規則都在裡面，使用者可以根據此來編寫自己的插件並放入到engine中。
• /gaft/operators裡面是內置遺傳運算元，他們也是遵循/gaft/plugin_interfaces中的規則進行編寫，可以作為編寫運算元的例子。其中運算元我目前內置了roulette wheel選擇運算元，uniform 交叉運算元和flipbit變異運算元，使用者可以直接使用內置運算元來使用gaft對自己的問題進行優化。
• /gaft/analysis裡面是內置的on-the-fly分析插件，他可以在遺傳演算法迭代的過程中對迭代過程中的變數進行分析，例如我在裡面內置了控制台日誌信息輸出，以及迭代適應度值的保存等插件方便對進化曲線作圖。
• /gaft/engine便是遺傳演算法的流程式控制制模塊了，他將所有的之前定義的各個部分組合到一起使用遺傳演算法流程進行優化迭代。

使用GAFT

下面我就以兩個函數作為例子來使用GAFT對目標函數進行優化.

一維搜索

首先我們先對一個簡單的具有多個局部極值的函數進行優化，我們來使用內置的運算元求函數

的極大值，x的取值範圍為[0,10]

1. 先導入需要的模塊

from math import sin, cos# 導入種群和內置運算元相關類from gaft import GAEnginefrom gaft.components import GAIndividualfrom gaft.components import GAPopulationfrom gaft.operators import RouletteWheelSelectionfrom gaft.operators import UniformCrossoverfrom gaft.operators import FlipBitMutation# 用於編寫分析插件的介面類from gaft.plugin_interfaces.analysis import OnTheFlyAnalysis# 內置的存檔適應度函數的分析類from gaft.analysis.fitness_store import FitnessStoreAnalysis# 我們將用兩種方式將分析插件註冊到遺傳演算法引擎中

2. 創建引擎

# 定義種群indv_template = GAIndividual(ranges=[(0, 10)], encoding="binary", eps=0.001)population = GAPopulation(indv_template=indv_template, size=50)# 創建遺傳運算元selection = RouletteWheelSelection()crossover = UniformCrossover(pc=0.8, pe=0.5)mutation = FlipBitMutation(pm=0.1)# 創建遺傳演算法引擎, 分析插件和適應度函數可以以參數的形式傳入引擎中engine = GAEngine(population=population, selection=selection, crossover=crossover, mutation=mutation, analysis=[FitnessStoreAnalysis])

3. 自定義適應度函數

可以通過修飾符的方式將，適應度函數註冊到引擎中。

@engine.fitness_registerdef fitness(indv): x, = indv.variants return x + 10*sin(5*x) + 7*cos(4*x)

4. 自定義on-the-fly分析插件

也可以通過修飾符在定義的時候直接將插件註冊到引擎中

@engine.analysis_registerclass ConsoleOutputAnalysis(OnTheFlyAnalysis): interval = 1 def register_step(self, ng, population, engine): best_indv = population.best_indv(engine.fitness) msg = "Generation: {}, best fitness: {:.3f}".format(ng, engine.fitness(best_indv)) engine.logger.info(msg) def finalize(self, population, engine): best_indv = population.best_indv(engine.fitness) x = best_indv.variants y = engine.fitness(best_indv) msg = "Optimal solution: ({}, {})".format(x, y) engine.logger.info(msg)

5. Ok, 開始跑(優化)吧！

我們這裡跑100代種群.

if "__main__" == __name__: # Run the GA engine. engine.run(ng=100)

內置的分析插件會在每步迭代中記錄得到的每一代的最優個體，並生成數據保存。

繪製一下函數本身的曲線和我們使用遺傳演算法得到的進化曲線:

優化過程動畫:

二維搜索

下面我們使用GAFT內置運算元來搜索同樣具有多個極值點的二元函數

的最大值，x, y 的範圍為 [?2,2].

這裡我們就不自定義分析插件了，直接使用內置的分析類，並在構造引擎時直接傳入.

"""Find the global maximum for binary function: f(x) = y*sim(2*pi*x) + x*cos(2*pi*y)"""from math import sin, cos, pifrom gaft import GAEnginefrom gaft.components import GAIndividualfrom gaft.components import GAPopulationfrom gaft.operators import RouletteWheelSelectionfrom gaft.operators import UniformCrossoverfrom gaft.operators import FlipBitMutation# Built-in best fitness analysis.from gaft.analysis.fitness_store import FitnessStoreAnalysisfrom gaft.analysis.console_output import ConsoleOutputAnalysis# Define population.indv_template = GAIndividual(ranges=[(-2, 2), (-2, 2)], encoding="binary", eps=0.001)population = GAPopulation(indv_template=indv_template, size=50)# Create genetic operators.selection = RouletteWheelSelection()crossover = UniformCrossover(pc=0.8, pe=0.5)mutation = FlipBitMutation(pm=0.1)# Create genetic algorithm engine.# Here we pass all built-in analysis to engine constructor.engine = GAEngine(population=population, selection=selection, crossover=crossover, mutation=mutation, analysis=[ConsoleOutputAnalysis, FitnessStoreAnalysis])# Define fitness function.@engine.fitness_registerdef fitness(indv): x, y = indv.variants return y*sin(2*pi*x) + x*cos(2*pi*y)if "__main__" == __name__: engine.run(ng=100)

進化曲線:

二維函數面:

搜索過程動畫:

可見目前內置的基本運算元都能很好的找到例子中函數的最優點。

總結

本文主要介紹了本人開發的一個用於遺傳演算法做優化計算的Python框架，框架內置了遺傳演算法中常用的組件，包括不同編碼方式的個體，種群，以及遺傳運算元等。同時框架還提供了自定義遺傳運算元和分析插件的介面，能夠方便快速搭建遺傳演算法流程並用於演算法測試。

目前框架僅僅處於初步階段，後續會在自己使用的過程中逐步完善更多的內置運算元，是框架更加通用。本文中的兩個優化例子均能在GitHub上找到源碼(https://github.com/PytLab/gaft/tree/master/examples)

目前的計劃：1. 添加更多的內置運算元; 2. 給內置運算元和組件添加C++ backend; 3. 並行化

參考

• 《智能優化演算法及其MATLAB實例》
• 《MATLAB最優化計算》

推薦閱讀：