SlideShare a Scribd company logo
1 of 15
Download to read offline
CAPÍTULO I
                           NOCIONES PREELIMINARES


Los Algoritmos Genéticos (AG) son métodos adaptativos que pueden usarse para
resolver problemas de búsqueda y optimización.
Están basados en el proceso genético de los organismos vivos. A lo largo de las
generaciones, las poblaciones evolucionan en la naturaleza de acorde con los principios
de la selección natural y la supervivencia de los más fuertes, postulados por Darwin. Por
imitación de este proceso, los Algoritmos Genéticos son capaces de ir creando
soluciones para problemas del mundo real. La evolución de dichas soluciones hacia
valores óptimos del problema depende en buena medida de una adecuada codificación
de las mismas.
Los principios básicos de los Algoritmos Genéticos fueron establecidos por Holland, y
se encuentran bien descritos en varios textos de Goldberg, Davis, Michalewicz, Reeves.
En la naturaleza los individuos de una población compiten entre sí en la búsqueda de
recursos tales como comida, agua y refugio. Incluso los miembros de una misma
especie compiten a menudo en la búsqueda de un compañero. Aquellos individuos que
tienen más éxito en sobrevivir y en atraer compañeros tienen mayor probabilidad de
generar un gran número de descendientes. Por el contrario individuos poco dotados
producirán un menor número de descendientes. Esto significa que los genes de los
individuos mejor adaptados se propagarán en sucesivas generaciones hacia un número
de individuos creciente. La combinación de buenas características provenientes de
diferentes ancestros, puede a veces producir descendientes “súper individuos”, cuya
adaptación es mucho mayor que la de cualquiera de sus ancestros. De esta manera, las
especies evolucionan logrando características cada vez mejor adaptadas al entorno en el
que viven.
Los Algoritmos Genéticos usan una analogía directa con el comportamiento natural.
Trabajan con una población de individuos, cada uno de los cuales representa una
solución factible a un problema dado. A cada individuo se le asigna un valor o
puntuación, relacionado con la bondad de dicha solución. En la naturaleza esto
equivaldría al grado de efectividad de un organismo para competir por unos
determinados recursos. Cuanto mayor sea la adaptación de un individuo al problema,
mayor será la probabilidad de que el mismo sea seleccionado para reproducirse,
cruzando su material genético con otro individuo seleccionado de igual forma. Este
cruce producirá nuevos individuos, descendientes de los anteriores, los cuales
comparten algunas de las características de sus padres. Cuanto menor sea la adaptación
de un individuo, menor será la probabilidad de que dicho individuo sea seleccionado
para la reproducción, y por tanto de que su material genético se propague en sucesivas
generaciones.
De esta manera se produce una nueva población de posibles soluciones, la cual
reemplaza a la anterior y verifica la interesante propiedad de que contiene una mayor
proporción de buenas características en comparación con la población anterior. Así a lo
largo de las generaciones las buenas características se propagan a través de la población.
Favoreciendo el cruce de los individuos mejor adaptados, van siendo exploradas las
áreas más prometedoras del espacio de búsqueda. Si el Algoritmo Genético ha sido bien
diseñado, la población convergerá hacia una solución óptima del problema.
El poder de los Algoritmos Genéticos proviene del hecho de que se trata de una técnica
robusta, y pueden tratar con éxito una gran variedad de problemas provenientes de
diferentes áreas, incluyendo aquellos en los que otros métodos encuentran dificultades.
Si bien no se garantiza que el Algoritmo Genético encuentre la solución óptima del
problema, existe evidencia empírica de que se encuentran soluciones de un nivel
aceptable, en un tiempo competitivo con el resto de algoritmos de optimización
combinatoria. En el caso de que existan técnicas especializadas para resolver un
determinado problema, lo más probable es que superen al Algoritmo Genético, tanto en
rapidez como en eficacia. El gran campo de aplicación de los Algoritmos Genéticos se
relaciona con aquellos problemas para los cuales no existen técnicas especializadas.
Incluso en el caso en que dichas técnicas existan, y funcionen bien, pueden efectuarse
mejoras de las mismas haciendo algoritmos híbridos entre éstas y los Algoritmos
Genéticos.
CAPÌTULO II
                      EL ALGORITMO GENÉTICO SIMPLE


El Algoritmo Genético Simple, también denominado “canónico” se representa en la
figura 2.1. Como se verá a continuación, se necesita una codificación o representación
del problema, que resulte adecuada al mismo. Además se requiere una función de ajuste
o adaptación al problema, la cual asigna un número real a cada posible solución
codificada. Durante la ejecución del algoritmo, los padres deben ser seleccionados para
la reproducción, a continuación dichos padres seleccionados se cruzarán generando dos
hijos, sobre cada uno de los cuales actuará un operador de mutación. El resultado de la
combinación de las anteriores funciones será un conjunto de individuos (posibles
soluciones al problema) los cuales en la evolución del Algoritmo Genético formarán
parte de la siguiente población.




                        Figura 2.1 Pseudo código del Algoritmo Genético Simple




Codificación
Se supone que los individuos (posibles soluciones del problema), pueden representarse
como un conjunto de parámetros denominados “genes”, los cuales agrupados forman
una cadena de valores o “cromosoma”. Si bien el alfabeto utilizado para representar los
individuos no debe necesariamente estar constituido por {0, l}, buena parte de la teoría
en la que se fundamentan los Algoritmos Genéticos utiliza dicho alfabeto. En términos
biológicos, el conjunto de parámetros representando un cromosoma particular se
denomina “fenotipo”. El fenotipo contiene la información requerida para construir un
organismo, el cual se refiere como “genotipo”. Los mismos términos se utilizan en el
campo de los Algoritmos Genéticos. La adaptación al problema de un individuo
depende de la evaluación del genotipo.
Esta última puede inferirse a partir del fenotipo, es decir puede ser computada a partir
del cromosoma, usando la función de evaluación. La función de adaptación debe ser
diseñada para cada problema de manera específica. Dado un cromosoma particular, la
función de adaptación le asigna un número real, que se supone refleja el nivel de
adaptación al problema del individuo representado por el cromosoma.
Durante la fase reproductiva se seleccionan los individuos de la población para cruzarse
y producir descendientes que constituirán, una vez mutados, la siguiente generación de
individuos. La selección de padres se efectúa al azar usando un procedimiento que
favorezca a los individuos mejor adaptados, ya que a cada individuo se le asigna una
probabilidad de ser seleccionado que es proporcional a su función de adaptación. Este
procedimiento se dice que está basado en la ruleta sesgada. Según dicho esquema, los
individuos bien adaptados se escogerán probablemente varias veces por generación,
mientras que los pobremente adaptados al problema no se escogerán más que de vez en
cuando.
Una vez seleccionados dos padres, sus cromosomas se combinan, utilizando
habitualmente los operadores de cruce y mutación. Las formas básicas de dichos
operadores se describen a continuación.
El operador de cruce toma dos padres seleccionados y corta sus cadenas de
cromosomas en una posición escogida al azar, para producir dos subcadenas iniciales y
dos subcadenas finales. Después se intercambian las subcadenas finales, produciéndose
dos nuevos cromosomas completos. Esto se muestra en la figura 2.2. Ambos
descendientes heredan genes de cada uno de los padres. Este operador se conoce como
operador de cruce basado en un punto.




                           Figura 2.2. Operador de cruce basado en un punto




Habitualmente el operador de cruce no se aplica a todos los pares de individuos que han
sido seleccionados para emparejarse, sino que se aplica de manera aleatoria,
normalmente con una probabilidad comprendida entre 0.5 y 1.0. En el caso en que el
operador de cruce no se aplique, la descendencia se obtiene simplemente duplicando los
padres.
El operador de mutación se aplica a cada hijo de manera individual, y consiste en la
alteración aleatoria (normalmente con probabilidad pequeña) de cada gen componente
del cromosoma. La figura 2.3 muestra la mutación del quinto gen del cromosoma.




                                       Figura 2.3. Operador de mutación




Si bien puede en principio pensarse que el operador de cruce es más importante que el
operador de mutación, ya que proporciona una exploración rápida del espacio de
búsqueda, éste último asegura que ningún punto del espacio de búsqueda tenga una
probabilidad cero de ser examinado, y es de capital importancia para asegurar la
convergencia de los Algoritmos Genéticos.
Para criterios prácticos, es muy útil la definición de convergencia introducida en este
campo por De Jong. Si el Algoritmo Genético ha sido correctamente implementado, la
población evolucionará a lo largo de las generaciones sucesivas de tal manera que la
adaptación media extendida a todos los individuos de la población, así como la
adaptación del mejor individuo se irán incrementando hacia el óptimo global. El
concepto de convergencia está relacionado con la progresión hacia la uniformidad: un
gen ha convergido cuando al menos el 95 % de los individuos de la población
comparten el mismo valor para dicho gen. Se dice que la población converge cuando
todos los genes han convergido. Se puede generalizar dicha definición al caso en que al
menos un poco de los individuos de la población hayan convergido.
La figura 2.4 muestra como varía la adaptación media y la mejor adaptación en un
Algoritmo Genético Simple típico.




                Figura 2.4. Adaptación media y mejor adaptación en un Algoritmo Genético simple
A medida que el número de generaciones aumenta, es más probable que la adaptación
media se aproxime a la del mejor individuo.


Ejemplo
Como ilustración de los diferentes componentes del Algoritmo Genético Simple,
supóngase el problema adaptado de Goldberg de encontrar el máximo de la función
                                                             f(z) = x’
para z = {1,2,...,32}.
Evidentemente para lograr dicho óptimo, bastaría actuar por búsqueda exhaustiva, dada
la baja cardinalidad del espacio de búsqueda. Se trata por tanto de un mero ejemplo con
el que se pretende ilustrar el comportamiento del algoritmo anteriormente descrito.
Consultando el pseudo código de la figura 2.1, se ve que el primer paso a efectuar
consiste en determinar el tamaño de la población inicial, para después obtener dicha
población al azar y computar la función de evaluación de cada uno de sus individuos.
Suponiendo que el alfabeto utilizado para codificar los individuos esté constituido por
{0, 1}, se necesitarán cadenas de longitud 5 para representar los 32 puntos del espacio
de búsqueda.
En la tabla 2.1 están representados los 4 individuos que constituyen la población inicial,
junto con su función de adaptación al problema, así como la probabilidad de que cada
uno de dichos individuos sea seleccionado – según el modelo de ruleta sesgada – para
emparejarse.
Volviendo a consultar el pseudo código expresado en la figura 2.1, se puede ver que el
siguiente paso consiste en la selección de 2 parejas de individuos.




        Tabla 2.1 Población inicial de la simulación efectuada a mano correspondiente al Algoritmo Genético simple.




Para ello es suficiente con obtener 4 números reales provenientes de una distribución de
probabilidad uniforme en el intervalo [0, 1), y compararlos con la última columna de la
Tabla 2.l. Así por ejemplo, supóngase que dichos 4 números son 0.58, 0.84, 0.11 y 0.43.
Esto significa que los individuos seleccionados para el cruce fueron el individuo 2 junto
con el individuo 4, así como el individuo 1 junto con el individuo 2.
Para seguir con el Algoritmo Genético Simple, se necesita determinar la probabilidad de
cruce p. Supóngase que p = 0.8. Valiéndose al igual que antes de 2 números
provenientes de la distribución uniforme para este caso, se determinará si los
emparejamientos anteriores se llevan a cabo. Admítase, por ejemplo, que los dos
números extraídos sean menores que 0.8, decidiéndose por tanto efectuar el cruce entre
las dos parejas. Para ello se escogerá un número al azar entre l y L – 1 (siendo L la
longitud de la cadena utilizada para representar el individuo). Nótese que la restricción
impuesta al escoger el número entre 1 y L – l, y no L, se realiza con la finalidad de que
los descendientes no coincidan con los padres.
Supóngase, tal y como se indica en la tabla 2.2, que los puntos de cruce resulten ser 2 y
3. De esta manera se obtendrían los 4 descendientes descritos en la tercera columna de
la tabla 2.2. A continuación siguiendo el seudo código de la figura 2.1, se mutaría con
una probabilidad p, cercana a cero, cada uno de los bits de las cuatro cadenas de
individuos. En este caso se supone que el único bit mutado corresponde al primer gen
del tercer individuo. En las dos últimas columnas se pueden consultar los valores de los
individuos, así como las funciones de adaptación correspondientes. Como puede
observarse, tanto el mejor individuo como la función de adaptación media han mejorado
sustancialmente al compararlos con los resultados de la Tabla 2.1.




Tabla 2.2. Población en el tiempo 1, proveniente de efectuar los operadores de cruce y mutación sobre los individuos expresados en
                                  la tabla 2.1, los cuales constituyen la población en el tiempo 0.
CAPÍTULO III
    EXTENSIONES Y MODIFICACIONES DEL ALGORITMO GENÉTICO
                           SIMPLE


En este capítulo se introducen otras técnicas referentes a la población, función objetivo,
selección, cruce y mutación.
Población
Tamaño de la población
Una cuestión que puede plantearse es la relacionada con el tamaño idóneo de la
población. Parece intuitivo que las poblaciones pequeñas corren el riesgo de no cubrir
adecuadamente el espacio de búsqueda, mientras que el trabajar con poblaciones de
gran tamaño puede acarrear problemas relacionados con el excesivo costo
computacional.
Goldberg efectuó un estudio teórico, obteniendo como conclusión que el tamaño óptimo
de la población para cadenas de longitud I, con codificación binaria, crece
exponencialmente con el tamaño de la cadena.
Este resultado traería como consecuencia que la aplicabilidad de los Algoritmos
Genéticos en problemas reales sería muy limitada, ya que resultarían no competitivos
con otros métodos de optimización combinatoria. Alander, basándose en evidencia
empírica sugiere que un tamaño de población comprendida entre l y 21 es suficiente
para atacar con éxito los problemas por él considerados.
Población inicial
Habitualmente la población inicial se escoge generando cadenas al azar, pudiendo
contener cada gen uno de los posibles valores del alfabeto con probabilidad uniforme.
Podría existir la pregunta sobre qué es lo que sucedería si los individuos de la población
inicial se obtuviesen como resultado de alguna técnica heurística o de optimización
local. En los pocos trabajos que existen sobre este aspecto, se constata que esta
inicialización no aleatoria de la población inicial, puede acelerar la convergencia del
Algoritmo Genético. Sin embargo en algunos casos la desventaja resulta ser la
prematura convergencia del algoritmo, queriendo indicar con esto la convergencia hacia
óptimos locales.
Función objetivo
Dos aspectos que resultan cruciales en el comportamiento de los Algoritmos Genéticos
son la determinación de una adecuada función de adaptación o función objetivo, así
como la codificación utilizada.
Idealmente interesaría construir funciones objetivo con “ciertas regularidades”, es decir
funciones objetivo que verifiquen que para dos individuos que se encuentren cercanos
en el espacio de búsqueda sus respectivos valores en las funciones objetivo sean
similares. Por otra parte una dificultad en el comportamiento del Algoritmo Genético
puede ser la existencia de gran cantidad de óptimos locales, así como el hecho de que el
óptimo global se encuentre muy aislado.
La regla general para construir una buena función objetivo es que ésta debe reflejar el
valor del individuo de una manera “real”, pero en muchos problemas de optimización
combinatoria, donde existe una gran cantidad de restricciones, buena parte de los puntos
del espacio de búsqueda representan individuos no válidos.
Para este planteamiento en el que los individuos están sometidos a restricciones, se han
propuesto varias soluciones. La primera sería la que se puede denominar “absolutista”,
en la que aquellos individuos que no verifican las restricciones no son considerados
como tales, y se siguen efectuando cruces y mutaciones hasta obtener individuos
válidos, o bien, a dichos individuos se les asigna una función objetivo igual a cero.
Otra posibilidad consiste en reconstruir aquellos individuos que no verifican las
restricciones. Dicha reconstrucción suele llevarse a cabo por medio de un nuevo
operador que se acostumbra a denominar “reparador”.
Otro enfoque está basado en la penalización de la función objetivo. La idea general
consiste en dividir la función objetivo del individuo por una cantidad (la penalización)
que guarda relación con las restricciones que dicho individuo viola. Dicha cantidad
puede simplemente tener en cuenta el número de restricciones violadas o bien el
denominado costo esperado de reconstrucción, es decir el coste asociado a la conversión
de dicho individuo en otro que no viole ninguna restricción.
Otra técnica que se ha venido utilizando en el caso en que la computación de la función
objetivo sea muy compleja es la denominada “evaluación aproximada de la función
objetivo”. En algunos casos la obtención de n funciones objetivo aproximadas puede
resultar mejor que la evaluación exacta de una única función objetivo (supuesto el caso
de que la evaluación aproximada resulta como mínimo n veces más rápida que la
evaluación exacta).
Un problema habitual en las ejecuciones de los Algoritmos Genéticos surge debido a la
velocidad con la que el algoritmo converge. En algunos casos la convergencia es muy
rápida, lo que suele denominarse “convergencia prematura”, en la cual el algoritmo
converge hacia óptimos locales, mientras que en otros casos el problema es justo el
contrario, es decir, se produce una convergencia lenta del algoritmo. Una posible
solución a estos problemas pasa por efectuar transformaciones en la función objetivo. El
problema de la convergencia prematura surge a menudo cuando la selección de
individuos se realiza de manera proporcional a su función objetivo. En tal caso, pueden
existir individuos con una adaptación al problema muy superior al resto, que a medida
que avanza el algoritmo “dominan” a la población. Por medio de una transformación de
la función objetivo, en este caso una comprensión del rango de variación de la función
objetivo, se pretende que dichos “súper-individuos” no lleguen a dominar a la
población.
El problema de la lenta convergencia del algoritmo, se resolvería de manera análoga,
pero en este caso efectuando una expansión del rango de la función objetivo.
La idea de especies de organismos, ha sido imitada en el diseño de los Algoritmos
Genéticos en un método propuesto por Goldberg y Richardson, utilizando una
modificación de la función objetivo de cada individuo, de tal manera que individuos que
estén muy cercanos entre sí devalúen su función objetivo, con objeto de que la
población gane en diversidad.
Selección
Para aplicar los operadores genéticos se tiene que seleccionar un subconjunto de la
población. Algunas de las técnicas disponibles son:
Selección directa: toma elementos de acuerdo a un criterio objetivo, como son “los x
mejores”, “los x peores”
Selección aleatoria: puede ser realizada por selección equiprobable o selección
estocástica.
            - Selección equiprobable: todos tienen la misma probabilidad de ser
            escogidos.
            - Selección estocástica: la probabilidad de que un individuo sea escogido
            depende de una heurística. Los distintos procedimientos estocásticos son:
                   - Selección por sorteo: cada individuo de la población tiene asignado
                   un rango proporcional (o inversamente proporcional) a su adaptación.
                   Se escoge un número aleatorio dentro del rango global, y el escogido
                   es aquél que tenga dicho número dentro de su rango. La probabilidad
                   de ser escogido es proporcional/inversamente proporcional al grado
                   de adaptación del individuo.
                   - Selección por escaños: se divide el rango del número aleatorio en
                   un número predeterminado de escaños. Los escaños se reparten de
                   acuerdo con la ley d'Hont, tomando como “puntuación” para repartir
                   los escaños el grado de adaptación. Se observa que es más probable
                   escoger un elemento de baja probabilidad por este método que en el
                   de selección por sorteo.
                   - Selección por restos estocásticos: es igual al método de selección
                   de escaños, sólo que los escaños no asignados directamente, es decir,
                   aquellos en que se aplica directamente la ley d'Hont se asignan de
                   forma aleatoria. La probabilidad de escoger un elemento de muy baja
                   probabilidad es más alta que en el de selección por escaños.
                   -   Por ruleta: Se define un rango con las características de la
                       selección por sorteo. El número al azar será un número aleatorio
                       forzosamente menor que el tamaño del rango. El elemento
                       escogido será aquel en cuyo rango esté el número resultante de
                       sumar el número aleatorio con el resultado total que sirvió para
                       escoger el elemento anterior. El comportamiento es similar al de
                       una ruleta, donde se define un avance cada tirada a partir de la
                       posición actual. Tiene la ventaja de que no es posible escoger dos
                       veces consecutivas el mismo elemento, y que puede ser forzado a
                       que sea alta la probabilidad de que no sean elementos próximos
                       en la población -esto último no es una ventaja de por sí; salvo que
                       algunos de los otros operadores genéticos emplee un método de
                       selección directa basado en la posición relativa de los individuos
                       de la población-.
-   Por torneo: escoge un subconjunto de individuos de acuerdo con
                      una de las técnicas anteriores -habitualmente, aleatoria o
                      estocástica- y de entre ellos selecciona el más adecuado por otra
                      técnica -habitualmente, determinística de tipo “el mejor” o “el
                      peor”-. Esta técnica tiene la ventaja de que permite un cierto
                      grado de elitismo -el mejor nunca va a morir, y los mejores tienen
                      más probabilidad de reproducirse y de emigrar que los peores-
                      pero sin producir una convergencia genética prematura, si la
                      población es, al menos, un orden de magnitud superior al del
                      número de elementos involucrados en el torneo.
Implementación del elitismo
Se denomina elitismo al proceso por el cual determinados elementos con una adaptación
especialmente buena tienen determinados privilegios -nunca mueren, proporción alta de
pasos en que se reproduce uno de la élite con otro al azar-... Sin embargo, en fases
iniciales es peligroso, ya que puede producirse que una élite de súper- individuos acabe
con la diversidad genética del problema. Para ello, lo que se puede hacer es escalar la
función de adaptación en las primeras fases del algoritmo -de forma que las diferencias
entre la élite y el pueblo sean menores- y superescalar la función de adaptación al final
del algoritmo, para evitar un bloqueo de la convergencia.
Cruce
Existen gran cantidad de técnicas de cruce. Las técnicas básicas son:
Cruce básico: se selecciona un punto al azar de la cadena. La parte anterior del punto es
copiada del genoma del padre y la posterior del de la madre.
Cruce multipunto: igual que el cruce básico, sólo que estableciendo más de un punto de
cruce.
Cruce segmentado: existe una probabilidad de que un cromosoma sea punto de un
cruce. Conforme se va formando la nueva cadena del descendiente, para cada gen, se
verifica si ahí se va producir un cruce.
Cruce uniforme: para cada gen de la cadena del descendiente existe una probabilidad de
que el gen pertenezca al padre, y otra de que pertenezca a la madre.
Cruces para permutación: Existe una familia de cruces específicas para los problemas
de permutación, siendo algunos de ellos:
           - Cruce de mapeamiento parcial: toma una subsecuencia del genoma del
           padre y procura preservar el orden absoluto de los fenotipos -es decir, orden
           y posición en el genoma- del resto del genoma lo más parecido posible de la
           madre. Aparece también en la bibliografía como PMX.
           - Cruce de orden: toma una subsecuencia del genoma del padre y procura
           preservar el orden relativo de los fenotipos del resto del genoma lo más
           parecido posible de la madre. Se puede encontrar en la bibliografía como
           OX.
           - Cruce de ciclo: Se toma el primer gen del genoma del padre, poniéndolo en
           la primera posición del hijo, y el primer gen del genoma de la madre,
poniéndolo dentro del genoma del hijo en la posición que ocupe en el
           genoma del padre. El fenotipo que está en la posición que ocupa el gen del
           genoma del padre igual al primer gen del genoma de la madre se va a colocar
           en la posición que ocupe en el genoma del padre, y así hasta rellenar el
           genoma del hijo. Este método también es conocido en la bibliografía como
           CX.
Es una buena idea que tanto la codificación como la técnica de cruce se hagan de
manera que las características buenas se hereden o al menos no sea mucho peor que el
peor de los padres. En problemas en los que, por ejemplo, la adaptación es función de
los pares de genes colaterales, el resultante del cruce uniforme tiene una adaptación
completamente aleatoria.
Mutación
Existen varias técnicas distintas de mutación. Algunas de éstas son:
Mutación de bit: existe una única probabilidad de que se produzca una mutación de
algún bit. De producirse, el algoritmo toma aleatoriamente un bit, y lo invierte.
Mutación multibit: cada bit tiene una probabilidad de mutarse o no, que es calculada en
cada pasada del operador de mutación multibit.
Mutación de gen: igual que la mutación de bit, solamente que, en vez de cambiar un bit,
cambia un gen completo. Puede sumar un valor aleatorio, un valor constante, o
introducir un gen aleatorio nuevo.
Mutación multigen: igual que la mutación de multibit solamente que, en vez de cambiar
un conjunto de bits, cambia un conjunto de genes. Puede sumar un valor aleatorio, un
valor constante, o introducir un gen aleatorio nuevo.
Mutación de intercambio: existe una probabilidad de que se produzca una mutación. De
producirse, toma dos bits/genes aleatoriamente y los intercambia.
Mutación de barajado: existe una probabilidad de que se produzca una mutación. De
producirse, toma dos bits o dos genes aleatoriamente y baraja de forma aleatoria los bits
-o genes, según se hubiera escogido- comprendidos entre los dos. La bibliografía en
inglés emplea el término scramble mutation, en mención a un juego de mesa, mas la
operación que se realiza realmente es un barajado entre los dos genes.
CAPÍTULO IV
                     SOFTWARE DE ALGORITMOS GENÉTICOS


Existen varios paquetes y bibliotecas de algoritmos genéticos en el mercado, a
continuación se presentan algunos:
GALOPPS
Dirección primaria:
GARAGe.cps.msu.edu/software/software-index.html
Dirección para descargar vía FTP:
garage.cps.msu.edu/pub/GA/galopps/


GAGS
Generador de aplicaciones basadas en algoritmos genéticos, escrito en C++.
Desarrollado por el grupo de J.J. Melero.
Dirección primaria:
kal-el.ugr.es/gags.html
Dirección para descargar vía FTP:
kal-el.ugr.es/GAGS/.


FORTRAN GA
Desarrollo de algoritmos genéticos para Fortran.
Dirección primaria:
www.staff.uiuc.edu/~ carroll/ga.html.


GALIB
Biblioteca de algoritmos genéticos de Matthew. Conjunto de clases en C++ de
algoritmos genéticos.
Dirección primaria:
lancet.mit.edu/ga/
Dirección para descargar vía FTP:
lancet.mit.edu/pub/ga/


GAS
Paquete para desarrollar aplicaciones de algoritmos genéticos en Python.
Dirección primaria:
starship.skyport.net/crew/gandalf
Dirección para descargar vía FTP:
ftp.coe.uga.edu/users/jae/ai.


GECO
Conjunto de herramientas para LISP
Dirección para descargar vía FTP:
ftp://ftp.aic.nrl.navy.mil/pub/galist/src/.


GPDATA
Para desarrollar algoritmos genéticos en C++.
Dirección primaria:
cs.ucl.ac.uk/genetic/papers/
Dirección para descargar vía FTP:
ftp.cs.bham.ac.uk/pub/authors/W.B.Langdon/gp-code/


GPJPP
Bibliotecas de clases para desarrollar algoritmos genéticos en Java
Dirección primaria:
www.turbopower.com/~ kimk/gpjpp.asp.
GP Kernel
Biblioteca de clases para programación genética en C++.
Dirección primaria:
www.emk.e-technik.th-darmstadt.de/~ thomasw/gp.html.


LIL-GP
Herramientas para programación genética en C.
Dirección primaria:
isl.msu.edu/GA/software/lil-gp/index.html
Dirección para descargar vía FTP:
isl.cps.msu.edu/pub/GA/lilgp/


SUGAL
SUnderland Genetic ALgorithm system. Para hacer experimentos con algoritmos
genéticos.
Dirección primaria:
www.trajan-software.demon.co.uk/sugal.htm.


GPsys
Sistema de programación genética en Java.
Dirección primaria:
www.cs.ucl.ac.uk/staff/A.Qureshi/gpsys.html.

More Related Content

What's hot

Método de Búsqueda Hash
Método de Búsqueda HashMétodo de Búsqueda Hash
Método de Búsqueda HashBlanca Parra
 
Agentes inteligentes
Agentes inteligentesAgentes inteligentes
Agentes inteligentesmenamigue
 
Capítulo 16 (Diseño fisico y refinación de la Base de Datos)
Capítulo 16 (Diseño fisico y refinación de la Base de Datos)Capítulo 16 (Diseño fisico y refinación de la Base de Datos)
Capítulo 16 (Diseño fisico y refinación de la Base de Datos)Liz Ocampo
 
Informe analisis de algoritmos (mitad de cuadrado)
Informe analisis de algoritmos (mitad de cuadrado)Informe analisis de algoritmos (mitad de cuadrado)
Informe analisis de algoritmos (mitad de cuadrado)Sergio Ormeño
 
Diagrama entidad-relacion normalización
Diagrama entidad-relacion normalizaciónDiagrama entidad-relacion normalización
Diagrama entidad-relacion normalizacióncintiap25
 
Modelo relacional y reglas de integridad
Modelo relacional y reglas de integridadModelo relacional y reglas de integridad
Modelo relacional y reglas de integridadkamui002
 
Conversión de un AFN a un AFD.
Conversión de un AFN a un AFD.Conversión de un AFN a un AFD.
Conversión de un AFN a un AFD.Vikky Moscoso
 
Tipos de Autómatas 
Tipos de Autómatas Tipos de Autómatas 
Tipos de Autómatas yelizabeth_20
 
Diagramas de flujo
Diagramas de flujoDiagramas de flujo
Diagramas de flujoCBISOE
 

What's hot (20)

Busqueda por profundidad iterativa
Busqueda por profundidad iterativaBusqueda por profundidad iterativa
Busqueda por profundidad iterativa
 
Metodo de busqueda
Metodo de busquedaMetodo de busqueda
Metodo de busqueda
 
Método de Búsqueda Hash
Método de Búsqueda HashMétodo de Búsqueda Hash
Método de Búsqueda Hash
 
Ejercicios parcial1
Ejercicios parcial1Ejercicios parcial1
Ejercicios parcial1
 
Agentes inteligentes
Agentes inteligentesAgentes inteligentes
Agentes inteligentes
 
Algoritmo de ordenamiento: Heap Sort
Algoritmo de ordenamiento: Heap SortAlgoritmo de ordenamiento: Heap Sort
Algoritmo de ordenamiento: Heap Sort
 
Capítulo 16 (Diseño fisico y refinación de la Base de Datos)
Capítulo 16 (Diseño fisico y refinación de la Base de Datos)Capítulo 16 (Diseño fisico y refinación de la Base de Datos)
Capítulo 16 (Diseño fisico y refinación de la Base de Datos)
 
Unidad 2 clases y objetos
Unidad 2 clases y objetosUnidad 2 clases y objetos
Unidad 2 clases y objetos
 
Informe analisis de algoritmos (mitad de cuadrado)
Informe analisis de algoritmos (mitad de cuadrado)Informe analisis de algoritmos (mitad de cuadrado)
Informe analisis de algoritmos (mitad de cuadrado)
 
Diagrama entidad-relacion normalización
Diagrama entidad-relacion normalizaciónDiagrama entidad-relacion normalización
Diagrama entidad-relacion normalización
 
Uml
UmlUml
Uml
 
Modelo relacional y reglas de integridad
Modelo relacional y reglas de integridadModelo relacional y reglas de integridad
Modelo relacional y reglas de integridad
 
Conversión de un AFN a un AFD.
Conversión de un AFN a un AFD.Conversión de un AFN a un AFD.
Conversión de un AFN a un AFD.
 
Tipos de Autómatas 
Tipos de Autómatas Tipos de Autómatas 
Tipos de Autómatas 
 
Metodos de ordenamiento
Metodos de ordenamientoMetodos de ordenamiento
Metodos de ordenamiento
 
Diagramas de flujo
Diagramas de flujoDiagramas de flujo
Diagramas de flujo
 
34655909 javascript
34655909 javascript34655909 javascript
34655909 javascript
 
6 Curso de POO en Java - clases y objetos
6  Curso de POO en Java - clases y objetos6  Curso de POO en Java - clases y objetos
6 Curso de POO en Java - clases y objetos
 
Cuestionario diagrama de clases
Cuestionario diagrama de clasesCuestionario diagrama de clases
Cuestionario diagrama de clases
 
Tipos de Datos Abstractos (TDA)
Tipos de Datos Abstractos (TDA)Tipos de Datos Abstractos (TDA)
Tipos de Datos Abstractos (TDA)
 

Viewers also liked

Algoritmo genetico
Algoritmo geneticoAlgoritmo genetico
Algoritmo geneticoMarco Gámez
 
Trabajo algoritmo genetico uba
Trabajo algoritmo genetico uba Trabajo algoritmo genetico uba
Trabajo algoritmo genetico uba yucci2323
 
Selection in Evolutionary Algorithm
Selection in Evolutionary AlgorithmSelection in Evolutionary Algorithm
Selection in Evolutionary AlgorithmRiyad Parvez
 
Int. a la Computación Evolutiva - Informe para cursada
Int. a la Computación Evolutiva - Informe para cursadaInt. a la Computación Evolutiva - Informe para cursada
Int. a la Computación Evolutiva - Informe para cursadamartinp
 
Logica Difusa Introduccion
Logica Difusa IntroduccionLogica Difusa Introduccion
Logica Difusa IntroduccionESCOM
 
РОЗ’ЯСНЕННЯ щодо застосування окремих положень Закону України «Про запобіганн...
РОЗ’ЯСНЕННЯ щодо застосування окремих положень Закону України «Про запобіганн...РОЗ’ЯСНЕННЯ щодо застосування окремих положень Закону України «Про запобіганн...
РОЗ’ЯСНЕННЯ щодо застосування окремих положень Закону України «Про запобіганн...Olexiy Ladyka
 

Viewers also liked (7)

Algoritmo genetico
Algoritmo geneticoAlgoritmo genetico
Algoritmo genetico
 
Trabajo algoritmo genetico uba
Trabajo algoritmo genetico uba Trabajo algoritmo genetico uba
Trabajo algoritmo genetico uba
 
Selection in Evolutionary Algorithm
Selection in Evolutionary AlgorithmSelection in Evolutionary Algorithm
Selection in Evolutionary Algorithm
 
A G's
A G'sA G's
A G's
 
Int. a la Computación Evolutiva - Informe para cursada
Int. a la Computación Evolutiva - Informe para cursadaInt. a la Computación Evolutiva - Informe para cursada
Int. a la Computación Evolutiva - Informe para cursada
 
Logica Difusa Introduccion
Logica Difusa IntroduccionLogica Difusa Introduccion
Logica Difusa Introduccion
 
РОЗ’ЯСНЕННЯ щодо застосування окремих положень Закону України «Про запобіганн...
РОЗ’ЯСНЕННЯ щодо застосування окремих положень Закону України «Про запобіганн...РОЗ’ЯСНЕННЯ щодо застосування окремих положень Закону України «Про запобіганн...
РОЗ’ЯСНЕННЯ щодо застосування окремих положень Закону України «Про запобіганн...
 

Similar to Apunte Algoritmos Geneticos

Algoritmo genetico
Algoritmo geneticoAlgoritmo genetico
Algoritmo geneticoRufino meri?
 
Algoritmo genetico
Algoritmo geneticoAlgoritmo genetico
Algoritmo geneticoVane Erraez
 
Algoritmos geneticos mundial
Algoritmos geneticos mundialAlgoritmos geneticos mundial
Algoritmos geneticos mundialJairo Banda
 
Trabajo+completo+de+inteligencia+algoritmo+genetico
Trabajo+completo+de+inteligencia+algoritmo+geneticoTrabajo+completo+de+inteligencia+algoritmo+genetico
Trabajo+completo+de+inteligencia+algoritmo+geneticoRufino meri?
 
computacion Evolutiva
computacion Evolutivacomputacion Evolutiva
computacion Evolutivaguest590a846
 
Introducción a los Algoritmos Genéticos
Introducción  a los Algoritmos GenéticosIntroducción  a los Algoritmos Genéticos
Introducción a los Algoritmos Genéticosdrk28
 
Artículo predicción mundial 2014 algoritmos geneticos
Artículo predicción mundial 2014   algoritmos geneticosArtículo predicción mundial 2014   algoritmos geneticos
Artículo predicción mundial 2014 algoritmos geneticosRichar León
 
Algoritmos Genéticos_Inteligencia Artificial
Algoritmos Genéticos_Inteligencia ArtificialAlgoritmos Genéticos_Inteligencia Artificial
Algoritmos Genéticos_Inteligencia ArtificialGabriela_Rodriguez
 
Algoritmos Geneticos - Teoria.pdf
Algoritmos Geneticos - Teoria.pdfAlgoritmos Geneticos - Teoria.pdf
Algoritmos Geneticos - Teoria.pdfCastañeda Samanamu
 

Similar to Apunte Algoritmos Geneticos (20)

Algoritmo genetico
Algoritmo geneticoAlgoritmo genetico
Algoritmo genetico
 
Algoritmo genetico
Algoritmo geneticoAlgoritmo genetico
Algoritmo genetico
 
ALGORITMO GENETICO - II.pptx
ALGORITMO GENETICO - II.pptxALGORITMO GENETICO - II.pptx
ALGORITMO GENETICO - II.pptx
 
Algoritmos geneticos mundial
Algoritmos geneticos mundialAlgoritmos geneticos mundial
Algoritmos geneticos mundial
 
Trabajo+completo+de+inteligencia+algoritmo+genetico
Trabajo+completo+de+inteligencia+algoritmo+geneticoTrabajo+completo+de+inteligencia+algoritmo+genetico
Trabajo+completo+de+inteligencia+algoritmo+genetico
 
Resumen 2 Unidad
Resumen 2 UnidadResumen 2 Unidad
Resumen 2 Unidad
 
Resumen 2 Unidad
Resumen 2 UnidadResumen 2 Unidad
Resumen 2 Unidad
 
Resumen 2 Unidad
Resumen 2 UnidadResumen 2 Unidad
Resumen 2 Unidad
 
Resumen 2 Unidad
Resumen 2 UnidadResumen 2 Unidad
Resumen 2 Unidad
 
computacion Evolutiva
computacion Evolutivacomputacion Evolutiva
computacion Evolutiva
 
Resumen 2 Unidad
Resumen 2 UnidadResumen 2 Unidad
Resumen 2 Unidad
 
Resumen 2 Unidad
Resumen 2 UnidadResumen 2 Unidad
Resumen 2 Unidad
 
Resumen 2 Unidad
Resumen 2 UnidadResumen 2 Unidad
Resumen 2 Unidad
 
Resumen 2 Unidad
Resumen 2 UnidadResumen 2 Unidad
Resumen 2 Unidad
 
Introducción a los Algoritmos Genéticos
Introducción  a los Algoritmos GenéticosIntroducción  a los Algoritmos Genéticos
Introducción a los Algoritmos Genéticos
 
Artículo predicción mundial 2014 algoritmos geneticos
Artículo predicción mundial 2014   algoritmos geneticosArtículo predicción mundial 2014   algoritmos geneticos
Artículo predicción mundial 2014 algoritmos geneticos
 
A Geneticos
A GeneticosA Geneticos
A Geneticos
 
Algoritmos Genéticos_Inteligencia Artificial
Algoritmos Genéticos_Inteligencia ArtificialAlgoritmos Genéticos_Inteligencia Artificial
Algoritmos Genéticos_Inteligencia Artificial
 
Algoritmos genéticos 2 s lun 30 sep-13
Algoritmos genéticos 2 s lun 30 sep-13Algoritmos genéticos 2 s lun 30 sep-13
Algoritmos genéticos 2 s lun 30 sep-13
 
Algoritmos Geneticos - Teoria.pdf
Algoritmos Geneticos - Teoria.pdfAlgoritmos Geneticos - Teoria.pdf
Algoritmos Geneticos - Teoria.pdf
 

More from ESCOM

redes neuronales tipo Som
redes neuronales tipo Somredes neuronales tipo Som
redes neuronales tipo SomESCOM
 
redes neuronales Som
redes neuronales Somredes neuronales Som
redes neuronales SomESCOM
 
redes neuronales Som Slides
redes neuronales Som Slidesredes neuronales Som Slides
redes neuronales Som SlidesESCOM
 
red neuronal Som Net
red neuronal Som Netred neuronal Som Net
red neuronal Som NetESCOM
 
Self Organinising neural networks
Self Organinising  neural networksSelf Organinising  neural networks
Self Organinising neural networksESCOM
 
redes neuronales Kohonen
redes neuronales Kohonenredes neuronales Kohonen
redes neuronales KohonenESCOM
 
Teoria Resonancia Adaptativa
Teoria Resonancia AdaptativaTeoria Resonancia Adaptativa
Teoria Resonancia AdaptativaESCOM
 
ejemplo red neuronal Art1
ejemplo red neuronal Art1ejemplo red neuronal Art1
ejemplo red neuronal Art1ESCOM
 
redes neuronales tipo Art3
redes neuronales tipo Art3redes neuronales tipo Art3
redes neuronales tipo Art3ESCOM
 
Art2
Art2Art2
Art2ESCOM
 
Redes neuronales tipo Art
Redes neuronales tipo ArtRedes neuronales tipo Art
Redes neuronales tipo ArtESCOM
 
Neocognitron
NeocognitronNeocognitron
NeocognitronESCOM
 
Neocognitron
NeocognitronNeocognitron
NeocognitronESCOM
 
Neocognitron
NeocognitronNeocognitron
NeocognitronESCOM
 
Fukushima Cognitron
Fukushima CognitronFukushima Cognitron
Fukushima CognitronESCOM
 
Counterpropagation NETWORK
Counterpropagation NETWORKCounterpropagation NETWORK
Counterpropagation NETWORKESCOM
 
Counterpropagation NETWORK
Counterpropagation NETWORKCounterpropagation NETWORK
Counterpropagation NETWORKESCOM
 
Counterpropagation
CounterpropagationCounterpropagation
CounterpropagationESCOM
 
Teoría de Resonancia Adaptativa Art2 ARTMAP
Teoría de Resonancia Adaptativa Art2 ARTMAPTeoría de Resonancia Adaptativa Art2 ARTMAP
Teoría de Resonancia Adaptativa Art2 ARTMAPESCOM
 
Teoría de Resonancia Adaptativa ART1
Teoría de Resonancia Adaptativa ART1Teoría de Resonancia Adaptativa ART1
Teoría de Resonancia Adaptativa ART1ESCOM
 

More from ESCOM (20)

redes neuronales tipo Som
redes neuronales tipo Somredes neuronales tipo Som
redes neuronales tipo Som
 
redes neuronales Som
redes neuronales Somredes neuronales Som
redes neuronales Som
 
redes neuronales Som Slides
redes neuronales Som Slidesredes neuronales Som Slides
redes neuronales Som Slides
 
red neuronal Som Net
red neuronal Som Netred neuronal Som Net
red neuronal Som Net
 
Self Organinising neural networks
Self Organinising  neural networksSelf Organinising  neural networks
Self Organinising neural networks
 
redes neuronales Kohonen
redes neuronales Kohonenredes neuronales Kohonen
redes neuronales Kohonen
 
Teoria Resonancia Adaptativa
Teoria Resonancia AdaptativaTeoria Resonancia Adaptativa
Teoria Resonancia Adaptativa
 
ejemplo red neuronal Art1
ejemplo red neuronal Art1ejemplo red neuronal Art1
ejemplo red neuronal Art1
 
redes neuronales tipo Art3
redes neuronales tipo Art3redes neuronales tipo Art3
redes neuronales tipo Art3
 
Art2
Art2Art2
Art2
 
Redes neuronales tipo Art
Redes neuronales tipo ArtRedes neuronales tipo Art
Redes neuronales tipo Art
 
Neocognitron
NeocognitronNeocognitron
Neocognitron
 
Neocognitron
NeocognitronNeocognitron
Neocognitron
 
Neocognitron
NeocognitronNeocognitron
Neocognitron
 
Fukushima Cognitron
Fukushima CognitronFukushima Cognitron
Fukushima Cognitron
 
Counterpropagation NETWORK
Counterpropagation NETWORKCounterpropagation NETWORK
Counterpropagation NETWORK
 
Counterpropagation NETWORK
Counterpropagation NETWORKCounterpropagation NETWORK
Counterpropagation NETWORK
 
Counterpropagation
CounterpropagationCounterpropagation
Counterpropagation
 
Teoría de Resonancia Adaptativa Art2 ARTMAP
Teoría de Resonancia Adaptativa Art2 ARTMAPTeoría de Resonancia Adaptativa Art2 ARTMAP
Teoría de Resonancia Adaptativa Art2 ARTMAP
 
Teoría de Resonancia Adaptativa ART1
Teoría de Resonancia Adaptativa ART1Teoría de Resonancia Adaptativa ART1
Teoría de Resonancia Adaptativa ART1
 

Recently uploaded

Ejemplo de trabajo de TIC´s CON VARIAS OPCIONES DE LAS TAREAS
Ejemplo de trabajo de TIC´s CON VARIAS OPCIONES DE LAS TAREASEjemplo de trabajo de TIC´s CON VARIAS OPCIONES DE LAS TAREAS
Ejemplo de trabajo de TIC´s CON VARIAS OPCIONES DE LAS TAREASJavier Sanchez
 
TECNOLOGÍA EDUCATIVA, USO DE LAS TIC.pptx
TECNOLOGÍA EDUCATIVA, USO DE LAS TIC.pptxTECNOLOGÍA EDUCATIVA, USO DE LAS TIC.pptx
TECNOLOGÍA EDUCATIVA, USO DE LAS TIC.pptxFranciscoCruz296518
 
EL BRILLO DEL ECLIPSE (CUENTO LITERARIO). Autor y diseñador JAVIER SOLIS NOYOLA
EL BRILLO DEL ECLIPSE (CUENTO LITERARIO). Autor y diseñador JAVIER SOLIS NOYOLAEL BRILLO DEL ECLIPSE (CUENTO LITERARIO). Autor y diseñador JAVIER SOLIS NOYOLA
EL BRILLO DEL ECLIPSE (CUENTO LITERARIO). Autor y diseñador JAVIER SOLIS NOYOLAJAVIER SOLIS NOYOLA
 
Tema 4 Rocas sedimentarias, características y clasificación
Tema 4 Rocas sedimentarias, características y clasificaciónTema 4 Rocas sedimentarias, características y clasificación
Tema 4 Rocas sedimentarias, características y clasificaciónIES Vicent Andres Estelles
 
21 MARZO DIA INTERNACIONAL DOS BOSQUES.pdf
21 MARZO DIA INTERNACIONAL DOS BOSQUES.pdf21 MARZO DIA INTERNACIONAL DOS BOSQUES.pdf
21 MARZO DIA INTERNACIONAL DOS BOSQUES.pdfceeabarcia
 
ficha de aplicacion para estudiantes El agua para niños de primaria
ficha de aplicacion para estudiantes El agua para niños de primariaficha de aplicacion para estudiantes El agua para niños de primaria
ficha de aplicacion para estudiantes El agua para niños de primariamichel carlos Capillo Dominguez
 
PPT Protocolo de desregulación emocional.pptx
PPT Protocolo de desregulación emocional.pptxPPT Protocolo de desregulación emocional.pptx
PPT Protocolo de desregulación emocional.pptxKarenSepulveda23
 
U2_EA2_descargable TICS PRESENCIAL 2.pdf
U2_EA2_descargable TICS PRESENCIAL 2.pdfU2_EA2_descargable TICS PRESENCIAL 2.pdf
U2_EA2_descargable TICS PRESENCIAL 2.pdfJavier Correa
 
5°-CARPETA PEDAGÓGICA 2024-MAESTRAS DE PRIMARIA PERÚ-978387435.doc
5°-CARPETA PEDAGÓGICA 2024-MAESTRAS DE PRIMARIA PERÚ-978387435.doc5°-CARPETA PEDAGÓGICA 2024-MAESTRAS DE PRIMARIA PERÚ-978387435.doc
5°-CARPETA PEDAGÓGICA 2024-MAESTRAS DE PRIMARIA PERÚ-978387435.docGLADYSPASTOR
 
Anuncio de Remitido Colegio SEK a la comunidad pública
Anuncio de Remitido Colegio SEK a la comunidad públicaAnuncio de Remitido Colegio SEK a la comunidad pública
Anuncio de Remitido Colegio SEK a la comunidad públicaIvannaMaciasAlvarez
 
la forma de los objetos expresión gráfica preescolar
la forma de los objetos expresión gráfica preescolarla forma de los objetos expresión gráfica preescolar
la forma de los objetos expresión gráfica preescolarCa Ut
 
Presentación contribuciones socioeconómicas del SUPV 2023
Presentación contribuciones socioeconómicas del SUPV 2023Presentación contribuciones socioeconómicas del SUPV 2023
Presentación contribuciones socioeconómicas del SUPV 2023Ivie
 
La poesía del encarcelamiento de Raúl Zurita en el aula: una propuesta didáctica
La poesía del encarcelamiento de Raúl Zurita en el aula: una propuesta didácticaLa poesía del encarcelamiento de Raúl Zurita en el aula: una propuesta didáctica
La poesía del encarcelamiento de Raúl Zurita en el aula: una propuesta didácticaIGNACIO BALLESTER PARDO
 
Tecnología educativa en la era actual .pptx
Tecnología educativa en la era actual .pptxTecnología educativa en la era actual .pptx
Tecnología educativa en la era actual .pptxJulioSantin2
 
U2_EA1_descargable TIC 2 SEM VIR PRE.pdf
U2_EA1_descargable TIC 2 SEM VIR PRE.pdfU2_EA1_descargable TIC 2 SEM VIR PRE.pdf
U2_EA1_descargable TIC 2 SEM VIR PRE.pdfJavier Correa
 
Presentación del tema: tecnología educativa
Presentación del tema: tecnología educativaPresentación del tema: tecnología educativa
Presentación del tema: tecnología educativaricardoruizaleman
 

Recently uploaded (20)

Ejemplo de trabajo de TIC´s CON VARIAS OPCIONES DE LAS TAREAS
Ejemplo de trabajo de TIC´s CON VARIAS OPCIONES DE LAS TAREASEjemplo de trabajo de TIC´s CON VARIAS OPCIONES DE LAS TAREAS
Ejemplo de trabajo de TIC´s CON VARIAS OPCIONES DE LAS TAREAS
 
Tema 6.- La identidad visual corporativa y el naming.pdf
Tema 6.- La identidad visual corporativa y el naming.pdfTema 6.- La identidad visual corporativa y el naming.pdf
Tema 6.- La identidad visual corporativa y el naming.pdf
 
TECNOLOGÍA EDUCATIVA, USO DE LAS TIC.pptx
TECNOLOGÍA EDUCATIVA, USO DE LAS TIC.pptxTECNOLOGÍA EDUCATIVA, USO DE LAS TIC.pptx
TECNOLOGÍA EDUCATIVA, USO DE LAS TIC.pptx
 
EL BRILLO DEL ECLIPSE (CUENTO LITERARIO). Autor y diseñador JAVIER SOLIS NOYOLA
EL BRILLO DEL ECLIPSE (CUENTO LITERARIO). Autor y diseñador JAVIER SOLIS NOYOLAEL BRILLO DEL ECLIPSE (CUENTO LITERARIO). Autor y diseñador JAVIER SOLIS NOYOLA
EL BRILLO DEL ECLIPSE (CUENTO LITERARIO). Autor y diseñador JAVIER SOLIS NOYOLA
 
Tema 4 Rocas sedimentarias, características y clasificación
Tema 4 Rocas sedimentarias, características y clasificaciónTema 4 Rocas sedimentarias, características y clasificación
Tema 4 Rocas sedimentarias, características y clasificación
 
21 MARZO DIA INTERNACIONAL DOS BOSQUES.pdf
21 MARZO DIA INTERNACIONAL DOS BOSQUES.pdf21 MARZO DIA INTERNACIONAL DOS BOSQUES.pdf
21 MARZO DIA INTERNACIONAL DOS BOSQUES.pdf
 
ficha de aplicacion para estudiantes El agua para niños de primaria
ficha de aplicacion para estudiantes El agua para niños de primariaficha de aplicacion para estudiantes El agua para niños de primaria
ficha de aplicacion para estudiantes El agua para niños de primaria
 
PPT Protocolo de desregulación emocional.pptx
PPT Protocolo de desregulación emocional.pptxPPT Protocolo de desregulación emocional.pptx
PPT Protocolo de desregulación emocional.pptx
 
Tema 5.- BASES DE DATOS Y GESTIÓN DE LA INF. PARA EL MARKETING.pdf
Tema 5.- BASES DE DATOS Y GESTIÓN DE LA INF. PARA EL MARKETING.pdfTema 5.- BASES DE DATOS Y GESTIÓN DE LA INF. PARA EL MARKETING.pdf
Tema 5.- BASES DE DATOS Y GESTIÓN DE LA INF. PARA EL MARKETING.pdf
 
Sesión de clase ES: Adoración sin fin...
Sesión de clase ES: Adoración sin fin...Sesión de clase ES: Adoración sin fin...
Sesión de clase ES: Adoración sin fin...
 
U2_EA2_descargable TICS PRESENCIAL 2.pdf
U2_EA2_descargable TICS PRESENCIAL 2.pdfU2_EA2_descargable TICS PRESENCIAL 2.pdf
U2_EA2_descargable TICS PRESENCIAL 2.pdf
 
5°-CARPETA PEDAGÓGICA 2024-MAESTRAS DE PRIMARIA PERÚ-978387435.doc
5°-CARPETA PEDAGÓGICA 2024-MAESTRAS DE PRIMARIA PERÚ-978387435.doc5°-CARPETA PEDAGÓGICA 2024-MAESTRAS DE PRIMARIA PERÚ-978387435.doc
5°-CARPETA PEDAGÓGICA 2024-MAESTRAS DE PRIMARIA PERÚ-978387435.doc
 
Anuncio de Remitido Colegio SEK a la comunidad pública
Anuncio de Remitido Colegio SEK a la comunidad públicaAnuncio de Remitido Colegio SEK a la comunidad pública
Anuncio de Remitido Colegio SEK a la comunidad pública
 
Conducta ética en investigación científica.pdf
Conducta ética en investigación científica.pdfConducta ética en investigación científica.pdf
Conducta ética en investigación científica.pdf
 
la forma de los objetos expresión gráfica preescolar
la forma de los objetos expresión gráfica preescolarla forma de los objetos expresión gráfica preescolar
la forma de los objetos expresión gráfica preescolar
 
Presentación contribuciones socioeconómicas del SUPV 2023
Presentación contribuciones socioeconómicas del SUPV 2023Presentación contribuciones socioeconómicas del SUPV 2023
Presentación contribuciones socioeconómicas del SUPV 2023
 
La poesía del encarcelamiento de Raúl Zurita en el aula: una propuesta didáctica
La poesía del encarcelamiento de Raúl Zurita en el aula: una propuesta didácticaLa poesía del encarcelamiento de Raúl Zurita en el aula: una propuesta didáctica
La poesía del encarcelamiento de Raúl Zurita en el aula: una propuesta didáctica
 
Tecnología educativa en la era actual .pptx
Tecnología educativa en la era actual .pptxTecnología educativa en la era actual .pptx
Tecnología educativa en la era actual .pptx
 
U2_EA1_descargable TIC 2 SEM VIR PRE.pdf
U2_EA1_descargable TIC 2 SEM VIR PRE.pdfU2_EA1_descargable TIC 2 SEM VIR PRE.pdf
U2_EA1_descargable TIC 2 SEM VIR PRE.pdf
 
Presentación del tema: tecnología educativa
Presentación del tema: tecnología educativaPresentación del tema: tecnología educativa
Presentación del tema: tecnología educativa
 

Apunte Algoritmos Geneticos

  • 1. CAPÍTULO I NOCIONES PREELIMINARES Los Algoritmos Genéticos (AG) son métodos adaptativos que pueden usarse para resolver problemas de búsqueda y optimización. Están basados en el proceso genético de los organismos vivos. A lo largo de las generaciones, las poblaciones evolucionan en la naturaleza de acorde con los principios de la selección natural y la supervivencia de los más fuertes, postulados por Darwin. Por imitación de este proceso, los Algoritmos Genéticos son capaces de ir creando soluciones para problemas del mundo real. La evolución de dichas soluciones hacia valores óptimos del problema depende en buena medida de una adecuada codificación de las mismas. Los principios básicos de los Algoritmos Genéticos fueron establecidos por Holland, y se encuentran bien descritos en varios textos de Goldberg, Davis, Michalewicz, Reeves. En la naturaleza los individuos de una población compiten entre sí en la búsqueda de recursos tales como comida, agua y refugio. Incluso los miembros de una misma especie compiten a menudo en la búsqueda de un compañero. Aquellos individuos que tienen más éxito en sobrevivir y en atraer compañeros tienen mayor probabilidad de generar un gran número de descendientes. Por el contrario individuos poco dotados producirán un menor número de descendientes. Esto significa que los genes de los individuos mejor adaptados se propagarán en sucesivas generaciones hacia un número de individuos creciente. La combinación de buenas características provenientes de diferentes ancestros, puede a veces producir descendientes “súper individuos”, cuya adaptación es mucho mayor que la de cualquiera de sus ancestros. De esta manera, las especies evolucionan logrando características cada vez mejor adaptadas al entorno en el que viven. Los Algoritmos Genéticos usan una analogía directa con el comportamiento natural. Trabajan con una población de individuos, cada uno de los cuales representa una solución factible a un problema dado. A cada individuo se le asigna un valor o puntuación, relacionado con la bondad de dicha solución. En la naturaleza esto equivaldría al grado de efectividad de un organismo para competir por unos determinados recursos. Cuanto mayor sea la adaptación de un individuo al problema, mayor será la probabilidad de que el mismo sea seleccionado para reproducirse, cruzando su material genético con otro individuo seleccionado de igual forma. Este cruce producirá nuevos individuos, descendientes de los anteriores, los cuales comparten algunas de las características de sus padres. Cuanto menor sea la adaptación de un individuo, menor será la probabilidad de que dicho individuo sea seleccionado para la reproducción, y por tanto de que su material genético se propague en sucesivas generaciones. De esta manera se produce una nueva población de posibles soluciones, la cual reemplaza a la anterior y verifica la interesante propiedad de que contiene una mayor proporción de buenas características en comparación con la población anterior. Así a lo largo de las generaciones las buenas características se propagan a través de la población.
  • 2. Favoreciendo el cruce de los individuos mejor adaptados, van siendo exploradas las áreas más prometedoras del espacio de búsqueda. Si el Algoritmo Genético ha sido bien diseñado, la población convergerá hacia una solución óptima del problema. El poder de los Algoritmos Genéticos proviene del hecho de que se trata de una técnica robusta, y pueden tratar con éxito una gran variedad de problemas provenientes de diferentes áreas, incluyendo aquellos en los que otros métodos encuentran dificultades. Si bien no se garantiza que el Algoritmo Genético encuentre la solución óptima del problema, existe evidencia empírica de que se encuentran soluciones de un nivel aceptable, en un tiempo competitivo con el resto de algoritmos de optimización combinatoria. En el caso de que existan técnicas especializadas para resolver un determinado problema, lo más probable es que superen al Algoritmo Genético, tanto en rapidez como en eficacia. El gran campo de aplicación de los Algoritmos Genéticos se relaciona con aquellos problemas para los cuales no existen técnicas especializadas. Incluso en el caso en que dichas técnicas existan, y funcionen bien, pueden efectuarse mejoras de las mismas haciendo algoritmos híbridos entre éstas y los Algoritmos Genéticos.
  • 3. CAPÌTULO II EL ALGORITMO GENÉTICO SIMPLE El Algoritmo Genético Simple, también denominado “canónico” se representa en la figura 2.1. Como se verá a continuación, se necesita una codificación o representación del problema, que resulte adecuada al mismo. Además se requiere una función de ajuste o adaptación al problema, la cual asigna un número real a cada posible solución codificada. Durante la ejecución del algoritmo, los padres deben ser seleccionados para la reproducción, a continuación dichos padres seleccionados se cruzarán generando dos hijos, sobre cada uno de los cuales actuará un operador de mutación. El resultado de la combinación de las anteriores funciones será un conjunto de individuos (posibles soluciones al problema) los cuales en la evolución del Algoritmo Genético formarán parte de la siguiente población. Figura 2.1 Pseudo código del Algoritmo Genético Simple Codificación Se supone que los individuos (posibles soluciones del problema), pueden representarse como un conjunto de parámetros denominados “genes”, los cuales agrupados forman una cadena de valores o “cromosoma”. Si bien el alfabeto utilizado para representar los individuos no debe necesariamente estar constituido por {0, l}, buena parte de la teoría en la que se fundamentan los Algoritmos Genéticos utiliza dicho alfabeto. En términos biológicos, el conjunto de parámetros representando un cromosoma particular se denomina “fenotipo”. El fenotipo contiene la información requerida para construir un organismo, el cual se refiere como “genotipo”. Los mismos términos se utilizan en el
  • 4. campo de los Algoritmos Genéticos. La adaptación al problema de un individuo depende de la evaluación del genotipo. Esta última puede inferirse a partir del fenotipo, es decir puede ser computada a partir del cromosoma, usando la función de evaluación. La función de adaptación debe ser diseñada para cada problema de manera específica. Dado un cromosoma particular, la función de adaptación le asigna un número real, que se supone refleja el nivel de adaptación al problema del individuo representado por el cromosoma. Durante la fase reproductiva se seleccionan los individuos de la población para cruzarse y producir descendientes que constituirán, una vez mutados, la siguiente generación de individuos. La selección de padres se efectúa al azar usando un procedimiento que favorezca a los individuos mejor adaptados, ya que a cada individuo se le asigna una probabilidad de ser seleccionado que es proporcional a su función de adaptación. Este procedimiento se dice que está basado en la ruleta sesgada. Según dicho esquema, los individuos bien adaptados se escogerán probablemente varias veces por generación, mientras que los pobremente adaptados al problema no se escogerán más que de vez en cuando. Una vez seleccionados dos padres, sus cromosomas se combinan, utilizando habitualmente los operadores de cruce y mutación. Las formas básicas de dichos operadores se describen a continuación. El operador de cruce toma dos padres seleccionados y corta sus cadenas de cromosomas en una posición escogida al azar, para producir dos subcadenas iniciales y dos subcadenas finales. Después se intercambian las subcadenas finales, produciéndose dos nuevos cromosomas completos. Esto se muestra en la figura 2.2. Ambos descendientes heredan genes de cada uno de los padres. Este operador se conoce como operador de cruce basado en un punto. Figura 2.2. Operador de cruce basado en un punto Habitualmente el operador de cruce no se aplica a todos los pares de individuos que han sido seleccionados para emparejarse, sino que se aplica de manera aleatoria, normalmente con una probabilidad comprendida entre 0.5 y 1.0. En el caso en que el operador de cruce no se aplique, la descendencia se obtiene simplemente duplicando los padres.
  • 5. El operador de mutación se aplica a cada hijo de manera individual, y consiste en la alteración aleatoria (normalmente con probabilidad pequeña) de cada gen componente del cromosoma. La figura 2.3 muestra la mutación del quinto gen del cromosoma. Figura 2.3. Operador de mutación Si bien puede en principio pensarse que el operador de cruce es más importante que el operador de mutación, ya que proporciona una exploración rápida del espacio de búsqueda, éste último asegura que ningún punto del espacio de búsqueda tenga una probabilidad cero de ser examinado, y es de capital importancia para asegurar la convergencia de los Algoritmos Genéticos. Para criterios prácticos, es muy útil la definición de convergencia introducida en este campo por De Jong. Si el Algoritmo Genético ha sido correctamente implementado, la población evolucionará a lo largo de las generaciones sucesivas de tal manera que la adaptación media extendida a todos los individuos de la población, así como la adaptación del mejor individuo se irán incrementando hacia el óptimo global. El concepto de convergencia está relacionado con la progresión hacia la uniformidad: un gen ha convergido cuando al menos el 95 % de los individuos de la población comparten el mismo valor para dicho gen. Se dice que la población converge cuando todos los genes han convergido. Se puede generalizar dicha definición al caso en que al menos un poco de los individuos de la población hayan convergido. La figura 2.4 muestra como varía la adaptación media y la mejor adaptación en un Algoritmo Genético Simple típico. Figura 2.4. Adaptación media y mejor adaptación en un Algoritmo Genético simple
  • 6. A medida que el número de generaciones aumenta, es más probable que la adaptación media se aproxime a la del mejor individuo. Ejemplo Como ilustración de los diferentes componentes del Algoritmo Genético Simple, supóngase el problema adaptado de Goldberg de encontrar el máximo de la función f(z) = x’ para z = {1,2,...,32}. Evidentemente para lograr dicho óptimo, bastaría actuar por búsqueda exhaustiva, dada la baja cardinalidad del espacio de búsqueda. Se trata por tanto de un mero ejemplo con el que se pretende ilustrar el comportamiento del algoritmo anteriormente descrito. Consultando el pseudo código de la figura 2.1, se ve que el primer paso a efectuar consiste en determinar el tamaño de la población inicial, para después obtener dicha población al azar y computar la función de evaluación de cada uno de sus individuos. Suponiendo que el alfabeto utilizado para codificar los individuos esté constituido por {0, 1}, se necesitarán cadenas de longitud 5 para representar los 32 puntos del espacio de búsqueda. En la tabla 2.1 están representados los 4 individuos que constituyen la población inicial, junto con su función de adaptación al problema, así como la probabilidad de que cada uno de dichos individuos sea seleccionado – según el modelo de ruleta sesgada – para emparejarse. Volviendo a consultar el pseudo código expresado en la figura 2.1, se puede ver que el siguiente paso consiste en la selección de 2 parejas de individuos. Tabla 2.1 Población inicial de la simulación efectuada a mano correspondiente al Algoritmo Genético simple. Para ello es suficiente con obtener 4 números reales provenientes de una distribución de probabilidad uniforme en el intervalo [0, 1), y compararlos con la última columna de la Tabla 2.l. Así por ejemplo, supóngase que dichos 4 números son 0.58, 0.84, 0.11 y 0.43. Esto significa que los individuos seleccionados para el cruce fueron el individuo 2 junto con el individuo 4, así como el individuo 1 junto con el individuo 2.
  • 7. Para seguir con el Algoritmo Genético Simple, se necesita determinar la probabilidad de cruce p. Supóngase que p = 0.8. Valiéndose al igual que antes de 2 números provenientes de la distribución uniforme para este caso, se determinará si los emparejamientos anteriores se llevan a cabo. Admítase, por ejemplo, que los dos números extraídos sean menores que 0.8, decidiéndose por tanto efectuar el cruce entre las dos parejas. Para ello se escogerá un número al azar entre l y L – 1 (siendo L la longitud de la cadena utilizada para representar el individuo). Nótese que la restricción impuesta al escoger el número entre 1 y L – l, y no L, se realiza con la finalidad de que los descendientes no coincidan con los padres. Supóngase, tal y como se indica en la tabla 2.2, que los puntos de cruce resulten ser 2 y 3. De esta manera se obtendrían los 4 descendientes descritos en la tercera columna de la tabla 2.2. A continuación siguiendo el seudo código de la figura 2.1, se mutaría con una probabilidad p, cercana a cero, cada uno de los bits de las cuatro cadenas de individuos. En este caso se supone que el único bit mutado corresponde al primer gen del tercer individuo. En las dos últimas columnas se pueden consultar los valores de los individuos, así como las funciones de adaptación correspondientes. Como puede observarse, tanto el mejor individuo como la función de adaptación media han mejorado sustancialmente al compararlos con los resultados de la Tabla 2.1. Tabla 2.2. Población en el tiempo 1, proveniente de efectuar los operadores de cruce y mutación sobre los individuos expresados en la tabla 2.1, los cuales constituyen la población en el tiempo 0.
  • 8. CAPÍTULO III EXTENSIONES Y MODIFICACIONES DEL ALGORITMO GENÉTICO SIMPLE En este capítulo se introducen otras técnicas referentes a la población, función objetivo, selección, cruce y mutación. Población Tamaño de la población Una cuestión que puede plantearse es la relacionada con el tamaño idóneo de la población. Parece intuitivo que las poblaciones pequeñas corren el riesgo de no cubrir adecuadamente el espacio de búsqueda, mientras que el trabajar con poblaciones de gran tamaño puede acarrear problemas relacionados con el excesivo costo computacional. Goldberg efectuó un estudio teórico, obteniendo como conclusión que el tamaño óptimo de la población para cadenas de longitud I, con codificación binaria, crece exponencialmente con el tamaño de la cadena. Este resultado traería como consecuencia que la aplicabilidad de los Algoritmos Genéticos en problemas reales sería muy limitada, ya que resultarían no competitivos con otros métodos de optimización combinatoria. Alander, basándose en evidencia empírica sugiere que un tamaño de población comprendida entre l y 21 es suficiente para atacar con éxito los problemas por él considerados. Población inicial Habitualmente la población inicial se escoge generando cadenas al azar, pudiendo contener cada gen uno de los posibles valores del alfabeto con probabilidad uniforme. Podría existir la pregunta sobre qué es lo que sucedería si los individuos de la población inicial se obtuviesen como resultado de alguna técnica heurística o de optimización local. En los pocos trabajos que existen sobre este aspecto, se constata que esta inicialización no aleatoria de la población inicial, puede acelerar la convergencia del Algoritmo Genético. Sin embargo en algunos casos la desventaja resulta ser la prematura convergencia del algoritmo, queriendo indicar con esto la convergencia hacia óptimos locales. Función objetivo Dos aspectos que resultan cruciales en el comportamiento de los Algoritmos Genéticos son la determinación de una adecuada función de adaptación o función objetivo, así como la codificación utilizada. Idealmente interesaría construir funciones objetivo con “ciertas regularidades”, es decir funciones objetivo que verifiquen que para dos individuos que se encuentren cercanos en el espacio de búsqueda sus respectivos valores en las funciones objetivo sean similares. Por otra parte una dificultad en el comportamiento del Algoritmo Genético puede ser la existencia de gran cantidad de óptimos locales, así como el hecho de que el óptimo global se encuentre muy aislado.
  • 9. La regla general para construir una buena función objetivo es que ésta debe reflejar el valor del individuo de una manera “real”, pero en muchos problemas de optimización combinatoria, donde existe una gran cantidad de restricciones, buena parte de los puntos del espacio de búsqueda representan individuos no válidos. Para este planteamiento en el que los individuos están sometidos a restricciones, se han propuesto varias soluciones. La primera sería la que se puede denominar “absolutista”, en la que aquellos individuos que no verifican las restricciones no son considerados como tales, y se siguen efectuando cruces y mutaciones hasta obtener individuos válidos, o bien, a dichos individuos se les asigna una función objetivo igual a cero. Otra posibilidad consiste en reconstruir aquellos individuos que no verifican las restricciones. Dicha reconstrucción suele llevarse a cabo por medio de un nuevo operador que se acostumbra a denominar “reparador”. Otro enfoque está basado en la penalización de la función objetivo. La idea general consiste en dividir la función objetivo del individuo por una cantidad (la penalización) que guarda relación con las restricciones que dicho individuo viola. Dicha cantidad puede simplemente tener en cuenta el número de restricciones violadas o bien el denominado costo esperado de reconstrucción, es decir el coste asociado a la conversión de dicho individuo en otro que no viole ninguna restricción. Otra técnica que se ha venido utilizando en el caso en que la computación de la función objetivo sea muy compleja es la denominada “evaluación aproximada de la función objetivo”. En algunos casos la obtención de n funciones objetivo aproximadas puede resultar mejor que la evaluación exacta de una única función objetivo (supuesto el caso de que la evaluación aproximada resulta como mínimo n veces más rápida que la evaluación exacta). Un problema habitual en las ejecuciones de los Algoritmos Genéticos surge debido a la velocidad con la que el algoritmo converge. En algunos casos la convergencia es muy rápida, lo que suele denominarse “convergencia prematura”, en la cual el algoritmo converge hacia óptimos locales, mientras que en otros casos el problema es justo el contrario, es decir, se produce una convergencia lenta del algoritmo. Una posible solución a estos problemas pasa por efectuar transformaciones en la función objetivo. El problema de la convergencia prematura surge a menudo cuando la selección de individuos se realiza de manera proporcional a su función objetivo. En tal caso, pueden existir individuos con una adaptación al problema muy superior al resto, que a medida que avanza el algoritmo “dominan” a la población. Por medio de una transformación de la función objetivo, en este caso una comprensión del rango de variación de la función objetivo, se pretende que dichos “súper-individuos” no lleguen a dominar a la población. El problema de la lenta convergencia del algoritmo, se resolvería de manera análoga, pero en este caso efectuando una expansión del rango de la función objetivo. La idea de especies de organismos, ha sido imitada en el diseño de los Algoritmos Genéticos en un método propuesto por Goldberg y Richardson, utilizando una modificación de la función objetivo de cada individuo, de tal manera que individuos que estén muy cercanos entre sí devalúen su función objetivo, con objeto de que la población gane en diversidad.
  • 10. Selección Para aplicar los operadores genéticos se tiene que seleccionar un subconjunto de la población. Algunas de las técnicas disponibles son: Selección directa: toma elementos de acuerdo a un criterio objetivo, como son “los x mejores”, “los x peores” Selección aleatoria: puede ser realizada por selección equiprobable o selección estocástica. - Selección equiprobable: todos tienen la misma probabilidad de ser escogidos. - Selección estocástica: la probabilidad de que un individuo sea escogido depende de una heurística. Los distintos procedimientos estocásticos son: - Selección por sorteo: cada individuo de la población tiene asignado un rango proporcional (o inversamente proporcional) a su adaptación. Se escoge un número aleatorio dentro del rango global, y el escogido es aquél que tenga dicho número dentro de su rango. La probabilidad de ser escogido es proporcional/inversamente proporcional al grado de adaptación del individuo. - Selección por escaños: se divide el rango del número aleatorio en un número predeterminado de escaños. Los escaños se reparten de acuerdo con la ley d'Hont, tomando como “puntuación” para repartir los escaños el grado de adaptación. Se observa que es más probable escoger un elemento de baja probabilidad por este método que en el de selección por sorteo. - Selección por restos estocásticos: es igual al método de selección de escaños, sólo que los escaños no asignados directamente, es decir, aquellos en que se aplica directamente la ley d'Hont se asignan de forma aleatoria. La probabilidad de escoger un elemento de muy baja probabilidad es más alta que en el de selección por escaños. - Por ruleta: Se define un rango con las características de la selección por sorteo. El número al azar será un número aleatorio forzosamente menor que el tamaño del rango. El elemento escogido será aquel en cuyo rango esté el número resultante de sumar el número aleatorio con el resultado total que sirvió para escoger el elemento anterior. El comportamiento es similar al de una ruleta, donde se define un avance cada tirada a partir de la posición actual. Tiene la ventaja de que no es posible escoger dos veces consecutivas el mismo elemento, y que puede ser forzado a que sea alta la probabilidad de que no sean elementos próximos en la población -esto último no es una ventaja de por sí; salvo que algunos de los otros operadores genéticos emplee un método de selección directa basado en la posición relativa de los individuos de la población-.
  • 11. - Por torneo: escoge un subconjunto de individuos de acuerdo con una de las técnicas anteriores -habitualmente, aleatoria o estocástica- y de entre ellos selecciona el más adecuado por otra técnica -habitualmente, determinística de tipo “el mejor” o “el peor”-. Esta técnica tiene la ventaja de que permite un cierto grado de elitismo -el mejor nunca va a morir, y los mejores tienen más probabilidad de reproducirse y de emigrar que los peores- pero sin producir una convergencia genética prematura, si la población es, al menos, un orden de magnitud superior al del número de elementos involucrados en el torneo. Implementación del elitismo Se denomina elitismo al proceso por el cual determinados elementos con una adaptación especialmente buena tienen determinados privilegios -nunca mueren, proporción alta de pasos en que se reproduce uno de la élite con otro al azar-... Sin embargo, en fases iniciales es peligroso, ya que puede producirse que una élite de súper- individuos acabe con la diversidad genética del problema. Para ello, lo que se puede hacer es escalar la función de adaptación en las primeras fases del algoritmo -de forma que las diferencias entre la élite y el pueblo sean menores- y superescalar la función de adaptación al final del algoritmo, para evitar un bloqueo de la convergencia. Cruce Existen gran cantidad de técnicas de cruce. Las técnicas básicas son: Cruce básico: se selecciona un punto al azar de la cadena. La parte anterior del punto es copiada del genoma del padre y la posterior del de la madre. Cruce multipunto: igual que el cruce básico, sólo que estableciendo más de un punto de cruce. Cruce segmentado: existe una probabilidad de que un cromosoma sea punto de un cruce. Conforme se va formando la nueva cadena del descendiente, para cada gen, se verifica si ahí se va producir un cruce. Cruce uniforme: para cada gen de la cadena del descendiente existe una probabilidad de que el gen pertenezca al padre, y otra de que pertenezca a la madre. Cruces para permutación: Existe una familia de cruces específicas para los problemas de permutación, siendo algunos de ellos: - Cruce de mapeamiento parcial: toma una subsecuencia del genoma del padre y procura preservar el orden absoluto de los fenotipos -es decir, orden y posición en el genoma- del resto del genoma lo más parecido posible de la madre. Aparece también en la bibliografía como PMX. - Cruce de orden: toma una subsecuencia del genoma del padre y procura preservar el orden relativo de los fenotipos del resto del genoma lo más parecido posible de la madre. Se puede encontrar en la bibliografía como OX. - Cruce de ciclo: Se toma el primer gen del genoma del padre, poniéndolo en la primera posición del hijo, y el primer gen del genoma de la madre,
  • 12. poniéndolo dentro del genoma del hijo en la posición que ocupe en el genoma del padre. El fenotipo que está en la posición que ocupa el gen del genoma del padre igual al primer gen del genoma de la madre se va a colocar en la posición que ocupe en el genoma del padre, y así hasta rellenar el genoma del hijo. Este método también es conocido en la bibliografía como CX. Es una buena idea que tanto la codificación como la técnica de cruce se hagan de manera que las características buenas se hereden o al menos no sea mucho peor que el peor de los padres. En problemas en los que, por ejemplo, la adaptación es función de los pares de genes colaterales, el resultante del cruce uniforme tiene una adaptación completamente aleatoria. Mutación Existen varias técnicas distintas de mutación. Algunas de éstas son: Mutación de bit: existe una única probabilidad de que se produzca una mutación de algún bit. De producirse, el algoritmo toma aleatoriamente un bit, y lo invierte. Mutación multibit: cada bit tiene una probabilidad de mutarse o no, que es calculada en cada pasada del operador de mutación multibit. Mutación de gen: igual que la mutación de bit, solamente que, en vez de cambiar un bit, cambia un gen completo. Puede sumar un valor aleatorio, un valor constante, o introducir un gen aleatorio nuevo. Mutación multigen: igual que la mutación de multibit solamente que, en vez de cambiar un conjunto de bits, cambia un conjunto de genes. Puede sumar un valor aleatorio, un valor constante, o introducir un gen aleatorio nuevo. Mutación de intercambio: existe una probabilidad de que se produzca una mutación. De producirse, toma dos bits/genes aleatoriamente y los intercambia. Mutación de barajado: existe una probabilidad de que se produzca una mutación. De producirse, toma dos bits o dos genes aleatoriamente y baraja de forma aleatoria los bits -o genes, según se hubiera escogido- comprendidos entre los dos. La bibliografía en inglés emplea el término scramble mutation, en mención a un juego de mesa, mas la operación que se realiza realmente es un barajado entre los dos genes.
  • 13. CAPÍTULO IV SOFTWARE DE ALGORITMOS GENÉTICOS Existen varios paquetes y bibliotecas de algoritmos genéticos en el mercado, a continuación se presentan algunos: GALOPPS Dirección primaria: GARAGe.cps.msu.edu/software/software-index.html Dirección para descargar vía FTP: garage.cps.msu.edu/pub/GA/galopps/ GAGS Generador de aplicaciones basadas en algoritmos genéticos, escrito en C++. Desarrollado por el grupo de J.J. Melero. Dirección primaria: kal-el.ugr.es/gags.html Dirección para descargar vía FTP: kal-el.ugr.es/GAGS/. FORTRAN GA Desarrollo de algoritmos genéticos para Fortran. Dirección primaria: www.staff.uiuc.edu/~ carroll/ga.html. GALIB Biblioteca de algoritmos genéticos de Matthew. Conjunto de clases en C++ de algoritmos genéticos. Dirección primaria: lancet.mit.edu/ga/
  • 14. Dirección para descargar vía FTP: lancet.mit.edu/pub/ga/ GAS Paquete para desarrollar aplicaciones de algoritmos genéticos en Python. Dirección primaria: starship.skyport.net/crew/gandalf Dirección para descargar vía FTP: ftp.coe.uga.edu/users/jae/ai. GECO Conjunto de herramientas para LISP Dirección para descargar vía FTP: ftp://ftp.aic.nrl.navy.mil/pub/galist/src/. GPDATA Para desarrollar algoritmos genéticos en C++. Dirección primaria: cs.ucl.ac.uk/genetic/papers/ Dirección para descargar vía FTP: ftp.cs.bham.ac.uk/pub/authors/W.B.Langdon/gp-code/ GPJPP Bibliotecas de clases para desarrollar algoritmos genéticos en Java Dirección primaria: www.turbopower.com/~ kimk/gpjpp.asp.
  • 15. GP Kernel Biblioteca de clases para programación genética en C++. Dirección primaria: www.emk.e-technik.th-darmstadt.de/~ thomasw/gp.html. LIL-GP Herramientas para programación genética en C. Dirección primaria: isl.msu.edu/GA/software/lil-gp/index.html Dirección para descargar vía FTP: isl.cps.msu.edu/pub/GA/lilgp/ SUGAL SUnderland Genetic ALgorithm system. Para hacer experimentos con algoritmos genéticos. Dirección primaria: www.trajan-software.demon.co.uk/sugal.htm. GPsys Sistema de programación genética en Java. Dirección primaria: www.cs.ucl.ac.uk/staff/A.Qureshi/gpsys.html.