Nothing Special   »   [go: up one dir, main page]

Skip to main content

Learning to Optimize

  • Chapter
  • First Online:
Recent Advances in Computational Optimization (WCO 2021)

Part of the book series: Studies in Computational Intelligence ((SCI,volume 1044))

Included in the following conference series:

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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 129.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 169.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book
USD 169.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

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)

    Article  Google Scholar 

  • Ball, R.C., Diakonova, M., MacKay, R.S.: Quantifying emergence in terms of persistent mutual information. Adv. Complex Syst. 13(03), 327–338 (2010)

    Article  MathSciNet  Google Scholar 

  • Bremer, J., Lehnhoff, S.: Towards evolutionary emergence. Ann. Comput. Sci. Inf. Syst. 26, 55–60 (2021)

    Google Scholar 

  • Burkov, A.: The Hundred-page Machine Learning Book, vol. 1. Andriy Burkov Canada (2019)

    Google Scholar 

  • 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)

    Google Scholar 

  • 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)

    Google Scholar 

  • 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)

    Google Scholar 

  • Cardwell, L., Shebanow, A.: The efficacy and challenges of scada and smart grid integration. J. Cyber Secur. Inf. Syst. 1(3), 1–7 (2016)

    Google Scholar 

  • Chaitin, G.J.: Algorithmic information theory. Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, Cambridge, Cambridgeshire, New York (1987)

    Google Scholar 

  • 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)

    Google Scholar 

  • 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)

    Google Scholar 

  • Collier, J.: Fundamental properties of self-organization. Causality, emergence, self-organisation, pp. 287–302 (2003)

    Google Scholar 

  • 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)

    Google Scholar 

  • De Jong, K.A.: Analysis of the behavior of a class of genetic adaptive systems. Ph.D. Thesis, University of Michigan, Ann Arbor (1975)

    Google Scholar 

  • 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)

    Google Scholar 

  • Dormans, J., et al.: Engineering emergence: applied theory for game design. Universiteit van Amsterdam [Host] (2012)

    Google Scholar 

  • 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)

    Google Scholar 

  • European Commission: Draft Ethics Guidelines for Trustworthy AI. Technical Report, European Commission (2018)

    Google Scholar 

  • Forsyth, R.: BEAGLE a darwinian approach to pattern recognition. Kybernetes 10(3), 159–166 (1981). https://doi.org/10.1108/eb005587

    Article  Google Scholar 

  • Goldman, B.W., Punch, W.F.: Reducing wasted evaluations in cartesian genetic programming. In: European Conference on Genetic Programming, pp. 61–72. Springer (2013)

    Google Scholar 

  • Grassberger, P., Procaccia, I.: Characterization of strange attractors. Phys. Rev. Lett. 50(5), 346 (1983)

    Article  MathSciNet  Google Scholar 

  • Grassberger, P., Schreiber, T., Schaffrath, C.: Nonlinear time sequence analysis. Int. J. Bifurc. Chaos 1(03), 521–547 (1991)

    Article  MathSciNet  Google Scholar 

  • 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)

    Google Scholar 

  • Harding, S.L., Miller, J.F., Banzhaf, W.: Self-modifying cartesian genetic programming. In: Cartesian Genetic Programming, pp. 101–124. Springer (2011)

    Google Scholar 

  • Hebb, D.O.: The organization of behavior; a neuropsycholocigal theory. A Wiley Book in Clinical Psychology, vol. 62, p. 78 (1949)

    Google Scholar 

  • 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)

    Article  Google Scholar 

  • 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)

    Article  Google Scholar 

  • Hovda, P.: Quantifying weak emergence. Mind. Mach. 18(4), 461–473 (2008)

    Article  Google Scholar 

  • 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)

    Google Scholar 

  • Hurst, H.E.: The problem of long-term storage in reservoirs. Hydrol. Sci. J. 1(3), 13–27 (1956)

    Google Scholar 

  • Hurst, H.E.: A suggested statistical model of some time series which occur in nature. Nature 180(4584), 494–494 (1957)

    Article  Google Scholar 

  • 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)

    Google Scholar 

  • Jahn, J.: Scalarization in multi objective optimization. In: Mathematics of Multi Objective Optimization, pp. 45–88. Springer (1985)

    Google Scholar 

  • 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

    Article  Google Scholar 

  • Kaelbling, L.P., Littman, M.L., Moore, A.W.: Reinforcement learning: a survey. J. Artif. Intell. Res. 4, 237–285 (1996)

    Article  Google Scholar 

  • 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)

    Google Scholar 

  • 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)

    Google Scholar 

  • Kennedy, J., Eberhart, R.: Particle swarm optimization. In: Proceedings of ICNN’95-International Conference on Neural Networks, vol. 4, pp. 1942–1948. IEEE (1995)

    Google Scholar 

  • 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)

    Article  Google Scholar 

  • 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)

    Google Scholar 

  • 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

    Google Scholar 

  • Koza, J.R.: Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge (1992)

    MATH  Google Scholar 

  • Koza, J.R., Koza, J.R.: Genetic programming: on the programming of computers by means of natural selection, vol. 1. MIT Press (1992)

    Google Scholar 

  • Koza, J.R., Poli, R.: Genetic programming. In: Search Methodologies, pp. 127–164. Springer (2005)

    Google Scholar 

  • 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)

    Article  Google Scholar 

  • 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)

    Article  Google Scholar 

  • Mihaylov, G., Spallanzani, M.: Emergent behaviour in a system of industrial plants detected via manifold learning. Int. J. Progn. Health Manag. 7(4) (2016)

    Google Scholar 

  • 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)

    Google Scholar 

  • 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)

    Google Scholar 

  • 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)

    Google Scholar 

  • Miller, J.F., Smith, S.L.: Redundancy and computational efficiency in cartesian genetic programming. IEEE Trans. Evol. Comput. 10(2), 167–174 (2006)

    Article  Google Scholar 

  • 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)

    Google Scholar 

  • 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)

    Google Scholar 

  • 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)

    Google Scholar 

  • 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

    Article  Google Scholar 

  • 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)

    Google Scholar 

  • 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)

    Google Scholar 

  • Pisner, D.A., Schnyer, D.M.: Support vector machine. In: Machine Learning, pp. 101–121. Elsevier (2020)

    Google Scholar 

  • Platzer, A.: The logical path to autonomous cyber-physical systems. In: International Conference on Quantitative Evaluation of Systems, pp. 25–33. Springer (2019)

    Google Scholar 

  • Poslad, S.: Specifying protocols for multi-agent systems interaction. ACM Trans. Auton. Adap. Syst. (TAAS) 2(4), 15–es (2007)

    Google Scholar 

  • 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

    Article  Google Scholar 

  • 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)

    Google Scholar 

  • 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)

    Google Scholar 

  • Shahbakhsh, A., Nieße, A.: Modeling multimodal energy systems. Automatisierungstechnik : AT 67(11), 893–903 (2019)

    Article  Google Scholar 

  • Shannon, C.E.: A mathematical theory of communication. Bell Syst. Techn. J. 27(379–423), 623–656 (1948)

    Article  MathSciNet  Google Scholar 

  • Sheridan, T.B., Parasuraman, R.: Human-automation interaction. Rev. Human Factors Ergon. 1(1), 89–129 (2016). https://doi.org/10.1518/155723405783703082

    Article  Google Scholar 

  • 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)

    Google Scholar 

  • 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)

    Google Scholar 

  • Sutton, R.S., Barto, A.G.: Reinforcement Learning: An Introduction. MIT Press (2018)

    Google Scholar 

  • Tan, M.: Multi-agent reinforcement learning: Independent vs. cooperative agents. In: Proceedings of the Tenth International Conference on Machine Learning, pp. 330–337 (1993)

    Google Scholar 

  • Theraulaz, G., Bonabeau, E.: A brief history of stigmergy. Artif. Life 5(2), 97–116 (1999)

    Article  Google Scholar 

  • Turing, A.M.: Computing machinery and intelligence. Mind 49(236), 433–460 (1950)

    Article  MathSciNet  Google Scholar 

  • Turner, A.J., Miller, J.F.: Cartesian genetic programming: Why no bloat? In: European Conference on Genetic Programming, pp. 222–233. Springer (2014a)

    Google Scholar 

  • 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)

    Chapter  Google Scholar 

  • Turner, A.J., Miller, J.F.: Recurrent cartesian genetic programming. In: International Conference on Parallel Problem Solving from Nature, pp. 476–486. Springer (2014c)

    Google Scholar 

  • Turner, A.J., Miller, J.F.: Recurrent cartesian genetic programming of artificial neural networks. Genet. Program Evolvable Mach. 18(2), 185–212 (2017)

    Article  Google Scholar 

  • Van Gerven, M., Bohte, S.: Artificial neural networks as models of neural information processing. Front. Comput. Neurosci. 11, 114 (2017)

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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)

    Google Scholar 

  • 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)

    Article  Google Scholar 

  • Watson, J.P.: An introduction to fitness landscape analysis and cost models for local search. In: Handbook of Metaheuristics, pp. 599–623. Springer (2010)

    Google Scholar 

  • Weron, R.: Estimating long-range dependence: finite sample properties and confidence intervals. Physica A 312(1–2), 285–299 (2002)

    Article  MathSciNet  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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)

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Jörg Bremer .

Editor information

Editors and Affiliations

Rights and permissions

Reprints and permissions

Copyright information

© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this chapter

Check for updates. Verify currency and authenticity via CrossMark

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

Publish with us

Policies and ethics