Wisdom of Artificial Crowds—A Metaheuristic Algorithm for Optimization

Roman V. Yampolskiy, Leif Ashby, Lucas Hassan

Computer Engineering and Computer Science, University of Louisville, Louisville, USA..

DOI: 10.4236/jilsa.2012.42009                

Abstract

Finding optimal solutions to NP-Hard problems requires exponential time with respect to the size of the problem. Consequently, heuristic methods are usually utilized to obtain approximate solutions to problems of such difficulty. In this paper, a novel swarm-based nature-inspired metaheuristic algorithm for optimization is proposed. Inspired by human collective intelligence, Wisdom of Artificial Crowds (WoAC) algorithm relies on a group of simulated intelligent agents to arrive at independent solutions aggregated to produce a solution which in many cases is superior to individual solutions of all participating agents. We illustrate superior performance of WoAC by comparing it against another bio-inspired approach, the Genetic Algorithm, on one of the classical NP-Hard problems, the Travelling Salesperson Problem. On average a 3% - 10% improvement in quality of solutions is observed with little computational overhead.

Keywords

NP-Complete; Optimization; TSP; Bio-Inspired

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	R. M. Karp, “Reducibility among Combinatorial Problems,” In: R. E. Miller and J. W. Thatcher, Eds., Complexity of Computer Computations, Plenum, New York, 1972, pp. 85-103.
[2]	P. Rabanal, I. Rodriguez and F. Rubio, “Using River Formation Dynamics to Design Heuristic Algorithms,” Lecture Notes in Computer Science, Vol. 4618, 2007, pp. 163-177. doi:10.1007/978-3-540-73554-0_16
[3]	R. V. Yampolskiy and A. EL-Barkouky, “Wisdom of Artificial Crowds Algorithm for Solving NP-Hard Problems,” International Journal of Bio-Inspired Computation, Vol. 3, No. 6, 2011, pp. 358-369. doi:10.1504/IJBIC.2011.043624
[4]	L. H. Ashby and R. V. Yampolskiy, “Genetic Algorithm and Wisdom of Artificial Crowds Algorithm Applied to Light Up,” The 16th International Conference on Computer Games, Louisville, 27-30 July 27, 2011, pp. 27-32.
[5]	A. B. Khalifa and R. V. Yampolskiy, “GA with Wisdom of Artificial Crowds for Solving Mastermind Satisfiability Problem,” International Journal of Intelligent Games & Simulation, Vol. 6, No. 2, 2011, pp. 12-17.
[6]	D. E. Goldberg, “Genetic Algorithms in Search, Optimization and Machine Learning,” Addison Wesley Publishing Company, Boston, 1989.
[7]	J. R. Koza, “Genetic Programming: A Paradigm for Genetically Breeding Populations of Computer Programs to Solve Problems,” Technical Report, Stanford University. Stanford, 1990.
[8]	S. Wolfram, “A New Kind of Science,” Wolfram Media Inc., Champaign, 2002.
[9]	J. D. Farmer, N. Packard and A. Perelson, “The Immune System, Adaptation and Machine Learning,” Physica D, Vol. 2, No. 1-3, 1986, pp. 187-204. doi:10.1016/0167-2789(86)90240-X
[10]	H. Shah-Hosseini, “The Intelligent Water Drops Algorithm: A Nature-Inspired Swarm-Based Optimization Algorithm,” International Journal of Bio-Inspired Computation, Vol. 1, No. 1-2, 2009, pp. 71-79. doi:10.1504/IJBIC.2009.022775
[11]	E. Rashedi, H. Nezamabadi-Pour and S. Saryazdi, “GSA: A Gravitational Search Algorithm,” Information Sciences, Vol. 179, No. 13, 2009, pp. 2232-2248. doi:10.1016/j.ins.2009.03.004
[12]	J. M. Bishop, “Stochastic Searching Networks,” 1st IEE International Conference on Artificial Neural Networks, London, 16-18 October 1989, pp. 329-331.
[13]	X.-J. Wang, L. Gao and C.-Y. Zhang, “Electromagnetism-Like Mechanism Based Algorithm for Neural Network Training,” Lecture Notes in Computer Science, Vol. 5227, 2008, pp. 40-45. doi:10.1007/978-3-540-85984-0_5
[14]	J. Kennedy and R. Eberhart, “Particle Swarm Optimization,” IEEE International Conference on Neural Networks, Perth, 27 November-1 December 1995, pp. 19421948.
[15]	A. Kaveh and S. Talatahari, “A Novel Heuristic Optimization Method: Charged System Search,” Acta Mechanica, Vol. 213, No. 3-4, 2010, pp. 267-289. doi:10.1007/s00707-009-0270-4
[16]	O. K. Erol and I. Eksim, “A New Optimization Method: Big Bang-Big Crunch,” Advances in Engineering Software, Vol. 37, No. 2, 2006, pp. 106-111. doi:10.1016/j.advengsoft.2005.04.005
[17]	M. Dorigo, M. Birattari and T. Stutzle, “Ant Colony Optimization: Artificial Ants as a Computational Intelligence Technique,” IEEE Computational Intelligence Magazine, Vol. 1, No. 4, 2006, pp. 28-39. doi:10.1109/MCI.2006.329691
[18]	D. T. Pham, A. Ghanbarzadeh, E. Koc, S. Otri, S. Rahim and M. Zaidi, “The Bees Algorithm—A Novel Tool for Complex Optimisation Problems,” Virtual International Conference on Intelligent Production Machines and Systems, Cardiff, 13-14 July 2006, pp. 454-459.
[19]	K. M. Passino, “Biomimicry of Bacterial Foraging for Distributed Optimization and Control,” Control Systems Magazine, Vol. 22, No. 3, 2002, pp. 52-67. doi:10.1109/MCS.2002.1004010
[20]	K. N. Krishnanand and D. Ghose, “Detection of Multiple Source Locations Using a Glowworm Metaphor With Applications to Collective Robotics,” IEEE Swarm Intelligence Symposium, Pasadena, 8-10 June 2005, pp. 84-91.
[21]	X. S. Yang, “Firefly Algorithms for Multimodal Optimization,” Lecture Notes in Computer Sciences, Vol. 5792, 2009, pp. 169-178. doi:10.1007/978-3-642-04944-6
[22]	X.-S. Yang and S. Deb, “Cuckoo Search via Levy Flights,” World Congress on Nature & Biologically Inspired Computing, Coimbatore, 9-11 December 2009, pp. 210-214.
[23]	C. W. Reynolds, “Flocks, Herds, and Schools: A Distributed Behavioral Model,” 14th Annual Conference on Computer Graphics and Interactive Techniques, Anaheim, 27-31 July 1987, pp. 25-34.
[24]	Z. W. Geem, J. H. Kim and G. V. Loganathan, “A New Heuristic Optimization Algorithm: Harmony Search,” Simulation, Vol. 76, No. 2, 2001, pp. 60-68. doi:10.1177/003754970107600201
[25]	A. Mucherino and O. Seref, “Monkey Search: A Novel Metaheuristic Search for Global Optimization,” AIP Conference on Data Mining, Systems Analysis and Optimization in Biomedicine, Gainesville, 28-30 March 2007, pp. 162-173.
[26]	A. R. Mehrabian and C. Lucas, “A Novel Numerical Optimization Algorithm Inspired from Weed Colonization,” Ecological Informatics, Vol. 1, No. 4, 2006, pp. 355-366. doi:10.1016/j.ecoinf.2006.07.003
[27]	J. Surowiecki, “The Wisdom of Crowds: Why the Many Are Smarter than the Few and How Collective Wisdom Shapes Business, Economies, Societies and Nations,” Doubleday, New York, 2004.
[28]	F. Galton, “Vox Populi,” Nature, Vol. 75, No. 1949, 1907, pp. 450-451.
[29]	S. K. M. Yi, M. Steyvers, M. D. Lee and M. Dry, “Wisdom of Crowds in Minimum Spanning Tree Problems,” Proceedings of the 32nd Annual Conference of the Cognitive Science Society, Austin, 2010, pp. 1840-1845.
[30]	S. K. M. Yi, M. Steyvers, M. D. Lee and M. Dry, “Wisdom of the Crowds in Traveling Salesman Problems,” 2011. socsci.uci.edu/~mdlee/YiEtAl2010.pdf
[31]	C. Wagner, C. Schneider, S. Zhao and H. Chen, “The Wisdom of Reluctant Crowds,” 43rd Hawaii International Conference on System Sciences, Honolulu, 5-8 January 2010, pp. 1-10.
[32]	M. C. Mozer, H. Pashler and H. Homaei, “Optimal Predictions in Everyday Cognition: The Wisdom of Individuals or Crowds?” Cognitive Science, Vol. 32, No. 7, 2008, pp. 1133-1147. doi:10.1080/03640210802353
[33]	F. Bai and B. Krishnamachari, “Exploiting the Wisdom of the Crowd: Localized, Distributed Information-Centric VANETs,” Communications Magazine, Vol. 48, No. 5, 2010, pp. 1-8.
[34]	T. Moore and R. Clayton, “Evaluating the Wisdom of Crowds in Assessing Phishing Websites,” Lecture Notes in Computer Science, Vol. 5143, 2008, pp. 16-30. doi:10.1007/978-3-540-85230-8_2
[35]	K. Shiratsuchi, S. Yoshii and M. Furukawa, “Finding Unknown Interests Utilizing the Wisdom of Crowds in a Social Bookmark Service,” IEEE/WIC/ACM International Conference on Intelligence and Intelligent Agent Technology, Hong Kong, 18-22 December 2006, pp. 421-424.
[36]	F. C. C. Osorio and J. Whitney, “Trust, the Wisdom of Crowds, and Societal Norms,” 1st International Conference on Security and Privacy for Emerging Areas in Communication Networks, Athens, 5-9 September 2005, pp. 199208.
[37]	D. Opitz and R. Maclin, “Popular Ensemble Methods: An Empirical Study,” Journal of Artificial Intelligence Research, Vol. 11, 1999, pp. 169-198.
[38]	P. Melville and R. J. Mooney, “Diverse Ensembles for Active Learning,” 21st International Conference on Machine Learning, Banff, 4-8 July 2004, pp. 584-591.
[39]	P. Melville and R. J. Mooney, “Constructing Diverse Classifier Ensembles Using Artificial Training Examples,” 18th International Joint Conference on Artificial Intelligence, Acapulco, 9-15 August 2003, pp. 505-510.
[40]	R. J. Mooney, “Machine Learning: Ensembles,” 2011. cs.utexas.edu/~mooney/cs391L/slides/ensembles.ppt
[41]	M. Bellmore and G. L. Nemhauser, “The Traveling Salesman Problem: A Survey,” Operations Research, Vol. 16, No. 3, 1968, pp. 538-558. doi:10.1287/opre.16
[42]	M. Dorigo and L. M. Gambardella, “Ant Colonies for the Traveling Salesman Problem,” Biosystems, Vol. 43, No. 2, 1997, pp. 73-81. doi:10.1016/S0303-2647(97)01708-5
[43]	R. E. Burkard, V. G. Deineko, R. V. Dal, J. A. A. V. D. Veen and G. J. Woeginger, “Well-Solvable Special Cases of the Traveling Salesman Problem: A Survey,” SIAM Review, Vol. 40, No. 3, 1998, pp. 496-546.
[44]	W. Cook, “Concorde TSP Solver,” 2010. tsp.gatech.edu/concorde/index.html
[45]	R. V. Yampolskiy, “Application of Bio-Inspired Algorithm to the Problem of Integer Factorisation,” International Journal of Bio-Inspired Computation, Vol. 2, No. 2, 2010, pp. 115-123. doi:10.1504/IJBIC.2010.032127
[46]	R. Yampolskiy, et al., “Printer Model Integrating Genetic Algorithm for Improvement of Halftone Patterns,” Western New York Image Processing Workshop, Rochester, 2004.
[47]	J. McCaffrey, “Using Permutations in NET for Improved Systems Security,” 2003. msdn.microsoft.com/en-us/library/Aa302371
[48]	C. K. Tan, “C# BigInteger Class-CodeProject,” 2002. http://www.codeproject.com/KB/cs/biginteger.aspx