Variable Population Memetic Search: A Case Study on the Critical Node Problem

2019·arXiv

Abstract

I. INTRODUCTION

Memetic algorithms (MAs) are hybrid metaheuristics that combines local optimization and evolutionary search [27]. By hybridizing these two different search methods, MAs are expected to benefit from their complementary search strategies. Since their introduction, MAs have been applied with success to numerous search problems including popular NPhard problems (e.g., graph coloring [31], maximum diversity

This work was partially supported by the National Natural Science Foundation of China under Grant 61903144, the Shanghai Sailing Program under Grant 19YF1412400, the Fundamental Research Funds for the Central Universities of China under Grant 222201817006, and the Shenzhen Science and Technology Innovation Commission under Grant JCYJ20180508162601910. (Corresponding authors: Jin-Kao Hao and Zhang-Hua Fu.)

Y. Zhou and Z. Wang are with the School of Information Science and Engineering, East China University of Science and Technology, 130 Meilong Road, 200237 Shanghai, China. Y. Zhou is also with the Key Laboratory of Advanced Control and Optimization for Chemical Processes, Ministry of Education (e-mails: ymzhou@ecust.edu.cn, wangzhe@ecust.edu.cn).

J.-K. Hao is with the Department of Computer Science, LERIA, Universit´e d’Angers, 2 Boulevard Lavoisier, 49045 Angers, France and the Institut Universitaire de France, 1 rue Descartes, 75231 Paris, France (e-mail: jinhao.hao@univ-angers.fr).

Z. Fu is with the Robotics Laboratory for Logistics Service, Institute of Robotics and Intelligent Manufacturing, The Chinese University of Hong Kong and the Shenzhen Institute of Artificial Intelligence and Robotics for Society, 518172 Shenzhen, China (e-mail: fuzhanghua@cuhk.edu.cn).

X. Lai is with the Institute of Advanced Technology, Nanjing University of Posts and Telecommunications, 210023 Nanjing, China (e-mail: laixiangjing@gmail.com).

[45], and quadratic assignment [7]) and practical applications (e.g., identification of critical nodes in sparse graphs [47], influence maximization in multiplex networks [42], vehicle routing [15]). Comprehensive surveys of recent research in memetic computation and additional application examples can be found in, e.g., [10], [29].

To design an effective memetic algorithm for a given problem, one needs to specify a number of algorithmic components including the local optimization procedure, the crossover operator, and the pool updating strategy [24]. Additionally, since MAs rely on a population of individuals, the population size needs to be identified as well. Our literature review indicates that existing studies on MA applications focus mainly on designing algorithmic components such as local optimization and crossover, while the population size is typically fixed to a constant value which is kept unchanged during the search.

Meanwhile, it is known that for a memetic algorithm, the population size impacts its solution quality and the running time [18]. Indeed, there is a general consensus that a small population implies a low population diversity and may lead to premature convergence of the algorithm, whereas a large population promotes diversity, nevertheless consumes more computational resources. Moreover, for a population-based evolutionary algorithm, it is recognized that the optimal population size depends on the problem instance under consideration [14] and can even vary at different evolution stages of the algorithm [43]. Specifically, for MAs in discrete optimization, the importance of selecting a proper population size was investigated in the context of solving a particular assignment problem [22] and to our knowledge, this is the only study in the literature dedicated to population sizing for MAs applied to combinatorial problem.

In this work, we present variable population memetic search (VPMS) where a strategic population sizing mechanism is integrated to the memetic computation framework. This work was motivated by the importance of MAs and the scarcity of research on dynamic population sizing in MAs. We summarize the contributions of the work as follows.

First, from an algorithmic perspective, the proposed variable population memetic search enhances the memetic computation framework with a strategic population sizing mechanism to dynamically influence the balancing between exploration and exploitation. A VPMS algorithm starts its search with a small population of two individuals (solutions) to favor exploitation. Upon reaching local optima solutions, the population is augmented with new high-quality solutions to strengthen population diversity and enhance exploration of the search space. When the population reaches a maximum allowable size while the search is still stagnating, it is shrunk to two individuals while maintaining the best solution found so far to start a new round of exploitation and exploration. This strategic population sizing mechanism helps the MA algorithm to make its search more focused and more effective.

Second, from a computational perspective, we apply the proposed method to solving the challenging (NP-hard) critical node problem (CNP). For this purpose, we integrate a dedicated local improvement procedure (named diversified late acceptance search) and a structured crossover (called doublebackbone crossover) within the variable population memetic search framework. We demonstrate the competitiveness of the resulting VPMS algorithm on two sets of 42 synthetic and real-world benchmark instances in the literature compared to the best-performing CNP methods. Specifically, our VPMS algorithm matches the best-known results for 23 instances and notably discovers new record results (improved upper bounds) for 13 instances. It is also the first heuristic algorithm able to steadily reach the optimal solutions for all 9 instances with known optima in only one minute.

Finally, the proposed VPMS method is of generic nature and can help to design effective memetic algorithms for solving various (combinatorial) problems. It can also be used to boost an existing MA by integrating within it the strategic population sizing mechanism introduced in this work. As such, it is expected that the VPMS method contributes favorably to better solve numerous optimization problems.

The rest of this paper is organized as follows. Section II presents a brief literature review of studies on population sizing in evolutionary algorithms. Section III introduces the proposed VPMS approach. Section IV shows the case study of applying the general VPMS approach to the critical node problem, including detailed computational results and comparisons with state-of-the-art CNP algorithms. Finally, Section V summarizes the work with potential research perspectives.

II. RELATED WORK ON POPULATION CONTROL IN EVOLUTIONARY ALGORITHMS

Evolutionary algorithms (EAs) are population-based computation methods. One important issue concerning EAs is population control. Indeed this issue has been investigated in a number of studies in the literature mainly on continuous optimization [17]. These studies can be divided into two categories, namely deterministic methods and adaptive methods.

Deterministic methods change the population size during the evolution process according to some deterministic rules. For example, Fern´andez et al. [16] proposed a method based on the phenomena of plague, in which a fixed number of bad individuals are removed at each generation. Instead of removing individuals at each generation, Brest et al. [8] presented a method, which starts from a small population size. Then, the population is increased with a specific size determined by a constant value and then reduced by half during the evolution. Besides increasing or decreasing a specific number of individuals after each specific number of generations during evolution, a few methods have been proposed to automatically adjust the size of population based on predefined functions. For example, Koumousis et al. [23] introduced functions with saw-tooth shape for adjusting the population size.

Adaptive methods utilize feedback information from the search to determine the direction and magnitude of change of population size. For example, Arabas et al. [3] presented a genetic algorithm with variable population, which eliminates the population size as an explicit parameter by using features such as “age” and “maximal lifetime” of individuals. Eiben et al. [14] introduced a technique that grows the population in case of high fitness improvement or long lasting stagnation, while shrinking the population in case of short period stagnation. Besides the fitness of individuals, information on fitness diversity of the population was also used to control the population size. For example, Tirronen and Neri [38] proposed a method based on fitness diversity measured by the distances between pairs of individuals along with their fitness values to control population size.

Although considerable studies have been performed on population control in EAs, existing studies are not fully suitable for memetic algorithms because of the totally different algorithm dynamics [22]. Moreover, compared to population control in EAs for continuous problems, very few effort has been made on memetic algorithms (MAs) for combinatorial problems. To our knowledge, the only study on population sizing in discrete MAs was presented in [22]. In their work, Karapetyan and Gutin presented a memetic algorithm for the multidimensional assignment problem, where the population size is adjustable according to a function of the average running time of the local optimization component.

In addition to the scarceness of investigations on population control in MAs for discrete problems, it is surprising to observe that the most recent studies on population control dated back to 2012. In this work, we fill the gap by proposing variable population memetic search (see Section III) which enhances the memetic search framework with a strategic population sizing mechanism.

III. VARIABLE POPULATION MEMETIC SEARCH

In this section, we present the variable population memetic search (VPMS) framework, which introduces a strategic population sizing mechanism into memetic algorithms.

A. General scheme

Like any population-based search algorithm, the performance of a memetic algorithm depends critically on its ability of maintaining a suitable balance of exploration and exploitation of the search space. The proposed variable population memetic search (VPMS) framework aims to encourage such a search balance via a dynamic population sizing mechanism.

From a search perspective, the VPMS approach starts with a small population of two individuals (solutions) to favor exploitation and then strategically adjusts the populations size to influence the population diversity and thus the balance of exploitation and exploration.

From an algorithmic perspective, VPMS mainly consists of five components: population building (Section III-B), solution construction (Section III-C), local improvement (Section III-D), population updating (Section III-E) and population sizing (Section III-F). As shown in Algorithm 1, VPMS starts with an elite population of only two solutions that are obtained by the PopulationBuilding() procedure (line 4). From this small elite population, VPMS enters a “while” loop (lines 8-26) to perform its evolutionary search until a given stopping condition is satisfied. At each generation, two or more parents are selected to create an offspring solution based on the SolutionConstruction() procedure (line 10). Afterwards, the offspring solution is further improved by the LocalImprovement() procedure (line 12). The improved offspring solution is then inserted into the population according to the PopulationUpdating() procedure (line 22). In addition to these basic components of a general memetic algorithm, the proposed VPMS approach specifically integrates a new component to dynamically control the population size according to the PopulationSizing() procedure (line 24). With the help of its strategic population sizing mechanism, the algorithm adapts (i.e., increases or decreases) its population size according to the current search status.

27 end

28 return the best solution found

B. Population building

VPMS uses a population building strategy to build an initial population. Specifically, an initial solution is first generated by a random or greedy construction method, and then improved by a local improvement procedure. A second high quality solution is generated in the same way. Our population building strategy distinguishes itself from the general strategy by using a small population of only two solutions. This is based on two particular considerations. First, building an initial population of multiple high-quality solutions may be timeconsuming. In some settings where a time limit is given, the allowable time can fully be consumed during the population building phase, leaving no time for further search (see [47] for an example). Second, at the beginning of the search, since the search space is not examined yet, it is desirable to perform an intensified search to locate as fast as possible some first high-quality local optima.

C. Solution construction

Solution construction is an important component of a memetic algorithm and forms one leading force for exploration. It aims to create new solutions (offspring) by blending existing solutions. Crossover is a widely-used method to generate offspring solutions, which is responsible for exploring new search areas of the solution space. Crossover operators usually considers two or more parents to form one or more offspring solutions. Various crossover operators have been developed and studied in the literature for different representations [30], such as single point crossover, uniform crossover, partially matched crossover, and order crossovers. In addition to these (general) operators, it is often advantageous to design dedicated crossovers that enable the offspring solutions to inherit meaningful features (building blocks) of the studied problem from the parent solutions. For example, several specific crossovers based on the idea of “backbone” were proposed for problems such as graph coloring [21], [31] and critical nodes identification [47]. Finally, other solution construction methods have also studied. For example, Martins et al. [26] developed a pattern based solution construction method, which tries to construct offspring based on common patterns mined from a set of elite solutions.

D. Local improvement

Local improvement plays a critical role in a memetic algorithm and ensures essentially the role of intensive exploitation of the search space by focusing on a limited region. The local improvement procedure can benefit from many general local search methods [19] such as hill climbing, simulated annealing, tabu search, threshold accepting, and variable neighborhood search. Still, these general methods need to be adapted to the given problem in particular by designing suitable search components (e.g., neighborhoods). For example, Segura et al. [33] integrated a simple stochastic hill climbing into a memetic algorithm for the frequency assignment problem. Benlic and Hao [7] used breakout local search as the local improvement procedure of an effective memetic algorithm for quadratic assignment. Tang et al. [37] applied within their memetic algorithm an extended neighborhood search procedure for capacitated arc routing. Wu et al. [44] developed a game-based memetic algorithm for vertex cover of networks, where local improvement is based on an asynchronous updating best response rule of snowdrift game. For the critical node problem of Section IV, our local improvement procedure is based on a diversified late acceptance search algorithm [28].

E. Population updating

For each offspring solution constructed by the solution construction component (Section III-C) and further improved by the local improvement component (Section III-D), a decision is made to determine whether and how the offspring solution is inserted into the population according to a population updating strategy. For this purpose, existing population replacement strategies can be used in the VPMS approach. For instance, a popular population updating strategy replaces the worst solution if the offspring has a better quality and is distinct from any solution in the population. This greedy strategy however may lead to a premature loss of population diversity, given that only the fitness of the offspring is considered regardless of its distance to the individuals in the population. To better manage the population diversity, more elaborated updating strategies exist in the literature. For example, S¨orensen and Sevaux [34] proposed a population management strategy to maintain a healthy diversity of the population, which simultaneously considers offspring’s quality and its distance to the individuals in the population.

F. Population sizing

As its key component, our VPMS approach integrates a strategic population sizing mechanism (see Algorithm 2) to dynamically adjust the population size during the evolutionary search. This mechanism is composed of a population expanding strategy (to add new individuals) and a population rebuilding strategy (to shrink the population to two individuals). In general terms, we expand the population with new elite solutions when a search stagnation is detected. If the population becomes too large but the search still stagnates, we reduce the population to two solutions. A search stagnation occurs when the best recorded solution has not been updated after MaxIdleGens consecutive generations.

1) Population expanding: When the search stagnates, we try to break the stagnation by introducing more diversity into the algorithm. It is a common sense that the greater the population size, the greater the population diversity. Therefore, we increase the diversity by expanding the population upon search stagnation. Specifically, our population expanding strategy adds new high quality solutions into the population, where each new solution is generated according to the population building strategy of Section III-B and added to the population only if the new solution is not the same as any existing solution in the population.

2) Population rebuilding: Since large populations usually consume more computational resources, we rebuild the population when the population size exceeds an allowable threshold value while the search is still stagnating. Unlike the population building strategy of Section III-B, the population rebuilding strategy shrinks the population to a small population of only two solutions. The new population retains always the best recorded solution and includes another elite solution generated in the same way as the population building strategy of Section III-B.

IV. VPMS APPLIED TO THE CRITICAL NODE PROBLEM

This section presents a practical application of the VPMS approach to solve the critical node problem (CNP) and demonstrates its competitiveness compared to the state of the art.

A. Critical node problem

and |E| = m edges, the critical node problem (CNP) involves identifying a subset of nodes ) such that the removal of the vertices in S leads to a residual graph G[V \ V ] with the minimum pairwise connectivity. These removed nodes are usually called as critical nodes. Once the critical nodes have been removed from G, the residual graph G[V \S] can be represented by a set of disjoint connected subgraphs (i.e., components) , where a connected component is a set of nodes such that there exists a path from a node to any other node in this component, and no edge exists between any two connected components.

is a feasible solution for the given graph, the search space is composed of all possible k-node subsets of V , i.e., . Clearly this search space has a size of

connectivity of a graph, where if and only if node i and node j are in the same component, otherwise . Therefore, the objective function can be rewritten as

where S is a set of critical nodes, is the size of the i-th component of residual graph G[V \ S]. It is known that f(S) can be easily computed by fast algorithms like breadth or depth first search algorithms in O(|V |+|E|) time using an adjacency list representation of the graph [11].

Fig. 1. A taxonomy of critical node detection problems.

CNP has several interesting variants, which optimize different objectives, such as minimizing the size of the largest connected component and maximizing the number of connected components. A detailed classification of the main CNP variants is provided in Fig. 1, while more details about these variants can be found in the recent survey [25].

B. Existing studies on CNP

Given its practical and theoretical significance, CNP has been widely studied in the literature. Various solution approaches have been developed, which can be divided into two categories: exact algorithms and heuristic algorithms.

Exact algorithms aim to provide the proven optimal solutions. Since they have exponential complexities, they are particularly useful for handling special graphs. For example, Di Summa et al. [35] proved that CNP is polynomially solvable on trees via dynamic programming. Addis et al. [1] defined another dynamic programming procedure that solves CNP in polynomial time when the graph has bounded treewidth, which generalizes and extends the results presented in [35] for the case of a tree. Di Summa et al. [36] also studied branch and cut algorithms for detecting critical nodes in general graphs, where an integer linear programming model with a non-polynomial number of constraints is proposed. However, the above-mentioned exact algorithms are able to solve CNP on general graphs with no more than 150 nodes. Veremyev et al. [41] developed a more compact linear 0-1 formulations of CNP that requires constraints, which was tested on much larger real-world sparse networks.

Heuristic algorithms aim to find high-quality solutions within reasonable time without guaranteeing the optimality of the solutions found. Heuristic algorithms are particular useful to handle problem instances that cannot be solved by exact algorithms. Heuristic algorithms for CNP can be divided into three categories: constructive approaches, local search approaches and population-based approaches.

• Constructive approaches start from an “empty solution” and repeatedly extend the current solution until a complete solution is obtained. A early constructive heuristic obtains an initial solution by determining a vertex cover,

and then uses a greedy rule to add some nodes back (Add for short) to the original graph until a feasible solution is obtained [6]. Inversely, a greedy heuristic starts from an empty set and then removes nodes (Remove for short) from the original graph using a greedy rule [40]. Addis et al. [2] developed several hybrid constructive approaches by alternating the application of these two basic greedy operations. Moreover, a sophisticated multi-start greedy algorithm (CNA1 for short) was developed in [32].

• Local search approaches start from a complete candidate solution and then try to improve the current solution by performing local moves. For example, Aringhieri et al. [5] presented two local search algorithms based on the iterated local search and variable neighborhood search frameworks, respectively. Recently, Zhou and Hao [46] proposed a fast and effective iterated local search (FastCNP for short), which employs an effective two-phase node exchange strategy to locate high-quality solutions and applies a destructive-constructive perturbation procedure to drive the search to new regions when the search stagnates.

• Population-based hybrid approaches work with multiple solutions that are manipulated by search operators such as recombination and mutation. For example, Ventresca [39] proposed a population-based incremental learning approach for CNP, where a combinatorial unranking-based problem representation is used. Aringhieri et al. [4] introduced an efficient evolutionary framework for solving different variants of CNP, where greedy rules are used to guide the search towards good quality solutions during reproduction and mutation phases. Recently, Zhou et al. [47] developed an effective memetic search approach (MACNP for short) for both CNP and CC-CNP, which achieves the state-of-the-art performance on benchmark instances from two popular synthetic and real-world datasets (which are presented in Section IV-D1). It is worth noting that the state-of-the-art results on CNP benchmark instances were reported by CAN1 [32], FastCNP [46] and MACNP [47]. These algorithms will thus be used as reference algorithms in our comparisons in Section IV-D5.

C. Variable population memetic algorithm for CNP

Our variable population memetic search algorithm for CNP (denoted by VPMS) strictly follows Algorithm 1, while specifying the solution construction component and the local improvement component. Additionally, for its population management, VPMSapplies the rank-based quality-and-distance pool updating strategy presented in [45].

1) Double backbone-based crossover: Concerning the solution construction component, we adopt the double backbone-based crossover (DBC) [47], which performs structured combinations by inheriting common elements from the parent solutions. Specifically, from two parent solutions and randomly taken from the population, DBC generates an offspring solution in three steps: a) create a partial solution by inheriting the common elements shared by the parents (i.e., identified by the set ); b) add the elements from the set into the partial solution in a probabilistic way; c) repair the solution structurally until a feasible solution is achieved by either adding elements from the set or removing elements from the solution. Once a feasible offspring solution is obtained, it is further ameliorated by the diversified late acceptance search procedure below.

2) Diversified late acceptance search: Diversified late acceptance search (DLAS) [28] is an iterative local search algorithm that is inspired by the late acceptance hill climbing (LAHC) algorithm [9]. Both DLAS and LAHC start their search from an initial solution and iteratively accepts or rejects candidate solutions until a given stopping condition is met. The LAHC method uses a fitness array of size HL (i.e., history length) to memorize the cost of the previous encountered solutions. Initially, all elements of this array are filled with the cost of the initial solution S. At each subsequent iteration iters, a candidate solution is generated. Then, an acceptance decision is made according to a comparison between the cost of the candidate solution and the previous solution cost stored at position v (the virtual beginning of the fitness array, iters mod HL). Specifically, the candidate solution is accepted if its cost is not worse than the cost at position v of the fitness array. After the transition from the current solution to the candidate solution (i.e., becomes the new current solution), the value of position v of the fitness array, is updated by . The process repeats until the given stopping condition is met.

DLAS (Algorithm 3) enhances LAHC by increasing the diversity of the accepted solutions and improving the diversity of the values stored in the fitness array. This is achieved by adopting a new acceptance strategy and a new replacement strategy which takes worsening, improving, and sideways movement scenarios into account [28] (lines 14-35). Specifically, the new acceptance strategy compares at each iteration the fitness value of the candidate solution with the maximum fitness value in the fitness array instead of only comparing it with (lines 14-23). For the new replacement strategy, the replacement occurs only in two cases: 1) if , and 2) if and simultaneously hold (line 27). Our experiments showed that the combination of the new acceptance and replacement strategies in DLAS is indeed more effective in increasing the search diversity than just increasing the length of the fitness array, and consequently helps the algorithm to reach high quality solutions in less time.

To generate a candidate solution, DLAS relies on the component-based two-phase node exchange operator (denoted by swap) introduced in [47], which exchanges a node with a node from a large component. Let G[V \S] be the residual graph G[V \ S] induced by the current solution S and be the set of connected components of G[V \ S]. For a swap operation, we consider as candidate nodes a restricted set of nodes such that , where L is a predefined threshold value to qualify large components in the residual graph. Thus, a candidate neighbor solution is obtained by swap(u, v), where and . For a given candidate solution, its quality can be evaluated in O(|V |+|E|) time with a modified depth-first search algorithm [20] according to Eq. (1).

37 end

38 end

39 return the best solution found

D. Computational studies of VPMS for CNP

This section is devoted to an experimental evaluation of the performance of the VPMSalgorithm in comparison with state-of-the-art CNP algorithms.

1) Benchmark instances: Our computational experiments were performed on two widely-used benchmark datasets: synthetic dataset1 and real-world dataset2. The synthetic dataset presented in [39] is composed of 16 graphs with various structures. The real-world dataset introduced in [4] includes 26 instances from different practical applications. More details about these two datasets are provided in Table I.

TABLE I CHARACTERISTICS OF THE SYNTHETIC AND REAL-WORLD DATASETS USED IN THE EXPERIMENTS.

2) Experimental settings: All our algorithms3 were implemented in the C++ programming language, and complied using GNU gcc 4.1.2 with ‘-O3’ option on an Intel E5-2670 with 2.5GHz and 2GB RAM under Linux. With a ‘-O3’ flag, running the DIMACS machine benchmark program dfmax4

on our machine requires 0.19, 1.17 and 4.54 seconds to solve graphs r300.5, r400.5 and r500.5 respectively.

TABLE II PARAMETER SETTINGS OF THE PROPOSED VPMS

In the following experiments, we use the well-known twotailed sign test to check the statistical significance of our comparisons between two algorithms on each comparison indicator. This statistical test is based on the number of instances on which an algorithm is the overall winner, and it is highly recommended in [12]. There are N = 42 benchmark instances in our experiments. At a significant level of 0.05, the critical value is . This means that algorithm A significantly outperforms algorithm B if A wins at least 27 out of 42 instances.

3) Effectiveness of the strategic population sizing mechanism: Compared to the conventional memetic algorithm framework, the proposed VPMSalgorithm integrates a strategic population sizing mechanism to dynamically adjust the population size during the evolutionary search. To verify the effectiveness of our population sizing mechanism, we compare VPMSwith an alternative algorithm named FPMSwhose population size is fixed to the maximal population size of VPMSwhile keeping the other components as the same as VPMS. As such, FPMSis a classical memetic algorithm which is quite similar to the powerful state-of-the-art memetic algorithm MACNP of [47] where a different local improvement procedure is used.

To make a fair comparison between VPMSand FPMS, we ran them on the same computing platform with the setting shown in Table II. We independently solved each instance 30 times with different random seeds, and the time limit of each run was limited to seconds. Detailed comparative results for both synthetic and real-world datasets are summarized in Tables III.

In Table III, columns 1 and 2 present for each instance its name (Instance) and the best-known value () reported in the literature [5], [32], [47]. Columns 3-7 report the results of the FPMSalgorithm, namely the best objective value () found during 30 runs, the average objective value (), the average running time per run to attain a best objective value (), the average number of generations per run required to find the best objective value (#gens), and the number of times to successfully find the best objective value (#succ). Similarly, columns 8-12 give the results of VPMS. The best values of the compared results in terms of and are indicated in bold. For the #succ indicator, we compare them only when the same values are obtained by the two algorithms.

From Table III, we observe that the VPMSalgorithm (with a variable population) achieves better results on 14 instances, equal results on 20 instances and worse results on 8 instances in terms of compared to the fixed population algorithm FPMS. However, there is no significant difference between these two algorithms (i.e., ). For the indicator, VPMSattains better results on 25 instances, equal results on 10 instances and worse results on 7 instances. At a significant level of 0.05, we find that VPMSis significantly better than FPMSon the indicator (i.e., ). Although VPMSand FPMSachieve the same values for 20 out of 42 synthetic instances, VPMSattains these results with a higher success rate on 8 instances, an equal success rate on 10 instances, a lower success rate only on two instance. It is worth noting that VPMSis the first heuristic to steadily (100%) reach the optimal solutions for all 9 instances with known optima (marked by “” in Table III) in only one minute. For the last three large instances, with the help of a variable population, our VPMSalgorithm is able to attain better results. Finally, compared to the values of all 42 benchmark instances, these two algorithms together improve on the best-known results (new upper bounds) on 8 instances (marked by “”) and match the best-known upper bounds on 22 instances. These results disclose thus the first positive indications of our strategic population sizing mechanism.

To further study the behavior of the proposed VPMSalgorithm, we also report comparative results between VPMSand FPMSwith a longer time limit

TABLE III COMPARISON OF VPMSWITH A VARIABLE POPULATION) AGAINST FPMSWITH A FIXED POPULATION) UNDER

∗ Optimal solutions obtained by a branch-and-cut algorithm [36] within 5 days. ⋆ Improved best upper bounds.

7200 seconds. The detailed computational results are summarized in Table IV. Table IV shows that VPMSand FPMSare able to reach better performances. Importantly, the performance difference between VPMSand FPMSis more obvious than the results shown in Table III. Specifically, we find that VPMSsignificantly outperforms FPMSin terms of both (i.e., ) and indicators (i.e., ). We also observe that these algorithms are able to find new upper bounds on 12 instances (marked by “”) and match the best-known upper bounds on 23 instances. These findings indicate that thank to the use of a strategically adjusted population size, the VPMSalgorithm is able to use its given computational budget more efficiently and more effectively to find high-quality solutions. This experiment (with both cutoff time limits) also indicates the that the DLAS procedure is an effective local improvement procedure.

4) Using the strategic population sizing mechanism to enhance a memetic algorithm: MACNP [47] is a recent state-of-the-art memetic search approach for both CNP and CC-

CNP. We verify now whether the strategic population sizing mechanism can enhance the performance of this memetic algorithm. For this purpose, we replace the fixed population of MACNP by the strategic population sizing mechanism and we use MACNPto denote the resulting MACNP variant with a variable population. We experimentally compare the original MACNP algorithm (with fixed population) and MACNP(with a variable population), based on the 26 real-world benchmark instances. We run both algorithm 30 times on each instance under the time limit seconds. The comparative results in terms of the and indicators are shown in Fig. 2. The x-axis indicates the instances (named by integer numbers), and the y-axis presents the gap of or ) values to the best-known values , i.e., . Therefore, a negative gap value indicates an improved best upper bound.

From Fig. 2, we observe that the variable population algorithm MACNPsignificantly outperforms the fixed population algorithm MACNP in terms of both and . Specifically, Fig. 2(a) indicates that MACNPachieves

TABLE IV COMPARISON OF VPMS

Fig. 2. Comparison between MACNP and MACNPunder the time limit Sub-figures (a) and (b) present the same results under different ranges of y-axis. Sub-figures (c) and (d) present the same results under different ranges of y-axis.

better values than MACNP except for the 21-th instance (i.e., facebook). A close look of these results (as shown in 2(b)) shows that MACNPachieves eight new upper bounds. Additionally, MACNPalso achieves better values

than MACNP except for the fourth instance (i.e., USAir) (see Fig. 2(c)). A clearer observation can be obtained from Fig. 2(d). That is, MACNPobtains better values on fifteen instances, worse values only on two instances (i.e., USAir and Ham5000), and equal values on the 9 remaining instances. These observations show that the state-of-the-art MACNP algorithm can also definitively benefit from the strategic population sizing mechanism proposed in this work.

5) Comparisons with state-of-the-art algorithms: We report now a comparative study with respect to three recent state-of-the-art CNP algorithms, including CAN1 [32], FastCNP [46] and MACNP [47]. To the best of our knowledge, the best-known results available in the literature have been achieved by these three algorithms. Detailed comparative results between our algorithms (i.e., VPMSand MACNP) and the reference algorithms are shown in Table V.

Table V shows that both VPMSand MACNPachieve highly competitive performances compared to the reference algorithms. Under the time limit

TABLE V COMPARISONS OF OUR ALGORITHMS WITH STATE-OF-THE-ART ALGORITHMS UNDER

seconds, these algorithms attain 9 new upper bounds and match 22 known best upper bounds. At a significant level of 0.05, VPMSis significantly better than CAN1 (i.e., ) and FastCNP (i.e., ) in terms of . For the indicator, both VPMSand MACNPonce again significantly outperform CAN1 and FastCNP. Compared to MACNP, VPMSperforms better, leading to better values on 11 instances, and equal values on 23 instances, but the performance difference is statistically marginal (i.e., ). For the indicator, MACNPis significantly better than MACNP (i.e., ) and VPMS(). These findings show that memetic algorithms using a variable population compete favorably with the state-of-the-art CNP algorithms.

To further study the behavior of the two memetic algorithms with a variable population (i.e., VPMSand MACNP) under long time limits, we also compared them against the MACNP algorithm, which uses a fixed population, with a relaxed time limit seconds. The comparative results are summarized in Table VI. We observe that both VPMSand MACNPachieve still better results. For the 42 benchmark instances, VPMSand MACNPfind 13 new upper bounds and reach 23 best-known solutions. At a significant level of 0.05, MACNPperforms significantly better than MACNP (i.e., ) in terms of the indicator. For the indicator, MACNPperforms marginally better than MACNP with a better result on 13 instances, an equal result on 22 instances and a worse result on 7 instances (i.e., ). Remarkably, VPMSsignificantly outperforms MACNP both in terms of (i.e., ) and (i.e., ). These observations further demonstrate the relevance of the strategic population sizing strategy for enhancing memetic algorithms.

V. CONCLUSION AND FUTURE WORK

In this work, we presented the variable population memetic search (VPMS) framework where a strategic population sizing mechanism is introduced into memetic algorithms to dy-

TABLE VI COMPARISONS OF THE VARIABLE POPULATION MEMETIC ALGORITHMS (MACNPWITH THE FIXED POPULATION MEMETIC MACNP ALGORITHM UNDER

namically adjust the population size during the evolutionary search. Unlike the conventional memetic search framework, our VPMS approach starts its search from a population of only two solutions, and dynamically increases or decreases the population size under specific rules. By strategically varying the population size, the memetic algorithm is able to adapt the population diversity during the search and thus favors a continuing balancing between exploitation and exploration. To demonstrate the effectiveness of the proposed VPMS approach, we presented a case study by applying VPMS to solve the challenging critical node problem where a diversified late acceptance search procedure for CNP was designed as the local improvement component of the VPMS algorithm.

Extensive computational studies on two sets of 42 (both synthetic and real-world) benchmark instances in the literature showed that our approach with a variable population competes very favorably with the state-of-the-art CNP algorithms, and remarkably discovers new upper bounds for 13 instances. This study also confirmed the benefit of the strategic population sizing mechanism as a general technique to improve the performance of the classical memetic search. For future work, one research perspective is to investigate the application of the VPMS approach to solve other combinatorial problems. Another interesting research is to determine the population size according to more elaborated rules that can rely on refined information acquired from machine learning techniques.

REFERENCES

[1] B. Addis, M. D. Summa, and A. Grosso, “Identifying critical nodes in undirected graphs: Complexity results and polynomial algorithms for the case of bounded treewidth,” Discrete Applied Mathematics, vol. 161, no. 16-17, pp. 2349–2360, 2013.

[2] B. Addis, R. Aringhieri, A. Grosso, and P. Hosteins, “Hybrid constructive heuristics for the critical node problem,” Annals of Operations Research, vol. 238, no. 1, pp. 1–13, 2016.

[3] J. Arabas, Z. Michalewicz, and J. Mulawka, “GAVaPS-a genetic algo- rithm with varying population size,” in Proceedings of the First IEEE Conference on Evolutionary Computation. IEEE World Congress on Computational Intelligence. IEEE, 1994, pp. 73–78.

[4] R. Aringhieri, A. Grosso, P. Hosteins, and R. Scatamacchia, “A general evolutionary framework for different classes of critical node problems,” Engineering Applications of Artificial Intelligence, vol. 55, no. C, pp. 128–145, 2016.

[5] R. Aringhieri, A. Grosso, P. Hosteins, and R. Scatamacchia, “Local search metaheuristics for the critical node problem,” Networks, vol. 67, no. 3, pp. 209–221, 2016.

[6] A. Arulselvan, C. W. Commander, L. Elefteriadou, and P. M. Pardalos, “Detecting critical nodes in sparse graphs,” Computers & Operations Research, vol. 36, no. 7, pp. 2193–2200, 2009.

[7] U. Benlic and J.-K. Hao, “Memetic search for the quadratic assignment problem,” Expert Systems with Applications, vol. 42, no. 1, pp. 584–595, 2015.

[8] J. Brest, A. Zamuda, I. Fister, M. S. Mauˇcec et al., “Self-adaptive differential evolution algorithm with a small and varying population size,” in 2012 IEEE Congress on Evolutionary Computation. IEEE, 2012, pp. 1–8.

[9] E. K. Burke and Y. Bykov, “The late acceptance hill-climbing heuristic,” European Journal of Operational Research, vol. 258, no. 1, pp. 70–78, 2017.

[10] X. Chen, Y.-S. Ong, M.-H. Lim, and K. C. Tan, “A multi-facet survey on memetic computation,” IEEE Transactions on Evolutionary Computation, vol. 15, no. 5, pp. 591–607, 2011.

[11] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 3rd Edition. MIT Press, 2009.

[12] J. Demˇsar, “Statistical comparisons of classifiers over multiple data sets,” Journal of Machine Learning Research, vol. 7, pp. 1–30, 2006.

[13] T. N. Dinh and M. T. Thai, “Precise structural vulnerability assessment via mathematical programming,” in Military Communications Conference, 2011-MILCOM 2011. IEEE, 2011, pp. 1351–1356.

[14] A. E. Eiben, E. Marchiori, and V. Valko, “Evolutionary algorithms with on-the-fly population size adjustment,” in International Conference on Parallel Problem Solving from Nature. Springer, 2004, pp. 41–50.

[15] L. Feng, Y.-S. Ong, M.-H. Lim, and I. W. Tsang, “Memetic search with interdomain learning: A realization between CVRP and CARP,” IEEE Transactions on Evolutionary Computation, vol. 19, no. 5, pp. 644–658, 2014.

[16] F. Fern´andez, M. Tomassini, and L. Vanneschi, “An empirical study of multipopulation genetic programming,” Genetic Programming and Evolvable Machines, vol. 4, no. 1, pp. 21–51, 2003.

[17] Y. Guan, L. Yang, and W. Sheng, “Population control in evolutionary algorithms: Review and Comparison,” Bio-inspired Computing: Theories and Applications, pp. 161–174, 2017.

[18] W. E. Hart, N. Krasnogor, and J. E. Smith, “Recent Advances in Memetic Algorithms,” Studies in Fuzziness and Soft Computing, vol. 166, Springer Science & Business Media, 2004.

[19] H. H. Hoos and T. St¨utzle, Stochastic Local Search: Foundations and Applications. Elsevier, 2004.

[20] J. Hopcroft and R. Tarjan, “Algorithm 447: efficient algorithms for graph manipulation,” Communications of the ACM, vol. 16, no. 6, pp. 372–378, 1973.

[21] Y. Jin, and J-K. Hao, “Solving the latin square completion problem by memetic graph coloring,” IEEE Transactions on Evolutionary Computation, online since February 2019, DOI: 10.1109/TEVC.2019.2899053.

[22] D. Karapetyan and G. Gutin, “A new approach to population sizing for memetic algorithms: a case study for the multidimensional assignment problem,” Evolutionary Computation, vol. 19, no. 3, pp. 345–371, 2011.

[23] V. K. Koumousis and C. P. Katsaras, “A saw-tooth genetic algorithm combining the effects of variable population size and reinitialization to enhance performance,” IEEE Transactions on Evolutionary Computation, vol. 10, no. 1, pp. 19–28, 2006.

[24] N. Krasnogor and J. Smith, “A tutorial for competent memetic al- gorithms: model, taxonomy, and design issues,” IEEE Transactions on Evolutionary Computation, vol. 9, no. 5, pp. 474–488, 2005.

[25] M. Lalou, M. A. Tahraoui, and H. Kheddouci, “The critical node detection problem in networks: A survey,” Computer Science Review, vol. 28, pp. 92–117, 2018.

[26] D. Martins, G. M. Viana, I. Rosseti, S. L. Martins, and A. Plastino, “Making a state-of-the-art heuristic faster with data mining,” Annals of Operations Research, vol. 263, pp. 141-162, 2018.

[27] P. Moscato and C. Cotta, “A gentle introduction to memetic algorithms,” In Handbook of Metaheuristics, Kluwer, Norwell, Massachusetts, USA, pp. 105–144, 2003.

[28] M. Namazi, C. Sanderson, M. A. H. Newton, M. M. A. Polash, and A. Sattar, “Diversified late acceptance search,” in AI 2018: Advances in Artificial Intelligence - 31st Australasian Joint Conference, Wellington, New Zealand, December 11-14, 2018, Proceedings, pp. 299–311, 2018.

[29] F. Neri and C. Cotta, “Memetic algorithms and memetic computing optimization: A literature review,” Swarm and Evolutionary Computation, vol. 2, pp. 1–14, 2012.

[30] G. Pavai and T. V. Geetha, “A survey on crossover operators,” ACM Computing Surveys, vol. 49, no. 4, pp. 72:1–72:43, 2016.

[31] D. C. Porumbel, J. K. Hao, and P. Kuntz, “An evolutionary approach with diversity guarantee and well-informed grouping recombination for graph coloring,” Computers & Operations Research, vol. 37, no. 10, pp. 1822–1832, 2010.

[32] W. Pullan, “Heuristic identification of critical nodes in sparse real-world graphs,” Journal of Heuristics, vol. 21, no. 5, pp. 577–598, 2015.

[33] C. Segura, A. H. Aguirre, F. Luna and E. Alba, “Improving diversity in evolutionary algorithms:New best solutions for frequency assignment,” IEEE Transactions on Evolutionary Computation, vol. 21, no. 4, pp. 539– 553, 2017.

[34] K. S¨orensen and M. Sevaux, “MA | PM: memetic algorithms with population management,” Computers & Operations Research, vol. 33, no. 5, pp. 1214–1225, 2006.

[35] M. D. Summa, A. Grosso, and M. Locatelli, “Complexity of the critical node problem over trees,” Computers & Operations Research, vol. 38, no. 12, pp. 1766–1774, 2011.

[36] M. D. Summa, A. Grosso, and M. Locatelli, “Branch and cut algo- rithms for detecting critical nodes in undirected graphs,” Computational Optimization and Applications, vol. 53, no. 3, pp. 649–680, 2012.

[37] K. Tang, Y. Mei, and X. Yao, “Memetic algorithm with extended neigh- borhood search for capacitated arc routing problems,” IEEE Transactions on Evolutionary Computation, vol. 13, no. 5, pp. 1151-1166, 2009.

[38] V. Tirronen and F. Neri, “Differential evolution with fitness diversity self- adaptation,” in Nature-Inspired Algorithms for Optimisation. Springer, 2009, pp. 199–234.

[39] M. Ventresca, “Global search algorithms using a combinatorial unranking-based problem representation for the critical node detection problem,” Computers & Operations Research, vol. 39, no. 11, pp. 2763– 2775, 2012.

[40] M. Ventresca and D. Aleman, “A fast greedy algorithm for the critical node detection problem,” in International Conference on Combinatorial Optimization and Applications. Springer, 2014, pp. 603–612.

[41] A. Veremyev, V. Boginski, and E. L. Pasiliao, “Exact identification of critical nodes in sparse networks via new compact formulations,” Optimization Letters, vol. 8, no. 4, pp. 1245–1259, 2014.

[42] S. Wang, J. Liu, and Y. Jin, “Finding influential nodes in multiplex networks using a memetic algorithm,” IEEE Transactions on Cybernetics, DOI: 10.1109/TCYB.2019.2917059, 2019.

[43] T. Weise, Y. Wu, R. Chiong, K. Tang, and J. L¨assig, “Global versus local search: the impact of population sizes on evolutionary algorithm performance,” Journal of Global Optimization, vol. 66, no. 3, pp. 511– 534, 2016.

[44] J. Wu, X. Shen, and K. Jiao, “Game-based memetic algorithm to the vertex cover of networks,” IEEE Transactions on Cybernetics, vol. 49, no. 3, pp. 974–988, 2019.

[45] Y. Zhou, J.-K. Hao, and B. Duval, “Opposition-based memetic search for the maximum diversity problem,” IEEE Transactions on Evolutionary Computation, vol. 21, no. 5, pp. 731–745, 2017.

[46] Y. Zhou and J.-K. Hao, “A fast heuristic algorithm for the critical node problem,” in Proceedings of the Genetic and Evolutionary Computation Conference Companion. ACM, 2017, pp. 121–122.

[47] Y. Zhou, J.-K. Hao, and G. Fred, “Memetic search for identifying critical nodes in sparse graphs,” IEEE Transactions on Cybernetics, vol. 49, no. 10, pp. 3699–3712, Oct 2019.

Designed for Accessibility and to further Open Science