遺傳演算法中適值函數的標定與大變異演算法
（點擊
上方藍字
，快速關注我們）
來源：伯樂在線 - iPytLab
如有好文章投稿，請點擊 → 這裡了解詳情
前言
本文嘗試對遺傳演算法中不同適值函數的標定(Scaling)方法進行下總結，並針對常用的線性標定和動態線性標定進行了Python實現，以裝飾器的形式添加到遺傳演算法框架GAFT中，這樣在使用GAFT運行遺傳演算法迭代的時候可以更加Pythonic的給自定義的適值函數進行標定。最後針對能夠防止早熟情況的大變異演算法進行了相應的實現。
目前(動態)線性標定裝飾器以及大變異運算元均已添加到GAFT中，gaft項目鏈接:
GitHub: https://github.com/PytLab/gaft
PyPI: https://pypi.python.org/pypi/gaft
適值函數的標定
選擇壓力
The tendency to select the best member of the current generation is known as selective pressure.
選擇壓力也就是種群中最好個體與最壞個體被選中概率的差值，這個差距越大，選中好個體的趨勢就越大，則成為選擇壓力大。
適值函數的標定
一般情況下，直接拿目標函數作為適值函數十分的方便，但是很多情況下卻不能這麼做，例如對於求最小值問題，我們必須將目標函數取反才能作為適值函數(這是最簡單的情況)。
當我們遺傳演算法中不同個體適值函數的值相對差別很小的時候，我們根據適應度值的大小進行個體選擇的選擇壓力(Selective pressure)就會變小，選優的能力弱化，這個時候我們需要對原始的適值函數進行標定(Scaling)是的他們相對差別增大，進而增大選擇壓力，增強演算法的選優能力。
例如:
局部搜索、廣域搜索與選擇壓力的關係
在遺傳演算法中，局部搜索同廣域搜索其實相互矛盾的，注重局部搜索則會陷入局部最優，但是注重廣域搜索會導致演算法精確開發能力不強。因此需要綜合兩者考慮，我們可以在搜索剛剛開始的時候使用較小的選擇壓力來廣域搜索，隨著迭代的進行可以動態的增大選擇壓力來使演算法偏向於局部搜索。
幾種不同的適值函數標定方法
對目標函數的標定方法一般有:線性標定、動態線性標定、冪律標定、對數標定等
線性標定
線性標定的形式:
其中f′為標定後的適值函數，ff為原始的目標函數。
求最大值
對於求目標函數的最大值的時候, 即 arg max f(x)
我們取a=1,b=?fmin+ξ, 其中ξ是一個較小的數，目的是使得種群中最差個體也有被選中的機會，不然自身減掉f?fmin=0, ξ的存在可以增加種群的多樣性。
最終的適值函數表達式:
求最小值
當我們需要求目標函數最小值的時候，arg min f(x)，我們需要對目標函數進行取反操作, 即 a=?1,b=fmax?f(x)+ξ
最終的適值函數表達式:
GAFT中添加對於目標函數的標定
由於適值函數標定並不針對某個目標函數，我便想通過裝飾器的方式來方便給任何自定義的fitness函數進行標定。對於基本的線性標定，我在GAEngine中添加了個帶參數的裝飾器:
def
linear_scaling
(
self
,
target
=
"max"
,
ksi
=
0.5
)
:
"""
A decorator constructor for fitness function linear scaling.
:param target: The optimization target, maximization or minimization.
:type target: str, "max" or "min"
:param ksi: Selective pressure adjustment value.
:type ksi: float
Linear Scaling:
1. arg max f(x), then f" = f - min{f(x)} + ksi;
2. arg min f(x), then f" = max{f(x)} - f(x) + ksi;
"""
def
_linear_scaling
(
fn
)
:
# For original fitness calculation.
self
.
ori_fitness
=
fn
@
wraps
(
fn
)
def
_fn_with_linear_scaling
(
indv
)
:
# Original fitness value.
f
=
fn
(
indv
)
# Determine the value of a and b.
if
target
==
"max"
:
f_prime
=
f
-
self
.
ori_fmin
+
ksi
elif
target
==
"min"
:
f_prime
=
self
.
ori_fmax
-
f
+
ksi
else
:
raise
ValueError
(
"Invalid target type({})"
.
format
(
target
))
return
f_prime
return
_fn_with_linear_scaling
return
_linear_scaling
這個時候如果我們在定義了一個自己的目標函數以後，想對其進行線性標定便可以使用engine的這個裝飾器對函數進行修飾即可, 像下面這樣:
# Create a GA engine...
# 先標定，後註冊到引擎中
@
engine
.
fitness
_
register@
engine
.
linear_scaling
(
target
=
"min"
,
ksi
=
0.5
)
def
fitness
(
indv
)
:
x
,
=
indv
.
variants
return
x
+
10
*
sin
(
5
*
x
)
+
7
*
cos
(
4
*
x
)
其中裝飾器中的參數分別為:
target: 優化目標函數到最小值還是最大值，值可以是:"max"或者"min"
ksi: 即公式中ξξ
動態線性標定
動態線性標定是遺傳演算法中最常用的標定方法，他是基於上面提到的線性標定，在線性標定中的ξξ在動態線性標定中並不是一成不變的，而是隨著迭代次數的增加而變化。
動態線性標定的函數表達式:
其中，k為迭代指標，表示ξ會隨著迭代數而不同。
求最大值
當我們的優化目標是目標函數的最大值，這是我們取ak=1,bk=?fmin+ξk, 這是的函數表達為:
關於ξk
動態線性標定中的ξk作用同線性標定中的ξ為選擇壓力調節值, 它的存在使得種群中最壞的個體仍有被選中的機會，但是動態標定中的ξkξk的值會隨著kk增大而減小。
ξk的取值: ξ0=M, ξk=ξk?1?r, r∈[0.9,0.999], 我們通過調節M和r來調節ξk
通過可以動態變化的ξk，我們可以使廣域搜索範圍寬保持種群的多樣性，局部搜索保持收斂性，即，開始時希望選擇小，迭代到後面希望選擇壓力逐漸變大.
GAFT中添加給目標函數添加動態線性標定
與上麵線性標定的方法相同，GAFT中同樣使用了標定裝飾器來裝飾用戶自定義的目標函數，實現代碼:
def
dynamic_linear_scaling
(
self
,
target
=
"max"
,
ksi0
=
2
,
r
=
0.9
)
:
"""
A decorator constructor for fitness dynamic linear scaling.
:param target: The optimization target, maximization or minimization.
:type target: str, "max" or "min"
:param ksi0: Initial selective pressure adjustment value, default value
is 2
:type ksi0: float
:param r: The reduction factor for selective pressure adjustment value,
ksi^(k-1)*r is the adjustment value for generation k, default
value is 0.9
:type r: float in range [0.9, 0.999]
Dynamic Linear Scaling:
For maximizaiton, f" = f(x) - min{f(x)} + ksi^k, k is generation number.
"""
def
_dynamic_linear_scaling
(
fn
)
:
# For original fitness calculation.
self
.
ori_fitness
=
fn
@
wraps
(
fn
)
def
_fn_with_dynamic_linear_scaling
(
indv
)
:
f
=
fn
(
indv
)
k
=
self
.
current_generation
+
1
if
target
==
"max"
:
f_prime
=
f
-
self
.
ori_fmin
+
ksi0
*
(
r
**
k
)
elif
target
==
"min"
:
f_prime
=
self
.
ori_fmax
-
f
+
ksi0
*
(
r
**
k
)
else
:
raise
ValueError
(
"Invalid target type({})"
.
format
(
target
))
return
f_prime
return
_fn_with_dynamic_linear_scaling
return
_dynamic_linear_scaling
這裡充分的利用Python的閉包，在engine中獲取當前種群最大值與最小值的相關數據。
在腳本中修飾目標函數便可以這樣:
@
engine
.
fitness
_
register@
engine
.
dynamic_linear_scaling
(
target
=
"max"
,
ksi0
=
2
,
r
=
0.9
)
def
fitness
(
indv
)
:
x
,
=
indv
.
variants
return
x
+
10
*
sin
(
5
*
x
)
+
7
*
cos
(
4
*
x
)
其他標定方法
這裡簡要的介紹下其他標定方法。
冪律標定
函數表達式: f′=fα
α的取值, α>1增大選擇壓力, α<1減小選擇壓力
對數標定
函數表達式: f′=aLnf+b
作用: 縮小目標函數之間的差別
指數標定
函數表達式: f′=aebf+c
作用: 擴大目標函數間的差別
窗口技術
函數表達式: f′=af?fw
fw為前W代中的目標函數最小值，他考慮了各代fmin的波動，這樣fw具有記憶性
大變異演算法
眾所周知，簡單的遺傳演算法存在「早熟」的問題，也就是演算法過早的收斂到一個非全局最優點，出現此問題的主要原因是一種被稱為「頂端優勢」的現象存在，即當演算法進行到某一代時，在種群中某個個體的適應度遠遠大於任何一個個體的適應度，導致選擇演算法總是會選到此個體生成子代個體，極限情況下就是所有個體都來自統一祖先，即」早熟」。除了對目標函數進行標定，我們可以通過大變異演算法來避免早熟。
大致思路: 當某代中所有個體集中在一起時，我們以一個遠大於通常變異概率的概率執行一次變異操作，具有大變異概率的變異操作能夠隨機、獨立的產生許多新的個體，從而是整個種群脫了「早熟」。
如何判斷種群個體的集中程度
通常採取比較種群中所有個體的適應度值的平均值favg與最大值fmax的接近程度來判斷，如果最大值與平均值越接近說明個體就越集中。
具體過程
當某一代的最大適應度fmax與平均適應度值favg滿足:
其中，0.5<α<1, 被稱為密集因子，表徵個體集中程度。隨後，我們以一個大變異概率進行一次變異操作(通常大5倍以上), 即「打散」。
大變異操作的兩個參數
密集因子α: 決定大變異操作在整個過程中所佔的比重，其數值約接近0.5，大變異操作越頻繁
大變異概率: 概率越大，大變異演算法的穩定性就越好，但是收斂速度可能會降低，當大變異概率的數值為0.5的時候，大變異操作就近似退化為隨機搜索
GAFT中的大變異運算元
大變異操作與具體的變異運算元實現無關，這裡我還是依據內置的FlipBitMutation運算元為基礎, 具體的代碼實現參見https://github.com/PytLab/gaft/blob/master/gaft/operators/mutation/flip_bit_mutation.py
class
FlipBitBigMutation
(
FlipBitMutation
)
:
def
__init__
(
self
,
pm
,
pbm
,
alpha
)
:
"""
Mutation operator using Flip Bit mutation implementation with adaptive
big mutation rate to overcome premature or local-best solution.
:param pm: The probability of mutation (usually between 0.001 ~ 0.1)
:type pm: float in (0.0, 1.0]
:param pbm: The probability of big mutation, usually more than 5 times
bigger than pm.
:type pbm: float
:param alpha: intensive factor
:type alpha: float, in range (0.5, 1)
"""
super
(
self
.
__class__
,
self
).
__init__
(
pm
)
if
not
(
0.0
<
pbm
<
1.0
)
:
raise
ValueError
(
"Invalid big mutation probability"
)
if
pbm
<
5
*
pm
:
self
.
logger
.
warning
(
"Relative low probability for big mutation"
)
self
.
pbm
=
pbm
# Intensive factor.
if
not
(
0.5
<
alpha
<
1.0
)
:
raise
ValueError
(
"Invalid intensive factor, should be in (0.5, 1.0)"
)
self
.
alpha
=
alpha
def
mutate
(
self
,
individual
,
engine
)
:
"""
Mutate the individual with adaptive big mutation rate.
"""
pm
=
self
.
pm
if
engine
.
fmax
*
self
.
alpha
<
engine
.
fmean
:
self
.
pm
=
self
.
pbm
self
.
logger
.
info
(
"Big mutation probabilty: {} -> {}"
.
format
(
pm
,
self
.
pm
))
# Mutate with big probability.
individual
=
super
(
self
.
__class__
,
self
).
mutate
(
individual
,
engine
)
# Recover probability.
self
.
pm
=
pm
return
individual
總結
本文嘗試對遺傳演算法中不同適值函數的標定(Scaling)方法進行下總結，並針對常用的線性標定和動態線性標定進行了Python實現，以裝飾器的形式添加到遺傳演算法框架GAFT中，這樣在使用GAFT運行遺傳演算法迭代的時候可以更加Pythonic的給自定義的適值函數進行標定。最後針對能夠防止早熟情況的大變異演算法進行了相應的實現。
參考
《MATLAB最優化計算(第三版)》
馬鈞水, 劉貴忠, 賈玉蘭. 改進遺傳演算法搜索性能的大變異操作[J]. 控制理論與應用, 1998(3):404-408.
看完本文有收穫？請轉發分享給更多人
關注「大數據與機器學習文摘」，成為Top 1%
※用 Scikit-Learn 和 Pandas 學習線性回歸
※Python 源碼閱讀：類型
※Python 爬蟲：爬取小說花千骨
※Python 最難的問題
※遺傳演算法中幾種不同選擇運算元及 Python 實現
TAG:Python開發者 |