Limitation of Small-world Topology for Application in Non-dominated Sorting Differential Evolution

Headnote

Abstrak

Dalam konteks teori jaringan kompleks, jaringan dunia-kecil adalah terkenal untuk fenomena dunia-kecil, yaitu enam derajat pemisahan. Berbeda dengan aplikasi yang luas dalam jaringan sosial, analisis jaringan fisik dan teknologi, dapat dikombinasikan dengan algoritma optimasi matematika barubaru ini. Pada makalah ini, keterbatasan dari topologi jaringan dunia-kecil untuk aplikasi pada algoritma optimasi multi-obyek adalah diusulkan. Algoritma optimasi ini berdasarkan topologi jaringan dunia-kecil yang paling cocok untuk memecahkan masalah optimasi obyek-tunggal, tetapi memiliki keterbatasan dan efektivitas yang tidak terlalu jelas untuk menangani banyak masalah optimasi multi-obyek. Makalah ini menitikberatkan algoritma evolusi non diferensial penyortiran tak dominan (NSDE) berdasarkan topologi dunia-kecil untuk memecahkan delapan masalah optimasi multi-obyek (MOPS), sebagai contohya. Dibandingkan dengan algoritma NSDE awal, keterbatasan efisiensi topologi dunia-kecil di NSDE divalidasi dengan hasil simulasi Matlab untuk delapan uji fungsi MOEA dari awal tahun 2007. Hasilnya membuktikan bahwa topologi dunia-kecil memiliki keterbatasan dan tidak terlalu jelas untuk meningkatkan efektivitas algoritma optimasi multi-obyek, tidak sebagus untuk meningkatkan algoritma optimasi obyek tunggal.

Kata kunci: jaringan dunia-kecil, jaringan kompleks, MOP, NSDE, teori jaringan

Abstract

In the context of complex network theory, the small-world network is famous for the small-world phenomenon, namely six degrees of separation. Different from its wide application in the social, physical and technological network analysis, it can be combined with the mathematical optimization algorithm recently. In this paper, the limitation of small-world network topology for application in multi-objective optimization algorithm is proposed. The optimization algorithm based on small-world network topology may be suitable for solving a few single-objective optimization problems, but has limitation and unobvious effectiveness to deal with many multi-objective optimization problems. This paper takes non-dominated sorting differential evolution algorithm (NSDE) based on small-world topology to solve eight multi-objective optimization problems (MOPs) for example. Compared with early NSDE algorithm, the limitation of the efficiency of small-world topology in NSDE is validated with the Matlab simulation results of eight MOEA test functions of early 2007. The results prove that small-world topology has limitation and unobvious effectiveness to improve a multi-objective optimization algorithm, not as good as to improve a single-objective optimization algorithm.

Keywords: complex network, MOP, network theory, NSDE, small-world network

(ProQuest: ... denotes formulae omitted.)

1. Introduction

The optimization problem can be classified into two categories: the single-objective optimization problem as in [1-2] and the multi-objective optimization problem [3]. Many realworld problems with several conflicting objectives to be optimized at the same time are called the multi-objective optimization problem (MOP). The multi-objective evolutionary algorithms (MOEAs) have been recognized to be the efficient algorithms to solve the MOP problems. Researchers improve the MOEAs aiming to find the most approximate Pareto-optimal front close to the true Pareto-optimal front. Some previous MOEAs include the vector-evaluated genetic algorithm (VEGA) by Schaffer [4], the multi-objective genetic algorithm (MOGA) by Fonseca and Fleming [5], the non-dominated sorting genetic algorithm (NSGA) by Srinivas and Deb [6], the niched Pareto genetic algorithm (NPGA) by Horn and Nafpliotis [7], the strength Pareto evolutionary algorithm (SPEA) by Zitzler et al. [8] and SPEA2 [9], the Pareto archived evolution strategy (PAES) [10] and PESA [11] by Knowles and Corne, the Pareto envelope based selection algorithm (PESA-II) [12], NSGA-II by Deb et al. [13], non-dominated sorting differential evolution (NSDE) by Iorio and Li [14] and non-dominated neighbor Immune Algorithm (NNIA) by Maoguo Gong [15]. Among them, the last three algorithms attract many researchers' attention.

The idea of NSDE combines the advantages of Differential Evolution (DE) with mechanisms of non-dominated sorting and crowding distance derived from the NSGA-II, enabling NSDE a fast convergence toward the true Pareto front [16]. The state-of-the-art DE techniques are summarized in [16]. These DE techniques can be classified into two categories according to different population topology, namely random topology and small-world topology. Despite the good performance and simple design derived from DE, most of the existing works in the literature implement DE with panmictic population [17]. The population structure has a major influence on the performance of DE algorithms. Small-world topologies were adopted for evolutionary algorithm firstly by Giacobini et al. in 2005 [18] in order to show that spatially structured populations have distinctive advantages over panmictic ones. The classical DE for single-objective optimization with small-world network theory [19] was introduced in [17]. Its effectiveness was tested on the single objective optimization problems [20]-[21] with 30 or 50 decision variables. Even though the performances of all DE algorithms are task-dependent, DE based on the small-world topology seems to be one of the best and fastest algorithms for a large amount of single-objective optimization cases. However, recently, no paper demonstrates whether the small-world topology combined with some MOEAs to solve MOP problem has high efficiency. The multi-objective optimization problem is different from the single-objective optimization problem. The former aims to find the Pareto-optimal front formed by many nondominated solutions, while the latter aims to find only one best solution. If the limitation of a technique is not introduced clearly, misuse of this technique may not get an expected effect. Due to the discussion of combining the complex network theory with previous mathematical optimization algorithm is still seldom seen, this paper takes NSDE based on small-world topology to solve eight MOP problems for example. The limitation of small-world network topology for application in NSDE is proposed. The optimization algorithm based on small-world network topology may be suitable for solving a few single-objective optimization problems, but has limitation and unobvious effectiveness to deal with many multi-objective optimization problems. In this paper, NSDE algorithm with the small-world topology is called NSDE-SW. To test the effectiveness for solving the MOP problems, this paper compares NSDE-SW with classical NSDE on eight known MOEA test functions of early 2007 [22], including three lowdimensional problems, one DTLZ problem and four ZDT problems.

The paper is organized as follows. In section 2, the design of NSDE-SW is described. In section 3, the case studies with the matlab simulation results are taken for example. Section 4 concludes this paper.

2. Research Method

2.1. Theory Background of NSDE-SW

The related background and the model of multi-objective optimization problem can be found in [14], [22]. In the context of network theory, a small-world network is a type of mathematical graph in which most nodes are not neighbors of one another, but most nodes can be reached from each other by a small number of steps. According to two independent structural features, namely the clustering coefficient and average node-to-node distance (or called average shortest path length), the graphs can be classified into three categories, namely regular graph, random graph and small-world graph. In 1998, Watts and Strogatz [19] proposed a small-world Watts-Strogztz (WS) model which interpolates between regular and random graphs. The small-world network can be highly clustered, like regular lattices, yet have small characteristic path lengths, like random graphs [19]. The system with small-world network characteristics also has a greater depth and wider breadth. This feature makes the population individuals from a single-objective optimization algorithm combined with small-world topology fast converge to the objective value. Thus, models of systems with small-world topology show enhanced computational power and fast spread ability. In this paper, NSDE-SW algorithm is based on the small-world WS topology. The regular network with 10 nodes and each node having 4 neighbors, changing into the small-world graph and random graph are shown in Figure 1.

In Figure 1, the small-world network construction has relation with the rewiring probability p. The rewiring probability p of WS model is between regularity (p=0) and random (p =1). When p is changed from zero to one, the graph is changed from a regular graph to a random graph. When 0<p<1, the graph is a small-world graph. We'll explain how the network is related with the population topology in an evolution algorithm as follows.

In a network, each node can be seen as an individual. All nodes form a population. The amount of nodes is the size of the population. This situation is similar to a population for an evolution algorithm. In the initialization step, we need set a population size. In the mutation and crossover process, the population size is kept unchanged. A pair or two pairs of parent individuals are selected to produce one or two pairs of offspring individuals. How to select the parent individuals is a main problem that may influence the performance of an algorithm.

The common way is to randomly select two parents. The parent individuals are represented by the nodes in the network. According to the complex network theory, the random selection of parents is similar to forming a random graph for the population. In the random graph in Figure 1, we can see that node 1 is linked to three nodes, i.e. nodes 2, 5 and 8. If using this random graph in an evolution algorithm, there are three pairs of parents selected to produce the offspring individuals, namely parent 1 and parent 2, parent 1 and parent 5, parent 1 and parent 8. If taking the small-world graph as example, we can see that node 1 is linked to nodes 3, 5 and 10 in Figure 1. If using this small-world graph in an evolution algorithm, there are three pairs of parents, namely parent 1 and parent 3, parent 1 and parent 5, parent 1 and parent 10.

In Figure1, all three graphs have 20 edges, namely 20 different connections. Due to different ways of connection, the graphs having the same amount of nodes and same amount of edges have different network structural features. If used in the mutation and crossover operators instead of randomly selecting parents, the small-world population topology makes the population have two advantages, namely high clustering coefficient and small characteristic path lengths.

2.2. Description of NSDE with Small-world

The description of NSDE can be found in [14]. This approach is a simple modification of the NSGA-II. The only difference between NSDE and NSGA-II is in the method for generating new offspring individuals [23]. In the NSDE, DE operator replaces of a real-coded crossover and mutation operator as in NSGA-II. According to the different DE operators, a survey of the previous DE techniques and their variants which have been extended to multi-objective optimization is presented in [23], including "DE/rand/1/bin", "DE/rand/1/exp", "DE/best/1/bin", "DE/best/1/exp", et al.. These DE operators and the population structure are two different aspects. For example, a basic variant of "DE/rand/m/bin" is given as [23]:

... (1)

Where, x=[x1, x2, ..., xn]T is the vector of decision variables, jr is a random integer number generated using a uniform distribution between [0, n], and n is the number of variables of the problem. Uj(0, 1) is a real number randomly generated using a uniform distribution between [0, 1]. m is the number of pairs of parents used to calculate the differences in the mutation operator. ui,j is the offspring, xr3,j is the donor solution randomly selected, xr1 m and xr2 m are the "mth" pair to calculate the mutation differential. There are two control parameters: the scale factor F and the crossover rate CR.

The elements of vector x are individuals that can be seen as nodes in the network. We aim to find several appropriate connections for xr1 m and xr2 m to form the "mth" pair. Thus, each DE operator combined with random or small-world population structure has no conflict. In this section, we describe the rewiring process of small-world topology combined with NSDE.

For the mating operator in the classical EAs, the population model that all selected parents can interact with one another is known as panmictic. All non-dominated solutions in each generation have a close relationship with neighboring non-dominated solutions after the non-dominated sorting, because the objective values of the neighbors are closer than those of the other solutions. We can deal with this close relationship as neighboring connection in the network. In the crossover and mutation operators, different selections of parent chromosomes to generate the offspring chromosomes have main influence on the effectiveness of algorithms. In order to fast converge to the approximate Pareto front when the population size is large, preserving more parent chromosomes with the best fitness seems to enable the algorithm a better performance than random selection. However, only selecting neighboring parent regularly, similar to a regular network topology, makes the algorithm relatively poor population diversity. The matching of the parent chromosomes based on the small-world topology is between the randomly selection and regular selection. In the WS model, the random rewiring procedure is started from a ring graph with n nodes and k edges. One node of each edge is located unchanged, while the other node is rewired at random with the probability p.

The WS model with a suitable probability p is combined into NSDE algorithm to get fast exploration capability. We give its pseudo-code in Figure 2(a). The pseudo-code is the process of building the WS model. According to [19], there are two steps to build the WS model. Firstly, a regular graph with a ring of n vertices is built. In the graph, every node is connected to its k nearest neighbors with the same number (i.e. k/2) of neighbors on both sides by undirected edges. An n-by-n state matrix A=[A1, A2,...,An]T is constructed to represent the regular graph. Each row or column in A represents a node. The element aij of the row vector Ai= [ai1, ai2,...,ain], i=1,..., n, represents the state of connection. The node i connected with the node j is expressed by aij=1, if not, aij=0. Thus, all the diagonal elements are zero because a node can't be connected to its own. Secondly, as shown in the "randomly rewiring process" in Figure 2(a), we choose a node and reconnect its edge to another node at random around the entire ring with probability p. The duplicate edges are forbidden. Each node and each edge in the original regular graph need to be considered once in the rewiring process according to [19]. A vector B is formed to locate all off-diagonal zero elements in row vector Ai. The flow chart of NSDE-SW is given in Figure 2(b). In Figure 2(b), G is the total evolution generation.

2.3. Performance Evaluation

The criteria to evaluate the performance of a multi-objective optimization algorithm are different from those to evaluate the performance of a single-objective optimization algorithm [14]. Because a multi-objective optimization algorithm provides a set of solutions not only one best solution, the final solutions need to be assessed in terms of uniform coverage of the approximating Pareto-optimal front, convergence to the true front and robustness of the algorithm. We use the convergence metric introduced by Deb et al. in [24] and spacing metric introduced by Schott in [25].

(1) Convergence metric

The convergence metric is used frequently in previous literature and can assess the convergence and robustness of the algorithms. The box plots are adopted to display the convergence metric. The convergence metric value C for a population with the non-dominated set P is calculated as Equation (2). P is the approximating Pareto-optimal front. P* is the true Pareto-optimal front. |P| is the number of the approximating Pareto-optimal solutions. |P*| is the number of the true Pareto-optimal solutions. The true Pareto-optimal fronts of all test functions can be found at (www.cs.cinvestav.mx/~emoobook/).

... (2)

Where, m is the number of objectives, and fk max and fk min are the maximum and the minimum values of the kth objective function in P*, respectively. fk i(x) is the kth objective function value of vector of the ith decision variable. The mathematical explanation for the convergence metric is the average Euclid distance of the every solution in the approximating Pareto-optimal front relative to the closest solution in the true Pareto-optimal front. Generally, the metric C that is less than 0.01 represents good convergence.

(2) Spacing metric

The spacing metric is used for measuring how evenly the solutions in the approximation set are distributed in the objective space. This metric is given by [25]:

... (3)

Where,

... (4)

Where d is the mean of all di, and n is the size of the approximating Pareto-optimal front.

3. Case Studies

3.1. Experiments and Parameter Settings

To compare NSDE-SW with classical NSDE, experiments were conducted on three lowdimensional problems, one DTLZ problem and four ZDT problems [22]. The algorithm program was written using Matlab platform utilizing an Dual Core 2.71GHz PC with 1.75GB memory. The true Pareto-fronts of the eight functions are shown in Figure 3.

The eight MOP numeric unconstrained test functions are given in Tab. 1. Each experiment was run 30 times. The population size is 100 and evolution generation is 500. The crossover probability CR is 0.8. The scale factor F is 0.8. For NSDE-SW, the rewiring probability p of WS model is 0.05. Based on many times of tests on different DE strategies, we adopt the most suitable strategy for all the eight problems, namely "DE/rand/1/bin", in NSDE and NSDESW.

3.2. Results and Analysis

The statistical results about the convergence metric values obtained by NSDE and NSDE-SW in solving eight test problems are shown in Figure 4. The computation time for these test problems is given in Tab. 2. The notched box plot represents the robustness of the uncertainty about the median for box-to-box comparison [15]. Symbol "+" denotes outliers. The upper and lower bound represent 25% quantile and 75% quantile, respectively. The middle of box plot is the median value, namely 50% quantile. The spacing metric SP using NSDE and NSDE-SW are shown in Figure 5.

With a high precision strictly according to the metric values, we can conclude that:

(1) In Figure 4, for the three low-dimensional problems (i.e. DEB, SCH, KUR) and five high-dimensional problems (i.e. ZDT1, ZDT2, ZDT3, ZDT4 and DTLZ4), NSDE-SW is capable of approximating the true Pareto-optimal fronts.

(2) In Figure 4, for DEB, SCH, KUR, ZDT2, ZDT4 and DTLZ4 problems, NSDE-SW does better than NSDE in the aspect of the convergence metric. In the aspect of the mean value of the convergence metric, NSDE does better than NSDE-SW for ZDT1 and ZDT3 problems.

(3) In Figure 5, the spacing metric shows that NSDE-SW can get a little more uniformly distributed solution front for DEB, KUR, ZDT2, ZDT3, ZDT4 and DTLZ4 than NSDE. But, for SCH and ZDT1, NSDE-SW is no better than NSDE.

(4) Considering convergence metric and spacing metric, we can find that for DEB, KUR, ZDT2, ZDT4, and DTLZ4, NSDE-SW is better than NSDE. Other test functions, NSDE-SE is no better than NSDE.

With a low level of precision, for example, assuming that gap of convergence metric less than 0.001 and the gap of spacing metric less than 0.1 is acceptable, we can see that for most following functions, NSDE-SW has similar performance as NSDE, namely small-world topology has an unobvious effect on improving the performance of NSDE.

4. Conclusion

The small-world population topology can improve the performance of the singleobjective optimization algorithm, but, it has limitation to improve that of a multi-objective optimization algorithm. This paper combines the small-world population topology with NSDE to form a hybrid algorithm called NSDE-SW. Eight test multi-objective optimization problems are taken for examples. The values of convergence metric and spacing metric show the following conclusions. (1) If with a high precision, for most cases, small-world population topology can improve NSDE a little in the aspects of the convergence and spacing distribution. (2) If with a low precision, for example, assuming the gap of convergence metric less than 0.001 and the gap of spacing metric less than 0.1 is seen as no difference, small-world topology has an unobvious effect on improving the performance of NSDE. It shows that the small-world population topology designed for single-objective optimization problem has limitation for applied in a multi-objective optimization problem.

Acknowledgements

This paper is supported by the National High Technology Research and Development of China (863 Program) (2011AA05A101).

References

References

[1] . Chanda S, De A. Congestion relief of contingent power network with evolutionary optimization algorithm. TELKOMNIKA. 2012; 10(1): 1-8.

[2] . Tahami F, Nademi H, Rezaei M. Maximum torque per ampere control of PMSM using genetic algorithm. TELKOMNIKA. 2011; 9(2): 237-244.

[3] . Sen S, Roy P, Chakrabarti A, Sengupta S. Generator contribution based congestion management using multiobjective genetic algorithm. TELKOMNIKA. 2011; 9(1): 1-8.

[4] . Schaffer JD. Multiple objective optimization with vector evaluated genetic algorithms. Proceedings of the 1st International Conference on Genetic Algorithms and Their Applications. Pittsburgh. 1985: 93- 100.

[5] . Fonseca CM, Fleming PJ. Genetic algorithm for multiobjective optimization: Formulation, discussion and generalization. Proceedings of the 5th International Conference on Genetic Algorithms. San Mateo. 1993: 416-423.

[6] . Srinivas N, Deb K. Multiobjective optimization using non-dominated sorting in genetic algorithms. Evolutionary Computation. 1994; 2(3): 221-248.

[7] . Horn J, Nafpliotis N, Goldberg DE. A niched Pareto genetic algorithm for multiobjective optimization. Proceedings of the 1st IEEE World Congress on Evolutionary Computation. Piscataway. 1994; 1: 82- 87.

[8] . Zitzler E, Thiele L. Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach. IEEE Trans. on Evolutionary Computation, 1999; 3(4): 257-271.

[9] . Zitzler E, Laumanns M, Thiele L. SPEA2: Improving the strength Pareto evolutionary algorithm for multiobjective optimization. Proceedings of EUROGEN 2001 Evolutionary Methods for Design, Optimization and Control with Applications to Industrial Problems. Athens. 2001: 95-100.

[10] . Knowles JD, Corne DW. Approximating the non-dominated front using the Pareto archived evolution strategy. Evolutionary Computation. 2000; 8(2): 149-172.

[11] . Corne DW, Knowles JD, Oates MJ. The Pareto envelope-based selection algorithm for multiobjective optimization. Parallel Problem Solving from Nature (PPSN) VI Conf. Lecture Notes in Computer Science. 2000; 1917: 839-848.

[12] . Corne DW, Jerram NR, Knowles JD, Oates MJ. PESA-II: Region-based selection in evolutionary multiobjective optimization. Proceedings of the Genetic and Evolutionary Computation Conf. (GECCO). San Francisco. 2001: 283-290.

[13] . Deb K, Pratap A, Agarwal S, Meyarivan T. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. on Evolutionary Computation. 2002; 6(2):182-197.

[14] . A. W. Iorio and X. Li. Solving rotated multiobjective optimization problems using differential evolution. Proceedings of 17th Australian Joint Conference on Artificial Intelligence: Advances in Artificial Intelligence. 2004; 3339: 861-872.

[15] . Gong, M. G., Jiao, L. C., Du, H. F., Bo, L. F. Multi-objective immune algorithm with nondominated neighbor-based selection. Evolutionary Computation. 2008; 16(2): 225-255.

[16] . S. Das, P. N. Suganthan. Differential evolution: A survey of the state-of-the-art. IEEE Transactions on Evolutionary Computation. 2011; 15(1): 4-31.

[17] . Bernabé Dorronsoro, Pascal Bouvry. Improving classical and decentralized differential evolution with new mutation operator and population topologies. IEEE Transactions on Evolutionary Computation. 2011; 15(1): 67-98.

[18] . M. Giacobini, M. Tomassini, A. Tettamanzi. Takeover time curves in random and small-world structured populations. Proceedings of Genetic and Evolutionary Computation Conference (GECCO). Washington DC. 2005: 1333-1340.

[19] . D. J. Watts and S. H. Strogatz. Collective dynamics of 'small-world' networks. Nature. 1998; 393: 440-442.

[20] . S. García, D. Molina, M. Lozano, F. Herrera. A study on the use of non-parametric tests for analyzing the evolutionary algorithms' behavior: A case study on the CEC'05 special session on real parameter optimization. J. Heuristics. 2009, 15(6): 617-644.

[21] . Suganthan, P. N., Hansen, N., Liang, J. J., Deb, K., Chen, Y. P., Auger, A., Tiwari, S. Problem definitions and evaluation criteria for the CEC 2005 Special Session on Real Parameter Optimization. Nanyang Technological University. Report number: 2005005. 2005.

[22] . Coello Coello CA, van Veldhuizen DA, Lamont GB. Evolutionary Algorithms for Solving Multi- Objective Problems (2nd ed.). New York: Springer-Verlag, 2007.

[23] . E. Mezura-Montes, M. Reyes-Sierra, C. A. Coello Coello. Multi-objective optimization using differential evolution: a survey of the state-of-art. Advances in Differential Evolution: Studies in Computational Intelligence. 2008; 143: 173-196.

[24] . Deb K, Jain S. Running performance metrics for evolutionary multi-objective optimization. Indian Institute of Technology Kanpur. Report number: 2002004. 2002.

[25] . Schott, JR. Fault tolerant design using single and multicriteria genetic algorithm optimization. MS. Thesis. Cambridge: Massachusetts Institute of Technology; 1995.