{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,27]],"date-time":"2026-01-27T13:37:56Z","timestamp":1769521076091,"version":"3.49.0"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2019,12,1]],"date-time":"2019-12-01T00:00:00Z","timestamp":1575158400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,12,30]],"date-time":"2019-12-30T00:00:00Z","timestamp":1577664000000},"content-version":"vor","delay-in-days":29,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Appl Netw Sci"],"published-print":{"date-parts":[[2019,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Random Boolean Networks (RBNs) are an arguably simple model which can be used to express rather complex behaviour, and have been applied in various domains. RBNs may be controlled using rule-based machine learning, specifically through the use of a learning classifier system (LCS) \u2013 an eXtended Classifier System (XCS) can evolve a set of<jats:italic>condition-action<\/jats:italic>rules that direct an RBN from any state to a target state (<jats:italic>attractor<\/jats:italic>). However, the rules evolved by XCS may not be optimal, in terms of minimising the total cost along the paths used to direct the network from any state to a specified attractor. In this paper, we present an algorithm for uncovering the optimal set of control rules for controlling random Boolean networks. We assign relative costs for interventions and \u2018natural\u2019 steps. We then compare the performance of this optimal rule calculator algorithm (ORC) and the XCS variant of learning classifier systems. We find that the rules evolved by XCS are not optimal in terms of total cost. The results provide a benchmark for future improvement.<\/jats:p>","DOI":"10.1007\/s41109-019-0243-z","type":"journal-article","created":{"date-parts":[[2019,12,30]],"date-time":"2019-12-30T15:02:31Z","timestamp":1577718151000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Learning versus optimal intervention in random Boolean networks"],"prefix":"10.1007","volume":"4","author":[{"given":"Matthew R.","family":"Karlsen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sotiris K.","family":"Moschoyiannis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vlad B.","family":"Georgiev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,12,30]]},"reference":[{"issue":"4","key":"243_CR1","doi-asserted-by":"publisher","first-page":"670","DOI":"10.1016\/j.jtbi.2006.09.023","volume":"244","author":"T Akutsu","year":"2007","unstructured":"Akutsu, T, Hayashida M, Ching WK, Ng MK (2007) Control of Boolean networks: Hardness results and algorithms for tree structured networks. J Theor Biol 244(4):670\u2013679.","journal-title":"J Theor Biol"},{"key":"243_CR2","first-page":"1832","volume-title":"Genetic and Evolutionary Computation Conference","author":"A Barry","year":"2003","unstructured":"Barry, A (2003) Limits in long path learning with xcs In: Genetic and Evolutionary Computation Conference, 1832\u20131843. Springer, Berlin."},{"issue":"3-4","key":"243_CR3","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/s005000100115","volume":"6","author":"AM Barry","year":"2002","unstructured":"Barry, AM (2002) The stability of long action chains in XCS. Soft Comput 6(3-4):183\u2013199.","journal-title":"Soft Comput"},{"key":"243_CR4","doi-asserted-by":"publisher","unstructured":"Bianconi, G, Pin P, Marsili M (2009) Assessing the relevance of node features for network structure. Proc Natl Acad Sci 106(28):11,433\u201311,438. https:\/\/doi.org\/10.1073\/pnas.0811511106. http:\/\/www.pnas.org\/content\/106\/28\/11433.","DOI":"10.1073\/pnas.0811511106"},{"key":"243_CR5","first-page":"253","volume-title":"International Workshop on Learning Classifier Systems","author":"MV Butz","year":"2000","unstructured":"Butz, MV, Wilson SW (2000) An algorithmic description of XCS In: International Workshop on Learning Classifier Systems, 253\u2013272. Springer, Berlin."},{"key":"243_CR6","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/3-540-44640-0_15","volume-title":"P. Luca Lanzi, W. Stolzmann, S.W. Wilson (eds.) Advances in Learning Classifier Systems","author":"MV Butz","year":"2001","unstructured":"Butz, MV, Wilson SW (2001) An Algorithmic Description of XCS In: P. Luca Lanzi, W. Stolzmann, S.W. Wilson (eds.) Advances in Learning Classifier Systems, 253\u2013272. Springer Berlin Heidelberg, Berlin."},{"issue":"7","key":"243_CR7","doi-asserted-by":"publisher","first-page":"1659","DOI":"10.1016\/j.automatica.2009.03.006","volume":"45","author":"D Cheng","year":"2009","unstructured":"Cheng, D, Qi H (2009) Controllability and observability of Boolean control networks. Automatica 45(7):1659\u20131667.","journal-title":"Automatica"},{"key":"243_CR8","doi-asserted-by":"publisher","first-page":"1942","DOI":"10.1038\/ncomms2939","volume":"4","author":"SP Cornelius","year":"2013","unstructured":"Cornelius, SP, Kath WL, Motter AE (2013) Realistic control of network dynamics. Nat Commun 4:1942.","journal-title":"Nat Commun"},{"issue":"1-2","key":"243_CR9","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1023\/A:1023909812213","volume":"52","author":"A Datta","year":"2003","unstructured":"Datta, A, Choudhary A, Bittner ML, Dougherty ER (2003) External Control in Markovian Genetic Regulatory Networks. Mach Learn 52(1-2):169\u2013191. https:\/\/doi.org\/10.1023\/A:1023909812213.","journal-title":"Mach Learn"},{"key":"243_CR10","unstructured":"Dutot, A, Guinand F, Olivier D, Pign\u00e9 Y (2007) Graphstream: A tool for bridging the gap between complex systems and dynamic graphs In: Emergent Properties in Natural and Artificial Complex Systems. 4th European Conference on Complex Systems (ECCS\u20192007), 63\u201374, Dresden."},{"issue":"5","key":"243_CR11","doi-asserted-by":"publisher","first-page":"1258","DOI":"10.1109\/TAC.2013.2294821","volume":"59","author":"E Fornasini","year":"2014","unstructured":"Fornasini, E, Valcher ME (2014) Optimal control of Boolean Control Networks. IEEE Trans Autom Control 59(5):1258\u20131270. https:\/\/doi.org\/10.1109\/TAC.2013.2294821.","journal-title":"IEEE Trans Autom Control"},{"issue":"1","key":"243_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1080\/23307706.2015.1098577","volume":"3","author":"E Fornasini","year":"2016","unstructured":"Fornasini, E, Valcher ME (2016) Recent developments in Boolean networks control. J Control Decis 3(1):1\u201318.","journal-title":"J Control Decis"},{"issue":"11","key":"243_CR13","doi-asserted-by":"publisher","first-page":"1203","DOI":"10.1002\/1097-024X(200009)30:11<1203::AID-SPE338>3.0.CO;2-N","volume":"30","author":"ER Gansner","year":"2000","unstructured":"Gansner, ER, North SC (2000) An open graph visualization system and its applications to software engineering. Softw Pract Experience 30(11):1203\u20131233.","journal-title":"Softw Pract Experience"},{"key":"243_CR14","doi-asserted-by":"crossref","unstructured":"Gates, AJ, Rocha LM, Control of complex networks requires both structure and dynamics (2016). Sci Rep 6:24,456.","DOI":"10.1038\/srep24456"},{"key":"243_CR15","doi-asserted-by":"publisher","unstructured":"Haghighi, R, Namazi H (2015) Algorithm for identifying minimum driver nodes based on structural controllability. Math Probl Eng 2015:1\u20139. https:\/\/doi.org\/10.1155\/2015\/192307.","DOI":"10.1155\/2015\/192307"},{"issue":"1","key":"243_CR16","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1007\/s41109-018-0088-x","volume":"3","author":"MR Karlsen","year":"2018","unstructured":"Karlsen, MR, Moschoyiannis S (2018a) Evolution of control with learning classifier systems. Appl Netw Sci 3(1):30. https:\/\/doi.org\/10.1007\/s41109-018-0088-x. Google Scholar.","journal-title":"Appl Netw Sci"},{"key":"243_CR17","doi-asserted-by":"publisher","unstructured":"Karlsen, MR, Moschoyiannis S (2018b) Learning condition-action rules for personalised journey recommendations In: RuleML and RR 2018, RuleML+RR 2018. Lecture Notes in Computer Science, vol. 11092. Springer, Cham. https:\/\/doi.org\/10.1007\/978-3-319-99906-7_21.","DOI":"10.1007\/978-3-319-99906-7_21"},{"key":"243_CR18","doi-asserted-by":"publisher","unstructured":"Karlsen, MR, Moschoyiannis SK (2018c) Optimal control rules for random boolean networks In: 7th International Conference on Complex Networks and their Applications, Studies in Computational Intelligence, 828\u2013840. Springer, Cham. https:\/\/doi.org\/10.1007\/978-3-030-05411-3_66. Google Scholar.","DOI":"10.1007\/978-3-030-05411-3_66"},{"key":"243_CR19","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780195079517.001.0001","volume-title":"The Origins of Order","author":"S Kauffman","year":"1993","unstructured":"Kauffman, S (1993) The Origins of Order. Oxford University Press, New York."},{"issue":"3","key":"243_CR20","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1016\/0022-5193(69)90015-0","volume":"22","author":"SA Kauffman","year":"1969","unstructured":"Kauffman, SA (1969) Metabolic stability and epigenesis in randomly constructed genetic nets. J Theor Biol 22(3):437\u2013467.","journal-title":"J Theor Biol"},{"key":"243_CR21","doi-asserted-by":"publisher","first-page":"2223","DOI":"10.1038\/srep02223","volume":"3","author":"J Kim","year":"2013","unstructured":"Kim, J, Park SM, Cho KH (2013) Discovery of a kernel for controlling biomolecular regulatory networks. Sci Rep 3:2223. https:\/\/doi.org\/10.1038\/srep02223.","journal-title":"Sci Rep"},{"key":"243_CR22","doi-asserted-by":"crossref","unstructured":"Kobayashi, K, Hiraishi K2012. A petri net-based approach to control of Boolean networks. IEEE, New York.","DOI":"10.1109\/ICNC.2012.76"},{"key":"243_CR23","doi-asserted-by":"publisher","first-page":"42551","DOI":"10.1109\/ACCESS.2018.2847765","volume":"6","author":"D Kosmanos","year":"2018","unstructured":"Kosmanos, D, Maglaras L, Mavrovouniotis M, Moschoyiannis S, Argyriou A, Janicke H (2018) Route optimization of electric vehicles based on dynamic wireless charging. IEEE Access 6:42551\u201342565.","journal-title":"IEEE Access"},{"key":"243_CR24","doi-asserted-by":"crossref","unstructured":"Kovacs, T (1998) XCS classifier system reliably evolves accurate, complete, and minimal representations for Boolean functions. Soft Comput Eng Des Manuf:59\u201368.","DOI":"10.1007\/978-1-4471-0427-8_7"},{"key":"243_CR25","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/B978-155860734-7\/50092-5","volume-title":"Foundations of Genetic Algorithms 6","author":"T Kovacs","year":"2001","unstructured":"Kovacs, T (2001) Towards a theory of strong overgeneral classifiers In: Foundations of Genetic Algorithms 6, 165\u2013184. Elsevier, London."},{"key":"243_CR26","first-page":"85","volume-title":"IEEE Digital Ecosystems and Technologies (IEEE DEST)","author":"P Krause","year":"2009","unstructured":"Krause, P, Razavi A, Moschoyiannis S, Marinos A (2009) Stability and complexity in digital ecosystems In: IEEE Digital Ecosystems and Technologies (IEEE DEST), 85\u201390. IEEE, New York."},{"key":"243_CR27","doi-asserted-by":"publisher","unstructured":"Li, R, Yang M, Chu T (2015) Controllability and observability of Boolean networks arising from biology In: Chaos: An Interdisciplinary Journal of Nonlinear Science, vol. 25, 023,104. AIP Publishing. https:\/\/doi.org\/10.1063\/1.4907708.","DOI":"10.1063\/1.4907708"},{"issue":"7346","key":"243_CR28","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1038\/nature10011","volume":"473","author":"YY Liu","year":"2011","unstructured":"Liu, YY, Slotine JJ, Barab\u00e1si AL (2011) Controllability of complex networks. Nature 473(7346):167.","journal-title":"Nature"},{"issue":"9","key":"243_CR29","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1209\/epl\/i1997-00196-9","volume":"37","author":"B Luque","year":"1997","unstructured":"Luque, B, Sol\u00e9 RV (1997) Controlling chaos in random Boolean networks. Europhysics Lett (EPL) 37(9):597\u2013602. https:\/\/doi.org\/10.1209\/epl\/i1997-00196-9.","journal-title":"Europhysics Lett (EPL)"},{"issue":"3","key":"243_CR30","doi-asserted-by":"publisher","first-page":"e55,946","DOI":"10.1371\/journal.pone.0055946","volume":"8","author":"M Marques-Pita","year":"2013","unstructured":"Marques-Pita, M, Rocha LM (2013) Canalization and control in automata networks: body segmentation in drosophila melanogaster. PloS One 8(3):e55,946.","journal-title":"PloS One"},{"key":"243_CR31","doi-asserted-by":"publisher","unstructured":"Moschoyiannis, S, Elia N, Penn A, Lloyd DJB, Knight C (2016) A web-based tool for identifying strategic intervention points in complex systems. Electronic Proceedings in Theoretical Computer Science 220:39\u201352. Open Publishing Association. https:\/\/doi.org\/10.4204\/eptcs.220.4.","DOI":"10.4204\/eptcs.220.4"},{"key":"243_CR32","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1145\/3233547.3233550","volume-title":"Proceedings of the 2018 ACM International Conference on Bioinformatics, Computational Biology, and Health Informatics","author":"S Paul","year":"2018","unstructured":"Paul, S, Su C, Pang J, Mizera A (2018) A decomposition-based approach towards the control of Boolean networks In: Proceedings of the 2018 ACM International Conference on Bioinformatics, Computational Biology, and Health Informatics, 11\u201320. ACM, New York."},{"key":"243_CR33","doi-asserted-by":"publisher","unstructured":"Razavi, AR, Marinos A, Moschoyiannis S, Krause P (2009) RESTful transactions supported by the isolation theorems In: International Conference on Web Engineering (ICWE), LNCS, vol. 5648, 394\u2013409. Springer, Berlin. https:\/\/doi.org\/10.1007\/978-3-642-02818-2_32. Google Scholar.","DOI":"10.1007\/978-3-642-02818-2_32"},{"key":"243_CR34","first-page":"361","volume-title":"6th Conf. on Complex Networks and Applications","author":"S Savvopoulos","year":"2017","unstructured":"Savvopoulos, S, Moschoyiannis S (2017) Impact of removing nodes on the controllability of complex networks In: 6th Conf. on Complex Networks and Applications, 361\u2013363. Springer, Berlin."},{"key":"243_CR35","volume-title":"Conference in Complex Systems (CCS 2017), 17-22 September 2017","author":"S Savvopoulos","year":"2017","unstructured":"Savvopoulos, S, Penn AS, Moschoyiannis S (2017) On the interplay between topology and controllability of complex networks In: Conference in Complex Systems (CCS 2017), 17-22 September 2017. Cancun, Mexico."},{"issue":"2","key":"243_CR36","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1080\/17477778.2017.1387335","volume":"12","author":"L Schoenenberger","year":"2018","unstructured":"Schoenenberger, L, Tanase R (2018) Controlling complex policy problems: A multimethodological approach using system dynamics and network controllability. J Simulation 12(2):162\u2013170. https:\/\/doi.org\/10.1080\/17477778.2017.1387335.","journal-title":"J Simulation"},{"issue":"3","key":"243_CR37","doi-asserted-by":"publisher","first-page":"036,401","DOI":"10.1088\/1674-1056\/20\/3\/036401","volume":"20","author":"C Shi-Jian","year":"2011","unstructured":"Shi-Jian, C, Yi-Guang H (2011) Control of random Boolean networks via average sensitivity of Boolean functions. Chin Phys B 20(3):036,401.","journal-title":"Chin Phys B"},{"issue":"04","key":"243_CR38","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1142\/S0218339002000706","volume":"10","author":"I Shmulevich","year":"2002","unstructured":"Shmulevich, I, Dougherty ER, Zhang W (2002) Control of stationary behavior in probabilistic Boolean networks by means of structural intervention. J Biol Syst 10(04):431\u2013445.","journal-title":"J Biol Syst"},{"key":"243_CR39","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/j.jocs.2018.04.012","volume":"26","author":"NS Taou","year":"2018","unstructured":"Taou, NS, Corne DW, Lones MA (2018) Investigating the use of Boolean networks for the control of gene regulatory networks. J Comput Sci 26:147\u2013156.","journal-title":"J Comput Sci"},{"issue":"1","key":"243_CR40","first-page":"1","volume":"2009","author":"RJ Urbanowicz","year":"2009","unstructured":"Urbanowicz, RJ, Moore JH (2009) Learning classifier systems: a complete introduction, review, and roadmap. J Artif Evol Appl 2009(1):1\u201325.","journal-title":"J Artif Evol Appl"},{"issue":"23","key":"243_CR41","doi-asserted-by":"publisher","first-page":"10,478","DOI":"10.1073\/pnas.0914180107","volume":"107","author":"G Wang","year":"2010","unstructured":"Wang, G, Du C, Chen H, Simha R, Rong Y, Xiao Y, Zeng C (2010) Process-based network decomposition reveals backbone motif structure. Proc Natl Acad Sci 107(23):10,478\u201310,483.","journal-title":"Proc Natl Acad Sci"},{"issue":"2","key":"243_CR42","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1162\/evco.1995.3.2.149","volume":"3","author":"SW Wilson","year":"1995","unstructured":"Wilson, SW (1995) Classifier fitness based on accuracy. Evol Comput 3(2):149\u2013175.","journal-title":"Evol Comput"},{"key":"243_CR43","volume-title":"Genetic Programming 1998: Proceedings of the Third Annual Conference","author":"SW Wilson","year":"1998","unstructured":"Wilson, SW (1998) Generalization in the XCS classifier system. In: Koza J, Banzhaf W, Chellapilla K, Deb K, Dorigo M, Fogel D, Garzon M, Goldberg D, Iba H, Riolo R (eds)Genetic Programming 1998: Proceedings of the Third Annual Conference. Morgan Kaufmann, San Francisco."},{"key":"243_CR44","first-page":"197","volume-title":"International Workshop on Learning Classifier Systems","author":"SW Wilson","year":"2001","unstructured":"Wilson, SW (2001) Compact rulesets from XCSI In: International Workshop on Learning Classifier Systems, 197\u2013208. Springer, Berlin."},{"issue":"28","key":"243_CR45","doi-asserted-by":"publisher","first-page":"7234","DOI":"10.1073\/pnas.1617387114","volume":"114","author":"JGT Za\u00f1udo","year":"2017","unstructured":"Za\u00f1udo, JGT, Yang G, Albert R (2017) Structure-based control of complex networks with nonlinear dynamics. Proc Natl Acad Sci 114(28):7234\u20137239. https:\/\/doi.org\/10.1073\/pnas.1617387114.","journal-title":"Proc Natl Acad Sci"}],"container-title":["Applied Network Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-019-0243-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s41109-019-0243-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-019-0243-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,29]],"date-time":"2024-07-29T10:06:24Z","timestamp":1722247584000},"score":1,"resource":{"primary":{"URL":"https:\/\/appliednetsci.springeropen.com\/articles\/10.1007\/s41109-019-0243-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12]]},"references-count":45,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,12]]}},"alternative-id":["243"],"URL":"https:\/\/doi.org\/10.1007\/s41109-019-0243-z","relation":{},"ISSN":["2364-8228"],"issn-type":[{"value":"2364-8228","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,12]]},"assertion":[{"value":"20 March 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 December 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 December 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare that they have no competing interests.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"129"}}