UNIVERSIDAD DE PAMPLONA FACULTAD DE INGENIERIAS Y ARQUITECTURA DEPARTAMENTO DE INGENIERIA ELECTRONICA, ELECTRICA, TELECOMUNICACIONES Y SISTEMAS PROGRAMA DE INGENIERÍA ELECTRÓNICA

TITULO: SINTONIZACION DE CONTROLADORES PID UTILIZANDO ALGORITMOS EVOLUTIVOS

AUTOR: MARÍA CLAUDIA PINTO FIGUEROA

PAMPLONA COLOMBIA MAYO 2006

UNIVERSIDAD DE PAMPLONA FACULTAD DE INGENIERIAS Y ARQUITECTURA DEPARTAMENTO DE INGENIERIA ELECTRONICA, ELECTRICA, TELECOMUNICACIONES Y SISTEMAS PROGRAMA DE INGENIERÍA ELECTRÓNICA

TRABAJO DE GRADO PARA OPTAR POR EL TITULO DE INGENIERO ELECTRÓNICO

TÍTULO: SINTONIZACION DE CONTROLADORES PID UTILIZANDO ALGORITMOS EVOLUTIVOS

AUTOR: MARÍA CLAUDIA PINTO FIGUEROA

DIRECTOR: Ph.D. ELIEZER COLINA MORLES

PAMPLONA COLOMBIA MAYO 2006

RESUMEN

En el desarrollo de

este trabajo se diseñó una herramienta computacional

basada en algoritmos evolutivos para la sintonización de controladores PID.

Inicialmente la herramienta fue empleada con técnicas fuera de línea, para varios sistemas estables e inestables a lazo abierto, con sistemas con distintos tiempos de respuesta y con sistemas no lineales; usando diferentes funciones objetivo.

Luego se trabajó con sistemas en línea, manipulando pocos individuos con una función de aptitud que tiene en cuenta el sobreimpulso y el tiempo de asentamiento, con el fin de comparar su desempeño con otras técnicas de sintonización ya existentes.

Por último se aplicaron algoritmos evolutivos en el diseño del controlador de un proceso de evaporación, tomando en cuenta la variable tasa de flujo de vapor, que depende de la tasa de transferencia de calor.

ABSTRACT

This work includes an evolutionary algorithm based computational tool design intended for PID tuning in a variety of control system configurations. The computational tool was tested on open loop stable and unstable control systems, control systems with different time response as well as with some clases of non linear control system. Different objective functions were considered in order to check the performance of the evolutionary algorithm.

The work also includes computational simulations of the evolutionary algorithm for on line tuning of PID controllers and a performance trade off with respect to other tuning techniques is presented.

Finally, the work contemplates the controller design problem for an evaporator system using the proposed evolutionary computational tool.

CONTENIDO

INTRODUCCION OBJETIVOS JUSTIFICACION PLANTEAMIENTO DEL PROBLEMA METODOLOGIA

CAPÍTULO 1. COMPUTACION EVOLUTIVA 1.1. INTRODUCCIÓN 1.2. ORIGENES 1.3. ANTECEDENTES 1.4. BASES BIOLÓGICAS DE LA COMPUTACIÓN EVOLUTIVA. 1.5. COMPONENTES DE UN ALGORITMO EVOLUTIVO 1.6. MODELOS SOBRE EL ESQUEMA GENERAL 1.7. ALGORITMOS GENÉTICOS (AG) 1.7.1. CODIFICACIÓN DE LAS VARIABLES 1.7.2. OPERADORES 1.7.2.1. CRUCE 1.7.2.1.1. Cruces para permutación 1.7.2.1.1.1. Cruce por emparejamiento parcial (PMX) 1.7.2.1.1.2. Cruces por orden (OX) 1.7.2.1.1.2.1. Variantes al Cruce por orden 1.7.2.1.1.3. Cruce por ciclos (CX) 1.7.2.1.1.4. Cruce por recombinación de rutas (ERX) 1.7.2.2. MUTACIÓN 1.7.2.2.1. Mutaciones sobre genes 1.7.2.2.2. Mutaciones no estacionarías 1.7.2.2.3. Mutaciones no uniformes 1.7.2.3. VARIANTES EN OPERADORES BÁSICOS PARA NÚMEROS REALES

1.7.2.4. OTROS OPERADORES 1.7.2.4.1. Cromosomas de longitud variable 1.7.2.4.2. Operadores de nicho (ecológico) 1.7.2.4.3. Operadores especializados 1.7.3. FUNCIÓN DE ADAPTACIÓN 1.7.4. EL TEOREMA DEL ESQUEMA 1.7.5. EVALUACIÓN 1.7.6. MÉTODOS DE SELECCIÓN 1.7.7. MECANISMOS DE REEMPLAZO 1.7.8. CARACTERÍSTICAS DE LOS AGS 1.7.9. ¿COMO FUNCIONAN? 1.7.10. ¿POR QUÉ UTILIZAR

ALGORITMOS GENÉTICOS EN LA

OPTIMIZACIÓN 1.7.11. CONVERGENCIA DEL ALGORITMO 1.7.12. ¿CÓMO SABER SI ES POSIBLE USAR EL ALGORITMO GENÉTICO? 1.7.13. DECISIONES PARA IMPLEMENTAR UN ALGORITMO GENÉTICO 1.7.14. VENTAJAS DE LOS AGS 1.7.15. DESVENTAJAS O LIMITACIONES QUE TIENEN LOS AG CON RESPECTO A OTRAS TÉCNICAS DE BÚSQUEDA 1.7.16. CONSIDERACIONES AL USAR ALGORITMOS GENÉTICOS 1.7.17. DIFERENCIAS ENTRE LOS MÉTODOS TRADICIONALES Y LOS A.G. 1.8. PROGRAMAS EVOLUTIVOS (PES) 1.8.1. PES EN OPTIMIZACIÓN PARAMÉTRICA 1.8.2. PES EN OPTIMIZACIÓN COMBINATORIA 1.8.3. PROGRAMAS EVOLUTIVOS Y ALGORITMOS GENÉTICOS 1.9. ESTRATEGIAS EVOLUTIVAS (EES) 1.9.1. EES SIMPLES 1.9.2. EES MÚLTIPLES

1.9.3. ESTRATEGIAS EVOLUTIVAS Y ALGORITMOS GENÉTICOS 1.10. PROGRAMACIÓN EVOLUTIVA (EP) 1.10.1. ALGORITMO GENERAL 1.10.2. PROGRAMACIÓN EVOLUTIVA Y ALGORITMOS GENÉTICOS 1.10.3.

PROGRAMACIÓN

EVOLUTIVA

Y

LAS

ESTRATEGIAS

EVOLUTIVAS 1.11. PROGRAMACIÓN GENÉTICA (PG) 1.11.1. FUNCIONAMIENTO DE LOS OPERADORES GENÉTICOS 1.11.2. MUTACIÓN EN PG 1.11.3. ALGORITMO GENERAL 1.12. AMBIENTES DE PROGRAMACIÓN 1.13. PROGRAMAS AUTOCONFIGURABLES 1.14. ROBUSTEZ DE LOS MÉTODOS DE OPTIMIZACIÓN Y BÚSQUEDA TRADICIONALES

CAPÍTULO 2. CONTROLADORES PID 2.1. INTRODUCCIÓN 2.2. ACCIONES BASICAS DE CONTROL 2.2.1. CLASIFICACIÓN DE LOS CONTROLADORES INDUSTRIALES 2.2.2.

CONTROLADOR

AUTOMÁTICO,

ACTUADOR

Y

SENSOR

(ELEMENTO DE MEDICIÓN) 2.2.3. CONTROLADORES AUTO-OPERADOS 2.2.4. ACCIÓN DE CONTROL DE DOS POSICIONES O ENCENDIDO Y APAGADO (ON/OFF) 2.2.5. ACCIÓN DE CONTROL PROPORCIONAL 2.2.6. ACCIÓN DE CONTROL INTEGRAL 2.2.7. ACCIÓN DE CONTROL PROPORCIONAL- INTEGRAL 2.2.8. ACCIÓN DE CONTROL PROPORCIONAL – DERIVATIVA 2.2.9. ACCIÓN DE CONTROL PROPORCIONAL- INTEGRAL- DERIVATIVA

2.3.

EFECTOS DE LAS

ACCIONES

DE CONTROL INTEGRAL Y

DERIVATIVO SOBRE EL DESEMPEÑO DE UN SISTEMA.

2.3.1. ACCIÓN DE CONTROL INTEGRAL 2.3.2. ACCIÓN DE CONTROL DERIVATIVA 2.4. SINTONIZACIÓN DE CONTROLADORES PID 2.4.1. CONTROL PID DE PLANTAS 2.4.2.

REGLAS

DE

ZIEGLER

–

NICHOLS

PARA

SINTONIZAR

CONTROLADORES PID 2.4.2.1. PRIMER MÉTODO. MÉTODO BASADO EN LA CURVA DE REACCIÓN 2.4.2.2. SEGUNDO MÉTODO. MÉTODO DE OSCILACIÓN 2.4.3. MÉTODO DE ASIGNACIÓN DE POLOS 2.4.3.1. TEOREMA 1 (TEOREMA DE SYLVESTER). 2.4.3.2. LEMA 1 (ASIGNACIÓN DE POLOS SISO). 2.4.3.3. LEMA 2. 2.5. MODIFICACIONES DE LOS ESQUEMAS DE CONTROL PID 2.5.1. CONTROL PI-D 2.5.2. CONTROL I-PD 2.6. INTEGRAL WINDUP

CAPÍTULO 3. DISCRETIZACIÓN DE SISTEMAS Y LINEALIZACIÓN DE SISTEMAS NO LINEALES 3.1. LINEALIZACIÓN DE SISTEMAS NO LINEALES 3.2. DISCRETIZACIÓN DE SISTEMAS EN TIEMPO CONTINUO. 3.2.1. IMPLEMENTACIÓN DIGITAL DE CONTROLADORES ANALÓGICOS 3.2.1.1. IMPLEMENTACIÓN DIGITAL DEL CONTROLADOR PID 3.2.1.1.1. Integración trapezoidal 3.2.1.1.2. Integración rectangular hacia delante 3.2.1.1.3. Integración rectangular hacia atrás 3.2.2. ÍNDICES DE DESEMPEÑO 3.2.2.1. FORMULACIÓN DE LOS PROBLEMAS DE OPTIMIZACIÓN 3.2.2.2. PUNTOS CONCERNIENTES A LA EXISTENCIA DE LAS SOLUCIONES A LOS PROBLEMAS DE CONTROL ÓPTIMO. 3.2.2.3. NOTAS ACERCA DE LOS SISTEMAS DE CONTROL ÓPTIMO.

CAPÍTULO 4. ESTADO DEL ARTE DE LOS ALGORITMOS EVOLUTIVOS Y SU USO PARA CONTROLADORES PID 4.1. APLICACIONES DE LA PROGRAMACIÓN GENÉTICA. 4.2. COMPUTACIÓN EVOLUTIVA Y CONTROLADORES PID 4.3. APLICACIÓN EN PROCESOS DE CONTROL 4.3.1. SINTONIZACIÓN DE CONTROLADORES 4.3.2. DISEÑO DE ESTRUCTURA DE CONTROL 4.3.3. APLICACIONES EN LÍNEA 4.4. CÓMO PUEDEN LOS AG SER DE BENEFICIO PARA EL CONTROL? 4.4.1. ESTABILIDAD

CAPÍTULO 5. SINTONIZACIÓN DE CONTROLADORES PID UTILIZANDO ALGORITMOS EVOLUTIVOS 5.1. SISTEMA MECÁNICO: MASA –RESORTE 5.1.1. CONTROLABILIDAD DEL SISTEMA 5.1.2. OBSERVABILIDAD 5.1.3. DISCRETIZACIÓN DEL SISTEMA 5.1.4. CALCULO DEL CONTROLADOR 5.1.5. DISCRETIZACIÓN DEL CONTROLADOR 5.1.6.

SINTONIZACIÓN

DE

CONTROLADORES

PID

UTILIZANDO

ALGORITMOS EVOLUTIVOS EN LÍNEA 5.1.6.1. VALIDACIÓN DEL ALGORITMO EN LÍNEA 5.2. CIRCUITO LRC 5.3. SISTEMA DE LEVITACIÓN MAGNÉTICA 5.3.1. FUNCIÓN DE TRANSFERENCIA 5.3.2. CALCULO DEL CONTROLADOR 5.4. MODELO DEL EVAPORADOR 5.4.1. MODELO NO LINEAL 5.4.2. PROCESO DE BALANCE DE MASA LIQUIDA 5.4.3. PROCESO DE BALANCE DE MASA LIQUIDA DEL SOLUTO 5.4.4. PROCESO DE BALANCE DE MASA DE VAPOR

5.4.5. PROCESO DE BALANCE DE ENERGÍA LIQUIDA 5.4.6. ENVOLTURA DEL VAPOR CALIENTE 5.4.7. CONDENSADOR 5.4.8. MODELO MATEMÁTICO DEL EVAPORADOR 5.5.

SINTONIZACIÓN

DE

CONTROLADORES

ALGORITMOS EVOLUTIVOS FUERA DE LÍNEA 5.5.1. SISTEMA MECÁNICO: MASA –RESORTE 5.5.2. CIRCUITO LRC 5.5.3. SISTEMA DE LEVITACIÓN MAGNÉTICA 5.5.4. MODELO DEL EVAPORADOR 6. ANALISIS ECONOMICO Y ADMINISTRATIVO 7. ANALISIS DE LEGALIDA 8. INFLUENCIA AMBIENTAL CONCLUSIONES RECOMENDACIONES BIBLIOGRAFIA ANEXOS GLOSARIO DE TÉRMINOS TÉCNICOS

PID

UTILIZANDO

INTRODUCCIÓN

A pesar de que la tecnología ha ido avanzando a pasos gigantescos en el área industrial desde la invención del controlador PID, éstos continúan teniendo una gran acogida hasta nuestros días, siendo utilizados para el control de la mayoría de los procesos a lazo cerrado. En general, los procesos donde estos controladores

son

empleados

tienden

a

desestabilizarse

debido

a

perturbaciones no lineales, desgaste de equipos, y varios otros factores, lo cual hace que tengan que ser resintonizados o reajustados para las nuevas condiciones de operación o funcionamiento de los sistemas.

Con este trabajo se busca realizar la entonación de controladores PID, ante cambios de los parámetros de los sistemas, de forma autónoma, sin la ayuda del operador.

Para esto se propone utilizar algoritmos evolutivos, que constituyen una rama de la llamada Computación Blanda, con los cuales se emula la evolución natural de los seres vivos, utilizando la selección y reproducción, para encontrar la solución óptima a un problema específico, sin tener ningún conocimiento previo de este.

Inicialmente se propone un conjunto de posibles soluciones, que luego son sometidas a procesos de transformación y después a una selección que escoge las mejores y descarta las peores, de acuerdo a una calificación o medida de aptitud dada por una función de aptitud, que se establece de acuerdo al objetivo del problema.

Dentro de los algoritmos evolutivos se pueden destacar diferentes directrices, como la de los algoritmos genéticos, las cuales se aplican de acuerdo a la codificación que se hace de los individuos (posibles soluciones al problema).

El desarrollo de este trabajo esta organizado como sigue:

-

En el primer capítulo se trata todo lo referente a los algoritmos evolutivos desde sus inicios, pasando por todas las técnicas que han sido desarrolladas a través del tiempo. También se orienta un poco sobre las consideraciones que se deben tener en cuenta a la hora de la implementación y se mencionan sus ventajas y sus desventajas.

-

En el segundo capítulo se hace referencia a toda la teoría relacionada con

los

controladores

PID.

Diferentes

acciones

de

control

y

configuraciones de los controladores y sus efectos sobre los sistemas. -

El tercer capítulo es un enfoque reducido sobre las diferentes técnicas de discretización de sistemas y además la linealización de sistemas no lineales.

-

El cuarto capítulo es una perspectiva sobre el estado del arte de los algoritmos evolutivos y sus usos para solucionar problemas relacionados con controladores PID

-

En el quinto capítulo se llevan a cabo varios experimentos para la sintonización de controladores con algoritmos evolutivos; primero en línea y luego fuera de línea, para luego ser aplicados a un proceso de evaporación.

-

El sexto capítulo se dan conclusiones específicas y recomendaciones sobre el uso de este método de acuerdo a las conclusiones obtenidas en los experimentos.

OBJETIVOS

OBJETIVO GENERAL: Desarrollar un nuevo algoritmo de sintonización de controladores PID utilizando algoritmos evolutivos.

OBJETIVOS ESPECÍFICOS •

Diseñar experimentos para respaldar el desarrollo de algoritmos evolutivos para la sintonización de controladores.

•

Diseñar un algoritmo

evolutivo para la sintonización adaptativa de

controladores PID e implementar el diseño utilizando herramientas de computación en Matlab. •

Validar los desarrollos, a través de simulaciones computacionales, con un modelo matemático de un sistema de evaporación, mediante la verificación de condiciones de estabilidad del sistema en estudio.

•

Definir otras potenciales aplicaciones de implementación en el ámbito industrial.

JUSTIFICACIÓN

De acuerdo con las diversas asignaturas cursadas en el transcurso del programa propuesto para Ingeniería Electrónica, el control automático es una de las áreas de estudio de la carrera. El control como tal, dentro de su diversidad de temas, métodos y técnicas, incluye el diseño de controladores PID, los cuales son ampliamente utilizados a nivel industrial.

Los controladores han generado muchos beneficios para la apropiada operación de procesos o sistemas; por lo cual son de gran interés, tanto en sus funcionalidades, como en el mejoramiento continuo del desempeño de procesos industriales. Para lograr estas mejoras se han usado diferentes métodos basados en una diversidad de técnicas para la entonación automática de los controladores.

Teniendo en cuenta los objetivos del proyecto, sus logros aportarían soluciones a la industria, ya que permitirían mejorar la operación de plantas al tiempo que robustecerían las condiciones de seguridad operacional en procesos de alto riesgo donde el control resulta esencial.

PLANTEAMIENTO DEL PROBLEMA

En las instalaciones industriales más del 95% de los procesos son regulados por controladores PID, pero debido a la vida útil de los equipos, a cambios de dinámica de los procesos, a la presencia de comportamientos no lineales y a perturbaciones de naturaleza aleatoria, entre otros factores, con frecuencia se pierde la entonación de los controladores. Todo eso ocasiona una degradación en las condiciones de operación de los sistemas, ya que estos están diseñados para operar en un punto específico de equilibrio, trayendo como consecuencia pérdidas económicas o detrimento de las condiciones de seguridad en la operación del proceso. Por esto, se hace necesaria la asistencia de ingenieros de control para reestablecer el buen desempeño del sistema, entonando los controladores. Lo ideal sería que el controlador se acoplara automáticamente a los cambios de parámetros del sistema de forma eficiente, rápida y efectiva sin necesidad de recurrir a un operador para realizarlo, lo cual resultaría más costoso.

METODOLOGÍA •

Recolección de información: En este primer paso se llevó a cabo una consulta e investigación documental sobre el estado del arte de los controladores PID y los algoritmos evolutivos. Para esto fue necesario usar la INTERNET, fuentes bibliográficas (artículos, libros, folletos y revistas) y colaboración de profesores conocedores del área. La información recopilada permitió la escogencia de la estructura del controlador y de los parámetros de diseño del algoritmo evolutivo: codificación, población inicial, fusión objetivo, condición de terminación, operadores, entre otros elementos. •

Diseño de experimentos: Se comenzó con el desarrollo de la técnica en línea, utilizando varios sistemas estables a lazo cerrado, a los cuales se les realizó cambios de las condiciones iniciales, usando como función de aptitud la diferencia del error cuadrático y empleando como operador genético el de mutación basada en descenso por gradiente. También se trabajó con sistemas inestables a lazo abierto y un tipo de sistemas no lineales, haciendo cambios en la función objetivo del algoritmo evolutivo y con mutación basada en ascenso por gradiente. Luego fue desarrollada la técnica fuera de línea. Para todas estas pruebas se utilizó la ayuda del sistema programado Simulink y las herramientas de programación de Matlab. Por último se aplicó este algoritmo a la variable de tasa de flujo, de un proceso de evaporación, para controlar las diferentes salidas de este sistema. Aquí se hizo necesaria la utilización de diferentes técnicas de discretización de sistemas lineales para la implementación del algoritmo.

•

Obtención de resultados: Una vez obtenidos los comportamientos de los diferentes sistemas considerados después de haber utilizado el algoritmo evolutivo diseñado, fueron establecidas conclusiones y recomendaciones relativas a los resultados y en correspondencia con los objetivos originalmente planteados para el trabajo. Así mismo se realizaron consideraciones sobre la plataforma tecnológica necesaria a nivel industrial para poder hacer la implantación física del método de entonación PID desarrollado.

Capítulo 1 Computación Evolutiva 1.1. INTRODUCCIÓN En la naturaleza todos los seres vivos se enfrentan a problemas que deben resolver con éxito, como conseguir más luz del sol, o cazar una mosca. La Computación Evolutiva interpreta la naturaleza como una inmensa máquina de resolver problemas y trata de encontrar el origen de dicha potencialidad para utilizarla en programas [1, 5,13].

La computación evolutiva busca relacionar algunos conceptos expresados en la teoría de la evolución con un conjunto de técnicas usadas para resolver computacionalmente algunos problemas. La computación evolutiva CE abarca los modelos computacionales que usan como elemento clave algún mecanismo de la teoría de la evolución para su diseño e implementación [4].

El principal aporte de la CE a la metodología de la resolución de problemas ha sido el uso de mecanismos de selección de soluciones potenciales y de construcción de nuevas candidatas por recombinación de característica de otras ya existentes [4].

La Computación Evolutiva surge a finales de los años 60 cuando John Holland planteó la posibilidad de incorporar los mecanismos naturales de selección y supervivencia a la resolución de problemas de Inteligencia Artificial. [22]

En la actualidad se tienen varias aplicaciones industriales exitosas inspiradas en enfoques evolutivos para diversas áreas [22]:

o Diseño de circuitos o Planificación de tareas

o Cálculo de Estrategias de Mercado o Cortado de patrones, etc.

Las implementaciones concretas en el área de la CE han sido denominadas algoritmos evolutivos [4].

Los Algoritmos Evolutivos recogen un conjunto de modelos basados en la evolución de los seres vivos inspirados en la naturaleza, constituyendo así una técnica de resolución de problemas [22,5].

En un Algoritmo Evolutivo se define una estructura de datos que admite todas las posibles soluciones a un problema. Cada uno de los posibles conjuntos de datos admitidos por esa estructura será una solución al problema. Unas soluciones serán mejores, otras peores. Estas soluciones serán sometidas a ciertas transformaciones y luego a un proceso de selección que favorece a los mejores. Se espera que después de cierto número de generaciones el mejor individuo de la población esté cerca de la solución buscada. Solucionar el problema consistirá en encontrar la solución óptima, y por tanto, los Algoritmos Evolutivos son en realidad un método de búsqueda muy especial, en el que las soluciones al problema son capaces de reproducirse entre sí, combinando sus características y generando nuevas soluciones [5, 8,22]. En cada ciclo se seleccionan las soluciones que más se acercan al objetivo buscado, eliminando el resto de soluciones. Las soluciones seleccionadas se reproducirán entre sí, permitiendo de vez en cuando alguna mutación o modificación al azar durante la reproducción [5]. No siempre el espacio de búsqueda completo contiene soluciones válidas; en algunos casos, los valores de las variables se sitúan dentro de un rango, más allá del cual la solución es inválida. Se trata entonces de un problema de optimización con restricciones. En este caso, el problema consiste en maximizar F(xi) dentro del subespacio.

1.2. ORIGENES A principios del siglo XIX, las cuestiones relacionadas con las variaciones evolutivas se centraban en tres aspectos: cuál era la naturaleza del material genético transmitido a la descendencia, cómo pasaban fielmente las características de una generación a la siguiente, y cómo se producían variaciones en ellas que después se transmitían. El zoólogo francés Jean Baptiste de Lamarck pensaba que la vida animal y vegetal sufría nuevas influencia de acuerdo a los cambios climáticos y áreas geográficas que experimentaban, desencadenando nuevas necesidades y por tanto nuevas estrucuturas. A estas nuevas estructuras Lamarck las llamó características adquiridas que pueden ser heredadas a nuevas generaciones [19].

A finales del siglo XIX, científicos como Charles Darwin, el biólogo alemán Ernst Haeckel, el botánico holandés Hugo De Vries y el biólogo alemán August Weismann desarrollaron teorías sobre la herencia. La razón principal que suscitó este interés fue que la teoría de la selección natural de Darwin, publicada por primera vez en 1859. La selección natural fomenta la adaptación de los organismos cuando ello es necesario para la supervivencia, el éxito debió alcanzar a aquellas que conseguían desarrollar una habilidad o mecanismo especial para su autoconservación y replicación rápida [19]. Charles Darwin elaboró su teoría de la selección natural, que se convertiría en el fundamento de la teoría de la evolución, influenciado por las ideas del geólogo Adam Sedgwick y el naturalista John Henslow.

La mayor parte de la selección natural se denomina selección estabilizadora, por cuanto elimina genes del conjunto genético que tienden a producir desviaciones de una forma que ya es óptima [20].

La selección natural elige los más aptos, los organismos más capacitados. Para Darwin aptitud significaba cualquier cualidad que ayudaba a un organismo a sobrevivir y reproducirse [18].

Gregor Johann Mendel (1822-1884) fue un monje austriaco, cuyos experimentos se convirtieron en el fundamento de la actual teoría de la herencia (transmisión a los descendientes de los caracteres de los ascendientes). Sus exhaustivos experimentos con plantas tuvieron como resultado el enunciado de dos principios que más tarde serían conocidos como leyes de la herencia. Sus observaciones le llevaron también a acuñar dos términos que siguen empleándose en la genética de nuestros días: dominante y recesivo [18, 21].

El redescubrimiento en 1900 de los escritos de Mendel del año 1866 sobre los patrones de la herencia en la planta del guisante, supuso una fuente importante de conceptos nuevos sobre la herencia. De su estudio sobre el cruzamiento de este tipo de plantas, Mendel llegó a tres generalizaciones. La primera fue la ley de la uniformidad en la primera generación filial: cuando se cruzan dos razas puras (homocigotas), diferentes en un carácter concreto, la descendencia presenta siempre el mismo fenotipo. La segunda fue la ley de la segregación: en la formación de células germinales, los dos factores (alelos) para cualquier característica están siempre separados entre sí y van a diferentes óvulos o espermatozoides. La tercera generalización, que con posterioridad se denominó la ley de la herencia independiente, afirmaba que los factores maternos y paternos para cualquier grupo de características se separaban de forma independiente de aquellos que pertenecían a otro grupo de características [20,21].

Los estudios de Mendel, retomados a finales del siglo, demostraron lo que Darwin insinuó vagamente en cierta época, que la herencia es particular, no combinada. Sean o no los descendientes formas intermedias entre sus dos padres, heredan y transmiten partículas hereditarias separadas, que hoy en día se denominan genes.

Hugo Marie de Vries (1848-1935) fue un botánico holandés, quien redescubrió de modo independiente las leyes de la herencia desarrolladas por el monje

austriaco Gregor Mendel, e incorporó el concepto de mutación a la teoría evolutiva (variaciones a gran escala que pueden producir nuevas especies en una sola generación), la mutación es el origen último de la variación genética. De Vries concedió a Mendel todo el mérito por el trabajo [18].

En 1903, Walter Sutton, en Estados Unidos, y Theodore Boveri, en Alemania, formularon por separado la teoría cromosómica de la herencia, en la que proponían que los cromosomas eran el soporte físico de los genes. Después de varios años de experimentación el científico estadounidense Thomas Hunt Morgan, junto con sus colaboradores, Alfred Henry Sturtevant, Calvin Blackman Bridges y Hermann Joseph Muller, demostraron la teoría formulada por Sutton y Boveri. Los cromosomas contienen la información genética del organismo. La mitad de los cromosomas proceden del padre, y la otra mitad de la madre. Las diferencias entre individuos reflejan la recombinación genética de estos juegos de cromosomas al pasar de una generación a otra [19].

Harriet B. Creighton y Barbara McClintock demostraron experimentalmente, en 1931, la correlación existente entre la recombinación genética y el intercambio de fragmentos cromosómicos (entrecruzamiento) que acontece durante la meiosis [19].

1.3. ANTECEDENTES Los primeros ejemplos de lo que hoy se podría llamar algoritmos genéticos aparecieron a finales de los 50 y principios de los 60, programados en computadoras por biólogos evolutivos que buscaban explícitamente realizar modelos de aspectos de la evolución natural [28]. John Holland En los años 50 entró en contacto con los primeros ordenadores, donde pudo llevar a cabo algunas de sus ideas, aunque no se encontró con un ambiente intelectual fértil para propagarlas. Fue a principios de los 60, en la Universidad de Michigan en Ann Arbor, donde, dentro del grupo Logic of Computers, sus ideas comenzaron a desarrollarse y a dar frutos. Y fue,

además, leyendo un libro escrito por un biólogo evolucionista, R. A. Fisher, titulado La teoría genética de la selección natural, como comenzó a descubrir los medios de llevar a cabo sus propósitos de comprensión de la naturaleza [2]. En esa universidad, Holland impartía un curso titulado Teoría de sistemas adaptativos. Dentro de este curso, y con una participación activa por parte de sus estudiantes, fue donde se crearon las ideas que más tarde se convertirían en los algoritmos genéticos [2].

Por tanto, cuando Holland se enfrentó a los algoritmos genéticos, los objetivos de su investigación fueron dos [2]: •

Imitar los procesos adaptativos de los sistemas naturales, y

•

Diseñar sistemas artificiales (normalmente programas) que retengan los mecanismos importantes de los sistemas naturales.

Ese mismo año, la importante tesis de Kenneth De Jong estableció el potencial de los AGs demostrando que podían desenvolverse bien en una gran variedad de funciones de prueba, incluyendo paisajes de búsqueda ruidosos, discontinuos y multimodales [28]. Unos 15 años más adelante, David Goldberg, actual delfín de los algoritmos genéticos, conoció a Holland, y se convirtió en su estudiante. Golberg era un ingeniero industrial que trabajó en diseño de pipelines, y fue uno de los primeros que trató de aplicar los algoritmos genéticos a problemas industriales [2]. En 1932, Cannon visualizó la evolución natural como un proceso de aprendizaje. Alan Turing reconoció, en 1950, que debe haber una conexión obvia entre el aprendizaje de máquina y la evolución y señaló que se podrían desarrollar programas para jugar ajedrez usando esta técnica. Campbell conjeturó en 1960 que en todos los procesos que llevan a la expansión del conocimiento, se involucra un proceso ciego de variación y supervivencia selectiva. Los primeros intentos de aplicar de manera formal la teoría de la

evolución, a problemas prácticos de ingeniería, apareció en las áreas de control de procesos estadísticos, aprendizaje de máquina y optimización de funciones. Tal vez el primer intento serio de este tipo se dio en el trabajo que realizaron G.E.P. Box y sus colegas G.J. Friedman, W.W. Bledsoe y H.J. Bremermann en 1957, en el desarrollo de una técnica que denominaron Operación Evolutiva, la cual se aplicó a una planta de manufactura para manejarla, y que se implanto sobre la base de los votos de un comité de jefes técnicos. Bajo este esquema, la planta se veía como a una especie en evolución. La calidad del producto avanzaba a través de mutaciones aleatorias y la selección era determinada por el comité [3,8]. Por su parte, Friedberg intentó, en 1958, hacer que un programa en lenguaje de máquina se mejorara a sí mismo, seleccionando instrucciones que se asociaran más frecuentemente con un resultado exitoso. La comunidad de Inteligencia Artificial de la época prestó poca atención a su trabajo, y en algunas ocasiones lo atacó despiadadamente. Por ejemplo, Minsky lo criticó duramente, argumentando que una búsqueda puramente aleatoria era mucho mejor que el algoritmo de Friedberg (este argumento aún es esgrimido infundadamente por algunos miembros de la comunidad científica en contra de los algoritmos genéticos) [3]. El trabajo de Bremermann, en 1958, se enfocó más a la optimización, introduciendo el importante manejo de un valor de aptitud, y definiendo a un individuo como una cadena de símbolos binarios (unos y ceros). Bremermann advirtió, acertadamente, que la mutación jugaba un papel importante en la evolución, pues impedía el estancamiento en mínimos locales [3]. Barricelli ofreció, en 1954, una de las primeras simulaciones que usaba principios evolutivos, utilizando los mismos procedimientos generales que se usan hoy en día en la disciplina conocida como vida artificial. Sin embargo, en este trabajo, así como el que Reed realizó posteriormente en 1967, se concluyó que el cruce no parecía mejorar la velocidad de la adaptación selectiva, y el operador primordial era la mutación [3].

El siguiente desarrollo importante en el campo vino en 1966, cuando L.J. Fogel, A.J. Owens y M.J. Walsh introdujeron en América una técnica que llamaron programación evolutiva. En este método, las soluciones candidatas para los problemas se representaban como máquinas de estado finito sencillas; su algoritmo funcionaba mutando aleatoriamente una de estas máquinas simuladas y conservando la mejor de las dos. Fue Fogel el que introdujo la primera técnica evolutiva que realmente funcionó más o menos dentro de los lineamientos actuales de la computación evolutiva. Su programación evolutiva consistía en hacer evolucionar autómatas de estados finitos por medio de mutaciones. Fogel introdujo los importantes conceptos de población y selección, y aunque las revisiones iniciales de su trabajo fueron favorables, algunos investigadores, como Solomonoff, enfatizaron que el método de Fogel no debía verse en su estado actual (en 1966) como algo particularmente útil para resolver problemas, a excepción de los más simples posibles [3, 28]. Otra técnica evolutiva dirigida particularmente a la optimización de funciones continuas de alta complejidad se desarrolló en Alemania, en 1965, por Ingo Rechenberg y Schwefel. Esta técnica, llamada estrategia evolutiva, se utilizó inicialmente para resolver problemas ingenieriles que desafiaban a los métodos de optimización tradicionales, como el gradiente conjugado, y se basa en la modificación sistemática de un vector de números reales (representando las variables de decisión del problema) mediante operadores probabilísticos, usando ciertos criterios para decidir en qué dirección dirigir la búsqueda. La estrategia evolutiva utiliza como operador principal a la mutación, y en su versión más reciente usa el cruce como operador secundario [3]. Aunque el australiano Fraser propuso, desde fines de los 50, un procedimiento muy similar al que John Holland llamó planes evolutivos a fines de los 60, es al segundo al que se le suele atribuir la creación de la técnica que se conoce como algoritmo genético, a raíz de que Holland publicara el libro Adaptation in Natural and Artificial Systems en 1975. La principal diferencia del algoritmo genético con las técnicas antes mencionadas, es que utiliza el cruce como operador principal y a la mutación como operador secundario (e incluso

opcional). El algoritmo genético, al igual que las redes neuronales, funciona como una caja negra que recibe ciertas entradas y produce (tras una cantidad de tiempo indeterminada) las salidas deseadas [3]. En 1994, Karl Sims publicó Evolving Virtual Creatures en la conferencia SIGGRAPH, en la que despertó el interés de expertos y del público en general. Sims reprodujo en su computadora un entorno natural en el que se simulaban diversos medios como el acuático y el terrestre, con consideración de parámetros físicos como gravedad, rozamiento y viscosidad. Asimismo, dotó a la computadora de un conjunto de bloques con los que construyó criaturas virtuales [11]. 1.4. BASES BIOLÓGICAS DE LA COMPUTACIÓN EVOLUTIVA. Desde el punto de vista biológico, la CE se basa en tres teorías: Evolución de Darwin, la de seleccionismo de Weismann y la de genética de Mendel [4]. Postulados de la selección natural que conforman las bases biológicas de la CE [4]: 1. No todos los individuos de una misma especie son iguales. Pueden ser heredadas pequeñas variaciones a sus descendientes.

2. Dichas variaciones podrían facilitar la supervivencia a sus portadores en determinados ambientes.

3.

En

las

poblaciones

en

cada

generación

el

número

permanece

aproximadamente constante, por el hecho de que no todos sobreviven.

4. Los individuos portadores de la mejor adaptación irán incrementando en relación de parte de la población al transmitir sus características a sus descendientes.

5. Al irse agregando características favorables, luego de cierto numero de generaciones se forma una nueva especie que difiere mucho del grupo original.

La NeoDarwinista combina la teoría de Darwin con los aportes de la Genética, conocida también con el nombre de Teoría Sintética de la Evolución. Esta teoría postula un principio que es altamente relevante para la CE: La unidad sobre la que actúa la evolución no es el individuo, sino otra de orden superior, La población [4].

De entre las teorías formuladas para explicar cómo se heredan las características, una merece especial mención. Esta es la de Mendel, que proporcionó el fundamento sobre el cual se ha basado toda la investigación genética posterior [4].

Para explicar los resultados obtenidos en sus experimentos, Mendel formuló una serie de hipótesis para explicar resultados obtenidos. Las hipótesis formuladas por Mendel fueron las siguientes [4]:

1. En cada organismo existe un par de factores que regulan la aparición de una determinada característica (Hoy en día, a estos factores son denominamos genes).

2. El organismo obtiene tales factores de sus padres, un factor por cada padre.

3. Cada uno de estos factores se transmite como una unidad discreta inmodificable.

4. Primera ley de Mendel, o ley de la segregación.

5. Si un organismo posee dos factores diferentes para una característica dada, uno de ellos debe expresarse y excluir totalmente al otro. Hoy en día, los

biólogos usan el término alelo para describir las formas alternativas de un gen que controla la aparición de una característica dada.

Por su parte, la teoría de Weismann ha tenido implicaciones cruciales para la evolución: Demostró que los cambios en el cuerpo, debido al uso o el desuso de partes del mismo, no se reflejan en el plasma del germen, y por consiguiente, no pueden ser heredados. Con experimentos

probó que el

cuerpo del padre transmite meramente su germen plasmático, invalidando así la teoría Lamarkista [4].

1.5. COMPONENTES DE UN ALGORITMO EVOLUTIVO Los componentes de un algoritmo evolutivo se `pueden observar en la figura 1.1 [5]: 1. Una representación genética de soluciones del problema. 2. una manera de crear una población inicial con estas estructuras. 3. una función de aptitud que juegue el papel de ambiente y que jerarquice las soluciones en términos de su efectividad en la resolución del problema. 4. un mecanismo de selección y un conjunto de operadores que motoricen la búsqueda modificando parcialmente las estructuras de solución. 5. valores para los parámetros que determinan la dinámica evolutiva.

Figura 1.1. Estructura De Los Algoritmos Evolutivos

Los Algoritmos Evolutivos han emergido como una clase de búsqueda aleatoria de varios puntos, concurrentemente, sobre un espacio de soluciones factibles; los AEs requieren de mucho poder de cómputo y espacio de memoria lo cual los hace interesantes para paralelizarlos. La paralelización del AE mejora considerablemente tanto el desempeño del algoritmo como la calidad de las soluciones reportadas debido a que se pueden manipular grandes espacios de búsqueda y además abarata los costes del hardware [7]. Los Algoritmos Evolutivos requieren que se les especifique la codificación de los individuos y una función de evaluación que mida la aptitud de cada individuo. La función de Aptitud es la guía que emplean estos algoritmos para explorar de forma eficiente su amplio espacio de búsqueda de posibles soluciones [7]. Los algoritmos evolutivos han sido amplia y exitosamente usados para diseños de aplicaciones fuera de línea. En el campo de la ingeniería de control de sistemas, estas aplicaciones incluyen diseño de controladores, identificación de modelos, análisis de estabilidad robusta, fiabilidad a de sistemas y diagnostico de fallas [9].

Los Algoritmos Evolutivos pueden considerarse una técnica de aprendizaje no supervisado, es decir, aprendizaje inductivo por observación y descubrimiento [22]: •

Estos algoritmos generan ejemplos por si mismos.

•

La creación de nuevos ejemplos (puntos de búsqueda) por el algoritmo es una apuesta inductiva sobre la base del conocimiento existente.

Los algoritmos evolutivos se distinguen también por no quedar atrapados fácilmente en mínimos locales, como la mayor parte de las técnicas de búsqueda clásicas, además de usar operadores probabilísticos más robustos que los operadores determinísticos, que las otras técnicas suelen usar. No obstante, siendo una heurística, tampoco pueden garantizar encontrar siempre la solución óptima, si bien la experiencia acumulada hasta la fecha parece demostrar que, cuando se utilizan apropiadamente, pueden proporcionar soluciones muy aceptables y, en la mayoría de los casos, superiores a las encontradas con otras técnicas de búsqueda y optimización [3].

La clara ventaja de los Algoritmos Evolutivos es su aplicabilidad universal a cualquier tipo de espacio de estructuras [22].

1.6. MODELOS SOBRE EL ESQUEMA GENERAL Hasta hace poco era común hablar de Algoritmos Genéticos (AG) en general, en vez de identificar diferentes tipos de CE, ya que el resto de los algoritmos se pueden interpretar como variaciones o mejoras de los AG, más conocidos [25,14]. -

Algoritmos Genéticos: trabajan con una población de cadenas binarias con

el fin obtener la máxima generalidad y el máximo grado de

paralelismo implícito [22]. -

Programas Evolutivos: los individuos pueden ser cualquier estructura de datos [22].

-

Programas Genéticos: los individuos son programas o autómatas (longitud variable), generalmente representados en forma de árbol [22].

-

Estrategias Evolutivas: trabajan con números reales que codifican las posibles soluciones de problemas numéricos [22].

La agregación simulada (Simulated Annealing) se puede considerar una simplificación de los AG cuyo origen está en los procedimientos físicos de solidificación controlada [25]. 1.7. ALGORITMOS GENÉTICOS (AG) Los primeros hechos relacionados con los Algoritmos Genéticos (en adelante AGs) surgieron en 1932 cuando Cannon interpreta la evolución natural como un proceso de aprendizaje muy similar al proceso mediante el cual una persona aprende por ensayo y error. También en 1950 Turing reconoce una conexión entre la evolución y el aprendizaje de una máquina [24]. Los investigadores en computación observaron que esta clase de algoritmos podía utilizarse también para optimizar funciones. De hecho, aunque las primeras descripciones técnicas y definiciones de adaptación provienen de la biología, ya en este contexto, adaptación designa cualquier proceso por el cual una estructura va modificándose de forma progresiva para lograr el comportamiento óptimo en su entorno. Es decir, los procesos adaptativos son básicamente procesos de optimización, pero es difícil aglutinarlos y unificar su estudio

porque

las

estructuras

modificables

son

complejas

y

su

comportamiento es incierto [24, 25]. Los algoritmos genéticos son métodos sistemáticos para la resolución de problemas de búsqueda y optimización que aplican a estos los mismos métodos de la evolución biológica: selección basada en la población, reproducción sexual y mutación. Los AG utilizan el cruce como operación principal y a la mutación como operador secundario e incluso opcional [2,3, 27]. Los mecanismos de selección del más apto y de reproducción sexual del algoritmo genético, son los encargados de preservar las características más

adecuadas de cada individuo a fin de hacer converger a la población en soluciones óptimas [3]. Mediante la selección se determina que miembros de una población sobreviven para reproducirse, y mediante la reproducción se asegura la mezcla y recombinación de los genes de la descendencia [24].

Esta mezcla del material genético permite que las especies evolucionen mucho mas rápidamente de lo que lo harían si tuvieran sólo la copia de los genes de uno de sus progenitores [24]. En un algoritmo genético, tras parametrizar el problema en una serie de variables, (xi,...,xn) se codifican en un cromosoma. Todos los operadores utilizados por un algoritmo genético se aplicarán sobre estos cromosomas, o sobre poblaciones de ellos [2]. Aunque no se sabe aún de manera completa la información específica codificada en los cromosomas de un individuo, las siguientes propiedades generales son aceptadas por todos los especialistas en el tema [15]:

a) La evolución es un proceso que opera fundamentalmente sobre los cromosomas. b) El proceso de selección natural es el responsable de que aquellos individuos que tienen mejor adaptación al entorno se reproduzcan más que los poco adaptados. c) En la reproducción es donde tiene lugar la evolución. d) La evolución biológica carece de memoria. En el algoritmo genético va implícito el método para resolver el problema; son solo parámetros de tal método los que están codificados, a diferencia de otros algoritmos evolutivos como la programación genética. Hay que tener en cuenta que un algoritmo genético es independiente del problema, lo cual lo hace un

algoritmo robusto, por ser útil para cualquier problema, pero a la vez débil, pues no está especializado en ninguno [2]. Las soluciones codificadas en un cromosoma compiten para ver cuál constituye la mejor solución (aunque no necesariamente la mejor de todas las soluciones posibles). El ambiente, constituido por las otras camaradas soluciones, ejercerá una presión selectiva sobre la población, de forma que sólo los mejor adaptados sobrevivan o leguen su material genético a las siguientes generaciones, igual que en la evolución de las especies [2].

Los algoritmos genéticos han demostrado ser un método útil de búsqueda de soluciones satisfactorias (calidad/tiempo), en problemas cuyo espacio de solución es difícil de tratar por otros métodos por su amplio rango. Estas posibilidades brindan la oportunidad de ajustar los parámetros de tal manera que la convergencia a la solución sea mucho más eficiente en cuanto a la relación calidad/tiempo que los métodos exactos pueden ofrecer [6]. Para encontrar óptimos globales, los algoritmos de optimización hacen uso de dos técnicas: explorar áreas desconocidas en el espacio de búsqueda y explotar el conocimiento obtenidos de puntos previamente evaluados. Los algoritmos combinan ambas técnicas de una forma eficiente [17]. Los resultados de los AGs mejoran significativamente si se usa una representación y unos operadores genéticos naturales.

1.7.1. Codificación de las variables Los algoritmos genéticos requieren que el conjunto se codifique en un cromosoma. Cada cromosoma tiene varios genes, que corresponden a sendos parámetros del problema. Para poder trabajar con estos genes en el ordenador, es necesario codificarlos en una cadena, es decir, una ristra de símbolos (números o letras) que generalmente va a estar compuesta de 0s y 1s aunque hay otras codificaciones posibles usando alfabetos de diferente cardinalidad [2, 28].

La mayoría de las veces, una codificación correcta es la clave de una buena resolución

del

problema.

Esto

puede

llevar

a

usar

cromosomas

bidimensionales, o tridimensionales, o con relaciones entre genes que no sean puramente lineales de vecindad. En algunos casos, cuando no se conoce de antemano el número de variables del problema, caben dos opciones: codificar también el número de variables, fijando un número máximo, o bien, lo cual es mucho más natural, crear un cromosoma que pueda variar de longitud. Para ello, claro está, se necesitan operadores genéticos que alteren la longitud. Normalmente, la codificación es estática, pero en casos de optimización numérica, el número de bits dedicados a codificar un parámetro puede variar, o incluso lo que representen los bits dedicados a codificar cada parámetro [2]. 1.7.2. Operadores Una vez que la selección ha elegido a los individuos aptos, éstos deben ser alterados aleatoriamente con la esperanza de mejorar su aptitud para la siguiente generación. Existen dos estrategias básicas para llevar esto a cabo. 1.7.2.1. Cruce Consiste en el intercambio de material genético entre dos cromosomas (a veces más, como el operador orgía propuesto por Eiben). El teorema de los esquemas confía en él para hallar la mejor solución a un problema, combinando soluciones parciales [2]. Implica elegir a dos individuos para que intercambien segmentos de su código, produciendo una “descendencia'' artificial cuyos individuos son combinaciones de sus padres

como se muestra en la figura 1.2. Este proceso pretende

simular el proceso análogo de la recombinación que se da en los cromosomas durante la reproducción sexual. Como norma general se aplica después de un proceso de selección de dos individuos [15, 28].

Padres (criadores)

0

0

0

0

1

1

1

1

0

0

0 1

0

0

1

1

0

1

0

1

0

1

0

1

0

1

0

1

0

0

0

1

Hijos (vástagos)

Figura1.2. Aplicación del operador de cruce.

Las 2 formas más comunes de reproducción sexual son: uso de un punto único de cruce y uso de 2 puntos de cruce [6,26, 28]. Cuando se usa un solo punto de cruce, éste se escoge de forma aleatoria sobre la longitud de la cadena que representa el cromosoma, y a partir de él se realiza el intercambio de material de los 2 individuos [2,6, 26]. Cuando se usan 2 puntos de cruce, se procede de manera similar, pero en este caso Se eligen dos puntos de ruptura al azar para intercambiar [6,26]. •

cruce uniforme: se genera un patrón aleatorio de 1s y 0s, y se intercambian los bits de los dos cromosomas que coincidan donde hay un 1 en el patrón. O bien se genera un número aleatorio para cada bit, y si supera una determinada probabilidad se intercambia ese bit entre los dos cromosomas [2,6].

•

cruce especializado: en algunos problemas, aplicar aleatoriamente el cruce da lugar a cromosomas que codifican soluciones inválidas; en este caso hay que aplicar el cruce de forma que genere siempre soluciones válidas [2].

•

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.

Normalmente el cruce se maneja dentro de la implementación del algoritmo genético como un porcentaje que indica con qué frecuencia se efectuará. Esto significa que no todas las parejas de cromosomas se cruzarán, sino que habrá algunas que pasarán intactas a la siguiente generación. De hecho existe una técnica desarrollada hace algunos años en la que el individuo más apto a lo largo de las distintas generaciones no se cruza con nadie, y se mantiene intacto hasta que surge otro individuo mejor que él, que lo desplazará. Dicha técnica es llamada elitismo, y no debe sorprender el hecho de que haya sido desarrollada en Alemania [26]. 1.7.2.1.1. Cruces para permutación 1.7.2.1.1.1. Cruce por emparejamiento parcial (PMX) Toma una subsecuencia del cromosoma del padre y procura preservar el orden absoluto de los genes, es decir, orden y posición en el cromosoma, del resto del cromosoma lo más parecido posible de la madre. Aparece también en la bibliografía como PMX [23]. 1.7.2.1.1.2. Cruces por orden (OX)

Cruce de mapeamiento parcial o Cruce por orden: toma una subsecuencia del cromosoma del padre y procura preservar el orden relativo de los genes del resto del cromosoma lo más parecido posible de la madre. Se puede encontrar en la bibliografía como OX [23].

Este cruce sólo considera el orden relativo de las soluciones, no su posición. Existen dos variantes de este cruce que toman en cuenta las posiciones (muy usados en planificación de tareas).

1.7.2.1.1.2.1. Variantes al Cruce por orden

-

Cruce por orden con posiciones prioritarias No se elige un tramo para intercambiarlo entre los progenitores, sino un

conjunto de posiciones al azar. (El resto no cambia). -

Cruce por orden con orden prioritario: Los individuos no intercambian genes, sino el orden relativo existente entre ellas.

1.7.2.1.1.3. Cruce por ciclos (CX) Se toma el primer gen del cromosoma del padre, poniéndolo en la primera posición del hijo, y el primer gen del cromosoma de la madre, poniéndolo dentro del cromosoma del hijo en la posición que ocupe en el cromosoma del padre. El gen que está en la posición que ocupa el gen del cromosoma del padre igual al primer gen del cromosoma de la madre se va a colocar en la posición que ocupe en el cromosoma del padre, y así hasta rellenar el cromosoma del hijo. Este método también es conocido en la bibliografía como CX. 1.7.2.1.1.4. Cruce por recombinación de rutas (ERX)

La descendencia se construye combinando los cromosomas que interconectan los genes de los progenitores. 1.7.2.2. Mutación En la Evolución, una mutación es un suceso bastante poco común (sucede aproximadamente una de cada mil replicaciones), como ya se ha visto anteriormente. En la mayoría de los casos las mutaciones son letales, pero en promedio, contribuyen a la diversidad genética de la especie. En un algoritmo genético tendrán el mismo papel, y la misma frecuencia (es decir, muy baja) [2]. Realiza un cambio a uno de los genes de un cromosoma elegido aleatoriamente. Cuando se usa una representación binaria, el gen seleccionado

se sustituye por su complemento (un cero cambia en uno y viceversa) como se puede observar en la figura 1.3. Este operador permite la introducción de nuevo material cromosómico en la población, tal y como sucede con sus equivalentes biológicos [26]. Individuo original

1

0

1

1

1

1

1

1

0

1

1

1

0

0

1

1

Individuo después de la mutación

Figura 1.3. Aplicación del operador de mutación.

Al igual que la cruce, la mutación se maneja como un porcentaje que indica con qué frecuencia se efectuará, aunque se distingue de la primera por ocurrir mucho más esporádicamente (el porcentaje de cruce normalmente es de más del 60%, mientras que el de mutación normalmente nunca supera el 5%) [26]. El operador de mutación que se acaba de describir representa la denominada mutación clásica. Este operador también puede tener algunas variantes al operador clásico [4]. 1.7.2.2.1. Mutaciones sobre genes: Cuando un gen puede tomar más de dos valores (llamados también alelos), la mutación se realiza cambiando el valor actual por otro más o menos parecido [4].

1.7.2.2.2. Mutaciones no estacionarías: en algunas ocasiones es conveniente reducir la tasa de mutación (probabilidad de mutación) según el programa progresa. La forma de implementar tal reducción depende en gran medida del

problema; una manera sencilla es multiplicando la probabilidad de mutación por un factor de reducción cada cierto número de generaciones [4]. 1.7.2.2.3. Mutaciones no uniformes: Se dan distintas probabilidades de mutación a cada gen (o a cada bit dentro de un gen), dependiendo de su significado. 1.7.2.3. Variantes en operadores básicos para números reales Aunque t5ambien se puede utilizar los mecanismos mencionados para codificar binarios, existen variantes relevantes si se trabaja con representación basada en números reales.

Por ejemplo Cruce

C1

escalar o vector de números reales

C2

escalar o vector de números reales

H1 = C1 + α (C1 − C2 )

(1-1)

H 2 = C2 + α (C2 − C1 )

(1-2)

Hu =

C1 + C2 2

(1-3)

También se pueden producir más de dos hijos asignando una terna operación posible a cada caso.

Mutación

C1

Cromosoma a ser mutado

H1 = C1 + α∆f

Gradiente ascendente

H1 = C1 − α∆f

Gradiente descendente

Depende de si se quiere minimizar o maximizar la función objetivo.

El gradiente pudiera ser analítico explicito derivable,

se

selecciona

el

individuo

∂f si f f es derivable. Si f no e ∂C

a

mutar

y

otro

que

difiera

significativamente del C1 ∗ puede ser en cuanto a función de ajuste o de estructura.

∆f fC − fC1 ∗ = 1 ∆C1 C1 − C1 ∗

(1-4)

Si C1 es un escalar, es directo el gradiente. Si C1 es un vector habrá un gradiente distinto para cada elemento del cromosoma, ya que para cada elemento varia el valor del denominador. 1.7.2.4. Otros operadores No se usan en todos los problemas, sino sólo en algunos, y en principio su variedad es infinita. Generalmente son operadores que exploran el espacio de soluciones de una forma más ordenada, y que actúan más en las últimas fases de la búsqueda, en la cual se pasa de soluciones "casi buenas" a "buenas" soluciones [2]. 1.7.2.4.1. Cromosomas de longitud variable Hay problemas en los que no se conoce de antemano el número de parámetros del mismo. En estos casos, se necesitan dos operadores más: añadir y eliminar. Estos operadores se utilizan para añadir un gen, o eliminar un gen del cromosoma. La forma más habitual de añadir un locus es duplicar uno ya existente, el cual sufre mutación y se añade al lado del anterior. En este caso, los operadores del algoritmo genético simple (selección, mutación, cruce) funcionarán de la forma habitual, salvo, claro está, que sólo se hará cruce en la zona del cromosoma de menor longitud [2]. Estos operadores permiten, además, crear un algoritmo genético de dos niveles: a nivel de cromosoma y a nivel de gen [2].

1.7.2.4.2. Operadores de nicho (ecológico) Otros operadores importantes son los operadores de nicho. Estos operadores están encaminados a mantener la diversidad genética de la población, de forma que cromosomas similares sustituyan sólo a cromosomas similares, y son especialmente útiles en problemas con muchas soluciones; un algoritmo genético con estos operadores es capaz de hallar todos los máximos, dedicándose cada especie a un máximo. Más que operadores genéticos, son formas de enfocar la selección y la evaluación de la población [2]. 1.7.2.4.3. Operadores especializados En una serie de problemas hay que restringir las nuevas soluciones generadas por los operadores genéticos, pues no todas las soluciones generadas van a ser válidas, sobre todo en los problemas con restricciones. Por ello, se aplican operadores que mantengan la estructura del problema. Otros operadores son simplemente generadores de diversidad, pero la generan de una forma determinada [2]: •

Zap: en vez de cambiar un solo bit de un cromosoma, cambia un gen completo de un cromosoma [2].

•

Creep: este operador aumenta o disminuye en 1 el valor de un gen; sirve para cambiar suavemente y de forma controlada los valores de los genes [2].

•

Transposición: similar al cruce y a la recombinación genética, pero dentro de un solo cromosoma; dos genes intercambian sus valores, sin afectar al resto del cromosoma. Similar a este es el operador de eliminación-reinserción: en el que un gen cambia de posición con respecto a los demás [2].

•

Agrega Alternativa: generaliza una restricción sobre un atributo, cambiando un 0 por un 1 en la sub cadena que corresponde al atributo [17].

•

Elimina Condición: lleva a cabo una generalización más drástica, remplazando todos los bits de una sub cadena por 1s, esto es, elimina por completo la restricción en un atributo dado [17].

•

Duplicación: Copia exactamente la información de un individuo a otro [4].

•

Translocación: Se intercambian trozos del código genético de un individuo [4].

•

Inversión: Este operador modifica la información genética de un individuo

tomando

dos

componentes

(genes)

del

mismo

e

intercambiando los valores de éstos; es decir, al primero se le asigna la información del segundo y al segundo la información del primero [4]. •

Dominación: Determina algunos componentes (genes) que son preponderantes en el individuo para su valor de aptitud y da preferencia a esos componentes en otros operadores genéticos [4].

•

Segregación: Es lo contrario a la dominación. En este caso, los componentes segregados no influyen de manera determinante en el grado de adaptabilidad del individuo [4].

1.7.3. Función de adaptación

La función de adaptación (fitness) define el criterio para ordenar las hipótesis potenciales y para seleccionarlas probabilísticamente, para su inclusión en la siguiente generación de la población. Si la tarea consiste en aprender reglas de clasificación, entonces la función de adaptación contiene un componente para evaluar la precisión de las hipótesis sobre un conjunto de entrenamiento dado [17]. Es la base para determinar qué soluciones tienen mayor o menor probabilidad de sobrevivir.

Se tiene que tener un balance entre una función que haga diferencias muy grandes (y por lo tanto una convergencia prematura) y diferencias muy pequeñas (y por lo tanto un estancamiento). La función de aptitud no es más que la función objetivo de nuestro problema de optimización. El algoritmo genético únicamente maximiza, pero la minimización puede realizarse fácilmente utilizando el recíproco de la función maximizante (debe cuidarse, por supuesto, que el recíproco de la función no genere una división por cero). Una característica que debe tener esta función es que debe ser capaz de "castigar" a las malas soluciones, y de "premiar" a las buenas, de forma que sean estas últimas las que se propaguen con mayor rapidez [26]. 1.7.4. El teorema del esquema Proporciona el fundamento teórico de porqué los AG pueden resolver diversos problemas. En su análisis se considera el proceso de selección y los operadores de cruce y mutación. Un esquema se construye utilizando un nuevo símbolo (*) para representar un comodín (no importa) que puede aparear ambos valores (0 o 1). El esquema 11*00* representa las cadenas: 111001, 111000, 110001, 110000. El orden de un esquema es el número de elementos que no son “`*'' dentro del esquema. La longitud que define a un esquema es la distancia entre la primera posición fija y la última posición fija. El teorema dice que: Los esquemas pequeños de bajo orden arriba del promedio reciben un incremento exponencial de representantes en las siguientes generaciones de un algoritmo genético [Holland 92] El teorema del esquema caracteriza la evolución de una población en un algoritmo genético en términos del número de elementos representando cada esquema. Sea m(s, t) el numero de elementos del esquema s al tiempo t. El

teorema del esquema describe el valor esperado de m(s, t + 1) en términos de m(s, t) y otras propiedades del esquema, la población, y los parámetros del algoritmo genético [17]. Un algoritmo genético tiene también una serie de parámetros que se tienen que fijar para cada ejecución, como los siguientes [2]: •

Tamaño de la población: debe de ser suficiente para garantizar la diversidad de las soluciones, y, además, tiene que crecer más o menos con el número de bits del cromosoma. Por supuesto, depende también del ordenador en el que se esté ejecutando. El número de soluciones en una población es altamente relevante para la velocidad de optimización.

•

Condición de terminación: lo más habitual es que la condición de terminación sea la convergencia del algoritmo genético o un número prefijado de generaciones.

1.7.5. Evaluación Durante la evaluación, se decodifica el gen, convirtiéndose en una serie de parámetros de un problema, se halla la solución del problema a partir de esos parámetros, y se le da una puntuación a esa solución en función de lo cerca que esté de la mejor solución. A esta puntuación se le llama fitness [2]. El fitness determina siempre los cromosomas que se van a reproducir, y aquellos que se van a eliminar, pero hay varias formas de considerarlo para seleccionar la población de la siguiente generación [2]. Una vez evaluado el fitness, se tiene que crear la nueva población teniendo en cuenta que los buenos rasgos de los mejores se transmitan a esta. Para ello, hay que seleccionar a una serie de individuos encargados de tan ardua tarea. 1.7.6. Métodos de selección El mecanismo de selección permite orientar la búsqueda a aquellos puntos más promisorios con la mayor adaptación observada hasta el momento. La

selección no produce puntos nuevos en el espacio de búsqueda, sino que determina que individuos dejaran descendencia y en que cantidad en la próxima generación [12]. Un algoritmo genético puede utilizar muchas técnicas diferentes para seleccionar a los individuos que deben copiarse hacia la siguiente generación, pero abajo se listan algunos de los más comunes. Algunos de estos métodos son mutuamente exclusivos, pero otros pueden utilizarse en combinación, algo que se hace a menudo [28]: •

Selección elitista: se garantiza la selección de los miembros más aptos de cada generación [28].

•

Selección proporcional a la aptitud: los individuos más aptos tienen más probabilidad de ser seleccionados, pero no la certeza [28].

•

Selección por rueda de ruleta o universal (R): Conceptualmente, esto puede representarse como un juego de ruleta, cada individuo obtiene una sección de la ruleta, pero los más aptos obtienen secciones mayores que las de los menos aptos. Luego la ruleta se hace girar, y en cada vez se elige al individuo que “`posea'' la sección en la que se pare la ruleta [2, 15, 26,28].

•

Selección escalada: al incrementarse la aptitud media de la población, la fuerza de la presión selectiva también aumenta y la función de aptitud se hace más discriminadora. Este método puede ser útil para seleccionar más tarde, cuando todos los individuos tengan una aptitud relativamente alta y sólo les distingan pequeñas diferencias en la aptitud [28].

•

Selección por torneo (T): se eligen subgrupos de individuos de la población, y los miembros de cada subgrupo compiten entre ellos. Sólo se elige a un individuo de cada subgrupo para la reproducción [2, 26,28].

•

Selección por rango: a cada individuo de la población se le asigna un rango numérico basado en su aptitud, y la selección se basa en este ranking, en lugar de las diferencias absolutas en aptitud. La ventaja de este método es que puede evitar que individuos muy aptos ganen

dominancia al principio a expensas de los menos aptos, lo que reduciría la diversidad genética de la población y podría obstaculizar la búsqueda de una solución aceptable [2,28]. •

Selección

generacional:

la

descendencia

de

los

individuos

seleccionados en cada generación se convierte en toda la siguiente generación. No se conservan individuos entre las generaciones [28]. •

Selección por estado estacionario: la descendencia de los individuos seleccionados en cada generación vuelven al acervo genético preexistente, reemplazando a algunos de los miembros menos aptos de la siguiente generación. Se conservan algunos individuos entre generaciones [28].

•

Selección jerárquica: los individuos atraviesan múltiples rondas de selección en cada generación. Las evaluaciones de los primeros niveles son más rápidas y menos discriminatorias, mientras que los que sobreviven hasta niveles más altos son evaluados más rigurosamente. La ventaja de este método es que reduce el tiempo total de cálculo al utilizar una evaluación más rápida y menos selectiva para eliminar a la mayoría de los individuos que se muestran poco o nada prometedores, y sometiendo

a

una

evaluación

de

aptitud

más

rigurosa

y

computacionalmente más costosa sólo a los que sobreviven a esta prueba inicial [28]. •

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: igual que el 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.

•

Selección estocástica universal SUS: es análogo a la ruleta con M puntos igualmente espaciados entre si, de modo que con un solo lanzamiento se obtienen M ganadores. El método SUS no tiene sesgo y su dispersión es la mínima posible [12].

•

Selección por sorteo :Se asume que cada individuo de la población tiene una cierta puntuación, normalmente relacionada a su valor de aptitud, con la cual se calcula la probabilidad pi que tiene cada individuo i’ para formar parte de la muestra [4]: p

i=

fi

(1-5)

n

∑ fj j =0

Donde:

n : tamaño de la población f: función de aptitud 1.7.7. Mecanismos de Reemplazo

Los mecanismos de reemplazo permiten mantener la población constante. Entre los mecanismos de reemplazo, los de mayor uso y aceptación son [4]:

Reemplazo directo Los progenitores son reemplazados directamente por sus descendientes. Obviamente, este criterio solo puede usarse si s < n [4]. Reemplazo por similitud Cada descendiente reemplaza aquel miembro de la población que más se le asemeja. Al igual que en el caso directo, debe cumplirse que s < n [4]. Reemplazo por inserción (,) Este criterio puede usarse con variación según la relación entre s y n [4]:

Si s

n; Se escogen s individuos de la población, los cuales serán sustituidos

por los s descendientes. Esta escogencia se hace a través de algún criterio de muestreo, normalmente se toman los peores.

Si S > n: Se toma una muestra (con algún criterio) de tamaño n de los s descendientes. Bajo este esquema, cada individuo vive sólo por una generación. Reemplazo por inclusión (+} Se unen los n miembros de la población con los s descendientes, conformando una población auxiliar de tamaño s + n. Luego, de esta población auxiliar, se toma una muestra de tamaño n según algún criterio de selección [4]. 1.7.8. Características de los AGs

Los AGs poseen características que determinan su funcionamiento y su aplicabilidad en determinados problemas. Estas son [4]:

Búsqueda Ciega. No disponen de ningún conocimiento específico del problema. Codificación de Parámetros. Se trabaja con la codificación de un conjunto de parámetros (o un subconjunto de ellos) y no con los parámetros en sí. Búsqueda Basada en Población. Se busca desde una población de puntos y no desde uno solo. Función Objetivo como Elemento a Optimizar. Se usa una función objetivo o función de evaluación para definir lo que se desea optimizar, sin requerir más información derivada o auxiliar. Operadores Aleatorios. Se hace uso de operadores estocásticos para las transformaciones, en vez de reglas de transición determinísticas

1.7.9. ¿Como funcionan?

El funcionamiento de un algoritmo genético clásico comienza generando una población inicial aleatoria de candidatos a ser el óptimo y usa la información contenida en ella con el fin de producir iterativamente nuevas y “mejores” poblaciones. Esa “calidad” se entiende en términos de la medida que de su idoneidad proporciona la función de ajuste [24].

Para ello, en primer lugar (y una vez codificados los miembros de la población Inicial), se evalúa su idoneidad y se seleccionan los mejores cromosomas. Algunos de estos individuos seleccionados sufren ciertas alteraciones por la acción de diferentes operadores genéticos encargados de introducir nuevos elementos en la población. En los algoritmos genéticos clásicos, dos son los operadores genéticos a destacar: el cruce y la mutación [24].

Los descendientes obtenidos a través de la selección y la recombinación, constituyen lo que se conoce como una generación. El proceso se repite durante generaciones hasta que se alcanza una cierta condición de parada. Es decir, el algoritmo finaliza cuando se ha ejecutado un número determinado de iteraciones prefijado de antemano, cuando se ha encontrado el óptimo [24]. 1.7.10. ¿Por qué utilizar algoritmos genéticos en la optimización?

La razón del creciente interés por los algoritmos genéticos es que estos son un método global y robusto de búsqueda de las soluciones de problemas. La principal ventaja de estas características es el equilibrio alcanzado entre la eficiencia y eficacia para resolver diferentes y muy complejos problemas de grandes dimensiones [24].

1.7.11. Convergencia del Algoritmo

Dado que el algoritmo genético opera con una población en cada iteración, se espera que el método converja de modo que al final del proceso la población sea muy similar, y en el infinito se reduzca a un sólo individuo [6].

Se ha desarrollado toda una teoría para estudiar la convergencia de estos algoritmos en el caso de cadenas binarios. Esta teoría se basa principalmente en considerar que una cadena es un representante de una clase de equivalencia o esquema, reinterpretando la búsqueda en lugar de entre cadenas, entre esquemas [6]. 1.7.12. ¿Cómo saber si es posible usar el Algoritmo Genético? No todos los problemas pudieran ser apropiados para la técnica, y se recomienda en general tomar en cuenta las siguientes características del mismo antes de intentar usarla [26]: · Su espacio de búsqueda (sus posibles soluciones) debe estar delimitado dentro de un cierto rango. · Debe poderse definir una función de aptitud que indique qué tan buena o mala es una cierta respuesta. Las soluciones deben codificarse de una forma que resulte relativamente fácil de implementar en el computador. 1.7.13. Decisiones para implementar un algoritmo genético Las decisiones que hay que tomar para implementar un algoritmo genético son: •

Criterio de codificación. Como se va a almacenar la información en el cromosoma.

•

Criterio de tratamiento de individuos no factibles. Como se van a tratar a los individuos que no cumplan las restricciones

•

Criterio de inicialización. Cómo se va a construir la población inicial del algoritmo genético.

•

Criterio de parada. Determina cuándo el algoritmo ha llegado a una solución aceptable.

•

Función de adaptación.

•

Operadores genéticos.

•

Criterios de reemplazo.

•

Parámetros de funcionamiento. Determinados parámetros que, sin poder ser englobados en ninguno de los anteriores, son fundamentales para el funcionamiento de un algoritmo genético. Es el caso, por ejemplo, del tamaño de la población, la probabilidad de la aplicación de los operadores genéticos.

1.7.14. Ventajas de los AGs •

los algoritmos genéticos son intrínsecamente paralelos, pueden explorar el espacio de soluciones en múltiples direcciones a la vez [28,29].

•

funcionan particularmente bien resolviendo problemas cuyo espacio de soluciones potenciales es realmente grande (demasiado vasto para hacer una búsqueda exhaustiva en un tiempo razonable) [28].

•

se desenvuelven bien en problemas con un paisaje adaptativo complejo, aquéllos en los que la función de aptitud es discontinua, ruidosa, cambia con el tiempo, o tiene muchos óptimos locales [28].

•

Otra área en el que destacan los algoritmos genéticos es su habilidad para manipular muchos parámetros simultáneamente [28,29].

•

Usan operadores probabilísticos, en vez de los típicos operadores determinísticos de las otras técnicas [26].

•

los AGs no saben nada de los problemas que deben resolver [28].

1.7.15. Desventajas o limitaciones que tienen los AG con respecto a otras técnicas de búsqueda Aunque los algoritmos genéticos han demostrado su eficiencia y potencia como estrategia de resolución de problemas, no son la panacea. Los AGs tienen

ciertas limitaciones; sin embargo, se ha demostrado que todas ellas pueden superarse y que ninguna de ellas afecta a la validez de la evolución biológica [28]. •

Pueden tardar mucho en converger, o no converger en absoluto, dependiendo en cierta medida de los parámetros que se utilicen (tamaño de la población, número de generaciones, etc.) [26].

•

Pueden converger prematuramente debido a una serie de problemas de diversa índole [26].

•

El lenguaje utilizado para especificar soluciones candidatas debe ser robusto; es decir, debe ser capaz de tolerar cambios aleatorios que no produzcan constantemente errores fatales o resultados sin sentido [28].

•

Si se elige mal una función de aptitud o se define de manera inexacta, puede que el algoritmo genético sea incapaz de encontrar una solución al problema, o puede acabar resolviendo el problema equivocado [28].

•

Si el tamaño de la población es demasiado pequeño, puede que el algoritmo genético no explore suficientemente el espacio de soluciones para encontrar buenas soluciones consistentemente. Si el ritmo de cambio genético es demasiado alto o el sistema de selección se escoge inadecuadamente,

puede

alterarse

el

desarrollo

de

esquemas

beneficiosos y la población puede entrar en catástrofe de errores, al cambiar demasiado rápido para que la selección llegue a producir convergencia [28]. •

Una dificultad práctica al usar algoritmos genéticos es conocida como crowding. En este fenómeno, un individuo que es mas apto que otros miembros de la población, comienza a reproducirse rápidamente de tal forma que copias de este individuo, o bien de individuos muy parecidos, ocupan una fracción importante de la población reduciendo la diversidad de la población, haciendo la búsqueda más lenta. Eso se puede solucionar escogiendo un apropiado método de selección [17].

•

Se aconseja no utilizar algoritmos genéticos en problemas resolubles de manera analítica. Ya que los métodos analíticos tradicionales consumen mucho menos tiempo y potencia computacional que los [28].

1.7.16. Consideraciones al usar algoritmos genéticos

Tomar cualquier método de optimización para trabajar de una manera óptima requiere alguna experimentación con sus parámetros de configuración y selecciones inadecuadas de éstos conducirán a un bajo rendimiento en la búsqueda. Cuando no se conoce mucho acerca de la superficie de respuesta y calcular el gradiente es computacionalmente intensivo o numéricamente inestable muchas personas prefieren usar métodos de optimización como AG, SA y Simplex los cuales no requieren información del gradiente [16].

Para las aplicaciones donde el cálculo del vector gradiente es numéricamente preciso y rápido, no se recomienda usar los AG, ya que éstos alcanzarán la región óptima mucho más lento que los métodos hill-climbing. Otro tipo de aplicaciones no recomendadas para los AG son aquellas que requieren encontrar el óptimo global exacto, dada la característica de los AG de ser buenos encontrando la región óptima global pero enfrentando problemas algunas veces para localizar el óptimo exacto [16]. 1.7.17. Diferencias entre los Métodos Tradicionales y los A.G.

Se puede decir que los Algoritmos Genéticos difieren de los principales métodos tradicionales de optimización en cuatro puntos fundamentales de los cuales no han sido mencionados [15]:

1. Los A.G. no utilizan derivadas ni otras propiedades de la función objetivo, sino únicamente la propia función objetivo. 2. Los A.G. se rigen mediante reglas de transición probabilísticas, no determinísticas.

1.8. PROGRAMAS EVOLUTIVOS (PEs) Los programas evolutivos fueron presentados en 1994 por Michalewicz. los PEs son métodos que incorporan directamente conocimiento específico a los AGs, puesto que permiten la utilización de estructuras de datos naturales. Además, de perder un poco de generalización, con la incorporación de conocimiento específico, también se pierde el paralelismo implícito (basado en alfabetos de símbolos mínimos). Sin embargo, esta pérdida se compensa con el procesamiento de información más útil [14]. Los PEs no son restrictivos en cuanto a la representación del problema. Mientras en los AGs se hace necesaria una codificación de las soluciones del problema; en los PEs, tal representación se hace de forma directa. Si se diseñan adecuadamente, los PEs pueden competir en eficiencia y calidad de las soluciones con métodos específicos (más costosos de implementar) [23].

Los PEs surgieron al resolver problemas de optimización paramétrica en los que se requería alta precisión [23].

Se distinguen dos grandes grupos de PEs según la naturaleza de los objetos tratados [23]: PEs, especializados en optimización paramétrica PEs, especializados en optimización combinatoria 1.8.1. PEs en optimización paramétrica Por precisión y eficiencia no es conveniente utilizar AGs en problemas de optimización paramétrica. De esta manera, se requería un esquema que permitiese representar a los individuos como arreglos de números reales donde cada uno de esos números seria un gen [4].

1.8.2. PEs en optimización combinatoria Existen algunos problemas que se caracterizan por la existencia de soluciones que se componen secuencialmente, es decir, dando un conjunto de elementos se pueden obtener diferentes arreglos ordenados de estos , permitiendo una basta cantidad de posibilidades; los cuales se denominan problemas de optimización combinatoria [4]. 1.8.3. Programas Evolutivos y Algoritmos Genéticos Desde el punto de vista práctico, se tratarán a los PEs como una variación de los AGs, compartiendo exactamente su estructura básica, con las siguientes distinciones [14]: a. La representación es más natural. Por lo cual, está más cercana al dominio del problema. b. Los operadores genéticos son específicos al contexto del problema. 1.9. ESTRATEGIAS EVOLUTIVAS (EEs) Las Estrategias Evolutivas, desarrolladas en 1964 por Rechenberg, surgieron inicialmente para resolver problemas de optimización paramétrica; con el paso del tiempo fueron incorporando procedimientos propios de la computación evolutiva, con lo que han llegado a convertirse en una disciplina más. Su principal característica es que utilizan una representación de vectores reales, una selección determinística y operadores genéticos específicos de cruce y mutación. [8, 14,25]. Las EEs pueden dividirse en dos tipos: Estrategias Evolutivas Simples y Estrategias Evolutivas Múltiples. 1.9.1. EEs Simples En este caso, se hace evolucionar un solo individuo usando únicamente a la mutación como operador genético. Son relativamente sencillas, y se

denominan también EEs de dos miembros. Debido a que evoluciona un solo individuo a la vez, no son consideradas estrictamente como métodos evolutivos [14]. 1.9.2. EEs Múltiples Surgen como respuesta a las debilidades de las EEs simples, las cuales tienden a converger hacia subóptimos. En las EEs múltiples existen múltiples individuos (población), y se producen en cada generación varios nuevos individuos, usando tanto mutación como cruce (también puede usarse cualquier otro operador [14]. 1.9.3. Estrategias Evolutivas y Algoritmos Genéticos Los puntos de inicio de los AGs y de las EEs son diferentes, puesto que parten de enfoques distintos. Se puede decir que las EEs son un tipo especial de AGs o viceversa. A continuación se presentan las diferencias más significativas entre ambos métodos [14]: a. Las EEs son más fuertes por lo que los AGs son mucho más generales b. El operador fundamental en las EEs es la mutación, mientras que en los AGs es el cruce. c. Los AGs realizan búsqueda global, mientras que en las EEs se presenta exactamente lo contrario.

1.10. Programación evolutiva (EP) La Programación Evolutiva originalmente fue concebida por Lawrence J. Fogel en 1960, es una estrategia de optimización estocástica similar a los Algoritmos Genéticos. El libro "Artificial Intelligence Through Simulated Evolution" publicado en 1966 por Fogel, Owens y Walsh es la publicación clave para las aplicaciones de la EP [14].

Una maquina de estados finitos es un transductor que puede ser estimulado por un alfabeto finito de símbolos de entrada que puede responder a un alfabeto finitos de símbolo de salida, y que posee algún numero finito de estados internos diferentes. La figura 1.4 muestra una maquina de estados finitos, donde os números representan los símbolos de entrada, las letras griegas símbolos de salida, y los caracteres en mayúscula representan los estados [4]. 0/

0/

B

0/

1/

1/

C

A 1/

Figura 1.4. Maquina de estados finitos de tres estados (A,B,C), dos Símbolos de entrada (0,1) y tres símbolos de salida

En la programación evolutiva, un conjunto de maquinas de estado finitos (son los individuos) se expone a un ambiente; esto es, a una secuencia de símbolos observados en un momento dado. Para cada máquina de Estados Finitos, por cada símbolo de entrada que se le presenta se determina el símbolo de salida que da y se compara con el del ambiente (también puede compararse su próximo estado con el que corresponde en el ambiente). Así, la predicción de cada máquina de Estados Finitos es media respecto al ambiente, como una función error (error absoluto, error cuadrático, etc.). Después que se hace la última predicción, un error promedio para cada máquina es calculado para indicar la aptitud de ella. Las máquinas que presenten el mejor resultado (mínimo error) se retienen para ser padres en la próxima generación [4].

Funciones de optimización combinatoria y de valores reales en las cuales, la superficie de optimización es abrupta, presentando muchas soluciones óptimas locales, son bien tratadas a través de la EP [14]. Para la EP, existe una suposición muy importante que consiste en que la función de fitness puede caracterizarse en término de las variables, y además existe una solución óptima (o múltiples óptimos) en función de dichas variables [14]. El método de EP básico involucra tres pasos (repetidos hasta que se excede el umbral de iteraciones o hasta que se encuentre una solución adecuada) [14]: 1. Selección de forma aleatoria de una población inicial de posibles soluciones. 2. Cada solución se replica en una nueva población. 3. A cada solución hija se le calcula y asigna un valor de adaptación. Debe resaltarse que la EP típicamente no utiliza el cruzamiento como operador genético. 1.10.1. Algoritmo General 1. Definir la secuencia de símbolos y función objetivo como una matriz de pago. 2. Inicializar la población de Máquinas de Estado Finito (MEF). 3. Introducir símbolo de entrada a la población de MEF y observar su salida. 4. Evaluar comparando su salida con la próxima entrada para ver si predijo bien. 5. Crear nuevos hijos usando mutación 5.1. Cambiar símbolos 5.2 Cambiar estado de transición 5.3 Añadir o eliminar estado

5.4 Cambiar estado inicial 6. Seleccionar los mejores padres 1.10.2. Programación Evolutiva y Algoritmos Genéticos Existen dos aspectos importantes en los cuales la EP difiere de los AG. Primero, no existe restricción en la representación. En la EP, la representación depende del problema [14]. Segundo, la operación mutación simplemente cambia aspectos de la solución de acuerdo a una distribución estadística, la cual reconoce que menores variaciones en el comportamiento de los descendientes son altamente probables, y que variaciones sustanciales son altamente improbables [14].

1.10.3. Programación Evolutiva y las Estrategias Evolutivas A pesar de haber sido desarrolladas de forma independiente a lo largo de 30 años, estas dos técnicas presentan bastantes similitudes. Ambas técnicas típicamente operan sobre los valores reales. Se aplican mutaciones gaussianas multivariadas de media cero a cada padre de una población [14]. Las principales diferencias entre EEs y EP son [14]: 1. Selección: la EP típicamente utiliza una selección estocástica a través de un torneo. En contraste, las EEs utiliza una abstracción de la evolución a nivel del comportamiento del individuo. 2. Recombinación: La EP es una abstracción de la evolución al nivel de poblaciones reproductivas (es decir, especies), por ende no se usan mecanismos de recombinación debido a que esta no ocurre entre especies. En contraste, las EEs es una abstracción de la evolución a nivel del comportamiento individual.

1.11. PROGRAMACIÓN GENÉTICA (PG) La PG es un método independiente del dominio que generalmente reproduce poblaciones de programas de computación, con el fin de resolver problemas. La PG es una extensión de los AGs, en la cual la población genética está contenida por programas de computación [14]. La PG combina la expresiva representación simbólica de alto nivel usada en los programas de computación, con la eficiencia de la búsqueda alrededor del óptimo que realizan los AGs. Un programa de computación que resuelve (o aproximadamente resuelve) un problema dado, frecuentemente emerge de este proceso. Esto significa, que no se está en la búsqueda de soluciones a los problemas planteados, sino en encontrar el mejor procedimiento para resolverlos. [14]. Los elementos básicos de la PG fueron introducidos por Koza a partir de 1987 en diferentes trabajos de investigación realizados por él y un grupo de colaboradores. La primera corrida usando PG se hizo en ese mismo año y sus bases teóricas fueron descritas en detalle en 1988 [14]. La PG establece los siguientes aspectos que son muy importantes [14]: Una amplia variedad de problemas aparentemente diferentes provenientes de distintos campos pueden ser combinados, con el fin de descubrir un programa de computación que produzca algunas salidas deseadas cuando se presentan ciertos valores particulares en las entradas. La PG provee una forma de hacer programación inductiva. La PG determina automáticamente el tamaño del programa (es decir, el número total de pasos) y de la misma manera determina la secuencia exacta de funciones primitivas y terminales que son ejecutadas por el programa. Específicamente, la PG demuestra que es posible [14]:

Crear de forma automática programas que poseen una única rama principal, Crear de forma automática programas con múltiples ramas, Crear de forma automática programas cuyas ramas se construyen de acuerdo a la estructura sintáctica restrictiva, Crear de forma automática programas formados de un programa principal

y

una

o

más

subrutinas

que

pueden

referenciarse

jerárquicamente unos con otros. En la PG, la representación de los individuos se hace a través de unas estructuras de datos jerárquicamente enlazadas que reciben el nombre de árboles de análisis como se muestra en la figura 2.6 [4]. Las funciones pueden ser operaciones aritméticas, funciones matemáticas, funciones lógicas, o funciones específicas del dominio [4]. En

la

práctica,

tanto

las

funciones

como

los

símbolos

pueden

implementarse de manera sencilla usando “expresiones-S” de LISP. Por ejemplo, la siguiente expresión [4]: (+ 1 2 (IF (> TIME 10) 3 4)) Contiene los átomos: 1, 2, 10, 3, 4, TIME; y las funciones:+, IF, >. El respectivo arrebol se observa en la figura 1.5.

+ I

2

1

F 3

>

TIME

4

10

Figura 1.5. Ejemplo de un árbol de análisis

1.11.1. Funcionamiento de los operadores genéticos Tomando como los árboles padres de la figura 1.6. Si se toma la raíz del árbol como punto de cruce, el hijo 1 contendrá las ramas izquierdas de los padres; mientras que el hijo 2 las derechas como se observa en la figura 1.7. (a): (+ (+ 0.234 Z) (- X 0.789) (b): (*(* Z Y) (+Y 0.314 Z)))

+

*

+

0.23

-

Z

X (a)

+

* 0.78

Z

Y

Y

*

(b) 0.31 4

Figura 1.6. Árboles padres para el operador de cruce

Z

+

*

Z

+

-

*

0.23

Y

-

Y

Z

0.78

X

*

(a)

(b) Z

0.31

Figura 1.7. Árboles hijos obtenidos por el cruce

(a): (*(* Z Y) (+ 0.234 Z)) (b): (+ (+ Y (* 0.314 Z)) (- X 0.789)) 1.11.2.1. Mutación en PG El operador de mutación tiene una implementación mas intuitiva, ya que permite cambiar símbolos terminales por funciones (crear nuevas ramas), o modificar funciones (cambiar ramas ya existentes, ya sea por otras ramas o por símbolos terminales). En el árbol de la figura 1.8 se le cambia el símbolo Terminal 1 por una nueva rama [4]. +

1

I

2

+

F 3

>

4

TIME

4

10

Figura 1.8. Árbol obtenido por mutación de un árbol padre

Los problemas resueltos en la PG involucran regresión simbólica (sistemas de identificación, descubrimiento empírico, modelado, minería de datos (data

mining), proyecciones), clasificación, control, optimización, resolución de ecuaciones, juegos, inducción, problemas que exhiben comportamiento emergente, problemas que involucran coevolución, programación de autómatas celulares, construcción aleatoria, compresión de imágenes, integración simbólica y diferenciación, problemas inversos, árboles de decisión de inducción y muchas otras. Los problemas en PG incluyen muchos problemas actuales presentes en área como inteligencia artificial, redes neuronales y máquinas de aprendizaje [14]. Con todo esto se puede concluir que esta técnica posee un atributo muy importante como la aplicabilidad, ya que produce soluciones satisfactorias a una amplia variedad de problemas provenientes de diferentes campos [14]. 1.11.3. Algoritmo General Los pasos de este algoritmo consisten en crear una población inicial y entonces de forma iterativa ejecutar el ciclo generacional principal. La adaptación (fitness) de cada individuo en la población se determina y las operaciones genéticas se llevan a cabo en dicho ciclo principal. A diferencia de los otros métodos de CE en este se debe escoger una operación de alteración de arquitectura del repertorio de este tipo de funciones disponibles y crear un nuevo programa hijo para la nueva población. En este método, los cambios aleatorios pueden generarse cambiado el operador o alterando el valor de un cierto nodo del árbol, o sustituyendo un subárbol por otro [25]. 1.12. Ambientes de Programación En la actualidad existe un gran número de ambientes de programación disponibles en el mercado para experimentar con los algoritmos, pueden distinguirse 3 clases de ambientes de programación [26]: 1) Sistemas Orientados a las aplicaciones: Son esencialmente "cajas negras" para el usuario, pues ocultan todos los detalles de implementación. Ejemplos

de este tipo de sistemas son: Evolver (Axcelis, Inc.) y XpertRule GenAsys (Attar Software). 2) Sistemas Orientados a los algoritmos: Soportan algoritmos genéticos específicos, y suelen subdividirse en: · Sistemas de uso específico · Bibliotecas En estos sistemas se proporciona el código fuente para que el usuario (normalmente un programador) pueda incluir el algoritmo genético en sus propias aplicaciones. 3)

Cajas

de

Herramientas:

Proporcionan

muchas

herramientas

de

programación, algoritmos y operadores genéticos que pueden aplicarse en una enorme gama de problemas. Normalmente se subdividen en: · Sistemas Educativos. · Sistemas de Propósito General. 1.13. Programas autoconfigurables Es interesante agrupar todos los aspectos y opciones en cuatro categorías, según la siguiente. •

Tipo gen

Los aspectos de tipo gen serán aquellos que, como los genes, son diferentes dentro de un mismo individuo. •

Tipo individuo

Los aspectos de tipo individuo son aquellos que se mantienen iguales en un mismo individuo, pero difieren de unos agentes a otros.

•

Tipo isla

Los aspectos de tipo isla son aquellos que son iguales para un subconjunto de individuos; de más de uno, pero sin llegar al total. •

Tipo población

Los aspectos de tipo población son los que deben ser iguales para toda la población. 1.14. Robustez de los Métodos de Optimización y Búsqueda Tradicionales

Existen en la literatura tres tipos principales de métodos de búsqueda a saber: basados en el cálculo, enumerativos y aleatorios [15].

Los métodos basados en el cálculo se subdividen a su vez en directos e indirectos. Los métodos indirectos realizan la búsqueda de extremos locales mediante la resolución de sistemas de ecuaciones no lineales resultantes de igualar a cero el gradiente de la función a optimizar. Por otro lado, los métodos directos buscan óptimos locales moviéndose sobre la función en dirección del gradiente local. Pero estos métodos basados en el cálculo tienen cierta carencia de robustez, debida principalmente a dos causas. En primer lugar la búsqueda se realiza localmente, es decir se busca mejorar dentro de un entorno del estado actual, lo que en muchos casos deriva en un óptimo local. En segundo lugar, es necesario que las funciones a optimizar sean derivables [15].

Los métodos enumerativos, como su propio nombre indica, realizan una búsqueda punto a punto. Es evidente que cuando el espacio de búsqueda es de un tamaño importante estos métodos carecen de eficiencia [15]. Finalmente, los algoritmos de búsqueda aleatorios poseen igualmente una falta de eficiencia. De todas formas no se debe confundir los métodos puramente aleatorios con aquellos que utilizan la aleatoriedad como una técnica en una búsqueda guiada mediante la explotación de buenas características de algún

punto ya encontrado. De alguna manera, este tipo de técnica es utilizada por los algoritmos genéticos [15].

Capítulo 2 Controladores PID 2.1. Introducción Hoy en día, a pesar de la abundancia de sofisticadas herramientas y métodos avanzados de control, el controlador PID es aún el más ampliamente utilizado en la industria moderna, controlando más del 95% de los procesos industriales en lazo cerrado.

Históricamente, ya las primeras estructuras de control usaban las ideas del control PID. Sin embargo, no fue hasta el trabajo de Minorsky de 1922, sobre conducción de barcos, que el control PID cobró verdadera importancia teórica.

Los controladores automáticos comparan el valor real de la salida de una planta con la entrada de referencia (el valor deseado), determina la desviación y produce una señal de control que reducirá la desviación a cero o a un valor pequeño. La manera en la cual el controlador produce una señal de control se denomina acción de control. 2.2. ACCIONES BASICAS DE CONTROL

Para analizar las acciones básicas de control que utilizan los controladores analógicos industriales primero se hará una clasificación de los controladores analógicos industriales [32].

2.2.1. Clasificación de los controladores industriales: los controladores industriales se clasifican, de acuerdo con sus acciones de control como [32]: 1. de dos posiciones o encendido y apagado (on/off) 2. proporcionales 3. integrales

4. proporcionales- integrales 5. proporcionales- derivativos 6. proporcionales- integrales-derivativos

Casi todos los controladores industriales emplean como fuente de energía la electricidad o fluido despresurizado, tal como el aceite o el aire. Los controladores también pueden clasificarse, de acuerdo con el tipo de energía que utilizan en su operación, como neumáticos, hidráulicos o electrónicos. El tipo de controlador que se use debe decidirse con base en la naturaleza de la planta y las condiciones operacionales, incluyendo consideraciones tales como seguridad, costo, disponibilidad, precisión, peso y tamaño [32]. 2.2.2. Controlador automático, actuador y sensor (elemento de medición): el diagrama en bloques de la figura 2.1 es un sistema de control industrial que consiste en un controlador automático, un actuador, una planta y sensor (elemento de medición). El controlador detecta la señal de error y la amplifica a un nivel lo suficientemente alto. La salida de un controlador automático se alimenta a un actuador, tal como un motor o una válvula neumática, un motor hidráulico, o un motor eléctrico. El actuador es un dispositivo de potencia que produce la entrada para la planta de acuerdo con la señal de control, a fin de que la señal de salida se aproxime a la señal de entrada de referencia.

El sensor, o elemento de medición, es un dispositivo que convierte la variable de salida en otra variable manejable, tal como un desplazamiento, una presión, o un voltaje que pueda usarse para comparar la salida con la señal de entrada de referencia [32].

Controlador automático

Detector de errores Entrada De referencia

Salida +

amplificador

-

Punto De ajuste

Actuador

Planta

Señal De error

Sensor

Figura 2.1. Diagrama en bloques de un sistema de control industrial, formado por un controlador automático, un actuador, una planta y un sensor. (Elemento de medición)

2.2.3. Controladores auto-operados: en la mayor parte de los controladores automáticos industriales, se usan unidades separadas para el elemento de medición y el actuador. Sin embargo, en algunos muy sencillos, como los controladores auto-operados, estos elementos se integran en una unidad. Los controladores auto-operados utilizan la potencia desarrollada por el elemento de medición, son muy sencillos y poco costosos [32]. 2.2.4. Acción de control de dos posiciones o encendido y apagado (on/off): en un sistema de control de dos posiciones, el elemento de actuación sólo tiene dos posiciones fijas que, en muchos casos, son simplemente encendido y apagado. El control de dos posiciones o de encendido y apagado es relativamente simple y barato, razón por la cual su uso se ha extendido en sistemas de control tanto industriales como domestico [32].

Si se supone que la señal de salida del controlador es u(t) y que la señal se error es e(t). En el control de dos posiciones, la señal u(t) permanece en un valor ya sea máximo o mínimo, dependiendo de si la señal de error es positiva o negativa. De este modo, u(t)= U1 para e(t)>0

(2-1)

u(t)= U2 para e(t)