Aula_Lourdes_AG_Modo_de_Compatibilidade_

Prévia do material em texto

Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Informática em SaúdeInformática em Saúde
Computação EvolucionáriaComputação Evolucionária
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 11
Computação EvolucionáriaComputação Evolucionária
Profa. Dra. Lourdes Mattos Brasil
lmbrasil@unb.br
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
♦Introdução
♦Histórico
♦Algoritmos evolucionários
♦Base biológica
♦Algoritmos genéticos
Sumário
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 22
♦Algoritmos genéticos
♦Aplicações
♦Algoritmos genéticos no aprendizado de redes 
neurais
♦Algoritmos genéticos na otimização do número 
de neurônios na camada intermediária
♦Perspectivas futuras
♦Outras
♦Conclusões
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
♦ Até a Modernidade
• Criacionismo e Abiogênese (teorias fixistas)
♦ 1735: Carl von Linneé (Lineu)
Histórico
♦ 1735: Carl von Linneé (Lineu)
• Classificação dos seres vivos
♦ 1809: Jean-Baptiste de Monet, Cavaleiro de Lamark
• Hereditariedade (Lei do uso e desuso)
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 33
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
♦ 1859: Charles Darwin
• Existe uma diversidade de seres devido aos contingentes da 
natureza (comida, clima, ...) e é pela lei da Seleção Natural
que os seres mais adaptados ao seus ambientes sobrevivem
Histórico
– Contra a Lei do uso e desuso
• Caracteres adquiridos são herdados pelas gerações seguintes 
♦ 1864: Louis Pasteur
• Biogênese
♦ 1865: Gregor Mendel
• Genética: “herança de características”
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 44
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Histórico
♦ 1901: Hugo De Vries
• Formalizou o processo de geração de diversidade (Teoria da 
Mutação)
♦ 1907: Thomas Hunt Morgan 
• Cromossomos
♦ 1953: James Watson e Francis Crick
• Estrutura do DNA
♦ 1950-1960
• Simulações computacionais de sistemas genéticos
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 55
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
♦ 1960: John Holland
• Algoritmos Genéticos
♦ 1964: Ingo Rechenberg e Hans-Paul Schwefel
• Estratégias de evolução
♦ 1966: Fogel, Owens e Walsh
Histórico
♦ 1966: Fogel, Owens e Walsh
• Programação evolucionária
♦ 1975: John Holland
• 1º livro sobre AG: “Adaptação em Sistemas Naturais e 
Artificiais”
♦ 1992: John Koza
• Programação genética
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 66
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
♦♦ Inteligência ComputacionalInteligência Computacional
• Área da ciência que busca, através de técnicas inspiradas na
Natureza, o desenvolvimento de sistemas inteligentes que 
imitam aspectos do comportamento humano, tais como: 
Introdução
imitam aspectos do comportamento humano, tais como: 
aprendizado, percepção, raciocínio, evolução e adaptação.
Método probabilista de busca para resolução de problemas 
(otimização) “inspirado” na teoria da evolução.
Técnica Inspiração
Redes Neurais Neurônios biológicos
Algoritmos Genéticos Evolução biológica
Lógica Fuzzy Processamento lingüístico
Sistemas Especialistas Inferência lógica
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 77
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Computação Computação evolucionáriaevolucionária
� É o nome genérico dado à métodos computacionais
inspirados na teoria da evolução.
Introdução
� Os algoritmos usados em computação evolucionária
se chamam de Algoritmos Evolucionários (AE)
[barreto96].
♦ Variantes: 
• Algoritmos genéticos 
• Programação evolucionária
• Estratégias evolucionárias
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 88
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Computação Computação evolucionáriaevolucionária
♦ Método probabilista de busca para resolução de problemas 
(otimização) “inspirado” na teoria da evolução;
♦ Utilizam o princípio de seleção natural para resolver 
Introdução
♦ Utilizam o princípio de seleção natural para resolver 
problemas de otimização “complicada”;
♦ Inventados por John Holland (1975), da Universidade de 
Michigan.
♦ Variantes: 
• Algoritmos genéticos 
• Programação evolucionária
• Estratégias evolucionárias
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 99
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Porque a evolução é uma boa metáfora?Porque a evolução é uma boa metáfora?
♦ Muitos problemas computacionais ...
• ... envolvem busca através de um grande número de 
possíveis soluções
Introdução
possíveis soluções
• ... requerem que o programa seja adaptativo, apto a agir em 
um ambiente dinâmico
♦ A evolução biológica é ...
• ... uma busca massivamente paralela em um enorme espaço 
de problema
• soluções desejadas ≡ organismos mais adaptados
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 1010
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Exemplo de implementação de um AE simples
� Inicialize uma população aleatória de indivíduos;
� Avalie o fitness de todos os indivíduos da
população;
� Teste o critério de encerramento, ou seja, por
exemplo, tempo, fitness, etc., Até alcançá-lo,
enquanto isso faça:
- Incrementar o contador de tempo;
- Formar descendentes usando alguma
forma de pertubação;
- Calcular um novo fitness;
- Enumere sobreviventes.
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 1111
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica–––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Base Biológica
� Charles Darwin e Alfred Russel Wallace 
foram os precursores, através de suas 
evidências para a teoria de evolução, em 
1858.1858.
� TEORIA DE EVOLUÇÃO:
� Alguns indivíduos são melhores do que os
outros.
� Aqueles que são melhores estão mais
habilitados a sobreviver e propagar sua carga
genética.
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 1212
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 1313
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Reprodução Assexuada
� Na reprodução assexuada, não há diferença
genética entre seres da mesma espécie, no que se
refere ao seu papel na reprodução.
� Dois seres geneticamente equivalentes se unem,
trocam material genético entre seus cromossomos
(cruzamento ou crossover) e se reproduzem,
resultando em cromossomos filhos que tem um
material genético que é combinação dos materiais
dos dois progenitores.
� Este processo é o que é imitado pela maioria dos
AE.
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 1414
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Diversidade
� Quanto a evolução biológica, esta exige
diversidade.
� Na natureza, a diversidade deriva, no caso
dos seres que se utilizam da reprodução
assexuada, de mutações, enquanto que no
caso de reprodução sexuada, a cada
reprodução.
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 1515
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Algoritmos Genéticos (AG)
� Foram desenvolvidos inicialmente por John H. Holland, em
1975, no trabalho intitulado como Adaption in Natural and
Artificial Systems.
� Holland inspirou-se no mecanismo de evolução das� Holland inspirou-se no mecanismo de evolução das
espécies e na genética natural.
� De acordo com a Teoria Darwiniana de evolução das
espécies, uma população sujeita a um ambiente qualquer,
sofrerá influências desse, de tal forma que os mais
adaptados terão maior probabilidade de sobreviver a tal
ambiente.
� A cada geração haverá uma população mais adaptada ao
ambiente em questão [Silva95].
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 1616
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
DefiniçãoDefinição dede AGAG (I)(I)
�AG constituem uma técnica de 
busca, inspirada no processo de busca, inspirada no processo de 
evolução dos seres vivos, baseada 
na seleção natural de Darwin. 
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 1717
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Definição de AG (II)
� Uma das definições de AG, tomada como base, é referida por
J.J. Grefenstette [Grefenstette86], como sendo um
procedimento iterativo que mantém uma população de
estruturas (chamadas indivíduos ou string), que representam
possíveis soluções de um determinado problema.possíveis soluções de um determinado problema.
� A cada incremento temporal (chamado geração), os
indivíduos na população atual são avaliados de acordo com o
valor de seu fitness para solução de problema.
� Tendo como base essa avaliação, uma nova população de
soluções candidatas é formada utilizando Operadores
Genéticos (GO) específicos, tais como crossover e mutação.
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 1818
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Destacam-se:
�Simplicidade de operação;
�Facilidade de implementação; �Facilidade de implementação; 
�Eficácia na busca da região onde, provavelmente, 
encontra-se o máximo global;
�Aplicável em situações onde não se conhece o 
modelo matemático ou este é impreciso e, 
também, em funções lineares e não lineares.
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 1919
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Considerações
�Os valores que influenciam o desempenho 
de um algoritmo genético são: 
�tamanho da população;
�taxa de operadores;
�intervalo de geração;
�seleção de estratégia.
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 2020
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Busca e Otimização
�Os algoritmos genéticos podem ser 
enquadrados em grande parte dos 
problemas científicos a serem formulados 
como problemas de busca e otimização.como problemas de busca e otimização.
�O objetivo é encontrar a melhor combinação 
dos fatores que proporcione o melhor 
desempenho possível para o sistema em 
questão. 
�Esse conjunto de todas as combinações é 
chamado de espaço de busca. 
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 2121
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Busca e Otimização
� Todo problema de busca pode ser 
considerado um problema de otimização e 
vice-versa.
� Os algoritmos usam o conceito de 
probabilidade, mas não são buscas 
aleatórias, pois tentam direcionar para 
regiões onde é provável que a solução 
esteja.
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 2222
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Métodos de Resolução
Programação Dinamica
Metodos Exatos
Heuristicas Meta-Heuristicas Especiais
Metodos Aproximados
Metodos de Resolução
Programação Dinamica
Branch-and-Bound
Branch-and-Cut
Branch-and-Price
Outros
Gulosa (Greedy)
Melhoria
Construção
Particionamento
Decomposição
Form. Matematica
Relaxação
Heuristicas
Algoritmos Geneticos
Simulated Annealing
Busca Tabu
GRASP
Meta-Heuristicas
Times Assincronos
Logica Fuzzy
Redes Neurais
Especiais
♦♦Profa. Lourdes Brasil Profa. Lourdes Brasil --AGAG-- 2323
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Complexidade e o cérebro humano
�� ComputadoresComputadores estãoestão próximospróximos da da potênciapotência
do do cérebrocérebro humanohumano??
�� Chip de Chip de computadorcomputador correntecorrente (CPU):(CPU):
� 10^3 pinos de entrada
� 10^7 elementos de processamento� 10^7 elementos de processamento
� 2 entradas por elemento de processamento (fan-in = 2)
� elementos de proc. computam lógica booleana (OR, 
AND, NOT, etc)
�� TTíípicopico cérebrocérebro humanohumano::
� 10^7 entradas (sensores)
� 10^10 elementos de processamento (neurônios)
� fan-in = 10^3
� elementos de processamento computam funções
complicadas
♦Ainda precisa um monte de melhorias para computadores; mas Um 
cluster de computadores chega perto☺! Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 2424
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Computação Evolutiva (ou evolucionária): Um Novo 
Paradigma Para a Resolução de Problemas Complexos
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 2525
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
MotivaçãoMotivação
� AG são eficientes métodos de otimização e 
planejamento inspirados na natureza 
baseados nos princípios da evolução 
natural e genética.natural e genética.
� Devido a sua eficiência e simples princípios, 
estes métodos são usados em uma 
variedade de problemas de otimização e 
aprendizado de máquina. 
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 2626
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Ambientação
♦Modelo
♦Teoria de 
Computação 
Evolucionária
♦Modelo
♦Computa-
♦cional
♦Natureza
♦Modelo
♦Biológico
♦Teoria de Darwin
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 2727
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Conceitos 
BIOLOGIA AG
CROMOSSOMO INDIVÍDUO (STRING)
GENE BIT
LOCUS POSIÇÃO DE UM BIT
ESPECÍFICO NOConceitos fundamentais ESPECÍFICO NO
INDIVÍDUO
ALELO VALOR DE BIT
GENÓTIPO INDIVÍDUO
CANDIDATO À
SOLUÇÃO - X
FENÓTIPO VALOR DA FUNÇÃO
PARA UM DADO
INDIVÍDUO - f(x)
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 2828
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Conceitos Fundamentais
� Um indivíduo (estrutura, elemento) é definido por uma 
string, que é formada por um alfabeto finito. 
� Cada posição dessa string representa um gene, e cada 
gene tem seu local fixo no cromossomo, que é gene tem seu local fixo no cromossomo, que é 
chamado de locus. O conjunto de valores que cada 
gene pode assumir é chamado de alelo.
� Em Algoritmos Genéticos: gene=bit ; locus=posição do 
bit na string.
� O conjunto de indivíduos é chamado de população.
� A função a ser otimizada é o ambiente no qual a 
população inicial vai ser posta.
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 2929
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
GRAU DE APTIDÃO
� O grau de fitness (aptidão) de cada indivíduo é 
obtido pela avaliação de tal indivíduo através 
da função a ser otimizada. 
SELEÇÃOSELEÇÃO
♦ROLETA PONDERADA
Elemento Nota Nota Acumulada
X3 5 5
X2 4 9
X1 3 12
X4 2 14
X5 1 15
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 3030
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Representação gráfica da roleta ponderada
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 3131
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Operadores Genéticos (Mecanismos de 
Busca)
�Crossover�Crossover
�Mutação
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 3232
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Operadores GenéticosOperadores Genéticos
CrossoverCrossover
♦O crossover combina características de duas 
estruturas pais para formar dois descendentes 
similares.similares.
♦O operador crossover seleciona uma localização 
randômica na string genética dos pais (essa 
localização é chamada de ponto de crossover) e 
concatena o segmento inicial de um pai com o 
segmento final do segundo pai. Um segundo filho 
é gerado da mesma forma, com os segmentos 
restantes.
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 3333
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Operadores GenéticosOperadores Genéticos
CrossoverCrossover
♦ O operador crossover mais simples é chamado crossover de 
um ponto, onde um primeiro local de cruzamento 
cruzamento é escolhido com probabilidade uniforme sobre o 
comprimento do cromossomo, então, as stringscomprimento do cromossomo, então, as strings
correspondentes são permutadas.
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 3434
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Operadores GenéticosOperadores Genéticos
Crossover (Cruzamento - permutação)
Pais 2: 1 0 1 1 0 0 1 0 | 0 1 0 1 
1: 0 0 1 0 1 1 0 1 | 1 0 0 0
Local de cruzamento
2: 1 0 1 1 0 0 1 0 | 1 0 0 0 
1: 0 0 1 0 1 1 0 1 | 0 1 0 1
Filhos
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 3535
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
♦Crossover
Profa. Lourdes Brasil Profa. Lourdes Brasil -- RNA RNA -- 3636
♦ponto único ♦ponto duplo
Informática emSaúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
♦♦CruzamentoCruzamento
• Toma dois indivíduos e corta seus cromossomos 
em uma partição selecionada ao azar, para 
produzir os segmentos anteriores e os 
posteriores, os posteriores realizam um 
intercâmbio para obter dois novos cromossomos
Profa. Lourdes Brasil Profa. Lourdes Brasil -- RNA RNA -- 3737
intercâmbio para obter dois novos cromossomos
♦Crossover com formação de somente um indivíduo
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Operadores GenéticosOperadores Genéticos
MutaçãoMutação
♦Consiste em perturbações na cadeia dos 
cromossomos que dará origem a uma nova cadeia, 
que guardará pouca ou nenhuma informação da que guardará pouca ou nenhuma informação da 
cadeia mãe.
♦A probabilidade de mutação é geralmente mantida 
em um valor baixo para evitar a perda de um 
número grande de cromossomos bons. 
♦Dentre os principais mecanismos de mutação, 
destacam-se: troca simples, translocação, 
inversão, deleção e adição
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 3838
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Operadores GenéticosOperadores Genéticos
MutaçãoMutação
♦Em algoritmos genéticos geralmente não se usam 
adição e deleção, pois esses alteram o tamanho da 
cadeia do cromossomo.
♦A troca simples consiste de um erro de cópia de um ♦A troca simples consiste de um erro de cópia de um 
ou mais genes da cadeia.
♦A inversão consiste na retirada de um pedaço de 
código que é recolocado no mesmo local, com 
ordem inversa.
♦A translocação retira uma parte de um cromossomo 
e coloca em uma posição do mesmo cromossomo.
♦O termo mutação muitas vezes é sinônimo de troca 
simples.
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 3939
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
♦♦MutaçãoMutação
• Inversão do valor de um bit dentro de um 
string.
Profa. Lourdes Brasil Profa. Lourdes Brasil -- RNA RNA -- 4040
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Operadores GenéticosOperadores Genéticos
MutaçãoMutação
♦Troca Simples
11111111
11111011
Mutação
Ponto de
Mutação
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 4141
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Operadores GenéticosOperadores Genéticos
MutaçãoMutação
♦Inversão
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 4242
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
♦♦Critérios de paradaCritérios de parada
• Em um algoritmo genético vários parâmetros 
controlam o processo evolucionário:
◊ Tamanho da População: número de pontos do espaço de 
busca sendo considerados em paralelo
◊ Taxa de Crossover: probabilidade de um indivíduo ser 
Profa. Lourdes Brasil Profa. Lourdes Brasil -- RNA RNA -- 4343
◊ Taxa de Crossover: probabilidade de um indivíduo ser 
recombinado com outro
◊ Taxa de Mutação: probabilidade do conteúdo de cada 
posição/gene do cromossoma ser alterado
◊ Número de Gerações: total de ciclos de evolução
◊ Total de Indivíduos: total de tentativas (tamanho da 
população x número de gerações)
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
♦♦Medidas de desempenhoMedidas de desempenho
• O desempenho de um AG é medido pelo grau 
de evolução alcançado durante todo o processo 
evolucionário (experimento)
• Devido à natureza estocástica dos AGs, é 
Profa. Lourdes Brasil Profa. Lourdes Brasil -- RNA RNA -- 4444
• Devido à natureza estocástica dos AGs, é 
necessário avaliar o resultado médio de vários 
experimentos para se ter uma ideia de seu 
desempenho
• A curva média dos melhores indivíduos em 
vários experimentos apresenta o desempenho 
médio de um AG e serve para ajuste de 
parâmetros
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
AG SIMPLESAG SIMPLES (Trabalho original de (Trabalho original de HollandHolland --
1975): 1975): 
�Geração da população inicial;
Validação dos elementos da população e �Validação dos elementos da população e 
análise de convergência;
�Seleção;
�Manipulação genética.
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 4545
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Profa. Lourdes Brasil Profa. Lourdes Brasil -- RNA RNA -- 4646
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Profa. Lourdes Brasil Profa. Lourdes Brasil -- RNA RNA -- 4747
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Fluxograma de um 
AGAG
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 4848
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
ResumoResumoResumoResumo
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 4949
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Algoritmos Genéticos PopulaçãoPopulação
♦ Conjunto dos indivíduos
♦ Prováveis soluções
FitnessFitness
♦ Desempenho, aptidão
♦ avaliação de um indivíduo 
através da função a ser 
otimizada
EvoluçãoEvolução
BIOLOGIA ALGORITMOS 
GENÉTICOS
Cromosso
mo
indivíduo, oustring
Gene gene, caractere, ou bit (no EvoluçãoEvolução
♦ Geração de um nova população
SeleçãoSeleção
♦ Os mais aptos devem ter maior 
probabilidade de participar da 
nova população
Operadores GenéticosOperadores Genéticos
♦ Reprodução
♦ Mutação
ConvergênciaConvergência
♦ Ponto de otimização atingido
♦ Pouca variação na aptidões 
média
Gene gene, caractere, ou bit (no 
caso binário)
Alelo valor do gene, ou do bit (no 
caso binário)
Locus posição de um gene 
específico no indivíduo ou 
string
Genótipo estrutura, indivíduo candidato 
à seleção x
Fenótipo solução, valor da função f(x)
para um dado indivíduo
♦Profa. Lourdes Brasil - AG- 50
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Algoritmos GenéticosAlgoritmos Genéticos
 
2 : 1 0 1 1 0 0 1 0 | 1 0 0 0 
1 : 0 0 1 0 1 1 0 1 | 0 1 0 1
F ilho s
P a is 2 : 1 0 1 1 0 0 1 0 | 0 1 0 1 
1 : 0 0 1 0 1 1 0 1 | 1 0 0 0
 
INÍCIO
Gerar População
Inicial
L oc a l d e c ru z am en to
11111111
11111011
Mutação
Ponto de
Mutação
Calcular Aptidão
(fitness) para cada
Indivíduo
Verificar
Convergência
Deve parar
Evolução?
FIM
Selecionar
Membros para
Próxima
População
Aplicar Operador
de Reprodução
entre Membros
Selecionados
Aplicar Operador
de Mutação sobre
os “Filhos”
Não
Sim
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 5151
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Algoritmos Genéticos
VariaçõesVariações
População InicialPopulação Inicial
♦ Geração aleatória
♦ Geração indicada
RepresentaçõesRepresentações
♦ Dígitos binários
♦ Números reais
Operadores GenéticosOperadores GenéticosOperadores GenéticosOperadores Genéticos
♦ Com números binários
• Crossover de vários pontos, mutação por adição, deleção
♦ Com números reais
• Crossover média, média geométrica, mutação randômica, 
mutação creep
SeleçãoSeleção
♦ Elitismo
♦ Roleta
♦ Roleta Ponderada
♦ Seleção por Torneio
ConvergênciaConvergência
♦ Análise do valor máximo da função objetivo
♦ Desvio padrão
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 5252
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
� AGs diferem dos métodos tradicionais de 
busca e otimização, principalmente em 
quatro aspectos:
ConclusõesConclusões
• AGs trabalham com uma população e não com um único ponto
• AGs utilizam regras de transição probabilísticas e não 
determinísticas 
• AG é estocástico, raramente repete o mesmo desempenho em 
um experimento (fator sorte)
• Pode ser caro computacionalmente
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 5353
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Parte II - Aplicações
GeneticGenetic--Backpropagation Based Backpropagation Based 
Learning AlgorithmLearning Algorithm
(GENBACK)(GENBACK)
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 5454
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
♦ Aplicações de AG para RNA
�Treinamento de RNA (ajuste dos pesos);
�Otimização da topologia de RNA (número
de neurônios da camada intermediária);
�Geração tanto da topologia como dos
pesos das conexões.
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 5555
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
AG no aprendizado de RNA
ALGORITMO SIMPLES
1 – Criação da população inicial de pesos
para uma RNA:para uma RNA:
♦ Inicia-se com todas as redes tendo a mesma
arquitetura;
♦Cada indivíduo da população terá um conjunto de
pesos sinápticos diferente;
♦Usa-se, para a criação desta população inicial, a
distribuição uniforme ou distribuição Gaussiana;
♦Codificação da cadeia de cromossomos fixa;
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 5656
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
No entanto, neste caso, cada gene é constituído de 
um “string”: como cada gene corresponde a um 
valor de peso e este é um número real, torna-se 
necessária a codificação deste número em um 
“string”, conforme mostrado na Figura.
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 5757
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
2 – Avaliação da população e teste de 
convergência:
♦ Para esta avaliação uma função de aptidão deve ser 
escolhida. Normalmente esta função é o próprio erro 
acumulado por época para os padrões de treinamento;acumulado por época para os padrões de treinamento;
♦ Caso um indivíduo da população atual tenha atingido o erro 
esperado, considera-se que o algoritmo convergiu para uma 
solução e o treinamento termina.
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 5858
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
3 – A seguir parte-se para a criação de 
novos indivíduos:
♦ Emprega-se o AG para seleção, “crossover” e mutação.
♦ Determina-se, por conseguinte, a nova geração.
4 – Volta-se ao passo 2.
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 5959
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
AplicaçãoAplicação
� Algoritmo de aprendizado denominado 
Genetic-Backpropagation Based Learning 
Algorithm (GENBACK)
� Utilizado em um Sistema Especialista Baseado � Utilizado em um Sistema Especialista Baseado 
em Redes Neurais (Neural Networks Based 
Expert System - NNES), constituinte de um 
Sistema Especialista Híbrido (HES) de 
aplicação em domínio médico.
� Objetivo: Definição de uma topologia para a 
Rede Neural Artificial (RNA) do NNES.
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 6060
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Diagrama geral do NNESDiagrama geral do NNES
Elicitation Initial rules FuzzificationVariable treatment
(linguistic, numerical
and boolean)
Examples 1
Initial
NNES
Backpropagation
algorithm
AG optimization
of the hidden
layer
Refined
NNES
Examples 2
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 6161
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Algoritmo de AprendizadoAlgoritmo de Aprendizado
� O GENBACK utiliza Algoritmo Genético (AG) 
como uma ferramenta de auxílio na escolha da 
melhor topologia para o NNES.
� É aplicado a uma Rede Neural Artificial (RNA) � É aplicado a uma Rede Neural Artificial (RNA) 
estática, direta, com múltiplas camadas e 
contendo neurônios fuzzy do tipo E / OU.
� Baseia-se no algoritmo clássico de 
retropropagação (backpropagation) 
desenvolvido por D.E. Rumelhart et al, usado 
para o aprendizado de RNAs multi-camadas.
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 6262
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Algoritmo de AprendizadoAlgoritmo de Aprendizado
Principais características:Principais características:
♦Uso de AG para auxiliar na otimização da 
camada escondida da RNA;
♦Tratamento das variáveis de entrada da rede 
através da lógica fuzzy.
♦Uso de conectivos lógicos E /OU no local do 
somatório dos pesos
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 6363
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Algoritmo de AprendizadoAlgoritmo de Aprendizado
� O GENBACK, em seu primeiro estágio,
considera que o NNES já existe.
� Através do processo de AC, o número de� Através do processo de AC, o número de
neurônios nas camadas de entrada,
intermediária e de saída da RNA inicial é
determinado.
� A estrutura desta RNA depende dos neurônios
serem fuzzy ou abruptos (0 ou 1).
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 6464
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Algoritmo de AprendizadoAlgoritmo de Aprendizado
� O número de neurônios na camada de entrada
corresponde aos possíveis sintomas.
� O número de neurônios na camada de saída
corresponde aos possíveis diagnósticos.corresponde aos possíveis diagnósticos.
� A camada intermediária (da rede inicial) possui
a quantidade de neurônios correspondente ao
número de regras iniciais adquiridas no
processo de AC.
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 6565
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Algoritmo de AprendizadoAlgoritmo de Aprendizado
�� OO GENBACKGENBACK usausa oo conjuntoconjunto dede exemplosexemplos parapara realizarrealizar
modificaçõesmodificações nosnos pesospesos dasdas conexõesconexões ee nana estruturaestrutura dada rederede..
�� AtravésAtravés dada aplicaçãoaplicação dede AGAG::
� Conexões que podem não estar na RNA inicial, são incluídas
ou excluídas entre os neurônios.ou excluídas entre os neurônios.
� Neurônios podem ser incluídos ou excluídos da camada
intermediária da rede.
�� DestaDesta forma,forma, oo algoritmoalgoritmo podepode produzirproduzir maismais conceitosconceitos queque
nãonão existiamexistiam nono conjuntoconjunto inicialinicial dede regrasregras e,e,
conseqüentementeconseqüentemente,, podepode deduzirdeduzir regrasregras queque oo especialistaespecialista
médicomédico nãonão foifoi capazcapaz dede articulararticular..
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Algoritmo de AprendizadoAlgoritmo de Aprendizado
AG foi escolhido para otimizar o tamanho da camada AG foi escolhido para otimizar o tamanho da camada 
intermediária de uma dada RNA, o que pode ser intermediária de uma dada RNA, o que pode ser justificado justificado 
pelos seguintes fatos: pelos seguintes fatos: 
♦ evitar o ótimo local;
♦ experimentar soluções de otimização próximas ao ótimo 
global;global;
♦ ser de fácil implementação.
Alguns cuidados a serem tomados em relação ao nº de neurônios Alguns cuidados a serem tomados em relação ao nº de neurônios 
a serem colocados na camada intermediária:a serem colocados na camada intermediária:
♦ muitos neurônios geralmente têm como efeito reduzir a 
capacidade de generalização da rede. Isto implica em uma 
longa fase de aprendizado;
♦ por outro lado, com pouquíssimos neurônios, a rede pode não 
aprender a tarefa com a precisão desejada
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 6767
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Etapas do GENBACK
1.1. CriaçãoCriação dosdos indivíduosindivíduos dada populaçãopopulação.. UsoUso dada distribuiçãodistribuição
GaussianaGaussiana;;
2.2. CodificaçãoCodificação dada cadeiacadeia dede cromossomoscromossomos.. UsoUso dede umauma cadeiacadeia fixafixa
dede 88 bitsbits;;
3.3. TreinamentoTreinamento,, baseadobaseado nono backpropagationbackpropagation;;
4.4. AvaliaçãoAvaliação utilizandoutilizando asas funçõesfunções dede aptidãoaptidão (fitness)(fitness)::4.4. AvaliaçãoAvaliação utilizandoutilizando asas funçõesfunções dede aptidãoaptidão (fitness)(fitness)::
F1 = NCH/ERROR
F2 = 1/NCH + ERROR
onde F1 e F2 são as funções de fitness, NCH = nº de neurônios
na camada intermediária da rede, ERROR = erro na saída da
rede;
5.5. AplicaçãoAplicação dodo processoprocesso dede roletaroleta ponderadaponderada;;
6.6. OrdenaçãoOrdenação dosdos indivíduosindivíduos dada populaçãopopulação;;
7.7. AplicaçãoAplicação dosdos operadoresoperadores dede seleçãoseleção,, crossovercrossover ee mutaçãomutação;;
8.8. NovaNova geraçãogeração;;
9.9. RepetiçãoRepetição do do passopasso 3 3 atéaté obtermosobtermos a a rederede vencedoravencedora
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 6868
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Considerações p/ o GENBACK
Condição de parada:
♦ A parada do processo de utilização de AG é realizada pelo 
número de gerações, podendo ter opção por convergência
Nova população:
♦ Nas gerações subseqüentes pode ter ocorrido o surgimento 
de novos indivíduos que não sofreram mutação e/ou de novos indivíduos que não sofreram mutação e/ou 
crossover.
♦ Nesta etapa guardam-se os pesos, os erros e o número de 
épocas de cada rede gerada. 
♦ Os novos indivíduos são treinados até o número de épocas 
pré-determinado, desde a primeira geração até a atual, 
enquanto aqueles que foram inalterados são treinados 
apenas em relação ao nº de épocas naquela geração.♦ Resultado: RNA otimizada e treinada.
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 6969
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Diagrama geral do NNESDiagrama geral do NNES
Elicitation Initial rules Fuzzification
Variable treatment
(linguistic, numerical
and boolean)
Examples 1
Initial
NNES
Backpropagation
algorithm
AG optimization
of the hidden
layer
Refined
NNES
Examples 2
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 7070
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
AG na otimização do número de neurônios na 
camada intermediária
ALGORITMO GENBACK GENERALIZADO
1 – Criação da população inicial de RNA:1 – Criação da população inicial de RNA:
♦ Inicia-se com todas as redes tendo o mesmo número
de neurônios de entrada e de saída;
♦Cada indivíduo (RNA) da população terá um número
diferente de neurônios na camada intermediária;
♦Usa-se, para a criação desta população inicial, a
distribuição uniforme ou distribuição Gaussiana;
♦Codificação da cadeia de cromossomos fixa.
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 7171
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
2 – Treinamento da RNA: treina-se cada rede 
utilizando um algoritmo tipo “Backpropagation” 
para o mesmo número de épocas:
♦A partir da segunda geração, as redes novas devem 
ser treinadas para um número de épocas igual ao total ser treinadas para um número de épocas igual ao total 
de todas as iterações deste algoritmo.
3 – Avaliação da melhor topologia de rede:
♦Uma função de aptidão deve ser escolhida.
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 7272
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
4 – A seguir parte-se para a criação de novos 
indivíduos:
♦Emprega-se o AG para seleção, “crossover” e 
mutação;
♦Determina-se, por conseguinte, a nova geração;♦Determina-se, por conseguinte, a nova geração;
♦Este processo é repetido até que o conhecimento da 
solução do ótimo global seja descoberto, ou até algum 
critério de parada, por exemplo, o número de 
gerações.
5 – Volta-se ao passo 2.
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 7373
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
PERSPECTIVAS FUTURASPERSPECTIVAS FUTURAS
AG PARA APRENDIZADO DA RNA E AG PARA APRENDIZADO DA RNA E 
OTIMIZAÇÃO DA CAMADA OTIMIZAÇÃO DA CAMADA OTIMIZAÇÃO DA CAMADA OTIMIZAÇÃO DA CAMADA 
INTERMEDIÁRIA.INTERMEDIÁRIA.
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 7474
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Exemplos de Aplicações Reais 
� Projeto de Antenas
� Projeto de Drogas
�Projeto de Sistemas de 
Controle� Projeto de Drogas
� Classificação Química
� Circuitos Elétricos
� Escalonamento de Fabricas 
(Volvo, Deere, outras)
� Projeto de Turbina
� Projeto de Carros 
“Crashworthy”
� Projeto de Redes
Controle
�Parâmetros de Produção
�Projeto de Satélite
� Stock/commodity/ analises/ 
tendências
�Ajuste de Celulares
� Data Mining
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 7575
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Detecção de contornos
♦Original♦VND
♦VND paralelo A
♦VND paralelo B
♦Variable Neighborhood Search (VNS) Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 7676
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Bibliografias
• M. R. Garey and D. S. Johnson. Computers and 
Intractability: a Guide to the Theory of NP 
Completeness. Freeman, 1979. 
• Richard Karp. NP-Complete Problems. Tutorial em 
video, 1993. 
• David Harel. Algorithmics- The Spirit of Computing. 
Addison-Wesley 1987.
• http://professor.webizu.org/ga/
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 7777
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Bibliografias
• ENCORE, the EvolutioNary COmputation REpository network, Rede Repositório de 
Computação Evolucionária
ftp://alife.santafe.edu/pub/USER-AREA/EC/ (tem também alguns outros nós)
• FAQ - The Hitch-Hiker's Guide to Evolutionary Computation
O guia Hitch-Hiker sobre Computação EvolucionáriaO guia Hitch-Hiker sobre Computação Evolucionária
ftp://alife.santafe.edu/pub/USER-AREA/EC/FAQ/www/index.html
• FAQ - Genetic programming
Perguntas mais freqüentes sobre Programação Genética
http://www-dept.cs.ucl.ac.uk/research/genprog/gp2faq/gp2faq.html
• The Genetic Algorithms Archive - many links, information about mailing list, some fun 
stuff
Arquivo de Algoritmos Genéticos - vários links, informações sobre listas, e algum material 
divertido
http://www.aic.nrl.navy.mil:80/galist/
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 7878
Informática em Saúde Informática em Saúde Informática em Saúde Informática em Saúde 
Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica Engenharia Eletrônica –––– Instrumentação BiomédicaInstrumentação BiomédicaInstrumentação BiomédicaInstrumentação Biomédica
Bibliografias
• Artificial Life Online - Vida Artificial Online - links.
Se você está procurando por material introdutório, veja aqui
http://alife.santafe.edu/
• Yahoo! Science:Computer Science:Algorithms:Genetic
Algorithms - diretório de outros links
http://www.yahoo.com/Science/Computer_Science/Algorithms/Gene
tic_Algorithms/
• Grupos Usenet comp.ai.genetic e comp.ai.alife
Profa. Lourdes Brasil Profa. Lourdes Brasil -- AGAG-- 7979