服务器之家

服务器之家 > 正文

遗传算法python版

时间:2021-01-22 00:55     来源/作者:bible_reader

本文实例为大家分享了python遗传算法的具体代码,供大家参考,具体内容如下

1、基本概念

遗传算法python版

遗传算法(ga)是最早由美国holland教授提出的一种基于自然界的“适者生存,优胜劣汰”基本法则的智能搜索算法。该法则很好地诠释了生物进化的自然选择过程。遗传算法也是借鉴该基本法则,通过基于种群的思想,将问题的解通过编码的方式转化为种群中的个体,并让这些个体不断地通过选择、交叉和变异算子模拟生物的进化过程,然后利用“优胜劣汰”法则选择种群中适应性较强的个体构成子种群,然后让子种群重复类似的进化过程,直到找到问题的最优解或者到达一定的进化(运算)时间。

ga算法中的几个重要名词概念。

个体(染色体):自然界中一个个体(染色体)代表一个生物,在ga算法中,个体(染色体)代表了具体问题的一个解。

遗传算法python版

基因:在ga算法中,基因代表了具体问题解的一个决策变量,问题解和染色体中基因的对应关系如下所示:

遗传算法python版

种群:多个个体即组成一个种群。ga算法中,一个问题的多组解即构成了问题的解的种群。

2、主要步骤

ga算法的基本步骤如下:

step 1. 种群初始化。选择一种编码方案然后在解空间内通过随机生成的方式初始化一定数量的个体构成ga的种群。

step 2. 评估种群。利用启发式算法对种群中的个体(矩形件的排入顺序)生成排样图并依此计算个体的适应函数值(利用率),然后保存当前种群中的最优个体作为搜索到的最优解。

step 3. 选择操作。根据种群中个体的适应度的大小,通过轮盘赌或者期望值方法,将适应度高的个体从当前种群中选择出来。

step 4. 交叉操作。将上一步骤选择的个体,用一定的概率阀值pc控制是否利用单点交叉、多点交叉或者其他交叉方式生成新的交叉个体。

step 5. 变异操作。用一定的概率阀值pm控制是否对个体的部分基因执行单点变异或多点变异。

step 6. 终止判断。若满足终止条件,则终止算法,否则返回step 2。

流程图如下所示:

遗传算法python版

3、主要操作介绍

3.1 种群初始化

种群的初始化和具体的问题有关。比如一个问题有n个决策变量{x1,x2,…,xn}。每个决策变量有取值范围:下界{l1,l2,…,ln}和上界{u1,u2,…,un},则种群中个体的初始化即随机地在决策变量的取值范围内生成各个决策变量的值:xj={x1,x2,...,xn},其中xi属于范围(li,ui)内。所有的个体即构成种群。当每个个体都初始化后,即种群完成初始化。

3.2 评价种群

种群的评价即计算种群中个体的适应度值。假设种群populationpopsize个个体。依次计算每个个体的适应度值及评价种群。

3.3 选择操作

ga算法中常见的选择操作有轮盘赌方式:种群中适应度值更优的个体被选择的概率越大。假设popsize=4,按照如下表达式计算各个个体的被选择概率的大小,然后用圆饼图表示如下。

p(xj) = fit(xj)/(fit(x1)+fit(x2)+fit(x3)+fit(x4)),j=1,2,3,4

遗传算法python版

当依据轮盘赌方式进行选择时,则概率越大的越容易被选择到。

3.4 交叉操作

交叉操作也有许多种:单点交叉,两点交叉等。此处仅讲解一下两点交叉。首先利用选择操作从种群中选择两个父辈个体parent1和parent2,然后随机产生两个位置pos1和pos2,将这两个位置中间的基因位信息进行交换,便得到下图所示的off1和off2两个个体,但是这两个个体中一般会存在基因位信息冲突的现象(整数编码时),此时需要对off1和off2个体进行调整:off1中的冲突基因根据parent1中的基因调整为parent2中的相同位置处的基因。如off1中的“1”出现了两次,则第二处的“1”需要调整为parent1中“1”对应的parent2中的“4”,依次类推处理off1中的相冲突的基因。需要注意的是,调整off2,则需要参考parent2。

遗传算法python版

3.5 变异操作

变异操作的话,根据不同的编码方式有不同的变异操作。

如果是浮点数编码,则变异可以就染色体中间的某一个基因位的信息进行变异(重新生成或者其他调整方案)。

遗传算法python版

如果是采用整数编码方案,则一般有多种变异方法:位置变异和符号变异。

位置变异: 

遗传算法python版

符号变异: 

遗传算法python版

4、python代码

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
#-*- coding:utf-8 -*-
 
import random
import math
from operator import itemgetter
 
class gene:
 '''''
 this is a class to represent individual(gene) in ga algorithom
 each object of this class have two attribute: data, size
 '''
 def __init__(self,**data):
  self.__dict__.update(data)  
  self.size = len(data['data'])#length of gene
         
   
class ga:
 '''''
 this is a class of ga algorithm.
 '''
 def __init__(self,parameter):
  '''''
  initialize the pop of ga algorithom and evaluate the pop by computing its' fitness value .
  the data structure of pop is composed of several individuals which has the form like that:
   
  {'gene':a object of class gene, 'fitness': 1.02(for example)}
 
  representation of gene is a list: [b s0 u0 sita0 s1 u1 sita1 s2 u2 sita2]
   
  '''
  #parameter = [cxpb, mutpb, ngen, popsize, low, up]
  self.parameter = parameter
 
  low = self.parameter[4]
  up = self.parameter[5]
   
  self.bound = []
  self.bound.append(low)
  self.bound.append(up)
   
  pop = []
  for i in range(self.parameter[3]):
   geneinfo = []
   for pos in range(len(low)):
    geneinfo.append(random.uniform(self.bound[0][pos], self.bound[1][pos]))#initialise popluation
     
   fitness = evaluate(geneinfo)#evaluate each chromosome
   pop.append({'gene':gene(data = geneinfo), 'fitness':fitness})#store the chromosome and its fitness
    
  self.pop = pop
  self.bestindividual = self.selectbest(self.pop)#store the best chromosome in the population
   
 def selectbest(self, pop):
  '''''
  select the best individual from pop
  '''
  s_inds = sorted(pop, key = itemgetter("fitness"), reverse = false)
  return s_inds[0]
   
 def selection(self, individuals, k):
  '''''
  select two individuals from pop
  '''
  s_inds = sorted(individuals, key = itemgetter("fitness"), reverse=true)#sort the pop by the reference of 1/fitness
  sum_fits = sum(1/ind['fitness'] for ind in individuals) #sum up the 1/fitness of the whole pop
   
  chosen = []
  for i in xrange(k):
   u = random.random() * sum_fits#randomly produce a num in the range of [0, sum_fits]
   sum_ = 0
   for ind in s_inds:
    sum_ += 1/ind['fitness']#sum up the 1/fitness
    if sum_ > u:
     #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
     chosen.append(ind)
     break
   
  return chosen 
 
 
 def crossoperate(self, offspring):
  '''''
  cross operation
  '''
  dim = len(offspring[0]['gene'].data)
 
  geninfo1 = offspring[0]['gene'].data#gene's data of first offspring chosen from the selected pop
  geninfo2 = offspring[1]['gene'].data#gene's data of second offspring chosen from the selected pop
   
  pos1 = random.randrange(1,dim)#select a position in the range from 0 to dim-1,
  pos2 = random.randrange(1,dim)
 
  newoff = gene(data = [])#offspring produced by cross operation
  temp = []
  for i in range(dim):
   if (i >= min(pos1,pos2) and i <= max(pos1,pos2)):
    temp.append(geninfo2[i])
    #the gene data of offspring produced by cross operation is from the second offspring in the range [min(pos1,pos2),max(pos1,pos2)]
   else:
    temp.append(geninfo1[i])
    #the gene data of offspring produced by cross operation is from the frist offspring in the range [min(pos1,pos2),max(pos1,pos2)]
  newoff.data = temp
   
  return newoff
 
 
 def mutation(self, crossoff, bound):
  '''''
  mutation operation
  '''
   
  dim = len(crossoff.data)
 
  pos = random.randrange(1,dim)#chose a position in crossoff to perform mutation.
 
  crossoff.data[pos] = random.uniform(bound[0][pos],bound[1][pos])
  return crossoff
  
 def ga_main(self):
  '''''
  main frame work of ga
  '''
   
  popsize = self.parameter[3]
   
  print("start of evolution")
   
  # begin the evolution
  for g in range(ngen):
    
   print("-- generation %i --" % g) 
      
   #apply selection based on their converted fitness
   selectpop = self.selection(self.pop, popsize) 
 
   nextoff = [] 
   while len(nextoff) != popsize: 
    # apply crossover and mutation on the offspring   
         
    # select two individuals
    offspring = [random.choice(selectpop) for i in xrange(2)]
     
    if random.random() < cxpb: # cross two individuals with probability cxpb
     crossoff = self.crossoperate(offspring)
     fit_crossoff = evaluate(self.xydata, crossoff.data)# evaluate the individuals   
      
     if random.random() < mutpb: # mutate an individual with probability mutpb
      muteoff = self.mutation(crossoff,self.bound)
      fit_muteoff = evaluate(self.xydata, muteoff.data)# evaluate the individuals
      nextoff.append({'gene':muteoff,'fitness':fit_muteoff})
       
   # the population is entirely replaced by the offspring
   self.pop = nextoff
    
   # gather all the fitnesses in one list and print the stats
   fits = [ind['fitness'] for ind in self.pop]
     
   length = len(self.pop)
   mean = sum(fits) / length
   sum2 = sum(x*x for x in fits)
   std = abs(sum2 / length - mean**2)**0.5
   best_ind = self.selectbest(self.pop)
 
   if best_ind['fitness'] < self.bestindividual['fitness']:
    self.bestindividual = best_ind
 
   print("best individual found is %s, %s" % (self.bestindividual['gene'].data,self.bestindividual['fitness']))
   print(" min fitness of current pop: %s" % min(fits))
   print(" max fitness of current pop: %s" % max(fits))
   print(" avg fitness of current pop: %s" % mean)
   print(" std of currrent pop: %s" % std)
   
  print("-- end of (successful) evolution --"
 
if __name__ == "__main__":
 
 cxpb, mutpb, ngen, popsize = 0.8, 0.3, 50, 100#control parameters
  
 up = [64, 64, 64, 64, 64, 64, 64, 64, 64, 64]#upper range for variables
 low = [-64, -64, -64, -64, -64, -64, -64, -64, -64, -64]#lower range for variables
 parameter = [cxpb, mutpb, ngen, popsize, low, up]
  
 run = ga(parameter)
 run.ga_main()

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持服务器之家。

原文链接:http://blog.csdn.net/bible_reader/article/details/72782675

标签:

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
Intellij idea2020永久破解,亲测可用!!!
Intellij idea2020永久破解,亲测可用!!! 2020-07-29
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
歪歪漫画vip账号共享2020_yy漫画免费账号密码共享
歪歪漫画vip账号共享2020_yy漫画免费账号密码共享 2020-04-07
返回顶部