python实现的遗传算法实例（一）

杨利霞

python实现的遗传算法实例（一）

一、遗传算法介绍
2 P7 ~$ h6 ]2 Q# c( D2 `
+ M- |. k& U& F" i8 e( z        遗传算法是通过模拟大自然中生物进化的历程，来解决问题的。大自然中一个种群经历过若干代的自然选择后，剩下的种群必定是适应环境的。把一个问题所有的解看做一个种群，经历过若干次的自然选择以后，剩下的解中是有问题的最优解的。当然，只能说有最优解的概率很大。这里，我们用遗传算法求一个函数的最大值。
        f(x) = 10 * sin( 5x ) + 7 * cos( 4x ),    0 <=  x <= 10

2 c1 Y8 Q! ?' x  U& k1、将自变量x进行编码

      取基因片段的长度为10, 则10位二进制位可以表示的范围是0到1023。基因与自变量转变的公式是x = b2d(individual) * 10 / 1023。构造初始的种群pop。每个个体的基因初始值是[0, 1, 0, 1, 0, 1, 0, 1, 0, 1]

5 ?% \+ n: G8 ~" r' P1 ^" m  ^2、计算目标函数值

, M9 z( u# K- H' l      根据自变量与基因的转化关系式，求出每个个体的基因对应的自变量，然后将自变量代入函数f（x），求出每个个体的目标函数值。
7 Y1 e! E( v, G5 w
' K3 `: Q. e) M/ a6 ?9 ~3、适应度函数
; H0 l* c9 s4 U* u0 ^
+ v2 U/ O9 ~7 `/ X" {      适应度函数是用来评估个体适应环境的能力，是进行自然选择的依据。本题的适应度函数直接将目标函数值中的负值变成0. 因为我们求的是最大值，所以要使目标函数值是负数的个体不适应环境，使其繁殖后代的能力为0.适应度函数的作用将在自然选择中体现。
7 \5 v  f8 e8 Y1 b1 @
; y; ^# n8 Q  T: B4、自然选择

) g2 X: r6 _5 T- Q6 Y自然选择的思想不再赘述，操作使用轮盘赌算法。其具体步骤：

假设种群中共5个个体，适应度函数计算出来的个体适应性列表是fitvalue = [1 ,3, 0, 2, 4] ，totalvalue = 10 ， 如果将fitvalue画到圆盘上，值的大小表示在圆盘上的面积。在转动轮盘的过程中，单个模块的面积越大则被选中的概率越大。选择的方法是将fitvalue转化为[1 ， 4 ，4 , 6 ，10], fitvalue / totalvalue = [0.1 , 0.4 , 0.4 , 0.6 , 1.0] . 然后产生5个0-1之间的随机数，将随机数从小到大排序，假如是[0.05 , 0.2 , 0.7 , 0.8 ,0.9]，则将0号个体、1号个体、4号个体、4号个体、4号个体拷贝到新种群中。自然选择的结果使种群更符合条件了。

5、繁殖
* T8 f6 y& X- }* M- C+ f8 b4 Q
假设个体a、b的基因是
& Y8 |/ R: s. W$ E1 F/ t6 U7 }
a = [1, 0, 0, 0, 0, 1, 1, 1, 0, 0]
/ o9 f& L( H5 e4 u1 M- I
3 u1 ?. \# F1 f! p3 j0 d% Ub = [0, 0, 0, 1, 1, 0, 1, 1, 1, 1]

这两个个体发生基因交换的概率pc = 0.6.如果要发生基因交换，则产生一个随机数point表示基因交换的位置，假设point = 4,则：

% S  F7 G5 ?8 z2 U, Ha = [1, 0, 0, 0, 0, 1, 1, 1, 0, 0]

' N2 `: K0 d( E% z( Q1 sb = [0, 0, 0, 1, 1, 0, 1, 1, 1, 1]

' G1 A$ z" M5 h9 a* I交换后为：
' h: i" r! n( ]
a = [1, 0, 0, 0, 1, 0, 1, 1, 1, 1]
5 h; x$ ?; f$ N2 R6 e
b = [0, 0, 0, 1, 0, 1, 1, 1, 0, 0]

/ r" Q9 b  v/ g, g! D* w6、突变
( F% B3 h: {  z/ ^/ o. S8 [
遍历每一个个体，基因的每一位发生突变（0变为1,1变为0）的概率为0.001.突变可以增加解空间

4 a8 z  I: C7 C7 v& f1 {" O二、代码
% V% }" u9 m& G$ {: Tdef b2d(b): #将二进制转化为十进制 x∈[0,10]
        t = 0
& c% o" _) J0 m1 u% C        for j in range(len(b)):
                t += b[j] * (math.pow(2, j))
; m9 n$ V* y  I5 {5 I% B. M        t = t * 10 / 1023
        return t
8 l+ ?. p! A! @- @- V" h
! x! i' y% |$ j# e/ a  Qpopsize = 50 #种群的大小
#用遗传算法求函数最大值：
#f(x)=10*sin(5x)+7*cos(4x) x∈[0,10]
9 H  V& d3 ?% I. K# U6 \
6 A0 N. n8 e2 L  Schromlength = 10 #基因片段的长度
) C1 b9 G# c4 ]( z/ l* J  kpc = 0.6 #两个个体交叉的概率
' L+ y' J7 w7 a& ~pm = 0.001; #基因突变的概率
. l" v: [& M$ Y5 d6 k' Bresults = [[]]
# J9 \* y' P4 S$ t6 q/ G- S" rbestindividual = []
4 H+ e* u! b# Mbestfit = 0
fitvalue = []
tempop = [[]]
pop = [[0, 1, 0, 1, 0, 1, 0, 1, 0, 1]  for i in range(popsize)]
4 N* L5 [8 o* O6 I% ^3 vfor i in range(100): #繁殖100代
+ C0 F- q3 L0 o8 T$ {- a: P4 t        objvalue = calobjvalue(pop) #计算目标函数值
5 ?% R) z2 j) r+ W( g9 Q. m5 T        fitvalue = calfitvalue(objvalue); #计算个体的适应值
        [bestindividual, bestfit] = best(pop, fitvalue) #选出最好的个体和最好的函数值
        results.append([bestfit,b2d(bestindividual)]) #每次繁殖，将最好的结果记录下来
) q: f) H* H( c/ [* @- E        selection(pop, fitvalue) #自然选择，淘汰掉一部分适应性低的个体
        crossover(pop, pc) #交叉繁殖
        mutation(pop, pc) #基因突变
+ p6 F5 o* |  U; Y5 Z       
  k% o2 l* T, N" R
$ N3 P6 V$ ]; g9 Iresults.sort()       
print(results[-1]) #打印函数最大值和对应的
. j( K: a# {: |$ Ddef calfitvalue(objvalue):#转化为适应值，目标函数值越大越好，负值淘汰。
- r; w4 f3 R& h+ K" J    fitvalue = []
3 v6 b$ u( i$ q7 A    temp = 0.0
    Cmin = 0;
    for i in range(len(objvalue)):
" ~+ Q2 X2 P$ i8 B        if(objvalue + Cmin > 0):
            temp = Cmin + objvalue
0 M" L5 f% e7 p# M- E! V0 P        else:
1 O6 Q) y) k: N. A2 o/ u            temp = 0.0
        fitvalue.append(temp)
& H1 Y2 g3 K& h9 q    return fitvalue
import math

3 [7 a0 Y% _6 {4 d  Z! A: t7 Hdef decodechrom(pop): #将种群的二进制基因转化为十进制（0,1023）
    temp = [];
. K! b$ p- n" z6 h' ]4 O' E8 r; V    for i in range(len(pop)):
: \! R1 R# O3 t' c* a" N0 V        t = 0;
        for j in range(10):
            t += pop[j] * (math.pow(2, j))
* T6 v) W1 U# [, m' R        temp.append(t)
$ m& d2 g% s! {/ D$ ?    return temp

def calobjvalue(pop): #计算目标函数值
" q! O' }: O0 x9 _    temp1 = [];
    objvalue = [];
    temp1 = decodechrom(pop)
- @9 F) K6 e/ t7 c8 r2 c  ]" o5 K( N    for i in range(len(temp1)):
# m2 l5 K; z: k# K2 \. q7 r/ u% ~        x = temp1 * 10 / 1023 #（0,1023）转化为 （0,10）
        objvalue.append(10 * math.sin(5 * x) + 7 * math.cos(4 * x))
* Y) ?5 d, u5 l1 g# }) q: F1 O    return objvalue #目标函数值objvalue[m] 与个体基因 pop[m] 对应
def best(pop, fitvalue): #找出适应函数值中最大值，和对应的个体
( @" L# ^, B  y+ c( u        px = len(pop)
0 r& `# {  U5 v0 C" X9 Q        bestindividual = []
8 V: D" J4 s- e( K( ^, m: k7 _- R        bestfit = fitvalue[0]
        for i in range(1,px):
5 m9 l, ]4 k" y* G                if(fitvalue > bestfit):
                        bestfit = fitvalue
                        bestindividual = pop
6 _" K4 t( ]4 g, {) t9 |5 u        return [bestindividual, bestfit]
import random

! S& j! P# N8 e0 i$ t4 idef sum(fitvalue):
. c% o' T; c( F$ ^( N    total = 0
  u0 ~4 p. {4 W/ D4 m    for i in range(len(fitvalue)):
        total += fitvalue
    return total
7 L# L7 X: {7 D1 [$ a. @  I
def cumsum(fitvalue):
    for i in range(len(fitvalue)):
+ X7 ~3 X; D* \' s% e- h        t = 0;
3 J- \4 O4 ~: R+ |1 R' C        j = 0;
        while(j <= i):
            t += fitvalue[j]
6 l  U# L8 S# p9 m5 z/ G1 z            j = j + 1
2 O9 q2 u6 T1 F! T4 v& w' l        fitvalue = t;
" ^0 V$ L' Z7 i  _; ~8 ]
, y3 ^& J$ C( c+ ?def selection(pop, fitvalue): #自然选择（轮盘赌算法）
4 a% g  y$ S  l+ m& k: K* ^        newfitvalue = []
6 c& C* V) o3 r, e7 [        totalfit = sum(fitvalue)
9 z/ n- K* u& K2 u  [        for i in range(len(fitvalue)):
                newfitvalue.append(fitvalue / totalfit)
        cumsum(newfitvalue)
  P5 i2 c! ?$ z, h9 ?) A0 W% a        ms = [];
        poplen = len(pop)
        for i in range(poplen):
                ms.append(random.random()) #random float list ms
        ms.sort()
        fitin = 0
        newin = 0
! j  Z. s: ]+ l6 d! ]        newpop = pop
3 e- n6 W1 ^9 S& P  q. w        while newin < poplen:
                if(ms[newin] < newfitvalue[fitin]):
# E% A) |- |) |) v6 u  z                        newpop[newin] = pop[fitin]
                        newin = newin + 1
( e; L% \% m* g& S0 B. `                else:
                        fitin = fitin + 1
; [$ |" ?: {1 n1 b        pop = newpop
0 \4 L: l7 W7 @0 e, o% W6 Eimport random
9 f( R$ p, |" j5 Q5 L" [
def crossover(pop, pc): #个体间交叉，实现基因交换
    poplen = len(pop)
  X. \" m8 T- Q* R: b1 @    for i in range(poplen - 1):
        if(random.random() < pc):
            cpoint = random.randint(0,len(pop[0]))
- p( b  m- G) B            temp1 = []
8 j. c( A) ]# N! F0 G: Y& n0 O, C            temp2 = []
- w0 t" u0 L, Z- g& [            temp1.extend(pop[0 : cpoint])
4 a- o! n1 v3 Z            temp1.extend(pop[i+1][cpoint : len(pop)])
            temp2.extend(pop[i+1][0 : cpoint])
8 ~; |, }' W* u! B7 E+ \5 G5 m            temp2.extend(pop[cpoint : len(pop)])
/ T! n$ ~* S8 S+ |& w: `( A            pop = temp1
            pop[i+1] = temp2
) s5 W, `" o% eimport random
, O* B4 n- C; ^6 J  t
% w% \* J/ k  ^, Y9 |def mutation(pop, pm): #基因突变
$ n- m: S% w- {$ t/ ~  S8 M# T    px = len(pop)
    py = len(pop[0])
0 u+ s* A! S, }, E- `
, p. u6 N# n  k2 z4 G. t  f    for i in range(px):
        if(random.random() < pm):
            mpoint = random.randint(0,py-1)
: Z. u& F7 d8 A            if(pop[mpoint] == 1):
0 L' ~7 }7 [8 }: m0 _$ o4 }5 y                pop[mpoint] = 0
            else:
$ o/ [$ W) @" f+ \* }( v, o4 Y                pop[mpoint] = 1

: {4 v/ t: n5 @' H9 _
————————————————
& G1 u4 T+ J' O6 g$ J) h版权声明：本文为CSDN博主「simon-zhao」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
1 T4 b# z6 q2 p$ `* I原文链接：https://blog.csdn.net/u010902721/article/details/23531359


# G! J' f4 k" u7 X