遺傳算法及其實作

遺傳算法是計算數學中用于解決最優化的搜尋算法，是進化算法的一種。它是借鑒了生物進化學中的一些現象而發展起來的，這些現象包括遺傳，突變，自然選擇以及雜交等。

遺傳算法的思想

遺傳算法是模拟生物學種的進化論，物種朝着有利于自己的方向發展，這在遺傳算法中表現為朝着最優化的方向發展。在進化過程中，遺傳算法模拟基因的行為，首先選擇有優勢的基因，并對基因進行配對，然後等位基因進行交換，并有一定的機率進行基因變異，這就導緻了下一代基因的産生，産生新的個體。

編碼和解碼

遺傳算法的編碼有兩種，二進制編碼和浮點數編碼。将一個二進制串(長度為n)轉化為區間[a,b]裡對應是實數值：

（1）将一個二進制串代表的二進制轉化為10進制數

( b 0 ⋯ b n − 2 b n − 1 ) 2 = ( Σ i = 0 n − 1 b i ⋅ 2 i ) 10 = x t (b_0\cdots b_{n-2}b_{n-1})_2=(\Sigma_{i=0}^{n-1}b_i\cdot 2^i)_{10}=x^t (b0​⋯bn−2​bn−1​)2​=(Σi=0n−1​bi​⋅2i)10​=xt

（2）對應區間内的實數

x = a + x t b − a 2 n − 1 x = a+x^t\frac{b-a}{2^{n}-1} x=a+xt2n−1b−a​

選擇

越适應的個體越有可能繁衍後代，通過适應性函數（被選中的機率函數）選擇個體進行繁殖，某個個體被選中的機率為

p i = f i Σ i = 1 n f i p_i = \frac{f_i}{\Sigma_{i=1}^nf_i} pi​=Σi=1n​fi​fi​​

交叉

即同源染色體聯會過程中，非姐妹染色單體之間發生交叉，并交換一部分染色體，也是等位基因的交換。

基因突變

基因突變是染色體某一個基因點的改變，基因串上0或1突變為1或0。例如

1001000101110 1001000101110 1001000101110

經過突變後可能變為

1001000101111 1001000101111 1001000101111

Python實作

# -*- coding:utf-8 -*-

#随機生成二進制編碼
import random
def geneEncoding(pop_size, chrom_length):
    pop = [[]]
    for i in range(pop_size):
        temp = []
        for j in range(chrom_length):
            temp.append(random.randint(0,1))
        pop.append(temp)
    return pop[1:]
# pop = geneEncoding(pop_size,chrom_length)

#對二進制編碼進行解碼并計算
import math
def decodechrom(pop, chrom_length):
    temp = []
    for i in range(len(pop)):
        t = 0
        for j in range(chrom_length):
            t += pop[i][j] * (math.pow(2,j)) #計算的對嗎，上面應該range(chrom_lenth,0,-1)
        temp.append(t)
    return temp

def calobjValue(pop, chrom_length, max_value):
    temp1 = []
    obj_value = []
    temp1 = decodechrom(pop,chrom_length)
    for i in range(len(temp1)):
        x = temp1[i] * max_value / (math.pow(2, chrom_length)-1)
        obj_value.append(10*math.sin(5*x) + 7 * math.cos(4*x))
    return obj_value

#淘汰個體(去除負值)
def calfitValue(obj_value):
    fit_value = []
    c_min = 0
    for i in range(len(obj_value)):
        if (obj_value[i] + c_min > 0):
            temp = c_min + obj_value[i] #c_min可以沒有
        else:
            temp = 0.0
        fit_value.append(temp)
    return fit_value

#選擇
def sum(fit_value):
    total = 0
    for i in range(len(fit_value)):
        total += fit_value[i]
    return total

def cumsum(fit_value):
    for i in range(len(fit_value)-2,-1,-1):
        t = 0
        j = 0
        while j <= i:
            t += fit_value[j]
            j += 1
        fit_value[i] = t
        fit_value[len(fit_value)-1] = 1 #why set it to 1

def selection(pop, fit_value):
    newfit_value = []
    #适應度總和
    total_fit = sum(fit_value)
    for i in range(len(fit_value)):
        newfit_value.append(fit_value[i] / total_fit)
    #計算累計機率
    cumsum(newfit_value)
    ms = []
    pop_len = len(pop)
    for i in range(pop_len):
        ms.append(random.random())
    ms.sort()
    fitin = 0
    newin = 0
    newpop = pop
    #轉輪盤選擇法
    while newin < pop_len:
        if(ms[newin] < newfit_value[fitin]):
            newpop[newin] = pop[fitin]
            newin += 1
        else:
            fitin += 1
    pop = newpop

#交叉
def crossover(pop, pc):
    pop_len = len(pop)
    for i in range(pop_len - 1):
        if random.random() < pc:
            cpoint = random.randint(0,len(pop[0]))
            temp1 = []
            temp2 = []
            temp1.extend(pop[i][0:cpoint])
            temp1.extend(pop[i+1][cpoint:len(pop[i])])
            temp2.extend(pop[i+1][0:cpoint])
            temp2.extend(pop[i][cpoint:len(pop[i])])
            pop[i] = temp1
            pop[i+1] = temp2

#變異
def mutation(pop, pm):
    px = len(pop)
    py = len(pop[0])
    for i in range(px):
        if random.random() < pm:
            mpoint = random.randint(0,py-1)
            if(pop[i][mpoint] == 1):
                pop[i][mpoint] = 0
            else:
                pop[i][mpoint] = 1

#找出最優解和最優解的基因編碼
def best(pop, fit_value):
    px = len(pop)
    best_individual = []
    best_fit = fit_value[0]
    for i in range(1,px):
        if fit_value[i] > best_fit:
            best_fit = fit_value[i]
            best_individual = pop[i]
    return [best_individual, best_fit]

#計算二進制序列代表的數值
def b2d(b, max_value, chrom_length):
    t = 0
    for j in range(len(b)):
        t += b[j] * math.pow(2,j)
    t = t * max_value / (math.pow(2, chrom_length) - 1)
    return t

import matplotlib.pyplot as plt

print 'y = 10 * math.sin(5*x) + 7 * math.cos(4*x)'


pop_size = 500  #種群數量
max_value = 10  #基因中允許出現的最大值
chrom_length = 10 #染色體長度
pc = 0.6        #交配機率
pm = 0.01       #變異機率
results = [[]]  #存儲每一代的最優解，N個二進制組
fit_value = []  #個體适應度
fit_mean = []   #平均适應度

pop = geneEncoding(pop_size, chrom_length)

for i in range(pop_size):
    obj_value = calobjValue(pop, chrom_length, max_value)
    fit_value = calfitValue(obj_value) #淘汰
    best_individual, best_fit = best(pop, fit_value)
    results.append([best_fit,b2d(best_individual,max_value,chrom_length)])
    selection(pop, fit_value) #新種群複制
    crossover(pop, pc) #交叉
    mutation(pop,pm) #變異

results = results[1:]
results.sort()

X = []
Y = []
for i in range(500):
    X.append(i)
    t = results[i][0]
    Y.append(t)

plt.plot(X,Y)
plt.show()

           

參考

遺傳算法入門到掌握（一）

非常好的了解遺傳算法的例子

用python實作簡單的遺傳算法

wiki-遺傳算法