Rigorous Running Time Analysis of a Simple Immune-Based Multi-Objective Optimizer for Bi-Objective Pseudo-Boolean Functions

doi:10.1007/s12204-018-2004-z

Journal of Shanghai Jiao Tong University (Science) ›› 2018, Vol. 23 ›› Issue (6): 827-833.doi: 10.1007/s12204-018-2004-z

Rigorous Running Time Analysis of a Simple Immune-Based Multi-Objective Optimizer for Bi-Objective Pseudo-Boolean Functions

ZHOU Shiyuan (周诗源), PENG Xue (彭雪), WANG Yinglin (王英林), XIA Xiaoyun (夏小云)

(1. School of Information Management and Engineering, Shanghai University of Finance and Economics, Shanghai 200433, China; 2. School of Mathematics and Systems Science, Guangdong Polytechnic Normal University, Guangzhou 510665, China; 3. Office of Budget and Finance, Jiaxing University, Jiaxing 314001, Zhejiang, China; 4. College of Mathematics, Physics and Information Engineering, Jiaxing University, Jiaxing 314001, Zhejiang, China)

出版日期:2018-12-01 发布日期:2018-12-07
通讯作者: PENG Xue (彭雪) E-mail: pxue2008@163.com

Rigorous Running Time Analysis of a Simple Immune-Based Multi-Objective Optimizer for Bi-Objective Pseudo-Boolean Functions

ZHOU Shiyuan (周诗源), PENG Xue (彭雪), WANG Yinglin (王英林), XIA Xiaoyun (夏小云)

(1. School of Information Management and Engineering, Shanghai University of Finance and Economics, Shanghai 200433, China; 2. School of Mathematics and Systems Science, Guangdong Polytechnic Normal University, Guangzhou 510665, China; 3. Office of Budget and Finance, Jiaxing University, Jiaxing 314001, Zhejiang, China; 4. College of Mathematics, Physics and Information Engineering, Jiaxing University, Jiaxing 314001, Zhejiang, China)

Online:2018-12-01 Published:2018-12-07
Contact: PENG Xue (彭雪) E-mail: pxue2008@163.com

摘要/Abstract

摘要： A simple immune-based multi-objective optimizer (IBMO) is proposed, and a rigorous running time analysis of IBMO on three proposed bi-objective pseudo-Boolean functions (Bi-Trap, Bi-Plateau and Bi-Jump) is presented. The running time of a global simple evolutionary multi-objective optimizer (GSEMO) using standard bit mutation operator with IBMO using somatic contiguous hypermutation (CHM) operator is compared with these three functions. The results show that the immune-based hypermutation can significantly beat standard bit mutation on some well-known multi-objective pseudo-Boolean functions. The proofs allow us to understand the relationship between the characteristics of the problems and the features of the algorithms more deeply. These analysis results also give us a good inspiration to analyze and design a bio-inspired search heuristics.

关键词: evolutionary algorithm , running time analysis , somatic contiguous hypermutation

Abstract: A simple immune-based multi-objective optimizer (IBMO) is proposed, and a rigorous running time analysis of IBMO on three proposed bi-objective pseudo-Boolean functions (Bi-Trap, Bi-Plateau and Bi-Jump) is presented. The running time of a global simple evolutionary multi-objective optimizer (GSEMO) using standard bit mutation operator with IBMO using somatic contiguous hypermutation (CHM) operator is compared with these three functions. The results show that the immune-based hypermutation can significantly beat standard bit mutation on some well-known multi-objective pseudo-Boolean functions. The proofs allow us to understand the relationship between the characteristics of the problems and the features of the algorithms more deeply. These analysis results also give us a good inspiration to analyze and design a bio-inspired search heuristics.

Key words: evolutionary algorithm , running time analysis , somatic contiguous hypermutation

中图分类号:

TP 18

ZHOU Shiyuan (周诗源), PENG Xue (彭雪), WANG Yinglin (王英林), XIA Xiaoyun (夏小云). Rigorous Running Time Analysis of a Simple Immune-Based Multi-Objective Optimizer for Bi-Objective Pseudo-Boolean Functions[J]. Journal of Shanghai Jiao Tong University (Science), 2018, 23(6): 827-833.

参考文献

[1] HANNE T. Global multiobjective optimization withevolutionary algorithms: Selection mechanisms andmutation control [C]//Evolutionary Multi-CriterionOptimization. Ouro Preto, Brazil: EMO, 2001: 197-212. [2] LAUMANNS M, THIELE L, ZITZLER E. Archivingwith guaranteed convergence and diversity in multiobjectiveoptimization [C]//Genetic and EvolutionaryComputation Conference. New York, USA: MorganKaufmann Publishers, 2002: 439-447. [3] LAUMANNS M, THIELE L, ZITZLER E. Runningtime analysis of multiobjective evolutionary algorithmson pseudo-Boolean functions [J]. IEEE Transaction onEvolutionary Computation, 2004, 8(2): 170-182. [4] LAUMANNS M, THIELE L, ZITZLER E. Runningtime analysis of evolutionary algorithms on a simplifiedmultiobjective knapsack problem [J]. Natural Computing,2004, 3(1): 37-51. [5] SCHARNOW J, TINNEFELD K, WEGENER I.Fitness landscapes based on sorting and shortestpaths problems [C]//International Conference on ParallelProblem Solving from Nature. Berlin, Germany:Springer-Verlag, 2002: 54-63. [6] QIAN C, YU Y, ZHOU Z H. An analysis on recombinationin multi-objective evolutionary optimization[J]. Artificial Intelligence, 2013, 204: 99-119. [7] PENG X, XIA X Y, LIAO W Z, et al. Running timeanalysis of the Pareto archived evolution strategy onpseudo-Boolean functions [J]. Multimedia Tools andApplications, 2018, 77(9): 11203-11217. [8] XIA X Y, PENG X, DENG L Y, et al. Performanceanalysis of evolutionary optimization for the bank accountlocation problem [J]. IEEE Access, 2018, 6:17756-17767. [9] KELSEY J, TIMMIS J. Immune inspired somaticcontiguous hypermutations for function optimisation[C]//Genetic and Evolutionary Computation Conference.Chicago, IL, USA: Springer-Verlag, 2003: 207-218. [10] XIA X Y, ZHOU Y R. On the effectiveness of immuneinspired mutation operators in some discrete optimizationproblems [J]. Information Sciences, 2018, 426:87-100. [11] JANSEN T, ZARGES C. Analysis of randomisedsearch heuristics for dynamic optimization [J]. EvolutionaryComputation, 2015, 23(4): 513-541. [12] JANSEN T, ZARGES C. Computing longestcommon subsequences with the B-cell algorithm[C]//International Conference on Artificial ImmuneSystems. Taormina, Italy: Springer-Verlag, 2012:111-124. [13] JANSEN T, ZARGES C. Re-evaluating immuneinspiredhypermutations using the fixed budget perspective[J]. IEEE Transactions on Evolutionary Computation,2014, 18(5): 674-688. [14] XIA X Y, ZHOU Y R. Performance analysis of immuneinspired B-cell algorithm for the SAT problem[J]. Microelectronics and Computer, 2016, 33(7): 5-10(in Chinese). [15] NEUMANN F. Expected runtimes of a simple evolutionaryalgorithm for the multi-objective minimumspanning tree problem [J]. European Journal of OperationalResearch, 2007, 181(3): 1620-1629. [16] NEUMANN F, WEGENER I. Minimum spanningtrees made easier via multi-objective optimization [J].Natural Computing, 2006, 5 (3): 305-319. [17] LAI X S, ZHOU Y R, HE J, et al. Performance analysisof evolutionary algorithms for the minimum labelspanning tree problem [J]. IEEE Transactions on EvolutionaryComputation, 2014, 18(6): 860-872. [18] FRIEDRICH T, HEBBINGHAUS N, NEUMANN F,et al. Approximating covering problems by randomizedsearch heuristics using multi-objective models[C]//Genetic and Evolutionary Computation Conference.London, UK: ACM, 2007: 797-804. [19] JANSEN T, ZARGES, C. Analyzing different variantsof immune inspired somatic contiguous hypermutations[J]. Theoretical Computer Science, 2011, 412(6):517-533. [20] MITZENMACHER M, UPFAL E. Propability andcomputing: Randomized algorithms and probabilisticanalysis [M]. Cambridge, UK: Cambridge UniversityPress, 2005. [21] JANSEN T, WEGENER I. Evolutionary algorithms:How to cope with plateaus of constant fitness and whento reject strings of the same fitness [J]. IEEE Transactionson Evolutionary Computation, 2001, 5(6): 589-599. [22] DROSTE S, JANSEN T, WEGENER I. A rigorouscomplexity analysis of the (1+1) evolutionary algorithmfor separable functions with Boolean inputs [J].Evolutionary Computation, 1998, 6(2): 185-196.

Rigorous Running Time Analysis of a Simple Immune-Based Multi-Objective Optimizer for Bi-Objective Pseudo-Boolean Functions

Rigorous Running Time Analysis of a Simple Immune-Based Multi-Objective Optimizer for Bi-Objective Pseudo-Boolean Functions

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

编辑推荐

Metrics

本文评价

[1]	ZHANG Wen-fen (张雯雰). Simplified Group Search Optimizer Algorithm for Large Scale Global Optimization[J]. 上海交通大学学报（英文版）, 2015, 20(1): 38-43.
[2]	QU Guo-dong* (屈国栋), LOU Zhang-hua (楼章华). Application of Particle Swarm Algorithm in the Optimal Allocation of Regional Water Resources Based on Immune Evolutionary Algorithm[J]. 上海交通大学学报（英文版）, 2013, 18(5): 634-640.