Computación Evolutiva

2. Objetivo
   general
3. Panorama histórico de la
   computación evolutiva
4. Conceptos básicos. Los
   orígenes
5. Programación
   evolutiva
6. Estrategias evolutivas
   (EE)
7. Algoritmos
   genéticos
8. Clases de algoritmos
   genéticos
9. Elementos de un algoritmo
   genético
10. Operadores
    genéticos.
11. Ciclo general de un algoritmo
    genético estándar
12. Software
13. Conclusión
14. Bibliografía

 INTRODUCCIÓN

En este tema se verá la forma en que los
científicos han tomado a la evolución a través de la selección
natural determinando que miembros de la población sobrevivirán hasta
reproducirse y la reproducción sexual garantizando la mezcla
y combinación de sus genes entre la
descendencia.

En la naturaleza, los
individuos compiten entre sí por recursos tales
como comida, agua refugio.
Adicionalmente, los animales de la
misma especie normalmente antagonizan para obtener una
pareja.

Veremos conceptos básicos de las técnicas
más importantes de computación evolutiva. Luego comenzaremos a
hablar de la computación evolutiva en particular.
Iniciaremos con un recorrido histórico en el que se
resumirán los logros más importantes en torno a la
simulación de los procesos
evolutivos como una herramienta para el aprendizaje y
la optimización.

Posteriormente se analizarán de manera general
los 3 paradigmas
principales que se utilizan hoy en día en la
computación evolutiva: las estrategias
evolutivas, la programación evolutiva y los algoritmos
genéticos. En cada caso se abordará su
inspiración biológica, su motivación, su funcionamiento y algunas de
sus aplicaciones. Finalmente se estudiará el
funcionamiento, fundamentos teóricos,
implementación de los algoritmos genéticos, que es
actualmente el paradigma
evolutivo más utilizado por los investigadores que
trabajan en esta disciplina.

OBJETIVO
GENERAL

Comprender el concepto de la
computación evolutiva, su importancia en el mundo actual
así como su historia, sus conceptos
básicos y sus diferentes aplicaciones.

Computación Evolutiva

La Computación Evolutiva interpreta la naturaleza
como una inmensa máquina de resolver problemas y
trata de encontrar el origen de dicha potencialidad para
utilizarla en nuestros programas.

Definición :Con el término de
Computación Evolutiva se engloba al conjunto de
técnicas que basándose en la simulación de
los procesos naturales y la genética
se utilizan para resolver problemas complejos de búsqueda
y aprendizaje.

Panorama
histórico de la computación
evolutiva

Cannon 1932, visualizó la evolución
natural como un proceso de
aprendizaje. Alan Turing reconoció, en 1950, que
debe haber una conexión obvia entre el aprendizaje de
máquina y la evolución, y señaló que
se podrían desarrollar programas para jugar ajedrez usando
esta técnica.

Campbell conjeturó en 1960 que en todos
los procesos que llevan a la expansión del conocimiento,
se involucra un proceso ciego de variación y supervivencia
selectiva.

Los primeros intentos de aplicar de manera formal la
teoría
de la evolución, apareció en las áreas de
control de
procesos estadísticos, aprendizaje de máquina y
optimización de funciones. Tal
vez el primer intento serio de este tipo se dio en el trabajo que
realizaron Box y sus colegas en 1957, en el desarrollo de
una técnica que denominaron operación evolutiva, la
cual se aplicó a una planta de manufactura
para manejarla.

Friedberg intentó, en 1958, hacer que un
programa en
lenguaje
máquina se mejorara a sí mismo, seleccionando
instrucciones que se asociaran más frecuentemente con un
resultado exitoso.

Barricelli ofreció, en 1954, una de las
primeras simulaciones que usaba principios
evolutivos, utilizando los mismos procedimientos
generales que se usan hoy en día en la disciplina conocida
como vida artificial.

Fogel el que introdujo la primera técnica
evolutiva que realmente funcionó más o menos dentro
de los lineamientos actuales de la computación evolutiva.
Su programación evolutiva consistía en hacer
evolucionar autómatas de estados finitos por medio de
mutaciones artificial.

Rechenberg y Schwefel 1965. desarrollaron una
técnica, llamada estrategia
evolutiva, se utilizó inicialmente para resolver problemas
ingenieriles que desafiaban a los métodos de
optimización tradicionales.

CONCEPTOS BASICOS

LOS ORIGENES

La evolución se produce como resultado de dos
procesos primarios: la selección natural y la
reproducción sexual. La primera determina que miembros de
la población sobrevivirán hasta reproducirse, la
segunda garantiza la mezcla y combinación de sus genes
entre la descendencia. En la fusión del
óvulo y el espermatozoide, los cromosomas
homologados se estiran y adosan uno al otro, y luego se
entrecruzan en zonas intermedias, intercambiando así
material genético. [Holland 92] .

En la naturaleza, los individuos compiten entre
sí por recursos tales como comida, agua refugio.
Adicionalmente, los animales de la misma especie normalmente
antagonizan para obtener una pareja. [Martín
95].

Esta es la teoría de la evolución,
especies naturales que van evolucionando para adaptarse al medio
que las rodea y aquellos individuos que tenga más éxito
en tal adaptación tendrán mejor probabilidad de
sobrevivir hasta la edad adulta y probablemente un número
mayor de descendientes, por lo tanto, mayores probabilidades de
que sus genes sean propagados a los largo de sucesivas
generaciones. La combinación de características de los padres bien
adaptados, en un descendiente, puede producir muchas veces un
nuevo individuo mucho mejor adaptado que cualquiera de sus padres
a las características de su medio
ambiente.
Este proceso no debe verse en ningún momento como un
proceso determinista, sino como un proceso con la fuerte
componente estocástica. Es decir, si un individuo se
adapta al entorno, lo más que se puede afirmar es que ese
individuo tendrá mayor probabilidad de conservar sus genes
en la siguiente generación que sus congéneres. Pero
solo es una probabilidad, no es un hecho absolutamente seguro. Siempre
existirá la posibilidad de que a pesar de estar muy dotado
por alguna razón no consiga reproducirse. Pero en cuanto a
la especie como un conjunto o población, si puede
afirmarse que ira adaptándose al medio. [Martín
95]
La idea surgió en la universidad de
Michigan, Estados Unidos
donde el profesor J. H. Holland quien, consciente de la
importancia de la selección natural introdujo la idea de
los Algoritmos Genéticos en los años sesenta y al
final de esta década desarrollo una técnica que
permitió incorporarla en un programa de computadora.
Su principal objetivo era
lograr que las computadoras
aprendieran por sí mismas. A la técnica inventada
por Holland se le llamo inicialmente Planes Reproductivos pero se
hizo popular bajo el nombre de Algoritmos Genéticos,
A.G.
Obviamente desde aquellos años sesenta hasta ahora, muchas
otras personas han contribuido de modo notable al desarrollo de
estas ideas, abriéndose muchos nuevos frentes de trabajo y
subdividiéndose la idea original en múltiples
disciplinas. [Martín 95] Estas técnicas se usan
principalmente en países desarrollados como Japón
Estados Unidos y en Europa.

En la naturaleza todos los seres vivos se enfrentan a
problemas que deben resolver con éxito, como conseguir
más luz del sol, o
cazar una mosca. La Computación Evolutiva interpreta la
naturaleza como una inmensa máquina de resolver problemas
y trata de encontrar el origen de dicha potencialidad para
utilizarla en nuestros programas.

Los Algoritmos Genéticos son una de las
más conocidas y originales técnicas de
resolución de problemas dentro de lo que se ha definido
como "Computación Evolutiva" (o "Algoritmos Evolutivos"),
término que agrupa a los Algoritmos Genéticos,
las Estrategias Evolutivas y la Programación
Evolutiva. En realidad todas estas técnicas son muy
parecidas y comparten muchos aspectos.

Un Algoritmo
Evolutivo es una técnica de resolución de
problemas inspirada en la evolución de los seres
vivos.

En un Algoritmo Evolutivo se define una estructura de
datos que admita todas las posibles soluciones a
un problema.

Cada uno de los posibles conjuntos de
datos
admitidos por esa estructura
será una solución al problema. Unas soluciones
serán mejores, otras peores.

Solucionar el problema consistirá en encontrar la
solución óptima, y por tanto, los Algoritmos
Evolutivos son en realidad un método de
búsqueda.

Pero un método de búsqueda muy especial,
en el que las soluciones al problema son capaces de reproducirse
entre sí, combinando sus características y
generando nuevas soluciones.

En cada ciclo se seleccionan las soluciones que
más se acercan al objetivo buscado, eliminando el resto de
soluciones. Las soluciones seleccionadas se reproducirán
entre sí, permitiendo de vez en cuando alguna
mutación o modificación al azar durante la
reproducción.

Algoritmo Evolutivo

• Es una técnica de resolución de
  problemas inspirada en la evolución de los seres
  vivos.
• Programas computacionales cuyo fin es imitar el
  proceso de "selección natural" que según la
  teoría de Darwin rige el
  curso de la evolución

Esquema de la computación
evolutiva

• Inteligencia artificial.
• • Enfoque simbólico o
    `top-down'.
  • Enfoque subsimbólico o
    `botton-up'.
  • • Redes neuronales
      artificiales.
    • Computación evolutiva o algoritmos
      evolutivos.
    • • Solidificación o recocido
        simulado (simulated annealing).
      • Algoritmos
        genéticos.
      • Estrategias evolutivas.
      • Clasificadores
        genéticos.
      • Programación
        genética.

Fases de un Algoritmo Evolutivo

• Opciones Generales.
• • Número de entidades.
  • Número de elementos (genes, reglas) por
    cada agente.
• Método de Evaluación: Asignar un
  peso.
• • Desordenar las entidades antes de
    evaluarlas.
  • Diferentes formas de modificación de los
    pesos después de la evaluación. Por
    ejemplo, el peso de una entidad se puede calcular
    independientemente de las demás entidades, o se
    puede modificar posteriormente este valor,
    disminuyendo el peso si existe otra entidad muy parecida,
    analizando para ello un cierto subconjunto de la
    población vecina.
• Método de Selección:
  ¿Quién muere? ¿Quién se
  reproduce?
• • Con o sin reemplazamiento.
  • Método de la ruleta.
  • Método de los torneos.
  • Seleccionar el n% mejor y el m%
    peor.
• Método de Reproducción: Generar
  y mutar nuevos hijos.
• • Los padres pueden tomarse por parejas o en
    grupos
    más numerosos, elegidos al azar o en orden de
    pesos.
  • En el caso de detectar que los progenitores son
    muy parecidos, se puede realizar una acción
    especial, como incrementar la probabilidad de
    mutación.
  • Las entidades pueden comunicar a otras su
    conocimiento, ya sea a toda o a una parte de la
    población, directamente o a través de una
    pizarra, (una especie de tablón de
    anuncios).
  • Método de recombinación de genes:
    se puede tomar genes de uno u otro progenitor al azar, en
    un cierto orden, con uno, dos o más puntos de
    corte, etc.
  • Tasa de mutación variable.
  • Fijar una tasa de mutación diferente
    para cada individuo o incluso para cada gen.
  • Hacer que sea más probable que se
    produzca una mutación en un gen si en su vecino ya
    se ha producido.
  • Sustituir por mutaciones, genes sin utilidad, como reglas incorrectas o
    repetidas.
  • Tipos de mutaciones

Algoritmo

El algoritmo básico de la programación
evolutiva es el siguiente:

• Generar aleatoriamente una población
  inicial.
• Se aplica mutación.
• Se calcula la aptitud de cada hijo y se usa un
  proceso de selección mediante torneo (normalmente
  estocástico) para determinar cuales serán las
  soluciones que se retendrán.

El termino computación evolutiva o
algoritmos evolutivos, realmente engloba

una serie de técnicas inspiradas
biológicamente. En términos generales, para simular
el proceso evolutivo en una computadora se requiere:

• Codificar las estructuras
  que se replicaran.
• Operaciones que afecten a los
  "individuos".
• Una función
  de aptitud.
• Un mecanismo de selección.

Aunque hoy en día es cada vez mas difícil
distinguir las diferencias entre los distintos tipos de
algoritmos evolutivos existentes, suele hablarse de tres
paradigmas principales:

PROGRAMACIÓN
EVOLUTIVA

_Estrategias Evolutivas

_Algoritmos Genéticos.

Programas Evolutivos (PE)

Son una estrategia de optimización
estocástica similar a los Ags, pero hacen un
énfasis específico en los operadores
genéticos tal y como se observan en la naturaleza y en la
estructura de datos que utilizan adaptada al problema. Por esto,
a diferencia de los AGs, los PEs no son restrictivos en cuanto a
la representación del problema. Mientras en los AGs se
hace necesario una codificación de las soluciones del
problema; en los PEs, tal representación se hace de forma
directa.

Historia

Los programas evolutivos fueron presentados en 1994 por
Michalewicz, cuando propuso incorporar conocimiento
específico del problema a resolver en las estructuras de
datos. Así, los PEs son métodos que incorporan
directamente conocimiento específico a los AGs, puesto que
permiten la utilización de estructuras de datos naturales.
Esto permite, a su vez, la utilización de operadores
genéticos sensibles al contexto, con el fin de mejorar la
eficiencia del
algoritmo de búsqueda sin perder gran parte de la propiedad de
generalización. Además, de perder un poco de
generalización, con la incorporación de
conocimiento específico, también se pierde el
paralelismo implícito (basado en alfabetos de
símbolos mínimos). Sin embargo, esta pérdida
se compensa con el procesamiento de información mas útil.

 Veamos el ejemplo del funcionamiento de la
programación evolutiva que se indica en la figura 3.2. La
tabla de transiciones de este autómata es la
siguiente:

 En este autómata pueden ahora aplicarse
cinco diferentes tipos de mutaciones:

cambiar un símbolo de salida, cambiar una
transición, agregar un estado, borrar
un estado y cambiar el estado
inicial. El objetivo es hacer que el autómata reconozca un
cierto conjunto de entradas (o sea, una cierta expresión
regular) sin equivocarse ni una sola vez.

Aplicaciones

Predicción

Generalización

Juegos

Control automático

Problema del viajero

Planeación de rutas

Diseño y entrenamiento de
redes
neuronales

Reconocimiento de patrones.

ESTRATEGIAS
EVOLUTIVAS (EE)

Esta técnica esta básicamente enfocada
hacia la optimización paramétrica. En esencia son
métodos estocásticos con paso adaptativo, que
permiten resolver problemas de optimización
paramétrica. A este método se le han agregado
procedimientos propios de la computación evolutiva, que lo
han convertido en un paradigma más de dicha metodología. Con tal mezcla, las EEs pueden
definirse como algoritmos evolutivos enfocados hacia la
optimización paramétrica, teniendo como
características principales que utilizan una
representación a través de vectores reales,
una selección determinística y operadores
genéticos específicos de cruce y mutación.
Además, su objetivo fundamental consiste en encontrar el
valor real de un vector de N dimensiones.

Las EEs pueden dividirse en dos tipos: Estrategias
Evolutivas Simples y Estrategias Evolutivas
Múltiples.

• EEs Simples

Son consideradas como procedimientos estocásticos
de optimización paramétrica con paso adaptativo,
esta característica las hace similares al temple simulado.
En este caso, se hace evolucionar un solo individuo usando
únicamente a la mutación como operador
genético. Son relativamente sencillas, y se denominan
también EEs de dos miembros. Debido a que evoluciona un
solo individuo a la vez, no son consideradas estrictamente como
métodos evolutivos. A pesar de ser muy sencillas, son de
gran utilidad práctica y han sido utilizadas, con algunas
mejoras, para resolver problemas reales en diversas
áreas.

• EEs Múltiples:

Surgen como respuesta a las debilidades de las EEs
simples, las cuales tienden a converger hacia subóptimos.
En las EEs múltiples existen múltiples individuos
(población), y se producen en cada generación
varios nuevos individuos, usando tanto mutación como cruce
(también puede usarse cualquier otro operador). Se usa
normalmente e cruce promedio, el cual genera un único
descendiente de dos padres, promediando los valores de
estos. En cuanto a los criterios de reemplazo, siempre se usa un
esquema determinístico pudiéndose utilizar una
estrategia de inserción o de inclusión.

Algunas aplicaciones de las estrategias evolutivas
son

Problemas de ruteo y redes

Bioquímica

Óptica

Diseño en ingeniería

Magnetismo

ALGORITMOS
GENÉTICOS

Los organismos vivos poseen destreza consumada en la
resolución de problemas y se manifiesta una versatilidad
capaz de avergonzar a los problemas más refinados. Una
definición bastante completa de un Algoritmo
Genético es la propuesta por Jhon Kosa [Coello 95]: Es un
Algoritmo matemático altamente paralelo que transforma un
conjunto de objetos matemáticos con respecto al tiempo usando
operaciones
modeladas de acuerdo al principio Darwiniano de
reproducción y supervivencia del mas apto, y tras haberse
presentado de forma natural una serie de operaciones
genéticas de entre las que destaca la recombinación
sexual. Cada uno de estos objetos matemáticos suele ser
una cadena de caracteres (letras o números) de longitud
fija que se ajusta al modelo de las
cadenas de cromosomas, y se asocian con una cierta función
matemática
que refleja su aptitud. Los Algoritmos Genéticos utilizan
una analogía directa del fenómeno de
evolución en la naturaleza. Trabajan con una
población de individuos, cada uno representado una posible
solución a un problema dado. A cada individuo se le asigna
una puntuación de adaptación, dependiendo de que
tan buena fue la respuesta al problema. A los más
adaptados se les da la oportunidad de reproducirse mediante
cruzamientos con otros individuos de la población,
produciendo descendientes con características de ambos
padres. Los miembros menos adaptados poseen pocas probabilidades
de que sean seleccionados para la reproducción, y
desaparecen. El evaluar esta adaptación no es sencillo de
hacer, pues el entorno esta modificándose constantemente
por lo que nunca se llegara al súper individuo perfecto,
sino que la naturaleza tendera a optimizar los individuos de cada
especie en las circunstancias actuales. Existen varios tipos de
Algoritmos Genéticos, cada uno basado en una
metáfora distinta de la naturaleza.

Los algoritmos genéticos parten de una
población inicial donde cada individuo se representa con
un código
genético (típicamente una secuencia de bits) en la
que se encuentra codificada su información. Sobre esta
población se realiza una serie de operaciones, en primer
lugar se seleccionan parejas de soluciones para que se
reproduzcan (a este proceso se le llama cruce), siendo los hijos
una mezcla del código genético de los padres. A
continuación se producen una serie de mutaciones que
alteran los genes de los recién nacidos y por
último de entre toda la población se eligen
aquellos que van a sobrevivir desechándose el resto (la
población en un algoritmo genético típico
permanece constante en todas las iteraciones). Tanto a la hora de
la reproducción, como en el momento de elegir las
soluciones supervivientes en cada iteración, se favorece a
aquellos individuos que según la función de
evaluación sean más fuertes. El algoritmo
terminará cuando se llegue a un número de
iteraciones seleccionado previamente, o cuando se observe tras
una serie de iteraciones no se ha detectado ninguna mejora en la
población. El pseudo código sería el
siguiente:

Algoritmo

Crear población inicial
Evaluar la población
Mientras No(condición salida)
Seleccionar a los padres
Combinar los genes de los padres para crear a los
descendientes
Mutar a los descendientes
Evaluar la nueva población
Elegir los individuos que sobrevivirán

CLASES DE ALGORITMOS
GENÉTICOS

Algoritmos Genéticos
Generacionales

Se asemejan a la forma de reproducción de los
insectos, donde una generación pone huevos, se aleja
geográficamente o muere y es substituida por una nueva. En
este momento se realizan cruces en una piscina de individuos, los
descendientes son puestos en otra, al final de la fase
reproductiva se elimina la generación anterior y se pasa a
utilizar la nueva. Este modelo también es conocido como
Algoritmo Genético Canónico.

Algoritmos Genéticos de estado
Fijo.

Utilizan el esquema generacional de los mamíferos y otros animales de vida larga,
donde coexisten padres y sus descendientes, permitiendo que los
hijos sean educados por sus progenitores, pero también que
a la larga se genere competencia entre
ellos. En este modelo, no solo se deben seleccionar los dos
individuos a ser padres, si no también cuales de la
población anterior serán eliminados, para dar
espacio a los descendientes. La diferencia esencial entre el
reemplazo generacional y el modelo de estado fijo es que las
estadísticas de la población son
recalculadas luego de cada cruce y los nuevos descendientes
están disponibles inmediatamente para la
reproducción. Esto permite al modelo utilizar las
características de un individuo prometedor tan pronto como
es creado.
Algunos autores dicen que este modelo tiende a evolucionar mucho
más rápido que el modelo generacional, sin embargo
investigaciones de Goldberg y deb [GOLDBERG 93],
encontraron que las ventajas parecen estar relacionadas con la
alta tasa de crecimiento inicial, ellos dicen que los mismos
efectos pueden ser obtenidos en rangos de adaptación
exponencial o selección por competencia. No encontraron
evidencia que este modelo sea mejor que el Generacional.
Algoritmos Genéticos Paralelos.

Parte de la metáfora biológica que motivo
a utilizar la búsqueda genética consiste en que es
inherentemente paralela, donde al evolucionar se recorren
simultáneamente muchas soluciones, cada una representada
por un individuo de la población. Sin embargo, es muy
común en la naturaleza que no solo sea una
población evolucionando, si no varias poblaciones,
normalmente aisladas geográficamente, que originan
respuestas diferentes a la presión
evolutiva. Esto origina dos modelos que
toman es cuenta esta variación, y utilizan no una
población como los anteriores si4 no múltiples
concurrentemente.

Modelos de Islas.

Si se tiene una población de individuos, esta se
divide en subpoblaciones que evolucionan independientemente como
un Algoritmo Genético normal. Ocasionalmente, se producen
migraciones entre ellas, permitiéndoles intercambiar
material genético. Con la utilización de la
migración, este modelo puede explotar las
diferencias en las subpoblaciones; esta variación
representa una fuente de diversidad genética. Sin embargo,
si un número de individuos emigran en cada
generación, ocurre una mezcla global y se eliminan las
diferencias locales, y si la migración es infrecuente, es
probable que se produzca convergencia prematura en las
subpoblaciones.

Modelo Celular

Coloca cada individuo en una matriz, donde
cada uno sólo podrá buscar reproducirse con los
individuos que tenga a su alrededor (mas cerca de casa)
escogiendo al azar o al mejor adaptado. El descendiente pasara a
ocupar una posición cercana. No hay islas en este modelo,
pero hay efectos potenciales similares. Asumiendo que el cruce
esta restringido a individuos adyacentes, dos individuos
separados por 20 espacios están tan aislados como si
estuvieran en dos islas, este tipo de separación es
conocido como aislamiento por distancia.
Luego de la primera evaluación, los individuos
están todavia distribuidos al azar sobre la matriz.
Posteriormente, empiezan a emerger zonas como cromosomas y
adaptaciones semejantes. La reproducción y
selección local crea tendencias evolutivas aisladas, luego
de varias generaciones, la competencia local resultara en grupos
mas grandes de individuos semejantes.

ELEMENTOS DE UN
ALGORITMO GENETICO

Como los Algoritmos Genéticos se encuentra
basados en los procesos de evolución de los seres vivos,
casi todos sus conceptos se basan en conceptos de biología y
genética que son fáciles de comprender.

Individuo
Un individuo es un ser que caracteriza su propia especie. El
individuo es un cromosoma y es el codigo de
información sobre el cual opera el algoritmo. Cada
solución parcial del problema a optimizar está
codificada en forma de cadena o String en un alfabeto
determinado, que puede ser binario. Una cadena representa a un
cormosoma, por lo tanto tambien a un individuo y cada
posición de la cadena representa a un gen. Esto significa
que el algoritmo trabaja con una codificación de los
parametros y no con los parametros en si mismos. El genotipo, es
el conjunto de genes ordenados y representa las caracteristicas
del individuo. Cada individuo tinen una medida de su
adecuación como solución al problema.
Población
A un conjunto de individuos
(Cromosomas) se le denomina población. El método de
A.G´s consiste en ir obteniendo de forma sucesiva distintas
poblaciones. Por otra parte un Algoritmo Genético trabaja
con un conjunto de puntos representativos de diferentes zonas del
espacio de búsqueda y no con un solo punto (como lo hace
Hillclimbing).

Función Fitness.

La única restricción para usar un
algoritmo genético es que exista una función
llamada fitness, que le informe de cuan
bueno es un individuo dado en la solución de un problema.
Esta función fitness o de evaluación es el
principal enlace entre el Algoritmo Genético a un problema
real, es la efectividad y eficiencia de la función fitness
que se tome, por lo tanto debe procurarse que la función
fitness sea similar, si no igual a la función objetivo que
se quiere optimizar. Esta medida se utiliza como parámetro
de los operadores y guía la obtención de nuevas
poblaciones.

OPERADORES
GENETICOS.

Son los diferentes métodos u operaciones que se
pueden ejercer sobre una población y que nos permite
obtener poblaciones nuevas. Una vez que se ha evaluado cada
individuo sobre una función fitness, se aplican los
operadores genéticos. En Algoritmos Genéticos se
destacan los siguientes operadores.
Operador de Selección.

El paso siguiente a la evaluación es escoger los
miembros de la población que serán utilizados para
la reproducción. Su meta es dar mas oportunidades de
selección a los miembros más aptos de la
población. Así funciona: se calcula el cociente
entre el valor fitness de un individuo y la suma total de los
valores
fitness de todos los individuos de la población. Este
resultado mide la probabilidad de selección Ps (i) de cada
individuo.

Para ver la fórmula seleccione la
opción "Descargar" del menú superior

Ecuación No. 1 Probabilidad de
selección.

Empezando desde la población P (t) de N
individuos se obtiene una nueva población P(t+1) aplicando
N veces el operador de selección. Los individuos se
seleccionan de una especie de rueda de ruleta (como se muestra en la
figura 1) donde cada uno tiene asignado un trozo en
proporción a su probabilidad selecc

Para ver el gráfico seleccione la
opción "Descargar" del menú superiorión
Ps.

Figura No.1 Operador de
Selección

Este mecanismo puede causar problemas de convergencia
prematura, causada por la aparición de un individuo que es
mucho mejor que los otros de la población aunque esta
lejos de optimo; las copias de este individuo pueden dominar
rápidamente a la población, sin poder escapar
de este mínimo local.

Operador de Cruce

Consiste en unir en alguna forma los cromosomas de los
padres que han sido previamente selecciónados de la
generación anterior para formar dos descendientes. Existen
diversas variaciones, dependiendo del número de puntos de
división a emplear y la forma de ver el cromosoma. El
operador cruce se aplica en dos pasos: en el primero los
individuos se aparean (se seleccionan de dos a dos)
aleatoriamente con una determinada probabilidad, llamada
probabilidad de cruce Pc; en el segundo paso a cada par de
individuos seleccionados anteriormente se le aplica un
intercambio en su contenido desde una posición aleatoria K
hasta el final, con K Î [1, m-1], donde m es la longitud de
individuo. K es el denominado punto de cruce y determina la
subdivisión de cada padre en dos partes que se
intercambian para formar dos nuevos hijos, según podemos
ver en la figura 2 Esto se conoce como cruce ordinario o cruce de
un punto. El objetivo del operador de cruce es recombinar
subcadenas de forma eficiente; esta gestión
recibe el nombre de construcción de bloques.

Para ver el gráfico seleccione la
opción "Descargar" del menú superior

Figura No. 2 Operador de
Cruce

Mutación.

El operador de mutación consiste en la
alteración aleatoria de cada uno de los genes del
individuo con una probabilidad de mutación PM, como se
puede ver en la figura 3. El objetivo de la mutación es
producir diversidad en la población. Si al generar
aleatoriamente la población inicial o después de
varias generaciones, en la misma posición de todos los
cromosomas sólo aparece un único elemento del
alfabeto utilizado, esto supondrá que con los operadores
de reproducción y cruce, nunca cambiara dicho elemento,
por lo que puede ocurrir que jamas se alcance la solución
más optima a nuestro problema. La probabilidad de
aparición del operador de mutación no debe ser
grande para no perjudicar la correcta construcción de
bloques. El operador de mutación origina variaciones
elementales en la población y garantiza que cualquier
punto del espacio de búsqueda pueda ser
alcanzado.

Para ver el gráfico seleccione la
opción "Descargar" del menú superior

Figura No. 3 Operador de
Mutación

CICLO GENERAL DE UN
ALGORITMO GENETICO ESTANDAR

El AG estándar se puede expresar en pseudocodigo
con el siguiente ciclo. [Coello 95]:
1. Generar aleatoriamente la población inicial de
individuos P(0). Generación = 0:
2. Mientras ( numero _ generaciones <= máximo _
números _ generaciones)

Hacer

{

Evaluación;

Selección;

Reproducción;

Generación ++;

}

3.Mostrar resultados;

Fin de la generación

Estas características de los AG, a su vez,
describen las diferencias entre ellos, y otros métodos
normales de optimización.

1. Un Algoritmo Genético trabaja con
codificación de los parámetros que busca optimizar
y no con los parámetros en sí mismo.

2. Un Algoritmo Genético trabaja con un conjunto
de puntos representativos de diferentes zonas del espacio y no
con un solo punto. Por el contrario necesita considerables
recursos de computación.

3. La aplicación de AG no depende de ninguna
propiedad de la función a optimizar (derivable, continua,
ni siquiera conocida), o de que el conjunto de posibles
soluciones sea finito o no lo sea.

4. Un AG utiliza reglas de transición
probabilisticas, no deterministas, lo cual hace que dos
aplicaciones consecutivas de un AG a un mismo problema puedan
producir dos soluciones distintas.

EL ejemplo siguiente nos da una pequeña ilustración de un Pseudocódigo de
Algoritmo Genético.

BEGIN /* Algoritmo Genético */

Generar una población inicial.

Computar la función de evaluación de cada
individuo.

WHILE NOT Terminado DO

BEGIN /* Producir nueva Generación */

FOR Tamaño Población /2 DO

BEGIN /* Ciclo Reproductivo */

Seleccionar dos individuos de la anterior
generación

El cruce (probabilidad de selección proporcional
a la

Función de evaluación de
individuo).

Cruzar con cierta probabilidad los dos
individuos

obtenida dos descendientes

Mutar los dos descendientes con cierta
probabilidad.

Computar la función de evaluación de los
dos

descendientes Mutados.

Insertar los dos descendientes mutados en la
nueva

generación.

END

IF La población ha convergido THEN

Terminado =TRUE

END

END

Algunas aplicaciones de los AGs son las
siguientes

• Optimización (estructural, de topologías, numérica,
  combinatoria, etc.)
• Aprendizaje de maquina (sistemas
  clasificadores)
• Bases de datos (optimización de
  consultas)
• Reconocimiento de patrones (por ejemplo, imágenes)
• Generación de gramáticas (regulares,
  libres de contexto, etc.)
• Planeación de movimientos de
  robots
• Predicción.

Estrategias Evolutivas vs Programación
Evolutiva

La Programación Evolutiva usa normalmente
selección estocástica, mientras que

las estrategias evolutivas usan selección
deterministica.

Ambas técnicas operan a nivel fenotipico (es
decir, no requieren codificación

de las variables del
problema).

La programación evolutiva es una
abstracción de la evolución al nivel de
las

especies, por lo que no se requiere el uso de un
operador de recombinación (diferentes especies no se
pueden cruzar entre si). En contraste, las estrategias evolutivas
son una abstracción de la evolución al nivel de un
individuo, por lo que la recombinación es
posible.

 Tendencias futuras

Las limitaciones de la representación binaria en
algunas aplicaciones ha hecho de esta una ruta interesante de
investigación, sobre todo en el contexto de
problemas de manufactura y definición de rutas, en los
cuales la respuesta se expresa en forma de permutaciones.
Idealmente, debiera existir un tipo de representación
suficientemente flexible como para permitir su utilización
en una amplia gama de problemas de forma sencilla y
natural.

Filho [77] desarrollo un sistema llamado
GAME (Genetic Algorithms Manipu-lation Environment), que
constituye un paso importante en esta dirección. GAME usa una codificación
de árbol en la que las hojas pueden ser enteros,
caracteres,números reales o cadenas binarias.

Gibson [101] también propuso una
codificación híbrida similar a la de
Filho.

Su propuesta se basa en el uso de componentes de
diferentes tipos en el contexto de modelado de procesos
industriales.

Existe amplia evidencia en la literatura especializada
[159, 155, 190, 100, 115] de que el usar una
representación adecuada puede simplificar tremendamente el
proceso de búsqueda de un algoritmo genético, pero
a pesar de eso, muchos investigadores suelen pasar por alto este
importante hecho. Por lo tanto, es vital no únicamente
reconocer que se requieren codificaciones mas poderosas,
sino

SOFTWARE

En general, podemos clasificar el software para
computación evolutiva en 3 grandes grupos:

_Orientado a las aplicaciones: Son "cajas negras"
diseñadas para ocultar

detalles de los AGs y ayudar al usuario a desarrollar
aplicaciones para dominios

específicos tales como las finanzas, la
programación de horarios, etc.

_Orientado a los algoritmos: Se basan en modelos
de AGs específicos y

pueden subdividirse en 2 grupos:

1. Sistemas Específicos: Contienen un solo
algoritmo.

2. Bibliotecas:
Contienen una gama de algoritmos y operadores
genéticos

que pueden estar disponibles solo de manera
precompilada.

Cajas de herramientas
(tool kits): Sistemas de programación que
proporcionan

muchas utilerías, algoritmos y operadores
genéticos que pueden

usarse para cualquier tipo de aplicación y que
normalmente se proporcionan

en forma de código fuente (al menos de manera
parcial).

A su vez, las cajas de herramientas se pueden subdividir
en 2 grupos:

1.Sistemas Educativos:

2. Sistemas de propósito general:

CONCLUSIÓN

• Los algoritmos genéticos son un proceso de
  prueba y error.
• Una de las partes mas importantes del algoritmo es la
  función de "adaptación". Sin ella la
  mutación se pueden "contaminar", y no hay
  evolución.
• Solucionar el problema consistirá en encontrar
  la solución óptima, y por tanto, los Algoritmos
  Evolutivos son en realidad un método de
  búsqueda.
• La Computación Evolutiva, en resumen, es
  la ciencia
  computacional cuyos algoritmos imitan el proceso evolutivo de
  la naturaleza.

BIBLIOGRAFÍA

1. http://www.redcientifica.com/doc/doc199904260012.html

2.
http://www.redcientifica.com/gaia/ce/ce_c.htm

3.http://www.lania.mx/spanish/actividades/newsletters/1997-otono-invierno/evolutiv.html

4.http://www.lania.mx/spanish/actividades/newsletters/1997-otono-invierno/evolutiv.html

5.
http://www.cimat.mx/talleres/pasados/2003/evolutiva/

6.
http://www.dccia.ua.es/ria/artics/sceta97.pdf

7.http://www.lania.mx/spanish/actividades/newsletters/1999-primavera-verano/tendencias.html

8. http://cursos.itam.mx/akuri/Semestre2/RNS/0123Pres/0.pdf

9. http://pitagoras.usach.cl/~msanchez/ce/

10.
http://delta.cs.cinvestav.mx/~ccoello/talks.html

11.
http://www.psicologiacientifica.com/articulos/ar-h_gascon01.htm

12.http://chue.ing.ula.ve/DOCENCIA/POSTGRADO/CURSOS/MSS05/ComputacionEvolutiva.html#PE

13.
http://www.elrinconcito.com/articulos/Genetico/Geneticos.htm

14.
http://delta.cs.cinvestav.mx/~ccoello/genetic.html

15.
http://delta.cs.cinvestav.mx/~ccoello/compevol/apuntes.pdf.gz

16. http://kal-el.ugr.es/VidArt/VidaArti.html

17. http://pitagoras.usach.cl/~msanchez/ce/

18.
http://members.tripod.com/jesus_alfonso_lopez/AgIntro.html

19. http://www.iieh.com/comunidad/mherran.html

José Madrigal García

Mateo Luna Luna

CUNDUACÁN TABASCO