Алгоритм роя частиц python

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

Алгоритм роя частиц (Partical swarm)

LIvanoff/ParticleSwarm

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

Реализация алгоритма роя частиц на Python

В качестве задачи оптимизации программа должна найти глобальный миниму черно-белой .jpg картинки с упрощённым изображением карты высот, на которой изображена впадина, Минимум будет соответсовать чёрному пятну со значениями RGB (0,0,0)

Анимация поведения роя частиц

Программа написана в рамках практических работ по предметам третьего курса Прогаммной инженерии 09.03.04 Тестирование и верификация программного обеспечения и Системный анализ данных в СППР в РТУ МИРЭА

About

Алгоритм роя частиц (Partical swarm)

Источник

Particle Swarm Optimization: Python Tutorial

Particle Swarm Optimization is one of the most successful and famous population-based metaheuristics. Its simplicity and performance made it easy to be adapted and used in many applications including the tasks of scheduling (more details can be found in my paper— Cloudlet Scheduling with Particle Swarm Optimization) or power consumption optimization in IoT devices (more details can be found in my paper— Particle Swarm Optimized Power Consumption Of Trilateration)

There are many versions of PSO such as the hybrid ones where PSO is used along with other algorithms (such as Simulated Annealing) in my publication above. But in general, when we are talking about a pure PSO algorithm we would recognize it as being a single or multi-objective that operates on a discrete or continuous space. The objectives of the algorithm are the things that PSO try to find a solution for. For example, PSO might concentrate on reducing the power consumption of a device without taking into consideration anything else, like the speed of the device. That’s why we developed multi-objective versions to kind of try to balance the solution. Balancing the work of the algorithm to consider more than one objective is part of the Game theory field (if you are curious and want to know more look at Nash Equilibrium and Pareto Optimality).

The original algorithm work on a continuous space. What that means is that it works to solve problems such as the numeric minimization problem I mentioned in the previous Heuristics post. PSO also works on a discrete binary space, which means that the algorithm is used to find a $ 0 $ or $ 1 $ values for the given problem (a simple example can be found in my scheduling paper). But now, let’s go back to our simple minimization problem and try to solve it using PSO. At this point if you didn’t read my other blog post please do so to know what I am trying to solve here.

PSO starts by creating a swarm of particles where each particle is a possible solution to the problem. Therefore, we need to understand what exactly we are trying to solve and how to map it to the objective function of PSO, which is considered the hardest part when designing the algorithm.

Let’s first define few global variables needed throughout our program

# the x and y in our function (x - y + 7) (aka. dimensions) number_of_variables = 2 # the minimum possible value x or y can take min_value = -100 # the maximum possible value x or y can take max_value = 100 # the number of particles in the swarm number_of_particles = 10 # number of times the algorithm moves each particle in the problem space number_of_iterations = 2000 w = 0.729 # inertia weight c1 = 1.49 # cognitive (particle) c2 = 1.49 # social (swarm) 

The first step is to create the swarm of particles

swarm = [Particle(number_of_variables, min_value, max_value) for __x in range(number_of_particles)] 

Where each Particle is an Abstract Data Type (ADT) defined as follows:

class Particle: def __init__(self, number_of_variables, min_value, max_value): # init x and y values self.positions = [0.0 for v in range(number_of_variables)] # init velocities of x and y self.velocities = [0.0 for v in range(number_of_variables)] for v in range(number_of_variables): # update x and y positions self.positions[v] = ((max_value - min_value) * random.random() + min_value) # update x and y velocities self.velocities[v] = ((max_value - min_value) * random.random() + min_value) # current fitness after updating the x and y values self.fitness = Fitness(self.positions) # the current particle positions as the best fitness found yet self.best_particle_positions = list(self.positions) # the current particle fitness as the best fitness found yet self.best_particle_fitness = self.fitness 

Before I explain what each line means I should first explain how a particle behaves in the problem space then get back to our code snippet above.

As I mentioned before, each particle in the swarm represents a possible solution to the problem. And as I also mentioned in the previous blog post, each particle try to improve its solution by learning from two sources: its movement in the problem space and the movement of the other particles of the swarm (through learning from the best solution found by any of the other particles). To watch a simple visualization of PSO click on the image below:

Now, let’s see how that translates into code. The positions list in the above code snippet represent the current values of the variables in the objective function ($ x $ and $ y $) where the velocities list represent the (artificial) velocities (for each position) of the particle in space. We first initialize the values to zeros then update them using random numbers as follows:

(( max_value - min_value) * random.random() + min_value ) 

Each particle in our swarm keep track of its fitness value and the best positions and fitness found by any particle of the swarm (including itself). Where a particle fitness is the solution it achieved by plugging the current positions list values in the objective function (in our example problem, $ positions[0] = x $ and $ positions[1] = y $). Notice that during initialization we consider the particle’s fitness and positions as the best ones found yet because it might be the case, later we will check that and update with the correct information during each iteration of the algorithm.

After the initialization of the swarm, we check all particles and find the best solution found and keep track of that using the two variables best_swarm_positions and best_swarm_fitness.

best_swarm_positions = [0.0 for v in range(number_of_variables)] best_swarm_fitness = sys.float_info.max for particle in swarm: # check each particle if particle.fitness  best_swarm_fitness: best_swarm_fitness = particle.fitness best_swarm_positions = list(particle.positions) 

Now, we are ready to start moving particles in the problem space by generating new velocities to find new positions ($x$ and $y$ values) and eventually find new solutions (fitness values). The fitness value of each particle in the swarm is going to be updated during each iteration of the algorithm.

for __x in range(number_of_iterations): for particle in swarm: # start moving/updating particles to calculate new fitness 

Then, inside the nested loops, we start updating the velocities and positions and calculate the new fitness while keeping track of the best fitness of the swarm. But first, let’s start by updating the velocities as follows:

# compute new velocities for each particle for v in range(number_of_variables): particle.velocities[v] = calculate_new_velocity_value(particle, v) 

For each variable in the objective function, we should calculate a new velocity to later aid in calculating a new set of positions. That is done by calling calculate_new_velocity_value() function and passing the current particle and the variable number to it as follows:

# calculate a new velocity for one variable def calculate_new_velocity_value(p, v): # generate random numbers r1 = random.random() r2 = random.random() # the learning rate part part_1 = (w * p.velocities[v]) # the cognitive part - learning from itself part_2 = (c1 * r1 * (p.best_particle_positions[v] - p.positions[v])) # the social part - learning from others part_3 = (c2 * r2 * (best_swarm_positions[v] - p.positions[v])) new_velocity = part_1 + part_2 + part_3 return new_velocity 

As shown in the above code snippet, the value of the new velocity is the sum of all of the following three parts:

The learning rate part:

• The multiplication result of the inertia weight parameter ($w$) and the particle’s current velocity.
• The inertia weight parameter influences the convergence of the algorithm and the exploration of its particles. Therefore, a well-defined inertia weight is very important in influencing the quality of the solution found by PSO. The higher the inertia weight means bigger steps in the problem space (in other words, higher velocities). There are many types of inertia weights but we use in this example the fixed inertia weight (a static value) which do not change throughout the iterations. To learn more about other kinds of inertia weights read section 2.3.4 in my master thesis. Also, check how I used the simulated annealing and how it helped PSO in achieving better results in my paper (Cloudlet Scheduling with Particle Swarm Optimization).

The cognitive part:

• This part of the equation is the multiplication result of the constant c1 and the random number r1 and the subtraction of the position value that corresponds to the best fitness found by the particle and the current position value.
• The overall idea of this part of the equation is to represent the cognitive (self-learning) part of the particle.

The social part:

• The multiplication result of the constant c2 and the random number r2 and the subtraction of the position value that corresponds to the best fitness found by any particle of the swarm and the current position value of the particle.
• The overall idea of this part of the equation is to represent the social ability of the particle (learning from the swarm).

To keep our velocities within our desired range we use the following few lines of code:

if particle.velocities[v]  min_value: particle.velocities[v] = min_value elif particle.velocities[v] > max_value: particle.velocities[v] = max_value 

Now, we are ready to calculate our new positions values using our new velocities to later calculate the new fitness of each particle.

# compute new positions using the new velocities for v in range(number_of_variables): particle.positions[v] += particle.velocities[v] 

And again, to keep the values of the positions within control we use the following lines of code as before:

if particle.positions[v]  min_value: particle.positions[v] = min_value elif particle.positions[v] > max_value: particle.positions[v] = max_value 

Finally, we are ready to calculate the new fitness value using the objective function. As apparent in the following code snippet, we plug the two positions values in the objective function which corresponds to the $ x $ and $ y $ value in the original equation $ x-y+7 $.

# compute the fitness of the new positions particle.fitness = Fitness(particle.positions) def Fitness(positions): # x - y + 7 return positions[0] - positions[1] + 7 

At the end of each iteration, we evaluate the quality of the newly calculated fitness value and use it to do two kinds of updates if it is of a high quality. The first is to update the value of the best fitness found by the particle we are moving and the second is to update the value of the best fitness found by any particle of the swarm. Remember that the whole point of using PSO is to find the values of $ x $ and $ y $ such that we minimize the value of the whole function. Therefore, the best solution to the problem would be $ -100 — +100 + 7 $ which equals to $ -193 $ and PSO would be able to find the correct solution by the end of the iterations.

You can also download the full code and play with it yourself. And with that, I finish this post. I hope you learned something new and if you have any question don’t hesitate to contact me. Happy learning!

Источник