{"id":12568,"date":"2019-02-19T11:30:19","date_gmt":"2019-02-19T11:30:19","guid":{"rendered":"http:\/\/stblog.lunaeme.com\/?p=12568"},"modified":"2023-09-20T15:33:04","modified_gmt":"2023-09-20T15:33:04","slug":"swarm-intelligence-metaheuristics-part-2-particle-swarm-optimization","status":"publish","type":"post","link":"https:\/\/www.stratio.com\/blog\/swarm-intelligence-metaheuristics-part-2-particle-swarm-optimization\/","title":{"rendered":"Swarm Intelligence Metaheuristics, part 2: Particle Swarm Optimization"},"content":{"rendered":"

Welcome back to our series on Swarm Intelligence Metaheuristics for Optimization! In <\/span>part 1<\/span><\/a>, we talked about a family of metaheuristic algorithms known generically as Ant Colony Optimization (ACO), which were specially well-suited for combinatorial optimization problems, i.e. finding the best combination of values of many categorical variables. Recall we define Metaheuristics as a class of optimization algorithms which turn out to be very useful when the function being optimized is non-differentiable or does not have an analytical expression at all.<\/span><\/p>\n

<\/p>\n

We had framed ACO in the broader context of Swarm Intelligence, a yet-more-general family of algorithms able to solve hard optimization problems by a set of very simple cooperative agents and the appropriate communication rules between them, which together exhibit intelligent behaviour. In this post, we focus on another subclass of Swarm Intelligence algorithms, known as Particle Swarm Optimization (PSO), <\/span>first published in 1995<\/span><\/a> at Univ. of Washington and Indianapolis [1]. <\/span><\/p>\n

Particle Swarm Optimization<\/span><\/h2>\n

Like ants, birds are another example of social animals which rely on each other to solve problems. But differently from ants, they are not blind so they can see each other and interact directly: a flying bird knows the position of its nearest birds. When searching for food, a bird does not know the exact location of the food but can perceive the distance to it. Ideally every bird would trust its neighbour birds if they are closer to the food.<\/span><\/p>\n

\"\"
Figure 1. Flock of birds showing a curved trajectory generated by following the neighbours<\/figcaption><\/figure>\n

In a function optimization context, each bird is represented by a particle moving along the optimization space (which we assume either \u211d<\/span>n<\/sup> <\/span> with <\/span>n <\/span><\/i>the number of variables being optimized, or a bounded subset of it). We initialize a number of particles (this number is problem-dependent and has to be tuned) spread along the space (Fig. 2), either randomly placed or following a uniform grid covering the feasible space in case it is bounded. Each particle is located at some point, which is a solution to the problem (not necessarily optimal) and it is in continuous movement during the algorithm, always exploring other solutions.<\/span><\/p>\n

\"\"
Figure 2. Particle initialization: spread along the search space<\/figcaption><\/figure>\n

While ACO algorithms follow a constructive approach (each ant needs several steps to build a solution, which consists of a sequence of decisions of candidate values, one for each variable), each particle in PSO represents already a full solution in \u211dn<\/sup><\/span>. In contrast with classical techniques like gradient descent, the particles do not use an analytical expression of the function to decide where to move next (as such expression might not even exist), but only the quality of the solutions of their neighbours. Such neighbour solutions are known to the particle. In addition, PSO is used mainly for continuous optimization problems, while ACO works best in combinatorial optimization (although continuous variants also exist).<\/span><\/p>\n


\nParticles initialization and movement in PSO<\/b><\/p>\n

We could somehow assume that a bird\u2019s movement is guided by its current velocity (as it cannot turn suddenly), the position of its neighbours and how desirable each of the neighbour positions are, which is the analogy of the quality of the solutions found by such neighbours.<\/span><\/p>\n

More formally, each particle <\/span>i<\/span><\/i> stores:<\/span><\/p>\n