GAFT：一個使用Python實現(xiàn)的遺傳算法框架
前言
最近需要用到遺傳算法來優(yōu)化一些東西，最初是打算直接基于某些算法實現(xiàn)一個簡單的函數(shù)來優(yōu)化，但是感覺單純寫個非通用的函數(shù)運行后期改進算子或者別人使用起來都會帶來困難，同時遺傳算法基本概念和運行流程相對固定，改進也一般通過編碼機制，選擇策略，交叉變異算子以及參數(shù)設(shè)計等方面，對于算法的整體結(jié)構(gòu)并沒有大的影響。這樣對于遺傳算法來說，就非常適合寫個相對固定的框架然后給算子、參數(shù)等留出空間以便對新算法進行測試和改進。于是就動手寫了個遺傳算法的小框架gaft，本文對此框架進行一些介紹并分別以一個一維搜索和二維搜索為例子對使用方法進行了介紹。
- GitHub: https://github.com/PytLab/gaft
- PyPI: https://pypi.python.org/pypi/gaft
目前框架只是完成了最初的版本，比較簡陋，內(nèi)置了幾個基本的常用算子，使用者可以根據(jù)接口規(guī)則實現(xiàn)自定義的算子并放入框架中運行。我自己也會根據(jù)自己的需求后續(xù)添加更多的改進算子，同時改進框架使其更加通用.
正文
遺傳算法介紹
這里我對遺傳算法的基本概念進行簡要的介紹，并闡述gaft的設(shè)計原則。
簡單而言，遺傳算法使用群體搜索技術(shù)，將種群代表一組問題的可行解，通過對當(dāng)前種群施加選擇，交叉，變異等一些列遺傳操作來產(chǎn)生新一代的種群，并逐步是種群進化到包含近似全局***解的狀態(tài)。下面我將遺傳學(xué)和遺傳算法相關(guān)術(shù)語的對應(yīng)關(guān)系總結(jié)一下:
術(shù)語
算法特點
- 以決策變量的編碼作為運算對象，使得優(yōu)化過程借鑒生物學(xué)中的概念成為可能
- 直接以目標函數(shù)作為搜索信息，確定搜索方向很范圍，屬于無導(dǎo)數(shù)優(yōu)化
- 同時使用多個搜索點的搜索信息，算是一種隱含的并行性
- 是一種基于概率的搜索技術(shù)
- 具有自組織，自適應(yīng)和自學(xué)習(xí)等特性
算法流程
gaft 設(shè)計原則
由于遺傳算法的流程相對固定，我們優(yōu)化算法基本上也是在流程整體框架下對編碼機制，算子，參數(shù)等進行修改，因此在寫框架的時候，我便想把那些固定的遺傳算子，適應(yīng)度函數(shù)寫成接口，并使用元類、裝飾器等方式實現(xiàn)對接口的限制和優(yōu)化，這樣便可以方便后續(xù)自定義算符和適應(yīng)度函數(shù)定制。***將各個部分組合到一起組成一個engine然后根據(jù)算法流程運行遺傳算法對目標進行優(yōu)化.
這樣我們便脫離每次都要寫遺傳算法流程的繁瑣，每次只需要像寫插件一樣實現(xiàn)自己的算子和適應(yīng)度函數(shù)便可以將其放入gaft開始對算法進行測試或者對目標函數(shù)進行優(yōu)化了。
GAFT文件結(jié)構(gòu)
此部分我對自己實現(xiàn)的框架的整體結(jié)構(gòu)進行下介紹.
- .
- ├── 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
目前的文件結(jié)果如上所示，
- /gaft/components中定義了內(nèi)置的個體和種群類型，提供了兩種不同的遺傳編碼方式:二進制編碼和實數(shù)編碼。
- /gaft/plugin_interfaces中是插件接口定義，所有的算子定義以及on-the-fly分析的接口規(guī)則都在里面，使用者可以根據(jù)此來編寫自己的插件并放入到engine中。
- /gaft/operators里面是內(nèi)置遺傳算子，他們也是遵循/gaft/plugin_interfaces中的規(guī)則進行編寫，可以作為編寫算子的例子。其中算子我目前內(nèi)置了roulette wheel選擇算子，uniform 交叉算子和flipbit變異算子，使用者可以直接使用內(nèi)置算子來使用gaft對自己的問題進行優(yōu)化。
- /gaft/analysis里面是內(nèi)置的on-the-fly分析插件，他可以在遺傳算法迭代的過程中對迭代過程中的變量進行分析，例如我在里面內(nèi)置了控制臺日志信息輸出，以及迭代適應(yīng)度值的保存等插件方便對進化曲線作圖。
- /gaft/engine便是遺傳算法的流程控制模塊了，他將所有的之前定義的各個部分組合到一起使用遺傳算法流程進行優(yōu)化迭代。
使用GAFT
下面我就以兩個函數(shù)作為例子來使用GAFT對目標函數(shù)進行優(yōu)化.
一維搜索
首先我們先對一個簡單的具有多個局部極值的函數(shù)進行優(yōu)化，我們來使用內(nèi)置的算子求函數(shù) f(x)=x+10sin(5x)+7cos(4x)的極大值，x的取值范圍為[0,10]
1. 先導(dǎo)入需要的模塊
- from math import sin, cos
- # 導(dǎo)入種群和內(nèi)置算子相關(guān)類
- 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
- # 內(nèi)置的存檔適應(yīng)度函數(shù)的分析類
- from gaft.analysis.fitness_store import FitnessStoreAnalysis
- # 我們將用兩種方式將分析插件注冊到遺傳算法引擎中
2. 創(chuàng)建引擎
- # 定義種群
- indv_template = GAIndividual(ranges=[(0, 10)], encoding='binary', eps=0.001)
- population = GAPopulation(indv_template=indv_template, size=50)
- # 創(chuàng)建遺傳算子
- selection = RouletteWheelSelection()
- crossover = UniformCrossover(pc=0.8, pe=0.5)
- mutation = FlipBitMutation(pm=0.1)
- # 創(chuàng)建遺傳算法引擎, 分析插件和適應(yīng)度函數(shù)可以以參數(shù)的形式傳入引擎中
- engine = GAEngine(population=population, selection=selection,
- crossover=crossover, mutation=mutation,
- analysis=[FitnessStoreAnalysis])
3. 自定義適應(yīng)度函數(shù)
可以通過修飾符的方式將，適應(yīng)度函數(shù)注冊到引擎中。
- @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, 開始跑(優(yōu)化)吧!
我們這里跑100代種群.
- if '__main__' == __name__:
- # Run the GA engine.
- engine.run(ng=100)
內(nèi)置的分析插件會在每步迭代中記錄得到的每一代的***個體，并生成數(shù)據(jù)保存。
繪制一下函數(shù)本身的曲線和我們使用遺傳算法得到的進化曲線:
優(yōu)化過程動畫:
二維搜索
下面我們使用GAFT內(nèi)置算子來搜索同樣具有多個極值點的二元函數(shù)f(x)=ysin(2πx)+xcos(2πy) 的***值，x, y 的范圍為 [−2,2] .
這里我們就不自定義分析插件了，直接使用內(nèi)置的分析類，并在構(gòu)造引擎時直接傳入.
- '''
- 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)
進化曲線:
二維函數(shù)面:
搜索過程動畫:
可見目前內(nèi)置的基本算子都能很好的找到例子中函數(shù)的***點。
總結(jié)
本文主要介紹了本人開發(fā)的一個用于遺傳算法做優(yōu)化計算的Python框架，框架內(nèi)置了遺傳算法中常用的組件，包括不同編碼方式的個體，種群，以及遺傳算子等。同時框架還提供了自定義遺傳算子和分析插件的接口，能夠方便快速搭建遺傳算法流程并用于算法測試。
目前框架僅僅處于初步階段，后續(xù)會在自己使用的過程中逐步完善更多的內(nèi)置算子，是框架更加通用。本文中的兩個優(yōu)化例子均能在GitHub上找到源碼(https://github.com/PytLab/gaft/tree/master/examples)
目前的計劃：1. 添加更多的內(nèi)置算子; 2. 給內(nèi)置算子和組件添加C++ backend; 3. 并行化
參考
- 《智能優(yōu)化算法及其MATLAB實例》
- 《MATLAB***化計算》
