CFP last date
20 December 2024
Call for Paper
January Edition
IJCA solicits high quality original research papers for the upcoming January edition of the journal. The last date of research paper submission is 20 December 2024

Submit your paper
Know more
The week's pick
Responsive image
Improved Shuffled Frog Leaping Algorithm with Self-Adaptive Shuffling for Fuzzy Logic PD+G Controller Optimization in Robotic Manipulators

Duc Hoang Nguyen
Random Articles
Reseach Article

Survey in Novelty Search

by Mahmoud Mohamed Nabil, Magdy Zakaria
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 183 - Number 46
Year of Publication: 2022
Authors: Mahmoud Mohamed Nabil, Magdy Zakaria
10.5120/ijca2022921862

Mahmoud Mohamed Nabil, Magdy Zakaria . Survey in Novelty Search. International Journal of Computer Applications. 183, 46 ( Jan 2022), 18-22. DOI=10.5120/ijca2022921862

@article{ 10.5120/ijca2022921862,
author = { Mahmoud Mohamed Nabil, Magdy Zakaria },
title = { Survey in Novelty Search },
journal = { International Journal of Computer Applications },
issue_date = { Jan 2022 },
volume = { 183 },
number = { 46 },
month = { Jan },
year = { 2022 },
issn = { 0975-8887 },
pages = { 18-22 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume183/number46/32238-2022921862/ },
doi = { 10.5120/ijca2022921862 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-07T01:20:07.257614+05:30
%A Mahmoud Mohamed Nabil
%A Magdy Zakaria
%T Survey in Novelty Search
%J International Journal of Computer Applications
%@ 0975-8887
%V 183
%N 46
%P 18-22
%D 2022
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Novelty Search is an algorithm for discovering new things that is motivated by a behavior's novelty. Different generations from the same individual have varying levels of fitness. As a result, the fitness scene is always shifting, and while at the size of a single generation, the euphemism of a fitness landscape with peaks and valleys still remains true, it no longer holds true when seen from the perspective of the entire evolutionary process. What are the characteristics of these algorithms? Is it possible to define a model that will aid in understanding how it functions? This knowledge is necessary for analyzing new Novelty Search versions and current Novelty Search versions, perhaps more effective ones. We claim that in the behaviour space, Novelty Search behaves asymptotically as a uniform random search process. This is an intriguing feature because it's not practical to sample this area directly. The genotype space is only accessible to the algorithm directly, which has a complicated interaction with the behaviour space. On a classic Novelty Search experiment, we discuss the model and put it through its paces. We also show that it puts new light on previous study findings and suggests new research directions.

References
  1. M. A. Bedau and N. H. Packard. Measurement of evolutionary activity, teleology, and life. In C. G. Langton, C. Taylor, J. D. Farmer, and S. Rasmussen, editors, Proc. of Art. Life II, pages 431–461, Redwood City, CA, 1991. AddisonWesley.
  2. M. A. Bedau, E. Snyder, and N. H. Packard. A classification of longterm evolutionary dynamics. In C. Adami, R. Belew, H. Kitano, and C. Taylor, editors, Pro. of Art. Life VI, pages 228–237, Cambridge, MA, 1998. MIT Press.
  3. Mark Bedau. Four puzzles about life. Artificial Life, 4:125–140, 1998.
  4. A. Channon. Passing the alife test: Activity statistics classify evolution in geb as unbounded. In Proceedings of the European Conference on Artificial Life (ECAL-2001). Springer, 2001.
  5. Paul Darwen and Yin Yao. Every niching method has its niche: Fitness sharing and implicit sharing compared. In Hans-Michael Voigt, Werner Ebeling, Ingo Rechenberg, and Hans-Paul Schwefel, editors, Parallel Problem Solving from Nature – PPSN IV, pages 398–407, Berlin, 1996. Springer.
  6. Richard Dawkins. Genetic and evolutionary computation conference (GECCO2007) Keynote Debate, July 2007.
  7. E. D. De Jong. The incremental pareto-coevolution archive. In Proc. of the Genetic and Evol. Comp. Conf. (GECCO-2004), Berlin, 2004. Springer Verlag.
  8. Jeffrey L. Elman. Incremental learning, or the importance of starting small Technical Report 9101, CRL, La Jolla, CA, 1991.
  9. David E. Goldberg. Simple genetic algorithms and the minimal deceptive problem. In L. D. Davis, editor, Genetic Algorithms and Simulated Annealing, Research Notes in Artificial Intelligence. Morgan Kaufmann, 2007.
  10. Faustino Gomez and Risto Miikkulainen. Incremental evolution of complex general behavior. Adaptive Behavior, 5:317–342, 1997.
  11. Inman Harvey. The Artificial Evolution of Adaptive Behavior. PhD thesis, School of Cognitive and Computing Sciences, U. of Sussex, Sussex, 1993.
  12. Kimberly A. Hughes, Linh Du, F. Helen Rodd, and David N. Reznick. Familiarity leads to female mate preference for novel males in the guppy, poecilia reticulata. Animal Behavior, 58(4):907–916, 1999.
  13. Marcus Hutter and Shane Legg. Fitness uniform optimization. IEEE Transactions on Evolutionary Computation, 10:568–589, 2006.
  14. Michael Lynch. The evolution of genetic networks by non-adaptive processes. Nature Reviews Genetics, 8:803–813, 2007.
  15. Michael Lynch. The frailty of adaptive hypotheses for the origins of organismal complexity. In Proc Natl Acad Sci USA, volume 104, pages 8597–8604, 2007.
  16. C. C. Maley. Four steps toward open-ended evolution. In Proc. of the Genetic and Evol. Comp. Conf. (GECCO-1999), pages 1336–1343, San Francisco, 1999.Kaufmann.
  17. Andrew P. Martin. Increasing genomic complexity by gene duplication and the origin of vertebrates. The American Naturalist, 154(2):111–128, 1999.
  18. Daniel W. McShea. Complexity and evolution: What everybody knows. Biology and Philosophy, 6(3):303–324, 1991.
  19. Thomas Miconi. Evolution and complexity: The double-edged sword. Artificial Life: Special Issue on the Evolution of Complexity, 2007.
  20. Thomas Miconi. THE ROAD TO EVERYWHERE: Evolution, Complexity and Progress in Nature and in Computers. PhD thesis, U. of Birmingham, 2007.
  21. Melanie Mitchell, Stephanie Forrest, and John H. Holland. The royal road for genetic algorithms: Fitness landscapes and ga performance. In F. J. Varela and P. Bourgine, editors, Proceedings of the First European Conference on Artificial Life, Cambridge, MA, 1992. MIT Press.
  22. Tom M. Mitchell. Machine Learning. McGraw-Hill, New York, 1997.
  23. C. L. Nehaniv and J. L. Rhodes. On the manner in which biological complexity may grow. In Math. and Comp. Biology, volume 26 of Lectures on Mathematics in the Life Sciences, pages 93–102. American Mathematical Society, 1999.
  24. T. Ray. Evolution, ecology and optimization of digital organisms. Technical Report Working paper 92-08-042, Santa Fe Institute, 1992.
  25. Russell Standish. Open-ended artificial evolution. International Journal of Computational Intelligence and Applications, 3(167), 2003.
  26. Kenneth O. Stanley, Bobby D. Bryant, and Risto Miikkulainen. Real-time neuroevolution in the NERO video game. IEEE Trans. on Evol. Comp. Special Issue on Evolutionary Computation and Games, 9(6):653–668, 2005.
  27. Kenneth O. Stanley and Risto Miikkulainen. Evolving neural networks through augmenting topologies. Evolutionary Computation, 10:99–127, 2002.
  28. Kenneth O. Stanley and Risto Miikkulainen. A taxonomy for artificial embryogeny. Artificial Life, 9(2):93–130, 2003.
  29. Kenneth O. Stanley and Risto Miikkulainen. Competitive coevolution through evolutionary complexification. Journal of Art. Int. Research, 21:63–100, 2004.
  30. Michiel Van de Panne and Alexis Lamouret. Guided optimization for balanced locomotion. In D. Terzopoulos and D. Thalmann, editors, Sixth Eurographics Workshop on Animation and Simulation, pages 165–177. Springer Verlag, 1995.
  31. James D. Watson, Nancy H. Hopkins, Jeffrey W. Roberts, Joan A. Steitz, and Alan M. Weiner. Molecular Biology of the Gene Fourth Edition. The Benjamin Cummings Publishing Company, Inc., Menlo Park, CA, 1987.
  32. Larry Yaeger. Computational genetics, physiology, metabolism, neural systems, learning, vision and behavior or polyworld: Life in a new context. In C. G. Langton, editor, Art. Life III, Proc. Vol. XVII, pages 263–298. Addison-Wesley,1994.
  33. Stephane Doncieux, Alban Laflaquière, Alexandre Coninx, Novelty Search: A Theoretical Perspective.
  34. Matej Črepinšek, Shih-Hsi Liu, and Marjan Mernik. 2013. Exploration and exploitation in evolutionary algorithms: A survey. ACM Computing Surveys (CSUR) 45, 3 (2013), 35.
  35. Antoine Cully and Yiannis Demiris. 2018. Quality and diversity optimization: A unifying modular framework. IEEE Transactions on Evolutionary Computation 22, 2 (2018), 245–259.
  36. Agoston E Eiben and Cornelis A Schippers. 1998. On evolutionary exploration and exploitation. Fundamental Informatician 35, 1-4 (1998), 35–50.
  37. Jorge Gomes, Pedro Mariano, and Anders Lyhne Christensen. 2015. Devising effective novelty search algorithms: A comprehensive empirical study. In Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation. ACM, 943–950.
  38. Jorge Gomes, Paulo Urbano, and Anders Lyhne Christensen. 2013. Evolution of swarm robotics systems with novelty search. Swarm Intelligence 7, 2-3 (2013), 115–144.
  39. Marc Kirschner and John Gerhart. 1998. Evolvability. Proceedings of the National Academy of Sciences 95, 15 (1998), 8420–8427.
  40. Steijn Kistemaker and Shimon Whiteson. 2011. Critical factors in the performance of novelty search. In Proceedings of the 13th annual conference on Genetic and evolutionary computation. ACM, 965–972.
  41. Joel Lehman and Kenneth O Stanley. 2010. Efficiently evolving programs through the search for novelty. In Proceedings of the 12th annual conference on Genetic and evolutionary computation. ACM, 837–844.
  42. Joel Lehman and Kenneth O Stanley. 2011. Abandoning objectives: Evolution through the search for novelty alone. Evolutionary computation 19, 2 (2011), 189–223.
  43. Joel Lehman and Kenneth O Stanley. 2011. Evolving a diversity of virtual creatures through novelty search and local competition. In Proceedings of the 13th annual conference on Genetic and evolutionary computation. ACM, 211–218.
  44. Joel Lehman and Kenneth O Stanley. 2011. Improving evolvability through novelty search and self-adaptation. In IEEE Congress on Evolutionary Computation. 2693–2700.
  45. Joel Lehman and Kenneth O Stanley. 2013. Evolvability is inevitable: Increasing evolvability without the pressure to adapt. PloS one 8, 4 (2013), e62186.
  46. Joel Lehman, Bryan Wilder, and Kenneth O Stanley. 2016. On the critical role of divergent selection in evolvability. Frontiers in Robotics and AI 3 (2016), 45.
  47. Antonios Liapis, Georgios N Yannakakis, and Julian Togelius. 2015. Constrained novelty search: A study on game content generation. Evolutionary computation 23, 1 (2015), 101–129. Jean-Baptiste Mouret and Jeff Clune. 2015. Illuminating search spaces by mapping elites. CoRR abs/1504.04909 (2015). arXiv:1504.04909 http://arxiv.org/abs/1504. 04909 .
  48. Jean-Baptiste Mouret and Stephane Doncieux. 2012. Encouraging behavioral diversity in evolutionary robotics: An empirical study. Evolutionary computation 20, 1 (2012), 91–133.
  49. Massimo Pigliucci. 2008. Is evolvability evolvable? Nature Reviews Genetics 9, 1 (2008), 75.
  50. Justin K Pugh, Lisa B Soros, and Kenneth O Stanley. 2016. Quality diversity: A new frontier for evolutionary computation. Frontiers in Robotics and AI 3 (2016), 40.
  51. Joseph Reisinger and Risto Miikkulainen. 2007. Acquiring evolvability through adaptive representations. In Proceedings of the 9th annual conference on Genetic and evolutionary computation. ACM, 1045–1052.
  52. Sebastian Risi, Charles E Hughes, and Kenneth O Stanley. 2010. Evolving plastic neural networks with novelty search. Adaptive Behavior 18, 6 (2010), 470–491.
  53. Tom Smith, Phil Husbands, and Michael O’Shea. 2003. Local evolvability of statistically neutral GasNet robot controllers. Biosystems 69, 2-3 (2003), 223–243.
  54. Kenneth O Stanley and Risto Miikkulainen. 2002. Evolving neural networks through augmenting topologies. Evolutionary computation 10, 2 (2002), 99–127.
  55. Danesh Tarapore, Jeff Clune, Antoine Cully, and Jean-Baptiste Mouret. 2016. How do different encodings influence the performance of the MAP-Elites algorithm? In Proceedings of the Genetic and Evolutionary Computation Conference 2016. ACM, 173–180.
  56. Danesh Tarapore and Jean-Baptiste Mouret. 2015. Evolvability signatures of generative encodings: beyond standard performance benchmarks. Information Sciences 313 (2015), 43–61.
  57. Günter P Wagner and Lee Altenberg. 1996. Perspective: complex adaptations and the evolution of evolvability. Evolution 50, 3 (1996), 967–976.
  58. Bryan Wilder and Kenneth Stanley. 2015. Reconciling explanations for the evolution of evolvability. Adaptive Behavior 23, 3 (2015), 171–179. Sewall Wright. 1932. The roles of mutation, inbreeding, crossbreeding, and selection in evolution. In Proceedings of the Sixth International Congress on Genetics. 356–366.
  59. Al-Moalmi, Ammar, Juan Luo, Ahmad Salah, and Kenli Li. "Optimal virtual machine placement based on grey wolf optimization." Electronics 8, no. 3 (2019): 283.
  60. Al-Moalmi, Ammar, Juan Luo, Ahmad Salah, Kenli Li, and Luxiu Yin. "A whale optimization system for energy-efficient container placement in data centers." Expert Systems with Applications 164 (2021): 113719.
  61. Salah A, Shalabi E, Khedr W. A lightweight android malware classifier using novel feature selection methods. Symmetry. 2020 May;12(5):858.
  62. Salah A, Li K, Li K. Lazy-Merge: A Novel Implementation for Indexed Parallel K-Way In-Place Merging. IEEE Transactions on Parallel and Distributed Systems. 2015 Sep 2;27(7):2049-61.
  63. Hosny KM, Salah A, Saleh HI, Sayed M. Fast computation of 2D and 3D Legendre moments using multi-core CPUs and GPU parallel architectures. Journal of Real-Time Image Processing. 2019 Dec;16(6):2027-41.
Index Terms

Computer Science
Information Sciences

Keywords

Robotics

Powered by PhDFocusTM