! U; `7 l' Q* @- M6 Q# m/ P# Q4、Python代码 8 y0 y% e/ b% ^; R4 y#-*- coding:utf-8 -*-0 @. b$ J3 u$ F/ C7 j% N- A6 y
7 E8 c. U9 W& u1 a! z0 M/ I
import random) `; n# p" k8 I+ I, z6 s
import math- D2 t% d/ X2 o9 N! }
from operator import itemgetter 1 C; S" m8 w" r; i( {" G" c; D1 X/ c+ t( V
class Gene:' i/ k& g0 o2 W0 I% d) x
''' ( W$ d# m% E& }: Q! M% f This is a class to represent individual(Gene) in GA algorithom$ H. }" a! v3 p5 A4 F" k
each object of this class have two attribute: data, size / j4 d9 ~# z/ a& U, \7 @ '''0 W: Z" L4 `; j' }
def __init__(self,**data): , ^, ^# u2 m9 g self.__dict__.update(data) * k0 [: i; N3 t& e
self.size = len(data['data'])#length of gene & b; w" e% g0 E1 p$ h' @ Y l% `. L3 u3 A& G( _8 |5 [
9 f3 |. n* D, M" G: C$ c8 @
class GA: 1 K1 X* K& ^9 e& M4 B Z; ~2 u( v '''& m. P3 D% k6 l8 z/ e
This is a class of GA algorithm. " @9 b {2 o0 r. v( A. A '''8 J% x. ?* c* |4 P+ d
def __init__(self,parameter): ) s. G8 `% t2 l '''+ E. S: P3 z5 L, x9 f
Initialize the pop of GA algorithom and evaluate the pop by computing its' fitness value .) n B- k; g' V3 j
The data structure of pop is composed of several individuals which has the form like that:# U' z% F( ?8 p
" \* r( W" `0 G2 Q9 X6 l/ s {'Gene':a object of class Gene, 'fitness': 1.02(for example)} $ K" M: Z' i2 } Representation of Gene is a list: [b s0 u0 sita0 s1 u1 sita1 s2 u2 sita2]+ m. u8 ^6 ?% {5 g$ z9 M: W
& I4 f" \2 S. X" d/ f. C '''7 M/ p. ?. E+ `. y' L, |" d+ l
#parameter = [CXPB, MUTPB, NGEN, popsize, low, up]/ N3 u9 u) n/ q, t& e
self.parameter = parameter + [! R1 N R$ u$ T6 n2 I0 h& S6 U7 a
low = self.parameter[4] ) ?* [0 \4 L8 w7 K' S up = self.parameter[5] ! X# E: h( X0 ~9 I0 z0 {2 M ' @! P0 s: h1 w" D3 `, O+ s self.bound = [] - l5 E) t0 c6 j N0 W self.bound.append(low)* L$ V j& i2 t7 B9 D* P/ R* L
self.bound.append(up) 4 |/ j3 ~2 f8 o5 w1 x; b0 }3 k$ X: v3 `+ f* R9 E0 g6 w
pop = []4 r9 s& z. I1 F& \1 ]
for i in range(self.parameter[3]): 5 q; |7 ?$ t3 Q: N7 V geneinfo = [] ) B' o! Y3 I4 }( Y* j for pos in range(len(low)):1 k0 @% H" {/ j, u* W! ^9 M
geneinfo.append(random.uniform(self.bound[0][pos], self.bound[1][pos]))#initialise popluation, o* D6 l% i$ {
$ @& M( E: ^2 W; e9 y fitness = evaluate(geneinfo)#evaluate each chromosome6 a9 ~0 L y5 L0 [- p1 h' n( {. i9 G
pop.append({'Gene':Gene(data = geneinfo), 'fitness':fitness})#store the chromosome and its fitness 1 V/ H2 ^/ Z: C7 Q8 [4 w% S, Q$ b ' M( M8 e+ {" c ~' _' V* U9 | self.pop = pop + k" ?# J. ?$ f6 Z( D" ] self.bestindividual = self.selectBest(self.pop)#store the best chromosome in the population4 {3 {+ ]3 ~" r, Q4 B. |
+ n0 j/ ]4 ]" D# B
def selectBest(self, pop): ( m/ `8 H7 j! t- V ''') O$ Y$ J& W3 F
select the best individual from pop * j! i4 b2 s" s6 R! n6 H '''- Y# Y- T6 g$ L8 _: F0 _
s_inds = sorted(pop, key = itemgetter("fitness"), reverse = False) / }- Q; H+ e# q+ E m; ^' U# B return s_inds[0]9 U4 b i. F# [4 }
, r N+ j, {5 ^+ { def selection(self, individuals, k):* F1 {* J" t3 y; v% C+ P
'''% f8 Y9 M) P3 t/ A
select two individuals from pop + P) l4 \3 v8 V4 i1 o, [) z ''' ' r! w: b; h, i. M2 V& R1 @/ D s_inds = sorted(individuals, key = itemgetter("fitness"), reverse=True)#sort the pop by the reference of 1/fitness 2 y* i& I L( @! V
sum_fits = sum(1/ind['fitness'] for ind in individuals) #sum up the 1/fitness of the whole pop' Z) A0 M( _) O3 b* Q6 q
) E( a1 e& y& H& y4 U! t chosen = []0 U! `" e& M8 G6 y- \6 @- S9 ~
for i in xrange(k): / Y R7 c! V8 h6 h; R( M! e u = random.random() * sum_fits#randomly produce a num in the range of [0, sum_fits] 7 a' B$ N# ]5 K) r8 ?9 Z/ L4 C+ b sum_ = 0 1 x5 f1 x# I4 M# _# q) y5 k# x for ind in s_inds: ' v2 i% n# ^2 H' |3 D k sum_ += 1/ind['fitness']#sum up the 1/fitness ) h" l( s( F7 p! l if sum_ > u:+ \- T6 ~# J: d& G: Y
#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 ! T Y! z0 I: Z0 R& o2 v chosen.append(ind) / Y. L" h4 I, Z5 B2 w @ break4 n4 A# W0 T* B, K: H: Z
9 {8 |: `* o6 m' Z. g" h return chosen $ E- w* j( f+ v! o- f" w, f- D* e/ }; z* J0 b7 |* V
* @ T% t9 R2 k' K& U( X! C# W
def crossoperate(self, offspring): " }: M* ]4 e8 z% }0 h9 k '''7 S, l, I6 t5 g2 d2 V
cross operation 6 s: a4 G* X |$ l6 }" o '''; |, g8 v: s/ J _5 ] y, p
dim = len(offspring[0]['Gene'].data)) N( M1 s: A3 ~( p' v
5 h* @+ i# @. g; N$ h: Y$ i geninfo1 = offspring[0]['Gene'].data#Gene's data of first offspring chosen from the selected pop, O3 j1 F5 G0 d+ G1 }" I
geninfo2 = offspring[1]['Gene'].data#Gene's data of second offspring chosen from the selected pop3 C0 ]- \+ o+ c5 L% ^$ k0 O& b
- f( T/ T$ t* o
pos1 = random.randrange(1,dim)#select a position in the range from 0 to dim-1, & g$ e/ F7 W. s pos2 = random.randrange(1,dim). Y# F2 J! D0 K G
& P8 m0 w6 t) K" U9 u newoff = Gene(data = [])#offspring produced by cross operation - X: r9 Q- r! o+ l. M temp = []9 v: S# w" U( e! s, ?3 ~
for i in range(dim): . g4 [" `2 Z. u7 P' @) m) m4 p+ d if (i >= min(pos1,pos2) and i <= max(pos1,pos2)):& v6 _( h$ v8 J: B1 b1 Z
temp.append(geninfo2) + u3 h. w( Q: e #the gene data of offspring produced by cross operation is from the second offspring in the range [min(pos1,pos2),max(pos1,pos2)]' H$ [) q8 `/ q7 {- a
else:1 _# _/ E6 U2 t
temp.append(geninfo1)8 B1 H1 d5 W# V7 s4 g, U# I
#the gene data of offspring produced by cross operation is from the frist offspring in the range [min(pos1,pos2),max(pos1,pos2)]5 I9 A* r0 `# }, [
newoff.data = temp( T3 V* @' n- y
' _8 }6 F2 Q a M
return newoff" D' |/ Z* f5 R" X
. H5 p: y7 w/ e+ o2 O
4 |& `) T: v9 u' T
def mutation(self, crossoff, bound):' f* h7 b. ~( Q* S1 q- ^
'''7 c' D" x" ]1 g v, h- t
mutation operation $ ]2 u1 l5 G) Q, R ''' * {: a% S2 ]+ }# r7 S7 _( t$ k" g 8 J1 p6 P" p: q dim = len(crossoff.data) . N$ [6 b- y/ t, K , a/ X# ?1 d. X3 M9 L% p pos = random.randrange(1,dim)#chose a position in crossoff to perform mutation. * Y1 w) u$ f: I k$ j% J! H I: H$ R! @$ U5 M5 X
crossoff.data[pos] = random.uniform(bound[0][pos],bound[1][pos]) & L0 z1 c1 M4 l! O% X return crossoff 5 T3 Q6 e$ T( h9 { w# T* P2 v: f7 o8 J; f2 X, p& h" G
def GA_main(self): ( z5 q Q/ ?. M; m; T5 I ''' $ q5 i( e$ m- P, m8 s5 l+ m main frame work of GA& E+ n8 _) O; z% y" k
'''+ e) B: ? x$ R; v/ T
8 V( x' M% e$ [4 {' Q( v6 I6 o
popsize = self.parameter[3]* r4 M& m6 u6 B
; l) M7 A/ Y1 ?* g5 ` print("Start of evolution") 7 z0 r' \; D' h+ \: o z ( n( Y$ d Q; H9 b# ?* ?5 s/ i # Begin the evolution! A t5 ?. u2 [: \- K [: W9 N
for g in range(NGEN):) V- G/ ~% n4 Z+ i9 K2 W2 v) P
; N4 t; M. a! g0 Y' P3 w: c; c print("-- Generation %i --" % g) / ], m; }8 ^- U/ f3 m/ t* [ 9 |0 p G0 y3 {% ` #Apply selection based on their converted fitness" g! v8 I$ V2 O: X& ?+ G
selectpop = self.selection(self.pop, popsize) ) W2 s' X1 @ i$ X$ d9 u 3 o6 y: ?% H9 D8 Z% Q9 w nextoff = [] 6 E* U$ b( W9 c while len(nextoff) != popsize: 5 U) f% l, g; p% x- _" c6 \+ j* B # Apply crossover and mutation on the offspring 0 q. g, \' J* k( B$ g& V. T
6 M& {) w* R# z6 l) W* R. J) i # Select two individuals6 f5 Z$ Q* k- v
offspring = [random.choice(selectpop) for i in xrange(2)] f& _! Q- S! v2 I: @* @( i D7 c5 D$ S+ T/ k5 y
if random.random() < CXPB: # cross two individuals with probability CXPB9 u2 y2 K# _0 H- U4 z: G! c/ ?3 C) {
crossoff = self.crossoperate(offspring) ) ~/ K8 S+ a/ E5 _. N3 }, w3 F. [ fit_crossoff = evaluate(self.xydata, crossoff.data)# Evaluate the individuals ; o* P! \3 H B1 Z% m- A& h/ w2 m . W7 f: v0 F( C, [/ d if random.random() < MUTPB: # mutate an individual with probability MUTPB # P B8 j. N% X muteoff = self.mutation(crossoff,self.bound) ! t$ [) {( F/ {8 X9 _0 g ?9 U fit_muteoff = evaluate(self.xydata, muteoff.data)# Evaluate the individuals+ y# b7 ]7 `: I+ x2 x; ^( f
nextoff.append({'Gene':muteoff,'fitness':fit_muteoff})' T+ k4 q8 o! u8 W
3 n; C) v: \6 o8 {2 F/ n: d! h8 P
# The population is entirely replaced by the offspring 1 h+ A+ {; j0 _% D- z5 z self.pop = nextoff : p) k3 o" P2 U2 s8 s$ _ & u" _; d3 f3 S3 N$ g5 N, N2 {; c; N0 f # Gather all the fitnesses in one list and print the stats( H5 `$ V* b r1 | G2 w. ?
fits = [ind['fitness'] for ind in self.pop], E% s5 u5 z3 E3 R
6 |6 t8 p6 v& O" E$ ?, Y; n
length = len(self.pop) 1 _1 w% i3 e3 v, v+ u' ? i mean = sum(fits) / length , Q3 s1 i* e9 G; E- h p sum2 = sum(x*x for x in fits), c0 i! z6 N9 m& B
std = abs(sum2 / length - mean**2)**0.5; z& I. c# B, r, I! K
best_ind = self.selectBest(self.pop) 8 T( P; Q$ f9 i- n% `# {) K P% I7 d x4 v
if best_ind['fitness'] < self.bestindividual['fitness']:5 ?7 J. H* O* v" g- W5 C% e( _, t E
self.bestindividual = best_ind ( I9 n3 z2 v( X& i6 S \$ c- K) K6 Q) A% t; b
print("Best individual found is %s, %s" % (self.bestindividual['Gene'].data,self.bestindividual['fitness'])) " y ?# h; t5 o, N$ Y3 F0 x6 ? print(" Min fitness of current pop: %s" % min(fits)) , z: j4 {: Q6 b. v: J) R print(" Max fitness of current pop: %s" % max(fits)) $ r" X# ?# g" S: k4 w print(" Avg fitness of current pop: %s" % mean)/ o0 w! r0 M- l9 {9 u) ?$ v
print(" Std of currrent pop: %s" % std)0 Z* E) Q5 U% L: s9 M
# }$ k$ n. l& ~* N7 i print("-- End of (successful) evolution --") ( _* n, P8 }& F8 t" F: q
# `% K1 e% F; P$ A+ s9 }3 \4 bif __name__ == "__main__":; ]4 k" x' V8 [& R! ]
/ N; o. y7 y w2 T; `( ~, h& X& J
CXPB, MUTPB, NGEN, popsize = 0.8, 0.3, 50, 100#control parameters , n* A( x! T( v' r+ A8 m) K 9 n. X/ ?* P) L. S; k$ _/ n up = [64, 64, 64, 64, 64, 64, 64, 64, 64, 64]#upper range for variables " B- N+ k- L, _ low = [-64, -64, -64, -64, -64, -64, -64, -64, -64, -64]#lower range for variables. V$ [; ?/ M2 H* _8 Z; w
parameter = [CXPB, MUTPB, NGEN, popsize, low, up]! ^- ^* w/ C( l5 l. Q
# f8 x( C& Z" _2 P0 h
run = GA(parameter) ; v- }* X7 t( _* ^, _) s6 Y( b run.GA_main() 1 d' j8 d* L- f" b& v————————————————- |! @3 o3 y( c0 \
版权声明:本文为CSDN博主「bible_reader」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。 . m* j* P+ }) \' k3 r原文链接:https://blog.csdn.net/bible_reader/article/details/727826757 ^* V: m6 _' a) v- X; A( L$ w; l