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

Ciclo de um Algoritmo Genético

Ciclo de um Algoritmo Genético

Ciclo de um Algoritmo Genético

Ciclo de um Algoritmo Genético

Ciclo de um Algoritmo Genético

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

TOOLBOX SCILAB

TOOLBOX SCILAB

TOOLBOX SCILAB

TOOLBOX SCILAB

TOOLBOX SCILAB

Conhecendo o SCILAB

XCOS

SCILAB XCOS

SCILAB XCOS

SCILAB XCOS

SCILAB XCOS

SCILAB XCOS

SCILAB XCOS

SCILAB XCOS

SCILAB XCOS

SCILAB XCOS

SCILAB XCOS

SCILAB XCOS

SCILAB XCOS

SCILAB XCOS

SCILAB XCOS

SCILAB XCOS

SCILAB XCOS

ATIVIDADE 5

Comparando LED + LDR + PIDCom Toolbox AG Scilab

Atividade 5

Equação da malha fechada do Sistema