SÍNTESE ALGORITIMOS GENETICOS

Prévia do material em texto

1 
 
 
INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO PARÁ 
CAMPUS CASTANHAL 
CURSO DE LICENCIATURA EM INFORMÁTICA 
 
 
 
 
 
 
 
CLAUDIO ALVES DA SILVA 
 
 
 
 
 
 
SÍNTESE ALGORITIMOS GENETICOS 
 
 
 
 
 
 
 
 
 
 
CASTANHAL 
2021 
2 
 
 
CLAUDIO ALVES DA SILVA 
 
 
 
 
 
 
 
SÍNTESE ALGORITIMOS GENETICOS 
 
 
 
 
 
 
Trabalho apresentado à disciplina Tópicos 
especiais em IA , do Curso de Licenciatura 
em Informática, do Instituto Federal de 
Educação, Ciência e Tecnologia – IFPA, 
campus Castanhal, como requisito avaliativo 
para o 2º Bi. 
Docente: Suelene Correia 
 
 
 
 
 
 
 
 
 
CASTANHAL 
2021 
3 
 
 
Algoritmos Genéticos tem como ideia inicial nos princípios darwiniano da evolução das 
espécies e na genética, neste sentido eles são algoritmos probabilísticos construídos de forma 
em que fornecem uma construção de busca paralela e adaptativa baseando-se no princípio de 
sobrevivência dos mais aptos e na reprodução. 
De acordo com evolução das espécies no darwiniano, uma população passa por um 
processo de seleção de indivíduos quando há escassez de recursos para a sobrevivência, ou seja, 
na falta de comida, água, demais recurso essencial para a viverem, nesta seleção os aqueles 
mais aptos para a competição dominam os mais fracos e sobrevivem, neste princípio os 
sobreviventes são os que possuem características indispensáveis à competição de forma mais 
intensificado que os outros, essas características são passadas a seus descendentes, torando eles 
mais fortes, com mais chances de sobrevivência e tornando-os em vencedores na competição 
por recursos essenciais para viverem, e depois, dos indivíduos mais fortes podem surgir de 
uma característica que ainda não existe na população. 
Estes princípios servem como base na construção de algoritmos geneticos 
computacionais que procuram uma melhor solução para um determinado problema, para isso, 
são criados evoluções populações codificadas de cromossomos artificiais que executam a 
mesma função da teoria darwinista da evolução das espécies e na genética. Desta forma, pode-
se afirmar que, os algoritmos genéticos são uma família de modelos computacionais inspirados 
na evolução, que incorporam uma solução potencial para um problema específico numa 
estrutura semelhante a de um cromossomo, e aplicam operadores de seleção a essas estruturas 
de forma a preservar informações críticas relativas à solução do problema. E umas das 
vantagens disso é que eles permitem uma simplificação para formulação e solução de problemas 
de otimização. 
Esses estudos começaram a ganhar forças de 1950 a 1960 com a criação de sistemas 
evolucionários, e teve com um dos principais pesquisador John Holland, que desenvolveu 
Programas para simulação e solução de problemas complexos, usando função matemática e 
manipulação de cadeias binárias como representação dos cromossomos. Depois disso, os 
estudos e aplicações de algoritmos genéticos tiveram grandes evoluções e hoje já é bastante 
usados no ramo computacional. 
Os principais conceitos sobre algoritmos genéticos são: 
 cromossomo (genótipo) - cadeia de bits que representa uma solução possível para o problema. 
4 
 
Gene - representação de cada parâmetro de acordo com o alfabeto utilizado (binário, inteiro ou 
real). 
Fenótipo - cromossomo codificado 
População - conjunto de pontos (indivíduos) no Espaço de Busca 
Geração - iteração completa do AG que gera uma nova população 
Aptidão bruta - saída gerada pela função objetivo para um indivíduo da população 
Aptidão normalizada - aptidão bruta normalizada, entrada para o algoritmo de seleção. 
Aptidão máxima - melhor indivíduo da população corrente 
Aptidão média - aptidão média da população corrente 
Deve ser levando em conta que cada cromossomo, obedece a um ponto no espaço de 
soluções do problema de otimização. O processo de solução adotado nos algoritmos genéticos 
consiste em gerar, através de regras específicas, um grande número de indivíduos (população), 
de forma a promover uma varredura tão extensa quanto necessária do espaço de soluções. 
Na figura abaixo é mostrada A estrutura básica do algoritmo genético 
 
 
 
 
 
 
 
 
 
De acordo com a imagem do diagrama mostrado na figura a cima pode se observar que 
cada iteração do algoritmo genético obedece à aplicação de um conjunto de quatro operações 
básicas: cálculo de aptidão, seleção, cruzamento e mutação. Ao executar estas operações cria-
se uma nova população, denominada de geração que, espera-se, representa uma melhor 
5 
 
aproximação da solução do problema de otimização que a população anterior. Para gera uma 
nova população, é necessário que seja atribuído aleatoriamente valores aos genes de cada 
cromossomo. A aptidão bruta de um indivíduo da população é medida por uma função de erro, 
também chamada de função objetivo do problema de otimização. Para permitir um melhor 
controle do processo de seleção, é preciso normalizar a aptidão bruta. Como critérios de parada 
do algoritmo em geral são usados a aptidão do melhor indivíduo em conjunto com a limitação 
do número de gerações. Pode-se envolver outros critérios, por exemplo, um erro abaixo de um 
valor especificado pelo projetista para um determinado parâmetro do problema. 
Iniciação 
Primeiro gera-se de forma aleatória uma população de n indivíduos onde cada um dos 
indivíduos da população representa uma possível solução para o problema. 
Calculo da aptidão 
A aptidão do indivíduo é feita através do cálculo da função objetivo, que depende das 
especificações de projeto. Nesta execução, cada indivíduo é uma entrada para uma ferramenta 
de análise de desempenho, na qual a saída fornece medidas que fazem que seja possível o 
algoritmo genético o calcular a aptidão do indivíduo, nesta fase os indivíduos são ordenados 
conforme a sua aptidão. 
Seleção 
Nesta fase são selecionados os indivíduos mais aptos da geração atua, depois usa-se 
esses indivíduos para gerar uma nova população por cruzamento. Cada indivíduo tem uma 
probabilidade de ser selecionado proporcional à sua aptidão. Para visualização, este método 
considere um círculo dividido em n regiões de acordo com tamanho da população, onde a área 
de cada região é a representação da aptidão do indivíduo, depois é colocado sobre esse circulo 
uma “roleta” com n cursores com espaçamentos iguais, os indivíduos selecionados são 
indicados após um giro da roleta. Este método é denominado amostragem universal estocástica. 
Matematicamente os indivíduos cujas regiões possuem maior área terão maior chances de 
serem selecionados várias vezes. a consequência, disso é que seleção de indivíduos pode conter 
várias cópias de um mesmo indivíduo enquanto outros podem desaparecer. 
6 
 
A figura a baixo mostra um exemplo desta fase: 
 
 
Cruzamento ("CROSS-OVER") 
Todos os indivíduos selecionados na etapa anterior são cruzados da seguinte forma: 
embaralha-se de forma aleatória a lista dos indivíduos selecionados, com isso, é criada uma 
segunda lista, que é denominada de lista de parceiros, depois é feito o cruzamento de cada 
indivíduo selecionado com o indivíduo que ocupa a mesma posição na lista de parceiros. os 
cromossomos de cada par de indivíduos a serem cruzados são particionados em um ponto, 
chamado ponto de corte, sorteado aleatoriamente. Um novo cromossomo é gerado permutando-
se a metade inicial de um cromossomo coma metade final do outro. Deve-se notar que se o 
cromossomo for representado por uma cadeia de bits, o ponto de corte pode incidir em qualquer 
posição dos bits no interior de um gene, não importando os limites do gene. No caso de genes 
representados por números reais, a menor unidade do cromossomo que pode ser permutada é o 
gene. 
A imagem abaixo ilustra essa etapa: 
 
 
 
 
 
 
 Mutação 
Para garanti uma maior varredura do espaço de estados e impedir queo algoritmo 
genético faça correção muito cedo para mínimos locais, é necessário fazer a operação 
chamada de mutação, para isso, executa-se uma alteração no valor de um gen de um ter 
terminado indivíduo que foi sorteado aleatoriamente com uma determinada probabilidade, 
com isso, vários indivíduos de uma nova poderão ter seus gens alterados. 
Escolha dos parâmetros do algoritmo genético 
7 
 
 
Muitas vezes é necessário usar formas de codificação diferentes de como o cromossomo 
é codificado, para isso, vários parâmetros podem ser escolhidos para melhorar o desempenho 
do algoritmo genético, isso é feito para adapta-lo as às características particulares de 
determinadas classes de problemas. Os paramentos mais importantes são o número de gerações, 
a probabilidade de cross-over e a probabilidade de mutação. A influência de cada parâmetro no 
desempenho do algoritmo depende da classe de problemas que se está tratando, desta forma, 
para determinar um conjunto de valores otimizado para estes parâmetros será necessário a 
execução de um grande número de experimentos e testes. Em grande maioria das literaturas 
sobre o assunto, os valores então na estão na faixa de 60 a 65% para a probabilidade de cross-
over e entre 0,1 e 5% para a probabilidade de mutação. O tamanho da população e o número 
de gerações dependem da complexidade do problema de otimização e devem ser determinados 
experimentalmente. 
Entretanto, é necessário observa que tamanho da população e o número de gerações 
determina diretamente o tamanho do espaço de busca a ser coberto. 
Existem casos que é utilizado um algoritmo genético como método de otimização para 
a escolha dos parâmetros de outro algoritmo, devido à importância da escolha correta destes 
parâmetros. 
Aplicações 
 Os algoritmos genéticos são aplicados em muitas áreas científicas, entre as quais podem 
ser destacadas: 
Gerenciamento de redes: supervisão do tráfego nos links e das filas nos "buffers" de 
roteadores para descobrir rotas ótimas e para reconfigurar as rotas existentes no caso de falha 
de algum link 
Programação Genética: gera a listagem de um programa, numa determinada 
linguagem especificada, para que um determinado conjunto de dados de entrada forneça uma 
saída desejada. 
 
8 
 
Ciências biológicas: modela processos biológicos para o entendimento do 
comportamento de estruturas genéticas. 
Computação Evolutiva: gera programas que se adaptam a mudanças no sistema ao 
longo do tempo. 
 
 
 
 
 
 
 
 
Estudo do caso 
Coluna de destilação com sistema mimo 
Aplicação do algoritmo genético para tarefa de design de controlador, com o objetivo 
quantitativo 
1. As metas são definidas por engenheiros da produção e operadores 
2. Para esse caso será usado uma função PGS que controla as entras e saídas do sistema e uma 
função CDS que será a função controladora, esta função apresenta os parâmetros (Kc,Td, e 
Ti). 
3. Problema: Encontrar as variáveis Kc, Td e Ti, para que respondam a círculos fechados para 
mudanças de espaço nos pontos definidos, as seguintes característica qualitativas: 
Sejam sensíveis a bruscas mudanças, sejam sensíveis a mudanças suaves e tenha uma resposta 
estável sem muitos ruídos. 
4. O procedimento de otimização é inicializado por 10 valores, de zero ate dez 
respectivamente. Esses parâmetros predefinidos são a primeira geração. 
5. Usando esses valores, simulações são conduzidas em ciclos fechados, as respostas são 
classificadas em pontuação pelo critério definido chamado de operador, que decide um 
valor numérico para cada resposta, demostrando a qualidade a qualidade das respostas 
9 
 
apresentadas. Caso tenha ausência de uma pontuação pode-se substituí por uma 
convergência do algoritmo genético, no entanto, a convergência se torna lenta. 
6. No final do processamento do algoritmo genético, sera empreso um rank sendo escolhido 
os melhores resultados para as condições de operação pelos engenheiros. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Referencias: 
Correia Suelene, apostila Tópicos especiais em IA, Instituto Federal de Educação, Ciência e 
Tecnologia do Pará 
Miranda Marcio, Algoritmos Genéticos: Fundamentos e Aplicações, universidade federal do 
Rio de Janeiro, disponível em, http://www.nce.ufrj.br/GINAPE/VIDA/alggenet.htm, acessado 
em, 09/03/2021, as 20:00h 
Inicio 
A, B, operador 
Kc= A1B; 
Td= A1b; 
Ti=A1b; 
N=0 
Kc, Td, e Ti, não satisfazem as 
condições do operador 
Criação de uma nova geração através dos operadores 
de seleção, cruzamento e mutação. 
Pontuação dos melhores indivíduos. 
N1=N+1 
Melhores resultados para Kc, Td 
e Ti 
 
http://www.nce.ufrj.br/GINAPE/VIDA/alggenet.htm