Optimizacion GA

  • Published on
    03-Oct-2015

  • View
    216

  • Download
    1

Embed Size (px)

DESCRIPTION

disfrutalo

Transcript

  • 54

    CAPTULO 3

    Algoritmos Genticos 3.1 Introduccin

    Existen diversas tcnicas de optimizacin que han sido desarrolladas para buscar la optimalidad de una funcin. Sin embargo, se conoce una gran variedad de problemas que no se pueden solucionar de manera exacta debido a su complejidad. El tiempo de ejecucin de cualquier algoritmo preciso para la solucin de estos problemas depende del tipo de problema, llegando a tener un tiempo de solucin exponencial en algunos casos. Los mtodos convencionales que ut ilizan el conocimiento del problema reducen la complejidad del mismo para algunos casos particulares utilizando herramientas heursticas. El conocimiento del problema mejora en parte el proceso de su ejecucin, pero la complejidad del problema mismo es fija por lo que los esfuerzos son an insuficientes y la solucin que se logra no es precisa. Por consiguiente, se requieren de otras tcnicas que brinden mejores resultados para solucionar problemas de gran complejidad. Los mtodos evolutivos constituyen uno de estos mtodos usados para la bsqueda de las soluciones ptimas mediante algn proceso de bsqueda aleatoria. Una caracterstica relevante de los mtodos evolutivos es que buscan soluciones sin tener conocimiento previo del problema. Los mtodos evolutivos tambin son conocidos como mtodos heursticos y tienen como ventaja el reducir los inconvenientes que se presentan al usar las tcnicas convencionales de optimizacin debido a que utilizan un espacio de bsqueda generado aleatoriamente.

    En este trabajo se analiza y se aplica el algoritmo gentico como un mtodo evolutivo

    para resolver el problema de la coordinacin de estabilizadores y el mejoramiento de la seguridad en los sistemas de potencia.

    3.1.1 Resumen de las tcnicas evolutivas. En 1957, el experto en estadstica ingls George E. P. Box propuso un enfoque

    evolutivo para la optimizacin de la produccin industrial denominado EVOP (Evolutionary Operation por sus siglas en ingls) [1]. Este enfoque consiste en realizar pequeas modificaciones a los parmetros de un proceso de produccin censando datos en forma aleatoria para dirigir la bsqueda. Box mostr que el mtodo propuesto por l era similar al proceso de seleccin natural a pesar de que sus ideas no se formularon en la forma de programas de computadoras.

  • 55

    En 1959, R. M. Friedberg public los primeros trabajos sobre tcnicas evolutivas aplicados mediante programas en computadora. No obstante que Friedberg no usa el trmino evolutivo, es evidente que se fue el verdadero enfoque que adopt en su artculo original. Su trabajo consisti en generar un conjunto de instrucciones en lenguaje de mquina y en programacin automtica usando las computadoras [2].

    George J. Friedman fue uno de los primeros en proponer la aplicacin de las tcnicas

    evolutivas al rea de la robtica; en su trabajo de maestra, l propuso evolucionar circuitos de control nombrando a esta tcnica como retroalimentacin selectiva siendo similar a lo que actualmente se le conoce como redes neuronales. El trabajo de Friedman ha sido considerado como el principio de la robtica evolutiva, rea donde se intenta aplicar tcnicas evolutivas para planeacin de movimientos, control, transporte, produccin, etc. [3].

    En 1961, Hans Joachim Bremermann aplic la evolucin como un proceso de

    optimizacin numrica; asimismo, realiz las primeras simulaciones de la evolucin mediante el uso de cadenas binarias teniendo como fundamento la reproduccin, seleccin y mutacin, siendo as, un pionero de los algoritmos genticos [4].

    Posterior a esos trabajos, se formaron las tres corrientes ms importantes en el rea de

    los mtodos evolutivos:

    En 1965, en Alemania se desarrollaron las estrategias evolutivas para solucionar problemas hidroneumticos de gran complejidad, presentados por I. Rochenberg y Schwefel. Las estrategias evolutivas no utilizan la recombinacin; tienen su origen en el rea de la optimizacin numrica [5].

    En 1966, Lawrence J. Fogel present la programacin evolutiva modelando la

    inteligencia como un comportamiento adaptativo. La programacin evolutiva tiene aplicaciones en diversas reas como la inteligencia artificial, la programacin automtica y la optimizacin numrica. Este mtodo enfatiza la relacin de comportamiento entre padres y descendientes y no utiliza operadores genticos [6].

    En 1967, John H. Holland implement el algoritmo gentico que ha servido de

    referencia para muchos investigadores. El algoritmo gentico usa seleccin probabilstica al igual que la programacin evolutiva, mientras que las estrategias evolutivas usan seleccin determinstica. El algoritmo gentico comenz usando la representacin binaria para codificar las

    soluciones a un problema, evolucionando el genotipo y no el fenotipo como en la programacin evolutiva o las estrategias evolutivas. El operador principal en el algoritmo gentico es el cruzamiento, mientras que en la programacin evolutiva ste no existe y en las estrategias evolutivas se emplea como un operador secundario.

  • 56

    En este captulo se describe un algoritmo gentico cons iderando dos etapas: en la primera no se consideran restricciones de ningn tipo, y en la segunda se incluyen algunas restricciones. El captulo est organizado de la forma siguiente: en la seccin 3.1 se describen los avances de los mtodos evolutivos para optimizacin. La seccin 3.2 describe la metodologa del algoritmo gentico sin restricciones y sus ventajas comparadas con las tcnicas convencionales; se presentan ejemplos de aplicacin. En la seccin 3.3 se describe el algoritmo gentico considerando la solucin de problemas con restricciones, y sus diferentes enfoques de solucin. La seccin 3.4 se presenta la metodologa propuesta para la coordinacin eficiente y robusta e estabilizadotes, as como el diagrama de flujo correspondiente. En la seccin 3.5 se ilustra un ejemplo de aplicacin a una red elctrica con caractersticas reales. En la seccin 3.6 se propone la inclusin de restricciones de seguridad dinmica en el algoritmo del trabajo. Finalmente, la seccin 3.7 brinda un breve resumen acerca de este captulo.

    3.2 Descripcin de los Algoritmos Genticos Los algoritmos genticos se fundamentan en una analoga con el proceso de la

    evolucin natural investigada por G. Johann Mendel a principios del siglo XIX, su trabajo se bas en el estudio de la herencia gentica, esto es, la transmisin de caractersticas especficas de padres a sus descendientes; sin embargo, estos resultados se obtuvieron mediante el anlisis de una sola especie. Posterior a Mendel, Charles Darwin present en 1859 sus ideas sobre la evolucin en su trabajo titulado The Origin of Species. Darwin afirmaba que la supervivencia de una especie depende del grado de adaptacin en el ambiente en que habita; de no adaptarse, las especies se extinguirn a largo plazo. Con las ideas de Darwin, se concluy que la evolucin de una especie se realiza mediante unos procesos, que son: reproduccin (es la habilidad de transmitir ciertas caractersticas por herencia a los descendientes), recombinacin de caractersticas de los padres a los descendientes, mutacin (se considera como una pequea modificacin del patrn hereditario), y la seleccin de los individuos ms fuertes. Consecuentemente, Darwin concluy que solamente sobreviven los individuos que estn mejor adaptados a su ambiente. El grado de adaptacin al ambiente se le denomina aptitud; mientras ms alta sea la aptitud de un individuo, tendr ms probabilidad de sobrevivir.

    Basado de manera estricta en las leyes de la naturaleza y tomando como base las

    aportaciones hechas por Darwin, John Holland de la Universidad de Michigan present formalmente los algoritmos genticos en 1966, para estudiar procesos lgicos involucrados en la adaptacin [3]. Denominados originalmente como planes reproductivos genticos se les conoci posteriormente como algoritmos genticos. Los algoritmos genticos fueron inicialmente concebidos en el contexto del aprendizaje de mquina, pero en la actualidad se ha convertido en una tcnica muy popular para la solucin de problemas de optimizacin [8].

    Los AG son tcnicas de bsqueda globales, aleatorias y estn basados en la mecnica

    de la seleccin natural y en la gentica natural [9]. Fueron desarrollados para permitir identificar mltiples soluciones ptimas a problemas difciles tales como funciones de

  • 57

    optimizacin e inteligencia artificial. En un AG, las soluciones representadas por estructuras de datos llamadas individuos son evolucionadas y una nueva poblacin de individuos es creada. A cada individuo se le asigna un valor o aptitud mediante el cual se compara con otros individuos de la misma poblacin. Los algoritmos genticos han sido desarrollados para resolver problemas lineales y no lineales, explorando todas las regiones del espacio de bsqueda a travs de la mutacin, cruzamiento y la seleccin, operaciones aplicadas a los individuos de una poblacin [10, 11].

    El algoritmo bsico es el siguiente. a) Generar aleatoriamente una poblacin inicial.

    b) Calcular la aptitud de cada individuo.

    c) Seleccionar (probabilsticamente) basndose en la aptitud. d) Aplicar operadores genticos (cruza y mutacin) para generar la siguiente

    poblacin.

    e) Repetir el proceso hasta que cierta condicin se cumpla.

    El algoritmo gentico utiliza la seleccin probabilstica y no determinstica. Requiere

    de la determinacin de cinco puntos fundamentales: 1) La representacin del individuo.

    2) Una forma de crear una poblacin inicial de posibles soluciones (generalmente, un proceso aleatorio).

    3) Una funcin de evaluacin que juegue el papel del ambiente, clasificando las

    soluciones en trminos de su aptitud.

    4) Operadores genticos que alteren la composicin de los descendientes que se producirn para las siguientes gen