Abstract
With a growing availability of ambient computing power as well as sensor data, networked systems are emerging in all areas of daily life. Coordination and optimization in complex cyber-physical systems demand for decentralized and self-organizing algorithms to cope with problem size and distributed information availability. Self-organization often relies on emergent behavior. Local observations and decisions aggregate to some global behavior without any apparent, explicitly programmed rule. Systematically designing algorithms with emergent behavior suitably for a new orchestration or optimization task is, at best, tedious and error prone. Appropriate design patterns are scarce so far. It is demonstrated that a machine learning approach based on Cartesian Genetic Programming is capable of learning the emergent mechanisms that are necessary for swarm-based optimization. Targeted emergent behavior can be evolved by evolution strategies. The learned swarm behavior is already significantly better than just random search. The encountered pitfalls as well as remaining challenges on the research agenda are discussed in detail. An additional fitness landscape analysis gives insight in obstructions during evolutions and clues for future improvements.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Balaban, V., Lim, S., Gupta, G., Boedicker, J., Bogdan, P.: Quantifying emergence and self-organisation of enterobacter cloacae microbial communities. Sci. Rep. 8(1), 1–9 (2018)
Ball, R.C., Diakonova, M., MacKay, R.S.: Quantifying emergence in terms of persistent mutual information. Adv. Complex Syst. 13(03), 327–338 (2010)
Bremer, J., Lehnhoff, S.: Towards evolutionary emergence. Ann. Comput. Sci. Inf. Syst. 26, 55–60 (2021)
Burkov, A.: The Hundred-page Machine Learning Book, vol. 1. Andriy Burkov Canada (2019)
Busoniu, L., Babuska, R., De Schutter, B.: A comprehensive survey of multiagent reinforcement learning. IEEE Trans. Syst. Man Cybernet. Part C (Applications and Reviews) 38(2), 156–172 (2008)
Buşoniu, L., Babuška, R., De Schutter, B.: Multi-agent reinforcement learning: an overview. Innovations in Multi-agent Systems and Applications-1, pp. 183–221 (2010)
Calvaresi, D., Appoggetti, K., Lustrissimini, L., Marinoni, M., Sernani, P., Dragoni, A.F., Schumacher, M.: Multi-agent systems’ negotiation protocols for cyber-physical systems: results from a systematic literature review. In: ICAART (1), pp. 224–235 (2018)
Cardwell, L., Shebanow, A.: The efficacy and challenges of scada and smart grid integration. J. Cyber Secur. Inf. Syst. 1(3), 1–7 (2016)
Chaitin, G.J.: Algorithmic information theory. Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, Cambridge, Cambridgeshire, New York (1987)
Chen, C.C., Nagl, S.B., Clack, C.D.: Specifying, detecting and analysing emergent behaviours in multi-level agent-based simulations. In: Summer Computer Simulation Conference 2007, SCSC’07, Part of the 2007 Summer Simulation Multiconference, SummerSim’07, vol. 2, pp. 969–976. ACM: Association for Computing Machinery (2007)
Clegg, J., Walker, J.A., Miller, J.F.: A new crossover technique for cartesian genetic programming. In: Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation, pp. 1580–1587 (2007)
Collier, J.: Fundamental properties of self-organization. Causality, emergence, self-organisation, pp. 287–302 (2003)
Cramer, N.L.: A representation for the adaptive generation of simple sequential programs. In: Grefenstette, J.J. (ed.), Proceedings of an International Conference on Genetic Algorithms and the Applications, pp. 183–187. Carnegie-Mellon University, Pittsburgh, PA, USA (1985)
De Jong, K.A.: Analysis of the behavior of a class of genetic adaptive systems. Ph.D. Thesis, University of Michigan, Ann Arbor (1975)
Di Marzo Serugendo, G.: Engineering emergent behaviour: a vision. In: Hales, D., Edmonds, B., Norling, E., Rouchier, J. (eds.) Multi-Agent-Based Simulation III, pp. 1–7. Springer, Berlin (2003)
Dormans, J., et al.: Engineering emergence: applied theory for game design. Universiteit van Amsterdam [Host] (2012)
Dourado, A.M.B., Pedrino, E.C.: Multi-objective cartesian genetic programming optimization of morphological filters in navigation systems for visually impaired people. Appl. Soft Comput. 89, 106,130 (2020)
European Commission: Draft Ethics Guidelines for Trustworthy AI. Technical Report, European Commission (2018)
Forsyth, R.: BEAGLE a darwinian approach to pattern recognition. Kybernetes 10(3), 159–166 (1981). https://doi.org/10.1108/eb005587
Goldman, B.W., Punch, W.F.: Reducing wasted evaluations in cartesian genetic programming. In: European Conference on Genetic Programming, pp. 61–72. Springer (2013)
Grassberger, P., Procaccia, I.: Characterization of strange attractors. Phys. Rev. Lett. 50(5), 346 (1983)
Grassberger, P., Schreiber, T., Schaffrath, C.: Nonlinear time sequence analysis. Int. J. Bifurc. Chaos 1(03), 521–547 (1991)
Harding, S., Graziano, V., Leitner, J., Schmidhuber, J.: Mt-cgp: Mixed type cartesian genetic programming. In: Proceedings of the 14th Annual Conference on Genetic and Evolutionary Computation, GECCO ’12, pp. 751–758. Association for Computing Machinery, New York, NY, USA (2012). https://doi.org/10.1145/2330163.2330268
Harding, S., Leitner, J., Schmidhuber, J.: Cartesian genetic programming for image processing. In: Genetic programming theory and practice X, pp. 31–44. Springer (2013)
Harding, S.L., Miller, J.F., Banzhaf, W.: Self-modifying cartesian genetic programming. In: Cartesian Genetic Programming, pp. 101–124. Springer (2011)
Hebb, D.O.: The organization of behavior; a neuropsycholocigal theory. A Wiley Book in Clinical Psychology, vol. 62, p. 78 (1949)
Hinrichs, C., Sonnenschein, M.: A distributed combinatorial optimisation heuristic for the scheduling of energy resources represented by self-interested agents. Int. J. Bio-Inspir. Comput. 10(2), 69–78 (2017)
Hoel, E.P., Albantakis, L., Tononi, G.: Quantifying causal emergence shows that macro can beat micro. Proc. Natl. Acad. Sci. 110(49), 19790–19795 (2013a). https://doi.org/10.1073/pnas.1314922110. https://www.pnas.org/content/110/49/19790
Hoel, E.P., Albantakis, L., Tononi, G.: Quantifying causal emergence shows that macro can beat micro. Proc. Natl. Acad. Sci. 110(49), 19790–19795 (2013b)
Hovda, P.: Quantifying weak emergence. Mind. Mach. 18(4), 461–473 (2008)
Hrbacek, R., Dvorak, V.: Bent function synthesis by means of cartesian genetic programming. In: International Conference on Parallel Problem Solving from Nature, pp. 414–423. Springer (2014)
Hurst, H.E.: The problem of long-term storage in reservoirs. Hydrol. Sci. J. 1(3), 13–27 (1956)
Hurst, H.E.: A suggested statistical model of some time series which occur in nature. Nature 180(4584), 494–494 (1957)
Inácio, T., Miragaia, R., Reis, G., Grilo, C., Fernandéz, F.: Cartesian genetic programming applied to pitch estimation of piano notes. In: 2016 IEEE Symposium Series on Computational Intelligence (SSCI), pp. 1–7. IEEE (2016)
Jahn, J.: Scalarization in multi objective optimization. In: Mathematics of Multi Objective Optimization, pp. 45–88. Springer (1985)
Jamil, M., Yang, X.S., Zepernick, H.J.: 8 - test functions for global optimization: a comprehensive survey. In: Yang, X.S., Cui, Z., Xiao, R., Gandomi, A.H., Karamanoglu, M. (eds.), Swarm Intelligence and Bio-Inspired Computation, pp. 193–222. Elsevier, Oxford (2013). https://doi.org/10.1016/B978-0-12-405163-8.00008-9
Jipp, M., Ackerman, P.L.: The impact of higher levels of automation on performance and situation awareness. J. Cognit. Eng. Dec. Making 10(2), 138–166 (2016). https://doi.org/10.1177/1555343416637517
Kaelbling, L.P., Littman, M.L., Moore, A.W.: Reinforcement learning: a survey. J. Artif. Intell. Res. 4, 237–285 (1996)
Kalkreuth, R., Rudolph, G., Krone, J.: More efficient evolution of small genetic programs in cartesian genetic programming by using genotypie age. In: 2016 IEEE Congress on Evolutionary Computation (CEC), pp. 5052–5059. IEEE (2016)
Kaufmann, P., Platzner, M.: Combining local and global search: a multi-objective evolutionary algorithm for cartesian genetic programming. In: Inspired by Nature, pp. 175–194. Springer (2018)
Kennedy, J., Eberhart, R.: Particle swarm optimization. In: Proceedings of ICNN’95-International Conference on Neural Networks, vol. 4, pp. 1942–1948. IEEE (1995)
Khan, M.M., Ahmad, A.M., Khan, G.M., Miller, J.F.: Fast learning neural networks using cartesian genetic programming. Neurocomputing 121, 274–289 (2013)
Koza, J.R.: Hierarchical genetic algorithms operating on populations of computer programs. In: Sridharan, N.S. (ed.) Proceedings of the Eleventh International Joint Conference on Artificial Intelligence IJCAI-89, vol. 1, pp. 768–774. Morgan Kaufmann, Detroit, MI, USA (1989)
Koza, J.R.: Non-linear genetic algorithms for solving problems. United States Patent 4935877 (1990). Filed may 20, 1988, issued june 19, 1990, 4,935,877. Australian patent 611,350 issued september 21, 1991. Canadian patent 1,311,561 Issued December 15, 1992
Koza, J.R.: Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge (1992)
Koza, J.R., Koza, J.R.: Genetic programming: on the programming of computers by means of natural selection, vol. 1. MIT Press (1992)
Koza, J.R., Poli, R.: Genetic programming. In: Search Methodologies, pp. 127–164. Springer (2005)
Martinez-Gil, F., Lozano, M., Fernandez, F.: Emergent behaviors and scalability for multi-agent reinforcement learning-based pedestrian models. Simul. Model. Pract. Theory 74, 117–133 (2017)
McKee, D.W., Clement, S.J., Almutairi, J., Xu, J.: Survey of advances and challenges in intelligent autonomy for distributed cyber-physical systems. CAAI Trans. Intell. Technol. 3(2), 75–82 (2018)
Mihaylov, G., Spallanzani, M.: Emergent behaviour in a system of industrial plants detected via manifold learning. Int. J. Progn. Health Manag. 7(4) (2016)
Miller, J.: What bloat? Cartesian genetic programming on Boolean problems. In: 2001 Genetic and Evolutionary Computation Conference Late Breaking Papers, pp. 295–302. San Francisco, California, USA (2001)
Miller, J.: Cartesian Genetic Programming, vol. 43. Springer (2003). https://doi.org/10.1007/978-3-642-17310-3
Miller, J., Series, N.C.: Resources for cartesian genetic programming. Cartesian Genetic Programming, p. 337 (2011)
Miller, J.F., Harding, S.L.: Cartesian genetic programming. In: Proceedings of the 10th Annual Conference Companion on Genetic and Evolutionary Computation, pp. 2701–2726 (2008)
Miller, J.F., Smith, S.L.: Redundancy and computational efficiency in cartesian genetic programming. IEEE Trans. Evol. Comput. 10(2), 167–174 (2006)
Miller, J.F., Thomson, P., Fogarty, T.: Designing electronic circuits using evolutionary algorithms. Arithmetic circuits: a case study. Genetic Algorithms and Evolution Strategies in Engineering and Computer Science, pp. 105–131 (1997)
Miller, J.F., et al.: An empirical study of the efficiency of learning Boolean functions using a cartesian genetic programming approach. In: Proceedings of the Genetic and Evolutionary Computation Conference, vol. 2, pp. 1135–1142 (1999)
Nápoles, G., Grau, I., Bello, M., Bello, R.: Towards swarm diversity: Random sampling in variable neighborhoods procedure using a lévy distribution. Computación y Sistemas 18(1), 79–95 (2014)
Nieße, A., Lehnhoff, S., Tröschel, M., Uslar, M., Wissing, C., Appelrath, H.J., Sonnenschein, M.: Market-based self-organized provision of active power and ancillary services: an agent-based approach for smart distribution grids. In: 2012 Complexity in Engineering (COMPENG). Proceedings, pp. 1–5 (2012). https://doi.org/10.1109/CompEng.2012.6242953
Parasuraman, R., Wickens, C.D.: Humans: still vital after all these years of automation. Hum. Factors 50(3), 511–520 (2008). https://doi.org/10.1518/001872008X312198
Parhizkar, M., Serugendo, G.D.M., Hassas, S.: Leaders and followers: a design pattern for second-order emergence. In: 2019 IEEE 4th International Workshops on Foundations and Applications of Self* Systems (FAS* W), pp. 269–270. IEEE (2019)
Parzyjegla, H., Schröter, A., Seib, E., Holzapfel, S., Wander, M., Richling, J., Wacker, A., Heiß, H.U., Mühl, G., Weis, T.: Model-driven development of self-organising control applications. In: Organic Computing – A Paradigm Shift for Complex Systems, pp. 131–144. Springer (2011)
Pisner, D.A., Schnyer, D.M.: Support vector machine. In: Machine Learning, pp. 101–121. Elsevier (2020)
Platzer, A.: The logical path to autonomous cyber-physical systems. In: International Conference on Quantitative Evaluation of Systems, pp. 25–33. Springer (2019)
Poslad, S.: Specifying protocols for multi-agent systems interaction. ACM Trans. Auton. Adap. Syst. (TAAS) 2(4), 15–es (2007)
Prehofer, C., Bettstetter, C.: Self-organization in communication networks: principles and design paradigms. IEEE Commun. Mag. 43(7), 78–85 (2005). https://doi.org/10.1109/MCOM.2005.1470824
Rapp, B., Solsbach, A., Mahmoud, T., Memari, A., Bremer, J.: It-for-green: Next generation cemis for environmental, energy and resource management. In: Pillmann, W., Schade, S., Smits, P. (eds.), EnviroInfo 2011 - Innovations in Sharing Environmental Observation and Information, Proceedings of the 25th EnviroInfo Conference ‘Environmental Informatics’, pp. 573–581. Shaker Verlag (2011)
Scott, E.O., Luke, S.: Ecj at 20: toward a general metaheuristics toolkit. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion, pp. 1391–1398 (2019)
Shahbakhsh, A., Nieße, A.: Modeling multimodal energy systems. Automatisierungstechnik : AT 67(11), 893–903 (2019)
Shannon, C.E.: A mathematical theory of communication. Bell Syst. Techn. J. 27(379–423), 623–656 (1948)
Sheridan, T.B., Parasuraman, R.: Human-automation interaction. Rev. Human Factors Ergon. 1(1), 89–129 (2016). https://doi.org/10.1518/155723405783703082
Singh, S., Lu, S., Kokar, M.M., Kogut, P.A., Martin, L.: Detection and classification of emergent behaviors using multi-agent simulation framework (wip). In: Proceedings of the Symposium on Modeling and Simulation of Complexity in Intelligent, Adaptive and Autonomous Systems, MSCIAAS ’17. Society for Computer Simulation International, San Diego, CA, USA (2017)
Sotto, L.F.D.P., Kaufmann, P., Atkinson, T., Kalkreuth, R., Basgalupp, M.P.: A study on graph representations for genetic programming. In: Proceedings of the 2020 Genetic and Evolutionary Computation Conference, GECCO ’20, pp. 931–939. Association for Computing Machinery, New York, NY, USA (2020). https://doi.org/10.1145/3377930.3390234
Spaanenburg, L.: Early detection of abnormal emergent behaviour. European Signal Processing Conference (2007)
Sutton, R.S., Barto, A.G.: Reinforcement Learning: An Introduction. MIT Press (2018)
Tan, M.: Multi-agent reinforcement learning: Independent vs. cooperative agents. In: Proceedings of the Tenth International Conference on Machine Learning, pp. 330–337 (1993)
Theraulaz, G., Bonabeau, E.: A brief history of stigmergy. Artif. Life 5(2), 97–116 (1999)
Turing, A.M.: Computing machinery and intelligence. Mind 49(236), 433–460 (1950)
Turner, A.J., Miller, J.F.: Cartesian genetic programming: Why no bloat? In: European Conference on Genetic Programming, pp. 222–233. Springer (2014a)
Turner, A.J., Miller, J.F.: Recurrent cartesian genetic programming. In: Bartz-Beielstein, T., Branke, J., Filipič, B., Smith, J. (eds.) Parallel Problem Solving from Nature - PPSN XIII, pp. 476–486. Springer International Publishing, Cham (2014b)
Turner, A.J., Miller, J.F.: Recurrent cartesian genetic programming. In: International Conference on Parallel Problem Solving from Nature, pp. 476–486. Springer (2014c)
Turner, A.J., Miller, J.F.: Recurrent cartesian genetic programming of artificial neural networks. Genet. Program Evolvable Mach. 18(2), 185–212 (2017)
Van Gerven, M., Bohte, S.: Artificial neural networks as models of neural information processing. Front. Comput. Neurosci. 11, 114 (2017)
Vassilev, V.K., Fogarty, T.C., Miller, J.F.: Information characteristics and the structure of landscapes. Evol. Comput. 8(1), 31–60 (2000). https://doi.org/10.1162/106365600568095
Walker, J.A., Miller, J.F., Cavill, R.: A multi-chromosome approach to standard and embedded cartesian genetic programming. In: Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation, pp. 903–910 (2006)
Walker, J.A., Völk, K., Smith, S.L., Miller, J.F.: Parallel evolution using multi-chromosome cartesian genetic programming. Genet. Program Evolvable Mach. 10(4), 417 (2009)
Watson, J.P.: An introduction to fitness landscape analysis and cost models for local search. In: Handbook of Metaheuristics, pp. 599–623. Springer (2010)
Weron, R.: Estimating long-range dependence: finite sample properties and confidence intervals. Physica A 312(1–2), 285–299 (2002)
Zanella, A., Bui, N., Castellani, A., Vangelista, L., Zorzi, M.: Internet of things for smart cities. IEEE Internet Things J. 1(1), 22–32 (2014). https://doi.org/10.1109/JIOT.2014.2306328
Zhu, Q., Bushnell, L., Başar, T.: Resilient distributed control of multi-agent cyber-physical systems. In: Control of Cyber-Physical Systems, pp. 301–316. Springer (2013)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this chapter
Cite this chapter
Bremer, J. (2022). Learning to Optimize. In: Fidanova, S. (eds) Recent Advances in Computational Optimization. WCO 2021. Studies in Computational Intelligence, vol 1044. Springer, Cham. https://doi.org/10.1007/978-3-031-06839-3_1
Download citation
DOI: https://doi.org/10.1007/978-3-031-06839-3_1
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-06838-6
Online ISBN: 978-3-031-06839-3
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)