Algoritmo Genetico

UNIVERSIDAD TECNICA DE MACHALA
FACULTAD DE INGENIERIA CIVIL
ESCUELA DE INFORMATICA
CARRERA DE INGENIERIA DE SISTEMAS
MODULO DE INTELIGENCIA ARTIFICIAL

Operadores Genéticos
Para el paso de una generación a la siguiente se aplican una serie de operadores genéticos. Los más empleados son los operadores de selección, cruce, copia y mutaci´on. En el caso de no trabajar con una poblaciónintermedia temporal también cobran relevancia los algoritmos de remplazo.
A continuación se verán en mayor detalle.
6.1. Selección
Los algoritmos de selección serán los encargados de escoger que individuos
Van a disponer de oportunidades de reproducirse y cuales no.
Puesto que se trata de imitar lo que ocurre en la naturaleza, se ha de otorgar
Un mayor numero de oportunidades de reproducción a losindividuos más
Aptos. Por lo tanto la selección de un individuo estar ‘a relacionada con su valor
de ajuste. No se debe sin embargo eliminar por completo las opciones de reproducción de los individuos menos aptos, pues en pocas generaciones la población se volvería homogénea.
Una opción bastante común consiste en seleccionar el primero de los individuos participantes en el cruce mediantealguno de los métodos expuestos a continuación y el segundo de manera aleatoria.

Selección por ruleta
Propuesto por DeJong, es posiblemente el método más utilizado desde los
orígenes de los Algoritmos Genéticos [Blickle and Thiele, 1995].
A cada uno de los individuos de la población se le asigna una parte proporcional a su ajuste de una ruleta, de tal forma que la suma de todos los
porcentajessea la unidad. Los mejores individuos recibirán una porción de la
ruleta mayor que la recibida por los peores. Generalmente la población est´a ordenada en base al ajuste por lo que las porciones más grandes se encuentran al inicio de la ruleta. Para seleccionar un individuo basta con generar un numero aleatorio del intervalo [0..1] y devolver el individuo situado en esa posición de la ruleta. Estaposición se suele obtener recorriendo los individuos de la población y acumulando sus proporciones de ruleta hasta que la suma exceda el valor obtenido.

Es un método muy sencillo, pero ineficiente a medida que aumenta el tamaño
de la población (su complejidad es O(n2)). Presenta además el inconveniente de que el peor individuo puede ser seleccionado más de una vez.

En mucha bibliografía sesuele referenciar a este método con el nombre de
Selección de Montecarlo.

Selección por torneo
La idea principal de este método consiste en realizar la selección en base
a comparaciones directas entre individuos. Existen dos versiones de selección
mediante torneo:
* Determinística
* Probabilística
En la versión determinística se selecciona al azar un numero p de individuos(Generalmente se escoge p = 2). De entre los individuos seleccionados se
selecciona el más apto para pasarlo a la siguiente generación.

La versión probabilística únicamente se diferencia en el paso de selección del
ganador del torneo. En vez de escoger siempre el mejor se genera un número
aleatorio del intervalo [0..1], si es mayor que un parámetro p (fijado para todo el
proceso evolutivo) seescoge el individuo más alto y en caso contrario el menos apto. Generalmente p toma valores en el rango 0,5 < p ≤ 1.

Variando el numero de individuos que participan en cada torneo se puede
modificar la presión de selección. Cuando participan muchos individuos en cada torneo, la presión de selección es elevada y los peores individuos apenas tienen oportunidades de reproducción. Un casoparticular es el elitismo global. Se trata de un torneo en el que participan todos los individuos de la población con lo cual la selección se vuelve totalmente determinística. Cuando el tamaño del torneo es reducido, la presión de selección disminuye y los peores individuos tienen m´as oportunidades de ser seleccionados.

Elegir uno u otro método de selección determinar ‘a la estrategia de búsqueda...