introduction
Beaucoup de problèmes de mathématiques, d'économie, de statistiques, etc. se réduisent aux problèmes de trouver la meilleure solution (objet, paramètres ou autres données). Ces problèmes surviennent lorsque vous devez construire un modèle mathématique de la situation. Lors du traitement du modèle mathématique obtenu, il n'est pas toujours possible d'itérer toutes les données fournies par le système, il est donc nécessaire de développer des algorithmes qui pourraient rechercher des données optimales avec quelques erreurs afin de limiter la zone de traitement pour trouver le Prochaines meilleures valeurs.
Dans cet article, le problème d'optimisation est compris comme la recherche de l'extrême (minimum) d'une fonction réelle dans une zone donnée. Deux des algorithmes d'optimisation les plus importants seront discutés: l'algorithme génétique et l'algorithme d'essaim de particules.
Algorithme génétique
Brève description
Le premier algorithme d'optimisation sera un algorithme génétique, qui, à son tour, est l'un des algorithmes évolutifs, c'est-à -dire qu'il est basé sur les processus de sélection, de mutation et de combinaison (croisement). Puisque nous optimisons le problème de la recherche de l'extrémum global d'une fonction, il convient d'examiner plus en détail chaque étape de l'algorithme génétique:
Chaque individu de la population aura trois paramètres principaux: la position le long de l'axe X, la position le long de l'axe Y et la valeur de la fonction objectif (c'est cette valeur qui agira comme paramètre principal dans la sélection).
Dans un premier temps, une population initiale est créée, où chaque individu reçoit aléatoirement ses coordonnées en X et Y. Cette population peut être loin d'être idéale, mais en cours d'évolution, l'algorithme devra la corriger.
. , . . , , .
, . .
. . , , .
“”, “” “” , . , ….
, , ( ) . , - , .
, : , , 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)):
:
, ( ) , , . .
, . , , , . , , . , .