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

Jun-fang Li Jun-fang Li, Bu-han Zhang

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.


Full Text:

PDF

References


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

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

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

. 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.

. 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.

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

. 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.

. 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.

. 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.

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

. 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.

. 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.

. 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.

. 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.

. 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.

. 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.

. 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.

. 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.

. D. J. Watts and S. H. Strogatz. Collective dynamics of ‘small-world’ networks. Nature. 1998; 393: 440-442.

. 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.

. 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.

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

. 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.

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

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




DOI: http://doi.org/10.12928/telkomnika.v10i2.816

Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

TELKOMNIKA Telecommunication, Computing, Electronics and Control
ISSN: 1693-6930, e-ISSN: 2302-9293
Universitas Ahmad Dahlan, 4th Campus
Jl. Ringroad Selatan, Kragilan, Tamanan, Banguntapan, Bantul, Yogyakarta, Indonesia 55191
Phone: +62 (274) 563515, 511830, 379418, 371120
Fax: +62 274 564604

View TELKOMNIKA Stats