Bel. Ciência da Computação (UFPI) • FACOMP & PPGCC - ICEN/UFPA • Membro do LAAI • Pesquisador de Inteligência Computacional Aplicada • Disciplinas de Fundamentos da Computação e Matemática Computacional • Desenvolvedor de Software Livre Filipe Saraiva | UFPA | 4 / 66
há um conjunto de variáveis que devem ter seus valores ajustados de forma que, submetidas a um conjunto de restrições, consigam atingir o maior (ou o menor) valor possível de uma dada função. Filipe Saraiva | UFPA | 6 / 66
capaz de vender toda a sua produção no período. O único recurso restrito é a mão de obra, cuja produtividade, juntamente com os lucros, são: • Mesa: R$ 20 de lucro, necessita-se de 3 homens/hora na montagem e 4 homens/hora no acabamento; • Banco: R$ 24 de lucro, necessita-se de 6 homens/hora na montagem e 2 homens/hora no acabamento; No total, a manufatura dispõe de 60 homens/hora para trabalhar com montagem e 32 homens/hora para trabalhar com acabamento. Filipe Saraiva | UFPA | 7 / 66
otimização, na otimização combinatória não há funções matemáticas relacionadas com os valores que as variáveis de decisão podem assumir. Na otimização linear o que temos é a combinação dos próprios elementos entre si. Filipe Saraiva | UFPA | 11 / 66
mochila de forma a maximizar seu valor?” vs Otimização Combinatória: “quais itens cabem na mochila de forma a maximizar seu valor?” Filipe Saraiva | UFPA | 12 / 66
a seguinte: “Dado um conjunto de cidades e um conjunto de estradas que ligam essas cidades, sair de alguma delas e visitar todas as demais, apenas uma vez, e voltar à cidade inicial, no menor caminho possível”. Filipe Saraiva | UFPA | 15 / 66
e as estradas como um grafo, fazendo com que o problema passe a ser encontrar o ciclo hamiltoniano mínimo. Não há um algoritmo polinomial conhecido para resolver esse problema. Portanto, para obtermos a solução ótima, é necessário listar todas as soluções possíveis. O número de soluções possíveis é (n − 1)!/2, onde n é o número de cidades. Filipe Saraiva | UFPA | 17 / 66
do Caixeiro Viajante: • Problemas de logística; • Entrega de suprimentos; • Planejamento de rotas; • Planejamento e construção de estradas; • ... Filipe Saraiva | UFPA | 19 / 66
seus respectivos pesos e valores, e uma mochila com capacidade máxima, quais itens devem ser carregados na mochila de forma a termos o maior valor possível? Filipe Saraiva | UFPA | 22 / 66
em diversos subtipos. O enunciado apresentado diz respeito ao Problema da Mochila 0-1 onde os itens podem apenas estar ou não estar na solução. No Problema da Mochila Fracionada os itens podem ser alocados como frações de um todo, o que torna o problema linear. Em outros tipos, é possível ter mais de um item do mesmo tipo na mochila. Filipe Saraiva | UFPA | 24 / 66
i e seus respectivos pesos ci e valores vi , e uma variável binária xi para representar se um dado item está (1) ou não (0) na mochila, e a capacidade máxima da mochila dada por p, a modelagem matemática do problema é dada por: Max Z = vi xi Suj. a: ci xi ≤ p Filipe Saraiva | UFPA | 26 / 66
Mochila: • Investimento de capital; • Carregamento de veículos; • Orçamento; • Resolução de alguns algoritmos de criptografia; • ... Filipe Saraiva | UFPA | 27 / 66
observados já naquela época (em especial, Darwin e Mendel), os GAs trabalham sobre um conjunto de soluções que terão partes combinadas ou modificadas, realizando a busca no espaço de soluções. Espera-se que essa busca conduza o GA a boas soluções a medida que as iterações vão acontecendo. Filipe Saraiva | UFPA | 35 / 66
o GA utiliza sobremaneira o linguajar da biologia evolutiva para nomear funções computacionais realizadas pelo método. A saber: • Indivíduo: uma solução (ou representação de uma solução) do problema trabalhado; • População: conjunto de indivíduos (soluções) do problema; • Geração: iteração de formação de novas populações do problema; Filipe Saraiva | UFPA | 36 / 66
o GA utiliza sobremaneira o linguajar da biologia evolutiva para nomear funções computacionais realizadas pelo método. A saber: • Seleção: processo onde 2 ou mais indivíduos são selecionados para gerar novos indivíduos combinados destes; • Cruzamento (Crossover): forma pela qual 2 ou mais indivíduos são combinados entre si, gerando novos indivíduos; • Mutação: alteração aleatória onde algum componente do indivíduo tem seu valor modificado. Filipe Saraiva | UFPA | 37 / 66
• Algoritmo populacional; • Utiliza “operadores genéticos” (seleção, cruzamento e mutação) para realizar a busca; • A cada iteração (geração) uma nova população é formada da geração anterior. Filipe Saraiva | UFPA | 38 / 66
as seguintes: • Codificação dos indivíduos; • Geração da população inicial; • Seleção; • Cruzamento; • Mutação; • Geração da Nova População; • Critério de parada. Filipe Saraiva | UFPA | 40 / 66
no GA é de grande importância para o método pois a partir dele a busca é realizada e operadores de cruzamento ou mutação podem ser implementados de formas diferentes. Filipe Saraiva | UFPA | 41 / 66
Viajante poderíamos utilizar uma codificação inteira, onde cada valor representa o vértice do grafo que será visitado, na sequência. 4 5 3 1 2 No exemplo, os vértices visitados serão na ordem 4, 5, 3, 1 e 2. Filipe Saraiva | UFPA | 42 / 66
Problema da Mochila 0-1, uma codificação binária é suficiente para representar uma solução. 0 1 0 0 1 No exemplo, a solução contém apenas os itens 2 e 5 na mochila. Filipe Saraiva | UFPA | 43 / 66
conjunto de soluções que chamamos população. No geral, no início do método essa população é gerada de forma aleatória. É possível também utilizar conhecimento da instância do problema ou heurísticas para gerar essa população. O tamanho da população é uma característica que o projetista do GA deve definir a priori. Se for muito grande, potencialmente haverá maior diversidade mas também haverá maior custo computacional. Uma população pequena terá menos diversidade, mas tornará o método mais rápido. Filipe Saraiva | UFPA | 44 / 66
função objetivo do método. Assim, é possível listá-los dos melhores para os piores em relação ao desempenho na função objetivo. O operador de seleção realiza a seleção de um ou mais indivíduos para terem seus genes misturados e assim criarem novos indivíduos. Filipe Saraiva | UFPA | 45 / 66
de serem selecionados. A ideia é que melhores indivíduos (“mais aptos”) tem mais chances de passarem seus genes para as próximas gerações. Há diversos operadores de seleção, dentre eles os mais conhecidos são a roleta e o torneio. Filipe Saraiva | UFPA | 46 / 66
tem proporcionalmente mais chances de serem selecionados. Nesse método, soma-se os valores das funções objetivo de toda a população e sorteia-se um número aleatório até esse valor somado. Cada indivíduo ocupa um espaço na roleta proporcional à sua função objetivo. O indivíduo que estiver ocupando a fatia do valor sorteado terá sido o selecionado nessa etapa. Filipe Saraiva | UFPA | 47 / 66
de seleções. Na primeira, todos os indivíduos tem a mesma chance de serem selecionados, portanto seleciona-se um subconjunto do conjunto total de indivíduos. Em seguida, do subconjunto seleciona-se apenas os melhores, de forma gulosa. Filipe Saraiva | UFPA | 48 / 66
indivíduos previamente selecionados para criar novos indivíduos para a geração seguinte. Há vários tipos de operadores de cruzamento, que dependem também da codificação utilizada. Veremos alguns utilizados na codificação binária. Filipe Saraiva | UFPA | 50 / 66
0 1 P2: 1 0 1 1 1 Cruzamento de 1 ponto No cruzamento de 1 ponto temos um corte nos indivíduos selecionados gerando combinações entre os genes da esquerda do primeiro indivíduo com os da direita do segundo, e vice-versa. Para o exemplo: P1: 0 1 | 0 0 1 F1: 0 1 1 1 1 P2: 1 0 | 1 1 1 F2: 1 0 0 0 1 Filipe Saraiva | UFPA | 51 / 66
cortes nos indivíduos e o subcromossomo (subconjunto de genes) entre esses dois cortes é trocado entre os dois indivíduos pais. Para o exemplo: P1: 0 | 1 0 0 | 1 F1: 0 0 1 1 1 P2: 1 | 0 1 1 | 1 F2: 1 1 0 0 1 Filipe Saraiva | UFPA | 52 / 66
lista de 0 e 1 do tamanho do indivíduo e gera-se novos indivíduos pegando o valor do gene do indivíduo 1 se o valor gerado na máscara foi 0, do indivíduo 2 se o valor gerado foi 1, e o contrário para o segundo indivíduo. Para o exemplo: Máscara: 0 0 1 0 1 P1: 0 1 0 0 1 F1: 0 1 1 0 1 P2: 1 0 1 1 1 F2: 1 0 0 1 1 Filipe Saraiva | UFPA | 53 / 66
pelo Algoritmo Genético. Utilizando uma porcentagem baixa, o operador altera os genes dos cromossomos para algum valor possível. No geral a mutação age sobre indivíduos gerados após o cruzamento. Utilizando uma taxa baixa (um valor comum é de 2% a 5%), o algoritmo percorre o cromossomo gene-a-gene e, caso um valor gerado aleatoriamente fique abaixo da taxa de mutação, o gene em análise é modificado. Filipe Saraiva | UFPA | 54 / 66
novos indivíduos vão sendo formados. Nessa etapa o GA deve formar uma nova população, o que marca a passagem de Geração no método. Em geral é gerado um número de indivíduos igual ao tamanho da população, que substitui a anterior e dá prosseguimento à execução do método. Filipe Saraiva | UFPA | 56 / 66
geração da nova população para direcionar a busca realizada pelo método. A mais comum é a chamada Elitismo, que é a presença automática do melhor indivíduo da geração anterior na geração posterior. Isso garante que a melhor solução encontrada sempre estará presente no GA. Filipe Saraiva | UFPA | 57 / 66
o GA é quando o número de gerações atinge um valor máximo estabelecido. Outro critério de parada muito utilizado é quando o GA executa um certo número de gerações sem melhoria na melhor solução encontrada. Filipe Saraiva | UFPA | 58 / 66
decididos durante o projeto do algoritmo são: • O tamanho da população; • O número de Gerações; • O operador de Seleção; • O valor da taxa de Cruzamento e qual será o Cruzamento; • O valor da taxa de Mutação e como será implementada; • Se o GA terá Elitismo ou não; • Critério de parada. A seguir temos o pseudocódigo para o Algoritmo Genético. Filipe Saraiva | UFPA | 60 / 66
se Número aleatório for menor que Taxa de Mutação então Executa Mutação fim se até Gerar nova População Atualiza número de Gerações até Atingir critério de parada Filipe Saraiva | UFPA | 61 / 66
conseguimos resolver de maneira exata; • Para esses problemas, técnicas de inteligência computacional como os Algoritmos Genéticos são empregados para encontrar boas soluções, aceitáveis, ao problema; • Baseados na dinâmica evolutiva das espécies, os Algoritmos Genéticos são importantes ferramentas para problemas de otimização mas também para aprendizado. Filipe Saraiva | UFPA | 65 / 66