Relation of Neighborhood Size and Diversity Loss Rate in Particle Swarm Optimization With Ring Topology

MENDEL — Soft Computing Journal, Volume 2d, No.gk, .2+2K#2` 2021, Brno, Czech RepublicX ISSN: 1803-3814 (Printed), 2571-3701 (Online) https://doi.org/10.13164/mendel.2021.k.0d9 Relation of Neighborhood Size and Diversity Loss Rate in Particle Swarm Optimization With Ring Topology Michal Pluhacek , Anezka Kazikova, Tomas Kadavy, Adam Viktorin, Roman Senkerik Faculty of Applied Informatics, Tomas Bata University in Zlin, Zlin, Czech Republic [email protected] , kazik[email protected], k[email protected], avikto[email protected], senk[email protected] Abstract Measuring the population diversity in metaheuristics has become a common practice for adaptive approaches, aiming mainly to address the issue of premature convergence. Understanding the processes leading to a diversity loss in a metaheuristic algorithm is crucial for designing successful adaptive approaches. In this study, we focus on the relation of the neighborhood size and the rate of diversity loss in the Particle Swarm Optimization algorithm with local topology (also known as LPSO). We argue that the neighborhood size is an important input to consider when designing any adaptive approach based on the change of population diversity. We used the extensive benchmark suite of the IEEE CEC 2014 competition for experiments. Keywords: Particle Swarm Optimization, Population Diversity, Neighborhood, Ring Topology, LPSO. Received: 07 October 2021 Accepted: 15 December 2021 Published: 21 December 2021 1 Introduction Recording and adapting to the population diversity value has lately become a popular component of many metaheuristic optimizers [1,6,11,12,13]. There are numerous measures for quantifying the population diversity [8,9,11]; however, usually, the diversity change rate is more important for understanding the inner dynamic of the algorithm than any specific value of the used numerical measure. A rapid loss of diversity of the population might indicate a poor exploration ability of the algorithm, while minimal loss of diversity might prevent convergence of the method at all [15]. One of the most popular metaheuristics, the Particle Swarm Optimization (PSO) [4], is well known for fast and often premature convergence [2]. One of the possible solutions to slow the diversity loss is to limit the communication within the swarm. Typically, the swarm is divided into several overlapping sub-swarms, also known as local neighborhoods, hence the Local PSO notation (LPSO) [3]. The popular choice for local neighborhood structure is the ring topology [16]. In this work, we focus on the relation of the neighborhood size and diversity loss in the above-mentioned LPSO with ring topology. We set to answer the following research questions: 1. Is there a direct relation between the neighborhood size and the population diversity loss rate? 2. Could any particular neighborhood size setting prevent significant diversity decrease indefinitely? 3. Is there a correlation between the rate of diversity decrease and the improvement of cost function? The rest of the paper is structured as follows: the Particle Swarm Optimization algorithm is described in section two; the experiments are described in sections three and four. The results are discussed in section five, preceding the conclusion. 2 Particle Swarm Optimization (PSO) Particle Swarm Optimization is one of the most popular metaheuristic optimizers. It draws its inspiration from the movement patterns of bird flocks and fish schools [4]. In the original variant, all artificial particles in the swarm are attracted to two main points of interest, the personal best-discovered solution of each particle (pBest) and the (global) best solution within the whole swarm (gBest). However, it has been discovered that limiting the communication within the swarm into a particular neighborhood (sub-swarm) could improve the performance in specific scenarios [3]. In such a scenario, the gBest is replaced with the lBest, referring to a (local) best solution within the pre-defined neighborhood (sub-swarm) [3]. To build the local sub-swarms, several topologies are commonly used. Among the most popular is the ring topology, where each particle communicates only with its direct neighbors in the logical (based on particles IDs, not position) ring structure [16]. In Fig. 1, the ring topology is depicted. The numbers refer to the indexes of the particles in the population, and three different neighborhood sizes (radiuses) are exampled with the active particle being in the center of the highlighted neighborhood (bold number). In the first case (highlighted in green color), the ac74 MENDEL — Soft Computing Journal, Volume 2d, No.gk, .2+2K#2` 2021, Brno, Czech RepublicX tive particle (#10) communicates only with its direct neighbors (#9 and #11). Therefore, the total number of particles in this neighborhood is three, and the neighborhood radius is one. Subsequently, this variant is noted as LPSO 1. Similarly, in the red example, the neighborhood radius is two (noted hereinafter LPSO 2), and the number of particles in the resulting communication bubble is five. Finally, the example of a neighborhood radius size of three (subsequently LPSO 3) is highlighted in grey. As could be observed, the number of particles within a neighborhood in this setting is seven. As mentioned before, for each particular setting of the neighborhood size (radius), the resulting sub swarms are overlapping; therefore, the information of a high-quality solution being discovered might eventually (depending on the total number of particles and neighborhood size) affect all particles. a) b) c) Figure 1: Ring topology example; neighborhood radius a) one (green), b) two (red), and c) three (grey). 3 Experiment Setup In the experimental part of this paper, we use three above-described LPSO variants (LPSO 1, LPSO 2, and LPSO 3). These variants differ only in the neighborhood size setup while using the following control parameters setting (with respect to recommendations in [2,14]): Number of particles (NP): 40 Max. FEs: 1000 ·dim c1,c 2:1.49618 w:0.7298 In addition, we utilized a broad benchmark (IEEE CEC 2014 Benchmark set [5]) of thirty test problems to thoroughly investigate the behavior of the examined variants facing various fitness landscapes [7]. This particular benchmark was selected for the wide range and number of test problems and the high number of possible dimension size (dim) settings. Given the computational complexity and memory demands, the experiments were performed for dim: 10, 20, and 30 during our investigation. For similar reasons, the maximal number of cost function evaluations (Max. FEs) was set to 1000 ·dim, and the best cost function value and the population diversity were recorded for every NP function evaluations. To quantify the population diversity, we use the measure introduced in [10]. The diversity value is based on the sum of deviations (1) of an individual’s components from their corresponding means (2). PD =    1 NP NP  i=1 D  j=1 (xj,i −¯xj)2(1) ¯xj=1 NP NP  i=1 xj,i (2) Where iis the population member iterator jis the vector component iterator. 4 Experiment Results Firstly, we examine the diversity loss rate while optimizing the benchmark mentioned above. Thirty randomly initialized runs were performed for each variant and test function, and the results averaged. In the first experiment, we compute the initial population diversity value and observe its decrease during the optimization process. We record the number of cost function evaluations (FEs) it takes the population diversity to decrease to 90%, 80%, . . . , 10% of the initial value. In Table 1, we summarize the first experiment results for dim: 30. Note: the values of FEs are rounded to the nearest NP multiple (see Section 3 for details). For additional insight, we present the Pearson’s correlation between the average diversity history and the average cost function value history in Table 2. The lowest and highest correlation value are highlighted. According to Table 1, the smaller the neighborhood’s size, the slower the diversity loss is. In several cases, the LPSO 1 retains more than 70% of its initial diversity over the whole course of optimization. In such cases, it is necessary to consult Table 2. A high correlation might point at simultaneous stagnation of diversity and stagnation of cost function value (see, e.g., f11 and f12). Providing further insight for the highlighted results in Table 2, we graphically compare the mean diversity history in Fig. 2 (for f3) alongside the corresponding average cost function value history in Fig. 3 and the same for f13 in Fig. 4 and Fig. 5. 75 MENDEL — Soft Computing Journal, Volume 2d, No.gk, .2+2K#2` 2021, Brno, Czech RepublicX SHm?+2Fg2igHX,g_2HiBQMgQ7gL2B;?#Q`?QQ/gaBx2gM/g.Bp2`bBivgGQbbg_i2gBMgS`iB+H2gar`KgPTiBKBxiBQMgrBi?gXXX Table 1: : Average number of FEs to drop to x% of initial diversity; dim :30. Alg. f(x)90% 80% 70% 60% 50% 40% 30% 20% 10% f(x)90% 80% 70% 60% 50% 40% 30% 20% 10% LPSO 1 f1 80 80 200 840 12800 - - - - f16 80 120 1280 - - - - - - LPSO 2 80 80 120 320 1240 6320 - - - 80 80 400 7840 - - - - - LPSO 3 80 80 120 120 600 2640 11640 - - 80 80 120 1840 - - - - - LPSO 1 f2 80 80 120 240 600 1080 1840 3200 7720 f17 80 120 280 - - - - - - LPSO 2 80 80 120 120 360 640 1160 2160 4800 80 80 120 800 - - - - - LPSO 3 80 80 120 120 280 520 880 1800 4400 80 80 120 280 1560 - - - - LPSO 1 f3 80 120 1440 7040 15040 23160 - - - f18 80 80 120 560 - - - - - LPSO 2 80 80 120 2200 7680 14680 20240 28480 - 80 80 120 320 14800 - - - - LPSO 3 80 80 120 1160 4640 10400 15200 22080 - 80 80 120 120 560 19240 - - - LPSO 1 f4 80 80 120 280 680 1360 2640 - - f19 80 80 120 560 2040 - - - - LPSO 2 80 80 120 120 400 760 1440 4040 - 80 80 120 240 680 2440 - - - LPSO 3 80 80 120 120 320 600 1200 2720 - 80 80 120 120 400 1080 3200 - - LPSO 1 f5 80 120 - - - - - - - f20 80 120 800 14200 - - - - - LPSO 2 80 80 1040 - - - - - - 80 80 240 1600 17720 - - - - LPSO 3 80 80 520 - - - - - - 80 80 120 680 4840 28600 - - - LPSO 1 f6 80 120 480 - - - - - - f21 80 120 360 - - - - - - LPSO 2 80 80 120 2840 - - - - - 80 80 120 1320 - - - - - LPSO 3 80 80 120 440 2360 - - - - 80 80 120 360 - - - - - LPSO 1 f7 80 80 120 320 600 1040 1720 2840 5160 f22 80 120 280 26640 - - - - - LPSO 2 80 80 120 120 360 640 1160 2000 4000 80 80 120 320 - - - - - LPSO 3 80 80 120 120 280 480 880 1640 3440 80 80 120 240 2880 - - - - LPSO 1 f8 80 80 120 360 1120 - - - - f23 80 80 120 400 1080 2520 4360 6600 10840 LPSO 2 80 80 120 120 520 2240 - - - 80 80 120 240 520 1280 2400 4200 7560 LPSO 3 80 80 120 120 360 960 27800 - - 80 80 120 120 360 840 1920 3640 6520 LPSO 1 f9 80 80 120 400 2800 - - - - f24 80 80 120 320 880 2840 - - - LPSO 2 80 80 120 120 720 4720 - - - 80 80 120 120 480 1040 20360 - - LPSO 3 80 80 80 120 440 2160 - - - 80 80 120 120 320 680 3040 - - LPSO 1 f10 80 120 1960 - - - - - - f25 80 80 120 1720 24040 - - - - LPSO 2 80 80 440 - - - - - - 80 80 120 280 2160 17200 - - - LPSO 3 80 80 280 6280 - - - - - 80 80 120 240 760 4480 22880 - - LPSO 1 f11 80 120 - - - - - - - f26 80 80 120 320 2080 - - - - LPSO 2 80 80 400 - - - - - - 80 80 120 120 840 7200 - - - LPSO 3 80 80 240 4120 - - - - - 80 80 120 120 400 2200 27760 - - LPSO 1 f12 80 120 ------- f27 80 120 320 1000 4920 - - - - LPSO 2 80 80 920 - - - - - - 80 80 160 400 1120 6080 - - - LPSO 3 80 80 480 - - - - - - 80 80 120 280 560 1640 9960 - - LPSO 1 f13 80 80 120 360 680 1080 1800 - - f28 80 120 600 1040 1560 2080 3120 - - LPSO 2 80 80 120 120 400 680 1160 21080 - 80 80 280 520 760 1200 1800 4320 - LPSO 3 80 80 120 120 320 480 840 6680 - 80 80 160 360 560 800 1200 2400 - LPSO 1 f14 80 80 120 320 640 1080 1680 2840 - f29 80 200 520 1440 - - - - - LPSO 2 80 80 120 120 400 640 1120 2040 - 80 120 200 440 1000 - - - - LPSO 3 80 80 120 120 280 520 880 1640 - 80 80 160 320 560 1160 - - - LPSO 1 f15 80 80 120 280 720 1320 2440 4840 - f30 80 160 480 12320 - - - - - LPSO 2 80 80 120 120 360 760 1600 3000 - 80 120 200 560 4840 - - - - LPSO 3 80 80 120 120 280 600 1240 2640 - 80 80 120 280 1040 3040 12760 - - Finally, we provide a direct graphical comparison of the final diversity value for each function in Fig. 6. 5 Discussion As presented in Table 1, the neighborhood size directly impacts the speed of population diversity decrease. Intuitively a more restricted communication should lead to a slower convergence of the swarm. There are, however, additional, less apparent observations possible in Table 1. While the neighborhood size factors the speed of diversity decrease, the fitness landscape characteristics (problem complexity) seem to have a dominant role in the final diversity value. In some cases (e.g., f5,f 10,f 11,or f12), the diversity decreases fast, but only to a certain threshold of initial diversity percentage (e.g., 70% or 60%) and will not decrease further in the given time frame (1000 ·dim FEs). In contrast, in other cases (e.g., f2,f 7,f 15,or f23), the population diversity drops to (and under) 10% of 76 MENDEL — Soft Computing Journal, Volume 2d, No.gk, .2+2K#2` 2021, Brno, Czech RepublicX Table 2: Pearson’s correlation between the average diversity history and the average cost function value history for dim : 10, 20 and 30. dim :10 20 30 f(x)LPSO 1LPSO 2LPSO 3LPSO 1LPSO 2LPSO 3LPSO 1LPSO 2LPSO 3 10.74 0.73 0.68 0.66 0.62 0.63 0.88 0.85 0.83 20.91 0.88 0.83 0.86 0.80 0.79 0.87 0.83 0.81 30.40 0.42 0.45 0.33 0.28 0.31 0.27 0.27 0.22 40.84 0.87 0.86 0.79 0.80 0.77 0.84 0.83 0.79 50.80 0.77 0.80 0.67 0.73 0.74 0.77 0.82 0.79 60.94 0.97 0.98 0.98 0.99 0.99 0.81 0.87 0.92 70.85 0.85 0.85 0.86 0.85 0.84 0.86 0.84 0.83 80.95 0.94 0.93 0.92 0.92 0.93 0.87 0.89 0.90 90.97 0.97 0.97 0.94 0.93 0.94 0.89 0.93 0.91 10 0.81 0.85 0.86 0.67 0.79 0.84 0.74 0.81 0.86 11 0.81 0.83 0.90 0.71 0.79 0.89 0.64 0.79 0.90 12 0.77 0.77 0.82 0.71 0.78 0.82 0.76 0.81 0.76 13 0.99 0.99 0.98 0.99 0.99 0.99 1.00 0.99 0.99 14 0.93 0.93 0.93 0.95 0.95 0.95 0.94 0.94 0.95 15 0.53 0.58 0.62 0.50 0.52 0.55 0.42 0.44 0.49 16 0.90 0.93 0.91 0.91 0.89 0.92 0.88 0.89 0.91 17 0.82 0.71 0.75 0.86 0.81 0.86 0.66 0.62 0.65 18 0.93 0.94 0.83 0.83 0.73 0.71 0.84 0.60 0.71 19 0.93 0.94 0.88 0.86 0.87 0.83 0.88 0.85 0.81 20 0.63 0.59 0.58 0.54 0.51 0.53 0.52 0.56 0.48 21 0.73 0.72 0.66 0.90 0.87 0.88 0.86 0.87 0.89 22 0.91 0.87 0.90 0.97 0.93 0.90 0.88 0.81 0.69 23 0.66 0.67 0.68 0.61 0.60 0.63 0.58 0.60 0.62 24 0.98 0.98 0.99 0.96 0.96 0.95 0.94 0.94 0.94 25 0.88 0.95 0.82 0.97 0.89 0.82 0.86 0.90 0.88 26 0.72 0.70 0.68 0.70 0.68 0.66 0.80 0.73 0.75 27 0.69 0.75 0.72 0.76 0.76 0.78 0.80 0.77 0.77 28 0.57 0.65 0.69 0.55 0.63 0.66 0.55 0.60 0.67 29 0.46 0.81 0.84 0.72 0.79 0.87 0.37 0.38 0.36 30 0.84 0.89 0.86 0.90 0.90 0.89 0.79 0.66 0.59 the initial value. Nevertheless, when consulting this phenomenon with Table 2, there is evidence that keeping high diversity does not guarantee further improvement of the cost function value and vice versa. In other words, keeping the population diverse is advantageous for some fitness landscapes, while for others, it seems to have little effect, despite the neighborhood size factoring into the diversity decrease rate. Observing further from Table 1, it seems that the difference in the speed of diversity decrease is much more profound between LPSO 1 and 2 than LPSO 2 and 3. Interestingly, this is not the case in Table 2, where the problem’s dimensionality has a significantly more important role in affecting the correlation value than the neighborhood size. Based on the results, there seems to be a strong correlation between the average diversity history and the average cost function value history in many cases (see Fig. 4 and Fig. 5) with several exceptions (e.g., Fig. 2 and Fig. 3). The data presented in Table 2 hint that the correlation values are highly dependent on the fitness landscape and the problem’s dimensionality, producing some unpredictable results (see, e.g., f29). The difference in the correlation values will motivate a follow-up study investigating if the correlation value is linked to any specific characteristic of the fitness landscape and how it translates into the algorithm’s actual performance and convergence behavior. In Fig. 6, the final diversity values for all three algorithms and thirty test problems are depicted in direct Figure 2: Average diversity history f3;dim : 30. Figure 3: Average cost function value history f3;dim : 30. comparison. While the general trends are similar, there seem to be irregularities in the pattern, likely caused by certain features of the particular fitness landscape, that are worth investigating in the future. Overall, the results show a strong connection between the neighborhood size and the diversity loss. In some cases, the decrease of diversity seems to be stopped or marginalized in the given time frame; however, according to the correlations with the algorithm’s performance, a prevailing high diversity does not guarantee an ever-improving value of the cost function. It is essential to understand that loss of diversity alone might indicate various states of the population, however with the added information of the algorithm performance, quantified in the form of mutual correlation, it is, e.g., possible to recognize the local optima containment. As the diversity drops but the cost function value remains the same, the correlation value is bound to be low. Regarding the used benchmark set, it is necessary to emphasize that the primary goal of this paper is not a performance study or comparison with the participating algorithms and with others in later publications, i.e., to adhere to the exact definition of performance experiments according to the technical report. 6 Conclusion This work focused on providing more insight into the relation of population diversity and neighborhood size 77 MENDEL — Soft Computing Journal, Volume 2d, No.gk, .2+2K#2` 2021, Brno, Czech RepublicX SHm?+2Fg2igHX,g_2HiBQMgQ7gL2B;?#Q`?QQ/gaBx2gM/g.Bp2`bBivgGQbbg_i2gBMgS`iB+H2gar`KgPTiBKBxiBQMgrBi?gXXX Figure 4: Average diversity history f13;dim : 30. Figure 5: Average cost function value history f13;dim : 30. Figure 6: Average final diversity value for each function; dim : 30. in the Particle Swarm Optimization algorithm with local topology organized into a logic ring. In this topology, the communication is limited into overlapping subswarms that are constructed not from the positions of the particles in the search space but their IDs. Regarding the research questions: 1. Is there a direct relation between the neighborhood size and the population diversity loss rate? 2. Could any particular neighborhood size setting prevent significant diversity decrease indefinitely? 3. Is there a correlation between the rate of diversity decrease and the improvement of cost function? We have shown that there is a direct relation between the diversity loss rate and the neighborhood size. It seems that by limiting the neighborhood size only, it is possible in the same cases to maintain a high diversity; however, this does not guarantee a continuation of cost function value improvement. Further, in many cases, there is a strong correlation between the population diversity history and cost function value history, prompting our future research towards this direction. Acknowledgement: This work was supported by the Internal Grant Agency of Tomas Bata University under the Projects no. IGA/CebiaTech/2021/001. The work was further supported by resources of A.I.Lab at the Faculty of Applied Informatics, Tomas Bata University in Zlin (ailab.fai.utb.cz). References [1] Cheng, S., Shi, Y., Qin, Q., Zhang, Q., and Bai, R. Population diversity maintenance in brain storm optimization algorithm. Journal of Artificial Intelligence and Soft Computing Research 4, 2 (2014), 83–97. [2] Cleghorn, C. W., and Engelbrecht, A. P. Particle swarm convergence: An empirical investigation. In 2014 IEEE Congress on Evolutionary Computation (CEC) (2014), IEEE, pp. 2524– 2530. [3] Engelbrecht, A. P. Particle swarm optimization: Global best or local best? In 2013 BRICS congress on computational intelligence and 11th Brazilian congress on computational intelligence (2013), IEEE, pp. 124–135. [4] Kennedy, J., and Eberhart, R. Particle swarm optimization. In Proceedings of ICNN’95-international conference on neural networks (1995), vol. 4, IEEE, pp. 1942–1948. [5] Liang, J. J., Qu, B. Y., and Suganthan, P. N. Problem definitions and evaluation criteria for the cec 2014 special session and competition on single objective real-parameter numerical optimization. Computational Intelligence Laboratory, Zhengzhou University, Zhengzhou China and Technical Report, Nanyang Technological University, Singapore 635 (2013), 490. [6] Lin, C. An adaptive genetic algorithm based on population diversity strategy. In 2009 Third International Conference on Genetic and Evolutionary Computing (2009), IEEE, pp. 93–96. [7] Matousek, R., Dobrovsky, L., and Kudela, J. How to start a heuristic? utilizing lower bounds for solving the quadratic assignment problem. International Journal of Industrial Engineering Computations 13, 2 (2022), 151–164. [8] McGinley, B., Maher, J., O’Riordan, C., and Morgan, F. Maintaining healthy population diversity using adaptive crossover, mutation, and selection. IEEE Transactions on Evolutionary Computation 15, 5 (2011), 692–714. 78 MENDEL — Soft Computing Journal, Volume 2d, No.gk, .2+2K#2` 2021, Brno, Czech RepublicX [9] Morrison, R. W., and De Jong, K. A. Measurement of population diversity. In International conference on artificial evolution (evolution artificielle) (2001), Springer, pp. 31–41. [10] Polakova, R., Tvrdik, J., and Bujok, P. Differential evolution with adaptive mechanism of population size according to current population diversity. Swarm and Evolutionary Computation 50 (2019), 100519. [11] Pol´ akov´ a, R., Tvrd´ ık, J., Bujok, P., and Matouˇ sek, R. Population-size adaptation through diversity-control mechanism for differential evolution. In MENDEL, 22th International Conference on Soft Computing (2016), pp. 49–56. [12] Sun, N., and Lu, Y. A self-adaptive genetic algorithm with improved mutation mode based on measurement of population diversity. Neural Computing and Applications 31, 5 (2019), 1435– 1443. [13] Tang, J., Lim, M. H., and Ong, Y. S. Diversity-adaptive parallel memetic algorithm for solving large scale combinatorial optimization problems. Soft Computing 11, 9 (2007), 873–888. [14] Van den Bergh, F., and Engelbrecht, A. P. A study of particle swarm optimization particle trajectories. Information sciences 176, 8 (2006), 937–971. [15] Van den Bergh, F., and Engelbrecht, A. P. A convergence proof for the particle swarm optimiser. Fundamenta Informaticae 105, 4 (2010), 341–374. [16] Zavala, A. E. M. A comparison study of pso neighborhoods. In EVOLVE-A Bridge between Probability, Set Oriented Numerics, and Evolutionary Computation II. Springer, 2013, pp. 251– 265. 79