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

杨利霞

python实现的遗传算法实例（一）
' O& S' K9 Y; i' O
一、遗传算法介绍

2 m, K  F$ m$ f  ~; S        遗传算法是通过模拟大自然中生物进化的历程，来解决问题的。大自然中一个种群经历过若干代的自然选择后，剩下的种群必定是适应环境的。把一个问题所有的解看做一个种群，经历过若干次的自然选择以后，剩下的解中是有问题的最优解的。当然，只能说有最优解的概率很大。这里，我们用遗传算法求一个函数的最大值。
! C/ }$ t, Y) `8 {/ T        f(x) = 10 * sin( 5x ) + 7 * cos( 4x ),    0 <=  x <= 10

1、将自变量x进行编码
0 {0 I5 E: L0 [% `  Q/ X* K+ {2 U
  S4 c# Z& t! R# U% v      取基因片段的长度为10, 则10位二进制位可以表示的范围是0到1023。基因与自变量转变的公式是x = b2d(individual) * 10 / 1023。构造初始的种群pop。每个个体的基因初始值是[0, 1, 0, 1, 0, 1, 0, 1, 0, 1]
+ l1 B# J4 J" c; \5 p+ }
& N  }/ G4 F% f2、计算目标函数值
8 v1 B& ]' k2 x: t
; ^3 j+ W/ o; [      根据自变量与基因的转化关系式，求出每个个体的基因对应的自变量，然后将自变量代入函数f（x），求出每个个体的目标函数值。
2 e. V3 j3 \7 S% `5 O" A3 B
$ b$ k) H! {" K, c7 Z3 Y3、适应度函数

; l8 u! m, ^- B      适应度函数是用来评估个体适应环境的能力，是进行自然选择的依据。本题的适应度函数直接将目标函数值中的负值变成0. 因为我们求的是最大值，所以要使目标函数值是负数的个体不适应环境，使其繁殖后代的能力为0.适应度函数的作用将在自然选择中体现。
0 M  G5 ^" n# K# i* X
4、自然选择
8 Q) u. Y) C' c3 I
) \2 N: C$ D; y' ^' P$ z自然选择的思想不再赘述，操作使用轮盘赌算法。其具体步骤：
5 k7 b; t5 e9 ?' _8 b9 S) ~
假设种群中共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号个体拷贝到新种群中。自然选择的结果使种群更符合条件了。
$ d& k- k# V6 `
/ l% Q7 I, {1 Q5 F5、繁殖

假设个体a、b的基因是
) v  m# }' f1 s7 n  d
a = [1, 0, 0, 0, 0, 1, 1, 1, 0, 0]

$ ~3 ]+ r- Z8 u6 A( e, Bb = [0, 0, 0, 1, 1, 0, 1, 1, 1, 1]

3 l- Y  q5 p9 Q. f# n" s这两个个体发生基因交换的概率pc = 0.6.如果要发生基因交换，则产生一个随机数point表示基因交换的位置，假设point = 4,则：

a = [1, 0, 0, 0, 0, 1, 1, 1, 0, 0]

8 b5 y0 r9 F  N/ {$ n) Sb = [0, 0, 0, 1, 1, 0, 1, 1, 1, 1]
# {5 @3 |: f7 Z) m# t" F4 }! I
交换后为：

a = [1, 0, 0, 0, 1, 0, 1, 1, 1, 1]

b = [0, 0, 0, 1, 0, 1, 1, 1, 0, 0]
  a5 k" W9 G; M0 D3 X. |1 N
* W: {; i& X! y& Y0 O: \6、突变
3 \+ z8 h/ z4 _% d, C! Q( n% v
遍历每一个个体，基因的每一位发生突变（0变为1,1变为0）的概率为0.001.突变可以增加解空间

二、代码
9 p; q) h3 \/ ^' C* S' udef b2d(b): #将二进制转化为十进制 x∈[0,10]
        t = 0
        for j in range(len(b)):
                t += b[j] * (math.pow(2, j))
2 F# z; \8 ~  U0 r2 V; r0 _0 t8 I        t = t * 10 / 1023
& ?+ P" k3 H6 c        return t
, U. l) o- p9 z* t' g+ y7 x2 h
popsize = 50 #种群的大小
: |. j' X4 a; ~7 f#用遗传算法求函数最大值：
#f(x)=10*sin(5x)+7*cos(4x) x∈[0,10]

! H0 W. u. ?* l( N# W/ q( F0 n2 kchromlength = 10 #基因片段的长度
+ t0 l6 P( S6 X' e+ Q$ J3 j1 ~pc = 0.6 #两个个体交叉的概率
pm = 0.001; #基因突变的概率
results = [[]]
1 ]0 o: \9 E4 Z/ j! T& zbestindividual = []
- C) F6 \+ Q/ y' E9 y: i8 Cbestfit = 0
fitvalue = []
tempop = [[]]
: j! s7 R1 t7 [. Z3 Upop = [[0, 1, 0, 1, 0, 1, 0, 1, 0, 1]  for i in range(popsize)]
for i in range(100): #繁殖100代
        objvalue = calobjvalue(pop) #计算目标函数值
# ~5 [# C5 @0 w. W% b5 ~( A0 f        fitvalue = calfitvalue(objvalue); #计算个体的适应值
2 J/ p# L; R6 B, j        [bestindividual, bestfit] = best(pop, fitvalue) #选出最好的个体和最好的函数值
) B! w& O8 z( m: @( X) b. m# n6 z        results.append([bestfit,b2d(bestindividual)]) #每次繁殖，将最好的结果记录下来
        selection(pop, fitvalue) #自然选择，淘汰掉一部分适应性低的个体
        crossover(pop, pc) #交叉繁殖
9 P9 m+ X" r# E! _3 q% p. e8 r: q        mutation(pop, pc) #基因突变
       

results.sort()       
print(results[-1]) #打印函数最大值和对应的
% d% ?* K* f0 A2 odef calfitvalue(objvalue):#转化为适应值，目标函数值越大越好，负值淘汰。
    fitvalue = []
    temp = 0.0
    Cmin = 0;
    for i in range(len(objvalue)):
        if(objvalue + Cmin > 0):
            temp = Cmin + objvalue
        else:
            temp = 0.0
, T1 q1 o* ]7 b8 o+ l( u        fitvalue.append(temp)
    return fitvalue
, n% \" ?. `( W& simport math
. U) S9 ?$ f7 \* d6 m
( I( K" [8 u% [7 n3 Jdef decodechrom(pop): #将种群的二进制基因转化为十进制（0,1023）
! O6 ~/ g- a( ?. k    temp = [];
    for i in range(len(pop)):
        t = 0;
7 b0 ^/ a( V* _# r        for j in range(10):
            t += pop[j] * (math.pow(2, j))
        temp.append(t)
" x! n( D5 }3 @: t$ C  i, _    return temp
3 `& W% q% d9 k* A
def calobjvalue(pop): #计算目标函数值
2 p& @, }% _8 S. o    temp1 = [];
    objvalue = [];
    temp1 = decodechrom(pop)
    for i in range(len(temp1)):
$ c. f# A& b$ e* f" S        x = temp1 * 10 / 1023 #（0,1023）转化为 （0,10）
, s  }6 C* c' F3 _. [6 y  a! u1 }        objvalue.append(10 * math.sin(5 * x) + 7 * math.cos(4 * x))
    return objvalue #目标函数值objvalue[m] 与个体基因 pop[m] 对应
def best(pop, fitvalue): #找出适应函数值中最大值，和对应的个体
        px = len(pop)
        bestindividual = []
        bestfit = fitvalue[0]
+ v5 ]5 F% T0 C  |2 I        for i in range(1,px):
                if(fitvalue > bestfit):
                        bestfit = fitvalue
& t: H% P4 w4 l/ S' `7 M( N                        bestindividual = pop
3 k$ h1 f1 N4 e* B0 b( j, V        return [bestindividual, bestfit]
import random

+ x2 |. A' A, O, jdef sum(fitvalue):
    total = 0
    for i in range(len(fitvalue)):
  M1 ^9 x8 q: ]1 k0 r3 K+ Y" Q+ T        total += fitvalue
    return total
( S+ Y6 n" F: |
( L" [) A7 V1 L  `" M# hdef cumsum(fitvalue):
    for i in range(len(fitvalue)):
- f5 c2 c( ^& q; u- J/ ~        t = 0;
6 @/ f7 O, F2 {" Z  M& U        j = 0;
        while(j <= i):
+ c( j5 C+ r/ z1 w: l0 b' w' D            t += fitvalue[j]
2 R- Z% i8 r5 V# m/ Q& |            j = j + 1
        fitvalue = t;

def selection(pop, fitvalue): #自然选择（轮盘赌算法）
3 G; P, C+ z& y9 u# `        newfitvalue = []
        totalfit = sum(fitvalue)
+ ]6 K& \3 i2 B6 `" @' Z        for i in range(len(fitvalue)):
7 }+ z9 P& k3 n                newfitvalue.append(fitvalue / totalfit)
        cumsum(newfitvalue)
        ms = [];
( p9 J& {( }4 A        poplen = len(pop)
- x  P1 Z+ N, ^0 [# [        for i in range(poplen):
                ms.append(random.random()) #random float list ms
. @( i6 b6 V1 _! i4 d. q        ms.sort()
        fitin = 0
& x7 H5 Y, d0 Q/ o- ~* E        newin = 0
$ e. e3 Y1 R: P* l' g/ O2 U3 r$ |        newpop = pop
/ p# l* s1 r# C. l9 v        while newin < poplen:
                if(ms[newin] < newfitvalue[fitin]):
                        newpop[newin] = pop[fitin]
                        newin = newin + 1
7 _: P/ e9 w. F" ^3 d                else:
4 U! c' M4 V' i% e                        fitin = fitin + 1
1 b2 s4 R, F% O7 H$ r; T: ~+ w2 x        pop = newpop
import random

  l7 r( U6 t4 w# d3 w' d- C8 m8 udef crossover(pop, pc): #个体间交叉，实现基因交换
* ~2 p: g9 j- I* X+ x+ ]% [4 S    poplen = len(pop)
    for i in range(poplen - 1):
        if(random.random() < pc):
            cpoint = random.randint(0,len(pop[0]))
# C- J" E" a3 N$ K2 B1 ~            temp1 = []
( i! V1 O* g: Q: Y3 N% i0 F8 Z            temp2 = []
: l+ `  s8 r4 l# Z/ f* C, H            temp1.extend(pop[0 : cpoint])
* F' s# t) ?3 f  L+ J: L9 w            temp1.extend(pop[i+1][cpoint : len(pop)])
' n! i7 a8 S- s. C; q* s* @            temp2.extend(pop[i+1][0 : cpoint])
            temp2.extend(pop[cpoint : len(pop)])
0 @! H/ i- p! A! M, d' o% s& }            pop = temp1
            pop[i+1] = temp2
+ [9 B9 W7 V7 x5 M( o2 x. w1 kimport random

: w2 s" E3 h) Q1 I9 k; Rdef mutation(pop, pm): #基因突变
" s; v. w' E5 A; U+ a    px = len(pop)
' |- n; B: @' v5 R; }* V    py = len(pop[0])
* Y$ ?: U, m. a& U3 N
$ y* ^' I7 n2 O6 O. {- ]    for i in range(px):
        if(random.random() < pm):
( O/ h2 W- V/ R: `: m            mpoint = random.randint(0,py-1)
* _! R/ y: Q6 j5 s/ E            if(pop[mpoint] == 1):
                pop[mpoint] = 0
            else:
" }; B3 M/ u! r& ?8 \8 s                pop[mpoint] = 1

  s2 b! U  d. ~- e
& n2 D3 T, o. L' N% j————————————————
4 n6 B& W: {, A+ m: F" A版权声明：本文为CSDN博主「simon-zhao」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
3 @) Y  x* P& d) ~6 }1 p; C原文链接：https://blog.csdn.net/u010902721/article/details/23531359
1 s& g" H0 ]- W5 O

, R: d# ?/ V2 f$ n