Algoritmos Geneticos - Transparencias

  • Published on
    01-Dec-2015

  • View
    20

  • Download
    10

Transcript

  • ALGORITMOS GENTICOS

    Rene JaraMitzi OmegnaLuis Verdugo

  • Algoritmos Genticos

    Historia Qu es un Algoritmo Gentico (AG)? Conceptos biolgicos Implementacion de un AG Ejemplo, problema del viajero Conceptos finales y conclusiones

  • Qu es un AG?

    Los algoritmos genticos son una rama de la computacin evolutiva, que es el rea de la ciencia computacional cuyos algoritmos imitan el proceso evolutivo de la naturaleza.

    Segn Holland, los algoritmos genticos son programas que evolucionan, simulando en cierto grado la seleccin natural, quealcanzan a resolver problemas complejos que ni siquiera quienes lo crearon comprenden.

  • Conceptos biolgicos

    l Fundamentos biolgicos Cromosomas, anteproyecto del individuo (cadenas de

    ADN) Estn compuestos de Genes, bloques funcionales

    responsables de determinar los rasgos de un individuo Las posibilidades de escoger un rasgo son los Alelos Cada gen tiene una posicin en el cromosoma o Locus El conjunto del material gentico es el Genoma El conjunto de genes es el Genotipo El conjunto de caractersticas finales fsicas y mentales del

    individuo es el Fenotipo

  • Conceptos previos (II)

    Naturaleza Algoritmos Genticos Cromosoma (Individuo) Palabra binaria, vector,...

    (Solucin) Gen Caracterstica del problema

    (parmetro) Alelo Alfabeto de representacin

    Locus Posicin en la cromosoma de los bits

    Genotipo Configuracin de bits concreta

    Generacin Ciclo

  • Conceptos previos (III)

    l En trminos generales, para simular el proceso evolutivo en una computadora mediante un AG se requiere:

    Codificar el espacio de soluciones. Un mecanismo de seleccin. Operaciones que afecten a los individuos (operadores

    genticos). Recombinacin (Crossover) Mutacin

    Una funcin de aptitud (funcin de fitness)

  • Algoritmo Gentico Simple

    l Caractersticas para poder aplicar un AG Espacio de bsqueda en un rango conocido Codificacin de soluciones fcil

    l Generalmente un codificacin correcta es la clave de una buena resolucin del problema.

    Se debe poder definir la funcin de aptitud o fitness

  • AGS (I)

    l Algoritmo Gentico Simple (AGS) Propuesto inicialmente por John Holland Constituye la base del resto de algoritmos

    l Parmetros del AGS (de ellos depender la eficiencia y convergencia)

    Parmetros de codificacinl a = Nmero de alelos ( normalmente {0, 1} )l w = Longitud de los cromosomas

    Parmetros de funcionamientol n = Tamao de la poblacin. l m = Nmero de generaciones

  • AGS (II)

    Parmetros probabilsticosl Pr = Probabilidad de recombinacin o cruce

    l Pm = Probabilidad de mutacin de un alelo

    Funcin de aptitud o fitness de cada individuo, f(x)

  • Cundo debe ser usado un AG?

    l No hay una forma rigurosa de determinar si un mtodo es bueno o no.

    l Si el espacio de soluciones no es muy grande, se puede realizar una busque exhaustiva en lugar de AG.

    l Si el espacio es continuo, se podra emplear un algoritmo de gradiente-ascendente, ya que son ms eficiente que un AG.

    l Si la funcin fitness tiene ruido, la estrategia de seguir el gradiente puede ir desencaminada con la imposibilidad de vuelta atrs, mientras que los AGs acumulan una estadstica de fitness sobre varias generaciones.

  • Mtodos de seleccin

    l Elitistal Rueda-ruleta l Escalamiento Sigmal Seleccin por rangol Seleccin por torneol Seleccin de Vasconcelos

  • Cruzamiento simple

  • Ejemplo del viajante

    l Enunciado: Una persona debe recorrer varias ciudades distintas, con la condicin de que debe pasar solamente una vez por cada una de ellas y volver a la ciudad de origen, recorriendo la menor distancia posible. En este ejemplo se han considerado 4 ciudades

  • Ejemplo del viajante (II)

    l Para resolver este problema con un algoritmo gentico, lo primero que se debe realizar es la codificacin de los individuos

    Para ver cmo evoluciona la poblacin es necesario definir una funcin de evaluacin:

    Fitness(w) = Fitness(w)1 0.1 * Fitness(w)2-C es el nmero de ciudades -L es la longitud de la cadena de bits -bi es el bit i-simo-Ti es la distancia del tramo i

  • Ejemplo del viajante (IV)

    1.0000000.1472460.636193010110

    0.8527540.0877860.379290011000

    0.7649680.2059070.889645011101

    0.5590610.2059070.889645010111

    0.3531530.2059070.889645011011

    0.1472460.1472460.636193011001

    Aptitud AcumuladaValor esperadofitness(x)Individuo

    -Fitness(w).- Valor devuelto por la funcin de aptitud al aplicar sobre ella el individuo w.-FitTOT.- Es la aptitud total de la poblacin actual.

    -Aptitud(w).- Aptitud del individuo w respecto del resto de individuosAppt(w3) = Fitness(w3)/FitTOT

    -Aptitud acumulada(w).-

  • Ejemplo del viajante (VI)

    l Los descendientes obtenidos del cruzamiento se aaden a la poblacin intermedia y se realiza la mutacin.

    l De la poblacin intermedia elegimos aquellos individuos que recorren 4 tramos y los pasamos a la nueva generacin.

    1.0000000.1666670.889645010111

    0.8333330.1666670.889645010111

    0.7649680.1666670.889645011101

    0.5000000.1666670.889645011101

    0.3333330.1666670.889645011101

    0.1666670.1666670.889645011101

    Aptitud AcumuladaAptitudfitness(x)Individuo

    Se llega a la conclusin de que esta generacin es ms apta que la anterior puesto que el valor de FitTOT actual (5.337868 ) es mayor que el inicial (4.320610 ).

  • Conceptos finales

    l Diferencias con mtodos tradicionales de bsqueda y optimizacin

    Trabajan con poblaciones de soluciones en lugar de un individuo

    Usan una funcin de aptitud como nico conocimiento Reglas de transicin probabilsticas y no determinsticas El hecho de que usen operadores probabilsticas no significa

    que operen de manera anloga a una simple bsqueda aleatoria.

  • Conceptos finales (II)

    l Ventajas No se necesita conocimiento especfico

    l Simplicidad Conceptual.l Amplia aplicabilidad, Tienen el potencial para incorporar

    conocimiento sobre el dominio y para hibridizarse con otras tcnicas de bsqueda/optimizacin.

    Pueden explotar fcilmente las arquitecturas en paralelo. Son robustas a los cambios dinmicos, resultan menos

    afectados por los mximos locales

  • Conceptos finales (III)

    l Ventajas Capaces de resolver problemas para los cuales no se

    conoce solucin alguna.

    l Inconvenientes Dificultad en el ajuste de los parmetros

    l Operadores probabilsticosl Problemas de convergencia

    Principio bsico: Los parmetros de un AG deben ajustarse de modo que no se produzca una convergencia rpida de la poblacin

  • Conceptos finales (V)

    l Algunas aplicaciones Optimizacin (estructural, de topologas, numrica,

    combinatoria, etc.) Aprendizaje de mquina (sistemas clasificadores) Bases de datos (optimizacin de consultas) Reconocimiento de patrones (por ejemplo, imgenes) Generacin de gramticas (regulares, libres de contexto,

    etc.) Planeacin de movimientos de robots Prediccin,...

  • Conclusiones

    l Los algoritmos genticos prometen ser: mtodos de resolucin de problemas tecnolgicamente

    complejos o para el aprendizaje mquina. mtodos para la simulacin de sistemas (naturales) no

    fcilmente describibles.

    l Sin embargo, an estn lejos de establecerse como tcnicas completamente conocidas y formales.