[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Population-Based Algorithms Built on Weighted Automata

  • Conference paper
  • First Online:
Parallel Problem Solving from Nature – PPSN XVIII (PPSN 2024)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 15150))

Included in the following conference series:

  • 210 Accesses

Abstract

Many algorithms in natural computing and computational biology are population-based: genetic algorithms evolve candidate solutions for optimization problems; artificial immune systems and learning classifier systems maintain populations of rules. Using such algorithms at very large population sizes (e.g., millions or billions) is computationally expensive. Here, we develop a methodology for implementing population-based models using weighted finite state machines (WFSMs) with exact rational weights. For populations that can be represented as weighted sets of strings, WFSMs can reduce memory use and runtime of population-based algorithms by orders of magnitude. We demonstrate the generality of our approach by constructing an immune-inspired anomaly detector for string data and an evolutionary algorithm that solves Boolean satisfiability problems. The WFSM approach allows repurposing of advanced algorithms developed for natural language processing, and should be applicable to other population-based algorithms such as learning classifier systems.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
£29.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
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 129.99
Price includes VAT (United Kingdom)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 64.99
Price includes VAT (United Kingdom)
  • Compact, lightweight 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

  1. Allauzen, C., Riley, M., Schalkwyk, J., Skut, W., Mohri, M.: OpenFst: a general and efficient weighted finite-state transducer library. In: Holub, J., Zdarek, J. (eds.) CIAA 2007. LNCS, vol. 4783, pp. 11–23. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-76336-9_3

    Chapter  Google Scholar 

  2. Baluja, S., Caruana, R.: Removing the genetics from the standard genetic algorithm. In: Machine Learning Proceedings 1995, pp. 38–46. Elsevier (1995)

    Google Scholar 

  3. Blum, C.: Ant colony optimization: introduction and recent trends. Phys. Life Rev. 2(4), 353–373 (2005). https://doi.org/10.1016/j.plrev.2005.10.001

    Article  Google Scholar 

  4. Blum, C., Roli, A.: Metaheuristics in combinatorial optimization: overview and conceptual comparison. ACM Comput. Surv. 35(3), 268–308 (2003). https://doi.org/10.1145/937503.937505

    Article  Google Scholar 

  5. Borisovsky, P., Eremeev, A.: Comparing evolutionary algorithms to the (1+1)-ea. Theoret. Comput. Sci. 403(1), 33–41 (2008). https://doi.org/10.1016/j.tcs.2008.03.008

    Article  MathSciNet  Google Scholar 

  6. Cheeseman, P.C., Kanefsky, B., Taylor, W.M., et al.: Where the really hard problems are. In: IJCAI, vol. 91, pp. 331–337 (1991)

    Google Scholar 

  7. D’haeseleer, P.: An immunological approach to change detection: theoretical results. In: Proceedings 9th IEEE Computer Security Foundations Workshop. IEEE Computer Society Press (1996). https://doi.org/10.1109/csfw.1996.503687

  8. D’haeseleer, P., Forrest, S., Helman, P.: An immunological approach to change detection: algorithms, analysis and implications. In: Proceedings 1996 IEEE Symposium on Security and Privacy. IEEE Computer Society Press (1996). https://doi.org/10.1109/secpri.1996.502674

  9. Dunning, T.: Statistical Identification of Language. Tech. Rep. MCCS 94-273, New Mexico State University (1994)

    Google Scholar 

  10. Eisner, J.: Simpler and more general minimization for weighted finite-state automata. In: Proceedings of the 2003 Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics, pp. 64–71 (2003). https://doi.org/10.3115/1073445.1073454

  11. Elberfeld, M., Textor, J.: Efficient algorithms for string-based negative selection. In: Andrews, P.S., et al. (eds.) ICARIS 2009. LNCS, vol. 5666, pp. 109–121. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03246-2_14

  12. Elberfeld, M., Textor, J.: Negative selection algorithms on strings with efficient training and linear-time classification. Theor. Comput. Sci. 412, 534–542 (2011). https://doi.org/10.1016/j.tcs.2010.09.022

  13. Forrest, S., Perelson, A., Allen, L., Cherukuri, R.: Self-nonself discrimination in a computer. In: Proceedings of 1994 IEEE Computer Society Symposium on Research in Security and Privacy. IEEE Computer Society Press (1994). https://doi.org/10.1109/risp.1994.296580

  14. Gad, A.G.: Particle swarm optimization algorithm and its applications: a systematic review. Archiv. Comput. Methods Eng. 29(5), 2531–2561 (2022). https://doi.org/10.1007/s11831-021-09694-4

    Article  MathSciNet  Google Scholar 

  15. Boost. Boost C++ libraries. https://www.boost.org

  16. Harik, G.R., Lobo, F.G., Goldberg, D.E.: The compact genetic algorithm. IEEE Trans. Evol. Comput. 3(4), 287–297 (1999). https://doi.org/10.1109/4235.797971

    Article  Google Scholar 

  17. Hoos, H.H., Stützle, T.: Satlib: an online resource for research on sat. Sat 2000, 283–292 (2000)

    Google Scholar 

  18. Jansen, T.: Analyzing Evolutionary Algorithms: The Computer Science Perspective. Springer, Incorporated (2013). https://doi.org/10.1007/978-3-642-17339-4

    Book  Google Scholar 

  19. Kirkpatrick, S., Selman, B.: Critical behavior in the satisfiability of random Boolean expressions. Science 264(5163), 1297–1301 (1994). https://doi.org/10.1126/science.264.5163.1297

    Article  MathSciNet  Google Scholar 

  20. Liśkiewicz, M., Textor, J.: Negative selection algorithms without generating detectors. In: Proceedings of Genetic and Evolutionary Computation Conference (GECCO 2010), pp. 1047–1054. ACM (2010). https://doi.org/10.1145/1830483.1830673

  21. Manso, A., Correia, L.: Genetic algorithms using populations based on multisets. New Trends Artif. Intell. EPIA 2009, 53–64 (2009)

    Google Scholar 

  22. Martin, O.C., Monasson, R., Zecchina, R.: Statistical mechanics methods and phase transitions in optimization problems. Theoret. Comput. Sci. 265(1–2), 3–67 (2001). https://doi.org/10.1016/s0304-3975(01)00149-9

    Article  MathSciNet  Google Scholar 

  23. Mitchell, D., Selman, B., Levesque, H.: Hard and easy distributions of sat problems. In: Proceedings of the Tenth National Conference on Artificial Intelligence (AAAI 1992), pp. 459–465. AAAI Press (1992)

    Google Scholar 

  24. Mohri, M.: On some applications of finite-state automata theory to natural language processing. Nat. Lang. Eng. 2(1), 61–80 (1996). https://doi.org/10.1017/S135132499600126X

    Article  Google Scholar 

  25. Mohri, M.: Minimization algorithms for sequential transducers. Theoret. Comput. Sci. 234(1–2), 177–201 (2000). https://doi.org/10.1016/S0304-3975(98)00115-7

    Article  MathSciNet  Google Scholar 

  26. Schoning, T.: A probabilistic algorithm for k-sat and constraint satisfaction problems. In: 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039). SFCS-99. IEEE Computer Society (1999). https://doi.org/10.1109/sffcs.1999.814612

  27. Schröder, G., Textor, J.: Population-based algorithms built on weighted automata (implementation). Zenodo (2024). https://doi.org/10.5281/zenodo.12205008

  28. Sisson, S.A., Fan, Y., Tanaka, M.M.: Sequential Monte Carlo without likelihoods. Proc. Natl. Acad. Sci. 104(6), 1760–1765 (Feb 2007). https://doi.org/10.1073/pnas.0607208104

  29. Stibor, T., Mohr, P., Timmis, J., Eckert, C.: Is negative selection appropriate for anomaly detection? In: Proceedings of the 7th Annual Conference on Genetic and Evolutionary Computation. ACM (2005). https://doi.org/10.1145/1068009.1068061

  30. Textor, J.: A comparative study of negative selection based anomaly detection in sequence data. In: Coello Coello, C.A., Greensmith, J., Krasnogor, N., Liò, P., Nicosia, G., Pavone, M. (eds.) ICARIS 2012. LNCS, vol. 7597, pp. 28–41. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33757-4_3

    Chapter  Google Scholar 

  31. Textor, J., Dannenberg, K., Liśkiewicz, M.: A generic finite automata based approach to implementing lymphocyte repertoire models. In: Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation, pp. 129–136 (2014). https://doi.org/10.1145/2576768.2598331

  32. Timmis, J., Hone, A., Stibor, T., Clark, E.: Theoretical advances in artificial immune systems. Theor. Comput. Sci. 403(1), 11–32 (2008). https://doi.org/10.1016/j.tcs.2008.02.011

  33. Timmis, J., Knight, T., de Castro, L.N., Hart, E.: An Overview of Artificial Immune Systems, pp. 51–91. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-662-06369-9_4

  34. Urbanowicz, R.J., Moore, J.H.: Learning classifier systems: a complete introduction, review, and roadmap. J. Artif. Evol. Appl. 2009, 1–25 (2009). https://doi.org/10.1155/2009/736398

  35. Wortel, I.M., Keşmir, C., de Boer, R.J., Mandl, J.N., Textor, J.: Is T cell negative selection a learning algorithm? Cells 9(3), 690 (2020). https://doi.org/10.3390/cells9030690

    Article  Google Scholar 

Download references

Acknowledgments

JT and GS were supported by NWO grant VI.Vidi.192.084 (to JT).

Disclosure of Interests. The authors do not declare any conflict of interest.

Author information

Authors and Affiliations

  1. Institute for Computing and Information Sciences, Radboud University, Nijmegen, The Netherlands

    Gijs Schröder, Inge Wortel & Johannes Textor

Authors
  1. Gijs Schröder
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Inge Wortel
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Johannes Textor
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Johannes Textor .

Editor information

Editors and Affiliations

  1. University of Applied Sciences Upper Austria, Wels, Austria

    Michael Affenzeller

  2. University of Applied Sciences Upper Austria, Hagenberg, Austria

    Stephan M. Winkler

  3. Leiden University, Leiden, The Netherlands

    Anna V. Kononova

  4. University of Paderborn, Paderborn, Germany

    Heike Trautmann

  5. Jožef Stefan Institute, Ljubljana, Slovenia

    Tea Tušar

  6. University of Coimbra, Coimbra, Portugal

    Penousal Machado

  7. Leiden University, LEIDEN, The Netherlands

    Thomas Bäck

Rights and permissions

Reprints and permissions

Copyright information

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

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Schröder, G., Wortel, I., Textor, J. (2024). Population-Based Algorithms Built on Weighted Automata. In: Affenzeller, M., et al. Parallel Problem Solving from Nature – PPSN XVIII. PPSN 2024. Lecture Notes in Computer Science, vol 15150. Springer, Cham. https://doi.org/10.1007/978-3-031-70071-2_20

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-70071-2_20

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-70070-5

  • Online ISBN: 978-3-031-70071-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation