resumo - Centro de Ciências Exatas e da Terra

UNIVERSIDADE FEDERAL DO RIO GRANDE DO NORTE
DEPARTAMENTO DE INFORMÁTICA E MATEMÁTICA APLICADA - DIMAp
PROGRAMA DE MESTRADO EM SISTEMAS E COMPUTAÇÃO
DISSERTAÇÃO DE MESTRADO
ALGORITMOS EVOLUCIONÁRIOS NA SOLUÇÃO DO PROBLEMA DA
PROGRAMAÇÃO DE SONDAS DE PRODUÇÃO
MÁRCIA BORCHARDT
Natal
Junho - 2002
Márcia Borchardt
ALGORITMOS EVOLUCIONÁRIOS NA SOLUÇÃO DO PROBLEMA
DA PROGRAMAÇÃO DE SONDAS DE PRODUÇÃO
Dissertação apresentada como requisito parcial à
obtenção do grau de Mestre, pelo curso de
Pós-Graduação em Sistemas e Computação, da
Universidade Federal do Rio Grande do Norte
Área de concentração: Sistemas de Alto Desempenho
Orientador: Prof. Dr. Marco César Goldbarg
Universidade Federal do Rio Grande do Norte
Natal
2002
TERMO DE APROVAÇÃO
MÁRCIA BORCHARDT
ALGORITMOS EVOLUCIONÁRIOS NA SOLUÇÃO DO PROBLEMA
DA PROGRAMAÇÃO DE SONDAS DE PRODUÇÃO
Dissertação aprovada como requisito parcial para obtenção do grau de Mestre no
Curso de Pós-Graduação em Sistemas e Computação da Universidade Federal do Rio
Grande do Norte, pela seguinte banca examinadora:
_____________________________
Prof. Dr. Marco César Goldbarg - Orientador
Departamento de Informática e Matemática Aplicada, UFRN
_____________________________
Profª Drª Elizabeth Ferreira Gouvêa
Departamento de Informática e Matemática Aplicada, UFRN
_____________________________
Prof. Dr. Henrique Pacca L. Luna
Departamento de Ciência da Computação, UFMG
Natal, 28 de junho de 2002
ii
À Vasco Velleda
meu eterno amor
iii
AGRADECIMENTOS
Em especial ao meu noivo Vasco Velleda pelo amor inabalável nos momentos
de ausência; por todo apoio e incentivo para a realização deste trabalho.
Aos meus pais, Harald e Nelci, pelo apoio, dedicação e preocupação que sempre
tiveram em todos os momentos de minha vida, e a toda minha família.
Ao PRH-ANP 22/00 – Programa de Recursos Humanos da Agência Nacional de
Petróleo (ANP) para o setor petróleo e gás – cujo apoio financeiro tornou possível à
realização do curso de pós-graduação.
Ao professor Marco César Goldbarg pela orientação para a realização deste
trabalho.
Aos membros da banca, professores Henrique Pacca L. Luna e Elizabeth
Ferreira Gouvêa, por avaliarem o trabalho.
iv
SUMÁRIO
RESUMO.......................................................................................................................vii
ABSTRACT..................................................................................................................viii
1
INTRODUÇÃO....................................................................................................... 1
2
PROBLEMAS DE SEQUENCIAMENTO........................................................... 6
2.1
2.2
2.3
2.4
3
Introdução ......................................................................................................... 6
Definição e Caracterização ............................................................................... 7
Complexidade ................................................................................................. 10
Métodos de solução ........................................................................................ 11
SONDAS DE PRODUÇÃO.................................................................................. 17
3.1
Atividade de sondagem................................................................................... 17
3.1.1
Breve visão elucidativa sobre completação e workover......................... 18
3.2
A importância do problema ............................................................................ 20
3.3
Formulação e modelagem matemática do problema ...................................... 22
4
ALGORITMOS GENÉTICOS............................................................................ 32
4.1
Histórico.......................................................................................................... 32
4.2
Definição......................................................................................................... 34
4.3
Terminologia................................................................................................... 35
4.4
Aplicação ........................................................................................................ 37
4.5
Algoritmo Genético híbrido - memético......................................................... 38
4.6
Algoritmo Genético híbrido (memético) utilizado neste trabalho .................. 41
4.6.1
Representação Genética.......................................................................... 45
4.6.2
Operadores Genéticos ............................................................................. 46
4.6.3
Definição de vizinhança de busca........................................................... 50
5
TRANSGENÉTICA COMPUTACIONAL........................................................ 52
5.1
Evolução cultural e biológica ......................................................................... 52
5.2
O paradigma intracelular e extracelular.......................................................... 54
5.3
O processo evolucionário da Transgenética Computacional.......................... 56
5.4
Agentes Transgenéticos .................................................................................. 59
5.5
Algoritmos Transgenéticos ............................................................................. 61
5.6
Pseudocódigo do algoritmo ProtoG_PSPT..................................................... 61
5.6.1
Construção do BM e da população inicial .............................................. 63
5.6.2
Processo evolucionário ........................................................................... 64
v
6
RESULTADOS COMPUTACIONAIS............................................................... 68
6.1
6.2
6.3
Instâncias ........................................................................................................ 68
Desempenho dos algoritmos........................................................................... 69
Comparação de tempo de processamento....................................................... 73
7
CONCLUSÕES..................................................................................................... 76
8
REFERÊNCIAS BIBLIOGRÁFICAS................................................................ 77
vi
RESUMO
O problema que envolve a programação do atendimento da frota de sondas de produção
de poços de petróleo, embora de difícil resolução, é de extrema importância econômica,
técnica e ambiental. Uma formulação matemática deste problema é apresentada, onde
uma abordagem algorítmica de solução é desenvolvida. O problema abordado pode ser
considerado como um problema de sequenciamento em máquinas paralelas que é uma
classe importante dos problemas de otimização combinatória. O objetivo da presente
pesquisa é desenvolver uma abordagem algorítmica para resolvê-lo, utilizando os
fundamentos do algoritmo transgenético Proto-Gene da metaheurística Transgenética
Computacional. Em paralelo, é implementado um Algoritmo Genético híbrido –
memético – que objetiva fornecer elementos para a comparação de desempenho entre as
abordagens de solução. Instâncias são geradas para a realização dos testes
computacionais para análise do desempenho das abordagens acima citadas.
Palavras-chave: Transgenética Computacional, Algoritmo Genético Híbrido, Sondas de
Produção de poços de petróleo, Algoritmo Proto-Gene, problemas de
sequenciamento.
vii
ABSTRACT
The problem that involves the programming of the attendance of the fleet of workover
rigs of oil wells, even so of difficult resolution, is of extreme economic importance,
enviroment and technique. A mathematical formulation of this problem is presented,
where an algorithmic boarding of solution is developed. The boarded problem can be
considered as a schedule problem in parallel machines that are an important classroom
of the combinatoiral optimization problems. The objective of the present research is to
develop an algorithmic boarding to decide it, using the beddings of the Proto-Gene
algorithm of the Computational Transgenetics metaheuristics. In parallel, it’s
implemented a hybrid Genetic Algorithm – memétic – that objective to supply elements
the comparison of performance it enters the solution boardings. Instances are generated
for the accomplishment of the computational tests for analysis of the performance of the
boardings above cited.
Keywords: Computational Transgenetics, Hybrid Genetic Algorithm, workover rigs of
oil wells, Proto-Gene Algorithm, schedule problem.
viii
1
INTRODUÇÃO
Modelos são artifícios utilizados para representar uma situação real. O uso de
modelos ocorre devido à necessidade de uma melhor compreensão da realidade. O poder
de representatividade é a característica do modelo que o torna desejável (Goldbarg e
Luna, 2000). O elemento modelo é perceptível nas mais diferentes áreas: no telejornalismo
através da simulação ou da recriação gráfica; engenharia civil com o uso de maquetes, o
uso de gráficos na economia, na otimização combinatória com o uso dos modelos
matemáticos.
O uso de modelos matemáticos fornece uma melhor compreensão da essência
dos problemas de otimização, pois eles representam os objetivos que se pretende alcançar
com a resolução do problema, as restrições (limitações) e as relações de interdependência
existentes entre todos os componentes do problema (Jordan, 2001).
Um modelo matemático de um problema de otimização é representado por um
sistema de equações (inequações) que descrevem a essência do problema. Este modelo
determina um número n de decisões a serem tomadas, denominadas variáveis de decisão
(x1, x2, ... , xn) inter-relacionadas por uma função matemática que representa a medida da
vantagem (desvantagem) associada à tomada de decisão. Esta função é denominada função
objetivo. Qualquer restrição associada às variáveis de decisão pode ser representada por
equações (inequações) matemáticas, sendo denominadas restrições do modelo. Também
são definidos os parâmetros do modelo que são as constantes da função objetivo e das
restrições.
Na formulação de um modelo matemático, deve haver a preocupação com a
criação de um modelo que corresponda à realidade, de tal forma que a solução obtida
através do modelo possa realmente ser aplicada. Muitas vezes a criação de um modelo não
é necessária, visto que o problema pode ser representado por modelos já desenvolvidos.
Neste caso formular matematicamente o problema nada mais é do que convertê-lo para
algum modelo específico. Para o problema da programação das sondas de produção
(PPSP), ainda não se criou uma formulação matemática, sendo um dos objetivos deste
trabalho. Além da formulação matemática, é apresentado um estudo algorítmico para o
PPSP.
O PPSP foi classificado como sendo um problema de sequenciamento
(schedule problem) em máquinas paralelas e conforme Husbands e Mill (1994) é
NP-árduo.
Com o desenvolvimento da Teoria da Complexidade Computacional
(Campello e Maculan, 1994), os problemas passaram a serem classificados de acordo com
a complexidade de seus algoritmos e aqueles denominados intratáveis são alvo de interesse
de muitos pesquisadores, inclusive os da área de Otimização Combinatória, pois muitos
problemas desta área pertencem a esta classe. Diga-se, dentro do atual contexto, um dos
campos de conhecimento mais férteis, onde surge a cada dia novos problemas desafiando o
pesquisador a descortinar esses novos horizontes em busca de métodos que conduzam a
obter um melhor resultado.
Os problemas ditos intratáveis, a que se refere o parágrafo acima, são aqueles
em que não existe algoritmo de complexidade polinomial que o resolva. Enquanto que para
os problemas tratáveis tal algoritmo existe. Por outro lado, para verificar que um problema
é intratável, há necessidade de se provar que todo possível algoritmo que o resolva não
possui complexidade polinomial. Por exemplo, para o Problema do Caixeiro Viajante
(PCV) (Buriol et al, 1999) cujo objetivo é fazer um percurso que visite todas as cidades
passando uma vez por cada uma e retornando ao ponto inicial de partida, os algoritmos
conhecidos até agora são todos exponenciais. Contudo, não é conhecida prova de que seja
impossível a formulação de algoritmo polinomial para o problema (Szwacfiter, 1988).
Um problema tratável pode ser resolvido para entradas e saídas de tamanho
razoável. Enquanto que, um algoritmo de complexidade não polinomial, de algum
problema intratável, poderia em certos casos levar séculos para computar dados de entrada
e saída de tamanhos reduzidos, tornando-o inviável (Rogia, 1998).
O PCV é um exemplo clássico de problema de otimização combinatória que
não apresenta, até o presente momento, algoritmo de complexidade polinomial. Um PCV
com 20 cidades, sendo que o número de soluções viáveis é n! (n = número de cidades) tem
aproximadamente 2*1018 configurações a serem examinadas. Assumindo que 109
percursos por segundo pudessem ser enumerados, um computador possivelmente levará 78
anos para estabelecer o tour ótimo através da enumeração completa, e se n crescer em 1
unidade o tempo passa a ser em torno de 1642 anos. Esse aumento significativo do tempo
quando a instância acresce em apenas uma unidade é chamado de explosão computacional
(Campello e Maculan, 1994).
2
Através do PCV e de outros problemas clássicos citados na literatura, como por
exemplo o Problema da Coloração de Grafos (Papadimitriou e Steiglitz, 1982), do
Quadrático de Alocação (Gouvêa, 2001), percebe-se que o uso da enumeração completa é
totalmente inviável devido à explosão computacional gerada. Isto vale também para
problemas do mundo real que são um desafio e que tem peculiaridades inerentes a cada
um. Desta forma, a real necessidade é criar estratégias de propósito geral que podem
negociar com estas peculiaridades, explorando aspectos gerais dos problemas (Moscato,
1989).
As heurísticas, surgiram como métodos de solução mais abrangentes para os
problemas clássicos e do mundo real considerados intratáveis, as quais tornaram-se uma
importante área de pesquisa e aplicações. Pois, a existência de uma solução ótima, não é o
principal foco de atenção, pelo contrário, é abandonado pelo método. Parece contraditório
utilizar um algoritmo heurístico para solucionar a classe dos problemas intratáveis, visto
que o ideal da solução ótima é abandonado, porém, os algoritmos heurísticos buscam o
equilíbrio entre o desempenho computacional e a qualidade da solução. Goldbarg e Luna
(2000) definem uma heurística como sendo uma técnica que busca alcançar uma boa
solução utilizando um esforço computacional considerado razoável.
Várias
estratégias
vieram
somar-se
às
heurísticas
gerando
técnicas
denominadas de metaheurísticas. Não existe, segundo Gouvêa (2001), uma formalização
literária para o termo metaheurística, embora torna-se cada vez mais aceito no que se refere
a uma grande estratégia para o desenho de algoritmos heurísticos.
As pesquisas da grande parte das metaheurísticas têm se caracterizado pela
busca de modelos inspirados na natureza. Por exemplo, a fisiologia do sistema nervoso
central e o processo de evolução das espécies, forneceram inspiração para o
desenvolvimento de novas metaheurísticas chamadas de redes neurais artificiais (Haykin,
1999) e Algoritmos Genéticos (Whitley, 1993), respectivamente.
Devido ao fato do PPSP ser um problema generalizado de scheduling, um
conhecido problema NP-árduo, o uso da abordagem heurística se faz necessário. São
utilizadas duas heurísticas para a resolução deste problema: o algoritmo transgenético
Proto-Gene (ProtoG) da metaheurística Transgenética Computacional e o Algoritmo
Genético híbrido (AGh) – memético – que objetiva fornecer elementos para a comparação
de desempenho entre as abordagens de solução
3
A proposta do presente trabalho é apresentar algoritmos evolucionários para
solucionar o PPSP. Também são visados outros objetivos mais específicos, entre eles:
1. Definir o problema: de acordo com Goldbarg e Luna (2000), a definição
do problema é uma das fases mais importantes do processo e compreende a clara
percepção do desafio colocado;
2. Fazer a coleta e análise de requisitos que englobam o problema para
formular o modelo matemático;
3. Formular o modelo matemático do problema através das variáveis de
decisão, função(s) objetivo(s), restrições;
4. Construir um Gerador aleatório de Instâncias para obter instâncias
utilizadas como dados de entrada para os algoritmos evolucionários implementados;
5. Implementar um algoritmo ProtoG para solucionar o problema;
6. Implementar um AGh para solucionar o problema a fim de criar uma base
de comparação de desempenho computacional;
7. Comparar a qualidade das soluções obtidas pelo ProtoG e AGh e avaliar
os seus desempenhos.
O texto está estruturado em 7 capítulos. O Capítulo 2 trata da classe dos
problemas de sequenciamento. São apresentados os principais elementos que caracterizam
um problema de sequenciamento: a configuração da(s) máquina(s), das tarefas e a função
objetivo. Este capítulo faz uma descrição geral do funcionamento dos principais métodos
de solução empregados nesta classe de problemas: Branch e Bound, Busca Tabu,
Simulated Annealing, Algoritmos Genéticos e Algoritmos Genéticos híbridos; suas
vantagens e desvantagens.
O Capítulo 3 apresenta o PPSP. São abordados tópicos referentes à importância
do problema e à descrição da atividade de sondagem. Este capítulo apresenta uma
descrição formal do problema, a partir da qual um modelo matemático é apresentado.
O capítulo 4 destina-se à descrição dos Algoritmos Genéticos, enfocando suas
características, terminologia e funcionamento. Os AGh também são descritos neste
capítulo e considerações a respeito da busca local por eles utilizada são feitas. Um
pseudocódigo do AGh implementando para solucionar o problema da programação das
sondas é apresentado com a descrição da representação genética, operadores genéticos e a
busca local.
4
A metaheurística Transgenética Computacional (TC) é apresentada no capítulo
5, com a descrição do funcionamento do processo evolucionário que utiliza a informação
para guiar a busca da melhor solução. Aspectos referentes aos paradigmas do fluxo
intracelular, extracelular, evolução cultural e biológica são descritos, visto que esta
metaheurística utiliza os fundamentos dos paradigmas para desenvolver seus algoritmos.
São apresentadas as características do algoritmo transgenético ProtoG e a descrição do
pseudocódigo utilizado na implementação para solucionar o PPSP.
No capítulo 6 são apresentados os resultados computacionais obtidos, incluindo
a comparação e análise dos resultados dos algoritmos evolucionários implementados.
Finalmente, o capítulo 7, traz as conclusões finais e as sugestões para trabalhos
futuros.
5
2
PROBLEMAS DE SEQUENCIAMENTO
Neste capítulo são apresentados os problemas de sequenciamento e os métodos
mais empregados para solucionar estes problemas. Na seção 2.1 é feita uma breve
descrição do escalonamento das atividades nas empresas, demonstrando a importância
prática destes problemas e a necessidade de soluções de boa qualidade. Na seção 2.2, são
definidos os problemas de sequenciamento e apresentadas as características dos seus
elementos (tarefas, máquinas e outros parâmetros). A dificuldade de resolução dos
problemas de sequenciamento é apresentada na seção 2.3. Os métodos de solução mais
utilizados são descritos na seção 2.4 juntamente com as suas vantagens e desvantagens.
2.1
Introdução
Sequenciamento ou escalonamento são formas de tomada de decisão que
possuem um papel crucial nas empresas. No atual ambiente competitivo, o efetivo
escalonamento se tornou uma necessidade para a sobrevivência no mercado. Companhias
devem esforçar-se ao máximo para cumprir as datas firmadas, o fracasso deste
comprometimento pode resultar em uma perda significativa da imagem da empresa perante
os clientes.
Em sistemas produtivos, o escalonamento das atividades ou scheduling é uma
das atividades que compõem o planejamento da produção, onde são levados em
consideração uma série de elementos que disputam vários recursos por um período de
tempo, recursos esses que possuem capacidade limitada (Cury, 1999). Os elementos a
serem processados são chamados de ordens de fabricação ou jobs e são compostos de
partes elementares chamadas de atividades ou operações. Os principais objetivos no
escalonamento das atividades podem ser: o atendimento de prazos, datas de entrega, na
minimização do tempo de fluxo dos estoques intermediários, na maximização da utilização
da capacidade disponível, dentre outros.
Em sistemas produtivos, as ordens de produção são envidas para a linha de
produção com as respectivas datas de entrega e planos de processo (inclui informação das
seqüências de produção, que máquinas utilizar, tempos de processamento, etc.). Essas
ordens têm de ser processadas nas seqüências previstas. O processamento das ordens
muitas vezes atrasa devido a ocorrência de problemas inesperados como a falha em alguma
6
das máquinas, o que pode por em causa o cumprimento dos programas. Outros problemas
como tempos de processamento maiores do que o previsto podem produzir atrasos. Se os
materiais necessários não estiverem disponíveis no momento previsto atrasos podem
ocorrer, causando prejuízo à empresa.
Devido à importância econômica que os problemas de sequenciamento práticos
apresentam, a comunidade acadêmica e científica tem mostrado interesse por esses
problemas. Esta classe de problemas, embora de relativa simplicidade em termos de
visualização do que é requerido, apresenta extrema dificuldade em termos de encontrar a
solução ótima para os problemas mais comuns. Os problemas de sequenciamento, na
esmagadora maioria, são, por natureza, muito complexos e com resolução muito difícil, em
termos da solução ótima exata (Carvalho, 2000).
2.2
Definição e Caracterização
De uma maneira bem geral, pode-se definir um problema de sequenciamento
como sendo aquele em que se tem um conjunto de tarefas que serão executadas em
processadores obedecendo a certas restrições com o objetivo de otimizar algum critério.
Os principais elementos que caracterizam um problema de sequenciamento
determinístico são a configuração da(s) máquina(s), das tarefas e a função objetivo
(Mendes, 1999).
A configuração das máquinas serve para classificar o problema como sendo de
máquina simples ou múltiplas máquinas. Quando se têm múltiplas máquinas elas podem
ser: idênticas - todas as máquinas têm a mesma velocidade e o tempo de processamento de
uma tarefa é idêntico para qualquer máquina; uniformes – as máquinas têm diferentes
velocidades e o tempo de processamento da tarefa pode diferir devido ao fator velocidade;
não relacionadas – o tempo de processamento da tarefa na máquina é um valor arbitrário e
não tem uma característica especial.
Em relação à configuração das tarefas, elas podem estar relacionadas com
várias operações ou não. De acordo com Williamsom et al.(1997), na classe de problemas
shop scheduling cada tarefa consiste de várias operações. Os problemas desta classe podem
ser do tipo open shop, job shop e flow shop. Em um open shop, as operações de cada tarefa
podem ser processadas em qualquer ordem. No job shop, as operações de cada tarefa
precisam ser processadas em uma ordem específica para a tarefa. O flow shop é um job
shop onde as máquinas são numeradas em ordem crescente. Para cada tarefa considerada, a
7
operação k é realizada em uma máquina de numeração mais alta que a operação j, se j
precede k.
Quase todos os problemas práticos de sequenciamento podem ser descritos em
termos do problema de job-shop scheduling, o mais difícil e abrangente de todos os
problemas de sequenciamento (Husbands e Mill, 1994).
Conforme Husbands e Mill (1994) e Vaessens et al. (1994), uma definição
formal para um problema de job shop pode ser a seguinte: dado um conjunto J de n tarefas,
um conjunto M de m máquinas e um conjunto O de k operações. Para cada operação p ε O
há uma tarefa jp ε J para a qual a operação pertence e uma máquina mp ε M na qual ela
será processada num tempo tp ε N. Há também uma relação de ordem (→) em O que
decompõem o conjunto em um fluxo parcial de ordem das tarefas. Se x → y (a operação x
é processa antes de y), então jx = jy, e não tem uma operação z, diferente de x e y, tal que
x → z ou z → y. Usando como função objetivo minimizar o makespan, isto é, o tempo
decorrido para terminar o processamento de todas as tarefas, o problema é encontrar o
tempo de inicio sp para cada operação p ε O tal que:
Minimizar: Maxp ε O (sp + tp)
Sujeito a: tp ≥ 0,
∀p ε O
sx - sy ≥ ty, se y → x,
x, y ε O
(si - sj ≥ tj) ⋁ (sj - si ≥ ti), se mi = mj,
i,j ε O
Esta é uma definição de um problema de job-shop scheduling determinístico,
onde todos os tempos de processamento são conhecidos e não há restrições de quando as
tarefas poderão ser executadas. Há outras formulações para problemas de sequenciamento
(Chen e Powell, 1998). Um problema pode ser dinâmico com a inclusão de novas tarefas,
problemas nas máquinas ou mudança de prioridade das tarefas podem ocorrer, entre outros.
Os problemas de sequenciamento estão relacionados com parâmetros, dente
eles: deadlines (prazo de entrega da tarefa), release date (tempo de liberação da tarefa para
ser processada) – ambas são consideradas restrições – , tempo de preparação da máquina
dependente da seqüência das tarefas, due date (prazo de entrega), tails (período de tempo
que a tarefa, após ser processada em alguma máquina, precisa para ser completada - por
exemplo: transporte até o cliente), relação de precedência entre tarefas e valores atribuídos
às tarefas.
8
Na literatura, há distinção entre deadlines e due date pelo fato que deadlines
não pode ser violado (Sourd e Nuijten, 2001). Due data geralmente está associado com o
critério de otimizar o número de tarefas atrasadas enquanto que deadlines é uma restrição
imposta às tarefas. Uma tarefa pode estar associada com due date e deadline, tal que ela
pode ser terminada após a due date e antes do deadline.
Quando no problema, as tarefas estão associadas com deadlines e due date, o
critério de otimização é minimizar os tempos das tarefas atrasadas. Quando deadlines e
tails fazem parte de um problema, o critério de otimização é minimizar o tempo de término
da última tarefa. Sourd e Nuijten (2001) e Lancia (2000) demonstram que, se um problema
de sequenciamento, ao invés de estar relacionado com tails, está com due date são
equivalentes.
As funções objetivos podem ser: a minimização do makespan (tempo de
finalização da última tarefa), número de tarefas atrasadas, tempo de atraso máximo da
seqüência, atraso médio ou ainda, uma combinação de funções objetivos, dando origem a
um problema multi-critério (Mendes,1999).
O trabalho de Rogia (1998) combina duas funções objetivos para um problema
de sequenciamento cíclico de tarefas em processadores paralelos idênticos. Uma delas é
minimizar o tempo de finalização dos processadores e a outra é fazer com que estes tempos
sejam os mais próximos possíveis, a fim de deixar os processadores menos ociosos.
Atualmente pode-se encontrar na literatura um grande número de problemas de
sequenciamento que diferem um do outro devido à combinação do tipo de máquina, as
características das tarefas e a função objetivo (Mendes, 1999; França et al., 1999; Chen e
Powell, 1998; Sourd e Nuijten, 2001; Epstein et al., 2001; Cury, 1999).
O problema de programar o atendimento da frota de sondas de produção
(PPSP), apesar de ter sido considerado como sendo da categoria dos problemas de
sequenciamento, apresenta características que o difere dos problemas típicos desta
categoria.
A primeira diferença é a caracterização do PPSP, onde as sondas (máquinas) se
deslocam até os poços (tarefas), o que nos problemas de sequenciamento acontece ao
contrário.
Outra diferença é o critério de otimalidade, que nos problemas clássicos onde
as tarefas estão associadas a release date e due date o objetivo é minimizar o número de
9
tarefas atrasadas. Como os poços não estão relacionados com due date não faz sentido
minimizar o número de poços atrasados.
Embora o PPSP relacione os poços com release date, pois cada poço tem uma
data a partir da qual ele poderá sofrer a sondagem, o critério de otimização não pode ser
minimizar o makespan. Não faz sentido otimizar o makespan porque já existe um horizonte
de tempo definido que pode ser considerado como um deadline idêntico para todos os
poços e não é objetivo minimizá-lo.
Como os poços estão relacionados com um valor de produção que é um fator
extremamente importante a ser considerado na resolução do problema. Qualquer que seja o
critério de otimização adotado para o problema, deve considerar este fator de produção.
2.3
Complexidade
Os problemas de sequenciamento são uma classe importante dos problemas de
otimização combinatória e em geral são NP-difíceis (Husbands e Mill, 1994) portanto não
há algoritmo que os resolva em um período de tempo que seja uma função polinomial do
número de variáveis de entrada (Papadimitriou e Steiglitz, 1982). Logo, encontrar uma
solução que tenha a melhor seqüência de poços para cada sonda da frota é uma tarefa
muito difícil.
O caso mais simples de problema de sequenciamento é aquele que considera
apenas uma máquina onde as operações estão relacionadas com tempo de processamento e
data de entrega, com o objetivo de minimizar o atraso total. Conforme Mendes (1999), este
problema pertence à classe dos NP-Completo.
O problema de sequenciamento torna-se mais complexo quando envolve mais
de uma máquina, sendo que o número de soluções possíveis é (n!)m (Jain e Meeran, 1999).
O Quadro 1 mostra a variação do número de soluções possíveis à medida que varia o
número de máquinas e/ou de tarefas.
10
número de tarefas - n número de máquinas – m
número de soluções
5
1
120
5
3
1,7 milhões
6
3
373 milhões
10
10
3,96*1065
Quadro 1 – Relação entre o tamanho do problema e esforço computacional
Como pode ser observado, o número de soluções aumenta extraordinariamente
mesmo para um pequeno aumento no número de tarefas e/ou de máquinas,
impossibilitando a enumeração completa de todas as soluções para encontrar a solução
ótima. Isto demonstra que há necessidade de métodos que encontrem soluções de boa
qualidade, inclusive a ótima, desconsiderando a enumeração completa.
2.4
Métodos de solução
O atual estado da arte sugere fortemente que a abordagem exata encontrará
limitações dificilmente superáveis pela tecnologia computacional atual para o tratamento
dos problemas NP-árduos cujas instâncias (dados específicos que constituem uma entrada
para o problema) sejam complexas ou de grande porte.
Apesar da dificuldade dos métodos exatos devido à natureza exponencial, uma
estratégia enumerativa denominada de Branch and Bound (BB) (Chen e Powell, 1998;
Cury, 1999) tem sido utilizada para resolver problemas de sequenciamento. O método
baseia-se na idéia de desenvolver uma enumeração inteligente dos pontos candidatos à
solução ótima inteira de um problema (Goldbarg e Luna, 2000).
O método BB busca por uma solução ótima através do exame de somente uma
pequena parte do número total de possíveis soluções. Ele trabalha quebrando o espaço de
soluções viáveis em subproblemas menores até que uma solução ótima seja alcançada.
Na técnica BB, uma árvore construída dinamicamente representa o espaço de
soluções onde ocorre a busca da melhor solução. Para construir a árvore, é necessário
desenvolver duas tarefas (Papadimitriou e Steiglitz., 1982): branching (ramificação)– um
conjunto de soluções é representado por nodos, podendo ser particionado em conjuntos
mutuamente exclusivos. Cada subconjunto no particionamento é representado por um filho
do nodo original; lower bounding (limitação inferior) – um algoritmo está disponível para
11
avaliar e calcular o limite inferior para alguma solução no subconjunto. Esta técnica é
baseada em procedimentos e regras para permitir que grande parte da árvore seja removida
da busca e os grupos de pesquisa tem dado ênfase na construção de melhores estratégias de
branching e bounding e a geração de regras mais poderosas para remover grande parte dos
nodos da árvore no estágio de busca.
O trabalho de Lancia (2000) constrói, através de uma heurística, uma solução e
aplica a técnica de BB para resolver um problema de sequenciamento de tarefas com
tempo de liberação e tails em duas máquinas paralelas não relacionadas para minimizar o
makespan. Conforme o autor, a regra de branching pode tornar-se extremamente
ineficiente se o número de máquinas for maior do que dois. Já o trabalho de Cury (1999)
associa lógica difusa com BB para problemas flow-shop. De acordo com Jain e Meeran
(1999), o método BB é capaz de produzir soluções de qualidade, porém para instâncias de
grande porte, a árvore gerada fica muito grande e overflow da memória pode ocorrer. A
abundância de variáveis inteiras e o número de restrições na formulação, bem como a
natureza exponencial do algoritmo branch and bound, tem impedido o desenvolvimento de
procedimentos para problemas de grande porte (Ichihara, 1998)
Devido às limitações gerais das técnicas de enumeração exata, os métodos
aproximativos tornaram-se uma alternativa viável para solucionar os problemas de
sequenciamento (Jain e Meeran, 1999).
Uma regra de prioridade – pdrs (do inglês: priority dispatch rules) é método
aproximativo que estabelece prioridades para todas as operações e vai escolhendo as
operações de mais alta prioridade para determinar as seqüências do processamento nas
máquinas (Jones e Rabelo, 1998). A determinação da prioridade pode estar relacionada
com atributos das tarefas, atributos das máquinas, ou também relacionada com o tempo
atual.
As regras de prioridade podem ser estáticas ou dinâmicas (Carvalho, 2000). As
regras de prioridade estáticas são aquelas cujo valor da prioridade é independente do
instante de tempo atual, por exemplo, a regra SPT (Shortest Processing Time), em que a
tarefa com menor tempo de processamento é a que tem maior prioridade, é uma regra
estática pois o tempo de processamento não varia com o tempo. As regras dinâmicas são
regras cujo valor de prioridade varia com o tempo. A regra denominada de “Folga para
processamento” que controla o tempo que ainda há para processamento até data de entrega.
O valor desta regra varia continuamente com o tempo, por isso é uma regra dinâmica.
12
Outra forma de classificação tem a ver com o tipo de informação em que se baseia a regra:
as regras locais apenas consideram a informação relativa à fila de espera das tarefas
enquanto que, as regras globais consideram as informações de todo o sistema produtivo.
Muitas regras de prioridade podem ser encontradas na literatura e com o intuito
de dar alguns exemplos do funcionamento são descritas algumas delas, citadas em
Carvalho (2000):
¾ RANDOM (Random): as tarefas são seqüenciadas para serem executadas
nas máquinas num processo aleatório. Não há objetivo nenhum em otimizar qualquer
medida de desempenho;
¾ EDD (Earliest Due Date): as tarefas são ordenadas numa fila em ordem
não decrescente de data de entrega. As tarefas são selecionadas segundo a ordenação da
fila, onde a tarefas com a data de entrega menor tem maior prioridade. Esta regra tende a
minimizar o atraso máximo entre as tarefas da fila de espera;
¾ SPT (Shortest Processing Time): quando uma máquina fica livre, de todas
as tarefas da fila de espera, é selecionada para processamento aquela com menor tempo de
processamento nessa máquina. Em problemas com uma máquina, esta regra garante o
menor tempo de percurso médio;
¾ FCFS (First Come First Served): quando uma máquina fica livre, de todas
as tarefas da fila de espera, é selecionada para processamento aquela que mais cedo chegou
à fila. Esta regra garante que nenhuma tarefa fique eternamente na fila de espera.
As pdrs são muito simples de serem implementadas e tem baixo custo
computacional, contudo o sucesso na solução de um problema vai depender da natureza
das regras utilizadas e a qualidade da solução cai quando o tamanho do problema aumenta
(Jain e Meeram, 1999). O problema de escolher a melhor regra como uma medida de
desempenho é uma área ativa de pesquisa (Jones e Rabelo, 1998).
Assim como os métodos aproximativos, as heurísticas tornaram-se uma
alternativa viável para solucionar os problemas de sequenciamento.
A heurística Simulated Anneling (SA) (Cunha, 1999) desenvolve seus
algoritmos baseada na metáfora do resfriamento gradual, ou recozimento, processo esse
que, nos metais, leva a formação de configurações cristalográficas mais estáveis, ou seja,
com mais baixo nível de energia retida, decorrendo das propriedades físicas dos metais.
13
O algoritmo cria um espaço de soluções de um problema matemático como um
substrato de cristalização de partículas materiais. Na medida em que a temperatura do
material que está sendo tratado termicamente vai diminuindo, as partículas vão se
agregando em configurações coerentes com a energia correspondente à temperatura do
material. Com um decréscimo lento de temperatura, os átomos podem se acomodar de
forma ótima, o que minimiza a energia retida dentro da configuração da estrutura
molecular do material. Com um decréscimo rápido algumas configurações são cristalizadas
em posição de maior energia, sem terem tempo de se estruturarem em um nível inferior de
energia.
De acordo com Jain e Meeran (1999), SA é incapaz de alcançar de modo
rápido soluções de boa qualidade para os problemas job-shop scheduling. Por isso a
heurística tem sido utilizada com outros métodos para melhorar os resultados e reduzir o
tempo computacional. Yamada e Nakano (1996) utiliza SA combinada com busca local
determinística para problemas job-shop, obtendo soluções iguais e até superiores nos testes
realizados para problemas encontrados na literatura, porém foi necessário bastante tempo
computacional.
A Busca Tabu também tem sido utilizada na resolução de problemas de
sequenciamento (Rogia, 1998). Ela é uma metaheurística que explora o espaço de soluções
mantendo um histórico do processo de busca para evitar possíveis retornos a soluções já
visitadas. Este histórico é chamado de lista tabu. A busca é restringida por uma estratégia
de proibição, cuja função é controlar e atualizar a lista tabu, com o objetivo de evitar que
seqüências de soluções sejam repetidas, até um número pré-determinado de interações, e
com isto induzir a exploração de novas regiões (Glover, 1997). A Busca Tabu é uma
abordagem inteligente para guiar o processo de busca (Jain e Meeran, 1999), porém o
sucesso da busca vai depender dos parâmetros utilizados para intensificar a busca em
novas configurações ou diversificar a busca em regiões que não foram exploradas no
espaço de soluções. O tamanho da lista tabu também é um parâmetro que influencia para
guiar o processo de busca.
Outra heurística utilizada para resolver problemas de sequenciamento são os
Algoritmos Genéticos (AG’s) (Whitley, 1993) que é uma técnica, baseada numa
população, que busca ao longo de várias gerações indivíduos mais aptos. Estes indivíduos
são levados ao longo de várias gerações, evoluindo de acordo com os princípios de seleção
natural e sobrevivência dos mais aptos.
14
O princípio básico de um AG consiste em selecionar bons indivíduos –
soluções do problema – para reprodução e cruzá-los com o propósito de obter soluções
melhores que os pais. Os novos indivíduos gerados tendem a ocupar o lugar dos indivíduos
menos adaptados da população, melhorando a adaptabilidade da população como um todo.
Os novos indivíduos podem também sofrer mutação que introduz e mantém a diversidade
genética da população.
Os operadores genéticos interferem no sucesso dos AG’s e simples operadores
de cruzamento podem gerar novos indivíduos inviáveis (Husbands e Mill, 1994),
principalmente quando há relação de precedência entre tarefas. A geração de indivíduos
inviáveis causa perda de eficiência desses algoritmos.
Os trabalhos iniciais para os problemas de sequenciamento usando os AG’s
eram muito específicos, portanto não podiam ser utilizados em outros problemas de
sequenciamento. Apesar de terem alcançado sucesso, eles não foram difundidos por
apresentarem características específicas. Em Husbands e Mill (1994), há uma descrição
geral destes trabalhos e também de trabalhos recentes para os problemas job-shop
scheduling com uma análise da qualidade da solução alcançada e do esforço
computacional.
Os AG’s convencionais são muito pobres (Jain e Meeran, 1999) e o seu uso
pode estar associado com técnicas de busca local. Formando assim os Algoritmos
Genéticos híbridos (AGh), os chamados Algoritmos Meméticos (Moscato, 1989; Mendes,
1999; Buriol et al., 1999), que repontam resultados significativamente superiores,
superando várias deficiências dos AG clássicos (Radcliffe e Surry, 1994).
A qualidade da solução obtida através do uso da busca local associada ao AG
vai depender dos parâmetros utilizados para se fazer a busca e de acordo com Johnson et
al. (1989)1, citado por Jain e Meeran (1999), esta técnica é mais uma arte assim como as
escolhas dos parâmetros não pode ser de modo trivial. Visando comparar a proposta do
presente trabalho com a melhor disponibilidade no contexto evolucionário, será usado um
AGh (memético) na resolução do PPSP. No capítulo 4 é feita uma apresentação mais
detalhada dos AGh.
1
JOHNSON, D. S., C. R., M’GEOCH, L. A., SCHEVON, C., 1989, “Optimization by Simuletead
Annealing: An experimental evaluation; Part I, graph partitionin”, Operations Research 376, Nov-Dec,
865-892.
15
A metaheurística Transgenética Computacional (TC) para problemas de
sequenciamento está sendo utilizada pela primeira vez. Em outros problemas de otimização
como: o problema quadrático de alocação (Gouvêa, 2001; Gouvêa e Goldbarg, 2001),
coloração em grafos (Gouvêa, 2001; Goldbarg et al., 2001a), problema de roteamento de
veículos (Goldbarg et al., 2001b) ela tem demonstrado eficácia para encontrar soluções de
boa qualidade. O capítulo 5 descreve detalhadamente a TC.
Os trabalhos de Jain e Meeran (1999), Jones e Rabelo (1998) apresentam uma
descrição dos métodos utilizados desde o surgimento dos problemas de sequenciamento até
os dias atuais. A busca por novos métodos de solução e o aprimoramento dos métodos
existentes é uma constante para estes problemas. Isto se deve porque problemas de
sequenciamento práticos são numerosos e variados e apresentam duas importantes
características (Husbands e Mill, 1994): são de difícil resolução e soluções de boa
qualidade trazem benefícios reais.
16
3
SONDAS DE PRODUÇÃO
Este capítulo apresenta o problema que consiste na programação da frota de
sondas de produção de poços de petróleo (PPSP). As seções 3.1 e 3.1.1 resumem o
emprego das sondas e as operações realizadas pelas mesmas em poços terrestres de
produção, respectivamente. A seção 3.2 apresenta a importância do problema sob o ponto
de vista econômico, técnico e ambiental. Uma descrição formal do problema é descrita na
seção 3.3 juntamente com a formulação matemática proposta. Tendo em vista que o
problema já foi abordado, a seção 3.3 também descreve o modelo de solução proposto por
Paiva et al. (2000), apresentando as diferenças entre as abordagens.
3.1
Atividade de sondagem
O petróleo é usado desde os primórdios da civilização, porém a perfuração do
primeiro poço petrolífero ocorreu nos Estados Unidos e seu autor foi Edwin L. Drake que
após meses no trabalho de perfuração, encontra o petróleo em 27/08/1859. No Brasil, a
primeira sondagem ocorreu entre os anos de 1892 e 1896, no entanto o primeiro poço
viável comercialmente foi descoberto em 1941 na Bacia do Recôncavo Baiano e, desde
então, os investimentos e as novas buscas por jazidas de petróleo no país não pararam de
crescer. Até o final da década de 70, o foco dos investimentos foi o desenvolvimento do
segmento de refino e transporte. Com o segmento do abastecimento implantado e em
resposta aos seguidos ‘choques do petróleo’ da década de 70, começaram a ser
empreendidos maiores esforços na exploração de petróleo e gás, especialmente na área
offshore. Atualmente, se os novos campos brasileiros que estão sendo desbravados se
revelarem produtivos, a produção petróleo/gás vai aumentar de 1,3 milhões de barris dias
para 2,1 milhões em 2005, um crescimento de 61% (Caixeta, 2001). Este aumento, se
ocorrer, é muito significativo para o país, pois uma súbita alta no preço do petróleo
deixaria de ser uma ameaça para a economia.
Desde o momento em que o petróleo foi descoberto comercialmente, muitas
áreas da ciência aplicam pesquisa e estudo no setor petrolífero. Se no princípio Drake
enfrentou diversas dificuldades técnicas para encontrar o petróleo, hoje a perfuração de
poços sucede o estudo da Geologia e da Geofísica que investigam a localização das
jazidas; esta fase é denominada de exploração. Após a atividade de exploração, inicia a de
17
perfuração que comprova a existência do petróleo e avalia a condição ou não de ser
comercialmente viável. Caso seja, tem-se um campo de petróleo e começa a fase de
produção na qual atuam as sondas de produção.
As sondas de produção são equipamentos com características físicas e
complexidade tecnológica muito diversas que realizam operações de completação e
workover. Estas operações são de extrema importância, pois permitem condicionar os
poços para a produção ou até mesmo melhorá-la e são descritas, a seguir, de forma breve e
sucinta.
a)
b)
Figura 1 − Sonda de Produção
a) Terrestre b) Marítima
3.1.1
Breve visão elucidativa sobre completação e workover
Não menos importante que a descoberta do poço, são as operações de
completação e workover. Estas atividades demandam um esforço tecnológico e de mão de
obra especializada, que a cada dia vem se tornando mais exigente, tendo em vista o mundo
atual e sua dependência do petróleo/gás, o petróleo/gás e o custo que demanda a sua
produção que sendo quase que em sua totalidade, avaliado em dólar, em um mundo a cada
dia mais globalizado, sofre ou se beneficia com a ciranda do mercado financeiro.
Ao término da perfuração de um poço, é necessário deixá-lo em condições de
operar, de forma segura e econômica, durante toda a sua vida produtiva. Ao conjunto de
operações destinadas a equipar o poço para produzir óleo ou gás (ou ainda injetar fluidos
nos reservatórios) denomina-se completação e nesta são envolvidas técnicas de isolamento
18
das zonas produtoras e testes de vazão e pressão do poço, condicionando-o e equipando-o
de forma a deixá-lo em condições adequadas de produtividade.
Quanto aos aspectos técnico e operacional, deve-se buscar otimizar a vazão de
produção e tornar a completação a mais permanente possível, ou seja, aquela que minimize
a necessidade de intervenções futuras para a manutenção do poço (Thomas, 2001).
Considerando que a completação influencia em toda a vida produtiva do poço e
envolve altos custos, faz-se necessário um planejamento criterioso das operações e uma
análise econômica cuidadosa para evitar perdas dos investimentos.
Primeiramente são instalados na superfície os equipamentos que garantem a
segurança necessária para acessar o interior do poço e para a execução das fases seguintes.
Em seguida, procede a fase de condicionamento do revestimento de produção e a
substituição do fluido que se encontra no interior do poço por um fluido de completação.
Após o condicionamento do revestimento de produção, é necessário avaliar a
qualidade da cimentação. A cimentação tem a função primordial de promover vedação
hidráulica entre os diversos intervalos permeáveis, ou até mesmo dentro de um mesmo
intervalo, impedindo a migração de fluidos por trás do revestimento, bem como propiciar
suporte mecânico ao revestimento. Caso seja comprovada deficiência na vedação
hidráulica, correções são feitas. Defeitos na vedação hidráulica podem gerar diversos
problemas, tais como: produção de fluidos indesejáveis devido à proximidade dos contatos
óleo/água ou gás/óleo, prejuízo no controle dos reservatórios e operações de estimulação
mal sucedidas, com possibilidade até mesmo de perda do poço.
A operação seguinte é o canhoneio: um canhão especial desce pelo interior do
revestimento e, acionado da superfície, provoca perfurações no aço e no cimento, abrindo
furos nas zonas portadoras de óleo ou gás e permitindo o escoamento desses fluidos para o
interior do poço. Após se ter o acesso as zonas produtoras, é instalada a coluna de
produção.
A coluna de produção tem por finalidades básicas conduzir os fluidos até a
superfície, protegendo o revestimento contra fluidos agressivos e pressões elevadas;
permitir a instalação de equipamentos para a elevação artificial e possibilitar a circulação
de fluidos para o amortecimento do poço em intervenções futuras. Dependendo do
potencial produtor do reservatório, vinculado às propriedades petrofísicas da rocha e das
propriedades dos fluidos do reservatório, há necessidade da utilização de técnicas de
19
estimulação química (acidificação), mecânica (fraturamento hidráulico) ou químicomecânica, para aumentar a produtividade do poço.
Após a fase completação, inicia-se a de produção onde o óleo/gás pode vir à
superfície espontaneamente, impelido pela pressão interna dos gases. Nesses casos, temos
os chamados poços surgentes e instala-se um conjunto de válvulas conhecido como árvorede-natal para controlar a produção. Quando isso não ocorre, é preciso usar equipamentos
para promover a elevação artificial dos fluidos. O bombeio mecânico é feito por meio do
cavalo-de-pau, montado na cabeça do poço, que aciona uma bomba colocada no seu
interior. Existem ainda os bombeios hidráulicos, centrífugos e a injeção de gás, com o
mesmo objetivo.
Ao longo da vida produtiva do poço, é necessário realizar operações que visam
manter a produtividade do poço ou até mesmo melhorá-la, sendo denominadas de
workover. Uma série possível destas operações podem ser realizadas por cabo. Também há
necessidade de intervenção com as sondas de produção para realizar certas operações
quando não se pode utilizar cabo.
As sondas de produção realizam intervenções para: restaurar danos mecânicos
devido a falhas na coluna de produção ou revestimento; limpar o revestimento do poço;
estimular a produção através de alguma técnica específica; reduzir a produção excessiva de
água ou gás; alterar a forma pela qual o óleo vem até a superfície quando a pressão interna
fica reduzida ou substituir a que está com defeito.
As intervenções de workover costumam ser classificadas como: avaliação,
recompletação, restauração, estimulação e mudança do método de elevação e abandono do
poço (Thomas, 2001).
3.2
A importância do problema
O PPSP é definido em um campo de petróleo, onde se tem uma frota de sondas
que estão disponíveis para realizar intervenção num conjunto de poços que diminuíram a
produção ou que não estão produzindo. No entanto, a frota não consegue atender a
demanda dos poços, logo há poços que ficam aguardando por sondas.
Para atender à demanda dos poços, há uma frota de sondas disponíveis para o
uso que são de domínio da empresa ou que foram contratadas, por um período de tempo
maior, através de uma perspectiva orçamentária baseada num plano de metas; também há
possibilidade de alocação de novas sondas para atender à demanda, porém a relação entre o
20
custo do aluguel (custo) e o ganho na produção (benefício) deve ser muito bem analisada,
pois pode haver um aumento significativo na produção entretanto, este ganho pode não
compensar o custo do aluguel das sondas. Sendo que o custo diário das sondas varia muito,
ao longo do tempo, em função das condições de mercado ditadas principalmente pelo
preço do barril de petróleo e também em função do seu tipo ou categoria.
O PPSP é extremamente importante, não só pelo fator econômico mas também
técnico e ambiental. Do ponto de vista econômico, o problema está fortemente ligado à
produção de petróleo e produzir petróleo, num mundo globalizado, significa produção de
capital e divisas. Além do mais, o poder de atratividade exercido pelo ouro negro estimula
a aplicação de outros investimentos paralelos.
O petróleo também tem um papel importante na economia mundial, por vezes
até chamado de ouro negro, pois o seu valor monetário é elevado. Isto se deve ao fato da
imensa utilização do mesmo pois, além de produzir combustível e energia, serve como
matéria-prima para centenas de produtos, entre eles: plásticos, borrachas sintéticas, tintas,
corantes, detergentes, cosméticos, etc.
Apesar de toda a tecnologia empregada na intervenção dos poços, se faz
necessário analisar o grau dos riscos envolvidos para que não ocorram acidentes
ambientais através de vazamentos de poços, perdas ou até mesmo explosões. É aí, que o
fator ambiental deve ser considerado no problema proposto, pois o mesmo, em muitas
vezes, é responsável por uma visão negativa da imagem da empresa envolvida na
exploração petrolífera. Principalmente, quando ocorrem falhas técnicas, sendo a de maior
contundência vazamentos/derrames e, uma visão positiva da imagem da empresa, quando
associada a projetos de preservação e exploração ética e tecnicamente correta desse valioso
bem natural. O fator ambiental será considerado no PPSP através do percentual de
atratividade de cada poço que representa possíveis riscos envolvidos na atividade de
sondagem.
Outros fatores de riscos presentes na atividade de sondagem são a possível
perda de um poço devido a danos na estrutura interna provocadas pelo tempo, pelo
desgaste ou por outros fatores que causam destruição. E estes fatores de riscos são
considerados na solução do problema e são de extrema importância na tomada de decisão.
Por exemplo, um poço com elevado risco e um potencial de produção baixo pode ter
menos prioridade no atendimento pela sonda e até ser considerada inviável a sua
permanência ou, no caso de ser um poço altamente produtivo, fazer uma nova perfuração
21
para se ter acesso ao reservatório. A tomada de decisão não faz parte deste trabalho, porém
os riscos associados aos poços irão influenciar no planejamento da programação que será
um fator de influência para o tomador de decisão.
O PPSP será abordado de modo off-line, portanto as demandas dos poços são
conhecidas dentro de um intervalo de tempo e neste intervalo, os poços estão agendados
para receber a intervenção podendo ou não ser realizada na data marcada. O objetivo
principal na resolução do problema é programar o atendimento da frota de sondas obtendo,
desta maneira, o maior retorno de óleo produzido no horizonte de tempo. Além de otimizar
a produção e o rendimento através da programação do atendimento da frota de sondas,
direcionar a programação de modo a evitar acidentes ambientais, considerando os riscos
envolvidos na atividade de sondagem. Fator que será considerado através da “atratividade”
do poço.
Através da otimização, empregar de modo seguro e planejado a tecnologia de
produção que, embora à primeira vista pareça ter um custo elevado, compensa através dos
ganhos obtidos com este valioso bem natural – o petróleo.
3.3
Formulação e modelagem matemática do problema
O problema proposto neste trabalho consiste em programar o atendimento da
frota de sondas aos poços de petróleo no horizonte de tempo determinado. Conforme Paiva
et al. (2000), usualmente a programação do atendimento das sondas é definida em reuniões
de técnicos e a tomada de decisão é baseada em opiniões e cálculos superficiais. Maiores
informações e dados reais do problema não foram fornecidos pelas pessoas responsáveis
pelo gerenciamento da atividade de sondagem.
No horizonte de tempo, as demandas dos poços que necessitam sofrer
sondagem são conhecidas e cada poço está relacionado a uma data que indica o momento a
partir do qual a sonda poderá intervir no poço. Por serem conhecidas as demandas dos
poços, existe uma possibilidade real de modelá-lo como um problema de decisão off-line.
Para cada poço i ∈ P (i = 1, ..., n, onde n é o número de poços) está associado
um Qi que representa a unidade de tempo a partir da qual a sonda poderá intervir no poço i,
Vi que são as unidades de volume por unidade de tempo que se espera produzir após a
intervenção, um Di representando o tempo utilizado para a intervenção em cada poço i e
um percentual Ai que representa a atratividade do poço i.
22
A atratividade representa os riscos associados ao poço e varia entre [0,1 e 0,9].
Quanto mais próximo de 0,1 mais baixa a atratividade, ou seja, possivelmente representa
uma situação onde há riscos; quanto mais próxima de 0,9 mais alta a atratividade
supostamente correspondendo a menores riscos.
A atratividade é considerada como um fator de correção associado a cada poço
(penalidade), reduzindo a produção nominal esperada para o poço em questão. Um limite
máximo de 90% para esse parâmetro foi fixado em função de dados de campo. A
atratividade é considerada associada à produção de cada poço.
A atratividade é um percentual que não determina qual será a produção do
poço após a intervenção mas, por indicar riscos, é um parâmetro de muito peso, assim
como o valor da produção, que influencia na programação do atendimento das sondas. Um
poço com uma elevada produtividade e risco pode ter menos prioridade no atendimento do
que um poço com um pequeno volume de produção e risco.
Apesar das sondas serem idênticas em relação à velocidade da sondagem dos
poços, elas diferem em relação aos custos que vai depender da origem da sonda. Uma
sonda pode ser contratada por um período de tempo maior, através de uma perspectiva
orçamentária baseada num plano de metas, ou ser de domínio da empresa e para estes
casos os custos das sondas são de manutenção, uso, etc. Há possibilidade também de se ter
sondas alugadas por um tempo menor sendo que o seu custo é mais elevado. O custo da
sonda disponível é em função da sua utilização, enquanto que o custo da sonda alugada
está na função tempo de permanência na empresa, o que independe de seu uso ou não. A
opção pelo aluguel da sonda deve ser muito bem estudada e, quando se fizer necessária,
seu uso deve ser maximizado, principalmente através da utilização racional de cada sonda.
Cada sonda j ∈ M (j = 1, ..., m, onde m é o número de sondas) está associada
um custo cj (unidades de volume de petróleo por unidade de tempo).
De um modo bem geral, o PPSP consiste em alocar uma frota M de sondas a
um conjunto P de poços de modo não preemptivo (isto é, uma vez que uma sonda esteja
alocada para um poço, ela deverá permanecer no mesmo até o término da intervenção, sem
interrupções), objetivando maximizar o retorno da produção no intervalo entre o momento
em que o poço aguarda pela sonda e o término do horizonte de tempo.
Paiva et al. (2000) apresenta o estudo de uma metodologia para otimizar o
itinerário das sondas e o objetivo é encontrar as rotas de menor custo total para uma lista
de n poços que estão aguardando pelas sondas. No custo total são incluídas as perdas de
23
cada poço Ri = FiQsi, (Fi é o fator de perda, Qsi é o valor da produção em m3/dia),
multiplicado pelo tempo em que o poço permanece fechado (tsi); Li = Ritsi, onde
tsi = ts(i-1) + di-1,i / Vwr + twi; ts(i-1) é o tempo que o poço anterior a i permanece fechado;
di-1,i / Vwr é o tempo que a sonda leva para se deslocar de um poço até o outro (di-1,i –
distância entre o poço i-1 e o poço i, Vwr – velocidade de deslocamento da sonda) e twi é o
tempo da sondagem do poço i.
O custo total também inclui o custo da sonda utilizada na intervenção do poço i
que é: Ctad – custo de montagem, transporte e operação, somado ao custo da rota
Ct = cddi-1,i, onde cd é o custo em função do deslocamento, somada ao custo de operação no
poço i Cop = cttwi, onde ct é o custo de operação e twi é o tempo de intervenção no poço i.
Logo Ci = Ctad + cddi-1, i + cttwi.
A função objetivo proposta por Paiva et al. (2000) é:
n
min w = ∑ (Li + Ci )
i =1
O trabalho de Paiva et al. (2000) também discorre sobre quais são realmente as
perdas que ocorrem devido ao fechamento de poços que estão aguardando intervenção. A
perda real de um poço é menor do que a perda aparente – volume produzido desde o
fechamento do poço multiplicado pelo tempo sem produzir – e a diferença entre a perda
real e a aparente ocorre porque o poço ao sofrer uma interrupção volta com uma produção
suplementar causada pela pressão no interior do reservatório devido ao fechamento do
poço. Quando o fechamento de um poço interfere significativamente na produção de um
poço que está produzindo no mesmo reservatório, pode haver um aumento significativo na
produção do poço em operação, compensando em partes as perdas do poço fechado. A
perda do poço depende do nível de produção antes do fechamento, do tempo que o poço
permanece fechado, da configuração do reservatório e outras condições, logo a perda é
representada como um fator de perda. Cada poço da lista está associado a um fator de
perda, a um volume de petróleo produzido por unidade de tempo e ao tempo de
intervenção da sonda. Não existe horizonte de tempo para a programação do atendimento
das sonda e os poços não estão associados a uma data de atendimento, a partir da qual a
sonda poderá intervir.
O presente trabalho não considera o PPSP como um problema de roteamento
como proposto por Paiva et al. (2000), porque os custos associados aos deslocamentos
24
serão considerados não significativos quando comparados com os custos decorrentes da
intervenção e paralisação dos poços. Os tempos de deslocamentos entre poços são muito
inferiores aos tempos necessários à montagem e desmontagem das sondas, bem como à
duração da intervenção. O tempo de preparo das sondas está incluso no tempo necessário
para realizar a intervenção de cada poço.
O problema proposto neste trabalho foi classificado como sendo da categoria
dos problemas de schedule (sequenciamento) com tempo de liberação das tarefas em
máquinas paralelas idênticas, onde as máquinas são as sondas e as tarefas são os poços.
Usando a notação padrão para problemas de sequenciamento (Chen e Powell,
1998; Lancia, 2000), o PPSP é um problema da classe P|ri, vi|Cmax onde |P| representa a
característica de processadores paralelos idênticos (todos têm a mesma velocidade e o
tempo de processamento de uma tarefa é identifico para diferentes máquinas); |ri ,vi| ri
representa o tempo de liberação da tarefa e vi o valor agregado a tarefa – unidades de
volume produzida por unidades de tempo ; |Cmax| é o critério de otimalidade.
Em geral, problemas em máquinas paralelas requerem ao menos dois tipos de
tomada de decisão: a designação e a seqüência (Lancia, 2000). Então, para cada poço i
s
s
s
(i = 1, ..., n) está relacionado um par ( xik , tik ), onde xik indica a sonda k que intervirá no
s
s-ésimo atendimento do poço i (isto é xik = 1 se a sonda k intervir no s-ésimo atendimento
s
do poço i, 0 em caso contrário); tik o tempo de início da sondagem no poço i pela sonda k
no s-ésimo atendimento.
A formulação matemática para o PPSP é a seguinte:
1º Definição das variáveis de decisão
¾ variável de decisão binária,∀i ∈P, k∈M, s∈N:
1 se o poço i sofre sondagem no s - ésimo atendiment o da sonda k
xiks = 
0 em caso contrário
Onde: N é o conjunto (1, ..., p, onde p é o número máximo de possíveis
atendimentos de uma sonda k) máximo de s-ésimos atendimentos da sonda K
¾ variável que indica o tempo de início da sondagem, ∀i∈P, k∈M, s∈N:
tiks = o tempo de início da sondagem no poço i no s-ésimo atendimento da
sonda k
25
2º Definição da função objetivo
A função objetivo é maximizar o retorno da produção de cada poço que está
agendado para receber intervenção considerando o custo da sonda utilizada.
A produção ponderada de cada poço i {i = 1, ..., n} vai depender do tempo
restante (TPi) entre o término da sondagem e o horizonte de tempo multiplicado pelo
volume de produção do poço i (Vi – volume produzido por unidade de tempo) e pela
atratividade Ai do poço i. Portanto a produção ponderada do poço i é: PRi = TPi*Vi*Ai.
O TPi são as unidades de tempo restantes entre o término da sondagem
( t iks + Di , onde Di é a duração da intervenção) e o horizonte de tempo (tempo). A Figura 2
ilustra o TPi de dois poços 1 e 2, ambos sendo atendidos pela mesma sonda k.
t 12,k
(
)
TP1 = tempo − t12,k + D1 + 1
t12,k
D1
1
2
3
4
5
7
6
8
9
(
D2
10
11
12
)
TP2 = tempo − t 12,k + D2 + 1
tempo = 12
Figura 2 – Tempo restante entre o término da sondagem e o horizonte de tempo
Fazendo a substituição de TPi, a produção de ponderada do poço i (PRi) fica
sendo:
(
(
) )
PRiks = Vi * Ai tempo − t iks + Di + 1
∀i , k , s
(1)
Os custos das intervenções nos poços devem ser considerados. O cálculo do
custo da intervenção do poço vai depender do tipo de sonda utilizada: alugada ou
disponível.
No caso da sonda ser disponível, o seu custo é em função da sua utilização, ou
seja, do tempo de duração da intervenção do poço. Assim, o custo da intervenção do poço i
será expresso da seguinte maneira:
CS iks = c k*Di ,
∀i , k , s
(2)
Onde: ck - custo unitário de operação da sonda k;
Di - duração da intervenção no poço i.
26
Caso seja utilizada uma sonda alugada, há custos na intervenção dos poços e do
aluguel. O custo de uma sonda alugada difere da sonda disponível, pois independe do seu
uso e depende do tempo de permanência na empresa. O tempo de permanência de uma
sonda alugada na empresa será considerado como sendo o intervalo de tempo entre o início
de sua primeira intervenção e o término do seu último atendimento.
Ao calcular o custo da intervenção de um poço i pela sonda k do tipo alugada,
deve ser considerado o custo da intervenção no poço i mais o custo do aluguel e o custo do
tempo de ociosidade da sonda em relação ao poço j (j precede i no atendimento pela sonda
k). A equação a seguir representa este custo, onde o primeiro termo refere-se ao custo da
intervenção do poço i pela sonda k no s-ésimo atendimento e o custo do aluguel da sonda;
o segundo termo refere-se ao custo do tempo de ociosidade da sonda.
)
( (
CS iks = Di * (ck + cak ) + x sjk−1*cak* t iks − t sjk−1 + D j , se k for alugada ∀i, k , s (3)
Onde: cak = custo do aluguel da sonda k
Caso o poço i seja o primeiro poço a ser atendido pela sonda k do tipo alugada
– neste caso s = 1 e não há ociosidade de tempo da sonda, sendo considerado somente o
custo relacionado à duração da intervenção.
Finalmente, a função objetivo será maximizar o volume de petróleo retornado
de cada poço considerando o custo da sonda envolvida na intervenção:
n
Max ∑
∑ ∑ xiks (PRiks − CS iks )
m
p
i =1 k =1 s =1
Onde :
(
(
) )
PRiks = Vi * Ai tempo − t iks + Di + 1
CS iks
∀i , k , s
(1)
(2)
c k*Di , se k for disponível ∀i, k , s

=
s −1
s
s −1
 Di ∗ (ca k + c k ) + x jk * ca k * t ik − t jk + D j , se k for alugada ∀i, k , s (3)
( (
27
))
3º Definição das restrições
¾ Garantir que cada poço seja atendido uma única vez e que todos os poços
sofram intervenção
p
m
∑ ∑ xiks
=1
∀i
(4)
s =1 k =1
¾ Representar a disponibilidade das sondas
m
n
∑ ∑ x1ik
≤m
(5)
k =1 i =1
¾ Dois poços não podem ser executados simultaneamente em uma mesma
sonda. Para garantir esta restrição, nos baseamos na restrição apresentada em
Papadimitriou e Steiglitz (1982) onde duas tarefas não podem ser executadas
simultaneamente no mesmo processador. Quando dois poços sofrem sondagem pela
l
= 1 e o poço Pj é executado antes do poço Pi, nós temos que
mesma sonda então x sjk = xik
l
t sjk + D j ≤ t ik
. Para garantir isto, faremos T = ∑ Di e δji será uma variável inteira não
i∈ P
l
; 0 em caso contrário.
negativa igual a 1 se t sjk ≤ t ik
A restrição abaixo garante que dois poços não podem ser executados
simultaneamente em uma mesma sonda:
)
(
l
l
t sjk + D j − tik
≤ T 1 − δ ji + 2 − xik
− x sjk ,
i ≠ j,∀i,j,k , s,l (6)
l
A inequação acima é restrita somente se δji = 1 e x sjk = xik
= 1 ; nesse caso o
poço j sofre intervenção antes do que poço i pela mesma sonda k, garantindo que
l
t sjk + D j ≤ t ik
(Papadimitriou e Steiglitz, 1982).
¾ O horizonte de tempo de planejamento para a programação do atendimento
dos poços pelas sondas não poderá ser ultrapassado
n
∑
i =1
(
)
x iks t iks + D i ≤ tempo
∀ k,s
28
(7)
¾ A data de liberação do poço não poderá ser violada, logo a sonda somente
poderá intervir no poço Pi a partir do momento na qual ele fica liberado para sofrer a
sondagem
t iks ≥ Qi
∀i,k,s
(8)
¾ não negatividade: representar a integridade das variáveis
t iks ≥ 1
∀i, k , s
(9)
s
xik
∈ {0 ,1}
∀i, k , s
(10)
29
O problema formulado como um problema da Programação Linear Mista é o
seguinte:
PPSP :
∑ ∑ ∑ xiks (PRiks − CS iks )
n
Max
p
m
i =1 k =1 s =1
Sujeito à :
p
m
∑ ∑ xiks
=1
∀i
(4)
s =1 k =1
m
n
∑ ∑ x1ik
≤m
k =1 i =1
(5)
)
(
l
l
≤ T 1 − δ ji + 2 − xik
− x sjk , i ≠ j,∀i,j, k , s,l
t sjk + D j − t ik
∑ xiks (tiks + D j ) ≤ tempo
n
∀k , s
(6)
(7)
i =1
t iks ≥ Qi
∀i, k , s
(8)
s
∈ {0 ,1}
xik
∀i,k, s
(9)
∀i,k, s
(10)
t iks ≥ 1
(
(
) )
PRiks = Vi*Ai tempo − t iks + Di + 1
∀i, k, s
(1)
(2)
c k*Di , se k for disponível ∀i,k , s

CS iks = 
s −1
s
s −1
 Di ∗ (c k + ca k ) + x jk *ca k* t ik − t jk + D j , se k for alugada ∀i,k , s (3)
( (
))
n
T = ∑ Di
i =1
Onde:
s
xik
: variável binária igual a 1 quando o poço j sofre sondagem pela sonda k no
s-ésimo atendimento; 0 em caso contrário.
t iks : tempo de início da sondagem no poço i no s-ésimo atendimento da sonda k.
PRiks : produção de retorno do poço i no s-ésimo atendimento da sonda k;
30
CS iks : custo da sondagem do poço i no s-ésimo atendimento da sonda k;
Di : duração da intervenção no poço i;
Qi : unidade de tempo a partir da qual o poço i fica liberado para sofrer intervenção;
Vi : unidades de volume de petróleo produzido por unidade de tempo no poço i;
Ai : atratividade do poço i {0,1, ...., 0,9};
ck : custo de operação (em unidade de volume de petróleo por unidade de tempo) da
sonda k;
cak : custo (em unidade de volume de petróleo por unidade de tempo) do aluguel da
sonda k;
31
4
ALGORITMOS GENÉTICOS
Como os Algoritmos Genéticos híbridos (AGh) associam busca local ao
Algoritmo Genético (AG) clássico, primeiramente serão apresentadas as características
referentes a este último algoritmo. Um breve histórico da teria da evolução é apresentado
na seção 4.1, visto que os AG’s desenvolvem seus algoritmos inspirados na evolução
biológica. Em seguida, na seção 4.2, são descritas as características e o funcionamento dos
AG’s. A terminologia empregada consta na seção 4.3. Na seção 4.4, é descrita a aplicação
desses algoritmos. Finalmente, a seção 4.5 trata dos AGh, enfatizando a busca local e os
dois modos (evolução lamarckiana e efeito baldwin) como ela pode ser incorporada nestes
algoritmos. Um pseudocódigo do AGh implementado neste trabalho é descrito na seção 4.6
com itens especificando a representação genética, os operadores genéticos e a busca local.
4.1
Histórico
As idéias de Darwin sobre adaptação, seleção natural, sobrevivência dos mais
aptos, evolução e origem das espécies não são originais. Tudo isso, já havia sido levantado
por outros pesquisadores e naturalistas que o antecederam. No entanto, percebe-se que a
maioria dos antecessores de Darwin apenas levantou questões, dúvidas e até mesmo
conceitos sobre os fatos observados na natureza, sem porém, tentar ou conseguir explicar o
porquê deles existirem. Somente dois naturalistas conseguiram formular teorias para tentar
explicá-los de uma forma global, amarrando os diversos conceitos isolados já levantados
em suas épocas: Lamarck e Darwin.
Lamarck, no entanto, trilhou um caminho errado ao concluir que, na lei do
desenvolvimento progressivo, as modificações adquiridas seriam passadas para as gerações
seguintes. A forma pela qual operavam essas modificações, ele atribuiu grande importância
à ação direta das condições de vida, ao fator uso e desuso, ou seja, aos efeitos do hábito.
Para Lamarck, os animais mudavam sob pressão ambiental e essas mudanças eram
transferidas para os seus filhos. A transferência das características adquiridas era, para ele,
o principal mecanismo de evolução.
Embora a comprovação de que Lamarck estava errado a respeito do fenômeno
da evolução, foi uma idéia revolucionária que afetou todo o pensamento científico
subseqüente, em particular Charles Darwin (Capra, 2001).
32
Darwin, após o regresso de sua viagem ao redor do mundo, apresenta em 1958
sua teoria da evolução através da variação casual e seleção natural. No ano seguinte, com o
livro intitulado On the Origem of Species by Means of Natural Selection, Darwin relata
suas análises e conclusões finais sobre o assunto.
Conforme Capra (2001), a visão que Darwin tinha sobre hereditariedade
causava uma falha séria na sua teoria, pois acreditava-se na época que as características
biológicas herdadas por um indivíduo eram uma mistura das de seus pais, com ambos os
pais contribuindo com cerca de 50 por cento de suas características para seu filho. Isto
implica que a prole de um pai seria capaz de transferir somente 25 por cento dessas
características para a geração seguinte. Dessa forma, a nova característica se diluiria
rapidamente, com pouca chance de se estabelecer por meio da seleção natural.
Gregor Mendel solucionou o problema de Darwin ao deduzir que havia
unidades de hereditariedade as quais não se misturavam no processo da reprodução, mas
eram transmitidas de geração em geração sem mudar de identidade.
A moderna teoria da evolução – neodarwinismo - combina as idéias de Darwin
sobre mudanças evolutivas com a descoberta de Mendel. Na teoria neodarwinista, toda
variação evolutiva resulta de mutação aleatória seguida por seleção natural.
A teoria da evolução e a computação são contemporâneas, nasceram
praticamente na mesma época: Charles Babbage, um dos fundadores da computação e
amigo pessoal de Darwin, criou sua máquina analítica em 1883 (Smiderle, 2001). Ambos,
nem imaginavam que as duas áreas pudessem estar atualmente fortemente ligadas através
da Computação Evolucionária (CE), que é a área da Ciência da Computação que
desenvolve técnicas inspiradas na analogia dos princípios da evolução biológica para
solucionar problemas considerados intratáveis.
Um dos trabalhos iniciais pertencentes a CE foram os Algoritmos Genéticos
(AG’s). John Holland foi quem começou seriamente a desenvolver as primeiras pesquisas
neste trabalho e foi gradualmente refinando suas idéias. Em 1975 publicou o seu livro
“Adaptation in Natural and Artificial Systems”, hoje considerado a Bíblia dos AG’s. Nos
anos 80, Davi Goldberg, aluno de Holland, consegue o primeiro sucesso em aplicação
industrial desses algoritmos. Desde então, estes algoritmos vêm sendo aplicados com
sucesso nos mais diversos problemas de otimização e aprendizado de máquinas.
33
4.2
Definição
Os Algoritmos Genéticos (AG’s) referem-se a um método de busca inspirado
nos princípios de seleção e evolução natural. Sua denominação originou-se da analogia
entre a representação de uma estrutura complexa através de um vetor de componentes e a
idéia da estrutura genética de um cromossomo. Basicamente, o ponto de referência é gerar,
a partir de uma população de cromossomos, novos cromossomos com propriedades
genéticas superiores às de seus antecedentes. Os cromossomos estão associados a soluções
de um problema onde, a partir de um conjunto de soluções atuais, são geradas novas
soluções superiores às antecedentes, sob algum critério pré-estabelecido.
Durante o curso da evolução, as populações naturais evoluem conforme os
princípios de seleção natural e sobrevivência da adaptação. Ou seja, indivíduos que se
adaptam melhor ao ambiente, possuem maiores chances de sobreviver e reproduzir,
enquanto que os indivíduos menos aptos tendem a serem eliminados. Isto significa que os
genes dos indivíduos altamente aptos influenciarão um número crescente de indivíduos a
cada geração, e a sua espécie evolui para se tornar cada vez mais adaptada ao seu
ambiente.
Um AG simula o processo de evolução, partindo de uma população inicial de
indivíduos e aplicando operadores genéticos em cada geração para buscar uma população
mais evoluída.
Cada indivíduo da população é codificado em um cromossomo, o qual
representa uma solução possível para um determinado problema, enquanto a adaptação do
indivíduo é avaliada através de uma função de aptidão. Aos indivíduos mais adaptados
(melhores soluções) são dadas maiores chances de se reproduzirem, fazendo com que os
seus genes passem para a nova geração, simulando desta forma a seleção natural proposta
por Darwin em que os indivíduos mais aptos têm maiores chances de sobreviverem e
passarem as suas características para sua prole, que melhor adaptada, ao longo dos anos se
tornará maioria na população. A descendência ou nova população, pode substituir toda a
população atual ou substituir apenas os indivíduos de menor ajuste.
O processo evolutivo dos AG’s representa a busca por indivíduos mais
adaptados, ou seja, a busca por soluções de melhor qualidade. O ciclo de seleção, geração e
avaliação é repetido até que uma solução satisfatória seja encontrada ou até um número
determinado de interações. Na Figura 3 está representado genericamente este ciclo.
34
Meta-Algoritmo Genético
Início
Gerar uma população inicial
Avaliar a fitness dos indivíduos da população
Repetir
Início
Selecionar um conjunto de pais na população
Cruzar os pais de modo que se reproduzam
Avaliar a fitness dos filhos gerados
Substituir os filhos julgados inadequados
Fim
Até critério de parada ser atendido
Fim
Figura 3 - Meta-Algoritmo Genético
Fonte – Goldbarg e Luna, 2000. p. 420
Os AG’s possuem as seguintes características gerais:
¾ operam em um conjunto de pontos e não a partir de pontos isolados,
caracterizando-os como um algoritmo populacional que utiliza um conjunto de indivíduos
para vasculhar o espaço de soluções. É um processo estruturalmente paralelo (Mendes,
1999), com troca de informações entre as soluções. A propriedade do paralelismo
intrínseco, através da qual os AG’s não melhoram apenas única solução, mas permitem a
simultaneidade da avaliação das soluções;
¾ operam em um conjunto de soluções codificadas (cromossomos) e não
diretamente no espaço de busca (Goldbarg e Luna, 2000). Por trabalharem sobre a
codificação do problema, permitem resolver muitos problemas de otimização diferentes
(Ichihara, 1998);
¾ necessitam como informação somente o valor da fitness;
¾ são probabilísticos.
4.3
Terminologia
A terminologia empregada nos AG’s consiste basicamente de analogias
extraídas da biologia. Os termos que seguem são intensamente usados por esses
algoritmos:
- cromossomo: representa um indivíduo na população ou uma estrutura de
solução candidata para o problema;
- população: conjunto de indivíduos (isto é conjunto de soluções do problema);
35
- gene: divisão conceitual ou bloco funcional de um cromossomo, capaz de
codificar uma característica (uma variável do problema);
- alelo: característica ou valor numérico que representa um gene (os possíveis
valores de uma variável do problema). Como exemplo, um cromossomo que utiliza
codificação binária, possui em cada posição (locus) dois possíveis alelos: 0 e 1;
- fitness: medida de aptidão de um indivíduo. A fitness normalmente está
associada ao valor da função objetivo para uma dada solução;
- genótipo: representa a estrutura do cromossomo codificado;
- fenótipo: representa a estrutura do cromossomo decodificado.
- cruzamento (crossover): operador genético que permite a obtenção de
indivíduos a partir da troca de partes entre dois cromossomos;
- mutação: operador genético que permite mudança ou troca de um ou mais
alelos de um cromossomo.
Na Figura 4, são dados alguns exemplos dos termos acima descritos através de
uma solução viável S = (1, 2, 3, 4, 5, 1) para o problema do caixeiro viajante com 5
cidades. Esta solução é representada por um cromossomo na forma binária
p = (001;010;011;100;101), onde fica implícito que após a cidade 5 retorna-se à cidade
origem 1.
fenótipo
1
fitness = à distância percorrida pelo caixeiro viajante
5
Genótipo= (001,010,011,100,101)
2
4
Cromossomo = (001010011100101)
3
gene
Figura 4 - Exemplo de alguns termos empregados pelos AG’s
36
4.4
Aplicação
De acordo com Ichihara (1998), não existe um consenso rigoroso sobre o
campo de aplicabilidade dos AG’s e o seu uso é interessante para um determinado
problema se:
¾ o espaço a ser pesquisado for grande, ou seja, com um grande número de
soluções possíveis, é impossível pesquisá-lo exaustivamente até que seja encontrado um
ponto ótimo global;
¾ o espaço é formado por uma simples colina lisa, um algoritmo
gradiente-ascendente é mais eficiente que um algoritmo genético;
¾ o espaço de pesquisa não for bem entendido, em caso contrário, os métodos
de pesquisa que usam heurísticas de domínio específico podem ser utilizadas com a mesma
desenvoltura de um algoritmo genético;
¾ o usuário deve ficar satisfeito com uma boa solução e ser beneficiado pela
rapidez com que esta solução é encontrada, já que os AG’s podem ou não encontrar um
ótimo global.
Há uma vasta aplicação dos AG’s e AGh, tanto para problemas clássicos da
literatura: coloração em grafos (Fleurent e Ferland, 1994), caixeiro viajante (Zuben, 2000;
Potvin, 1996; Buriol et al., 1999), problemas de sequenciamento (Husbands e Mill, 1994;
Mendes, 1999; Shi, 1997; Yamada e Nakano, 1996), como para problemas de ordem
prática.
Santos e Cunha (2000) usam AG’s associada `a realidade virtual para
determinar a posição da cabine de controle em plataformas de perfuração de poços de
petróleo.
Kornosinski et al. (1998) apresentam algumas considerações teóricas sobre os
uso dos AG’s como um instrumento de apoio no processo de aprendizagem, onde estes
algoritmos seriam utilizados como uma ferramenta para compreensão da modelagem de
problemas. O sistema baseado em AG’s funcionaria como um instrumento de
aprendizagem, a partir do qual um estudante modela um problema e avalia a qualidade da
solução gerada pelo sistema. Se a solução gerada não for satisfatória, cabe ao estudante
analisar a modelagem fornecida do problema ao sistema.
Ichihara (1998) propõem um método de solução híbrido baseado em regras de
prioridade e AG para o problema da programação de projetos com restrição de recursos na
construção de edifícios dotados de múltiplos pavimentos-tipo. O modelo se propõe a
37
minimizar os desvios mensais entre os recursos monetários disponíveis e as despesas, bem
como promover a continuidade do trabalho nas atividades repetitivas.
Rebello e Hamacher (2000) propõem uma metodologia para resolver o
problema que envolve o recolhimento da correspondência de 39 agências de correios do
Rio de Janeiro para a agência central. Foi implementado um AG composto de duas fases
que se alternam: a primeira fase (AG de zoneamento) busca separar as agências em grupos;
na segunda fase (AG de roteamento) são geradas rotas de distância mínima entre as
agências que estão em um determinado grupo.
Smiderle (2001) também apresenta um AG de duas fases para determinação do
caminho mais curto no trabalho de leitura dos medidores de contas de água. Na primeira
fase dá-se à formação dos subgrupos de atendimento para cada leiturista, na fase seguinte
determina-se o roteamento em cada subgrupo.
Guyaguler e Home (2000) desenvolveram um AGh para determinar a
localização dos poços de petróleo num reservatório.
4.5
Algoritmo Genético híbrido - memético
O Algoritmo Genético híbrido (AGh) combina busca local com o mais
tradicional algoritmo genético (Whitley et al., 1994). A busca local é utilizada para tentar
melhorar uma população inicial ou os novos descendentes gerados através dos operadores
genéticos. Uma busca local possibilita que a partir de uma solução se chegue a outras
soluções de qualidade superior ou inferior. Rotinas de busca local se baseiam em uma
definição de vizinhança que estabelece uma relação entre soluções. Pode-se definir a
vizinhança de uma solução como o conjunto de soluções que podem ser geradas
executando-se qualquer movimento ou conjunto de movimentos possíveis, permitidos pela
política da própria vizinhança.
A busca local pode ser vista como um tipo de aprendizagem que ocorre durante
o tempo de vida de um indivíduo (Gouvêa, 2001).
A forma de busca local utilizada comumente em AGh é equivalente à idéia de
evolução de Lamarck, isto é, um aprendizado que modifica o código genético do indivíduo.
Outro caminho onde aprendizado e evolução interagem, é permitir que o aprendizado
mude o valor da fitness, o que representa um aprendizado conhecido como efeito Baldwin,
aprendizado este que não afeta o código genético.
38
Para Lamarck, os órgãos que desenvolvem intensa atividade crescem e se
tornam mais eficazes e, aqueles pouco utilizados se atrofiam e degeneram (lei do uso e
desuso). Estas alterações poderiam ser transmitidas aos descendentes (herança de
caracteres adquiridos), portanto para ele existia um mapeamento de condições ambientais e
fenótipos que determinam o genótipo, o que é biologicamente impossível.
Apesar da teoria evolucionista que Lamarck propôs estivesse errada, é possível
para um indivíduo aprender para facilitar a evolução. As idéias de que o aprendizado
poderia auxiliar a evolução surgiram em 1896 e foram propostas por James Mark Baldwin.
Estas idéias, subseqüentemente conhecidas como efeito Baldwin, foram
consideradas como um "novo fator" da teoria evolutiva. Baldwin considerava que a
aprendizagem individual pode explicar fenômenos evolucionários que parecem requerer
herança lamarckista. Ele explica que a aprendizagem inicialmente facilita a evolução de
comportamentos complexos, posteriormente, os comportamentos aprendidos são
substituídos pelo comportamento instintivo. Assim, comportamentos aprendidos poderiam
ser comportamentos instintivos em gerações subseqüentes, sem apelar à herança
lamarckista (Turney, 1996). Portanto, o efeito Baldwin não requer o mapeamento de
fenótipo e ambiente em genótipo, como requer a teoria de Lamarck, o que biologicamente
não é aceitável.
Através da Figura 5 é ilustrado o conceito de busca local implementada nos
AGh, demonstrando como o aprendizado, tanto lamarckiano como baldwiniano, atua em
conjunto com os AG’s. O eixo horizontal representa o espaço de soluções de um problema
de otimização qualquer, onde três soluções estão representadas através dos indivíduos “a”,
“b” e “c”, sendo que a fitnes de cada indivíduo f(a), f(b) e f(c), respectivamente, medida no
eixo vertical.
39
fitnes
f(a)
f(b)
f(c)
f(b’)
f(a’)
a
a’
c
b b’
Espaço de soluções
Figura 5 - Ilustração do conceito de busca local no espaço de soluções
Baseado no valor de fitnes de cada indivíduo, após a ordenação em ordem
decrescente de adaptação, teríamos o indivíduo “c” como sendo o mais adaptado, seguido
por “b” e “a”. Com a aplicação do aprendizado, dependendo da busca local implementada
em cada um dos três indivíduo, “a“ passaria a ser o mais adaptado seguido por “b“ e “c”.
No aprendizado lamarckiano, as características adquiridas são herdadas pelo
código genético. Portanto, a aplicação do aprendizado substtitui o genótipo do indivíduo
“a” por “a’“ e “b” por “b’“, com os novos valores de fitnes f(a’) e f(b’), respectivamente. A
aplicação do aprendizado lamarckiano, fez com que o genótipo dos indíviduos “a” e “b” se
perdesse.
Já no aprendizado baldwiniano, o indivíduo é avaliado em sua vizinhança,
porém as informações obtidas não são atribuídas ao seu código genético, somente o valor
de sua fitnes é alterado. Portanto o aprendizado não afeta o código genético do indivíduo.
Assim, indivíduo “a” com o valor de fitnes f(a) seria atualizado para f(a’). O mesmo
aconteceria para “b” com o valor de sua fitness alterado para f(b’). O indivíduo “c”
permanece inalterado pois é um mínimo local.
O efeito Baldwin é puramente darwiniano: as características adquiridas não são
herdadas pelo indivíduo e sim, a capacidade de adquirir estas caracterísiticas (Turney,
1996).
Em geral, os AGh possuem um melhor desempenho que os algoritmos
genéticos clássicos (Gouvêa, 2001) porém a implementação do aprendizado implica em
custos (Mayley, 1996; Turney, 1996).
Conforme Whitley et al. (1994), ambas as estratégias de aprendizado para os
testes realizados são mais eficientes que o AG convencional, sendo que o aprendizado
40
balwiniamo, para alguns casos, foi mais eficiente convergindo para um ótimo global
quando o aprendizado lamarckiano convergia para um ótimo local. Porém, a estratégia
baldwiniana foi mais lenta que a lamarckiana.
4.6
Algoritmo Genético híbrido (memético) utilizado neste trabalho
Para uma melhor compreensão da estrutura do AGh implementado neste
trabalho, é apresentado um pseudocódigo com explicações detalhadas do funcionamento
do mesmo. A representação genética, os operadores genéticos e a busca local utilizada são
descritos na seqüência.
Procedure AGh
begin
Inicia população_principal usando Carrega_pop_inicial
Avalia_fitnes (população_principal)
Repeat /*laço de evolução da população*/
i:=1;
while i< #descendentes do
seleciona dois pais (Dpais) da população_principal
novo_individuo:= recombinação(Dpais)
if novo_individuo=viável then
avalia_fitness (novo_individuo)
adiciona (novo_individuo) na população_intermediária
i:=i + 1;
for i:=0 to #mutação do
seleciona individuo da população_intermediária
individuo_aux:= individuo
mutação(individuo_aux)
if individuo_aux = viável then
avalia_fitness (individuo_aux)
adiciona (individuo_aux) na população_intermediária
forEach individuo i ε população_intermediária do Busca_local(i)
População_principal:= Seleciona (população_principal,
população_intermediária)
until (condição de parada = TRUE)
end;
Como pode ser observado, o algoritmo possui cinco partes principais: o inicio,
dois laços – recombinação e mutação -, o aprendizado (busca local) e a parte de
atualização.
41
1. Inicialização
Inicia população_principal usando Carrega_pop_inicial
Avalia_fitness (população_principal)
Uma população é o conjunto de indivíduos, isto é, o conjunto de soluções do
problema. O passo inicial do algoritmo é obter uma população inicial que pode ser obtida
de vários modos: aleatoriamente, através de heurísticas, etc. A população inicial neste
trabalho foi obtida de modo totalmente aleatório, sendo que os seus indivíduos são sempre
viáveis. Um indivíduo representa uma solução do PPSP e a viabilidade do mesmo garante
que cada poço está relacionado a uma sonda e que o horizonte de tempo da programação
das sondas não é ultrapassado. Na seção 4.6.1 há uma descrição mais detalhada do
indivíduo e da sua representação genética. Pelo fato de trabalhar com uma população
viável e a dificuldade de obtê-la de modo aleatório, a mesma foi gerada quando da criação
das instâncias utilizadas para a realização dos testes computacionais. Deste modo uma
instância, além de conter as informações referentes aos poços, as sondas, contém também a
população inicial. Após carregar a população principal inicial através da função
Carrega_pop_inicial, é feita a avaliação da fitnes – função avalia_fitness – de todos os
indivíduos.
A fitness é a medida de aptidão do indivíduo, ela quantifica a qualidade do
indivíduo. Para tanto ela deve guardar uma relação estreita com a função objetivo para uma
dada solução do problema sendo que, em muitas vezes, é a própria. No PPSP, a fitness do
indivíduo é o valor da função objetivo apresentado na formulação.
2. Laço de recombinação
i:=1;
while i< #descendentes do
seleciona dois pais (Dpais) da população_principal
novo_individuo:= recombina (Dpais)
if novo_individuo=viável then
avalia_fitness (novo_individuo)
adiciona (novo_individuo) na população_intermediária
i:=i + 1;
Depois de definido o número de descendentes gerados (20% do número de
indivíduos da população principal), dá-se inicio o laço de recombinação, onde dois pais da
população são escolhidos. Esses pais irão gerar um único descendente através da função
42
recombina (Dpais). Se o filho gerado é viável, é feita a avaliação da sua fitness e
adicionado na população intermediária separada da principal de forma que os filhos não
participem na recombinação na mesma geração em que foram gerados. Se o filho gerado
for inviável, ele é desprezado.
A escolha dos pais para a geração de descendentes é através do método da
roleta ponderada (Roulette Whel). Este método permite que indivíduos com maior
adaptabilidade tenham maiores probabilidades de serem escolhidos para gerar um novo
indivíduo, sem eliminar a possibilidade de indivíduos poucos adaptados serem
selecionados.
Na seleção pelo método da roleta ponderada, o intervalo [0,1] é divido entre os
indivíduos da população de modo que, indivíduos com maior valor adaptabilidade tenham
fatias proporcionalmente maiores. Baseado no valor de fitness de cada indivíduo, calculase a porcentagem que o indivíduo contribui para a adaptabilidade total da população.
A Figura 6 representa o funcionamento da escolha pelo método da roleta para
um problema de maximização. Se o número 0,222 for sorteado, o indivíduo 2 é escolhido
para gerar um novo indivíduo. Percebe-se claramente, pelo gráfico de setores, que os
indivíduos com maior adaptabilidade tem maior probabilidade de serem sorteados.
0
Indivíduo Aptidão
1
8
2
9
3
14
4
4
5
20
percentual
0,146
0,163
0,255
0,073
0,363
adaptabilidade total = 55
0,146
1
5
0,647
2
4
3
0,319
0,574
Figura 6 - Exemplo de funcionamento do método de seleção usando roleta
Para manter a diversidade e evitar a rápida convergência, foi criado um
mecanismo que atua em conjunto com o método da roleta. A adoção do mecanismo impõe
que no início do laço de recombinação todos os indivíduos da população principal podem
ser escolhidos para gerar descendentes. À medida que são selecionados e gerarem um filho
viável, ficam excluídos de serem selecionados novamente neste laço. Esta exclusão se
43
aplica a todos os indivíduos da população com exceção do melhor. Foram realizados testes
onde não foi adotado este mecanismo e os resultados demonstraram uma rápida
convergência dos indivíduos da população, causando perdas na qualidade das soluções
obtidas. Mendes (1999) adotou o mesmo mecanismo, o que levou a melhores resultados
em relação ao método original da roleta.
3. Laço de mutação
for i:=0 to #mutação do
seleciona individuo da população_intermediária
individuo_aux:= individuo
mutação(individuo_aux)
if individuo_aux = viável then
avalia_fitness (individuo_aux)
adiciona (individuo_aux) na população_intermediária
Do mesmo modo que laço de recombinação, o laço de mutação inicia depois de
definido o número de indivíduos da população intermediária que sofrerão mutação (0,1%).
Feito isso, um indivíduo é selecionado aleatoriamente e sofre mutação. A viabilidade do
indivíduo mutante é verificada, em caso positivo, sua fitness é avaliada e o novo indivíduo
é adicionado à população intermediária. Caso a mutação provoque inviabilidade, o
individuo mutante é desprezado, permanecendo no seu estado original.
4. Aprendizado
forEach individuo i ε população_intermediária do Busca_local(i)
Nesta etapa é feita uma tentativa para melhorar os filhos obtidos através do
cruzamento dos pais. Uma busca local na vizinhança é aplicada sobre cada indivíduo da
população intermediária. Os métodos de busca em vizinhança, também são comumente
utilizados como uma base para algoritmos e soluções heurísticas de problemas de
otimização combinatória, ou para melhorar uma solução que tenha sido gerada por uma
outra heurística (Papadimitriou e Steiglitz, 1982).
5. Atualização
População_principal:= Seleciona (população_principal,
população_intermediária)
44
Nesta etapa é feita a atualização da população, onde os indivíduos antigos são
substituídos por novos, sendo que o tamanho da população permanece constante.
A atualização da população é um processo totalmente determinístico.
Primeiramente, a população principal e a população intermediária são ordenadas em ordem
não-decrescente do valor de fitness. Os novos indivíduos mais adaptados irão substituir os
indivíduos menos adaptados da população principal. Outra precaução é evitar indivíduos
clonados na população principal. Essa condição exige que um novo indivíduo para ser
inserido na população principal seja único, proibindo a presença de soluções duplicadas.
Desta forma, mantendo a diversidade da população.
Nesta etapa, é verificado se foi gerada uma solução melhor que a melhor
solução corrente (melhor solução até o momento). Caso tenha surgido uma solução melhor
que a corrente, é realizada uma busca local nesta solução.
4.6.1 Representação Genética
Na Biologia, cromossomos são extensas cadeias de compostos químicos que
contém a descrição genética dos seres vivos. No contexto dos AG’s, um cromossomo é
uma solução candidata, ou seja, um ponto no espaço de busca; cada cromossomo codifica
uma solução do problema e seu valor contribui para o cálculo da função objetivo da
solução que ele representa.
Uma das formas de representação dos AG’s é a representação binária
(zero - um). A motivação para o uso de codificação binária vem do teorema dos esquemas
(schemata theory), utilizada com relativo sucesso para explicar por que os algoritmos
genéticos funcionam (Altenberg, 1994).
Outra forma de representação utilizada é por números reais e inteiros, sendo
esta uma forma mais simples de representação (Bramlette, 1991). Conforme Michalewicz
(1996), para problemas com parâmetros reais, AG’S com representação inteira ou em
ponto flutuante freqüentemente apresentam desempenho superior à codificação binária.
Michalewicz (1996) argumenta que a representação binária apresenta desempenho pobre
quando aplicada a problemas numéricos com alta dimensionalidade e onde alta precisão é
requerida
Embora o teorema da representação por inteiros ou reais não foi desenvolvido,
diversos pesquisadores têm mostrado que estas representações otimizam da mesma
maneira que o AG de codificação binária (Antonisse, 1989; Eshelman e Schaffer, 1992).
45
Além de um tipo adequado de representação genética utilizado, se faz
necessário o uso de operadores genéticos eficientes para não gerar com freqüência soluções
inviáveis, mantendo desta forma o desempenho dos AG’s.
Independente do tipo de representação genética utilizada, sempre se deve
verificar se ela está corretamente associada com as soluções do problema analisado, ou
seja, que toda solução tenha um cromossomo associado e que todo cromossomo gerado
esteja associado a uma solução válida do problema em questão. Desta forma, uma
representação genética deve ser capaz de representar todas as possíveis soluções de um
problema.
A representação escolhida para uma solução do PPSP é um cromossomo cujos
alelos assumem dois valores: um caractere do tipo ‘S’ ou ‘P’ para indicar se trata de sonda
ou poço, respectivamente; um valor inteiro e distinto no intervalo [1,m] se estiver
associado com ‘S’ ou no intervalo [1,n] se estiver associado a ‘P’. Desta forma, um
exemplo de cromossomo válido para um problema com 8 poços e 3 sondas seria <S1 P1 P2
S3 P4 P5 P6 S2 P3 P7 P8>. A sonda 1 irá atender a seqüência de poços 1 e 2; a sonda 3 os
poços 4, 5 e 6 e finalmente a sonda 2 os poços 3, 7 e 8.
Cada sonda irá intervir seguindo a ordem da seqüência dos poços que a
sucedem, podendo também não estar relacionada com poços e ser considerada uma sonda
sem serviço. No cromossomo <S1 S2 P1 P2 P3 S3> as sondas 1 e 3 não realizam
sondagem e são consideradas sem serviço.
Cada poço precisa estar relacionado a uma sonda e sofrerá intervenção pela
sonda mais próxima que o antecede. Sendo assim, o cromossomo <P1 P2 S1 P4 S2 P3>
não é válido pois os poços 1 e 2 não estão relacionados com sondas. Todo poço precisa
estar relacionado a uma sonda, porém nem toda sonda precisa estar atribuída a um poço.
4.6.2 Operadores Genéticos
Os operadores genéticos são instrumentos de variação dos AG’s. Analisando
sob o prisma do problema, são operadores cuja função é criar novos pontos de busca no
espaço de solução, com base nos indivíduos da população atual.
4.6.2.1 Cruzamento
O cruzamento (crossover) é um operador genético que produz novos indivíduos
contendo informações a partir da combinação dos cromossomos dos pais. Existem os mais
variados tipos de operadores de cruzamento na literatura (Mendes, 1999) e essa variedade
46
ocorre devido a necessidade de se ter operadores eficientes que não gerem descendentes
inviáveis e que apresentem um bom desempenho.
Para o problema proposto neste trabalho, inicialmente foram desenvolvidos
dois operadores de crossover: o OX (Goldbarg e Luna, 2000) e o LOX (Ichihara, 1998).
4.6.2.1.1
Operador OX
O operador OX (operador order crossover) constrói um cromossomo filho
herdando uma seqüência parcial de um dos pais e mantendo a ordem relativa do outro. O
procedimento inicia com a escolha de dois pais. Um fragmento de um deles é escolhido
aleatoriamente e copiado para o filho, mantendo as mesmas posições do pai origem. As
posições não preenchidas do cromossomo filho, agora serão completadas com a do outro
pai, iniciando-se a partir do segundo ponto de corte e ignorando as informações que o filho
já possui. O exemplo a seguir ilustra a idéia do procedimento:
Pai A: S1 P2 P3 S2 P5 P6 P4 P1
Pai B: S2 P1 P3 P6 S1 P5 P2 P4
Filho:
__ __ S2 P5 P6 __ __ (Pai A)
1ª etapa
__ __ S2 P5 P6 P2
__ __ S2 P5 P6 P2
P1 __ __ S2 P5 P6 P2
P1 P3 __ S2 P5 P6 P2
P1 P3 S1 S2 P5 P6 P2
2ª etapa – filho completo
S1 P1 P3 S2 P5 P6 P2
3ª etapa - filho viável
_
P4
P4
P4
P4
P4
No exemplo acima, o fragmento S2 P5 P6 foi selecionado do pai A e copiado
na mesma posição no filho. As posições não completadas foram preenchidas seguindo a
seqüência do pai B a partir do segundo ponto de corte, desprezando as informações que o
cromossomo filho já contém.
No decorrer dos testes computacionais, este operador mostrou ineficiência para
tamanhos de cromossomos maiores que 50, gerando um número muito grande de
descendentes inviáveis que violavam o horizonte de tempo. Por causar perdas do
desempenho computacional, optou-se por não fazer uso deste operador.
4.6.2.1.2
Operador LOX – operador escolhido
O Cruzamento de Ordem Linear (LOX), uma variante do operador OX, foi
elaborado por Faulkenauer, para satisfazer a todos os requisitos que o problema de job-
shop scheduling exige (Ichihara, 1998), isto é, manter a relação de precedência das
47
operações para cada tarefa. Desta forma, se uma dada operação é realizada antes de outra
em ambos os pais, provavelmente esta relação se manterá no filho.
Para PPSP, não existe relação de precedência entre os poços, porém a
seqüência de poços atendidos por uma sonda não poderá violar o horizonte de tempo. O
operador LOX, por ter a característica marcante de manter a posição relativa dos poços,
reduz a possibilidade de gerar novos indivíduos que violem a restrição do tempo de
programação, logo reduzindo o esforço computacional na geração dos indivíduos da
população intermediária.
Após a escolha de dois pais A e B, dois pontos de corte são escolhidos ao
acaso. O novo indivíduo vai receber todas as informações do pai A marcando com um
asterisco as posições na qual ele possui em comum entre os pontos de cruzamento com o
fragmento do pai B. os asteriscos são substituídos pelos genes mais próximos, mantendo a
ordem de seqüência e forçando os asteriscos a ocuparem a região entre os pontos de corte.
O fragmento do pai B é copiado para a região do novo indivíduo que contém os asteriscos.
O exemplo a seguir ilustra a idéia do procedimento:
Pai A: S1 P2 P3 S2 P5 P6 P4 P1
Pai B: S2 P1 P3 P6 S1 P5 P2 P4
Filho:
S1 P2 P3 S2 P5 P6 P4 P1 (Pai A)
Filho: * P2 P3 S2 *_ *_ P4 P1
1ª etapa – marcar posições com asterisco
P2 * P3 S2 * * P4 P1
P2 P3 * S2 * * P4 P1
P2 P3 S2 * * * P4 P1
P2 P3 S2 * * * P4 P1
2ª etapa – agrupar posições dos
asteriscos
P2 P3 S2 P6 S1 P5 P4 P1
3ª etapa – indexar fragmento do pai B
O novo indivíduo é inviável, pois apresenta uma informação do tipo poço no
primeiro gene do cromossomo. Como mencionado anteriormente, haverá deslocamento no
sentido da esquerda para a direita para que a primeira posição refira-se a sonda. Indivíduo
viável: <S2 P2 P3 P6 S1 P5 P4 P1>.
4.6.2.2 Ajuste nos parâmetros de cruzamento
Antes de fixar o número de descendentes, foram realizados testes para a
determinação da taxa de cruzamento. Para a realização destes testes foram escolhidas
48
aleatoriamente algumas instâncias e os resultados indicam, como pode ser observado nos
valor da solução
Graficos 1, 2, 3, 4 e 5, que os melhores resultados obtidos foram com uma taxa de 20%.
175600
10%
175300
20%
175000
30%
174700
valor da solução
Gráfico 1 - Relação entre a taxa de cruzamento e o valor da solução para a instância D4
168800
10%
168200
20%
167600
30%
167000
valor da solução
Gráfico 2 - Relação entre a taxa de cruzamento e o valor da solução para a instância D9
647650
647350
10%
647050
20%
646750
30%
646450
valor da solução
Gráfico 3 - Relação entre a taxa de cruzamento e o valor da solução para a instância C1
652950
10%
652800
20%
652650
30%
652500
valor da solução
Gráfico 4 - Relação entre a taxa de cruzamento e o valor da solução para a instância C4
1314950
10%
1313750
1312550
20%
1311350
30%
1310150
Gráfico 5 - Relação entre a taxa de cruzamento e o valor da solução para a instância B1
49
4.6.2.3 Mutação
A mutação é um operador genético que permite a produção de um novo
indivíduo através da manipulação direta do seu cromossomo, causando a diversidade na
população.
Ela é considerada como um mecanismo secundário nas operações dos AG,
consistindo na mudança aleatória de um ou mais genes de um cromossomo e,
conseqüentemente, produzindo albinos (Chan e Tansri, 1994). Albinos são indivíduos com
algumas propriedades de cromossomos completamente diferentes da maioria dos
indivíduos da população.
A mutação tem a função de criar uma política de prevenção que diminua as
probabilidades das soluções serem apanhadas em um ótimo local. A taxa de mutação é
normalmente fixada em um nível muito baixo, tal como nas populações naturais.
O operador de mutação adotado é a mutação baseada na ordem que consiste na
seleção aleatória de duas posições e a troca de seus conteúdos. O exemplo a seguir ilustra o
procedimento deste operador.
cromossomo original
cromossomo após a mutação
S1 P2 P3 S2 P5 P6 P4 P1
posição1
S1 P2 P6 S2 P5 P3 P4 P1
posição2
4.6.3 Definição de vizinhança de busca
A busca local implementada neste trabalho é a all-pairs. Ela consiste em fazer
uma varredura seqüencial avaliando a troca de posições de todos os pares de informações
de uma dada solução. Trocas que melhorem o valor da fitness são confirmadas. Trocas que
piorem são ignoradas. Se todas as possíveis trocas forem avaliadas e nenhuma melhorou a
solução, o processo para. Se houve melhora, o processo é reiniciado com a solução
atualizada.
O algoritmo de busca local all-pairs é descrito a seguir:
1º passo: obter uma solução inicial;
2º passo: fazer uma varredura seqüencial, avaliando todas as possíveis trocas
de pares de informações da solução inicial. Confirmar trocas que melhorem o valor da
solução e ignorar as que piorem;
50
3º passo: se no passo anterior houve alguma troca que melhorou o valor da
solução, realiza-o novamente com a solução atualizada. Em caso contrário pare, pois a
solução é um mínimo local.
Seja a sequência < a b c d e >. Inicialmente troca-se às posições (a,b), gerando
a solução < b a c d e f >. Se a troca for vantajosa, confirma-se a mudança e continua-se o
processo. Caso contrário a troca é desfeita. Seguindo a seqüência troca-se (a,c), (a,d), até o
par (a,e). O processo é reiniciado agora a partir da segunda posição: (b,c), (b,d) até (b,e). O
processo termina na troca das posições (d,e). Ao terminar uma passagem completa,
verifica-se alguma mudança foi vantajosa. Em caso positivo é realizada uma nova
passagem, pois a solução não é necessariamente um mínimo local. Se nenhuma troca foi
confirmada em uma passagem completa então a solução é um mínimo local e o processo
pára.
A troca all-pairs é de ordem O(n2), o que significa que o número de trocas
cresce de forma quadrática com o tamanho do cromossomo. Assim, devido ao tempo
necessário para se varrer toda a vizinhança, foi estabelecida à realização de apenas a troca
da segunda posição com todas as demais. Assim, na seqüência < a b c d e >, são feitas
todas as trocas vantajosas: (b,c), (b,d),(b,e). Os passos seguintes, que seriam a troca da
terceira posição com todas as demais e assim por diante, não são realizados. A troca parte
da segunda posição porque a primeira deve sempre se referir a uma sonda.
No caso da busca local na melhor solução, as trocas são feitas partindo-se da
terceira posição com todas as demais, da quarta com todas as demais e assim por diante até
a quinta posição.
51
5
TRANSGENÉTICA COMPUTACIONAL
A Transgenética Computacional (TC) é uma metaheurística que pertence à área
da Computação Evolucionária (CE) e os algoritmos desenvolvidos baseados nesta
metaheurística são denominados de algoritmos transgenéticos. O processo evolucionário da
TC está inspirado na evolução biológica, com uso dos paradigmas do fluxo extracelular e
intracelular, e na evolução cultural dos memes. A seção 5.1 contém uma breve descrição
da relação entre a evolução cultural e biológica e como elas estão contextualizadas nos
algoritmos transgenéticos. O paradigma do fluxo extracelular e intracelular é descrito da
seção 5.2. Na seção 5.3 será apresentado o processo evolucionário da abordagem TC com
subitens que descrevem os agentes e os algoritmos transgenéticos. Um pseudocódigo do
algoritmo transgenético ProtoG utilizado para solucionar o PPSP é apresentado na seção
5.4.
5.1
Evolução cultural e biológica
Um dos maiores bens que o ser humano pode adquirir durante a vida é a
cultura, um precioso legado e um recurso renovável dos mais importantes. Nela estão
contidas as crenças, a linguagem, costumes, cerimônias, tradições, a arte e a
intelectualidade, dentre outros. Do homem e da sua convivência observadora e
transformadora resulta a evolução cultural, é dele que nasce e se desenvolve esse
mecanismo evolutivo que é muito diferente da lenta evolução biológica.
Salzano (1993) afirma que, em geral, não há dúvida de que existe uma
harmonia entre a seleção natural e a seleção cultural. Isto, no entanto, nem sempre é
verdadeiro. Existem exemplos de características culturais que são claramente prejudiciais
do ponto de vista biológico, mas que persistem pela sua valorização cultural – a prática de
circuncisão feminina, ainda muito prevalente em sociedades islâmicas, é claramente
maléfica à saúde das mulheres e pode afetar a probabilidade do nascimento de crianças
normais, por problemas relacionados ao parto.
Em analogia com a unidade da herança biológica (o gene), Dawkins sugeriu
que se denomine a unidade cultural de meme. Exemplos de memes são estilos musicais,
idéias, frases de efeito, modas, meios de construir navios e fabricar potes. Assim como
genes propagam a si mesmo no pool genético indo de corpo em corpo por esperma ou
52
ovos, memes propagam a si mesmos no pool memético indo de cérebro em cérebro pelo
processo que chamamos "imitação" (Salzano, 1993).
Muitos biólogos e sociólogos aceitam que as formas mais complexas do
comportamento humano são herdadas por pura transmissão cultural, aceitando que a mente
e a cultura humana estão livres dos genes de modo que a evolução cultural independe da
biológica (Lacadena, 2001).
No entanto, Wilson (1999), considera que esta percepção está errada - "A
cultura é criada pela mente coletiva, e cada mente por sua vez é produto do cérebro
humano geneticamente estruturado. Genes e cultura estão, portanto, inseparavelmente
ligados, mas a ligação é flexível". Os comportamentos humanos também evoluíram com a
finalidade de garantir a sobrevivência. Estes comportamentos, acredita Wilson (1999), são
governados pelo que ele chama de regras epigenéticas, redes neurais com bases genéticas
que predispõem o cérebro a favor de determinados tipos de ação. No caso do tabu universal
contra o incesto, Wilson (1999) sugere que existe uma regra epigenética que torna as
pessoas instintivamente avessas a se casar com aqueles que conheceram intimamente na
infância.
O uso do paradigma da evolução cultural, assim como o da evolução natural,
está presente no contexto computacional. Os Algoritmos Meméticos (Moscato, 1989;
Mendes, 1999) se mostram abertos a inclusão de procedimentos evolucionários não
estritamente associados a reprodução sexual. A este tipo de procedimentos (Moscato,
1989) denomina “aprendizagem lamarckiana”. Normalmente nos Algoritmos Meméticos, a
aprendizagem lamarckiana é expressa por procedimentos de busca local sobre os
cromossomos, visando melhorar artificialmente a sua fitness. Assim, eles simulam a
co-evolução genética e cultural dos seres humanos, onde indivíduos geneticamente pouco
favorecidos ao nascerem, mas devido às condições em que vivem, por trocas de
informações com outras pessoas, etc, podem se tornar mais adaptados.
A TC também utiliza o paradigma da evolução cultural. Com o uso do
paradigma epigenético e dos memes para melhorar a adaptabilidade dos indivíduos da
população mas de um modo diferente dos Algoritmos Meméticos. Na TC os memes estão
associados a informações que podem ser obtidas fora do fluxo extracelular. Os memes da
TC são considerados como uma proposta de organização do cromossomo sendo
introduzidos no processo evolucionário através dos agentes transgenéticos (Gouvêa, 2001).
53
Na TC, o paradigma memético é utilizado para criar um planejamento de
informações através das regras epigenéticas e expressar estas regras nos cromossomos
através dos agentes do fluxo intracelular no decorrer do processo evolucionário.
As regras epigenéticas, no contexto da TC, especificam a criação planejada de
uma base de informação que pode até mesmo não estar codificada no formato genético. No
problema da Coloração em Grafos (Papadimitriou e Steiglitz, 1982) as cores designadas
aos vértices adjacentes precisam ser diferentes. Deste modo, as cores designadas para os
vértices da clique precisam ser todas distintas. Uma regra epigenética é: designar cores
distintas para os vértices de uma clique. Sendo assim, um meme pode estar relacionado a
uma clique de cores e representa o fato de que todos os vértices de cada uma das cliques
desse grafo devem ser coloridos com cores diferentes. Um meme é mais que simplesmente
uma lista ou seqüência de vértices – supostamente um conjunto de genes – e representa o fato de
que todos os vértices de cada uma das cliques desse grafo devem ser coloridos com cores
diferentes.
5.2
O paradigma intracelular e extracelular
O principal mecanismo que leva à mudança na freqüência genética, portanto, à
evolução, é a seleção natural. Se, numa população composta por duas ou mais formas, uma
delas apresentar uma característica hereditária que seja vantajosa para um determinado
ambiente, a seleção vai favorecer esta forma, que irá sobreviver e proliferar com mais
sucesso, deixando um número maior de prole em relação as demais, ao longo das gerações.
Assim, esta forma poderá superar as demais a ponto de alterar a constituição genética da
população como um todo.
Para a evolução por seleção natural atuar deve haver variação genética dentro
da população, variação esta que é decorrente principalmente de recombinações e
mutações.
A
reprodução
sexuada
é
responsável
pela
variação
decorrente
da
recombinação. A escolha dos parceiros para o acasalamento ocorre no paradigma
extracelular no nível de fenótipo, onde ambos irão contribuir com células reprodutivas que
irão gerar um novo ser vivo. As células reprodutivas contêm as informações genéticas dos
pais que irão determinar as características do novo ser vivo. Na reprodução sexuada há um
fluxo de informações entre células sendo denominado de fluxo extracelular.
54
A variação causada pela mutação ocorre devido a um erro na auto replicação
do DNA (ácido desoxirribonucléico), quando as duas cadeias da dupla hélice do DNA se
separam e cada uma delas serve como um molde para a construção de uma nova célula. A
freqüência de mutações é de cerca de um para várias centenas de milhões de células em
cada geração. Essa freqüência não tem muita influência na evolução da grande diversidade
das espécies. Ao contrário das bactérias, a mutação é um dos caminhos da evolução.
Devido a enorme taxa de reprodução, uma única bactéria mutante bem sucedida pode
espalhar-se rapidamente pelo seu meio ambiente (Capra, 2001). Outro mecanismo de
evolução utilizado pelas bactérias é o intercâmbio de genes que não está ligado à
reprodução sexual, logo as bactérias podem utilizar o fluxo extracelular deforma planejada
para trocarem informações entre si.
A variação causada pela mutação ocorre no interior da célula, no fluxo
intracelular. O fluxo intracelular engloba as informações que conseguem atravessar a
barreira celular e aquelas que são originadas em seu interior.
O paradigma intracelular, assim como o extracelular, é responsável pela
evolução biológica. Além da mutação, outras alterações podem ocorrer no fluxo
intracelular. A incorporação nas eucarióticas (células que apresentam núcleo) das
organelas cloroplastos e mitocôndrias aconteceram no fluxo intracelular (Salzano, 1993).
Steele et al.2, citado por Korthof (2001), acreditam que nos mamíferos existem
mecanismos que permitem incorporar no DNA a capacidade imunológica adquirida em
vida e que essa capacidade imunológica pode assim ser transmitida às gerações futuras.
O paradigma da evolução biológica vem sendo utilizado no contexto
computacional. Os AG’s ao utilizarem a reprodução sexual estão fazendo uso do fluxo
extracelular, mas eles também utilizam o fluxo intracelular quando realizam mutações. Os
AG’s são desenvolvidos inspirados na seleção natural. No entanto, no contexto biológico o
número de mutações ocorre com pouca freqüência nos organismos que utilizam
reprodução sexual. Ao permitir o uso irrestrito do acúmulo de mutações, o processo
evolucionário computacional acaba artificialmente enriquecido perdendo, todavia, o
contato com a realidade da sua metáfora biológica inspiradora.
A TC, além do paradigma do fluxo extracelular, utiliza o fluxo intracelular
quando insere informações nos cromossomos da população durante o processo
2
STEELE, E. J., LINDLEY, R. A., BLANDEN, R. V., 1998, Lamarck's Signature. How Retrogenes Are
Changing Darwin's, Natural Selection Paradigm, Perseus Books.
55
evolucionário através de agentes inspirados em mecanismos desenvolvidos pela
Engenharia Genética para manipular o DNA.
5.3
O processo evolucionário da Transgenética Computacional
A TC é uma metaheurística pertencente à área da Computação Evolucionária
que utiliza a informação para guiar uma população de cromossomos durante o processo
evolucionário. Assim como nos AG’s, os cromossomos estão associados a soluções de um
problema onde, partindo de um conjunto de soluções iniciais, são obtidas novas soluções
com o uso da informação para guiar a busca por melhores soluções.
As informações utilizadas no processo evolucionário são denominadas de
memes. Os memes permitem intensificar e diversificar os cromossomos da população. O
sucesso pela busca de uma solução de boa qualidade vai depender das informações
carregadas pelos agentes, logo a busca por memes de boa qualidade é uma constante do
processo de evolução cultural. Os memes irão modificar diretamente os genes que
compõem os cromossomos e são uma proposta para construir blocos de genes (blocos de
montagem) (Gouvêa e Goldbarg, 2001).
Para inserir os memes nos cromossomos durante o processo evolucionário, a
TC usa mecanismos inspirados na Engenharia Genética. A metáfora que integra técnicas
de EG no processo evolucionário é denominada de transgenética (Gouvêa, 2001).
A EG é uma ciência que modifica os seres vivos pela manipulação direta do
DNA, através da inserção ou deleção de fragmentos específicos. Sua aplicação pode ser na
produção de vacinas, proteínas por microorganismos, alimentos, transplantes, terapia
gênica, transgênicos. No contexto da TC, a inspiração na metáfora da EG permite que,
através do uso de agentes transgenéticos, informações sejam inseridas no processo
evolucionário. A transcrição da informação nos cromossomos promove, no processo
evolucionário, a intensificação e a diversificação da população. Os agentes podem também
fortalecer cromossomos mais fracos simulando desta forma o mecanismo de terapia gênica
da EG. A terapia gênica é a manipulação de genes do indivíduo para corrigir defeitos
genéticos, ela pode ser do tipo: correção - quando ocorre a inserção de um gene funcional
no local de um não funcional; complementação - quando é feita a introdução de uma cópia
normal sem modificação do original; adição - com o acréscimo de um gene ausente no
genoma.
56
A inspiração na metáfora da EG resulta na introdução de informações exógenas
no processo evolucionário que podem intensificar ou diversificar a população, e fortalecer
os cromossomos mais fracos (Gouvêa, 2001).
O processo evolucionário da TC pode ser observado na Figura 7, evidenciando
o funcionamento básico dos algoritmos transgenéticos. A partir das regras epigenéticas é
gerado um Banco de Memes que por sua vez contribuem para a formação dos agentes
inspirados na EG. Estes agentes atuam no cromossomo que determinam o fenótipo. A
partir dos cromossomos manipulados, novas informações são adquiridas e irão alimentar o
Banco de Memes.
Co-evolução
gene-cultura
produz
Regras epigenéticas
e outras pressões
evolucionárias
influenciam
geram
Banco de
Memes
dá
suporte
Fenótipo
Agentes
da EG
atuam
sobre
Cromossomos
constroem
Figura 7 - Fluxograma do Ciclo Evolucionário da Transgenética Computacional
Fonte - (Gouvêa, 2001. p. 52)
Fica evidente que a evolução da população influencia na evolução dos memes,
caracterizando desta forma a co-evolução gene X cultura presente na TC. Portanto, além
do uso de informações exógenas, são usadas informações endógenas inerentes ao processo
evolucionário. O uso de informações endógenas demonstra o caráter co-evolucionário da
metaheurística TC, pois a evolução da população implica na evolução dos memes que dão
suporte para a geração dos agentes, que por sua vez atuam no processo evolucionário.
Logo, população e memes co-evoluem.
As informações que são usadas pelos algoritmos transgenéticos são obtidas de
duas maneiras: fora e durante o processo evolucionário.
As informações obtidas fora do processo evolucionário são denominadas
informações exógenas e podem ser originárias de heurísticas, conhecimento prévio do
problema, etc,. O algoritmo transgenético para o Problema do Caixeiro Viajante pode obter
informações exógenas de estruturas como a árvore geradora mínima ou de procedimentos
como a heurística de Christofides (Papadimitriou e Steiglitz, 1982), entre outras.
No decorrer do processo evolucionário, informações de boa qualidade que
surgirem também podem ser utilizadas.
57
Há um fluxo contínuo de informações no processo evolucionário. A Figura 8
representa este fluxo. Primeiramente são obtidas informações exógenas que irão formar os
memes. De posse dos memes, as regras meméticas determinam como serão construídos os
agentes de manipulação que irão transportar estes memes. Os agentes formados irão atuar
sobre os cromossomos e o modo de atuação vai depender das regras transgenéticas
especificadas. A atuação dos agentes sobre os cromossomos vai resultar na manipulação
destes e a partir desta atuação informações endógenas poderão ser obtidas.
Engenharia
Genética
Memética
Contexto do Fenótipo
Informações
Endógenas
Memes
1. Busca Local
2. Heurística
Informações
Exógenas
Contexto do Genótipo
Cromossomo normal
Agentes de
Manipulação
Informações
Cromossomo manipulado
Codificadas
Regras Meméticas para
a formação de agentes
Regras Transgenéticas de manipulação
Figura 8 – O fluxo de informação na TC
Fonte – Gouvêa (2001) p. 53
O processo evolucionário dos algoritmos transgenéticos utiliza a informação
transportada pelos agentes logo, se faz necessário manter um fluxo contínuo de
informações ao longo do desenvolvimento do algoritmo de solução. No entanto, a
população no decorrer do processo evolucionário pode ficar imune à atuação dos agentes.
A imunidade da população ocorre quando o agente não consegue transcrever suas
informações nos cromossomos. O fracasso da atuação dos agentes se deve a dois motivos:
(a) os memes transportados já foram incorporados `a população; (b) a atuação dos agentes
não melhora o valor da fitness nos cromossomos devido à baixa qualidade dos memes.
Para garantir a qualidade das informações transportadas e o sucesso na
transcrição dessas informações, os agentes deverão ser redesenhados durante o processo
evolucionário. Este constante redesenho simula o que ocorre, por exemplo, no processo
imunológico da biologia, onde os agentes de defesa do organismo naturalmente buscam
um aumento no seu poder de resposta.
A característica fundamental do sistema imunológico é a sua capacidade de
distinguir, englobar, na tentativa de eliminar partes de um corpo estranho, como bactérias,
58
vírus, etc. O ferimento com uma pequena farpa de madeira faz o sistema imunológico
ativar as células brancas fagocitárias conhecidas como macrófagos. Estas células buscam
englobar e destruir possíveis invasores, produzindo proteínas que ativam outras partes do
sistema imunológico, alertando outros fagócitos. Outro componente do sistema
imunológico, presente apenas nos vertebrados, é a imunidade adquirida que é formada por
células brancas especializadas, chamadas linfócitos B e T , que se tornam ativos e se
multiplicam ao encontrarem moléculas específicas de organismos estranhos chamadas
antígenos. A principal característica da imunidade adquirida que é a memória imunológica,
surge de mecanismos baseados em DNA que permitem aos linfócitos reconhecer uma
grande diversidade de antígenos. Essencialmente, cada encontro com um organismo
invasor estampa uma "fotocópia" genética dentro das células B e T. Numa segunda vez que
estas células encontrarem com o mesmo invasor, usarão a "fotocópia" genética, o que lhes
proporcionará um reconhecimento mais rápido e mais eficiente do organismo invasor. Este
fenômeno é o que torna possível a imunização.
O uso do paradigma imunológico pela TC corresponde a obter informações do
processo evolucionário e utilizar essas informações para redesenhar agentes de
manipulação mais eficientes ao longo das iterações do algoritmo de busca (Gouvêa, 2001).
Modificações no método de atuação dos agentes, alterações no tamanho da cadeia de
memes dos agentes, substituição dos agentes são algumas possibilidades para se efetuar o
redesenho dos agentes e enfrentar o desafio de continuar a transcrição em uma população
que se torne cada vez mais resistente ao ataque dos agentes.
5.4
Agentes Transgenéticos
Os agentes transgenéticos são os mecanismos para a manipulação dos
cromossomos. Um agente é composto de um ou mais memes acompanhado por um método
de atuação. A formação do agente vai depender das regras meméticas que definem a sua
formação. Os agentes transportam informações (memes) e manipulam o cromossomo de
acordo com um método de atuação que é definido pelas regras transgenéticas. Esse método
de atuação vai das circunstâncias relativas ao processo evolucionário e ao tipo de agente
empregado (Gouvêa, 2001).
No contexto biológico, os agentes utilizados pela EG servem para manipular o
código do DNA. O uso de agentes na EG serve para quebrar a cadeia de DNA em
determinados lugares, inserir segmentos de outros organismos e costurar novamente a
59
cadeia. No contexto evolucionário, os agentes são utilizados para infiltrar informações nos
cromossomos durante o processo da busca por soluções de boa qualidade, intensificando e
diversificando a população.
O agente transgenético denominado vírus tem a capacidade de manipular o
cromossomo, alterando sua fitness devido a manipulação. Os memes carregados por este
agente, quando transcritos, permanecem invioláveis no cromossomo por um período de
tempo chamado tempo de vida do vírus.
O agente vírus é composto por um string de informações, a contaminação e um
método de descontaminação. A contaminação consiste de três estágios:
1.
ataque: um cromossomo para ser manipulado pelo agente vírus deve
ser sensível ao ataque. A sensibilidade do cromossomo pode ser determinada de duas
maneiras: (a) a manipulação causada pelo vírus melhora a fitness do cromossomo; (b) em
caso contrário, é feita analise se o decréscimo da fitness atende a um esquema imune prédefinido. Um esquema imune pré-definido pode ser, por exemplo, um decréscimo de 2%
no valor da fitness do cromossomo;
2.
transcrição: após ser verificada a sensibilidade do cromossomo, as
informações transportadas pelo vírus serão transferidas para o cromossomo de acordo com
o operador de transcrição;
3.
duração: após a transcrição das informações, elas permanecem
invioláveis num período específico de gerações. Este período de inviolabilidade é
determinado tempo de vida do vírus. Quando termina o tempo de vida, o cromossomo fica
livre das restrições impostas pelo ataque viral.
Gouvêa (2001) apresenta vários tipos de vírus: vírus esquema, vírus de corte,
vírus 51, vírus de retorno, vírus natural, vírus molde.
Outro agente transgenético é a Partícula Genética Móvel (PGM), o principal
agente usado pelo algoritmo ProtoG. A PGM transporta memes que são fragmentos de
cromossomo. Estes fragmentos serão engolidos pelo cromossomo atacado caso seja
verificada a sensibilidade ao ataque. Um cromossomo é sensível ao ataque da PGM
somente se melhorar o valor de sua fitness. Os memes transcritos para o cromossomo não
permanecem invioláveis, portanto a duração da inviolabilidade é zero.
60
Uma PGM é um agente composto por uma cadeia de informação (meme) e um
método de contaminação. A (PGM) é um caso especial de vírus esquema sem apresentar
descontaminação pois suas informações não permanecem invioláveis.
O uso do agente PGM acarreta em dois estágios:
1.
ataque: neste estágio se verifica a sensibilidade do cromossomo as
informações transportadas pelo agente;
2.
transcrição: no segundo estágio, caso resulte em uma resposta
verdadeira o estágio anterior, é feita a transcrição das informações resultando em um
cromossomo manipulado.
5.5
Algoritmos Transgenéticos
Os algoritmos transgenéticos são classificados em dois grupos: os que utilizam
o fluxo intracelular e o extracelular (operadores de cruzamento e mutação típicos dos
AG’s) e aqueles que utilizam apenas o fluxo intracelular. Além do fluxo extracelular e
intracelular, os algoritmos transgenéticos desfrutam dos paradigmas da EG, da memética e
imunológico. No Quadro 2 estão especificadas as categorias de algoritmos transgenéticos,
onde as áreas em destaque indicam o uso do paradigma pelo algoritmo.
ALGORITMOS TRANSGENÉTICOS
Extra
Extra Intracelular
Extra
Intracelular
Imunológicos com
Intracelulares
Imunológicos
Times de Agentes
(ATEIs)
(ATEI-Is)
(ATEI-Its)
PARADIGMAS
5.6
Proto-Gene
(ProtoG)
Engenharia
Genética
Evolução
Darwiniana
Memética
Processo
Imunológico
Quadro 2- Algoritmos Transgenéticos de acordo com os paradigmas utilizados
Pseudocódigo do algoritmo ProtoG_PSPT
O algoritmo ProtoG não utiliza operadores de cruzamento ou mutação típicos
dos AG. Abandonando, desta forma,o uso do paradigma do fluxo extracelular uma das vias
da evolução biológica dos seres de reprodução sexuada. O processo evolucionário do
ProtoG está inspirado no paradigma procariótico. Nas espécies com células procarióticas
61
(bactérias) a evolução ocorre através de troca de genes entre si sem utilizar a via de
reprodução sexuada. O comércio global de genes das bactérias, conhecido como
recombinação de DNA (Capra, 2001), mostra o porquê da rápida velocidade em que se
espalha a resistência às drogas pela comunidade das bactérias.
O ProtoG está inspirado no paradigma procariótico quando abandona a via de
reprodução sexuada e utiliza troca informações no processo evolucionário. São
basicamente duas as fases do algoritmo. A primeira consiste em adquirir informações
(memes) planejadas que irão compor o BM. A partir daí, na segunda fase, são construídos
os agentes transgenéticos que irão atacar os cromossomos da população. O BM poderá
também ser realimentado no decorrer do processo evolucionário com informações de boa
qualidade, como um agente ou com cromossomo campeão ainda não considerado. A
realimentação do BM caracteriza o uso do paradigma imunológico pelo algoritmo. O
paradigma epignético também está presente no algoritmo quando dá formação do BM
através do uso das regras epigenéticas.
A exemplo do AGh, é apresentado um pseudocódigo do algoritmo ProtoG
implementado para solucionar o PPSP.
Procedure ProtoG
Início
GerarBanco_de_memes
Inicia_pop população_principal usando Carrega_pop_inicial
Avalia_fitnes (população_principal)
Repetir /*laço de evolução da população*/
Escolhe meme
Carregar agente de manipulação
Se agente vírus então
Para i:=1 até (0.025*tamanho_da_população) faça
Início
indivíduo_aux := manipula (indivíduo[i])
avalia_fitness (indivíduo_aux)
Se cromossomo sensível então indivíduo[i]:=indivíduo_aux
Fim
Se agente PGM então
Para i:=1 até #tamanho da população faça
Início
indivíduo_aux := manipula (indivíduo[i])
avalia_fitness (indivíduo_aux)
Se adaptabilidade indivíduo_aux > adaptabilidade
indivíduo[i] então
indivíduo[i]:=indivíduo_aux
Fim
Atualizar melhor_solução
Realimentar Banco de Memes
Até (condição de parada)
Fim
62
5.6.1 Construção do BM e da população inicial
Gerar Banco_de_memes
Inicializa_pop população_principal usando Carrega_pop_inicial
Avalia_fitnes(população_principal)
O primeiro passo é a construção do Banco de Memes (BM) contendo soluções
do problema. Para gerar o BM, foi utilizado um método ‘guloso’ e construtivo baseado no
EDD (do inglês: Earliest Due Date).
Este método, na sua forma original, é utilizado para problemas de
sequenciamento que envolvem data de entrega das tarefas. O método EDD considera
apenas as datas de entrega das tarefas, ordenando as tarefas segundo uma seqüência
não-decrescente das mesmas (Mendes, 1999). No caso do atendimento dos poços, não há
data de entrega e sim, data de liberação para a sondagem. Os poços também têm diferentes
tempos de intervenção e volumes de produção que devem ser considerados no
sequenciamento de atendimento.
Desta forma, a regra foi modificada de modo que os poços serão ordenados
numa seqüência não-decrescente segundo a data de liberação. Em seguida, serão
designados para as sondas considerando os atributos (duração da intervenção, atratividade,
volume de produção) que lhes conferem. A regra modificada foi denominada de ERR. A
seguir uma descrição passo a passo da regra:
1º passo (inicialização): criar um vetor A que contenha os poços numa
seqüência não decrescente segundo a data de liberação;
2º passo (interações): seguindo a seqüência do vetor A, verificar dentre todas
as sondas e escolher aquela que o poço retorna o maior volume de petróleo produzido,
considerando os poços que já foram alocados. Este passo se repete até que todos os poços
sejam alocados;
3º passo (busca local): após a determinação das seqüências de poços que serão
atendidos pelas sondas, é realizado uma busca local. A busca local consiste na all-pairs, a
mesma utilizada pelo AGh.
O primeiro passo resume em ordenar os poços, de modo a determinar a ordem
em que eles serão escolhidos para o atendimento das sondas. O segundo passo é a escolha
da sonda que fará a intervenção. Num primeiro instante as sondas não estão relacionadas
63
com poços. O primeiro poço a ser atendido vai considerar apenas os custo das sondas. Os
poços seguintes vão considerar os custos das sondas e a seqüência dos poços que já foram
atribuídos as sondas para o cálculo parcial do maior retorno de petróleo produzido. Um
poço sempre será inserido após o último poço da seqüência da sonda, de modo que a
escolha da sonda será a que produzir o maior retorno parcial da produção. O último passo
consiste em realizar uma busca local na solução gerada pelo 2º passo.
Além da solução ERR, o BM contém uma lista de poços ordenada numa
seqüência não-decrescente segundo a de liberação da sondagem. Da lista serão extraídas
partículas formadas por poços que sejam próximos considerando a data de liberação e o
tempo da intervenção. Seja a partícula formada pela seguinte seqüência de poços {3, 4,5}
então, a data de liberação para a sondagem do poço 3 somada ao tempo de intervenção tem
valor próximo à data de liberação do poço 4; o mesmo acontece entre o poço 4 e 5.
Durante o processo evolucionário, o BM será realimentado com os dois melhores
cromossomos da população.
Depois de formado o BM, uma população é iniciada e a fitness de cada
indivíduo é avaliada. A população inicial é obtida de modo totalmente aleatório, sendo a
mesma utilizada pelo AGh, pois ela está armazenada na instância junto com as
informações relativas aos poços.
5.6.2
Processo evolucionário
O processo evolucionário consiste basicamente em carregar um agente
transgenético com memes e atacar os cromossomos da população até a condição de parada
ser atendida. O laço de repetição para quando forem realizadas 100000 interações ou se a
melhor solução não melhorar passado um intervalo de 5000 interações.
No início de cada volta do laço, ocorre a competição entre os memes para
constituir os agentes. Como o BM é composto por informações que provem de quatro
procedimentos diferentes (solução ERR, poços ordenados, 1ª e 2ª melhores soluções) a
cada nova interação, quando for utilizado um meme de intensificação, uma das quatro
soluções será escolhida para compor um bloco de montagem. A escolha não será aleatória,
seguirá uma ordem. O tamanho do bloco de montagem não foi constante. A cada nova
interação foi sorteado aleatoriamente o tamanho do bloco, sendo que foi especificado um
valor máximo de 10% do comprimento do cromossomo.
64
Para promover a diversificação, foram gerados blocos de montagem de modo
aleatório utilizados pelos agentes vírus para atacar os cromossomos. Para o bloco de
montagem originário da diversificação, o tamanho máximo foi de 10% do comprimento do
cromossomo. A relação entre os memes de intensificação e diversificação foi de 1:1,
respectivamente.
Os agentes de manipulação – agente transgenético – usados foram a Partícula
Genética Móvel (PGM) e o vírus com tempo de vida igual a zero. Foram desenvolvidos
dois ataques: um para o agente do tipo vírus e o outro para a PGM.
Para o agente do tipo vírus, o ataque é o seguinte:
Se agente vírus então
Para i:=1 até (0.025*tamanho_da_população) faça
Início
j:= sorteia (indivíduo da população)
indivíduo_aux := manipula (indivíduo[j])
avalia_fitnes(indivíduo_aux)
Se cromossomo sensível então indivíduo[j]:=indivíduo_aux
Fim
A princípio todos os indivíduos da população eram atacados pelo vírus, porém
os resultados obtidos não foram satisfatórios. Passou-se estão a atacar 2,5% dos indivíduos
da população. Os indivíduos são sorteados num processo aleatório e são atacados pelo
vírus. Aqueles que forem sensíveis ao ataque são manipulados e recebem as informações
contidas no agente transgenético. O cromossomo é sensível nos seguintes casos: (a) o valor
da fitness melhorar; (b) se o valor da fitness piorar, deverá atender ao critério da fórmula de
propagação de memes. Neste trabalho, a fórmula que segue representa uma regra
estocástica de sensibilidade dos cromossomos (Gouvêa, 2001):
1
P=
Val_ant − Val_dep ,

Val_ant


β∗
e
onde Val_ant e Val_dep são os valores da fitness do indivíduo antes e depois da
contaminação, respectivamente; β é um parâmetro de ajuste. O valor de P foi comparado
com um valor sorteado (Vsort) no intervalo (0, 1). Se P > Vsort então o cromossomo é
sensível ao ataque e será manipulado, em caso contrário o cromossomo permanece no seu
estado original.
Para determinar o valor do parâmetro β foram escolhidas 6 instâncias e, para
cada uma delas, foram realizados quatro testes com β = 5 e quatro testes com β = 9.
65
Conforme a Tabela 1, observa-se que os resultados obtidos para β = 9 foram melhores e
este foi o valor assumido não realização dos testes para as 34 instâncias.
TABELA 1
Resultados obtidos para diferentes valores de Beta
Beta
5
9
Instância
melhor
melhor
Média
média
solução
solução
D4
175652
175530
175684
175653,5
D9
169032
168980
169086
169050
C1
648251
648247,8
648255
648248
C4
654756
654732,5
654864
654779
B1
1316674
1315344
1317014
1316660
B3
1215018
1214732
1215822
1214822
A forma de transcrição das informações do vírus pode ser observada no
exemplo da Figura 9. Uma posição do cromossomo é sorteada aleatoriamente. As posições
do cromossomo que contém informações em comum com a partícula são marcadas como
posições livres. Em seguida, as posições livres se deslocam de modo a se agruparem no
lugar onde serão transcritas as informações da partícula.
cromossomo
S1
P3
P2
P1
P2
P4
P5
vírus
S2
P4
P3
Marcar posições
S1
P1
#
P5
S2
#
#
Posições livres = #
Deslocar posições
S1
#
#
#
P1
P5
S2
Transcrição
S1
P3
P2
P4
P1
P5
S2
Figura 9 - Forma de transcrição do vírus
Para o agente PGM, o ataque é o seguinte:
Se agente PGM então
Para i:=1 até #tamanho da população faça
Início
indivíduo_aux := manipula (indivíduo[i])
avalia_fitness (indivíduo_aux)
Se adaptabilidade indivíduo_aux > adaptabilidade indivíduo[i] então
indivíduo[i]:=indivíduo_aux
Fim
66
Para PGM todos os cromossomos da população são atacados e o cromossomo é
contaminado somente se melhorar o valor de fitness. A forma de ataque da PGM com
memes de intensificação pode ser observado na Figura 10.
P3
cromossomo
S1
P1
P2
P5
S2
P4
P2
P4
PGM
P3
Marcar posições
S1
P1
#
P5
S2
#
P3
Posições livres = #
Deslocar posições
S1
P1
P5
S2
P3
#
#
Transcrição
S1
P1
P5
S2
P3
P2
P4
Figura 10 – Forma de transcrição da PGM
Á adoção de duas formas de transcrição foi para manter o desempenho
computacional. Visto que, quando utilizada a forma de ataque descrito na Figura 9 para
PGM, muitos cromossomos da população não podiam ser contaminados pois se tornavam
inviáveis, caindo o desempenho computacional. Os indivíduos se tornavam inviáveis
porque ultrapassavam o horizonte de tempo para a programação das sondas.
No final de cada volta do laço de repetição, ocorre a atualização da melhor
solução. Foram implementadas duas versões para a atualização da melhor solução. Na
primeira versão, caso tenha um indivíduo da população com um valor de fitness melhor do
que a melhor solução, então a melhor solução é atualizada. Na segunda versão, foi
realizado uma busca local no melhor indivíduo da população com valor de fitness superior
a fitness da melhor solução. Depois de realizada a busca local, a melhor solução é
atualizada.
O BM é realimentado ao final de cada volta do laço, com os dois melhores e
diferentes indivíduos da população ainda não considerados. Deste modo, fica estabelecido
o uso de informações endógenas durante o processo evolucionário.
67
6
RESULTADOS COMPUTACIONAIS
Neste capítulo são apresentados os resultados computacionais obtidos na
realização dos testes realizados para um grupo de 34 instâncias. É feita a avaliação do
desempenho para cada versão do algoritmo ProtoG (uma utilizando busca local e a outra
não) comparando-a com o AGh. Os resultados obtidos pelo método guloso e construtivo
ERR utilizado para compor o BM das duas o ProtoG também são apresentados.
6.1
Instâncias
Para a realização dos testes computacionais foram criadas aleatoriamente 34
instâncias. As 34 instâncias estão divididas em três grupos. No Quadro 3 estão
especificadas os parâmetros das 34 instâncias, onde estão definidos o número de poços, o
número de sondas alugadas e disponíveis, o horizonte de tempo que define o
intervalo – ∆tempo – em que são geradas as datas de liberação dos poços para a sondagem;
o intervalo de duração que define o intervalo – ∆intervalo – em que são geradas as
durações da intervenção de cada poço.
G
R
U
P
O
Nº
p
o
ç
o
s
I
N
S
T
Â
N
C
I
A
B1
B
B 400 2
B3
B4
C1
C
C 200 2
C3
C4
D1
D
D 100 2
D3
D4
Sondas
Disponíveis
Sondas
Alugadas
I
N
S
T
Â
N
C
I
A
10
10
10
10
8
8
8
8
8
8
8
8
2
4
6
8
2
4
6
8
2
4
6
8
B5
B6
B7
B8
C5
C6
C7
C8
D5
D6
D7
D8
Horizonte de tempo
360
Intervalo de duração
3a5
Sondas
alugadas
I
N
S
T
Â
N
C
I
A
Sondas
disponíveis
Sondas
alugadas
2
4
6
8
2
4
6
8
2
4
6
8
B9
B10
B11
B12
C9
C10
C11
C12
D10
D11
D12
D13
11
11
11
11
7
7
7
7
7
7
7
7
1
3
5
7
1
3
5
7
1
3
5
7
Horizonte de tempo
240
Intervalo de duração
3a7
Sondas
disponíveis
12
12
12
12
10
10
10
10
10
10
10
10
Horizonte de tempo
270
Intervalo de duração
3 a 10
Quadro 3 – Especificação das instâncias através de seus parâmetros
68
Para cada instância foram sorteados os atributos dos poços da respectiva
instância. São quatro os atributos: o volume de petróleo produzido por unidade de tempo,
uma data de liberação pertencente no intervalo ∆tempo, a atratividade do poço pertencente
ao intervalo (0.1, 0.9) e o tempo de duração da sondagem compreendido no intervalo
∆intervalo. Quando se trata de proporções, não foram definidas unidades específicas de
medidas.
Além dos atributos referentes aos poços, o tempo de planejamento, o número
de sondas alugadas e disponíveis, a instância contém a população inicial utilizada pelos
algoritmos ProtoG e AGh.
6.2
Desempenho dos algoritmos
Foram implementadas duas versões para o algoritmo ProtoG: uma sem busca
local e a outra com busca local. A busca local usada foi a all-pairs a mesma do AGh.
Para a realização dos testes computacionais, os algoritmos foram rodados
quatro vezes para cada instância. Desta forma, para cada instância foram obtidos 12
valores de soluções provenientes do algoritmo ProtoG com e sem busca local e do AGh.
Entre as 12 soluções obtidas para cada instância, foi extraída a melhor solução que está
descrita na coluna valor da solução da Tabela 2. As outras colunas da Tabela 2 relativas
aos algoritmos mostram a diferença de percentual da melhor solução obtida em relação a
melhor solução dentre as 12 soluções geradas para cada instância.
TABELA 2
Comparação de resultados
(Continua)
instância
D1
D2
D3
D4
D5
D6
D7
D8
D9
D10
D11
D12
valor da
solução
253161
251636
202315
175684
165521
159303
136741
133955
169086
179432
184646
181846
ProtoG sem
busca local
0
0,00119
0
0,0295
0,0537
0
0
0
0,0248
0
0,0005
0,0032
ProtoG com
busca local
0
0
0
0
0,0061
0
0
0
0
0
0
0
69
AGh
método ERR
0
0
0
0,09107
0
0
0
0
0,06564
0
0
0,001649
0,02844
0
0,01087
0,39275
0,05679
0,00062
0,03071
0
0,68012
0
0,09260
0,0032
TABELA 2
Comparação de resultados
(Conclusão)
instância
C1
C2
C3
C4
C5
C6
C7
C8
C9
C10
C11
C12
B1
B2
B3
B4
B5
B6
B7
B8
B11
B12
valor da
solução
648255
559495
592329
654864
394887
436790
416498
397294
451869
487653
477072
380867
1317014
1255661
1215822
1126218
962880
799406
808085
883077
889170
857382
ProtoG sem
busca local
0,00740
0,00327
0,07411
0,06138
0,04102
0,25092
0,09507
0,06695
0,30628
0,04839
0,34648
0,26203
0,47448
0,83589
0,54898
0,37594
0,04704
0,37040
0,59770
0,62304
1,50882
0,29683
ProtoG com
busca local
0
0
0
0
0
0
0
0
0,3864
0
0
0
0
0
0
0
1,6709
1,67225
0
0,05278
2,27044
2,26609
AGh
método ERR
0,078518
0,001966
0,235342
0,295939
0,205881
0,32693
0,24561
0,46262
0
0,10212
0,01194
0,18930
0,08352
0,27245
0,10782
0,27969
0
0
0,16088
0
0
0
0,01727
0,06988
0,11986
0,13254
1,27884
1,71959
1,07659
0,32872
0,65638
0,10191
2,22293
1,24111
0,699
2,20537
2,07407
1,64195
0,1592
0,37728
0,84075
0,75180
0,3408
0,47388
Os valores de afastamento médio da melhor solução encontrada para os
algoritmos ProtoG com busca local, ProtoG sem busca local, AGh e o método guloso e
construtivo ERR são, respectivamente: 0,28, 0,21 0,094 e 0,58. Estes valores estão
representados no Gráfico 6.
0,6
0,5
0,4
0,3
0,2
0,1
0
ProtoG
AGh
com busca
local
ERR
ProtoG
sem busca
local
Gráfico 6 – Afastamentos médios das melhores soluções
70
Observando a Tabela 2, verifica-se que os percentuais de distância para as
instâncias B5, B6, B11 e B12 arrastam para cima o valor do afastamento médio das
melhores soluções do algoritmo ProtoG com busca local. Desconsiderando o percentual de
distância das quatro instâncias, os valores de afastamento médio da melhor solução
encontrada para os algoritmos ProtoG com busca local, ProtoG sem busca local, AGh e o
método guloso e construtivo ERR são, respectivamente: 0,014, 0,17, 0,1 e 0,61. Eles estão
representados no Gráfico 7.
0,7
0,6
0,5
0,4
0,3
0,2
0,1
0
AGh
ProtoG
com busca
local
ERR
ProtoG
sem busca
local
Gráfico 7 – Afastamentos médios das melhores soluções
O afastamento médio do algoritmo ProtoG com busca local, considerando
todas as instâncias, é de 0,28. Com este valor, ele fica com o terceiro melhor afastamento
médio, como mostra o Gráfico 6. Excluindo as instâncias B5, B6, B11 e B12, o mesmo
algoritmo fica com o melhor afastamento médio, como mostra o Gráfico 7.
No Gráfico 8 são mostrados os desempenhos dos algoritmos em relação à
obtenção de soluções com valor igual a melhor solução, isto é, com o percentual de
distância igual a 0%. Observando o Gráfico 8, verifica-se que o algoritmo ProtoG com
busca local encontrou a melhor solução um número maior de vezes que o AGh, apesar de
ter ficado com o valor de afastamento médio superior ao AGh. O mesmo acontece com o
algoritmo Protog com busca local em relação ao algoritmo ProtoG sem busca local.
35
30
25
20
15
10
5
0
AGh
ProtoG
com busca
local
ERR
ProtoG
sem busca
local
Gráfico 8 – Percentual de soluções com afastamento 0%
71
Nos Gráficos 9, 10 e 11 estão representados as comparações de desempenho
relativo, segundo o critério da qualidade de solução, entre o algoritmo ProtoG com busca
local e cada um dos demais algoritmos. A barra da esquerda representa o número de
instâncias em que os algoritmos obtiveram iguais resultados. A barra central e a barra da
direita representam o número de instâncias em que o algoritmo comparado e o ProtoG
com busca local obtiveram melhor performance, respectivamente.
20
15
10
5
0
Empate
ProtoG com
busca local
AGh
Gráfico 9 – Comparação de desempenho ProtoG com busca local x AGh
30
25
20
15
10
5
0
Empate
ProtoG com
busca local
ERR
Gráfico 10 – Comparação de desempenho ProtoG com busca local x ERR
20
15
10
5
0
Empate
ProtoG com
busca local
ProtoG sem
busca local
Gráfico 11 – Comparação de desempenho ProtoG com busca local x ProtoG sem busca local
72
Nos Gráficos 12 e 13 estão representados as comparações de desempenho
relativo, segundo o critério da qualidade de solução, entre o algoritmo ProtoG sem busca
local e cada um dos demais algoritmos. A barra da esquerda representa o número de
instâncias em que os algoritmos obtiveram iguais resultados. A barra central e a barra da
direita representam o número de instâncias em que o algoritmo comparado e o ProtoG sem
busca local obtiveram melhor performance, respectivamente.
20
15
10
5
0
Empate
ProtoG sem
busca local
AGh
Gráfico 12 – Comparação de desempenho ProtoG sem busca local x AGh
20
15
10
5
0
Empate
ProtoG sem
busca local
ERR
Gráfico 13 – Comparação de desempenho ProtoG sem busca local x ERR
6.3
Comparação de tempo de processamento
As instâncias foram divididas em três grupos para serem feitas as análises dos
tempos de processamento gastos pelos algoritmos ProtoG com busca local e o AGh.
O primeiro grupo foi formado pelas instâncias em que os dois algoritmos
obtiveram empate, isto é, o percentual de distância da melhor solução igual a 0% para
ambos os algoritmos. Estas instâncias estão descritas na coluna instância da Tabela 3. As
colunas AGh e ProtoG com busca local da Tabela 3 estão divididas em duas: distância que
contém o percentual de distância e tempo que contém o tempo gasto para encontrar a
73
melhor solução. Observando a Tabela 3, verifica-se que para apenas uma instância o
algoritmo ProtoG com busca local gastou mais tempo em relação ao AGh.
TABELA 3
Tempo de processamento para as instâncias que os Algoritmos ProtoG e AGh
obtiveram percentual de distância igual a 0%
AGh
ProtoG com busca local
melhor
distância
distância
solução
tempo
(seg.)
tempo (seg.)
instância
%
%
D1
253161
0
399
0
269
D2
251636
0
429
0
268
D3
202315
0
579
0
250
D6
159303
0
450
0
267
D7
136741
0
752
0
243
D8
133955
0
292
0
241
D10
179432
0
180
0
273
D11
184646
0
1026
0
710
O segundo grupo foi formado pelas instâncias em que algoritmo ProtoG com
busca local obteve soluções de melhor qualidade do que AGh. As instâncias estão descritas
na coluna instância da Tabela 4. As colunas AGh e ProtoG com busca local da Tabela 4
estão divididas em duas: distância que contém o percentual de distância da melhor solução
e tempo que contém o tempo gasto pelo algoritmo para encontrar a sua melhor solução.
Observando a Tabela 4, verifica-se que para cinco instâncias, o algoritmo
ProtoG com busca local utilizou menos tempo que o AGh. Nas instâncias restantes, o
ProtoG com busca local obteve melhor solução e gastou mais tempo que o AGh. Para estas
instâncias, foi dado o mesmo tempo utilizado pelo ProtoG ao AGh. O AGh utilizando o
mesmo tempo gasto pelo ProtoG com busca local conseguiu, entre as 19 instâncias, reduzir
o percentual de distância de duas instãncias: C5 e C10 ficaram com um percentual de
distância de 0,1073% e 0,0785%, respectivamente.
O terceiro grupo foi formado pelas instâncias em que AGh obteve soluções de
melhor qualidade do que ProtG. Estas instâncias estão descritas na coluna instância da
Tabela 5. As colunas AGh e ProtoG com busca local da Tabela 5 estão divididas em duas:
distância que contém o percentual de distância da melhor solução e tempo que contém o
tempo gasto pelo algoritmo encontrar a sua melhor solução.
Observando a Tabela 5, verifica-se que para duas instâncias, o AGh utilizou
mesmo tempo que o algoritmo ProtoG com busca local. Nas outras cinco instâncias, o AGh
obteve melhor solução e gastou mais tempo que o ProtoG com busca local. Para estas
74
cinco instâncias, foi dado o mesmo tempo utilizado pelo AGh ao ProtoG, sendo que três
instâncias reduziram o percentual de afastamento: B11 ficou com um percentual de
distância de 0,16%, B12 com 1,15% e B5 com 1,2%.
TABELA 4
Tempo de processamento para as instâncias em que o Algoritmo ProtoG obteve
percentual de distância igual a 0%
AGh
ProtoG com busca local
melhor
distância
tempo
distância
tempo
solução
instância
%
(seg.)
%
(seg.)
D4
175684
0,09107
547
0
1052
D9
169086
0,06564
2758
0
646
D12
181846
0,001649
470
0
220
C1
648255
0,078518
6942
0
1405
C2
559495
0,001966
6198
0
1508
C3
592329
0,235342
2545
0
4959
C4
654769
0,295939
3174
0
1050
C5
394887
0,205881
729
0
1944
C6
436790
0,32693
1657
0
3360
C7
416498
0,24561
1644
0
1740
C8
397294
0,46262
1340
0
1740
C10
487653
0,10212
472
0
1440
C11
477072
0,01194
1802
0
5482
C12
380867
0,18930
940
0
1936
B1
1317014
0,08352
3549
0
3911
B2
1255661
0,27245
7143
0
9494
B3
1215329
0,10782
4297
0
6420
B4
1126218
0,27969
7194
0
7251
B7
808085
0,16088
3165
0
7951
TABELA 5
Tempo de processamento para as instâncias em que o AGh obteve
percentual de distância igual a 0%
AGh
ProtoG com busca local
melhor
distância tempo
distância
tempo
instância solução
%
(seg.)
%
(seg.)
D5
165521
0
0,0006
834
616
C9
451869
0
0,3863
6086
1478
B5
962880
0
5679
1,6709
1241
B6
799406
0
5254
1,6722
1980
B8
883077
0
7149
0,0527
6100
B11
889170
0
7197
2,2704
1587
B12
857382
0
7136
2,2660
2285
75
7
CONCLUSÕES
A implementação de dois operadores, sendo que um deles foi descartado por
gerar um número muito grande de indivíduos inviáveis, mostra a importância que a escolha
de operadores de cruzamento tem no desempenho dos AGh.
O ProtoG com busca local apesar de não usar operadores de cruzamento e
mutação, fornece melhores resultados qualitativos para o PPSP do que o AGh. O ProtoG
com busca local também fornece melhores resultados qualitativos que o ProtoG sem busca
local. O uso da busca local forneceu bons resultados para o algoritmo ProtoG.
Observa-se que a comparação qualitativa foi realizada com o mesmo tempo de
processamento para ambos os algoritmos. No caso de empate, as rodadas do ProtoG com
busca local utilizaram, em sua maioria, o menor tempo.
Outro aspecto importante a ser considerado é a regra de parada para o ProtoG.
Um número de interações sem melhorar a melhor solução corrente não se mostrou uma boa
condição de parada, pois se observou que quatro instâncias ficaram com valor de solução
inferior a solução fornecida pelo método guloso e construtivo ERR utilizado para compor o
BM. Além disso o tempo de parada na condição anterior foi muito pequeno. A condição de
parada deve considerar as informações contidas no BM e analisar se o BM fornece
possibilidade de proporcionar melhoria nos cromossomos da população. Além de um
número específico de interações e um número de interações sem melhorar a melhor
solução corrente, uma outra condição de parada poderia ser adotada. Esta condição poderia
ser, no mínimo: o melhor indivíduo da população tem um valor de fitness melhor do que
valor de uma solução do BM e o número de interações já foi atendido.
Em relação ao tempo, a disponibilidade de mais tempo para o ProtoG com
busca local proporcionou melhoraria da solução.
Trabalhos futuros podem incluir a extensão do que foi implementado nesta
tese. Entre eles, o uso de partículas com tamanhos inferiores a 10% do tamanho do
cromossomo, agentes do tipo vírus com tempo de vida diferente de zero.
76
8
REFERÊNCIAS BIBLIOGRÁFICAS
ALBERS, Susanne, 1997, “Competitive Online Algorithms”, OPTIMA - Mathematical
Programming Society Newsletter, v. 54, 1-8.
ANTONISSE, J., 1989, “A new interpretation of schema notation that overturns the binary
encoding constraint”, In: Proceedings of the Third International Conference on Genetic
Algorithms, Schaffer, J.D. (Ed.), Mateo, CA, 1989, 86-91.
Available from < www.cba.ufl.edu/dis/papers >
ALTENBERG, Lee, 1994, “The Schema Theorem and Price’s Theorem”, In: Foundations
of Genetic Algorithms, Whitley, D., Vose, A. (Eds), v.3, San Mateo, CA: Morgan
Kaufman, 23-49.
BÄCK, T.; SCHEWEFEL, Hans-Paul, 1999, Evolutionary Computation: An Overview, In:
IEEE International Conference On Evolutionary Computation, Nagoya – Japan.
BRAMLETTE, M.F, 1991, "Initialization, Mutation, and Selection Methods in Genetic
Algorithms for Function Optimization", In: Proceedings of the Fourth International
Conference on Genetic Algorithms, Belew, R.K., Booker L.B. (Eds.), San Mateo, CA:
Morgan Kaufman, 100-107.
BURIOL, Luciana, FRANÇA, Paulo M., MOSCATO, Pablo, 1999, Algoritmo Memético
para o Problema do Caixeiro Viajante. Anais do XXXI Simpósio Brasileiro de Pesquisa
Operacional, (Outubro) Juiz de Fora, MG, Brasil.
CAIXETA, Nely, 2001, Você ainda não viu nada, Revista Exame, São Paulo, 10 jan. 2001.
edição 731, ano 35 No 01 p. 44-50.
CAMPELLO, R., MACULAN, N., 1994, Algoritmos e Heurísticas - Desenvolvimento e
Avaliação de Performance, Editora da Universidade Federal Fluminense, Niterói, RJ.
CARVALHO, Dinis, 2000, Programação da Produção, Relatório Técnico, Departamento
de Produção e Sistemas, Universidade de Minho, Portugal.
CHAN, K. C., TANSRI, H., 1994, "A Study of Genetic Crossover Operations on the
Facilities Layout Problem", Computers and Industrial Engineering, v. 26, 537-550.
CHEN, Zhi-Long, POWELL, Warren B., 1998, Solving Parallel Machine Scheduling
Problens by Column Generation,. INFORMS Journal on computing, No 11, 78-94.
CUNHA, A. G. L., 1999, Modelling and Optimisation of Single Screw Extrusion, (Tese
de doutorado), Departamento de Ciências e Engenharia de Polímeros – Universidade de
Minho.
CURY, Ricardo M., 1999, Uma Abordagem Difusa para o Problema de Flow-shop
Scheduling, (Tese de doutorado) – Faculdade de Engenharia de Produção, Universidade
Federal
de
Santa
Catarina,
Florianópolis.
Disponível
em:
http://www.eps.ufsc.br/teses99/cury.
77
CAPRA, Fritjof, 2001, A teia da vida - Uma Nova Compreensão Científica dos Sistemas
Vivos, tradução Newton Roberval Eichenberg. São Paulo: Editora Cultrix, 5ª edição (2001).
D’ALMEIDA, Albino L., 2000, Determinação de Frota de Sondas de Petróleo Aplicando
a Teoria das Opções Reais, In: Rio Oil & Gás Expo and Conference, (Outubro) Rio de
Janeiro, RJ, Brasil.
DE JONG, Kenneth; SPEARS,W., 1993, “On The State of Evolutionary Computation”,.
In: Proceedings of the Sixth Conference on Genetic Algorithms, 618-623. Available from
< http://www.aic.nrl.navy.mil/~spears/ea.html>
EPSTEIN, L., NOGA, J., SEIDEN, S., SGALL, J., WOEGING, G., 2001, “Randomized
on-line Scheduling on two Uniform Machines”, In: Journal of Scheduling, v. 4, No 2
(março – abril 2001), 104-121.
ESHELMAN, L. J., SCHAFFER, J. D., 1992, “Real-Coded Genetic Algorithms and
Interval-Schemata”, In: Foundations of Genetic Algorithms, Whitley, L.D. (Ed.), v.2, San
Mateo, CA: Morgan Kaufman, 5-17.
FLEURENT, C., FERLAND, J. A., 1994, Genetic and Hybrid Algorithm for Graph
Coloring, Technical. Report - Université de Montréal.
FRANÇA, P., MENDES, A., MOSCATO, P., 1999, “Memetic Algorithms to minimize
tardiness on a Single Machine Scheduling with sequence-dependent setup times”, In: 5th
International Conference of the Decision Sciences Institute, Athens, Greece.
FOGEL, David B., 1997, The Advantages of Evolutionary Computation,. Natural
Selection, Inc. Bio – Computing and Emergent Computation. Singapore: Sköbe, Sweden,
World Scientific Press.
GLOVER, F., LAGUNA, M., 1997, Tabu Search, Kluver Academic Publishers – USA,
apud ROGIA, Iria B., 1998, “Método Heurístico para Solução do Problema de
Sequenciamento Cíclico de n tarefas em m Processadores Paralelos Idênticos”, in: 3ª
Semana Acadêmica do Curso de
Pos-graduação da Ciência da Computação –
Universidade Federal do Rio Grande do Sul.
GOLDBARG, Marco C., LUNA, Henrique Pacca L., 2000, Otimização Combinatória e
Programação Linear - Modelos e Algoritmos, Editora Campus, Rio de Janeiro.
GOLDBARG, M. C., GOUVÊA, Elizabeth. F., 2000, Extra–Intracellular Transgenetic
Algorithm, Natal – RN: Universidade Federal do Rio Grande do Norte.
GOLDBARG, Marco C., GOUVÊA, Elizabeth. F., SILVA, Lívia. Maria da., 2001a, A
Transgenetic Approach for The Graph Coloring Problem,.In: EURO 2001- European
Operational Research Conference, Roterdan EURO 2001 Proceedings. 2001, 34-34.
GOLDBARG, Marco C., GOUVÊA, Elizabeth F., MEDEIROS, Ana, C. C., 2001b, A
Transgenetic Algorithm Applied to the Piston Pump Mobile Unity Tour Problem, In:
EURO 2001- European Operational Research Conference, Rotterdan. EURO 2001
Proceedings. 2001, p.36.
78
GOLDBERG, Leslie. Ann, PATERSON, Mike, SRINIVASAN, Arivand, SWEEDY,
Elizabeth, 1997, Better Approximation Guarantes for Job-shop Scheduling, In: proc. ACM
– SIAN Symposiun on Discrete Algorithms, 599-608.
GOUVÊA, Elizabeth F., 2001, Transgenética Computacional – Um Estudo Algorítmico,
(Tese de Doutorado) COPPE – UFRJ.
GOUVÊA, E. F., GOLDBARG, M. C., 2001, “ProtoG: a Computational Transgenetic
Algorithm”, In: MIC’2001 – 4th Metaheuristics International Conference, Porto –
Portugal, July 16 – 20, 625- 630.
GUYAGULER, B., HORNE, R. N., 2000, "Optimization of Well Placement", Journal of
Energy Resources Technology 122, 64-70.
HAYKIN, S., 1999, Neural Networks: A Comprehensive Foundation, Pretice Hall.
HUSBANDS, Philip, MILL, Frank, 1994, Scheduling with Genetic Algorithms, AISB
Quarterly, nº 89.
ICHIHARA, J. A., 1998, Um Método de Solução Heurístico para a Programação de
Edifícios Dotados de Múltiplos Pavimentos – tipo, (Tese de Doutorado), Departamento de
Engenharia de Produção e Sistemas - Universidade Federal de Santa Catarina.
JAIN, A. S.; MEERAN S., 1999, “Deterministic Job-shop Scheduling: past, present and
future”, European Journal of Operations Research, v.118.
JORDAN, G. C., 2001, Investigação Operacional e Optimization, Relatório Técnico,
Departamento de Matemática, Universidade de Minho - Portugual.
JONES, A., RABELO, L. C., 1998, Survey of Job Shop Scheduling Techniques, Technical
Report, NISTIR - National Institute of Standards and Technology, Gaithersburg, MD.
KORTHOF, Gert, 2001, Retrogenes: genes that don’t behave – Reverse transcription: who
needs it?, available from <http://home.wxs.nl/~gkorthof/kortho39.htm>.
KOMOSINSKI, L. J., LACERDA, C. D. de F., BORGES, P. S. S.,1998, “Aprendizagem
Mediada por Algoritmos Genéticos”, In: Congresso RIBIE, Brasília, DF, Brasil.
LACADENA, Jaun Ramón, 2001, Evolucioón de La Humanidade: Evolución Biológica y
Evolución Cultural, Revista Latinoamericana de Bioética No1.
LANCIA, Giuseppe, 2000, “Scheduling Jobs with Release Dates and Tails on Unrelated
Parallel Machines to Minimize the Madespan”, European Journal of Operational
Research, v. 2, 277-288.
LAND, Mark W. S., 1998, “Evolutionary Algorithms with Local Search for Combinatorial
Optimization”, (Tese de Doutorado), University of Califórnia, San Diego.
79
MAYLEY, G., 1996, “The Evolutionary Cost of Learning”, In: From Animals to Animats:
Proceedings of the Fourth International Conference on Simulation of Adaptive Behaviour,
Proc. Of the fourth Int. Conf. On S of Adaptaive Behavior, . Maes, P., Mataric, M., Meyer,
J-A., Pollack, J., Wilson, S. (Eds.), London: MIT Press.
MENDES, Alexandre S., 1999, Algoritmos Meméticos Aplicados aos Problemas de
Sequenciamento em Máquinas, (Tese de Mestrado), Faculdade de Engenharia Elétrica e
Computação - Universidade Estadual de Campinas.
MICHALEWICZ, Zbigniew (Ed.), 1996, Genetic Algorithms + Date Structures =
Evolution Programs, Springer.
MITCHELL, Melanie, 2000, Life and Evolution in Computers,. In: Darwinian Evolution
Across the Disciplines, ed. M. McPeek.
MOSCATO, Pablo, 1989, “On Evolution, Search, Optimization, Genetic Algorithms and
Martial Arts”, Caltech Concurt Computation Program 158-79, California Institute of
Technology, Program,C3P Report 826.
MÜHLENBEIN, Heinz, 1993, “Evolutionary Algorithms: Theory and Aplications”, In:
Tech. Rep. Nº GMD AS GA 93-03, German National Reserarch Center for Computer
Science (GMD), German.
PAIVA, R. O., SCHIOZER, D. J., BORDALO, S.N., 2000, “Optimizing the Itinerary of
Workover Rigs”, In: World Petroleum Congress 16., Calgary – Canada.
PAPADIMITRIOU, C. H., STEIGLITZ, K., 1982, Combinatorial Optimization –
Algorithms and Complexity, © 1982 by Prentice-Hall, Inc. Englewood Cliffs, New Jersey.
POTVIN, Jean-Yves, 1996, “Genetic Algorithms for the Traveling Salesman Problem”, In:
Annals of Operations Research, v. 63, 339-370.
RADCLIFFE, N. J., SURRY, P. D., 1994, Formal Memetic Algorithms, Edinburgh
Parallel Computing Centre, King’s Buildings, University of Edinburgh.
REBELLO, F. R., HAMACHER, S., 2000, "Uma Proposta de Algoritmo Genético de Duas
Fases para Roteamento de Veículos", Anais do XXXII Simpósio Brasileiro de Pesquisa
Operacional, Viçosa, MG, Brasil.
ROGIA, Iria B., 1998, “Método Heurístico para Solução do Problema de Sequenciamento
Cíclico de n Tarefas em m Processadores Paralelos Idênticos”, In: 3ª Semana Acadêmica
do Curso de Pos-graduação da Ciência da Computação – Universidade Federal do Rio
Grande do Sul.
SALZANO, Francisco M., 1993, Biologia, Cultura e Evolução, 2ª edição, Editora da
Universidade, Porto Alegre.
SANTOS, Robson da Cunha, CUNHA, Gerson G., 2000, “O uso de Algoritmos Genéticos
e Realidade Virtual na Determinação da Posição da Cabine de Controle em Sondas de
Perfuração”, In: Rio Oil & Gás Expo and Conference, Rio de Janeiro - Brasil.
80
SHI, Gouhong, 1997, “A Genetic Algorithm Applied to a Classic Job-Shop Scheduling
Problem”, International Journal of Systems Science, v. 28, No 1, 25-32.
SMIDERLENE, Andréia, 2001, Técnicas da Pesquisa Operacional Aplicadas - Um
Problema de Cobertura de Arcos, (Dissertação de Mestrado) - Curso de pós-graduação em
Métodos Numéricos em Engenharia – Programação Matemática, Universidade do Paraná.
SOURD, Francis; NUIJTEN, Win, 2001, “Scheduling with Tails and Deadlines”, Journal
of Scheduling, v. 4, No 2, (março – abril 2001), 104-121.
SZPILMAN, Marcelo, O Mundo de Darvin e a Teoria da Evolução, Instituto Ecológico
Aqualung - on line, informátivo nº 08, julho/agosto de 1996.
SZWACFITER, L. J., 1988, Grafos e Algoritmos Computacionais, Editora Campus, 2ª
edição, Rio de Janeiro.
THOMAS, J. E. (Ed.), 2001, Fundamentos de Engenharia de Petróleo, Editora
Interciência, Rio de Janeiro.
TURNEY, P., 1996, Myths and Legends of the Baldwin Effect, Proceedings of the
Workshop on Evolutionary Computing and Machine Learning at the 13th International
Conference on Machine Learning, Bari, Italy, 35-142.
VAESSENS, R. J. M., AARTS, E. H. L., LENSTRA, J. K., 1994, Job Shop Scheduling by
Local Search, Technical Report COSOR Memorandum 94-05, Eindhoven University of
Technology.
WHITLEY, D., 1993, A Genetic Algorithm Tutorial, Technical Report CS-93-103,
Computer Science Department, Colorado State University.
WHITLEY, D., GORDON, S., MATHIAS, K., 1994, “Lamarckian Evolution, The
Baldwin Effect and Function Optimization”, In: Parallel Problem Solving from NaturePPSN III, Davidor, H., P. Schwefel and R. Manner, (Eds.), Springer-Verlag, 6-15.
Available from <http://www.cs.colostate.edu/~genitor/Pubs.html#1994>
WILLIAMSON, D. P., HALL, L. A., HOOGEVEEN, J. A., LENSTRA, J. K.,
SERVASTO’JANOV, S. V., SHMOYS, D. B., 1997, Short Shop Schedules, Operations
Research 45, 288-294.
WILSON, E. O., 1999, A unidade do conhecimento – Consiliência, Editora Campus, Rio
de Janeiro.
YAMADA, Takeshi; NAKANO, Ryohei, 1996, “Job Shop Scheduling by Simulated
Anneling Combinied With Deterministic Local Search”, In: Kluver Academic Publishers,
MS – USA.
ZUBEN, Fernando J. V., 2000, “Computação Evolutiva: Uma Abordagem Pragmática”,
Anais da I Jornada de Estudos em Computação de Piracicaba e Região (1ª JECOMP), v.
1, 25-45.
81