数学建模社区-数学中国
标题:
python实现的遗传算法实例（一）
[打印本页]
作者:
杨利霞
时间:
2020-5-9 14:48
标题:
python实现的遗传算法实例（一）
python实现的遗传算法实例（一）
p6 r. l& v& F7 w9 v$ e. P
* i3 l5 r. X) N7 L
一、遗传算法介绍
9 X4 G% z. f( S' A
) e3 x) z% x3 n* n+ M
遗传算法是通过模拟大自然中生物进化的历程，来解决问题的。大自然中一个种群经历过若干代的自然选择后，剩下的种群必定是适应环境的。把一个问题所有的解看做一个种群，经历过若干次的自然选择以后，剩下的解中是有问题的最优解的。当然，只能说有最优解的概率很大。这里，我们用遗传算法求一个函数的最大值。
! J2 b: o# P# J* e
f(x) = 10 * sin( 5x ) + 7 * cos( 4x ), 0 <= x <= 10
0 M- c0 M6 T8 V: l7 w
" A% ~8 z; \; |
1、将自变量x进行编码
3 K2 D9 ]5 S" r
# V+ W) v* R- `' f# q( b
取基因片段的长度为10, 则10位二进制位可以表示的范围是0到1023。基因与自变量转变的公式是x = b2d(individual) * 10 / 1023。构造初始的种群pop。每个个体的基因初始值是[0, 1, 0, 1, 0, 1, 0, 1, 0, 1]
2 q! z+ u5 U* @ H6 P9 o! T
: k: n' \# B M% F+ n# c) j
2、计算目标函数值
+ B% n( {: l* ^
9 j& Y3 b- M# h" \2 F
根据自变量与基因的转化关系式，求出每个个体的基因对应的自变量，然后将自变量代入函数f（x），求出每个个体的目标函数值。
$ ~% O$ L L( m, F1 s
3 h7 G3 Z; X. Y
3、适应度函数
* O" C7 o) ^2 C* }
5 A0 P) r5 X5 z; ]* }* c3 B" x* F
适应度函数是用来评估个体适应环境的能力，是进行自然选择的依据。本题的适应度函数直接将目标函数值中的负值变成0. 因为我们求的是最大值，所以要使目标函数值是负数的个体不适应环境，使其繁殖后代的能力为0.适应度函数的作用将在自然选择中体现。
! ^3 h5 E2 R" [/ t! T
* c6 T+ l# ~5 ?$ r1 d4 P2 V
4、自然选择
# F' {2 d2 e$ U: e' v( z
( s1 X; [( `3 s! J
自然选择的思想不再赘述，操作使用轮盘赌算法。其具体步骤：
. L# F* Q+ B# n$ M, g- \
o( h& i3 ~2 |9 J" t9 O c7 S; y
假设种群中共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号个体拷贝到新种群中。自然选择的结果使种群更符合条件了。
1 D8 L4 l* f: n5 e# _& t! V9 Z
# A2 @9 [" T5 k, v4 K: A
5、繁殖
5 Y& `$ M$ Y' p5 S3 O
0 ?" y, z# U4 |, C# f* J* ?
假设个体a、b的基因是
) x) }! S9 f( T6 l" A
0 I2 ?; b7 H: b
a = [1, 0, 0, 0, 0, 1, 1, 1, 0, 0]
' X0 W* l- i! q
7 \4 v2 Q6 G1 O L- `- H+ N
b = [0, 0, 0, 1, 1, 0, 1, 1, 1, 1]
+ b+ ~' U: |: f# T0 n4 A+ w0 W0 P
0 ?5 S. h+ c2 ~& O2 J
这两个个体发生基因交换的概率pc = 0.6.如果要发生基因交换，则产生一个随机数point表示基因交换的位置，假设point = 4,则：
5 Z/ D2 R3 e U
! x) V# @/ z/ q* E6 L4 F
a = [1, 0, 0, 0, 0, 1, 1, 1, 0, 0]
* `1 O) Z t1 Q- r, H
6 U Z4 a" w# v+ Q5 w
b = [0, 0, 0, 1, 1, 0, 1, 1, 1, 1]
, T% i2 K! o9 i* }% h
* ^0 Q) P9 d* r2 t
交换后为：
* O; Y: c2 o6 @
: j% V2 x+ W% O: Y
a = [1, 0, 0, 0, 1, 0, 1, 1, 1, 1]
8 S% U, u1 L/ N! [- o! b6 D2 d
8 V( @* W& n6 ^8 p: t4 n
b = [0, 0, 0, 1, 0, 1, 1, 1, 0, 0]
& _$ U- `3 W' y) [! ~& p/ ~9 z0 F
- S# B+ U, {9 P: M7 a0 D% w1 B
6、突变
9 [3 E" w+ t, M8 |3 d; e' G
! T" T/ k$ K* |* U6 I- j1 n4 N1 i w
遍历每一个个体，基因的每一位发生突变（0变为1,1变为0）的概率为0.001.突变可以增加解空间
5 W0 S) }; Q. Q$ A7 {
$ d# u" F3 Z$ C& C& _% T$ a
二、代码
' p! }. K+ A2 |, k" C, ?
def b2d(b): #将二进制转化为十进制 x∈[0,10]
1 j! v- k/ I' X( m0 _
t = 0
# B9 U8 X$ K: M, Q) ]( X5 z4 P
for j in range(len(b)):
" v/ J& r8 Z) G4 H" E& c, ^0 M
t += b[j] * (math.pow(2, j))
8 |+ X+ @ \# `6 f% f" h) Z
t = t * 10 / 1023
( ^0 u W, a f& G3 ?# a
return t
; A* S3 Y& X& @9 B5 u
( S0 v ]2 W9 M, W
popsize = 50 #种群的大小
n2 {! m* s& m" s0 y( T
#用遗传算法求函数最大值：
% L8 o- w) K. s1 [
#f(x)=10*sin(5x)+7*cos(4x) x∈[0,10]
. N* k1 V) Q8 r9 T" W' T
5 G2 n/ O$ r7 u9 o0 p: ] _) E1 C
chromlength = 10 #基因片段的长度
4 l) p& u3 L- G( G3 _
pc = 0.6 #两个个体交叉的概率
, ?( L7 j8 D9 i, A
pm = 0.001; #基因突变的概率
4 S& M* ^$ A. G
results = [[]]
. k& F d1 s- g5 e# o
bestindividual = []
/ k2 X/ E" ?. J" s
bestfit = 0
( h" I7 I: K, O7 z2 G7 M
fitvalue = []
0 D) t! K+ y7 m; [3 o
tempop = [[]]
* a; O; b: [" @. t3 `* P
pop = [[0, 1, 0, 1, 0, 1, 0, 1, 0, 1] for i in range(popsize)]
! O( V/ T: y& U
for i in range(100): #繁殖100代
/ V% S Y i* Q. C
objvalue = calobjvalue(pop) #计算目标函数值
0 W. a3 W$ B7 a
fitvalue = calfitvalue(objvalue); #计算个体的适应值
0 k0 r7 R+ _4 a! x
[bestindividual, bestfit] = best(pop, fitvalue) #选出最好的个体和最好的函数值
$ y% Z+ [8 P* `- `
results.append([bestfit,b2d(bestindividual)]) #每次繁殖，将最好的结果记录下来
+ B1 T* m1 Z1 F4 t8 {3 p7 n
selection(pop, fitvalue) #自然选择，淘汰掉一部分适应性低的个体
7 l' W$ B" g; [3 } b
crossover(pop, pc) #交叉繁殖
1 Q, E% z6 P5 T6 p2 o; A
mutation(pop, pc) #基因突变
# R( p6 O- t8 v6 A4 x% g# V6 c* x: T* ?
/ d5 p' V& f) ?; ]) U
0 u% v& u: Q% G* H5 ?- X- l7 k
results.sort()
; Z! B" w0 U7 ~2 N$ `* D* T9 m
print(results[-1]) #打印函数最大值和对应的
1 r& v- G- }) ]0 M
def calfitvalue(objvalue):#转化为适应值，目标函数值越大越好，负值淘汰。
9 ?' j) Q4 t4 K) \' t% H5 r7 c6 ]7 z
fitvalue = []
8 i& p1 e/ `6 t
temp = 0.0
: Q8 u( }' y" e5 R) s$ h
Cmin = 0;
" L5 a( }4 R V. M7 n$ A8 |
for i in range(len(objvalue)):
! q5 d* o3 Z9 c
if(objvalue
+ Cmin > 0):
2 r' [) C( n8 c
temp = Cmin + objvalue
3 M. a* M5 c) C7 n
else:
9 k; j( K9 n( W( u
temp = 0.0
, _* [4 O* n- k f! }. O) n
fitvalue.append(temp)
3 _: i7 g- O( S0 W
return fitvalue
- }3 l% a7 ^$ F& r3 X& j* [
import math
8 \7 W) F/ v* K, [" c1 V1 F R5 e6 K
" Z+ B4 y {4 o; R8 B- a
def decodechrom(pop): #将种群的二进制基因转化为十进制（0,1023）
: ?! l0 n$ _$ X+ d, B" x7 j; ?8 p
temp = [];
0 j& V4 u- A \; j R
for i in range(len(pop)):
6 ]) n: h5 O% }( f% H# S5 Q9 o
t = 0;
' x( R. O+ h! B% s v. k y% F
for j in range(10):
- j, G0 a$ I1 T0 c( ~1 G! i
t += pop
[j] * (math.pow(2, j))
4 e9 z/ V6 q3 \) R$ m
temp.append(t)
7 G# k: j& F3 y
return temp
4 F. h3 R6 P y4 W2 S
4 i) V2 l( l7 W, d4 a- C: `" m
def calobjvalue(pop): #计算目标函数值
8 i: Q) ?) e; Q; Z( S5 A
temp1 = [];
+ q7 Q! x( f* [4 O }
objvalue = [];
/ B! I3 y; W. e! S- B5 ?: _9 \
temp1 = decodechrom(pop)
4 }9 [% r$ m% I% [' W5 a" _& V: g
for i in range(len(temp1)):
5 d; J) X$ @0 `& P0 a
x = temp1
* 10 / 1023 #（0,1023）转化为 （0,10）
0 T1 h8 H8 t, K1 R, U% d
objvalue.append(10 * math.sin(5 * x) + 7 * math.cos(4 * x))
0 P3 |1 H* A$ s4 d- e1 A" `# F
return objvalue #目标函数值objvalue[m] 与个体基因 pop[m] 对应
, D3 ?. b6 v: H
def best(pop, fitvalue): #找出适应函数值中最大值，和对应的个体
) N' y }) L! }7 U D( }- s
px = len(pop)
2 `# X# I. d" @/ M* p/ ^2 @
bestindividual = []
) |3 m' B! f0 _* J! w; a
bestfit = fitvalue[0]
3 m( y' |2 n0 a1 u
for i in range(1,px):
* Z: ?" M6 V0 A% V" B7 D
if(fitvalue
> bestfit):
: O w E6 Y. x
bestfit = fitvalue
% I9 q9 C6 l3 j+ ?
bestindividual = pop
5 ~7 T4 S, |# Y+ d2 m4 ?
return [bestindividual, bestfit]
! W) _" E! V2 d4 A
import random
% ^* S; e [ S
) {+ M; |0 F; D: P* a5 Y
def sum(fitvalue):
/ T$ O6 S0 t% `: n. k! N) y6 `
total = 0
* w8 W" Y4 z6 z" h0 L
for i in range(len(fitvalue)):
7 I* f% {1 j9 ]+ v1 J
total += fitvalue
2 ]3 {( q' H4 Y7 C; H1 q# U4 a
return total
& O! E! c5 c# Q% I' u y; \
, O" z$ z7 g; G3 s% o
def cumsum(fitvalue):
4 r* T/ a6 b, H0 w: x8 _
for i in range(len(fitvalue)):
: K: s0 | Y, x, j
t = 0;
* y+ w) e- F4 y7 ~- w; B/ r+ }
j = 0;
5 P" g2 ~# S4 w
while(j <= i):
8 I- Q5 m( A" c& l, B( c
t += fitvalue[j]
7 d8 Z, t5 v9 f* \2 R
j = j + 1
" T3 _( w, a4 ~; I
fitvalue
= t;
# B3 P/ }/ T+ a
" d7 S4 Q- U: G: a5 E$ a
def selection(pop, fitvalue): #自然选择（轮盘赌算法）
) n# S \' T$ [
newfitvalue = []
8 Q4 P+ g. [5 ?- T& g6 Q# w$ P
totalfit = sum(fitvalue)
3 A+ [1 W$ T7 f
for i in range(len(fitvalue)):
4 D7 c' y, o! h+ Y# X
newfitvalue.append(fitvalue
/ totalfit)
- G0 H3 i' |, P4 a% v
cumsum(newfitvalue)
1 ~- V2 ~+ k! O8 s1 t0 F6 X" M1 z
ms = [];
$ o! O2 ?- w D! \
poplen = len(pop)
5 p0 D, `; D# n/ }
for i in range(poplen):
6 H5 ]7 d% B3 r7 P
ms.append(random.random()) #random float list ms
; S) y( J0 d6 Q. V
ms.sort()
4 D% q3 U& d0 o/ R9 g8 G
fitin = 0
# ~1 @ }6 Z8 `8 ?; x7 x
newin = 0
: j Q% o2 w A
newpop = pop
0 v' d* ^( R: Q1 K1 b
while newin < poplen:
5 A9 c9 y4 f& j w
if(ms[newin] < newfitvalue[fitin]):
% K$ A' P( x. p0 _9 J
newpop[newin] = pop[fitin]
+ z, M% x4 }9 i: P) p5 s* p
newin = newin + 1
4 n0 \: Y6 O8 C) q2 ^! v1 Y
else:
0 V8 }: k- |. |! U( D3 [: P, C
fitin = fitin + 1
) y- {, [8 n. T0 k; y
pop = newpop
9 i+ c( W0 J/ d2 n* H
import random
/ k% P3 `" H" v, e* r+ F
2 h- s& c( L% c8 w5 K, r) o
def crossover(pop, pc): #个体间交叉，实现基因交换
, U6 a& q4 x) a9 q+ d6 k- h
poplen = len(pop)
. E. [- w4 [1 i( g, a
for i in range(poplen - 1):
2 `" j4 j- M! C4 y+ I+ l
if(random.random() < pc):
) n4 n* Z7 t* Y9 x2 \+ R
cpoint = random.randint(0,len(pop[0]))
" l7 D# s: W9 M( E: Q# i* C. e* g
temp1 = []
- J* A4 W- v3 O: u& p" Y# G% I4 o
temp2 = []
c6 k/ X+ ^/ ]1 x7 t
temp1.extend(pop
[0 : cpoint])
6 p9 |% _% Z' `& S. s
temp1.extend(pop[i+1][cpoint : len(pop
)])
- G5 c( [9 v- P% z& n
temp2.extend(pop[i+1][0 : cpoint])
: s( I: j) O9 H
temp2.extend(pop
[cpoint : len(pop
)])
" C) c* X- O3 e' O8 z: ~
pop
= temp1
6 Y$ Y# T8 C, A+ E9 i
pop[i+1] = temp2
. T; U: T, M8 B' M, t( v; ~$ b2 T1 n
import random
/ a" P7 R8 v/ ` n1 T, f
% u- R4 f- u: g' N9 U6 j6 p
def mutation(pop, pm): #基因突变
) g! b0 @/ [/ E; q) X4 |
px = len(pop)
6 N4 q# U' p/ j4 Y7 q o/ ~
py = len(pop[0])
+ |" V0 `% y' j$ G
% z o2 T4 I* P6 l6 J; b
for i in range(px):
, ?/ m3 D! h* n/ |+ }* \
if(random.random() < pm):
! S- W( J7 g1 f9 N5 }
mpoint = random.randint(0,py-1)
4 f1 \9 e3 _8 e# v5 S" s
if(pop
[mpoint] == 1):
9 L6 J4 m. f7 L L* Q
pop
[mpoint] = 0
: P1 I' o0 O1 \8 L) F- O: h
else:
# `& U2 S! B6 y A
pop
[mpoint] = 1
: S$ M* `* m! e5 Q- |) X
$ W7 j, O; ^8 m" p
' M; L6 @$ b- U/ |8 i: @
————————————————
0 [8 f2 u; X# t( a& n* m
版权声明：本文为CSDN博主「simon-zhao」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
# q L, u: a8 J' ^3 }9 v- \, {
原文链接：https://blog.csdn.net/u010902721/article/details/23531359
9 ]# M% d' ^# m! j/ D2 g6 T
7 B) E- H- e- q: i ^6 ]
4 u+ C- S. \: u3 ~ [) o- {4 b
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5