Inteligência Artificial (aula 5)

Inteligência Artificial (aula 5)

1. Método Heurístico

   • O Método Heurístico também é conhecido como Resolução de Problemas.Este método tem o objetivo de encontrar soluções para um determinado problema.
     • Com a utilização de um método heurístico busca-se a simplificação de um problema complexo, como por exemplo repartindo-o em pequenas partes.

2. Algoritmo Genético

   • O algoritmo genético -> Método de otimização
     • Criado por John Henry Holland em 1975
       • Esse algoritmo segue a teoria evolucionária de Charles Darwin.
         • O algoritmo genético trabalha com a lógica da seleção natural que segue a teoria da evolução.
           • O algoritmo genético é classificado como um método meta-heurístico para otimização. É bastante usado para lugares que necessitam de métodos de otimização.
   • Requisitos para implementação do Algoritmo Genético:
     • Ter uma solução que seja possível usar código genético.
       • População Inicial
         • Tem que ser bem diversificado, permitindo que exista combinação das características para gerar novos indivíduos.
         • Conter um modo de avaliar os indivíduos
           • Realizar o cruzamento de dois indivíduos da população, gerando filhos. (NOVA POPULAÇÃO)
             • Possuir um modo de selecionar os indivíduos que continuarão na população.
               • Uma forma de realizar modificações nos indivíduos.
         • Seleção
           • Escolher os elementos da população que participarão do processo de reprodução
             • Selecionar os pais dos indivíduos que estarão presentes na nova população.
               • Esta escolha deve ser feita de tal forma que os membros da população mais adaptados ao meio ambiente, tenham maior chance de reprodução.
                 • Os que apresentam um valor da função necessário mais elevado.
                   • Desta forma quem tem mais pontuação recebe uma porção maior. A roleta é girada varias vezes, selecionando a quantidade de acordo com o tamanho da população.
                 • Esta porção é proporcional a pontuação do indivíduo.
               • Cada indivíduo ocupa uma porção da roleta
             • Seleção de Monte Carlo ou seleção por roleta
           • Cruzamento
             • Combinar os cromossomos dos pais para gerar os cromossomos dos filhos
               • Há vários tipos de operadores de cruzamento: alguns mais genéricos, outros mais personalizados.
                 • Cruzamento em um ponto
                   • Dividi os pais selecionados num ponto aleatório.
                     • Depois é realizado a combinação para gerar os filhos.
             • Mutação
               • Realiza inserção de pequenas mudanças aleatórias nos filhos.
                 • Há vários tipos de mutação, um deles é o mutação de bit.
                   • Mutação de bit
                     • Cada bit recebe um número aleatório (com algumas casas decimais), e é realizado aleatoriamente qual será o novo bit 0,1 ou sem alteração.
                       • Então a posição que recebeu a menor posição tem seu bit alterado pelo bit designado aleatoriamente.

3. Busca em Espaço de Estados

   • O que é busca?
     • Encontrar algo, um objetivo.
       • O domínio tem um conjunto de estados (algumas vezes este conjunto é infinito)
         • Cada “etapa” é chamado de estados.
           • Há transições entre os estados do domínio (grafo).
             • Aplica-se algoritmos para encontrar um caminho no grafo
               • partindo do estado inicial (atual)
                 • até o estado final (objetivo)
               • Operador: transforma um estado em outro
           • É praticamente impossível de modelar todas as informações do mundo real
             • O estado é usado para abstrair os detalhes, levando em conta só o que é importante para a solução do problema.
               • O estado é usado para abstrair os detalhes, levando em conta só o que é importante para a solução do problema.
                 • Estado: determinada configuração das peças
                   • Estado inicial: Como o problema se inicia, pode ser de forma aleatória // Estado final: Objetivo a ser atingido
                     • Representação:
                       • Estado inicial: [2,8,3,1,0,4,6,7,5]
                         • Estado objetivo: [1,2,3,4,5,6,7,8,0]
                           • descrição dos operadores: [2,8,3,1,0,4,6,7,5]  [2,8,3,1,7,4,6,0,5] para baixo
                       • por Grafos
                         • Os nós representam um estado
                           • Os arcos representam os operandos
                             • Métodos de busca -> grafos de estado: Percorre-se o grafo até encontrar o estado objetivo
                               • Tipos de busca: busca “cega” (sistemática), busca heurística
                                 • Busca em largura ou amplitude
                                   • Aplica-se todos os operadores possíveis para cada estado (busca por nível)
                                 • A busca não é cega, mas sim por meio de informações que auxiliam a seleção dos operadores
                                   • busca heurística -> em cada etapa a escolha é baseada em informações, ou seja, a escolha se dá pelo “melhor” nó existente. Essa escolha leva em conta a função de avaliação (custo de se chegar a solução), quanto menor o valor, melhor é a função de avaliação.
                               • Busca em extensão: análise
                                 • Completa: sempre encontra o objetivo que esteja em uma profundidade d (desde que a ramificação b seja finito);
                                   • Ótima?? O nó objetivo mais raso não é necessariamente o nó ótimo
                                 • Busca em Profundidade
                                   • Ao invés de realizar primeiro a análise “horizontal”, é feito a análise “vertical”, ou seja, percorre os nós na direção das folhas.
                                     • Busca em profundidade: análise -> Só precisa armazenar um único caminho da raiz até um nó folha, e os nós irmãos não expandidos.
                                       • Nós cujos descendentes já foram completamente explorados podem ser retirados da memória.
                                         • Portanto, a busca em profundidade não é completa e nem ótima!
                                   • Busca em profundidade limitada
                                     • Para resolver o problema de busca em profundidade em árvores infinitas, um limite n restringe a busca.
                                       • Esses nós na profundidade n são tratados como se não tivessem sucessores. Resolve caminhos infinitos, porém adiciona mais incompleteza.
   • Agente orientado a objetivo
     • Não há uma determinação do mapeamento entre percepções e ações, mas uma determinação do objetivo que o agente deve conseguir
       • O próprio agente “constrói” as ações para atinjir o objetivo. Ex: Motoboy, Aspirador de pó...
   • Redução de problema
     • A utilização de redução de problemas realiza a segmentação deste problema
       • Desta forma ficam subproblemas que também são segmentados em novos subproblemas.
         • Esta segmentação serve para que se atinja resoluções imediatas e simples.
           • Representação para solução por redução de problemas
             • Etapas: Descrição do problema, Reduzir em subproblemas, Descrição dos subproblemas (solução)
   • Critérios de comparação entre os algoritmos
     • Completo: o algoritmo encontra a solução se ela existir // Ótimo : o algoritmo encontra a solução de menor custo // Tempo: quanto tempo o algoritmo leva para encontrar a solução no pior caso // Espaço: quanto de memória o algoritmo ocupa