{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,25]],"date-time":"2026-04-25T16:48:18Z","timestamp":1777135698416,"version":"3.51.4"},"reference-count":26,"publisher":"MIT Press","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Evolutionary Computation"],"published-print":{"date-parts":[[2015,6]]},"abstract":"<jats:p>Bit-flip mutation is a common mutation operator for evolutionary algorithms applied to optimize functions over binary strings. In this paper, we develop results from the theory of landscapes and Krawtchouk polynomials to exactly compute the probability distribution of fitness values of a binary string undergoing uniform bit-flip mutation. We prove that this probability distribution can be expressed as a polynomial in p, the probability of flipping each bit. We analyze these polynomials and provide closed-form expressions for an easy linear problem (Onemax), and an NP-hard problem, MAX-SAT. We also discuss a connection of the results with runtime analysis.<\/jats:p>","DOI":"10.1162\/evco_a_00130","type":"journal-article","created":{"date-parts":[[2014,6,2]],"date-time":"2014-06-02T13:15:41Z","timestamp":1401714941000},"page":"217-248","source":"Crossref","is-referenced-by-count":43,"title":["Fitness Probability Distribution of Bit-Flip Mutation"],"prefix":"10.1162","volume":"23","author":[{"given":"Francisco","family":"Chicano","sequence":"first","affiliation":[{"name":"Departamento de Lenguajes y Ciencias de la Computaci\u00f3n, Universidad de M\u00e1laga, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrew M.","family":"Sutton","sequence":"additional","affiliation":[{"name":"Fakult\u00e4t f\u00fcr Mathematik und Informatik, Friedrich-Schiller-Universit\u00e4t Jena, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"L. Darrell","family":"Whitley","sequence":"additional","affiliation":[{"name":"Department of Computer Science Colorado State University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Enrique","family":"Alba","sequence":"additional","affiliation":[{"name":"Departamento de Lenguajes y Ciencias de la Computaci\u00f3n, Universidad de M\u00e1laga, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"281","reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73510-6"},{"key":"B2","doi-asserted-by":"publisher","DOI":"10.1145\/2001576.2001849"},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1145\/2330163.2330344"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1162\/EVCO_a_00039"},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1145\/2463372.2463569"},{"key":"B7","doi-asserted-by":"publisher","DOI":"10.1007\/0-387-23394-6_5"},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1162\/evco.1999.7.2.173"},{"key":"B9","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(92)90049-9"},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(02)00381-8"},{"key":"B11","volume-title":"Finite Markov processes and their applications","author":"Iosifescu M","year":"1980"},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1162\/106365605774666921"},{"key":"B13","volume-title":"An introduction to linear algebra","author":"Mirsky L","year":"1955"},{"key":"B14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16544-3"},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144501395952"},{"key":"B16","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0103571"},{"key":"B17","first-page":"90","volume-title":"Proceedings of the 3rd Annual Symposium on Combinatorial Search","author":"Sutton A. M.","year":"2010"},{"key":"B18","doi-asserted-by":"publisher","DOI":"10.1145\/1967654.1967663"},{"key":"B19","doi-asserted-by":"publisher","DOI":"10.1145\/2001576.2001709"},{"key":"B20","doi-asserted-by":"publisher","DOI":"10.1145\/1569901.1569952"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.02.006"},{"key":"B22","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511626265"},{"key":"B23","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/6229.001.0001","volume-title":"The simple genetic algorithm: Foundations and theory","author":"Vose M. D","year":"1999"},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.2307\/2387224"},{"key":"B25","doi-asserted-by":"publisher","DOI":"10.1145\/1389095.1389208"},{"key":"B26","doi-asserted-by":"publisher","DOI":"10.1145\/1569901.1569954"},{"key":"B27","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548312000600"}],"container-title":["Evolutionary Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/EVCO_a_00130","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,13]],"date-time":"2023-07-13T21:29:05Z","timestamp":1689283745000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/evco\/article\/23\/2\/217-248\/992"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,6]]}},"alternative-id":["10.1162\/EVCO_a_00130"],"URL":"https:\/\/doi.org\/10.1162\/evco_a_00130","relation":{},"ISSN":["1063-6560","1530-9304"],"issn-type":[{"value":"1063-6560","type":"print"},{"value":"1530-9304","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,6]]}}}