Análise de dados e compilado de informações sobre computação evolucionária

Análise de dados e compilado de informações sobre computação evolucionária - por Diego Itacolomy - Em construção

Proposta de problema

Elaboração de um Simulacro de vida simples utilizando Computação Evolucionária.

Conceito e objetivo

Nosso objetivo será a criação de algoritmos que simulem processos naturais de sobrevivência e reprodução de populações. Para isso teremos que levar em consideração, além dos conflitos externos, conflitos internos pela busca da sobrevivência, seja a busca de recursos como alimento, ou visando a reprodução. Os indivíduos mais aptos terão um maior número de descendentes, ao contrário dos indivíduos menos aptos.

Esperamos obter os seguintes fenômenos:

· Seleção Natural

· Deriva Genética

· Mutação

· Migração

· Adaptação

· Especiação

Hipóteses e desafios

Como representar as possíveis soluções;

Criação de um procedimento para criar soluções e verificar a qualidade das mesmas através dos resultados;

Criação de critérios de qualidade das soluções para permitir que seja possível a substituição das soluções com menos eficácia e a reutilização de soluções que se mostrem mais efetivas;

Garantir o mínimo de diversidade inicial para permitir que o algoritmo combine características e produza soluções;

Criação de um critério que permita a criação de soluções inovadoras;

Criação de um método para avaliação e comparação de aptidão de cada indivíduo;

Criação de operadores genéticos para os métodos de cruzamento e mutação;

Aplicação de técnicas para manter diversidade das populações;

Análise de dados

Uma maneira de executar a rotina de um programa de simulação de seleção natural, segundo Angeline P.J. seria com a seguinte estrutura básica: População > Avaliação de aptidão > Seleção > Cruzamento > Mutação > Critério de parada.

A população de um algoritmo genético é o conjunto de indivíduos que estão sendo cogitados como solução e que serão usados para criar o novo conjunto de indivíduos para análise (Angeline 1994)

Uma das principais formas é representar cada atributo como uma sequência de bits e o indivíduo como a concatenação das sequências de bits de todos os seus atributos. Outras variações de codificações binárias podem ser encontradas em (Holland 1975; Caruana 1988).

Métodos de Seleção

Seleção Proporcional (fitness-proportionate selection): Apresentada por John Holland (Holland 1975) para Algoritmos Genéticos, foi o método escolhido por John Koza no seu primeiro livro (Koza 1992). Usa a aptidão normalizada disposta em uma “roleta”, sendo que cada indivíduo da população ocupa uma “fatia” proporcional a sua aptidãonormalizada. Em seguida é produzido um número aleatório entre zero (0) e um (1). Este número representará a posição ocupada pela “agulha” da roleta. Apesar de seu grandesucesso devido a sua simplicidade, este método é muito afetado pela escalabilidade da aptidão normalizada (Blickle 1995).

Seleção por Torneio (tournament selection): Apresentada por David Goldberg (Goldberg 1991) para Algoritmos Genéticos, foi utilizada em vários problemas por John Koza no seu segundo livro (Koza 1994). A seleção por torneio é feita da seguinte forma: t indivíduos são escolhidos aleatoriamente da população e o melhor deles é o escolhido. Este processo é repetido até que se tenha uma nova população. O valor de t é conhecido como o tamanho do torneio.

Seleção por Truncamento (truncation selection): Com base em um valor de limiar(threshold) T entre zero (0) e um (1), a seleção é feita aleatoriamente entre os T melhores indivíduos (Muhlenbein 1993). Por exemplo, se T = 0.4, então a seleção éfeita entre os 40 % melhores indivíduos e os outros 60 % são descartados.

Seleção por Nivelamento Linear (linear ranking selection): Sugerido por Baker(Baker 1989) para eliminar as sérias desvantagens do uso de seleção proporcional. Para tal, os indivíduos são ordenados de acordo com os valores de fitness e o nível N é associado ao melhor indivíduo e o nível 1, ao pior. Em seguida, a cada indivíduo i é associada uma probabilidade pi de ser selecionado.

Seleção por Nivelamento Exponencial (exponential ranking selection): A seleção pornivelamento exponencial se diferencia do Nivelamento Linear apenas no fato dasprobabilidades pi serem exponencialmente ponderadas (Baker 1989). Um parâmetro c entre zero (0) e um (1) é usado como base. Quanto mais próximo de um, menor é a“exponencialidade” da seleção. Tal como no Nivelamento Linear, os indivíduos são ordenados de acordo com os valores de fitness e o nível N é associado ao melhor indivíduo e o nível 1, ao pior. Em seguida, a cada indivíduo i é associada uma probabilidade pi de ser selecionado.