Pós-Graduação em Engenharia de Automação...

View
4
Download
0
Category

Documents

Preview:

Citation preview

SISTEMAS INTELIGENTES PARA AUTOMAÇÃO

Pós-Graduação em Engenharia de Automação

Industrial

Algoritmos Genéticos

AULA 06

Sumário

• Introdução

• Inteligência Artificial (IA)

• Algoritmos Genéticos

• Aplicações de Algoritmos Genéticos

• Conclusões e Recomendações

Introdução

Diversos problemas de ciência e engenharia

requerem aplicar técnicas de optimização.

● Optimização de parâmetros

● Consideração de restrições dos parâmetros

● Um amplo espaço de busca de soluções

Introdução

Exemplos de problemas em que se implementar procedimentos de optimização requer

● Optimização de funções matemáticas● Problema do carteiro viajante● Optimização de rotas de veículos● Optimização de projeto de circuitos eletrônicos● Optimização de planejamento e distribuição

Introdução

Uma grande quantidade de possíveis soluções

● Restrições das variáveis

● Problemas de Minimização/Maximização

Inteligência Artificial (IA)

São técnicas e sistemas computacionais que imitam aspectos humanos em computadores, tais como:

● Percepção● Raciocínio● Aprendizagem● Evolução● Adaptação

Inteligência Artificial (IA)

As técnicas de inteligência computacional estão inspiradas na natureza e compreendem:

Algoritmos Genéticos ↔ Evolução Biológica

Redes Neurais ↔ Neurônios Biológicas

Lógica Fuzzy ↔ Processamento Linguístico

Sistemas Especialistas ↔ Inferência Humana

Algoritmos Genético

Algoritmo de busca e optimização inspirado na

seleção natural e reprodução genética.

Seleção do mais apto Reprodução Genética

Evolução

Algoritmo Genético

Buscam imitar o processo da Evolução das Espécies

Simplificado, porém eficiente

Aplicado em problemas de busca, otimização, agendamento etc.

Diferenças:◦ Na natureza não existe condição de parada

Adaptação (Fitness)

A cada geração, quanto maior a adaptação dos descendentes, maior a chance de ele ser escolhido para produzir a próxima geração e assim aumentam as chances de sucesso (como ocorre na natureza)

Adaptação (Fitness)

Cromossomo e População

• Cromossomo é uma solução proposta para o problema

• População é o conjunto de cromossomos com propostas de solução para o problema

• A população não deve ser muito pequena e também muito grande (aumenta processamento e não otimiza a solução)

Genes

Um cromossomo é composto por genes, que pode ser valores binários, numéricos, texto etc.,dependendo do problema

Cada cromossomo carrega um conjunto diferentes de genes, ou seja, propostas diferentes para a solução do problema

Genes

Recombinação (crossover)Processo de combinar alguns cromossomos produzindo uma nova geração (descendentes)

Objetiva gerar descendentes melhores

Estes novos cromossomos possuem uma combinação de seus genes

A combinação de dois indivíduos ocorre de acordo uma probabilidade, por exemplo (0,5, 0,7)

Os cromossomos são selecionados com reposição

Os pontos de cruzamento são selecionados aleatoriamente

Utiliza-se um método de seleção, como por exemplo a Roleta (Roulette wheel)

Elitismo

A fim de não se perder os cromossomos com melhor adaptação, uma cópia destes é mantida sem alterações (sem crossover) e passada para a próxima geração

Codificação

Basicamente diz qual será a estrutura dos genes do cromossomo

◦ Binária (O que levar na mochila)

◦ Permutação (Caixeiro viajante)

◦ Valores (Equação matemática)

Recombinação (crossover)

Recombinação: Seleção por Roleta

• Cromossomos mais ajustados, tem mais chance de seleção, e serão selecionados mais vezes

• Desvantagem: cromossomos com baixa adequação tem muito poucas chances

Recombinação: Seleção por Classificação

Os piores cromossomos recebem uma classificação igual a 1, o segundo pior igual a 2 e assim sucessivamente

Assim há um balanceamento na chance de seleção doscromossomos, mesmo os com ajuste muito baixo

Mutação

Cada Gene pode ser modificado aleatoriamente de acordo com uma probabilidade Normalmente a probabilidade é muito baixa (por exemplo, 0,01 ou 0,001)

Adaptação (Fitness)

Na natureza, a adaptação é medida mediante o ambiente

Cada individuo recebe uma “nota” Quanto maior a nota, mais

chances do individuo tem de permanecer para reproduzir a

próxima geração Indivíduos com baixas notas, tem mais

chances de serem descartados

Adaptação: como medir?

Espaço de Soluções

Soluções possíveis para o problema

Uma solução é medida pela sua adaptação

A melhor solução encontrada nem sempre é a solução ótima

Descendentes

Através de crossover, mutação e elitismo, uma nova geração é gerada

A geração anterior é completamente substituída

A nova geração tem a mesma população (cromossomos) da geração anterior

Algoritmos Genético

Paradigma utilizado para a implementação de

algoritmos evolutivos para optimização

Algoritmos Genético

Problema de minimização de uma função matemática.

Ciclo de um Algoritmo Genético

Evolução do AG

Algoritmos Genéticos

• Algoritmo de busca e optimização inspirado na seleção natural e reprodução genética

• Algoritmos Genéticos empregam um processo adaptativo e paralelo de busca de soluções em problemas complexos

• Combina a sobrevivência do individuo mais apto e o cruzamento aleatório da informação

Aplicações de AGs

● Optimização de funções matemáticas

● Problema do carteiro viajante

● Optimização de rotas de veículos

● Optimização de projeto de circuitos eletrônicos

● Optimização de planejamento e distribuição

Optimização de Funções Matemáticas

Problema do Carteiro Viajante

Se desejam visitar as cidades desde um ponto de partida, com a menor distância e sem passar dois vezes pela mesma cidade.

Problema do Carteiro Viajante

Optimização de Projeto de Circuitos Eletrônicos

• Para uma resposta de saída desejada, é possível otimizar o projeto do circuito eletrônico usando AG

Optimização Planejamento e Distribuição

• Planejamento de Horários de aulas em Universidades em função das disponibilidades dos docentes e salas disponíveis

Conclusões

• Algoritmos Genéticos permitem encontrar soluções ótimas e em tempos curtos quando o espaço de busca é muito amplo.

• Os AGs realizam buscas de soluções de forma direcionada de forma adaptativa e paralela.

• Deve-se considerar a construção de uma função de adaptação (Fitness) que permita diferenciar aos indivíduos mais aptos.

Conclusões

Os AGs não garantem uma solução global (Problema de estagnação)

ATIVIDADE 4

Algoritmo OneMax

Conhecendo o SCILAB

Toolbox AG

TOOLBOX SCILAB

A planta de teste simulada para o controle PID foi uma planta de primeira ordem estável sem atraso

Função Fitness

O primeiro passo na resolução deste tipo de problema é definir qual será a função fitness, ou função de avaliação utilizada para que as avaliações das possíveis soluções sejam realizadas. Ou seja, qual é a condição que um determinado conjunto de Kp, Ki e Kd deve satisfazer a cada iteração, para que a resposta do sistema seja cada vez mais semelhante à referência.

Função FitnessNas aplicações deste tipo de problema existem alguns índices de desempenho bastante usuais e que basicamente atuam sobre o erro do sistema, isto é, a diferença entre os valores de referência e de saída. Sendo assim, pode-se utilizar como estratégia para a determinação dos parâmetros do controlador a premissa de que, se a cada instante o desvio entre estas duas variáveis for diminuindo, as curvas dos sinais de saída e de referência serão cada vez mais próximas. Alguns destes são:

Função Fitness

ISE - Integral do quadrado do erro;IAE - Integral do valor absoluto do erro;ITAE - Integral do tempo multiplicado pelo valor absoluto do erro;ITSE - Integral do tempo multiplicado pelo quadrado do erro.

TOOLBOX SCILAB