QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 5861|回复: 0
打印 上一主题 下一主题

python实现的遗传算法实例(一)

[复制链接]
字体大小: 正常 放大
杨利霞        

5273

主题

82

听众

17万

积分

  • TA的每日心情
    开心
    2021-8-11 17:59
  • 签到天数: 17 天

    [LV.4]偶尔看看III

    网络挑战赛参赛者

    网络挑战赛参赛者

    自我介绍
    本人女,毕业于内蒙古科技大学,担任文职专业,毕业专业英语。

    群组2018美赛大象算法课程

    群组2018美赛护航培训课程

    群组2019年 数学中国站长建

    群组2019年数据分析师课程

    群组2018年大象老师国赛优

    跳转到指定楼层
    1#
    发表于 2020-5-9 14:48 |只看该作者 |倒序浏览
    |招呼Ta 关注Ta
    python实现的遗传算法实例(一)$ F: a5 e6 h6 ]' Q5 V8 q6 J
    * I. m* M* D8 ]& e: a% i. X
    一、遗传算法介绍
    : Z  Y; r: ]- q
    % K* s* y7 Y% _3 r% Y        遗传算法是通过模拟大自然中生物进化的历程,来解决问题的。大自然中一个种群经历过若干代的自然选择后,剩下的种群必定是适应环境的。把一个问题所有的解看做一个种群,经历过若干次的自然选择以后,剩下的解中是有问题的最优解的。当然,只能说有最优解的概率很大。这里,我们用遗传算法求一个函数的最大值。9 l% u8 A! l' w9 Y! W
            f(x) = 10 * sin( 5x ) + 7 * cos( 4x ),    0 <=  x <= 10
    9 F) s: G5 @/ C  g# v5 q8 ^
    5 I7 {8 G. S' Q' h( O6 E. N6 T1、将自变量x进行编码
    1 X+ w/ V+ [, ?4 F: i7 v; u7 Z& v7 X6 l; A% p! X
          取基因片段的长度为10, 则10位二进制位可以表示的范围是0到1023。基因与自变量转变的公式是x = b2d(individual) * 10 / 1023。构造初始的种群pop。每个个体的基因初始值是[0, 1, 0, 1, 0, 1, 0, 1, 0, 1]
    0 ~9 j/ y7 d  C& x$ l% v2 z/ s- X. Z# k
    2、计算目标函数值
    6 B9 i, M( F% }9 O& a. l. W  p5 `; q5 j+ @
          根据自变量与基因的转化关系式,求出每个个体的基因对应的自变量,然后将自变量代入函数f(x),求出每个个体的目标函数值。
    0 Z- H# V% \0 ^5 A& e. N
    1 V# X+ V2 ]. B5 o( k; X. g3、适应度函数9 m+ d8 d' `# n( A. N2 h4 G

    2 v0 e) V9 S) s* z( h      适应度函数是用来评估个体适应环境的能力,是进行自然选择的依据。本题的适应度函数直接将目标函数值中的负值变成0. 因为我们求的是最大值,所以要使目标函数值是负数的个体不适应环境,使其繁殖后代的能力为0.适应度函数的作用将在自然选择中体现。
    8 o1 Y( g( X  q' D/ E- ?$ T! X! y( K' |0 F; L. g7 J- s# m" Q8 F
    4、自然选择
    # I7 v7 j6 p# Y9 y" W5 \
    ! r+ N2 q$ s/ t0 J! J自然选择的思想不再赘述,操作使用轮盘赌算法。其具体步骤:
    7 B0 H. U* z' p& e6 \& R0 f
    - E. H( a+ o& v" T假设种群中共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号个体拷贝到新种群中。自然选择的结果使种群更符合条件了。+ N* l' Y/ a4 r% D' S" }
    # I5 b% A6 f. h6 F& W* o$ h/ m! m' Q
    5、繁殖
    5 }0 Y+ {7 D$ e6 I# q8 G7 K; n- l: ]. m, C' ?1 U7 A( s6 v! n' u
    假设个体a、b的基因是
    5 K. u1 [$ N  C* A& Y: L
    + j0 B$ p# ?! g8 K2 j& j; H, Q9 }( [a = [1, 0, 0, 0, 0, 1, 1, 1, 0, 0]
    ) N8 V/ f; h" K4 d) w* i' a
    5 ?/ {' ~! _) z  y* g6 wb = [0, 0, 0, 1, 1, 0, 1, 1, 1, 1]- V: l2 o9 b" ~) V) E$ C' a
    9 Y; D9 Z+ R1 J9 _  M' Z) `
    这两个个体发生基因交换的概率pc = 0.6.如果要发生基因交换,则产生一个随机数point表示基因交换的位置,假设point = 4,则:0 u3 u# A4 m" G1 p" j& l, _
    0 n! Q' d* m; ~
    a = [1, 0, 0, 0, 0, 1, 1, 1, 0, 0]
    1 A( K% Z) V% N2 B. A
    * J  c2 u* c1 q# lb = [0, 0, 0, 1, 1, 0, 1, 1, 1, 1]
    * Y/ q5 U) O" v- A9 [+ H% g, R9 Y- m4 l: }+ ?
    交换后为:
    2 O2 e) u2 l9 Q6 ~' h2 E! [6 n; d4 ]) e8 J& B' X
    a = [1, 0, 0, 0, 1, 0, 1, 1, 1, 1]
    - Z) Q  z6 `9 e& H
    3 _$ R0 K( M# }* o' k1 f$ }- Hb = [0, 0, 0, 1, 0, 1, 1, 1, 0, 0]
    1 Q: R; w, _+ j: ^: i/ Q
    7 C& z2 i' P3 h6、突变1 I) H3 L$ t8 R5 ?" N7 g( ^5 Q

    1 A- C2 _! N: h* Z遍历每一个个体,基因的每一位发生突变(0变为1,1变为0)的概率为0.001.突变可以增加解空间
      [6 k  a1 [4 j6 n
    9 ^/ b6 Q# i" c# j( d二、代码; x( H* G$ B$ [8 u$ \
    def b2d(b): #将二进制转化为十进制 x∈[0,10]2 L' k( `& ]; A: c
            t = 09 x0 G! q% S8 @+ E2 @
            for j in range(len(b)):
    4 c* Y* U8 K5 E" a2 `                t += b[j] * (math.pow(2, j)). z9 f3 W% ~9 \) F" P. y
            t = t * 10 / 1023/ u6 _( n3 t, u' z( {% K. ~5 \
            return t7 k4 I5 R) ^, b# V. b- i) L) P0 c% j
    6 U: K8 R7 U8 J7 a7 [
    popsize = 50 #种群的大小0 h/ C1 r0 ]& B% _. {$ S) W
    #用遗传算法求函数最大值:: M" J4 B3 |: I6 p  ]& w( v' B/ y
    #f(x)=10*sin(5x)+7*cos(4x) x∈[0,10]
    - |% U, x+ ^1 f, l
    - U. r9 L) D$ C5 R( q0 F4 m- N  I5 Dchromlength = 10 #基因片段的长度8 w7 ?% |% r* ?
    pc = 0.6 #两个个体交叉的概率! Y* Y3 j  I0 B6 s. M0 S3 M
    pm = 0.001; #基因突变的概率7 ?( E" j8 K3 t* c" x! ]4 r% }
    results = [[]]
    $ Y8 g6 @1 T, C1 ^bestindividual = []
    * K, T& ?# N! L9 Ybestfit = 0
    $ J' w9 [9 U  }3 J/ i- Y# nfitvalue = []
    7 t8 n& S. P3 Ftempop = [[]]
    / p$ X- u; H  X& n* I- t( R1 d  Z' ?pop = [[0, 1, 0, 1, 0, 1, 0, 1, 0, 1]  for i in range(popsize)]
    $ ^* v' C8 ?7 P: X, C$ F5 Gfor i in range(100): #繁殖100代: O) R% p. ]7 Z, d/ z6 V2 {( F
            objvalue = calobjvalue(pop) #计算目标函数值% {2 @8 J  K: ]8 L
            fitvalue = calfitvalue(objvalue); #计算个体的适应值
      h' A0 [' r% N3 ~! C5 v( [: d1 A: V        [bestindividual, bestfit] = best(pop, fitvalue) #选出最好的个体和最好的函数值
      `5 E7 O8 y8 r: b8 L        results.append([bestfit,b2d(bestindividual)]) #每次繁殖,将最好的结果记录下来* m) s' r) D& V* W! j8 _4 x
            selection(pop, fitvalue) #自然选择,淘汰掉一部分适应性低的个体4 w( H+ ~5 y- L9 I
            crossover(pop, pc) #交叉繁殖
    1 j# e* B1 g, N3 R( y9 _& M$ A* S        mutation(pop, pc) #基因突变# {2 ^; s" V" u6 j" S9 C
            1 o9 E7 w. @9 }

    & C* |, Q0 V& n: N( @$ i9 O3 ~" hresults.sort()       
    & d7 c8 V" Z. C. o  M1 P/ Dprint(results[-1]) #打印函数最大值和对应的% h# |" w' a. \6 u
    def calfitvalue(objvalue):#转化为适应值,目标函数值越大越好,负值淘汰。( S# t1 W( f1 e, y
        fitvalue = []. C" y2 C) F; ?3 h0 {" W6 M7 U
        temp = 0.03 B3 P; w$ S9 V6 O: l  O
        Cmin = 0;
    : |5 H2 A+ G8 k; o  W% g    for i in range(len(objvalue)):! [2 r  D' N& c. M: b+ R
            if(objvalue + Cmin > 0):
    3 y3 h/ d- H) _" n; s1 X            temp = Cmin + objvalue
    - x; m/ o. f( v8 N9 u+ R0 {        else:
    * ^  S! ^, @$ U' _$ ?4 ?  i            temp = 0.00 ~4 V0 K% r9 {# z* |
            fitvalue.append(temp)4 V( N# Q- i0 F0 O. E; N
        return fitvalue
    3 `2 P! {5 R, R; x0 ]import math8 _, {  m  Q" A; H

    9 d/ D6 `% {( F- X' _# c$ c+ s* ]+ Udef decodechrom(pop): #将种群的二进制基因转化为十进制(0,1023); @9 w" U( `* l
        temp = [];
    2 d. w  P+ U- x: B+ o; l6 E    for i in range(len(pop)):
    1 ?/ N/ L2 ^/ p5 J0 M5 t, y        t = 0;
    1 c7 {* I, c: y  ?+ ?6 w* n. n' C. O9 m        for j in range(10):" E! F# }& L5 X# D
                t += pop[j] * (math.pow(2, j))( n) g  K8 W: Y' G6 d
            temp.append(t)
    1 ?" Y8 W$ Q5 _, H* ~* e    return temp! O; ^/ [& {9 g+ W/ p  w, H$ D# h8 J

    ! x, x; _# Q" R9 L2 W; h& Tdef calobjvalue(pop): #计算目标函数值9 J# G" A- }: y
        temp1 = [];5 t  F# c" r9 ?) W6 O9 \  p! V
        objvalue = [];9 ^3 {* I8 l* b. q6 b7 z
        temp1 = decodechrom(pop)' a  U! u* E+ W" Q. }: F; |
        for i in range(len(temp1)):
    ' V* X5 [! [2 a% i: S        x = temp1 * 10 / 1023 #(0,1023)转化为 (0,10)8 p# f, V4 l6 B# q! h$ g& L
            objvalue.append(10 * math.sin(5 * x) + 7 * math.cos(4 * x))& k! S6 N0 m% H+ N4 O+ c# ^! [2 C
        return objvalue #目标函数值objvalue[m] 与个体基因 pop[m] 对应 " B7 ?3 p/ Y9 _! q( o
    def best(pop, fitvalue): #找出适应函数值中最大值,和对应的个体
    ; I; D' @/ H, `/ X; L) p        px = len(pop)
    8 o  ?: f) F4 _        bestindividual = []2 f9 ]5 u4 u( Y
            bestfit = fitvalue[0]2 m' }8 k) I5 u; z9 z* H1 C
            for i in range(1,px):
    0 a$ l4 m6 s2 E( f. M8 {2 Y* N                if(fitvalue > bestfit):
    % g( w" k+ M" O5 c$ T8 a. Q                        bestfit = fitvalue
    . J; P3 d+ R/ w4 k$ g                        bestindividual = pop2 m  _* P& k7 U5 G
            return [bestindividual, bestfit]. Y% u' F9 E' k/ P/ |% Y
    import random/ w: {: _: f3 J  {0 X" V5 A
    % w7 n' Z, F: {8 \9 \
    def sum(fitvalue):3 N' }& H" |3 y/ a0 k* @! C1 b
        total = 0
    ; j2 x; E$ Q& c1 U0 I* s* f6 a& u    for i in range(len(fitvalue)):# l' `) f. S% V% D9 m
            total += fitvalue
    ' |% ?4 G3 }- K% P! I  H( C1 S    return total& `: [+ O' c4 O6 E4 i
    & x2 h1 T" @, y7 I; H6 S
    def cumsum(fitvalue):
    ) L' g4 q; h3 O3 `% c9 Q    for i in range(len(fitvalue)):0 Q) f9 O7 b; H! v- }
            t = 0;
    ) L5 u5 G5 p4 n$ h        j = 0;
    $ {0 A' ^4 N( j2 C        while(j <= i):1 q1 ^" \  z% a  a- M4 ^
                t += fitvalue[j]: B8 i* N( c/ f: d2 L& {' n7 t  Q
                j = j + 1* J. k0 q0 W( _1 t0 W# `, D2 A6 F
            fitvalue = t;
    : T! H% C; [% }, M# h# r  C/ c- R
    ; P7 W# ~: q* R8 Y2 i. c% qdef selection(pop, fitvalue): #自然选择(轮盘赌算法)
    , Y  x7 f- Q. l" c" j  J) `        newfitvalue = []
    % ^1 z: @$ ]- G0 p        totalfit = sum(fitvalue): B4 r4 Q3 B% u3 B5 {  T. g0 a1 h
            for i in range(len(fitvalue)):
    & {  t1 ^) _5 K, B' {( O                newfitvalue.append(fitvalue / totalfit)
    2 z( {4 {8 E& Z" o% A        cumsum(newfitvalue)/ n4 [6 ^. J7 V5 g- O7 a$ g
            ms = [];
    , q5 H2 w8 p2 f" N        poplen = len(pop); K: F, l8 u8 \. \
            for i in range(poplen):
      k( G. q1 [8 d: e* ]2 |  K. n                ms.append(random.random()) #random float list ms
    1 d& T; g% U4 ~2 s+ C/ _+ |5 g        ms.sort()
    & d2 v( ]6 @, [8 ?; J; S8 `0 J        fitin = 09 W7 g* u1 `* F9 ]. H9 a: O- U/ R
            newin = 06 O: h4 J$ G3 B% m$ A
            newpop = pop
    8 Z; ?* t" R; S( b. e" X        while newin < poplen:6 g0 C$ j0 a5 c2 u) @/ c
                    if(ms[newin] < newfitvalue[fitin]):" j! D' b* q: ~& `& X: F2 e
                            newpop[newin] = pop[fitin]
    - m: N' l" F1 n$ E' o2 D                        newin = newin + 13 Q  j. m: Z# h0 a% ?9 C
                    else:
    5 V% g+ s. P. y' f4 x6 B- B9 u                        fitin = fitin + 1
    ! ]% P, o# S* x: F* ]7 N' P        pop = newpop7 `  }! s) D$ m1 p/ j( w
    import random
    % `: f3 J9 z' E( ?& y: E) M0 u' q
    def crossover(pop, pc): #个体间交叉,实现基因交换
    + F& Y1 @: k  u$ ?; @    poplen = len(pop)- L9 S) e. @: H% L* x
        for i in range(poplen - 1):
    - r% ~2 _, |8 o6 q* Y        if(random.random() < pc):- \+ ]' q( B# w- X$ _' m9 l5 y0 v# K
                cpoint = random.randint(0,len(pop[0])). \5 h) h/ S5 _+ j1 V* m9 X
                temp1 = []
    * K9 z( g0 H. w( q( O% W0 w            temp2 = []; {7 k: Y; l) p% W% p5 n$ E4 L
                temp1.extend(pop[0 : cpoint])0 U* w8 ?  D) z+ I4 ~
                temp1.extend(pop[i+1][cpoint : len(pop)])0 o' b  n& m* b+ H+ n/ f6 N2 s
                temp2.extend(pop[i+1][0 : cpoint])4 [% I! ]* ]8 J) l9 D1 |
                temp2.extend(pop[cpoint : len(pop)])
    5 Q$ x- b# q7 q/ N            pop = temp1
    + r4 d+ J! F% C! l* ~; [            pop[i+1] = temp24 s8 |' s- M  c$ y
    import random% y7 \( T% |, v# [2 J
    # `" j; D/ C% `3 L' @! V
    def mutation(pop, pm): #基因突变
    0 i% s' a2 W, ^    px = len(pop)- P( q4 Y2 H+ J5 v) ^) G( O1 F
        py = len(pop[0])
    $ f9 C- w0 S. S4 B+ a$ R8 N% M/ H) L  C: M% @/ I% B  o$ ~3 t3 A
        for i in range(px):
    " J2 c9 l! z6 b- X        if(random.random() < pm):- ^$ K: B4 z, j  F
                mpoint = random.randint(0,py-1)
    7 g$ h" S* i$ G2 H& a7 N8 h# P            if(pop[mpoint] == 1):
    . G5 U1 z% j3 w$ E* ]                pop[mpoint] = 0* ~! H7 u6 d1 }/ _9 ]
                else:
    4 h5 m, A5 M; p9 I2 L                pop[mpoint] = 1
    # e/ D5 s- P$ f+ r- J3 {# a4 P2 k1 A

    7 H! o: }/ O. z) M5 b+ }————————————————
    $ S# }/ T, O# n6 |$ ?, a版权声明:本文为CSDN博主「simon-zhao」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
    6 i+ K; ~. b, V# P8 k! o, h+ b2 ^原文链接:https://blog.csdn.net/u010902721/article/details/23531359
    8 D) R0 K& i0 m  @* R2 @. {2 l4 Y# X4 C  o
    1 S  I5 Q" ?4 |( f) L% o
    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2026-6-3 10:11 , Processed in 0.530456 second(s), 51 queries .

    回顶部