Metaheurísticas e Algoritmos Genéticos - Notas de Aula Métodos Quantitativos

Notas de Aula da Disciplina de Métodos Quantitativos para Tomada de Decisão Prof Edgard Pedroso Arquivo de aulas n o 12 Introdução aos Métodos metaheurísticos Algoritmos Genéticos AG Heurísticas são métodos aproximativos criados especificamente para resolver determinados tipos de problemas em tempo polinomial razoável exAlgoritmo dos Savings economias de Clarke e Wright Algoritmo da inserção do nó mais próximo Algoritmo de Teitz Bart Algoritmo de Gillett Johnson etc METAHEURÍSTICAS Introdução As Metaheurísticas são consideradas heurísticas de uso geral ou uma heurística das heurísticas que fornecem boas soluções mas também não garantem soluções ótimas São heurísticas inspiradas em fenômenos naturais e pertencem a uma área limite entre a Pesquisa Operacional e a Inteligência Artificial Estes algoritmos se inspiram na Física Biologia Ciências Sociais e usam uma certa quantidade de repetições de tentativas dadas por um ou mais agentes operando um mecanismo de competição e cooperação Estes métodos Metaheurísticos probabilísticos ou nãodeterminísticos geram bons resultados em problemas de otimização combinatória NPhard Mapa Mental Máximo Global Máximo Local Máximo Local Função Objetivo m Solução Inicial C Solução Inicial A Solução Inicial B Métodos Exatos Heurísticas MetaHeurísticas Teoria dos Jogos Data Mining Métodos Multicritérios Métodos Quantitativos A B C Entre várias existentes vamos abordar as seguintes Metaheurísticas que são largamente utilizadas nos problemas de Otimização Combinatória Genetic Algorithm ou Algoritmo Genético AG Simulated Annealing ou Têmpera Simulada SA Neural Networks ou Redes Neurais RN Características Gerais das Metaheurísticas usam um certo número de repetições de tentativas empregam um ou mais agentes exsneurônios RN partículas SA cromossomos AG etc podem operar em caso de múltiplos agentes com um mecanismo de competição e cooperação podem trabalhar com procedimentos de auto modificação dos parâmetros heurísticos há uma mudança dos parâmetros iniciais durante a aplicação do método De outra forma podemos dizer que são adaptativas o sistema tem a capacidade de usar informação feedback para modificar seus parâmetros e seu modelo interno ex Redes Neurais com a modificação dos pesos das ligações Inspiração em fenômenos naturais biológicos físicos etc Ex Seleção otimização premia os indivíduos mais fortes e penaliza os mais fracos e a Mutação busca não determinística introduz elementos aleatórios permitindo o nascimento de novos indivíduos Além disso em alguns algoritmos existe um parâmetro indicado como parâmetro de controle ou de aprendizagem ou de equilíbrio que varia lentamente com o objetivo de evitar ótimos locais e permitir a exploration exploração em amplitude do espaço quanto mais lentamente este parâmetro varia mais alta é a probabilidade de que a solução final obtida esteja próxima ao ótimo global é possível projetar metaheurísticas contendo como uma característica procuras específicas locais para o valor ótimo deste parâmetro de controle Grau de exploitation o grau de profundidade exploração intensificada focada quantidade de esforço direcionado à busca local em determinada região do espaço de busca se a região é promissora procure mais profundamente Grau de exploration o grau de amplitude exploração diversificada quantidade de esforço gasto na procura em regiões distantes algumas vezes se escolhe uma solução em uma região distante eou aceitase uma solução pior para ganhar a possibilidade de descobrir novas soluções melhores Obs Estas duas possibilidades são conflitantes uma boa troca entre elas é muito importante e deve ser cuidadosamente afinadas em cada algoritmo Características importantes devem ser balanceadas na construção dos algoritmos heurísticos eficiência número de iterações eficácia precisão do valor da solução final Exemplo de busca pelo mínimo global 7 Espaço de busca S fz Função Objetivo x y z máximos locais mínimos locais mínimo global no espaço de busca S diferentes estados de busca máximo global no espaço de busca S mínimo global no espaço de busca S pto de aprimoramento mínimo local máximo local Exploration Procura em amplitude regiões Promissoras Exploitation Procura local Exploitation Procura local máximo global no espaço de busca S pto de aprimoramento sol inicial LANGERMANNs function 11 objective value x2 x1 9 Introdução aos ALGORITMOS GENÉTICOS AGs Usam analogia com a genética humana para resolver problemas de otimização tais como Problema do Caixeiro Viajante PCV Problema de Localização de Facilidades PLF Problema de Transporte Problema de Designação entre outros Os Algoritmos Genéticos AGs ou algoritmos evolucionários constituem um método de otimização inspirado no processo Darwiniano de seleção natural dos seres vivos Fazem parte de uma classe de modelos e técnicas computacionais inspiradas na evolução natural dita Computação Evolucionista Segundo Dias e Barreto 1998 dentre os principais fatores que têm feito dos AGs uma técnica bem sucedida destacamse a simplicidade de operação facilidade de implementação computacional eficácia na busca da região onde provavelmente encontrase o ótimo global busca em amplitude ser aplicável em situações onde não se conhece o modelo matemático ou se este for impreciso ser aplicável em problemas que envolvem funções lineares e nãolineares Contudo em virtude da lenta e até mesmo crítica convergência dos AGs redução do erro recomendase utilizálo de forma híbrida Os AGs poderiam se encarregar de dentro do espaço de busca procurar regiões promissoras para se encontrar ótimo global busca em amplitudeexploration enquanto outro método por ex o método do gradiente seria usado para a busca local busca localexploitation Quanto melhor um indivíduo se adaptar ao seu meio ambiente maior será sua chance de sobreviver e gerar descendentes DARWIN 1859 Holland 1975 Goldberg1989 10 Exemplo 1aplicação simplificada em um problema de otimização combinatória Suponha o Problema de Localização de Facilidades PLF em que são dadas as coordenadas de 6 pontos localizações de bairros de uma cidade entre os quais deverão ser escolhidos 4 para construir escolas instalações Os 4 pontos escolhidos deverão atender as demandas existentes de forma a minimizar as distâncias entre os pontos de demanda e de instalações ou seja devem ser escolhidos 4 pontos para medianas p 4 São dadas também as demandas pesos existentes em cada um dos 6 pontos tabela Determine uma solução para o PLF utilizando a metaheurística dos Algoritmos Genéticos AGs Pontos bairros Coordenadas xy Pesos W demandas 1 11 2 2 23 3 3 32 2 4 44 4 5 51 4 6 15 5 Adote os seguintes parâmetros e operadores para a aplicação da metaheurística 1 No de cromossomos soluções ou indivíduos da população m 5 2 Método de seleção dos cromossomos pais ou indivíduos pais para cruzamento ou reprodução Utilize a função Select 3 Operador de cruzamento ou reprodução Utilize o crossover de um ponto simples tomando como ponto de crossover PC 2 4 Operador de mutação De forma simplificada adotaremos aqui realizar uma mutação quando um filho gerado for uma solução inviável para o PLF substituindo por um processo randômico um dos elementos escola repetidos na solução por um elemento bairro que não esteja presente na solução corrente 5 Critério regra de parada Realize apenas uma iteração apenas Dados 11 Pontos Coord xy Pesos W 1 11 2 2 23 3 3 32 2 4 44 4 5 51 4 6 15 5 1 4 2 3 2 4 5 1 2 3 4 5 6 W 1 0 2 2 4 4 4 2 2 2 0 1 2 3 2 3 3 2 1 0 2 2 3 2 4 4 2 2 0 3 3 4 5 4 3 2 3 0 5 4 6 4 2 3 3 5 0 5 2 3 4 5 6 Matriz com as distâncias inteiras mínimas aproximadas entre todos os pares de pontos OBS Caso não tivéssemos dada a matriz com as distâncias mínimas poderíamos obtêla através da aplicação do algoritmo de FLOYD como já foi visto anteriormente 12 Aplicação e teoria da metaheurística 1º Passo Criase aleatoriamente uma população de m 5 cromossomos soluções r11356 r22461 r33562 r41456 r56324 Por exemplo 2ª OBS O processo de inicialização da população é quase sempre realizado aleatoriamente utilizandose um gerador randômico de soluções numa faixa previamente definida pelo usuário Esta faixa é definida levandose em consideração algum conhecimento prévio do problema a ser otimizado podese também iniciar com soluções aproximadas já conhecidas 1ª OBS O nº m de elementos que irá compor a população é questionável ou seja depende muito da experiência do usuário e do seu conhecimento prévio sobre a função a ser otimizada Em geral o número m mantémse igual para novas populações geradas na sequência Aqui adotamos m 5 como definido no enunciado do problema Equivalências inspiradas na biologia Cromossomo Uma solução possível no espaço de busca var independente X Genes Um parâmetro do problema codificado em uma solução ou uma componente do vetor que representa a solução cromossomo String Sequência finita de parâmetros codificados genes ou componentes do vetor solução cromossomo Locus Posição que os genes ocupam no cromossomo Alelo Conjunto de valores possíveis que o gene pode assumir Genótipo Cromossomo Genes Alelo Fenótipo Aptidão Fitness Valor da Função Objetivo fX Var Dependente 1 2 3 4 5 6 1 0 4 4 8 8 8 2 6 0 3 6 9 6 3 4 2 0 4 4 6 4 16 8 8 0 12 12 5 16 12 8 12 0 20 6 20 10 15 15 25 0 1 2 3 4 5 6 W 1 0 2 2 4 4 4 2 2 2 0 1 2 3 2 3 3 2 1 0 2 2 3 2 4 4 2 2 0 3 3 4 5 4 3 2 3 0 5 4 6 4 2 3 3 5 0 5 Matriz das distâncias já ponderadas com as demandas 13 2º Passo Calculase o fitness custo para cada um dos cromossomos soluções ou indivíduos 1 2 3 4 5 6 1 0 4 4 8 8 8 2 6 0 3 6 9 6 3 4 2 0 4 4 6 4 16 8 8 0 12 12 5 16 12 8 12 0 20 6 20 10 15 15 25 0 r11356 C1 030800 11 r22461 C2 002012014 r33562 C3 400800 12 r41456 C4 064000 10 r56324 C5 400080 12 min d v v w fitness r C j k v 1 j j i i Para r1 1 2 3 4 5 6 1 0 4 4 8 8 8 2 6 0 3 6 9 6 3 4 2 0 4 4 6 4 16 8 8 0 12 12 5 16 12 8 12 0 20 6 20 10 15 15 25 0 Para r2 1 2 3 4 5 6 1 0 4 4 8 8 8 2 6 0 3 6 9 6 3 4 2 0 4 4 6 4 16 8 8 0 12 12 5 16 12 8 12 0 20 6 20 10 15 15 25 0 Para r3 1 2 3 4 5 6 1 0 4 4 8 8 8 2 6 0 3 6 9 6 3 4 2 0 4 4 6 4 16 8 8 0 12 12 5 16 12 8 12 0 20 6 20 10 15 15 25 0 Para r4 1 2 3 4 5 6 1 0 4 4 8 8 8 2 6 0 3 6 9 6 3 4 2 0 4 4 6 4 16 8 8 0 12 12 5 16 12 8 12 0 20 6 20 10 15 15 25 0 Para r5 FUNÇÃO APTIDÃO O grau de adaptação de cada indivíduo é sua aptidão fitness custo ou valor da função objetivo e é obtido pela avaliação do indivíduo através da função a ser otimizada A função de aptidão objetivo deve refletir a qualidade de um elemento em solucionar o problema A regra que a determina depende do problema que está sendo considerado e no tipo de otimização minimização ou maximização desejada Por exemplo No PLF a função de aptidão pode ser a expressão que fornece Ci a soma ponderada wj demandas das distâncias mínimas min dvkvj percorridas entre cada ponto dado até os pontos que compõe cada solução instalações Por exemplo No PCV a regra da função de aptidão pode ser a expressão que fornece a distância total percorrida pelo viajante Distância ponderada 14 3º Passo Colocase a população em ordem do melhor no ex menor para o pior no ex maior renumerando os indivíduos fazse um reordenamento ou seja criase um ranque assim temos r11456 C1 10 r21356 C2 11 r33562 C3 12 r46324 C4 12 r52461 C5 14 r11356 C1 11 r22461 C2 14 r33562 C3 12 r41456 C4 10 r56324 C5 12 r11356 C1 11 r22461 C2 14 r33562 C3 12 r41456 C4 10 r56324 C5 12 4º Passo Em geral a regra de parada é determinada pelo número de iterações ou por regras associadas a critérios de convergência Aqui faremos uma iteração ou 1 geração como definido no enunciado do problema População População reordenada da melhor p pior Melhor Para Pior População inicial 5º Passo Selecionase dois indivíduos para cruzamento crossover Existem várias formas de fazer esta seleção Aqui usaremos a função denominada função SELECT como definido no enunciado do problema etc 4 3 37 23 EX tsendo t o inteiro imediatamente superior a k k 2 m 4 rdn m 1 1 1 m r tal que j R select s 2 j 5 0 1 4 nº obtido por gerador randômico rnd01 rdn 01 rnd r 0 6 6 5 6 2 121 1 6 2 5 1 4 1 5 1 5 1 j 1 rnd Se seleciona r 5 6 1 0 6 2 1 1 6 2 5 1 4 0 5 1 5 1 j 0 rnd Se 0 2 5 2 existe não Comentário sobre o motivo da exclusão do valor 1 para rdn Substitua pelo inteiro imediatamente superior Cuidado Esclarecimentos teóricos 5º Passo Selecionase dois indivíduos p o cruzamento Forma de seleção Função SELECT 1r seleciona 1 5 6 84 6 j 2 112 6 1 6 2 5 0 93 5 4 1 1 5 1 j 0 93 Se rnd seleciona 3r 3 3 6 52 6 j 2 37 1 6 2 5 4 030 5 1 1 5 1 j 0 30 Se rnd Assim temse 093 ex gerado por software 03 e rnd rnd Para resolver o exercício vamos escolher aleatoriamente 2 2 Continuidade da resolução do exemplo Substitua pelo inteiro imediatamente superior Substitua pelo inteiro imediatamente superior OBS Embora tenhamos optado em usar a função Select como método de seleção dos cromossomos pais outros métodos randômicos podem ser aplicados para este fim tais como métodos do RANKING e da ROLETA SIMPLES entre outros encontrados na bibliografia a respeito do assunto Pais selecionados 6º Passo Fazse o cruzamento crossover sobre os indivíduos selecionados Do 3º passo obtevese a populacão X r1 1 4 5 6 r3 3 5 6 2 r11456 C1 10 r21356 C2 11 r33562 C3 12 r46324 C4 12 r52461 C5 14 Filhos gerados f11462 e f23556 Operador de Mutação dado no enunciado Escolhese aleatoriamente um ponto que esteja fora de f2 1 2 ou 4 p substituir aleatoriamente um dos pontos repetidos iguais a 5 por ex 4 no segundo 5 temse Solução obtida da mutação f23546 Operador de cruzamento Crossover de um ponto Ponto de crossover pc 2 normalmente gerado aleatoriamente Conta duas posições da esquerda para direita cabeça e permutase as demais posições à direita cauda 1 No PFL Tanto faz substituir 4 no lugar do 1º ou 2º número 5 pois a solução seria a mesma 2 A mutação avalia áreas do espaço de busca ainda não exploradas explorationbamplitude O operador crossorver busca solução a partir de indivíduos já existentes exploitationbusca local Continuidade da resolução do exemplo Permutase os blocos genes da cauda Cromossomo cabeça corte cauda OBS importante O fato do filho f2 ser inviável não é uma condição para a que mutação seja necessariamente executada ou seja poderíamos simplesmente descartar o filho f2 Aqui realizamos a mutação em f2 por força da regra estabelecida no enunciado da questão Na prática o tomador de decisão deve préestabelecer com que probabilidade será aplicado um determinado operador de mutação independentemente dos filhos serem ou não viáveis isto define o esforço de busca em amplitude regiões não exploradas durante o desenvolvimento das gerações iterações na aplicação da metaheurística dos AGs filho inviável Esclarecimentos teóricos 1 Existem vários tipos de operadores genéticos mecanismos de recombinação aleatória tanto de crossover como de mutação aplicáveis na solução de problemas de otimização convencional ou combinatória mono ou multiobjetivo com ou sem restrições A escolha adequada do operador genético depende da natureza do problema a ser resolvido Exemplos de operadores de crossover Para cadeias de bits 0 e 1 Convencionais N pontos de corte e uniforme Para cadeias de números reais Aritméticos médias aritmética e geométrica Davis 1991 mistura ou BLXα EshelmanShalffer1993 linear Wright1991 aritmético heurístico e simples adaptado para representação Real Michalewicz1994 entre outros de maior complexidade Para permutação entre os elementos da cadeia em problemas combinatoriais Ex Problema do Caixeiro Viajante PCV entre outros OBX Order Based Crossover PBX Position Based Crossover PMX Partially Matched Crossover CX Cycle Crossover OX Order Crossover Exemplos de operadores de mutação Para representação real uniforme gaussiana creep limite nãouniforme e nãouniforme múltipla Michalewicz1994 Para problemas de otimização combinatória podese usar operadores de permutação e substituição dos elementos que compõem as soluções entre outros OBS Podese também ponderar o uso simultâneo de vários operadores durante o uso do AG r1 11111 111 1111 r2 00000 000 0000 f1 11111 000 1111 f2 00000 111 0000 Ex N 2 pontos de corte 19 Esclarecimentos teóricos 2 Algumas bibliografias sugerem que a probabilidade de aplicação do operador de crossover exploitation busca local intensificação em cada par de cromossomos pais selecionados varie de 60 a 90 e que a probabilidade de aplicação do operador de mutação exploration busca em amplitudediversificação seja pequena de 01 a 5 3 Normalmente a forma de codificação corresponde a utilizar cadeias strings de comprimento finito formadas por caracteres de um determinado alfabeto determinado conjunto de caracteres letras números ou símbolos Uma possível alternativa é a forma binária onde o alfabeto é composto somente pelos símbolos 0 e 1 bit binary digit Outra alternativa é a representação através dos próprios significados envolvidos no problema Exs na Otimização Combinatória no PLF as possíveis localizações das medianas no PCV as possíveis sequências de pontos etc Exs na Otimização Convencional na Programação Linear PL o conjunto das possíveis soluções reais na Programação Linear Inteira PLI o conjunto das possíveis soluções inteiras etc 4 Representação Real X Binária exemplo Seja a solução de um problema de otimização convencional dada por vetor do R2 r 25 72 então a representação no sistema binário seria dada por r 110011001000 OBS A representação binária bits pode gerar cadeias cromossomos mais longas e isto pode fazer com que a convergência do algoritmo seja mais lenta enquanto a representação real gera cadeias curtas e de compreensão mais fácil 20 6º Passo cont Fazse o cruzamento crossover sobre os indivíduos selecionados f23546 fitness Cf2 4 3 0 0 0 0 7 Logo obtevese dois novos indivíduos f11462 fitness Cf1 0 0 2 0 12 0 14 1 2 3 4 5 6 1 0 4 4 8 8 8 2 6 0 3 6 9 6 3 4 2 0 4 4 6 4 16 8 8 0 12 12 5 16 12 8 12 0 20 6 20 10 15 15 25 0 Para f1 1 2 3 4 5 6 1 0 4 4 8 8 8 2 6 0 3 6 9 6 3 4 2 0 4 4 6 4 16 8 8 0 12 12 5 16 12 8 12 0 20 6 20 10 15 15 25 0 Para f2 r13546 C1 7 r21456 C2 10 r31356 C3 11 r43562 C4 12 r56324 C5 12 r62461 C6 14 r71462 C7 14 Família anterior ampliada na ordem melhor p pior r13546 C1 7 r21456 C2 10 r31356 C3 11 r43562 C4 12 r56324 C5 12 Família nova Volta ao 4º passo 7º Passo Obtenção da nova família Método de substituição SteadyState Estado Estável Acrescenta os novos filhos na população anterior e elimina os piores Eliminase os piores Obs Além do método de substituição Steady State podese aplicar outros métodos de substituição 21 4º Passo Em geral a regra de parada é determinada pelo número de iterações ou por regras associadas a critérios de convergência Aqui fizemos uma iteração ou 1 geração como definido no enunciado do problema FIM Resposta p 1 iteração r13546 C1 7 r21456 C2 10 r31356 C3 11 r43562 C4 12 r56324 C5 12 As escolas serão construídas em r13546 A distância mínima percorrida pelos alunos será de C1 430000 7 1 4 2 3 2 4 5 2 3 4 5 6 1 2 3 4 5 6 1 0 4 4 8 8 8 2 6 0 3 6 9 6 3 4 2 0 4 4 6 4 16 8 8 0 12 12 5 16 12 8 12 0 20 6 20 10 15 15 25 0 O gráfico mostra que os alunos que moram nos bairros 1 2 e 3 estudarão na escola em 3 Dos bairros 4 5 e 6 estudarão nos próprios bairros pois neles serão construídas escolas Agrupamentos ou clusters 22 Comentário Como já vimos os Algoritmos Genéticos requerem a definição de vários parâmetros que afetam o desempenho do algoritmo de várias formas O tamanho da população o número de indivíduos formando a população deve ser suficientemente grande para garantir diversidade suficiente e assim cobrir bem o espaço de soluções Outros parâmetros como as probabilidades taxas de cruzamento e de mutação e os tipos mecanismos de cruzamento e mutação devem ser adequados para o bom desempenho do AG Não há valores de parâmetros reconhecidamente ótimos apenas faixas sugeridas de trabalho MICHALEWICZ 1996 Mesmo sendo muito mais rápido que métodos tipo busca exaustiva ainda são métodos muito lentos se comparados com métodos do tipo gradiente já que não empregam qualquer informação referente à derivada da função objetivo GOLDBERG 1989 Trabalho proposto 1 TDE 2 Usando os mesmos parâmetros do exemplo anterior determine a solução para o PLF caso executássemos uma segunda geração iteração 23 ALGORITMOS GENÉTICOS AGs Exemplo 2 aplicação simplificada em um problema de otimização combinatória Considere o Problema de Caixeiro Viajante PCV constituído de seis pontos e a matriz com as distâncias inteiras mínimas aproximadas entre todos os pares de pontos Determine uma solução do PCV aplicando os Algoritmos Genéticos 1 2 3 4 5 6 1 0 2 2 4 4 4 2 2 0 1 2 3 2 3 2 1 0 2 2 3 4 4 2 2 0 3 3 5 4 3 2 3 0 5 6 4 2 3 3 5 0 1º Passo Criase aleatoriamente uma população de m 4 cromossomos soluções ou indivíduos r1123456 1 r2246135 2 r3156342 1 r4651423 6 Por exemplo O número final foi acrescentado apenas para lembrar quando do cálculo do valor da função objetivo de incluir a distância de retorno p o ponto inicial Dados OBS Caso não tivéssemos dada a matriz com as distâncias mínimas poderíamos obtêla através da aplicação do algoritmo de FLOYD como já foi visto na disciplina de Métodos Heurísticos Adote os seguintes parâmetros e operadores para a aplicação da metaheurística 1 No de cromossomos indivíduos da população m 4 2 Método de seleção dos cromossomos pais ou soluções pais para cruzamento ou reprodução Utilize a função Select 3 Operador de cruzamento ou reprodução Utilize o operador OBX Order Based Crossover Este método será detalhado durante a resolução do problema 4 Operador de mutação Suponha que regra probabilística estabelecida para aplicação realização da mutação recaia aleatoriamente sobre ambos os filhos gerados na segunda iteração e que um operador randômico de mutação determine a permuta de posição entre o 5º e 6º elementos genes de ambas soluções cromossomos obtidas para o PCV 5 Critério regra de parada Realize três iterações 24 2º Passo Calculase os fitness grau de adaptabilidade valor da função objetivo para cada um dos cromossomos 1 2 3 4 5 6 1 0 2 2 4 4 4 2 2 0 1 2 3 2 3 2 1 0 2 2 3 4 4 2 2 0 3 3 5 4 3 2 3 0 5 6 4 2 3 3 5 0 r1123456 1 C1 21235417 r2246135 2 C2 23422316 r3156342 1 C3 45322218 r4651423 6 C4 54421319 Para r1 1 2 3 4 5 6 1 0 2 2 4 4 4 2 2 0 1 2 3 2 3 2 1 0 2 2 3 4 4 2 2 0 3 3 5 4 3 2 3 0 5 6 4 2 3 3 5 0 Para r2 1 2 3 4 5 6 1 0 2 2 4 4 4 2 2 0 1 2 3 2 3 2 1 0 2 2 3 4 4 2 2 0 3 3 5 4 3 2 3 0 5 6 4 2 3 3 5 0 Para r3 1 2 3 4 5 6 1 0 2 2 4 4 4 2 2 0 1 2 3 2 3 2 1 0 2 2 3 4 4 2 2 0 3 3 5 4 3 2 3 0 5 6 4 2 3 3 5 0 Para r4 3º Passo Colocase a população em ordem do melhor no ex menor para o pior no ex maior renumerando os indivíduos fazse um ranqueamento assim temos r1123456 1 C1 17 r2246135 2 C2 16 r3156342 1 C3 18 r4651423 6 C4 19 r1246135 2 C1 16 r2123456 1 C2 17 r3156342 1 C3 18 r4651423 6 C4 19 4º Passo Em geral a regra de parada é determinada pelo número de iterações Aqui escolheremos arbitrariamente fazer 3 iterações ou 3 gerações 5º Passo Método de seleção dos cromossomos pais ou soluções pais para cruzamento ou reprodução Utilize a função Select seleciona 2 3 5 2 5 j 2 25 1 5 2 4 4 30 4 1 1 1 4 j 30 Se rnd seleciona 1 4 5 3 27 5 j 2 57 1 5 2 4 4 07 4 1 1 1 4 j 70 Se rnd Assim temse 03 07 e rnd Para resolver o exercício vamos escolher aleatoriamente rnd 2 2 2 r 1 r 2 m 4 RND m 1 1 m 1 r tal que j R select 2 j cuidado 6º Passo Fazse o cruzamento crossover sobre os indivíduos selecionados Pais selecionados Cf1 23423216 1 2 3 4 5 6 1 0 2 2 4 4 4 2 2 0 1 2 3 2 3 2 1 0 2 2 3 4 4 2 2 0 3 3 5 4 3 2 3 0 5 6 4 2 3 3 5 0 Para f1 1 2 3 4 5 6 1 0 2 2 4 4 4 2 2 0 1 2 3 2 3 2 1 0 2 2 3 4 4 2 2 0 3 3 5 4 3 2 3 0 5 6 4 2 3 3 5 0 Para f2 Cf2 22352216 Operador OBX Order Based Crossover Geração do filho f1 aDetermine aleatoriamente um determinado número de posições que compõem o cromossomo Suponha a escolha das três posições a seguir bOrdene os elementos pai r1 que ocupam as posições selecionadas na mesma ordem que estes mesmos elementos seguem no pai r2 e assim será obtido o filho f1 r1 246135 r2123456 e r1 24 6 13 5 f1 4 13 1o 2o 3o 2 5 6 a b Geração do filho f2 r21 2 3 4 5 6 f21 2 5 1o 2o 3o 4 6 3 f1 2 4 51 3 6 2 f2 1 2 4 6 5 3 1 Usando o mesmo método temse Família anterior ampliada ordenada Família nova Volta ao 4º passo Eliminados Indivíduo Fitness r1246135 2 C1 16 r2245136 2 C2 16 r3124653 1 C3 16 r4123456 1 C4 17 4º Passo Em geral o teste regra de parada é determinado pelo número de iterações Aqui escolheremos arbitrariamente fazer 3 iterações 7º Passo Obtenção da nova família r1246135 2 C1 16 r2245136 2 C2 16 r3124653 1 C3 16 r4123456 1 C4 17 r5156342 1 C5 18 r6651423 6 C6 19 2ª iteração 28 5º Passo Selecionase dois indivíduos para o cruzamento Existem várias formas para fazer esta seleção A partir desta iteração usaremos a função denominada função SELECT 1 4 5 53 5 2 65 1 5 2 4 4 80 4 1 1 4 1 j 80 Se rnd 3 2 5 156 5 2 17 1 5 2 4 4 20 4 1 1 4 1 j 20 Se rnd Assim temse 08 02 e rnd Para resolver o exercício vamos escolher aleatoriamente rnd 2 2 1r seleciona r 3 seleciona 2 m 4 RND m 1 1 m 1 r tal que j R select 2 j Excepcionalmente cálculos desnecessários por conta do operador de mutação indicado no enunciado Família atual Pais selecionados Indivíduo Fitness r1246135 2 C1 16 r2245136 2 C2 16 r3124653 1 C3 16 r4123456 1 C4 17 e 6º Passo Fazse o cruzamento crossover sobre os indivíduos selecionados Operador OBX Order Based Crossover Geração do filho f1 aDetermine aleatoriamente um determinado número de posições que compõem os cromossomos Suponha a escolha das três posições a seguir bOrdene os elementos pai r1 que ocupam as posições selecionadas na mesma ordem que estes mesmos elementos seguem no pai r2 e assim será obtido o filho f1 f1 6 3 5 1 2 4 a b Geração do filho f2 r31 2 4 6 5 3 f2 4 6 3 2 1 5 r1246135 r3124653 r1 2 4 6 1 3 5 1o 2o 3o 1o 2o 3o 1 2 3 4 5 6 1 0 2 2 4 4 4 2 2 0 1 2 3 2 3 2 1 0 2 2 3 4 4 2 2 0 3 3 5 4 3 2 3 0 5 6 4 2 3 3 5 0 Para f1 1 2 3 4 5 6 1 0 2 2 4 4 4 2 2 0 1 2 3 2 3 2 1 0 2 2 3 4 4 2 2 0 3 3 5 4 3 2 3 0 5 6 4 2 3 3 5 0 Para f2 Cf1 22322415 Cf2 24352117 f1 1 2 64 3 5 1 f2 2 1 4 6 5 3 2 Operador de mutação permutação Conforme o enunciado do problema faremos a permuta de posição entre o 5º e 6º elementos de ambas as soluções filhos Cf1 22332214 Cf2 24332317 f1 mutação 1264531 f2 mutação 2146352 1 2 3 4 5 6 1 0 2 2 4 4 4 2 2 0 1 2 3 2 3 2 1 0 2 2 3 4 4 2 2 0 3 3 5 4 3 2 3 0 5 6 4 2 3 3 5 0 1 2 3 4 5 6 1 0 2 2 4 4 4 2 2 0 1 2 3 2 3 2 1 0 2 2 3 4 4 2 2 0 3 3 5 4 3 2 3 0 5 6 4 2 3 3 5 0 Família anterior ampliada ordenada Família nova Volta ao 4º passo Indivíduo Fitness r1126453 1 C1 14 r2246135 2 C2 16 r3245136 2 C3 16 r4124653 1 C4 16 4º Passo Em geral o teste regra de parada é determinado pelo número de iterações Aqui escolheremos arbitrariamente fazer 3 iterações 7º Passo Obtenção da nova família r1126453 1 C1 14 r2246135 2 C2 16 r3245136 2 C3 16 r4124653 1 C4 16 r5123465 1 C5 17 r6214635 2 C6 17 Eliminados 3ª iteração 31 5º Passo Selecionase dois indivíduos para o cruzamento Existem várias formas para fazer esta seleção A partir desta iteração usaremos a função denominada função SELECT 2 m 4 RND m 1 1 m 1 r tal que j R select 2 j 2 3 5 92 5 2 46 6 1 5 2 4 0 57 4 4 1 1 4 1 j 0 57 rnd Se 4 5 1 90 5 2 47 1 5 2 4 4 008 4 1 1 4 1 j 0 08 rnd Se 057 Assim temse 008 e rnd resolver o exercício vamos escolher aleatoriamente rnd Para 2 2 2 4 r seleciona r seleciona Indivíduo Fitness r1126453 1 C1 14 r2246135 2 C2 16 r3245136 2 C3 16 r4124653 1 C4 16 6º Passo Fazse o cruzamento crossover sobre os indivíduos selecionados Pais selecionados Cf1 42232417 1 2 3 4 5 6 1 0 2 2 4 4 4 2 2 0 1 2 3 2 3 2 1 0 2 2 3 4 4 2 2 0 3 3 5 4 3 2 3 0 5 6 4 2 3 3 5 0 Para f1 1 2 3 4 5 6 1 0 2 2 4 4 4 2 2 0 1 2 3 2 3 2 1 0 2 2 3 4 4 2 2 0 3 3 5 4 3 2 3 0 5 6 4 2 3 3 5 0 Para f2 Cf2 24353118 Operador OBX Order Based Crossover Geração do filho f1 aDetermine aleatoriamente um determinado número de posições que compõem os cromossomos Suponha a escolha das três posições a seguir bOrdene os elementos pai r1 que ocupam as posições selecionadas na mesma ordem que estes mesmos elementos seguem no pai r2 e assim será obtido o filho f1 r2 2 4 6 1 3 5 e f1 4 3 5 1o 2o 3o 1 2 6 a b Geração do filho f2 f2 4 6 5 1o 2o 3o 2 1 3 f2 2 1 4 6 5 3 2 f1 1 4 2 6 3 5 1 r41 2 4 6 5 3 r2 2 4 6 1 3 5 r41 2 4 6 5 3 Família anterior ampliada ordenada Família nova Volta ao 4º passo Indivíduo Fitness r1126453 1 C1 14 r2246135 2 C2 16 r3245136 2 C3 16 r4124653 1 C4 16 4º Passo Em geral o teste regra de parada é determinado pelo número de iterações Aqui escolheremos arbitrariamente fazer 3 iterações FIM 7º Passo Obtenção da nova família Eliminados Indivíduo Fitness r1126453 1 C1 14 r2246135 2 C2 16 r3245136 2 C3 16 r4124653 1 C4 16 r5142635 1 C5 17 r6214653 2 C6 18 r1 1264531 C1 14 1 2 3 4 5 6 Resposta p 3 iterações A continuidade na realização das iterações selecionaria Famílias com membros cada vez melhores convergindo para uma solução com custo cada vez menor Família nova Trabalho proposto 2 TDE 2 Usando os mesmos parâmetros usados na segunda iteração do exemplo anterior determine a solução do PCV caso executássemos uma quarta geração iteração Indivíduo Fitness r1126453 1 C1 14 r2246135 2 C2 16 r3245136 2 C3 16 r4124653 1 C4 16 35 Algoritmo Genético PCV de 225 pontos 50 gerações menor distância alcançada 4206 distância mínima ótima 3864 TSP Traveling Salesman Problem 36 Observação Importante Embora tenhamos exemplificado a aplicação dos AG apenas nos problemas PLF e PCV lembrese existem diversos outros exemplos de aplicação na solução de problemas de otimização combinatória aqui não abordados 37 Notas de Aula Prof Edgard 1 GOLDBARG Marco Cesar LUNA Henrique Pacca L Otimização combinatória e programação linear modelos e algoritmos 2 ed rev e atual Rio de Janeiro Campus 2005 2 LOPES Heitor Silvério RODRIGUES Luiz Carlos de Abreu STEINER Maria Teresinha Arns Meta heurísticas em pesquisa operacional Curitiba Omnipax 2013 3 SHIMIZU Tamio Decisão nas organizações introdução aos problemas de decisão encontrados nas organizações e nos sistemas de apoio à decisão São Paulo Atlas 2001 4 ARENALES Marcos Nereu Pesquisa operacional para cursos de engenharia Rio de Janeiro Elsevier 2007 5 HILLIER Frederick S LIEBERMAN Gerald J Introdução à pesquisa operacional Porto Alegre AMGH 2013 6 GOMES Luiz Flavio Autran Monteiro GONZÁLEZ ARAYA Marcela Cecilia CARIGNANO Claudia Tomada de decisões em cenários complexos introdução aos métodos discretos do apoio multicritério à decisão 1 ed São Paulo Cengage Learning 2004 7 DUDA Richard O HART Peter E STORK David G Pattern classification and scene analysis 2nd ed New York J Wiley Sons c2001 8 Bodin L Golden B Assad A and Ball M Routing and Scheduling of veicles and crews Special edition of Computer and Operations Research col 10 n2 1983 9 Bronson R Pesquisa Operacional São Paulo Schaum McGrawHill do Brasil Ltda 1985 10 Murty K Linear and Combinatorial Programming Robert E Krieger Publishing Company Malabar Florida 1985 11 Steiner MT A Notas de Aulas Importante Este material tem finalidade única e exclusivamente didática e serve apenas como notas de apoio às aulas da disciplina de Métodos Quantitativos para Tomada de Decisão do curso de Graduação de Engenharia de Produção Este material não pode ser utilizado como referência bibliográfica e muito menos comercialmente Recomendase consultar as seguintes obras