本文用Python3完整實(shí)現(xiàn)了簡單遺傳算法(SGA)

Simple Genetic Alogrithm是模擬生物進(jìn)化過程而提出的一種優(yōu)化算法。SGA采用隨機(jī)導(dǎo)向搜索全局最優(yōu)解或者說近似全局最優(yōu)解。傳統(tǒng)的爬山算法(例如梯度下降，牛頓法)一次只優(yōu)化一個(gè)解，并且對于多峰的目標(biāo)函數(shù)很容易陷入局部最優(yōu)解，而SGA算法一次優(yōu)化一個(gè)種群(即一次優(yōu)化多個(gè)解)，SGA比傳統(tǒng)的爬山算法更容易收斂到全局最優(yōu)解或者近似全局最優(yōu)解。
SGA基本流程如下:

1、對問題的解進(jìn)行二進(jìn)制編碼。編碼涉及精度的問題，在本例中精度delta=0.0001,根據(jù)決策變量的上下界確定對應(yīng)此決策變量的染色體基因的長度（m）。假設(shè)一個(gè)決策變量x0上界為upper,下界為lower,則精度delta = (upper-lower)/2^m-1。如果已知決策變量邊界和編碼精度，那么可以用下面的公式確定編碼決策變量x0所對應(yīng)的染色體長度：

2^(length-1)<(upper-lower)/delta<=2^length-1

2、對染色體解碼得到表現(xiàn)形:

解碼后得到10進(jìn)制的值；decoded = lower + binary2demical(chromosome)*delta。其中binary2demical為二進(jìn)制轉(zhuǎn)10進(jìn)制的函數(shù)，在代碼中有實(shí)現(xiàn)，chromosome是編碼后的染色體。

3、確定初始種群,初始種群隨機(jī)生成

4、根據(jù)解碼函數(shù)得到初始種群的10進(jìn)制表現(xiàn)型的值

5、確定適應(yīng)度函數(shù)，對于求最大值最小值問題，一般適應(yīng)度函數(shù)就是目標(biāo)函數(shù)。根據(jù)適應(yīng)度函數(shù)確定每個(gè)個(gè)體的適應(yīng)度值Fi=FitnessFunction(individual);然后確定每個(gè)個(gè)體被選擇的概率Pi=Fi/sum(Fi),sum(Fi)代表所有個(gè)體適應(yīng)度之和。

6、根據(jù)輪盤賭選擇算子，選取適應(yīng)度較大的個(gè)體。一次選取一個(gè)個(gè)體，選取n次,得到新的種群population

7、確定交叉概率Pc,對上一步得到的種群進(jìn)行單點(diǎn)交叉。每次交叉點(diǎn)的位置隨機(jī)。

8、確定變異概率Pm,假設(shè)種群大小為10，每個(gè)個(gè)體染色體編碼長度為33，則一共有330個(gè)基因位，則變異的基因位數(shù)是330*Pm。接下來，要確定是那個(gè)染色體中哪個(gè)位置的基因發(fā)生了變異。將330按照10進(jìn)制序號進(jìn)行編碼即從0,1,2,.......229。隨機(jī)從330個(gè)數(shù)中選擇330*Pm個(gè)數(shù)，假設(shè)其中一個(gè)數(shù)時(shí)154，chromosomeIndex = 154/33 =4,
geneIndex = 154%33 = 22。由此確定了第154號位置的基因位于第4個(gè)染色體的第22個(gè)位置上，將此位置的基因值置反完成基本位變異操作。

9、以上步驟完成了一次迭代的所有操作。接下就是評估的過程。對變異后得到的最終的種群進(jìn)行解碼，利用解碼值求得每個(gè)個(gè)體的適應(yīng)度值，將最大的適應(yīng)度值保存下來，對應(yīng)的解碼后的決策變量的值也保存下來。

10、根據(jù)迭代次數(shù)，假設(shè)是500次，重復(fù)執(zhí)行1-9的步驟，最終得到是一個(gè)500個(gè)數(shù)值的最優(yōu)適應(yīng)度取值的數(shù)組以及一個(gè)500*n的決策變量取值數(shù)組（假設(shè)有n個(gè)決策變量）。從500個(gè)值中找到最優(yōu)的一個(gè)（最大或者最小，根據(jù)定義的適應(yīng)度函數(shù)來選擇）以及對應(yīng)的決策變量的取值。