Date post: | 10-Feb-2018 |
Category: |
Documents |
Upload: | hoangduong |
View: | 219 times |
Download: | 0 times |
Computación Evolutiva, principio y aplicaciones
D.Sc. Yván Jesús Túpac Valdivia
IEEE Sociedad de Inteligencia Computacional
12 de abril de 2013
IEEE CIS-DAY (12 de abril de 2013) Computación Evolutiva, principio y aplicacionesTÚPAC, Y. (IEEE CIS Perú) Pág 1/24
Contenido
1 Algoritmos EvolutivosIdeas PrecursorasCiclo básico de un EAParadigmas de la Computación Evolutiva
2 Aplicación EAProyecto ANEPI
3 Bibliografía
IEEE CIS-DAY (12 de abril de 2013) Computación Evolutiva, principio y aplicacionesTÚPAC, Y. (IEEE CIS Perú) Pág 2/24
Algoritmos Evolutivos
Algoritmos Evolutivos (EA)
Definición:Son algoritmos metaheurísticos basados en una población de individuosque usan mecanismos biológicamente inspirados como: mutación,recombinación, selección natural y sobrevivencia de los más aptos paraiterativamente refinar un conjunto de soluciones.
VentajasCaracterística black boxCalidad de respuesta consistente para muchos tipos de problema.
Computación Evolutiva o Algoritmos Evolutivos tratan de un conjunto detécnicas y metodologías que la componen, todas ellas con inspiraciónbiológica en la evolución Neo-Darwiniana.
IEEE CIS-DAY (12 de abril de 2013) Computación Evolutiva, principio y aplicacionesTÚPAC, Y. (IEEE CIS Perú) Pág 3/24
Algoritmos Evolutivos
Algoritmos Evolutivos (EA)Principio basado en la Naturaleza
EA son una abstracción de los procesos y principios establecidos por elDarwinismo y Neo-darwinismo y el principio goal-driven (conducido a losobjetivos) [1].
IEEE CIS-DAY (12 de abril de 2013) Computación Evolutiva, principio y aplicacionesTÚPAC, Y. (IEEE CIS Perú) Pág 4/24
Algoritmos Evolutivos Ideas Precursoras
Ideas PrecursorasNeodarwinismo
El pensamiento evolutivo actual se basa en el Neo-Darwinismo.
Paradigma Neodarwiniano:Establece que la historia de la vida puede ser explicada por los siguientesprocesos estadísticos [2]:
HerenciaReproducciónMutación y recombinaciónCompetencia ySelección Natural.
IEEE CIS-DAY (12 de abril de 2013) Computación Evolutiva, principio y aplicacionesTÚPAC, Y. (IEEE CIS Perú) Pág 5/24
Algoritmos Evolutivos Ideas Precursoras
Ideas PrecursorasNeodarwinismo
El pensamiento evolutivo actual se basa en el Neo-Darwinismo.
Paradigma Neodarwiniano:Establece que la historia de la vida puede ser explicada por los siguientesprocesos estadísticos [2]:
HerenciaReproducciónMutación y recombinaciónCompetencia ySelección Natural.
IEEE CIS-DAY (12 de abril de 2013) Computación Evolutiva, principio y aplicacionesTÚPAC, Y. (IEEE CIS Perú) Pág 5/24
Algoritmos Evolutivos Ideas Precursoras
Ideas PrecursorasNeodarwinismo
El Neodarwinismo es la combinación de:La Teoría evolutiva original de Charles DarwinEl Seleccionismo de August WeismannLa Genética de Gregor Mendel
C. Darwin
(Teoría Evolutiva)
A. Weismann
(Seleccionismo)
G. Mendel
(Genética)+ +
IEEE CIS-DAY (12 de abril de 2013) Computación Evolutiva, principio y aplicacionesTÚPAC, Y. (IEEE CIS Perú) Pág 6/24
Algoritmos Evolutivos Ideas Precursoras
Ideas PrecursorasNeodarwinismo
El Neodarwinismo es la combinación de:La Teoría evolutiva original de Charles DarwinEl Seleccionismo de August WeismannLa Genética de Gregor Mendel
C. Darwin
(Teoría Evolutiva)
A. Weismann
(Seleccionismo)
G. Mendel
(Genética)+ +
IEEE CIS-DAY (12 de abril de 2013) Computación Evolutiva, principio y aplicacionesTÚPAC, Y. (IEEE CIS Perú) Pág 6/24
Algoritmos Evolutivos Ciclo básico de un EA
Algoritmos Evolutivos: Ciclo Básico
Un algoritmo evolutivo de cualquier tipo emplea los siguientes mecanismos:
1 Una forma de codificar las soluciones x en estructuras g que sereproducirán conformando una población G0 inicial generadaaleatoriamente.
2 Una función de asignación de aptitud a(•) que depende de losindividuos x y su evaluación f (x).
3 Un mecanismo de selección basado en la aptitud a(•).4 Operaciones que actuen sobre los individuos codificados gi ∈ G para
reproducirlos.
IEEE CIS-DAY (12 de abril de 2013) Computación Evolutiva, principio y aplicacionesTÚPAC, Y. (IEEE CIS Perú) Pág 7/24
Algoritmos Evolutivos Ciclo básico de un EA
Ciclo Básico de un EA
Estos mecanismos siguen un orden como el de la figura 2:
Población InicialCrear una población
inicial de individuos
aleatorios
EvaluaciónCalcular las funciones
objetivo de los
candidatos
Asignar AptitudA partir de los valores de
de función objetivo de
los candidatos
ReproducciónCrear nuevos individuos
usando mutación y
recombinación
SelecciónEscoger los mejores
individuos para su
reproducción
Figure: Ciclo Básico de un Algoritmo Evolutivo
IEEE CIS-DAY (12 de abril de 2013) Computación Evolutiva, principio y aplicacionesTÚPAC, Y. (IEEE CIS Perú) Pág 8/24
Algoritmos Evolutivos Paradigmas de la Computación Evolutiva
Paradigmas de la Computación Evolutiva
Se puede diferenciar tres principales paradigmas de la ComputaciónEvolutiva [3]
1 Programación Evolutiva2 Estrategias Evolutivas3 Algoritmos Genéticos
Adicionalmente se encuentran dos paradigmas más:
4 Learning Classifier Systems5 Programación Genética
que son bastante próximos a Algoritmos Genéticos y ProgramaciónEvolutiva respectivamente.
IEEE CIS-DAY (12 de abril de 2013) Computación Evolutiva, principio y aplicacionesTÚPAC, Y. (IEEE CIS Perú) Pág 9/24
Algoritmos Evolutivos Paradigmas de la Computación Evolutiva
Paradigmas de la Computación Evolutiva
Se puede diferenciar tres principales paradigmas de la ComputaciónEvolutiva [3]
1 Programación Evolutiva2 Estrategias Evolutivas3 Algoritmos Genéticos
Adicionalmente se encuentran dos paradigmas más:
4 Learning Classifier Systems5 Programación Genética
que son bastante próximos a Algoritmos Genéticos y ProgramaciónEvolutiva respectivamente.
IEEE CIS-DAY (12 de abril de 2013) Computación Evolutiva, principio y aplicacionesTÚPAC, Y. (IEEE CIS Perú) Pág 9/24
Algoritmos Evolutivos Paradigmas de la Computación Evolutiva
Paradigmas de la Computación Evolutiva
Se puede diferenciar tres principales paradigmas de la ComputaciónEvolutiva [3]
1 Programación Evolutiva2 Estrategias Evolutivas3 Algoritmos Genéticos
Adicionalmente se encuentran dos paradigmas más:
4 Learning Classifier Systems5 Programación Genética
que son bastante próximos a Algoritmos Genéticos y ProgramaciónEvolutiva respectivamente.
IEEE CIS-DAY (12 de abril de 2013) Computación Evolutiva, principio y aplicacionesTÚPAC, Y. (IEEE CIS Perú) Pág 9/24
Algoritmos Evolutivos Paradigmas de la Computación Evolutiva
Paradigmas de la Computación EvolutivaFamilia de los Algoritmos Evolutivos
Algoritmos Evolutivos
ProgramacionEvolutiva
Algoritmos Geneticos
Programacion Genetica
Estrategias EvolutivasLearning ClassifierSystems
DiferencialEvolucion
IEEE CIS-DAY (12 de abril de 2013) Computación Evolutiva, principio y aplicacionesTÚPAC, Y. (IEEE CIS Perú) Pág 10/24
Aplicación EA Proyecto ANEPI
Proyecto ANEPIANEPI: Análise Econômica de Projetos de E&P de Petróleo sob Incerteza
Objetivo:Desarrollo de tecnologías para el Análisis de Alternativas de Desarrollode Campos de Petróleo bajo Incertidumbre Técnica y de Mercado
Optimizacion(Algoritmo Evolutivo)
EvaluacionEconomica Simulacion de
Reservorio Petrolıfero Alternativa de Desarrollo
(VPN) Reservorio
IEEE CIS-DAY (12 de abril de 2013) Computación Evolutiva, principio y aplicacionesTÚPAC, Y. (IEEE CIS Perú) Pág 11/24
Aplicación EA Proyecto ANEPI
Proyecto ANEPIANEPI: Análise Econômica de Projetos de E&P de Petróleo sob Incerteza
Objetivo:Desarrollo de tecnologías para el Análisis de Alternativas de Desarrollode Campos de Petróleo bajo Incertidumbre Técnica y de Mercado
Optimizacion(Algoritmo Evolutivo)
EvaluacionEconomica Simulacion de
Reservorio Petrolıfero Alternativa de Desarrollo
(VPN) Reservorio
IEEE CIS-DAY (12 de abril de 2013) Computación Evolutiva, principio y aplicacionesTÚPAC, Y. (IEEE CIS Perú) Pág 11/24
Aplicación EA Proyecto ANEPI
Proyecto ANEPIANEPI: Análise Econômica de Projetos de E&P de Petróleo sob Incerteza
Este proyecto constó de los siguientes módulos:
1 Optimización de alternativas en condiciones de certeza2 Análisis de Alternativas de Desarrollo de Campos Petrolíferos bajo
incertidumbres técnicas y de mercado3 Cálculo del Valor de Opción considerando incertidumbre técnica y de
Mercado
IEEE CIS-DAY (12 de abril de 2013) Computación Evolutiva, principio y aplicacionesTÚPAC, Y. (IEEE CIS Perú) Pág 12/24
Aplicación EA Proyecto ANEPI
Proyecto ANEPIOptimización de alternativas en condiciones de certeza
Encontrar una o más alternativas iniciales de desarrollo óptimas: número,localización, tipo, orden de perforación y dimensión de pozos petroliferos.
Aplicación de Computación Evolutiva [4, 5, 6, 7].
NPV = V −D
NPVcompute
Productioncurve
Reservoirsimulator
AlternativeWells
layout
Objective
function
ExpertReservoirmodel
CapEx
OpEx
EvolutionaryModel
knowledge
IEEE CIS-DAY (12 de abril de 2013) Computación Evolutiva, principio y aplicacionesTÚPAC, Y. (IEEE CIS Perú) Pág 13/24
Aplicación EA Proyecto ANEPI
Proyecto ANEPIOptimización de alternativas en condiciones de certeza
Modelo evolutivo:1 Representación: uso de un modelo de cromosoma con tamaño
variable (para soportar alternativas con cantidades diferentes depozos) y usando las estrategias de cromosoma creciente y cromosomaoscilante [8]
i, j i, j i, ji, ji, j,k i, j,k i, j,k i, j,kdir, l dir, l dir, l dir, l
0 1 0 1 1 10 0
Verticales Horizontales
Inyectores Productores Inyectores Productores
Mascara de activacion mi
Genotipo gi
IEEE CIS-DAY (12 de abril de 2013) Computación Evolutiva, principio y aplicacionesTÚPAC, Y. (IEEE CIS Perú) Pág 14/24
Aplicación EA Proyecto ANEPI
Proyecto ANEPIOptimización de alternativas en condiciones de certeza
Modelo evolutivo:2 Evaluación: que consta de dos etapas:
i Simulación de la producción para la alternativa de pozos de cromosoma:para obtener las curvas de producción de óleo, gas y agua. Uso de unsimulador de fluidos para modelo blackoil.
ii Cálculo del Valor Presente Neto de la alternativa del cromosoma a partirde la producción, información geométrica y datos de mercado. Uso deecuaciones para el flujo de caja descontado.
Se hace uso de la arquitectura master-slave para evaluaciones enparalelo [6, 9]
IEEE CIS-DAY (12 de abril de 2013) Computación Evolutiva, principio y aplicacionesTÚPAC, Y. (IEEE CIS Perú) Pág 15/24
Aplicación EA Proyecto ANEPI
Proyecto ANEPIOptimización de alternativas en condiciones de certeza
Modelo evolutivo: Simulación de producción
Evaluacion dela alternativa
AE Script de pozos
VPN
Alternativa(Cromosoma)
Datos de produccion:oleo, gas, agua y pasosde simulacion
Parametros demercado,inversiony operacion
Informacion de lageologıa de rocasparametros PVT, ,
info de pozos
Archivos desalida (.OUT.MRF .IRF)Simulador
blackoil
(CMG/IMEX)
Informacion demalla y pozos
Geometrıa dela malla
Filtro desalida
INCLUDE
IEEE CIS-DAY (12 de abril de 2013) Computación Evolutiva, principio y aplicacionesTÚPAC, Y. (IEEE CIS Perú) Pág 16/24
Aplicación EA Proyecto ANEPI
Proyecto ANEPIOptimización de alternativas en condiciones de certeza
Modelo evolutivo: Cálculo del VPN
NPV = PV −D
D = ( fhwa+ r)nw +b+nw
∑j=1|p j− pplat |cPV = (PVInc−PVOp)(1− I)
PVInc =T
∑i=1
Inc(ti)e−ρti PVOp =T
∑i=1
Op(ti)e−ρti
Inc(t) =(
Q(t)+G(t)1000
)Poil(t) Op(ti) = mnw +VcQ(ti)+RyInc(ti)+Fc +WcW (ti)
IEEE CIS-DAY (12 de abril de 2013) Computación Evolutiva, principio y aplicacionesTÚPAC, Y. (IEEE CIS Perú) Pág 17/24
Aplicación EA Proyecto ANEPI
Proyecto ANEPIOptimización de alternativas en condiciones de certeza
Ejemplo de Aplicación:Se usó un modelo de campo petrolífero homogéneo que consiste en unamalla de 30× 30× 1 con los siguientes parámetros geológicos:
Parámetro Valor UnidadPermeabilidad 1000.00 mdPorosidad 0.20Presión inicial 100.00 kg
cm2
Saturación agua 0.2
IEEE CIS-DAY (12 de abril de 2013) Computación Evolutiva, principio y aplicacionesTÚPAC, Y. (IEEE CIS Perú) Pág 18/24
Aplicación EA Proyecto ANEPI
Proyecto ANEPIOptimización de alternativas en condiciones de certeza
Ejemplo de Aplicación – Experimento 01 (Aleatorio):Respuesta ante una inicialización totalmente aleatoria.La respuesta encontrada es la siguiente:
Parámetro Valor UnidadVPN 1699.122 (MUS$)Petróleo 364.075 (Barriles)
HINJ
HINJ
HPRO1
VINJ
VINJ
VINJ
VINJ
VINJ
VINJ
VPRO
VPRO
VPRO
VPRO
VPRO
VPRO
VPRO
VPRO
VPRO
IEEE CIS-DAY (12 de abril de 2013) Computación Evolutiva, principio y aplicacionesTÚPAC, Y. (IEEE CIS Perú) Pág 19/24
Aplicación EA Proyecto ANEPI
Proyecto ANEPIOptimización de alternativas en condiciones de certeza
Ejemplo de Aplicación – Experimento 02 (S. Inicial):Alternativa “five-spot” original
HINJ1 HINJ2
HINJ3
HINJ4 HINJ5 HINJ6
HINJ7
HINJ8
HINJ9
HPRO1 HPRO2
HPRO3 HPRO4
Parámetro Valor UnidadVPN 1397.981 (MUS$)Petróleo 297.025 (Barriles)
Alternativa optimizada:
HINJ10 HINJ11
HINJ12
HINJ13
HINJ14
HINJ7 HINJ8
HINJ9
HPRO1 HPRO2
HPRO3 HPRO4
VINJ1
VINJ2
VINJ3
VINJ4
VINJ5 VINJ6
Parámetro Valor UnidadVPN 1667.821 (MUS$)Petróleo 359.100 (Barriles)
IEEE CIS-DAY (12 de abril de 2013) Computación Evolutiva, principio y aplicacionesTÚPAC, Y. (IEEE CIS Perú) Pág 20/24
Aplicación EA Proyecto ANEPI
Proyecto ANEPIIntegración [10, 11]
Evolution ar y Alg orithm
Genet ic operators
NPV Computing
Alternative
DVNPV −=
Objective Function
Wells Layout
Reservoir Simulator (or Proxy)
Experts’ knowledge
CAPEX Parameters
OPEX Parameters
Produ ction Curve
Reservoir Model
GENETIC ALGORITHM
Evaluation
Decision Rule(Thresho ldCurve)
Option ValueSim. Monte Car lo( Oil Pri ce )
Gene ra to r an d sa mple r
o f ra ndom numbers
Pse udo RandomLati nHypercubic Samp ling
Stochas ti c Proces sfo r a Commo di ty
Geometri c Brownia n Mot ion Mean Rev ersion Process
Ha nd li ngL ine ar
Const ra in ts
GENETIC ALGORITHM
Evaluation
Decision Rule(Thresho ldCurve)
Option ValueSim. Monte Car lo( Oil Pri ce )
Gene ra to r an d sa mple r
o f ra ndom numbers
Pse udo RandomLati nHypercubic Samp ling
Stochas ti c Proces sfo r a Commo di ty
Geometri c Brownia n Mot ion Mean Rev ersion Process
Ha nd li ngL ine ar
Const ra in ts
D e c is i o n R u le b y G e n e ti c A lg o r it h m
0
2
4
6
8
1 0
1 2
1 4
1 6
1 8
2 0
2 2
2 4
2 6
2 8
3 0
3 2
3 4
0.0
00
0.0
82
0
.164
0.2
47
0.
329
0.4
11
0.
493
0.5
75
0.6
58
0 .74
0.8
22
0.
904
0.9
86
1.0
68
1
.151
1.2
33
1.
315
1.3
97
1.
479
1.5
62
1.6
44
1.
726
1.8
08
1 .89
1.9
73
Ti me (y e a rs )
Oi
l Pr
ice
(US
$)
A lt er n at iv e 1 W a itin g 1 A lt er na ti ve 2 W ai tin g 2 A lte r na ti ve 3
W a iti n g R e g io n
W a iti n g R e g io n
R e g io n o f A lt e rn a ti v e 2
R e g io n o f A lt er n a ti ve 3
R eg i o n o f
A lte r n at iv e 1
Generator and samp ler of r an dom numbers
Pse udo- ra ndom
Q ua si Mon te Ca r lo
Stochactic Process for a Commodi ty
Ge om et ric Bro wnia n M o tion
Me an Re ve rsio n Pr oc essMe an Re ve rsio n Pr oc ess with jum p s
Fu zzy Numbers
Calculati on of th e Thresho ld Cu rve:
Algo rithm ofGrant, Vo ra and
Weeks Modi fied for F uzzy Numbers
M onte Carlo S imulatio n
to Deter mine theReal Op tion Value
(Fuzzy Numbe r )
Real Op tion Valu e
( Fuz zy Me an )
M arket Uncertaint y
Technical Uncertainty
Generator and samp ler of r an dom numbers
Pse udo- ra ndom
Q ua si Mon te Ca r lo
Stochactic Process for a Commodi ty
Ge om et ric Bro wnia n M o tion
Me an Re ve rsio n Pr oc essMe an Re ve rsio n Pr oc ess with jum p s
Stochactic Process for a Commodi ty
Ge om et ric Bro wnia n M o tion
Me an Re ve rsio n Pr oc essMe an Re ve rsio n Pr oc ess with jum p s
Fu zzy Numbers
Calculati on of th e Thresho ld Cu rve:
Algo rithm ofGrant, Vo ra and
Weeks Modi fied for F uzzy Numbers
M onte Carlo S imulatio n
to Deter mine theReal Op tion Value
(Fuzzy Numbe r )
Real Op tion Valu e
( Fuz zy Me an )
M arket Uncertaint y
Technical Uncertainty
Optimized alternatives
Decision Rule
Option value considering the value of the expansion option or investment in information
IEEE CIS-DAY (12 de abril de 2013) Computación Evolutiva, principio y aplicacionesTÚPAC, Y. (IEEE CIS Perú) Pág 21/24
Bibliografía
Bibliografía I
J. van der Hauw, “Evaluating and improving steady state evolutionaryalgorithms on constraint satisfaction problems,” Master’s thesis, ComputerScience Department of Leiden University, Leiden, Netherlands, august 1996.
A. Hoffman, Arguments on Evolution: A Paleontologist’s Perspective. NewYork: Oxford University Press, 1989.
T. Back, D. B. Fogel, and Z. Michalewicz, Eds., Handbook of EvolutionaryComputation, 1st ed. Bristol, UK, UK: IOP Publishing Ltd., 1997.
Y. J. Túpac, M. M. Vellasco, and M. A. C. Pacheco, “Selection ofalternatives for oil field development by genetic algorithms,” RevistaEngenharia Térmica, Edição Especial, vol. 2, pp. 51– 54, may 2002.
IEEE CIS-DAY (12 de abril de 2013) Computación Evolutiva, principio y aplicacionesTÚPAC, Y. (IEEE CIS Perú) Pág 22/24
Bibliografía
Bibliografía II
L. Faletti, “Otimização de alternativas para desenvolvimento de campo depetróleo usando computação evolucionária (in portuguese),” Master’s thesis,Departamento de Engenharia Elétrica, Pontifía Universidade Católica do Riode Janeiro, Rio de Janeiro, Brasil, 2003, (In Portuguese).
Y. J. Túpac, “Sistema inteligente de otimização de alternativas (inportuguese),” Ph.D. dissertation, Pontifícia Universidade Católica do Rio deJaneiro, Rio de Janeiro, RJ, Brasil, 2005, (In Portuguese).
L. F. Almeida, Y. T. Valdivia, M. M. B. R. Vellasco, and M. A. C. Pacheco,“Otimização de alternativas para o desenvolvimento de campos de petróleo,”Gestão & Produção, vol. 14, pp. 489–503, 12 2007.
R. S. Zebulum, M. A. Pacheco, and M. M. B. R. Vellasco, EvolutionaryElectronics: Automatic Design of Electronic Circuits and Systems by GeneticAlgorithms. CRC Press, 2002.
IEEE CIS-DAY (12 de abril de 2013) Computación Evolutiva, principio y aplicacionesTÚPAC, Y. (IEEE CIS Perú) Pág 23/24
Bibliografía
Bibliografía III
Y. J. Túpac and L. Faletti, “Parallel evolutionary algorithms applied tooptimize the oilfields development,” in Proceedings del Encuentro Chileno deComputación, Curicó, Chile, 2011. [Online]. Available:http://jcc2011.utalca.cl/actas/ECC/jcc2011_submission_170.pdf
Y. J. Túpac, J. G. Lazo, L. Faletti, M. M. R. Vellasco, and M. A. Pacheco,“Decision support system for economic analysis of E & P projects underuncertainties,” in 2008 SPE Intelligent Energy Conference and Exhibition.Society of Petroleum Engineers, 2008.
M. A. Pacheco and M. M. Vellasco, Eds., Intelligent Systems in Oil FieldDevelopment under Uncertainty. Springer Berlin / Heidelberg, January2009.
IEEE CIS-DAY (12 de abril de 2013) Computación Evolutiva, principio y aplicacionesTÚPAC, Y. (IEEE CIS Perú) Pág 24/24