Tap
av
celleklumper
ved
Lymphoprep‐metoden

1: Gerar e avaliar a população de cromossomos (Pop) 2: Inicializar o repositório do hospedeiro (RH)

3: Repita

4: Gerar vetores transgenéticos (VetTrans, RH)

5: Subpop ← Selecionar cromossomos para manipulação (Pop)

6: Novapop ← Manipular os cromossomos selecionados (Subpop, VetTrans) 7: Atualizar(Novapop,RH)

8: Pop ← Novapop

9: Até que um critério de parada seja satisfeito

O Algoritmo 6 apresenta o framework geral do algoritmo transgenético. A população inicial de endossimbiontes é criada e avaliada no passo 1. O repositório do hospedeiro é inicializado com informações a priori e, se existir alguma informação interessante na população, então ela é também incluída no referido repositório. Os passos de 3 a 9 são repetidos até que um critério de parada seja satisfeito. No passo 4, os

52

vetores transgenéticos são gerados e, no passo 5, um conjunto de cromossomos é escolhido para ser manipulado. Se a ação dos vetores transgenéticos nos cromossomos da população produz novas informações, então o repositório do hospedeiro é atualizado no passo 7.

Em um algoritmo transgenético, vários tipos de informações são combinados, por meio de contextos de informação interdependentes, porém autônomos. Assim, o aninhamento destes contextos resulta em um comportamento complexo. Em virtude desta característica, a abordagem transgenética se caracteriza pelo gerenciamento de informações. Portanto, se o problema é capaz de fornecer informação de qualidade, esta metaheurística tem grande probabilidade de obter resultados competitivos quando comparada a outras abordagens (Goldbarg e Goldbarg, 2009).

4.4.1 Aplicações de Algoritmos Transgenéticos

A transgenética computacional tem sido aplicada com sucesso a diversos problemas de otimização combinatória. Os primeiros resultados da transgenética computacional foram obtidos para o problema quadrático de alocação (Goldbarg e Goldbarg, 2000a) (Goldbarg e Goldbarg, 2000b) (Goldbarg e Goldbarg, 2001). Outras aplicações dos algoritmos transgenéticos foram no problema da coloração de vértices (Goldbarg; Goldbarg; Silva, 2001), no flow shop de permutação (Goldbarg; Goldbarg; Costa, 2004), no problema do caixeiro viajante (Goldbarg; Goldbarg; Ramos, 2003), no problema do caixeiro comprador (Goldbarg; Bagi; Goldbarg, 2009) (Goldbarg e Goldbarg, 2009) (Goldbarg; Goldbarg; Bagi, 2008), no problema do caixeiro viajante com aluguel de carros (Asconavieta; Goldbarg; Goldbarg, 2011), na predição da estrutura de proteínas (Almeida et al., 2007), no problema da árvore de steiner com coleta de prêmios (Goldbarg; Goldbarg; Schmidt, 2008), na otimização da configuração de um serviço de distribuição de vídeo baseado em replicação móvel (Goldbarg; Goldbarg; Medeiros, 2001b) e na otimização do planejamento do tratamento radioterápico (Goldbarg et al., 2009).

A metáfora também está sendo aplicada favoravelmente a problemas de otimização combinatorial com múltiplos objetivos, tais como o problema da árvore geradora biobjetivo (Monteiro; Goldbarg; Goldbarg, 2009) (Rocha; Goldbarg; Goldbarg, 2007), o problema do caixeiro comprador biobjetivo e o problema quadrático de alocação multiobjetivo (Almeida, 2012).

Além disso, existem várias aplicações em problemas do mundo real especialmente na área Petróleo, Gás e Energia. Algumas destas aplicações foram apresentadas por: Goldbarg, Goldbarg e Neto (2005), Goldbarg, Goldbarg e Duarte (2010), Goldbarg, Castro e Goldbarg (2004) e Souza, Goldbarg e Goldbarg (2011).

53

4.5 Implementações para o Problema Triobjetivo de

Distribuição de Derivados de Petróleo por Redes de Polidutos

Nas subseções seguintes são descritas as implementações dos algoritmos NSGA2, SPEA2, MOEA/D e algoritmo transgenético (AT) para o problema triobjetivo de distribuição de derivados de petróleo por redes de polidutos.

4.5.1 Representação do Cromossomo

A representação do cromossomo é a mesma para todos os algoritmos implementados. Cada cromossomo é codificado em um vetor como ilustrado na Tabela 4.2, em que uma solução para o problema com quatro produtos, dez conexões e um horizonte de planejamento de 10 unidades de tempo é esboçada. Os produtos são numerados de 1 a 4, um 0 indica que nenhum produto está a ser enviado pela correspondente conexão na correspondente unidade de tempo. As conexões bidirecionais são desdobradas em duas conexões, cada uma representando uma direção de fluxo. Neste exemplo mostra que o produto 1 está sendo enviado pela conexão D1 no

tempo 1 e pela conexão D2 no tempo 10, produto 2 está sendo enviado pelas conexões

D5 e D9 no tempo 1 e pelas conexões D1, D6 e D7 no tempo 10, e assim por diante.

Tabela 4.2 - Exemplo de vetor de soluções.

Tempo 1 ... 10

Conexão 1 2 3 4 5 6 7 8 9 10 ... 1 2 3 4 5 6 7 8 9 10 Produto 1 0 0 3 2 3 3 0 2 3 ... 2 1 3 0 0 2 2 3 0 3

4.5.2 Recombinação

Nos algoritmos NSGA2 e SPEA2 propostos são utilizados a recombinação de dois pontos. A recombinação de k-pontos é apresentada por Holland (1975). Duas novas soluções são obtidas a partir de dois pais com esse operador de recombinação, através da troca de k+1 segmentos das sequências do pai. Os pontos de recombinação são selecionados aleatoriamente com probabilidade uniforme.

A Figura 4.7 ilustra a operação de recombinação de dois pontos, que é utilizado indivíduos para um problema com uma rede composta por dois dutos (conexões), que transporta quatro tipos diferentes de produtos e um horizonte de seis períodos de tempo.

54 1 1 0 2 1 1 2 2 0 1 1 1 1 0 2 1 2 0 0 1 2 1 2 0 1 1 0 1 2 0 0 1 2 1 1 1 1 0 2 2 1 1 2 2 0 1 2 0 Pai 2 Filho 1 Filho 2 Pai 1

Figura 4.7 - Exemplo da operação realizada pela Recombinação de Dois Pontos.

4.5.3 Mutação

O operador mutação é realizado sobre os novos indivíduos gerados após a recombinação, mediante uma taxa que indica a probabilidade da mutação ocorrer. A mutação é um importante operador genético, pois é responsável em provocar a diversidade na população, percorrendo assim um campo maior do espaço de busca de soluções. Seu conceito consiste em mudar aleatoriamente um indivíduo existente de forma que um novo indivíduo seja criado.

Nos algoritmos NSGA2 e SPEA2, a mutação é feita em um determinado gene, substituindo o produto no poliduto correspondente a esse gene por outro produto selecionado aleatoriamente entre aqueles que podem ser atribuídos ao poliduto correspondente.

4.5.4 Funções Reparadoras

Após a geração dos indivíduos da população inicial e depois da aplicação dos operadores genéticos de recombinação e de mutação, algumas restrições do problema podem não ser satisfeitas, assim, são usadas funções reparadoras, que têm por objetivo promover a viabilidade das soluções (Souza et al., 2009). Existem quatro funções reparadoras:

 Repara tempo devido para entrega: verifica se os limites máximos para o tempo de chegada das bateladas nos nós terminais estão sendo violados. As bateladas que violam esse limite de tempo máximo são removidas.

Ponto de Cruzamento Ponto de Cruzamento

55

 Repara demanda: verifica para cada instante de tempo se a demanda de cada produto foi satisfeito. Se o número demandado de bateladas de um determinado produto tenha sido excedido, então, as bateladas excedidas serão removidas.  Repara capacidade de armazenamento: lida com a capacidade dos tanques,

verificando se a capacidade mínima dos nós de origem e a capacidade máxima dos nós de destino estão sendo violadas. Caso ocorra a violação da capacidade mínima dos tanques, a batelada do produto correspondente é removida da conexão e adicionada ao tanque de origem. Se a capacidade máxima no nó destino é violada as bateladas que excedem este limite são removidas.

 Repara colisão: lida com a ocorrência de colisões em conexões bidirecionais, verificando se duas bateladas enviadas no tempo t1 e t2, t1 < t2, colidem na mesma conexão, então a batelada que foi enviada no tempo t2 é removida. Se t1 = t2, então uma batelada é selecionada aleatoriamente, com probabilidade uniforme, e removida.

4.5.5 Implementação do algoritmo NSGA2 para o PTDPP

O pseudocódigo geral do NSGA2 para o problema investigado neste trabalho é apresentado no Algoritmo 7.

O mesmo procedimento de inicialização do algoritmo transgenético é usado para a gerar população inicial. Em seguida, a heurística de defragmentação apresentada por Westphal (2006) é usada.

No passo 1 a população inicial é gerada. Depois, no passo 5 são aplicados os

operadores de seleção de torneio, recombinação e mutação a Pt para gerar a população

filha Qt com tamanho de N indivíduos.

Após a aplicação dos operadores de recombinação e de mutação, algumas restrições podem ser violadas, portanto, são utilizadas as funções reparadoras, que são implementadas no procedimento reparar_funções (passo 6) do Algoritmo 7.

A população Rt é formada com os indivíduos da população Pt e Qt no passo 7. Os

cromossomos de Rt são classificados de acordo com os níveis de dominância que são

agrupados nos conjuntos de F1, F2, ... O conjunto F contém as fronteiras de F1, F2, ...

(passo 8). A população Pt+1, com tamanho N, é formada, iterativamente, com os

elementos de cada fronteira Fi, i = 1, 2, ... Se Ffinal é a última fronteira que contribui

com os elementos para Pt+1, então, espera-se que o número de elementos de Pt+1 mais

Ffinal exceda N. Assim, os elementos de Ffinal são ordenados de acordo o rank de

dominância e a distância de aglomeração (Deb et al., 2002) (passo 16). As N - |Pt+1|

melhores soluções de Ffinal de acordo com o operador de comparação são incluídas na

população Pt+1.

56 parâmetro tmax.