1 h) `: G# a; ~; v4、Python代码" Y8 K+ w8 w# d4 k5 ^
#-*- coding:utf-8 -*- ) N2 u! a3 `9 Z% S0 u Z4 A8 ` ! o* x$ b8 q( Z J+ Simport random0 y9 F3 \: u" W8 {% @ S$ s$ B
import math" P! s: n3 Y6 `2 R3 j/ p7 E
from operator import itemgetter1 P! h- ~- k5 q4 P; g+ y
" u" T' w# O/ e. Q$ g" |
class Gene:3 K& n" A5 U! {- L; h; |( c! ~! z2 ^5 |
'''3 p" M2 A# W0 M2 N
This is a class to represent individual(Gene) in GA algorithom 3 q+ X7 J. X4 B2 v; T- i each object of this class have two attribute: data, size ^' _1 f. b& m2 X$ a
'''5 x' i* S! s4 \
def __init__(self,**data):, A/ S5 f( P0 w; X2 P& v
self.__dict__.update(data) 1 L/ j$ B/ b4 E
self.size = len(data['data'])#length of gene* j! G) R3 I- ~/ y8 w6 a0 Y6 X' D
, f! a/ |/ v" t% V+ P1 z" m/ S) ?2 S) w0 k3 c
class GA: 9 j; q, W) c k. N3 o '''! O/ N' _7 g( E: g! E4 m
This is a class of GA algorithm. . ~6 M8 u5 S0 u/ Y/ T ^7 z ''' 7 ^( }& b1 v8 { def __init__(self,parameter): 2 v- i! y4 K% w* t* _+ V. ] ''') K, ~8 l3 D3 o. V
Initialize the pop of GA algorithom and evaluate the pop by computing its' fitness value .) N4 u" |# ]5 h! J, h3 l6 [" t
The data structure of pop is composed of several individuals which has the form like that:" s4 w5 d& v Y! D$ A: D8 b
, X0 S, e- y/ U3 b
{'Gene':a object of class Gene, 'fitness': 1.02(for example)} ) y4 U+ ^. j- o5 G3 K X/ b Representation of Gene is a list: [b s0 u0 sita0 s1 u1 sita1 s2 u2 sita2]% P5 c7 c" o+ P: W8 V
0 C5 y$ C: o% Q3 o3 c
'''8 |6 ?: j- }+ ~9 S! M
#parameter = [CXPB, MUTPB, NGEN, popsize, low, up]5 ~+ @" d0 t7 w$ W4 b' U
self.parameter = parameter " D/ ], ]$ G' x1 s8 |" E Q- Y& I% e8 c/ ?' S/ c8 v. @( D* E
low = self.parameter[4] + W) M* }* X# [, d! S6 h: ? up = self.parameter[5] S) z6 ?# L' t" u/ ] * [, s9 P2 _* p' P3 N6 m1 O$ N8 R& B self.bound = [] 3 {4 @( p' l! F) ? self.bound.append(low)! w4 A9 B4 `; |1 U" [
self.bound.append(up)) h- [: Q% Q4 ?1 O+ _' l
0 U, [; C& X( k0 r
pop = []$ X' I7 \+ H4 I* A p" g
for i in range(self.parameter[3]):/ d* i( Y$ X+ W6 q. Q) a
geneinfo = [] ) x5 i; p7 m1 f7 W for pos in range(len(low)): , A: ?2 l1 Z9 N+ e m8 c4 G geneinfo.append(random.uniform(self.bound[0][pos], self.bound[1][pos]))#initialise popluation. b- [6 r+ x% B# r, i) {( T% r) j
# M( Z% v* d' r8 C7 o fitness = evaluate(geneinfo)#evaluate each chromosome L' M/ @; [# B$ o" Y+ S! a
pop.append({'Gene':Gene(data = geneinfo), 'fitness':fitness})#store the chromosome and its fitness2 J r( N4 O4 ~- K! m0 {9 |1 i
1 C* z2 a5 R! w6 u1 ] self.pop = pop2 }6 a8 |9 C9 X! }
self.bestindividual = self.selectBest(self.pop)#store the best chromosome in the population; y2 A9 C2 W+ p5 }+ q# q3 [
/ E+ g! y U6 H! z( D% E def selectBest(self, pop): 4 E5 j! Y; e! r: u ''' ( a. c$ G! t5 ~" R# e select the best individual from pop0 e* u% Q9 B/ A1 J" n1 j$ K
''' 8 v# K+ W( |/ Q( r s_inds = sorted(pop, key = itemgetter("fitness"), reverse = False) 7 f1 j5 K4 s5 j7 z0 _: `: L return s_inds[0]7 z- ^/ L1 U5 v6 o
1 G- ~+ p- _$ I5 U4 Q
def selection(self, individuals, k): # x4 X( U2 {+ a) e0 Y) u, X '''0 A- ^% O2 d1 ]
select two individuals from pop 5 s3 M( P* l( q ''' 6 L3 Z a& \3 t" ^: c/ w s_inds = sorted(individuals, key = itemgetter("fitness"), reverse=True)#sort the pop by the reference of 1/fitness % R+ b0 l' Q. ]5 [0 x
sum_fits = sum(1/ind['fitness'] for ind in individuals) #sum up the 1/fitness of the whole pop ( b- O: r+ j; K+ z8 E4 O8 J # z, l3 N) x1 A1 x/ m5 B% _8 t chosen = []' _5 P, e" t4 O* P* H* y" j+ d
for i in xrange(k): " |* X$ N5 H( s" b' q- o$ S2 m u = random.random() * sum_fits#randomly produce a num in the range of [0, sum_fits] + g- I. D* G2 w6 | sum_ = 0& D9 E% A1 B I) v
for ind in s_inds:- N8 S) s6 o) k: R* r: W6 t
sum_ += 1/ind['fitness']#sum up the 1/fitness " I5 j( }9 ?2 x) @7 p5 ~# } if sum_ > u:- t8 z9 Y7 [/ N9 M- C
#when the sum of 1/fitness is bigger than u, choose the one, which means u is in the range of [sum(1,2,...,n-1),sum(1,2,...,n)] and is time to choose the one ,namely n-th individual in the pop 5 d5 g% ^5 o' n( a4 l* q7 ~" C chosen.append(ind)8 d% N. K2 l% s
break , r/ t' E: G% x- z- K1 s2 K! q& E* o& p, X
return chosen `, i# M8 ^/ Y, h( S
) Y2 k' d2 m% f; G' n
- b0 R9 d O( t5 z6 B3 c# D
def crossoperate(self, offspring): " m# |6 \+ x! w$ D% Q+ W, d+ ?/ ] '''8 [( a1 v6 U1 I6 x. t7 ~
cross operation 5 g1 `* W* z2 ]( Q '''' Q. l8 q5 L# |$ ~! U4 Q" ^3 u
dim = len(offspring[0]['Gene'].data)' v. o# h6 S8 s
( s0 f& S0 O) }! @) u8 H; A, G
geninfo1 = offspring[0]['Gene'].data#Gene's data of first offspring chosen from the selected pop' k; ^# D3 D4 O
geninfo2 = offspring[1]['Gene'].data#Gene's data of second offspring chosen from the selected pop) s* L# p0 i; Y" b4 d' N. X
+ q( d- q) f8 L pos1 = random.randrange(1,dim)#select a position in the range from 0 to dim-1, 4 h! Z+ I# L% P. c m3 A4 F" c0 y/ B pos2 = random.randrange(1,dim)6 x. B) K8 C9 R& y# k
( G3 ?' i' z# S: K& L' |, f& k newoff = Gene(data = [])#offspring produced by cross operation 5 U+ P3 j* J* t temp = [] / O0 V! x( o, m; d( w for i in range(dim): " m) y- i: H- x$ t% L$ r2 i if (i >= min(pos1,pos2) and i <= max(pos1,pos2)): # G( d) M" i5 L5 i) e/ X, \ temp.append(geninfo2) " c) q7 Y4 R# e+ U) C3 b% @ #the gene data of offspring produced by cross operation is from the second offspring in the range [min(pos1,pos2),max(pos1,pos2)]' W: N& h# T0 ^# G. i! o
else: " R/ w8 U; [# N9 q; l$ i" U* R- q; U temp.append(geninfo1) 0 L8 [/ b/ g% s #the gene data of offspring produced by cross operation is from the frist offspring in the range [min(pos1,pos2),max(pos1,pos2)]* Z0 O, n+ ]& U) s; [& R0 i
newoff.data = temp8 s0 ?; F: p L7 O/ g& Q8 B
' w4 {+ l( t- D* \" c' q: u/ ~ return newoff9 n0 ~- f2 o4 P7 L$ w. A
( f6 K) q3 w1 v- \& B
/ k3 W: q4 }) s( ~' F' R
def mutation(self, crossoff, bound): + c+ I: X( [$ G6 v* {6 T ''' / u& \6 K2 F9 ]0 \, [& X mutation operation 6 F# E/ ~' i3 ?6 M% o# a '''' R; ]* F& k0 n3 R& P
' }) s( l6 y" a7 N2 o7 B
dim = len(crossoff.data)9 P4 D# v" C ]8 Y+ V* g
/ A x( I3 f: v& J( s# r# E pos = random.randrange(1,dim)#chose a position in crossoff to perform mutation. 8 h3 \: P' {$ x% a. R/ o 3 k0 P4 d( U# y* {1 b# ~. H" V crossoff.data[pos] = random.uniform(bound[0][pos],bound[1][pos]) % ~ W' ]: @5 ^, ~ H: l return crossoff, Z- l8 F7 x% m8 i, X
: V3 `1 U; T7 A def GA_main(self): % B1 p0 i$ ]' l' s3 t( `, s' | ''' ) _2 C# K: B$ O; D4 ^ main frame work of GA# X" `* T, ^* z; X4 j
'''( W$ c4 b& s6 V& E
/ A l+ p8 P8 S) a popsize = self.parameter[3] G" [5 @) v/ n2 a( G7 X / y) Y0 n) e$ @ R print("Start of evolution")1 _. N" l, f }' u
" w; Y# L# z7 K8 v7 t! b0 o) z
# Begin the evolution h4 \0 r! H' A
for g in range(NGEN): 6 [1 E( R3 e! ` 9 v7 i9 F* m# Y! B V n# x4 C print("-- Generation %i --" % g) ! m5 u% r( b7 {; I + A( F7 A# E. ]3 _5 Y; I+ ]/ k2 d. }! s #Apply selection based on their converted fitness6 F5 e; u$ p. @, S* p
selectpop = self.selection(self.pop, popsize) 5 ^. J) g6 ^% q) U \! E/ L2 R6 `' P% V
nextoff = [] / @% u/ }# ?0 o4 a
while len(nextoff) != popsize: 0 X/ |/ k8 U3 O. W' F; Q$ H4 A
# Apply crossover and mutation on the offspring + U, I& U8 z; g7 @# C - y. G* `. F+ O& U" q$ _ # Select two individuals 3 b! V7 |3 `" _& b offspring = [random.choice(selectpop) for i in xrange(2)] 3 z1 v3 f& T, J' Z 3 {3 H7 p2 d9 t if random.random() < CXPB: # cross two individuals with probability CXPB & E C5 h: |- N' `0 t; G N+ B crossoff = self.crossoperate(offspring) $ t6 ^5 m* y( g; ` U: R, P5 B) t Q fit_crossoff = evaluate(self.xydata, crossoff.data)# Evaluate the individuals 6 f9 F- L9 o5 j0 e' }
! l" w) q7 H0 w, B, |& v if random.random() < MUTPB: # mutate an individual with probability MUTPB! \, T) \' _: a `
muteoff = self.mutation(crossoff,self.bound)6 ~3 C3 b6 O' y/ k1 S; y9 W
fit_muteoff = evaluate(self.xydata, muteoff.data)# Evaluate the individuals9 T- w. G6 H6 m
nextoff.append({'Gene':muteoff,'fitness':fit_muteoff}) ! m/ k* R' k- k4 _! u" J 9 ?* V8 k/ x9 O9 p. U) O # The population is entirely replaced by the offspring " ]+ v" _) S( g0 X, j3 p6 B$ h self.pop = nextoff - S; L& p& ?! D2 k( ~& B* Q1 Y' r7 e6 q( Q
# Gather all the fitnesses in one list and print the stats& d Y# z' M$ F! F
fits = [ind['fitness'] for ind in self.pop] 4 B/ ~ e. D1 d1 y- H; { g; N- S& W/ ~4 A, {! `
length = len(self.pop)& Y. W' w3 x4 V
mean = sum(fits) / length( _$ r/ `$ O: Y
sum2 = sum(x*x for x in fits) ' f, c. S& J: c4 K7 a std = abs(sum2 / length - mean**2)**0.5 ' ` w/ {. d) O8 l" r; G best_ind = self.selectBest(self.pop)8 L( {6 \7 O1 n% z5 {
9 e9 e$ g( G; g5 D! T$ V4 M& z
if best_ind['fitness'] < self.bestindividual['fitness']:/ t2 h* ?6 t& ~5 R, p, K; E
self.bestindividual = best_ind! e: R8 y8 e, G! o
: f8 p% `# X9 c7 m+ f0 _
print("Best individual found is %s, %s" % (self.bestindividual['Gene'].data,self.bestindividual['fitness']))# Z) E3 Y9 t4 |: J3 S Q& S
print(" Min fitness of current pop: %s" % min(fits)) 8 a$ H: w6 _; n3 v1 I- U: b0 x6 K print(" Max fitness of current pop: %s" % max(fits))* Z) m' b$ M4 p
print(" Avg fitness of current pop: %s" % mean). ]3 E' Z) h2 \9 P- w
print(" Std of currrent pop: %s" % std) a' a' {+ q$ x2 n * g9 S1 z) E+ p! R print("-- End of (successful) evolution --") ' x; z) z) U) f( U9 Q$ Z
0 _) C D0 o5 F7 ]2 V
if __name__ == "__main__":9 S/ v: l- ^2 Y. {2 a" M9 Y. @, d
0 a3 h& t, ?# v( A U5 X; b& D/ M
CXPB, MUTPB, NGEN, popsize = 0.8, 0.3, 50, 100#control parameters 6 g! x) W" v, u# B- M8 b s) f 6 s7 o( m/ i: {9 K up = [64, 64, 64, 64, 64, 64, 64, 64, 64, 64]#upper range for variables. t. [0 r3 k) c
low = [-64, -64, -64, -64, -64, -64, -64, -64, -64, -64]#lower range for variables 5 t: [* l, s6 l$ X/ Y8 ~ parameter = [CXPB, MUTPB, NGEN, popsize, low, up] X$ ]$ D# [" O& A
( {1 q4 D: e0 c run = GA(parameter)6 a% f: v. u* W* s* z
run.GA_main() D! F2 q2 l' `- k& {————————————————1 ?2 ?! N5 E$ [3 D
版权声明:本文为CSDN博主「bible_reader」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。 : {7 K0 z. G; K; r原文链接:https://blog.csdn.net/bible_reader/article/details/72782675 9 A& v- H; X6 ?4 F. i / A/ p7 g! @: z @ w) |: \6 x% L