En los últimos años, la comunidad científica ha mostrado un creciente interés en una nueva técnica de búsqueda basada en la teoría de la evolución y que se conoce como “algoritmo genético”. Esta técnica se basa en los mecanismos de selección que utiliza la naturaleza, de acuerdo a los cuales los individuos más aptos de una población son los que sobreviven, al adaptarse de forma más fácil a los cambios que se producen en su entorno. Hoy en día se sabe que estos cambios se efectúan en los genes de un individuo, los cuales constituyen la unidad básica de codificación de cada uno de los atributos de un ser vivo, y que los atributos más deseables, es decir aquellos que le permiten a un individuo adaptarse mejor a su entorno, se transmiten a sus descendientes cuando éste se reproduce sexualmente. Un investigador de la Universidad de Michigan llamado John Holland estaba consciente de la importancia de la selección natural, y a fines de los años 1960 desarrolló una técnica que permitió incorporarlos en un programa de computadora. Su objetivo era lograr que las computadoras aprendieran por sí mismas. A la técnica que inventó Holland se le llamó originalmente “planes reproductivos”, pero se hizo popular hacia el año 1975 con el nombre de “algoritmos genéticos”.
Una definición bastante completa de un algoritmo genético es la siguiente: “Un algoritmo genético es un algoritmo matemático altamente paralelo que transforma un conjunto de objetos matemáticos individuales, con respecto al tiempo, usando operaciones modeladas de acuerdo al principio Darwiniano de reproducción y supervivencia del más apto, y tras haberse presentado de forma natural una serie de operaciones genéticas, entre las que destaca la recombinación sexual. Cada uno de estos objetos matemáticos suele ser una cadena de caracteres, letras o números, de longitud fija que se ajusta al modelo de las cadenas asociado a los cromosomas biológicos, y se les asocia además una cierta función matemática que refleja su grado de adaptabilidad.
Por su parte, un sistema distribuido se define como una colección de computadoras autónomas conectadas por una red, y con el software distribuido adecuado para que el sistema sea visto por los usuarios como una única entidad capaz de proporcionar facilidades de computación. El desarrollo de los sistemas distribuidos vino de la mano de las redes locales de alta velocidad a principios de los años 1970. Más recientemente, la disponibilidad de computadoras personales de altas prestaciones, estaciones de trabajo y servidores ha resultado en un mayor desplazamiento hacia los sistemas distribuidos en detrimento de las computadoras centralizadas multiusuario. Esta tendencia se ha acelerado por el desarrollo de software para sistemas distribuidos, diseñado para soportar el desarrollo de aplicaciones distribuidas. Este software permite a las computadoras coordinar sus actividades y compartir los recursos del sistema: hardware, software y datos. Los sistemas distribuidos se implementan en diversas plataformas hardware, desde unas pocas estaciones de trabajo conectadas por una red de área local, hasta Internet, una colección de redes de área local y de área extensa interconectados, que en lazan millones de computadoras.
De retorno a la idea central de la presente propuesta, el proceso de evolución, similarmente a lo que sucede en los seres vivos, toma lugar en el código fundamental de los individuos o estructuras. En la implementación tradicional de los algoritmos genéticos las variables de diseño del problema a ser optimizado son codificadas en un alfabeto en particular, inicialmente códigos binarios, más recientemente números reales, y concatenadas para generar cromosomas artificiales. Posteriormente, el proceso de selección natural toma lugar y los cromosomas con códigos más saludables tienen mayor probabilidad de reproducirse que aquellos más débiles. Una vez seleccionados para reproducción y basados en la fortaleza de sus representaciones, los cromosomas se combinan mediante la aplicación de diferentes operadores de apareamiento, el material genético es intercambiando con el fin de producir diferente descendencia. Por otro lado, en el proceso de mutación ocurre un cambio repentino en una posición particular del cromosoma lo cual altera su estructura y lo hace diferente del cromosoma de sus padres.
Los procesos de evolución artificial dependen de los mecanismos de los diferentes operadores y parámetros involucrados en su construcción. La selección inapropiada de ellos hace que se presente un modo severo de falla en el algoritmo genético denominado convergencia prematura. El mismo es originado por la carencia de diversidad en la población, lo cual afecta el balance del algoritmo entre explotar lo que ya conoce y explorar nuevas posibilidades que podrían funcionar mejor. Entre los factores que pueden hacer que se pierda este delicado balance, se encuentran los siguientes: la pérdida de material importante dentro del cromosoma debido a la presión de selección, la distorsión o ruido en la probabilidad de selección, la destrucción de esquemas o cadenas de estructuras con información importante, debido al operador de apareamiento y una inadecuada escogencia de los valores de los parámetros probabilísticos que guían los diferentes operadores genéticos. Cuando el algoritmo cae en este modo de falla el mismo queda a la deriva y es conducido hacia una región del espacio de diseño donde seguramente no se encuentra el óptimo global.
El proceso de selección es la manera como los individuos son escogidos para ser apareados. La correcta elección del modelo usado para realizar esta operación es un factor importante que ayuda a evitar la selección inadecuada de padres, por el hecho que si los cromosomas que portan valiosa información nunca son seleccionados para la reproducción, el material genético contenidos en ellos puede considerarse perdido si no hay una vía para pasar esta información a otros individuos. Otra fuente de pérdida de material genético importante es la destrucción de las cadenas de información o esquemas, situación que puede presentarse cuando el punto de apareamiento separa material genético que pertenece a un hiperplano que contiene una solución óptima. En la literatura especializada se pueden conseguir numerosas técnicas que reducen la probabilidad de alterar estas cadenas o bloques de construcción y mejorar el proceso de selección.
La correcta elección de parámetros tales como tamaño de población, tasa de mutación y probabilidad de apareamiento, entre otros, es uno de los tópicos más estudiados debido a que al variar sus valores repercuten directamente en el balance entre la exploración y explotación del espacio de diseño, representando la vía como los algoritmos genéticos encuentran soluciones en los diferentes hiperplanos del espacio de búsqueda. A fin de preservar la diversidad en la población se desarrollaron algoritmos de tipo distribuido y celular basándose en la teoría de “separación espacial”. En esta teoría la población total es dividida en pequeñas subpoblaciones, cada una de las cuales evoluciona independiente y simultáneamente de acuerdo a un algoritmo genético especifico. Periódicamente un mecanismo de migración intercambia individuos entre las subpoblaciones, permitiendo inyectar nueva diversidad dentro de las subpoblaciones convergentes.
Los algoritmos genéticos distribuidos se construyen combinando diferentes tipos de operadores genéticos, los cuales exhiben diferentes grados de exploración o explotación, en las diferentes subpoblaciones que componen la topología distribuida de subpoblaciones. Por ejemplo, en el trabajo de Herrera y Lozano escrito el año 2000, se aplican diferentes operadores de apareamiento de tipo real a cada subpoblación, los cuales presentan diferencias en sus propiedades de exploración-explotación y en el grado en que son aplicadas, para proponer un algoritmo genético distribuido gradual y codificado en punto flotante. Así mismo, en la literatura se encuentran también algoritmos genéticos distribuidos pero codificados en binario como el propuesto por Potts y sus colegas el año 1994, donde se propone el uso de diferentes grados y niveles del operador de mutación para modificar el carácter de explotación o exploración de las diferentes subpoblaciones.
Una metodología de optimización propuesta se encuentra dividida en dos niveles. En un nivel macro, un conjunto de subpoblaciones aisladas son construidas sobre los vértices de un cubo formando una topología hipercúbica basándose en un algoritmo genético distribuido. Por otro lado a nivel micro, en el interior de cada subpoblación, se ejecuta un algoritmo genético más simple con el fin de generar los individuos que en posteriores etapas migraran a las subpoblaciones vecinas. Las estrategias de migración empleadas se basan en la emigración del mejor individuo de cada subpoblación cada cierto número de subgeneraciones internas.
Una definición bastante completa de un algoritmo genético es la siguiente: “Un algoritmo genético es un algoritmo matemático altamente paralelo que transforma un conjunto de objetos matemáticos individuales, con respecto al tiempo, usando operaciones modeladas de acuerdo al principio Darwiniano de reproducción y supervivencia del más apto, y tras haberse presentado de forma natural una serie de operaciones genéticas, entre las que destaca la recombinación sexual. Cada uno de estos objetos matemáticos suele ser una cadena de caracteres, letras o números, de longitud fija que se ajusta al modelo de las cadenas asociado a los cromosomas biológicos, y se les asocia además una cierta función matemática que refleja su grado de adaptabilidad.
Por su parte, un sistema distribuido se define como una colección de computadoras autónomas conectadas por una red, y con el software distribuido adecuado para que el sistema sea visto por los usuarios como una única entidad capaz de proporcionar facilidades de computación. El desarrollo de los sistemas distribuidos vino de la mano de las redes locales de alta velocidad a principios de los años 1970. Más recientemente, la disponibilidad de computadoras personales de altas prestaciones, estaciones de trabajo y servidores ha resultado en un mayor desplazamiento hacia los sistemas distribuidos en detrimento de las computadoras centralizadas multiusuario. Esta tendencia se ha acelerado por el desarrollo de software para sistemas distribuidos, diseñado para soportar el desarrollo de aplicaciones distribuidas. Este software permite a las computadoras coordinar sus actividades y compartir los recursos del sistema: hardware, software y datos. Los sistemas distribuidos se implementan en diversas plataformas hardware, desde unas pocas estaciones de trabajo conectadas por una red de área local, hasta Internet, una colección de redes de área local y de área extensa interconectados, que en lazan millones de computadoras.
De retorno a la idea central de la presente propuesta, el proceso de evolución, similarmente a lo que sucede en los seres vivos, toma lugar en el código fundamental de los individuos o estructuras. En la implementación tradicional de los algoritmos genéticos las variables de diseño del problema a ser optimizado son codificadas en un alfabeto en particular, inicialmente códigos binarios, más recientemente números reales, y concatenadas para generar cromosomas artificiales. Posteriormente, el proceso de selección natural toma lugar y los cromosomas con códigos más saludables tienen mayor probabilidad de reproducirse que aquellos más débiles. Una vez seleccionados para reproducción y basados en la fortaleza de sus representaciones, los cromosomas se combinan mediante la aplicación de diferentes operadores de apareamiento, el material genético es intercambiando con el fin de producir diferente descendencia. Por otro lado, en el proceso de mutación ocurre un cambio repentino en una posición particular del cromosoma lo cual altera su estructura y lo hace diferente del cromosoma de sus padres.
Los procesos de evolución artificial dependen de los mecanismos de los diferentes operadores y parámetros involucrados en su construcción. La selección inapropiada de ellos hace que se presente un modo severo de falla en el algoritmo genético denominado convergencia prematura. El mismo es originado por la carencia de diversidad en la población, lo cual afecta el balance del algoritmo entre explotar lo que ya conoce y explorar nuevas posibilidades que podrían funcionar mejor. Entre los factores que pueden hacer que se pierda este delicado balance, se encuentran los siguientes: la pérdida de material importante dentro del cromosoma debido a la presión de selección, la distorsión o ruido en la probabilidad de selección, la destrucción de esquemas o cadenas de estructuras con información importante, debido al operador de apareamiento y una inadecuada escogencia de los valores de los parámetros probabilísticos que guían los diferentes operadores genéticos. Cuando el algoritmo cae en este modo de falla el mismo queda a la deriva y es conducido hacia una región del espacio de diseño donde seguramente no se encuentra el óptimo global.
El proceso de selección es la manera como los individuos son escogidos para ser apareados. La correcta elección del modelo usado para realizar esta operación es un factor importante que ayuda a evitar la selección inadecuada de padres, por el hecho que si los cromosomas que portan valiosa información nunca son seleccionados para la reproducción, el material genético contenidos en ellos puede considerarse perdido si no hay una vía para pasar esta información a otros individuos. Otra fuente de pérdida de material genético importante es la destrucción de las cadenas de información o esquemas, situación que puede presentarse cuando el punto de apareamiento separa material genético que pertenece a un hiperplano que contiene una solución óptima. En la literatura especializada se pueden conseguir numerosas técnicas que reducen la probabilidad de alterar estas cadenas o bloques de construcción y mejorar el proceso de selección.
La correcta elección de parámetros tales como tamaño de población, tasa de mutación y probabilidad de apareamiento, entre otros, es uno de los tópicos más estudiados debido a que al variar sus valores repercuten directamente en el balance entre la exploración y explotación del espacio de diseño, representando la vía como los algoritmos genéticos encuentran soluciones en los diferentes hiperplanos del espacio de búsqueda. A fin de preservar la diversidad en la población se desarrollaron algoritmos de tipo distribuido y celular basándose en la teoría de “separación espacial”. En esta teoría la población total es dividida en pequeñas subpoblaciones, cada una de las cuales evoluciona independiente y simultáneamente de acuerdo a un algoritmo genético especifico. Periódicamente un mecanismo de migración intercambia individuos entre las subpoblaciones, permitiendo inyectar nueva diversidad dentro de las subpoblaciones convergentes.
Los algoritmos genéticos distribuidos se construyen combinando diferentes tipos de operadores genéticos, los cuales exhiben diferentes grados de exploración o explotación, en las diferentes subpoblaciones que componen la topología distribuida de subpoblaciones. Por ejemplo, en el trabajo de Herrera y Lozano escrito el año 2000, se aplican diferentes operadores de apareamiento de tipo real a cada subpoblación, los cuales presentan diferencias en sus propiedades de exploración-explotación y en el grado en que son aplicadas, para proponer un algoritmo genético distribuido gradual y codificado en punto flotante. Así mismo, en la literatura se encuentran también algoritmos genéticos distribuidos pero codificados en binario como el propuesto por Potts y sus colegas el año 1994, donde se propone el uso de diferentes grados y niveles del operador de mutación para modificar el carácter de explotación o exploración de las diferentes subpoblaciones.
Una metodología de optimización propuesta se encuentra dividida en dos niveles. En un nivel macro, un conjunto de subpoblaciones aisladas son construidas sobre los vértices de un cubo formando una topología hipercúbica basándose en un algoritmo genético distribuido. Por otro lado a nivel micro, en el interior de cada subpoblación, se ejecuta un algoritmo genético más simple con el fin de generar los individuos que en posteriores etapas migraran a las subpoblaciones vecinas. Las estrategias de migración empleadas se basan en la emigración del mejor individuo de cada subpoblación cada cierto número de subgeneraciones internas.
No hay comentarios:
Publicar un comentario