{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,3]],"date-time":"2026-10-03T16:54:55Z","timestamp":1791046495044,"version":"4.1.0"},"reference-count":36,"publisher":"MIT Press - Journals","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Evolutionary Computation"],"published-print":{"date-parts":[[2019,6]]},"abstract":"<jats:p> Studying coevolutionary systems in the context of simplified models (i.e., games with pairwise interactions between coevolving solutions modeled as self plays) remains an open challenge since the rich underlying structures associated with pairwise-comparison-based fitness measures are often not taken fully into account. Although cyclic dynamics have been demonstrated in several contexts (such as intransitivity in coevolutionary problems), there is no complete characterization of cycle structures and their effects on coevolutionary search. We develop a new framework to address this issue. At the core of our approach is the directed graph (digraph) representation of coevolutionary problems that fully captures structures in the relations between candidate solutions. Coevolutionary processes are modeled as a specific type of Markov chains\u2014random walks on digraphs. Using this framework, we show that coevolutionary problems admit a qualitative characterization: a coevolutionary problem is either solvable (there is a subset of solutions that dominates the remaining candidate solutions) or not. This has an implication on coevolutionary search. We further develop our framework that provides the means to construct quantitative tools for analysis of coevolutionary processes and demonstrate their applications through case studies. We show that coevolution of solvable problems corresponds to an absorbing Markov chain for which we can compute the expected hitting time of the absorbing class. Otherwise, coevolution will cycle indefinitely and the quantity of interest will be the limiting invariant distribution of the Markov chain. We also provide an index for characterizing complexity in coevolutionary problems and show how they can be generated in a controlled manner. <\/jats:p>","DOI":"10.1162\/evco_a_00218","type":"journal-article","created":{"date-parts":[[2017,11,20]],"date-time":"2017-11-20T18:34:25Z","timestamp":1511202865000},"page":"195-228","source":"Crossref","is-referenced-by-count":6,"title":["A New Framework for Analysis of Coevolutionary Systems\u2014Directed Graph Representation and Random Walks"],"prefix":"10.1162","volume":"27","author":[{"given":"Siang Yew","family":"Chong","sequence":"first","affiliation":[{"name":"School of Computer Science, University of Birmingham, Birmingham B15 2TT, United Kingdom and School of Computer Science, University of Nottingham, Malaysia Campus, Jalan Broga, 43500 Semenyih, Malaysia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peter","family":"Ti\u0148o","sequence":"additional","affiliation":[{"name":"School of Computer Science, University of Birmingham, Birmingham B15 2TT, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jun","family":"He","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Aberystwyth University, Aberystwyth SY23 3DB, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xin","family":"Yao","sequence":"additional","affiliation":[{"name":"School of Computer Science, University of Birmingham, Birmingham B15 2TT, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"281","reference":[{"key":"B1","author":"Bader-Natal A.","year":"2005","journal-title":"Coevolutionary and Coadaptive Systems Workshop: 2005 AAAI Symposium"},{"key":"B2","first-page":"131","volume-title":"Surveys in graph theory, Congressus Numerantium","volume":"115","author":"Bang-Jensen J.","year":"1996"},{"key":"B3","first-page":"167\u2013168","author":"Bang-Jensen J.","year":"1997","journal-title":"Discrete Mathematics"},{"key":"B4","volume-title":"Digraphs theory, algorithms and applications","author":"Bang-Jensen J.","year":"2009"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1109\/CEC.2013.6557681"},{"key":"B6","first-page":"432:2181","author":"Brualdi R. A.","year":"2010","journal-title":"Linear Algebra and Its Applications"},{"key":"B7","doi-asserted-by":"publisher","DOI":"10.1162\/106365604773955148"},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2010.2051673"},{"key":"B9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-49686-8"},{"key":"B10","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1007\/3-540-59496-5_300","volume":"929","author":"Cliff D.","year":"1995","journal-title":"Advances in Artificial Life: Proceedings of the Third European Conference on Artificial Life"},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.1109\/4235.687878"},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1162\/evco.2007.15.1.61"},{"key":"B13","doi-asserted-by":"publisher","DOI":"10.1162\/106365604773955139"},{"key":"B14","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2005.856203"},{"key":"B15","first-page":"378","volume-title":"Proceedings of the Fourth European Conference on Artificial Intelligence","author":"Floreano D.","year":"1997"},{"key":"B16","volume-title":"Introduction to probability","author":"Grinstead C. M.","year":"1997"},{"key":"B17","first-page":"145:59","author":"He J.","year":"2003","journal-title":"Artificial Intelligence"},{"key":"B18","first-page":"37:377","author":"Hemasinha R.","year":"2003","journal-title":"Mathematical and Computer Modelling"},{"key":"B19","first-page":"42:228","author":"Hillis W. D.","year":"1990","journal-title":"Physica D"},{"key":"B20","volume-title":"Finite Markov processes and their applications","author":"Iosifescu M","year":"1980"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1162\/ARTL_a_00208"},{"key":"B22","doi-asserted-by":"publisher","DOI":"10.1002\/mcda.1598"},{"key":"B23","volume-title":"Markov chains and mixing times","author":"Levin D. A.","year":"2009"},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719512"},{"key":"B25","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511626630"},{"key":"B26","first-page":"4:1343","author":"Moon J. W.","year":"1963","journal-title":"Pacific Journal of Mathematics"},{"key":"B27","volume-title":"Topics on tournament","author":"Moon J. W","year":"1968"},{"key":"B28","volume-title":"Markov chains","author":"Norris J. R","year":"1998"},{"key":"B29","first-page":"403","author":"Pirzada S.","year":"2012","journal-title":"An introduction to graph theory"},{"key":"B30","first-page":"24:27","author":"Reid K. B.","year":"1998","journal-title":"Bulletin of the Institute of Combinatorics and Its Applications"},{"key":"B31","doi-asserted-by":"publisher","DOI":"10.1162\/evco.1997.5.1.1"},{"key":"B32","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.85.026114"},{"key":"B33","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2005.856212"},{"key":"B34","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2012.2208755"},{"key":"B35","first-page":"242","volume-title":"Bird of a Feather Workshop: Proceedings of the 2002 Genetic and Evolutionary Computation Conference (GECCO'02)","author":"Stanley K. O.","year":"2002"},{"key":"B36","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2013.2244897"}],"container-title":["Evolutionary Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/evco_a_00218","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,12]],"date-time":"2021-03-12T21:58:59Z","timestamp":1615586339000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/evco\/article\/27\/2\/195-228\/1088"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,6]]}},"alternative-id":["10.1162\/evco_a_00218"],"URL":"https:\/\/doi.org\/10.1162\/evco_a_00218","relation":{},"ISSN":["1063-6560","1530-9304"],"issn-type":[{"value":"1063-6560","type":"print"},{"value":"1530-9304","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,6]]}}}