Dentro del cómputo evolutivo existen diferentes paradigmas. Aunque todos los paradigmas se basan en la misma idea del neo-darwinismo y en el uso de una población de soluciones, difieren entre ellos por la forma de implementar los mecanismos de selección, apareamiento, mutación y elitismo. Los principales paradigmas son: los algoritmos genéticos, las estrategias evolutivas y la programación evolutiva. Aunque también existen otras técnicas como la programación genética, la evolución diferencial, la optimización mediante cúmulos de partículas, la optimización por colonia de hormigas, los algoritmos culturales, los sistemas inmunes artificiales y la búsqueda dispersa.
En la actualidad, el paradigma de algoritmos genéticos se presume como el más popular. Aunque existen propuestas similares, como la de Fraser, y la de Bremermann, se considera a John Holland como el que definió las bases de los algoritmos genéticos modernos. En cuanto a la representación, tradicionalmente hace uso de una cadena binaria, es decir, trabajan a nivel de genotipo, lo que equivale a transformar el problema de un espacio cualquiera al binario. Por ello, en el algoritmo genético una representación adecuada es un factor importante para obtener buenos resultados. Tradicionalmente, los algoritmos genéticos hacen uso de la selección proporcional con base en la adaptabilidad. Le da mayor importancia al operador de apareamiento que al de mutación, y no cuenta con mecanismos de auto-adaptación. En cuanto a la probabilidad de apareamiento se utilizan valores altos, al contrario de la probabilidad de mutación donde los valores usualmente son bajos.
Los algoritmos genéticos son técnicas de optimización que se basan en la evolución de las especies, son utilizados especialmente en problemas bastante complicados donde las técnicas tradicionales de optimización no obtienen buenos resultados. El pensamiento evolutivo actual gira en torno al Neo-Darwinismo, que está basado principalmente en las ideas de Darwin, Weismann y Mendel, el cual establece que toda la vida en el planeta puede ser explicada a través de: selección, apareamiento, mutación y competencia. En sí, en los algoritmos evolutivos se requiere codificar las estructuras del problema de optimización, definir las operaciones entre los individuos, una función de adaptabilidad y los mecanismos de selección. Los algoritmos genéticos inicialmente se conocieron como planes reproductivos, y fueron introducidos por John H. Holland a principios de los años sesenta y fueron utilizados en el aprendizaje automático. El algoritmo genético es un algoritmo evolutivo en el cual el apareamiento es el operador principal y la mutación es un operador secundario, en cuanto al otro operador se utiliza a manera de selección probabilística
Coloquialmente, por élite se entiende un grupo pequeño que por algún motivo, característica, facultad o privilegio es superior o mejor en comparación al grueso de una población determinada; con cualidades o prerrogativas de las que la gran mayoría no disfrutan. En general, se habla de élite como sinónimo de elegido, escogido, eminente o distinguido. Esta concepción tiene más o menos el mismo significado con que éste término es manejado en las ciencias sociales. Es común también que se le llame elitista a quienes son selectivos, a quienes discriminan a otros, a los que manifiestan repulsión por lo común o popular, que le dan una valoración negativa o califican peyorativamente a los conceptos de masa y mayoría. Un algoritmo genético, desde el punto de vista de la optimización, es un método poblacional de búsqueda dirigida basada en probabilidad. Bajo una condición bastante débil, que el algoritmo mantenga elitismo, es decir, guarde siempre al mejor elemento de la población sin hacerle ningún cambio, se puede demostrar que el algoritmo converge en probabilidad al óptimo. En otras palabras, al aumentar el número de iteraciones, la probabilidad de tener el óptimo en la población tiende a uno. Un algoritmo genético emula el comportamiento de una población de individuos que representan soluciones y que evoluciona en base a los principios de la evolución natural: reproducción mediante operadores genéticos y selección de los mejores individuos, correspondiendo éstos a las mejores soluciones del problema a optimizar.
El método más utilizado para mejorar la convergencia de los algoritmos genéticos es el elitismo. Este método consiste básicamente en realizar la etapa de selección en dos partes: (1) Se realiza un muestreo en una élite de “ere” miembros de entre los mejores de la población inicial y se incorporan directamente a la población final, sin pasar por la población intermedia. (2) La población auxiliar de criadores se muestrea de entre los “total menos ere” restantes miembros de la población inicial. Normalmente, el tamaño de la élite “ere” es bastante pequeño y el tipo de muestreo es bien directo o bien por sorteo, ambos en la variedad diversa.
Para aprovechar las ventajas del modelo del proceso evolutivo en la resolución de un problema de optimización, se deben establecer las siguientes correspondencias: (1) Una apropiada codificación de las posibles soluciones del problema representará a éstas de la misma forma que el cromosoma. Representa a los individuos de la especie. Dada esta unívoca relación, se usarán indistintamente los términos solución, codificación, cromosoma o individuo. (2) La adecuación de cada solución será una medida del comportamiento de ésta en el problema particular considerado. Normalmente, es el valor objetivo de la solución. Así, una solución está más adecuada a un problema cuanto mejor sea su valor objetivo. (3) La definición de algunos operadores genéticos que, al actuar sobre una o varias soluciones, suministren una o más soluciones al alterar genéticamente los cromosomas. Juegan el papel del apareamiento y la mutación en el proceso evolutivo natural.
En principio aparenta una cierta conveniencia contar con una estrategia de selección estricta para que mejore rápidamente la población y converja el algoritmo, es decir, que la población se acumule alrededor de un genotipo óptimo. Esto no es cierto. Lo que ocurre es que la población se acumula rápidamente alrededor de algún individuo que es bueno, comparativamente con el resto de los individuos considerados a lo largo de la ejecución del algoritmo, pero este individuo puede no ser el mejor posible. A esto se le suele llamar convergencia prematura. No se puede asegurar pero sí procurar que lo anterior no ocurra. Además de la explotación es necesario que exista exploración. El algoritmo genético debe, no sólo seleccionar de entre lo mejor que ha encontrado, sino procurar encontrar mejores individuos. En la estrategia de selección normalmente se incluye un elemento extra que sirve de “ancla”. Si sólo se hace selección forzando que sea más probable elegir al mejor individuo de la población pero sin asegurarlo, es posible que este individuo se pierda y no forme parte de la siguiente generación. Para evitar lo anterior se fuerza la selección de los mejores individuos de la generación para pasar intactos a la siguiente. A esta estrategia se le denomina elitismo y puede ser generalizada especificando que permanezcan en la población los mejores individuos de las pasadas generaciones.
El mecanismo elitista pretende asegurar que aquel o aquellos individuos que son los más aptos de la población actual sobrevivan y continúen participando en el proceso evolutivo, pasando a la siguiente generación de manera intacta, sin recombinarse ni mutarse. Implementar este mecanismo asegura que la mejor aptitud encontrada hasta el momento, el mejor individuo hasta el momento, no se perderá en la siguiente generación. El elitismo es importante, pues garantiza, a través de pruebas matemáticas, la convergencia global del algoritmo genético. Se acepta que con el elitismo, cuando se mantiene una copia del mejor individuo es posible garantizar convergencia global para un problema de optimización. En este dominio existen variantes de modelos elitistas a las que se denominan elitismo parcial y elitismo total. Por elitismo parcial se quiere decir que en una población de tamaño “ene” se mantiene una copia de los mejores “eme” individuos hasta el total de generaciones definidas. Por elitismo total se quiere decir que se mantiene una copia de los mejores “ene” individuos, el total de individuos de la población, hasta el total de generaciones definidas.
Bajo ciertas condiciones muy generales, la introducción del elitismo garantiza la convergencia teórica al óptimo global; en la práctica, mejora la velocidad de convergencia de los algoritmos genéticos cuando la función de evaluación es unidmodal, es decir, no hay subóptimos, sin embargo la velocidad de convergencia empeora con funciones fuertemente multimodales. Con tamaños de población pequeños se consiguen efectos similares a los del elitismo introduciendo un proceso de reinicialización periódica en los algoritmos genéticos: cada vez que el algoritmo genético converge se salvan los mejores individuos, se reinicializan los demás y se vuelve a comenzar. La reinicialización tiene efectos beneficiosos sobre las prestaciones del método debido a que introduce diversidad, requisito especialmente crítico en los algoritmos genéticos con poblaciones pequeñas.
En la actualidad, el paradigma de algoritmos genéticos se presume como el más popular. Aunque existen propuestas similares, como la de Fraser, y la de Bremermann, se considera a John Holland como el que definió las bases de los algoritmos genéticos modernos. En cuanto a la representación, tradicionalmente hace uso de una cadena binaria, es decir, trabajan a nivel de genotipo, lo que equivale a transformar el problema de un espacio cualquiera al binario. Por ello, en el algoritmo genético una representación adecuada es un factor importante para obtener buenos resultados. Tradicionalmente, los algoritmos genéticos hacen uso de la selección proporcional con base en la adaptabilidad. Le da mayor importancia al operador de apareamiento que al de mutación, y no cuenta con mecanismos de auto-adaptación. En cuanto a la probabilidad de apareamiento se utilizan valores altos, al contrario de la probabilidad de mutación donde los valores usualmente son bajos.
Los algoritmos genéticos son técnicas de optimización que se basan en la evolución de las especies, son utilizados especialmente en problemas bastante complicados donde las técnicas tradicionales de optimización no obtienen buenos resultados. El pensamiento evolutivo actual gira en torno al Neo-Darwinismo, que está basado principalmente en las ideas de Darwin, Weismann y Mendel, el cual establece que toda la vida en el planeta puede ser explicada a través de: selección, apareamiento, mutación y competencia. En sí, en los algoritmos evolutivos se requiere codificar las estructuras del problema de optimización, definir las operaciones entre los individuos, una función de adaptabilidad y los mecanismos de selección. Los algoritmos genéticos inicialmente se conocieron como planes reproductivos, y fueron introducidos por John H. Holland a principios de los años sesenta y fueron utilizados en el aprendizaje automático. El algoritmo genético es un algoritmo evolutivo en el cual el apareamiento es el operador principal y la mutación es un operador secundario, en cuanto al otro operador se utiliza a manera de selección probabilística
Coloquialmente, por élite se entiende un grupo pequeño que por algún motivo, característica, facultad o privilegio es superior o mejor en comparación al grueso de una población determinada; con cualidades o prerrogativas de las que la gran mayoría no disfrutan. En general, se habla de élite como sinónimo de elegido, escogido, eminente o distinguido. Esta concepción tiene más o menos el mismo significado con que éste término es manejado en las ciencias sociales. Es común también que se le llame elitista a quienes son selectivos, a quienes discriminan a otros, a los que manifiestan repulsión por lo común o popular, que le dan una valoración negativa o califican peyorativamente a los conceptos de masa y mayoría. Un algoritmo genético, desde el punto de vista de la optimización, es un método poblacional de búsqueda dirigida basada en probabilidad. Bajo una condición bastante débil, que el algoritmo mantenga elitismo, es decir, guarde siempre al mejor elemento de la población sin hacerle ningún cambio, se puede demostrar que el algoritmo converge en probabilidad al óptimo. En otras palabras, al aumentar el número de iteraciones, la probabilidad de tener el óptimo en la población tiende a uno. Un algoritmo genético emula el comportamiento de una población de individuos que representan soluciones y que evoluciona en base a los principios de la evolución natural: reproducción mediante operadores genéticos y selección de los mejores individuos, correspondiendo éstos a las mejores soluciones del problema a optimizar.
El método más utilizado para mejorar la convergencia de los algoritmos genéticos es el elitismo. Este método consiste básicamente en realizar la etapa de selección en dos partes: (1) Se realiza un muestreo en una élite de “ere” miembros de entre los mejores de la población inicial y se incorporan directamente a la población final, sin pasar por la población intermedia. (2) La población auxiliar de criadores se muestrea de entre los “total menos ere” restantes miembros de la población inicial. Normalmente, el tamaño de la élite “ere” es bastante pequeño y el tipo de muestreo es bien directo o bien por sorteo, ambos en la variedad diversa.
Para aprovechar las ventajas del modelo del proceso evolutivo en la resolución de un problema de optimización, se deben establecer las siguientes correspondencias: (1) Una apropiada codificación de las posibles soluciones del problema representará a éstas de la misma forma que el cromosoma. Representa a los individuos de la especie. Dada esta unívoca relación, se usarán indistintamente los términos solución, codificación, cromosoma o individuo. (2) La adecuación de cada solución será una medida del comportamiento de ésta en el problema particular considerado. Normalmente, es el valor objetivo de la solución. Así, una solución está más adecuada a un problema cuanto mejor sea su valor objetivo. (3) La definición de algunos operadores genéticos que, al actuar sobre una o varias soluciones, suministren una o más soluciones al alterar genéticamente los cromosomas. Juegan el papel del apareamiento y la mutación en el proceso evolutivo natural.
En principio aparenta una cierta conveniencia contar con una estrategia de selección estricta para que mejore rápidamente la población y converja el algoritmo, es decir, que la población se acumule alrededor de un genotipo óptimo. Esto no es cierto. Lo que ocurre es que la población se acumula rápidamente alrededor de algún individuo que es bueno, comparativamente con el resto de los individuos considerados a lo largo de la ejecución del algoritmo, pero este individuo puede no ser el mejor posible. A esto se le suele llamar convergencia prematura. No se puede asegurar pero sí procurar que lo anterior no ocurra. Además de la explotación es necesario que exista exploración. El algoritmo genético debe, no sólo seleccionar de entre lo mejor que ha encontrado, sino procurar encontrar mejores individuos. En la estrategia de selección normalmente se incluye un elemento extra que sirve de “ancla”. Si sólo se hace selección forzando que sea más probable elegir al mejor individuo de la población pero sin asegurarlo, es posible que este individuo se pierda y no forme parte de la siguiente generación. Para evitar lo anterior se fuerza la selección de los mejores individuos de la generación para pasar intactos a la siguiente. A esta estrategia se le denomina elitismo y puede ser generalizada especificando que permanezcan en la población los mejores individuos de las pasadas generaciones.
El mecanismo elitista pretende asegurar que aquel o aquellos individuos que son los más aptos de la población actual sobrevivan y continúen participando en el proceso evolutivo, pasando a la siguiente generación de manera intacta, sin recombinarse ni mutarse. Implementar este mecanismo asegura que la mejor aptitud encontrada hasta el momento, el mejor individuo hasta el momento, no se perderá en la siguiente generación. El elitismo es importante, pues garantiza, a través de pruebas matemáticas, la convergencia global del algoritmo genético. Se acepta que con el elitismo, cuando se mantiene una copia del mejor individuo es posible garantizar convergencia global para un problema de optimización. En este dominio existen variantes de modelos elitistas a las que se denominan elitismo parcial y elitismo total. Por elitismo parcial se quiere decir que en una población de tamaño “ene” se mantiene una copia de los mejores “eme” individuos hasta el total de generaciones definidas. Por elitismo total se quiere decir que se mantiene una copia de los mejores “ene” individuos, el total de individuos de la población, hasta el total de generaciones definidas.
Bajo ciertas condiciones muy generales, la introducción del elitismo garantiza la convergencia teórica al óptimo global; en la práctica, mejora la velocidad de convergencia de los algoritmos genéticos cuando la función de evaluación es unidmodal, es decir, no hay subóptimos, sin embargo la velocidad de convergencia empeora con funciones fuertemente multimodales. Con tamaños de población pequeños se consiguen efectos similares a los del elitismo introduciendo un proceso de reinicialización periódica en los algoritmos genéticos: cada vez que el algoritmo genético converge se salvan los mejores individuos, se reinicializan los demás y se vuelve a comenzar. La reinicialización tiene efectos beneficiosos sobre las prestaciones del método debido a que introduce diversidad, requisito especialmente crítico en los algoritmos genéticos con poblaciones pequeñas.
Guillermo Choque Aspiazu
http://www.eldiario.net/
Marzo 15 de 2010
No hay comentarios:
Publicar un comentario