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

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

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

Popis výsledku anglicky

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.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2014

Kód důvěrnosti údajů

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

Název periodika

Theoretical Computer Science

ISSN

0304-3975

e-ISSN

—

Svazek periodika

545

Číslo periodika v rámci svazku

AUG

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

18

Strana od-do

76-93

Kód UT WoS článku

000340337500006

EID výsledku v databázi Scopus

—