python中遺傳算法的示例分析

這篇文章主要介紹了python中遺傳算法的示例分析，具有一定借鑒價(jià)值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

具體內(nèi)容如下

1、基本概念

遺傳算法（GA）是最早由美國(guó)Holland教授提出的一種基于自然界的“適者生存，優(yōu)勝劣汰”基本法則的智能搜索算法。該法則很好地詮釋了生物進(jìn)化的自然選擇過程。遺傳算法也是借鑒該基本法則，通過基于種群的思想，將問題的解通過編碼的方式轉(zhuǎn)化為種群中的個(gè)體，并讓這些個(gè)體不斷地通過選擇、交叉和變異算子模擬生物的進(jìn)化過程，然后利用“優(yōu)勝劣汰”法則選擇種群中適應(yīng)性較強(qiáng)的個(gè)體構(gòu)成子種群，然后讓子種群重復(fù)類似的進(jìn)化過程，直到找到問題的最優(yōu)解或者到達(dá)一定的進(jìn)化（運(yùn)算）時(shí)間。

Ga算法中的幾個(gè)重要名詞概念。

個(gè)體（染色體）：自然界中一個(gè)個(gè)體（染色體）代表一個(gè)生物，在GA算法中，個(gè)體（染色體）代表了具體問題的一個(gè)解。

基因：在GA算法中，基因代表了具體問題解的一個(gè)決策變量，問題解和染色體中基因的對(duì)應(yīng)關(guān)系如下所示：

種群：多個(gè)個(gè)體即組成一個(gè)種群。GA算法中，一個(gè)問題的多組解即構(gòu)成了問題的解的種群。

2、主要步驟

GA算法的基本步驟如下：

Step 1. 種群初始化。選擇一種編碼方案然后在解空間內(nèi)通過隨機(jī)生成的方式初始化一定數(shù)量的個(gè)體構(gòu)成GA的種群。

Step 2. 評(píng)估種群。利用啟發(fā)式算法對(duì)種群中的個(gè)體（矩形件的排入順序）生成排樣圖并依此計(jì)算個(gè)體的適應(yīng)函數(shù)值（利用率），然后保存當(dāng)前種群中的最優(yōu)個(gè)體作為搜索到的最優(yōu)解。

Step 3. 選擇操作。根據(jù)種群中個(gè)體的適應(yīng)度的大小，通過輪盤賭或者期望值方法，將適應(yīng)度高的個(gè)體從當(dāng)前種群中選擇出來。

Step 4. 交叉操作。將上一步驟選擇的個(gè)體，用一定的概率閥值Pc控制是否利用單點(diǎn)交叉、多點(diǎn)交叉或者其他交叉方式生成新的交叉?zhèn)€體。

Step 5. 變異操作。用一定的概率閥值Pm控制是否對(duì)個(gè)體的部分基因執(zhí)行單點(diǎn)變異或多點(diǎn)變異。

Step 6. 終止判斷。若滿足終止條件，則終止算法，否則返回Step 2。

流程圖如下所示：

3、主要操作介紹

3.1 種群初始化

種群的初始化和具體的問題有關(guān)。比如一個(gè)問題有n個(gè)決策變量{x1,x2,…,xn}。每個(gè)決策變量有取值范圍:下界{L1,L2,…,Ln}和上界{U1,U2,…,Un}，則種群中個(gè)體的初始化即隨機(jī)地在決策變量的取值范圍內(nèi)生成各個(gè)決策變量的值：Xj={x1,x2,...,xn}，其中xi屬于范圍(Li，Ui)內(nèi)。所有的個(gè)體即構(gòu)成種群。當(dāng)每個(gè)個(gè)體都初始化后，即種群完成初始化。

3.2 評(píng)價(jià)種群

種群的評(píng)價(jià)即計(jì)算種群中個(gè)體的適應(yīng)度值。假設(shè)種群population有popsize個(gè)個(gè)體。依次計(jì)算每個(gè)個(gè)體的適應(yīng)度值及評(píng)價(jià)種群。

3.3 選擇操作

GA算法中常見的選擇操作有輪盤賭方式：種群中適應(yīng)度值更優(yōu)的個(gè)體被選擇的概率越大。假設(shè)popsize=4，按照如下表達(dá)式計(jì)算各個(gè)個(gè)體的被選擇概率的大小，然后用圓餅圖表示如下。

P(Xj) = fit(Xj)/(fit(X1)+fit(X2)+fit(X3)+fit(X4)),j=1,2,3,4

當(dāng)依據(jù)輪盤賭方式進(jìn)行選擇時(shí)，則概率越大的越容易被選擇到。

3.4 交叉操作

交叉操作也有許多種：?jiǎn)吸c(diǎn)交叉，兩點(diǎn)交叉等。此處僅講解一下兩點(diǎn)交叉。首先利用選擇操作從種群中選擇兩個(gè)父輩個(gè)體parent1和parent2,然后隨機(jī)產(chǎn)生兩個(gè)位置pos1和pos2，將這兩個(gè)位置中間的基因位信息進(jìn)行交換，便得到下圖所示的off1和off2兩個(gè)個(gè)體，但是這兩個(gè)個(gè)體中一般會(huì)存在基因位信息沖突的現(xiàn)象（整數(shù)編碼時(shí)），此時(shí)需要對(duì)off1和off2個(gè)體進(jìn)行調(diào)整：off1中的沖突基因根據(jù)parent1中的基因調(diào)整為parent2中的相同位置處的基因。如off1中的“1”出現(xiàn)了兩次，則第二處的“1”需要調(diào)整為parent1中“1”對(duì)應(yīng)的parent2中的“4”，依次類推處理off1中的相沖突的基因。需要注意的是，調(diào)整off2，則需要參考parent2。

3.5 變異操作

變異操作的話，根據(jù)不同的編碼方式有不同的變異操作。

如果是浮點(diǎn)數(shù)編碼，則變異可以就染色體中間的某一個(gè)基因位的信息進(jìn)行變異（重新生成或者其他調(diào)整方案）。

如果是采用整數(shù)編碼方案，則一般有多種變異方法：位置變異和符號(hào)變異。

位置變異： 

符號(hào)變異： 

4、Python代碼

#-*- 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()

感謝你能夠認(rèn)真閱讀完這篇文章，希望小編分享的“python中遺傳算法的示例分析”這篇文章對(duì)大家有幫助，同時(shí)也希望大家多多支持億速云，關(guān)注億速云行業(yè)資訊頻道，更多相關(guān)知識(shí)等著你來學(xué)習(xí)!