- 在线时间
- 1630 小时
- 最后登录
- 2024-1-29
- 注册时间
- 2017-5-16
- 听众数
- 82
- 收听数
- 1
- 能力
- 120 分
- 体力
- 564568 点
- 威望
- 12 点
- 阅读权限
- 255
- 积分
- 174593
- 相册
- 1
- 日志
- 0
- 记录
- 0
- 帖子
- 5313
- 主题
- 5273
- 精华
- 3
- 分享
- 0
- 好友
- 163
TA的每日心情 | 开心 2021-8-11 17:59 |
|---|
签到天数: 17 天 [LV.4]偶尔看看III 网络挑战赛参赛者 网络挑战赛参赛者 - 自我介绍
- 本人女,毕业于内蒙古科技大学,担任文职专业,毕业专业英语。
 群组: 2018美赛大象算法课程 群组: 2018美赛护航培训课程 群组: 2019年 数学中国站长建 群组: 2019年数据分析师课程 群组: 2018年大象老师国赛优 |
python实现的遗传算法实例(一)
5 p8 ^& h3 A5 O9 \' B( x1 \2 }+ Q. n" U6 V5 n. a. s: C! f' U% t
一、遗传算法介绍' K+ P/ w8 S0 z7 _
" ]. i9 P* f# L6 `. V; c 遗传算法是通过模拟大自然中生物进化的历程,来解决问题的。大自然中一个种群经历过若干代的自然选择后,剩下的种群必定是适应环境的。把一个问题所有的解看做一个种群,经历过若干次的自然选择以后,剩下的解中是有问题的最优解的。当然,只能说有最优解的概率很大。这里,我们用遗传算法求一个函数的最大值。
; c- e& n% t2 I6 q5 f0 c8 |, [ f(x) = 10 * sin( 5x ) + 7 * cos( 4x ), 0 <= x <= 10
: p4 D/ n' ]: {: a5 O+ W- a8 K0 |, Z
1、将自变量x进行编码
w! y1 x, M" l6 ~% _8 {
+ u9 u* {* b4 a4 n( C 取基因片段的长度为10, 则10位二进制位可以表示的范围是0到1023。基因与自变量转变的公式是x = b2d(individual) * 10 / 1023。构造初始的种群pop。每个个体的基因初始值是[0, 1, 0, 1, 0, 1, 0, 1, 0, 1], |+ b# o/ s& I) T
8 ^1 H) o# o# M: d2、计算目标函数值4 @' ^: M2 b+ j8 S
4 z$ k# I. R+ U' @ 根据自变量与基因的转化关系式,求出每个个体的基因对应的自变量,然后将自变量代入函数f(x),求出每个个体的目标函数值。. ^# I, q4 e4 H' V# |
+ L: }9 O) V) N
3、适应度函数
. |$ @. x5 W4 S$ h2 \) f6 p1 R6 p/ y1 z' {% K5 m
适应度函数是用来评估个体适应环境的能力,是进行自然选择的依据。本题的适应度函数直接将目标函数值中的负值变成0. 因为我们求的是最大值,所以要使目标函数值是负数的个体不适应环境,使其繁殖后代的能力为0.适应度函数的作用将在自然选择中体现。! ^, G7 b; H ]" x5 x
: K3 d( g- C5 r1 m: m
4、自然选择' I5 V# Z: t1 {
( y2 f8 k- {" C% l& t1 r
自然选择的思想不再赘述,操作使用轮盘赌算法。其具体步骤:
) h y0 e! A _+ m/ j
7 T3 D0 @# A+ x, L; {假设种群中共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号个体拷贝到新种群中。自然选择的结果使种群更符合条件了。. {; F/ U- {; b2 P
9 t4 [: K. r" i) G" Z" ]. x5、繁殖: `3 H- j& V, }
" _8 i( J' x( ~8 e& @& Y假设个体a、b的基因是2 z" g( x6 k# j6 J, A) I
+ u9 j) }- w4 t. F
a = [1, 0, 0, 0, 0, 1, 1, 1, 0, 0]$ S8 K! \/ w9 X" Y: q6 `' {+ P8 P
7 o% f N6 I( Eb = [0, 0, 0, 1, 1, 0, 1, 1, 1, 1]
6 I7 H( f+ v8 [! G: R8 N. h5 H5 u. {! C$ j& Q
这两个个体发生基因交换的概率pc = 0.6.如果要发生基因交换,则产生一个随机数point表示基因交换的位置,假设point = 4,则:8 {2 ~, V+ W0 H$ U8 y6 f4 n6 Z3 L
; d5 f; w; n$ g1 t: Ha = [1, 0, 0, 0, 0, 1, 1, 1, 0, 0]8 C) R1 N t) H1 t
- H! L: U! p! [) N/ ab = [0, 0, 0, 1, 1, 0, 1, 1, 1, 1]
% m3 _8 @* B$ u0 H& G2 Y, Q w
/ j$ T' c$ |$ C2 o# h4 ]$ q, L交换后为:# u3 ~5 W$ G) D+ c% ~7 m1 d; f
" z# e8 R+ b9 \a = [1, 0, 0, 0, 1, 0, 1, 1, 1, 1]
j# ~ U! ?5 ] ^* w5 y# Y+ W7 g S4 G' v# \6 _
b = [0, 0, 0, 1, 0, 1, 1, 1, 0, 0]& D y0 P* h9 U
* R5 C# Q; p7 F( G
6、突变
( P% A2 U+ B7 |; z9 g4 R0 d- O2 A! V! }
遍历每一个个体,基因的每一位发生突变(0变为1,1变为0)的概率为0.001.突变可以增加解空间+ {+ t" D' o" I3 N* m$ i
4 P. x" U! ~/ v6 u' P, ~9 v( n# x二、代码& }6 U0 ^- c W2 t* K: a* A
def b2d(b): #将二进制转化为十进制 x∈[0,10]
$ b0 L) z: W5 g; w4 \1 x2 {; D2 C4 J t = 0 X5 e# D$ u! c4 C
for j in range(len(b)):
9 G: c/ Q; {! k" N, E t += b[j] * (math.pow(2, j))
m. a2 U q* a# L, d( v* ~& t. f t = t * 10 / 10233 } s' Y2 Z* y1 H$ H- r
return t
: w4 ]! U' X: d, S5 Y; ]; _; Z4 M/ L; ~& _' v \
popsize = 50 #种群的大小0 ^; S3 I" [6 ~5 k8 d3 D
#用遗传算法求函数最大值:
: p$ s* I$ @* t+ e4 o# P* d% H#f(x)=10*sin(5x)+7*cos(4x) x∈[0,10]3 Q" x. d6 T5 R, E- m& H; r
3 \5 U a% P7 p0 c) F0 I, N, ychromlength = 10 #基因片段的长度( l/ g0 Q8 j7 z0 \7 ?3 h
pc = 0.6 #两个个体交叉的概率# ^& s; a% w8 n# m5 r1 c7 L5 `
pm = 0.001; #基因突变的概率
4 y! i. @) n4 F- yresults = [[]]+ H! Z. j+ [/ l C; f
bestindividual = []
# d4 _: Z6 c6 N/ j6 H# M/ H, Ybestfit = 02 ]8 r, } j; M( J" w
fitvalue = []$ G4 o6 G" z" J8 |& ]3 ~7 e6 [
tempop = [[]]
6 |- n. j. V2 Ypop = [[0, 1, 0, 1, 0, 1, 0, 1, 0, 1] for i in range(popsize)], z1 C) j3 d- c$ g+ L1 d3 h
for i in range(100): #繁殖100代/ K/ Z8 `0 y- ~0 L5 s
objvalue = calobjvalue(pop) #计算目标函数值
: ]; s6 a( a' ?- g5 {' T fitvalue = calfitvalue(objvalue); #计算个体的适应值
9 j0 }7 a5 | M2 E; \- e' T [bestindividual, bestfit] = best(pop, fitvalue) #选出最好的个体和最好的函数值0 u. l5 Q# s" D
results.append([bestfit,b2d(bestindividual)]) #每次繁殖,将最好的结果记录下来; _2 D3 ?/ W" D0 b9 V& L- C! J$ K, U7 `
selection(pop, fitvalue) #自然选择,淘汰掉一部分适应性低的个体
# f7 j& m! b8 i: v crossover(pop, pc) #交叉繁殖
" L0 d1 K* @ u' w mutation(pop, pc) #基因突变6 S* o% n6 N* @5 u
$ O6 M$ f+ T8 q
* Z# r. r2 n6 l; U! w
results.sort()
! }9 ?; z/ B4 k+ yprint(results[-1]) #打印函数最大值和对应的
1 \. h `+ d/ y2 G& rdef calfitvalue(objvalue):#转化为适应值,目标函数值越大越好,负值淘汰。
% W3 t$ t' y! P fitvalue = []
9 t* U: f4 t _3 S: c temp = 0.04 C0 j+ C( y! B+ ~. G- F
Cmin = 0;' j; V% @% ]) _4 m, z' i) O& I
for i in range(len(objvalue)):4 s/ F0 P" `' ]( {. U5 {! x
if(objvalue + Cmin > 0):# G# o( u9 Y$ c; `
temp = Cmin + objvalue; _+ K. j! b7 p: ?: j
else:1 l- O. F6 U7 n) ?; h
temp = 0.0
$ f# i/ U. E5 s- V# u7 s$ \# { fitvalue.append(temp)) u8 c, V1 e/ e' {, T: E' e
return fitvalue
$ U+ h, L; b. l9 ~ |8 N0 D kimport math
, H( T" t6 n2 \5 e1 X! T+ m' z; k6 K
def decodechrom(pop): #将种群的二进制基因转化为十进制(0,1023)0 Y2 k& c/ `; B, o! Q
temp = [];% K$ y) N i( u2 O: h; I+ j
for i in range(len(pop)):. {: ^$ t5 y; C% ]
t = 0;2 ?' i; m; ?, e1 D
for j in range(10):2 n I1 Z2 Z: ~- x1 H9 j
t += pop[j] * (math.pow(2, j))
; ^& ~$ m# n* A5 x" \ temp.append(t)
. T+ }( l4 _5 i# {+ x6 k: X return temp
( x' L" }7 E4 Z, L6 e2 Z r4 ]# A3 w8 j/ J
def calobjvalue(pop): #计算目标函数值2 N5 Z b" U5 ?- O7 K' i& o
temp1 = [];# z5 t9 N- N/ r& q8 p9 o2 z
objvalue = [];1 P; x# W* W5 R" ?2 r
temp1 = decodechrom(pop)
2 Y/ `7 M' Y m8 j for i in range(len(temp1)):% Z, Z- F0 M- A/ d2 i* `: j" m$ \* {! X
x = temp1 * 10 / 1023 #(0,1023)转化为 (0,10)8 d' X' ] W i$ z* n( a0 o [" _9 y
objvalue.append(10 * math.sin(5 * x) + 7 * math.cos(4 * x))) N/ l& H, A! b2 X* e1 G- n2 g$ n
return objvalue #目标函数值objvalue[m] 与个体基因 pop[m] 对应 7 }5 R! D7 V2 G. {0 j
def best(pop, fitvalue): #找出适应函数值中最大值,和对应的个体
$ o* {4 V/ V1 `" `8 D px = len(pop)8 @7 c( u: T/ D9 P. {$ N% ]
bestindividual = []! N5 ~6 m$ ]1 s9 {4 ^5 G7 t, C( ]) l
bestfit = fitvalue[0]
( {( O5 F( Y ~2 \7 i1 L" `9 j for i in range(1,px):' x' a; I1 E: W. u/ W
if(fitvalue > bestfit):6 m: {' |8 ^. N0 X
bestfit = fitvalue
% c6 Z1 H8 O9 d- s bestindividual = pop
- W# F5 Q! a6 H1 \ return [bestindividual, bestfit]
' c0 B; t- b2 M5 Uimport random
* y5 n; G/ h8 Z( v: M, N
; b6 n( ?2 T7 E: I8 F0 ]def sum(fitvalue):6 a& s: s: y: d: f V5 d
total = 08 j- j: U: X9 C$ c# Z9 g7 k+ w
for i in range(len(fitvalue)):6 A: B6 q7 X5 i5 S
total += fitvalue
5 G" Y: ~1 s4 [, A return total
- z$ U% P8 Q& |; G- L( Q, w6 \( m/ t; h, n
def cumsum(fitvalue):8 R. o! Y& k: j/ j9 N o
for i in range(len(fitvalue)):- C9 L* C% V3 Z# S
t = 0;
( f# K" N6 k. ~9 o( Y* o; ?; B j = 0;/ S* c3 M/ ]$ ?- d$ M
while(j <= i):
! p2 p+ O3 q6 n+ E6 C t += fitvalue[j]
\ ?3 p# [: M+ h2 P0 L j = j + 1$ o8 L" s; L* ?0 R, A( q [
fitvalue = t;
0 p/ i5 R: C! J2 M" `4 b! f6 b0 i3 S( j/ v" ]& W
def selection(pop, fitvalue): #自然选择(轮盘赌算法)
6 o( {) t9 S4 q, @5 X newfitvalue = []2 |8 `3 [, k; @, l
totalfit = sum(fitvalue)
- _; x1 l5 ?9 t% v1 w; c6 R8 J for i in range(len(fitvalue)):( }7 F z6 i7 x0 D/ ]5 h
newfitvalue.append(fitvalue / totalfit)
2 j7 E8 ]' A6 s7 N cumsum(newfitvalue)
0 E* W& i0 x5 x! q ms = [];! ^* x( T2 |+ |6 Z9 e+ ^# a
poplen = len(pop)
0 ^; }9 _( C. J for i in range(poplen):
) R4 e5 L5 l- f$ @ k ms.append(random.random()) #random float list ms
( o% O: n! i) S# ~ ms.sort()
! U9 |/ \5 c0 }. O$ ` s7 B fitin = 03 ^$ n2 R) G: g f& M1 _1 `
newin = 0
6 {( @9 }, e7 j/ n( f# M. a newpop = pop
u, {3 C: T' r$ d6 D1 M" u% ~ while newin < poplen:
) c- |! g' ~' J7 }& u if(ms[newin] < newfitvalue[fitin]):
# U, c: f9 r Y newpop[newin] = pop[fitin]
0 r+ _/ w# Q, D8 n% ?/ f newin = newin + 1- R, _+ M9 }* V+ A
else:
& f+ p! o9 E7 J) o fitin = fitin + 1
9 H* E8 Q/ G/ b; `2 N pop = newpop
: M6 U# K: D' K& `% _" h& e/ u/ aimport random
" _, b6 D, |$ m% Q) n+ ]4 L: ?8 K9 z- W
def crossover(pop, pc): #个体间交叉,实现基因交换
, l5 G( j7 n: `+ K poplen = len(pop)- g, U* v2 H; S q8 s9 X, j
for i in range(poplen - 1):* @7 }, D! x, N* s, Q& T+ Y
if(random.random() < pc):/ C; S! L1 b9 r
cpoint = random.randint(0,len(pop[0]))
l1 I$ ^' N O0 [8 H U) ?0 f: s temp1 = []9 n9 g! M1 H: s
temp2 = []
* d3 w" E. y1 E# I: ] temp1.extend(pop[0 : cpoint])
& a. l$ R/ U8 e! R+ G8 R temp1.extend(pop[i+1][cpoint : len(pop)])
/ a- }; G' f( n: M# z* d temp2.extend(pop[i+1][0 : cpoint])
; i& n1 g& N$ \) e/ n temp2.extend(pop[cpoint : len(pop)]), R3 }8 l8 r; ^4 U/ d- N
pop = temp15 v9 M' p- N1 T! a4 C
pop[i+1] = temp21 ]! g: l5 n- {0 O
import random4 ^$ ^4 w9 W" T+ l) j, D4 }! h/ U2 S
& D9 E; D! @( l; d5 M3 |& E5 rdef mutation(pop, pm): #基因突变. v7 |* Q. B* @* c ^; ^" y
px = len(pop)
6 Z2 T( G; P/ G% K( m4 c py = len(pop[0])
+ k) v6 W x8 u
2 Q- w- X/ W* s" ~' M9 G2 k5 l6 \ for i in range(px):! v7 Y7 t2 `2 T, e0 p
if(random.random() < pm):
1 u& i4 @3 ~$ d- U mpoint = random.randint(0,py-1)
0 A9 a. a/ E- `7 K$ ]* P9 y if(pop[mpoint] == 1):8 m8 {1 n* i$ F( B% J
pop[mpoint] = 09 f- C$ l3 S8 G7 y5 E
else:
r# O6 D" U$ @) S pop[mpoint] = 1
" ~& Y/ `2 \1 F: d! L6 w, k' q( B' N0 [9 L( p. \
, M2 O" Z4 c" K/ m( K' l; E" A
————————————————0 R) Q; C' W7 R# e
版权声明:本文为CSDN博主「simon-zhao」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。( P( K& F3 |) I1 h( ]
原文链接:https://blog.csdn.net/u010902721/article/details/235313590 d- F0 ]% M+ P/ j d
' {! l2 S2 L7 ^1 f2 l( K
. @% r: \5 ?0 I
|
zan
|