Controladores PID de dos grados de libertad y algoritmos genéticos multiobjetivo

INTRODUCCION

La optimización multiobjetivo tiene amplias aplicaciones en distintas áreas de la ingeniería y las ciencias computacionales. Muchos de estos problemas tienen espacios de búsqueda muy grandes por lo que, en algunos casos, no pueden ser resueltos mediante técnicas exactas en un tiempo razonable.

Los algoritmos genéticos multiobjetivo, son una alternativa para resolver problemas de control planteados como problemas de optimización multiobjetivo con restricciones. El planteamiento de muchos problemas de control automático, sobre todo en procesos industriales, como una serie de objetivos y restricciones, ha despertado el interés de numerosos investigadores por la aplicación de las técnicas evolutivas. Las especificaciones de diseño se pueden plantear como funciones objetivo, las cuales serán, en algunos casos minimizados y en otras maximizadas.

Los objetivos de esta investigación pueden presentar en dos partes. La primera concierne en la teoría y planteamiento de diversas ecuaciones que nos llevaran a comprender como operan los Algoritmos Genéticos Multiobjetivo. La segunda parte se trata de conocer cómo opera un controlador PID. Específicamente se trata de un controlador PID de dos grados de libertad, dentro de un esquema de control básico.

Para seleccionar los parámetros es necesario plantear los requerimientos de diseño que contemplan principalmente: el desempeño del sistema a controlar y la robustez ante las incertidumbres y variaciones del proceso.

PLANTEAMIENTO DEL PROBLEMA

Para el ajuste de los parámetros de un controlador tipo PID se dispone de varios métodos ampliamente difundidos, basados tanto en el dominio del tiempo como en el dominio de la frecuencia, entre ellos están: los de Ziegler-Nichols, el del lugar geométrico de las raíces y el de la respuesta en frecuencia. Con estos métodos muchas veces se diseñan controladores que presentan comportamientos inaceptables, como tiempos de respuesta o estabilización muy largos, incumpliendo así con los requerimientos del sistema. Esto se traduce en disminución de la eficiencia del proceso y pérdidas económicas para las plantas. Por esta razón se hace necesario optimizar el diseño, con lo cual se busca obtener los parámetros (Kp, Ti y Td) que brinden el mejor desempeño del controlador una vez que este es instalado en el sistema.

La optimización de un sistema de control consiste en establecer y minimizar una función de costo del sistema, con el objetivo de lograr una sintonía fina de los controladores diseñados por los métodos convencionales, es decir, ajustar los parámetros del controlador de manera de minimizar algún criterio.

RELEVANCIA DEL TEMA DE INVESTIGACIÓN

Los controladores PID continúan siendo los más utilizados en la gran mayoría de instalaciones industriales. Su principal ventaja, desde un punto de vista práctico, consiste en que vienen programados en todos los controladores comerciales (PLC/DCS) y son bien conocidos por los técnicos responsables de la instrumentación. Los controladores PID son parte importante de los sistemas de control, sin embargo, el operar controladores mal sintonizados representa enormes pérdidas materiales para cualquier industria.

En esta investigación se presenta una estrategia para su diseño basado en Optimización Multiobjetivo, por medio de un algoritmo genético multiobjetivo. El planteamiento de muchos problemas de control automático, sobre todo en procesos industriales, como una serie de objetivos y restricciones, ha despertado el interés de numerosos investigadores por la aplicación de las técnicas evolutivas. Las especificaciones de diseño se pueden plantear como funciones objetivo, las cuales serán, en algunos casos minimizados y en otras maximizadas.

El uso de un enfoque evolutivo, como herramienta computacional para resolver problemas de optimización, tiene sus ventajas sobre las técnicas tradicionales, sobre todo cuando se tratan problemas complejos.

MARCO TEÓRICO

En este capítulo se abordan brevemente los conceptos básicos de los sistemas de control así como la teoría de controladores P, PI, PD y, PID; también se presentan la definición de optimización multiobjetivo, las normas más usadas en control; posteriormente, se trata el tema de los algoritmos genéticos haciendo énfasis en el NSGA-II y como estos se aplican a problemas de optimización en general.

Conceptos básicos en los Sistemas de Control

Definiciones.- Antes de analizar los sistemas de control, deben definirse ciertos conceptos básicos. [31]

Variable controlada y señal de control o variable manipulada. La variable controlada es la cantidad o condición que se mide o controla. La señal de control o variable manipulada, es la cantidad o condición que el controlador modifica para afectar el valor de la variable controlada. Normalmente, la variable controlada es la salida del sistema.

Plantas. Una planta puede ser una parte de un equipo, tal vez un conjunto de los elementos de una máquina que funcionan juntos, y cuyo objetivo es efectuar una operación particular.

Procesos. El Diccionario Merriam-Webster define un proceso como una operación o un desarrollo natural progresivamente continuo, marcado por una serie de cambios graduales que se suceden unos a otros de una forma relativamente fija y que conducen a un resultado o propósito determinados; o una operación artificial o voluntaria que se hace de forma progresiva y que consta de una serie de acciones o movimientos controlados, sistemáticamente dirigidos hacia un resultado o propósito determinado.

Sistemas. Un sistema es una combinación de componentes que actúan juntos y realizan un objetivo determinado. Un sistema no está necesariamente limitado a los sistemas físicos. Por tanto, la palabra sistema debe interpretarse en un sentido amplio que comprenda sistemas físicos, biológicos, económicos y similares.

Perturbaciones. Una perturbación es una señal que tiende a afectar negativamente el valor de la salida de un sistema. Si la perturbación se genera dentro del sistema se denomina interna, mientras que una perturbación externa se genera fuera del sistema y es una entrada.

Control realimentado. El control realimentado se refiere a una operación que, en presencia de perturbaciones, tiende a reducir la diferencia entre la salida de un sistema y alguna entrada de referencia, y lo realiza tomando en cuenta esta diferencia. Aquí sólo se especifican con este término las perturbaciones impredecibles, ya que las perturbaciones predecibles o conocidas siempre pueden compensarse dentro del sistema.

Sistemas de Control en lazo cerrado y en lazo abierto.

El primer paso para el diseño de un sistema de control es la obtención del modelo matemático de la planta u objeto de control. En realidad, cualquier modelo de una planta que se quiere controlar incluirá un error debido al proceso de modelado. Esto es, la planta real difiere del modelo que se va a utilizar en el diseño del sistema de control.

Una aproximación razonable para asegurar que el controlador diseñado basado en un modelo funcionará adecuadamente cuando se utilice con la planta real, consiste en asumir desde el comienzo que existe una incertidumbre o error entre la planta real y su modelo matemático e incluir dicha incertidumbre o error en el proceso de diseño del sistema de control. El sistema de control diseñado basado en esta aproximación se denomina sistema de control robusto.

Un sistema que mantiene una relación determinada entre la salida y la entrada de referencia, comparándolas y usando la diferencia como medio de control, se denomina sistema de control realimentado. Los sistemas de control realimentados se denominan también sistemas de control en lazo cerrado.

En un sistema de control en lazo cerrado, se alimenta al controlador la señal de error de actuación, que es la diferencia entre la señal de entrada y la señal de realimentación, con el fin de reducir el error y llevar la salida del sistema a un valor deseado. El término control en lazo cerrado siempre implica el uso de una acción de control realimentado para reducir el error del sistema. En su configuración más elemental, un sistema realimentado contiene los bloques y señales que se muestran en la figura.

Sistema realimentado.

La señal Ea(s) es una medida del error del sistema, y es igual al error E(s)=R(s)- C(s) cuando H(s)=1. La salida del sistema está representada por C(s), R(s) denota la señal de entrada, G(s) es la función de transferencia del proceso bajo control y H(s) representa la función de transferencia del sensor con el cual se obtiene la señal de salida. [33]

Para el sistema que aparece en la figura, la salida C(s) y la entrada R(s) se relacionan del modo siguiente:

C(s) = G(s) Ea(s) =G(s) [R(s)-H(s) C(s)]

C(s) =G(s) R(s)-G(s) H(s) C(s)

C(s) +G(s) H(s) C(s) =G(s) R(s)

C(s) [1+G(s) H(s)] =G(s) R(s)

De la ecuación anterior, se obtiene la función de transferencia en lazo cerrado (GLC(s)). Esta función de transferencia relaciona la dinámica del sistema en lazo cerrado con la dinámica de los elementos de las trayectorias directa y de realimentación.

GLC(s) = C(s)/R(s) = G(s)/ (1+G(s) H(s))

Por lo tanto, la salida del sistema en lazo cerrado depende claramente tanto de la función de transferencia en lazo cerrado como de la naturaleza de la entrada.

Los sistemas en los cuales la salida no tiene efecto sobre la acción de control se denominan sistemas de control en lazo abierto. En otras palabras, en un sistema de control en lazo abierto no se mide la salida ni se realimenta para compararla con la entrada. Un ejemplo práctico es una lavadora. El remojo, el lavado y el centrifugado en la lavadora operan con una base de tiempo. La máquina no mide la señal de salida, que es la limpieza de la ropa. Así, a cada entrada de referencia le corresponde una condición de operación fija; como resultado de ello, la precisión del sistema depende de la calibración.

Ante la presencia de perturbaciones, un sistema de control en lazo abierto no realiza la tarea deseada. En la práctica, el control en lazo abierto sólo se usa si se conoce la relación entre la entrada y la salida y si no hay perturbaciones internas ni externas. Desde el punto de vista de estabilidad, el sistema de control en lazo abierto es más fácil de desarrollar, porque la estabilidad del sistema no es un problema importante.

Las ventajas fundamentales de los sistemas de control en lazo abierto son las siguientes:

• Construcción simple y facilidad de mantenimiento.

• Menos costosos que el correspondiente sistema en lazo cerrado.

• No hay problemas de estabilidad. 4. Convenientes cuando la salida es difícil de medir o cuando medir la salida de manera precisa no es económicamente viable. (Por ejemplo, en el caso de la lavadora, sería bastante costoso proporcionar un dispositivo para medir la calidad de la salida de la lavadora, es decir, la limpieza de la ropa lavada.)

Las desventajas fundamentales de los sistemas de control en lazo abierto son las siguientes:

• Las perturbaciones y los cambios en la calibración originan errores, y la salida puede ser diferente de lo que se desea.

• Para mantener la calidad requerida en la salida, es necesaria la recalibración de vez en cuando.

Introducción al Control PID

La utilidad de los controles PID estriba en que se aplican en forma casi general a la mayoría de los sistemas de control. En particular, cuando el modelo matemático de la planta no se conoce y, por lo tanto, no se pueden emplear métodos de diseño analíticos, es cuando los controles PID resultan más útiles. En el campo de los sistemas para control de procesos, es un hecho bien conocido que los esquemas de control PID básicos y modificados han demostrado su utilidad para aportar un control satisfactorio, aunque tal vez en muchas situaciones específicas no aporten un control óptimo. [31]

Acción Proporcional

En el caso de control proporcional puro, la ley de control se reduce a:

La acción de control es simplemente proporcional al error de control. La variable ub es un sesgo o reajuste. Cuando el error de control es cero, la variable de control toma el valor u(t)=ub. Parcialmente ub a menudo se fija para (umax+umin)/2, pero puede ser ajustado algunas veces manualmente de manera que el error de control estacionario sea cero para un set point dado. [4]

Para evitar que el sistema de medición sea sensible al ruido, la ganancia del lazo no debe hacerse demasiado grande. Además, el controlador ub parcialmente influye en el sistema de la misma manera que la perturbación de carga. [4]

Para la mayoría de los sistemas hay un límite superior en la ganancia proporcional, con tal de lograr una respuesta bien amortiguada y estable. [16]

Cualquiera que sea el mecanismo real y la forma de la potencia de operación, el controlador proporcional es, en esencia, un amplificador con una ganancia ajustable. [31]

Un ejemplo típico de control proporcional es ilustrado en la siguiente figura. La figura muestra el comportamiento de la salida del proceso y la señal de control después de una etapa de cambio en el set point. Con una ganancia de controlador K=1 y una ganancia de proceso estático Kp=1, el error es por lo tanto del 50%. Nótese también que la respuesta se vuelve más oscilatoria conforme la ganancia del controlador se incrementa, esto es debido a la dinámica del proceso. [4]

Análisis estático

Varias propiedades de un control proporcional pueden ser entendidas por el siguiente argumento, cosa que se basa en consideraciones estáticas puros.

Considerar el lazo de realimentación simple que se muestra en la figura, y compuesto de un proceso y un controlador. Asumir que el controlador tiene acción proporcional y que el proceso es modelado por el modelo estático.

Donde x es la variable de proceso, u es la variable de control, l es una alteración de la carga, y Kp, es la ganancia del proceso estático. Las siguientes ecuaciones se obtienen a partir del diagrama de bloques.

La eliminación de variables intermedias da la siguiente relación entre la variable de proceso x, el punto de ajuste ysp, la perturbación de carga l, y el ruido de medición n:

El producto KKp es un número adimensional llamado la ganancia de lazo. Varias propiedades interesantes del sistema de circuito cerrado se pueden leer en la ecuación (6.6).

Primero se asume que n y ub son cero. Entonces la ganancia del lazo debe ser alto con el propósito de garantizar la salida del proceso de x está cerca de la señal de referencia ysp.

Un alto valor de la ganancia de lazo también hará que el sistema sea insensible a la perturbación de carga l. Sin embargo, si n es distinto de cero, se desprende de la ecuación que el ruido de medición n influye en la salida del proceso de la misma manera como ysp, para evitar que el sistema de medición sensible al ruido, la ganancia de lazo no debe hacerse demasiado grande.

Acción Integral

La función principal de la acción integral es asegurar que el proceso de salida este de acuerdo con el set point en estado estacionario. Con la acción proporcional, normalmente existe un control con error en estado estacionario. Con la acción integral, un pequeño error positivo conducirá siempre a incrementar la señal de control, y un error negativo dará siempre una señal de control decreciente sin importar cuan pequeño sea el error. [4]

El siguiente argumento muestra que el error en estado estacionario siempre será cero con una acción integral. Asúmase que el sistema está en estado estacionario con una señal de control contante (u0) y una constante de error (e0). La señal de control es dada por [4]

Siempre que e0 ? 0, esto claramente contradice la suposición que la señal de control u0 es constante. Un controlador con acción integral será siempre cero en error en estado estacionario.

La acción integral también puede ser visualizada como un mecanismo que automáticamente reinicia al termino parcial ub de un controlador proporcional.

Las propiedades de la acción integral son ilustradas en la figura, la cual muestra una simulación de un sistema con control PI.

La ganancia proporcional es constante, K=1 en todas las curvas, y el tiempo integral es variable. El caso de Ti=8 corresponde a control proporcional puro. Este caso es idéntico cuando K=1 en la figura, donde el error en estado estacionario es del 50%. El error en estado estacionario es removido cuando Ti alcanza valores infinitos. Para grandes valores en tiempo de integración, la respuesta se dirige lentamente hacia el set point. El acercamiento es aproximadamente exponencial con el tiempo constante Ti/KKp. El acercamiento es rápido para valores pequeños de Ti, y esto es también más oscilatorio. [4]

Acción Derivativa

El propósito de la acción derivativa es mejorar la estabilidad en lazo cerrado. El mecanismo de la inestabilidad puede ser descrito intuitivamente de la siguiente manera. Porque de la dinámica del proceso, se tomaría algo de tiempo antes de que un cambio en la variable de control sea notable en la salida del proceso. Así que el sistema de control se tardaría en la corrección de un error. La estructura básica de un controlador PD es [4]:

u(t)=Kpe(t)+KpTd(de(t)/dt)

Y la función de transferencia es

U(s)/E(s)=Kp (1+Tds)

Donde Td es el tiempo derivativo.

La señal de control es por lo tanto proporcional a una estimación del error de control en el momento antes Td, donde la estimación es obtenida por extrapolación.

Las propiedades de la acción derivativa son ilustradas en la Figura, la cual muestra una simulación de un sistema de control PID. La ganancia del controlador y el tiempo integral permanecen constantes, K=3 y Ti=2, y se cambia el tiempo derivativo Td. para Td=0 se tiene puro control PI. El sistema en lazo cerrado es oscilatorio cuando se seleccionan los parámetros. Inicialmente la amortiguación incrementa con el incremento del tiempo derivativo, pero disminuye de nuevo cuando el tiempo derivativo se hace demasiado largo. [4]

Acción de control Proporcional-Integral-Derivativa

La combinación de la acción de control proporcional, la acción de control integral y la acción de control derivativa se denomina acción de control proporcional-integral- derivativa. Esta acción combinada tiene las ventajas de cada una de las tres acciones de control individuales. La ecuación de un controlador con esta acción combinada está dada por [4]:

O la función de transferencia es:

Donde Kp es la ganancia proporcional, Ti es el tiempo integral y Td es el tiempo derivativo.

El diagrama de bloques de un controlador proporcional-integral-derivativo aparece en la Figura:

Introducción al Control de dos grados de libertad Introducción

Por lo general, la mayoría de controladores son sintonizados para el rechazo de las perturbaciones o para un buen seguimiento del cambio en la señal de referencia, siendo necesaria la elección de uno u otro modo de sintonía y obteniendo, como regla general, un mal rendimiento en seguimiento cuando se utiliza una sintonía para regulación y viceversa. Mientras que con un controlador PID de un grado de libertad tradicional, es imposible logar un buen seguimiento del valor deseado (servo control), al mismo tiempo que obtener insensibilidad a las perturbaciones de carga (control regulatorio), con un controlador PID de dos grados de libertad esto se puede obtener con un cierto grado de independencia.

A continuación se detallan cada una de las partes que intervienen en la formulación de un controlador de dos grados de libertad, a fin de comprender mejor su funcionamiento y alcances de aplicación en la ingeniería de control.

Formulación PID de Dos Grados de Libertad

Un lazo de control realimentado como el mostrado en la Figura tiene dos entradas, el valor deseado r y la perturbación de carga d, y una salida, la variable controlada

• En este esquema, al ajustar el controlador para lograr el comportamiento deseado ante un cambio en una de las entradas, queda automáticamente establecido el comportamiento ante la otra. Por esta razón se dice que estos controladores tienen solo un grado de libertad. [2]

Cuando un sistema de control en lazo cerrado funciona con solo una señal de error (e=r-y), se conoce como un sistema con un grado de libertad. [23]

Sin embargo, la necesidad de lograr en muchas aplicaciones industriales un buen desempeño del lazo de control, tanto a un cambio en la perturbación de carga como en el valor deseado, dio lugar a la modificación de los controladores de manera de tener un segundo grado de libertad. Por lo general, la mayoría de controladores de los lazos de control realimentado, son sintonizados para el rechazo de las perturbaciones (control regulatorio) [45, 11, 27] o para un buen seguimiento del cambio en la señal de referencia (servo control) [28, 38], siendo necesaria la elección de uno u otro modo de sintonía y obteniendo, como regla general, un mal rendimiento en seguimiento cuando se utiliza una sintonía para regulación y viceversa. La formulación de Dos Grados de Libertad (2-GdL) tiene como objetivo tratar de satisfacer estas dos condiciones. El segundo grado de libertad proviene de la relativa flexibilidad obtenida a la hora de diseñar un sistema de control, en lo que se refiere a la posibilidad de procesar de manera independiente las señales de referencia y salida. [2]

Esta estructura se utiliza ampliamente en el control industrial. La señal de referencia ysp y el rechazo de perturbaciones de carga pueden desacoplarse mediante una estructura de dos grados de libertad. El esquema de control propuesto en este trabajo se muestra en la Figura:

Donde:

r denota la señal de referencia de entrada.

e denota la señal de error.

? denota la salida de la señal filtrada;

u denota la señal de control;

l denota la señal de perturbación de carga;

d denota la señal de ruido;

y denota la señal de salida;

G(s) es lineal e invariante en el tiempo y es una planta de una entrada- una salida (SISO).

PID(s) denota un controlador PID.

El filtro F(s) se emplea para reducir el efecto del ruido de altas frecuencias en la señal de

salida, donde Tf es la constante de tiempo del filtro.

El modelo del controlador PID se basa en:

Un diagrama equivalente del controlador puede ser representado por la Figura 6. [4]

Como se puede apreciar, en este esquema Gff representa a la parte del controlador la cual es únicamente afectada por la señal de referencia ysp, y Gc es la función de transferencia del controlador cuya entrada es la salida del proceso y.

A continuación se presentan las ecuaciones para Gff y Gc. [4]

De las ecuaciones anteriores: k, Ti y Td corresponde a la ganancia del controlador, el tiempo integral y el tiempo derivativo respectivamente.

Los parámetros b y c son los factores de peso que influencian la respuesta del set point, sin alterar la respuesta del controlador para las perturbaciones de carga y efectos de ruido. [3]

En muchos casos el valor de b es restringido por los fabricantes de los controladores comerciales a valores en el ámbito 0 = b = 1,0. [1]

Si se definen los grados de libertad de un sistema de control, como el número de funciones de transferencia de lazo cerrado que pueden seleccionarse de manera independiente (Horowitz, 1963) [19], para el caso concreto del controlador PID se puede tener un sistema de un grado de libertad (1-GdL) o uno de dos grados de libertad (2-GdL), dependiendo del valor del parámetro b. [2]

Para b =1, las funciones de transferencia del lazo cerrado del sistema de control no pueden tener dinámicas independientes por lo que se tendrá un sistema de 1-GdL. Lo anterior introduce una limitación a la hora de diseñar la sintonía del controlador ya que se puede obtener un rendimiento óptimo del sistema, solo para uno de los dos tipos de funcionamiento, servo control o control regulatorio. De esta manera, el ingeniero de control se ve obligado a escoger uno de los dos tipos de funcionamiento, cuando en la práctica ambas situaciones se presentan en los sistemas de control. [2]

En el subtema titulado "Antecedentes de los Algoritmos Genéticos Simples" se presenta una breve reseña de algunos personajes que han realizado aportaciones en el campo de los algoritmos genéticos, estos personajes aportaron cambios en la forma de comprender los procesos evolutivos de la naturaleza y que han sido aplicados hoy en día al campo de la alta tecnología, se presenta formalmente en que consiste el proceso genético, como se desarrolla en los problemas de optimización y un diagrama de algoritmo genético simple el cual engloba dicho proceso. Posteriormente se presentan las definiciones del Optimo de Pareto, la forma de operación de los algoritmos genéticos multiobjetivo, la norma H8 su uso e importancia en el manejo de restricciones y el NSGA-II, famoso algoritmo multiobjetivo más ampliamente usado en cuanto a problemas de optimización.

Antecedentes de los Algoritmos Genéticos Simples Antecedentes

Los algoritmos genéticos están inspirados en procesos evolutivos que se presentan en la naturaleza, donde la idea central es la supervivencia de los individuos más aptos y la modificación constante de sus descendientes para adaptarse al entorno donde habitan. Estos principios son en parte emulados por los algoritmos genéticos, cuando se usan para resolver problemas de optimización. [10, 8, 30]

La primera idea surgió en la tesis de J. D. Bagley: "El funcionamiento de los sistemas adaptables empleando algoritmos genéticos y correlativos", en 1967. Esta tesis influyó decisivamente en J. H. Holland, quien se puede considerar como el pionero de los AG. [34]

Los Algoritmos genéticos han sido utilizados exitosamente en optimización multiobjetivo. Una de las primeras aplicaciones fue realizada por Fonseca y Fleming en 1988, donde utilizan un algoritmo genético multiobjetivo (MOGA), en el control de una turbina de gas. [14]

En el año 2000, Herreros propuso en su tesis doctoral un algoritmo llamado "Multi- Objective Robust Control Design (MRCD)", para el diseño de controladores PID robustos.[17]

Para la sintonización de los controladores PID, el problema de control, se presenta como un problema de optimización multiobjetivo, de un conjunto de funciones, donde se incluyen los parámetros del controlador. En este trabajo se utiliza el algoritmo genético multiobjetivo, el NSGA-II (Nondominated Sorting Genetic Algorithm) [21], el cual entrega un conjunto de soluciones, todas buenas en el sentido de no-dominancia de Pareto (Conjunto de óptimos de Pareto), donde cada uno de ellas contiene los parámetros del controlador PID. De este conjunto, la persona que plantea el problema de optimización (usuario), puede seleccionar algunas de las soluciones, de acuerdo con sus preferencias. El NSGA-II se ha utilizado en muchas aplicaciones de control, como se puede ver en [9, 40, 22].

Introducción a los Algoritmos Genéticos Simples

La técnica de solución de problemas basada en Algoritmos Genéticos, supone que la solución potencial de cualquier problema es un individuo, el cual puede representarse mediante un conjunto de parámetros. Estos parámetros son vistos de forma análoga como los genes de un cromosoma y pueden ser estructurados por medio de una cadena de valores en forma binaria. En control automático, muchos problemas pueden ser planteados como problemas de optimización, con una o más funciones objetivo, sujeto a restricciones.

La optimización consiste en encontrar dentro de un conjunto de posibles candidatos que resuelven un problema, aquél que se caracterice por ser el mejor. Para evaluar la característica de "mejor" se considera una función de desempeño. Esta función de desempeño tiene varias formas de nombrarse: puede ser costo, calidad, adaptación (fitness).

A continuación se explicara en que consiste el proceso genético y las partes que lo componen a fin de comprender cómo opera un algoritmo genético y posteriormente se abordará el tema de como este algoritmo se relaciona con la Optimización Multiobjetivo.

El proceso genético Codificación

Para un algoritmo genético lo primero que se requiere es determinar en qué espacio se encuentran las posibles soluciones al problema que se pretende resolver. En caso de tener un problema de optimización de una función cuyo dominio es un subconjunto de los números reales, entonces este subconjunto es al que se hace referencia. Pero el algoritmo opera sobre "códigos genéticos", sobre genotipos que se deberán mapear al espacio de soluciones. Es decir, es necesario codificar de alguna manera el dominio del problema para obtener estructuras manejables que puedan ser manipuladas por el AG.

Cada una de estas estructuras constituye el equivalente al genotipo de un individuo en términos biológicos.

En contraste con lo que sucede en la estrategia evolutiva y en la programación evolutiva. Los algoritmos genéticos trabajan con cadenas de bits de extensión fija (l). Frecuentemente los algoritmos genéticos se aplican en problemas de control óptimo con parámetros que varían dentro de un rango continuo de valores. El proceso de codificación consiste en determinar el número de bits para representar a cada parámetro tomando como base los valores mínimo y máximo de los parámetros, así, como la resolución deseada. El número de bits para codificar un parámetro se puede encontrar a partir de la siguiente ecuación:

Donde:

V: mínimo valor del rango del parámetro U: máximo valor del rango del parámetro

I: número de bits necesarios para codificar el parámetro R: resolución deseada

Ejemplo: Determinar el número de bits necesarios para codificar un parámetro contenido dentro del intervalo [-5,5] con una resolución de 0.1

Aplicando la ecuación anterior se tiene como resultado l=6.6582, sin embargo, el número de bits debe ser un valor entero, entonces se toma el número inmediato superior, que es en este caso 7, y dado que se modifica el valor de la resolución deseada: el siguiente paso es recalcular el valor de la resolución con el nuevo valor de l; después del cambio l, los resultados son los siguientes:

El número total de bits que conforman cada una de las cadenas binarias es la suma de los números de bits de cada parámetro, conocido como ancho de la cadena. El número de bits por cada parámetro y el ancho de la cadena serán necesarios para inicializar la población, que es el siguiente paso del proceso genético.

Inicialización de la población

La población de cadenas binarias, que representan a los parámetros, se genera aleatoriamente con una distribución uniforme, sobre el espacio de búsqueda, a partir del conocimiento del número de bits de cada parámetro, el ancho de la cadena y el tamaño de la población. El tamaño de la población está en función de la complejidad del problema a resolver, del ancho de las cadenas de la población y de los recursos de procesamiento.

Con un tamaño pequeño existe poca probabilidad de encontrar la solución y con poblaciones muy grandes se utiliza mucho tiempo de proceso.

Ejemplo: Inicializar una población de tamaño cinco, considerando los datos de ejemplo anterior.

Dado que la población es creada aleatoriamente, se podría tener una población como la siguiente.

En resumen, el algoritmo recibirá como entrada una población de códigos y a partir de ésta generará nuevas poblaciones, donde algunos códigos desaparecerán mientras que otros, que se mapean en mejores soluciones posibles, aparecen con más frecuencia hasta que se encuentra una solución satisfactoria o hasta que se cumple alguna otra condición de terminación. [42]

Ahora se tienen los datos necesarios para la siguiente parte del proceso genético.

Decodificación

El proceso de decodificación convierte cada uno de los individuos de la población (cadenas binarias), a sus respectivos valores reales, para ser evaluados a través de una función objetivo. A los individuos representados por sus valores reales se les conoce como fenotipos. La decodificación se puede realizar por medio del código binario estándar o mediante la aplicación de otros códigos, por ejemplo: el código grey, el cual presenta la ventaja principal de que para valores de parámetros solución muy cercanos entre sí, existen pocos cambios que representan a esos números, lo cual se puede tomar como una ventaja sobre el código binario estándar en la solución de muchos problemas de optimización. A continuación se presenta la ecuación, para el caso binario estándar.

Para el caso de decodificación mediante código Grey se tiene:

Donde la relación entre el código binario estándar y el código Grey está dada por la siguiente expresión.

Evaluación

Se evalúa la función objetivo tomando como argumentos cada uno de los elementos de la población (parámetros), es decir, los valores reales ya decodificados de cada una de las cadenas binarias. Durante este proceso se asigna una calificación a cada elemento de la población, que indica su grado de aptitud.

Reproducción

Para las estructuras básicas de un AG también es necesario conocer la transición de una generación a otra, que consta de tres elementos básicos: Selección, Cruzamiento y Mutación. Dentro de esta etapa se puede hacer uso de un parámetro adicional que es conocido como elitismo, que permite conservar los mejores elementos a través de las n"s generaciones.

• Selección: Mecanismo de selección individual (cadena) para la reproducción acorde con la función de aptitud (valor de la función objetivo). Los algoritmos de selección serán los encargados de escoger que individuos van a disponer de oportunidades de reproducirse y cuáles no. La idea básica de selección está asociada con la función de aptitud y el sistema original; para implementación es comúnmente conocida como roulette-wheel (RWS); esta utiliza una distribución de probabilidad, donde la probabilidad de selección de una cadena es directamente proporcional a su aptitud. [34]

Como se mencionó, los métodos de selección más usados son los siguientes:

• Torneo (tournament)

Puede resolver problemas de optimización (de maximización o minimización). Un par de elementos de la población son seleccionados aleatoriamente y el individuo que tenga la mejor calificación, es copiado en un lugar de almacenamiento conocido como mating pool. Este proceso se repite hasta que este arreglo es llenado con los mejores elementos.

• Selección de la Rueda de la Ruleta (roulette-wheel)

Es una de las técnicas de selección más usada. Este mecanismo permite seleccionar de manera aleatoria a los mejores individuos, tomando como base alguna medida de aptitud. Se obtiene la suma de (Fs) de los valores de aptitud de cada uno de los individuos de la población actual, donde los individuo son transformados en segmentos contiguos en el intervalo [0, Fs]. Por ejemplo, la circunferencia de la rueda de la ruleta en la Figura, es la suma de los valores de aptitud de cinco individuos. El individuo 5 es el que tiene el valor de desempeño más alto y es el que ocupa el intervalo más grande, en contraparte, el individuo 1 es el que tiene el desempeño más pobre y por lo tanto, ocupa el espacio más pequeño de la rueda de la ruleta.

Para seleccionar un individuo, primero se genera un número de forma aleatoria, en el intervalo [0, Fs], entonces se selecciona un individuo cuyo segmento cubre el número aleatorio. El proceso se repite hasta que se alcanza el número de elementos deseado.

• Cruzamiento

Método de fusión sobre la información genética de los individuos; si la codificación se elige apropiadamente, dos progenitores saludables producirán progenitores sanos. Es el principal operador genético; provee un mecanismo para heredar características a su descendencia; interviene en ambos progenitores. [34]

Para ilustrar la manera como trabaja el operador de cruzamiento, un mecanismo de cruzamiento de un punto es mostrado en la Figura. Como puede verse, se fija aleatoriamente un punto de cruzamiento. Las porciones de los dos cromosomas que se encuentran a la derecha del punto de cruzamiento son intercambiadas para generar la descendencia. Una tasa funcional (pc) con un valor típico de entre 0.6 y

• es utilizada normalmente como la probabilidad de cruzamiento.

Para otros problemas o diferentes codificaciones, pueden ser útiles o incluso necesarios otros métodos de cruzamiento [34]. A continuación se menciona alguno de ellos:

• Cruzamiento de N-puntos: en lugar de un único punto, se eligen al azar N puntos de ruptura. Cada segunda sección se intercambia. Entre estas clases, la de dos-puntos es particularmente importante.

• Cruzamiento segmentado: esta técnica es muy parecida al cruzamiento de N-puntos, con la diferencia de que el número de puntos de ruptura puede variar.

• Cruzamiento uniforme: para cada posición se decide al azar si se intercambian las posiciones.

• Cruzamiento aleatorio: primero se escoge una permutación aleatoria que se aplicara a los progenitores, después el cruzamiento de N-puntos se aplica a los progenitores aleatorios y, finalmente, los descendientes aleatorios se transforman de nuevo con permutación inversa.

Mutación

El último bloque de los AG´s es la mutación, es decir, la deformación aleatoria de la información genética en un individuo, en forma análoga con los seres vivos cuando se enfrentan a las radiaciones u otros medios de influencia. En la reproducción real, la probabilidad de que en un determinado gen sea mutado es casi igual para todos los genes. Así, está al alcance de la mano usar las siguientes técnicas de mutación para una determinada cadena binaria s, donde pM es la probabilidad de que un solo gen sea modificado. [34]

Este proceso altera cada bit con una pequeña probabilidad (pM ) con un valor típico de menos 0.1.

Por supuesto, se puede encontrar muchas alternativas y con más detalles. Algunas técnicas se muestran a continuación:

• Inversión de un solo bit: la probabilidad de mutación pM de que un bite elegido al azar sea negado.

• Inversión por fragmentos: toda la cadena es invertida bit a bit con una probabilidad de mutación pM.

• Selección aleatoria: la probabilidad de mutación pM de que una cadena elegida al azar sea reemplazada.

Para ejemplificar este proceso, en la Figura se muestra a un individuo antes y después de ser mutado.

Diagrama del Algoritmo Genético simple