Embed Size (px)
Citation preview
UNIVERSIDADE FEDERAL DA PARAÍBA CENTRO DE CIÊNCIAS E TECNOLOGIA
COORDENAÇÃO DE PÓS-GRADUAÇÃO EM INFORMÁTICA
Um Algoritmo Genético para Otimização do Controle de Redes de Escoamento de Petróleo
Esther Vilar Brasileiro
Dissertação de Mestrado submetida à Coor-
denação do Curso de Pós-Graduação em Ci-
ência da Computação da Universidade Fede-
ral de Campina Grande como parte dos re-
quisitos necessários para obtenção do grau de
Mestre em Ciência da Computação.
Área de Concentração: Ciência da Computação Linha de Pesquisa: Redes de Computadores e Sistemas Distribuídos
Carlos de Oliveira Galvão, Dr. Orientador
Francisco V. Brasileiro, Dr.
Orientador
Campina Grande - Paraíba ©Esther Vilar Brasileiro, Fevereiro de 2005
ii
Resumo
O controle em tempo real de redes de tubulações, complexas e de grande escala,
para escoamento da produção de petróleo é complicado por vários fatores, entre eles: (a) a
confiabilidade dos sistemas de aquisição de dados e comunicação, (b) tempos limites entre
a aquisição de dados e a decisão de controle, (c) restrições operacionais de um grande nú-
mero de dispositivos, (d) controle multi-objetivo, envolvendo objetivos e restrições eco-
nômicas, operacionais, ambientais e institucionais. Neste trabalho propomos um Algoritmo
Genético (AG) para solucionar o problema do controle em tempo real de redes de escoa-
mento complexas. Centrado no sistema de bombeamento, o algoritmo de otimização ex-
posto utiliza conhecimento especialista do problema para reduzir o tempo de busca e me-
lhorar a qualidade da solução utilizando uma infra-estrutura de grade computacional. Os
objetivos do controle são a redução do custo com o consumo de energia e dos riscos ao
meio ambiente, mantendo os níveis de produção e segurança. Os operadores genéticos de
cruzamento e mutação foram modificados para prevenir convergência prematura e acelerar
a busca em regiões mais promissoras do espaço-solução, dando à tradicional ‘cegueira’ dos
operadores genéticos a direção para gerar melhores descendentes. A técnica de seeding foi
utilizada para garantir uma solução viável dentro do prazo. O AG apresenta uma função de
adaptabilidade ponderada no tempo. Esta função minimiza as possíveis perdas que se pos-
sa ter devido às incertezas presentes na previsão da produção. Os resultados mostram que o
AG encontra soluções mais econômicas que os procedimentos ad hoc de operação da rede,
com uma redução média de 5,45% do custo. Além disso, verificamos que um ganho médio
adicional de 16,92% pode ser alcançado com o aumento dos recursos computacionais dis-
poníveis.
iii
Abstract
Real-time control of complex and large-scale oil pipeline networks is complicated by sev-
eral reasons, among them (a) reliability of data acquisition and communication systems,
(b) strict time limits between data acquisition and decision of control action, (c) opera-
tional constraints of a large number of pipeline devices, such as tanks, pumps, valves and
pipes, (d) multi-objective control, involving economic, operational, environmental and
institutional objectives and constraints. In this work we propose a Genetic Algorithm (GA)
to solve the problem of optimizing the control of complex pipeline networks in real time.
Centered in the pumping system, the optimization algorithm uses domain based knowledge
to reduce the search time and to improve the quality of the solution. The control objectives
are reduction of costs with consumption of energy and risks to the environment, at the
same time that production and the operational security levels are maintained. Standard GA
crossover and mutation operators were modified to prevent early convergence and to speed
up search in promising search space areas, giving to the traditional ‘blindness’ of the ge-
netic operators an insight of the best way to apply them in order to generate better descen-
dents. Seeding was used to overcome the problem of delivering a suitable solution on time.
The GA introduces an evaluation function weighted over time. This function minimizes
the possible loss that one may have due to uncertainty of the production forecast over time.
The results showed that the GA provides better solutions than ad hoc procedures for pipe-
line network operation. Our experiments have shown an average reduction on cost of
5,45%. Moreover, we verified that additional gains (16,92% in our experiments) can be
achieve increasing the amount of computational resources available.
iv
Agradecimentos
Aos meus orientadores, Prof. Carlos de Oliveira Galvão e Prof. Francisco Vilar Brasileiro
por tudo que aprendi e pela orientação.
Aos meus amigos do laboratório de sistemas distribuídos, em especial a Daniel Paranhos,
Lívia, Randolph, Raquel e Zane, pelo apoio, suporte técnico e o bate-papo gostoso durante
nossos breaks .
À equipe do projeto SmartPumping, em especial a Bruno, Cledson, Érica e Mônica, pela
modelagem e desenvolvimento do modelo de simulação hidráulico, pelo interesse e dispo-
nibilidade em ajudar e pelas preciosas discussões que muito enriqueceram este trabalho.
Aos funcionários do LSD e da COPIN, por todos os serviços prestados.
À minha família e a Andrey, pela paciência nos momentos difíceis.
v
Conteúdo
1 INTRODUÇÃO___________________________________________ 1
2 FORMALIZAÇÃO DO PROBLEMA __________________________ 4
2.1 Visão geral do domínio do problema __________________________________________ 4
2.2 Objetivo do controle _______________________________________________________ 8
2.3 Simulação do custo da energia _______________________________________________ 8
2.4 Modelo de simulação hidráulico_____________________________________________ 13
2.5 Restrições _______________________________________________________________ 19
2.6 Estudo de caso ___________________________________________________________ 21
3 REVISÃO BIBLIOGRÁFICA _______________________________ 28
4 ALGORITMOS GENÉTICOS ______________________________ 32
4.1 Estrutura do Algoritmo Genético____________________________________________ 32
4.2 Codificação da solução ____________________________________________________ 34
4.3 Geração da população inicial _______________________________________________ 35
4.4 Cálculo da aptidão________________________________________________________ 36
4.5 Seleção _________________________________________________________________ 37
4.6 Operadores de reprodução _________________________________________________ 40
4.7 Parâmetros de controle do algoritmo_________________________________________ 41
4.8 Estratégia de reposição ____________________________________________________ 42
4.9 Critérios de parada _______________________________________________________ 43
4.10 Princípios e funcionamento ______________________________________________ 44
5 ADAPTANDO O ALGORITMO GENÉTICO ___________________ 45
5.1 Codificação do problema __________________________________________________ 45
5.2 Função de aptidão ________________________________________________________ 46
5.3 Tamanho da população____________________________________________________ 48
vi
5.4 Algoritmo Genético canônico _______________________________________________ 50
5.5 Tratando as restrições do problema__________________________________________ 52 5.5.1 Função de penalidade__________________________________________________ 52 5.5.2 Eliminação de soluções ________________________________________________ 54 5.5.3 Operadores genéticos modificados________________________________________ 55
5.6 Garantido resultados dentro do prazo com o seeding ___________________________ 57
5.7 Parâmetros de controle ____________________________________________________ 60
5.8 Testando o AG para diferentes padrões de produção ___________________________ 62
6 CONCLUSÕES E TRABALHOS FUTUROS __________________ 70
6.1 Novos objetivos a serem otimizados__________________________________________ 71
6.2 Tratamento de inviabilidades _______________________________________________ 71
6.3 Hibridização_____________________________________________________________ 72
REFERÊNCIAS BIBLIOGRÁFICAS ____________________________ 73
vii
Lista de Tabelas TABELA 1 - GRUPOS DE CONSUMO DE ALTA TENSÃO........................................................................................ 12 TABELA 2 - EXEMPLO DE TARIFA HORO-SAZONAL AZUL .................................................................................. 13 TABELA 3 - CARACTERÍSTICAS FÍSICAS E DE OPERAÇÃO DOS TANQUES............................................................ 22 TABELA 4 - CARACTERÍSTICAS FÍSICAS DOS DUTOS ......................................................................................... 23 TABELA 5 - LIMITES DE OPERAÇÃO DOS DUTOS................................................................................................ 23 TABELA 6 - CARACTERÍSTICAS FÍSICAS DAS BOMBAS....................................................................................... 23 TABELA 7 - QUADRO DE TARIFAS ELÉTRICAS ................................................................................................... 24 TABELA 8 - CONDIÇÕES INICIAIS DO SISTEMA .................................................................................................. 25 TABELA 9 - CARACTERÍSTICA DO FLUIDO NAS ESTAÇÕES................................................................................. 25 TABELA 10 - PREVISÃO DE ENTRADA (DA PRODUÇÃO) E SAÍDA DAS ESTAÇÕES................................................ 26 TABELA 11 - VISCOSIDADE CINEMÁTICA DO FLUIDO........................................................................................ 26 TABELA 12 - BSW DO FLUIDO.......................................................................................................................... 26 TABELA 13 - TEMPERATURA DO FLUIDO .......................................................................................................... 26 TABELA 14 - MASSA ESPECÍFICA DO FLUIDO .................................................................................................... 27 TABELA 15 - DADOS DE APTIDÃO DE UM PROBLEMA HIPOTÉTICO .................................................................... 39 TABELA 16- PARÂMETROS DE CONTROLE ........................................................................................................ 51 TABELA 17 - RESTRIÇÕES E GRAU DE SEVERIDADE .......................................................................................... 53 TABELA 18 - ESTRATÉGIA PARA REPARO DE SOLUÇÃO..................................................................................... 59 TABELA 19 - PARÂMETROS DE CONTROLE........................................................................................................ 61 TABELA 20 - CARACTERÍSTICAS DA PRODUÇÃO ............................................................................................... 62 TABELA 21 - RESULTADOS DA OTIMIZAÇÃO..................................................................................................... 66
viii
Lista de Figuras FIGURA 1 – ESQUEMA PARCIAL DA REDE DE ESCOAMENTO DA UN-RNCE ___________________________ 4 FIGURA 2 – ESQUEMA DE REDE DE ESCOAMENTO_______________________________________________ 5 FIGURA 3 - VAZÃO ESTIMADA INICIAL PARA AS BOMBAS CENTRÍFUGAS E VOLUMÉTRICAS ______________ 15 FIGURA 4 - VAZÃO ESTIMADA INICIAL PARA AS BOMBAS ALTERNATIVAS ___________________________ 15 FIGURA 5 - GRÁFICO DO VALOR DA COMPUTAÇÃO VERSUS TEMPO ________________________________ 21 FIGURA 6 - ESQUEMA DA MALHA DE ESCOAMENTO DE TESTES____________________________________ 22 FIGURA 7 - ESTRUTURA DE UM ALGORITMO GENÉTICO _________________________________________ 33 FIGURA 8 - CODIFICAÇÃO DOS CROMOSSOMOS _______________________________________________ 35 FIGURA 9 - REPARO DE UM CROMOSSOMO ___________________________________________________ 36 FIGURA 10 - AMOSTRAGEM ESTOCÁSTICA UNIVERSAL__________________________________________ 40 FIGURA 11 - CRUZAMENTO DE CROMOSSOMOS EM UM E DOIS PONTOS______________________________ 40 FIGURA 12 - OPERADOR DE MUTAÇÃO ______________________________________________________ 41 FIGURA 13 - REPRESENTAÇÃO DE UM CROMOSSOMO ___________________________________________ 46 FIGURA 14 - DETERMINANDO O TAMANHO DA POPULAÇÃO ______________________________________ 49 FIGURA 15 - CRUZAMENTO DIRECIONADO ___________________________________________________ 56 FIGURA 16 - ALGORITMO DO CALCULADOR DE SOLUÇÃO VIÁVEL _________________________________ 58 FIGURA 17 - ALGORITMO DE OPERAÇÃO DA REDE DE ESCOAMENTO _______________________________ 64 FIGURA 18 - DESEMPENHO NO CENÁRIO I DE PRODUÇÃO ________________________________________ 67 FIGURA 19 - DESEMPENHO NO CENÁRIO II DE PRODUÇÃO _______________________________________ 68 FIGURA 20 - DESEMPENHO NO CENÁRIO III DE PRODUÇÃO_______________________________________ 68
ix
1 Introdução
A Unidade de Negócios Rio Grande do Norte - Ceará (UN-RNCE) da PETRO-
BRAS, que explora os campos de petróleo da região compreendida entre os estados do
Rio Grande do Norte e Ceará, opera atualmente uma rede de dutos de 350km, que se es-
tende por toda a região oeste até o litoral norte do estado do Rio Grande do Norte e com-
preende 95 campos de produção, onde se encontram mais de 4.500 poços perfurados e 67
estações coletoras. É a maior produção de petróleo onshore do Brasil e o bombeamento
desta produção consome bastante energia elétrica.
A busca da redução do consumo de energia em sistemas de escoamento de petró-
leo é importante e uma forma natural de se tornar mais competitiva e racional a produção
de petróleo onshore para as empresas da área que competem em escala global.
Sem fazer alterações nos equipamentos ou na topologia da rede - alterações de
engenharia, uma forma de conseguir reduções do custo do bombeamento da produção é
otimizando a operação das bombas.
Atualmente, a operação das bombas responsáveis pelo escoamento da produção é
feita de forma descentralizada, baseada em procedimentos ad hoc, apoiados em sistemas
que monitoram parte dos dispositivos da rede. A complexidade inerente ao sistema, a
descentralização do controle, e a visão limitada dos operadores em relação à malha glo-
bal de escoamento impedem a otimização do processo.
Neste contexto, o trabalho aqui apresentado tem como objetivo prover uma solu-
ção otimizada que garanta a máxima eficiência de movimentação da produção, e a redu-
ção dos gastos com energia elétrica atendendo aos objetivos financeiros, operacionais,
ambientais e institucionais.
O controle de redes de tubulações, complexas e de grande escala, para escoamen-
to da produção de petróleo é complicado por vários fatores, entre eles: (a) a confiabilida-
de dos sistemas de aquisição de dados e comunicação, (b) tempos limites entre a aquisi-
ção de dados e a decisão de controle, (c) restrições operacionais de um grande número de
dispositivos, (d) controle multi-objetivo, envolvendo metas e restrições econômicas, ope-
racionais, ambientais e institucionais.
Os aspectos apontados acima se tornam ainda mais críticos à medida que o nume-
ro de dispositivos aumenta, já que cada um destes dispositivos possui suas próprias espe-
1
cificações de uso e restrições operacionais. Além disso, o grande número de restrições,
tanto do ponto de vista operacional dos equipamentos, como níveis mínimos e máximos
de óleo nos tanques, pressão nos dutos e bombas, quanto dos aspectos de segurança ope-
racional e econômico, e, as incertezas presentes no sistema advindas da variação do pa-
drão de produção dos poços, se tornam especialmente críticos à medida que a capacidade
máxima de operação do sistema vai se aproximando.
Muitos dos métodos matemáticos que têm sido utilizados para otimização da pro-
gramação de operação -escalonamento- de bombas sofrem ao lidar com redes com um
número elevado de combinações diferentes de bombas e/ou de estações coletoras, com a
quantidade de cálculos crescendo tão rapidamente que a demanda por recursos computa-
cionais se torna inaceitável e as restrições temporais difíceis de serem atendidas [28].
A otimização de sistemas de bombeamento tem sido bastante estudada, em espe-
cial em sistemas de redes de abastecimento de água [35][41][28][26][37]. As característi-
cas das redes de escoamento dos fluidos de petróleo, com um número maior de bombas e
um fluido que exige que processos de mistura de óleos e decantação sejam modelados,
aumentam a complexidade do sistema que se está querendo otimizar. Uma grande varie-
dade de técnicas pode ser utilizada para a resolução deste tipo de problema de elevada
complexidade, variando desde métodos de programação matemática, aos sistemas basea-
dos em regras, e aos sistemas baseados em meta-heurísticas, em que se encontram os
Algoritmos Genéticos, colônias de formigas entre outros. Esses métodos podem ainda ser
utilizados de forma combinada para atacar diferentes aspectos do problema.
Neste trabalho apresentamos uma solução baseada em Algoritmo Genético para
otimização do escalonamento das bombas em uma rede de escoamento da produção de
petróleo. O Algoritmo Genético tem uma função objetivo ponderada no tempo, operado-
res de reprodução modificados e pode ser executado em paralelo em uma grade computa-
cional. O algoritmo trata as questões referentes à restrição temporal do problema e às
incertezas advindas das mudanças no cenário de produção dos campos de exploração.
Questões relativas à confiabilidade dos sistemas de aquisição de dados não são tratadas
neste estudo.
O trabalho está estruturado em sete capítulos. No Capítulo 2 expomos detalhada-
mente o problema, apresentando as características dos sistemas tratados, juntamente com
os dados da área piloto utilizada para validação da solução, o modelo matemático da si-
2
mulação hidráulica e as características do modelo tarifário ao qual o sistema está subme-
tido.
No Capítulo 3 apresentamos as pesquisas na área de otimização da operação de
redes de escoamento tanto de óleo quanto de água, e as diversas técnicas utilizadas para
resolução de problemas semelhantes. Concluímos este capítulo com uma justificativa
para a utilização de Algoritmos Genéticos na solução proposta.
O Capítulo 4 introduz o método de otimização escolhido, os fundamentos do seu
funcionamento, suas aplicações e o detalhamento das suas estruturas. No Capítulo 5 a-
presentamos a solução proposta e a avaliação desta solução em vários cenários, compa-
rando-a com os procedimentos em uso atualmente. Por fim, o Capítulo 6 apresenta as
conclusões e as direções futuras de desenvolvimento desta linha de pesquisa.
3
2 Formalização do problema
2.1 Visão geral do domínio do problema
Um campo de extração de petróleo é composto por poços e uma rede de dutos, a
qual conecta esses poços a estações coletoras, e estas a uma estação de tratamento. O
óleo extraído é armazenado em tanques nas estações coletoras e destes tanques é bombe-
ado através da rede de dutos até a estação de tratamento. A operação adequada da rede
requer uma programação do bombeamento de maneira a reduzir o gasto com energia elé-
trica no bombeamento da produção. Uma configuração de rede típica pode ser observada
na Figura 1.
Figura 1 – Esquema parcial da rede de escoamento da UN-RNCE1
A produção bruta dos poços escoa para estações coletoras satélites e daí para esta-
ções coletoras centrais. O gás produzido cujo aproveitamento não é econômico, face à
baixa razão gás/óleo (RGO) é queimado nas estações satélites. Nas estações coletoras
centrais, parte da água produzida é separada e tratada. O restante, juntamente com o óleo,
é enviado para a estação final de tratamento de óleo e efluentes (ETO). Após o tratamen- 1 Fonte: Arquivos de imagens da UN-RNCE
4
to, o óleo segue para as refinarias transportado em navios petroleiros. A água separada na
estação de tratamento é tratada para descarte no mar de acordo com os índices e parâme-
tros permitidos pela legislação ambiental.
B - bombasECS – estação coletora satéliteECC – estação coletora centralET – estação de tratamento
B ECSB
ECS
BECS
BECC
BECS
ET
BECC
B ECC
Poços
Oleoduto Central
B - bombasECS – estação coletora satéliteECC – estação coletora centralET – estação de tratamento
B ECSBB ECSECSB
ECSBB
ECSECS
BECS BBECSECS
BECC BBECCECC
BECS BBECS
ETET
BECC
BBECCECC
B ECCBB ECCECC
Poços
Oleoduto Central
Figura 2 – Esquema de rede de escoamento
Atualmente, o controle da operação das bombas da malha de escoamento da Uni-
dade de Negócios do Rio Grande do Norte e Ceará (UN-RNCE) da PETROBRAS
(Figura 1) é feito de forma descentralizada e independente, baseado em regras simples de
operação, auxiliado por equipamentos de segurança, como sensores de níveis e pressosta-
tos. Cada ativo da rede, uma unidade administrativa independente, composta de uma es-
tação coletora central e suas estações coletoras satélites, é controlada por um operador,
que, obedecendo a essas regras de operação, determina quando ligar e desligar cada
bomba da estação. Dessa forma, o operador possui uma visão limitada, restrita ao ativo
sob sua responsabilidade e ao oleoduto central compartilhado, não possuindo informa-
ções sobre as demais unidades administrativas da rede, o que normalmente não garante
um escoamento ótimo de toda a produção. Do ponto de vista do operador, a operação
ótima do seu ativo é aquela em que a maior quantidade de petróleo é escoada, respeitan-
do as restrições operacionais e os requisitos de segurança da rede. As questões relativas
ao custo da operação da rede advindo do consumo de energia elétrica são secundárias,
5
visto que, a avaliação do desempenho de cada unidade administrativa é baseada no vo-
lume de fluído bombeado para a estação final de tratamento.
Determinar o escalonamento (quando ligar ou desligar cada bomba) das bombas
para certo período no futuro (horizonte de operação), sob dados modelo de simulação
hidráulica da rede, previsão de produção e esquema tarifário de energia elétrica, objeti-
vando a máxima segurança operacional e o mínimo custo global, respeitando as restri-
ções operacionais dos elementos da rede e sem reduzir as metas de produção de petróleo
é um problema de otimização complexo.
O sistema que estamos modelando (Figura 2) está compreendido entre as estações
coletoras, que armazenam a produção vinda dos poços nos tanques produtores, e a esta-
ção de tratamento, formada por um conjunto de tanques receptores. Todos os elementos
fora desse sistema, incluindo os campos de exploração e os poços, e o bombeio até as
estações coletoras não estão sendo modelados.
O horizonte de operação define o período de tempo para o qual a otimização será
realizada. Por exemplo, um horizonte de operação de 12 horas indica que o otimizador
deverá calcular um escalonamento para as bombas da malha fornecida para um período
de 12 horas, a partir do horário inicial estipulado. Um horizonte de operação típico é de
24 horas, pois inclui todos os ciclos de tarifação de energia elétrica.
O intervalo de atuação é um divisor do horizonte de operação e discretiza o perío-
do de tempo do horizonte de operação, de maneira que a sugestão de escalonamento obe-
deça a esses intervalos ao sugerir mudanças no estado das bombas. A granularidade do
intervalo de atuação não deve ser muito pequena sob pena de acarretar um desgaste nas
bombas e diminuir a sua vida útil, nem tampouco pode ser muito grande, por reduzir as
possibilidades de otimização [42].
Na entrada de toda estação coletora satélite ou central, o fluido que está sendo
produzido e bombeado para ser armazenado nos tanques destas estações deve ser caracte-
rizado por uma previsão da produção de fluidos, que neste trabalho utiliza cenários hipo-
téticos. A previsão da produção informa a temperatura, a viscosidade e a vazão de entra-
da do fluido nas diversas estações para o horizonte de operação. Como não se pode ga-
rantir que a previsão da produção, baseada em dados históricos da produção, se confirma-
rá tal como foi prevista, e grandes variações no padrão de produção podem inviabilizar
parte ou toda a aplicação de uma programação de escalonamento bombas sugerida pelo
otimizador, é importante que o otimizador privilegie estratégias de soluções segundo as
6
quais a maior parte da produção é bombeada não só fora do horário de pico, como tam-
bém nos primeiros intervalos de operação, onde são maiores as chances da previsão da
produção se concretizar como previsto. O escoamento da produção armazenada nas esta-
ções nos primeiros intervalos de otimização minimizam as possíveis perdas que uma uni-
dade administrativa possa ter devido a mudanças no cenário futuro de produção, que in-
viabilizem o escoamento da sua produção, programado para um momento no futuro.
A estratégia de otimização buscará uma solução econômica, mantendo a produção
bombeada dos poços. A otimização se dá em sistemas sob qualquer esquema tarifário e
os diversos ativos da rede podem constituir diferentes unidades consumidoras, e estar
submetidos a diferentes contratos entre os fornecedores de energia elétrica ou mesmo
utilizar fontes de energia de geração própria. A redução dos gastos com energia é alcan-
çada evitando-se a operação das bombas nos períodos de tarifas mais cara. O período de
ponta é definido pela Concessionária, de acordo com as características do sistema elétri-
co, e geralmente está situado no intervalo compreendido diariamente, entre 17h e 22h,
exceto sábados e domingos e feriados nacionais ou outros feriados definidos por Lei Fe-
deral [29]. Outro aspecto que deve ser observado é o acionamento simultâneo de várias
bombas, que deve ser evitado para que o pico gerado não ultrapasse os valores de de-
manda contratados.
A solução para o escalonamento das bombas deve obedecer a todas as restrições
de pressões e vazões dos dutos, capacidade de armazenamento dos tanques e operacio-
nais das bombas, válvulas e demais dispositivos do sistema, garantindo a segurança da
operação. Uma solução só será considerada válida se, para o horizonte de operação espe-
cificado, não ocorrer nenhuma violação das restrições do problema para o conjunto de
intervalos de atuação. A violação de uma restrição operacional do problema equivale a
um alarme no sistema de escoamento real. Dizemos de uma solução que gera um alarme
falha para o intervalo da ocorrência do alarme.
Além disso, o otimizador deve ser capaz de atender às restrições temporais do
problema, que estipula um tempo máximo para o otimizador fornecer uma solução de
escalonamento para o problema, dada pelo período entre dois intervalos de atuação.
7
2.2 Objetivo do controle
O problema do escalonamento das bombas é formulado como um problema de o-
timização de custos. Existem diferentes componentes do custo da produção, mas um dos
mais relevantes é o custo da energia. O modelo matemático do problema tratado tem co-
mo objetivo a minimização do custo da energia por volume de fluido bombeado para os
tanques receptores da rede, na estação de tratamento (Equação 1).
entregueVCustoTSfo = (1)
Em que: é a função que se deseja minimizar [R$/m3]; fo
CustoTS é o custo total de demanda e energia consumida durante todo o período
da simulação [R$];
entregueV é o volume total entregue à estação final de tratamento durante todo o
período da simulação [m3];
O volume total entregue é dado pela seguinte equação:
∑=
=n
iientregue QdtV
1. (2)
Em que: t é o tempo correspondente a um intervalo da simulação [s];
i é o índice do intervalo da simulação [adimensional];
∑=
n
i 1
corresponde ao somatório de todos os intervalos da simulação;
iQd é a vazão no duto conectado a estação de tratamento para cada intervalo da
simulação [m3/s];
2.3 Simulação do custo da energia
O custo de energia é formado tanto pelo custo da energia consumida pela opera-
ção das bombas, o custo do regime permanente, como pelo custo da energia no momento
de acionamento da bomba, custo do regime transitório. Por questões de simplificação,
neste trabalho, o custo do regime transitório foi desconsiderado no cálculo do custo com
8
energia elétrica para uma dada solução de escalonamento das bombas. Não encontramos
na literatura a quantificação deste custo em comparação ao custo considerado do regime
permanente, mas esta perde a relevância quando um dispositivo opera por um período
longo, e o número de acionamentos é portanto reduzido. O custo total (CustoTS) de um
cenário de simulação é portanto obtido pela seguinte equação:
CustoDTCustoETCustoTS += (3)
Em que: é o custo total da energia consumida referente a todo o perío-
do da simulação [R$];
CustoET
CustoDT é o custo total da demanda, dado pelo pico de potência durante o perí-
odo da simulação [R$];
Conforme a Equação (3), o custo de energia é o somatório do custo da energia
consumida pelas bombas e do custo da demanda. O custo da energia consumida (Custo-
ET) é dada por:
(∑ ∑= =
⎟⎟⎠
⎞⎜⎜⎝
⎛=
n
UC
n
i
UCi
UCi tarifaECeCustoET
1 1. ) (4)
Em que: corresponde ao somatório de todas as unidades consumidoras; ∑=
n
UC 1
∑=
n
b 1
corresponde ao somatório de todas as bombas de uma unidade consumido-
ra; UCiCe é o consumo de energia verificado na unidade consumidora UC, para cada
intervalo da simulação [MWh]; UCitarifaE é o preço aplicado ao consumo de energia para cada intervalo da simu-
lação, determinado no contrato feito entre a unidade consumidora UC e a concessionária
[R$/MWh];
hUCi
UCi tDpCe ⋅= (5)
Em que: é o somatório das potências de todas as bombas da unidade con-
sumidora UC, para cada intervalo da simulação [MW];
UCiDp
ht é o intervalo de tempo correspondente a um intervalo da simulação [h];
9
A potência de uma bomba , para um intervalo da simulação i é dada por [36]: iP
im
iifluidoi
QbHmangP i
ηηρ
....
= (6)
Em que: ifluidoρ é a massa específica do fluido bombeado, para cada intervalo da
simulação [Kg/m3];
g é a aceleração da gravidade [m/s2];
Hmani é a altura manométrica da bomba, para cada intervalo da simulação
[mcf]2;
iQb é a vazão que passa pela bomba, para cada intervalo da simulação [m3/s];
mη é o rendimento do motor [%];
iη é o rendimento da bomba, para cada intervalo da simulação [%];
A demanda é a potência média durante qualquer intervalo de tempo, medido por
um aparelho integrador. Para o faturamento de energia pela concessionária são utilizados
intervalos de integração de 15 minutos. Em um mês, ocorrem quase 3000 intervalos de
quinze minutos. Assim, a demanda será medida quase 3000 vezes no mês, e seu custo é
calculado pelo pico verificado num período de 30 dias, ainda que este tenha sido verifi-
cado apenas uma única vez. Nos cálculos feitos para determinar o custo de uma solução
proposta, com horizonte de operação inferior a 30 dias, consideramos o valor do pico
observado durante o horizonte de operação que está sendo otimizado, e o custo da de-
manda é uma proporção da demanda contratada estabelecida no contrato de fornecimen-
to. Tomando como exemplo um horizonte de operação de 24h, o valor referente ao custo
da demanda equivale a 1/30 do valor estipulado para aquela faixa de demanda, conforme
contrato que estabelece as tarifas elétricas.
Caso o valor da demanda contratada seja excedido, a parcela da demanda que ex-
cede o contratado será cobrada pelo valor especificado nas tarifas de ultrapassagem. A
tarifa de ultrapassagem é superior à tarifa normal porque o sistema funciona em condi-
ções ótimas quando as demandas são bem definidas e estimadas com antecedência (a
partir da demanda contratada). Quando o cliente ultrapassa sua demanda, sobrecarrega o
2 mcf é a unidade métrica metro coluna de fluido.
10
sistema, o que implica em redução da qualidade do fornecimento (com mais picos e osci-
lações) e mais perdas de energia elétrica. O custo da demanda (custoDT) é dado por:
∑=
⋅=n
UC
UCCustoDMdmês
dSCustoDT1
(7)
Em que: dS é a duração da simulação [s];
dmês é a duração do período “entre fechamento de faturas” da unidade consumi-
dora UC [s]; UCCustoDM é o custo total da demanda verificado para o período entre “fecha-
mento de faturas”, para cada unidade consumidora UC [R$];
UCUCUC custodfpcustodpCustoDM += (8)
Em que: é o custo da demanda correspondente aos períodos de ponta
verificados entre “fechamento de faturas”, para cada unidade consumidora UC [R$];
UCcustodp
UCcustodfp é o custo da demanda correspondente aos períodos fora de ponta veri-
ficados entre “fechamento de faturas”, para cada unidade consumidora UC [R$];
),,,,( UCUCi tarifaDDpchoradataDpfcustodp = (9)
),,,,( UCUCi tarifaDDpfhoradataDpfcustodfp = (10)
Em que: e cor-
respondem ao custo da demanda para uma unidade consumidora, que é função das de-
mandas medidas (Dpi), da data e das horas transcorridas durante a simulação, da de-
manda contratada para a ponta (DpcUC) e fora de ponta (DpfUC), e das características da
tarifação (tarifaDUC), conforme o contrato feito com a concessionária [R$];
),,,,( UCUCi tarifaDDpchoradataDpf ),,,,( UCUC
i tarifaDDpchoradataDpf
Nos contratos das concessionárias, os consumidores são classificados pelo nível
de tensão em que são atendidos (Tabela 1). Os consumidores atendidos em alta tensão,
acima de 2,3 KV, como indústrias, shopping centers e alguns edifícios comerciais, são
classificados no Grupo A.
11
Tabela 1 - Grupos de consumo de alta tensão
Subgrupos Tensão de Fornecimento A1 ≥ 203 KV A2 88 KV a 138 KV A3 69 KV A3a 30 KV a 44 KV A4 2,3 KV a 25 KV AS Subterrâneo
Os consumidores do Grupo A têm tarifa binômia, isto é, são cobrados tanto pela
demanda quanto pela energia que consomem. Estes consumidores podem ser enquadra-
dos em uma de três categorias tarifárias: tarifação convencional, tarifação horo-sazonal
verde ou tarifação horo-sazonal azul. As tarifas horo-sazonais são caracterizadas pela
aplicação de tarifas diferenciadas de consumo de energia elétrica e de demanda de potên-
cia de acordo com as horas de utilização do dia e dos períodos do ano.
Os contratos entre a PETROBRAS e as concessionárias recaem nos subgrupos A3
e A4, e são do tipo horo-sazonal azul. A tarifação horo-sazonal azul apresenta tarifas
diferenciadas de acordo com o horário do dia (na ponta e fora de ponta) e com a época do
ano (período seco e período úmido) (Tabela 2). Em relação à demanda, apresenta tarifas
baseadas apenas no horário do dia (ponta e fora de ponta). O custo da energia elétrica na
tarifação horo-sazonal azul será o somatório dos custos devido à demanda na ponta (mais
porcentagem da ultrapassagem), à demanda fora de ponta (mais porcentagem da ultrapas-
sagem), ao consumo na ponta (período seco ou úmido) e ao consumo fora de ponta (perí-
odo seco ou úmido).
12
Tabela 2 - Exemplo de tarifa horo-sazonal azul3
Horo-sazonal azul Demanda (R$/KWh)
Normal Ultrapassagem
Ponta Fora de
ponta Ponta
Fora de
ponta 28,39 9,43 85,22 28,39
Consumo (R$/MWh)
Ponta Fora de ponta Seco Úmido Seco Úmido
186,33 172,40 88,58 78,28
2.4 Modelo de simulação hidráulico
O que se deseja na simulação é a obtenção do equilíbrio hidráulico da rede, ou se-
ja, encontrar o ponto de funcionamento do sistema em termos de suas variáveis de esta-
do: vazão e pressão.
Para equilibrar a rede (Equação (13)) são encontradas: as vazões (Equação (11)),
pressões nos dutos e alturas manométricas das bombas (Equação (12)), para uma dada
configuração em um determinado instante. Para tanto, arbitra-se, inicialmente, o ponto de
trabalho de cada bomba, calcula-se o comportamento da rede (vazões, perdas de carga,
pressões, etc.) e verifica-se o atendimento ao equilíbrio hidráulico (critério de parada). Se
esse não for atendido, realizam-se novos cálculos iterativamente, k vezes, partindo-se das
novas vazões encontradas, até que o critério de parada (Equação (13)) seja atingido.
ki estimestim QbQb = (11)
ki manman HH = (12)
( )61 10−= ≤
−∑n
QbQbn
bestimcalc kk
(13)
3 subgrupo A4 – fonte: www.lightempresas.com.br
13
Em que: é a vazão adotada para a bomba a fim de que o equilíbrio seja
verificado, para o intervalo i da verificação [m3/s];
iestimQb
kestimQb é a vazão adotada para a bomba a fim de que o equilíbrio seja verificado,
para o intervalo k da verificação [m3/s];
kcalcQb é a vazão encontrada a partir dos valores de pressões calculados para a
vazão estimada ( ) aplicada ao sistema, para o intervalo k da verificação [m3/s]; kestimQb
n é o número total de bombas;
Hmani é a altura manométrica da bomba para o intervalo i da verificação [mcf];
Hmank é a altura manométrica da bomba para cada intervalo k da verificação
[mcf];
Para equilibrar a rede, estima-se, para cada bomba, uma vazão inicial (Equação
(14)). Convencionou-se que, para as bombas centrífugas, a vazão estimada inicial é i-
gual à metade da vazão resultante da resolução da equação de sua respectiva curva ca-
racterística obtida para altura manométrica igual a zero. Segundo Driedger [9], a curva
característica das bombas volumétricas é basicamente retilínea, logo, para essas bom-
bas, toma-se como vazão estimada inicial a vazão resultante da resolução da equação da
sua curva característica para altura manométrica igual a zero ( Figuras 3 e 4).
1, == kparaQbQbkk iniestim (14)
Em que: é a vazão inicial estimada para a bomba [m3/s]. kiniQb
Apesar de produzirem fluxo pulsante, as bombas alternativas, com vários êmbolos
(duplex, triplex ou multiplex) e/ou com duplo efeito, descarregam uma vazão aproxima-
damente constante ao longo do tempo, recaindo no gráfico das bombas volumétricas da
Figura 4.
14
Hman
Qinicial Q Qinicial Q
Hman
Figura 3 - Vazão estimada inicial para as bombas centrífugas e volumétricas
Q
vazão ≅ constante
Figura 4 - Vazão estimada inicial para as bombas alter
Uma vez adotadas as vazões iniciais para as bombas, dete
timadas em cada duto da rede até a estação de tratamento; quando
lelo, a vazão é inicialmente dividida pelo número de dutos e de
quações (15) e (16)).
A vazão do duto x, quando o duto está conectado a uma bo
iestimi QbQx =
Em que: é a vazão do duto x, para cada intervalo i da iQx
iestimQb é a vazão da bomba, para cada intervalo i da simul
A vazão do duto x, quando o duto não está conectado a u
somatório das vazões dos dutos conectados a sua montante:
∑=
=n
dii QdQx
1
Em que: é a vazão do duto x, para cada intervalo i da iQx
iQd é a vazão do duto, o qual está a montante do duto x,
simulação [m3/s];
∑=
n
d 1
corresponde ao somatório dos dutos.
15
t
nativas
rminam-se as vazões es-
houver dutos em para-
pois é redistribuída (E-
mba é dada por:
(15)
simulação [m3/s];
ação [m3/s];
ma bomba é dado pelo
(16)
simulação [m3/s];
para cada intervalo da
De posse das vazões estimadas para cada duto, calculam-se as perdas de carga
nos dutos a partir da seguinte equação:
gv
dLfh i
ii .2..
2
=∆ (17)
Em que: é a perda de carga no duto, para cada intervalo da simulação [mcf]; ih∆
if é o fator de atrito no duto, para cada intervalo da simulação [adimensional];
L é o comprimento do duto [m];
d é o diâmetro interno do duto [m];
iv é a velocidade do fluido no duto, para cada intervalo da simulação [m/s];
g é a aceleração da gravidade [m/s2].
⎪⎪
⎩
⎪⎪
⎨
⎧
≥⎪⎭
⎪⎬⎫
⎪⎩
⎪⎨⎧
⎥⎥⎦
⎤
⎢⎢⎣
⎡⎟⎟⎠
⎞⎜⎜⎝
⎛+−−
<
= −
2300 se,5,14.7,3
log.02,5.7,3
log.2
2300 se,64
2
1010 iii
ii
i
yReReydyRed
yReyRe
fεε
(18)
Em que: é o número de Reynolds, para cada intervalo da simulação [adi-
mensional];
iyRe
ε é a rugosidade absoluta do duto [m].
A Equação (18) está sendo utilizada em substituição à fórmula de Colebrook-
White [34], por evitar cálculos iterativos.
dQ
Reyi
ii ..
.4πν
= (19)
Em que: é a vazão no duto, para cada intervalo i da simulação [m3/s]; iQ
iν é a viscosidade cinemática do fluido no duto, para cada intervalo i da simula-
ção [m2/s].
ivAQi
.= (20)
Em que: é a velocidade do fluido no duto, para cada intervalo i da simulação
[m/s];
iv
16
A é a área de seção transversal do duto [m²];
Calcula-se a pressão a montante e a jusante de todos os dutos, seqüencialmente,
utilizando as seguintes equações:
⎩⎨⎧
−∆++=
contráriocasocmhpjxZjquetanumaconectadoestáxdutoseN
pmxii
ii ,
, (21)
⎩⎨⎧
−∆−+=
contráriocasoZjhpmxcmquetanumaconectadoestáxdutoseN
pjxiii
ii ,
, (22)
Em que: é a pressão a montante do duto x, para cada intervalo da simula-
ção [mcf];
ipmx
iN é o nível do tanque para cada intervalo da simulação [m];
ipjx é a pressão a jusante do duto x, para cada intervalo da simulação [mcf];
ZmZj, são as cotas a jusante e a montante do duto x [m].
Calcula-se a altura manométrica de cada bomba pela diferença de pressão a ju-
sante e a montante da mesma (Equações (22), (23), e (24)).
⎩⎨⎧ −
=desligadaestábbombasezero
ligadaestábbombasepmbpjbHman ii
i ),(0,
(22)
ii pmpjb = (23)
ii pjpmb = (24)
Em que: é a pressão a jusante da bomba, para cada intervalo da simulação
[mcf];
ipjb
ipmb é a pressão a montante da bomba, para cada intervalo da simulação [mcf];
ipm é a pressão a montante do duto conectado a jusante da bomba, para cada in-
tervalo da simulação [mcf];
ipj é a pressão a jusante do duto conectado a montante da bomba, para cada in-
tervalo da simulação [mcf].
17
De posse das alturas manométricas, calcula-se uma nova vazão de descarga para
todas as bombas, a partir da inserção deste valor na sua curva característica (Equação
(25)).
( )⎥⎥⎦
⎤
⎢⎢⎣
⎡ −−±−=
aHmancabb
Qb kcalck .2
..4max
2 4 (25)
Em que: é a vazão encontrada a partir dos valores de pressões calculadas
para a vazão estimada ( ) aplicada ao sistema, para o intervalo de simulação atual
[m3/s].
kcalcQb
kestimQb
Se a diferença entre as vazões calculadas e as estimadas for maior que um valor
mínimo preestabelecido (condição de parada, Equação (27)), repete-se todo procedi-
mento interativo, assumindo que a nova vazão estimada é igual a média entre a vazão
estimada e a vazão calculada anteriores (Equação (26)).
211 −−
+= kk
k
estimcalcestim
QbQbQb (26)
( )61 10
11−= >
−∑ −−
n
QbQbnb
bestimcalc kk
(27)
Em que: é a vazão adotada para a bomba a fim de que o equilíbrio seja
verificado, para o intervalo k da verificação [m3/s];
1−kestimQb
1−kcalcQb é a vazão encontrada a partir dos valores de pressões calculadas para a
vazão estimada ( ) aplicada ao sistema, para o intervalo k da verificação [m3/s]; kestimQb
∑=
n
b 1
corresponde ao somatório de todas as bombas do sistema;
n é o número de bombas do sistema.
4a, b e c são os coeficientes da equação da curva da bomba (Hman [mcf] = a.Q2 + b.Q + c; Q
[l/s]).
18
Atendido o critério de parada, obtém-se os valores reais das vazões das bombas
(Equação (28)), realiza-se o balanço hídrico nos tanques, onde é calculado o nível atual
de cada um (Equação (29)) e calculam-se os consumos de energia envolvidos (Seção
2.3), com isso, finaliza-se um intervalo da simulação.
2kk estimcalc
i
QbQbQb
+=
(28)
⎪⎩
⎪⎨⎧
>−
+
==
− 1,.)(1,
1 iseAb
tQsQeN
iseNN
iii
ini
i (29)
Em que: é o nível atual de fluido no tanque [m]; iN
iniN é o nível inicial de fluido no tanque [m];
1−iN é o nível anterior de fluido no tanque [m];
Ab é a área da base do tanque [m2];
Qe, Qs são as vazões de entrada e de saída de um tanque, respectivamente
[m3/s];
t é o intervalo de tempo correspondente a um intervalo da simulação [s].
2.5 Restrições
Uma solução será considerada viável caso obedeça a todas as restrições impostas
pelo problema. As restrições do problema podem ser de diversas naturezas. As restrições
operacionais dizem respeito a restrições de funcionamento dos dispositivos da rede, tais
como bombas, dutos e tanques. Os tanques possuem limites de nível mínimo e máximo e
os dutos, limites mínimos e máximos de pressão e velocidade do fluido transportado.
Estas restrições não podem ser flexibilizadas sob pena de reduzir os níveis de se-
gurança da operação da rede, devendo ser respeitadas pelo escalonamento gerado. Cada
restrição operacional da rede tem um impacto diferente na operação e nos aspectos de
segurança e assim podem ser classificados pela sua severidade. Por exemplo, bombear
fluido além do limite de nível mínimo de um tanque pode comprometer a vida útil das
bombas e até causar a parada do sistema de bombeio. Por outro lado, operar com o fluido
19
escoando a uma velocidade menor do que a mínima especificada aumenta a deposição de
material nas paredes dos dutos, mas é menos crítico do que operar abaixo dos níveis mí-
nimos dos tanques. A pressão sob a qual o sistema opera não só está intimamente ligado
à segurança da operação e por isso é uma das restrições mais severas, como também é
uma das variáveis mais importantes do ponto de vista econômico. A pressão, juntamente
com a vazão, influencia o ponto ótimo de trabalho das bombas. Encontrar uma solução
que não viole as restrições operacionais é uma das maiores dificuldades para o algoritmo
de otimização.
Além das restrições operacionais, um outro aspecto muito importante é o tempo
limite entre a aquisição dos dados e o tempo para informar a programação das bombas
para o próximo intervalo de atuação. Por ser aplicado a um sistema em tempo real, as
restrições de tempo são fortes, e o algoritmo deve ser capaz de encontrar uma solução
viável para o escalonamento das bombas dentro do intervalo de atuação, já que uma solu-
ção encontrada após este tempo não terá mais interesse/valor para a aplicação. Dentro de
um intervalo de tempo tmin, inferior a intervalo de atuação, o otimizador deve ser capaz
de prover pelo menos uma solução viável para o escalonamento das bombas no próximo
intervalo de atuação. O otimizador continuará perseguindo um valor ótimo para todo o
horizonte de operação até que o tempo máximo tmax seja alcançado. Desta forma, à medi-
da que o tempo passa e novas soluções para o problema são exploradas, evoluindo em
direção a uma solução ótima para o problema, o valor do processamento aumenta, pois
estamos melhorando o resultado que tínhamos inicialmente em tmin. Depois de transcorri-
do o prazo (tmax), dado pelo horizonte de operação, o valor do processamento cai abrup-
tamente para zero, indicando que o resultado da computação já não tem mais valor para a
aplicação (Figura 5). Aplicações com essas características possuem várias soluções in-
termediárias que podem ter valor para aplicação, mesmo não sendo a solução ótima para
o problema.
20
tmin tmax
Val
or d
a co
mpu
taçã
o (V
)
Tempo (t)
Figura 5 - Gráfico do valor da computação versus tempo
2.6 Estudo de caso
O método de resolução proposto será aplicado a uma rede de escoamento de pe-
tróleo que consiste em mais de 70 tanques produtores, distribuídos nas diversas estações
coletoras, 4 tanques receptores, localizados na estação de tratamento, em torno de 250
bombas de produção e mais de 300 Km de dutos. Os tanques que compõem esta rede
possuem diferentes capacidades, as bombas são de diferentes tipos e capacidades e os
dutos são de diferentes comprimentos, diâmetros internos e rugosidades. O escalonamen-
to proposto deve adequar-se a todas essas peculiaridades de forma a não desrespeitar ne-
nhuma restrição operacional desses elementos.
Devido ao grande número de dispositivos da rede, o tempo de otimização da ma-
lha de escoamento da unidade de negócios RN-CE é bastante elevado, chegando a con-
sumir cerca de cinco minutos para a simulação de cada solução candidata, o que implica-
ria em vários dias para realizar a otimização de um único cenário. Para fazer o ajuste de
parâmetros do algoritmo de otimização é necessário fazer repetidas otimizações da malha
de escoamento sob diversas configurações. Por esta razão, para os experimentos que ilus-
trarão os resultados obtidos durante a realização deste trabalho, apresentados no Capítulo
5, utilizamos uma simplificação desta malha, com um número reduzido de estações e
com bombas e tanques equivalentes.
A malha utilizada no estudo é composta por quatro estações coletoras, cada uma
com um tanque produtor, e uma estação de tratamento com um tanque receptor. A produ-
21
ção é bombeada por seis bombas de deslocamento positivo, como pode ser observado no
esquema da Figura 6.
AR-B
T3
MAG
N2 D1
ETA
T1 B2 B1
D3
D5 D6N3
D7
D2
N1
AR-A
B5
T2
D4
T4
B6
ETO
T5
B4 B3
Figura 6 - Esquema da malha de escoamento de testes
As características físicas e os limites operacionais dos tanques, dutos e bombas
estão descritas nas Tabelas 3, 4, 5 e Tabela 6.
Tabela 3 - Características físicas e de operação dos tanques
Estação Tanque Cota de fundo Z [m]
Nível máximo Nmáx [m]
Nível má-ximo de controle Ncmáx [m]
Nível mí-nimo de controle Ncmin [m]
Diâmetro D [m]
Área da base Ab [m2]
ETA T1 29,8 11,00 9,10 0,50 10,60 88,25ARA T2 10,70 11,00 9,10 0,50 10,60 88,25ARB T3 17,10 11,00 9,10 0,50 10,60 88,25MAG T4 34,10 11,00 9,10 0,50 10,60 88,25ETO T5 71,90 11,00 9,10 0,50 15,95 200,00
22
Tabela 4 - Características físicas dos dutos
Duto Diâmetro interno d [m]
Comprimento L [m]
Rugosidade ε [mm]
Cota de montante Zmon [m]
Cota de jusante Zjus [m]
D1 0,591 7000 0,025 29,8 10,7D2 0,337 1200 0,025 10,7 10,7D3 0,255 1200 0,025 17,1 17,1D4 0,255 1200 0,025 34,1 34,1D5 0,591 4200 0,025 10,7 17,1D6 0,591 6300 0,025 17,1 34,1D7 0,591 20000 0,025 34,1 71,9
Tabela 5 - Limites de operação dos dutos
Duto Pressão máxima pmax [mcf]
Pressão mínima pmin [mcf]
Velocidade má-xima vmax [m/s]
Velocidade mí-nima vmin [m/s]
D1 250 0 3,0 0D2 250 0 3,0 0D3 250 0 3,0 0D4 250 0 3,0 0D5 250 0 3,0 0D6 250 0 3,0 0D7 250 0 3,0 0
Tabela 6 - Características físicas das bombas
Curva Característica Estação
Número de bombas5
Cota Z[m]
Rendimento do motor ηM [%]
Rendimento da bomba ηB [%] a b c
ETA 2 29,8 90 0 0 90 0 -200 12000ARA 2 10,7 90 0 0 90 0 -200 12000ARB 1 17,1 90 0 0 90 0 -200 28000MAG 1 34,1 90 0 0 90 0 -200 28000
Os sistemas sobre os quais desenvolvemos este estudo de caso estão sujeitos a um
esquema de tarifas que segue o modelo extraído do contrato entre a Companhia Energéti-
ca do Rio Grande do Norte (COSERN) e a Central Termoelétrica Alto do Rodrigues com
5 Todas as bombas de uma estação são iguais (Hman [mcf] = a.Q2 + b.Q + c; Q [l/s] )
23
a PETROBRAS, referentes às unidades consumidoras SE ARG-A3 e SE CAM-A36
(Tabela 7). Todas as estações da malha simplificada, baseada na rede de escoamento da
UN-RNCE, fazem parte de uma única unidade consumidora, mas como o número de dis-
positivos nesta malha foi reduzido da original, reduzimos também o valor da demanda
contratada presente no contrato original, para tornar os valores adequados para uma rede
com um número menor de bombas. Os experimentos ocorrem dentro do período sazonal
úmido, no intervalo das 0h às 24h, compreendendo todos os horários tarifários, inclusive
o horário de ponta que no contrato com a COSERN corresponde ao período entre
17h30min e 20h30min.
Tabela 7 - Quadro de tarifas elétricas
Ponta 21,02
Fora de Ponta 5,66
Ponta (ultrapassagem)
63,06
DEM
AN
DA
[R$/
KW
]
Fora de Ponta (ultrapassagem)
16,99
Ponta (período seco)
105,05
Fora Ponta (período seco)
70,89
Ponta (período úmido)
93,22
CO
NSU
MO
[R$/
MW
h]
Fora de Ponta (período úmido)
61,42
O sistema será otimizado em diferentes cenários de produção, para que ele possa
ser calibrado para funcionar num cenário cuja produção esteja abaixo do que a rede de
6 A PETROBRAS e a COSERN possuem outros contratos tarifários para outras unidades con-
sumidoras, como Upanema – A4 e Con/SRC – A4. Todos os contratos utilizam o sistema tarifário horo-sazonal azul.
24
dutos suporta, um cenário de baixa saturação (Cenário I), em um cenário de média satu-
ração (Cenário II), onde surgem as primeiras dificuldades de encontrar um escalonamen-
to de bombas que não viole as restrições operacionais do sistema, com a presença de al-
guns pontos de falhas, e um cenário saturado (Cenário III), onde é impossível operar a
malha sem que haja um mínimo de coordenação entre as diversas unidades administrati-
vas que estão concorrendo pela capacidade de transferência da tubulação. As condições
iniciais do sistema, arbitrados dentro da faixa de operação do sistema, estão nas Tabela 8
e 9, e a previsão da produção para o período a ser otimizado, nos diferentes cenários, é a
apresentada na Tabela 10. As características do fluido para todos os cenários hipotéticos
de previsão da produção e da previsão de saída da estação de tratamento ETO são apre-
sentadas nas Tabelas 11, 12, 13 e 14.
Tabela 8 - Condições iniciais do sistema
Estação Tanque Nível inicial N [m]
Quantidade de bombas ligadas inicialmente
ETA T1 2,0 0 ARA T2 7,5 1 ARB T3 8,1 1 MAG T4 6,0 1 ETO T5 6,0 -
Tabela 9 - Característica do fluido nas estações
Viscosidade cinemática ν [m2/s] Estação Tanque
BSW7 [%]
Massa espe-cífica ρ [kg/m3] p q
Temperatura do fluido T [ºC]
ETA T1 50,000 941,26 0,0579 -2,050 30ARA T2 50,000 939,91 0,0435 -1,661 35ARB T3 90,000 938,76 0,0290 -1,661 45MAG T4 20,000 937,97 0,0145 -1,661 50ETO T5 53,491 939,00 0,0268 -1,719 43
7 Basic Sediments and Water– sedimentos básicos e água.
25
Tabela 10 - Previsão de entrada (da produção) e saída das estações
Vazão [l/s] Estação
Período ETA ARB ARA MAG ETO
Cenário I 00:00 a 24:00
29,5130 73,614 34,1664 15,625 160,00
Cenário II 00:00 a 24:00
35,4160 103,060 42,7080 18,750 207,46
Cenário III 00:00 a 24:00
42,4992 135,600 53,3000 22,500 270,00
Tabela 11 - Viscosidade cinemática do fluido
Viscosidade Cinemática do fluido: ν = p . Tq [m2/s] ETA ARA ARB MAG Estação
Período
p q p q p q p q 00:00 a 07:20 0,0579 -2,050 0,0435 -1,661 0,0290 -1,661 0,0145 -1,661 07:20 a 15:40 0,0290 -1,661 0,0435 -1,661 0,0579 -2,050 0,0145 -1,661 15:40 a 20:40 0,0290 -1,661 0,0579 -2,050 0,0435 -1,661 0,0145 -1,661 20:40 a 00:00 0,0290 -1,661 0,0579 -2,050 0,0435 -1,661 0,0579 -1,661
Tabela 12 - BSW do fluido
BSW [%] Estação
Período ETA ARA ARB MAG
00:00 a 09:50 50 50 90 2009:50 a 18:10 50 25 65 2018:10 a 00:00 90 25 65 70
Tabela 13 - Temperatura do fluido
Temperatura do fluido: T [ºC] Estação
Período ETA ARA ARB MAG
00:00 a 08:10 30 35 45 5008:10 a 16:30 37 35 40 5016:30 a 19:50 37 35 40 6019:50 a 00:00 35 42 40 60
26
Tabela 14 - Massa específica do fluido
Massa específica do fluido: ρ [kg/m3] Estação
Período ETA ARA ARB MAG
00:00 a 04:50 941,26 939,91 938,76 937,9704:50 a 13:10 937,97 939,91 938,76 941,2613:10 a 22:20 938,76 939,91 937,97 941,2622:20 a 00:00 938,76 941,26 937,97 941,26
27
3 Revisão bibliográfica
Devido à natureza do problema, a otimização do escalonamento das bombas em
redes de escoamento de fluidos é difícil de ser tratada pela maioria dos métodos de otimi-
zação, especialmente quando o sistema a ser otimizado é de grande escala.
Vários métodos dependem da existência de derivadas e restrições de continuidade
das funções. A busca no mundo real é cheia de descontinuidades inconvenientes, e espa-
ços de busca multi-modais.
Ormsbee e Lansey [35] publicaram uma revisão das diferentes abordagens para o
problema de otimização do escalonamento de bombas. O estudo considera os métodos de
programação linear, dinâmica e não-linear, além de adaptações desses métodos. Os di-
versos trabalhos em otimização do bombeamento são organizados de acordo com os tipos
de sistemas aos quais os métodos de otimização se aplicam, explicitando os tipos de rede,
de modelo hidráulico e de modelo de demanda que foram utilizados em cada um deles.
Os estudos do Water Research Center presentes no relatório “Pump Scheduling in Water
Supply” [46] consideram várias abordagens para o problema de escalonamento de bom-
bas em redes de escoamento de água e traz uma breve descrição dos métodos de progra-
mação linear, programação dinâmica, entre outras técnicas, com suas vantagens e des-
vantagens.
Todavia, nenhum destes métodos é totalmente satisfatório para todos os tipos de
problemas de escalonamento de bombas. Todos estes métodos têm um problema comum
de serem pouco escaláveis, o que inviabiliza a sua aplicação quando o número de disposi-
tivos cresce, porque a quantidade de cálculos necessários cresce rapidamente e, por con-
seguinte, o tempo computacional, só sendo adequados para redes de pequeno porte. Mui-
tas vezes os métodos apresentam dificuldades de adequação a redes com mais de um re-
servatório ou combinações e tipos de bombas diferentes [28].
Muitos problemas de otimização como este, onde a complexidade do problema e
a não-linearidade das funções impedem o uso de métodos de otimização tradicionais co-
mo a programação linear e a programação dinâmica, utilizam algoritmos de aproximação
como os Algoritmos Genéticos. Na falta de algoritmos robustos para localizar o ótimo
global, estes têm se destacado por chegar a valores ótimos muito próximos do ótimo glo-
bal com uma probabilidade alta, sendo muito utilizados em uma grande variedade de
28
problemas do mundo real, para os quais o espaço de soluções é muito vasto e verificar
todas as opções é computacionalmente impraticável.
O uso de Algoritmos Genéticos para a resolução de problemas em redes de esco-
amento de água, em particular, é muito comum. Os trabalhos mais recentes têm focado
seus estudos na otimização de redes de distribuição de água, incluindo, além de projeto
de novas redes [7] e modelagem e calibração de modelos de distribuição [39], a reabilita-
ção e a operação [40]. Isso se deve à capacidade dos Algoritmos Genéticos de lidar com
problemas grandes e complexos, com funções de otimização multi-objetivo e, muitas
vezes, com objetivos conflitantes.
Mackle et al [28], por exemplo, apresentam o uso de Algoritmos Genéticos para a
otimização de redes de abastecimento de água. O Algoritmo Genético utiliza uma popu-
lação inicial gerada randômicamente e um algoritmo de seleção do tipo ordenação. Os
resultados com o algoritmo de seleção, que são usados em muitos outros trabalhos de
otimização em redes de água, são a maior contribuição daquele trabalho. Posteriormente,
há um refinamento, substituindo a população inicial randômica por uma população lida
de um arquivo e novos operadores de cruzamento, não apenas com um ponto de troca,
mas com dois pontos de troca. O estudo mostra ainda várias comparações entre a aborda-
gem do problema de objetivo único, bem como, como um problema multi-objetivo [41].
A rede estudada tem um único reservatório e quatro bombas, o que totaliza apenas 16
combinações possíveis de escalonamento a cada intervalo de atuação, o que torna possí-
vel a exclusão de várias soluções, e mapear a vazão dada pelas diversas combinações e o
consumo do conjunto sem a necessidade de simulá-los a cada nova solução candidata a
ser avaliada.
Beckwith e Wong [5] apresentam um Algoritmo Genético com o objetivo de re-
duzir o custo do bombeamento num sistema de água com múltiplos reservatórios, aten-
dendo à demanda diária. O problema é tratado em dois passos: o primeiro determina o
volume de água produzido por cada estação para que a demanda seja atendida e o segun-
do, as bombas que devem ser ligadas para suprir este volume. A solução foi aplicada em
uma malha com 5 estações e 16 bombas para um horizonte de operação de uma hora e
intervalo de atuação de 15 minutos. Um dos problemas dessa solução é o elevado tempo
de processamento. Para a otimização de um cenário, utilizando uma população de 100
indivíduos e 100 gerações, leva-se 3,2 horas.
29
O EXPLORE (Hybrid Expert System for water Supply) [26], por sua vez, é um
sistema especialista de apoio à decisão desenvolvido para gerenciar o fornecimento de
água na cidade de Sevilha, tendo como meta reduzir o custo da operação de bombeamen-
to da água em reservatórios, mantendo a demanda satisfatória e a água dentro dos pa-
drões de qualidade determinados. O sistema funciona utilizando regras de operação e
procedimentos algorítmicos. Para tanto, são necessárias regras que descrevam a operação
do sistema de abastecimento de água. A dificuldade de aplicar esta solução ao nosso pro-
blema está nas limitações de se capturar as regras de operação, que em geral são proce-
dimentos ad hoc, baseadas na experiência prática dos operadores da rede, e que em am-
bientes cujo comando é descentralizado são difíceis de extrair, dado que o operador não
tem uma visão do “todo”. No caso particular do nosso problema, as decisões tomadas nas
diversas estações embora sejam consensuais, não visam a otimização do processo de uma
forma global. Uma outra abordagem para o problema é a utilização dos Algoritmos Ge-
néticos, juntamente com o aprendizado de máquinas, para a obtenção de regras operacio-
nais ótimas [26]. Esta abordagem, ao invés de fornecer ao operador da rede o escalona-
mento das bombas para um certo intervalo de tempo, fornece um conjunto de regras ex-
traídas com base nas soluções propostas pelo Algoritmo Genético multi-objetivo, que
devem ser seguidas para alcançar um escalonamento ótimo.
A aplicação de Algoritmos Genéticos na indústria de petróleo, por sua vez, tem
sido bastante focada na caracterização de reservatórios subterrâneos, inversão sísmica e
no desenvolvimento de campos de petróleo [38][6]. O seu uso para operação de sistemas
foi pouco explorado, concentrando-se em sistemas de inspeção e reparo de tanques e du-
tos [42]. As peculiaridades advindas das restrições operacionais neste contexto trazem
novos desafios na busca de um algoritmo eficiente para a resolução deste problema (veja
[44] para um compêndio sobre aplicação de Algoritmos Genéticos na indústria de petró-
leo).
Os problemas em redes de escoamento de petróleo foram pouco investigados. Em
[42], por exemplo, Algoritmos Genéticos são utilizados juntamente com programação
linear para alcançar um fluxo quase constante de óleo na entrada da estação de tratamen-
to de óleo de uma malha de escoamento. Os Algoritmos Genéticos foram utilizados para
determinar que bombas seriam ligadas/desligadas. Um indivíduo neste problema é repre-
sentado por um vetor de apenas 16 variáveis de decisão, com cada variável representando
uma bomba do sistema. O número de bombas deste problema é portanto bem menor do
30
que o do problema da malha de escoamento da UN-RNCE (em torno de 250 bombas), o
que reduz bastante o tempo de processamento necessário para alcançar uma solução óti-
ma para este problema. Um outro aspecto é que cabe ao Algoritmo Genético determinar
apenas se a bomba estará ligada ou desligada num determinado intervalo de tempo, fi-
cando a cargo do método de programação linear determinar quanto de vazão as bombas
de rotação variável, que estiverem ligadas, colocarão no sistema. As restrições do pro-
blema foram mapeadas na função de aptidão8, em forma de penalidades, de maneira a
beneficiar as soluções que além de contribuírem para a menor variação no fluxo de en-
trada, também reduzam a quantidade armazenada nos tanques e a pressão nos dutos.
A escolha do algoritmo apropriado para a otimização depende bastante das carac-
terísticas físicas do sistema que se deseja otimizar. Os Algoritmos Genéticos se apresen-
tam como uma boa solução para otimização de redes de escoamento devido ao tamanho
do espaço-solução a ser explorado e a não-linearidade do problema, pois além de não
terem nenhum requisito de linearização ou cálculo de derivadas parciais, trabalham com
amostras globais, ao invés de seguir um único caminho a partir de um ponto inicial, o que
aumenta as chances de convergir num ótimo global.
8 A função de aptidão avalia o quão bem um indivíduo se adapta ao ambiente, em outras palavras
ela diz quão boa é a solução.
31
4 Algoritmos Genéticos
Inspirados nos princípios da evolução biológica de Charles Darwin, em que indi-
víduos mais aptos estão mais capacitados a sobreviver e gerar descendentes pela própria
seleção natural, perpetuando suas características através da hereditariedade, os Algorit-
mos Genéticos são uma versão simplificada do que se passa na natureza. Durante a re-
produção, genes dos pais se combinam para formar um novo indivíduo. O descendente
criado pode eventualmente sofrer mutação, resultado principalmente de erros na cópia
dos genes dos pais, o que possibilita a incorporação de novo material genético a uma
população, e o reaparecimento de alguma característica que possa ter desaparecido ao
longo da evolução. A aptidão do indivíduo da população é medida pelo sucesso do orga-
nismo na sua vida, suas chances de sobrevivência. Os indivíduos mais aptos, que sobre-
vivem por mais tempo na população têm, portanto, maiores chances de gerar descenden-
tes e, por conseguinte, perpetuar as suas características na população.
Os primeiros estudos e refinamentos das idéias de utilização dos princípios da se-
leção natural e da evolução em algoritmos de busca culminam com a publicação do livro
“Adaptation in Natural and Artificial Systems” por John Holland em 1975. Nas últimas
décadas os Algoritmos Genéticos vêem sendo amplamente utilizados na solução de pro-
blemas nas mais diversas áreas do conhecimento que visam a encontrar um indivíduo ou
um conjunto de indivíduos que melhor se adeqüem a uma série de condições ambientais
previamente estabelecidas. Estes problemas se concentram nas áreas de elaboração de
escalas de alocação de salas, tarefas e recursos humanos, problemas de timetable, seleção
de rotas e configuração de sistemas complexos [15].
4.1 Estrutura do Algoritmo Genético
A implementação de um Algoritmo Genético começa com a definição de uma
função objetivo que se deseja minimizar ou maximizar e uma população aleatória de
“cromossomos”, os quais representam possíveis soluções do problema a ser resolvido.
Durante o “processo evolutivo” essas estruturas são avaliadas segundo uma função de
aptidão e a elas são associadas uma probabilidade de reprodução, de tal forma que as
32
maiores probabilidades são atribuídas aos cromossomos que representam uma melhor
solução para o problema de otimização.
Os indivíduos com maior aptidão são escolhidos através de operadores que imi-
tam o processo de seleção natural da natureza. Os que levam a estados inviáveis do sis-
tema serão fortemente penalizados e muitas vezes descartados da população. Os indiví-
duos selecionados são modificados através de operadores genéticos de cruzamento e mu-
tação, gerando descendentes para a próxima geração a ser avaliada. Esse processo se re-
pete até que uma solução satisfatória seja encontrada. Estes procedimentos definem a
estrutura típica de um Algoritmo Genético, que pode ser observada na Figura 7.
População Avaliada
NovaPopulação
População Intermediária
Seleção
Elitismo
Operadores deReprodução
Início
Fim
Geração de uma novapopulação
Geração da População Inicial
Cálculo da Aptidão
Condição de paradasatisfeita?
Não
Sim
Início
Fim
Geração de uma novapopulação
Geração da População Inicial
Cálculo da Aptidão
Condição de paradasatisfeita?
Não
Sim
Figura 7 - Estrutura de um Algoritmo Genético
Considerando portanto a estrutura típica de um Algoritmo Genético, podemos a-
firmar que a escolha da estrutura e definição dos parâmetros de controle do algoritmo
incluem as seguintes decisões:
A forma mais apropriada de codificar o problema;
A função de aptidão a ser usada;
O tamanho da população a ser adotado;
33
A forma de gerar uma população inicial com possíveis soluções;
A forma como os cromossomos pais são escolhidos e os descendentes gerados,
incluindo decisões a respeito de seleção preferencial, cruzamento e mutação;
A forma como os indivíduos de uma população são substituídos e,
Critérios de parada do processamento.
Cada um destes aspectos diferencia um Algoritmo Genético de outro e são deter-
minantes na eficiência do algoritmo. Analisaremos a seguir cada um deles.
4.2 Codificação da solução A escolha da codificação que representa uma possível solução para o problema
tem grande impacto no desempenho da busca, já que o tamanho do indivíduo está dire-
tamente ligado ao tempo de processamento necessário para alcançar uma solução ótima.
Por esta razão, a codificação deve ser a mais simples e compacta que represente todo o
espaço de busca do problema tratado.
Tradicionalmente os Algoritmos Genéticos utilizam uma codificação na forma de
seqüência de bits. Esta representação facilita a aplicação dos operadores genéticos pa-
drões e tem uma similaridade maior com a representação genética de um ser vivo. Entre-
tanto, muitas outras formas de codificação são possíveis, entre elas a representação de
números inteiros e de números reais. Mesmo nestas representações é possível codificá-las
em representações binárias e após a aplicação dos operadores genéticos, decodificá-las
para o formato original para avaliação da função de aptidão, o que embora tenha o aspec-
to negativo das freqüentes conversões, que impactam no tempo de processamento, possi-
bilita utilizar operadores genéticos típicos de representações binárias.
Cada característica codificada é chamada de gene e o conjunto destes genes forma
um cromossomo, que representa matematicamente uma possível solução para o proble-
ma. Em geral, um cromossomo representa o conjunto de parâmetros da função objetivo.
Tomando como exemplo os cromossomos ilustrados na Figura 8, podemos observar vá-
rios tipos de codificação e problemas para os quais eles melhor se adequam. O cromos-
somo A utiliza uma codificação binária, que serve por exemplo, para representar solu-
ções no problema da mochila, que consiste em maximizar o valor dos objetos contidos
em uma mochila de capacidade limitada, dado que a cada objeto é atribuído um volume e
34
um valor. Os cromossomos B e C, por outro lado, utilizam uma codificação valorada,
com números reais e caracteres respectivamente. Na codificação valorada cada gene pode
assumir o valor de qualquer objeto relacionado ao domínio do problema, um número real,
uma seqüência de caracteres ou um objeto, e na maioria das vezes necessitam de opera-
dores de mutação e cruzamento específicos.
Cromossomo A 0 1 0 0 1 0 0 1 1 1 0
Cromossomo B 2.43 3.27 5.88 9.14 11.3
Cromossomo C Azul verde marrom azul Figura 8 - Codificação dos cromossomos
4.3 Geração da população inicial
Uma população inicial pode ser gerada de maneira aleatória, utilizando conheci-
mentos do domínio do problema, com regras que permitam uma distribuição homogênea
no espaço de busca, ou mesmo partindo de soluções previamente calculadas para o pro-
blema proposto.
Quando populações pequenas são utilizadas, a distribuição dos indivíduos no es-
paço de busca pode ser comprometida. Para evitar que regiões do espaço de busca não
sejam representadas, uma possibilidade é distribuir os cromossomos de forma eqüidistan-
te a partir de um ponto aleatório do espaço de busca, ou gerar apenas uma metade da po-
pulação de maneira aleatória e a outra metade gerar invertendo-se os valores dos indiví-
duos gerados aleatoriamente.
Alguns problemas permitem que durante a configuração inicial da população, se
faça uso de conhecimentos do domínio do problema para gerar apenas soluções possíveis
(viáveis). Em algoritmos que visam, por exemplo, maximizar o retorno de uma carteira
de investimentos, sabendo-se que a soma dos percentuais investidos em cada uma das
diferentes ações que compõem a carteira não pode ultrapassar 100%, pode-se descartar
ou corrigir um cromossomo que não esteja em conformidade com esta restrição, evitando
que soluções sabidamente inválidas sejam inseridas na população inicial. Isto pode ser
observado na Figura 9, onde o cromossomo A não é uma solução válida para o problema,
já que a soma dos percentuais investidos em cada uma das ações da carteira supera os
35
100%. Este cromossomo tanto poderia ser descartado como corrigido, gerando, por e-
xemplo, o cromossomo A’ apto a ser incorporado na população (ver Figura 9).
Ação A Ação B Ação C
Cromossomo A 25% 32% 73%
Ação A Ação B Ação C
Cromossomo A’ 25% 32% 43%
Figura 9 - Reparo de um cromossomo
Outras abordagens inserem já nos cromossomos iniciais características mais dese-
jáveis ou mesmo soluções já conhecidas para o problema. Em problemas de otimização, é
comum partir de soluções previamente calculadas por um outro método de maneira que
se aumente a possibilidade de encontrar algo melhor do que já se tem, em uma técnica
chamada de seeding [27].
4.4 Cálculo da aptidão A função de aptidão calcula a adequação de um indivíduo em relação ao problema
proposto, e representa as chances desse indivíduo ser selecionado para fazer parte do
processo reprodutivo. A função de aptidão pode considerar um único objetivo, ou pode
agregar várias metas e restrições. Em muitos casos ela pode ser a própria função objetivo.
Em outros, onde a função objetivo fornece valores negativos, inadequados para alguns
métodos de seleção, ou fornece valores muito próximos entre os indivíduos da população
ou muito elevados para um pequeno grupo destes indivíduos, se faz necessário mapear a
função objetivo em valores de aptidão utilizando uma função de aptidão distinta da fun-
ção objetivo.
A aptidão é calculada pela aplicação da função de aptidão sobre as variáveis de
decisão do problema e fornece um valor único. Este valor é uma medida da proximidade
da solução em relação ao conjunto de parâmetros (objetivos) que se tenta otimizar. Os
36
objetivos que se deseja otimizar podem ser conflitantes, ou seja, quando um aumenta o
outro diminui. Por exemplo, ao tentar reduzir o de custo de produção e aumentar a quali-
dade do que é produzido, temos claramente objetivos divergentes. O objetivo é encontrar
o ponto ótimo, ou um conjunto de soluções que sejam as soluções de “melhor compro-
misso” entre os objetivos considerados, em que não há uma solução melhor que a outra,
mas apenas uma relação de compromisso entre os diversos objetivos.
Muitas vezes uma função de penalidade é utilizada embutida ou combinada à
função objetivo como forma de calcular a aptidão dos indivíduos inviáveis que possam
conter informações importantes para gerar um indivíduo viável. Tipicamente uma função
de aptidão com restrições tem a forma
∑ =+=
n
j j xzrxhxf1
)()()( (30)
Em que: h(x) é a função objetivo,
r é a constante de penalidade,
e zj(x) é a função de penalidade associada à restrição j do problema.
Em problemas cuja função de aptidão demande um custo computacional elevado,
o algoritmo deve preocupar-se em não reavaliar indivíduos previamente avaliados e que
não tenham sofrido alterações (cruzamento e mutação) de uma geração para outra. O
algoritmo pode também possuir mecanismos que mantêm resultados parciais previamente
calculados que possam ser reutilizados em avaliações futuras ou até mesmo utilizar
funções de aptidão mais simples nas primeiras gerações, a fim de identificar as regiões de
busca promissoras e só depois avaliar com a função de aptidão desejada [23] [43].
4.5 Seleção Ao final da avaliação da população, os indivíduos são selecionados para reprodu-
ção pela sua aptidão. Utilizando algum critério de seleção, promove-se a sobrevivência
dos indivíduos mais adaptáveis, com o sacrifício dos menos aptos, que terminam desapa-
recendo. Os indivíduos selecionados formarão uma população intermediária, também
chamada de matepool, que é o conjunto de indivíduos que combinados através de opera-
dores genéticos formarão a próxima geração de indivíduos que será avaliada.
Um aspecto importante a ser considerado é o número de cópias de um mesmo in-
divíduo na população intermediária. Quando se trabalha com populações pequenas, em
que exista uma grande discrepância entre os valores resultantes da aplicação da função de
37
aptidão em uma pequena parte dos indivíduos da população, estes indivíduos com apti-
dão muito acima da média dominarão a população causando a convergência prematura.
Por outro lado, nos casos em que os valores resultantes da aplicação da função de aptidão
sob os indivíduos da população assumam valores muito próximos, a busca pode se tornar
essencialmente aleatória pela dificuldade de se distinguir entre os membros medianos e
os acima da média, necessários para que haja evolução no decorrer das diversas gerações.
Nestes casos é necessário mapear os valores da função objetivo em aptidão utilizando
uma função de escalonamento da aptidão de forma a possibilitar uma seleção mais equi-
librada.
O mapeamento do resultado da avaliação da função objetivo para valores de apti-
dão permite que se regule os níveis de competição entre os diversos membros da popula-
ção, através do ajuste da pressão de seleção - probabilidade de o melhor indivíduos ser
selecionado comparada à probabilidade média de seleção dos demais indivíduos, e pode
ser feito utilizando diversos métodos de escalonamento de aptidão, dentre eles se desta-
cam o método de ordenamento linear [4] e o método de ordenamento exponencial [13].
Estes métodos ordenam a população de acordo com os valores de aptidão de cada indiví-
duo. A probabilidade de seleção atribuída a cada um dos indivíduos depende somente de
sua posição na classificação dos indivíduos da população e não da magnitude da aptidão.
Estes métodos introduzem uma função de escalonamento uniforme através da população
e fornece uma maneira simples e eficaz de controlar a pressão de seleção, comportando-
se de forma mais robusta que métodos que atribuem chances de reprodução a um indiví-
duo proporcional a sua aptidão [2]. Observe na Tabela 15, que para os mesmos indiví-
duos temos probabilidades de reprodução diferentes dependendo de como atribuímos a
aptidão ao indivíduo, seja pela magnitude da sua aptidão, seja pela sua posição relativa
dentro da população. Observe que o indivíduo com maior aptidão teve sua fatia reduzida
enquanto que o de menor aptidão teve um crescimento quanto utilizamos a posição rela-
tiva na população para definir a aptidão. As chances do primeiro indivíduo ser escolhido
em relação ao segundo (os indivíduos de menor e maior aptidão, respectivamente) é de
46,87:6,25, usando o valor real da aptidão ou de 40:10, quando se considera a posição na
população.
Dentre os métodos de seleção, um dos mais populares é o método da roleta [16].
O método da roleta consiste em distribuir os indivíduos em fatias de uma roleta de tama-
nho proporcional à sua aptidão. A roleta possue uma única paleta, que será girada n ve-
38
zes, onde n representa o número de indivíduos da população intermediária. Desta forma,
os indivíduos que possuem as mais altas aptidões e por conseguinte uma fatia maior da
roleta, têm mais chances de serem selecionados. Vejamos por exemplo o caso de termos
indivíduos e uma função de aptidão hipotética, cuja probabilidade de seleção são apre-
sentadas na Figura 10. O indivíduo de número quatro terá a maior fatia da roleta e conse-
qüentemente a maior chance de ser escolhido para fazer parte do matepool. O método da
roleta tem uma alta pressão de seleção, que está diretamente relacionado com a diversi-
dade da população.
Tabela 15 - Dados de aptidão de um problema hipotético
No Indivíduo Função
objetivo
Apt. proporcional ao
valor da função obje-
tivo %
Apt. em relação à
posição na popula-
ção %
1 000100 6 6,25 10
2 100011 45 46,87 40
3 111111 28 29,17 30
4 101100 17 17,71 20
Total 96 100 100
A amostragem estocástica universal (SUS, Stochastic Universal Sampling) pro-
posta por Baker [4], é um método de seleção semelhante ao da roleta. No SUS a popula-
ção também é representada por um gráfico em forma de roleta onde o tamanho de cada
uma das marcações na roleta é proporcional à aptidão do cromossomo que ela representa.
Diferentemente do método da roleta, no SUS o marcador, formado por Q paletas eqüidis-
tantes, e os Q indivíduos na nova população são selecionados em um único giro do mar-
cador, como apresentado na Figura 10. Esse método é uma melhoria do método da roleta,
uma vez que mantém a diversidade e previne que as características dos indivíduos com
mais alta aptidão dominem a população [18], já que dá chance a indivíduos menos aptos
a permanecerem na população e poder fazer parte da formação da nova geração. Vale
ressaltar que neste método um indivíduo pode ter mais de uma cópia na população inter-
mediária, como podemos observar no caso dos indivíduos nas fatias 1 e 4 da Figura 10.
39
1
2
3 4
...
P
P-1
Figura 10 - Amostragem estocástica universal
4.6 Operadores de reprodução
Os operadores de reprodução geram novos indivíduos a partir dos indivíduos se-
lecionados para compor a população intermediária. O operador de cruzamento (crosso-
ver) cruza parte de dois indivíduos, trocando parte de suas informações genéticas e ge-
rando dois novos indivíduos, como podemos observar na Figura 11.
Pai 1
0 1 1 1 1 Pai 2
1 1 1 0 1
Filho 1 0 1 1 0 1
Filho 2 1 1 1 1 1
Pai 1
0 1 1 1 1 0 Pai 2
1 1 1 0 1 1
Filho 1 0 1 1 0 1 0
Filho 2 1 1 1 1 1 1
Figura 11 - Cruzamento de cromossomos em um e dois pontos
Se considerarmos que o bom desempenho de um cromossomo é devido aos blo-
cos de construções com alta aptidão, o operador de cruzamento fornece meios de combi-
nar estes blocos de construção de alta aptidão e assim conduzir a soluções com aptidão
ainda mais alta.
40
O operador de mutação por sua vez, altera informações genéticas pontuais em um
cromossomo, e desta forma contribui para que informações genéticas novas possam ser
introduzidas na população ou mesmo que características perdidas voltem a reaparecer,
garantindo a diversidade genética da população. Na Figura 12 o operador de mutação é
aplicado a um cromossomo formado por uma cadeia de bits e um gene do cromossomo é
invertido de zero para um. A quantidade de genes que sofre mutação e a forma como ela
se dá depende tanto da representação adotada quando do comprimento do indivíduo.
Original
0 1 1 1 1
mutação
Modificado 1 1 1 1 1
Figura 12 - Operador de mutação
4.7 Parâmetros de controle do algoritmo As taxas para os operadores de reprodução, assim como o tamanho da população,
são parâmetros genéticos que influem no comportamento dos algoritmos. A análise da
influência de cada um dos operadores é importante para que se possa definir as taxas de
reprodução correspondentes conforme as características do problema e dos recursos dis-
poníveis [1][11][17][20].
Populações grandes possibilitam uma melhor exploração do espaço de busca e e-
vitam a convergência prematura num ótimo local, mas implicam num tempo maior de
processamento. As populações pequenas, por outro lado, oferecem uma pequena cobertu-
ra do espaço de busca. Em geral o tamanho das populações varia entre 50 e 200 indiví-
duos.
A taxa ou probabilidade de cruzamento determina as chances de que dois indiví-
duos escolhidos para a reprodução venham a se recombinar. Usualmente a taxa de cru-
zamento é superior a 60%, chegando muitas vezes a 100% e igual para todos os indiví-
41
duos da população [30][20]. Caso os indivíduos não sejam recombinados, serão inseridos
na população inalterados [16][20].
O número de genes que sofre mutação e a forma como ela se dá depende tanto da
representação adotada quando do comprimento do indivíduo. O operador de mutação é
aplicado aos indivíduos com uma probabilidade dada pela taxa de mutação que em geral
varia numa faixa pequena entre 0,1% e 3% [20][18][16]. As taxas de cruzamento influ-
enciam a velocidade com que novas estruturas são introduzidas na população e conse-
qüentemente a velocidade da evolução. Taxas muito altas podem causar a perda de indi-
víduos de alta aptidão, enquanto que taxas muito baixas deixam o algoritmo muito lento.
A mutação, responsável pela reintrodução de características que possam ter sido
perdidas durante a evolução na população, deve se manter em uma taxa baixa para evitar
que a busca se torne essencialmente aleatória.
Ao gerarmos novos indivíduos utilizando os operadores de cruzamento e mutação
podemos perder o melhor indivíduo obtido até aquele momento. Para melhorar o desem-
penho do Algoritmo Genético é importante evitar que isto ocorra. DeJong [8] propôs um
operador que preserva o melhor indivíduo de uma população, levando-o sem alteração
para a próxima geração. Os estudos de DeJong [8] sugerem que a introdução deste indi-
víduo melhora a busca local, mas em contrapartida prejudica a busca mais abrangente no
espaço solução. Está técnica é chamada de elitismo e é largamente utilizada.
4.8 Estratégia de reposição
A forma como a reposição dos indivíduos de uma geração para outra se dá, define
os dois tipos principais de Algoritmos Genéticos: os geracionais, que a cada passo substi-
tuem todos os indivíduos de uma geração pelos indivíduos gerados por estes indivíduos
através de cruzamento e mutação, e os em regime (steady-state) que substituem um pe-
queno número dos indivíduos de uma população, conforme uma estratégia de reposição
estabelecida [13]. Nos algoritmos steady-state em geral são criados n filhos que substitu-
em os n piores pais e em geral a taxa de crossover aproxima-se de 100% [13]. A primeira
abordagem geralmente é acrescida de um operador de elitismo, para garantir que o me-
lhor indivíduo não seja perdido entre uma geração e outra. Variações entre estes dois
extremos também são encontradas na literatura.
42
4.9 Critérios de parada
Os Algoritmos Genéticos finalizam sua execução quando um número pré-definido
de gerações é atingido, o tempo máximo para execução do algoritmo é atingido, ou pela
convergência do algoritmo, que se dá quando não há melhoras significativas nos valores
obtidos para a função objetivo por um certo número de gerações, ou mesmo quando toda
a população possui uma certa porcentagem de genes com o mesmo valor, o que caracteri-
za um processo de estagnação do processo evolutivo.
O desaparecimento de algumas características genéticas ao longo do processo de
otimização pode levar o algoritmo a restringir sua busca em torno de um máximo ou mí-
nimo local, e acabar por convergir em uma solução não ótima. A este problema dá-se o
nome de convergência prematura. A convergência prematura se dá quando indivíduos de
alta aptidão, quanto comparados com o restante da população, são escolhidos com mais
freqüência para participar do processo reprodutivo, pelos próprios critérios da seleção
natural, o que causa o aparecimento de muitos indivíduos com características semelhan-
tes, reduzindo a diversidade genética, e levando a uma convergência do algoritmo nas
vizinhanças desses superindivíduos. Estes indivíduos embora tenham uma alta aptidão
podem não estar na região do ótimo global [13].
Para evitar este comportamento indesejável do algoritmo, pode-se aumentar a taxa
de mutação, que reduz a possibilidade de convergência prematura, pois possibilita a bus-
ca em diversas regiões do espaço de busca, além de possibilitar o reaparecimento de al-
gum gene que tenha por ventura desaparecido da população devido à superioridade das
características contidas num determinado cromossomo que não carrega esta característi-
ca. Outra possibilidade é reduzir a participação dos superindivíduos no processo reprodu-
tivo, seja por medidas que restrinjam a possibilidade de se ter cromossomos iguais na
população ou pela utilização de funções de escalonamento da aptidão.
43
4.10 Princípios e funcionamento
Um bom algoritmo de busca deve tanto explorar uma vasta região de soluções, ou
seja, sempre buscar pontos novos no espaço de busca a fim de evitar que se fique preso a
um região de um ótimo local, o que é conhecido por exploration; quanto utilizar as in-
formações oriundas das melhores regiões visitadas para fazer uma busca no entorno -
exploitation.
Nos Algoritmos Genéticos, os operadores de reprodução – mutação e cruzamento
– fazem exploration enquanto que o método de seleção dirige a busca para os melhores
pontos do espaço de busca - exploitation.
A pressão de seleção é dada pela razão entre a aptidão máxima e a aptidão média
da população, e influencia diretamente o comportamento exploratório dos Algoritmos
Genéticos. Quando a pressão de seleção é muito baixa, ou seja, não há uma grande varia-
ção na aptidão dos indivíduos, o algoritmo adquire um comportamento quase que aleató-
rio, o que não é desejável. Por outro lado, se a pressão de seleção for muito alta o algo-
ritmo tem um comportamento semelhante ao dos algoritmos do tipo subida de encosta. O
Algoritmo Genético deve ser configurado de maneira a estabelecer uma pressão de sele-
ção que evite tanto que a busca se torne apenas exploratória, o que levaria a um compor-
tamento de busca aleatório, quanto que a busca se restrinja a uma pequena área do espaço
de busca, culminando em soluções pobres (ótimos locais).
44
5 Adaptando o Algoritmo Genético
Neste capítulo apresentamos o algoritmo proposto para a resolução do problema
apresentado no Capítulo 2. A apresentação do algoritmo será feita de forma incremental,
apontando as transformações feitas no Algoritmo Genético canônico, para alcançar um
escalonamento de bombas otimizado dentro do tempo limite imposto pela aplicação.
No decorrer do capítulo destacamos os resultados alcançados, e os problemas en-
frentados na aplicação de um Algoritmo Genético padrão num problema complexo como
o abordado neste trabalho.
5.1 Codificação do problema
No problema tratado, a função que se deseja minimizar é o custo de energia con-
sumida pelo volume de petróleo bombeado para a estação de tratamento da malha em um
dado horizonte de operação. O horizonte de operação é discretizado em intervalos, cha-
mados de intervalos de atuação, onde se dá a programação da operação das bombas. Ca-
da cromossomo da população consiste em uma solução para o escalonamento temporal
das bombas, em que cada gene assume os valores 0 (desligado) ou 1 (ligado), que repre-
sentam se uma determinada bomba B está em operação ou não em um dado intervalo de
atuação ∆t, formando uma matriz bi-dimensional tempo versus bomba, como apresentada
na Figura 13. Cada linha da matriz representa uma bomba da rede de escoamento que se
deseja otimizar e as colunas, os intervalos de atuação ∆t, que são o menor intervalo entre
uma alteração de um estado das bombas. Somados, os intervalos de atuação formam o
horizonte de operação.
45
1 0 ∆t1 ∆t2 ... ... ∆tn 1
B1 1 0 1 0 ... 0 1 0 1 Bm 1 1 1 1
... ... 1 0 1
Figura 13 - Representação de um cromossomo
Um cromossomo representado como uma matriz bidimensional m x n pode ser
reorganizado de forma que tenhamos uma estrutura vetorial, sem que haja perda de in-
formação. Cada coluna seria disposta sequencialmente nessa nova estrutura. A opção
pelo uso de uma estrutura matricial se deve ao aumento da clareza, pois mantemos a se-
mântica do problema ao preservarmos o sentido temporal da estrutura, e a facilidade de
manipulação, já que podemos aplicar os operadores genéticos tradicionalmente utilizados
em representações vetoriais.
5.2 Função de aptidão
Inicialmente a aptidão foi calculada como a própria função objetivo. As variáveis
de estado correspondem ao estado de cada uma das bombas do sistema em um determi-
nado instante, podendo assumir dois valores: ligada ou desligada. O algoritmo visava,
portanto, encontrar os valores dessas variáveis que minimizem o resultado da função
entregueVCustoTSfo = em que,
CustoTS é o custo total de energia consumida durante todo o horizonte de opera-
ção, que é resultado da soma do custo total da energia consumida durante o horizonte de
operação com o custo total da demanda no mesmo período [R$];
entregueV é o total de volume entregue na estação de tratamento final durante todo o
período de otimização [m3];
46
Tendo em vista que o controle é obtido levando-se em consideração uma previsão
de produção de petróleo arbitrada, que pode vir ou não a se concretizar, a função objetivo
foi alterada para levar em consideração mais este fator, e minimizar a possível perda que
alguma das partes, no caso as diversas unidades administrativas responsáveis pela opera-
ção de cada um dos ativos da malha, possa ter devido a incertezas na previsão da produ-
ção.
A nova função de aptidão, ponderada no tempo, atribui pesos maiores para a pro-
dução bombeada nos intervalos iniciais do horizonte de operação. Como uma estratégia
de controle que envolve vários participantes e interesses conflitantes, a função de aptidão
deve privilegiar soluções cujo ganho alcançado nos primeiros intervalos do escalonamen-
to sejam maiores que aqueles obtidos ao final, considerando-se que os participantes pre-
ferem não arriscar seus ganhos, deixando-os para um período mais distante no futuro, sob
pena de que incertezas na previsão da produção, no modelo de simulação e nos sistemas
de aquisição de dados, tornarem o escalonamento previsto para aquele dado momento
não factível, e o participante ter seu momento de ganhos novamente adiado.
O algoritmo utiliza portanto uma função objetivo ponderada no tempo, dada pela
seguinte equação:
iin
iPV
CustoTSfo∑=
=1
em que, (31)
Custo é a soma do valor gasto com energia elétrica para aquela programação de
liga/desliga, em reais [R$],
n corresponde ao número de intervalos no horizonte de operação que está sendo
otimizado,
Vi é o volume entregue na estação de tratamento final no intervalo i, em m3, e
Pi é um fator de ponderação, que obedece à seguinte relação: Pi ≥ Pi+1.
O fator de ponderação foi estimado em 1,2, o que corresponde a um aumento de
20% no volume bombeado, aplicado no primeiro ¼ do horizonte de operação. A cada
novo ¼ do horizonte, o fator de ponderação é subtraído em 0,05.
47
5.3 Tamanho da população
Os estudos iniciais de Goldberg [17] a respeito do tamanho ideal para uma popu-
lação de cromossomos determinavam que em indivíduos codificados na forma de se-
qüências binárias, a população deveria crescer exponencialmente com o comprimento da
seqüência. Isto tornaria as populações em problemas como o que estamos tratando enor-
mes, e os Algoritmos Genéticos pouco eficientes para a solução destes problemas. Resul-
tados empíricos de estudos posteriores mostraram bons resultados para problemas com-
plexos com populações entre n e 2n, onde n é o comprimento da seqüência binária [1].
Apesar destas recomendações, questões relativas ao tempo de processamento necessário
para avaliar uma geração do algoritmo, nos fez reduzir a faixa de testes de tamanho da
população para valores até n.
O comprimento da representação de uma solução para o problema varia com o
tamanho do horizonte de operação, o intervalo de atuação e o número de bombas. A de-
terminação do tamanho ideal para a população foi feita através de experimentos com di-
ferentes tamanhos de população, em uma otimização com comprimento do indivíduo, n,
de 192 (24h x 30 min x 4 bombas)9. Tabela 16- Parâmetros de controle do experimento
Parâmetro Valor
Tamanho da população 20-200 Taxa de seleção para população intermediária 50% Taxa de cruzamento 90% Taxa de mutação 10% Critério de parada 24h
Optamos por variar numa faixa de 20 a 200 indivíduos, e estabelecer um critério
temporal para parada do algoritmo, a população intermediária era formada por 50% dos
indivíduos da população, e a melhor solução a cada geração era preservada (Tabela 16).
Não consideramos o tamanho de população que convergiria para a solução de mais alta
qualidade caso fosse dada a chance de evoluir pelo mesmo número de gerações, e sim,
9 Utilizamos neste experimento uma malha reduzida, com apenas quatro estações coletoras e
quatro bombas. Estes experimentos foram conduzidos antes que tivesse sido identificado o trecho da malha que utilizaríamos como piloto.
48
aquela que alcançaria, dentro do prazo estabelecido de 24h, a melhor solução. Populações
maiores não foram consideradas devido ao custo computacional da função objetivo que
está sendo avaliada e, por conseguinte, o tempo necessário para avaliar uma única gera-
ção ser muito elevado.
O gráfico da Figura 14 mostra o resultado obtido com populações de 20, 50 e 200
indivíduos para o mesmo tempo de processamento. A população de 200 indivíduos al-
cançou a pior solução dentro do prazo que foi estabelecido. Embora uma população mai-
or contribua para uma maior diversidade, devido ao tempo estrito que temos para otimi-
zar não foram consideradas as possíveis melhorias que uma população com 200 indiví-
duos alcançaria caso evoluísse pelo mesmo número de gerações que as demais popula-
ções. As populações com 20, 50 e 200 indivíduos alcançaram resultados muito próximos
(0,002089508 R$/m3, 0,001897773 R$/m3 e 0,002178901 R$/m3, respectivamente), to-
davia, os resultados da população com 50 indivíduos são melhores que a de 20 indivíduos
e, considerando que a população é bem maior, possibilitará uma melhor exploração do
espaço de soluções, por outro lado, e por esta razão foi o tamanho de população que ado-
tamos no algoritmo.
0,0015
0,0017
0,0019
0,0021
0,0023
0,0025
0,0027
0,0029
1 19 37 55 73 91 109 127 145
Número de Gerações
Cus
to (R
$/m
3) População de 20indivíduos
População de 50indivíduosPopulação de 200indivíduos
Figura 14 - Determinando o tamanho da população
49
5.4 Algoritmo Genético canônico
O Algoritmo Genético canônico ou SGA (Simple Genetic Algorithm) apresentado
por David Goldberg no livro “Genetic Algorithms in search, optimization, and machine
learning” [16] é utilizado na resolução de problemas em diferentes domínios de aplica-
ção. Algoritmos canônicos são todos os algoritmos que obedecem aos princípios do algo-
ritmo proposto por Holland, incluindo aí o algoritmo de DeJong [8], que servem como
comparativo e ponto de partida de diferentes implementações de um Algoritmo Genético
[48].
No Algoritmo Genético canônico cada membro da população é representado por
uma cadeia de caracteres binários de comprimento pré-definido. A população inicial é
gerada de maneira aleatória. Neste algoritmo a aptidão é definida por ff i / , onde é o
valor da função objetivo aplicado ao indivíduo i, e
if
f é a média do valor obtido com a
avaliação de todos os indivíduos da população (pode-se também utilizar uma aptidão
referente a posição do indivíduo na população). Após calcular a aptidão de todos os indi-
víduos é feita a seleção dos indivíduos que formarão a população intermediária. A esco-
lha é feita de forma que a ocorrência de um indivíduo na população intermediária seja
proporcional a sua aptidão. Utilizamos o método de amostragem estocástica universal
(SUS) para a seleção dos indivíduos para reprodução.
Escolhidos os indivíduos que comporão a população intermediária, inicia-se o
processo de reprodução utilizando um operador de cruzamento. O operador de cruzamen-
to escolhe dois cromossomos pais aleatoriamente na população, e combina-os em um
único ponto de troca. Após o cruzamento, um operador de mutação é aplicado. Para rea-
lizar a mutação em uma solução, é escolhido um intervalo de tempo aleatório e são modi-
ficados os estados de 10% das bombas da malha para esse intervalo. Nos casos em que
10% das bombas correspondam a um valor menor que um, o estado de uma bomba é alte-
rado. As bombas cujo estado é alterado são escolhidas aleatoriamente. Relacionar o nú-
mero de pontos a serem mutados ao número de bombas da malha é importante, pois per-
mite que em malhas com um conjunto de bombas grande por estação, onde o efeito de
ligar ou desligar apenas uma bomba não seria muito significativo, o estado de um número
maior de bombas seja alterado. Isto acelera a busca na vizinhança proporcionada pela
mutação.
50
Quando o Algoritmo Genético canônico foi aplicado ao problema proposto, con-
sideramos na função objetivo apenas a relação do custo com energia elétrica pelo volume
de fluido bombeado para a estação de tratamento da malha de escoamento e atribuímos
uma penalidade proporcional à posição do primeiro ponto da falha dada pela seguinte
equação:
, se não houver falhas )(xf
=)(xf )1/()( −× pfnxf , se pf > 1 (32)
0, se pf = 1
Em que é a função de aptidão do indivíduo x que se deseja minimizar, n é o
número total de intervalos de atuação da matriz de representação do individuo (número
de colunas), e pf, o intervalo de atuação no qual ocorre alguma violação a restrições do
problema.
)(xf
Tabela 17- Parâmetros de controle
Parâmetro Valor
Tamanho da população 50 Tamanho da população intermediária 25 Taxa de cruzamento 90% Taxa de mutação 10% Critério de parada 20 min
Os primeiros experimentos foram feitos em malhas com um número muito redu-
zido de bombas (4 bombas) e para horizontes de operação de poucas horas, com resulta-
dos satisfatórios. O Algoritmo Genético foi capaz de encontrar soluções viáveis, partindo
de soluções inviáveis, para horizontes de operação de 3h com intervalos de atuação de 30
min. Todavia, ao utilizar horizontes de operação mais realistas, em torno de 24h, os desa-
fios presentes no problema afloraram. O grande número de restrições violadas pelas solu-
ções e a incapacidade de sair das regiões de inviabilidade faziam com que o algoritmo
convergisse em soluções de baixo custo, mas operacionalmente inviáveis. Para nossa
malha exemplo (detalhes na seção 2.5), utilizando a função de aptidão da equação (32),
descrita acima, os parâmetros de controle da Tabela 17, e um horizonte de operação de
24h, a solução viável encontrada pela regra de operação padrão (ver detalhes na Seção
51
5.8) tinha um custo de 0,1583 R$/m3, o algoritmo canônico obteve seu melhor resultado
num experimento em que o custo da solução encontrada foi de 0,1317 R$/m3, o que re-
presenta uma redução de 16,8% no custo operacional padrão, contudo a solução encon-
trada era inviável e tinha sua primeira falha no décimo quarto intervalo de atuação, vio-
lando a pressão máxima admissível nos dutos. O algoritmo precisava ser guiado para sair
das regiões de inviabilidade e técnicas de tratamento de restrições foram incorporadas.
5.5 Tratando as restrições do problema
As técnicas de inicialização, cruzamento e mutação dos Algoritmos Genéticos ga-
rantem genes dentro do domínio de cada variável. Para o problema tratado, garantimos
que a matriz gerada será formada por elementos 0 e 1. Todavia, essas operações não ga-
rantem que os cromossomos satisfaçam determinadas restrições e não é trivial descobrir
a priori se as soluções serão viáveis ou não. Para aumentar as chances de termos indiví-
duos viáveis na população, utilizamos algumas técnicas conhecidas para lidar com pro-
blemas com restrições e propomos algumas variantes dos operadores de reprodução para
aumentar as chances de gerar um indivíduo viável.
5.5.1 Função de penalidade
A forma mais comum de tratar a inviabilidade das soluções é penalizando-as. A
maneira de trabalhar com a penalidade é adicioná-la ao grau de aptidão de uma solução
em problemas de mínimo e subtraí-la em problemas de máximo. Esta função impõe pe-
nalidades criando uma classificação onde as avaliações das soluções viáveis sejam sem-
pre mapeadas para valores melhores que as soluções não viáveis. Ou seja, a pior solução
viável é melhor que a melhor solução inviável [31].
No caso do problema em estudo, para que uma função de penalidade fosse utili-
zada seria necessário mapear as violações das restrições em uma equação matemática,
cujo resultado seria adicionado ao valor calculado para a função de aptidão de cada indi-
víduo. A dificuldade de implementação está na determinação de uma boa equação para
representar todas as restrições do sistema e a calibração desta função.
52
Optamos por, ao invés de utilizar uma função de penalidade, classificar as restri-
ções do problema por ordem de severidade (Tabela 18). Relacionamos tanto a restrição
quanto a posição na matriz em que ocorre a falha, com uma maior ou menor aptidão de
um indivíduo. Desta forma ao compararmos duas soluções inviáveis, aquela cuja falha
está mais próxima ao final do horizonte de operação, é considerada superior em relação a
outra. Caso o ponto de falha recaia na mesma posição nas duas soluções, aquela que vio-
lou a restrição de menor severidade será considerada mais apta. Por fim, caso a soluções
tenham o mesmo ponto de falha e violem a mesma restrição, aquela que tem o menor
custo será considerada melhor.
Tabela 18 - Restrições e grau de severidade
Restrição Violada Severidade
Tanque produtor atinge o nível máximo Alta Tanque produtor atinge o nível mínimo Baixa Tanque receptor atinge o nível máximo Alta Duto atinge pressão máxima Alta Duto atinge pressão mínima Baixa Fluido atinge velocidade mínima em um duto Baixa Fluido atinge velocidade máxima em um duto Alta
Após classificarmos os indivíduos, em ordem crescente de aptidão, segundo os
critérios apontados, atribuímos uma aptidão relativa à sua posição na classificação. Mé-
todos que relacionam a probabilidade de seleção à posição de classificação do indivíduo
comportam-se de forma mais robusta que métodos que atribuem à probabilidade de sele-
ção valores proporcionais ao resultado direto da avaliação da função de aptidão [47].
Utilizando o método da classificação linear (ver Seção 4.5), com uma pressão de
seleção arbitrada em 2,0, a aptidão é dada por:
)1/()1(2)( −−= nposposAptidão (33)
Em que: pos é a posição de um indivíduo na população; e
n é o tamanho da população.
Para selecionar a população intermediária, utilizamos a amostragem estocástica
universal (SUS). Caso o melhor indivíduo seja selecionado pelos critérios do algoritmo
de seleção para fazer parte da população intermediária, o operador de elitismo não mais
inserirá uma cópia do mesmo, evitando que tenhamos uma superpopulação de um indiví-
53
duo de alta aptidão, o que comprometeria a exploração do espaço de busca pelo Algorit-
mo Genético.
5.5.2 Eliminação de soluções
O descarte de indivíduos inviáveis, conhecido como penalidade de morte, é uma
opção bastante utilizada em muitos Algoritmos Genéticos. Em um problema como o que
está sendo estudado, cuja possibilidade de gerar soluções inválidas é muito grande, como
foi verificado nos nossos experimentos preliminares, o descarte de todas as soluções in-
viáveis comprometeria o desempenho do Algoritmo Genético, já que uma população
gerada aleatoriamente poderia ser completamente inviável e, caso as soluções estejam
dispersas no espaço de busca e descartássemos todas para gerar novos indivíduos, o algo-
ritmo estaria seriamente comprometido, tanto do ponto de vista de tempo computacional,
como do aspecto evolutivo, já que não seria dada a possibilidade de se evoluir a partir de
soluções inviáveis para regiões de soluções viáveis [31].
Optamos por utilizar regras de descarte simples que, antes mesmo que a simula-
ção da operação ocorra, permitam verificar se uma solução desrespeita alguma restrição
operacional do problema. Caso ocorra a violação, descartar-se-ia o indivíduo da popula-
ção sem nem mesmo avaliá-lo. Dada a complexidade do problema, e a limitação de se
extrair regras genéricas de descarte, sem que seja necessário simular as soluções, apenas
uma regra de descarte está sendo utilizada.
A regra de descarte implementada é capaz de evitar soluções que resultem no
transbordo dos tanques produtores. A avaliação é simples: para cada tanque produtor, a
previsão da produção determina a vazão de entrada a ser considerada. A partir dessa va-
zão de entrada podemos calcular facilmente em quanto tempo o tanque enche, caso todas
as bombas associadas a ele estejam desligadas. As soluções que apresentem as bombas
associadas a esse tanque desligadas por um número de intervalos de atuação superior ao
tempo de enchimento calculado serão descartadas. Aplicando essa regra simples para
todos os tanques produtores, muitas soluções inviáveis geradas podem ser descartadas
antes da simulação para o cálculo da função objetivo, melhorando assim o desempenho
do otimizador, especialmente para sistemas de bombeio escoando uma produção elevada
para a capacidade da rede de dutos. Nos experimentos conduzidos num cenário de produ-
54
ção de baixa saturação, nas primeiras gerações o número de descartes representa em mé-
dia 6% dos indivíduos gerados, caindo rapidamente para 0% dos indivíduos e se manten-
do desta forma até o fim da otimização. Em um cenário saturado, a média de descartes
foi ligeiramente mais elevada, 8,23%, mas esta se manteve por toda a otimização, com
uma pequena queda nas gerações finais
A técnica de descarte de soluções deve ser utilizada em problemas onde há baixa
probabilidade de gerar soluções inviáveis pelos operadores genéticos. No problema trata-
do há uma alta probabilidade de se gerar indivíduos inviáveis, mas o alto custo computa-
cional da avaliação da função objetivo, juntamente com o fato de apenas uma pequena
porcentagem de soluções inviáveis serem detectadas pela regra do transbordo dos tan-
ques, justifica-se sua utilização, visto que o desempenho do Algoritmo Genético não é
comprometido pela necessidade de se gerar novas soluções para complementar a popula-
ção, nem tampouco, pelo comportamento aleatório que substituições em grande quanti-
dade gerariam.
5.5.3 Operadores genéticos modificados
Alguns problemas possuem um nível de restrições tão elevado que apenas classi-
ficar as soluções pelo seu grau de inadequação ou mesmo descartar as soluções inviáveis
não é suficiente para o algoritmo convergir em uma solução ótima em um tempo satisfa-
tório. O problema da otimização do escoamento da produção de petróleo aqui tratado é
um destes.
Ao contrário do que se poderia supor, as muitas restrições de um problema, que
reduzem em tamanho o espaço-solução e, por conseguinte, o número de soluções possí-
veis, o que faria a busca por uma solução uma tarefa mais simples, exige que tenhamos
operadores que não só sejam capazes de mover-se de uma solução viável para outra solu-
ção viável melhor, como sair de uma região de inviabilidade para uma região de soluções
viáveis.
Uma técnica bastante utilizada para lidar com restrições é a de reparo de soluções
[31]. Esta técnica corrige soluções que violam restrições com um algoritmo de reparo
específico. Dada a complexidade do problema tratado, um algoritmo para correção de
soluções seria computacionalmente intensivo, e por esta razão inviável. Optamos por
55
introduzir modificações nos operadores genéticos tradicionais. Essas modificações utili-
zam informações de pontos de violação das restrições na solução melhorando as chances
de se gerar indivíduos mais aptos.
Ao gerar novos descendentes os operadores de mutação e cruzamento direciona-
dos levam em consideração o conhecimento da posição, na seqüência de bits, onde a so-
lução não satisfez as restrições do problema. A mutação direcionada efetua a mutação
dois intervalos antes do ponto de falha. As bombas que serão mutadas naquele intervalo,
num total de 10%, são escolhidas aleatoriamente.
O cruzamento direcionado, o nosso operador modificado, funciona da seguinte
forma. Comparamos o ponto de falha dos dois cromossomos envolvidos na operação de
cruzamento, tomamos a posição daquele que falha mais prematuramente, retrocedemos
duas posições e neste ponto fazemos a troca, como mostra a Figura 15. O Pai 2 falha na
quinta posição enquanto que o Pai 1 falha na quarta, assim procedemos a troca após o
segundo intervalo, dois intervalos antes que a falha no do Pai 1. A decisão de retroceder
duas posições é arbitrária, não havendo qualquer dado experimental que indique que este
seja um valor ideal, e foi adotada pela necessidade de retroceder um número de intervalos
de atuação suficientes para que uma falha possa ser corrigida. Este retrocesso amplia as
chances da viabilidade do cromossomo filho, todavia não garante que o resultado da ope-
ração será um indivíduo viável.
Pai 1 0 1 1 1 1 1 1 1 1 1 0 1 0 0 1
Pai 2
1 1 1 0 1 0 0 1 1 1 1 0 1 0 1
Filho 1 0 1 1 0 1 1 1 1 1 1 0 1 1 0 1
Filho 2
1 1 1 1 1 0 0 1 1 1 1 0 0 0 1
Ponto de falha
Ponto de falha
Figura 15 - Cruzamento direcionado
No caso do ponto de falha ser logo no primeiro intervalo, ao invés de fazermos
um cruzamento direcionado, que não resolveria o problema da falha, submetemos o cro-
56
mossomo a uma mutação direcionada no primeiro intervalo do cromossomo, e depois a
um cruzamento convencional.
As soluções resultantes das operações de cruzamento direcionado e mutação dire-
cionada são avaliadas pela regra de descarte descrita na seção 5.5.2 . No cruzamento di-
recionado, como os pontos de falha dos cromossomos são fixos, a troca de genes é reali-
zada apenas uma vez. Se um dos filhos for descartado, novos pais são selecionados na
população intermediária. Na mutação direcionada, caso alguma inviabilidade seja detec-
tada em uma determinada solução, esta é descartada e a operação é realizada novamente.
O número de tentativas é limitado de acordo com o tamanho da matriz que representa a
solução. Se esse limite for atingido, um outro cromossomo é escolhido na população in-
termediária para que a mutação possa ser efetuada.
Quando comparamos o desempenho do Algoritmo Genético com os operadores
genéticos modificados com aqueles utilizando apenas operadores convencionais, obser-
vamos uma evolução mais rápida da posição dos pontos de falhas nos operadores modifi-
cados. O número de gerações necessárias para que o ponto de falha da população se en-
contre em média na metade final do escalonamento, utilizando operadores modificados,
variou entre 6 e 10 gerações, enquanto que utilizando os operadores convencionais, vari-
ou entre 20 e 26 gerações. Esta variação seja com os operadores convencionais, ou com
os operadores modificados é válida para cenários de baixa saturação. Nos cenários satu-
rados pode-se levar até 40 gerações para atingir esta mesma posição de falha, dada a difi-
culdade de encontrar soluções que obedeçam as restrições neste cenário.
5.6 Garantido resultados dentro do prazo com o seeding
A técnica denomina “seeding” consiste em colocar, na população inicial, soluções
encontradas anteriormente para o problema pelo próprio Algoritmo Genético utilizado ou
por outros métodos de otimização. Esta técnica pode ser útil em muitos problemas práti-
cos, já que inicia a otimização por regiões mais promissoras, ou mesmo garante que a
solução gerada pelo Algoritmo Genético não será inferior às soluções geradas pelos de-
mais métodos de otimização.
A opção pelo uso da técnica de seeding foi motivada pelas características da apli-
cação a que este Algoritmo Genético se destina, uma aplicação com prazos estritos para
entrega de uma solução, sob pena de transcorrido o prazo as soluções calculadas até o
57
momento não terem mais valor para a aplicação. Este prazo é o tempo entre dois interva-
los de atuação. A introdução de uma solução do problema, previamente calculada, asse-
gura que, mesmo o Algoritmo Genético não encontrando uma solução viável para o pro-
blema dentro do tempo para o próximo intervalo de atuação, ele terá pelo menos uma
sugestão de escalonamento viável para este intervalo, caso ela exista.
Ao iniciar a otimização, paralelamente à execução do Algoritmo Genético, procu-
ramos por uma solução viável para o problema utilizando um calculador baseado em re-
gras de operação simples, que calcula para cada intervalo de atuação um escalonamento
de bombas que não gere alarmes. O algoritmo desse calculador é apresentado na Figura
16.
Algoritmo do Calculador de Solução Viável
intervaloAtual ← tempoInicialOtimizacao tempoFinalOtimizacao ← intervaloAtual + horizondeOperacao Enquanto IntervaloAtual < tempoFinalOtimizacao faça
Calcular configuração inicial das bombas Simular Enquanto ocorreAlarme e existeMudancaConfiguracaoPossível faça Alterar configuração das bombas baseada nas regras de operação Simular fimEnquanto Armazenar escalonamento para o intervaloAtual intervaloAtual ← intervaloAtual + intervaloAtuaçao
fimEnquanto Retorna escalonamento encontrado
Figura 16 - Algoritmo do calculador de solução viável
Para cada intervalo de atuação, o algoritmo define uma programação inicial das
bombas. A escolha da configuração inicial das bombas baseia-se no nível atual dos tan-
ques. Cada tanque produtor é dividido em três partes iguais, conforme a sua capacidade.
Se o nível do tanque estiver no primeiro terço da divisão, e o tanque portanto está com
um nível baixo de fluido, as bombas associadas a esse tanque são desligadas. Se o nível
estiver no último terço, e o tanque portanto estiver próximo a sua capacidade máxima, as
bombas são ligadas. E, finalmente, se o nível do tanque estiver no segundo terço do
mesmo, a decisão é baseada no nível do tanque receptor da malha, caso o tanque recep-
58
tor, da estação de tratamento, esteja com o nível abaixo ou acima da metade da sua capa-
cidade, as bombas são ligadas ou desligadas, respectivamente.
Após estabelecida a configuração das bombas, o intervalo é simulado e, caso o-
corra algum alarme, indicando que alguma restrição do sistema foi violada e, portanto, a
solução é inviável, são efetuadas modificações na configuração das bombas de acordo
com as regras de operação, estabelecidas na Tabela 19. Para evitar que o algoritmo fique
preso num laço infinito, com a aplicação sucessiva das regras de reparo, as ações toma-
das para solucionar problemas num dado intervalo são registradas. Portanto, quando a
simulação de um escalonamento resulta em um alarme, mas não é possível corrigi-lo,
pois todas as operações de liga/desliga de bombas definida nas ações já foram tomadas, o
calculador considera o intervalo atual como concluído e avança para o intervalo seguinte.
Após finalizada a busca, a solução encontrada, mesmo que não seja viável, é introduzida
na população.
Tabela 19 - Estratégia para reparo de solução
Restrição Violada Ações Tanque produtor atinge o nível máximo Liga-se uma bomba associada a esse tanque Tanque produtor atinge o nível mínimo Desliga-se uma bomba associada a esse
tanque Tanque receptor atinge o nível máximo Desliga-se uma bomba do tanque produtor
de menor nível Duto atinge pressão máxima Desliga-se uma bomba a montante do duto Duto atinge pressão mínima Liga-se uma bomba a montante do duto Fluido atinge velocidade mínima em um duto Liga-se uma bomba a montante do duto Fluido atinge velocidade máxima em um duto Desliga-se uma bomba a montante do duto
O calculador busca um escalonamento viável para cada intervalo de tempo inde-
pendentemente. Como ele não retrocede para um intervalo já resolvido, é possível que o
algoritmo não encontre uma solução viável, mesmo para malhas que apresentam tal solu-
ção. Se elaborássemos um calculador mais sofisticado, que retrocedesse para intervalos
anteriores na tentativa de gerar uma solução viável, teríamos um algoritmo de busca e-
xaustiva, e recairíamos no problema de solucionar um problema NP-hard10.
10 NP-hard é a classe de complexidade dos problemas de decisão que são intrinsecamente mais
difíceis que aqueles que podem ser resolvidos por uma máquina de Turing não-determinística em tempo
59
A análise dos indivíduos da população indica que a introdução deste indivíduo
aumenta significativamente as chances de se obter outros indivíduos viáveis, visto que a
introdução de um indivíduo de mais alta aptidão acelera a introdução de características
desejáveis na população, resultado dos blocos de construções com alto valor de aptidão
que se espalham rapidamente na população [18].
Mesmo nos casos onde o calculador de solução viável não é capaz de encontrar
uma solução viável para o problema, e o indivíduo inserido na população é inviável, as
características desse indivíduo tendem a se propagar pela população, pois seu ponto de
falha, em geral, está localizado em uma posição superior à dos indivíduos gerados aleato-
riamente.
Em cenários de produção onde o sistema opera dentro da sua capacidade, mesmo
quando o calculador de solução viável não é bem sucedido, os operadores genéticos mo-
dificados são capazes de mover a posição de falha para posições maiores na matriz de
escalonamento. Todavia, como não há a inserção de uma solução viável, não há uma
propagação rápida de blocos de construção com alta aptidão, que aceleram o progresso
da busca. Para o mesmo caso avaliado na Seção 5.5.3, com uma malha operando dentro
da sua capacidade, utilizando operadores genéticos modificados, sem que contudo te-
nhamos uma solução viável inserida na população, leva-se em torno de 30 gerações para
que se alcance uma matriz com falhas, apenas na segunda metade do horizonte de opera-
ção na maior parte dos indivíduos da população, valor bem acima da faixa observada
quando na presença de uma solução viável, de 6 a 10 gerações.
5.7 Parâmetros de controle
Incorporadas as modificações para o tratamento das restrições do problema e do
calculador de solução viável, passamos à fase de eleição dos parâmetros de controle do
algoritmo.
Cada um dos componentes de um Algoritmo Genético tem parâmetros associados
a si, como a probabilidade de mutação, a porcentagem de indivíduos escolhidos pelo al-
goritmo de seleção, o tamanho da população, entre outros. Os valores destes parâmetros
polinomial. Quando a versão de decisão de um problema de otimização é provada pertencer à classe dos problemas NP-completo, então sua versão de otimização é NP-hard [14].
60
têm grande influência no tempo para se alcançar uma solução viável e na qualidade da
solução encontrada [18][11].
Pesquisas mostram que certas classes de problemas requerem parametrização es-
pecífica para alcançar um bom desempenho [3]. Parâmetros como a taxa de cruzamento e
de mutação utilizados neste trabalho foram resgatados da literatura [20][16][30][21][1].
Outros como o tamanho da população e a porcentagem de indivíduos gerados por cruza-
mento e cruzamento direcionado foram determinados através de experimentos num pro-
cesso conhecido como “ajuste de parâmetros”. Esse ajuste de parâmetros manual, além
de demorado, tem alguns inconvenientes, visto que os experimentos são conduzidos para
cada parâmetro por vez, e há uma forte dependência entre eles que não é considerada,
pois proceder experimentos para todas as combinações é praticamente impossível [11].
Os parâmetros de controle do algoritmo podem ser observados no quadro da
Tabela 20. Tabela 20 - Parâmetros de controle
Parâmetro Valor Tamanho da população 50 Tamanho da população intermediária 25 Taxa de cruzamento 90% Taxa de mutação 30% Indivíduos inseridos por elitismo 1 Indivíduos inseridos por cruzamento/cruzamento direcionado
15/34
Critério de parada 20min
O tamanho da amostra selecionada para fazer parte da população intermediária é
de 50% do tamanho da população original. O operador de elitismo seleciona apenas o
melhor indivíduo de cada geração para fazer parte da próxima população. Os valores
encontrados na literatura levaram-nos a adotar uma probabilidade de cruzamento entre
dois indivíduos de 90%. A proporção de indivíduos gerados por cruzamento e cruzamen-
to direcionado é de 30% e 70%, respectivamente. A taxa de mutação foi fixada dentro
dos valores de referência da literatura, e têm uma probabilidade de ocorrência de 30%,
aplicada por individuo (e não bit a bit), em um único intervalo de tempo, o que resulta
numa probabilidade de aproximadamente 0,2% de que um bit venha a ser invertido. Estes
61
valores foram estabelecidos após experimentos variando as taxas de mutação no intervalo
de 0,1 a 5% e as taxas de cruzamento de 60 a 90% [3][1].
Resultados apresentados na seção 5.8 sugerem que um dos refinamentos que este
algoritmo deve sofrer é a substituição destes parâmetros estabelecidos experimentalmente
na forma de ajuste gradual pelo controle de parâmetros [11]. O controle de parâmetros é
uma outra abordagem para a parametrização de Algoritmos Genéticos, onde os parâme-
tros vão sendo configurados dinamicamente durante o processo de otimização, à medida
que o algoritmo evolui. A estagnação prematura observada em algumas amostras, em
torno de ótimos locais, sugere a necessidade de uma taxa de cruzamento e mutação adap-
tativa, até porque utilizamos duas técnicas diferentes para os operadores de cruzamento e
mutação, a convencional e a direcionada, que precisam ser equilibradas, conforme o pro-
gresso do algoritmo.
5.8 Testando o AG para diferentes padrões de produção
Um Algoritmo Genético para o problema tratado deve ser capaz de suportar tanto
variações na topologia e dimensão da malha, quanto alterações na previsão da produção.
As alterações de topologia e dimensão da malha relacionadas à parada de equipamentos
para manutenção e a expansões com obras de engenharia na rede e o padrão de produção
influenciam diretamente em uma maior ou menor dificuldade de se encontrar uma solu-
ção viável para o problema e na possibilidade de otimização do bombeio.
Nesta seção analisamos três cenários de operação distintos, que correspondem
respectivamente a um sistema com baixa saturação para a produção, um sistema de mé-
dia saturação e um sistema saturado. Para cada um destes cenários observamos como o
Algoritmo Genético se comporta quando comparado a um sistema de regras que simula o
comportamento de um operador.
Para conseguir representar estes cenários são feitas alterações no perfil de produ-
ção dos campos de maneira a saturar o sistema. O perfil de produção dos três cenários
pode ser observado na Tabela 21Tabela 21 (apresentada anteriormente no Capítulo 2).
Tabela 21 - Características da produção
Estação ETA ARB ARA MAG ETO
62
Propriedades Q (l/s) Q(l/s) Q(l/s) Q(l/s) Q(l/s)Cenário I (baixa saturação)
29,5130 73,614 34,1664 15,625 160,00
Cenário II (média saturação) 35,4160 103,060 42,7080 18,750 207,46Cenário III (saturado) 42,4992 135,600 53,3000 22,500 270,00
O perfil de produção nos diferentes campos varia, nos três cenários, apenas no
que se refere à vazão de entrada em cada uma das estações. As demais propriedades de
fluido, como temperatura e viscosidade, foram mantidas as mesmas nos três cenários (ver
Seção 2.6). A vazão de entrada em ETA cresce numa razão de 20% a cada cenário, em
ARA 25%, em MAG 20%, em ARB ela cresce 40% do cenário I para o cenário II, e 20%
do cenário II para o cenário III. A vazão de saída na estação de tratamento ETO aumenta
30% tanto do cenário I para o II, quanto do cenário II para o III. A vazão média de saída
das bombas associadas às estações é respectivamente, 188 l/s em ETA, 118 l/s em ARB,
139 l/s em ARA e 138 l/s em MAG.
Em todos os experimentos foi utilizada a mesma malha detalhada na Seção 2.6,
com 6 bombas. O horizonte de operação é de 24h com intervalo de atuação de 20 min.
Comparamos os resultados alcançados pelo Algoritmo Genético para os três cenários de
previsão da produção, com os resultados obtidos por uma regra de operação que simula o
comportamento de um operador da malha real. O operador deste sistema gerencia o
bombeio da sua estação coletora sem levar em consideração as outras unidades de bom-
beio. O objetivo do operador é bombear toda a sua produção durante os horários de tari-
fas mais baixas, de forma que no início do período de ponta os tanques estejam no menor
nível possível. A regra de operação, baseada na operação ad-hoc do sistema real, mantém
todas as bombas ligadas até que o limite de nível mínimo do tanque seja atingido, quando
as bombas são desligadas e só voltam a ser religadas quando o limite de nível máximo do
tanque for atingido. Esta é a operação em todo o período, exceto ao se aproximar do ho-
rário de pico, quando os operadores ligam as bombas, para que os tanques estejam no seu
menor nível no início do horário de ponta. O algoritmo está descrito na Figura 17.
63
Algoritmo da Regra de Operação
intervaloAtual ← tempoInicialOtimizacao tempoFinalOtimizacao ← intervaloAtual + horizondeOperacao Para cada estação faça
estaEsvaziando ← verdadeiro; cheioDentroHorarioPico ← falso; Enquanto intervaloAtual < tempoFinalOtimizacao faça Se tanque está seco Desligar bombas estaEsvaziando ← falso Se intervaloAtual dentro do horário de pico cheioDentroHorarioPico ← verdadeiro; fimSe Se tanque está cheio Ligar bombas estaEsvaziando ← verdadeiro fimSe Se (não está cheioDentroHorarioPico e intervaloAtual dentro do horário de pico) estaEsvaziando ← falso Deligar bombas Senão Se (intervaloAtual menor que tempoParaInícioHorárioPonta) e (tempoParaEsvaziarTanqueAntesHorarioPico maior que InicioHorarioPico) estaEsvaziando ← verdadeiro fimSe fimSe
fimEnquanto Armazenar escalonamento para o intervaloAtual AtualizarNíveisTanques intervaloAtual ← intervaloAtual + intervaloAtuaçao
fimPara Retorna escalonamento encontrado
Figura 17 - Algoritmo de operação da rede de escoamento
64
Os Algoritmos Genéticos fazem parte da classe de heurísticas não-
determinísticas, e por essa razão, para caracterizar seu desempenho é necessário a repeti-
ção de um mesmo experimento diversas vezes. O baixo desvio padrão observado nos
nossos experimentos (Tabela 22) nos dá uma indicação de que podemos considerar os
resultados dos nossos experimentos, com um número reduzido de repetições, válidos.
Executamos os experimentos numa grade computacional, um ambiente pouco estável e
heterogêneo, que utiliza computadores independentes conectados em rede, incluindo a-
queles utilizados para atividades de propósito geral, como plataforma para execução de
aplicações paralelas [12].
Adotamos um modelo de paralelização mestre-escravo pela facilidade de imple-
mentação, baixo acoplamento entre as tarefas e a grande eficiência do método quando a
função a ser avaliada consome muitos recursos computacionais [9]. Nesta arquitetura de
paralelização um dos processadores, o mestre, irá armazenar toda a população, enviar
indivíduos para serem avaliados pelos processadores escravos, coletar os resultados, e
aplicar os operadores genéticos para gerar a nova população. O algoritmo mestre-escravo
não tem seu comportamento de busca alterado devido à paralelização, visto que há uma
sincronização entre o nó mestre e os escravos, portando-se como um algoritmo seqüenci-
al, o que do ponto de vista do desempenho geral do algoritmo pode não ser o ideal, mas
permite que toda a teoria desenvolvida para os algoritmos seqüenciais possa ser aplicada
diretamente, sem adaptações ou considerações [19][44].
Devido ao elevado custo computacional da avaliação da função objetivo, que é
proporcional à complexidade da malha para a qual se deseja obter um escalonamento de
bombas ótimo, apenas um número pequeno de gerações consegue ser avaliada dentro do
prazo. As características da infra-estrutura de processamento dificultavam a comparação
dos experimentos, já que para um mesmo intervalo de tempo (20 min), poderíamos avali-
ar uma quantidade diferente de indivíduos, devido a variação na carga e no número de
recursos disponíveis na grade computacional.
Para determinar quantas gerações poderiam ser avaliadas em 20 min, caso os re-
cursos fossem de uso dedicado, deixamos as máquinas de uma grade computacional de
cinqüenta computadores pentium IV com 512Mb de RAM indisponíveis por este período
para uso pelos demais usuários. Neste período conseguimos avaliar apenas 20 gerações.
Fixamos então em 20, o número de gerações que seriam avaliadas em cada um dos expe-
rimentos.
65
Para cada cenário de operação, repetimos a otimização com o Algoritmo Genético
por cinco vezes, avaliando em cada uma delas 20 gerações. Os resultados obtidos estão
apresentados na Tabela 22. O Algoritmo Genético é na média, melhor que a regra em
todos os cenários, contudo no pior caso o Algoritmo Genético conforme implementado é
pior que a regra tanto no cenário I quanto no II, só superando a regra no cenário III devi-
do ao ponto de falha mais distante no horizonte de operação. No terceiro cenário, onde a
malha está saturada, e o custo obtido pela regra de operação é inferior em quase 5%, o
ponto de falha da regra acontece dezoito intervalos antes, enquanto a regra falha no oita-
vo intervalo, a solução encontrada pelo Algoritmo Genético só falha no vigésimo sexto
intervalo.
O número de gerações avaliadas, e por conseguinte o número de indivíduos avali-
ados, é muito pequeno quando comparado ao tamanho do espaço-solução. Este fato suge-
re que caso tivéssemos mais recursos disponíveis, e por conseguinte avaliássemos um
número maior de gerações, alcançaríamos além de maiores ganhos nos cenários I e II,
uma solução viável para o cenário III.
Tabela 22 - Resultados da otimização
Cenário I
(baixa saturação)
Cenário II
(média saturação)
Cenário III (saturado)
Custo (R$/m3) 0,00246 0,00275 0,00252
Reg
ra d
e
oper
ação
Ponto de falha Transbordo na ETO
12 8
Valor mínimo (R$/m3) 0,00216 0,00207 0,00220Valor máximo (R$/m3) 0,00256 0,00284 0,00312Média (R$/m3) 0,00225 0,00240 0,00264Desvio padrão 0,00011 0,00040 0,00035Ganho na média (%) 8,53 12,70 -4,87
Alg
oritm
o G
enét
ico
Ponto de falha - - 26
Para investigar essa hipótese, executamos o Algoritmo Genético por 24h em uma
grade computacional de oito máquinas não dedicadas, o que permitiu a avaliação de a-
proximadamente 250 gerações. Observando os resultados da otimização, percebeu-se que
após as primeiras 150 gerações, a redução do custo da função objetivo era mais lenta.
66
Fixamos então 150 gerações como o tempo ideal para que o algoritmo genético executas-
se. A opção por um número fixo de gerações, ao invés de uma condição de parada por
tempo, se deve a dificuldade que teríamos para analisar os resultados, visto que os recur-
sos da grade não estão dedicados, poderíamos ter experimentos sendo executados pela
mesma quantidade de tempo, mas com número de gerações avaliadas diferentes, e desta
forma com um número menor de soluções avaliadas.
Para os mesmos cenários avaliados inicialmente com 20 gerações, refizemos os
experimentos utilizando como critério de parada a avaliação de 150 gerações.
Na Figura 18, observamos o comportamento do cenário I, de baixa saturação, com
uma produção abaixo da capacidade de escoamento da rede. A solução encontrada pelo
Algoritmo Genético é mais barata que da regra de operação usual, e tem um custo de
0,00185 R$/m3. A regra de operação alcançou um custo de 0,00246 R$/m3, com uma
falha operacional de baixa severidade, com a violação do limite de nível superior do tan-
que da estação de tratamento final. O Algoritmo Genético conseguiu portanto uma redu-
ção de 24,79% em relação à operação convencional.
0,001500
0,001700
0,001900
0,002100
0,002300
0,002500
0,002700
0,002900
1 12 23 34 45 56 67 78 89 100
111
122
133
144
Número de Gerações
Cus
to (R
$/m
3)
Custo do melhor cromossomo
Figura 18 - Desempenho no cenário I de produção
No segundo cenário, um cenário de saturação mediana, observado (Figura 19), a
regra de operação também não consegue encontrar uma solução viável para o problema e
causa, além do transbordo do tanque receptor, sobrepressão em alguns dutos. A redução
de custo alcançada pelo Algoritmo Genético neste cenário em relação à regra de operação
é de 32%. O Algoritmo Genético alcança um valor de 0,00187 R$/m3, enquanto que a
regra de operação só consegue otimizar a solução a um custo de 0,00275 R$/m3.
67
0,001000
0,001500
0,002000
0,002500
0,003000
0,003500
1 13 25 37 49 61 73 85 97 109
121
133
145
Número de Gerações
Cus
to (R
$/m
3)
Custo do melhor cromossomo
Figura 19 - Desempenho no cenário II de produção
O terceiro cenário de simulação se dá em uma rede de escoamento saturada e,
neste cenário, a regra de operação também não é capaz de encontrar uma solução viável.
O calculador de solução viável também não consegue encontrar uma solução viável, e a
otimização se inicia com uma solução com falha no décimo quarto intervalo de atuação.
O primeiro indivíduo viável surge na geração 130 e tem um custo de 0,00231 R$/m3. Ao
final de 150 gerações o custo do melhor cromossomo é de 0,00226 R$/m3. A regra de
operação falha no oitavo intervalo e tem um custo de 0,00252 R$/m3. O ganho do Algo-
ritmo Genético em relação a regra é de 10,31 %.
0,0020000,0022000,0024000,0026000,0028000,0030000,0032000,0034000,003600
1 17 33 49 65 81 97 113 129 145
Número de Gerações
Cus
to (R
$/m
3)
01020304050607080
Pont
o de
falh
a
Custo do melhor cromossomoPosição da falha
Figura 20 - Desempenho no cenário III de produção
68
O gráfico da Figura 20, diferentemente dos demais, apresenta quedas e subidas no
valor da função de custo avaliada, isto é resultado do critério adotado para classificar as
soluções. Quando duas soluções inviáveis são comparadas, aquela que possui o ponto de
falha no maior intervalo de atuação será considerada a melhor solução entre elas, embora
o custo possa ser superior. Neste experimento, a melhor solução da nonagésima sétima
geração possui um custo de 0,002209 R$/m3 e a melhor da nonagésima oitava geração
tem um custo de 0,002904 R$/m3, mas o ponto de falha da primeira é na posição 54, en-
quanto o da segunda é no intervalo 55 de atuação.
Observando os gráficos das Figuras 18,19 e 20, podemos notar quedas bruscas no
valor do custo da melhor solução encontrada. Essas quedas ocorrem quando as operações
genéticas tiram da inviabilidade uma solução de mais baixo custo, por esta razão temos
mudanças pontuais significativas no custo do melhor cromossomo.
69
6 Conclusões e trabalhos futuros
O Algoritmo Genético demonstrou ser uma técnica satisfatória e simples para a
resolução de problemas em redes de escoamento complexas, com espaço de solução de
dimensão elevada e restrições operacionais rígidas. A complexidade da malha, os níveis
de saturação da rede e as restrições operacionais sob a qual opera são fatores importantes
para determinar se uma solução viável será alcançada e o tempo que levará para que isso
ocorra.
Um dos maiores problemas enfrentados pelo algoritmo apresentado são as restri-
ções temporais que precisam ser respeitadas. No cenário de otimização saturado, onde a
operação simultânea de todas as estações, com a conseqüente concorrência pela capaci-
dade de transferência da rede de dutos, leva a violação de restrições de pressão e veloci-
dade do fluido nos dutos, o algoritmo não foi capaz de identificar uma solução viável
para o problema dentro do prazo da aplicação. O elevado tempo computacional da avali-
ação da função de custo inviabiliza uma busca mais ampla no espaço-solução, o que pode
ser crítico quando o cenário que está sendo otimizado está saturado e o número de solu-
ções viáveis é pequeno.
A ampliação do estudo de caso para um cenário com um número maior de esta-
ções coletoras e de bombas por estação, como a malha da UN-RNCE, permitirá a avalia-
ção da eficiência e eficácia da solução quando aplicada a uma rede mais complexa, com
um número maior de dispositivos. Para isto, o modelo de simulação hidráulica precisa ser
refinado para melhorar a sua eficiência computacional, permitindo uma avaliação mais
rápida da função-objetivo, pois a adoção de uma outra arquitetura de paralelização de
Algoritmos Genéticos mais eficiente, ou mesmo uma grade computacional de maior di-
mensão, não seriam suficientes para viabilizar a otimização de uma malha com um gran-
de número de dispositivos em um tempo aceitável.
Um aspecto importante da solução apresentada é a sua generalidade. O modelo
apresentado se aplica a uma malha de escoamento de petróleo de topologia genérica, com
a possibilidade de paradas programadas em parte dos ativos da malha dentro do horizonte
de uma otimização, sem que para isso tenha que haver qualquer modificação na solução.
O desempenho do Algoritmo Genético depende fortemente dos parâmetros de
controle utilizados e do ajuste adequado desses parâmetros, especialmente em relação à
70
incorporação futura de taxas variáveis ao longo do tempo, onde o próprio algoritmo, de
acordo com o processo evolutivo, selecione os parâmetros e até mesmo os operadores
que devem ser aplicados.
Os operadores genéticos modificados e a solução inicial introduzida pelo calcula-
dor de solução viável se mostraram eficazes na aceleração da busca por uma solução viá-
vel para ao problema. O operador de elistismo assegurou a preservação da melhor solu-
ção, sem que com isso tivéssemos uma convergência prematura.
6.1 Novos objetivos a serem otimizados
O custo com consumo de energia transitório, dado pela energia consumida no
momento que a bomba é acionada, e o custo da manutenção das bombas, que são de difí-
cil estimativa e cálculo, além da manutenção de um padrão de BSW e vazão que chegam
à estação de tratamento, são alguns dos objetivos que podem ser incorporados.
O consumo de energia transitório e o custo da manutenção de equipamentos estão
diretamente ligados à sua operação. No caso das bombas, a operação de liga/desliga
constitui um fator importante para o desgaste do equipamento e redução da sua vida ú-
til,assim como sinaliza a solução que teria o maior custo caso o consumo de energia tran-
sitório fosse medido. Embora difícil de quantificar este custo, é possível adicionar este
novo objetivo como um dos objetivos a ser perseguido pelo algoritmo de otimização, de
forma que soluções equivalentes em termos de custo de energia elétrica (custo em regi-
me) possam ser diferenciadas uma das outras pelo número de chaveamentos. O chavea-
mento é a transição do estado desligado para estado ligado, e a sua otimização em muitos
casos é tão ou mais importante que os aspectos de consumo de energia em problemas de
otimização do escalonamento das bombas [25]. Soluções que tivessem um menor número
de alterações de estado de desligado para ligado seriam incentivadas em relação às de-
mais soluções.
6.2 Tratamento de inviabilidades
Devido às restrições do problema, uma preocupação relevante do algoritmo pro-
posto é o tratamento das soluções inviáveis. Parte dos nossos estudos foram focados nos
operadores de reprodução direcionados e na avaliação da sua contribuição para o direcio-
71
namento da busca. Alguns refinamentos desse operador podem ser conseguidos ao se
levar em consideração não só o ponto da falha, como também a natureza desta, possibili-
tando que o algoritmo faça o reparo da solução, tendo como base ações simples como as
apresentadas na Tabela 19 da Seção 5.6 .
Uma possibilidade que deve ser investigada é a incorporação da regra de reparo
na regra de descarte. Assim, ao invés de descartarmos as soluções que não satisfaçam os
critérios da regra de descarte, poderíamos aplicar regras de reparo nestas soluções, e
mantê-las na população.
Experimentos precisam ser conduzidos para melhor caracterizar o comportamento
do algoritmo em relação a esse mecanismo de descarte, considerando não só o tempo
computacional ganho por não avaliar uma solução inviável, mas principalmente, anali-
sando a implicação do uso dessa técnica na qualidade das soluções encontradas na popu-
lação.
Outra possibilidade para o tratamento das restrições do problema é a incorporação
das restrições do problema como novos objetivos a serem perseguidos, com os Algorit-
mos Genéticos multi-objetivos.
6.3 Hibridização
Uma alternativa para melhorar o desempenho do algoritmo que deve ser conside-
rada, é a hibridização com métodos de busca locais, visto que os Algoritmos Genéticos
são bastante eficientes para identificar as regiões promissoras do espaço de busca, mas
têm dificuldades de refinar as soluções, fazendo operações de busca numa vizinhança
próxima de uma solução. Pelas características do próprio problema que tratamos, um
simples deslocamento da programação da operação no tempo, por exemplo, podem pos-
sibilitar uma melhoria considerável no custo da solução. A integração desta heurística
com outros métodos de busca locais, como por exemplo, a Pesquisa em Vizinhança Vari-
ável (VNS, Variable Neighborhood Search) [33], partindo de soluções identificadas pelo
Algoritmo Genético, pode ser bastante promissora.
72
Referências bibliográficas [1] Alander, J.T., ‘On optimal population size of genetic algorithms’, Proc. of
CompEuro 92, Computer Systems and Software Engineering, 6th Annual European Computer Conference, pp. 65-70, 1992.
[2] Bäck, T. and Hoffmeister, F. ‘Extended Selection Mechanisms in Genetic Al-gorithms’. ICGA4, pp. 92-99, 1991
[3] Back, T., Fogel, D., Michalewicz, Z. Handbook of evolutionary computation. Ed. Thomas Baeck, 1997.
[4] Baker, J. E., ‘Reducing bias and inefficiency in the selection Algorithms’. Proc. of the 2nd Intl. Conference on Genetic Algorithms, pp.14-21, 1987.
[5] Beckwith, S.F. and Wong, K.P. ‘A Genetic Algorithm Approach for Electric Pump Scheduling in Water Supply Systems’,IEEE International Conference on Evolutionary Computing, Perth, IEEE Neural Networks Council, 1: pp 21-26, 1995.
[6] Bush, M.D.,Carter, J.N., ‘Application of a Modified Genetic Algorithm to Pa-rameter Estimation in the Petroleum Industry’. Intelligent Engineering Systems through Artificial Neural Networks 6, Dagli et. Al (Editores), ASME Press, NY, 397, 1996.
[7] Cembrowicz, R. G., ‘Water supply systems optimization for developing coun-tries.’, Pipeline Systems, B. Coulbeck and E. Evans, eds., Kluwer Academic Publishers, pp. 59-76, 1992.
[8] De Jong, K. Analysis of the behavior of a class of genetic adaptive systems, Ph.D. Thesis, Department of Computer and Communications Sciences, Univer-sity of Michigan, Ann Arbor, Mi, 1975.
[9] Cantú-Paz, E., Designing Efficient and Accurate Parallel Genetic Algorithms, PhD thesis, Graduate College of the University of Illinois at Urbana Cham-paign, 1999.
[10] Driedger, W., Controlling Positive Displacement Pumps. http://www.driedger.ca , 2000.
[11] Eiben, A.E., Hinterding, R., Michalewicz, Z. ‘Parameter control in evolution-ary algorithms’. IEEE Trans. on Evolutionary Computation, pp. 124-141, 1999.
[12] Foster, I., Kesseman, C. Globus: A toolkit-based architecture. The Grid: Blue-print for a New Computing Infrastructure. Editor Morgan Kaufmann. 1999.
73
[13] Galvão, C., Valença, M. (org.) Sistemas Inteligentes: Aplicações a Recursos Hídricos e Ciências Ambientais. Ed. Universidade/UFRGS/ABRH, 1999.
[14] Garey, M.R., Johnson, D.S. Computers and intractability: a guide to the theory of NP-completeness. Ed. W.H. Freeman and Company, 1979.
[15] Goldberg, D. E., "Genetic and Evolutionary Algorithms Come of Age", Com-munications of the ACM , N. 3 Vol. 37, pp. 113-119, 1994.
[16] Goldberg, D. E., ‘Genetic Algorithms in search, optimization, and machine learning’, Addison-Wesley Pub Co, 1989.
[17] Goldberg, D.E. ‘Sizing populations for serial and parallel genetic algorithms.’ Proceedings of third International Conference of Genetic Algorithms, pp. 70-79, 1989.
[18] Goldberg, D.E., The Design of Innovation: Lessons from and for Competent Genetic Algorithms, Série Kluwer em Genetic Algorithms and Evolutionary Computation, Vol. 7, 2002.
[19] Gordon, V.S., Whitley, D. ‘Serial and Parallel Genetic Algorithms as Function Optimizers’. Proc. of the Fifth Intl. Conf. on Genetic Algorithms, Morgan Kaufmann Publishers, pp. 177-183, 1993.
[20] Grefenstette, J.J. ‘Optimization of control parameters for genetic algorithms’. IEEE Transactions on System, Man, and Cybernetics, 16(1), pp 122-128, 1986.
[21] Grefentette, J. J., Foundations of Genetic Algorithms -2, D. Whitley, ed., Mor-gan Kaufmann, pp. 75-91, 1993.
[22] Hansen, P., Mladenovic, N. Variable Neighborhood Search. Handbook of Metaheuristics. Editores F. Glover e G. Kochenagen, Kuwer Academic Pub-lishers, Dordrecht, 2003.
[23] Haupt, R. L., Haupt, S. E. Practical Genetic Algorithms. Wiley-Interscience Publication, John Wiley & Sons, Inc., USA, 1998.
[24] Holland, J. H.. Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor, 1975.
[25] Lansey et al. ‘Optimal Pump Operations Considering Pump Swithes’. Jornal of Water Resources Planning and Management, vol. 120, N. 1, 1994.
[26] León C., Martín, S., Elena, J. M., Luque, J.: ‘Explore: Hybrid Expert System for Water Networks Management’, ASCE, Journal of Water Resources Plan-ning and Management. March/April 2000, pp. 65-74.
74
[27] Louis, S., Johnson, J., ‘Solving Similar Problems using Genetic Algorithms and Case- Based Memory’, Proc. of the 7th IEEE Int. Conf. on Genetic Algo-rithms - VII ICGA'97, Morgan Kauffman, pp. 283-290, 1997.
[28] Mackle, G. Savic, D., Walters, G. ‘Application of Genetic Algorithms to Pump Scheduling for Water Supply’, GALESIA’95, pp. 400-405, 1995.
[29] Manual de tarifação da energia elétrica, PROCEL –Programa nacional de con-servação de energia elétrica,1ª Edição, maio/2001.
[30] Mercer, R. E. ‘Adaptive Search using a reproductive meta-plan’. Kybernets, 7, 215-228, 1977.
[31] Michalewicz, Z., Forgel, D. B. How to solve it: modern heuristics. Editora S-pringer-Verlag, 3ª edição, 2002.
[32] Michalewicz, Z., “Genetic Algorithms, Numerical Optimization and Con-straints”, Proc. of the 6th Intl. Conference on Genetic Algorithms, Pittsburgh, 1995, p. 151-158.
[33] Mladenovic, N.;Hansen, P. Variable Neighborhood Search, a Chapter of "Handbook of Metaheuristics". Comps. in Opns. Res. 24, 1097--1100 ,1997.
[34] Olujic, Z. Compute friction factors fast for flow in pipes. Chemical Engineer-ing, pp. 91-93, dezembro, 1981.
[35] Ormsbee, l. E., Lansey, K.E. ‘Optimal Control of Water Supply Pumping Sys-tems’. Journal of Water Resources Planning and Management, Vol. 120, N. 2, pp 237-252 1994.
[36] Porto, R. M. Hidráulica Básica. Ed. EESC-USP, São Paulo, 1998.
[37] Reis, L. F. R., Carrijo, I. B. ‘Extração de regras operacionais ótimas de siste-mas de distribuição de água através de Algoritmos Genéticos multiobjetivo e aprendizado de máquina’. Quarto Seminário Hispano-Brasileiro sobre Sistemas de Abastecimento Urbano de Água- SEREA, João Pessoa, novembro, 2004
[38] Romero, CE., Carter, J. ‘Using genetic algorithms for reservoir characteriza-tion’. J. Petroleum Sci. and Eng. 31, pp. 113-123, 2001.
[39] Savic, D. A., and Walters, G. A. ‘Evolving Sustainable Water Networks’. Hy-drological Sciences, 42(4), 549, 1997.
[40] Savic, D. A., Walters, G. A., Randall-Smith, M., and Atkinson, R. M. ‘Large Water Distribution Systems Design Through Genetic Algorithm Optimisation’. Proceedings of the ASCE Joint Conference on Water Resources Engineering and Water Resources Planning and Management, American Society of Civil
75
Engineers, Hotchkiss, R. H., and Glade, M., eds., proceedings published on CD, Minneapolis, Minnesota, 2000.
[41] Schwab, M., D.A. Savic and G.A. Walters. Multi-Objective Genetic Algorithm for Pump Scheduling in Water Supply Systems, Centre For Systems And Con-trol Engineering, Report No. 96/02, School of Engineering, University of Exe-ter, Exeter, United Kingdom, p.60, 1996.
[42] Silva, A., T. Ohishi, A. Mendes, F. França e E. Delgado, ‘Using Genetic Algo-rithm and Simplex Method to Stabilize an Oil Treatment Plant Inlet Flow’. Proceedings do IPC2000 - International Pipeline Conference, pp. 1459-1466, 2000.
[43] Souza, B., Braz, H., Alves, H. ‘Um Algoritmo Genético para configuração ó-tima de alimentadores de energia elétrica’. 6º. Simpósio Brasileiro de Automa-ção Inteligente – SBAI, setembro de 2003.
[44] Starkweather, T., Whitley, D., e Mathias, K. ‘Optimization using Distributed Genetic Algorithms’. Proceedings of Parallel Problem Solving from Nature I, pp. 176-185, 1991.
[45] Velez-Langs, O., Ossowski, S., ‘Evolutionary Computation in Oil Industry: An Overview’. International Joint Conference on Artificial Intelligence, Second Workshop Intelligent Computing in the Petroleum Industry, pp. 51-55, 2003.
[46] Water Research Center, United Kingdom. Pump Scheduling in Water Supply, Report TR232, Swindon, Wiltshire SN5 8YR, 1985.
[47] Whitley, D. ‘The GENITOR Algorithm and Selection Pressure: Why Rank-Based Allocation of Reproductive Trials is Best’. Proceedings of the Third In-ternational Conference on Genetic Algorithms, San Mateo, California, USA: Morgan Kaufmann Publishers, pp. 116-121, 1989.
[48] Whitley, D. A Genetic Algorithm Tutorial. Technical Report CS-93-103, De-partment of Computer Science, Colorado State University, 1993.
76
