# b w( i& l3 @2 \$ {4、Python代码& d; K/ k" d! I
#-*- coding:utf-8 -*- ' l5 @. P7 H1 r7 Q% p; a$ \ q- d. w / P! w j1 h- E B$ Q- qimport random 9 }% U, t" d8 \9 A& Yimport math) I* U) `8 b+ d" q0 p: H: _7 B
from operator import itemgetter* E( R5 a3 G2 E! a6 `
( u+ o4 U/ ]+ |class Gene:3 D, x# m: d, j8 {& F
''' ; f. ?+ L# \9 h5 h' @" D This is a class to represent individual(Gene) in GA algorithom0 i1 A L- b+ x+ v: V( b& _# B
each object of this class have two attribute: data, size , J" V2 E( t3 I9 |) B! x ''' 0 {9 s) L( e: T' ^) J0 ]+ @ def __init__(self,**data): $ R1 Y O% ]" A! g4 Q, a# x self.__dict__.update(data) - ~& r4 [" Y, i1 q4 y( y0 Z0 E
self.size = len(data['data'])#length of gene / W S1 T/ i1 c& ~9 C1 y, ^. u( G5 ^3 [
, Y, h- A! B1 uclass GA: ^/ F6 b) d8 @" {3 H
''' * r) |6 g8 } V Z/ j% E This is a class of GA algorithm. & N9 z! q; z! `1 T ''' - E( N7 n& H+ U+ P g1 E& t7 g def __init__(self,parameter):* g1 M& q6 y2 d
''' . Y5 a8 R/ l" F& e Initialize the pop of GA algorithom and evaluate the pop by computing its' fitness value . 5 {- Q6 G4 e7 B; }% T The data structure of pop is composed of several individuals which has the form like that: + d1 ]" R- ]; B& V$ G$ z/ F5 S
{'Gene':a object of class Gene, 'fitness': 1.02(for example)} - B2 q, V/ B& y8 N+ V n4 \% o2 P Representation of Gene is a list: [b s0 u0 sita0 s1 u1 sita1 s2 u2 sita2] - q4 ^& E5 ?2 y2 b( S- l/ P0 w2 m' u( A: G+ U9 t4 M8 ]7 i
''' 2 F" Z$ g( s2 q* | #parameter = [CXPB, MUTPB, NGEN, popsize, low, up]- g. t- ]# H4 D8 d$ Z
self.parameter = parameter - h. L/ q' s o- v8 ~4 }- ] Z1 E0 `& t
low = self.parameter[4]! w; D, _! `- s" S% v
up = self.parameter[5] ( g2 P; J/ Y- Z* n$ g! i1 C4 L) l- n. d/ ?& _
self.bound = [] # k' Z: o; \& O$ g' a self.bound.append(low)$ R! N$ }: V& \: o {8 `# B+ y$ @7 B
self.bound.append(up) 4 c' w! T, w0 \/ g9 X S; n; G! d9 L1 c$ f2 e
pop = []- `% G; b5 J) f% i/ I1 S" D
for i in range(self.parameter[3]):2 x2 i( v7 ?6 u
geneinfo = []* P+ y1 ?, A3 c' N, T, D6 {9 p
for pos in range(len(low)): 9 S* v% T' {1 K4 F4 ? geneinfo.append(random.uniform(self.bound[0][pos], self.bound[1][pos]))#initialise popluation ' r# j9 @ }9 w, G 6 k5 {! N/ _+ A6 x- a fitness = evaluate(geneinfo)#evaluate each chromosome . h; \3 R( e" u6 @: i# p2 s& X pop.append({'Gene':Gene(data = geneinfo), 'fitness':fitness})#store the chromosome and its fitness6 f. M3 w0 V4 W) r& Q3 Z
( d1 E" D1 U# A9 {* C
self.pop = pop 3 l) j0 i- D+ U8 k6 V( h self.bestindividual = self.selectBest(self.pop)#store the best chromosome in the population $ u3 m6 Y6 @, U& X; ?' a- D2 ~: R1 v: `% ?9 \2 ]
def selectBest(self, pop): , e0 I# }7 a N: f- {5 K ''' m* S' w' W# a W
select the best individual from pop : G+ N; D# d. ~+ x8 Z. k% M ''' : z7 Y F8 |9 h- P; v5 Q s_inds = sorted(pop, key = itemgetter("fitness"), reverse = False) " a! y5 b8 l! }$ f( K, K return s_inds[0]3 `: p- `# P/ |$ g" s* f3 s
$ u4 ]% `% h+ ~0 _7 Z9 H! l
def selection(self, individuals, k): 5 p9 X$ n) r4 c# L ''' 0 \2 B" {2 V. o& ` select two individuals from pop: p* [& P ?# v' y4 x) n
'''" {' o+ p4 F/ v- e& q q, t
s_inds = sorted(individuals, key = itemgetter("fitness"), reverse=True)#sort the pop by the reference of 1/fitness * B" |) o6 h) t9 c7 ^) J sum_fits = sum(1/ind['fitness'] for ind in individuals) #sum up the 1/fitness of the whole pop * `$ K3 l: l8 Q0 _; \# ^8 |9 G: k1 w* a2 f! ^& R: ?, `9 M
chosen = [] # r `: S# {" j) E, K I3 Z6 Y for i in xrange(k): + F% `' A/ S( m# s3 w- c u = random.random() * sum_fits#randomly produce a num in the range of [0, sum_fits]+ ~; `) V1 y$ W0 p; z. {8 r+ z; M: B
sum_ = 0 ) V( F. m7 C1 k+ k, e& Q9 g5 | for ind in s_inds: ) ^1 y3 Q0 {" i9 M$ B2 H$ l sum_ += 1/ind['fitness']#sum up the 1/fitness1 v( M' Q5 B7 ~/ A3 C
if sum_ > u:( W- `4 j" }" T* \
#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 & f; c* |2 v/ } t2 D2 u9 C chosen.append(ind) 7 h' c# F# T) S- Z, j% T break, F: ?8 z% O. E" O* D8 G
) }" ^9 K2 N0 R- g$ }$ _ return chosen 9 |. }# R% \/ W" I" R. r( K/ U
. W% t i$ u' `
% @$ w. W8 ?8 [$ c( @ j) B! g
def crossoperate(self, offspring):) k) o" Z* d$ e6 a2 _4 H
'''' O2 |% D. k' e6 `) z
cross operation+ u0 {- z# H }9 f# x
''' ; I# ]" d6 `3 e% f$ T! U9 t dim = len(offspring[0]['Gene'].data) $ @) }2 N6 O8 W, \/ M3 s( ]0 g/ B$ t( V7 y2 H. ~6 c, a1 k. U
geninfo1 = offspring[0]['Gene'].data#Gene's data of first offspring chosen from the selected pop * ?: ^, |4 u1 S; [" J, @4 K geninfo2 = offspring[1]['Gene'].data#Gene's data of second offspring chosen from the selected pop9 T' k7 |% ^$ [% P/ [0 o3 f8 _
1 w; ~6 H) c7 d
pos1 = random.randrange(1,dim)#select a position in the range from 0 to dim-1, . J) H8 A- K4 K& b7 o: N+ F5 Y pos2 = random.randrange(1,dim) : o8 s8 a* p9 Y* p7 {" L( u % U" d: F7 Z. N$ j1 q newoff = Gene(data = [])#offspring produced by cross operation + ]6 y0 f9 G6 x6 i% i temp = [] 8 g6 ]) x( L7 b% Y1 v4 i for i in range(dim): 7 d, d; j6 t( h( \4 `, _) z5 C if (i >= min(pos1,pos2) and i <= max(pos1,pos2)): 8 l+ r' Z& M# W; a temp.append(geninfo2) . l2 }+ ]' S, w( u& P0 \+ h& v #the gene data of offspring produced by cross operation is from the second offspring in the range [min(pos1,pos2),max(pos1,pos2)] + \$ j7 C4 N- @) R$ ~1 O else:; F; B$ C, m" v) q1 ?' S( U
temp.append(geninfo1) 9 I3 j+ Z# {$ z( N #the gene data of offspring produced by cross operation is from the frist offspring in the range [min(pos1,pos2),max(pos1,pos2)]$ }3 o, g" }# p ^' e) H# d4 q
newoff.data = temp 7 Z. o" a1 `3 X$ Z4 ~7 }8 l- D, W. K& x* ]# H$ `* v; k' ?
return newoff0 J3 b9 l' _2 h1 x6 y& P
6 S i. ~9 v+ [, r9 L3 m4 W& d
6 E0 x3 E9 r2 Z
def mutation(self, crossoff, bound): 0 X$ f9 W2 [6 P ''' - H: B- Z2 A5 C$ b1 O mutation operation & j9 O5 f5 D9 E# W '''. ~& k$ E; c- C4 @* v9 J
- H8 _: r; `5 ~ j dim = len(crossoff.data) 8 e! g& ?( P' U c& _; B! r + h7 e W: n2 B pos = random.randrange(1,dim)#chose a position in crossoff to perform mutation." C7 \# o; W* S
4 H+ ?2 d% t/ ~. g k1 |" E7 j' A
crossoff.data[pos] = random.uniform(bound[0][pos],bound[1][pos])2 ^, } I7 h4 r) Y8 z2 F
return crossoff/ K2 L- Q+ X5 @% K8 j% z
$ J% |# P. h b: R! O
def GA_main(self): ( R [6 W; M2 \. q! D0 @: n% w" ` '''5 V h2 h- o3 a$ ]0 s
main frame work of GA 9 M+ }& ]5 L' B4 D0 q/ E6 { '''# N. f5 z1 H) q* Q) F
, |0 K* M. ]. B- S+ z/ K8 k' T print("Start of evolution") & } T/ `; @7 u _; `+ i9 |4 O- X# s 4 Q( v2 N$ N9 w0 w # Begin the evolution9 N1 o0 X5 |. B/ t: `/ G: l
for g in range(NGEN):2 c3 L/ a6 p, T8 N# {
+ [2 W9 c5 H, [4 h: Q$ o1 E5 `% M print("-- Generation %i --" % g) & O8 n* L0 p w% m1 ~$ _8 p7 V
k$ i4 V' H% w d D #Apply selection based on their converted fitness7 @" M% A: {' z( ~- ~ W: L. z4 y
selectpop = self.selection(self.pop, popsize) % p1 z0 S3 ?- z8 ]+ C : J3 I& i3 X$ D/ j+ K nextoff = [] ! j8 V/ v/ e$ ^6 N8 r' u R while len(nextoff) != popsize: : p/ _" M3 J- I1 { # Apply crossover and mutation on the offspring 4 _/ D8 K' U* b0 c% H3 R5 E8 f+ x+ K0 R9 R3 y: j
# Select two individuals$ i6 C( n$ |! y" o5 y) m/ T: q& M
offspring = [random.choice(selectpop) for i in xrange(2)]9 c Q L9 }% X$ r
& D( h1 d" \1 A
if random.random() < CXPB: # cross two individuals with probability CXPB* k2 A7 \/ c9 }+ W0 h: i
crossoff = self.crossoperate(offspring)- k. v( \' ~- N+ K. X6 d/ i
fit_crossoff = evaluate(self.xydata, crossoff.data)# Evaluate the individuals " a1 b$ N$ R: _3 E5 K% e. s
0 U- m% `. {, s2 {% a if random.random() < MUTPB: # mutate an individual with probability MUTPB ' x! v) h. P- }3 Z0 M muteoff = self.mutation(crossoff,self.bound) / l: C; f* e7 s2 O/ }. i7 w fit_muteoff = evaluate(self.xydata, muteoff.data)# Evaluate the individuals" O3 l2 K8 V( ?( A; }
nextoff.append({'Gene':muteoff,'fitness':fit_muteoff}) + R1 M1 d! X! i$ F T* d9 K9 q) k8 S# c
# The population is entirely replaced by the offspring * L4 I( h' p9 \" F self.pop = nextoff& f* L; k; _& ~9 l
# I2 w- e# B- g& e" ]4 o; E' d- l # Gather all the fitnesses in one list and print the stats, e1 i9 X; W# e
fits = [ind['fitness'] for ind in self.pop]; w5 z4 _' i f! l& H
% t: r7 L5 v- w( v" T. J+ ?+ E length = len(self.pop)( Z" ?) n. k0 e L D3 T( p
mean = sum(fits) / length % o- a- a' e1 R sum2 = sum(x*x for x in fits)! e4 w B4 J+ r/ f; Z0 r, b; O
std = abs(sum2 / length - mean**2)**0.54 \3 |/ l8 |8 I. H. y
best_ind = self.selectBest(self.pop) 5 _3 }1 L/ J6 f; b. `) i. u* N$ o2 ^' u2 y/ W" i4 H8 ^5 V$ W! N5 G
if best_ind['fitness'] < self.bestindividual['fitness']:0 r1 l1 S# u* F: n9 F1 K8 A2 }
self.bestindividual = best_ind 4 R) S# c# M) \. {; z# c [2 h2 \7 r: C) x8 D' r& C1 F
print("Best individual found is %s, %s" % (self.bestindividual['Gene'].data,self.bestindividual['fitness']))+ _# C1 L) R% u( }
print(" Min fitness of current pop: %s" % min(fits))& ]5 r7 f( X& ?. p4 x; p
print(" Max fitness of current pop: %s" % max(fits)) 1 _7 _* r, K; F. u print(" Avg fitness of current pop: %s" % mean)" C3 Z- ]) c1 a8 ?" J' _; h4 e
print(" Std of currrent pop: %s" % std) / Z d7 g% Q9 K9 V7 D/ }% T+ c3 s6 X4 H5 v3 ~
print("-- End of (successful) evolution --") 5 ]/ M$ U! n/ `: E5 h
+ X( ^ t' r4 b: d$ Eif __name__ == "__main__":4 ]8 O3 l) `3 R9 h; p
* ?' u$ r9 Y8 @% l+ ?8 j$ ?# B5 r
CXPB, MUTPB, NGEN, popsize = 0.8, 0.3, 50, 100#control parameters $ Y) B: }2 j2 ^ s5 q; V8 d/ }/ }; ^9 p7 f
up = [64, 64, 64, 64, 64, 64, 64, 64, 64, 64]#upper range for variables , d/ E: H/ }0 \4 r, w! l' c* @! a low = [-64, -64, -64, -64, -64, -64, -64, -64, -64, -64]#lower range for variables( ^6 s; r) i" s1 z' {
parameter = [CXPB, MUTPB, NGEN, popsize, low, up]( r( I' D- f+ n3 {& V& S9 D
. C7 j* o9 w% g5 A5 g" m
run = GA(parameter)/ N& [; C! s. s! `! E4 [; E% t+ \& L
run.GA_main()- A; d, m8 g$ n" X( ^
————————————————2 x+ G; y; H+ v3 @% X( X4 A
版权声明:本文为CSDN博主「bible_reader」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。 & q! ?) \* m) t- y原文链接:https://blog.csdn.net/bible_reader/article/details/72782675 7 P8 e$ H# D e' J' w$ W! W. R . d) q) o! ?5 s2 Y3 d/ Q5 E3 i* n 0 T1 ~' u# H2 g$ U. v