Konklusjon

Enquanto a movimentação de partículas em um espaço contínuo é perfeitamente compre- ensível, essa movimentação em um espaço discreto não é trivial. Por exemplo, a simples troca

de bits entre duas soluções espacialmente separadas deve gerar, na grande maioria das vezes, soluções espúrias, formadas por conjuntos desconexos de regiões espalhadas sobre o mapa. Para evitar essas soluções inviáveis, é necessário implementar uma maneira de fazer com que uma solução caminhe em direção a outra gerando outra solução factível, isto é, espacialmente conexa.

Para tanto, introduzimos o conceito de nicho. Seja Pi a população corrente na i-ésima

iteração do algoritmo e considere a zona z ∈ Pi que corresponde ao maior valor de λz. A essa

zona chamaremos pivô. Agora, identificamos todas as zonas que possuem alguma interseção com a zona pivô. Chamaremos esse conjunto de zonas formado pela zona pivô e pelas demais zonas com as quais ela possui interseção de nicho, o qual será denotado por n1. Agora seja Pi0 =

Pi−n1 o conjunto das zonas que não estão presentes no nicho n1. A partir de Pi0 construímos

um novo nicho n2identificando a zona pivô (isto é, a zona mais verossímil de Pi0) e as zonas que

fazem interseção com ela. O processo é repetido até que todas as zonas façam parte de algum nicho. Note que é possível que um nicho contenha apenas uma zona.

Com a intenção de emular o voo das partículas, para cada nicho faremos as zonas perten- centes a ele “caminharem” na direção do respectivo pivô. A forma com que esse “voo” é feito garante que apenas soluções conexas são geradas após o voo. Além disso, espera-se que dessas zonas híbridas (que possuem características tando da partícula que está voando quanto do pivô) possam eventualmente surgir algumas com maior valor de λz e também com formato espacial

arbitrário e não apenas circular.

Consideremos z1 e z2 duas zonas que possuem alguma interseção. Sejam n1 o número de

regiões de z1que não estão na interseção com z2, n2o número de regiões de z2que não estão na

interseção com z1 e n = n1+ n2. Suponha que desejamos fazer z1 voar em direção a z2. Esse

procedimento é feito removendo regiões de z1e acrescentando regiões de z2. Então, cada região

removida de z1 ou acrescentada de z2 representa (1/n) × 100% do total de “passos” possíveis

para se completar o caminho de z1 para z2. Assim, se por exemplo quiséssemos fazer z1 voar

100% em direção a z2, teríamos que remover todas as n1 regiões de z1 e acrescentar todas as

n2 regiões de z2, obtendo ao fim uma cópia exata da zona z2. Porém, para que o processo de

remoção e adição de regiões não gere zonas desconexas, essas operações devem ser feitas numa ordem que respeite a conectividade da zona.

Para ilustrar esse procedimento, vamos analisar a Figura 2.4 começando da esquerda para direita e de cima para baixo. No Gráfico A temos a zona z1, em amarelo, composta por 7 regiões,

e no Gráfico B temos a zona z2, em azul, composta por 9 regiões. No Gráfico C temos z1 e z2

sobrepostos e as regiões que representam a interseção estão na cor verde. Ainda em relação ao Gráfico C, é possível perceber que n1=4, n2=6 e, consequentemente, n=10. Assim cada região

removida de z1ou acrescentada de z2 representa 10% de caminhada de z1 em direção a z2.

Para fazermos z1 voar em direção a z2, a primeira coisa que devemos fazer é atribuir níveis

para as regiões que fazem parte da interseção, para as regiões que fazem parte apenas de z1 e

para as regiões que fazem parte apenas de z2. Esses níveis serão atribuídos da seguinte maneira:

as regiões da interseção recebem nível 0; as regiões que fazem parte apenas de z1 recebem os

níveis de forma crescente de 1 até n1; e as regiões que fazem parte apenas de z2 recebem os

níveis de forma crescente de -n2 até -1.

A região de z1 que irá receber o nível 1 deve ser alguma região que faz fronteira com (isto é,

é vizinha a) alguma região que recebeu nível 0. Percebemos que três regiões de z1 são vizinhas

das regiões com nível 0, então cada uma delas tem probabilidade 1/3 de receber o nível 1. Para uma região receber o nível 2, iremos verificar quais são as regiões vizinhas das regiões com nível 0 ou 1, e cada uma dessas regiões poderá receber o nível 2 com mesma probabilidade. Esse processo é repetido até que todas as regiões de z1 tenham recebido um nível. Os níveis de

z2 são atribuídos analogamente aos níveis de z1. Utilizamos níveis negativos apenas para evitar

a confunsão com os níveis de z1. As regiões com seus respectivos níveis atribuídos estão no

Gráfico D.

Uma vez que todas regiões receberam os níveis adequadamente, iremos adicionar e retirar regiões de z1até que se tenha atingido a proporção p desejada. Como vimos n=10, então cada

corrido alternando-se entre a remoção da região de maior nível presente na solução corrente (regiões amarelas e verdes) e a adição da região de menor (mais negativo) nível que ainda não está presente na solução corrente (regiões azuis), enquanto houver níveis positivos e negativos. Caso os níveis positivos acabem, os passos seguintes são dados somente acrescentando as re- giões com níveis negativos, e caso os níveis negativos acabem, os passos seguintes são dados apenas pela remoção das regiões com nível positivo.

Observando o Gráfico E da Figura 2.4, retiramos a região de maior nível (4) de z1, o que

representa 10% do caminho. No Gráfico F acrescentamos a região de menor nível (-6) de z2,

o que representa mais 10%. Depois repetimos esse processo de retirar de z1 e acrescentar de

z2 até que se tenha atingido a proporção desejada. Por exemplo, se p = 80% a zona resultante

seria a observada no Gráfico L, formada pelas regiões de cor verde. A remoção de regiões de z1

do maior para o menor nível, e a adição de regiões de z2 do nível mais negativo para o menos

negativo garantem a conectividade das soluções geradas, uma vez que a atribuição dos níveis é feita considerando-se as vizinhanças.

Figura 2.4: Zona voando em direção a outra.

Após todas as zonas caminharem em direção aos seus pivôs, algumas delas podem sofrer mutação. Isso é feito com o intuito de introduzir maior aleatoriedade ao processo, o que deve evitar a convergência precoce do algoritmo para máximos locais.