5. Proglasiale innsjøsedimenter - resultat
5.6 Tolkning av BGP211
5.6.1 Generell tolkning av sedimentparameterne
Os parâmetros dos AG são grandezas que inĆuenciam muito no desempenho dos mes- mos. Os mais utilizados são: tamanho da população, o número de gerações, a proba- bilidade de cruzamento e a mutação. O número de parâmetros em um AG não é Ąxo, dependendo das escolhas especíĄcas de um dado projeto. No caso de a escolha do método de seleção ser o torneio é necessário informar também qual a quantidade ou percentagem de indivíduos que vão participar de cada torneio. Se a escolha for pelo método da roleta, não há a necessidade de se adicionar outro parâmetro (MICHALEWICZ, 1996).
3.3.6.1 Tamanho da população
O tamanho da população indica o número de indivíduos (cromossomos) em cada po- pulação e normalmente se mantém constante durante a evolução.
3.3.6.2 Número de gerações
Indica a quantidade de novas populações (novas gerações) que será gerada até que o algoritmo genético termine a execução.
Capítulo 3. Referencial teórico 43
3.3.6.3 Probabilidade de cruzamento
A probabilidade de cruzamento é uma grandeza percentual do número de indivíduos que realizam o cruzamento em relação ao número total de indivíduos escolhidos no pro- cesso de seleção.
3.3.6.4 Probabilidade de mutação
A probabilidade de mutação indica a quantidade de mutação em relação ao número total de indivíduos escolhidos no processo de seleção.
3.3.7 Algoritmos genéticos paralelos
Os Algoritmos Genéticos Paralelos (AGPs) são classiĄcados em 3 tipos básicos, sendo eles o modelo mestre escravo, o modelo granularidade Ąna também conhecido como modelo celular e o modelo granularidade grossa ou modelo de ilhas (LUQUE; ALBA, 2011). Além desses, existem modelos híbridos que são combinações desses modelos.
3.3.7.1 Modelo Mestre Escravo
O modelo Mestre Escravo (CHIPPERFIELD; FLEMING, 1996) apresentado na Figura 9 possui uma população única e global fornecendo a forma mais simples de paralelismo (SHENFIELD; FLEMING, 2014). Ela é controlada pelo processo mestre que a distribui para os escravos apenas a função de avaliar a aptidão dos indivíduos em paralelo. É muito comum essa implementação paralela de AGs por ser de fácil execuçução, pois a aptidão de um indivíduo não depende do restante da população. A comunicação ocorre somente nos momentos em que a população é enviada aos escravos e no retorno dos valores das aptidões calculadas ao mestre. Esse modelo é muito utilizado quando a função de avaliação da aptidão tem alto custo computacional, tornando o tempo de comunicação entre mestre e escravos insigniĄcante quando comparado com o tempo gasto na avaliação da aptidão (LUQUE; ALBA, 2011). Embora esse tipo de estratégia não explore todo o paralelismo inerente ao algoritmo evolucionário, melhorias substanciais no desempenho podem ser alcançadas.
Figura 9 Ű Paradigma de comunicação mestre escravo (CHIPPERFIELD; FLEMING,
3.3.7.2 Modelo de granularidade Ąna
O modelo de granularidade Ąna (LUQUE; ALBA, 2011) apresentado na Figura 10, possui população única e, espacialmente, estruturada formando um reticulado retangular de duas dimensões, em que existe um indivíduo por ponto do reticulado. Cada indivíduo está vinculado a um processador e a avaliação da aptidão dos indivíduos pode ser exe- cutada simultaneamente para todos eles. A seleção e o cruzamento são restritos a uma pequena vizinhança ao redor de cada indivíduo. As vizinhanças se sobrepõem e, even- tualmente, as características de um bom indivíduo podem se propagar pela população. Essa classe de AGPs também é chamada de modelo de difusão, porque a difusão de boas características através da população é análoga à difusão aleatória de partículas em alguns Ćuidos.
Figura 10 Ű Algoritmo evolucionário de granulação Ąna (LUQUE; ALBA, 2011).
3.3.7.3 Modelo de granularidade grossa
O modelo de granularidade grossa (LUQUE; ALBA, 2011) é apresentado na Figura 11. Esse modelo também é conhecido como modelo de Ilhas. Ele divide a população em subpopulações que executam em paralelo o algoritmo de um AG convencional com a adição opcional de rotinas que implementam a migração de indivíduos entre as populações locais (FOGARTY; HUANG, 1991). São modelos difíceis de se controlar devido a sua complexidade, pois cada um dos parâmetros a serem conĄgurados inĆuencia na eĄciência do algoritmo evolucionário. A divisão da população implica a deĄnição do número de subpopulações, o tamanho das subpopulações, a frequência da migração, o número de migrantes e destinação, os métodos de seleção dos migrantes e a forma como os que chegam são inseridos na população local. Esse modelo produz um grau de isolamento geográĄco na busca pela divisão da população acima em subpopulações e permite que cada uma
Capítulo 3. Referencial teórico 45
(a) Topologia de comunicação em anel. (b) Topologia de comunicação em estrela.
Figura 11 Ű Algoritmo evolucionário paralelo em ilhas (RIVERA, 2001).
evolua separadamente. Periodicamente, a migração ocorre para permitir um intercâmbio entre subpopulações (RIVERA, 2001). AGPs desse modelo também são conhecidos como Algoritmos Genéticos Distribuídos. A topologia da comunicação entre as subpopulações é parte da estratégia de migração dos AGPs e essa topologia é mapeada sobre alguma rede física (LUQUE; ALBA, 2011) podendo ser qualquer coisa, desde a topologia em anel mostrado na Figura 11a até uma topologia totalmente interligada em que a migração ocorra entre cada elemento da subpopulação, como mostrado na Figura 11b. Vários autores demonstraram que a utilização de múltiplas subpopulações interligadas por algum mecanismo de migração pode melhorar a convergência do algoritmo para uma variedade de problemas (GROSSO, 1985; STARKWEATHER; WHITLEY; MATHIAS, 1991).
Os valores para os parâmetros evolutivos aumentam a complexidade, pois cada parâ- metro inĆuencia na eĄciência do algoritmo e na qualidade da solução encontrada.
Frequência de migração: A troca de indivíduos entre subpopulações ocorre a inter-
valos de gerações deĄnidos ou com dada probabilidade para decidir a cada geração se a migração ocorre ou não.
Taxa de Migração: Esse parâmetro determina o número de indivíduos que participam
da migração. O valor desse parâmetro pode ser dado em valor absoluto ou em valor percentual do tamanho da população.
Seleção dos Migrantes: A forma como os indivíduos que emigram são selecionados
é deĄnida por esse parâmetro. Podem ser escolhidos os melhores ou a escolha pode ser aleatória.
Posicionamento dos Migrantes: Esse parâmetro deĄne como os indivíduos que mi-
gram são colocados na sua subpopulação de destino. Podem substituir os piores indivíduos ou os escolhidos de forma aleatória.
Figura 12 Ű Fluxograma para NSGA-II (DEB et al., 2002).
Topologia de Migração: Esse parâmetro deĄne a vizinhança de cada subpopulação,
ou seja, as sub-populações para as quais dada subpopulação pode enviar (ou receber) indivíduos. Cada subpopulação pode ter valores diferentes de parâmetros, caracterizando os chamados modelos heterogêneos.