EMCSO: An Elitist Multi-Objective Cat Swarm Optimization

Document Type: Original Manuscript

Authors

1 Department of computer engineering, Science and Research branch, Islamic azad university, Tehran, Iran

2 Industrial Control Center of Excellence, Electrical Engineering Department, K. N. Toosi University, Tehran, Iran

10.22094/joie.2017.500.12

Abstract

This paper introduces a novel multi-objective evolutionary algorithm based on cat swarm optimizationalgorithm (EMCSO) and its application to solve a multi-objective knapsack problem. The multi-objective optimizers try to find the closest solutions to true Pareto front (POF) where it will be achieved by finding the less-crowded non-dominated solutions. The proposed method applies cat swarm optimization (CSO), a swarm-based algorithm with ability of exploration and exploitation, to produce offspring solutions and uses thenon-dominated sorting method to findthe solutionsas close as to POFand crowding distance technique toobtain a uniform distribution among thenon-dominated solutions. Also, the algorithm is allowedto keep the elites of population in reproduction processand use an opposition-based learning method for population initialization to enhance the convergence speed.The proposed algorithm is tested on standard test functions (zitzler’ functions: ZDT) and its performance is compared with traditional algorithms and is analyzed based onperformance measures of generational distance (GD), inverted GD, spread,and spacing. The simulation results indicate that the proposed method gets the quite satisfactory results in comparison with other optimization algorithms for functions of ZDT1 and ZDT2. Moreover, the proposed algorithm is applied to solve multi-objective knapsack problem.

Graphical Abstract

EMCSO: An Elitist Multi-Objective Cat Swarm Optimization

Highlights

  • Designing a new multi-objective optimization algorithm based on Cat swarm algorithm (CSO).
  • Solving multi-objective optimization problems: Test functions and multi-objective version of Knapsack problem.
  •  Integrating CSO, non-dominated sorting method, and corwding distance technique.
  • Comparing the obtained results of proposed method with traditional algorithms such as NSGA2, PDEA, MOGSA, and MOBBO/DE.
  • Analyzing the simulation results according to performance measures of GD, Inverted GD, Spread, and Spacing.

Keywords

Main Subjects


Abbasian, M., & Nezamabadipour, H. (2012). Multi-objective gravitational search algorithm using non-dominated fronts. Journal of electrical engineering, Vol 41, No 1 (in Persian).

Abdi, S., Teshnehlab, M., Aliyari, M., & Golahmadi, H. (2012). Designing a multi-objective optimization algorithm with BBO/DE (in persian). Intelligent systems in electrical engineering, No3.

Ali, M., Pant, M., & Abraham, A. (2009). A modified differential evolution algorithm and its application to engineering problems. In: Proceedings of International Conference of Soft Computing and Pattern Recognition (SoCPaR-2009), , (pp. pp.196–201).

Ali, M., Siarry, P., & Pant, M. (2012). An efficient Differential Evolution based algorithm for solving multi-objective optimization problems. European Journal of Operational Research 217, 404–416.

Bagherinejad, J., & Dehghani, M. (2016). A Non-dominated Sorting Ant Colony Optimization Algorithm Approach to the Bi-objective Multi-vehicle Allocation of Customers to Distribution Centers. Journal of Optimization in Industrial Engineering, Volume 9, Issue 19, Page 61-74.

Charnes, A. (1997). Goal programming and multiple objective optimization,. European journal of operational research. 1, , 39–54.

Chu, S., & Roddick, J. (2004). Ant colony system with communication strategies. Information Sciences 167, 63-76.

Chu, S., Tsai, P., & Pan, J. (2006). Cat Swarm Optimization. LNAI 4099, 3 (1), Berlin Heidelberg: Springer-Verlag, (pp. pp. 854–858).

Coello, A. C., Gary, B., & Veldhuisen, A. (2007). Evolutionary Algorithms for Solving Multi-Objective Problems.

Coello, C. (2004). Handling multi objectives with pso, . Evolutionary Computation, IEEE Transactions on (Volume:8 , Issue: 3 ).

Deb, K. (2002). A Fast and Elitist Multiobjective Genetic Algorithm. IEEE Transactions On Evolutionary Computation, Vol. 6, NO. 2.

Deb, K. (2002). MultiObjective optimization using evolutionary algorithms. Wiely.

Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2002). A Fast and Elitist Multiobjective Genetic Algorithm: NSGA–II. IEEE Transactions on Evolutionary Computation, 6(2), 182–197.

Dorigo, M., & Gambardella, L. (1997). Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Trans. On Evolutionary Computation. 26 (1) , 53-66.

Engelbrecht., A. ((2002).). Computational Intelligence. John Wiley & Sons Ltd.

Fleming, C., & Fonseca, P. (1993). Genetic Algorithms for Multiobjective Optimization: Formulation, Discussion and Generalization. Proceedings of the Fifth International Conference on Genetic Algorithms, (pp. 416–42).

Ghosh, A. (2004). Evolutionary Algorithms for Multi-Criterion Optimization: A Survey. International Journal of Computing & Information Sciences, 2 (1), pp. 38-57.

Goldberg, D. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Kluwer Academic Publishers.

Hassanzadeh, H. (2010). A Multi-objective Gravitational Search Algorithm. Computational Intelligence, Communication Systems and Networks (CICSyN), Second International Conference on, (pp. pages 7-12).

Hassanzadeha, R., Mahdavib, I., & Mahdavi-Amiric, N. (2014). Ant Colony Optimization for Multi-objective Digital Convergent. Journal of Optimization in Industrial Engineering, Volume 7, Issue 16, Page 1-19.

Hu, W., & Yen, G. (2013). Adaptive Multiobjective Particle Swarm Optimization Based on Parallel Cell Coordinate System. IEEE Transactions on Evolutionary Comutation.

Kahejvand, V., Hossein, P., & Zandieh, M. (2014). Multi-objective and Scalable Heuristic Algorithm for Workflow Task Scheduling in Utility Grids. Journal of Optimization in Industrial Engineering, Volume 7, Issue 14, Page 27-36.

karaboga, D. (2005). An Idea Based on Honey Bee Swarm for Numerical Optimization, Technical report, . Erciyes University.

Kennedy, J., & Eberhart, R. (1995). Particle Swarm Optimization. Proceedings of IEEE International Conference on Neural Networks.

Knowles, J., & Corne, D. (1999). The Pareto archived evolution strategy: A new baseline algorithm for multiobjective optimization. in Proceedings of the 1999 Congress on Evolutionary Computation. Piscataway, NJ: IEEE Press, (pp. pp. 98–105).

Luila, E. P. (2008). Problema da Mochila Multi-critério, Aspectos Algorítmicos e Implementação Informática. . Tese de Mestrado, Instituto Superior Técnico, Universidade Técnica de Lisboa.

Madavan, N. (2003). Multi-objective optimization using a Pareto differential evolution approach. Proceeding of the Congress on Evolutionary Computation”, Vol.2, (pp. pp.862-869).

Mehdizadeh, E., & Kivi, F. (2014). Three Metaheuristic Algorithms for Solving the Multi-item Capacitated Lot-sizing Problem with Product Returns and Remanufacturing. Journal of optimization in industrial engineering, Volume 7, Issue 16, Page 41-53.

Mirzazadeh, M., Shirdel, G., & Masoumi, B. (2011). A Honey Bee Algorithm To Solve Quadratic Assignment Problem. Journal of optimization in industrial engineering, Volume 4, Issue 9, Page 27-36 .

Naderi, B., & Sadeghi, H. (2012). A Multi-objective simulated annealing algorithm to solving flexible no-wait flowshop scheduling problems with transportation times. Journal of Optimization in Industrial Engineering, Volume 5, Issue 11, Page 33-41.

Orouskhani, M., Mansouri, M., & Teshnehlab, M. (2011). Average- Inertia weighted Cat swarm optimization. LNCS, Berlin Heidelberg: Springer-Verlag, (pp. pp 321– 328).

Orouskhani, M., Mansouri, M., Orouskhani, Y., & Teshnehlab, M. (2013). A hybrid method of modified cat swarm optimizationand gradient descent algorithm for training anfis. International Journal of Computational Intelligence and Applications Volume 12, Issue 02,.

Panda, G., Pradhana, P., & Majhib, B. (2011). IIR system identification using cat swarm optimization. Expert Systems with Applications, Volume 38, Issue 10, Pages 12671–12683.

Pradhan, P., & Panda, G. (2012). Solving multiobjective problems using cat swarm optimization. Expert Systems with Applications, Volume 39, Issue 3, Pages 2956–2964.

Qian, W., & Li, A. (2008). Adaptive differential evolution algorithm for multiobjective optimization problems. Applied Mathematics and Computation 201, 431–440.

Rahmanian, R., Ghaderi, A., & Mehrabad.M. (2012). A Simulated Annealing Algorithm within the Variable Neighbourhood Search Framework to Solve the Capacitated Facility Location-Allocation. Journal of Optimization in Industrial Engineering, Volume 5, Issue 10, Page 45-54.

Robic, T., & Filipi, B. (2005). DEMO: Differential Evolution for Multiobjective Optimization. LNCS 3410, (pp. pp. 520–533).

Santosa, B., & Ningrum, M. (2009). Cat Swarm Optimization for Clustering . International Conference of Soft Computing and Pattern Recognition, (pp. pp 54-59).

Scheffer, M. (1985). Multiple Objective Optimization with Vector Evaluated Genetic Algorithms. Proceedings of the 1st International Conference on Genetic Algorithms.

Schott, J. R. (1995). Fault tolerant design using single and multi-criteria genetic algorithms. Master’s thesis.

Shi, Y., & Eberhart, R. (1998). A modified particle swarm optimizer. Proceedings of IEEE International Conference on Evolutionary Computation, (pp. pp. 69–7).

Storn, R., & Price, K. (1997). Differential evolution - a simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization 11, 341–359.

Tizhoosh, H. (2005). Opposition-Based Learning. Proceedings of the 2005 International Conference on Computational Intelligence for Modelling, Control and Automation.

Tripathi, P., Bandyopadhyay, S., & Pal, S. (2007). Multi-Objective Particle Swarm Optimization with time variant inertia and acceleration coefficients. Information sciences 177, 5033-5049.

Veldhuizen, D. V. (1999). Multiobjective evolutionary algorithms: Classifications, analyses, and new innovations, PhD thesis.

Weise, T. (2009). Global Optimization Algorithms, Theory and applications.

Xue, F., & Sanderson, A. (2003). Pareto-based multi-objective differential evolution. Proceedings of the 2003 Congress on Evolutionary Computation, (pp. pp.420-431).

Yongguo, L., Xindong, W., & Yidong, S. (2012). Cat swarm optimization clustering (KSACSOC): A cat swarm optimization clustering algorithm . Scientific Research and Essays Vol. 7(49), pp. 4176-4185.

Zadeh, L. (1963). Optimality and Non-Scalar-Valued Performance Criteria. IEEE Trans Autom Control 8, 59–60.

Zhang, Q., & Li, H. (2007). MOEA/D: a multiobjective evolutionary algorithm based on decomposition. IEEE Trans. Evol. Comput., Vol. 11, no. 6, pp. 712-731.

Zitzler, E. (1999). Evolutionary algorithms for multiobjective optimization: Methods and applications. Doctoral dissertation ETH 13398, Swiss Federal Institute of Technology (ETH).

Zitzler, E., Laumanns, M., & Thiele, L. (2001). SPEA2: improving the strength pareto evolutionary algorithm. Swiss Federal Institute of Technology (ETH), Zurich, Switzerland, Technical report TIK- report 103.