1: Pop ← Gerar_população_inicial_e_avaliar(N) 2: Classificar_fronteira_e_aglomeração(Pop) 3: RH ← Criar repositório do hospedeiro(#mc) 4: probPlasm ← 1.0 - #probTransp
5: Para i ← 1 até tmax
6: Se (i % β = 0) então /* mudança de patamar */ 7: decrementar(#probTransp)
8: #probPlasm ← 1.0 - #probTransp 9: fim_se
10: Para j ← 1 até #tamPop
11: Se (random( ) < #probPlasm) então 12: CI ← Selecionar(RH)
13: t ← random(0,1) 14: Se (t = 0) então
15: Novo[j] ← Plasm(Pop[j], CI) 16: senão
17: Novo[j] ← PlasmR(Pop[j], CI) 18: fim_se
19: senão
20: Se (random( ) < #probTempDefragTransp) então 21: Novo [j] ← tempDefragTransp(Pop[j]) 22: senão 23: Novo [j] ← defragEnergTransp(Pop[j]) 24: fim_se 25: fim_se 26: funçõesReparadoras(Novo[j]) 27: fim_para 28: Q ← Unir(Pop, Novo) 29: Classificar_fronteira_e_aglomeração(Q) 30: Pop ← Próxima_população(Q) 31: RH ← Atualizar(RH) 32: fim_para
A população inicial é gerada de maneira aleatória de acordo com as características do problema abordado (detalhes na Subseção 4.5.8.1). Depois, os cromossomos (soluções) da população inicial são avaliados e a fronteira e o valor de aglomeração são calculados (descrito na Seção 4.1.1). Um repositório de informações é criado (RH). O repositório é inicializado com os melhores cromossomos gerados na população inicial. Os #mc melhores cromossomos são armazenados neste repositório (RH), onde #mc é a quantidade de cromossomos considerada para a geração das cadeias de informação (fragmentos de soluções) de plasmídeos. Os melhores cromossomos são determinados pela melhor fronteira, isto é quanto mais baixo o valor da fronteira melhor é a avaliação do cromossomo. Em caso de empate, verifica-se o valor de aglomeração. Neste caso, quanto maior o valor, isto é, quanto mais esparsa for à área onde o vetor objetivo do cromossomo está, melhor.
68
As cadeias de informação possuem um tamanho mínimo e máximo que devem ser respeitados. Os fragmentos de uma solução que irão compor uma cadeia de informação são selecionados de maneira aleatória.
Após esta etapa de inicializações, o algoritmo NSTA entra no seu laço principal (passos de 5 a 32) do Algoritmo 9. Nesta etapa são aplicados os vetores transgenéticos e à população e o repositório de informação do hospedeiro são atualizados.
A melhor cadeia de informação do repositório é utilizada de acordo com um vetor de escalarização (com os objetivos normalizados) sorteado aleatoriamente com uniformidade. Esta cadeia é utilizada como informação dos plasmídeos para a manipulação dos cromossomos da população em uma determinada geração. Os vetores transgenéticos implementados no algoritmo NSTA apresentado neste trabalho são os plasmídeos, os plasmídeos recombinados e os transposons. A escolha entre utilizar plasmídeos ou transponsons se dá de maneira aleatória e depende do estágio evolutivo do algoritmo: nos estágios iniciais a probabilidade de escolha do vetor transposon é maior, enquanto nos estágios finais a probabilidade de escolha do vetor plasmídeo costuma ser superior (conforme explicado na Subseção 4.5.8.3). A variação da probabilidade de escolha de um ou outro vetor transgenético ocorre a cada gerações, onde é o tamanho dos patamares evolutivos adotados.
O vetor plasmídeo age inserindo a cadeia de informação selecionada no cromossomo sendo manipulado. Cabe salientar que, diferente do que normalmente ocorre na Transgenética Computacional, os vetores plasmídeo e transposon utilizados no NSTA não fazem uso do procedimento de ataque (p1). Isso ocorre para adequar o algoritmo ao arcabouço do NSGA2, permitindo que um filho e o cromossomo original possam estar presentes na próxima população de cromossomos; ou ainda que nem o cromossomo original nem seu filho estejam presentes. O primeiro caso, a longo prazo, pode resultar numa perda de diversidade da população.
Após a aplicação dos vetores transgenéticos, as populações de cromossomos originais e cromossomos filhos são unidas. Então, os cromossomos filhos são avaliados e os valores de fronteira de dominância e de aglomeração de cada cromossomo são recalculados. A seleção dos cromossomos que farão parte da próxima população é análoga àquela adotada pelo NSGA2.
O repositório de informações do hospedeiro é atualizado neste ponto do algoritmo (passo 31). A atualização corresponde à inserção do melhor cromossomo gerado na iteração corrente do laço principal. O melhor cromossomo é determinado pelo o uso de ponderação (com os três objetivos normalizados) aleatorizada com uniformidade. Esse melhor cromossomo somente é inserido no repositório caso ele seja melhor que o pior cromossomo armazenado no repositório. 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.
69
Finalmente, é testado se o critério de parada foi satisfeito. Caso isso tenha ocorrido o algoritmo é encerrado; caso contrário uma nova iteração do laço principal é executada (nova geração).
5.1.1 Implementação do NSTA para o PTDPP
A implementação do NSTA segue os passos básicos descritos na Seção 5.1, apenas adaptando os passos para lidar com o referido problema. São adaptados a representação das soluções, a geração da população inicial, a geração das cadeias de informações, os vetores transgenéticos adotados, o procedimento de reparação utilizado e o critério de parada.
A representação das soluções e a geração da população inicial são idênticas àquelas adotadas no NSGA2, SPEA2 e no MOEA/D (ver Subseção 4.5.1 e 4.5.8.1). Os
cromossomos (soluções) são avaliados como no NSGA2.
O repositório do hospedeiro, RH, é inicializado com cromossomos escolhidos aleatoriamente a partir dos #mc melhores cromossomos da população inicial. Esses cromossomos são selecionados da mesma forma que o NSGA2, ou seja, de acordo com
a fronteira e o valor de aglomeração. Os cromossomos são armazenados a fim de gerar cadeias de informação (fragmentos) para o repositório.
Um cromossomo é escolhido aleatoriamente no repositório do hospedeiro (RH) e, então, parte dele é selecionada para compor a cadeia de informação dos plasmídeos.
Assim, as cadeias de informação continuam sendo geradas de maneira aleatória e
continuam sendo fragmentos da solução armazenada. Esta cadeia de informação será utilizada pelos vetores transgenéticos: plasmídeos e plasmídeos recombinados. Os vetores transgenéticos utilizados no NSTA são os mesmos descritos nas Subseções 4.5.8.4 e 4.5.8.5.
Ambos os vetores transgenéticos adotados neste algoritmo são semelhantes aos adotados no MOTA/D e no SPETA, com a diferença que no NSTA eles não fazem uso do procedimento de ataque. O procedimento de ataque é substituído pelo método de seleção da próxima população do NSGA2, que, após a avaliação dos filhos gerados, corresponde ao próximo passo do algoritmo. Assim, depois que a nova população é gerada, ela é unida com a população atual e o algoritmo seleciona a população da
próxima geração baseando-se nos valores de fronteira e o valor de aglomeração.
5.2 Strength Pareto Evolutionary Transgenetic Algorithm -
SPETA
O SPETA é uma proposta de hibridização do framework do SPEA2 com os operadores dos ATs. Modificações tanto do framework quanto dos operadores dos ATs
70
foram necessárias para essa hibridização. O Algoritmo 10 apresenta o arcabouço geral do SPETA.
Os parâmetros de entradas do algoritmo SPETA são: o tamanho da população,
N, a probabilidade (inicial) de ataque por transposon, #probTransp, o número de
gerações, tmax, o intervalo de gerações para atualização dos patamares de probabilidade, , a quantidade de melhores cromossomos considerada para a geração das cadeias de informação, #mc e o tamanho do arquivo externo, #tamE e a probabilidade de ataque pelo transposon tempDefragTransp, #probTempDefragTransp.
A população inicial é gerada de maneira aleatória da mesma maneira que no algoritmo NSTA (explicado na Subseção 4.5.8.1). O arquivo externo (E) armazena o conjunto de soluções não dominadas encontradas pelo algoritmo. O procedimento
filtro() retorna as soluções não dominadas do conjunto parâmetro de entrada. Este
arquivo é limitado ao tamanho #tamE, em que seu tamanho é menor do que o tamanho da população, N. A cada iteração do laço (linhas 4 - 7), é realizado o cálculo da função de aptidão para cada cromossomo (solução) (linhas 5-6), conforme o SPEA2 já descrito na Seção 4.2. Do mesmo modo que no NSTA, o repositório RH é criado com #mc cromossomos.
Após a etapa de inicializações, o algoritmo SPETA entra no seu laço principal (passos de 10 a 43) do Algoritmo 10. Nesta etapa são aplicados os vetores transgenéticos à população e o repositório de informação do hospedeiro é atualizado.
Atualmente, o SPETA utiliza plasmídeos, plasmídeos recombinados e transposons como vetores transgenéticos, mas isso não é uma restrição do algoritmo. A escolha entre utilizar plasmídeos ou transposons se dá da mesma forma que no NSTA.
Os vetores transgenéticos utilizados no SPETA são os mesmos descritos nas Subseções 4.5.8.4 e 4.5.8.5. O vetor plasmídeo age inserindo a cadeia de informação selecionada no cromossomo sendo manipulado. O vetor transponson corresponde à manipulação de uma parte do cromossomo sendo atacado.
71