• Bases biológicas
• Darwinismo
• Seleção Natural
• Precursores
• O QUE são?
• Parâmetros
• Estrut./Componentes
• Métodos/Critérios
• Quando podemos usar?
• Amostragem
• Operadores genéticos
• Problemas
• Representação/Codificação
• Avaliação/Aptidão
• Análise Teórica dos AG's
• Algoritmos Genéticos Paralelos
• Terminologia Biológica
• Bibliografia

	Os indivíduos de uma mesma espécie mostram muitas variações na forma e na fisiologia;
	Boa parte dessas variações é transmitida aos descendentes;
	Se todos os indivíduos de uma espécie se reproduzissem, as populações cresceriam exponencialmente;
	Como os recursos naturais são limitados, os indivíduos de uma população lutam por sua sobrevivência e de sua prole;
	Portanto, somente alguns (os mais aptos), sobrevivem e deixam descendentes. A sobrevivência e a reprodução diferencial dependem das características desses indivíduos que, por serem hereditárias, serão transmitidas aos seus filhos;
	Através dessa seleção natural, as espécies serão representadas por indivíduos cada vez mais adaptados.

Evolução;

Seleção natural;

Reprodução;

Ausência de memória.

	Apresentam-se como o paradigma mais completo da CE visto que englobam de forma simples e natural todos os conceitos nela contidos;
	Apresentam resultados bastante aceitáveis, com relação à precisão e recursos empregados (fáceis de implantar em computadores domésticos de porte médio), para uma ampla gama de problemas de difícil resolução por outros métodos;
	São muito flexíveis, aceitam sem grandes dificuldades uma infinidade de alterações na sua implementação e permitem fácil hibridação (vantagem importante no caso de aprendizagem) inclusive com técnicas não relacionadas à CE;
	Em relação aos outros paradigmas da CE, são os que exigem menor conhecimento específico do problema em questão para o seu funcionamento , o que os torna altamente versáteis e, além disso, agregam conhecimento específico com pouco esforço;
	São o paradigma mais usado dentro da CE e, junto com as Redes Neurais, os mais usados de toda a Computação Natural.

Na prática, nós podemos implementar facilmente um AG com o simples uso de strings de bits ou caracteres para representar os cromossomos e, com simples operações de manipulação de bits podemos implementar cruzamento, mutação e outros operadores genéticos. Na figura 1, podemos ver a simplicidade de representação de um cromossomo composto por dez genes, por meio de uma string de valores binários.

Figura 2 – Pseudocódigo básico de um Algoritmo Genético

	Cega: não tem conhecimento específico do problema a ser resolvido, tendo como guia apenas a função objetivo;
	Codificada: não trabalham diretamente com o domínio do problema e sim com representações dos seus elementos;
	Múltipla: executa busca simultânea em um conjunto de candidatos;
	Estocástica: aleatória. Combinam em proporção variável regras probabilísticas e determinísticas. Esse conceito refere tanto as fases de seleção como as de transformação.

Tamanho da População: O tamanho da população determina o número de cromossomos na população, afetando diretamente o desempenho global e a eficiência dos AG’s. Com uma população pequena o desempenho pode cair, pois deste modo a população fornece uma pequena cobertura do espaço de busca do problema. Uma grande população geralmente fornece uma cobertura representativa do domínio do problema, além de prevenir convergências prematuras para soluções locais ao invés de globais. No entanto, para se trabalhar com grandes populações, são necessários maiores recursos computacionais, ou que o algoritmo trabalhe por um período de tempo muito maior.

Taxa de Cruzamento: Quanto maior for esta taxa, mais rapidamente novas estruturas serão introduzidas na população. Mas se esta for muito alta, a maior parte da população será substituída, e pode ocorrer perda de estruturas de alta aptidão. Com um valor baixo, o algoritmo pode tornar-se muito lento.

Tipo de Cruzamento: O tipo de cruzamento a ser utilizado determina a forma como se procederá a troca de segmentos de informação entre os "casais" de cromossomos selecionados para cruzamento. Mais adiante serão explanados alguns tipos de cruzamento utilizados mas, deve-se levar em conta que existem muitas outras escolhas disponíveis para usuários de AG’s. O ideal, seria testar diversos tipos de cruzamento em conjunto com as outras configurações do AG em uso para verificar qual apresenta um melhor resultado.

Taxa de Mutação: Determina a probabilidade em que uma mutação ocorrerá. Mutação é utilizada para dar nova informação para a população e também para prevenir que a população se sature com cromossomos semelhantes (Convergência Prematura). Uma baixa taxa de mutação previne que uma dada posição fique estagnada em um valor, além de possibilitar que se chegue em qualquer ponto do espaço de busca. Com uma taxa muito alta a busca se torna essencialmente aleatória além de aumentar muito a possibilidade de que uma boa solução seja destruída. A melhor Taxa de Mutação é dependente da aplicação mas, para a maioria dos casos é entre 0,001 e 0,1.

ESTRUTURA E COMPONENTES BÁSICOS

Como não há uma definição rigorosa para "Algoritmo Genético" a qual seja aceita por todos os componentes da comunidade da computação evolucionária, podemos dizer que a maioria dos métodos denominados "AG’s" têm pelo menos os seguintes elementos em comum:

Uma população de cromossomos;

Seleção de acordo com a aptidão;

Cruzamento (crossover) para gerar novas populações;

Mutação aleatória para produzir novos indivíduos.

Para implantar um AG, necessita-se definir de forma correta os seguintes métodos e critérios [SER96]:

Critério de codificação: tendo em vista que os AG’s trabalham com manipulação de strings de determinados alfabetos (representação), deve-se especificar a codificação com a qual se faz corresponder cada ponto do domínio do problema com um Gene ou conjunto de Genes do Cromossomo.

Critério de tratamento dos indivíduos não factíveis: nem sempre é possível estabelecer uma correspondência ponto-a-ponto entre o domínio do problema e o conjunto de strings binárias (ou de outro alfabeto utilizado) usadas para resolvê-lo. Como conseqüência, nem todas as strings (indivíduos) codificam indivíduos válidos do espaço de busca e devem ser habilitados procedimentos úteis para distingui-las.

Critério de inicialização: refere-se a como deve ser construída a população inicial com a qual se inicializará o AG.

Critério de parada: devem ser determinadas as condições nas quais se considera que o AG encontrou uma solução aceitável ou tenha fracassado no processo de busca e não faça sentido continuar.

Funções de avaliação e aptidão: deve ser determinada a função de avaliação mais apropriada para o problema, assim como a função de aptidão que utilizará o AG para resolvê-lo.

Operadores Genéticos: denominação dada aos operadores utilizados para levar a cabo a reprodução. Todo AG faz uso de pelo menos três Operadores Genéticos (levando em conta o AG básico): seleção, cruzamento e mutação. Fique claro que estes não são os únicos possíveis e além de tudo admitem variações.

Critérios de Seleção: a seleção deve dirigir o processo de busca em favor dos indivíduos mais aptos. Isto pode ser feito de varias maneiras como, por exemplo, por amostragem direta, por amostragem aleatória simples ou por amostragem estocástica, como poderá ser visto mais adiante.

Critério de Substituição: os critérios com que se selecionam os criadores não necessariamente têm que ser os mesmos usados para selecionar os sobreviventes, logo a necessidade de especificá-los separadamente. Alguns exemplos são:

Substituição Imediata: os s descendentes substituem seus progenitores

Substituição por fator cheio: os s descendentes substituem aqueles membros da população mais parecidos com eles

Substituição por inserção: são selecionados para serem eliminados s membros da população de criadores (geralmente os s piores), os quais serão substituídos pelos descendentes.

Substituição por Inclusão: os s descendentes são somados aos n progenitores em uma única população e nesta, são selecionados os n melhores.

Parâmetros de Funcionamento: um AG precisa que lhe proporcionem certos parâmetros de funcionamento (tamanho da população, probabilidades de aplicação dos Operadores Genéticos, precisão da codificação, ...)

Em geral, os AG’s têm sido mais usados para solução de funções de otimização, nas quais eles têm se mostrado bastante eficientes e confiáveis. Mas, como é de se esperar, nem todos os problemas podem ter resultados satisfatórios ou mesmo ser representados adequadamente para o uso de técnicas de AG. A recomendação geral é levar em conta as seguintes características relativas ao problema, antes de tentar o uso das referidas técnicas [GOL89]:

Amostragem direta: seleção de um subconjunto de indivíduos da população mediante um critério fixo, no estilo de "os n melhores", "os n piores", "a dedo", etc...

Amostragem aleatória simples ou equiprovável: é determinada a mesma probabilidade para todos os elementos da população, de serem selecionados para a amostra.

Amostragem estocástica: são atribuídas probabilidades de seleção ou pontuações aos elementos da população com base na sua função de aptidão (fitness).

Por sorteio: as pontuações são consideradas estritamente como probabilidades de seleção para formar a amostra, a qual é constituída realizando n ensaios de uma variável aleatória com dita distribuição de probabilidades. Para ilustrar, levemos em conta a existência de uma população de 4 indivíduos , e digamos que o resultado da função de aptidão de cada indivíduo seja, respectivamente , , , .

Os passos seguintes seriam:

1) Calcular as pontuações acumuladas da seguinte forma:

2) Gerar um número aleatório simples , o qual a termo de exemplo consideraremos .

3) Por meio do número gerado aleatoriamente, eleger o indivíduo que se encaixe na regra:

No nosso exemplo, o indivíduo selecionado seria o , pois:

ou seja,

Para realizar a amostragem por sorteio de indivíduos, devemos apenas modificar os últimos dois passos da seguinte forma:

2) Gerar números aleatórios simples .

3) Para cada se escolhe o indivíduo que verifique

Por restos: a cada indivíduo é atribuído diretamente locais na amostra. Freqüentemente os indivíduos repartem os locais vagos em função das suas pontuações. A distribuição costuma ser por sorteio (ver item anterior) e então se diz "amostragem estocástica por restos". Continuando com o exemplo proposto, a é atribuído um local na amostra; o indivíduo que ocupará o outro local é selecionado por sorteio, pela geração de um número aleatório simples e se compara o seu valor com as pontuações acumuladas , seguindo a mesma regra anterior ().

 

Universal ou por roleta: inicialmente proposto por Goldberg [GOL89]. É um método bastante simples que consiste em criar uma roleta na qual cada cromossomo possui um segmento proporcional à sua aptidão. Suponhamos uma população de 6 cromossomos cuja aptidão é dada por uma função qualquer (neste caso é simplesmente a conversão de binário para decimal) conforme mostrado na tabela 1.

Tabela 1 – Valores de exemplo para ilustrar seleção por roleta.

Cromossomo nº	String	Aptidão	% do total
1	0101101	45	13,2
2	1011001	89	26,2
3	1111101	125	36,7
4	0010101	21	6,1
5	0110100	52	15,2
6	0001001	9	2,6
	Total	341	100,0

 

Com os valores percentuais constantes na quarta coluna da tabela 1, iremos elaborar a roleta constante da figura 4. Esta roleta irá ser girada 6 vezes para efetuar a seleção da população auxiliar (amostra) levando em conta que, os indivíduos com maior área na roleta tem, consequentemente, maiores chances de serem selecionados mais vezes que os indivíduos menos aptos.



Figura 4 – Representação gráfica da roleta.

 

Por torneio: o processo usado neste método é extremamente simples. Cada elemento da amostra e selecionado elegendo o melhor indivíduo de um conjunto de elementos tomados aleatoriamente na população base; isto é repetido o número de vezes necessárias para completar a amostra. O valor do parâmetro costuma ser um valor inteiro pequeno em relação ao tamanho total da população base, sendo em geral 2 ou 3.

OPERADORES GENÉTICOS

Seleção:

A idéia principal do operador de seleção em um algoritmo genético, é oferecer aos melhores indivíduos da população corrente, preferência para o processo de reprodução, permitindo que estes indivíduos possam passar as suas características às próximas gerações. Isto funciona como na natureza, onde os indivíduos altamente adaptados ao seu ambiente possuem naturalmente mais oportunidades para reproduzir do que aqueles indivíduos considerados mais fracos [SCH98].

Cruzamento:

Um ponto de cruzamento (single-point crossover): o ponto de quebra do cromossomo é escolhido de forma aleatória sobre a longitude da string que o representa, e é a partir desse ponto que se realiza a troca de material cromossômico entre os dois indivíduos, como é representado na figura 5, na qual a termo de representação foi escolhido o ponto de cruzamento 4.

Dois pontos de cruzamento (two-point crossover): procede-se de maneira similar ao cruzamento de um ponto, mas a troca de segmentos do gene ocorre como mostrado na figura 6, na qual a termo de representação foram escolhidos os pontos 2 e 6:

Cruzamento Uniforme (uniform crossover): É radicalmente diferente do cruzamento de um ponto. Cada gene do descendente é criado copiando o gene correspondente de um dos pais, escolhido de acordo com uma máscara de cruzamento gerada aleatoriamente. Onde houver 1 na máscara de cruzamento, o gene correspondente será copiado do primeiro pai e, onde houver 0 será copiado do segundo. O processo é repetido com os pais trocados para produzir o segundo descendente. Uma nova máscara de cruzamento é criada para cada par de pais. O número de pontos de troca de informação não é fixo mas em geral é usado (onde é o comprimento do cromossomo). A figura 7 demonstra graficamente o processo.

Mutação:

onde representa o bit, do indivíduo, que está sendo avaliado para mutação e é um número aleatório () atribuído a ele para comparação com a taxa de mutação . Dessa forma, aplicando a regra acima, será obtida a inversão de bit (no caso de indivíduos compostos por strings binárias) sempre que o valor de atribuído a for menor ou igual a ; caso contrário o bit permanecerá inalterado.

O PROBLEMA DA DIVERSIDADE NOS AG’S

Convergência e Elitismo

1 - Se seleciona uma elite de membros entre os melhores da população inicial, os quais serão incorporados diretamente à população final, sem passar pela população auxiliar.

2 - A população auxiliar é selecionada entre os

Pressão Seletiva

Deve ser utilizado um alfabeto o mais pequeno possível para representar os parâmetros; normalmente utilizam-se dígitos binários;

As variáveis que representam os parâmetros do problema devem ser discretizadas para poder representar as strings de bits;

A maior parte dos problemas tratados com AG's são não lineares e muitas vezes existem relações "ocultas" entre as variáveis que formam a solução;

O tratamento dos genótipos inválidos deve ser tomado em conta para o desenho da codificação.

ANALISE TEÓRICA DOS AG's

Até o momento foi explanado como funcionam os Algoritmos Genéticos, o que, visto de uma forma superficial, leva a pensar que os AG's processam apenas indivíduos, ou seja, elementos codificados de um conjunto de possíveis soluções para determinado problema.

Se esse fosse o caso, não teria grande sentido a utilização da codificação binária pois o AG deveria funcionar com a mesma eficiência com números de ponto flutuante que representassem diretamente as possíveis soluções, tendo apenas que modificar levemente os operadores genéticos. Implementando tal idéia na solução de um problema [RIO92], pode-se notar que o AG resultante também converge, mas de forma muito mais lenta, não sendo mais eficiente que outros métodos de busca cega.

O motivo disto é que os AG's não processam unicamente indivíduos, e sim padrões de semelhança entre ditos indivíduos e, tendo em vista que cada indivíduo pode conter muitos padrões simultaneamente, a eficiência da busca se multiplica.

Nesta parte do trabalho, será explicado "porquê" os AG's funcionam, dando o devido embasamento teórico para tal explicação.

Definições e Conceitos Básicos

Holland não foi apenas pioneiro no uso dos AG’s. Ele também propôs a primeira explicação de como os Algoritmos Genéticos trabalham mediante o teorema dos Esquemas [HOL75]. A fundamentação teórica dos AG’s é geralmente representada em termos de ditos Esquemas, os quais são conjuntos de cromossomos que partilham certas semelhanças na sua composição.

Um Esquema é um padrão de semelhança nas strings que compões os cromossomos de um AG, o qual é implementado incluindo mais um símbolo, o “*”, representando indiferença, no alfabeto utilizado para representação. Desta forma, para codificação binária, o alfabeto passa a ser {0, 1, *}, onde * representa qualquer um dos valores possíveis.

Por exemplo, o Esquema (*10*0011) representa estes quatro cromossomos:

Desta forma, os Esquemas permitem descrever sinteticamente configurações de strings que apresentem características interessantes para a resolução de um determinado problema. Naturalmente o Esquema (10011001) representa apenas um cromossomo (não possui o símbolo *), enquanto que o esquema (********) representa todos os cromossomos de comprimento =8.

Deve-se sempre levar em conta que o * é usado apenas na análise do AG, ou seja, o AG não processa Esquemas. Para podermos formalizar , devemos levar em conta, quanto aos cromossomos compostos por strings binárias, o que segue:

Com isto definido, podemos então definir a notação utilizada para permitir a representação dos Esquemas:

Formalizando

Tendo em foco as noções básicas apresentadas no item anterior, pode-se então verificar as seguintes propriedades relativas aos Esquemas [SER96]:

	Se um Esquema contém k símbolos de indiferença (*) então representa a 2strings binárias;
	Uma string binária de comprimento se encaixa em 2 Esquemas diferentes;
	Considerando as strings binárias de comprimento exitem no total 3 possíveis Esquemas;
	Uma população de n cromossomos de comprimento contém entre 2 e n.2 esquemas diferentes.

Dadas tais propriedades, é conveniente definir dois conceitos de grande importância para um dado Esquema H:

	Ordem de um Esquema, o(H): número de valores fixos na representação de um esquema. Por exemplo: 10*110* é de ordem 5 -----» o(10*110*)=5 0****** é de ordem 1 -----» o(0******)=1
	Comprimento definidor de um Esquema, d(H): distância em dígitos entre o primeiro e o último valor fixo na representação do Esquema. Por exemplo: 10*110* tem d(H) 5 -----» d(10*110*) = (6-1) = 5 0****** tem d(H) 0 -----» d(0******) = (1-1) = 0

Dado que um Esquema H representa 2 cromossomos, quanto maior seja a ordem do Esquema, menos indivíduos ele representará. Devemos notar que um esquema com uma única posição especificada possui uma longitude característica de 0. Logo, pode-se calcular a probabilidade de sobrevivência de um esquema em relação aos cruzamentos. Por exemplo, o esquema S = (****00**1*) possui ordem o(S)=3 e uma longitude característica (S) =9-5=4.

A aptidão média da população no instante t, AveFitness(P[t]), é a média das aptidões de todas as strings da população no instante t, ou em equivalência, a aptidão do esquema (* . . . *) em P[t]:

A aptidão relativa de S em P[t]:

Por fim, sendo Pxov e Pmut as probabilidades de cruzamento e mutação de um AGS respectivamente, a presença de certo esquema S na população P[t] evolui em média de acordo com a equação[CR]:

Assumindo para tal que, como acontece geralmente, Pmut <1.

Teorema Fundamental dos Algoritmos Genéticos

Tendo como base os resultados anteriores, podemos proceder o enunciado do seguinte teorema:

"Nas sucessivas gerações de um AGS, a presença de um esquema S na população P[t] evolui estatisticamente de modo exponencial de acordo com a equação [CR]."

ALGORITMOS GENÉTICOS PARALELOS

Paralelismo nos Algoritmos Genéticos

Os AG´s são habitualmente considerados algoritmos implicitamente paralelos, sendo esta característica um dos seus pontos fortes. Atualmente existe uma procura cada vez maior por algoritmos que, além de resolver os problemas de forma aceitável, também os resolvam de um modo que seja paralelizável, pois cada vez mais a tendência está voltada para a utilização de sistemas paralelos. Os AG possuem uma estrutura computacional altamente paralelizável. Assim, se analisarmos a estrutura de um AG chegamos às seguintes conclusões:

	Cada cromossomo da população tem uma qualidade Q, que pode ser avaliada independentemente de qualquer outro fator.
	Cada operador e operação genética é independente, pelo que podem ser aplicado em qualquer ordem, seqüencial ou não, a qualquer elemento da população.

Observando mais uma vez a Natureza, chegamos à conclusão que nela todos os processos são paralelos, ou seja, os processos seqüenciais é que não são naturais. Basta imaginarmos que neste momento, em qualquer parte do mundo, existem crianças nascendo, lutas pela sobrevivência, pessoas morrendo, e muitas outras atividades, sem que exista um ponto comum de controle. Podemos interferir diretamente ou não no que se passa, mas não existe ninguém com um conhecimento global do estado atual do mundo e acima de tudo ninguém consegue interferir ou controlar tudo o que acontece.

Modelos de Algoritmos Genéticos Paralelos

Uma das áreas de maior investigação nos AGs tem sido sobre o modo como podem ser efetivamente paralelizados, tendo surgido desse esforço um grande conjunto de possíveis implementações. O que todas estas diferentes implementações têm demonstrado é que o que é importante não é apenas o algoritmo em si, mas sim o conjunto do algoritmo, os problemas para que vai ser utilizado, a sua parametrização e o equipamento que vai servir de base à execução do AG.

Embora estes já fossem fatores essenciais nos algoritmos seqüenciais, o que se veio a notar é que surgiram muitos algoritmos que eram bons em determinadas situações, piores em outras e com pequenas variações de parâmetros e/ou nos problemas tudo se poderia inverter. Foram ainda acrescentados mais fatores a um problema que já não era simples. Assim, poderíamos ter um excelente algoritmo para executar num conjunto de transputers, que se fosse executado numa rede de workstations já não seria tão bom, ou vice-versa, mas dependendo também da parametrização e do problema.

O primeiro modelo que vai ser descrito, é a evolução natural do modelo seqüencial, que embora não seja dos mais eficientes, tem algumas vantagens em algumas utilizações especiais. Serão ainda apresentados dois outros modelos, que ao longo dos últimos anos se têm mostrado especialmente eficazes, que são o modelo Ilha e o modelo da Vizinhança, tendo cada um deles os seus pontos fortes.

Um fator bastante interessante nos AG paralelos, é que é possível que as soluções paralelas sejam, não apenas obtidas mais rapidamente, mas também tenham normalmente uma melhor qualidade que as soluções seqüenciais.

Modelo de Farming

Este modelo (chamado de Farming devido à analogia com uma fazenda em que existem várias tarefas para fazer e várias pessoas paras executá-las, controladas por um capataz), segue uma estrutura do tipo Mestre-Escravos, e é uma evolução quase natural do AG seqüencial. Assim, neste modelo temos um processo Mestre, que supervisiona a população e faz a seleção dos cromossomos em que se vai atuar. A partir da altura em que é feita a seleção, entrega o trabalho a um dos N processos Escravos, que executarão os operadores genéticos, avaliarão os cromossomos gerados e depois devolvem os cromossomos ao processo Mestre, enquanto este já entregou mais trabalho a outros Escravos.

Tem o inconveniente de ser necessário centralizar a seleção, e obrigar a comunicar os parâmetros para os Escravos atuarem e depois os resultados para o Mestre. No entanto, em sistemas que esta comunicação seja feita muito rapidamente, como em sistemas de memória partilhada, é uma solução bastante aceitável. Tem ainda problemas de escalabilidade, pelo que o seu uso obriga a calcular com rigor a quantidade de processos Escravos que será razoável ter, de modo que o processo Mestre possa funcionar sem sobrecarga.

Modelo Ilha

Observação de ambientes naturais isolados, como as ilhas, têm demonstrado que algumas das espécies que surgem são especialmente adaptadas às particularidades dos seus ambientes, em contraste com Populações equivalentes mas em ambientes mais abertos, em que todos os membros têm acesso a todos os outros membros.

Estas observações levaram ao surgimento de novas arquiteturas e operadores que melhoravam os AGs paralelos para além do ganho puro de performance, que em conjunto com as considerações relativas à possibilidade de varias populações concorrentes poderem gerar uma melhor solução do que a conseguida com apenas uma população, levaram à construção de um modelo que aproveita ambas as vantagens. Aproveita os ganhos de fiabilidade na obtenção de soluções com a melhor qualidade das soluções.

Este modelo é o chamado modelo Ilha, devido à fonte inspiradora do conceito. Assim, o algoritmo seqüencial fica dividido numa série de Ilhas (populações), que comunicam entre si as melhores soluções. No resto do tempo, estão trabalhando para melhorar as soluções internas da ilha. Este modelo, entretanto, mantém a estrutura seqüencial do AG, apenas sendo adicionados os operadores para fazer a migração dos elementos entre as diferentes ilhas, não existindo um verdadeiro paralelismo no algoritmo.

Modelo da Vizinhança (Difusão)

Consiste em dividir todo o AG, de modo a conseguir levar mais longe o paralelismo. Para tal, é feita a mesma divisão da população pelos vários processadores, mas em vez de usar o conceito de ilha para se fazer a migração, estabelece-se uma vizinhança com a qual é feito o normal processo de seleção e reprodução.

Este é o modelo da Vizinhança (East [EAS93], M. Gorges-Schleuter [SCL90]), também conhecido por modelo de Difusão, pois os bons cromossomos vão-se difundindo gradualmente pelos vários processadores. Como exemplo, se tivermos uma população de 100 elementos, podemos imaginar uma grade de 10x10 e dizer que cada uma das células tem uma vizinhança, a qual por questões de velocidade, seria composta pelos elementos imediatamente à sua volta na arquitetura usada. Esta vizinhança vai ser usada para selecionar quais dos cromossomos vão ser usados para gerar o novo cromossomo.

Depois é necessário substituir o cromossomo atual pelo cromossomo que acabou de se gerar. Esta fase de substituição é bastante crítica, pois se o elemento for substituído por um elemento com pior qualidade o algoritmo sai muito afetado.

Este algoritmo, tal como o modelo Ilha, também pode ser visto na Natureza, pois é uma aproximação daquilo que acontece quando aumentamos o tamanho de uma Ilha. Imagine que a evolução dos animais numa ilha é relativamente independente da evolução dos animais nas ilhas vizinhas, sendo ocasionalmente feita a emigração de alguns animais. Como vimos, este modelo funciona bem, e tem a vantagem de em cada Ilha poderem aparecer animais mais adaptados à ilha em questão. Agora, suponha que em vez de uma ilha pequena, em que cada elemento da população pode comunicar com qualquer outro, passamos para uma situação em que a ilha é tão grande que se torna impossível a comunicação entre todos os elementos da população. Aí o que aparece é a criação de nichos de população, como as aldeias, em que cada elemento tem maior probabilidade de encontrar o seu par na sua aldeia, mas uma probabilidade menor de encontrá-lo numa aldeia próxima e uma probabilidade ainda menor de encontrar o par numa aldeia longínqua.

Este modelo além de ter as mesmas vantagens do modelo da Ilha, tem também a seu favor o fato de ser massivamente paralelizável, pois as operações a nível de cada célula são muito simples, além de que não é necessária comunicação a grandes distâncias. Embora este seja o modelo que parece ter mais facilidade de escalar para grande número de processadores, tem no entanto o problema de ser de grão muito fino. Em cada processador apenas fica um cromossomo, sendo os cromossomos vizinhos transmitidos para o processador atual para a seleção e reprodução. Caso se opte por passar este modelo para um grão médio, acumulando vários cromossomos em cada processador, podemos optar por fazer o escalonamento de vários processos por processador, cada um atendendo a um cromossomo ou podemos elaborar um algoritmo seqüencial em cada nodo, que atenda a cada um dos pontos da grade que controla.

Toda a estrutura deste algoritmo assenta num grande grau de comunicação entre as várias partes da população, quer seja com um cromossomo por processador quer sejam vários cromossomos por processador. No caso de estar sendo utilizado um sistema cujas comunicações sejam muito rápidas, este modelo obtém performances equivalentes ao modelo da ilha. No entanto, não é adequado a sistemas com comunicações mais lentas, como através de uma rede Ethernet.

TERMINOLOGIA BIOLÓGICA

Nesta parte do texto, será traçado um breve paralelo entre a terminologia biologica (BIO) - [ABE70], [EVO98] - e a terminologia da Computação Evolutiva (CE) - [SCH98], [EVO98] - dos principais termos empregados neste trabalho, visando auxiliar no entendimento dos conceitos aplicados: ·

	(BIO) ADAPTABILIDADE: Toda característica de um organismo vivo que aumenta as possibilidades de sobrevivência e de deixar descendência no meio em que habita. Também proporcional ao tempo esperado para extinção. "Os adaptados são aqueles que se ajustaram ao Ambiente existente ao seu redor e cujos descendentes se ajustarão a ambientes futuros." (J. Thoday, - UM Século de Darwin, 1959). (CE) Qualquer alteração na estrutura de um cromossomo (string de caracteres de certo alfabeto) que melhore sua capacidade de resolver determinado problema, permitindo-lhe maiores chances de sobrevivência e reprodução. ·
	(BIO) AJUSTE : Medida que indica o grau de aptidão de um indivíduo ao meio ambiente. (CE) Valor de Adaptabilidade ou Fitness. Valor relativo a avaliação da Função Objetivo de uma solução. Também chamada de função de Avaliação ou Função Objetivo em problemas de otimização. ·
	(BIO) ALELOS : Se diz que dois ou mais GENES são ALELOS (entre si) ou ALELOMORFOS (um em relação ao outro), quando: 1. Ocupam a mesma posição relativa (LOCUS) em CROMOSSOMOS HOMÓLOGOS e quando, na mesma célula se unem em pares durante a meiose; 2. Produzem efeitos diferentes no mesmo grupo de processos do desenvolvimento; 3. Podem mutar de um para o outro. (CE) Possíveis valores dos genes (no caso de representação binária 0 ou 1). ·
	(BIO) CROMOSSOMO : Corpo em forma de filamento, constituído principalmente por DNA e proteína, que se encontra em número variável no núcleo de todas as células animais e vegetais. Componente genético responsável pelo fenótipo do indivíduo. (CE) Um vetor ou string devidamente codificado, pertencente ao conjunto de possíveis soluções de um determinado problema. ·
	(BIO) DIPLOIDE: Diz-se do núcleo cujos cromossomos se apresentam aos pares, sendo homólogos (contém os mesmos GENES na mesma seqüência) os membros de cada par, de forma que há um número o dobro do número haploide. (CE) Em cada local do cromossomo existe um par de genes. Isto permite uma boa economia de memória. ·
	(BIO) ESPÉCIE : Grupo de indivíduos intercruzantes que são isolados reprodutivamente de outros grupos semelhantes, contendo fenótipos semelhantes. (CE) Indivíduos componentes de uma mesma população. ·
	(BIO) FENÓTIPO : Conjunto das características de um indivíduo observadas ou discerníveis por outros métodos, fornecidas pelo genótipo. (CE) Expressão física das estruturas. Conjunto decodificado de parâmetros. ·
	(BIO) GENES : Unidade de material hereditário. Unidade básica do cromossomo que define, de acordo com seu valor e posição, uma característica; um determinador hereditário que especifica uma função biológica; uma unidade de herança (DNA) localizada em um lugar fixo no cromossomo. (CE) Variáveis componentes da string que representa o cromossomo. ·
	(BIO) GENÓTIPO : Arranjo dos genes e cromossomos de um organismo correspondente a determinado fenótipo. (CE) Estruturas atuais. Cromossomos codificados. ·
	(BIO) HAPLOIDE: Célula que contém um único CROMOSSOMO ou conjunto de CROMOSSOMOS em vez de dois em cada núcleo, cada qual consistindo de uma única seqüência de GENES. Um exemplo é um GAMETA. (CE) Em lugar de um cromossomo existe um AG Modelo Ilha de um gene simples. ·
	(BIO) INDIVÍDUO : Um exemplar de uma espécie que interage com o meio ambiente. (CE) Mesmo que Cromossomo. ·
	(BIO) MUTAÇÃO : Variação devida a alguma alteração da constituição hereditária com aparecimento de uma nova variedade em qualquer espécie viva. (CE) Modificação aleatória do cromossomo visando gerar novas possíveis soluções à explorar. ·
	(BIO) POPULAÇÃO : Conjunto de indivíduos da mesma espécie; grupos inteiros de organismos de um tipo; um grupo intercruzante de animais ou vegetais; grupo amplo do qual pode-se tomar uma amostra. (CE) Conjunto de possíveis soluções. ·
	(BIO) REPRODUÇÃO : Multiplicação de novos indivíduos a partir de outros de mesma espécie. (CE) Cruzamento (crossover) vem a ser uma troca de segmentos dos cromossomos (strings) selecionados. ·
	(BIO) SELEÇÃO NATURAL : Mecanismo que garante aos indivíduos mais aptos, maiores chances de reprodução; fertilidade diferencial na natureza que favorece indivíduos que se adaptam melhor ao meio ambiente e tende a eliminar aqueles não adaptados. (CE) Determinada pela aptidão (fitness) do indivíduo. Quanto maior a sua aptidão, maiores as chances de gerar descendentes. Indivíduos com aptidões baixas representam soluções indesejáveis no momento da avaliação.

[RIO92] RIOLO, Rick L. Los Bits Mejor Dotados. Investigación y Ciencia, setembro de 1992.

[YEP99] YEPES, Igor. Algoritmo Genético com Idades para Controle de Braço Mecânico. Erechim/RS: URI - Universidade Regional Integrada, 1999.

[YEP00] YEPES, Igor. Algoritmos Genéticos Paralelos. Trabalho Individual - Porto Alegre/RS: UFRGS - Universidade Federal do Rio rande do Sul, 2000.

 Página Principal Noções Básicas Algoritmos Genéticos Redes Neurais Multiagentes
Cognição Software Artigos Tutoriais Links Quem sou eu