V. Operadores del AG

Panorama general

Como puede verse en el esquema del algoritmo genetico, el cruce y la mutacion estan entre las partes mas importantes de un algoritmo genetico. Su rendimiento esta influido principalmente por estos dos operadores. Antes de explicar el cruce y la mutacion con mas detalle, conviene decir algunas cosas sobre los cromosomas.


Codificacion de un cromosoma

De alguna manera, un cromosoma debe contener informacion sobre la solucion que representa. La codificacion que se usa con mayor frecuencia es una cadena binaria. Un cromosoma podria verse asi:

Cromosoma 1 1101100100110110
Cromosoma 2 1101111000011110

Cada cromosoma tiene una cadena binaria. Cada bit de esa cadena puede representar alguna caracteristica de la solucion. O toda la cadena puede representar un numero; eso es lo que se uso en el demostracion basica del AG.

Por supuesto, hay muchas otras formas de codificacion. Esto depende principalmente del problema que se este resolviendo. Por ejemplo, se pueden codificar numeros enteros o reales; a veces tambien es util codificar algunas permutaciones, etcetera.

Cruce

Despues de decidir que codificacion usar, podemos pasar al cruce. El cruce selecciona genes de los cromosomas progenitores y crea nueva descendencia. La forma mas sencilla de hacerlo es elegir un punto de cruce aleatorio, copiar todo lo que esta antes de ese punto del primer progenitor y luego copiar todo lo que esta despues de ese punto del segundo progenitor.

El cruce puede verse asi (| es el punto de cruce):

Cromosoma 1 11011 | 00100110110
Cromosoma 2 11011 | 11000011110
Descendencia 1 11011 | 11000011110
Descendencia 2 11011 | 00100110110

Hay otras maneras de realizar el cruce. Por ejemplo, podemos elegir mas de un punto de cruce. El cruce puede llegar a ser bastante complicado, y depende mucho de la codificacion del cromosoma. Un metodo de cruce disenado para un problema especifico puede mejorar el rendimiento del algoritmo genetico.

Mutacion

Despues de realizar el cruce, ocurre la mutacion. Su objetivo es evitar que toda la poblacion caiga en un optimo local del problema que se esta resolviendo. La mutacion cambia aleatoriamente la nueva descendencia. Para la codificacion binaria, podemos cambiar unos pocos bits elegidos al azar de 1 a 0 o de 0 a 1. La mutacion puede verse asi:

Descendencia original 1 1101111000011110
Descendencia original 2 1101100100110110
Descendencia mutada 1 1100111000011110
Descendencia mutada 2 1101101100110100

Al igual que el cruce, la mutacion depende de la codificacion. Por ejemplo, cuando estamos codificando permutaciones, la mutacion podria significar intercambiar dos genes.

·