1: t ← 0
2: Pop0← Gerar_população_inicial_e_avaliar(#tamPop)
3: E0 ← filtro(Pop0)
4: Para cada solução i em Qt = Popt Et
5: Calcular os valores Si, Ri, Di
6: Calcular o valor de aptidão Fi
7: fim_para
7: RH ← Criar repositório do hospedeiro(#mc) 10: Repetir
11: CI ← Selecionar(RH)
12: Se (t % β = 0) então /*mudança de patamar*/ 13: decrementar(#probTransp)
14: #probPlasm ← 1.0 - #probTransp 15: fim_se
16: Para j ← 1 até #tamPop
17: Se (random() < #probPlasm) então 18: r ← rand(0,1)
19: Se (r = 0) então
20: filho[j] ← Plasm(Qt[j], CI)
21: senão
22: filho[j] ← PlasmR(Qt[j], CI)
23: fim_se 24: senão
25: Se (random() < #probTempDefragTransp) então 26: filho[j] ← tempDefragTransp(Qt[j]) 27: senão 28: filho[j] ← defragEnergTransp(Qt[j]) 29: fim_se 30: fim_se 31: funçõesReparadoras(filho[j]) 32: fim_para 33: Et+1← filtro(Qt, filho)
34: Se (|Et+1| > #tamE) então
35: Reduzir Et+1 utilizando o algoritmo de corte
36: fim_se
37: Se (|Et+1| < #tamE) então
38: Ordenar Q t conforme Fi
39: Qt+1← Copiar as melhores #tamE− |Et+1| soluções i de Qt∩ Et+1 tal que Fi≥ 1
40: fim_se
41: RH ← Atualizar(RH) 42: t ← t + 1
43:até que t > tmax
Após a aplicação dos vetores transgenéticos, uma vez calculado o valor de aptidão são copiados as soluções não dominadas de Qt para a nova população externa
72
Todas as soluções não dominadas do conjunto Qt são transferidas para a
população externa da próxima geração Et+1, sendo avaliadas novamente as relações de
dominância das novas soluções inseridas com as já contidas nesse conjunto, mantendo- se no mesmo apenas as soluções não dominadas. Caso o arquivo externo não seja totalmente preenchido, é completado com os indivíduos dominados de Qt, ordenados em
ordem crescente do valor de aptidão. Caso a dimensão de Et+1 ultrapasse o valor pré-
determinado #tamE, é aplicado um algoritmo de corte para eliminar os indivíduos excedentes. O algoritmo de corte é um processo iterativo que remove, a cada iteração, o indivíduo tal que a sua distância euclidiana para o vizinho mais próximo seja mínima dentre todos os indivíduos do arquivo. Em caso de empate, verifica-se a segunda menor distância euclidiana, e assim por diante.
A função de aptidão para um cromossomo i é a soma da força dos cromossomos que dominam i. Assim, o melhor cromossomo é determinado pela função aptidão, quanto menor o seu valor melhor é sua avaliação para Qt.
O repositório de informações do hospedeiro é atualizado. A atualização corresponde à inserção do melhor cromossomo gerado nesta iteração do laço principal. O melhor cromossomo é determinado também com base na força dos cromossomos que dominam i. Assim, a avaliação do melhor cromossomo é realizada em Qt. Esse melhor
cromossomo somente é inserido no repositório caso ele seja melhor que o pior cromossomo armazenado no repositório. Esta avaliação do cromossomo para entrada no repositório é feita com base no uso de ponderação aleatorizada (com os três objetivos normalizados) com uniformidade. Caso isso ocorra o pior cromossomo armazenado é descartado para dar lugar ao melhor cromossomo desta geração. Caso contrário, nada ocorre durante a atualização.
Finalmente, o critério de parada é testado. Caso isso tenha ocorrido o algoritmo é encerrado; caso contrário uma nova iteração do laço principal é executada (nova geração).
5.2.1 Implementação do SPETA para o PTDPP
O algoritmo básico do SPETA para o Problema é o mesmo apresentado na Seção 8.2, apenas adaptando os componentes do algoritmo para o problema em questão. O algoritmo é detalhado a seguir.
A população inicial é gerada aleatoriamente, da mesma maneira que é gerada para os demais algoritmos aplicados ao Problema.
O algoritmo entra em seu laço principal (passos de 10 a 43 do Algoritmo 10). Primeiro, uma cadeia de informação (CI) é gerada para ser utilizada pelos vetores transgenéticos. Neste trabalho são usados os vetores plasmídeos e transposons. A escolha entre um ou outro vetor é aleatória com probabilidade dependente do patamar evolucionário no qual o algoritmo se encontra.
73
Um cromossomo é escolhido aleatoriamente no repositório do hospedeiro e, então, parte do que é selecionado para compor a cadeia de informação. O tamanho da cadeia de informação é determinado aleatoriamente no intervalo [0,10c; 0,40c], em que
c representa o número de conexões da instância do problema. Deixa tamCI ser o tamanho da cadeia de informação, então, tamCI conexões, onde CI é uma lista de 3- tuplas composta por: poliduto, instante de tempo e produto, ou seja, ((poliduto1, tempo1,
prod1),..., (polidutotamPlasm, tempotamPlasm, prodtamCI)) , onde prodi é o produto bombeado
no poliduto polidutoi no instante tempoi correspondente ao i-ésimo da 3-tuplas do
plasmídeo. Cada 3-tupla da CI é escolhida aleatoriamente a partir do cromossomo doador.
Um novo cromossomo, novo, é gerado a partir de cada um existente, crom. Primeiro, os produtos da cadeia de informação são associados aos polidutos correspondentes e períodos de tempo do novo. Em seguida, as posições restantes do
novo são copiadas do crom.
No plasmídeo recombinado a heurística defragmentação é aplicada para as conexões na cadeia de informação. Se, após a defragmentação, o cromossomo resultante é inviável, então é reparado. Em seguida, o procedimento identifica pares (poliduto, instante) com nenhum produto que lhes foi atribuído. Se nenhum produto está sendo enviado na conexão p em um dado instante, então, as bateladas na conexão p são compactadas a fim de diminuir o tempo de entrega. Em seguida, o cromossomo manipulado é adicionado à população filha.
Se o novo cromossomo é inviável após a aplicação dos vetores transgenéticos, emtão, é reparado.
Ambos os vetores transgenéticos adotados neste algoritmo são semelhantes aos adotados no NSTA.
Após isso, o repositório de informações do hospedeiro (RH) é atualizado. Esta atualização corresponde à substituição dos #mc anteriores pelos #mc melhores da nova população.
Finalmente, o critério de parada é testado, o qual corresponde a um número máximo de iterações (gerações) do laço principal.
5.3 MOTA/D
O MOTA/D é uma proposta de algoritmo que corresponde a implementação do
framework baseado em decomposição MOEA/D com operadores transgenéticos.
Algumas modificações do algoritmo original do MOEA/D, que trabalha originalmente com operadores genéticos (Zhang; Li, 2007), foram necessárias para acomodar a inicialização e atualização dos repositórios do hospedeiro e o uso destas informações através dos vetores transgenéticos (operadores). No Algoritmo 11 é apresentado o pseudocódigo do MOTA/D.
74