前書き
数学、経済学、統計学などの問題の多くは、最良の解決策（オブジェクト、パラメーター、またはその他のデータ）を見つける問題に還元されます。これらの問題は、状況の数学的モデルを構築する必要がある場合に発生します。得られた数理モデルを処理する場合、システムが提供するすべてのデータを反復処理できるとは限らないため、エラーのある最適なデータを検索できるアルゴリズムを開発して、次善の値。
この記事では、最適化問題は、特定の領域でいくつかの実関数の極値（最小値）を見つけることとして理解されています。最適化で最も重要な2つのアルゴリズム、遺伝的アルゴリズムと粒子群アルゴリズムについて説明します。
遺伝的アルゴリズム
簡単な説明
最初の最適化アルゴリズムは遺伝的アルゴリズムであり、これは進化的アルゴリズムの1つです。つまり、選択、突然変異、および組み合わせ（交差）のプロセスに基づいています。関数のグローバル極値を見つける問題を最適化しているので、遺伝的アルゴリズムの各ステップをより詳細に検討する価値があります。
母集団の各個人には、X軸に沿った位置、Y軸に沿った位置、および目的関数の値の3つの主要なパラメーターがあります（選択の主要なパラメーターとして機能するのはこの値です）。
最初の段階で、各個体がXとYの座標をランダムに受け取る初期母集団が作成されます。この母集団は理想からはほど遠いかもしれませんが、進化の過程で、アルゴリズムはそれを修正する必要があります。
次は繁殖プロセスです。親のペアは、子孫を生成するためにランダムに選択されます。子孫は、親から特性を継承する必要があります。一人の個体からの優性を防ぐために、両方の親の遺伝子が生殖に参加します。
生殖後、遺伝子のランダムな突然変異を受ける個体の一部が選択されます。極値を検索する場合、X座標とY座標に沿った個人の位置が変化します。
最後に、適者生存の選択を行う必要があります。目的関数値の指標が最も低い個人はさらに進みます。人口が継続的に増加しないようにするために、そのサイズは特定の設定されたパラメータによって規制されます。
“”, “” “” , . , ….
, , ( ) . , - , .
, : , , 2 , , , :
class Individ():
""" """
def __init__(self, start, end, mutationSteps, function):
#
self.start = start
self.end = end
# ( )
self.x = rnd.triangular(self.start, self.end)
# Y ( )
self.y = rnd.triangular(self.start, self.end)
# ,
self.score = 0
#
self.function = function
#
self.mutationSteps = mutationSteps
#
self.calculateFunction()
:
def mutate(self):
""" """
#
delta = 0
for i in range(1, self.mutationSteps+1):
if rnd.random() < 1 / self.mutationSteps:
delta += 1 / (2 ** i)
if rnd.randint(0, 1):
delta = self.end * delta
else:
delta = self.start * delta
self.x += delta
#
if self.x < 0:
self.x = max(self.x, self.start)
else:
self.x = min(self.x, self.end)
#
delta = 0
for i in range(1, self.mutationSteps+1):
if rnd.random() < 1 / self.mutationSteps:
delta += 1 / (2 ** i)
if rnd.randint(0, 1):
delta = self.end * delta
else:
delta = self.start * delta
self.y += delta
#
if self.y < 0:
self.y = max(self.y, self.start)
else:
self.y = min(self.y, self.end)
. : ; , ; ; ; ( ), , . : (, ), :
class Genetic:
""" , """
def __init__(self,
numberOfIndividums,
crossoverRate,
mutationSteps,
chanceMutations,
numberLives,
function,
start,
end):
#
self.numberOfIndividums = numberOfIndividums
# ( % )
self.crossoverRate = crossoverRate
#
self.mutationSteps = mutationSteps
#
self.chanceMutations = chanceMutations
# ( )
self.numberLives = numberLives
#
self.function = function
# ,
self.bestScore = float('inf')
# , ,
self.xy = [float('inf'), float('inf')]
#
self.start = start
self.end = end
(). , :
def crossover(self, parent1:Individ, parent2:Individ):
"""
:return: 2 ,
"""
# 2
child1 = Individ(self.start, self.end, self.mutationSteps, self.function)
child2 = Individ(self.start, self.end, self.mutationSteps, self.function)
#
alpha = rnd.uniform(0.01, 1)
child1.x = parent1.x + alpha * (parent2.x - parent1.x)
alpha = rnd.uniform(0.01, 1)
child1.y = parent1.y + alpha * (parent2.y - parent1.y)
alpha = rnd.uniform(0.01, 1)
child2.x = parent1.x + alpha * (parent1.x - parent2.x)
alpha = rnd.uniform(0.01, 1)
child2.y = parent1.y + alpha * (parent1.y - parent2.y)
return child1, child2
( startGenetic Genetic). :
#
pack = [self.start, self.end, self.mutationSteps,self.function]
population = [Individ(*pack) for _ in range(self.numberOfIndividums)]
, . ( ) , :
#
for _ in range(self.numberLives):
# score
population = sorted(population, key=lambda item: item.scor
# ,
bestPopulation = population[:int(self.numberOfIndividums*self.crossoverRate)]
, :
# ,
childs = []
for individ1 in bestPopulation:
#
individ2 = rnd.choice(bestPopulation)
while individ1 == individ2:
individ2 = rnd.choice(bestPopulation)
child1, child2 = self.crossover(individ1, individ2)
childs.append(child1)
#
population.extend(childs) childs.append(child2)
, :
for individ in population:
#
individ.mutate()
#
individ.calculateFunction()
#
population = sorted(population, key=lambda item: item.score)
population = population[:self.numberOfIndividums]
:
#
if population[0].score < self.bestScore:
self.bestScore = population[0].score
self.xy = [population[0].x, population[0].y]
. ( 0,0):
def Sphere(x, y):
return x**2 + y**2
a = Genetic(numberOfIndividums=500, crossoverRate=0.5, mutationSteps=15, chanceMutations=0.4,
numberLives=200, function=Sphere, start=-5, end=5)
a.startGenetic()
print(" :", a.xy, a.bestScore)
>>> : [9.900341358415679e-05, -6.0054371129849215e-05] 1.3408203393117267e-08
, 5 , .
, . .
: . , , . , . .
:
Vj+1 - , Vj - , Pj - , , Xj - j- , G - , , r1 r2 - [0,1), a1 - , , a2 - , .
,
Lj - , . , :
, , , , :
class Swarm:
def __init__(self, sizeSwarm,
currentVelocityRatio,
localVelocityRatio,
globalVelocityRatio,
numbersOfLife,
function,
start,
end):
#
self.sizeSwarm = sizeSwarm
#
self.currentVelocityRatio = currentVelocityRatio
self.localVelocityRatio = localVelocityRatio
self.globalVelocityRatio = globalVelocityRatio
#
self.numbersOfLife = numbersOfLife
#
self.function = function
#
self.start = start
self.end = end
#
self.swarm = []
#
self.globalBestPos = []
self.globalBestScore = float('inf')
#
self.createSwarm()
:
class Unit:
def __init__(self, start, end, currentVelocityRatio, localVelocityRatio, globalVelocityRatio, function):
#
self.start = start
self.end = end
#
self.currentVelocityRatio = currentVelocityRatio
self.localVelocityRatio = localVelocityRatio
self.globalVelocityRatio = globalVelocityRatio
#
self.function = function
#
self.localBestPos = self.getFirsPos()
self.localBestScore = self.function(*self.localBestPos)
#
self.currentPos = self.localBestPos[:]
self.score = self.function(*self.localBestPos)
#
self.globalBestPos = []
#
self.velocity = self.getFirstVelocity()
def getFirstVelocity(self):
""" """
minval = -(self.end - self.start)
maxval = self.end - self.start
return [rnd.uniform(minval, maxval), rnd.uniform(minval, maxval)]
def getFirsPos(self):
""" """
return [rnd.uniform(self.start, self.end), rnd.uniform(self.start, self.end)]
:
def nextIteration(self):
""" """
#
rndCurrentBestPosition = [rnd.random(), rnd.random()]
rndGlobalBestPosition = [rnd.random(), rnd.random()]
#
velocityRatio = self.localVelocityRatio + self.globalVelocityRatio
commonVelocityRatio = 2 * self.currentVelocityRatio / abs(2-velocityRatio-sqrt(velocityRatio ** 2 - 4 * velocityRatio))
multLocal = list(map(lambda x: x*commonVelocityRatio * self.localVelocityRatio, rndCurrentBestPosition))
betweenLocalAndCurPos = [self.localBestPos[0] - self.currentPos[0], self.localBestPos[1] - self.currentPos[1]]
betweenGlobalAndCurPos = [self.globalBestPos[0] - self.currentPos[0], self.globalBestPos[1] - self.currentPos[1]]
multGlobal = list(map(lambda x: x*commonVelocityRatio * self.globalVelocityRatio, rndGlobalBestPosition))
newVelocity1 = list(map(lambda coord: coord * commonVelocityRatio, self.velocity))
newVelocity2 = [coord1 * coord2 for coord1, coord2 in zip(multLocal, betweenLocalAndCurPos)]
newVelocity3 = [coord1 * coord2 for coord1, coord2 in zip(multGlobal, betweenGlobalAndCurPos)]
self.velocity = [coord1 + coord2 + coord3 for coord1, coord2, coord3 in zip(newVelocity1, newVelocity2, newVelocity3)]
# ,
self.currentPos = [coord1 + coord2 for coord1, coord2 in zip(self.currentPos, self.velocity)]
newScore = self.function(*self.currentPos)
if newScore < self.localBestScore:
self.localBestPos = self.currentPos[:]
self.localBestScore = newScore
return newScore
Swarm :
def startSwarm(self):
""" """
for _ in range(self.numbersOfLife):
for unit in self.swarm:
unit.globalBestPos = self.globalBestPos
score = unit.nextIteration()
if score < self.globalBestScore:
self.globalBestScore = score
self.globalBestPos = unit.localBestPos
a = Swarm2(650, 0.1, 1, 5, 200, Sphere, -5, 5)
a.startSwarm()
print(":", a.globalBestScore, " :",a.globalBestPos)
>>> : 1.312199609838886e-14 : [1.0339745628764867e-07, -4.930478812075602e-08]
.
, . , , , . , , , GIF matplotlib ( ) imageio ( GIF). :
def Himmelblau(x, y):
return (x**2+y-11)**2 + (x+y**2-7)**2
def Holder(x, y):
return -1 * abs(sin(x)*cos(y)*exp(abs(1 - (sqrt(x**2 + y**2))/pi) ))
2 . , :
>>> : [8.055192789475683, 9.664625935217138] -19.20850227077434
>>> : [8.054968749727495, -9.664450802831455] -19.208502341200372
, ( ):
:
30 , . , 4 .
, :
>>> : -19.179380799107413 : [-8.04199083826373, -9.612324708539033]
>>> : -19.20850255479626 : [8.055014133170205, -9.664555295609443]
№1:
№2:
. , ( (0,0)):
:
, ( ) , , . .
, . , , , . , , . , .