QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 5833|回复: 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实现的遗传算法实例(一)6 p( X, k6 e: y, @4 q* B) Q
    2 u( H7 q- c% _/ ?: T! B* e% x
    一、遗传算法介绍
    : P1 J, c, ~# z# Z* L, x6 F% ]7 d1 X/ j5 k' Q' U; S+ k
            遗传算法是通过模拟大自然中生物进化的历程,来解决问题的。大自然中一个种群经历过若干代的自然选择后,剩下的种群必定是适应环境的。把一个问题所有的解看做一个种群,经历过若干次的自然选择以后,剩下的解中是有问题的最优解的。当然,只能说有最优解的概率很大。这里,我们用遗传算法求一个函数的最大值。
    $ a. Z3 g- z! y+ I        f(x) = 10 * sin( 5x ) + 7 * cos( 4x ),    0 <=  x <= 10
    + _! A1 \$ v9 w1 P0 d5 Y( n0 N3 O& F& K& w+ l
    1、将自变量x进行编码2 |! _% ~, \! ^% b5 u- t: Q5 S

    1 t$ |  z5 B$ q0 Y6 h0 V      取基因片段的长度为10, 则10位二进制位可以表示的范围是0到1023。基因与自变量转变的公式是x = b2d(individual) * 10 / 1023。构造初始的种群pop。每个个体的基因初始值是[0, 1, 0, 1, 0, 1, 0, 1, 0, 1]
    3 ]6 h  K/ N% |4 w0 j( O5 t2 z9 Q4 U6 h+ B, s9 A
    2、计算目标函数值
    2 {, ^  g  i4 h1 e3 Y8 t3 }8 V+ w* H- s9 c- h2 y. a, K
          根据自变量与基因的转化关系式,求出每个个体的基因对应的自变量,然后将自变量代入函数f(x),求出每个个体的目标函数值。
    & r2 C7 t9 T6 [, m* v; U( Q  u: _. Q" S: _4 \
    3、适应度函数
    / K! D/ {: }! B) Z' {* t" ?% r, R& S3 U! P9 I$ x
          适应度函数是用来评估个体适应环境的能力,是进行自然选择的依据。本题的适应度函数直接将目标函数值中的负值变成0. 因为我们求的是最大值,所以要使目标函数值是负数的个体不适应环境,使其繁殖后代的能力为0.适应度函数的作用将在自然选择中体现。3 ~. T! E9 A. j0 n4 v
    ) L! M: `, U8 i/ c% p. a
    4、自然选择
    8 o+ [/ A  N: \* G: S$ I* A+ c  r4 I  Z$ ~
    自然选择的思想不再赘述,操作使用轮盘赌算法。其具体步骤:; Q5 H$ g- k$ S' Z4 w

    - d0 G3 x4 E9 U假设种群中共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号个体拷贝到新种群中。自然选择的结果使种群更符合条件了。0 P. O1 X6 \) D+ T& J! I9 w

    9 ^! Y) E3 M( Q; T+ D5、繁殖
    5 X! u& r# \: ~
    5 f. i; F& X) H假设个体a、b的基因是
    * ]% N4 `2 D& t$ @
    , c' ?. s: F; m) J5 c5 ^a = [1, 0, 0, 0, 0, 1, 1, 1, 0, 0]
    1 z! H/ {/ |, W
    % o7 `5 j& r$ |& @' Wb = [0, 0, 0, 1, 1, 0, 1, 1, 1, 1]
    / G- t+ b- y- q( B( v3 \5 R% n0 O$ i/ {+ s6 R
    这两个个体发生基因交换的概率pc = 0.6.如果要发生基因交换,则产生一个随机数point表示基因交换的位置,假设point = 4,则:$ h9 V, Y! I' O1 V9 c! y

    ' k( E7 Y( A& n; p! {a = [1, 0, 0, 0, 0, 1, 1, 1, 0, 0]
    ! ]* L7 Q; p* `
    $ Q0 H( ]6 m; G* D5 g' Gb = [0, 0, 0, 1, 1, 0, 1, 1, 1, 1]
    8 P: f& U" g" g3 ?8 u& R! [' q* l6 L8 V0 }. s+ d: T
    交换后为:
    : L! G7 G) b- C# O$ t/ N% {% y8 @* O" X6 f. Y7 G/ o# K
    a = [1, 0, 0, 0, 1, 0, 1, 1, 1, 1]6 S3 o, X  K5 ?

    4 d! O7 r, f9 @3 l% O6 x' {6 O0 _b = [0, 0, 0, 1, 0, 1, 1, 1, 0, 0]! b- U/ P  c3 {3 U' h

    / r6 [" {) Y) D% V! v6、突变
    ; Q" G6 N- t2 t1 K4 I& C" H9 Q
    ' |  m8 L/ L1 b- F* d0 y. [遍历每一个个体,基因的每一位发生突变(0变为1,1变为0)的概率为0.001.突变可以增加解空间
    9 S; c. ]6 F7 A% [
    " O) w3 k, [6 v1 z& |8 c二、代码
    # ?7 h+ F/ c# f' a0 k: s. edef b2d(b): #将二进制转化为十进制 x∈[0,10]
    3 f/ z/ S. W9 x7 [% o        t = 04 r- R) E. M! j4 V
            for j in range(len(b)):/ e: W" w# `' P
                    t += b[j] * (math.pow(2, j))% p: w2 o* L& ^6 D/ u
            t = t * 10 / 1023
    $ H3 o- o! ]( O8 L2 ]4 x. Z% z        return t* D$ o, S1 N1 U/ T) p

    # {( L! L* t. B+ L5 m6 Bpopsize = 50 #种群的大小; V# R6 u/ b+ l5 M
    #用遗传算法求函数最大值:
    8 M$ a! ]* Z- j8 `0 {#f(x)=10*sin(5x)+7*cos(4x) x∈[0,10]
    # p# g) Z9 l/ U) E% I* ?& L8 l! ^
    chromlength = 10 #基因片段的长度
    9 d3 F9 _' s2 k3 d. S; w* rpc = 0.6 #两个个体交叉的概率
    % n& o6 U: [' }" Npm = 0.001; #基因突变的概率9 b" u) ?+ f8 g" p  t
    results = [[]]
    " U& B8 W4 `3 `' `# ~bestindividual = []
    + Y/ A6 p; S6 F2 ?. \bestfit = 0
    2 \9 y8 H0 k1 yfitvalue = []
    " r# u% {: @) Ctempop = [[]]6 E5 l- ?: M  C
    pop = [[0, 1, 0, 1, 0, 1, 0, 1, 0, 1]  for i in range(popsize)]; Z) s( E/ }6 _$ D0 M, j' ^
    for i in range(100): #繁殖100代
    - B! Q9 h7 t0 u) |; `        objvalue = calobjvalue(pop) #计算目标函数值+ Y' c6 `2 N$ p- c$ k7 P
            fitvalue = calfitvalue(objvalue); #计算个体的适应值" D+ L' C$ U+ S1 V* g
            [bestindividual, bestfit] = best(pop, fitvalue) #选出最好的个体和最好的函数值
    7 {( a. i4 m7 d6 N( k; z( t  @        results.append([bestfit,b2d(bestindividual)]) #每次繁殖,将最好的结果记录下来
    ( t3 }+ h2 r4 {$ s        selection(pop, fitvalue) #自然选择,淘汰掉一部分适应性低的个体. ]# ?/ p9 I  u
            crossover(pop, pc) #交叉繁殖; G; F, q( s5 ?0 F) u7 b
            mutation(pop, pc) #基因突变
    & G& d. q- ~. p, i5 e       
    8 f- O8 c3 k) M% ?- \; Q% t' d9 o. K. m2 i
    results.sort()       
    7 r! o5 B" d3 \: mprint(results[-1]) #打印函数最大值和对应的1 t" C( A. W1 Z& `
    def calfitvalue(objvalue):#转化为适应值,目标函数值越大越好,负值淘汰。, {4 E3 }- E/ x# c) L0 K5 ?9 j' @
        fitvalue = []
    1 k8 s" E2 E" e4 ?    temp = 0.00 D, y7 @0 S8 a
        Cmin = 0;
    7 V7 K3 m5 ^% L1 r9 e5 L2 Q, Y    for i in range(len(objvalue)):. I  ?* K# U! j, T
            if(objvalue + Cmin > 0):
    ' p! s3 W1 r6 F: @( n            temp = Cmin + objvalue
    5 v" H/ J0 D+ U% Q        else:
    % o' S' S: d* u5 ~' W/ \            temp = 0.0
    $ P$ k5 x* }" y5 P        fitvalue.append(temp). e  m; ]7 U8 I% c  I& s/ s
        return fitvalue
    ( }% f! v0 v8 ]. s( ^import math
    2 v6 _8 K* \; R' d/ M4 N) V
    7 Z1 p7 v! P/ y3 `4 O* `6 r# [def decodechrom(pop): #将种群的二进制基因转化为十进制(0,1023)
    ; ~. c5 L6 }  S* `0 V    temp = [];
    : [9 H3 t8 T* {  m- z- T    for i in range(len(pop)):
    : k4 f* f& q" d5 e1 q        t = 0;3 M9 P6 ~( |- `$ k+ d
            for j in range(10):% F0 T$ `  C1 y) j4 z
                t += pop[j] * (math.pow(2, j))! E$ M. L/ ^* _) q, V
            temp.append(t)
    * I# q; K+ V% m- w: U$ o& l    return temp
    2 _6 u  a! }5 V! N( N5 E7 f/ T: R* A% ?7 z% a$ E. S
    def calobjvalue(pop): #计算目标函数值
    1 ?( h$ Q1 {; m) v; v  d0 z    temp1 = [];
    ' x/ m$ C5 J2 ^. r  y( l7 n( ~; H    objvalue = [];& x7 o7 ~& b: r4 L4 d3 x% Q
        temp1 = decodechrom(pop)
    - C# y- s6 c$ G6 E    for i in range(len(temp1)):
    9 n" ?9 D& f, ]0 Z7 w' }/ L5 _& J        x = temp1 * 10 / 1023 #(0,1023)转化为 (0,10)
    , \9 M7 }5 d) Y" ^/ l4 L3 p7 ]        objvalue.append(10 * math.sin(5 * x) + 7 * math.cos(4 * x))( O) p9 {/ [' W" ^0 B; b6 t
        return objvalue #目标函数值objvalue[m] 与个体基因 pop[m] 对应
    8 x* x7 e: Y5 F; w) D" f% C* }def best(pop, fitvalue): #找出适应函数值中最大值,和对应的个体
    + Z0 q& ]! B& r1 |6 w  \        px = len(pop)
    9 {  M  j6 x/ a        bestindividual = []" E' ~8 m. ?8 l0 D- D$ W
            bestfit = fitvalue[0]$ M' x3 j6 o- G. ^6 T; \
            for i in range(1,px):0 P( p6 ~  U0 g: N* T, y
                    if(fitvalue > bestfit):
    ! C' \8 }6 u3 w/ d% _# T                        bestfit = fitvalue4 s) A) v4 Z2 _: w
                            bestindividual = pop; f+ j+ _+ E; N1 \9 U0 p
            return [bestindividual, bestfit]
    ( j4 e& X" i) g+ Fimport random
    , B: z8 G8 ]. U) l( `* ~  {9 z
    3 H5 o3 g. Z& \) V8 \9 M% Cdef sum(fitvalue):2 z. w8 n. R2 q8 q( Q7 K8 C* b
        total = 0
    . k$ B  Q& _' }    for i in range(len(fitvalue)):
    : c( @1 W& \$ N2 H4 h        total += fitvalue9 K. P2 e# d4 m) L* T
        return total6 f* J8 B3 @# c$ \6 |

    ( ]# y3 ?. K9 S8 l3 H* D4 Cdef cumsum(fitvalue):# v* X7 N4 s! M$ g& z+ B
        for i in range(len(fitvalue)):6 U$ S9 R; v  L4 a, i. S' C
            t = 0;( i$ R0 V( j/ p% i
            j = 0;
    2 u; o$ g+ z# g! _2 z) L% s7 b        while(j <= i):9 a8 s, j; i+ x4 O7 }
                t += fitvalue[j]+ M& h* M9 S6 d4 N, [
                j = j + 15 ?8 @4 [; M0 [6 t" [
            fitvalue = t;
    - F# ?' f! |% L2 }5 Y$ J! y! ?
    / {" W( x  O$ _/ sdef selection(pop, fitvalue): #自然选择(轮盘赌算法)
    ' Y- f: o( e5 ^5 G        newfitvalue = []
    " L0 T! ^% _% j; g  ~+ b        totalfit = sum(fitvalue)) Q( M' D' ~4 n% l; _9 S, |8 k* Z9 m/ i
            for i in range(len(fitvalue)):0 N7 \0 A7 l! b9 A
                    newfitvalue.append(fitvalue / totalfit)  l2 S+ ^' y; i6 D6 N
            cumsum(newfitvalue)/ Q7 P( n) i! {& k- z; }
            ms = [];
    9 O. i" {& t, _  D2 p' B2 L" y        poplen = len(pop)
    0 k) M3 \; E. D7 B! q# S        for i in range(poplen):/ Z5 ]: P3 Y( o1 K9 s
                    ms.append(random.random()) #random float list ms7 ~) J  `4 S: b  J4 W
            ms.sort()
    1 a6 T  ~% ?9 N# p: C) u        fitin = 0+ x  E" I2 s3 }) t1 v$ L
            newin = 03 a0 Q1 R4 F2 @$ m2 w9 E
            newpop = pop
    3 M; P: z: f1 L        while newin < poplen:
    & X- p& ~7 M( G/ x' {% O# @                if(ms[newin] < newfitvalue[fitin]):" U0 G- Y6 S# ^$ |6 ^- D- q
                            newpop[newin] = pop[fitin]3 U) i' T7 K# r2 l# \. S
                            newin = newin + 1
    . N6 ^8 b% W( I# R                else:
    0 W2 j3 i8 _5 a. F" m) \                        fitin = fitin + 11 |; {- K; n1 l5 r
            pop = newpop6 Y) L/ I+ Z4 b' r4 F" f+ H) t& r
    import random
    9 |& {* u- F" A6 v2 d% q* Y4 J2 d! h9 ^" G+ v
    def crossover(pop, pc): #个体间交叉,实现基因交换
    # e: U; S0 G: [. t; j    poplen = len(pop)0 x: |* u9 ?! e: k" [5 m! V; u
        for i in range(poplen - 1):6 D6 l7 x. i' ?! W5 v. @
            if(random.random() < pc):8 i3 M6 h0 f: ^" Q$ F
                cpoint = random.randint(0,len(pop[0]))
    & V# F. h/ l2 w; {- B            temp1 = []
    $ A% |! ~" V% @- ^! y3 r8 v            temp2 = []" n1 o1 X5 {+ m
                temp1.extend(pop[0 : cpoint])
    7 R3 N/ ~; _- ]) K5 S0 z            temp1.extend(pop[i+1][cpoint : len(pop)])
    / \/ }+ P) M" n$ C" b9 l, t. j            temp2.extend(pop[i+1][0 : cpoint])' Y: M# {3 c9 n; Q3 D
                temp2.extend(pop[cpoint : len(pop)])& w5 o8 i( J3 g) H8 U! {! `9 L
                pop = temp14 a0 g6 F. v* u3 e) Y
                pop[i+1] = temp2
    6 {. ?% N0 k- X1 W1 i4 E1 rimport random
    5 i/ w3 \/ W* ]/ [  J) A3 J3 m" }" _/ E6 A3 }
    def mutation(pop, pm): #基因突变5 F. M5 {  l6 b7 U+ W0 e  u% E$ I
        px = len(pop)5 R- ]! @/ j6 I" M4 R6 t5 H
        py = len(pop[0])8 {6 {* ?7 M. t
    : R- o0 G4 l; X
        for i in range(px):
    # v6 Y1 V* @% X& ~" {        if(random.random() < pm):$ s* w2 \9 g8 Q3 n% [0 d/ s+ m" a
                mpoint = random.randint(0,py-1)0 e/ b& M) O+ e: q2 U/ V
                if(pop[mpoint] == 1):
    5 A0 H( i. |0 n# ^- R  @! y                pop[mpoint] = 0
    1 m- I; b/ |0 b) z& e            else:! Z3 K3 U* Q3 @( Y
                    pop[mpoint] = 1. B$ J6 x8 \5 ~( E! ]6 `' Y$ P

    & W% L6 w/ z3 J( I/ l2 `( ^$ K! K4 e
    ————————————————
      W! v. @4 v; P7 V9 v2 O版权声明:本文为CSDN博主「simon-zhao」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。! m3 t0 c9 r2 u& }5 C4 Y
    原文链接:https://blog.csdn.net/u010902721/article/details/235313595 g! I/ A1 b* m+ r3 A3 t
    ! m# a$ i5 O7 X7 @6 f2 a

    , S& h& D3 ^5 A* Y! j, A) I1 v
    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-4-21 06:06 , Processed in 0.382482 second(s), 51 queries .

    回顶部