UM ALGORITMO GENÉTICO HÍBRIDO APLICADO AO … · Otimização do Itinerário de Sondas de Produção Terrestre (SPT). Na seção 3 é descrito o Algoritmo Genético com as propostas

UM ALGORITMO GENÉTICO-2OPT APLICADO AO PROBLEMA DE OTIMIZAÇÃO DE ITINERÁRIO DE SONDAS DE PRODUÇÃO

TERRESTRE

Rômulo Ferreira Douro *FAESA

[email protected]

Luciano Lessa Lorenzoni *#FAESA - IFES

[email protected]; [email protected]

* FAESA – Unidade de Computação e SistemasRua Anselmo Serrat, 199, Ilha de Mote Belo, Vitória - ES, CEP 29040-410

# IFES - COMATAv Vitória, 1729, Jucutuquara, Vitória - ES, CEP 29040-780

RESUMO

Dentre as atividades de grande importância executadas na indústria petrolífera está a tarefa de intervir em poços de petróleo a fim de que melhorem a sua produção. Essas intervenções são realizadas por unidades móveis denominadas sondas de produção. O custo das sondas é elevado o que a torna um recurso restrito gerando uma perda considerável com a não produção dos poços que estão aguardando a realização da intervenção solicitada. O presente trabalho apresenta uma estratégia de resolução para o problema de alocação de sondas aos poços usando a heurística Algoritmo Genético combinada com a técnica de melhoramento 2-opt, visando estabelecer uma melhoria na perda de vazão dos poços através da obtenção de um itinerário otimizado para os atendimentos efetuados pelas Sondas de Produção Terrestre. Ao final da implementação foram executados testes e comparativos com outros trabalhos encontrados na literatura, cujos resultados obtidos foram superiores, indicando um bom desempenho do algoritmo.

PALAVRAS CHAVE. Metaheurísticas, Intervenção em poços, Algoritmo genético

ABSTRACT

Among the activities undertaken by the oil industry is a task to intervene in oil wells to ensure that interventions are made to improve their performance, among other goals. Such interventions are costly and there is a lack of probes that perform this type of work, operating to answer many wells. This paper presents a strategy for solving using the heuristic Genetic Algorithm combined with the 2-opt technique, hybridized with the method, to establish an improvement in the loss of water from wells by obtaining an optimal route for visits made by Echo Production land. At the end of the deployment tests were performed and compared with other studies in the literature to explain the technical points of compliance employed here.

KEYWORDS. Metaheuristics, Intervention in wells, Genetic algorithm

XLI SBPO 2009 - Pesquisa Operacional na Gestão do Conhecimento Pág. 2121

1. IntroduçãoNo âmbito das atividades tratadas pela indústria petrolífera estão inclusas as intervenções em

poços de petróleo. Essas intervenções, denominadas workover, são solicitadas de tempos em tempos, e realizadas por unidades móveis denominadas sondas de produção terrestre (SPT) com o intuito de manter o bom funcionamento dos poços.

De acordo com Accioly & Chiyoshi (2000), citado por Noronha (2001), as operações de intervenção realizadas pelas sondas são classificadas como operações de restauração, estimulação, avaliação, limpeza e completação. Uma descrição detalhada sobre o funcionamento e as operações realizadas pelas sondas de produção pode ser encontrada em Thomas (1999) e Accioly & Chiyoshi (2000).

A sonda tem custo bastante elevado, o que a torna um recurso restrito, gerando uma perda considerável com a não produção dos poços que estão aguardando a realização da intervenção solicitada. Assim surge a necessidade de se estabelecer um itinerário a ser percorrido pelas sondas a fim de efetuar o atendimento aos poços requisitantes de serviços, minimizando a perda de vazão.

A obtenção de melhores itinerários para as sondas, a fim de minimizar a perda de vazão nos poços, não é uma tarefa de fácil resolução, dada a natureza combinatorial do problema, sendo necessário, na maioria das vezes, o emprego de estratégias heurísticas para tratar este problema. Diversas estratégias têm sido utilizadas na resolução desse problema. Dentre essas destacamos: Têmpera Simulada (Paiva (1997)), Busca Tabu (Maia et al. (2002)), Algoritmo Memético e Transgenético (Gouvêa et al. (2002)), Colônia de Formigas (Aloise et al. (2002)), GRASP (Costa (2005)), Algoritmo Genético (Alves & Ferreira (2006)) e Scatter Search (Oliveira et al. (2007)).

A heurística Algoritmo Genético será abordada neste trabalho como estratégia de resolução e será aplicada em conjunto com técnicas de busca local com o intuito de gerar melhores resultados.

Este trabalho está organizado da seguinte forma: na seção 2 é formalizado o Problema de Otimização do Itinerário de Sondas de Produção Terrestre (SPT). Na seção 3 é descrito o Algoritmo Genético com as propostas de modificações implementadas, que incluem o uso de um método de melhoramento de soluções. Na seção 4 relatam-se os experimentos computacionais bem como os resultados obtidos e realiza-se uma comparação com trabalhos encontrados na literatura. Finalizando, temos na seção 5, as conclusões.

2. O Problema de Otimização de Itinerário de Sondas de Produção Terrestre – POI-SPTComo mencionado em Costa (2005, p.1), o fato de se ter muitos poços distribuídos e a

existência de poucas sondas gera a expectativa de que, freqüentemente, ocorram problemas quanto à disponibilidade de SPT’s para o atendimento aos poços de petróleo, ocasionando prejuízos de caráter financeiro uma vez que surgem as chamadas filas de atendimento o que acarreta a perda da produção dos poços.

De acordo com Aloise et al. (2002) o problema de otimização da alocação de sondas de produção consiste em encontrar a melhor seqüência de atendimento para as sondas disponíveis, visando minimizar o tempo de atendimento das solicitações e maximizar a produção média diária da bacia petrolífera, o que implica em minimizar a perda de vazão pela espera no atendimento da intervenção solicitada. A decisão de qual sonda alocar a uma determinada solicitação de serviço depende de fatores como: potencial produtivo do poço, localização geográfica da sonda em relação ao poço, tempo de intervenção no poço, questões de risco ambiental e segurança e limitação técnica das sondas em relação ao tipo de intervenção visto que a frota de sondas pode não ser homogênea. Esse problema pode ser visto como um caso especial do clássico problema dos k-servos sendo portanto classificado como um problema NP-Árduo (Goldbarg & Luna, 2000). Neste trabalho será adotada a modelagem matemática proposta por Costa (2005) para o problema em questão, onde desconsidera-se o tempo de deslocamento da sonda entre os poços e assume-se que as sondas são homogêneas, ou seja, realizam as mesmas atividades com o mesmo desempenho. Os tempos de deslocamentos foram desconsiderados dado que na região de um

Sonda 0451Sonda 1720Sonda 263S 012345678tempot


campo de produção de petróleo o deslocamento entre poços não é, em geral, um tempo significativo perto do tempo dos trabalhos nos poços (Costa, 2005).

Inicialmente, são definidos os conjuntos:N = {0..n-1} : conjunto dos n poços sujeitos à intervenção;M = {0..m-1} : conjunto das m sondas disponíveis;T = {1..hp} : conjunto dos instantes de tempo no horizonte de planejamento hp.

Em seguida associa-se a cada poço i os seguintes parâmetros:Pi : perda de vazão em (unidade de volume) / (unidade de tempo);di : a data de liberação para início dos serviços;Di : data para a finalização dos serviços; Δti : tempo de serviço.

As variáveis de decisão são designadas por iktX , sendo elas binárias, e cujo valor será 1 quando a sonda k inicia a intervenção no instante t no poço i e, assume o valor 0, caso contrário. O objetivo (1) é minimizar a perda de vazão de petróleo em função do tempo de espera para atendimento e do tempo de atendimento propriamente dito.

O modelo matemático associado ao problema pode ser formulado como segue.( ) tkii

t i kii XPdttMin ⋅⋅−∆+∑ ∑ ∑ (1)

sujeito a:NiX

t ktki ∈∀=∑ ∑ ,1 (2)

iiitki dttDTtMkNiX <<∆−∈∀∈∀∈∀= |;;,0 (3)

TtMkXt

tki ∈∀∈∀≤∑ ;,1 (4)

}|;'|;;;{,1'

ijNjttttTtMkNiXXtkjtki ≠∈∀∆+≤≤∈∀∈∀∈∀≤+ (5)

TtMkNiX tki ∈∀∈∀∈∀∈ ;;},1,0{ (6)As igualdades expressas em (2), (3) indicam respectivamente que, cada poço i deve ser

atendido uma única vez por uma única sonda e que o atendimento do poço i não ocorrerá antes do instante di nem após )( ii tD ∆− . As desigualdades expressas em (4) e (5) estabelecem, respectivamente, que cada sonda k, em cada instante de tempo, só inicia o serviço em um poço, e que, quando uma sonda k inicia os trabalhos no poço i no instante t, ela fica indisponível para iniciar outros trabalhos nos instantes t’ subseqüentes, compreendido na janela de tempo

],[ ittt ∆+ , em todos os outros locais j diferentes de i. Por fim em (6) tem-se a definição das variáveis como binárias.

As questões referentes a prioridades de atendimento, caso hajam, podem ser atendidas por meio das diferenças temporais entre di e Di.

3. Algoritmo Genético – 2opt aplicado ao problemaSegundo Lopes (2006) a estrutura de um algoritmo genético, em sua forma básica, segue os

preceitos obedecidos por operadores genéticos atuando sobre uma população de indivíduos e que fazem as funções de reprodução, ou crossover, e mutação para que se obtenha uma nova geração de indivíduos.

3.1 Representação da solução Para tratar o POI-SPT foi estabelecida uma estrutura para representar uma solução para o

problema (figura 1) onde se tem para cada sonda a sequência de poços a serem atendidos pela mesma



Figura 1 – Esquema de representação de uma solução

Tomando como exemplo a disposição de poços, como na figura 1, e dada a tabela 1 com os dados sobre perdas de vazão e tempo de alocação, pode-se ilustrar o cálculo do fitness (função objetivo) desse indivíduo como segue.

i 0 1 2 3 4 5 6 7Pi 10 1 7 15 30 2 3 1Δti 1 2 2 5 1 1 3 5

Tabela 1 – Dados de referência para exemplo do cálculo de fitness

Na figura 2 temos a codificação da solução expressa por meio de um diagrama de Gantt.

Figura 2 – Diagrama de Gantt representando o tempo gasto nos poços atendidos

Assim o fitness, para o exemplo acima, é calculado da seguinte forma: fitness = (30*1) + (2*2) + (1*4) + (1*5) + (7*7) + (10*8) + (3*3) + (15*8) = 301.

3.2 Geração da população inicialPara a geração dos indivíduos da população inicial foi implementado um método heurístico.

Tal método é baseado na Heurística Máxima Prioridade Tricritério - HMPT elaborada por Costa (2005). Nesse método os poços com maior perda de vazão são alocados primeiro, como segue.

a) ordenam-se os índices que indicam cada poço de acordo com a maior perda de vazão, fazendo com que os índices dos poços com maior perda de vazão fiquem no início;

b) a partir dos índices ordenados, os mesmos são inseridos seqüencialmente nos vetores que representam cada sonda, de forma com que os que possuem maior perda sempre fiquem à frente.

A figura 3 exemplifica o método de construção da solução com base nos dados fornecidos na tabela 1.

Figura 3 – Exemplo de criação da solução-matriz

Assim, tem-se uma primeira solução a qual é aqui chamada de solução-matriz e que é o primeiro indivíduo inserido na nova população que está sendo criada. Essa solução-matriz é então recombinada com ela mesma (cruzamento assexuado) por meio da execução do operador single-

Poços atendidosSonda 0 { 4 , 5 , 1 }Sonda 1 { 7 , 2 , 0 }Sonda 2 { 6 , 3 }


Vetor índice de poços – ordenado por maior perda

{ 4 , 5 , 1 , 7 , 2 , 0 , 5 , 6 , 3 }

1º PassoSonda 0 { 4 }Sonda 1 { }Sonda 2 { }

2º PassoSonda 0 { 4 }Sonda 1 { 5 }Sonda 2 { }

3º PassoSonda 0 { 4 }Sonda 1 { 5 }Sonda 2 { 1 }

4º PassoSonda 0 { 4 , 7 }Sonda 1 { 5 }Sonda 2 { 1 }

5º PassoSonda 0 { 4 , 7 }Sonda 1 { 5 , 2 }Sonda 2 { 1 }

6º PassoSonda 0 { 4 , 7 }Sonda 1 { 5 , 2 }Sonda 2 { 1 , 0 }

7º PassoSonda 0 { 4 , 7 , 6 }Sonda 1 { 5 , 2 }Sonda 2 { 1 , 0 }

8º Passo - FinalSonda 0 { 4 , 7 , 6 }Sonda 1 { 5 , 2 , 3 }Sonda 2 { 1 , 0 }


point adaptado, descrito em 3.3.1. Os elementos gerados, desde que não tenham sido anteriormente gerados, são inseridos na população.

O processo de geração de indivíduos por mutação é repetido até que a população esteja totalmente preenchida com, no caso deste algoritmo, 50 indivíduos gerados (a solução-matriz e mais 49 mutações sobre a mesma).

3.3 As operações genéticas3.3.1 Cruzamento

Para a operação de cruzamento é usado o operador single-point crossover mostrado por Lobo (2005), o qual é usado em sua forma original e em uma formatação adaptada. Os métodos de cruzamento são executados por sorteio tendo 50% de chances de execução para cada método.

O processo de cruzamento single-point é aplicado sonda a sonda e nele, após a definição de um ponto de cruzamento aleatório, a parte final das seqüências de poços das sondas do primeiro pai é trocada com a parte final das referentes seqüências de poços das sondas do segundo pai, repetindo o processo do segundo para o primeiro pai e, conseqüentemente, gerando duas novas seqüências a serem usadas nos dois novos filhos. Na figura 4 está exemplificado este método.

Figura 4 – Exemplo de execução do cruzamento single-point

O single-point adaptado é efetuado, também, após a definição do ponto de cruzamento onde, para cada seqüência de sondas é feita a troca entre a parte final da seqüência do primeiro pai e a parte inicial da seqüência do segundo pai repetindo o processo trocando a parte final da seqüência do segundo pai e a parte inicial da seqüência do primeiro pai, gerando assim duas novas seqüências que serão usadas uma em cada novo indivíduo filho. Esse método é ilustrado na figura 5.

Figura 5 – Exemplo de execução do cruzamento single-point adaptado

Tanto nos processos de cruzamento quanto nos de mutação, ao executar a inserção de um índice em determinada posição, outro índice deve ser retirado e inserido na posição, seja ela em qualquer sonda, que era ocupada pelo índice recém inserido. Por exemplo, tomemos uma situação hipotética: o índice 5, que inicialmente está alocado na posição 3 da sonda 2, é inserido na

Pais escolhidosP1 = [VetorSonda_0,

VetorSonda_1, ..., VetorSonda_N]

P2 = [VetorSonda_0, VetorSonda_1, ...,

VetorSonda_N]

Para todos os vetores de sondas executa-se a seqüência de passos

VetorSonda_iVetor em P1 = { 3 , 4 , 2 , 1 , 5 , 0 }Vetor em P2 = { 2 , 1 , 0 , 5 , 4 , 3 }

Ponto de cruzamento definido

{ 3 , 4 , 2 , 1 , 5 , 0 }

{ 2 , 1 , 0 , 5 , 4 , 3 }

VetorSonda_i do 1º Filho (P1 em P2) Insere 5 { 2 , 1 , 0 , 5 , 5 , 3 } - 4 Troca 4 { 2 , 1 , 0 , 4 , 5 , 3 } Insere 0 { 2 , 1 , 0 , 4 , 5 , 0 } - 3 Troca 3 { 2 , 1 , 3 , 4 , 5 , 0 }


Pais escolhidosP1 = [VetorSonda_0,

VetorSonda_1, ..., VetorSonda_N]

P2 = [VetorSonda_0, VetorSonda_1, ...,

VetorSonda_N]

Para todos os vetores de sondas executa-se a seqüência de passos

VetorSonda_iVetor em P1 = { 3 , 4 , 2 , 1 , 5 , 0 }Vetor em P2 = { 2 , 1 , 0 , 5 , 4 , 3 }

Ponto de cruzamento definido{ 3 , 4 , 2 , 1 , 5 , 0 }{ 2 , 1 , 0 , 5 , 4 , 3 }Processo de

cruzamento

{ 3 , 4 , 2 , 1 , 5 , 0 }

{ 2 , 1 , 0 , 5 , 4 , 3 }




posição 0 da sonda 0 a qual é ocupada pelo índice 2. Neste momento o índice 2 é retirado de sua posição original e é inserido na posição original do índice 5 (posição 3 da sonda 2), com essa troca evita-se que algum poço apareça mais de uma vez no sistema Sondas X Poços.

Ao final do processo de cruzamento são gerados dois novos indivíduos filhos que, por sorteio, com uma probabilidade de 1%, podem ser submetidos ao processo de mutação, assim pode haver a criação de dois ou quatro descendentes, os quais são avaliados e somente serão incluídos na população caso seu fitness seja melhor do que, pelo menos, um indivíduo pai.

3.3.2 MutaçãoPara a mutação foram definidos três operadores sendo que em um deles é aplicado o

cruzamento assexuado onde é usado o método single-point adaptado, descrito anteriormente, a mutação por inversão e a mutação aleatória descritos a seguir.

Mutação por inversãoNa mutação por inversão, que é baseada no operador SIM (Simple Inversion Mutation)

proposto por Holland (1975), uma parte central de cada seqüência de cada sonda em um indivíduo é selecionada e então invertida simetricamente em relação ao centro da seqüência, trocando o primeiro elemento da parte selecionada com o último, o segundo com o penúltimo e assim por diante até que o centro da seqüência seja alcançado. A mutação por inversão é exemplificada como na figura 6.

Figura 6 – Exemplo de mutação por inversão

Mutação aleatóriaNo caso da mutação aleatória tem-se a seguinte situação:a) define-se uma quantidade inicial de, no máximo, 10% do tamanho da seqüência de poços

em uma sonda;b) sorteia-se uma posição aleatória que será usada como base para a escolha do poço a ser

trocado;c) para cada sonda é sorteada mais uma posição aleatória e trocam-se os índices dessa

posição com a posição sorteada para troca na mesma sonda;d) repete-se o passo anterior até que seja atingida a contagem de mutações estipulada.

Assim, tendo três métodos de mutação, foi definido o seu uso por sorteio, através do mecanismo conhecido como roleta, da seguinte forma: para a mutação por inversão é atribuída uma probabilidade de 50% de ser executada, a mutação por cruzamento assexuado, usando o single-point adaptado, possui uma probabilidade de 40%, em 5% é atribuída a probabilidade de usar uma combinação onde primeiro é aplicada a mutação por inversão e, em seguida, o cruzamento assexuado e, por fim, em 5% há a probabilidade de ser executado o método de mutação aleatório.

3.4 Método de melhoramento de soluçõesFoi usada uma técnica, aqui chamada de melhor troca, adaptada da heurística 2-opt que

segundo Goldbarg e Luna (2000) é descrita na literatura como uma estratégia de melhoria partindo de um ciclo hamiltoniano. Nessa adaptação são feitas trocas de posições entre os índices

Processo de inversão

Seleciona { 3 , 7 , 8 , 1 , 4 } { 5 , 9 , 0 , 2 }

Troca { 3 , 1 , 8 , 7 , 4 } { 5 , 2 , 0 , 9 }

Situação inicial{ 3 , 7 , 8 , 1 , 4 }{ 5 , 9 , 0 , 2 }

Pontos para inversão{ 3 , 7 , 8 , 1 , 4 }{ 5 , 9 , 0 , 2 }

Situação final{ 3 , 1 , 8 , 7 , 4 }{ 5 , 2 , 0 , 9 }


do conjunto Sondas X Poços, e essa troca pode ser feita em qualquer posição de qualquer sonda. Dessa forma a elaboração do método segue os seguintes passos:

a) seleciona-se o primeiro índice do conjunto de sondas X poços;b) do índice posterior ao selecionado até o último índice são feitas trocas de posição entre

eles e armazena-se o valor do custo para o novo conjunto elaborado, caso esse seja menor que o atual a posição de troca é então guardada como a melhor posição de troca e atualiza-se o valor do custo para comparação;

c) ao final, caso seja estabelecida uma posição de troca eficiente, a troca é então efetuada e o algoritmo é repetido para próximo índice do conjunto conforme a letra (a) até que seja atingido o final do conjunto de Sondas X Poços.

Para a definição de seqüência de índices aqui descrita deve-se fazer a seguinte consideração conforme a figura 7:

a) o primeiro índice de um conjunto Sondas X Poços é o primeiro índice da seqüência que representa a ordem de execução para a primeira sonda;

b) o segundo índice de um conjunto Sondas X Poços é o primeiro índice da seqüência que representa a ordem de execução para a segunda sonda;

c) os índices posteriores seguem a mesma ordem levando em consideração que, ao ser atingido o final do número de sondas o próximo índice a ser escolhido será o referente à próxima posição na seqüência da primeira sonda sendo depois contados os índices para cada sonda posterior conforme a figura 7.

Sonda 0 {Índice 0, Índice N+1, ...}Sonda 0 {Índice 1, Índice N+2, ...}...Sonda N {Índice N, ...}

Figura 7 – Disposição dos índices dos poços no sistema Sondas X Poços

A figura 8 esquematiza o método de melhoramento descrito.

Figura 8 – Esquema de execução do método de melhor troca

A figura 9 esboça um exemplo básico de como a técnica melhor troca é usada. Tomando como base as primeiras comparações feitas no sistema de Sondas X Poços numa situação em que se têm três sondas aplicadas a um conjunto de dez poços.

Armazena posição como melhor troca e atualiza o

valor de fitness

INÍCIOAtualiza a posição de melhor

troca e o valor do fitness

Seleciona o próximo índice

FIM

SIM

Chegou ao final do conjunto Sondas X

Poços?

Seleciona índice posterior

Chegou ao final do conjunto Sondas X

Poços?

Testa a troca de posições entre os

índices

NÃO

Melhorou o fitness ?

SIM

Efetua a melhor troca com base na posição armazenada após os

testes da iteração

SIM

NÃO


Figura 9 – Exemplo básico de execução da melhor troca

Assim, a figura 10 sintetiza o Algoritmo Genético-2opt (AG-2opt) implementado neste trabalho. O critério de parada adotado estabelece que o algoritmo é encerrado, após 12 iterações sem a alteração do melhor indivíduo da população o algoritmo ou quando atingir 2000 iterações.

Figura 10 – Esquema de execução do AG-2opt

4. Experimentos computacionaisNa implementação do algoritmo foi adotada a linguagem de programação JAVA e os testes

executados em um computador com processador Pentium IV, 2 GHz com 480 MB de RAM.Os experimentos foram realizados com a massa de dados gerada e disponibilizada por Costa

(2005). Essa massa de dados possui instâncias com 25, 50, 75, 100 e 125 poços e 1, 2, 4, 6, 8 e 10 sondas, sendo que para cada grupo de poços foram gerados 10 exemplos, designados de A até J, o que totaliza 300 instâncias. As instâncias foram nomeadas da seguinte forma: PNEx-S onde N corresponde ao número de poços, S ao número de sondas e Ex ao conjunto de exemplos. Assim, P75A-4 corresponde a uma instância do problema A com 75 poços e 4 sondas.

As heurísticas com as quais o algoritmo AG-2opt foi comparado são, a Heurística de Máxima Prioridade Tricritério (HMPT), a Heurística de Montagem Dinâmica (HMD) e o Grasp propostas por Costa (2005) e o Algoritmo Genético proposto Alves e Ferreira (2006), designado neste trabalho por AG, pois são as que utilizam a mesma base de dados. A HMTP e a HMD foram resolvidas usando 3 critérios diferentes para a alocação de um novo poço nas sondas, são eles: critéiro 1 – menor valor da vazão perdida (Pi), critério 2 – menor valor de Pi/∆ti e critério 3 – menor valor de Pi*∆ti.

Inicialmente, foram escolhidas 25 instâncias do exemplo A para os grupos de 25, 50, 75, 100 e 125 poços e 2, 4, 6,8 e 10 sondas para a calibração do algoritmo. Os resultados obtidos são apresentados na tabela 2 onde na coluna Melhor Heurística temos o melhor resultado obtido por Costa (2005) dentre todas as heurísticas implementadas em seu trabalho, na coluna AG-2opt os resultados obtidos pelo algoritmo desenvolvido no presente trabalho (sendo este resultado a média das cinco execuções para cada instância escolhida.) e a coluna Grasp indica os resultados obtidos por Costa (2005) para a referida técnica. Observa-se que o AG-2opt obteve melhores resultados que o Grasp para todas as instâncias testadas e também quando comparados com a Melhor Heurística, exceto para uma instância (P25A-8).

Situação inicial Primeira comparação Segunda comparação0 3 6 91 4 72 5 8

Sonda0 Sonda1 Sonda2

1 3 6 90 4 72 5 8


2 3 6 91 4 70 5 8


Terceira comparação3 0 6 91 4 72 5 8


Última comparação9 3 6 01 4 72 5 8


Efetua melhor troca7 3 6 91 4 02 5 8


Aplica mutação coletiva

INÍCIOPopulação inicial gerada

Executou o número máximo de iterações?

FIM

SIM

Executou máximo de operações sem alterar o

melhor?

Ordena população (50 indivíduos)

Efetua evolução(Reproduções e Mutações)

Executa heurística de melhoramento 2-opt

Passou período determinado sem alterar o melhor? SIMNÃO

SIM

NÃO

NÃO


Instância Melhor heurística

AG-2opt GraspCusto Tempo Custo Tempo

P25A-2 16421 16329 0:00:04 17737 0:01:24P25A-4 10348 10312 0:00:05 10825 0:01:28P25A-6 8555 8499 0:00:02 8897 0:01:28P25A-8 7735 7736 0:00:01 7939 0:01:27P25A-10 7329 7325 0:00:01 7470 0:01:29P50A-2 66920 66907 0:00:14 81986 0:19:36P50A-4 37936 37896 0:00:15 43451 0:20:24P50A-6 28485 28353 0:00:05 33635 0:19:03P50A-8 23839 23788 0:00:16 26910 0:20:00P50A-10 21409 21351 0:00:10 23770 0:20:07P75A-2 187358 187240 0:00:36 239459 1:23:50P75A-4 103364 103218 0:00:27 137715 1:13:55P75A-6 75871 75524 0:00:25 97572 1:30:44P75A-8 62179 61916 0:00:18 78165 1:22:44P75A-10 54099 53889 0:00:29 66270 1:26:01P100A-2 299093 299051 0:01:01 405969 3:09:37P100A-4 160016 159983 0:00:48 209626 2:59:46P100A-6 114456 114275 0:02:16 148148 2:59:45P100A-8 91954 91769 0:02:21 115852 3:05:01P100A-10 78541 78402 0:00:58 96243 3:01:58P125A-2 380631 380523 0:02:26 534998 5:38:07P125A-4 200408 200368 0:01:00 265171 5:37:12P125A-6 140648 140550 0:01:24 188746 5:34:10P125A-8 111015 110844 0:01:06 145440 5:37:49P125A-10 93280 93078 0:02:44 122438 5:48:08

Tabela 2 – Resultados dos testes para o grupo A (exceto uma sonda)

A figura 11 destaca as diferenças percentuais obtidas com a execução do AG-2opt em comparação a Melhor Heurística proveniente do trabalho de Costa (2005). Na comparação também foram incluídas as instâncias com apenas uma sonda.

P25

A-1

P25

A-2

P25

A-4

P25

A-6

P25

A-8

P25

A-1

0P

50A

-1P

50A

-2P

50A

-4P

50A

-6P

50A

-8P

50A

-10

P75

A-1

P75

A-2

P75

A-4

P75

A-6

P75

A-8

P75

A-1

0P

100A

-1P

100A

-2P

100A

-4P

100A

-6P

100A

-8P

100A

-10

P12

5A-1

P12

5A-2

P12

5A-4

P12

5A-6

P12

5A-8

P12

5A-1

0

-0,80%-0,70%-0,60%-0,50%-0,40%-0,30%-0,20%-0,10%0,00%0,10%

Instâncias

Dife

renç

a

Figura 11 – Diferenças percentuais – AG-2opt X Melhor heurística

A seguir os resultados obtidos por AG-2opt e AG foram comparados com os resultados ótimos, encontrados por Costa (2005) utilizando o solver CPLEX 9.0, para as 60 instâncias com


25 poços. O histograma da figura 12 mostra os gaps do AG-2opt e do AG em relação aos resultados obtidos pelo CPLEX 9.0. O gap é calculado da seguinte forma gap (%) = (resultado AG-2opt (ou AG) – resultado CPLEX)*100 / resultado CPLEX. Nesse histograma observa-se uma equiparação entre os resultados obtidos para as duas implementações com ligeira vantagem para o AG-2opt. Há que se ressaltar que os resultados são bastante satisfatórios já que o gap máximo para o AG-2opt não ultrapassa a 0,4%, enquanto para o AG chega em 0,6 % e para as melhores heurísticas apresentadas por Costa (2005) chega a 1,79 %.

55

3 1 1 0 0 0

54

2 3 0 0 1 00

102030405060

0,0

-0,

1 %

0,1

-0,

2 %

0,2

-0,

3 %

0,3

-0,

4 %

0,4

-0,

5 %

0,5

-0,

6 %

0,6

+%

AG-2opt AG

Figura 12 – Histograma comparativo do gap (%) em relação ao CPLEX 9.0

A seguir, foram realizados testes com todas as outras instâncias artificiais ainda não testadas. Na tabela 3 tem-se a média de iterações em cada grupo de poços para atingir a solução do problema, além do tempo médio de execução para obter essa solução.

25 Poços 50 Poços 75 Poços 100 Poços 125 PoçosMax. Iterações 39 57 78 79 103Iterações 17 24 35 37 39Tempo (s) 2 9 34 71 133

Tabela 3 – Médias de iterações e tempos de execução

Na tabela 4 encontra-se um resumo dos resultados obtidos, considerando vitória quando o algoritmo implementado encontra um resultado menor ou igual ao melhor resultado obtido por Costa(2005). Observa-se desempenho bastante superior do AG-2opt em relação às heurísticas implementadas por Costa (2005).

HMPT1 HMPT2 HMPT3 HMD1 HMD2 HMD3 AG-2opt25 poços 1 10 0 12 10 11 57

2% 17% 0% 20% 17% 18% 95%Exclusiva 0 0 0 1 0 1 4750 poços 0 10 0 9 10 9 60

0% 17% 0% 15% 17% 15% 100%Exclusiva 0 0 0 0 0 0 5075 poços 0 12 0 10 12 10 58

0% 20% 0% 17% 20% 17% 97%Exclusiva 0 0 0 0 0 0 48100 poços 0 10 0 10 10 10 60

0% 17% 0% 17% 17% 17% 100%Exclusiva 0 0 0 0 0 0 50125 poços 0 10 0 10 10 10 60

0% 17% 0% 17% 17% 17% 100%Exclusiva 0 0 0 0 0 0 50

Total 1 52 0 51 52 50 295 0% 17% 0% 17% 17% 17% 98%

Exclusiva 0 0 0 1 0 1 245Tabela 4 – Resumo das vitórias e vitórias exclusivas para todas as instâncias testadas

Na tabela 5 encontra-se um resumo do número de vitórias obtido pelo AG-2opt e pelo AG em relação aos resultados apresentados por Costa (2005). Ressalta-se que, no momento, não é possível uma comparação direta entre AG-2opt e AG pois em Alves e Ferreira (2006) não foram


apresentados os resultados obtidos para cada instância e sim um quadro resumo com as vitórias obtidas.

AG-2opt AG25 poços 95 % 83 %50 poços 100 % 77 %75 poços 97 % 68 %100 poços 100 % 45 %125 poços 100 % 22 %

Tabela 5 – Resumo das vitórias do AG-2opt e do AG

Nota-se um desempenho superior do AG-2opt em relação ao AG para todos os grupos de poços, em especial, para problemas de maior porte (com mais poços). Observa-se também que o desempenho do AG-2opt não se deteriora à medida que se aumenta o número de poços, ao contrário do AG, o que demonstra a robustez do AG-2opt.

Vale salientar que o AG foi executado numa máquina inferior (800 MHz Pentium III com 512 MB de RAM) ao que o AG-2opt foi executado. As instâncias dos grupos 100 e 125 foram resolvidas na média, respectivamente, em 97 e 122 segundos, para o AG, e 71 e 133 segundos para o AG-2opt, o que não desmerece a eficiência do algoritmo implementado, especialmente para instâncias com muitos poços. É interessante notar também que, o AG gera e avalia muito mais indivíduos, em torno de 24000, para instâncias com 100 e 125 poços, enquanto o AG-2opt, não ultrapassa a 8000 indivíduos, o que indica a eficiência das operações genéticas e do método de melhoramento implementados neste trabalho. Como trabalho futuro prevê-se a implementação do algoritmo genético proposto por Alves e Ferreira (2006) para que a comparação seja feita de forma ainda mais apurada.

5. ConclusõesEste trabalho mostrou a eficiência do uso da técnica Algoritmo Genético em conjunto com

outras técnicas, como a heurística 2-opt, possibilitando sua hibridização e a empregando ao POI-SPT. Pôde-se perceber a importância que há na combinação de métodos heurísticos para a obtenção de bons resultados. Em particular, a inclusão da heurística 2-opt, como método de aprimoramento de soluções, melhorou consideravelmente a qualidade das soluções obtidas no decorrer do trabalho. Há que se ressaltar a importância do uso de um método gerador de soluções iniciais derivado da HMPT, o qual foi empregado como estratégia para obter um melhoramento prévio das soluções tratadas pelo algoritmo, o que favoreceu a constituição de soluções de boa qualidade já no início da execução.

Ao se fazer comparações, com outros métodos, usando as instâncias artificiais do trabalho de Costa (2005) os resultados mostraram-se promissores dado que à medida que o número de poços aumenta a qualidade das soluções não diminui. Não obstante, novos tratamentos podem ser feitos no contexto da escolha da melhor opção dentre os diferentes tipos de operadores genéticos além dos critérios de parada e probabilidades de mutação e cruzamento, sendo interessante, ao final, observar o comportamento do AG-2opt quando o mesmo fosse empregado em um ambiente paralelizado.

6. Referências.Accioly, R. & Chiyoshi, Y. Modelando as operações de suas sondas de petróleo utilizadas na manutenção da produção. Editora Petrobrás, 2000.Aloise, D. et al., Heurísticas de colônia de formigas com path-relinking para o problema de otimização da alocação de sondas de produção terrestre – SPT, Atas do XXXIV SBPO, 2002.Alves, V. R. F. M.; Ferreira, V. J. M. Proposta de algoritmo genético para a solução do problema de roteamento e seqüenciamento de sondas de manutenção, Atas do XXXVIII SBPO, 2006.Costa, L. R. da, Soluções para o problema de otimização de itinerário de sondas, Tese de mestrado, UFRJ, Rio de Janeiro, 2005.


Goldbarg, M. C. e Luna, H. P. L., Otimização combinatória e programação linear: modelos e algoritmos, Campus, Rio de Janeiro, 2000.Gouvêa, E. F.; Goldbarg, M. C.; Costa, W. E., Algoritmos evolucionários na solução do problema de otimização do emprego de sondas de produção em poços de petróleo, Atas do XXXIV SBPO, 2002.Holland, J. H., Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence, University of Michigan Press, 1975.Lobo, E. L. M., Uma solução do problema de horário escolar via algoritmo genético. Tese de mestrado, CEFET-MG, 2005 (http://www.mmc.cefetmg.br/info/downloads/D006-EduardoLuizMirandaLobo2005.pdf), 9, 2008.Lopes, H. S., Fundamentos de computação evolucionária e aplicações, XIII Escola Regional de Informática da SBC - Paraná, Bandeirantes: FFALM/SBC, Paraná, 52-107, 2006.Maia, R. S.; Gonzaga, C. M.; Lima, F. C. & Bittencourt, V.G. Otimização das intervenções em poços de petróleo por sondas de produção terrestre: Busca Tabu. Atas do XXXIV SBPO, 2002.Noronha, T. F., Algoritmos e estratégias de solução para o problema de gerenciamento de sondas de produção terrestre na bacia petrolífera potiguar, Revista eletrônica de iniciação científica, a. 1, v. 1, n. 2, SBC, 11, 2001 (https://www.sbc.org.br/reic/edicoes/2001e2/), 5, 2008.Oliveira, E. F.; Pagoto, F. B.; Silva, F. T.; Lorenzoni, L. L., Scatter search aplicado ao problema de otimização da alocação de sondas de produção em poços de petróleo, Atas do XXVII ENEGEP, 2007.Paiva, R.O. Otimização do itinerário de Sondas de intervenção com quantificação de perdas através de simuladores de reservatórios. Dissertação de Mestrado - Unicamp, Campinas, SP, Brasil, 1997.Thomas, J. E. Fundamentos de Engenharia de Petróleo. Editora Interciência. Rio de Janeiro, 1999.Trindade, V. de A., Desenvolvimento e análise experimental da metaheurística GRASP para um problema de planejamento de sondas de manutenção, Tese de mestrado, Universidade Federal Fluminense, 2005 (http://www.ic.uff.br/PosGraduacao/Dissertacoes/273.pdf), 9, 2008.


Documents

UM ALGORITMO GENÉTICO HÍBRIDO APLICADO AO … · Otimização do Itinerário de Sondas de Produção Terrestre (SPT). Na seção 3 é descrito o Algoritmo Genético com as propostas