Monografias.com > Computación > Programación
Descargar Imprimir Comentar Ver trabajos relacionados

Introducción a los algoritmos genéticos en Python




Enviado por Pablo Turmero



Partes: 1, 2

    Monografias.com

    Conceptos básicos de optimización
    Dado un conjunto de posibles soluciones a un problema, el objetivo de la optimización es encontrar la mejor solución (óptimo) de acuerdo a una determinada medida de bondad de la solución (fitness function).
    Maximización del rendimiento, minimización de una función de coste.
    Soluciones analíticas vs soluciones numéricas.

    Monografias.com

    Conceptos básicos de optimización
    Espacio que contiene el conjunto de soluciones posibles a un problema de optimización – Óptimo local/global
    Espacio de búsqueda

    Monografias.com

    Conceptos básicos de optimización
    Fuerza bruta: Evaluar todas las posibles soluciones. Poco eficiente computacionalmente o imposible. Muy ineficiente y poco práctico.
    Búsqueda aleatoria: Búsqueda aleatoria sin ninguna guía. No garantiza soluciones óptimas, ni quasi-óptimas. Simplemente reduzco el número de evaluaciones.
    Técnicas basadas en gradiente: Requiere la existencia de derivadas; búsqueda local- problema de óptimos locales.
    Algoritmos meta heurísticos: Tenemos que ser capaces de evaluar las soluciones. Medir la calidad. No hay garantías de obtener el óptimo.

    ¿Cómo resolver un problema de optimización?

    Monografias.com

    Conceptos básicos de optimización
    Lo que nos han enseñado en las clases de cálculo (Aquellos maravillosos años en el instituto).

    1) Cálculo de los puntos críticos ? Primera derivada e igualamos a 0: x1 tal que f’(x1) = 0.

    2) Puntos de inflexión ? Segunda derivada y evaluábamos los puntos críticos: f’’(x1) > 0 mínimo ó f’’(x1) < 0 máximo relativos.

    Método de Newton.

    Métodos de optimización basados en gradientes

    Monografias.com

    Conceptos básicos de optimización
    Funciones con múltiples variables
    Matrices Hessianas ? Segundas derivadas parciales.
    Multiplicadores de Lagrange. Optimización con restricciones.

    SIEMPRE TENEMOS QUE CALCULAR LAS DERIVADAS!!!!
    ¿Es siempre posible?
    No tenemos la función matemática.
    Dimensiones del problema muy grandes.
    ¿Queremos el óptimo global o nos vale con una buena solución?

    Métodos de optimización basados en gradientes

    Monografias.com

    Algoritmos genéticos
    Definición
    Los GAs son métodos de búsqueda probabilísticos inspirados en los mecanismos de selección natural y la genética en la búsqueda de los óptimos globales.
    Las soluciones que mejor se adaptan al entorno (problema) sobreviven
    Idea original de John Holland en los 70’s.
    [“Adaptation in natural systems”, by J. Holland, 1975]

    Monografias.com

    Algoritmos genéticos
    Idea global de los GAs
    Población de individuos o posible soluciones que evolucionan a lo largo de un número de generaciones, creándose mejores individuos mediante operaciones genéticas (cruce y mutación).

    Monografias.com

    Algoritmos genéticos
    Características principales
    GAs son algoritmos de inteligencia computacional que permiten resolver problemas de optimización.

    GAs utilizan métodos heurísticos, basados en probabilidad (no son métodos exactos). Pero sí podemos obtener buenas soluciones!! En muchos casos ni sabes el óptimo.

    GAs son computacionalmente intensivos. Ojo con esto!!

    GAs inspirados en la teoría de evolución de las especies. Darwin!!

    Monografias.com

    Algoritmos genéticos
    Nomenclatura:
    Individuo: solución o candidato al problema de optimización.
    Población: conjunto de candidatos al problema.
    Fitness: calidad del individuo. Propiedad del individuo.
    Función de Fitness: problema que queremos resolver.
    Cromosoma: estructura genética que representa al individuo. Variables de nuestro problema de optimización.
    Gen: posición en particular en la estructura cromosómica. Variable.
    Operaciones genéticas: operaciones (cruce y mutación) para generar nuevos individuos.
    Selección: selección de individuos normalmente basándonos en el fitness.

    Monografias.com

    Algoritmos genéticos – Ejemplo
    Poblemas de las N reinas (“N queens”):
    Problema de optimización combinatorio muy popular.
    Consiste en colocar N reinas en un tablero de ajedrez N x N, sin que ninguna reina
    ataque a otra reina. ? Conforme N se hace más grande es más complejo!

    Monografias.com

    Algoritmos genéticos – Ejemplo
    Resolución con algoritmo genético
    Individuo: Una lista de posiciones de las damas en el tablero. Sólo guardamos la
    fila en la que está la reina, la columna coincide con el índice de la lista. Por lo que sólo hay una reina por columna (Simplificación).
    Selección: mediante torneo.
    Crossover: PartiallyMatched ? Combinamos la información genética de dos individuos (“padres”) para crear dos individuos (“hijos”) ? Operación probabilística.
    Mutación: Barajamos el contenido de la lista ? Operación probabilística.
    Función de fitness: Número de ataques entre reinas. Problema de optimización ? Minimizar el número de ataques entre reinas.

    Monografias.com

    DEAP: Distributed Evolutionary Algorithm in Python
    Paquete de Python con el que podemos implementar algoritmos evolutivos. Ha sido desarrollado por Computer Vision and Systems Laboratory (CVSL) at Université Laval, Quebec, Canada ? Proyecto activo.

    Algoritmos de optimización que podemos usar con DEAP:
    Algoritmos genéticos (single objective).

    Algoritmos genéticos multi-objetivos.

    Programación genética.

    Algoritmo coevolutivos.

    Particle Swarm Optimization.

    ? Instalación mediante pip: !pip install deap

    Partes: 1, 2

    Página siguiente 

    Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.

    Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

    Categorias
    Newsletter