Generalized Self-Adapting Particle Swarm Optimization algorithm with archive of samples

2020·Arxiv

Abstract

Abstract

In this paper we enhance Generalized Self-Adapting Particle Swarm Optimization algorithm (GAPSO), initially introduced at the Parallel Problem Solving from Nature 2018 conference, and to investigate its properties. The research on GAPSO is underlined by the two following assumptions: (1) it is possible to achieve good performance of an optimization algorithm through utilization of all of the gathered samples, (2) the best performance can be accomplished by means of a combination of specialized sampling behaviors (Particle Swarm Optimization, Differential Evolution, and locally fitted square functions).

From a software engineering point of view, GAPSO considers a standard Particle Swarm Optimization algorithm as an ideal starting point for creating a generalpurpose global optimization framework. Within this framework hybrid optimization algorithms are developed, and various additional techniques (like algorithm restart management or adaptation schemes) are tested.

The paper introduces a new version of the algorithm, abbreviated as M-GAPSO. In comparison with the original GAPSO formulation it includes the following four features: a global restart management scheme, samples gathering within an R-Tree based index (archive/memory of samples), adaptation of a sampling behavior based on a global particle performance, and a specific approach to local search.

The above-mentioned enhancements resulted in improved performance of M-GAPSO over GAPSO, observed on both COCO BBOB testbed and in the black-box optimization competition BBComp. Also, for lower dimensionality functions (up to 5D) results of M-GAPSO are better or comparable to the state-of-the art version of CMA-ES (namely the KL-BIPOP-CMA-ES algorithm presented at the GECCO 2017 conference).

Keywords

1 Introduction

The quest for the highly efficient general purpose optimization algorithms, which started with the works on evolutionary computations by de Jong De Jong (1975) and Holland Holland (1992), resulted in creation of a few excellent optimization methods like Differential Evolution (DE) Storn and Price (1997) or Covariance Matrix Adaptation Evolution Strategy (CMA-ES) Hansen et al. (2003). Those methods have been thoroughly studied and gradually improved over the years following their initial presentation Poa´ık and Klema (2012); Loshchilov et al. (2013); Brest et al. (2016); Yamaguchi and Akimoto (2017).

The search for a universal optimization algorithm is a challenging task because optimization performance strongly depends on the type of an optimized function Wolpert and Macready (1997). Additionally, the works on theoretical convergence of random sampling based methods (i.e. Genetic Algorithms (GA) Eiben et al. (1991), Simulated Annealing (SA) Eiben et al. (1991) and Particle Swarm Optimization (PSO) Poli (2009); Van Den Bergh and Engelbrecht (2010)) are not necessarily helpful in practical setting of parameters for particular problem.

Proposed (M-)GAPSO framework provides a platform for seamless cooperation of various existing optimization approaches. It also attempts to separate auxiliary techniques (e.g. population initialization after algorithm’s stagnation) from the actual optimization engine (e.g. PSO’s particles sampling strategy).

While the resulting system built on M-GAPSO platform may be quite complex, each of its parts remain relatively unsophisticated and independent, so as to make analysis of its impact and improvement of its performance easier. This goal is achieved by taking a multi-agent view on the hybrid optimization. In this view, a single search operator is indifferent to how exactly the current solutions were computed, it only needs to receive their arguments and function value. This way, pure sampling-based approaches (e.g. PSO or DE) can be easily mixed with local function approximations, e.g. quasi-newton methods.

1.1 Contribution

The main contribution of this paper is five-fold:

• Designing framework in which sampling methods and model-based optimization approaches seamlessly cooperate in a common environment.

• Performing extensive experimental studies on COCO benchmark set Hansen et al. (2019), aimed at analyzing the impact of various optimization techniques and seeking efficient hybridization of various optimization methods.

• Achieving better results than the state-of-the-art CMA-ES Yamaguchi and Aki- moto (2017) for lower-dimen-sional functions (up to 5D) from COCO set with optimization budget.

• Accomplishing the 8th and the 4th place in the BBComp 2019 black-box optimiza-tion competition1 in single-objective and expensive single-objective tracks, respectively.

• Significantly improving the performance over the initial version of the GAPSO algorithm Uli´nski et al. (2018).

The rest of the paper is organized as follows. Section 2 provides a literature review, with special emphasis on hybrid optimization approaches. Section 3 presents the original GAPSO algorithm and discusses its components (with Sections 3.4 and 3.5.2 describing population re-initialization and model-based optimization, respectively). Section 4 summarizes results on the COCO benchmark set and those achieved during BBComp competitions. Section 5 concludes the paper.

2 Related literature

M-GAPSO is characterized by the following three main features: (1) hybridization of optimization techniques, (2) memory-based space sampling by means of caching, and (3) the focus on particular components of the solution method in the context of their relevance and contribution to the overall method’s efficacy.

In more detail, the work advocates the relevance of hybrid optimization methods which above all can gain from synergetic combination of advantages of the compound methods. The idea of combining two or more optimization techniques so as to mitigate the local minima problem and/or establish an optimal balance between exploration and exploitation Lynn and Suganthan (2015) in the solution search process has recently become highly popular in Computational Intelligence (CI) community. The most prominent forms of its realization include hyperheuristic approaches and heterogeneous methods. In hyperheuristic solutions, typically, a top-level algorithm is responsible for selection of the locally optimal method to be used in a particular (current) context van der Stockt and Engelbrecht (2018); Castro et al. (2018); Lin et al. (2017); Schl¨unz et al. (2018). Heterogeneous methods, on the other hand, directly combine either two or more heuristics (a typical approach is to enhance the main method by some kind of local optimization Loshchilov et al. (2013); Ma´ndziuk and ˙Zychowski (2016)) or to combine several variants of the same heuristic method Nepomuceno and Engel- brecht (2012); Montes de Oca et al. (2009); Harrison et al. (2017)). In either case the resulting optimization approach leads to a qualitatively new behavior with respect to the component methods. Witihin the domain of PSO algorithms, the problem of balancing exploration and exploitation can be also solved by introducing specialized subswarms Du and Li (2008); Lynn and Suganthan (2015).

Our particular focus is on a combination of PSO and DE, further enhanced by utilization of locally fitted square functions. While combinations of PSO and DE have been considered in the literature before, their further improvement stemming from locally fitted low-degree polynomials is - to our knowledge - proposed for the first time. The hybrids of PSO and DE have already proven to have potential extending beyond each of the component methods alone. For instance, Liu, Cai and Wang Liu et al. (2010) presented a hybrid algorithm combining PSO and DE, motivated by the fact that PSO activity is prone to stagnation when particles are unable to improve their personal best positions. In such a case DE is applied to update particles best positions and make the swarm jump out of the stagnation phase Yu et al. (2014); Zhan et al. (2009). The main difference between Liu et al. (2010) and our approach is that in Liu et al. (2010) DE is employed for searching for new personal best positions of particles while in our method samples of both PSO and DE are concurrently utilized during the whole optimization process.

A related idea is presented in the Brain Storm Optimization algorithm (BSO) pro-

posed in Shi (2011b,a), which is a swarm intelligence technique inspired by collective behavior of humans - specifically the brainstorming approach to problem solving. BSO addresses the local minima problem by means of applying both converging and diverging operations in the quest for a COP optimum Cheng et al. (2019); Shi (2011b).

Another key aspect of our method (besides hybridization of PSO and DE) is utilization of a memory-based approach by means of caching function values in sampled points and promoting the best-found particles (solutions) to the next generation. This way the allotted number of fitness function evaluations (FFEs) can be utilized in a more effective way, leading to visible improvement of results. In this context, one of the seminal papers is Taillard et al. (2001) in which the authors discuss the memory-based properties of several popular metaheuristic algorithms, point their similarities, and consequently propose a unified view of these methods. Since Taillard et al. (2001) does not include PSO in the presented analysis, exploration of the memory-based enhancements of PSO, proposed in this paper, seems to well complement the findings of Taillard et al. (2001).

The third focus of the paper is on the relevance of implementation of particular components of the optimization method (whether hybrid or pure) for its final efficacy. This research thread is a continuation of our previous works devoted to detailed analysis of this aspect in the case of pure (non-hybridized) PSO Okulewicz and Ma´ndziuk (2013); Okulewicz and Mandziuk (2014); Okulewicz and Ma´ndziuk (2017, 2019) and Memetic Algorithm Ma´ndziuk and ˙Zychowski (2016). Specifically, in Okulewicz and Mandziuk (2014); Okulewicz and Ma´ndziuk (2017) we analyzed a Two-Phase MultiSwarm Particle Swarm Optimizer (2MPSO) solving the Dynamic Vehicle Routing Problem (DVRP) Ma´ndziuk (2019) with the aim of finding an optimal configuration of several optimization improvement techniques dedicated to solving dynamic optimization problems within the 2MPSO framework. One of the main conclusions was that strong results achieved by 2MPSO should be mainly attributed to the following three factors: generating initial solutions with a clustering heuristic, optimizing the requests-to-vehicle assignment with a metaheuristic approach, and direct passing of solutions obtained in the previous stage (times step) of the problem solving procedure to the next stage.

Current research directly extends our three previous papers Okulewicz (2016); Uli´nski et al. (2018); Zaborski et al. (2019). The first one discussed the possibility of finding an optimal team of optimization agents based on Belbin’s Team Roles Inventory. The second one introduced the initial version of GAPSO algorithm as a hybrid of several variants of the PSO and DE methods. The third one presented initial results on model-based optimization behaviors within GAPSO framework.

3 Description of M-GAPSO

This section describes the proposed Generalized Self-Adapting Particle Swarm Optimization (GAPSO) Uli´nski et al. (2018) framework enhanced with samples archive (M-GAPSO). The framework is based on the PSO algorithm, but allows the usage of virtually any other optimization method whose “particles” act independently. Additionally, the algorithm’s restart manager, the archive (external memory) of samples and the algorithm’s search space manager are defined as auxiliary modules independent from the core optimization module. Algorithm 1 presents a high–level pseudocode of

M-GAPSO.

The underlying features of the M-GAPSO design can be listed as follows:

• it relies on well-researched optimization algorithms, • effectively utilizes samples already gathered by means of randomized search procedures (i.e. PSO, DE),

• guides the search process of the algorithm on the basis of already found local optima,

• keeps independence of the constituting modules to the highest possible extent.

The main components of M-GAPSO are presented in the UML class diagram (Fig. 1) and discussed in detail in the following subsections.

3.1 General swarm–based optimization framework

A starting point for the GAPSO design was a multi-agent view of the PSO algorithm Okulewicz (2016). In PSO, the particles can be seen as independent optimization agents, each exposing its historically best location only and maintaining its own current location and velocity. This view led to the most important design choice: a separation

Figure 1: The UML class diagram of M-GAPSO.

of particles’ locations from their velocity update formula. Subsequently, regarding velocity update just as a method of specifying the next location to be sampled by the algorithm, allowed utilization of any population-based self-governing optimization algorithm in GAPSO. Apart from various swarm-based approaches, it also meant the possibility of including other than PSO-like sampling equations (e.g. DE) in GAPSO framework Uli´nski et al. (2018).

On top of the separation of locations from a sampling behavior, the performance of each of the considered types of behavior is registered and used to update the respective probability of selecting a given behavior as a sampling mechanism.

M-GAPSO extends the above-described version of GAPSO with three more components, that can be implemented and configured independently from the core optimization algorithm:

• samples archive - serving as a cache and a source of additional information about optimized function,

• population state observer - serving as an algorithm restart manager, • high-level manager of the problem space exploration.

Figure 2: M-GAPSO outer loop sampling scheme. Black dots mark locations of local optima estimations, a black rectangle marks the area for initial swarm location in a given run, and a red rectangle marks the resulting distribution of samples in that run.

Additionally, the optimization behavior pool has been extended by adding local search approaches based on fitting quadratic and polynomial functions. Due to that change, Variable Neighborhood Search Mladenovi´c and Hansen (1997), utilized as the local search procedure at the end of the optimization process in the original GAPSO, has been removed.

The purpose of the samples archive is to enable efficient utilization of function values gathered during the solution search process.

The restart manager together with the search space manager guide the optimization algorithm towards promising areas of the problem space, when further exploitation of the currently searched area seems to be pointless. With such a design it is possible to extend the GAPSO framework and test the impact of optimization improvements somewhat independently of the main optimization engine.

On a final note, GAPSO is maintained as an open source application on the MIT license and is available at: .

3.2 Samples archive

In order to store and efficiently retrieve samples, M-GAPSO utilizes a multidimensional R-Tree index. After a series of preliminary experiments, a maximum capacity of samples index was capped at 20 000, as in some cases it grew too large to effi-ciently handle the samples. After reaching the maximum capacity, the index is restarted from scratch.

Figure 3: Possible M-GAPSO initialization bounding boxes generated during the op- timization process for the functions with (f15) and without (f24) a general structure.

3.3 Restart management

A current version of GAPSO uses an enhanced version of JADE Poa´ık and Klema (2012) restart manager. In a basic JADE approach a spread of population locations was considered and combined with the frequency of global optimum estimation improvements. In M-GAPSO the RestartManager registers iteration count intervals between global optimum updates, considers a spread of personal best locations of particles and additionally a spread of personal best locations values. The last feature was added in order to better handle step functions, where the population spread can be quite large, even though the population reached a sort of a frozen state, with each particle having exactly the same personal best value.

3.4 Initialization scheme

An initialization scheme relies on selecting a smaller bounding box as the initial search area on the basis of previously estimated function optima. Figure 2 presents a sample step of M-GAPSO re-initialization and multiple local optima estimations as the final result of such a procedure.

The initialization procedure includes the following possibilities:

• starting from the original (full) bounding box defined for the optimized function, • starting from a random bounding box defined by boundaries derived from locations of the local optima estimations,

• starting from a small bounding box centered around the high-quality optimum estimation.

One of those actions is selected at random with probabilities set by the user of MGAPSO. Figure 3 visualizes possible bounding boxes for initializing the M-GAPSO population, created on the basis of optima estimations during the previous optimization process.

3.5 Optimization behaviors

One of the main conclusions from our initial work on GAPSO Uli´nski et al. (2018) was that the highest synergy among optimization behaviors could be observed when DE and PSO are utilized, instead of a pool of various PSO variants (i.e. Standard PSO, Charged PSO, Fully-Informed PSO). Therefore, the behavior pool considered in M-GAPSO consists of SPSO-2007 Kennedy and Eberhart (1995); Clerc (2012), DE/best/1/bin Storn and Price (1997) (previously used in Uli´nski et al. (2018)) and the local modeling technique (proposed in this paper) that employs quadratic and polynomial functions.

3.5.1 PSO and DE behaviors

The utilization of the SPSO-2007 within M-GAPSO framework is straightforward, as the framework is based on that algorithm. Addition of DE behavior required a slight adjustment, as original DE does not include a notions of individual’s velocity and current location. Therefore, when DE behavior is applied, the particle’s velocity is computed as follows:

The same approach is utilized in implementation of any other behavior not supporting the idea of velocity. One of the consequences of the above assumption is the loss of previously computed velocity, resulting in its reset. However, the new velocity still makes sense from the point of view of SPSO-2007 behavior. Please observe that, if a particle’s move is successful (i.e. is updated), this particle (when treated with the PSO behavior) will continue to move roughly in the direction that already improved its value. This direction might be perturbed only by the attraction vector of the best neighbor location.

3.5.2 Quadratic and polynomial model-based behaviors

In order to support fast convergence to local optima, the pool of behaviors was supplemented by model-based approaches Zaborski et al. (2019), which utilize samples already gathered in randomized behaviors (such as PSO and DE). For all model behaviors a sample archive uses an R-Tree data structure which proven efficient in handling these samples.

Quadratic model is fitted on a data set made of k samples nearest (in the Euclidean metric) to location of the particle for which the quadratic behavior has been selected (see Fig. 4 for an example). Quadratic function based approach fits the following model:

where is a vector of coordinates.

Ordinary Least Squares method is applied to obtain linear regression coefficients: and . Finding minimum of is equivalent to finding dim independent minima of dim independent parabolas .

Figure 4: Comparison of data sets of samples used for fitting quadratic and polynomial models.

Coordinates of the bounded parabola peak are computed in the following way:

where and are lower and upper bounds of the function domain, respectively.

Polynomial model enhances the quadratic model in the following way:

where is coordinate in a given dimension.

The polynomial model is fitted separately in each dimension. For each dimension d, the fitting data set is composed of k samples nearest to a line with coordinates fixed to the current location except for dimension d. The differences between methods of gathering samples in both models (quadratic and polynomial) are depicted in Fig. 4.

A coordinate of the minimum of the bounded polynomial is computed using grid search. For each dimension d, a space between and is divided into 1000 regular points, where and are respectively minimum and maximum coordinates in dimension d derived from the fitting data set. A function value (4) is calculated in each of these 1000 points and the smallest one determines the optimal coordinate . A vector of all (for all dimensions) defines the next sampling point.

Figure 5: Fractions of using various behaviors during a single algorithm’s run (i.e. till a restart). Black dots denote whether in a given iteration a global optimum value was improved.

3.6 Adaptation scheme

Adaptation scheme in M-GAPSO, for each optimization behavior takes into account its contributions to the improvement of the global best value. These contributions are aggregated by a moving average scheme (separately for each optimization behavior) and normalized in order to account for the number of times a given behavior was applied. This procedure is different than GAPSO adaptation scheme, which considered the average improvement of the local optimum estimation (i.e. against the former value of for each of the particles).

Figure 5 presents the effects of applying adaptation scheme in a single run of the algorithm. In the first few iterations the fractions of using various behaviors oscillate around predefined values set by the algorithm user. Afterwards the currently best performing behavior starts to dominate over the others in terms of the frequency of its application. In the final phase, all behaviors have pairwise equal probabilities of their application due to prolonged lack of improvement. If such a situation lasts for a certain (user defined) number of iterations, the algorithm is reset (cf. Section 3.3).

4 Experimental evaluation of M-GAPSO

M-GAPSO was tested on the COCO BBOB benchmark set and also took part in the BBComp competition.

Table 1: Settings of the M-GAPSO method

4.1 COCO BBOB benchmark results

The main assessment of M-GAPSO performance was made on 24 noiseless continuous functions from COCO BBOB data set. The algorithm has been run once on 15 instances for each of the functions, which is a standard procedure for this benchmark set. Using this particular benchmark allowed for a straightforward comparison with results obtained by various other optimization algorithms, as the benchmark comes with a database of results sent for evaluation in BBOB workshops.

The goal of the experiments was to assess the efficacy of various methods implemented within M-GAPSO framework, to compare M-GAPSO with its previous version (GAPSO), and to observe its performance versus state-of-the-art optimization algorithms. Values of M-GAPSO parameters (presented in Table 1) were set partly based on the literature and partly based on results of preliminary tests.

4.1.1 Improvements over GAPSO and comparison with one of the CMA-ES versions (state-of-the-art)

Figure 6 presents results of the experiments with optimization budget, on 2D, 5D, 10D and 20D benchmark functions. Three M-GAPSO configurations are compared with GAPSO Uli´nski et al. (2018) and one of the state-of-the-art versions of CMA-ES Yamaguchi and Akimoto (2017). All three GAPSO configurations utilize behaviors mixing (cf. line 21 in pseudocode of Algorithm 1), model-based behaviors and improved initialization scheme. PDLPr is the fastest approach, as it does not apply adaptation in any form. PDLar uses a square function model-based behavior only and includes behaviors’ adaptation. PDLPar includes all features discussed in this paper, but (as presented in Figure 7) is quite slow compared to the other two approaches and was unable to produce results for 20D functions within reasonable amount of time.

Figure 6: Results of M-GAPSO versus GAPSO and one of the state-of-the-art variants of CMA-ES.

4.1.2 Performance analysis of M-GAPSO components

The baseline experiment selects DE/best/1/bin as the sole behavior in M-GAPSO. This basic configuration is compared with three other approaches, each of them including additional features. The first enhancement consists in adding local neighborhood SPSO-2007 to behavior pool. The second one adds model based optimization behaviors (cf. Section 3.5.2). The final enhancement relies on adding behaviors adaptation and restart management that refers to previously found optima.

Performance plots of the 4 above-mentioned M-GAPSO configurations are presented in Figure 8. Enhancing behavior pool with local neighborhood SPSO-2007 algorithm, and subsequently with square and polynomial function based local optimizers, brings observable improvement in the case of 5D benchmark functions. Adaptation of behaviors and restart management improves the results also on 20D functions. A summary of function types with at least one successful run and the overall percentage of successful algorithm runs are presented in Tables 2 and 3, respectively. Additionally, Figure 7 presents the average computation times for various M-GAPSO configurations.

Figure 7: The average function value evaluation time of various M-GAPSO configura- tions with respect to function dimension.

With DE considered to be a baseline algorithm, the following conclusions could be stated: (1) Switching off samples’s caching results in around 3 times faster computations. (2) Mixing DE with PSO does not affect the speed significantly, while including model-based behaviors leads to 4 times slower computation than that in the baseline experiment. (3) The most significant disadvantage, in terms of the average computation time of a single function evaluation, is caused by simultaneous inclusion of model based approaches and the adaptation mechanism. The reason for that slowdown are algorithm iterations in which no improvement was observed for a certain amount of time. Therefore, the adaptation mechanism guided around half of the function evaluations to be made by one of the model based approaches (these methods related to samples memory are inherently slower than sampling based PSO and DE behaviors).

In order to further investigate which of the particular methods had the highest impact on M-GAPSO results, several additional experiments were performed. Their goal was to address the following questions:

• Should performance difference between plain DE and DE hybridized with PSO, be attributed to the adaptation of behaviors mechanism or is it simply enough to mix these behaviors among particles?

• How performance of the algorithm is affected by an addition of model based optimization behaviors?

• How selection of the swarm initialization strategy (i.e. selection of a bounding box for population initialization) influences the algorithm’s performance?

• Would a combination of all of the above-mentioned aspects (adaptation, modelingbased behaviors, restart strategies) demonstrate the advantage over application of each of them alone?

• How does M-GAPSO fare against its previous version (GAPSO) and against state-of-the-art variant of CMA-ES?

Figure 8: Results of various M-GAPSO configurations on 5D (left column) and 20D (right column) functions from COCO BBOB.

Table 2: Numbers of distinct function types obtained by each algorithm for the re- spective optimization precision target (Value) on 5D and 20D benchmark functions, respectively.

Table 3: Percentage rates of successfully completed runs by each algorithm for the re- spective optimization precision target (Value) on 5D and 20D benchmark functions, respectively.

In order to assess the impact of behaviors mixing and that of adaptation mechanism, M-GAPSO (utilizing DE and PSO) was run in three configurations. Figure 9 presents the results. In the first configuration (denoted PDnm) the behaviors of particles were set at the beginning of the optimization process. In the second one (denoted PD) the probabilities of behaviors were manually set up at the beginning, but assignment of behaviors to particles took place before each iteration. In the third one (denoted PDa) the behaviors probabilities were adapted during the entire optimization process, and assignment of behaviors to particles was made before each iteration. It can be observed that addition of behaviors mixing mechanism (cf. line 21 of the pseudocode of Algorithm 1) before each iteration has a clearly and positive impact on the performance of the PSO-DE hybrid. Meanwhile, the adaptation procedure influences the algorithm’s performance only for some function dimensions. However, in order to outrank a pure DE algorithm, both these techniques were necessary.

Since the behaviors mixing procedure proven to be undoubtedly useful, this technique will be used in all remaining experiments. While the adaptation mechanism is also clearly important, its application increases computational cost in the case of model-based behaviors (cf. Figure 7). Hence, adaptation will be applied only in a selected subset of experiments.

Figure 9: Results of M-GAPSO on 2D, 3D, 5D, 10D, 20D and 40D COCO BBOB func- tions: PSO and DE behaviors applied within a static particles’ behavior pool setup (PDnm), a setup with behaviors mixed among particles before each iteration (PD), and a setup with adapted behaviors pool (PDa).

Figure 10: Results of M-GAPSO on 2D, 3D, 5D, 10D, 20D and 40D COCO BBOB func- tions for various combinations of PSO, DE and linear and polynomial models from the behavior pool.

Figure 11: The effects of M-GAPSO restart mechanism which refers to the previously found optima. Results on 2D, 3D, 5D, 10D, 20D and 40D COCO BBOB functions.

The focus of the first experiment is on assessment of the quadratic and polynomial model behaviors. Figure 10 depicts cumulative plots of function evaluation counts required to reach an optimization target for the 5 following configurations: baseline PSO and DE behaviors (denoted PD); baseline PSO and DE behaviors with additional square model applied during population initialization phase (PDiL); PSO, DE and square model behaviors (PDL); PSO, DE and polynomial model behaviors (PDP); and PSO, DE, square model and polynomial model behaviors (PDLP). In all of the above config-urations behaviors were mixed. In the resulting plots one can generally observe that having anyone of model-based behaviors is beneficial. Additionally, configurations with more variable model-based behaviors performed slightly better in terms of found optima. As a side note, it should be mentioned that the square model was significantly faster than the polynomial one, due to smaller number of utilized samples and simpler formula for optimum identification.

The last mechanism to be tested is the initialization scheme, described in Section 3.4, with the aim of identifying the area for potential future improvements of M-GAPSO. Figure 11 presents the results of four configurations. Two of them (PDL and PDLP) were copied from the previous experiment, while the two others (PDLr and PDLPr) are their counterparts, with improved initialization scheme in place of a simple population reset. The results show that the improved initialization procedure has indeed potential, for instance for 10D functions PDLPr is clearly better than PDLP and PDLr outperforms PDL.

4.2 BBComp competition results

Figure 12: Summarized results from the BBComp black-box optimization competition in single objective function setup in years 2018 and 2019. GAPSO (2018) and M-GAPSO (2019) algorithms were fielded by our mini-mlog team.

GAPSO and M-GAPSO were evaluated against other optimization approaches during black-box optimization competition BBComp2 at GECCO conferences. Summarized results of 2018 and 2019 editions are depicted in Fig. 12. GAPSO run by the authors’ faculty team mini-mlog scored a 10th place (out of 15 competitors) in standard single objective optimization and an 8th place (out of 13) in the expensive single objective optimization tracks in 2018. M-GAPSO improved those results in 2019, and was classified

Figure 13: Plot of the cumulative relative results of GAPSO (2018), M-GAPSO (2019) and the winning approaches from 2018 and 2019, respectively, in the standard single goal optimization setup.

6th (out of 10) in standard setup and 4th (out of 9) in the expensive optimization track. In both cases M-GAPSO performed better in 2019, than GAPSO did in 2018, however, the relative difference between results obtained by the authors’ approach and the best approach was reduced only in the standard setup (cf. Fig. 13), while remained roughly the same in the expensive setup (see Fig. 14).

5 Conclusions

The results obtained by M-GAPSO on COCO BBOB benchmark set Hansen et al. (2019) and in the BBComp competition (https://bbcomp.ini.rub.de/) are very promising for lower-dimensional functions. At the same time further work is needed to make M-GAPSO competitive also for higher-dimensional functions.

The results support the claim that the behavior pool should consist of significantly variable sampling methods. The outcomes presented in Fig. 10 confirm that it is definitely beneficial to supplement PSO and DE with either of the function modeling behaviors, although concurrent use of both linear and polynomial models does not lead to visible performance improvement. These model-based approaches improved a general performance of M-GAPSO mainly by efficiently solving instances of f1 (spherical) and f5 (linear) BBOB functions, however some improvement during the initial function evaluations was also observable. Furthermore, the success of the PSO+DE hybrid approach should be mainly attributed to the mixing of behaviors mechanism, rather than to adaptation of the behavior pool (see Fig. 9).

Generally speaking, the improvement introduced in M-GAPSO allowed achieving comparable results with state-of-the-art CMA-ES Yamaguchi and Akimoto (2017) for lower dimensions (up to 5D) and greatly improved performance over the original GAPSO formulation Uli´nski et al. (2018) (see Fig. 6). This improvement can be par-

Figure 14: Plot of the cumulative relative results of GAPSO (2018), M-GAPSO (2019) and the winning approaches from 2018 and 2019, respectively, in the expensive single goal optimization setup.

tially attributed to the already mentioned samples caching, the addition of modeling approaches, and focusing on mixing behaviors. Significant part of the improvement came from changing the underlying philosophy of the method. When deciding on the GAPSO’s reset and adaptation mechanisms, we were focused on preventing the potential swarm collapse (during the algorithm’s run), which was motivated by a theoretical perspective of global optimization algorithms. Within this view, the algorithm should be constructed in a way which ensures that the limit of probability of including a global optimum in the set of tested solutions approaches 1, as the number of algorithm’s iterations n approaches infinity Eiben et al. (1991).

With M-GAPSO we took a different approach, where individual particles focus only on the task at hand (relatively quick convergence to high-quality local optimum), and the burden of exploration lies on higher level mechanisms: the convergence detector (RestartManager) and re-initialization module (SearchSpaceManager).

Our future research is concentrated on utilization of the knowledge of multiple local optima estimations. As could have been observed in Figure 2 positions of local optima gathered during the optimization process may form predictable structures which we plan to exploit in our future research. M-GAPSO should greatly benefit from a more structured approach to selecting search space boundaries in subsequent algorithm runs. Therefore, we believe that multiple and relatively short algorithm runs, combined with predictive setup of the algorithm search space boundaries are the key factors in further improvement of M-GAPSO results.

References

Brest, J., Maucec, M. S., and Boskovic, B. (2016). iL-SHADE: Improved L-SHADE algorithm for single objective real-parameter optimization. In 2016 IEEE Congress on Evolutionary Computation (CEC), pages 1188–1195. IEEE.

Castro, O. R., Fritsche, G. M., and Pozo, A. (2018). Evaluating selection methods on hyper-heuristic multi-objective particle swarm optimization. Journal of Heuristics, 24(4):581–616.

Cheng, S., Lu, H., Lei, X., and Shi, Y. (2019). Brain Storm Optimization Algorithms: More Ques- tions than Answers. pages 3–32.

Clerc, M. (2012). Standard particle swarm optimisation.

De Jong, K. A. (1975). Analysis of the behavior of a class of genetic adaptive systems. Phd thesis, University of Michigan.

Du, W. and Li, B. (2008). Multi-strategy ensemble particle swarm optimization for dynamic optimization. Information Sciences, 178(15):3096–3109.

Eiben, A. E., Aarts, E. H. L., and Van Hee, K. M. (1991). Global convergence of genetic algorithms: A markov chain analysis. pages 3–12.

Hansen, N., Brockhoff, D., Mersmann, O., Tusar, T., Tusar, D., ElHara, O. A., Sampaio, P. R., Atamna, A., Varelas, K., Batu, U., Nguyen, D. M., Matzner, F., and Auger, A. (2019). COmparing Continuous Optimizers: numbbo/COCO on Github.

Hansen, N., M¨uller, S. D., and Koumoutsakos, P. (2003). Reducing the Time Complexity of the Derandomized Evolution Strategy with Covariance Matrix Adaptation (CMA-ES). Evolutionary Computation, 11(1):1–18.

Harrison, K. R., Engelbrecht, A. P., and Ombuki-Berman, B. M. (2017). An adaptive particle swarm optimization algorithm based on optimal parameter regions. In 2017 IEEE Symposium Series on Computational Intelligence (SSCI), pages 1–8. IEEE.

Holland, J. H. (1992). Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. MIT Press.

Kennedy, J. and Eberhart, R. C. (1995). Particle Swarm Optimization. Proceedings of IEEE International Conference on Neural Networks. IV, pages 1942–1948.

Lin, J., Wang, Z.-J., and Li, X. (2017). A backtracking search hyper-heuristic for the distributed assembly flow-shop scheduling problem. Swarm and Evolutionary Computation, 36:124–135.

Liu, H., Cai, Z., and Wang, Y. (2010). Hybridizing particle swarm optimization with differential evolution for constrained numerical and engineering optimization. Applied Soft Computing, 10(2):629–640.

Loshchilov, I., Schoenauer, M., and S`ebag, M. (2013). BI-population CMA-ES Algorithms with Surrogate Models and Line Searches. In GECCO ’13 Companion Proceedings of the 15th annual conference companion on Genetic and evolutionary computation, pages 1177–1184.

Lynn, N. and Suganthan, P. N. (2015). Heterogeneous comprehensive learning particle swarm optimization with enhanced exploration and exploitation. Swarm and Evolutionary Computation, 24:11–24.

Ma´ndziuk, J. (2019). New shades of the Vehicle Routing Problem: Emerging problem formula- tions and Computational Intelligence solution methods. IEEE Transactions on Emerging Topics in Computational Intelligence, 3(3):230–244.

Ma´ndziuk, J. and ˙Zychowski, A. (2016). A memetic approach to vehicle routing problem with dynamic requests. Applied Soft Computing, 48:522–534.

Mladenovi´c, N. and Hansen, P. (1997). Variable neighborhood search. Computers & operations research, 24(11):1097–1100.

Montes de Oca, M. A., Pena, J., Stutzle, T., Pinciroli, C., and Dorigo, M. (2009). Heterogeneous particle swarm optimizers. In 2009 IEEE Congress on Evolutionary Computation, pages 698–705.

Nepomuceno, F. V. and Engelbrecht, A. P. (2012). A Self-adaptive Heterogeneous PSO Inspired by Ants. In International Conference on Swarm Intelligence, pages 188–195.

Okulewicz, M. (2016). Finding an Optimal Team. In Position Papers of the 2016 Federated Conference on Computer Science and Information Systems, pages 205–210. Polish Information Processing Society.

Okulewicz, M. and Ma´ndziuk, J. (2013). Application of Particle Swarm Optimization Algorithm to Dynamic Vehicle Routing Problem. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 7895:547–558.

Okulewicz, M. and Mandziuk, J. (2014). Two-phase multi-swarm PSO and the dynamic vehicle routing problem. In 2014 IEEE Symposium on Computational Intelligence for Human-like Intelligence (CIHLI), pages 1–8, Orlando, Fl, USA. IEEE.

Okulewicz, M. and Ma´ndziuk, J. (2017). The impact of particular components of the PSO-based algorithm solving the Dynamic Vehicle Routing Problem. Applied Soft Computing, 58:586–604.

Okulewicz, M. and Ma´ndziuk, J. (2019). A metaheuristic approach to solve Dynamic Vehicle Routing Problem in continuous search space. Swarm and Evolutionary Computation, 48:44–61.

Poa´ık, P. and Klema, V. (2012). JADE, an adaptive differential evolution algorithm, benchmarked on the BBOB noiseless testbed. In Proceedings of the fourteenth international conference on Genetic and evolutionary computation conference companion - GECCO Companion ’12, page 197, New York, New York, USA. ACM Press.

Poli, R. (2009). Mean and Variance of the Sampling Distribution of Particle Swarm Optimizers During Stagnation. IEEE Transactions on Evolutionary Computation, 13(4):712–721.

Schl¨unz, E. B., Bokov, P. M., and van Vuuren, J. H. (2018). Multiobjective in-core nuclear fuel management optimisation by means of a hyperheuristic. Swarm and Evolutionary Computation, 42:58–76.

Shi, Y. (2011a). An Optimization Algorithm Based on Brainstorming Process. International Journal of Swarm Intelligence Research, 2(4):35 – 62.

Shi, Y. (2011b). Brain Storm Optimization Algorithm. In Tan, Y., Shi, Y., Chai, Y., and Wang, G., editors, Advances in Swarm Intelligence, pages 303–309, Berlin, Heidelberg. Springer Berlin Heidelberg.

Storn, R. and Price, K. (1997). Differential Evolution – A Simple and Efficient Heuristic for global Optimization over Continuous Spaces. Journal of Global Optimization, 11(4):341–359.

Taillard, ´E. D., Gambardella, L. M., Gendreau, M., and Potvin, J.-Y. (2001). Adaptive memory programming: A unified view of metaheuristics. European Journal of Operational Research, 135(1):1– 16.

Uli´nski, M., ˙Zychowski, A., Okulewicz, M., Zaborski, M., and Kordulewski, H. (2018). Generalized Self-adapting Particle Swarm Optimization Algorithm. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), volume 3242, pages 29–40. Springer, Cham.

Van Den Bergh, F. and Engelbrecht, A. P. (2010). A convergence proof for the particle swarm optimiser. Fundamenta Informaticae, 105(4):341–374.

van der Stockt, S. A. G. and Engelbrecht, A. P. (2018). Analysis of selection hyper-heuristics for population-based meta-heuristics in real-valued dynamic optimization. Swarm and Evolutionary Computation, 43:127–146.

Wolpert, D. H. and Macready, W. G. (1997). No free lunch theorems for optimization. IEEE transactions on evolutionary computation, 1(1):67–82.

Yamaguchi, T. and Akimoto, Y. (2017). Benchmarking the novel CMA-ES restart strategy using the search history on the BBOB noiseless testbed. In GECCO ’17 Proceedings of the Genetic and Evolutionary Computation Conference Companion, pages 1780–1787.

Yu, X., Cao, J., Shan, H., Zhu, L., and Guo, J. (2014). An adaptive hybrid algorithm based on particle swarm optimization and differential evolution for global optimization. The Scientific World Journal, 2014:215472.

Zaborski, M., Okulewicz, M., and Ma´ndziuk, J. (2019). Generalized Self-Adapting Particle Swarm Optimization algorithm with model-based optimization enhancements. In Proceedings of 2nd PPRAI Conference, pages 380–383.

Zhan, Z.-H., Zhang, J., Li, Y., and Chung, H. S.-H. (2009). Adaptive particle swarm optimization. IEEE transactions on systems, man, and cybernetics. Part B, Cybernetics : a publication of the IEEE Systems, Man, and Cybernetics Society, 39(6):1362–1381.