Nothing Special   »   [go: up one dir, main page]

skip to main content
research-article

NSABC

Published: 05 December 2016 Publication History

Abstract

This paper presents a non-dominated sorting based multi-objective artificial bee colony algorithm NSABC to solve multi-objective optimization problems. It is an extension of the artificial bee colony algorithm ABC, which is a single objective optimization algorithm, to the multi-objective optimization domain. It uses a novel approach in the employee bee phase to steer the solutions to simultaneously achieve both the orthogonal goals in the multi-objective optimization convergence and diversity. The onlooker bee phase is similar to the ABC except for the fitness computation to exploit the promising solutions whereas there is no change in the scout bee phase, which is used to get rid of bad solutions and add diversity in the swarm by introducing random solutions. Along with a novel way of exploring new solutions, it uses non-dominated sorting and crowding distance, inspired by the NSGA-II, to maintain the best and diverse solutions in the swarm. It is tested on the 10 two-objective and three-objective unconstrained benchmark problems of varying nature and complexities from the CEC09 suite of test problems and is found better than or commensurable to thirteen state-of-the-art significant multi-objective optimization algorithms as well as other multi-objective variants of the ABC. Further, it is tested on the nine real-life data clustering problems considered from the UCI machine learning repository and proved itself better in comparison to the NSGA-II, MOVGA, and a recent multi-objective variant of the ABC named MOABC. Thus, it is observed that the NSABC is comparatively a simple, light, and powerful algorithm to solve multi-objective problems.

References

[1]
M.R. Garey, D.S. Johnson, Computer and Intractability, A Guide to the Theory of NP-Completeness.
[2]
K. Deb, John Wiley & Sons, 2001.
[3]
G.E. Box, Evolutionary operation, Appl. Stat. (1957) 81-101.
[4]
L.J. Fogel, A.J. Owens, M.J. Walsh, Artificial Intelligence Through Simulated Evolution.
[5]
J.D. Schaffer, Multiple objective optimization with vector evaluated genetic algorithms, in: Proceedings of the 1st International Conference on Genetic Algorithms, Pittsburgh, PA, USA, July 1985, pp. 93100.
[6]
J.D. Schaffer, Some experiments in machine learning using vector evaluated genetic algorithms, Tech. rep., Vanderbilt Univ., Nashville, TN (USA) (1985).
[7]
D.E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1989.
[8]
P. Hajela, C.-Y. Lin, Genetic search strategies in multicriterion optimal design, Struct. Optim., 4 (1992) 99-107.
[9]
C.M. Fonseca, P.J. Fleming, Multiobjective genetic algorithms, in: IEE Colloquium on Genetic Algorithms for Control Systems Engineering, IET, 1993, pp. 61.
[10]
J. Horn, N. Nafpliotis, D.E. Goldberg, A niched pareto genetic algorithm for multiobjective optimization, in: Proceedings of the First IEEE Conference on Evolutionary Computation, 1994. IEEE World Congress on Computational Intelligence, IEEE, 1994, pp. 8287.
[11]
N. Srinivas, K. Deb, Muiltiobjective optimization using nondominated sorting in genetic algorithms, Evol. Comput., 2 (1994) 221-248.
[12]
K. Deb, A. Pratap, S. Agarwal, T. Meyarivan, A fast and elitist multiobjective genetic algorithm, IEEE Trans. Evol. Comput., 6 (2002) 182-197.
[13]
E. Zitzler, L. Thiele, Multiobjective evolutionary algorithms, IEEE Trans. Evol. Comput., 3 (1999) 257-271.
[14]
E. Zitzler, M. Laumanns, L. Thiele, E. Zitzler, E. Zitzler, L. Thiele, L. Thiele, Spea2: Improving the Strength Pareto Evolutionary Algorithm, 2001.
[15]
J.D. Knowles, D.W. Corne, Approximating the nondominated front using the pareto archived evolution strategy, Evol. Comput., 8 (2000) 149-172.
[16]
D.W. Corne, J.D. Knowles, M.J. Oates, The pareto envelope-based selection algorithm for multiobjective optimization, in: Parallel Problem Solving from Nature PPSN VI, Springer, 2000, pp. 839848.
[17]
D.W. Corne, N.R. Jerram, J.D. Knowles, M.J. Oates, et al., Pesa-ii: Region-based selection in evolutionary multiobjective optimization, in: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO2001), Citeseer, 2001.
[18]
H.A. Abbass, The self-adaptive pareto differential evolution algorithm, in: Proceedings of the 2002 Congress on Evolutionary Computation, 2002. CEC'02, vol. 1, IEEE, 2002, pp. 831836.
[19]
M. Ali, P. Siarry, M. Pant, An efficient differential evolution based algorithm for solving multi-objective optimization problems, Eur. J. Oper. Res., 217 (2012) 404-416.
[20]
J.K. Chong, K.C. Tan, An opposition-based self-adaptive hybridized differential evolution algorithm for multi-objective optimization (osade), in: Proceedings of the 18th Asia Pacific Symposium on Intelligent and Evolutionary Systems, vol. 1, Springer, 2015, pp. 447461.
[21]
B. Chen, Y. Lin, W. Zeng, D. Zhang, Y.-W. Si, Modified differential evolution algorithm using a new diversity maintenance strategy for multi-objective optimization problems, Appl. Intell. (2015) 1-25.
[22]
H. Zhang, D. Yue, X. Xie, S. Hu, S. Weng, Multi-elite guide hybrid differential evolution with simulated annealing technique for dynamic economic emission dispatch, Appl. Soft Comput.
[23]
M. Kotinis, Improving a multi-objective differential evolution optimizer using fuzzy adaptation and k-medoids clustering, Soft Comput., 18 (2014) 757-771.
[24]
C.A.C. Coello, G.T. Pulido, M.S. Lechuga, Handling multiple objectives with particle swarm optimization, IEEE Trans. Evol. Comput.n, 8 (2004) 256-279.
[25]
V.L. Huang, P.N. Suganthan, J.J. Liang, Comprehensive learning particle swarm optimizer for solving multiobjective optimization problems, Int. J. Intell. Syst., 21 (2006) 209-226.
[26]
G. Xu, Y.-q. Yang, B.-B. Liu, Y.-h. Xu, A.-j. Wu, An efficient hybrid multi-objective particle swarm optimization with a multi-objective dichotomy line search, J. Comput. Appl. Math., 280 (2015) 310-326.
[27]
P.K. Tripathi, S. Bandyopadhyay, S.K. Pal, Multi-objective particle swarm optimization with time variant inertia and acceleration coefficients, Inf. Sci., 177 (2007) 5033-5049.
[28]
Q. Zhang, A. Zhou, S. Zhao, P.N. Suganthan, W. Liu, S. Tiwari, Multiobjective optimization test instances for the cec 2009 special session and competition, University of Essex, Colchester, UK and Nanyang Technological University, Singapore, Special Session on Performance Assessment of Multi-Objective Optimization Algorithms, Technical Report, 2008, pp. 130.
[29]
L.-Y. Tseng, C. Chen, Multiple trajectory search for unconstrained/constrained multi-objective optimization, in: IEEE Congress on Evolutionary Computation, 2009. CEC'09, IEEE, 2009, pp. 19511958.
[30]
Q. Zhang, W. Liu, H. Li, The performance of a new version of moea/d on cec09 unconstrained mop test instances, in: IEEE Congress on Evolutionary Computation, vol. 1, 2009, pp. 203208.
[31]
S. Tiwari, G. Fadel, P. Koch, K. Deb, Performance assessment of the hybrid archive-based micro genetic algorithm (amga) on the cec09 test problems, in: CEC'09. IEEE Congress on Evolutionary Computation, 2009, IEEE, 2009, pp. 19351942.
[32]
C.-M. Chen, Y.-p. Chen, Q. Zhang, Enhancing moea/d with guided mutation and priority update for multi-objective optimization, in: IEEE Congress on Evolutionary Computation, 2009, CEC'09, IEEE, 2009, pp. 209216.
[33]
S. Kukkonen, J. Lampinen, Performance assessment of generalized differential evolution 3 with a given set of constrained multi-objective test problems, in: IEEE Congress on Evolutionary Computation, 2009. CEC'09, IEEE, 2009, pp. 19431950.
[34]
M. Liu, X. Zou, Y. Chen, Z. Wu, Performance assessment of dmoea-dd with cec 2009 moea competition test instances, in: IEEE Congress on Evolutionary Computation, vol. 1, 2009, pp. 29132918.
[35]
V.L. Huang, S.Z. Zhao, R. Mallipeddi, P.N. Suganthan, Multi-objective optimization using self-adaptive differential evolution algorithm, in: IEEE Congress on Evolutionary Computation, 2009, CEC'09, IEEE, 2009, pp. 190194.
[36]
H.-l. Liu, X. Li, The multiobjective evolutionary algorithm based on determined weight and sub-regional search, in: IEEE Congress on Evolutionary Computation, 2009, CEC'09, IEEE, 2009, pp. 19281934.
[37]
Y. Wang, C. Dang, H. Li, L. Han, J. Wei, A clustering multi-objective evolutionary algorithm based on orthogonal and uniform design, in: IEEE Congress on Evolutionary Computation, 2009, CEC'09, IEEE, 2009, pp. 29272933.
[38]
K. Sindhya, A. Sinha, K. Deb, K. Miettinen, Local search based evolutionary multi-objective optimization algorithm for constrained and unconstrained problems, in: CEC'09. IEEE Congress on Evolutionary Computation, 2009, IEEE, 2009, pp. 29192926.
[39]
S. Gao, S. Zeng, B. Xiao, L. Zhang, Y. Shi, X. Tian, Y. Yang, H. Long, X. Yang, D. Yu, et al., An orthogonal multi-objective evolutionary algorithm with lower-dimensional crossover, in: IEEE Congress on Evolutionary Computation, 2009. CEC'09, IEEE, 2009, pp. 19591964.
[40]
B.-Y. Qu, P.N. Suganthan, Multi-objective evolutionary programming without non-domination sorting is up to twenty times faster, in: IEEE Congress on Evolutionary Computation, 2009, CEC'09, IEEE, 2009, pp. 29342939.
[41]
A. Zamuda, J. Brest, B. Boskovic, V. Zumer, Differential evolution with self-adaptation and local search for constrained multiobjective optimization, in: IEEE Congress on Evolutionary Computation, 2009, CEC'09, IEEE, 2009, pp. 195202.
[42]
Q. Zhang, P.N. Suganthan, Final report on cec09 moea competition, in: Congress on Evolutionary Computation (CEC 2009), 2009.
[43]
S. Omkar, J. Senthilnath, R. Khandelwal, G.N. Naik, S. Gopalakrishnan, Artificial bee colony (abc) for multi-objective design optimization of composite structures, Appl. Soft Comput., 11 (2011) 489-499.
[44]
S. Omkar, D. Mudigere, G.N. Naik, S. Gopalakrishnan, Vector evaluated particle swarm optimization (vepso) for multi-objective design optimization of composite structures, Comput. Struct., 86 (2008) 1-14.
[45]
R. Akbari, R. Hedayatzadeh, K. Ziarati, B. Hassanizadeh, A multi-objective artificial bee colony algorithm, Swarm Evol. Comput., 2 (2012) 39-52.
[46]
B. Akay, Synchronous and asynchronous pareto-based multi-objective artificial bee colony algorithms, J. Global Optim., 57 (2013) 415-445.
[47]
Y.-B. Zhong, Y. Xiang, H.-L. Liu, A multi-objective artificial bee colony algorithm based on division of the searching space, Appl. Intell., 41 (2014) 987-1011.
[48]
K. Naidu, H. Mokhlis, A. Bakar, Multiobjective optimization using weighted sum artificial bee colony algorithm for load frequency control, Int. J. Electr. Power Energy Syst., 55 (2014) 657-667.
[49]
J. Zhou, X. Liao, S. Ouyang, R. Zhang, Y. Zhang, Multi-objective artificial bee colony algorithm for short-term scheduling of hydrothermal system, Int. J. Electr. Power Energy Syst., 55 (2014) 542-553.
[50]
A.R. Yildiz, A new hybrid artificial bee colony algorithm for robust optimal design and manufacturing, Appl. Soft Comput., 13 (2013) 2906-2912.
[51]
A.R. Yildiz, Optimization of cutting parameters in multi-pass turning using artificial bee colony-based approach, Inf. Sci., 220 (2013) 399-407.
[52]
R. Deriche, H. Fizazi, The artificial bee colony algorithm for unsupervised classification of meteorological satellite images, Int. J. Comput. Appl. 112 (12).
[53]
K.Z. Gao, P.N. Suganthan, T.J. Chua, C.S. Chong, T.X. Cai, Q.K. Pan, A two-stage artificial bee colony algorithm scheduling flexible job-shop scheduling problem with new job insertion, Expert Syst. Appl., 42 (2015) 7652-7663.
[54]
M. Yazdani, S. Gohari, B. Naderi, Multi-factory parallel machine problems, Comput. Ind. Eng., 81 (2015) 36-45.
[55]
K. Ayan, U. Kl, B. Barakl, Chaotic artificial bee colony algorithm based solution of security and transient stability constrained optimal power flow, Int. J. Electr. Power Energy Syst., 64 (2015) 136-147.
[56]
B. Alatas, Chaotic bee colony algorithms for global numerical optimization, Expert Syst. Appl., 37 (2010) 5682-5687.
[57]
W.-f. Gao, S.-y. Liu, L.-l. Huang, A novel artificial bee colony algorithm based on modified search equation and orthogonal learning, IEEE Trans. Cybern., 43 (2013) 1011-1024.
[58]
W. Gao, F.T. Chan, L. Huang, S. Liu, Bare bones artificial bee colony algorithm with parameter adaptation and fitness-based neighborhood, Inf. Sci., 316 (2015) 180-200.
[59]
M.S. Kran, O. Fndk, A directed artificial bee colony algorithm, Appl. Soft Comput., 26 (2015) 454-462.
[60]
P. Mansouri, B. Asady, N. Gupta, The bisection-artificial bee colony algorithm to solve fixed point problems, Appl. Soft Comput., 26 (2015) 143-148.
[61]
C. Horoba, F. Neumann, Approximating pareto-optimal sets using diversity strategies in evolutionary multi-objective optimization, in: Advances in Multi-Objective Nature Inspired Computing, Springer, 2010, pp. 2344.
[62]
Y. Censor, Pareto optimality in multiobjective problems, Appl. Math. Optim., 4 (1977) 41-59.
[63]
D. Karaboga, B. Basturk, A powerful and efficient algorithm for numerical function optimization, J. Global Optim., 39 (2007) 459-471.
[64]
D. Corne, J. Knowles, Some multiobjective optimizers are better than others, in: The 2003 Congress on Evolutionary Computation, 2003, CEC'03, vol. 4, IEEE, 2003, pp. 25062512.
[65]
X. Zou, M. Liu, L. Kang, J. He, A high performance multi-objective evolutionary algorithm based on the principles of thermodynamics, in: Parallel Problem Solving from Nature-PPSN VIII, Springer, 2004, pp. 922931.
[66]
X. Zou, Y. Chen, M. Liu, L. Kang, A new evolutionary algorithm for solving many-objective optimization problems, IEEE Trans. Syst. Man Cybern.: Part B, 38 (2008) 1402-1412.
[67]
D.A. Van Veldhuizen, Multiobjective Evolutionary Algorithms: Classifications, Analyses, and New Innovations, Technical Report, DTIC Document, 1999.
[68]
Q. Zhang, H. Li, Moea/d, IEEE Trans. Evol. Comput., 11 (2007) 712-731.
[69]
S. Tiwari, P. Koch, G. Fadel, K. Deb, Amga: an archive-based micro genetic algorithm for multi-objective optimization, in: Proceedings of Genetic and Evolutionary Computation conference (GECCO-2008), Atlanta, USA, 2008, pp. 729736.
[70]
D. Karaboga, An Idea Based on Honey Bee Swarm for Numerical Optimization, Technical Report, Technical Report-tr06, Erciyes University, Engineering Faculty, Computer Engineering Department, 2005.
[71]
H. Sato, H.E. Aguirre, K. Tanaka, Controlling dominance area of solutions and its impact on the performance of moeas, in: Evolutionary Multi-criterion Optimization, Springer, 2007, pp. 520.
[72]
S. Garca, A. Fernndez, J. Luengo, F. Herrera, Advanced nonparametric tests for multiple comparisons in the design of experiments in computational intelligence and data mining, Inf. Sci., 180 (2010) 2044-2064.
[73]
A.K. Jain, M.N. Murty, P.J. Flynn, Data clustering, ACM Comput. Surv., 31 (1999) 264-323.
[74]
J. Bozdek, Pattern Recognition with Fuzzy Objective Function, 1981.
[75]
W. Kwedlo, A clustering method combining differential evolution with the k-means algorithm, Pattern Recogn. Lett., 32 (2011) 1613-1621.
[76]
J. Prakash, P. Singh, An effective multiobjective approach for hard partitional clustering, Memetic Comput. (2015) 1-12.
[77]
J. Handl, J. Knowles, An evolutionary approach to multiobjective clustering, IEEE Trans. Evol. Comput., 11 (2007) 56-76.
[78]
S. Saha, S. Bandyopadhyay, A generalized automatic clustering algorithm in a multiobjective framework, Appl. Soft Comput., 13 (2013) 89-108.
[79]
W.-Y. Chen, Y. Song, H. Bai, C.-J. Lin, E.Y. Chang, Parallel spectral clustering in distributed systems, IEEE Trans. Pattern Anal. Mach. Intell., 33 (2011) 568-586.
[80]
E. Amig, J. Gonzalo, J. Artiles, F. Verdejo, A comparison of extrinsic clustering evaluation metrics based on formal constraints, Inf. Retr., 12 (2009) 461-486.
[81]
A. Strehl, J. Ghosh, Cluster ensembles-a knowledge reuse framework for combining partitionings, in: AAAI/IAAI, 2002, pp. 9399.
[82]
C.A.C. Coello, D.A. Van Veldhuizen, G.B. Lamont, Springer, 2002.
[83]
K. Deb, S. Jain, Running performance metrics for evolutionary multi-objective optimizations, in: Proceedings of the Fourth Asia-Pacific Conference on Simulated Evolution and Learning (SEAL'02), Singapore, 2002, pp. 1320.
[84]
T. Okabe, Y. Jin, B. Sendhoff, A critical survey of performance indices for multi-objective optimisation, in: The 2003 Congress on Evolutionary Computation, 2003, CEC'03, vol. 2, IEEE, 2003, pp. 878885.

Cited By

View all
  • (2023)A modified artificial bee colony algorithm based on a non-dominated sorting genetic approach for combined economic-emission load dispatch problem▪Applied Soft Computing10.1016/j.asoc.2023.110433144:COnline publication date: 1-Sep-2023
  • (2023)Energy-aware workflow scheduling in fog computing using a hybrid chaotic algorithmThe Journal of Supercomputing10.1007/s11227-023-05330-z79:16(18569-18604)Online publication date: 16-May-2023
  • (2022)Enhanced Connectivity Validity Measure Based on Outlier Detection for Multi-Objective Metaheuristic Data Clustering AlgorithmsApplied Computational Intelligence and Soft Computing10.1155/2022/10362932022Online publication date: 1-Jan-2022
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Neurocomputing
Neurocomputing  Volume 216, Issue C
December 2016
645 pages

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 05 December 2016

Author Tags

  1. Artificial bee colony algorithm
  2. Augmented population
  3. Crowding distance
  4. Multi-objective optimization
  5. Non-dominated sorting

Qualifiers

  • Research-article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 14 Nov 2024

Other Metrics

Citations

Cited By

View all
  • (2023)A modified artificial bee colony algorithm based on a non-dominated sorting genetic approach for combined economic-emission load dispatch problem▪Applied Soft Computing10.1016/j.asoc.2023.110433144:COnline publication date: 1-Sep-2023
  • (2023)Energy-aware workflow scheduling in fog computing using a hybrid chaotic algorithmThe Journal of Supercomputing10.1007/s11227-023-05330-z79:16(18569-18604)Online publication date: 16-May-2023
  • (2022)Enhanced Connectivity Validity Measure Based on Outlier Detection for Multi-Objective Metaheuristic Data Clustering AlgorithmsApplied Computational Intelligence and Soft Computing10.1155/2022/10362932022Online publication date: 1-Jan-2022
  • (2022)Multiple objective metaheuristics for feature selection based on stakeholder requirements in credit scoringDecision Support Systems10.1016/j.dss.2021.113714155:COnline publication date: 1-Apr-2022
  • (2022)Multi-objective memetic differential evolution optimization algorithm for text clustering problemsNeural Computing and Applications10.1007/s00521-022-07888-w35:2(1711-1731)Online publication date: 3-Oct-2022
  • (2021)Multi-Objective Artificial Bee Colony Algorithm for Parameter-Free Neighborhood-Based ClusteringInternational Journal of Swarm Intelligence Research10.4018/IJSIR.202110011012:4(186-204)Online publication date: 1-Oct-2021
  • (2021)MODE-CNNApplied Soft Computing10.1016/j.asoc.2021.107582109:COnline publication date: 1-Sep-2021
  • (2021)A high speed roller dung beetles clustering algorithm and its architecture for real-time image segmentationApplied Intelligence10.1007/s10489-020-02067-751:7(4682-4713)Online publication date: 1-Jul-2021
  • (2020)A multiple search strategies based grey wolf optimizer for solving multi-objective optimization problemsExpert Systems with Applications: An International Journal10.1016/j.eswa.2019.113134145:COnline publication date: 1-May-2020
  • (2020)Multi-objective item evaluation for diverse as well as novel item recommendationsExpert Systems with Applications: An International Journal10.1016/j.eswa.2019.112857139:COnline publication date: 1-Jan-2020
  • Show More Cited By

View Options

View options

Get Access

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media