Creuament (algorisme genètic)
Parlant d'algorismes genètics, el creuament és un operador genètic utilitzat per variar la programació d'un cromosoma o cromosomes d'una generació a la següent. És anàleg a la reproducció biològica, en la que els algorismes genètics es basen.
Tècniques de creuament modifica
Existeixen moltes tècniques de creuament per a organismes que utilitzen diferents estructures per emmagatzemar les dades.
Creuament en un punt modifica
Se selecciona un punt en el vector del pare de l'organisme. Totes les dades més enllà d'aquest punt en el vector de l'organisme s'intercanvia entre els dos organismes pares. Els organismes resultants són els fills:
Creuament en dos punts modifica
El creuament en dos punts requereix seleccionar dos punts en els vectors dels organismes pare. Totes les dades entre els dos punts s'intercanvien entre els organismes pares, creant dos organismes fills:
Tallar i empalmar modifica
Un altre variant de creuament, l'enfocament "tallar i empalmar", ocasiona un canvi de la llargada dels vectors dels fills. la raó per a aquesta diferència és que se selecciona un punt de tall diferent per a cada vector del pare:
Creuament uniforme i uniforme mitjà modifica
En tots dos d'aquests esquemes els dos pares es combinen per produir els descendents.
A l'esquema de creuament uniforme (UX per l'anglès Uniform Crossover) els bits del vector es comparen individualment entre ambdós pares. Els bits s'intercanvien amb una probabilitat fixada, usualment 0.5.
A l'esquema de creuament uniforme mig (HUX de l'anglès Half Uniform Crossover), exactament la meitat dels bits que són diferents s'intercanvien. Per això és necessari calcular la distància de Hamming (nombre de bits diferents). Aquest nombre es divideix entre dos. El nombre resultant és la quantitat de bits diferents que ha de ser intercanviada entre els pares.
Creuament de cromosomes ordenats modifica
Depenent de com representa la solució el cromosoma, un canvi directe pot no ser possible.
Un cas és quan el cromosoma és una llista ordenada, com la llista ordenada de les ciutats viatjades per al problema del viatjant. Un punt de creuament se selecciona en els pares. Ja que el cromosoma és una llista ordenada, un canvi directe introduiria duplicats i treu candidats necessaris de la llista. En canvi, el cromosoma fins al punt de creuament es reté per a cada pare. La informació després del punt de creuament s'ordena com està ordenada en l'altre pare. Per exemple, si els nostres dos pares són ABCDEFGHI i IGAHFDBEC i el nostre punt de creuament està després del quart caràcter, llavors els nens que resulten serien ABCDIGHFE i IGAHBCDEF.
Tendències del Creuament modifica
Per a operadors de creuament que intercanvien seccions contigües dels cromosomes (p. ex. k-point) l'ordenació de les variables es pot tornar important. Això és especialment veritat quan les bones solucions contenen blocs de construcció que podrien ser interrompudes per un operador de creuament no respectuós.