PLANEJAMENTO DO TREINAMENTO DE TRABALHO EM ALTURA

[pic 1]

FACULDADE DE TECNOLOGIA DE SÃO PAULO

ANÁLISE E DESENVOLVIMENTO DE SISTEMAS

ELEN DE SOUZA

ISABELA FRANCISCO LOPES LEAL

MARCOS AKIRA FUKUSHIMA

MARINA MANENTE RODRIGUES

SANDY LEILA LEITE

INTELIGÊNCIA ARTIFICIAL: ALGORÍTMOS GENÉTICOS

São Paulo – SP

Setembro/2018

SUMÁRIO

1.        Introdução        2

2.        Algoritmos genéticos        3

3.        Operadores genéticos        6

3.1        crossover        6

3.2        mutação        9

4.        Técnicas para manter diversidade populacional em algoritmos genéticos        10

4.1        compartilhamento de recursos (sharing)        10

4.2        evolução cooperativa        11

4.3        abordagens hibridas        12

---

1. INTRODUÇÃO

Considerando o avanço significativo das tecnologias recentes, a solução de problemas de grande complexidade tem sido um desafio constante para os pesquisadores de diversas áreas. Os métodos tradicionais de resolução não apresentam um desempenho tão satisfatório em casos onde se leva em conta fenômenos como descontinuidade, instabilidade estrutural, entre outros aspectos.

 Na tentativa de se determinar as metodologias eficientes que objetivam a resolução desses problemas, surgem ramos de estudo dentro da Inteligência Artificial, como é o caso da Computação Evolucionária, que propõe um novo paradigma para solução de problemas e compreende um conjunto de técnicas de busca e otimização inspiradas na evolução natural das espécies (Seleção Natural (Darwin 1859)). Algoritmos Genéticos e Programação Genética são as duas principais frentes de pesquisa em Computação Evolutiva.

Os algoritmos genéticos foram introduzidos por J. Holland em meados dos anos 1960 e 1970 buscando formalizar matematicamente e explicar os processos de adaptações em sistemas naturais e então desenvolver sistemas artificiais que retenham os mecanismos originais encontrados em sistemas naturais. Entre os mecanismos originais retidos, temos os operadores de crossover e mutação como exemplo. O conceito de algoritmos genéticos foi futuramente popularizado por David Goldberg, através da resolução de um problema, envolvendo o controle de transmissão de gasoduto. Neste trabalho, buscamos explicar suas funcionalidades, características e aplicações.

1. ALGORITMOS GENÉTICOS

Um Algoritmo Genético (AG) é uma técnica que objetiva achar soluções aproximadas em problemas de otimização e busca. Algoritmos genéticos diferem dos algoritmos tradicionais de otimização em basicamente quatro aspectos:

• Baseiam-se em uma codificação do conjunto das soluções possíveis, e não nos parâmetros da otimização em si;
• Os resultados são apresentados como uma população de soluções e não como uma solução única;
• Não necessitam de nenhum conhecimento derivado do problema, apenas de uma forma de avaliação do resultado;
• Usam transições probabilísticas e não regras determinísticas.

Os algoritmos genéticos têm conceitos originados da teoria da evolução natural e da genética, como, por exemplo, o termo cromossomos, o qual corresponde a um indivíduo da população e contém a codificação (genótipo) de uma possível solução do problema (fenótipo). Levando para o lado prático, são implementados como vetores, onde cada elemento do vetor é chamado de gene, e os possíveis valores de um gene são chamados de alelos.

O processo de evolução começa com a criação aleatória dos indivíduos da população inicial, após isso é realizada a busca por quais são as melhores soluções, a qual é realizada a partir de um processo de seleção baseado na aptidão de cada indivíduo. Os indivíduos escolhidos através dessa busca são então direcionados para a fase de reprodução, onde são formadas novas soluções a partir destes indivíduos e os operadores genéticos. O procedimento básico de um algoritmo genéticos é resumido nas imagens abaixo:

[pic 2]

[pic 3]

Dentro de um algoritmo genético, o processo de evolução corresponde ao processo de busca em um espaço de soluções potenciais para um problema, isto é realizado a partir de dois principais estilos de métodos de otimização, os métodos do tipo hillclimbing aproveitam a melhor solução e realizam a busca de aprimoramentos a partir dela, de modo que acabem por ignorar a maior exploração do espaço de busca. Já os métodos de busca aleatória exploram o espaço de busca de maneira mais ampla, porém sem possuir um foco em regiões mais promissoras. Nos algoritmos genéticos busca-se manter uma classe de métodos de busca que balanceie o aproveitamento das melhores soluções e também do espaço de busca.

A cada geração, busca-se a reprodução de soluções relativamente “boas”, enquanto as soluções “ruins” estejam sendo eliminadas, a seleção baseada na aptidão de cada indivíduo é tida através de uma função objetivo a qual simula o papel da pressão do ambiente sobre o indivíduo. Com isto temos uma o início da nova geração da população deste algoritmo, a qual antes passa pela fase de reprodução onde são geradas novas soluções potenciais (indivíduos) através dos operadores genéticos. Este ciclo se repete dentro de um número máximo de iterações pré-determinado ou até que se alcance o nível de adaptação esperado e atinja assim a condição de fim do algoritmo.