Click here to load reader

Projeto e Análise de Algoritmos Projeto de Algoritmoshumberto/disciplinas/2011_1_paa/aulas/... · Projeto e Análise de Algoritmos Projeto de Algoritmos Heurísticas e Algoritmos

  • View
    213

  • Download
    0

Embed Size (px)

Text of Projeto e Análise de Algoritmos Projeto de Algoritmoshumberto/disciplinas/2011_1_paa/aulas/... ·...

  • Projeto e Anlise de Algoritmos

    Projeto de AlgoritmosHeursticas e Algoritmos Aproximados

    Prof. Humberto Brando

    [email protected]

    Universidade Federal de Alfenas

    Departamento de Cincias Exatas

    verso da aula: 0.4

    mailto:[email protected]:[email protected]:[email protected]

  • Problemas

    Problemas que podem ser resolvidos por: algoritmos polinomiais so considerados fceis,

    enquanto problemas que no podem ser resolvidos por algoritmos polinomiais so considerados difceis;

    Problemas considerados difceis ou intratveis so comuns; Problema da Mochila;

    Problema do Caixeiro Viajante;

    Problema de Cobertura de Conjuntos

  • Problemas

    Diante de um problema difcil, temos trs possibilidades:

    Tratar o mesmo com algoritmos que so timos;

    So chamados de algoritmos exatos;

  • Problemas

    Diante de um problema difcil, temos trs possibilidades:

    Tratar o mesmo com algoritmos que so timos;

    So chamados de algoritmos exatos;

    Ou tratar com algoritmos que chegam prximo ao timo;

    Neste caso a distncia mxima estabelecida;

    So os algoritmos aproximados;

  • Problemas

    Diante de um problema difcil, temos trs possibilidades:

    Tratar o mesmo com algoritmos que so timos;

    So chamados de algoritmos exatos;

    Ou tratar com algoritmos que chegam prximo ao timo;

    Neste caso a distncia mxima estabelecida;

    So os algoritmos aproximados;

    Ou tratar com algoritmos que tentam aproximar do timo;

    No existe garantia alguma de que a soluo encontrada possui qualidade;

    So chamados de algoritmos heursticos;

  • Problemas

    importante para o projetista/analista conhecer uma grande quantidade de problemas clssicos e seus algoritmos eficientes;

  • Problemas

    importante para o projetista/analista conhecer uma grande quantidade de problemas clssicos e seus algoritmos eficientes;

    Isso ajudar a resolver problemas gerais encontrados em qualquer software a ser desenvolvidos;

  • Problemas

    importante para o projetista/analista conhecer uma grande quantidade de problemas clssicos e seus algoritmos eficientes;

    Isso ajudar a resolver problemas gerais encontrados em qualquer software a ser desenvolvidos;

    Para muitos destes problemas conhecemos solues polinomiais;

    Embora para alguns deles tal soluo no facilmente visualizada por um leigo no problema;

  • Problemas

    importante para o projetista/analista conhecer uma grande quantidade de problemas clssicos e seus algoritmos eficientes;

    Isso ajudar a resolver problemas gerais encontrados em qualquer software a ser desenvolvidos;

    Para muitos destes problemas conhecemos solues polinomiais;

    Embora para alguns deles tal soluo no facilmente visualizada por um leigo no problema;

    Identificando qual o problema a ser tratado no software, o analista chega em duas opes;

    Quais so?

  • Problemas

    Duas opes possveis:

    Ou existe algoritmo polinomial conhecido;

    Ou no existe;

    O que fazer em ambos os casos?

  • Problemas

    O que fazer em ambos os casos?

    Se existe, pode ser que o polinmio de grau baixo;

    O analista pode implementar o algoritmo conhecido;

  • Problemas

    O que fazer em ambos os casos?

    Se existe, pode ser que o polinmio de grau baixo;

    O analista pode implementar o algoritmo conhecido;

    Mas e se o polinmio de grau elevado?

    Em grafos, alguns problemas giram na casa de O(n15);

  • Problemas

    Se o algoritmo mais eficiente conhecido exponencialexiste uma pergunta a ser feita:

    Qual a pergunta que o analista deve se fazer?

  • Problemas

    Se o algoritmo mais eficiente conhecido exponencialexiste uma pergunta a ser feita:

    Qual o tamanho do problema a ser resolvido?

  • Problemas

    Se o algoritmo mais eficiente conhecido exponencialexiste uma pergunta a ser feita:

    Qual o tamanho do problema a ser resolvido?

    Se sempre for pequeno, um algoritmo exponencial pode ser implementado;

  • Problemas

    Se o algoritmo mais eficiente conhecido exponencialexiste uma pergunta a ser feita:

    Qual o tamanho do problema a ser resolvido?

    Se sempre for pequeno, um algoritmo exponencial pode ser implementado;

    Se for de mdio porte, alguns algoritmos exponenciais adaptados podem ser utilizados; Como o backtracking com forward-checking com propagao de

    restries;

  • Problemas

    Se o algoritmo mais eficiente conhecido exponencialexiste uma pergunta a ser feita:

    Qual o tamanho do problema a ser resolvido?

    Se sempre for pequeno, um algoritmo exponencial pode ser implementado;

    Se for de mdio porte, alguns algoritmos exponenciais adaptados podem ser utilizados; Como o backtracking com forward-checking com propagao de

    restries;

    Se for de grande porte... O que fazer???

  • Problemas

    Se for de grande porte... O que fazer???

    Neste caso, os algoritmos exatos so inviveis;

  • Problemas

    Se for de grande porte... O que fazer???

    Neste caso, os algoritmos exatos so inviveis;

    A alternativa empregada so as heursticas;

  • Problemas

    Se for de grande porte... O que fazer???

    Neste caso, os algoritmos exatos so inviveis;

    A alternativa empregada so as heursticas;

    Existem meta-algoritmos, que so chamados de meta-heursticas;

  • Problemas

    Meta-heursticas no assumem caractersticas do problema;

    As heursticas assumem;

    Exemplos de meta-heursticas:

    Algoritmos Evolucionrios;

    Algoritmo Gentico;

    Programao Gentica;

    Estratgia Evolucionria;

    Programao Evolucionria;

    Simulated Annealing; (recozimento simulado)

    Busca Tabu;

    Colnia de Formigas;

    Otimizao por Enxame de Partculas;

  • Algoritmos Genticos

  • Antes de explicar AGs...

    Tcnica Inspirao

    Redes Neurais Neurnios Biolgicos

    Sistemas Especialistas Inferncia Humana

    Lgica Fuzzy Proc. Lingstico

    Algoritmos Genticos Evoluo Natural

  • Evoluo natural

    Qual borboleta est mais adaptada ao ambiente?

  • Evoluo natural

    Qual animal est mais adaptado ao ambiente?

  • Evoluo natural

    Qual das 6 solues est mais adaptada ao problema de roteamento de veculos?

    C1

    C0

    C2

    C5

    C3

    C4

    C1

    C0

    C2

    C5

    C3

    C4

    C1

    C0

    C2

    C5

    C3

    C4

    C1

    C0

    C2

    C5

    C3

    C4

    C1

    C0

    C2

    C5

    C3

    C4

    C1

    C0

    C2

    C5

    C3

    C4

  • Sink mvel em uma Rede de Sensores sem Fio (RSSF)

    Um problema de exemplo...

  • Soluo inicia vs Soluo Final

    Evoluo natural... de solues

  • Evoluo

    Ambiente

    Indivduo

    Fitness - Adaptabilidade

    Relacionando Evoluo Natural com AG

    Resolvendo um problema

    Problema

    Soluo Candidata

    Qualidade da soluo

    Fitness chance do indivduo sobreviver e reproduzir

  • Algoritmos Genticos

    Desenvolvido: EUA na dcada de 70.

    Primeiros pesquisadores: J. Holland, K. DeJong, D. Goldberg

    Aplicado tipicamente na rea de: Otimizao discreta

    Caractersticas: No muito rpido

    Bom comportamento em problemas combinatrios

    Caractersticas especiais: nfase tradicional na combinao de informaes de bons pais

    (crossover)

    Muitas variantes, por exemplo, modelos populacionais, operadores, ...

  • Algoritmos Genticos

    O AG original de Holland atualmente conhecido como Algoritmo Gentico Simples - AGS);

  • Algoritmos Genticos

    O AG original de Holland atualmente conhecido como Algoritmo Gentico Simples - AGS);

    Outros algoritmos genticos utilizam diferentes:

    Representaes

    Mutaes

    Cruzamentos

    Mecanismos de seleo

  • Algoritmos Genticos

    O AG original de Holland atualmente conhecido como Algoritmo Gentico Simples - AGS);

    Outros algoritmos genticos utilizam diferentes:

    Representaes

    Mutaes

    Cruzamentos

    Mecanismos de seleo

    Isso por que AG so gerais.

    Quando so instanciados as variaes aparecem devido a natureza dos problemas.

  • Esquema geral de um AE

  • Pseudo-cdigo

  • AGS

    Representao String binria

    Recombinao Corte de n pontos ou uniforme

    Mutao Mudana de bits com probabilidade

    fixa.

    Seleo de pais Proporcional ao fitness

    Seleo de sobreviventes Filhos substituem pais

    Detalhe nfase no cruzamento

  • Algoritmo GenticoRepresentao: String binria

    Espao do gentipo = {0,1}LEspao do fentipo

    codificao

    decodificao011101001

    010001001

    10010010

    10010001

  • Algoritmo GenticoExemplo de execuo do AG

    Maximizar x Sujeito a

    x>=0

    x

  • Algoritmo GenticoExemplo de execuo do AG

    Maximizar x Sujeito a

    x>=0

    x

  • Algoritmo GenticoExemplo de execuo do AG

  • Algoritmo GenticoExemplo de execuo do AGCruzamento

  • Algoritmo GenticoExemplo de execuo do AGMutao

  • Representao de indivduosecruzamentos e mutaes

    String Binria

    Representao Inteira

    Representao de Ponto Flutuante

    Representao de Permutao

  • Representao dos indivduosString Binria

    Muitos pesquisadores/programadores escolheram esta representao erroneamente ao longo das ltimas dcadas; Como por exemplo, o exemplo anterior: max x.

  • Representao dos indivduosString Binria

    Muitos pesquisadores/programadores escolheram esta representao erroneamente ao longo das ltimas dcadas; Como por exemplo, o exemplo anterior: max x.

    Para alguns problemas, a representao mais natural: Exemplo: Satisfabilidade Booleana (SAT)

  • Representao dos indivduosString Binria

    Exemplo de problema com esta codificao:

    Inteiro 7 codificado em binrio: 0111

    Para chegarmos ao nmero 8 (que prximo de 7 na escala dos nmeros inteiros, precisamos aplicar com sucesso 4 alteraes/mutaes: 0111 1000.

  • Representao dos indivduosString Binria

    Exemplo de problema com esta codificao:

    Inteiro 7 codificado em binrio: 0111

    Para chegarmos ao nmero 8 (que prximo de 7 na escala dos nmeros inteiros, precisamos aplicar com sucesso 4 alteraes/mutaes: 0111 1000.

    Ou seja, a Distncia de Hamming entre dois inteiros consecutivos no igual a 1.

    Isso prejudicaria uma busca (processo de otimizao), por exemplo.

  • Representao dos indivduosString Binria - Mutao

    Mudana de bits: Cada bit possui uma pequena probabilidade pm de ser invertido.

  • Representao de indivduosecruzamentos e mutaes

    String Binria

    Representao Inteira

    Representao de Ponto Flutuante

    Representao de Permutao

  • Representao dos indivduosRepresentao Inteira

    Pode ser uma representao mais direta para alguns problemas:

    Por exemplo, max x.

  • Representao dos indivduosRepresentao Inteira

    Pode ser uma representao mais direta para alguns problemas:

    Por exemplo, max x.

    O indivduo pode ser visto como um array de ints.

  • Representao dos indivduosRepresentao Inteira

    Pode ser uma representao mais direta para alguns problemas:

    Por exemplo, max x.

    O indivduo pode ser visto como um array de ints.

    Facilita buscas locais. Exemplo. 3 prximo de 4, que prximo de 5, que prximo de 6...

    Isso no acontecia na representao de string binria.

  • Representao dos indivduosRepresentao Inteira

    Pode ser uma representao mais direta para alguns problemas:

    Por exemplo, max x.

    O indivduo pode ser visto como um array de ints.

    Facilita buscas locais. Exemplo. 3 prximo de 4, que prximo de 5, que prximo de 6...

    Isso no acontecia na representao de string binria.

    Pode ser utiliza na codificao de tipos enumerados:

    Exemplo: Norte, Sul, Leste, Oeste...

    Alguma relao com o PSR???

  • Representao dos indivduosRepresentao Inteira - Mutao

    Dois operadores clssicos de mutao para a representao inteira. Ambos mutacionam cada gene com uma probabilidade pm.

    Reinicio aleatrio:

    Se o gene i sofre uma mutao de reinicio aleatrio, seu valor reiniciado, retirando-o de uma distribuio uniforme:

    NovoValor U(LimiteInferior, LimiteSuperior);

  • Representao dos indivduosRepresentao Inteira - Mutao

    Incremento:

    Se o gene i sofre uma mutao de incremento, seu valor adicionado a um pequeno valor sorteado (positivo ou negativo).

    natural que este incremento saia de uma distribuio simtrica, com o seu centro em 0.

    Pode ser uma distribuio uniforme: (int)U(-x, x)

    Pode ser uma distribuio gaussiana (normal): (int)N(0, desvio);

  • Representao de indivduosecruzamentos e mutaes

    String Binria

    Representao Inteira

    Representao de Ponto Flutuante

    Representao de Permutao

  • Representao dos indivduosRepresentao de Ponto Flutuante

    Utilizada quando queremos representar valores que possuem o domnio contnuo;

    Aplicaes tambm com a meta-heurstica PSO para esta representao;

    Claro que em um computador, a continuidade limitada pela implementao no hardware, mas podemos considerar que as arquiteturas atuais oferecem uma preciso adequada para a maioria dos problemas.

    O indivduo pode ser visto como um array de double.

  • Representao dos indivduosRepresentao de Ponto Flutuante - Mutao

    Podem ser feitas as mesmas mutaes da representao inteira.

    Incremento;

    Reinicio aleatrio.

    Sem precisar truncar para inteiro, como no outro exemplo.

  • Representao de indivduosecruzamentos e mutaes

    String Binria

    Representao Inteira

    Representao de Ponto Flutuante

    Representao de Permutao

  • Representao dos indivduosRepresentao de Permutao

    Muitos problemas possuem na soluo um indivduo que necessita informar a ordem de ocorrncia de certos eventos;

    Exemplos:

    Caminho mnimo;

    Caixeiro Viajante;

    Job-shop;

    Roteamento;

    Dentre inmeros outros...

  • Representao dos indivduosRepresentao de Permutao - Mutao

    E claro que se a cidade X precisa ser visitada, e no faz sentido manter cromossomos que no possuem X na soluo do caixeiro viajante.

    Isso aconteceria se utilizssemos uma mutao de reinicio aleatrio nos genes, por exemplo.

    Portanto, precisamos descrever operadores que mantm tal estrutura(todos os elementos).

  • Representao dos indivduosRepresentao de Permutao - Mutao

    Mutao de Insero: Escolhe aleatoriamente um gene

    Escolhe aleatoriamente uma nova posio

    Efetua a troca desde gene de ordem, causando uma perturbao na seqncia dos elementos.

    Fg f

    1 5 4 3 2 6 1 5 4 6 3 2

  • Representao dos indivduosRepresentao de Permutao - Mutao

    Mutao de Mistura: Escolhe aleatoriamente um intervalo e mistura aleatoriamente os genes daquele

    intervalo.

    Fg f

    1 5 4 3 2 6 1 5 2 4 3 6

  • Representao dos indivduosRepresentao de Permutao - Mutao

    Mutao de Troca: Escolhe aleatoriamente dois genes e os troca de posio.

    1 5 4 3 2 6 1 6 4 3 2 5

    Fg f

  • Representao dos indivduosRepresentao de Permutao - Mutao

    Mutao de Inverso: Escolhe aleatoriamente um intervalo e inverte a ordem dos genes.

    Fg f

    1 5 4 3 2 6 1 6 2 3 4 5

  • Prxima aula

    Viso Geral sobre:

    Programao Gentica;

    Simulated Annealing;

    Otimizao por Enxame de Partculas;

  • Bibliografia

    EIBEN, A. E.; SMITH, J. E.; Introduction to Evolutionary Computaing; Natural Computing Series; Springer. 2003.

    ZIVIANI, N. (2007). Projeto e Algoritmos com implementaes em Java e C++. So Paulo. Editora Thomson;