数学建模社区-数学中国

标题: python实现的遗传算法实例（一） [打印本页]

---

作者: 杨利霞    时间: 2020-5-9 14:48
标题: python实现的遗传算法实例（一）
python实现的遗传算法实例（一）
$ ]# ^! U. d- e
一、遗传算法介绍
; V0 @# W- A, Q( @# M/ K* C4 u
' I! s: D3 |1 g) Z% e        遗传算法是通过模拟大自然中生物进化的历程，来解决问题的。大自然中一个种群经历过若干代的自然选择后，剩下的种群必定是适应环境的。把一个问题所有的解看做一个种群，经历过若干次的自然选择以后，剩下的解中是有问题的最优解的。当然，只能说有最优解的概率很大。这里，我们用遗传算法求一个函数的最大值。
        f(x) = 10 * sin( 5x ) + 7 * cos( 4x ),    0 <=  x <= 10
8 W8 T% b. d9 @  ?: s9 R* v
: [' O% c. H2 a. t2 }' ^1、将自变量x进行编码
" u, e# S$ H# n
      取基因片段的长度为10, 则10位二进制位可以表示的范围是0到1023。基因与自变量转变的公式是x = b2d(individual) * 10 / 1023。构造初始的种群pop。每个个体的基因初始值是[0, 1, 0, 1, 0, 1, 0, 1, 0, 1]
& l* q, @; {, W4 y/ @# u% |, M
. B+ B! x0 F# o# ?% C7 F! r2、计算目标函数值
6 W+ }$ j2 B7 ]
      根据自变量与基因的转化关系式，求出每个个体的基因对应的自变量，然后将自变量代入函数f（x），求出每个个体的目标函数值。
0 P' {% G, J/ n% L4 m# k! n3 C. o
# a, W9 @8 Z9 P3、适应度函数
  g& i; a$ G( {5 @* X
8 G$ S' [$ ~# j( b3 ?% t' j8 k' P      适应度函数是用来评估个体适应环境的能力，是进行自然选择的依据。本题的适应度函数直接将目标函数值中的负值变成0. 因为我们求的是最大值，所以要使目标函数值是负数的个体不适应环境，使其繁殖后代的能力为0.适应度函数的作用将在自然选择中体现。
& X5 R% D4 ]2 F3 D( |7 G
4、自然选择
1 d+ W/ X  {: o! S+ {3 i
( }  R: q# q. v- _1 o自然选择的思想不再赘述，操作使用轮盘赌算法。其具体步骤：

$ [: q$ i" q) ~3 k0 \7 Z假设种群中共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号个体拷贝到新种群中。自然选择的结果使种群更符合条件了。
" w2 q) |" Q! z
; n% ]* M' N& A4 m- A) V% S' v5、繁殖

, P# d* T7 T. K! N2 G/ _假设个体a、b的基因是

a = [1, 0, 0, 0, 0, 1, 1, 1, 0, 0]
$ u; o! u; U8 G' \/ v. `: D/ {2 j
7 _5 m3 m0 o& N5 i: w$ M; y, Rb = [0, 0, 0, 1, 1, 0, 1, 1, 1, 1]
7 c3 }; ]8 N$ j# g- r) q
这两个个体发生基因交换的概率pc = 0.6.如果要发生基因交换，则产生一个随机数point表示基因交换的位置，假设point = 4,则：
6 r6 u7 E: c* \' E. N# r
9 T* M0 H2 j+ A8 q' p9 \a = [1, 0, 0, 0, 0, 1, 1, 1, 0, 0]
% S/ M  d) j' E9 u9 J$ R
, }1 X0 N: R. Eb = [0, 0, 0, 1, 1, 0, 1, 1, 1, 1]

+ C4 P8 S* S5 B/ O* ~7 D9 ]交换后为：
3 V  ]6 u9 b+ [8 n( d5 J3 }' h
a = [1, 0, 0, 0, 1, 0, 1, 1, 1, 1]
; G( c' v- g3 |' T1 j$ ^
b = [0, 0, 0, 1, 0, 1, 1, 1, 0, 0]

% m" E% E1 f% E$ t" ~6、突变

遍历每一个个体，基因的每一位发生突变（0变为1,1变为0）的概率为0.001.突变可以增加解空间
. r" b% h4 I! s$ ]9 u. q
7 J( i) i) x  P- r8 }- s: E4 Q二、代码
1 R/ r+ ?% ]% N/ fdef b2d(b): #将二进制转化为十进制 x∈[0,10]
% H5 K4 s1 M" R8 f8 k. f        t = 0
        for j in range(len(b)):
, d) S) Z" J4 V7 J' Z5 k" ]                t += b[j] * (math.pow(2, j))
- c3 B; B, [: F6 z+ S( ~( t# ^        t = t * 10 / 1023
        return t
" p+ h0 J  z9 {+ L, \9 Q
popsize = 50 #种群的大小
#用遗传算法求函数最大值：
#f(x)=10*sin(5x)+7*cos(4x) x∈[0,10]
& |/ f4 p: T6 Y' [0 v
chromlength = 10 #基因片段的长度
pc = 0.6 #两个个体交叉的概率
pm = 0.001; #基因突变的概率
3 t% ~$ v6 O1 vresults = [[]]
, c8 l, f  G  z& d. \bestindividual = []
. k; J3 i2 G1 y4 R' abestfit = 0
fitvalue = []
tempop = [[]]
pop = [[0, 1, 0, 1, 0, 1, 0, 1, 0, 1]  for i in range(popsize)]
6 J9 A/ s5 Y5 ?  sfor i in range(100): #繁殖100代
        objvalue = calobjvalue(pop) #计算目标函数值
        fitvalue = calfitvalue(objvalue); #计算个体的适应值
        [bestindividual, bestfit] = best(pop, fitvalue) #选出最好的个体和最好的函数值
: o2 ~" G2 s/ u& S        results.append([bestfit,b2d(bestindividual)]) #每次繁殖，将最好的结果记录下来
        selection(pop, fitvalue) #自然选择，淘汰掉一部分适应性低的个体
        crossover(pop, pc) #交叉繁殖
        mutation(pop, pc) #基因突变
       
) d+ d* Y  Q8 B) T* O: R4 z# H. S
results.sort()       
+ g- @! W' m4 q" P8 V2 Nprint(results[-1]) #打印函数最大值和对应的
def calfitvalue(objvalue):#转化为适应值，目标函数值越大越好，负值淘汰。
2 b, [6 N+ _& }. k    fitvalue = []
1 u( \; j$ V  W  z    temp = 0.0
0 v' a/ f& O9 p. o9 {) {- _    Cmin = 0;
& L, x8 u3 G  V6 Q) W! E5 P5 o, q    for i in range(len(objvalue)):
        if(objvalue + Cmin > 0):
            temp = Cmin + objvalue
0 l: \0 `3 J; z7 l) U        else:
            temp = 0.0
# P- b; z" y2 L) @! h: U" s        fitvalue.append(temp)
    return fitvalue
. P" }# ]- y+ Z2 {2 ?import math
6 K$ Z& C5 k) h0 `: M4 }/ Y. S; V
1 l4 d7 t: G- z4 H" }" X: I9 Ddef decodechrom(pop): #将种群的二进制基因转化为十进制（0,1023）
4 H- u/ a) |: R* X6 Z/ w* [, H    temp = [];
    for i in range(len(pop)):
4 ~0 l& a7 `* `+ h8 w        t = 0;
        for j in range(10):
4 w) C+ _6 _( O& w            t += pop[j] * (math.pow(2, j))
* x" Z' t5 A3 Z( h; a        temp.append(t)
    return temp

def calobjvalue(pop): #计算目标函数值
    temp1 = [];
  B0 T- {( U9 z0 |! S( M. M- t, E    objvalue = [];
    temp1 = decodechrom(pop)
3 F: ~9 B$ Z! h- E& v1 R% |$ i+ e    for i in range(len(temp1)):
        x = temp1 * 10 / 1023 #（0,1023）转化为 （0,10）
        objvalue.append(10 * math.sin(5 * x) + 7 * math.cos(4 * x))
& ~' z- X7 d& n4 z    return objvalue #目标函数值objvalue[m] 与个体基因 pop[m] 对应
! [/ S  ~0 Y& g+ F+ l8 H( Kdef best(pop, fitvalue): #找出适应函数值中最大值，和对应的个体
        px = len(pop)
3 ?7 A3 l" s* M( K5 C        bestindividual = []
1 F, i% x  e" O        bestfit = fitvalue[0]
5 U- L+ {  H, y7 Q        for i in range(1,px):
6 R: j8 ]7 q, {7 H9 |5 ~                if(fitvalue > bestfit):
1 V1 i" Z, c+ B! P( K1 H" w0 L                        bestfit = fitvalue
                        bestindividual = pop
        return [bestindividual, bestfit]
. h  U. C$ d$ i0 g: B* v# Cimport random
7 I9 J6 m/ ?0 E* e
- q8 q$ Q* V+ O: {  E8 Vdef sum(fitvalue):
  B3 X: w/ V: z" I    total = 0
7 F# W# s  @1 b" B$ |: C    for i in range(len(fitvalue)):
        total += fitvalue
$ G+ ^- _3 @0 O) x1 v& |  i* J    return total
& I- i( |; R- n/ l6 D9 q: K2 _
def cumsum(fitvalue):
% H$ S! i9 }! S# z5 C5 g0 x    for i in range(len(fitvalue)):
2 ^) o* E8 h/ @5 [( c) o        t = 0;
        j = 0;
        while(j <= i):
; |% b% p! ?& {9 x            t += fitvalue[j]
% {1 _' r7 O0 A# t2 K: K            j = j + 1
+ h4 |. n$ ^, z. d! f0 }$ V7 X. W        fitvalue = t;
- O& R: g$ S) r. Z
1 a  U+ |! d5 }4 i- fdef selection(pop, fitvalue): #自然选择（轮盘赌算法）
; H9 A+ e. s6 r; @/ j' j1 V0 \. p        newfitvalue = []
# R1 W3 T9 ]% T6 T+ V        totalfit = sum(fitvalue)
        for i in range(len(fitvalue)):
, ]) o* L1 @: d2 r                newfitvalue.append(fitvalue / totalfit)
1 u* P, |/ r8 K. N( a        cumsum(newfitvalue)
        ms = [];
  j& ~7 D3 g' O8 [- H        poplen = len(pop)
        for i in range(poplen):
                ms.append(random.random()) #random float list ms
        ms.sort()
        fitin = 0
* ^' R" m, m8 q+ K7 N( h4 |% u        newin = 0
+ R' k# _2 U1 i        newpop = pop
# {/ E0 H3 w2 b        while newin < poplen:
: }5 h/ F! x6 C8 S0 W8 [1 g- g                if(ms[newin] < newfitvalue[fitin]):
                        newpop[newin] = pop[fitin]
                        newin = newin + 1
                else:
6 E' L. N5 M7 z1 |                        fitin = fitin + 1
        pop = newpop
import random
8 ^% ]/ Q$ V: y; }! w: z( ?& n8 q
* u. y8 e! `$ v5 Adef crossover(pop, pc): #个体间交叉，实现基因交换
5 V) I/ E. C$ u; g    poplen = len(pop)
2 m5 w# \2 b; V& Q: S    for i in range(poplen - 1):
        if(random.random() < pc):
            cpoint = random.randint(0,len(pop[0]))
            temp1 = []
2 y0 M! K8 d! n            temp2 = []
            temp1.extend(pop[0 : cpoint])
            temp1.extend(pop[i+1][cpoint : len(pop)])
! I- T* X/ M8 t: g- b            temp2.extend(pop[i+1][0 : cpoint])
            temp2.extend(pop[cpoint : len(pop)])
            pop = temp1
) ~' f; b) J0 y( R6 E& P3 P            pop[i+1] = temp2
import random

/ S/ B9 [- @3 ?9 z) d8 sdef mutation(pop, pm): #基因突变
* `9 ~" [9 ~: ]3 L( p    px = len(pop)
1 Q* }& ^  u2 k    py = len(pop[0])

    for i in range(px):
        if(random.random() < pm):
            mpoint = random.randint(0,py-1)
  E! }- h* C1 e9 X# B4 }$ G            if(pop[mpoint] == 1):
                pop[mpoint] = 0
4 K/ H( a8 L8 M/ o% a            else:
                pop[mpoint] = 1
5 t) k3 U$ {/ F6 r& }4 O
. O# `7 V+ L' L+ O
————————————————
版权声明：本文为CSDN博主「simon-zhao」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
9 K7 @1 [& l$ h3 C% {原文链接：https://blog.csdn.net/u010902721/article/details/23531359

5 |: N9 E' Y6 h$ _+ V9 ?

---

欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)

Powered by Discuz! X2.5