Algoritmos Genéticos Capítulo 6

Algoritmos GenéticosAlgoritmos GenéticosCapítulo 6Capítulo 6

Prof. Ricardo LindenProf. Ricardo Linden

Algoritmos Genéticos - Capítulo 6Algoritmos Genéticos - Capítulo 6 22

Separando os OperadoresSeparando os Operadores

Até agora usamos somente um operador genético, o operador Até agora usamos somente um operador genético, o operador de crossover mais mutação de bit;de crossover mais mutação de bit;

A partir de agora dividiremo-lo em dois operadores separados A partir de agora dividiremo-lo em dois operadores separados (um para crossover e outro para mutação);(um para crossover e outro para mutação);

Separamos com o intuito de obter maior controle sobre a Separamos com o intuito de obter maior controle sobre a operação de cada um deles;operação de cada um deles;


Separando os OperadoresSeparando os Operadores

Separando:Separando: Podemos aumentar ou diminuir a incidência de cada um dos Podemos aumentar ou diminuir a incidência de cada um dos

operadores sobre nossa população;operadores sobre nossa população; Cada operador receberá uma avaliação;Cada operador receberá uma avaliação; Para decidir qual será aplicado a cada instante rodaremos uma roleta Para decidir qual será aplicado a cada instante rodaremos uma roleta

viciada;viciada; A seleção de indivíduos é feita depois da seleção do operador A seleção de indivíduos é feita depois da seleção do operador

genético a ser aplicado, visto que o operador de mutação requer genético a ser aplicado, visto que o operador de mutação requer somente um indivíduo enquanto que o de crossover requer dois; somente um indivíduo enquanto que o de crossover requer dois;

Normalmente o operador de crossover recebe uma probabilidade bem Normalmente o operador de crossover recebe uma probabilidade bem maior que o operador de mutação;maior que o operador de mutação;

Normalmente a probabilidade associada ao operador de mutação é Normalmente a probabilidade associada ao operador de mutação é igual a 100%-pc, onde pc é a probabilidade do operador de crossoverigual a 100%-pc, onde pc é a probabilidade do operador de crossover


Outros OperadoresOutros Operadores Existem vários outros tipos de operadores diferentes;Existem vários outros tipos de operadores diferentes;

Entre os de crossover, podemos incluir:Entre os de crossover, podemos incluir: Crossover de 2 pontos;Crossover de 2 pontos; Crossover Uniforme;Crossover Uniforme; Crossover de Maioria.Crossover de Maioria.

Vamos discutir cada um deles.Vamos discutir cada um deles.

Eles são necessários, pois:Eles são necessários, pois: Existem dezenas de esquemas que o crossover de 1 só ponto não consegue Existem dezenas de esquemas que o crossover de 1 só ponto não consegue

preservar, como por exemplo 1******1.preservar, como por exemplo 1******1. Se não mudarmos o nosso operador de crossover, nosso GA ficará limitado na Se não mudarmos o nosso operador de crossover, nosso GA ficará limitado na

sua capacidade de processar esquemassua capacidade de processar esquemas


Crossover de Dois PontosCrossover de Dois Pontos

Funcionamento:Funcionamento: Sortearmos dois pontos de corte;Sortearmos dois pontos de corte; O primeiro filho será então formado pela parte do primeiro pai fora dos O primeiro filho será então formado pela parte do primeiro pai fora dos

pontos de corte e pela parte do segundo pai entre os pontos de corte;pontos de corte e pela parte do segundo pai entre os pontos de corte; O segundo filho será formado pelas partes restantes.O segundo filho será formado pelas partes restantes.

Graficamente:Graficamente:


Exemplo: Exemplo: Suponha que temos dois pais de tamanho 10, dados respectivamente Suponha que temos dois pais de tamanho 10, dados respectivamente

pelas strings pelas strings 01010101010101010101 e e 11110000111111000011;; Sorteamos os pontos de corte 4 e 8;Sorteamos os pontos de corte 4 e 8; Primeiro filho será dado, então, por:Primeiro filho será dado, então, por:

a parte do primeiro pai até o ponto de corte 4 (a parte do primeiro pai até o ponto de corte 4 (01010101);); a parte do segundo pai entre o ponto de corte 4 e o ponto de corte a parte do segundo pai entre o ponto de corte 4 e o ponto de corte

8 (8 (00000000);); a parte do primeiro pai localizada após o ponto de corte 8 (a parte do primeiro pai localizada após o ponto de corte 8 (0101);); No final, o valor deste filho será No final, o valor deste filho será 01010000010101000001..

Crossover de Dois PontosCrossover de Dois Pontos


Crossover UniformeCrossover Uniforme

O número de esquemas que podem ser efetivamente O número de esquemas que podem ser efetivamente transferidos aos descendentes usando-se o crossover de dois transferidos aos descendentes usando-se o crossover de dois pontos aumenta de forma considerável;pontos aumenta de forma considerável;

Ele é ainda maior se usarmos o operador de crossover Ele é ainda maior se usarmos o operador de crossover uniforme.uniforme.



Para cada gene é sorteado um número zero ou um. Para cada gene é sorteado um número zero ou um. Se sorteamos um, primeiro filho recebe gene da posição Se sorteamos um, primeiro filho recebe gene da posição

corrente do primeiro pai e o outro, o do segundo pai. corrente do primeiro pai e o outro, o do segundo pai. Se o valor sorteado for zero, as atribuições serão invertidas.Se o valor sorteado for zero, as atribuições serão invertidas. Graficamente:Graficamente:



Este operador tende a conservar esquemas longos com a Este operador tende a conservar esquemas longos com a mesma probabilidade que preserva esquemas de menor mesma probabilidade que preserva esquemas de menor comprimento, desde que ambos tenham a mesma ordem.comprimento, desde que ambos tenham a mesma ordem.

Devido ao fato de fazer um sorteio para cada posição, este Devido ao fato de fazer um sorteio para cada posição, este crossover tem uma grande possibilidade de estragar todo e crossover tem uma grande possibilidade de estragar todo e qualquer esquema, mas em média o seu desempenho é qualquer esquema, mas em média o seu desempenho é superior à dos seus antecessores.superior à dos seus antecessores.


Crossover Baseado em MaioriaCrossover Baseado em Maioria

Não muito usado pois tende a fazer com que a convergência Não muito usado pois tende a fazer com que a convergência genética ocorra rapidamente.genética ocorra rapidamente.

Operação básica: Operação básica: sortear sortear nn pais pais cada bit do filho seja igual ao valor da maioria dos pais selecionados.cada bit do filho seja igual ao valor da maioria dos pais selecionados.



Crossover com mais de dois paisCrossover com mais de dois pais

Não existe nenhum tipo de restrição formal que obrigue que o número de Não existe nenhum tipo de restrição formal que obrigue que o número de pais participando de uma operação de crossover seja igual a dois;pais participando de uma operação de crossover seja igual a dois;

Podemos usar quantos pais quisermos, bastando adaptar o operador Podemos usar quantos pais quisermos, bastando adaptar o operador utilizado; utilizado;

Por exemplo, se quisermos usar o crossover uniforme, selecionar 0,1 ou Por exemplo, se quisermos usar o crossover uniforme, selecionar 0,1 ou 2, para fazer a seleção do pai;2, para fazer a seleção do pai;

Precisamos também de um segundo sorteio para determinar o pai que Precisamos também de um segundo sorteio para determinar o pai que mandará o indivíduo para o segundo filho. mandará o indivíduo para o segundo filho.

Pode-se extrapolar para o caso em que temos n pais, quando teremos Pode-se extrapolar para o caso em que temos n pais, quando teremos exatamente n-1 sorteios (o último filho é gerado com os “restos” não exatamente n-1 sorteios (o último filho é gerado com os “restos” não utilizados na composição de todos os seus irmãos)utilizados na composição de todos os seus irmãos)





Com Com nn pais, vetamos crossovers de pais, vetamos crossovers de kk pontos, onde pontos, onde kk<<n-1n-1. . Crossover de Crossover de kk pontos possui pontos possui k+1k+1 blocos para combinar; blocos para combinar; Se temos mais pais do que Se temos mais pais do que k+1k+1, alguns não participarão da , alguns não participarão da

composição dos filhos; composição dos filhos; Exemplo de uma operação possível para o crossover de 2 Exemplo de uma operação possível para o crossover de 2

pontos usando três pais pontos usando três pais



Operadores com Percentagens VariáveisOperadores com Percentagens Variáveis

Quando falávamos em dois operadores selecionados de forma separada, Quando falávamos em dois operadores selecionados de forma separada, atribuíamos a cada um deles uma percentagem fixa e rodávamos uma atribuíamos a cada um deles uma percentagem fixa e rodávamos uma roleta viciada de forma a escolher qual dos operadores seria aplicado roleta viciada de forma a escolher qual dos operadores seria aplicado sobre o indivíduo selecionado;sobre o indivíduo selecionado;

Não há uma probabilidade que seja adequada para os dois operadores Não há uma probabilidade que seja adequada para os dois operadores durante toda a execução do algoritmo;durante toda a execução do algoritmo;

No início do GA, nós queremos executar muita reprodução e pouca No início do GA, nós queremos executar muita reprodução e pouca mutação;mutação;

Depois de um grande número de gerações, ocorre a convergência Depois de um grande número de gerações, ocorre a convergência genética, tornando extremamente interessante que o operador de genética, tornando extremamente interessante que o operador de mutação seja escolhido mais freqüentemente. mutação seja escolhido mais freqüentemente.


Precisaríamos que a probabilidade do operador de crossover Precisaríamos que a probabilidade do operador de crossover fosse caindo com o decorrer do algoritmo e que a fosse caindo com o decorrer do algoritmo e que a probabilidade do operador aumentasse; probabilidade do operador aumentasse;

Podemos interpolar as probabilidades dos dois operadoresPodemos interpolar as probabilidades dos dois operadores;; Há várias técnicas de interpolação candidatas:Há várias técnicas de interpolação candidatas:

Operadores com Percentagens VariáveisOperadores com Percentagens Variáveis


Operador de Mutação DirigidaOperador de Mutação Dirigida

Pesquisadores resolvem o problema da convergência genética tornando a Pesquisadores resolvem o problema da convergência genética tornando a mutação mais provável que o crossover;mutação mais provável que o crossover;

Assim, há a tendência de que novamente venha a surgir uma variedade Assim, há a tendência de que novamente venha a surgir uma variedade genética dentro da população de soluções. genética dentro da população de soluções.

Todas as partes de cada uma das soluções têm igual probabilidade de Todas as partes de cada uma das soluções têm igual probabilidade de serem modificadas, sem distinção. serem modificadas, sem distinção.

O problema pode estar concentrado no esquema dominante entre as O problema pode estar concentrado no esquema dominante entre as melhores soluções;melhores soluções;

Se este esquema não for modificado de forma agressiva, pode ser que Se este esquema não for modificado de forma agressiva, pode ser que não cheguemos a lugar algum.não cheguemos a lugar algum.


Solução possível: Solução possível: Criar um novo operador de mutação, que procurasse se concentrar Criar um novo operador de mutação, que procurasse se concentrar

neste esquema dominante;neste esquema dominante; Objetivo: criar variedade genética nos genes que nos interessam. Objetivo: criar variedade genética nos genes que nos interessam. O operador só começa a agir depois de um grande número de O operador só começa a agir depois de um grande número de

gerações. gerações. Quando ativado:Quando ativado:

ele busca as ele busca as nn melhores soluções dentro da população padrão; melhores soluções dentro da população padrão; verifica qual é a bagagem cromossomial que elas têm em comum verifica qual é a bagagem cromossomial que elas têm em comum

(usando operador XNOR);(usando operador XNOR); pode-se considerar como comum cromossomos que estejam pode-se considerar como comum cromossomos que estejam

presentes apenas em uma maioria dos cromossomos.presentes apenas em uma maioria dos cromossomos.

Operador de Mutação DirigidaOperador de Mutação Dirigida


Comentários sobre Operador de MutaçãoComentários sobre Operador de Mutação

Operador de mutação é fundamental para um GA, pois Operador de mutação é fundamental para um GA, pois garante a continuidade da existência de diversidade genética garante a continuidade da existência de diversidade genética na população;na população; É uma heurística exploratória;É uma heurística exploratória; Se for sua probabilidade for baixa demais, população perderá Se for sua probabilidade for baixa demais, população perderá

diversidade rapidamente;diversidade rapidamente; Se for alta demais, GA se comportará como uma Se for alta demais, GA se comportará como uma random walk.random walk. Solução razoável: utilizar uma taxa de mutação que varie com o Solução razoável: utilizar uma taxa de mutação que varie com o

desenrolar da evolução do algoritmo;desenrolar da evolução do algoritmo; Com o steady state, pode-se aumentar taxa de mutação.Com o steady state, pode-se aumentar taxa de mutação.


Operador de crossover é o mais importante dos GAs;Operador de crossover é o mais importante dos GAs; Somado ao módulo de seleção proporcional à avaliação de Somado ao módulo de seleção proporcional à avaliação de

um indivíduo, é o responsável pelo fato de um algoritmo um indivíduo, é o responsável pelo fato de um algoritmo genético não poder ser comparado a uma busca aleatória; genético não poder ser comparado a uma busca aleatória;

Historicamente, o operador de crossover tem recebido uma Historicamente, o operador de crossover tem recebido uma percentagem de escolha muito altapercentagem de escolha muito alta; ;

Escolha do tipo de operador utilizado (representação binária):Escolha do tipo de operador utilizado (representação binária): Crossover uniforme é o mais poderosoCrossover uniforme é o mais poderoso Pode criar o mesmo tipo de soluções que os crossovers de um e de Pode criar o mesmo tipo de soluções que os crossovers de um e de

vários pontos, além de novas combinações que estes tipos não são vários pontos, além de novas combinações que estes tipos não são capazes de criar. capazes de criar.

Ele também é o mais destrutivo, sendo o crossover que mais separa Ele também é o mais destrutivo, sendo o crossover que mais separa elementos de um esquema interessante, especialmente se estes elementos de um esquema interessante, especialmente se estes elementos fundamentais são adjacentes.elementos fundamentais são adjacentes.

Comentários sobre Operador de CrossoverComentários sobre Operador de Crossover


Idéia interessante para minimizar poder destrutivo:Idéia interessante para minimizar poder destrutivo: modificar a probabilidade de selecionar um gene de cada um dos paismodificar a probabilidade de selecionar um gene de cada um dos pais aumentando a probabilidade de selecionar o gene aumentando a probabilidade de selecionar o gene ii do pai do pai kk se o gene se o gene i-1i-1 foi foi

selecionado deste pai. selecionado deste pai. Esta solução diminui a probabilidade de romper esquemas que contenham Esta solução diminui a probabilidade de romper esquemas que contenham

elementos adjacentes, sem evitar que o crossover uniforme gere soluções elementos adjacentes, sem evitar que o crossover uniforme gere soluções livremente. livremente.

Crossover de um ponto, possui uma característica denominada de Crossover de um ponto, possui uma característica denominada de preconceito positional (preconceito positional (positional biaspositional bias):): assume que esquemas curtos e de baixa ordem são os blocos funcionais assume que esquemas curtos e de baixa ordem são os blocos funcionais

básicos dos cromossomos;básicos dos cromossomos; uso deste operador permite a sobrevivência de genes “caroneiros” uso deste operador permite a sobrevivência de genes “caroneiros”

((hitchhikershitchhikers).).



Existem vários trabalhos que evitam ter que escolher entre os operadores Existem vários trabalhos que evitam ter que escolher entre os operadores de crossover;de crossover;

Acrescenta-se uma roleta adicional ao processo de reprodução;Acrescenta-se uma roleta adicional ao processo de reprodução;

Roleta serve para determinar qual operador de crossover será usado para Roleta serve para determinar qual operador de crossover será usado para aquele par de pais. aquele par de pais.

Esta estratégia tenta combinar as características exploratórias mais Esta estratégia tenta combinar as características exploratórias mais agressivas do operador de crossover uniforme com o conservadorismo do agressivas do operador de crossover uniforme com o conservadorismo do crossover de um ponto. crossover de um ponto.

Introduz-se mais um parâmetro que deve ser controlado pelo Introduz-se mais um parâmetro que deve ser controlado pelo desenvolvedor de GA, que é o conjunto de probabilidades de cada um dos desenvolvedor de GA, que é o conjunto de probabilidades de cada um dos tipos de crossover. tipos de crossover.


Documents

Algoritmos Genéticos Capítulo 6