- 在线时间
- 1630 小时
- 最后登录
- 2024-1-29
- 注册时间
- 2017-5-16
- 听众数
- 82
- 收听数
- 1
- 能力
- 120 分
- 体力
- 565372 点
- 威望
- 12 点
- 阅读权限
- 255
- 积分
- 174834
- 相册
- 1
- 日志
- 0
- 记录
- 0
- 帖子
- 5313
- 主题
- 5273
- 精华
- 3
- 分享
- 0
- 好友
- 163
TA的每日心情 | 开心 2021-8-11 17:59 |
|---|
签到天数: 17 天 [LV.4]偶尔看看III 网络挑战赛参赛者 网络挑战赛参赛者 - 自我介绍
- 本人女,毕业于内蒙古科技大学,担任文职专业,毕业专业英语。
 群组: 2018美赛大象算法课程 群组: 2018美赛护航培训课程 群组: 2019年 数学中国站长建 群组: 2019年数据分析师课程 群组: 2018年大象老师国赛优 |
python实现的遗传算法实例(一)
" l3 c/ Y3 U, f2 P* U9 D7 q
; U+ X: o! o- H; M+ U$ S一、遗传算法介绍$ \/ S( a+ N/ ?9 Q I" T
! f: L& `* T. l' s9 m 遗传算法是通过模拟大自然中生物进化的历程,来解决问题的。大自然中一个种群经历过若干代的自然选择后,剩下的种群必定是适应环境的。把一个问题所有的解看做一个种群,经历过若干次的自然选择以后,剩下的解中是有问题的最优解的。当然,只能说有最优解的概率很大。这里,我们用遗传算法求一个函数的最大值。
! A. Y: C C. j+ c4 R. L6 w; q f(x) = 10 * sin( 5x ) + 7 * cos( 4x ), 0 <= x <= 10
. B2 B& L2 m+ A: u
* @6 o3 s+ v, c" m7 O1、将自变量x进行编码
: a: F1 v* X& x. {- D. e$ T) U/ x
取基因片段的长度为10, 则10位二进制位可以表示的范围是0到1023。基因与自变量转变的公式是x = b2d(individual) * 10 / 1023。构造初始的种群pop。每个个体的基因初始值是[0, 1, 0, 1, 0, 1, 0, 1, 0, 1]
* C3 \ s6 ~; C5 j; s0 T/ z" C, N
1 v) g, M) a/ W8 ~* b: P2、计算目标函数值
5 {) }: Y6 v' R) c/ W
( f# P- r$ ~ i r4 y9 c 根据自变量与基因的转化关系式,求出每个个体的基因对应的自变量,然后将自变量代入函数f(x),求出每个个体的目标函数值。
6 V8 N' J' [, \
! i, b0 I: N* Q8 ~" D& Q. L; o3、适应度函数 l6 {3 M, Q6 N; x( ]+ t# `3 A
2 w% y% a2 C( l# Y. E 适应度函数是用来评估个体适应环境的能力,是进行自然选择的依据。本题的适应度函数直接将目标函数值中的负值变成0. 因为我们求的是最大值,所以要使目标函数值是负数的个体不适应环境,使其繁殖后代的能力为0.适应度函数的作用将在自然选择中体现。
1 [# I( j% ~3 }0 e6 U
7 v( V; L* K$ }( t0 ~8 l7 P4、自然选择
7 [, _' g& R7 X1 f, \% i, X6 ]
M% `$ I: a- `) ]自然选择的思想不再赘述,操作使用轮盘赌算法。其具体步骤:
$ ^8 z6 j! D% e. J- {% p2 j& w$ W3 N1 o; A, ^
假设种群中共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号个体拷贝到新种群中。自然选择的结果使种群更符合条件了。+ a s1 W2 H/ H {$ O9 _$ [" ]
- M% m& \# L* l* X: a5、繁殖
2 k ~6 F3 W3 c- I& }1 g0 Z+ X# X r; F" w. U* t
假设个体a、b的基因是
* C o9 K a* g# }
+ F3 u) N1 k/ |8 Ma = [1, 0, 0, 0, 0, 1, 1, 1, 0, 0]8 X- |4 [' Q5 E6 D
. S9 [# m$ o! o2 ib = [0, 0, 0, 1, 1, 0, 1, 1, 1, 1]) Q r8 G. { k+ J$ {5 i; s; w
# E' V2 k; V3 o# ^9 [4 ^这两个个体发生基因交换的概率pc = 0.6.如果要发生基因交换,则产生一个随机数point表示基因交换的位置,假设point = 4,则:
7 w# o; I6 }0 x( n8 ^
7 B' a. Q" A; f- G3 K1 T+ A% Ta = [1, 0, 0, 0, 0, 1, 1, 1, 0, 0]
5 Y+ L1 W5 E/ K- P* N2 f+ U' ]; t# F* P# e& ^& S6 d
b = [0, 0, 0, 1, 1, 0, 1, 1, 1, 1]- x3 m- h/ {( M6 j7 |- _! K
5 w9 d5 Y, G9 o, {* g
交换后为:
! @) N6 x9 Q: ]6 |8 W: w- @. ?
" [ H. r- T, | ?: \. ^- Ra = [1, 0, 0, 0, 1, 0, 1, 1, 1, 1]6 D8 H: n& f( p3 @/ ?3 X7 [
3 O7 T" V/ \0 h# `
b = [0, 0, 0, 1, 0, 1, 1, 1, 0, 0]
2 S7 b; D( ^- r
8 i4 ~# Y! M) ^! U6、突变5 c3 q! z! A8 O! }5 D
9 O1 X: `/ I1 Y; U! J
遍历每一个个体,基因的每一位发生突变(0变为1,1变为0)的概率为0.001.突变可以增加解空间* X8 j, w! M- S' Z8 R) ~- L; s5 f, \
_% h1 Y+ `7 P# w+ R( f+ d
二、代码' a& E3 q, g9 `. l) u! ~5 |
def b2d(b): #将二进制转化为十进制 x∈[0,10]: k5 b' b0 o6 K6 m: t+ w
t = 0
* O& H8 K6 s5 y6 _1 q for j in range(len(b)):
. s* v2 D' ]1 S6 K7 g) c/ P+ I t += b[j] * (math.pow(2, j))' u1 `. P8 v4 Y9 Q
t = t * 10 / 1023
/ E; n d. `7 }8 U0 r9 {- a return t
0 |" E" K& p3 D: N5 C: G9 F7 L5 ]" G6 q8 x
popsize = 50 #种群的大小" P; R* A- b/ G3 z0 w
#用遗传算法求函数最大值:
. v+ R" e4 R* t5 t- u f#f(x)=10*sin(5x)+7*cos(4x) x∈[0,10]4 K3 N+ \$ f6 T% o
( y! Q: u# N+ ]( e6 M0 g! bchromlength = 10 #基因片段的长度% E) c& ]5 l2 g
pc = 0.6 #两个个体交叉的概率) ]+ b# |; A: l& a) H8 d
pm = 0.001; #基因突变的概率+ Z* I" G6 e8 k
results = [[]]2 i. l7 I0 h2 o$ B) F7 A: `
bestindividual = []
; |: V& ?! t% n- lbestfit = 0
W5 n! R! _; T$ U- xfitvalue = []
5 S+ }# q6 a* e2 j9 ftempop = [[]]7 Z4 ?1 O6 K/ [! r- {
pop = [[0, 1, 0, 1, 0, 1, 0, 1, 0, 1] for i in range(popsize)]
3 E: ?% O( P: q; Gfor i in range(100): #繁殖100代# z' }# u! j7 C3 ]6 h" y) R0 p
objvalue = calobjvalue(pop) #计算目标函数值7 N( F7 k6 G6 i7 \3 Y. A" ]
fitvalue = calfitvalue(objvalue); #计算个体的适应值
1 M/ E( t9 ?7 }, C9 q4 E# x( _0 E [bestindividual, bestfit] = best(pop, fitvalue) #选出最好的个体和最好的函数值
9 z0 p3 Y, o. i- ?' P6 A* G results.append([bestfit,b2d(bestindividual)]) #每次繁殖,将最好的结果记录下来) k) {- l+ g7 c0 [9 D
selection(pop, fitvalue) #自然选择,淘汰掉一部分适应性低的个体
; O' l/ l9 ]. C8 @1 Y3 k! } crossover(pop, pc) #交叉繁殖
7 P0 U" w) u* v+ `7 P& m6 `/ P6 _/ [ mutation(pop, pc) #基因突变
, m E: o( C# k9 v* j$ i; D `5 T
" o! F1 |6 S m' c, H$ k- c2 W5 \, l ^/ r& d0 d
results.sort()
$ S s) S ]* K9 C+ U' P. vprint(results[-1]) #打印函数最大值和对应的9 q8 x) G* {) [$ O) B3 g5 b
def calfitvalue(objvalue):#转化为适应值,目标函数值越大越好,负值淘汰。1 O8 _7 Q9 a& b L0 ]
fitvalue = []5 A9 z" G9 {* O+ a$ A1 S- B: h, X/ o$ G
temp = 0.0. H3 w6 r3 r+ b
Cmin = 0;
" f8 X0 P; x! D for i in range(len(objvalue)):5 q- z! X4 O8 d7 A( J
if(objvalue + Cmin > 0):
7 S0 `3 J7 b3 V temp = Cmin + objvalue+ s# Z1 m2 i G H
else:
" D, W# l$ j! p3 D; ]+ l temp = 0.0: Z+ e' j" M* S; j' A
fitvalue.append(temp)
% l: W& w# T8 f |: n return fitvalue
2 x- t0 X5 {% uimport math
$ W- `1 L& ?* X1 T3 c
. y8 V6 J/ x' `3 x- a3 t' xdef decodechrom(pop): #将种群的二进制基因转化为十进制(0,1023)
' K9 J# F, F1 d! F$ J temp = [];
( Z+ @+ y4 V) c3 A6 u) }1 ^ for i in range(len(pop)):# k8 H: @ ^# |' W& O5 x
t = 0;
8 r# J/ `/ k+ ]6 l4 U, O for j in range(10):
8 @ {& a; t5 _( m t += pop[j] * (math.pow(2, j))
* u& D% U D# v7 c! Z" z temp.append(t)
* |0 P8 X, {3 a7 J return temp
/ s4 n" e- k* P% }
2 t; ~; ^- {' e9 Y6 i9 K [def calobjvalue(pop): #计算目标函数值
1 s- |% ^1 G5 H! G temp1 = [];- T& H3 _& v4 T
objvalue = [];( p- @ k% o6 i( ]" O
temp1 = decodechrom(pop)
) i7 r7 W; Q/ W8 c for i in range(len(temp1)):
. X+ D( Q, o3 r8 @5 X! f2 B x = temp1 * 10 / 1023 #(0,1023)转化为 (0,10)
6 }& h/ B8 |; V% j+ t' ~# @ objvalue.append(10 * math.sin(5 * x) + 7 * math.cos(4 * x)); V. w" T+ \8 M1 ~& \
return objvalue #目标函数值objvalue[m] 与个体基因 pop[m] 对应 ! V% s* N* h. e1 k) V8 n/ m, d
def best(pop, fitvalue): #找出适应函数值中最大值,和对应的个体* j# h) y" a4 A
px = len(pop), v- \* Y, F+ J! z
bestindividual = [], h+ q' ~+ y4 b3 N+ \+ T/ w
bestfit = fitvalue[0]
3 D ^: ?. O9 { for i in range(1,px):
2 Q" V; ]+ a6 d0 A if(fitvalue > bestfit):5 e' ?1 |# t3 u4 H
bestfit = fitvalue) k' }1 E1 t3 C4 R; ^
bestindividual = pop) L4 w8 [* L4 }6 h( Z0 O! \8 i
return [bestindividual, bestfit]; z# ~6 y, Q- E+ S( R
import random
: {7 M& v; ^7 c; q
+ f) |- `- E+ a3 ^" I# y9 idef sum(fitvalue):6 C, X: f* ?6 T5 K9 |& N
total = 0. E% B; w- N+ L$ }( f# X' K4 A
for i in range(len(fitvalue)):
5 z# [% l- U) b! Y% v6 ]6 Y; M0 o total += fitvalue" `+ K; F2 q4 j s# t. p
return total
' z' T0 _; c8 d0 X
. q3 Y& M% d# adef cumsum(fitvalue):' r% U+ h- \2 m" C) S9 R
for i in range(len(fitvalue)):8 S/ ?- t2 ]$ t7 g+ f7 L) g' L
t = 0;
1 X5 `1 s6 u; Y+ h j = 0;# o; A9 B# ]+ M0 b9 M, c
while(j <= i):
, b: b, x3 q% Z t += fitvalue[j]! H5 Q/ f( A! o
j = j + 1; j3 j+ L) i; t" p) ?5 b4 I
fitvalue = t;: ?6 V% Y1 }0 j( `( K: e- X
d5 a0 A& r+ Y L7 t, D, Ydef selection(pop, fitvalue): #自然选择(轮盘赌算法)
- [& O* J* P, K# t1 h% z5 X) d newfitvalue = []# ~, y2 Q, Z# i2 A/ R% f( j
totalfit = sum(fitvalue)/ a) l0 ]: S1 U9 }: `
for i in range(len(fitvalue)):
3 t2 F8 n! P( j! o1 y' T% X/ ?5 j! [ newfitvalue.append(fitvalue / totalfit). u z4 Y& q% v' ?8 i }0 a) p$ l
cumsum(newfitvalue)& K! A+ ^# ^! p( v# }* H
ms = [];& O6 F+ V7 q2 |* ]& E- Q6 x
poplen = len(pop)4 U5 u5 v0 `; k6 s
for i in range(poplen):
4 ~* u; k, i6 I0 [0 G5 F ms.append(random.random()) #random float list ms4 f# d- ~, T8 s
ms.sort()
8 q! N5 ~' U+ M' |1 ? fitin = 0! _" o0 u( k8 j4 j$ V7 n! E
newin = 0
4 u2 L8 n6 Q4 ~" m% z newpop = pop7 z" V: \9 m" j3 t8 g$ v, T
while newin < poplen:
; O4 [" ^8 D6 E. ~% v4 E" k; t if(ms[newin] < newfitvalue[fitin]):' M; Q8 ^7 e+ p9 _- [# n1 b( @
newpop[newin] = pop[fitin]
4 @7 f8 G; k" z! ] newin = newin + 14 R; G7 J' p4 _& Z( o3 k. {" N
else:! I: P7 n) [4 G6 V
fitin = fitin + 1
* w; V6 M( @) T pop = newpop* h% @: M8 M' V. I' x' W6 ~
import random
% x& `# M7 T5 G1 B! J) U1 e+ T) y1 C0 o% q: d: b; Q" h
def crossover(pop, pc): #个体间交叉,实现基因交换
0 o: i2 z; j$ M8 n! r# c3 F poplen = len(pop)
' g% n3 F" Z7 q for i in range(poplen - 1):; ^$ |# u- ]4 V9 F ~# C9 G
if(random.random() < pc):
4 u; z! _9 ~+ a cpoint = random.randint(0,len(pop[0]))
. Z m5 @& F! |9 k" k( y0 c z temp1 = []( w0 k8 I3 L5 S0 R( L, A
temp2 = []' b. [: b/ {; e6 t: e
temp1.extend(pop[0 : cpoint])
. ^# L1 S/ J K- f' v- W v temp1.extend(pop[i+1][cpoint : len(pop)])
" q4 i$ c, A$ P, b6 D temp2.extend(pop[i+1][0 : cpoint])
6 Q, M1 t( X% E* F8 a; b- [ temp2.extend(pop[cpoint : len(pop)])$ U# J' a' M% B5 P, i. @) w* L
pop = temp17 x2 x3 F1 C/ A% j* E7 {" \
pop[i+1] = temp2- z5 {8 p; Y: y3 r
import random0 i) a6 J! c3 _+ l6 Z
. B9 d. K! W; n4 V! a" n. U0 v$ Ydef mutation(pop, pm): #基因突变
" B2 q* r a) i, F& _6 I px = len(pop)% A P. ]+ N5 X, P0 W4 }, R
py = len(pop[0])7 M9 N( i1 V1 J$ u9 @
( }2 c j' P$ u! Q/ i, d0 N$ T: q
for i in range(px):
$ k9 ] X# i( m Q$ o if(random.random() < pm):- ]2 t" \# O4 E0 q5 ~. A& z
mpoint = random.randint(0,py-1); e; U+ M+ u0 d2 `; `
if(pop[mpoint] == 1):( N9 M5 y/ J9 M# q
pop[mpoint] = 0% t+ u! z. M# b
else:1 Q4 G% ~2 \7 s+ F/ [
pop[mpoint] = 1% W( a6 E$ P; v6 [- \
# b2 O. q" N3 I
% G4 E! p1 v1 j: F$ g/ `————————————————
# U# U# v3 ~/ x( G版权声明:本文为CSDN博主「simon-zhao」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
* r4 O6 N3 o6 a原文链接:https://blog.csdn.net/u010902721/article/details/235313595 g4 q. J2 U F' P" U1 g: E
) O; M+ E, A. Q$ Z4 F
+ b9 x" `+ m; S9 {- f! q! n
|
zan
|