pengantar
Banyak masalah matematika, ekonomi, statistik, dll. Direduksi menjadi masalah mencari solusi terbaik (objek, parameter, atau data lain). Masalah ini muncul ketika Anda harus membangun model matematis dari situasi tersebut. Saat memproses model matematis yang diperoleh, tidak selalu memungkinkan untuk melakukan iterasi melalui semua data yang disediakan oleh sistem, sehingga perlu dikembangkan algoritma yang dapat mencari data yang optimal dengan beberapa kesalahan untuk membatasi area pemrosesan untuk menemukan data tersebut. nilai terbaik berikutnya.
Dalam artikel ini, masalah pengoptimalan dipahami sebagai menemukan ekstrem (minimum) dari beberapa fungsi nyata di area tertentu. Dua algoritma terpenting dalam optimasi akan dibahas: algoritma genetika dan algoritma kumpulan partikel.
Algoritma genetika
Deskripsi Singkat
Algoritma optimasi yang pertama adalah algoritma genetika, yang selanjutnya merupakan salah satu algoritma evolusioner, yaitu berdasarkan proses seleksi, mutasi dan kombinasi (persilangan). Karena kami mengoptimalkan masalah menemukan ekstrem global suatu fungsi, ada baiknya mempertimbangkan secara lebih mendetail setiap langkah algoritme genetika:
Setiap individu populasi akan memiliki tiga parameter utama: posisi sepanjang sumbu X, posisi sepanjang sumbu Y dan nilai fungsi tujuan (nilai inilah yang akan bertindak sebagai parameter utama dalam pemilihan).
Pada tahap pertama, populasi awal dibuat, di mana setiap individu secara acak menerima koordinatnya dalam X dan Y. Populasi ini mungkin jauh dari ideal, tetapi dalam proses evolusi, algoritme harus memperbaikinya.
. , . . , , .
, . .
. . , , .
“”, “” “” , . , ….
, , ( ) . , - , .
, : , , 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)):
:
, ( ) , , . .
, . , , , . , , . , .