| 
  • If you are citizen of an European Union member nation, you may not use this service unless you are at least 16 years old.

  • Stop wasting time looking for files and revisions. Connect your Gmail, DriveDropbox, and Slack accounts and in less than 2 minutes, Dokkio will automatically organize all your file attachments. Learn more and claim your free account.

View
 

AG - Quadro Cognitivo 7

This version was saved 10 years, 12 months ago View current version     Page history
Saved by Marciel Degasperi
on December 1, 2009 at 1:39:57 pm
 

Disciplina: Inteligência Artificial

Autor: Marciel Mario Degasperi

Tema: Algoritmos Genéticos

 

1. O que eu sei sobre o tema?

Algoritmos Genéticos são algoritmos que evoluem a partir de pequenas alterações em seu "código genético" (cadeia de bits representando um conjunto de dados-objetivo), randômicas ou não, e conseguinte comparação de desempenho, em um processo que se assemelha à evolução de organismos vivos.

Os algoritmos genéticos foram criados inicialmente para auxiliar biólogos no estudo da evolução. Contudo, não demorou a que se adaptasse o algoritmo para uso geral.

Devido à natureza do algoritmo, serão empregados termos de biologia nesse documento. Por exemplo: cromossomo (conjunto de dados sob processo de seleção/mutação), indivíduo (pode ser uma classe, uma estrutura de dados, um registro, que contenha o cromossomo) e etc.

Em geral, esse processo consiste em três passos: reprodução, alteração e seleção.

 

          1.a. Reprodução            

          Consiste na criação de um novo "indivíduo". Existem duas abordagens diferentes na reprodução: na primeira, a reprodução ocorre ao acaso, gerando diversos descentes de todos os indivíduos. Na segunda, os indivíduos mais "aptos" são favorecidos a gerarem mais descendentes.

          No primeiro caso, todo o trabalho de controle dos mais aptos é feito pela função de seleção (fitness). Em geral, as reproduções ocorrem por um tempo determinado. Após esse período, a reprodução é interrompida e os mais aptos selecionados. Essa é uma abordagem menos usada.

          No segundo caso, o conceito de aptidão é incorporado à reprodução. Os indivíduos mais aptos geram mais descendentes. Essa é uma forma um pouco mais complexa, porém mais próxima do que ocorre no meio natural (talvez por isso seja a mais usada).

Ex:

Indivíduo pai                    Indivíduo mãe                 Indivíduo filho

100101010010100101     101011011101010101     100101010010100101

101010101110100011     100100111000111101     100100111000111101

 

          1.b. Alteração

            Ocorrem no cromossomo, a fim de garantir maior variabilidade. Podem ocorrer por mutação ou cross-over.

 

          1.b.1. Mutação

          No meio natural, a mutação é um dos principais fatores que garantem o surgimento de diversidade, necessária para a evolução. No meio computacional, esse processo é utilizado a fim de se evitar que o algoritmo tenda a um máximo local. A mutação ocorre ao acaso e em baixa proporção (geralmente 1%; uma alta taxa de mutação faz o algoritmo tender a uma busca randômica).

 

          1.b.2. Cross-over

          O cross-over é a troca de trechos das cadeias de bits. Su principal função é evitar a geração de diversos indivíduos filho idênticos, prejudicando a solução ou a direcionando de forma errada.

            Existem variações nas formas de cross-over: pode ser a parte final das cromátides, a parte inicial, uma parte central, ou com troca de diversos trechos das cadeias de bits. O uso de cada um depende da finalidade da aplicação ou mesmo do gosto do programador.

Ex:

Indivíduo pai                Indivíduo mãe              Indivíduo filho 1            Indivíduo filho 2:

100101010010100101   101011011101010101   100101010010111101    100100110010100101

101010101110100011   100100111000111101   100100111000100101    100101011000111101

 

 

          A peça chave do algoritmo é a função de fitness, que vai definir o problema a ser resolvido.

 

            1.c. Seleção

            A fim de se evitar uma “explosão demográfica”, a cada período pré-determinado é efetuada a seleção de um grupo de indivíduos, e conseguinte reinicialização do algoritmo. A escolha pode ocorrer de três formas: ao acaso, por elitismo (somente os melhores) ou por probabilidade, onde os mais aptos têm mais chances de serem escolhidos para o grupo.

 

            Limitações dos Algoritmos Genéticos

            Apesar dos algoritmos genéticos mostrarem eficiência e robustez como estratégia de busca de soluções, existem algumas limitações. Como exemplo, pode-se citar a dificuldade de se “dizer funcionalmente” o quanto cada indivíduo se encontra próximo da solução, a fim de se calcular a aptidão. Outro problema comum é um pequeno grupo de soluções ter aptidão muito alta, fazendo o algoritmo evoluir muito rápido a um máximo local. Existe também o fato de o algoritmo não encontrar sempre a melhor solução, e sim uma suficientemente boa.

            Então, quando utilizar Algoritmos Genéticos? Bem, sobre o meu ponto de vista, uma excelente aplicação de AG é em soluções de problemas onde a solução pode mudar de acordo com o ambiente. De fato, para se mudar o resultado final em qualquer momento basta que mudemos a função de aptidão durante a execução.

 

1.1. Aplicações que Utilizam Algoritmos Genéticos

          1.1.a - Kernel Linux

          Jake Moilanen disponibilizou uma série de quatro patches para o kernel Linux 2.6.9, que utilizam algoritmos genéticos permitindo se ajustar automaticamente para o melhor desempenho possível para qualquer trabalho dado.

          No patch de Jake, as cadeias de cromossomos são tunings possíveis para processos do kernel do Linux, e a aptidão é medida pelo desempenho em geral. Essencialmente, um grande conjunto de tunings possíveis são selecionados. Cada uma das soluções possíveis são testadas sob a carga de trabalho atual, medido para o melhor desempenho (fitness). Todas as soluções são, então, ordenadas por desempenho, e a "metade pior" do conjunto é substituída por novas soluções, geradas a partir das- melhores. Por último, a mutação aleatória é aplicada para alterar ligeiramente algumas das soluções. Segundo Jack, "ao longo do tempo as soluções devem convergir para as melhores configurações para a carga de trabalho." (Moilanen, Jake).

 

          1.1.b - Na música

          Foi apresentado em 1999 na CEC99 – IEEE – International Conference on Evolutionary Computation um ambiente interativo, utilizando Algoritmos Genéticos, para a avaliação de músicas tocadas em arquivos MIDI. O método emprega o formalismo difuso e é colocado como uma otimização baseada em fatores relevantes à audição de músicas. No caso, os indivíduos da população foram definidos em grupos de quatro vozes (soprano, contralto, tenor e baixo) ou coros. Cada um é avaliado segundo três critérios: melodia, harmonia e oitavas. A composição destes três critérios definia a aptidão definida pela função de seleção, que retorna o melhor indivíduo ou melhor coro. Um ciclo genético é operacionalizado, criando novos indivíduos dos anteriores e procurando sempre pelo melhor. Quando um novo grupo é selecionado, ele é tocado em MIDI. A duração do ciclo genético determina o ritmo da evolução. O sistema criado foi denominado Vox Populi. (FUKUSHIMA, 1999)

 

     1.1.c -Nas Telecomunicações

     Segundo Blanchard (1994), no WCCI'94 – World Congress on Computational Intelligence – ocorrido em Orlando, na Flórida, mostrou uma série de soluções promissoras a situações reais utilizando Algoritmos Genéticos. Blanchard mostrou o caso da US West, uma companhia regional de telecomunicações do estado do Colorado, que vem usando um sistema baseado em AGs que possibilita projetar, em duas horas, redes óticas especializadas, trabalho que levaria seis meses utilizando especialistas humanos. O sistema produz resultados ainda 10% (dez por cento) melhores que os realizados pelo homem. A companhia estimava, naquele momento, que o sistema possibilitará uma economia de 100 milhões de dólares até o final do século.

 

     1.1.d - Na Medicina

     Os Algoritmos Genéticos foram utilizados no Hospital Universitário da UFSC (1999) para auxiliar na elaboração de uma escala de trabalho dos médicos plantonistas neonatalogistas da maternidade. O objetivo era auxiliar na solução da escala de trabalho dos médicos, em como diminuir o esforço e o desgaste humanos para a confecção do plantão. O problema resumia-se na disponibilidade de 12 (doze) médicos e na necessidade de atendimento 24 (vinte e quatro) horas por dia, tendo-se como variáveis envolvidas o número de médicos contratados e o turno com número adaptável de horas. O questionamento apresentava ainda todo o conjunto de restrições de trabalho, como cargas horárias, turnos de trabalho, plantões noturnos e diurnos, finais de semana e feriados, número máximo de horas de trabalho consecutivas, períodos específicos de possibilidade de trabalho, horários fixos para determinados médicos e cargas horárias variáveis entre os médicos, podendo inclusive haver mudança nas variáveis todos os meses.

 

     1.1.e - Na Geografia

     Em um trabalho realizado pelo Instituto Nacional de Pesquisas Espaciais (INPE), os Algoritmos Genéticos foram utilizados para classificar automaticamente o espaço urbano, aplicando técnicas de extração e seleção de atributos em imagens de alta resolução. Para classificar a malha viária e outros componentes urbanos são implementados alguns atributos de forma que permitem reconhecer objetos distintos espectralmente semelhantes. Para maximizar a exatidão da classificação e diminuir o custo de processamento, a seleção de atributos é feita pelos algoritmos genéticos e pela busca exaustiva por máxima verossimilhança gaussiana.

 

     1.1.f - Na robótica

     Algoritmos Genéticos são bastante usados em robótica, quando existe ausência de padrão na busca de soluções onde Redes Neurais se aplicariam com amior eficiência. Um exemplo seria o ato de caminhar sobre uma superfície totalmente irregular, ou em um labirinto onde as passagens se reconfiguram com o passar do tempo. O vídeo abaixo mostra um pequeno robô que usa esse princípio para se mover em um labirinto.

 

YouTube plugin error

Uso de Algoritmo Genético na robótica  

 

     1.1.g - Implementação Gráfica

     Abaixo segue uma implementação gráfica, criado por Marek Obitko[1]. Nele é possível visualizar passo-a-passo todo o processo, inclusive a mutação e o cross-over.


Aqui tem um applet, porém seu navegador não suporta Java.

Funcionamento de um Algoritmo Genético 

1.2. Uma Implementação

           Para a implementação desse exemplo foram utilizadas algumas técnicas expostas em diversos documentos na Internet. A linguagem escolhida foi JAVA, devido aos métodos nativos de manipulação de threads e a característica de orientação a objetos que torna o código intuitivo. Gostaria de esclarecer que o objetivo desse código é puramente didático, não focado em otimização ou em algum critério rígido de eficiência. Foi planejado para se comportar o mais próximo possível do que ocorre no meio natural.

          A seguir são listadas as principais classes do algoritmo, com suas funcionalidades. O código completo está disponível para download na pasta de algoritmos genéticos de nossa wiki

 

 

1.2.a. Classe Cromossomo

           A classe Cromossomo armazena a informação, composta de um par de vetores de inteiros representando bits (cromátides). A idéia é representar dados simples, tais como inteiros, números de ponto flutuante, ou pequenas strings.

x=606           z=2003

001001011110011111010011

000100001001000101110111

y=265            w=375 

Fig. 1.1 - Exemplo de representação de 4 valores no cromossomo.

 

          Pertencem a esta classe as funções de cross-over e mutação. 

 

Função crossOver():

A função de cross-over troca partes das cromátides, em um ponto aleatório. O principal objetivo é impedir que todos os cromossomos filhos de mesmos pais sejam idênticos.

Nessa implementação o algoritmo usa o processo mais simples: um ponto da cromossomos é escolhido e a partir daí todos os bits são trocados.

 

001001011110011111010011

000100001001000101110111

Antes da chamada da função

 

001001011110011111010011

000100001001000101110111

      ▲

Escolha de um ponto

 

001001011110000101110111

000100001001011111010011

Após a chamada da função 

 

Fig. 1.2 – Cross-over

 

 

Função mutacao()

          A mutação ocorre com a troca de um bit, em um ponto aleatório. Sua finalidade é garantir variabilidade de resultados e impedir que a função tenda a um mínimo local.

 

001001011110011111010011

000100001001000101110111

Antes da chamada da função

 

001001011110011111010010

000100001001000101110111

Após a chamada da função 

 

Fig. 1.3 – Mutação

 

 

           Tanto a mutação quanto o cross-over ocorrem a uma taxa baixa (é comum encontrar as taxas de 1% e 3%, respectivamente, nos algoritmos). A explicação é simples: o excesso de variação transformaria o algoritmo numa busca por expansão.

 

1.2.b. Classes Ser, Macho e Femea

          A classe Ser é a base de um indivíduo, estendendo a classe nativa Thread. Cada indivíduo possui um cromossomo e uma propriedade chamada aptidao, que serão explicados adiante.

          As classes Macho e Femea herdam a classe Ser, porém possuem finalidades distintas (e óbvias): A classe Macho gera um valor (semente), que nada mais é que um de seus vetores de bits (cromátides), e lança numa variável global. A classe Femea se encarrega de ler a semente, combinar com o próprio cromossomo (uma de suas cromátides) e criar uma novo indivíduo, Macho ou Femea. Ambas as classes dependem de sua aptidão (que varia de 1 a 100) para realizar a tarefa; um Macho com aptidão de 50 gerará uma semente em 50% do casos.

          É no momento da criação de um novo indivíduo que podem ocorrer a mutação e o cross-over no cromossomo do indivíduo filho.

 

          Por que threads?

          Para os leigos (não que eu seja algum expert, longe disso), threads são como subprocessos que executam “paralelamente” (na verdade trata-se de pseudo-paralelismo). Cada thread após criada passa a ser executada independente do programa principal.

          Nessa implementação, cada indivíduo é uma nova thread, que ao ser criada passa a interagir com as demais por conta própria. Essas características fazem com que o processo se aproxime do comportamento de um meio natural.

 

1.2.c. Classe Selecao

          Coração do processo evolutivo. Sem ela, o algoritmo não passa de um monte de threads sendo geradas até o estouro de memória (imagine um casal de coelhos soltos em um planeta distante onde somente existam cenouras). Agora que temos o ambiente reprodutivo, precisamos criar um meio de direcionar a evolução e evitar uma explosão demográfica.

          Na classe são definidas duas funções principais: fitness() e calculaAptidao(). 

 

Função calculaAptidao()

          Em resumo, define o quão próximo os dados se encontram da solução. Retorna um valor no intervalo de 1 a 100, representando a chance em % da thread gerar sementes (Macho) ou gerar novos indivíduos (Femea). Dessa forma, induzimos a população a ter em sua maioria indivíduos mais aptos. Essa é a função que define o problema a ser resolvido. 

 

Função fitness()

          Consiste na renovação do espaço amostral. Um pequeno grupo de bons resultados é mantido, enquanto os demais são descartados (elitismo). 

 

1.2.d. Problemas do código (known bugs)

           Alguns problemas conhecidos no código foram ignorados, devido a diversos fatores, entre os quais podemos citar a baixa ocorrência e a não-necessidade de um algoritmo ótimo, visto sua aplicação didática, e um tanto de falta de tempo do programador, que não pôde se dedicar o tanto quanto queria.

          Entre os problemas, destacam-se:

          -“Solidão”: As melhores threads selecionadas no fitness() são todas de um único sexo. O programa simplesmente pára de reproduzir;

          -“Dormir ou morrer”: Todas as threads marcadas para morrer ficam em estado sleep (precisam acordar para finalizar). Ocorre então o estouro de memória;

          -“Maus Pais”:As primeiras threads (chamadas criativamente de “Adão” e “Eva”) possuem aptidão muito baixa. Com isso, reproduzem muito pouco ou não reproduzem.

          Os casos onde ocorreram os problemas acima foram ignorados.

2. O que quero saber?

          - Aplicações dos algoritmos genéticos em resolução de problemas de otimização;

          - Outras aplicações de algoritmos genéticos;

          - Softwares que utilizam algoritmos genéticos, e suas vantagens às outras soluções;

          -Mais sobre a aplicação dos Algoritmos Genéticos no kernel Linux.

 

3. O que vou fazer?

          - Pesquisa na área;

          - Implementação de testes e apresentação de resultados;

          - Atualização deste quadro cognitivo.

 

4. Como vou fazer?

          - Pesquisa na Internet e em livros sobre o assunto;

          - Implementação em JAVA de outros testes, modificando a classe Selecao do algoritmo apresentado;

          - Apresentação de outros algoritmos genéticos encontrados pela internet.

 

5. Quando vou fazer?

          - Atualizações do quadro cognitivo: a cada 15 dias.

          - Apresentação de resultados das implementações de teste: no último quadro cognitivo.

 

Referências:

          [1] http://www.obitko.com/tutorials/genetic-algorithms/portuguese/

 

Webliografia:

          - Wikipedia (espanhol e inglês);

          - Página da UFRJ;

          - Jake Moilanen's Linux Kernel Homepage;

          - BDBComp; 

          - Links relacionados

 

 

 

 

 

Comments (0)

You don't have permission to comment on this page.