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

杨利霞

python实现的遗传算法实例（一）
" I3 R% X2 h+ z/ a
7 d! P' D( I3 f, q3 k一、遗传算法介绍

: _0 e' m# X4 r8 p        遗传算法是通过模拟大自然中生物进化的历程，来解决问题的。大自然中一个种群经历过若干代的自然选择后，剩下的种群必定是适应环境的。把一个问题所有的解看做一个种群，经历过若干次的自然选择以后，剩下的解中是有问题的最优解的。当然，只能说有最优解的概率很大。这里，我们用遗传算法求一个函数的最大值。
' r# L  \; F, R) F        f(x) = 10 * sin( 5x ) + 7 * cos( 4x ),    0 <=  x <= 10
: }) z0 v8 E1 R/ B+ e
1、将自变量x进行编码
: {- k( G# \3 G( Q1 l
      取基因片段的长度为10, 则10位二进制位可以表示的范围是0到1023。基因与自变量转变的公式是x = b2d(individual) * 10 / 1023。构造初始的种群pop。每个个体的基因初始值是[0, 1, 0, 1, 0, 1, 0, 1, 0, 1]

2、计算目标函数值
# U9 j4 _7 n: m3 J
      根据自变量与基因的转化关系式，求出每个个体的基因对应的自变量，然后将自变量代入函数f（x），求出每个个体的目标函数值。

5 s3 L% L! k' A3、适应度函数

# L! x% S- h& X      适应度函数是用来评估个体适应环境的能力，是进行自然选择的依据。本题的适应度函数直接将目标函数值中的负值变成0. 因为我们求的是最大值，所以要使目标函数值是负数的个体不适应环境，使其繁殖后代的能力为0.适应度函数的作用将在自然选择中体现。

( C' e: X. W/ c; d6 I* V4、自然选择

1 @9 t& i3 \+ t) p8 b) I6 h! j  p1 {自然选择的思想不再赘述，操作使用轮盘赌算法。其具体步骤：
; {9 g0 v# [' H7 V6 M, U
- x, Y- f5 G0 j. t& ?- n假设种群中共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号个体拷贝到新种群中。自然选择的结果使种群更符合条件了。
; Q! W& J1 ]" o# n
5、繁殖

假设个体a、b的基因是

  }: |4 f9 y; t' [a = [1, 0, 0, 0, 0, 1, 1, 1, 0, 0]

, U, g" F" c6 y' z9 gb = [0, 0, 0, 1, 1, 0, 1, 1, 1, 1]
. w! h# j) P: L8 @4 c1 B, [
这两个个体发生基因交换的概率pc = 0.6.如果要发生基因交换，则产生一个随机数point表示基因交换的位置，假设point = 4,则：
! S5 |0 @3 w. J7 G2 Q
" @! A5 {, R8 z, I9 Ha = [1, 0, 0, 0, 0, 1, 1, 1, 0, 0]
: q, q2 M2 X3 C2 k/ y" F4 }2 X
b = [0, 0, 0, 1, 1, 0, 1, 1, 1, 1]

交换后为：
/ z6 @: j, \, Z& I  c, f, ]+ f8 R
/ z4 R! k) [, ?a = [1, 0, 0, 0, 1, 0, 1, 1, 1, 1]
. L; d7 Q3 N5 S0 h! X
b = [0, 0, 0, 1, 0, 1, 1, 1, 0, 0]
! `6 I4 Y# y# `( H. a% S4 a3 }
: z6 f3 T6 J; v$ o* K- p" x6、突变
# m% a2 _8 h  }5 f
& [5 A/ g4 ^2 }6 t, s遍历每一个个体，基因的每一位发生突变（0变为1,1变为0）的概率为0.001.突变可以增加解空间

二、代码
( F' K5 r$ {. R1 ]4 v& ]+ Ndef b2d(b): #将二进制转化为十进制 x∈[0,10]
4 _8 F" x  v' U  c        t = 0
        for j in range(len(b)):
                t += b[j] * (math.pow(2, j))
+ n: n- x, ~% L* c! H        t = t * 10 / 1023
% t! W+ ]! q6 Y4 A+ d* n        return t
2 f* M  z; f! [6 E4 W
/ C+ u' k. l9 v' u7 \  ^; Vpopsize = 50 #种群的大小
#用遗传算法求函数最大值：
5 p9 D% |! d" H1 h, Z/ U#f(x)=10*sin(5x)+7*cos(4x) x∈[0,10]
5 k' [: p2 G$ d2 u) Q- F7 _. X
2 \: p# l1 `. [chromlength = 10 #基因片段的长度
pc = 0.6 #两个个体交叉的概率
pm = 0.001; #基因突变的概率
1 J1 i) s$ x$ \0 A2 k( A, t  y) Y7 lresults = [[]]
" l/ M- E: T" C0 g% j, {bestindividual = []
bestfit = 0
. i3 H. N! V# L! W( Rfitvalue = []
tempop = [[]]
  m% o8 y' c( \, qpop = [[0, 1, 0, 1, 0, 1, 0, 1, 0, 1]  for i in range(popsize)]
for i in range(100): #繁殖100代
        objvalue = calobjvalue(pop) #计算目标函数值
        fitvalue = calfitvalue(objvalue); #计算个体的适应值
* a/ Z+ v, P: U        [bestindividual, bestfit] = best(pop, fitvalue) #选出最好的个体和最好的函数值
2 z  }4 G7 S" j, ]3 ?        results.append([bestfit,b2d(bestindividual)]) #每次繁殖，将最好的结果记录下来
8 {' Q/ Q% t2 \8 l        selection(pop, fitvalue) #自然选择，淘汰掉一部分适应性低的个体
$ G# Z' v# {2 b: w        crossover(pop, pc) #交叉繁殖
        mutation(pop, pc) #基因突变
       
! j  m" u' g0 n
0 f2 [! I1 y* h8 Dresults.sort()       
print(results[-1]) #打印函数最大值和对应的
3 M2 X3 M! h0 |; `/ Ldef calfitvalue(objvalue):#转化为适应值，目标函数值越大越好，负值淘汰。
    fitvalue = []
    temp = 0.0
3 |! }3 Z1 v  i; U    Cmin = 0;
4 s3 @# U& x: d! H8 I/ @; N( Y    for i in range(len(objvalue)):
        if(objvalue + Cmin > 0):
$ U$ A' m: v/ V- ?            temp = Cmin + objvalue
5 s" ~; A9 r* Z8 b        else:
            temp = 0.0
% @1 o0 w  b& G- Q4 S        fitvalue.append(temp)
" `' P& _  s( ?0 ]    return fitvalue
import math
1 t2 I0 I3 e& _5 ~/ x; i
8 k4 j! K8 N. q) F. @1 Adef decodechrom(pop): #将种群的二进制基因转化为十进制（0,1023）
2 a' b  Z% Q  ^* T. c/ J    temp = [];
$ k. \5 M! [1 I    for i in range(len(pop)):
* E" U: V/ i1 k7 |* |! Q        t = 0;
2 `, h9 ~" g  B        for j in range(10):
            t += pop[j] * (math.pow(2, j))
        temp.append(t)
    return temp

def calobjvalue(pop): #计算目标函数值
! ]$ t4 U! J- y# s9 ^    temp1 = [];
1 A: p3 T9 p$ a* v) g    objvalue = [];
9 z! v5 \$ u; T5 q+ z* D    temp1 = decodechrom(pop)
    for i in range(len(temp1)):
8 A( h3 ]2 y5 u. B' ~9 G: p        x = temp1 * 10 / 1023 #（0,1023）转化为 （0,10）
8 P. r$ q7 L' B! Q( M! H/ w$ Q        objvalue.append(10 * math.sin(5 * x) + 7 * math.cos(4 * x))
    return objvalue #目标函数值objvalue[m] 与个体基因 pop[m] 对应
8 I5 g: r) n* b& \' l1 Jdef best(pop, fitvalue): #找出适应函数值中最大值，和对应的个体
- u$ r, I2 y7 Y8 \% ~% d  d        px = len(pop)
" t- |" B" ]( T' A4 A# Q) \        bestindividual = []
        bestfit = fitvalue[0]
* J+ n, h* ]9 e. I* Y        for i in range(1,px):
                if(fitvalue > bestfit):
                        bestfit = fitvalue
8 @: ~8 A- }5 ~( Q3 X                        bestindividual = pop
. N$ Q# |# c! M5 p        return [bestindividual, bestfit]
5 K0 h# b5 m, B# a; gimport random

def sum(fitvalue):
' S$ I& M* G, J; m    total = 0
    for i in range(len(fitvalue)):
        total += fitvalue
2 g0 [1 J0 i+ {* ]; x; x7 ^    return total

def cumsum(fitvalue):
/ s. Q) k; U6 T. o    for i in range(len(fitvalue)):
        t = 0;
8 G/ c$ z: x' T% T( b        j = 0;
        while(j <= i):
            t += fitvalue[j]
1 ^' m% I# u5 H% F3 R2 e            j = j + 1
8 K4 @/ J5 Q' @& G5 F- \        fitvalue = t;

def selection(pop, fitvalue): #自然选择（轮盘赌算法）
' M5 p" a$ _  T+ b) a3 V- p* d        newfitvalue = []
  X" m2 A( _1 v$ _' ?! ^7 y" Z0 @        totalfit = sum(fitvalue)
        for i in range(len(fitvalue)):
6 ^; ^4 ?% J! n; d                newfitvalue.append(fitvalue / totalfit)
        cumsum(newfitvalue)
        ms = [];
* ^' l; f7 U) a! i6 E; R, ^        poplen = len(pop)
        for i in range(poplen):
                ms.append(random.random()) #random float list ms
" I+ B, T) X+ y3 Y        ms.sort()
        fitin = 0
        newin = 0
7 G" D  b* o4 O/ z        newpop = pop
        while newin < poplen:
                if(ms[newin] < newfitvalue[fitin]):
: i- k- K/ m& D                        newpop[newin] = pop[fitin]
                        newin = newin + 1
                else:
. a' s4 X, `0 W+ y5 o  G, p                        fitin = fitin + 1
& d+ w" x0 e* O7 j/ b        pop = newpop
import random

* l. ~) J+ s% V& [def crossover(pop, pc): #个体间交叉，实现基因交换
7 J/ Z& S$ h' _0 f: m% j5 R: {    poplen = len(pop)
6 X0 r# I# {8 ]+ t; ?. }. h    for i in range(poplen - 1):
$ F. p& z/ W: Y; ]. J3 P" [# Q1 V0 w        if(random.random() < pc):
            cpoint = random.randint(0,len(pop[0]))
9 C0 C) x- h! A7 l0 k$ T: q8 ~            temp1 = []
9 d# _) d* R$ l0 i3 i0 P' P            temp2 = []
            temp1.extend(pop[0 : cpoint])
            temp1.extend(pop[i+1][cpoint : len(pop)])
2 ~" E0 T9 H5 z; e4 Z            temp2.extend(pop[i+1][0 : cpoint])
% ^) ^, ~% [9 t! @6 c" S5 C            temp2.extend(pop[cpoint : len(pop)])
7 T. \2 ~1 m" S" K7 Y' N6 a! i            pop = temp1
* ]0 g) j3 Z; r  u+ ~            pop[i+1] = temp2
import random
' s7 J7 G/ ?0 Q5 J2 t2 ~: q  v
  b9 O+ H3 U1 F. E$ Sdef mutation(pop, pm): #基因突变
    px = len(pop)
    py = len(pop[0])
1 s' e7 G  c# X+ S; w
    for i in range(px):
) R1 O) m! k4 S8 B        if(random.random() < pm):
            mpoint = random.randint(0,py-1)
' |& C" j: @9 \            if(pop[mpoint] == 1):
                pop[mpoint] = 0
8 P, @" s9 @6 ]# S+ g, Z6 A2 c& w            else:
' q. J5 {0 _+ ^, B                pop[mpoint] = 1
4 M/ k4 c' {2 s" n

————————————————
2 t% m/ k. ?# W& W( j版权声明：本文为CSDN博主「simon-zhao」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
; G( Z5 Y, C2 ?9 v8 s& C3 C原文链接：https://blog.csdn.net/u010902721/article/details/23531359

# x6 ^* j( y. l$ @& c