Computación Evolutiva: Algoritmos Genéticos y Problemas de Optimización
Desde mediados del decenio de 1960, se han planteado un conjunto de nuevas herramientas de análisis para la optimización inteligente que se inspiran en la teoría de la evolución darwiniana. La Computación Evolutiva, al igual que otras herramientas de inteligencia virtual, tiene sus raíces en la naturaleza. Es un intento de imitar el proceso evolutivo utilizando intrucciones y algoritmos.
La evolución es un proceso de optimización. Uno de los principales principios de la evolución es la herencia. Cada generación hereda las características de la evolución de la generación anterior y pasa esas mismas características a la siguiente generación. Estas características incluyen el progreso, el crecimiento y el desarrollo. Este paso de las características de generación en generación se facilita a través de los genes.
Algoritmos Genéticos
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. En un algoritmo genético, tras parametrizar el problema en una serie de variables, 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.
En la naturaleza, el proceso evolutivo se produce cuando las siguientes cuatro condiciones se satisfacen: Una entidad que tiene la capacidad de reproducirse. Hay una población de libre reproducción de tales entidades. Existe cierta variedad entre la libre reproducción de las entidades. Esta variedad está asociada con algunas diferencias en la capacidad para sobrevivir en el medio ambiente.
La inteligencia y la evolución están íntimamente relacionadas. La inteligencia ha sido definida como la capacidad de un sistema para adaptar su comportamiento a cumplir los objetivos en una serie de ambientes. Mediante la imitación del proceso de la evolución usando intrucciones y algoritmos de computadoras, los investigadores tratan de imitar la inteligencia asociada a la capacidad de resolución de problemas similares a los resueltos en el proceso de evolución. Como en la vida real, este tipo de adaptación continua crea organismos muy robustos. Todo el proceso continúa a través de muchas generaciones, los mejores genes se entregan a las generaciones futuras. El resultado suele ser una muy buena solución al problema. Al simular con ordenadores el proceso de la evolución, los operadores genéticos lograr la transmisión de los genes de generación en generación. Estos operadores (crossover, la inversión, y mutación) son las principales herramientas para el desove de una nueva generación de individuos a partir de los individuos aptos de la población actual. Dichos operadores preservan el equilibrio necesario con una búsqueda inteligente: el equilibrio entre la explotación (aprovechamiento de la información ya obtenida) y la exploración (búsqueda de nuevas áreas).
Mecanismo de un Algoritmo Genético
El proceso de optimización de la genética se puede dividir en los siguientes pasos:
La evolución es un proceso de optimización. Uno de los principales principios de la evolución es la herencia. Cada generación hereda las características de la evolución de la generación anterior y pasa esas mismas características a la siguiente generación. Estas características incluyen el progreso, el crecimiento y el desarrollo. Este paso de las características de generación en generación se facilita a través de los genes.
Algoritmos Genéticos
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. En un algoritmo genético, tras parametrizar el problema en una serie de variables, 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.
En la naturaleza, el proceso evolutivo se produce cuando las siguientes cuatro condiciones se satisfacen: Una entidad que tiene la capacidad de reproducirse. Hay una población de libre reproducción de tales entidades. Existe cierta variedad entre la libre reproducción de las entidades. Esta variedad está asociada con algunas diferencias en la capacidad para sobrevivir en el medio ambiente.
La inteligencia y la evolución están íntimamente relacionadas. La inteligencia ha sido definida como la capacidad de un sistema para adaptar su comportamiento a cumplir los objetivos en una serie de ambientes. Mediante la imitación del proceso de la evolución usando intrucciones y algoritmos de computadoras, los investigadores tratan de imitar la inteligencia asociada a la capacidad de resolución de problemas similares a los resueltos en el proceso de evolución. Como en la vida real, este tipo de adaptación continua crea organismos muy robustos. Todo el proceso continúa a través de muchas generaciones, los mejores genes se entregan a las generaciones futuras. El resultado suele ser una muy buena solución al problema. Al simular con ordenadores el proceso de la evolución, los operadores genéticos lograr la transmisión de los genes de generación en generación. Estos operadores (crossover, la inversión, y mutación) son las principales herramientas para el desove de una nueva generación de individuos a partir de los individuos aptos de la población actual. Dichos operadores preservan el equilibrio necesario con una búsqueda inteligente: el equilibrio entre la explotación (aprovechamiento de la información ya obtenida) y la exploración (búsqueda de nuevas áreas).
Mecanismo de un Algoritmo Genético
El proceso de optimización de la genética se puede dividir en los siguientes pasos:
1. Generación de la población inicial.
2. Evaluación de la aptitud de cada individuo en la población.
3. Ranking de los individuos en base a su idoneidad.
4. Selección de las personas para producir la próxima generación sobre la base de su idoneidad.
5. Uso de las operaciones genéticas, como el crossover, la inversión y la mutación, para generar una nueva población.
6. Continuar el proceso por el que se remonta a la etapa 2, hasta que se cumplan los objetivos del problema.
La población inicial suele ser generado mediante un proceso aleatorio que cubra todo el espacio del problema. Esto garantizará una amplia variedad en la reserva genética. Cada problema está codificado en la forma de un cromosoma. Cada cromosoma está recogido en un conjunto de genes. Cada gen representa un parámetro en el problema. En los algoritmos genéticos clásicos, una cadena de ceros y unos o una cadena de bits representa cada gen (parámetro). Por lo tanto, un cromosoma es una larga cadena de bits que incluye todos los genes (parámetros) de un individuo.
En cada generación, el top ranking individual se guarda como la solución óptima al problema. Cada vez que un nuevo y mejor individuo está evolucionado, se convierte en la solución óptima. La convergencia de los procesos pueden ser evaluados utilizando varios criterios. Muchas aplicaciones simplemente utilizan un cierto número de generaciones como criterio de convergencia. Como otro criterio, la convergencia puede tener lugar cuando un nuevo y mejor individuo no evolucionó en un plazo de cuatro a cinco generaciones.
Otro aspecto importante es la introducción de limitaciones para el algoritmo. En la mayoría de los casos, ciertas limitaciones deben ser codificadas en el proceso a fin de que los individuos generados sean "legales". La legalidad de un individuo se define como su conformidad con las limitaciones del problema.
La población inicial suele ser generado mediante un proceso aleatorio que cubra todo el espacio del problema. Esto garantizará una amplia variedad en la reserva genética. Cada problema está codificado en la forma de un cromosoma. Cada cromosoma está recogido en un conjunto de genes. Cada gen representa un parámetro en el problema. En los algoritmos genéticos clásicos, una cadena de ceros y unos o una cadena de bits representa cada gen (parámetro). Por lo tanto, un cromosoma es una larga cadena de bits que incluye todos los genes (parámetros) de un individuo.
En cada generación, el top ranking individual se guarda como la solución óptima al problema. Cada vez que un nuevo y mejor individuo está evolucionado, se convierte en la solución óptima. La convergencia de los procesos pueden ser evaluados utilizando varios criterios. Muchas aplicaciones simplemente utilizan un cierto número de generaciones como criterio de convergencia. Como otro criterio, la convergencia puede tener lugar cuando un nuevo y mejor individuo no evolucionó en un plazo de cuatro a cinco generaciones.
Otro aspecto importante es la introducción de limitaciones para el algoritmo. En la mayoría de los casos, ciertas limitaciones deben ser codificadas en el proceso a fin de que los individuos generados sean "legales". La legalidad de un individuo se define como su conformidad con las limitaciones del problema.
Aplicación en la Industria del Petróleo
Se han generado varias aplicaciones de los algoritmos genéticos en la industria del petróleo y del gas natural. La primera aplicación en la literatura se remonta a uno de los estudiantes Holland llamado David Goldberg. Él aplicó un algoritmo genético para encontrar el diseño óptimo de líneas para el transporte de gas. Desde entonces, los algoritmos genéticos se han utilizado en variadas aplicaciones vinculadas a la industria de los hidrocarburos. Estas incluyen caracterización y modelaje de yacimientos, en la distribución de inyección en gas-lift, en petrofísica y geología del petróleo, así como en el análisis de pruebas de pozos, y el diseño de fracturamiento hidráulico.
Conclusión
Los paradigmas de la Computación Evolutiva proporcionan un entorno prometedor y capaz de resolver muchos problemas de optimización, y diseño. Cuanto mayor sea el espacio de las posibles soluciones, es aun más eficaz el uso de estos paradigmas. La Computación Evolutiva, en general, y los Algoritmos Genéticos, en concreto, son capaces de combinar la exploración de las características de un algoritmo de búsqueda eficaz con una notable capacidad de preservar y explotar los conocimientos adquiridos durante cada paso de la búsqueda como una guía para dar el siguiente paso. Esto ofrece un enfoque inteligente para la búsqueda, de manera más eficiente, de soluciones a problemas de optimización y diseño.
Fuentes y Referencias Bibliográficas:
Fang, J.H., et. al. Genetic Algorithm and Its Application to Petrophysics, SPE 26208, UNSOLICITED, 1992.
Goldberg, D. E., Computer Aided Gas Pipeline Operation Using Genetic Algorithms and Rule Learning, Ph.D. dissertation, University of Michigan, Ann Arbor, Michigan. 1983.
Guerreiro, J.N.C., et. al., Identification of Reservoir Heterogeneities Using Tracer Breakthrough Profiles and Genetic Algorithms, SPE 39066, Latin American and Caribbean Petroleum Engineering Conference and Exhibition held in Rio de Janeiro, Brazil, 30 August-3 September, 1997
Hu, L. Y., et. al., Random Genetic Simulation of the Internal Geometry of Deltaic Sandstone Bodies, SPE 24714, SPE 67th Annual Technical Conference and Exhibition of the Society of Petroleum Engineers held in Washington, DC, October 4-7, 1992.
Martinez, E.R. et. al., Application of Genetic Algorithm on the Distribution of Gas-Lift Injection, SPE 26993, SPE 69th Annual Technical Conference and Exhibition held in New Orleans, LA, U.S.A., 25-28 September, 1994.
Mohaghegh, S., Balan, B., Ameri, S., and McVey, D.S., A Hybrid, Neuro-Genetic Approach to Hydraulic Fracture Treatment Design and Optimization, SPE 36602, SPE Annual Technical Conference and Exhibition held in Denver, Colorado, 6-9 October, 1996.
Manzanilla, O. “Los Algoritmos Genéticos y su Aplicación en la Optimización” Cátedra de Métodos Discretos de Optimización - Prof. Pedro Di Novella. Maestría en Ingeniería de Sistemas - Opción Investigación de Operaciones Universidad Simón Bolívar, Caracas-Venezuela. Diciembre, 2003
Mohaghegh, S. " Virtual Intelligence and its Applications in Petroleum Engineering. Part 2. Evolutionary Computing", JPT - Journal of Petroleum Technology, October 2000.
Sen, M.K. et. al., Stochastic Reservoir Modeling Using Simulated Annealing and Genetic Algorithm, SPE 24754, SPE 67th Annual Technical Conference and Exhibition of the Society of Petroleum Engineers held in Washington, DC, October 4-7, 1992.
Yin, Hongjun, Zhai, Yunfang, An Optimum Method of Early -Time Well Test Analysis - Genetic Algorithm, SPE 50905, International Oil & Gas Conference and Exhibition in China held in Beijing, China, 2-6 November, 1998
Se han generado varias aplicaciones de los algoritmos genéticos en la industria del petróleo y del gas natural. La primera aplicación en la literatura se remonta a uno de los estudiantes Holland llamado David Goldberg. Él aplicó un algoritmo genético para encontrar el diseño óptimo de líneas para el transporte de gas. Desde entonces, los algoritmos genéticos se han utilizado en variadas aplicaciones vinculadas a la industria de los hidrocarburos. Estas incluyen caracterización y modelaje de yacimientos, en la distribución de inyección en gas-lift, en petrofísica y geología del petróleo, así como en el análisis de pruebas de pozos, y el diseño de fracturamiento hidráulico.
Conclusión
Los paradigmas de la Computación Evolutiva proporcionan un entorno prometedor y capaz de resolver muchos problemas de optimización, y diseño. Cuanto mayor sea el espacio de las posibles soluciones, es aun más eficaz el uso de estos paradigmas. La Computación Evolutiva, en general, y los Algoritmos Genéticos, en concreto, son capaces de combinar la exploración de las características de un algoritmo de búsqueda eficaz con una notable capacidad de preservar y explotar los conocimientos adquiridos durante cada paso de la búsqueda como una guía para dar el siguiente paso. Esto ofrece un enfoque inteligente para la búsqueda, de manera más eficiente, de soluciones a problemas de optimización y diseño.
Fuentes y Referencias Bibliográficas:
Fang, J.H., et. al. Genetic Algorithm and Its Application to Petrophysics, SPE 26208, UNSOLICITED, 1992.
Goldberg, D. E., Computer Aided Gas Pipeline Operation Using Genetic Algorithms and Rule Learning, Ph.D. dissertation, University of Michigan, Ann Arbor, Michigan. 1983.
Guerreiro, J.N.C., et. al., Identification of Reservoir Heterogeneities Using Tracer Breakthrough Profiles and Genetic Algorithms, SPE 39066, Latin American and Caribbean Petroleum Engineering Conference and Exhibition held in Rio de Janeiro, Brazil, 30 August-3 September, 1997
Hu, L. Y., et. al., Random Genetic Simulation of the Internal Geometry of Deltaic Sandstone Bodies, SPE 24714, SPE 67th Annual Technical Conference and Exhibition of the Society of Petroleum Engineers held in Washington, DC, October 4-7, 1992.
Martinez, E.R. et. al., Application of Genetic Algorithm on the Distribution of Gas-Lift Injection, SPE 26993, SPE 69th Annual Technical Conference and Exhibition held in New Orleans, LA, U.S.A., 25-28 September, 1994.
Mohaghegh, S., Balan, B., Ameri, S., and McVey, D.S., A Hybrid, Neuro-Genetic Approach to Hydraulic Fracture Treatment Design and Optimization, SPE 36602, SPE Annual Technical Conference and Exhibition held in Denver, Colorado, 6-9 October, 1996.
Manzanilla, O. “Los Algoritmos Genéticos y su Aplicación en la Optimización” Cátedra de Métodos Discretos de Optimización - Prof. Pedro Di Novella. Maestría en Ingeniería de Sistemas - Opción Investigación de Operaciones Universidad Simón Bolívar, Caracas-Venezuela. Diciembre, 2003
Mohaghegh, S. " Virtual Intelligence and its Applications in Petroleum Engineering. Part 2. Evolutionary Computing", JPT - Journal of Petroleum Technology, October 2000.
Sen, M.K. et. al., Stochastic Reservoir Modeling Using Simulated Annealing and Genetic Algorithm, SPE 24754, SPE 67th Annual Technical Conference and Exhibition of the Society of Petroleum Engineers held in Washington, DC, October 4-7, 1992.
Yin, Hongjun, Zhai, Yunfang, An Optimum Method of Early -Time Well Test Analysis - Genetic Algorithm, SPE 50905, International Oil & Gas Conference and Exhibition in China held in Beijing, China, 2-6 November, 1998
