Creuament (algorisme genètic)

De Viquipèdia
Dreceres ràpides: navegació, cerca

Parlant d'algorismes genètics, el creuament es 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 | modifica el codi]

Existeixen moltes tècniques de creuament per a organismes que utilitzen diferents estructures per emmagatzemar les dades.

Creuament en un punt[modifica | modifica el codi]

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

Creuament en dos punts[modifica | modifica el codi]

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:

Creuament en dos punts

Tallar i empalmar[modifica | modifica el codi]

Un altre variant de creuament, el 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:

Tallar i empalmar

Creuament uniforme i uniforme mig[modifica | modifica el codi]

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.

Creuament uniforme

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

Creuament de cromosomes ordenats[modifica | modifica el codi]

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 | modifica el codi]

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.

Vegeu també[modifica | modifica el codi]