Global optimization by small-world optimization algorithm based on social relationship network

Abstract

A fast global convergence algorithm, small-world optimization (SWO), was designed to solve the global optimization problems, which was inspired from small-world theory and six degrees of separation principle in sociology. Firstly, the solution space was organized into a small-world network model based on social relationship network. Secondly, a simple search strategy was adopted to navigate into this network in order to realize the optimization. In SWO, the two operators for searching the short-range contacts and long-range contacts in small-world network were corresponding to the exploitation and exploration, which have been revealed as the common features in many intelligent algorithms. The proposed algorithm was validated via popular benchmark functions and engineering problems. And also the impacts of parameters were studied. The simulation results indicate that because of the small-world theory, it is suitable for heuristic methods to search targets efficiently in this constructed small-world network model. It is not easy for each test mail to fall into a local trap by shifting into two mapping spaces in order to accelerate the convergence speed. Compared with some classical algorithms, SWO is inherited with optimal features and outstanding in convergence speed. Thus, the algorithm can be considered as a good alternative to solve global optimization problems.

Keywords

global optimization / intelligent algorithm / small-world optimization / decentralized search

References

[1] LinharesA.. preying on optima: A predatory search strategy for combinatorial problems [C]. Proceedings of the Proc IEEE Int Conf Syst, 1998San Diego, CA, USAIEEE2974-2978

[2] SunY., DaanW., TomS., JuergenS.. Efficient natural evolution strategies [C]. Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation (GECCO’ 09), 2009New York, USAACM539-546

[3] HollandJ. H.Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence [M], 1975Ann ArborUniversity of Michigan Press1-211

[4] SuG.-s., ZhangX.-f., ChenG.-q., FuX.-yi.. Identification of structure and parameters of rheological constitutive model for rocks using differential evolution algorithm [J]. Journal of Central South University of Technology, 2008, 15(s1): 25-28

[5] AnagnostopoulosA., MichelL., VanP., VergadosY.. A simulated annealing approach to the traveling tournament problem [J]. Journal of Scheduling, 2006, 9(2): 177-193

[6] GloverF.. Heuristics for integer programming using surrogate constraints [J]. Decision Sciences, 1977, 8: 156-166

[7] MahdiyehE., HussainS., AzahM.. Power system stabilizer design using hybrid multi-objective particle swarm optimization with chaos [J]. Journal of Central South University of Technology, 2011, 18(5): 1579-1588

[8] DorigoM., ManiezzoV., ColorniA.. Ant system: Optimization by a colony of cooperating agents [J]. IEEE Trans Syst Man Cybern B Cybern, 1996, 26(1): 29-41

[9] KarabogaD., BasturkB.. A powerful and efficient algorithm for numerical function optimization: Artificial bee colony (ABC) algorithm [J]. Journal of Global Optimization, 2007, 39(3): 459-471

[10] GuY.-l., XuX., DuJ., QianH.-y.. Optimization algorithm based on artificial life algorithm and particle swarm optimization [C]. Second International Conference on Information and Computing Science, 2009ManchesterIEEE Press173-176

[11] NguyenT. T., YaoX.. An experimental study of hybridizing cultural algorithms and local search [J]. Int J Neural Syst, 2008, 18(1): 1-17

[12] MassimoF., RonaldM.. Navigation in small-world networks: A scale-free continuum model [J]. Journal of Applied Probability, 2006, 43(4): 1173-1180

[13] TraversJ., MilgramS.. An experimental study of the small-world problem [J]. Sociometry, 1969, 32(4): 425-443

[14] WattsD. J., StrogatzS. H.. Collective dynamics of ’small-world’ networks [J]. Nature, 1998, 393(6684): 440-442

[15] StrogatzS. H.. Exploring complex networks [J]. Nature, 2001, 410(6825): 268-276

[16] KleinbergJ. M.The small-world phenomenon: An algorithmic perspective [R]. Cornell Computer Science Technical Report, 1999New YorkACM163-170

[17] WattsD. J., DoddsP. S., NewmanM. E. J.. Identity and search in social networks [J]. Science, 2002, 296(5571): 1302-1305

[18] WalshT.. Search in a small world [C]. Ijcai-99: Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, 1999San FranciscoMorgan Kaufmann1172-1177

[19] ChenJ.-z., LiuW., ZhuJ.-yang.. Two-dimensional small-world networks: Navigation with local information [J]. Phys Rev E, 2006, 73(5): 56111-56117

[20] CuiZ.-h., ChuY.-f., CaiX.-juan.. Nearest Neighbor Interaction PSO Based on Small-World Model [J]. Intelligent Data Engineering and Automated Learning, 2009, 5788: 633-640

[21] DuH.-f., ZhuangJ., ZhangJ.-h., WangS.-an.. Small-world phenomenon for function optimization [J]. Journal of Xi’an Jiaotong University, 2005, 39(9): 1011-1015

[22] LiX.-h., ZhangJ.-h., WangS.-a., LiM.-l., LiK.-peng.. A small world algorithm for high-dimensional function optimization [C]. Proceedings of the 8th IEEE International Conference on Computational Intelligence in Robotics and Automation (CIRA’09), 2009Piscataway, NJ, USAIEEE Press55-59

[23] WANG Shuang-xin, LIU Hai-rui, DONG Yang. Constrained model predictive control based on chaotic small-world optimization algorithm [C]// Proceedings of the 18th IFAC, World Congress, Milano, Italy, 2011: 134–142.

[24] YangX.-y., WangX.-hua.. Decentralized small-world optimization strategy [J]. Journal of Suzhou University: Engineering Science Edition, 2007, 3(11): 41-46

[25] WangX.-f., LiX., ChengG.-rong.Complex network theory and its applications [M], 2006BeijingTsinghua University Press46-52

[26] KleinbergJ. M.. Navigation in a small world-It is easier to find short chains between points in some networks than others [J]. Nature, 2000, 406(6798): 845

[27] SharmaB. D., KhannR. K.. On m-ary Gray codes [J]. Information Sciences, 1978, 15(1): 31-43

[28] ZhaoC.-l., SunX.-b., SunS.-l., JiangTing.. Fault diagnosis of sensor by chaos particle swarm optimization algorithm and support vector machine [J]. Expert Systems with Applications, 2011, 38(8): 9908-9912

[29] PriceK. V.. Differential evolution: A fast and simple numerical optimizer [C]. 1996 Biennial Conference of the North American Fuzzy Information Processing Society, 1996NafipsIEEE Press524-527

[30] EberhartR. C., ShiY.. Comparing inertia weights and constriction factors in particle swarm optimization [C]. Proceedings of the 2000 Congress on Evolutionary Computation, 2000La JollaiIEEE Press84-88

[31] JiaoL.-c., DuH.-f., LiuF., GongM.-guo.Immunological computation for optimization, learning and recognition [M], 2006BeijingScience Press58-118

[32] LeungY.-W., WangY.-ping.. An orthogonal genetic algorithm with quantization for global numerical optimization [J]. IEEE T Evolut Comput, 2001, 5(1): 41-53

[33] MADSEN K. Nonlinear approximation and engineering design [EB/OL]. [2006-12-21]. http://www2immdtudk/~km/GlobOpt/testex/testproblemshtml.Denmark.

[34] DuH.-f., WuX.-d., ZhuangJian.. Small-world optimization algorithm for function optimization [J]. Advances in Natural Computation, 2006, 4222(2006): 264-273

[35] FangW., SunJ., XuW.-bo.. A new mutated quantum-behaved particle swarm optimizer for digital IIR filter design [J]. Eurasip J Adv Sig Pr, 2009, 2009: 367465

[36] LiangJ. J., SuganthanP. N., DebK.. Novel composition test functions for numerical global optimization [C]. 2005 IEEE Swarm Intelligence Symposium, 2005PasadenaIEEE Press68-75

[37] DoddsP. S., MuhamadR., WattsD. J.. An experimental study of search in global social networks [J]. Science, 2003, 301(5634): 827-829

[38] JarbouiB., IbrahimS., SiarryP., RebaiA.. A combinatorial particle swarm optimization for solving permutation flowshop problems [J]. Computers & Industrial Engineering, 2008, 54(3): 526-538

[39] HuangG., TianZ.-p., ShaoX.-y., LiJ.-hang.GRZECHCAW.Small world optimization for multiple objects optimization of mixed-model assembly sequencing problem [M], 2011IntechAssembly Line-Theory and Practice131-148

[40] TaillardE.. Benchmarks for basic scheduling problems [J]. European Journal of Operational Research, 1993, 64(2): 278-285

[41] RuizR., MarotoC., AlcarazJ.. Two new robust genetic algorithms for the flowshop scheduling problem [J]. Omega, 2006, 34(5): 461-476

[42] LianZ.-g., GuX.-s., JiaoBin.. A novel particle swarm optimization algorithm for permutation flow-shop scheduling to minimize makespan [J]. Chaos, Solitons & Fractals, 2008, 35(5): 851-861

[43] ZhangC.-s., NingJ.-x., OuyangD.-tong.. A hybrid alternate two phases particle swarm optimization algorithm for flow shop scheduling problem [J]. Computers & Industrial Engineering, 2010, 58(1): 1-11.