Introducción
Muchos de los problemas de matemáticas, economía, estadística, etc. se reducen a problemas de encontrar la mejor solución (objeto, parámetros u otros datos). Estos problemas surgen cuando tienes que construir un modelo matemático de la situación. Al procesar el modelo matemático obtenido, no siempre es posible iterar a través de todos los datos proporcionados por el sistema, por lo que existe la necesidad de desarrollar algoritmos que puedan buscar datos óptimos con algunos errores con el fin de limitar el área de procesamiento para encontrar el siguientes mejores valores.
En este artículo, el problema de optimización se entiende como encontrar el extremo (mínimo) de alguna función real en un área determinada. Se discutirán dos de los algoritmos de optimización más importantes: el algoritmo genético y el algoritmo de enjambre de partículas.
Algoritmo genético
Breve descripción
El primer algoritmo de optimización será un algoritmo genético, que, a su vez, es uno de los algoritmos evolutivos, es decir, se basa en los procesos de selección, mutación y combinación (cruzamiento). Dado que estamos optimizando el problema de encontrar el extremo global de una función, vale la pena considerar con más detalle cada paso del algoritmo genético:
Cada individuo de la población tendrá tres parámetros principales: posición a lo largo del eje X, posición a lo largo del eje Y y el valor de la función objetivo (es este valor el que actuará como el parámetro principal en la selección).
En la primera etapa, se crea una población inicial, donde cada individuo recibe aleatoriamente sus coordenadas en X e Y. Esta población puede estar lejos de ser ideal, pero en el proceso de evolución, el algoritmo tendrá que corregirla.
. , . . , , .
, . .
. . , , .
“”, “” “” , . , ….
, , ( ) . , - , .
, : , , 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)):
:
, ( ) , , . .
, . , , , . , , . , .