Investigating Performance of Various Natural Computing Algorithms

Investigating Performance of Various Natural Computing Algorithms

Автор: Bharat V. Chawda, Jayeshkumar Madhubhai Patel

Журнал: International Journal of Intelligent Systems and Applications(IJISA) @ijisa

Статья в выпуске: 1 vol.9, 2017 года.

Бесплатный доступ

Nature is there since millenniums. Natural elements have withstood harsh complexities since years and have proved their efficiency in tackling them. This aspect has inspired many researchers to design algorithms based on phenomena in the natural world since the last couple of decades. Such algorithms are known as natural computing algorithms or nature inspired algorithms. These algorithms have established their ability to solve a large number of real-world complex problems by providing optimal solutions within the reasonable time duration. This paper presents an investigation by assessing the performance of some of the well-known natural computing algorithms with their variations. These algorithms include Genetic Algorithms, Ant Colony Optimization, River Formation Dynamics, Firefly Algorithm and Cuckoo Search. The Traveling Salesman Problem is used here as a test bed problem for performance evaluation of these algorithms. It is a kind of combinatorial optimization problem and known as one the most famous NP-Hard problems. It is simple and easy to understand, but at the same time, very difficult to find the optimal solution in a reasonable time – particularly with the increase in a number of cities. The source code for the above natural computing algorithms is developed in MATLAB R2015b and applied on several TSP instances given in TSPLIB library. Results obtained are analyzed based on various criteria such as tour length, required iterations, convergence time and quality of solutions. Conclusions derived from this analysis help to establish the superiority of Firefly Algorithms over the other algorithms in comparative terms.

Еще

Natural Computing Algorithms, Nature Inspired Algorithms, Traveling Salesman Problem, Genetic Algorithm, Ant Colony Optimization, River Formation Dynamics, Firefly Algorithm, Cuckoo Search

Короткий адрес: https://sciup.org/15010892

IDR: 15010892

Список литературы Investigating Performance of Various Natural Computing Algorithms

  • J. Dang, A. Brabazon, D. Edelman, and M. O’Neill, “An Introduction to Natural Computing in Finance,” in Applications of Evolutionary Computing, M. Giacobini, A. Brabazon, S. Cagnoni, G. A. D. Caro, A. Ekárt, A. I. Esparcia-Alcázar, M. Farooq, A. Fink, and P. Machado, Eds. Springer Berlin Heidelberg, 2009, pp. 182–192.
  • X.-S. Yang, Nature-inspired metaheuristic algorithms. Luniver press, 2010.
  • S. Mirjalili, S. M. Mirjalili, and A. Lewis, “Grey wolf optimizer,” Adv. Eng. Softw., vol. 69, pp. 46–61, 2014.
  • D. H. Wolpert and W. G. Macready, “No free lunch theorems for optimization,” Evol. Comput. IEEE Trans. On, vol. 1, no. 1, pp. 67–82, 1997.
  • G. Reinelt, “TSPLIB—A Traveling Salesman Problem Library,” ORSA J. Comput., vol. 3, no. 4, pp. 376–384, Nov. 1991.
  • J. H. Holland, “Genetic algorithms and the optimal allocation of trials,” SIAM J. Comput., vol. 2, no. 2, pp. 88–105, 1973.
  • J. H. Holland, Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. U Michigan Press, 1975.
  • J. H. Holland, Adaptation in Natural and Artificial Systems. Cambridge, MA, USA: MIT Press, 1992.
  • S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by simulated annealing,” SCIENCE, vol. 220, no. 4598, pp. 671–680, 1983.
  • D. Bookstaber, Simulated Annealing for Traveling Salesman Problem. Spring, 1997.
  • P. Moscato, On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts - Towards Memetic Algorithms. 1989.
  • A. Colorni, M. Dorigo, V. Maniezzo, and others, “Distributed optimization by ant colonies,” in Proceedings of the first European conference on artificial life, 1991, vol. 142, pp. 134–142.
  • J. R. Koza, Genetic Programming: On the Programming of Computers by Means of Natural Selection. Cambridge, MA, USA: MIT Press, 1992.
  • J. Kennedy and R. Eberhart, “Particle swarm optimization,” in , IEEE International Conference on Neural Networks, 1995. Proceedings, 1995, vol. 4, pp. 1942–1948 vol.4.
  • R. Storn and K. Price, “Differential evolution–a simple and efficient heuristic for global optimization over continuous spaces,” J. Glob. Optim., vol. 11, no. 4, pp. 341–359, 1997.
  • N. E. Nawa and T. Furuhashi, “Fuzzy system parameters discovery by bacterial evolutionary algorithm,” Fuzzy Syst. IEEE Trans. On, vol. 7, no. 5, pp. 608–616, 1999.
  • D. DasGupta, Artificial immune systems and their applications. Springer Publishing Company, Incorporated, 2014.
  • D. Dasgupta, Z. Ji, F. A. González, and others, “Artificial immune system (AIS) research in the last five years.,” in IEEE Congress on Evolutionary Computation (1), 2003, pp. 123–130.
  • H.-G. Beyer and H.-P. Schwefel, “Evolution strategies–A comprehensive introduction,” Nat. Comput., vol. 1, no. 1, pp. 3–52, 2002.
  • K. M. Passino, “Biomimicry of bacterial foraging for distributed optimization and control,” IEEE Control Syst., vol. 22, no. 3, pp. 52–67, Jun. 2002.
  • X. Li and J. Qian, “Studies on Artificial Fish Swarm Optimization Algorithm based on Decomposition and Coordination Techniques [J],” J. Circuits Syst., vol. 1, pp. 1–6, 2003.
  • M. M. Eusuff and K. E. Lansey, “Optimization of water distribution network design using the shuffled frog leaping algorithm,” J. Water Resour. Plan. Manag., vol. 129, no. 3, pp. 210–225, 2003.
  • M. Eusuff, K. Lansey, and F. Pasha, “Shuffled frog-leaping algorithm: a memetic meta-heuristic for discrete optimization,” Eng. Optim., vol. 38, no. 2, pp. 129–154, 2006.
  • X.-F. Xie and W.-J. Zhang, “Solving engineering design problems by social cognitive optimization,” in Genetic and Evolutionary Computation–GECCO 2004, 2004, pp. 261–262.
  • A. R. Mehrabian and C. Lucas, “A novel numerical optimization algorithm inspired from weed colonization,” Ecol. Inform., vol. 1, no. 4, pp. 355–366, 2006.
  • D. Karaboga, “An idea based on honey bee swarm for numerical optimization,” Technical report-tr06, Erciyes university, engineering faculty, computer engineering department, 2005.
  • D. Karaboga and B. Basturk, “A Powerful and Efficient Algorithm for Numerical Function Optimization: Artificial Bee Colony (ABC) Algorithm,” J Glob. Optim., vol. 39, no. 3, pp. 459–471, Nov. 2007.
  • S. He, Q. H. Wu, and J. R. Saunders, “A novel group search optimizer inspired by animal behavioural ecology,” in Evolutionary Computation, 2006. CEC 2006. IEEE Congress on, 2006, pp. 1272–1278.
  • R. A. Formato, “Central force optimization: a new metaheuristic with applications in applied electromagnetics,” Prog. Electromagn. Res., vol. 77, pp. 425–491, 2007.
  • R. A. Formato, “Central force optimization: a new nature inspired computational framework for multidimensional search and optimization,” in Nature Inspired Cooperative Strategies for Optimization (NICSO 2007), Springer, 2008, pp. 221–238.
  • P. Rabanal, I. Rodríguez, and F. Rubio, “Using river formation dynamics to design heuristic algorithms,” in Unconventional Computation, Springer, 2007, pp. 163–177.
  • P. Rabanal, I. Rodríguez, and F. Rubio, “Applying river formation dynamics to solve NP-complete problems,” in Nature-inspired algorithms for optimisation, Springer, 2009, pp. 333–368.
  • H. Shah-Hosseini, “Problem solving by intelligent water drops,” in IEEE Congress on Evolutionary Computation, 2007. CEC 2007, 2007, pp. 3226–3231.
  • T. C. Havens, C. J. Spain, N. G. Salmon, and J. M. Keller, “Roach infestation optimization,” in Swarm Intelligence Symposium, 2008. SIS 2008. IEEE, 2008, pp. 1–7.
  • R. Zhao and W. Tang, “Monkey algorithm for global numerical optimization,” J. Uncertain Syst., vol. 2, no. 3, pp. 165–176, 2008.
  • D. Simon, “Biogeography-Based Optimization,” IEEE Trans. Evol. Comput., vol. 12, no. 6, pp. 702–713, Dec. 2008.
  • A. H. Kashan, “League championship algorithm: a new algorithm for numerical function optimization,” in 2009 International Conference of Soft Computing and Pattern Recognition, 2009, pp. 43–48.
  • K. N. Krishnanand and D. Ghose, “Glowworm swarm optimization for simultaneous capture of multiple local optima of multimodal functions,” Swarm Intell., vol. 3, no. 2, pp. 87–124, 2009.
  • Y. Marinakis, M. Marinaki, and N. Matsatsinis, “A hybrid bumble bees mating optimization-grasp algorithm for clustering,” in Hybrid Artificial Intelligence Systems, Springer, 2009, pp. 549–556.
  • R. Oftadeh and M. J. Mahjoob, “A new meta-heuristic optimization algorithm: Hunting Search,” in Soft Computing, Computing with Words and Perceptions in System Analysis, Decision and Control, 2009. ICSCCW 2009. Fifth International Conference on, 2009, pp. 1–5.
  • X.-S. Yang, “Firefly algorithms for multimodal optimization,” in Stochastic algorithms: foundations and applications, Springer, 2009, pp. 169–178.
  • X.-S. Yang, “Harmony Search as a Metaheuristic Algorithm,” in Music-Inspired Harmony Search Algorithm, Z. W. Geem, Ed. Springer Berlin Heidelberg, 2009, pp. 1–14.
  • U. Premaratne, J. Samarabandu, and T. Sidhu, “A new biologically inspired optimization algorithm,” in 2009 International Conference on Industrial and Information Systems (ICIIS), 2009, pp. 279–284.
  • E. Rashedi, H. Nezamabadi-Pour, and S. Saryazdi, “GSA: a gravitational search algorithm,” Inf. Sci., vol. 179, no. 13, pp. 2232–2248, 2009.
  • X.-S. Yang and S. Deb, “Cuckoo search via Lévy flights,” in Nature & Biologically Inspired Computing, 2009. NaBIC 2009. World Congress on, 2009, pp. 210–214.
  • X.-S. Yang and S. Deb, “Engineering optimisation by cuckoo search,” Int. J. Math. Model. Numer. Optim., vol. 1, no. 4, pp. 330–343, 2010.
  • X.-S. Yang, “A New Metaheuristic Bat-Inspired Algorithm,” in Nature Inspired Cooperative Strategies for Optimization (NICSO 2010), J. R. González, D. A. Pelta, C. Cruz, G. Terrazas, and N. Krasnogor, Eds. Springer Berlin Heidelberg, 2010, pp. 65–74.
  • Y. Tan and Y. Zhu, “Fireworks Algorithm for Optimization,” in Advances in Swarm Intelligence, Y. Tan, Y. Shi, and K. C. Tan, Eds. Springer Berlin Heidelberg, 2010, pp. 355–364.
  • A. Salhi and E. S. Fraga, “Nature-inspired optimisation approaches and the new plant propagation algorithm,” 2011.
  • E. Cuevas, M. González, D. Zaldivar, M. Pérez-Cisneros, and G. García, “An algorithm for global optimization inspired by collective animal behavior,” Discrete Dyn. Nat. Soc., vol. 2012, 2012.
  • H. Eskandar, A. Sadollah, A. Bahreininejad, and M. Hamdi, “Water cycle algorithm–A novel metaheuristic optimization method for solving constrained engineering optimization problems,” Comput. Struct., vol. 110, pp. 151–166, 2012.
  • A. H. Gandomi and A. H. Alavi, “Krill herd: A new bio-inspired optimization algorithm,” Commun. Nonlinear Sci. Numer. Simul., vol. 17, no. 12, pp. 4831–4845, Dec. 2012.
  • B. Niu and H. Wang, “Bacterial colony optimization,” Discrete Dyn. Nat. Soc., vol. 2012, 2012.
  • B. R. Rajakumar, “The Lion’s Algorithm: A New Nature-Inspired Search Algorithm,” Procedia Technol., vol. 6, pp. 126–135, 2012.
  • M. Taherdangkoo, M. Yazdi, and M. H. Bagheri, “Stem Cells Optimization Algorithm,” in Bio-Inspired Computing and Applications, D.-S. Huang, Y. Gan, P. Premaratne, and K. Han, Eds. Springer Berlin Heidelberg, 2012, pp. 394–403.
  • M. T. M. H. Shirzadi and M. H. Bagheri, “A novel meta-heuristic algorithm for numerical function optimization: blind, naked mole-rats (BNMR) algorithm,” Sci. Res. Essays, vol. 7, no. 41, pp. 3566–3583, 2012.
  • X.-S. Yang, “Flower pollination algorithm for global optimization,” in Unconventional computation and natural computation, Springer, 2012, pp. 240–249.
  • X.-S. Yang, M. Karamanoglu, and X. He, “Flower pollination algorithm: a novel approach for multiobjective optimization,” Eng. Optim., vol. 46, no. 9, pp. 1222–1237, 2014.
  • T. Gerstner, M. Holtz, and R. Korn, “Valuation of performance-dependent options in a Black Scholes framework.”
  • A. S. Eesa, A. M. Abdulazeez, and Z. Orman, “Cuttlefish algorithm–a novel bio-inspired optimization algorithm,” Int. J. Sci. Eng. Res., vol. 4, no. 9, pp. 1978–1986, 2013.
  • A. Sadollah, A. Bahreininejad, H. Eskandar, and M. Hamdi, “Mine blast algorithm: A new population based algorithm for solving constrained engineering optimization problems,” Appl. Soft Comput., vol. 13, no. 5, pp. 2592–2612, May 2013.
  • E. Cuevas, M. Cienfuegos, D. Zaldívar, and M. Pérez-Cisneros, “A swarm optimization algorithm inspired in the behavior of the social-spider,” Expert Syst. Appl., vol. 40, no. 16, pp. 6374–6384, 2013.
  • J. C. Bansal, H. Sharma, S. S. Jadon, and M. Clerc, “Spider monkey optimization algorithm for numerical optimization,” Memetic Comput., vol. 6, no. 1, pp. 31–47, 2014.
  • X. Li, J. Zhang, and M. Yin, “Animal migration optimization: an optimization algorithm inspired by animal migration behavior,” Neural Comput. Appl., vol. 24, no. 7–8, pp. 1867–1877, 2014.
  • A. Askarzadeh, “Bird mating optimizer: An optimization algorithm inspired by bird mating strategies,” Commun. Nonlinear Sci. Numer. Simul., vol. 19, no. 4, pp. 1213–1228, Apr. 2014.
  • M. Ghaemi and M.-R. Feizi-Derakhshi, “Forest optimization algorithm,” Expert Syst. Appl., vol. 41, no. 15, pp. 6676–6687, 2014.
  • B. Doğan and T. Ölmez, “A new metaheuristic for numerical function optimization: Vortex Search algorithm,” Inf. Sci., vol. 293, pp. 125–145, 2015.
  • Y.-J. Zheng, “Water wave optimization: A new nature-inspired metaheuristic,” Comput. Oper. Res., vol. 55, pp. 1–11, Mar. 2015.
  • S. D. Gai-Ge Wang, “Elephant Herding Optimization,” 2015.
  • A. Brabazon, W. Cui, and M. O’Neill, “The raven roosting optimisation algorithm,” Soft Comput., vol. 20, no. 2, pp. 525–545, Jan. 2015.
  • “Optimization problem,” Wikipedia, the free encyclopedia. 16-Apr-2016.
  • “Types of Optimization Problems | NEOS.” [Online]. Available: http://neos-guide.org/optimization-tree. [Accessed: 15-May-2016].
  • M. M. Flood, “The traveling-salesman problem,” Oper. Res., vol. 4, no. 1, pp. 61–75, 1956.
  • G. Gutin and A. P. Punnen, Eds., The Traveling Salesman Problem and Its Variations, vol. 12. Boston, MA: Springer US, 2007.
  • R. Matai, S. Singh, and M. Lal, “Traveling Salesman Problem: an Overview of Applications, Formulations, and Solution Approaches,” in Traveling Salesman Problem, Theory and Applications, D. Davendra, Ed. InTech, 2010.
  • K. Sastry, D. E. Goldberg, and G. Kendall, “Genetic algorithms,” in Search methodologies, Springer, 2014, pp. 93–117.
  • N. Sureja and B. Chawda, “Random Traveling Salesman problem using Genetic Algorithms,” IFRSA’s Int. J. Comput., vol. 2, no. 2, 2012.
  • M. Dorigo and T. Stützle, “Ant colony optimization: overview and recent advances,” Techreport IRIDIA Univ. Libre Brux., 2009.
  • M. Dorigo and L. M. Gambardella, “Ant colonies for the travelling salesman problem,” BioSystems, vol. 43, no. 2, pp. 73–81, 1997.
  • B. V. Chawda and N. M. Sureja, “An ACO Approach to Solve a Variant of TSP,” Int. J. Adv. Res. Comput. Eng. Technol. IJARCET, vol. 1, no. 5, p. pp–222, 2012.
  • P. Rabanal, I. Rodríguez, and F. Rubio, “Solving dynamic TSP by using river formation dynamics,” in Natural Computation, 2008. ICNC’08. Fourth International Conference on, 2008, vol. 1, pp. 246–250.
  • S. S. Shah, P. B. Swadas, and B. V. Chawda, “Travelling Salesman Problem Solutions using Various Heuristic Algorithms,” in International Conference on Information, Knowledge & Research in Engineering, Technology & Sciences - 2012, Rajkot, Gujarat, India, 2012, pp. 1142–1145.
  • X.-S. Yang and X. He, “Firefly algorithm: recent advances and applications,” Int. J. Swarm Intell., vol. 1, no. 1, pp. 36–50, 2013.
  • G. K. Jati and others, Evolutionary discrete firefly algorithm for travelling salesman problem. Springer, 2011.
  • S. N. Kumbharana and G. M. Pandey, “Solving travelling salesman problem using firefly algorithm,” Int. J. Res. Sci. Adv. Technol., vol. 2, no. 2, pp. 53–57, 2013.
  • X. Ouyang, Y. Zhou, Q. Luo, and H. Chen, “A novel discrete cuckoo search algorithm for spherical traveling salesman problem,” Appl. Math. Inf. Sci., vol. 7, no. 2, p. 777, 2013.
  • W. C. E. Lim, G. Kanagaraj, and S. G. Ponnambalam, “Cuckoo search algorithm for optimization of sequence in pcb holes drilling process,” in Emerging trends in science, engineering and technology, Springer, 2012, pp. 207–216.
  • “Index of /software/TSPLIB95/tsp.” [Online]. Available: http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/. [Accessed: 20-May-2016].
Еще
Статья научная
QR-код для установки приложения SciUp Наведите камеру и скачайте бесплатное приложение SciUp