Introduction
Many of the problems of mathematics, economics, statistics, etc. are reduced to the problems of finding the best solution (object, parameters, or other data). These problems arise when you have to build a mathematical model of the situation. When processing the obtained mathematical model, it is not always possible to iterate through all the data provided by the system, so there is a need to develop algorithms that could search for optimal data with some errors in order to limit the processing area for finding the next best values.
In this article, the optimization problem is understood as finding the extremum (minimum) of some real function in a given area. Two of the most important algorithms in optimization will be discussed: the genetic algorithm and the particle swarm algorithm.
Genetic Algorithm
Short description
The first optimization algorithm will be a genetic algorithm, which, in turn, is one of the evolutionary algorithms, that is, it is based on the processes of selection, mutation and combination (crossing). Since we are optimizing the problem of finding the global extremum of a function, it is worth considering in more detail each step of the genetic algorithm:
Each individual of the population will have three main parameters: position along the X-axis, position along the Y-axis and the value of the objective function (it is this value that will act as the main parameter in selection).
At the first stage, an initial population is created, where each individual randomly receives its coordinates in X and Y. This population may be far from ideal, but in the process of evolution, the algorithm will have to correct it.
. , . . , , .
, . .
. . , , .
“”, “” “” , . , ….
, , ( ) . , - , .
, : , , 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)):
:
, ( ) , , . .
, . , , , . , , . , .