Exact computation of the expectation surfaces for uniform crossover along with bit-flip mutation

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989100%3A27240%2F14%3A86093020" target="_blank" >RIV/61989100:27240/14:86093020 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1016/j.tcs.2014.01.002" target="_blank" >http://dx.doi.org/10.1016/j.tcs.2014.01.002</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.tcs.2014.01.002" target="_blank" >10.1016/j.tcs.2014.01.002</a>

Result language
angličtina
Original language name
Exact computation of the expectation surfaces for uniform crossover along with bit-flip mutation
Original language description
Uniform crossover and bit-flip mutation are two popular operators used in genetic algorithms to generate new solutions in an iteration of the algorithm when the solutions are represented by binary strings. We use the Walsh decomposition of pseudo-Booleanfunctions and properties of Krawtchouk matrices to exactly compute the expected value for the fitness of a child generated by uniform crossover followed by bit-flip mutation from two parent solutions. We prove that this expectation is a polynomial in ?,the probability of selecting the best-parent bit in the crossover, and ?, the probability of flipping a bit in the mutation. We provide efficient algorithms to compute this polynomial for Onemax and MAX-SAT problems, but the results also hold for otherproblems such as NK-Landscapes. We also analyze the features of the expectation surfaces. 2014 Elsevier B.V.
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
IN - Informatics
OECD FORD branch
—

Publication year
2014
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)