GAFT：一個使用Python實現的遺傳算法框架
前言
最近需要用到遺傳算法來優化一些東西，最初是打算直接基于某些算法實現一個簡單的函數來優化，但是感覺單純寫個非通用的函數運行后期改進算子或者別人使用起來都會帶來困難，同時遺傳算法基本概念和運行流程相對固定，改進也一般通過編碼機制，選擇策略，交叉變異算子以及參數設計等方面，對于算法的整體結構并沒有大的影響。這樣對于遺傳算法來說，就非常適合寫個相對固定的框架然后給算子、參數等留出空間以便對新算法進行測試和改進。于是就動手寫了個遺傳算法的小框架gaft，本文對此框架進行一些介紹并分別以一個一維搜索和二維搜索為例子對使用方法進行了介紹。
- GitHub: https://github.com/PytLab/gaft
- PyPI: https://pypi.python.org/pypi/gaft
目前框架只是完成了最初的版本，比較簡陋，內置了幾個基本的常用算子，使用者可以根據接口規則實現自定義的算子并放入框架中運行。我自己也會根據自己的需求后續添加更多的改進算子，同時改進框架使其更加通用.
正文
遺傳算法介紹
這里我對遺傳算法的基本概念進行簡要的介紹，并闡述gaft的設計原則。
簡單而言，遺傳算法使用群體搜索技術，將種群代表一組問題的可行解，通過對當前種群施加選擇，交叉，變異等一些列遺傳操作來產生新一代的種群，并逐步是種群進化到包含近似全局***解的狀態。下面我將遺傳學和遺傳算法相關術語的對應關系總結一下:
術語
算法特點
- 以決策變量的編碼作為運算對象，使得優化過程借鑒生物學中的概念成為可能
- 直接以目標函數作為搜索信息，確定搜索方向很范圍，屬于無導數優化
- 同時使用多個搜索點的搜索信息，算是一種隱含的并行性
- 是一種基于概率的搜索技術
- 具有自組織，自適應和自學習等特性
算法流程
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對目標函數進行優化.
一維搜索
首先我們先對一個簡單的具有多個局部極值的函數進行優化，我們來使用內置的算子求函數 f(x)=x+10sin(5x)+7cos(4x)的極大值，x的取值范圍為[0,10]
1. 先導入需要的模塊
- from math import sin, cos
- # 導入種群和內置算子相關類
- from gaft import GAEngine
- from gaft.components import GAIndividual
- from gaft.components import GAPopulation
- from gaft.operators import RouletteWheelSelection
- from gaft.operators import UniformCrossover
- from 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_register
- def fitness(indv):
- x, = indv.variants
- return x + 10*sin(5*x) + 7*cos(4*x)
4. 自定義on-the-fly分析插件
也可以通過修飾符在定義的時候直接將插件注冊到引擎中
- @engine.analysis_register
- class 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內置算子來搜索同樣具有多個極值點的二元函數f(x)=ysin(2πx)+xcos(2πy) 的***值，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, pi
- from gaft import GAEngine
- from gaft.components import GAIndividual
- from gaft.components import GAPopulation
- from gaft.operators import RouletteWheelSelection
- from gaft.operators import UniformCrossover
- from gaft.operators import FlipBitMutation
- # Built-in best fitness analysis.
- from gaft.analysis.fitness_store import FitnessStoreAnalysis
- from 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_register
- def 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***化計算》
