Python:遺伝アルゴリズム実装

遺伝アルゴリズムについて
遺伝アルゴリズムは自然界における生物の進化を模倣して生まれた最適化アルゴリズムである.個人感覚遺伝アルゴリズムは簡単で乱暴で、適応性が広い.遺伝アルゴリズムについての紹介はネット上にたくさんありますが、ここでは自分の理解で簡単に要約します.

符号化復号化は、最適化されるパラメータをDNA配列に符号化し、最も簡単で直接的なものはバイナリ符号化(すなわち、2つのアルカリ基を有するDNA鎖)である.

ランダム初代

を生成する.

は選択され、適応度(最適化されるモデルから得られる)の良い個体はより大きな確率で選択され、比較的多くの方法を適用するとルーレット賭けと選手権がある.

は一定の確率でランダムな交差変異

を行う.

GOTO Step 2

複数の世代の反復を経て,最適解に収束する.クロスとコンパイルの役割は,局所最適解に陥ることを避ける新しい個体を生成することである.
Pythonで実現
先輩たちはよく「車輪を繰り返さないで」と言いますが、実は一番直接的なのは他人が書いたかばんを探していることです.ここで時間をかけて自分で1つをするのは主にこのアルゴリズムが比較的に簡単で、論理性が明確で、比較的に手を練習するのに適しているため、自分で実現することを決定して、Pythonの扉をノックする最初のプロジェクトです.
コーディングデコード
ここでは、ユーザが入力したパラメータ範囲と精度に基づいて各パラメータに必要なビット数を算出し、パラメータ空間をバイナリ符号化に均等にマッピングするバイナリ符号化方式を選択する.
Copy

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

# Encode parameters into DNA    
def encode(self, parameters):
 dna = ''
 for i in range(self.nGenes):
 geneSequenceDigit = (parameters[i]-self.parametersRange[i,0])/(self.parametersRange[i,1]-self.parametersRange[i,0])*(2**self.geneLength[i]-1)
 geneSequenceDigit = int(round(geneSequenceDigit))
 geneSequenceBin = self.int2bin(geneSequenceDigit, self.geneLength[i])
 dna = dna + geneSequenceBin 
 dna = list(dna) # Trun string to list
 return dna

# Decode DNA to parameters
def decode(self, dna):
 dna = ''.join(dna) # Trun list to string
 parameters = []
 for i in range(self.nGenes):
 geneSequenceBin = dna[self.dnaIdx[i,0]:self.dnaIdx[i,1]+1]
 geneSequenceDigit = self.bin2int(geneSequenceBin)
 parameterI = geneSequenceDigit/(2**self.geneLength[i]-1)*(self.parametersRange[i,1]-self.parametersRange[i,0])+self.parametersRange[i,0]
 parameters.append(parameterI)
 return parameters

# Returns the binary string of integer n, using count number of digits
def int2bin(self, n, count=32):
 binStr = "".join([str((n >> y) & 1) for y in range(count-1, -1, -1)])
 return binStr

# Returns digit integer of binary string
def bin2int(self, n):
 ret = int(n,2)
 return ret

このように実現される精度は、ユーザに正確に入力される精度ではなく、ユーザの入力精度よりも高い.
選択
選択した戦略は選手権という方法を使用し、エリート保持メカニズムを追加した.選手権はランダムにN個(通常N=2)候補個体を選択し、その中から最適個体を選択して次世代に入り、子の規模が要求に達するまで何度も繰り返す.エリート保持メカニズムとは、すでに発生した最適個体を淘汰されず、交差や変異によって破壊されないように保護することである.
Copy

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

# Select individuals
def select(self):
 nCandidates = 2
 generation = []
 for i in range(self.popGeneration):
 candidates = random.choices(self.generation, k=nCandidates)
 fitnessList = self.fitness(candidates=candidates)
 bestFitness = max(fitnessList)
 idx = fitnessList.index(bestFitness)
 generation.append(candidates[idx].copy())
 self.generation = generation
 return

# Elitist preservation
def elitistPreservation(self):
 bestFitness = max(self.fitnessList)
 if bestFitness > self.bestFitness:
 idx = self.fitnessList.index(bestFitness)
 self.bestFitness = bestFitness
 self.bestIndividual = self.generation[idx].copy()
 else:
 worstIndividual = min(self.fitnessList)
 idx = self.fitnessList.index(worstIndividual)
 self.generation[idx] = self.bestIndividual.copy()
 self.fitnessList[idx] = self.bestFitness
 return

こうさとへんい
クロスとコンパイルは比較的簡単で,乱数を用いて発生確率を制御する.ここで特筆すべきは,現実には多点の変異や交差が発生する可能性があるが,確率は非常に低いだけで,遺伝アルゴリズムの実現において単点の交差や変異だけを採用すればよい.
コードと例
https://yingnan.me/files/GeneticAlgorithm.py
使用例:
Copy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

import GeneticAlgorithm as GA #   GeneticAlgorithm  
import math

#                 ，par        ，ret    
def fitness(par):
 x = par[0]
 ret = x*math.sin(10*math.pi*x)+2
 return ret

maxGen = 500 #     
popGeneration = 50 #          
pCross = 0.1 #        
pMutation = 0.05 #        
nGenes = 1 #          
parametersRange = [[-1, 2, 0.01]] #               ，      ：[[-1, 2, 0.01]，[-2, 3, 0.1]]

#   GA  
ga = GA.GeneticAlgorithm(maxGen, popGeneration, pCross, pMutation, nGenes, parametersRange, fitness)
#       
ga.info()
#     
ga.run()
#      
ga.result()

転載先:https://www.cnblogs.com/ynnie/p/10590942.html