UNIVERSIDADE ESTADUAL PAULISTA “JÚLIO DE MESQUITA FILHO” FACULDADE DE ENGENHARIA DE PRODUÇÃO DE BAURU PROGRAMA DE PÓS-GRADUAÇÃO “STRICTO SENSU” ANDERSON ROGÉRIO FAIA PINTO ALGORITMO GENÉTICO APLICADO AO SEQUENCIAMENTO DE PICKING E FATURAMENTO Bauru 2012 ANDERSON ROGÉRIO FAIA PINTO ALGORITMO GENÉTICO APLICADO AO SEQUENCIAMENTO DE PICKING E FATURAMENTO Dissertação de Mestrado apresentada ao Programa de Pós Graduação em Engenharia de Produção da Faculdade de Engenharia de Bauru da Universidade Estadual Paulista “Júlio de Mesquita Filho”, como exigência parcial para obtenção do título de Mestre em Engenharia de Produção. Área de Concentração: Gestão de Operações e Sistemas. Orientador: Prof.º Dr. Antonio Fernando Crepaldi. Bauru 2012 Pinto, Anderson Rogério Faia. Algoritmo genético aplicado ao sequenciamento de picking e faturamento / Anderson Rogério Faia Pinto, 2012 80 f. Orientador: Antonio Fernando Crepaldi Dissertação (Mestrado)–Universidade Estadual Paulista. Faculdade de Engenharia, Bauru, 2012 1. Algoritmos Genéticos. 2. Processo de Picking. 3. Sequenciamento de Faturamento. I. Universidade Estadual Paulista. Faculdade de Engenharia. II. Título. Dedico este trabalho aos meus pais Vagne e Cleide, que estiveram sempre do meu lado me apoiando nos momentos de dificuldades e me fazendo acreditar que era possível. AGRADECIMENTOS Agradeço a DEUS por me dar a graça da saúde e do discernimento! À CAPES pelo apoio financeiro ao conceder a bolsa de estudo para realização desta pesquisa. À Faculdade de Engenharia de Bauru pela oportunidade de realização do curso de mestrado. Aos professores do Departamento de Engenharia de Produção pelos conhecimentos transmitidos com os quais deram a base para a realização deste trabalho. Em especial, ao meu orientador, professor Dr. Antonio Fernando Crepaldi, pela confiança e amizade construída e por sua valorosa atenção nas correções, orientações e sugestões que tanto contribuíram para o enriquecimento e realização deste projeto. Aos funcionários do Departamento de Engenharia de Produção, da Biblioteca, e da Seção de Pós Graduação da FEB/UNESP pela atenção e apoio administrativo, e a todos os servidores pelo pronto atendimento. A todas as pessoas que direta ou indiretamente contribuíram para a realização desta pesquisa, familiares, amigos, professores e alunos de mestrado, em particular ao amigo Alex Oliva Borrasca pela ajuda no desenvolvimento do software. À minha namorada Milene pelo apoio que têm me dado para concluir mais esta fase da minha vida, tanto nas horas difíceis quanto compartilhando dos momentos de conquistas. E, finalmente, aos meus pais, Vagne e Cleide, e meus irmãos Jefferson e Rafael pelos conselhos e incentivos ao longo desse projeto desafiador, e pelo eterno orgulho de me ver evoluindo ao longo dos anos. “Tudo que você vivamente imaginar, ardentemente desejar, sinceramente acreditar, e entusiasticamente colocar ação, ...inevitavelmente tornar-se-á realidade” Paul J. Meyer RESUMO PINTO, A. R. F. Algoritmo genético aplicado ao sequenciamento de picking e faturamento. 2012. 80 f. Dissertação de Mestrado (Mestrado em Engenharia de Produção) - Faculdade de Engenharia de Bauru, Universidade Estadual Paulista "Júlio de Mesquita Filho", Bauru, 2012. As desordens e incertezas provocadas no decorrer do tempo, face à dinâmica das mudanças e a complexidade dos sistemas que abrangem as organizações, acarretam diversas situações em que os gestores necessitam encontrar soluções das quais seja possível extrair a maximização do resultado empresarial. Logo, o desenvolvimento de ferramentas que possam em dado momento apresentar, de forma ágil, um número mínimo de opções necessárias para investigar a incerteza é uma tarefa necessária em ambientes de negócios. Esta dissertação tem como objetivo a busca por uma solução para o problema do Sequenciamento Ótimo de Faturamento (SOF). A perspectiva adotada para a solução do SOF é o desenvolvimento de um software que automatize o processo de atribuição dos produtos aos pedidos em carteira, denominado como processo de picking. O trabalho emprega a Computação Evolucionária como método de adaptação ao problema e utiliza a técnica dos Algoritmos Genéticos (AG) na formulação do modelo de busca de soluções. A concepção do software dar-se-á pela interconexão de um conjunto de dados estáticos que contempla o estoque disponível para venda em um período pré-determinado de tempo t e a carteira de pedidos solicitados em diferentes datas. A representação binária é utilizada para formular a programação das estruturas heurísticas de possíveis soluções e o Visual Basic for Applications (VBA) do Microsoft Office Excel é empregado como ferramenta computacional para a implementação do modelo proposto. A programação considera as restrições e os parâmetros de decisão de forma que maximização do faturamento seja o resultado otimizado do problema. A implantação do software gera um módulo que automatiza o processo de picking e apresenta resultados otimizados para o SOF, o que prove agilidade e aperfeiçoa a tomada de decisão de faturamento. Conclui-se por meio de testes experimentais que o AG desenvolvido é uma opção viável à solução do problema de SOF. Palavras-Chave: Algoritmos Genéticos; Processo de Picking; Sequenciamento de Faturamento. ABSTRACT PINTO, A. R. F. Genetic algorithm applied to the sequencing of picking and billing. 2012. 80 f. Master Dissertation (Master's Degree in Production Engineering) - Bauru School of Engineering, Universidade Estadual Paulista "Júlio de Mesquita Filho", Bauru, 2012. The disorders and uncertainties caused in the course of time, given the dynamics of change and systems complexity which include organizations, result in several situations in which managers need to find solutions which can extract the maximization of the entrepreneurial outcome. Therefore, the development of tools that can, at a given time and in an agile way, present a minimum number of options necessary to investigate the uncertainties is a necessary task in business environments. This dissertation aims to search for a solution to the Optimal Sequencing Billing (OSB ) problem. The perspective adopted for the solution of the OSB is the development of a software that automates the process of assigning products to backlog, named as “picking process”. The work employs the Evolutionary Computation as a method of adaptation to the problem and uses the technique of Genetic Algorithms (GA) in the formulation of the searching solutions model. The software design will come to be through the interconnection of a set of static data which includes the stock available for sale at a pre- determined period of time t and a backlog requested on different dates. The binary representation is used to formulate the scheduling heuristics structures of possible solutions and Visual Basic for Applications (VBA) in Microsoft Office Excel is a software tool used for the implementation of the proposed model. The program considers the constraints and decision parameters so that maximizing the billing is the result of optimized problem. The implementation of the software generates a module that automates the picking process and presents optimized results for the OSB, which provides agility and improves the decision making for billing. It was concluded by experimental tests that the GA developed is a viable option for solving the problem of OSB. Keywords: Genetic Algorithms; Picking Process; Billing Sequencing. LISTA DE FIGURAS Figura 1 - Fluxograma de desenvolvimento da pesquisa ......................................................... 20 Figura 2 - Estrutura de um algoritmo evolutivo ....................................................................... 24 Figura 3 - Diagrama que posiciona os algoritmos evolucionários como técnica de busca ...... 24 Figura 4 - Principais elementos de um algoritmo genético ...................................................... 27 Figura 5 - Fluxograma de funcionamento de um algoritmo genético simples ......................... 29 Figura 6 - Esquema de um algoritmo genético simples............................................................ 31 Figura 7 - Representação binária de um indivíduo ................................................................... 37 Figura 8 - Exemplo de seleção por roleta proporcional............................................................ 44 Figura 9 - Diagrama do operador de crossover de um ponto ................................................... 47 Figura 10 - Funcionamento do crossover uniforme ................................................................. 48 Figura 11 - Operador de mutação aleatória .............................................................................. 50 Figura 12 - Operador de inversão ............................................................................................. 50 Figura 13 - Esquema gráfico do elitismo.................................................................................. 53 Figura 14 - Representação do cromossomo do processo de picking ........................................ 61 Figura 15 - Interface do software ............................................................................................. 67 Figura 16 - Exemplo de execução do AG................................................................................. 68 Figura 17 - Lista do processo de picking .................................................................................. 70 Figura 18 - Lista de pendências a produzir............................................................................... 70 Figura 19 - Gráficos de convergência da primeira experimentação ......................................... 71 Figura 20 - Gráficos de convergência da segunda experimentação ......................................... 72 Figura 21 - Gráficos de convergência da terceira experimentação .......................................... 73 Figura 22 - Gráficos de convergência da quarta experimentação ............................................ 74 LISTA DE TABELAS Tabela 1 - Exemplo de alfabetos de esquemas e cálculos das strings de bits .......................... 33 Tabela 2 - Aptidão de indivíduos ............................................................................................. 39 Tabela 3 - Exemplo de cálculo da aptidão acumulada ............................................................. 45 Tabela 4 - Estoque de produtos disponíveis para venda e lista de pedidos em carteira ........... 59 Tabela 5 - Resultados estatísticos da primeira experimentação ............................................... 71 Tabela 6 - Resultados estatísticos da segunda experimentação ................................................ 72 Tabela 7 - Resultados estatísticos da terceira experimentação ................................................. 73 Tabela 8 - Resultados estatísticos da quarta experimentação ................................................... 74 LISTA DE QUADROS Quadro 1 - Analogia de termos entre algoritmos genéticos e a biologia. ................................. 26 Quadro 2 - Principais representações e os tipos de problemas onde melhor se aplicam .......... 35 Quadro 3 - Lógica do algoritmo de implementação da roleta .................................................. 43 Quadro 4 - Sequência de implementação e funcionamento do AG para o SOF ...................... 66 LISTA DE ABREVIATURAS E SIGLAS AE: Algoritmos evolucionários AG: Algoritmos genéticos CE: Computação evolucionária CFS: Sistemas classificadores NP: Não polinomial OG: Operador genético PE: Programação evolucionária PG: Programação genética SOF: Sequenciamento ótimo de faturamento VBA: Visual Basic for Applications SUMÁRIO 1 INTRODUÇÃO ................................................................................................................... 15 1.2. Problema de Pesquisa .................................................................................................. 17 1.3 Motivação e Justificativa .............................................................................................. 17 1.4. Objetivos ...................................................................................................................... 18 1.4.1. Objetivo Geral .................................................................................................... 18 1.4.2 Objetivos Específicos .......................................................................................... 18 1.5 Delimitação da Pesquisa ............................................................................................... 18 1.6 Método de Pesquisa Adotado ....................................................................................... 19 1.7 Estrutura da Dissertação ............................................................................................... 20 2 COMPUTAÇÃO EVOLUCIONÁRIA .............................................................................. 21 2.1 Teoria da Evolução Aplicada à Computação ............................................................... 21 2.2 Conceitos Fundamentais da CE .................................................................................... 22 2.3 Uma Breve História dos AEs........................................................................................ 22 2.4 Conceitos Básicos dos AEs .......................................................................................... 23 3 ALGORITMOS GENÉTICOS .......................................................................................... 25 3.1 Uma Breve História do AG .......................................................................................... 25 3.2 Conceitos Básicos do AG ............................................................................................. 25 3.3 Funcionamento de um AG ............................................................................................ 29 3.4 Conceitos dos Esquemas .............................................................................................. 32 3.5 Representação do Cromossomo.................................................................................... 35 3.5.1 Representação Binária ......................................................................................... 36 3.6 Geração da População Inicial ....................................................................................... 37 3.7 Função de Avaliação (Aptidão) .................................................................................... 39 3.8 Operadores Genéticos ................................................................................................... 40 3.9 Operador de Seleção ..................................................................................................... 41 3.9.1 Seleção por Roleta (Roulette Wheel) ................................................................... 43 3.10 Operador de Cruzamento (Crossover) ........................................................................ 45 3.10.1 Crossover de Um Ponto ..................................................................................... 46 3.10.2 Crossover Uniforme .......................................................................................... 47 3.11 Operador de Mutação ................................................................................................. 48 3.12 Geração da Nova População (Atualização) ................................................................ 51 3.12.1 Troca de Toda População (Substituição Geracional) ........................................ 51 3.12.2 Troca de Toda a População com Elitismo ......................................................... 52 3.13 Parâmetros .................................................................................................................. 53 3.14 Critérios de Parada...................................................................................................... 54 3.15 Verificação de Desempenho ....................................................................................... 54 3.16 Teorema Fundamental dos Esquemas ........................................................................ 55 4 IMPLEMENTAÇÃO DO ALGORITMO GENÉTICO PROPOSTO ........................... 59 4.1 Representação do Problema.......................................................................................... 59 4.2 Faturamento Máximo (FM) .......................................................................................... 60 4.3 Representação do Cromossomo.................................................................................... 61 4.4 Geração da População Inicial ....................................................................................... 61 4.5 Função de Aptidão ........................................................................................................ 62 4.6 Operador de Seleção ..................................................................................................... 64 4.7 Operador de Crossover e Mutação ............................................................................... 65 4.8 Geração da Nova População ......................................................................................... 65 4.9 Critério de Parada ......................................................................................................... 65 4.10 Metodologia de Implementação ................................................................................. 66 5 EXPERIMENTAÇÃO DO SOFTWARE .......................................................................... 67 5.1 Experimentação do Software ........................................................................................ 67 5.2 Relatórios Disponíveis .................................................................................................. 69 5.3 Análise de Desempenho ............................................................................................... 71 6 CONCLUSÃO ...................................................................................................................... 76 REFERÊNCIAS ..................................................................................................................... 78 15 1 INTRODUÇÃO A dinâmica das mudanças em ambientes empresariais, cada vez mais complexos, e a busca por adaptações que proporcionem respostas imediatas ao mercado competitivo, fundamentam a importância de ações que identifiquem o número mínimo de opções necessárias para restringir, de certa maneira, a incerteza. Recentemente, tornou-se comum entre os pesquisadores a inspiração nos mecanismos genéticos evolutivos como uma tentativa de desenvolver ferramentas de mensuração quantitativa que possam, em dado momento, fornecer subsídios, de forma ágil, ao processo de otimização em tomadas de decisões. No âmbito empresarial, os princípios de genética evolutiva se tornaram de grande importância e de uso crescente pela gestão organizacional como uma maneira de compreender as estratégias de negócios (MITCHELL; TAYLOR, 1999; PHILLIPS; SU, 2009). O avanço tecnológico e a incrível habilidade da evolução biológica em produzir estruturas ótimas motiva os cientistas a simularem estes mecanismos em problemas de otimização e adaptação (RUNARSSON; JONSSON, 1999). A prática da gestão exige otimização e o desenvolvimento de ferramentas computacionais para esse fim tem se beneficiado muito com os avanços nos estudos da biotecnologia. Em especial, a Computação Evolucionária (CE) tem gerado soluções viáveis quando aplicada em problemas complexos de otimização e tomada de decisões, em uma ampla variedade de atividades e projetos, das diferentes áreas, dos mais diversos tipos de organizações (MITCHELL; TAYLOR, 1999; YANG, 2005; YANG; KOZIEL, 2010). Nesse sentido, a Engenharia de Produção têm se utilizado, cada vez mais, de conceitos e técnicas oriundas da CE. Um problema relevante e ainda pouco abordado pela Engenharia de Produção é o Sequenciamento Ótimo de Faturamento, que para efeito de estudo é denominado de SOF. Por apresentar um grande número de possíveis combinações que devem ser obrigatoriamente avaliadas, o SOF caracteriza-se por ser um problema de natureza combinatorial complexa. Especificamente, esta complexidade é causada pelas restrições de quantidade e por parâmetros que a empresa define como critérios de decisão de faturamento, que podem ser a data de atendimento do pedido, questões logísticas na entrega, importância do cliente, etc. Em meio aos diversos paradigmas de otimização computacional existentes, a Programação Dinâmica, por exemplo, é um método eficiente quando utilizado na resolução de problemas de otimização combinatória e que poderia ser avaliado como uma provável técnica de solução para o SOF. No entanto, diante à natureza do problema, presume-se que o emprego 16 de uma técnica exata de otimização pode não ser uma opção viável, já que, o SOF pertence ao grupo dos problemas conhecidos pela comunidade científica como intratáveis, os titulados NP-completos, ou seja, aqueles em que ainda não se conhecem algoritmos polinomiais rápidos para resolvê-los de forma exata (LINDEN, 2008; ALMEIDA; VIANA; THOMAZ, 2009; YANG; KOZIEL, 2010). Um exemplo clássico deste tipo de problema é o do caixeiro viajante, que estando em qualquer n cidade pode partir para qualquer uma das outras n-1 cidades para a segunda n-2 restantes até chegar à última. Isso resulta em um número de opções igual a n(n-1)(n- 2)...(2)(1)=n!, onde para 100 cidades tem-se 10158 opções, o que levaria a um grande número de possíveis combinações a serem testadas. Teoricamente, um tempo igual a 10141 anos para encontrar a melhor solução (LINDEN, 2008; YANG; KOZIEL, 2010). Logo os tempos de respostas para modelos que possuam um grande número de variáveis e restrições, principalmente binárias, são ainda impraticáveis pelos métodos tradicionais de busca local. Além disso, o comportamento incerto sempre presente no mundo real dos sistemas faz com que os modelos de otimização sejam afetados por fatores e parâmetros complexos e, na prática, nem sempre é possível encontrar as melhores soluções. Normalmente, soluções viáveis, ou seja, boas o suficiente, e realizáveis em uma escala de tempo razoável são a escolha (YANG, 2005; LINDEN, 2008; ALMEIDA; VIANA; THOMAZ, 2009; YANG; KOZIEL, 2010). Dentre as técnicas mais utilizadas na obtenção de soluções aproximadas, a Busca Tabu é uma abordagem de destaque na resolução de problemas de decisão sequencial a ser analisada como método de decisão do SOF. Todavia, conforme abordado por Linden (2008), o fato de ainda não haver um algoritmo polinomial rápido para resolver todos os problemas de otimização não-lineares de forma exata faz-se da CE uma opção apropriada. Um método alternativo de adaptação à complexidade pertencente ao campo da CE e muito utilizado pela comunidade científica são os AGs. Em problemas de atribuição os AGs têm se mostrado satisfatórios em comparação a outros métodos na resolução de problemas de natureza semelhante e sua eficácia é comprovada pelo grande número de trabalhos publicados pela comunidade científica das mais diversas áreas (MITCHELL; TAYLOR, 1999; YANG, 2005; LINDEN, 2008; ALMEIDA; VIANA; THOMAZ, 2009; YANG; KOZIEL, 2010). Embora na investigação bibliográfica realizada não tenha sido encontrado nenhum trabalho em que se fez alusão ao AG para problemas de SOF, a sua aplicação prática nesta pesquisa é, portanto, fundamentada na resolução de problemas semelhantes apresentados na literatura disponível. A perspectiva adotada para a solução do SOF é a aplicação do AG à 17 automação do processo de picking, ou seja, na forma de designar quais produtos e quantidades serão faturados a cada cliente. Esse processo trata especificamente da atribuição ótima dos produtos disponíveis para venda à Pj pedidos visando satisfazer as necessidades da CP de forma ágil e eficiente, respeitando determinadas restrições e parâmetros de decisão pré- estabelecidos de forma que maximizar o faturamento seja o resultado otimizado para o SOF. 1.2 Problema de Pesquisa Essencialmente, o SOF pode ser descrito como um problema de atribuição de n produtos para atender Pj pedidos dado o estoque de produtos disponíveis para a venda (PA) e a carteira de pedidos (CP) em determinado momento t. Seja, então, um conjunto de n produtos, de forma que o vetor X representa PA, X = {x1, x2,...,xn} e CP = {P1, P2,...,Pj}, os produtos devem ser agrupados em j pedidos não vazios e não sobrepostos. Logo, ao considerar que cada pedido pode demandar diferentes produtos e que um mesmo item pode ser requisitado por j pedidos, reduz-se o SOF a um problema de otimização, em que o resultado esperado é a maximização do faturamento, a depender do conjunto específico de parâmetros e critérios de decisão utilizados. 1.3 Motivação e Justificativa Há uma vasta tecnologia de gestão que tem como objetivo oferecer ferramentas que apresentem um melhor gerenciamento de todos os recursos disponíveis às organizações. No entanto, em casos reais, problemas de SOF são ocasionados por restrições ou falhas na concepção dos sistemas de gestão, que podem ser atribuídas, em sua maioria, às desordens e incertezas provocadas no decorrer do tempo face à dinâmica das mudanças e a complexidade dos sistemas que abrangem as organizações. É, então, inevitável que os modelos de gestão nem sempre consigam prever toda a variabilidade do cenário empresarial ou encontrem soluções aceitáveis em curto espaço de tempo. Em determinadas situações, na medida em que se vai formando a CP, é comum a ocorrência de erros, além da emergência e a surpresa irredutível sempre presente no ambiente de negócios, que afetam as decisões de faturamento e acarretam diversas situações em que se devam encontrar soluções para o SOF. O fato é que a frequência de pedidos tem aumentado consideravelmente nos últimos anos, já que, objetivando reduções nos estoques, os clientes procuram fazer pedidos cada vez menores e com intervalos de tempo também menores, o que demanda um aumento no volume das operações de várias outras áreas dentro das organizações, em particular as financeiras, logísticas e de produção. Considerando que a carteira de pedidos é ininterruptamente renovada com novas demandas, alterações ou cancelamentos, e que, em dado momento, a 18 quantidade de produtos pode ser insuficiente para atender os diferentes pedidos, a busca pela melhor solução de um problema de SOF, pode se tornar uma tarefa complexa com a qual os gestores têm de lidar. Dessa forma, resolver o SOF de forma satisfatória sem o uso de uma ferramenta adequada é, na maioria das vezes, muito difícil, de um modo geral demanda muito trabalho, dado às restrições e critérios de decisão de faturamento específicos a cada caso. Evidentemente que, erros no faturamento, atrasos ou pedidos incompletos, podem ocasionar trabalhos desnecessários, aumento de custos, insatisfação do cliente e perda nas vendas. Ao considerar que os gestores necessitam tomar decisões de forma ágil e que resultem em uma série de ações consistentes, acredita-se ser de grande valia o desenvolvimento de um estudo mais detalhado que ofereça uma solução satisfatória para o problema apresentado. Em síntese, a possibilidade de desenvolver uma ferramenta computacional capaz de oferecer uma solução automática satisfatória diante às eventuais ocorrências do problema apresentado motiva a realização desta pesquisa. 1.4 Objetivos 1.4.1 Objetivo geral Este trabalho tem como objetivo principal desenvolver um software que automatize o processo de picking e apresente uma solução otimizada para o problema de SOF. 1.4.2 Objetivos Específicos Os objetivos específicos deste trabalho são: 1. Aperfeiçoar o processo de tomada de decisão de faturamento; 2. Minimizar os custos operacionais do processo de picking e faturamento; 3. Maximizar o faturamento de acordo com os parâmetros pré-estabelecidos; 4. Possibilitar que a área de produção tenha uma visão atualizada das necessidades de demanda. 1.5 Delimitação da Pesquisa A busca por uma solução otimizada para o problema de SOF utilizando AG é o enfoque dado a esta pesquisa. No entanto, a existência de diferentes organizações, atuando nos mais variados mercados, cada qual com suas peculiaridades e critérios decisórios específicos que mapeiem suas políticas diversas, faz com que o SOF seja um problema de difícil generalização. Em concomitância com os objetivos apresentados, o escopo desta pesquisa é o desenvolvimento de um software que apresente soluções otimizadas para 19 problemas de SOF específicos às organizações que necessitam realizar o processo de picking antes do faturamento. 1.6 Método de Pesquisa Esta dissertação classifica-se como sendo uma pesquisa aplicada no qual emprega o método dedutivo por meio de uma abordagem quantitativa (GIL, 1991; BERTO; NAKANO, 1998; BERTO; NAKANO, 1999; BERTRAND; FRANSOO, 2002; GAVIRA; 2003; MARCONI; LAKATOS, 2003; SILVA; MENEZES, 2005). Em relação à formulação do AG, este segue metodologicamente as fases práticas abordadas no referencial teórico, sendo o Visual Basic for Applications (VBA) do Microsoft Office Excel a ferramenta utilizada para a programação computacional do modelo proposto. O software será implementado e submetido a testes por meio de um microcomputador com processador Core I5 de 2.3GHz, 8 GByte de RAM e 750 GByte de HD. Na concepção do programa os parâmetros de decisão serão pré- configurados de forma que não poderá haver processo de picking de um produto sem saldo de estoque ou de quantidades parciais quando não aceito pelo cliente. O sistema irá fornecer relatórios de picking para faturamento e do que é necessário produzir para que todos os clientes sejam atendidos conforme os prazos negociados, sendo que, a preferência de faturamento será por ordem crescente de data de entrega dos pedidos. Em síntese, o AG é implementado por meio de um conjunto de parâmetros de forma que a obtenção da melhor solução para o SOF está sujeita às soluções otimizadas de Pj pedidos que compõem a CP. Dessa forma, a partir de uma solução inicial não satisfatória, o algoritmo repete ciclos de evolução para encontrar outra solução melhor que a anterior até que se satisfaça o critério de parada. A representação binária aleatória é usada para formular as estruturas heurísticas de atribuição dos produtos aos pedidos, onde o número de gerações é dado pelo usuário para no máximo 200 indivíduos a cada execução. A função aptidão penalizará soluções implausíveis por meio de punições corretivas correspondentes ao valor de faturamento de cada bit infrator. O método de seleção adotado é o da roleta proporcional que realizará a seleção de 50% do total de indivíduos gerados. O cruzamento será realizado pelo operador de crossover de um ponto, com probabilidade fixada em 100% dos pais selecionados, já o operador de mutação será aplicado a 50% dos filhos resultantes do crossover pela técnica de troca aleatória dos bits, no qual, o usuário terá a opção de informar a probabilidade desejada. A troca de toda a população com elitismo é a técnica adotada para a substituição da população onde somente o melhor indivíduo é transferido integralmente para a próxima geração. O critério de parada é determinado pelo número de gerações especificadas pelo usuário ou a chegada ao valor ótimo da função de aptidão. As análises da funcionalidade 20 do software serão obtidas em função das experimentações realizadas e a avaliação final pelo conjunto dos resultados alcançados. A figura 1 apresenta o fluxograma com as etapas do desenvolvimento desta pesquisa. Figura 1 - Fluxograma de desenvolvimento da pesquisa Fonte: Autor 1.7 Estrutura da Dissertação A dissertação está estruturada em capítulos, resumidos da seguinte forma: No capítulo 2 é feita uma breve explanação sobre a Computação Evolucionária (CE) e os Algoritmos Evolucionários (AEs), abordando desde os fatos históricos até seus conceitos e métodos de funcionamento. O capítulo 3 apresenta uma revisão bibliográfica sobre a teoria e aplicação dos Algoritmos Genéticos (AGs) ao qual fornece um arcabouço teórico que provê o suporte à formulação da estrutura genética adequada para o desenvolvimento do modelo e fundamenta os passos necessários à solução do problema que se pretende estudar. O capítulo 4 exprime a modelagem matemática e a implementação computacional do software desenvolvido. O capítulo 5 traz a interface do programa, as simulações experimentais e a análise conjunta dos resultados obtidos a cada execução. O último capítulo apresenta as conclusões relativas ao objetivo do trabalho, as principais contribuições e as sugestões de continuidade para futuros estudos sobre o assunto. Definição do problema Otimizar o SOF Pesquisa bibliográfica sobre Algoritmos Genéticos (AG) Estudar estrutura genética adequada para o SOF Formulação do modelo de programação matemática Construção e implementação computacional do AG Experimentação e validação (AG) Análise dos resultados e conclusões Redação final 21 2 COMPUTAÇÃO EVOLUCIONÁRIA Este capítulo apresenta uma breve explanação sobre a teoria da evolução genética e das pesquisas que inspiraram suas aplicações para o desenvolvimento da Computação Evolucionária (CE), abordando conceitos e fatos históricos desde sua constituição e publicação. Ao longo da seção são apresentados os tipos de Algoritmos Evolucionários (AEs) e suas estruturas funcionais comuns. O objetivo não é detalhar toda a CE e suas técnicas, mas fixar uma base teórica que facilite um melhor entendimento dos Algoritmos Genéticos (AGs). 2.1 Teoria da Evolução Aplicada à Computação Aceita por praticamente toda a comunidade acadêmica mundial, a moderna teoria da evolução combina a genética e as ideias de Darwin para dominar a biologia, e graças ao progresso científico hoje se sabe que o armazenamento e a transmissão das informações genéticas funcionam em nível molecular. Continuamente, os avanços nos estudos e simulações dos processos de evolução genética enriquecem a visão da ciência sobre a complexidade dos mecanismos moleculares ao explicar a níveis mais profundos porque a evolução acontece (BOWLER, 2004; CARVALHO, 2004; LINDEN, 2008; PHILLIPS; SU, 2009; AYALA, 2010). Em contrapartida, a recente explosão de conhecimentos e técnicas na área da biotecnologia direcionadas a compreender as características gerais de sistemas adaptativos complexos tem afetado também, já há algum tempo, direções futuras na previsão de novas tecnologias. Os pesquisadores discutem cada vez mais como estas técnicas podem ser aplicadas a outras áreas científicas onde a adaptabilidade às mudanças é observada e necessária ao bom funcionamento do sistema (MITCHELL; TAYLOR, 1999; BOWLER, 2004; PHILLIPS; SU, 2009). Para os cientistas, os conceitos de genética e seleção natural passaram a não ser mais dirigidos somente a organismos biológicos. Desde que justificados com apoio de uma teoria sólida com evidência empírica, esses conceitos podem ser aplicados a qualquer organismo que se reproduz de modo a envolver tanto a hereditariedade como a variação (MICHALEWICZ, 1996; LINDEN, 2008; GHISELIN, 2009). A área de inteligência artificial tem se beneficiado muito com a inspiração nestes mecanismos. Em especial as várias abordagens desenvolvidas de forma independente para explorar o ramo da computação, chamadas coletivamente de computação evolucionária (CE), parecem se adequar a capacidade biológica de pesquisar em paralelo todo o espaço de busca para encontrar melhores soluções candidatas a resolução de problemas específicos. A 22 aplicação de diversos algoritmos evolucionários (AEs) tem proporcionado grandes progressos na resolução de problemas computacionais nas mais variadas áreas (MITCHELL, 1996; MITCHELL; TAYLOR, 1999; YANG, 2005; YANG; KOZIEL, 2010; LINDEN, 2008). 2.2 Conceitos Fundamentais da CE A CE foi escolhida como o termo geral que engloba todas as áreas de computação inspiradas na natureza evolutiva e biológica. É uma ciência que aplica conceitos da natureza, por meio de paradigmas computacionais dos processos genéticos de seleção natural, como uma ferramenta alternativa para a solução de problemas computacionais complexos do mundo real de forma otimizada (MITCHELL; TAYLOR, 1999; YANG, 2005; LINDEN, 2008). O objetivo final da CE é criar algoritmos inteligentes que, inspirados na teoria evolutiva e biológica, tenham a capacidade de aprender e se adaptar à necessidade de determinado ambiente do qual são componentes, de forma que ao longo do processo evolutivo seja possível gerar indivíduos que sejam cada vez melhores às soluções de problemas específicos. Segundo Von Zuben (2000), a família de algoritmos que englobam toda a CE são coletivamente denominados de Algoritmos Evolucionários (AEs). 2.3 Uma Breve História da CE A primeira tentativa de representação da teoria de Darwin por meio de um modelo matemático surgiu em 1930 com o livro de Fisher “The Genetic Theory of Natural Selection”. Já na década de 40, muitos cientistas começaram a tentar se inspirar na natureza para criar o ramo da inteligência artificial. No entanto, foi nos anos 50 que diversos cientistas evolucionistas buscavam de forma independente desenvolver sistemas artificiais inspirados em sistemas naturais. Neste período, alguns biólogos usaram computadores com a finalidade de realizar experimentos para simular a evolução, e na área da engenharia eram desenvolvidas ferramentas de otimização para resolver problemas que eram insolúveis computacionalmente até aquela época (GOLDBERG, 1989; OBITKO, 1998; MITCHELL; TAYLOR, 1999; CARVALHO, 2004; YANG, 2005; LINDEN 2008). Em 1960, Ingo Rechenberg com seu trabalho “Evolutionsstrategie” introduziu a Computação Evolucionária (CE). Em termos históricos, três AEs foram desenvolvidos independentemente e formaram a espinha dorsal do campo da CE: Algoritmos genéticos (AG), inventado por Holland em 1962; Programação evolucionária (PE), desenvolvida em 1962 por Fogel, Owens e Walsh, na qual candidatos a soluções de tarefas eram representados como máquinas de estados finitos; Estratégia evolucionária (EE), concebidas por Ingo Rechenberg em 1963, desenvolvidas por Hans-Paul Schwefel, e mais tarde utilizadas por 23 Peter Bienert para resolver problemas de otimização técnica (GOLDBERG, 1989; BÄCK; SCHWEFEL, 1993; MITCHELL, 1996; OBITKO, 1998; MITCHELL; TAYLOR, 1999; VON ZUBEN, 2000; CARVALHO, 2004; GROSKO; GORSKI; DIAS, 2006; LINDEN 2008). No ano de 1989 Booker, Goldberg e Holland inventaram um método que combina a adaptação de aprendizagem e evolução que foi denominado como Sistemas de Classificadores (CFS). Em 1992 John Koza usou AGs para gerar e desenvolver automaticamente funções e programas computacionais para realizar certas tarefas e chamou seu método de Programação Genética (PG). Atualmente, existem cinco diferentes paradigmas de computação inspirados na natureza evolutiva: AG, PE, EE, CFS e PG (BÄCK; SCHWEFEL, 1993; MITCHELL, 1996; OBITKO, 1998; VON ZUBEN, 2000; CARVALHO, 2004; LINDEN 2008). 2.4 Conceitos Básicos dos AEs Os AEs são baseados na ideia central de processos de aprendizagem coletiva, por meio da evolução de uma população de indivíduos potenciais ou candidatos à solução de um determinado problema, usando operadores inspirados na variação genética e seleção natural (GOLDBERG, 1989; BÄCK; SCHWEFEL, 1993; MITCHELL, 1996; MITCHELL; TAYLOR, 1999; VON ZUBEN, 2000; LINDEN 2008). A principal característica dos AEs é a possibilidade de serem aplicados na solução de problemas complexos, via um conjunto de técnicas e procedimentos genéricos adaptáveis, onde muitos destes problemas requerem a busca por um espaço enorme de possibilidades de soluções. A vantagem mais significativa está na sua robustez e flexibilidade, ao possibilitar resolver problemas pela simples descrição matemática do que se quer ver presente na solução. (MITCHELL; TAYLOR, 1999; VON ZUBEN, 2000; LINDEN 2008). É peculiar na aplicação dos AEs não haver a necessidade de se indicar explicitamente todas as suas etapas de implementação, pois as ferramentas de propósitos gerais são as mesmas para uma ampla gama de problemas, com apenas certas especificidades a cada caso (VON ZUBEN, 2000). Um mesmo AG, por exemplo, pode ser usado para descobrir o máximo de toda e qualquer função de n variáveis sem nenhuma alteração das estruturas de dados e procedimentos adotados, alterando-se, apenas, a sua função de avaliação (LINDEN 2008). Dessa maneira, apesar de todos os AEs partilharem de uma estrutura conceitual comum, não devem ser considerados “prontos para uso”, mas sim um elenco de procedimentos gerais que podem ser prontamente adaptados a cada contexto de aplicação (VON ZUBEN, 2000; LINDEN 2008). Seja P(t)={xt 1, ... , x t n} a população de cromossomos 24 na geração t, na qual cada indivíduo é um candidato à solução do problema em questão, a estrutura básica de busca pela melhor solução de um AE é demonstrada na figura 2 (MICHALEWICZ, 1996). Figura 2 - Estrutura de um algoritmo evolutivo Fonte: (MICHALEWICZ, 1996) Em síntese, os AEs são heurísticas de otimização global que fazem parte de um ramo de busca da computação chamado de Técnicas Aleatórias Guiadas. Ainda que sejam métodos fortemente estocásticos, não são totalmente aleatórios, pois usam informações do estado corrente para guiar a pesquisa (LINDEN, 2008). A figura 3 ilustra o diagrama que posiciona os AEs como técnica de busca, e o capitulo 3 descreverá em detalhes todo o funcionamento dos AGs, uma vez que, representa a técnica de solução escolhida para estudo e aplicação ao problema de pesquisa. Figura 3 - Diagrama que posiciona os algoritmos evolucionários como técnica de busca Técnicas de Busca Baseadas em Cálculo Aleatórias Guiadas Enumerativas Algoritmos Evolucionários Resfriamento Simulado Estratégias Evolucionárias Algoritmos Genéticos Programação Genética Paralelos Sequenciais Fonte: Adaptado de Linden (2008) Procedimento do Programa Evolutivo Início t ← 0 inicialize P(t) avalie P(t) Enquanto (não condição de parada) faça Início t ← t + 1 selecione P(t) a partir de P(t - 1) altere P(t) avalie P(t) Fim Fim 25 3 ALGORITMOS GENÉTICOS Este capítulo apresenta uma revisão bibliográfica a respeito da teoria e aplicação dos Algoritmos Genéticos (AGs). Ao longo das seções são discutidas e explicadas as principais técnicas utilizadas em AGs. O objetivo não é esgotar o assunto ou torná-lo extenuante, mas fornecer um embasamento teórico suficiente para o desenvolvimento de um modelo de solução do problema que se pretende pesquisar. 3.1 Uma Breve História do AG O AG foi criado por John Holland na década de 60 em conjunto com seus alunos e colegas da Universidade de Michigan. Em contraste à EE e à PE, o objetivo de Holland não era desenvolver projetos de algoritmos para resolver problemas específicos. O escopo, até então, era estudar formalmente os fenômenos de adaptação, evolução e seleção natural como ocorre na natureza, e desenvolver formas de modelos heurísticos em que estes mecanismos (inputs sensoriais do ambiente) pudessem ser matematicamente formalizados e importados para sistemas computacionais. Ao invés de utilizar valores reais, Holland utilizou cadeias binárias, em que a mutação e o crossover se tornaram fontes de variações aleatórias de bits na população. Em 1975, ele publicou sua inovação no livro “Adaptation in Natural and Artificial Systems”, hoje considerada uma referência bibliográfica de extrema relevância, onde formalizou e fundamentou matematicamente suas técnicas por meio de um firme alicerce teórico baseado em “esquemas”, conforme será abordado na seção 3.4. No mesmo ano De Jong (1975) utilizou pela primeira vez os AGs em otimização de parâmetros, estabelecendo suas bases de aplicações técnicas. Em 1989, David Goldberg populariza os AG’s ao editar “Genetic Algorithms in Search, Optimization and Machine Learning”. Hoje em dia, numerosas modificações do AG canônico descrevem algo muito longe da sua concepção original, e são aplicados a muito mais campos conforme indicado por Holland (MITCHELL, 1996; OBITKO, 1998; BÄCK; SCHWEFEL, 1999; MITCHELL; TAYLOR, 1999; VON ZUBEN, 2000; CARVALHO, 2004; LINDEN 2008). 3.2 Conceitos Básicos do AG Os AGs são um ramo dos AEs, e podem ser definidos como um método genérico adaptativo de busca que imita o processo genético e Darwiniano de evolução natural, por meio da seleção, reprodução e sobrevivência dos mais aptos entre estruturas de strings, com uma troca estruturada, ainda que aleatória, de informações (PACHECO, 1999; GOLDBERG, 1989; LINDEN 2008). 26 Diferente das técnicas convencionais, os AGs são heurísticas de otimização global em que se utiliza um conjunto inicial randômico de soluções chamado de população, onde cada indivíduo desta população é candidato à solução do problema. Assim, a função de otimização representa o ambiente no qual a população inicial se encontra. Os cromossomos artificiais são compostos por cadeias de bits, usualmente referidos como genes, e os possíveis valores que um determinado gene pode assumir são denominados alelos (GOLDBERG, 1989; MITCHELL, 1996; GEN; CHENG, 1997; MITCHELL; TAYLOR, 1999; PACHECO, 1999). O quadro 1 apresenta uma analogia entre os termos usados em AGs originados da biologia e o sistema natural. Quadro 1 - Analogia de termos entre algoritmos genéticos e a biologia Termo Biologia Algoritmos Genéticos Cromossomo Conjunto de genes de um organismo que constituem um ser vivo. Indivíduo, String (de bits) que representa uma solução para o problema (variáveis e parâmetros são combinados). Gene Unidade de hereditariedade transmitida pelo cromossomo e que controla as características do organismo. Parâmetro codificado no cromossomo, ou seja, um elemento da string (podem assumir valores binários, inteiros ou reais). Genótipo Composição genética contida no cromossomo. Informação contida no cromossomo (estrutura). Fenótipo Manifestação física de um gene no organismo, por exemplo, pele lisa ou rugosa. Estrutura construída a partir do genótipo (interação com o ambiente que determina o conjunto de parâmetros). Alelo Uma das formas alternativas de um gene. Valores que o gene pode assumir. Locus Local fixo num cromossomo onde está localizado determinado gene ou marcador genético. Posição onde esta localizado um elemento da string, o “gene”. Geração Designação do grupo de indivíduos que têm os mesmos progenitores. Ciclo por meio dos operadores genéticos Fonte: Adaptado de Lacerda, Carvalho e Ludermir (1999); Pacheco (1999) A fundamentação teórica do AG baseia-se, então, na analogia de melhorar uma população de soluções de determinado problema por meio do desenvolvimento de modelos de mudanças evolutivas do capital genético dos cromossomos (DE JONG, 1988; BIEGLER; GROSSMANN, 2004; GROSKO; GORSKI; DIAS, 2006). Os principais elementos da 27 aplicação prática de um AG são apresentados na figura 4 e posteriormente detalhados no decorrer deste capítulo. Figura 4 - Principais elementos de um algoritmo genético Fonte: Adaptado de Argoud (2007) Todos os elementos ilustrados se interagem sequencialmente durante todo o processo de execução do algoritimo, cada qual com suas operações básicas especificas. A busca por soluções é realizada de forma paralela e estruturada utilizando-se de técnicas de transição probabilísticas de forma que é possível guiar a busca em regiões de pontos de “alta aptidão” (melhor solução), e que tem como objetivo encontrar o extremo (mínimo ou máximo) de uma função (GOLDBERG, 1989; CARVALHO, 2004; LINDEN 2008). Por serem métodos de busca aleatória ignoram o aproveitamento de regiões promissoras do espaço de soluções e não ficam estagnados simplesmente pelo fato de terem encontrado um máximo local, pelo contrário, continuam em busca de indivíduos mais aptos ou soluções que sejam globalmente mais significativas. Segundo Von Zuben (2000) e Linden (2008) estas questões opõem os AGs aos métodos como gradiente (hill climbing) que facilmente se prendem a máximos locais sem realizar uma exploração do espaço de busca global. O AG realiza a busca a partir de um grande número de pontos que representam possíveis soluções dentro de todo o espaço de soluções (universo de soluções), e não de um 28 ponto único. No entanto, não procura em todos os pontos possíveis, mas sim em um subconjunto destes pontos, chegando a uma sequência de diferentes subpopulações antes de apresentar a melhor solução (GOLDBERG, 1989; OBITKO, 1998; MITCHELL; TAYLOR, 1999; LINDEN, 2008). Apesar de serem algoritmos probabilísticos e apresentarem etapas não-determinísticas em seu desenvolvimento, não são puramente aleatórios, pois combinam elementos de procura direcionada e estocástica explorando informações históricas dos resultados já obtidos. Ou seja, o AG utiliza informações da função objetivo ou de aptidão para encontrar novos pontos de busca onde são esperados melhores desempenhos (VON ZUBEN, 2000; CARVALHO, 2005; LINDEN, 2008). É possível concluir que os AGs são sistemas não lineares com comportamento fortemente ecológico que combinam mudanças aleatórias com processos probabilísticos, são, portanto, estocásticos. Iniciando um AG com a mesma população e o mesmo conjunto de parâmetros os resultados encontrados raramente são reprodutíveis ou, necessariamente, os mesmos. A mutação, por exemplo, raramente gera indivíduos iguais, o que dificilmente repete um mesmo resultado de um experimento para outro (TANOMARU, 1995; PACHECO, 1999; LINDEN, 2008). Dessa forma, por ser uma técnica probabilística, não constitui um algoritmo de busca da solução ótima, o AG pode então encontrar boas soluções, mas não assegura a obtenção do melhor resultado em todas as suas execuções (TANOMARU, 1995; YANG, 2005). Porém, dentre as principais características que fazem do AG uma técnica de busca bem sucedida (DE JONG, 1988; GOLDBERG, 1989; BÄCK; SCHWEFEL, 1993; MICHALEWICZ, 1996; MITCHELL; TAYLOR, 1999; CARVALHO, 2004; LINDEN, 2008) destacam-se: � A simplicidade das operações, facilidade de implementação e um bom desempenho em sua execução; � Trabalha com a codificação do conjunto de parâmetros em uma string e não com os próprios parâmetros; � São muito flexíveis, aceitam sem grandes dificuldades uma infinidade de alterações e permitem fácil hibridização; � Não são totalmente aleatórios, fazem uma busca paralela de forma dirigida e simultânea; 29 � São extremamente eficientes no seu objetivo de varrer o espaço de soluções na busca da região onde provavelmente encontra-se o máximo ou o mínimo global; � São capazes de lidarem com funções discretas e contínuas sem serem afetados por descontinuidades na sua função ou em suas derivadas; � Fornecem um conjunto de heurísticas de pesquisa eficiente apresentando uma melhoria significativa sobre os métodos tradicionais sem a necessidade de incorporação de conhecimentos altamente específicos. 3.3 Funcionamento de um AG O funcionamento do AG pode ser descrito como um processo contínuo que repete ciclos de evolução controlados por parâmetros e critérios de parada pré-definidos pelo usuário (PACHECO, 1999). Por ser baseada na evolução biológica, cada iteração de todo este processo é chamado de geração e todo o conjunto de sucessivas gerações a serem testadas por uma função de aptidão, visando encontrar uma solução (adaptação) satisfatória aos critérios de parada, é denominado de execução. A figura 5 esboça o fluxograma de funcionamento de um AG simples. Figura 5 – Fluxograma de funcionamento de um algoritmo genético simples Fonte: Autor 30 Na figura 5 é possível observar que quando a condição de parada é atendida o algoritmo para e retorna o melhor indivíduo como a solução do problema, quando não, o algoritmo irá executar um incremento de iterações que consiste na aplicação dos OGs à atual população, na qual irá gerar uma nova solução que, do mesmo modo que a anterior, será submetida à função de avaliação, e esse processo irá se repetir, enquanto necessário, durante todo o processo de execução do algoritmo. Conforme demonstrado, a essência do funcionamento de um AG é toda fundamentada na técnica de geração e teste, utilizando-se de informações de custo ou recompensa para realizar uma procura contínua por melhores resultados. Inicialmente, fundamentadas por um conjunto pré-determinado de parâmetros, as informações sobre o problema são representadas nos cromossomos de acordo com o esquema de codificação escolhido. A partir daí, são gerados aleatoriamente n indivíduos que irão compor uma população inicial (OBITKO 1998; LACERDA; CARVALHO; LUDERMIR, 1999; MITCHELL; TAYLOR, 1999; YANG, 2005; LINDEN, 2008). Cada indivíduo gerado recebe, então, uma avaliação denominada de aptidão, que é uma quantificação da sua qualidade como solução do problema em questão. O operador de seleção preconiza os melhores indivíduos, ou seja, todo o processo depende da aptidão da string de forma a simular a sobrevivência dos mais aptos. Uma porcentagem dos cromossomos mais adaptados é, então, mantida, enquanto os restantes são descartados (MITCHELL, 1996; PACHECO, 1999; CARVALHO, 2004; LINDEN, 2008). Baseado no processo de avaliação, os cromossomos selecionados são, posteriormente, submetidos a um processo evolucionário de modificação genética por meio de operadores genéticos (OGs), tais como: recombinação sexual (crossover) e mutação. A reprodução é equivalente à sexuada e a mutação corrobora para que haja diversidade, evitando que haja convergência prematura (BÄCK; SCHWEFEL, 1993; PACHECO, 1999; VON ZUBEN, 2000; BIEGLER; GROSSMANN, 2004; GROSKO; GORSKI; DIAS, 2006; LINDEN, 2008). Esse processo de avaliação se encarregará de fazer com que a população evolua, já que, os indivíduos com melhor grau de adaptação terão maiores chances de sobreviver e repassar o seu material genético para as próximas gerações. Assim, em cada geração de uma nova população, um novo conjunto de strings artificiais é criado usando bits e partes aptas da geração anterior de forma a semear a população inicial da geração seguinte com as melhores soluções encontradas anteriormente (LACERDA; CARVALHO; LUDERMIR, 1999; CARVALHO, 2004; YANG, 2005; ZUKHRI; OMAR, 2006; ROSA; LUZ, 2009). 31 Ocasionalmente a nova população de indivíduos e sua eficácia na resolução do problema é novamente testada pelo processo de avaliação, que deverá eventualmente gerar um novo indivíduo no qual resultará na mais adequada (a sobrevivente), se não a ótima solução para o problema (OBITKO 1998; MITCHELL; TAYLOR, 1999; YANG, 2005; LINDEN, 2008). O término do algoritmo é estabelecido por um critério de parada. Após um número de gerações, a condição de parada deve ser atendida, a qual geralmente indica a existência, na população, de um indivíduo que represente, se não a melhor, uma solução aceitável para o problema (BÄCK; SCHWEFEL, 1993; MICHALEWICZ, 1996; PACHECO, 1999; VON ZUBEN, 2000; GROSKO; GORSKI; DIAS, 2006; LINDEN, 2008). Todo o diagrama de funcionamento básico de um AG canônico, conforme descrito anteriormente, é demonstrado na figura 6. Figura 6 - Esquema final de um algoritmo genético simples Fonte: Adaptado de Linden (2008) 32 3.4 Conceitos dos Esquemas A teoria dos esquemas (schema) foi formulada por Holland (1975) como uma forma de explicar, por meio de um modelo matemático, como e por que os AGs funcionam. O schema é demonstrado como um padrão genético capaz de ilustrar todo o processo de como um conjunto de cromossomos que apresentam similaridades em certas posições consegue, de forma simultânea, realizar uma varredura que explora todo o espaço de busca presente em determinado ambiente de soluções (GOLDBERG, 1989; PACHECO, 1999; WHITLEY, 1994 apud GROSKO; GORSKI; DIAS, 2006). O schema é uma string s= {s1 s2 ... sn}, de comprimento n, em que as posições pertencem ao conjunto Γ (alfabeto) utilizado na representação, mais o símbolo {*}, que significa “não-importa” (don't care ou wildcard ). Cada posição da string dada por sk ≠ * é chamada de especificação, enquanto que um wildcard demonstra o fato de que aquela posição pode assumir qualquer elemento dentro do conjunto Γ, e que o valor ali representado não terá relevância para a solução (MITCHELL, 1996; MICHALEWICZ, 1996; LINDEN, 2008). Em síntese, um esquema consiste em um gabarito (“template”) que representa um subconjunto dentre o conjunto de todos os indivíduos possíveis, descrevendo quais genomas são idênticos no espaço de busca. No caso binário, o Γ pode ser descrito como um modelo dado por {0, 1, *} que tem cardinalidade igual a 3, onde o símbolo {*} denota a possibilidade do gene poder assumir tanto o valor 0 como o 1 (HOLLAND, 1975; MITCHELL, 1996; MICHALEWICZ, 1996; PREBYS, 1999; LINDEN, 2008). Em AG, para representar o schemata (plural de schema) utiliza-se o símbolo de somatório “�”. Matematicamente emprega-se o H como um padrão que descreve todos os cromossomos do espaço de busca; K para representar o número de símbolos do alfabeto e L o comprimento do cromossomo (DIAS; BARRETO, 1998; PACHECO, 1999; GROSKO; GORSKI; DIAS, 2006; LINDEN, 2008). Assim, o esquema H �{0, 1, *}L é uma descrição de um modelo de similaridade ou um hiperplano L-dimensional do espaço de bits. (BÄCK; SCHWEFEL, 1993; MITCHELL, 1996). No Γ binário {0, 1, *}, sendo L = 2, o espaço de busca é igual a KL, então, se tem exatamente 22 = 4 soluções (pontos) possíveis. Considerando que para cada uma das L posições de um indivíduo define-se um schema diferente usando o símbolo *, para um espaço de busca representado por KL, existem, então, (K+1)L schemata, portanto, um total de (2+1)2 = 9 esquemas. Dessa forma, para o exemplo dado têm-se os seguintes schemata: 00, 01, 10, 11, 1*, 0*, *1, **, *0 (GOLDBERG, 1989; PACHECO, 1999; LINDEN, 2008). 33 Isto implica que, quando é usada a representação binária, um esquema que tenha comprimento L com m posições, incluindo o símbolo *, terá m graus de liberdade e representará até 2m indivíduos diferentes da atual população. Se o alfabeto K contiver n símbolos, e o esquema m posições com *, então o esquema será representado por (n-1)m indivíduos. Observe que a retirada de 1 elemento (n-1) provém do fato de que o * não entrará na composição dos cromossomos (GOLDBERG, 1989; PACHECO, 1999; LINDEN, 2008). O número de esquemas presente em um indivíduo é, então, dependente do comprimento da string e do número de opções contidas no Γ de codificações. Dessa forma, um indivíduo pertence a um schema se para todas as L posições o símbolo do indivíduo é igual ao símbolo do schema, exceto nas posições onde o símbolo do schema é “don’t care”, ou seja, um schema possui 2L-O(H) indivíduos que são quantificados por duas importantes propriedades (HOLLAND, 1975; GOLDBERG, 1989; BÄCK; SCHWEFEL, 1993; MITCHELL, 1996; PACHECO, 1999; PREBYS, 1999; LINDEN, 2008): � O(H) - denota a ordem de H, ou seja, a quantidade de posições (genes) que assumem valores 0’s e 1’s, ou seja, diferentes de * ; � �(H) - denota a definição de comprimento, ou seja, representa a distância entre a primeira e a última posição fixa em termos de números de corte existentes em �, ou o número de pontos de corte, diferente de *, dentro do esquema. Para que se possa transmitir um melhor entendimento de como e porque os AGs funcionam, a tabela 1 apresenta um exemplo matemático para três esquemas baseados na representação binária. A seguir é explicado todo o procedimento de cálculo do esquema H = 1*0*1, que, de acordo com Pacheco (1999), pode ser chamado de instância do esquema H, já que representa um modelo onde todos os cromossomos se iniciam e terminam com 1. Tabela 1 - Exemplo de alfabetos de esquemas e cálculos das strings de bits Esquemas (�) Indivíduos do Schema (Quantidade e Representação) Propriedade do Schema Graus de Liberdade Espaço de Soluções Schematapor Indivíduo (Quantidade e Representação) H 2L-O(H) Representação O(H) δδδδ(H) m KL (K+1)L Representação 1* 2 10, 11 1 0 1 4 9 00, 01, 10, 11, 1*, 0*, *1, *0, ** 1*0*1 4 10001, 10011, 11001, 11011 3 4 2 32 243 0000, 1000, 1100, 1110,...,**** **0 4 000, 010, 100, 110 1 0 2 8 27 000, 100, 110, 111, 010,...,*** Fonte: Adaptado de Pacheco (1999) e Linden (2008) De acordo com a tabela 1, o esquema H =1*0*1 terá 4=(25-3) possíveis representantes que podem ou não estarem presentes em determinada geração. A sua ordem é 3, já que existem três elementos diferentes de * na string H. O seu comprimento é 4, pois contém 4 34 pontos de corte entre a primeira posição fixa e a última. Possui 2 graus de liberdade, que é referente ao número de ocorrências de *. O espaço de busca KL para cada um dos 4 indivíduos que representam o schema é de 32=(25) pontos de possíveis de soluções, sendo capaz de gerar (2+1)5 = 243, dado que se têm três elementos (0,1,*) para 5 posições diferentes na string H. Conforme demonstrado, cada string na população é um exemplo de diferentes esquemas contidos uns nos outros, e se cada esquema gera certa quantidade de indivíduos, consequentemente, este número previsto será superior ao tamanho da população. Logo, se a população é suficientemente grande e inicialmente escolhida ao acaso, diversos esquemas podem ser manipulados em paralelo, o que permite ao AG explorar similaridades em codificações arbitrárias Assim, o processo de busca por melhores soluções gera outras possíveis soluções à medida que a evolução acontece (HOLLAND, 1975; LINDEN, 2008). Portanto, o paralelismo implícito nos AGs não está apenas no fato de que uma população contendo vários indivíduos é manipulada simultaneamente. Existe paralelismo também embutido no fato de que para cada elemento da população de um AG canônico processam-se e manipulam-se, simultaneamente, dezenas, ou mesmo centenas de esquemas com características negativas ou positivas, e que podem levar a uma boa ou má avaliação. O AG calcula explicitamente a avaliação de n indivíduos da população corrente, mas, implicitamente, calcula a avaliação de um número maior de esquemas que são instanciados por cada indivíduo da população (MITCHELL, 1996; LINDEN, 2008). Numa população de n indivíduos, onde cada indivíduo representa 2L schemata, há entre 2L e n.2L schemata, dependendo da diversidade da população. O número de schemata processados a cada geração é, então, proporcional a n3, enquanto avaliam n indivíduos. Nota- se que há mais informações nos schemata para guiar a busca do que simplesmente nos indivíduos. Isso quer dizer que o importante é o esquema e não o indivíduo, se este morrer o esquema que o torna bom tende a se proliferar e continuar na população (HOLLAND, 1975; PACHECO, 1999; LINDEN, 2008). A teoria dos esquemas corrobora que os AGs constituem uma classe de métodos de busca de propósito geral e que por meio de heurísticas poderosas têm como principal recurso a capacidade de identificar, explorar e acumular informações sobre um espaço de pesquisa inicialmente desconhecido, e que podem convergir rapidamente para soluções de alta qualidade em espaços complexos. Em síntese, a principal particularidade dos AGs esta na 35 busca para ajustar o equilíbrio ou tensão entre dois objetivos aparentemente conflitantes (HOLLAND, 1975; DE JONG, 1988; GOLDBERG, 1989; BÄCK; SCHWEFEL, 1993; MICHALEWICZ, 1996; MITCHELL; TAYLOR, 1999; LINDEN, 2008): � Exploration (exploração): exploração do espaço de busca no sentido de investigar novas áreas (adaptações) de regiões ainda desconhecidas; � Exploitation (aproveitamento): obter o máximo proveito do conhecimento adquirido e das melhores soluções em pontos mais promissores já visitados do espaço de busca (adaptações feitas até a atual geração). 3.5 Representação do Cromossomo A representação genotípica corresponde a uma descrição de cada indivíduo da população por meio de uma lista ordenada (cromossomo) de atributos descritos a partir de um alfabeto finito. Cada atributo desta cadeia representa um pedaço indivisível equivalente a um gene que por sua vez armazena informações de mensuração quantitativa nos alelos para representar uma das possíveis soluções do problema (PACHECO, 1999; VON ZUBEN, 2000; LINDEN, 2008). O tamanho da lista está diretamente associado ao número mínimo de atributos necessários para descrever cada indivíduo da população, geralmente têm tamanho único, embora existam abordagens que permitem o tratamento de cromossomos de tamanho variável (PACHECO, 1999; VON ZUBEN, 2000; LINDEN, 2008). A representação cromossomial é completamente arbitrária e consiste em traduzir a informação do problema em uma maneira viável de ser tratada pelo computador. Existem diversos tipos e formas de codificações que podem variar de acordo com a estrutura de dados imaginada pelo programador (OBITKO, 1998; PACHECO, 1999; ARGOUD, 2007; LINDEN, 2008). O quadro 2 apresenta as principais representações e os tipos de problemas onde melhor se aplicam. Quadro 2 - Principais representações e os tipos de problemas onde melhor se aplicam Representações Problemas Exemplos Binária Inteiros (100110011) Números Reais Numéricos (43.2 -33.1... 0.0 89.2) Permutação de Símbolos Baseados em Ordem (E4 E3 E7 E2 E6 E1 E5) Lista de Regras Grupamento (R1 R2 R3... R22 R23) Fonte: Adaptado de Pacheco (1999) e Linden (2008) 36 Apesar do AG ser uma heurística poderosa para lidar com problemas complexos, a representação cromossomial é uma das etapas mais críticas e fundamentais para sua definição e desempenho. Quanto mais adequada ao problema, maior a qualidade dos resultados obtidos, quando não, pode levar a problemas de convergência prematura ou exigir um esforço computacional intensivo, tornando-o ineficaz ou intratável. Portanto, se houver soluções proibidas ao problema estas não devem ter uma representação, se o problema impuser condições de algum tipo, estas devem estar implícitas dentro da representação (DE JONG, 1988; OBITKO, 1998; PACHECO, 1999; LINDEN, 2008). Dessa forma, embora arbitrária, a escolha do tipo de representação a ser usada deve ser realizada em função do problema que se quer resolver, do mecanismo de feedback e do que essencialmente se deseja manipular geneticamente. Em geral, as regras para a escolha da melhor forma de representação são: deve ser a mais simples possível e capaz de representar todo o espaço de busca do problema; deve utilizar um alfabeto mínimo que permita a expressão natural do que se deseja resolver e deve prestigiar a formação de schemata curtos e de baixa ordem (DE JONG, 1988; OBITKO, 1998; PACHECO, 1999; ARGOUD, 2007; LINDEN, 2008). 3.5.1 Representação Binária A representação binária, proposta por Holland (1975), é a mais utilizada pela maioria dos pesquisadores, e por ter sido mais frequentemente usada, apresenta um histórico de pesquisas que servem de modelos referenciais e que permitiram um avanço aos estudos e aplicação deste tipo de codificação. Embora apresente algumas desvantagens, quando aplicada a problemas com alta dimensionalidade de variáveis contínuas e alta precisão numérica, é a mais simples e a mais bem executável por um AG canônico. As principais vantagens deste tipo de representação resumem-se na facilidade de ser transformada em números inteiros ou números reais e de ser tratada pelos OGs; na capacidade de manipular esquemas de forma eficiente, oferecendo o número máximo de schemata e maximizando o paralelismo implícito; e, ainda por facilitar a prova de alguns teoremas (HOLLAND 1975; DE JONG, 1988; BÄCK; SCHWEFEL, 1993; PACHECO, 1999; MICHALEWICZ, 1996; LINDEN, 2008). Na codificação binária, um indivíduo x é representado por uma sequência de bits que pode assumir valores 0 ou 1, onde cada alelo é um bit. Esta sequência é representada por s = [bn....b2b1], 37 onde n é o número de bits necessários para representar x e cada bi � 0,1 (TANOMARU, 1995; MICHALEWICZ, 1996; PACHECO, 1999). A figura 7 demonstra a representação binária de um indivíduo composto por seis genes representados pelas variáveis x1, x2,...,x6, onde os primeiros bi (i=1 a 6) bits representam x1, os bi (i=7 a 12) bits seguintes representam x2 e assim por diante. Figura 7 - Representação binária de um indivíduo Fonte: Autor De acordo com a figura 7, cada um dos genes é mensurado por seis alelos ou bits que determinam um valor de solução entre os vários possíveis do espaço de busca deste problema. Segundo Linden (2008) é normal que a quantidade de alelos para os xn sejam iguais. Assim, bx1 = bx2 = ... = bxn, mas é possível que as necessidades de precisão, para cada número que estes representam, sejam diferentes, o que faz com que esta igualdade não seja obrigatória. A definição do tamanho do cromossomo sempre dependerá da precisão requerida para cada variável. Deste modo, para representar números reais como números binários é preciso se determinar dois parâmetros que em conjunto definem quantos bits por variável devem ser usados, são eles: a faixa de operação de cada uma das variáveis e a precisão desejada (TANOMARU, 1995; MICHALEWICZ, 1996; LINDEN, 2008). 3.6 Geração da População Inicial Um AG tem início a partir da execução do operador denominado inicialização. Tal operador consiste na criação de uma população inicial para o primeiro ciclo de solução do algoritmo. A população de cromossomos consiste de uma matriz com duas dimensões, podendo ser representada como Npop x Nbits, onde Npop é a quantidade de indivíduos de uma determinada população e Nbits é o tamanho de cada cromossomo (PACHECO, 1999; HAUPT, RANDY; HAUPT, SUE, 2004; ROSA; LUZ, 2009). A literatura apresenta várias formas de geração da população inicial, sendo que, a mais comum e simples é a geração randômica para cada indivíduo. Embora nenhum conhecimento de domínio seja necessário, existem também formas determinísticas, em que os cromossomos são gerados de acordo com uma função heurística (BÄCK; SCHWEFEL, 1993; HAUPT, RANDY; HAUPT, SUE, 2004; LINDEN, 2008; ROSA; LUZ, 2009). 38 Em geral, para uma evolução mais rápida, se busca semear os bons cromossomos, quando se conhece, a priori, o valor das boas “sementes” com certos níveis de desempenho. O ideal é que a população inicial contenha cromossomos representativos de todo o espaço de soluções para que se aumente a diversidade genética, garantindo assim, uma boa distribuição das soluções e maior alcance do espaço de busca. (DE JONG, 1988; LACERDA; CARVALHO; LUDERMIR, 1999; ARGOUD, 2007; LINDEN, 2008; ROSA; LUZ, 2009). O problema é que a capacidade de armazenamento demandada por um AG é exponencial e proporcional ao número de indivíduos presentes na população, ou seja, o total de avaliações em um experimento será igual ao tamanho da população vezes número de gerações a executar. A análise de desempenho do AG é, então, extremamente sensível ao tamanho da população, e isso faz com que o processo de dimensionamento do tamanho ideal incorra em duas situações complexas e conflitantes (DIAS; BARRETO, 1998; GROSKO; GORSKI; DIAS, 2006; ARGOUD, 2007; LINDEN, 2008). Isto ocorre porque, caso a população seja muito pequena não haverá espaço para que se tenha variedade genética, o que pode levar à convergência prematura e tornar o AG incapaz de encontrar boas soluções. Em contrapartida, quanto maior a quantidade de cromossomos maior a chance de encontrar melhores resultados, porém, se essa for grande demais, maior será o tempo de processamento, o que pode se aproximar de uma busca exaustiva. Logo, a demora em conseguir uma resposta pode fazer com que o AG deixe de ser um método interessante (DIAS; BARRETO, 1998; GROSKO; GORSKI; DIAS, 2006; ARGOUD, 2007; LINDEN, 2008). Evidentemente, há um limite superior para o tamanho da população onde se verifica a melhora no desempenho do AG. No entanto, a literatura disponível não especifica um número ideal, em geral, a maioria dos trabalhos publicados utiliza 100 indivíduos inicialmente, mas isto irá depender do tipo de problema, da experiência e heurística utilizada pelo usuário e da realização de testes (LACERDA; CARVALHO; LUDERMIR, 1999; ARGOUD, 2007; LINDEN, 2008; ROSA; LUZ, 2009). Para Tanomaru (1995) uma população entre 50-200 indivíduos é suficiente para resolver a maioria dos problemas. De acordo com Cole (1998) apud Argoud (2007) o tamanho ideal, especificamente em problemas de agrupamento, pode variar entre 10 e 1000. Já Linden (2008) sugere como tentativa inicial (extremamente imprecisa) uma quantidade de 40 cromossomos para qualquer tipo de problema. O mesmo autor apresenta ainda, como uma ideia para minimizar este tipo de problema, algumas estratégias de tamanho variável, cuja população aumente ou diminua com o tempo. 39 3.7 Função de Avaliação (Aptidão) A função de avaliação, de custos ou de adaptabilidade é a maneira utilizada pelos AGs para se determinar uma medida de qualidade ou habilidade de adaptação dos indivíduos gerados ao ambiente específico. A aptidão de um cromossomo é uma forma de diferenciar (métrica de qualidade) entre as boas e as soluções sub-ótimas, deixando claro qual delas está mais próxima, ou quão apto determinado cromossomo está da solução procurada (MITCHELL, 1996; PACHECO, 1999; CARVALHO, 2004; LINDEN, 2008; ROSA; LUZ, 2009). O cálculo da função de aptidão é o único elo não genérico entre o AG e o problema proposto e seu valor é posteriormente utilizado pelo operador de seleção como um parâmetro que irá dirigir o processo de busca para solucionar o problema em questão. Uma vez que o critério de seleção atua sobre a aptidão, em vez de valores da função objetivo, os valores de aptidão são utilizados como resultado do processo de avaliação (BÄCK; SCHWEFEL, 1993; PACHECO, 1999; GROSKO; GORSKI; DIAS, 2006; LINDEN, 2008; ROSA; LUZ, 2009). Nota-se que a formulação desta função é uma ação complexa que depende totalmente do problema a resolver. Logo, deve ser representada por meio de uma função capaz de identificar os objetivos específicos e embutir todas as restrições do problema (proporcional e gradual à sua gravidade) além de aplicar, quando necessário, punições aos cromossomos que as desrespeitarem (PACHECO, 1999; CARVALHO, 2004; GROSKO; GORSKI; DIAS, 2006; LINDEN, 2008; ROSA; LUZ, 2009). A função de aptidão atribui, então, uma nota ou um índice a cada indivíduo da população corrente no qual representa um valor numérico que reflete quão bem determinado indivíduo resolve o problema (GROSKO; GORSKI; DIAS, 2006; LINDEN, 2008; ROSA; LUZ, 2009). A tabela 2 apresenta um exemplo dado por Pacheco (1999) cuja função de avaliação dada por f(x) = x2 mede a aptidão de cada indivíduo. De acordo com essa função, a avaliação deve ser tal que, se o cromossomo C1 representa uma solução melhor do que o cromossomo C2, então a avaliação de C1 deve ser maior do que a avaliação de C2 (LINDEN, 2008). Tabela 2 - Aptidão de indivíduos. Cromossomo x f(x) C1 001001 9 81 C2 000100 4 16 Fonte: Pacheco (1999) 40 Conforme o exemplo dado na tabela 2, ao se aplicar a função de aptidão ao número inteiro correspondente ao cromossomo binário, o resultado demonstra que C1 é um indivíduo mais apto que C2, comprovando, assim, que a função de avaliação é para um AG o que o meio ambiente é para um ser vivo, ou seja, quando determinado indivíduo não se encontra apto para sobreviver ali, tende à extinção (LINDEN, 2008; ROSA; LUZ, 2009). Portanto, a avaliação simula o papel da pressão exercida pelo ambiente sobre o indivíduo, por meio do processo Darwiniano de seleção e sobrevivência dos mais aptos, sendo também usado para selecionar os cromossomos para reprodução. Ao manter uma porcentagem dos cromossomos mais aptos, estes terão maior chance de passar seu material genético para as próximas gerações para que se obtenham melhores descendentes (GOLDBERG, 1989; MITCHELL 1996; MICHALEWICZ, 1996; OBITKO, 1998; PACHECO, 1999; CARVALHO, 2004; GROSKO; GORSKI; DIAS, 2006; LINDEN, 2008). É, então, possível afirmar, que o valor exato fornecido por uma função de avaliação (fitness is evaluation) é a característica inerente à causa da convergência genética, visto que, pode fazer com que o desempenho do AG se degenere caso ocorra o “super-indivíduo” ou a “competição próxima” (MICHALEWICZ, 1996; LINDEN, 2008). O super-indivíduo se dá quando a avaliação de um cromossomo apresenta uma aptidão muito superior à média dos outros membros da população, que em casos extremos são próximos do ótimo global. A competição próxima ocorre quando os indivíduos apresentam valores de aptidão que diferem muito pouco, percentualmente, tornando a seleção praticamente aleatória, no qual bons esquemas podem deixar de ser selecionados (GOLDBERG, 1989; TANOMARU, 1995; LACERDA; CARVALHO; LUDERMIR, 1999; PACHECO, 1999; LINDEN, 2008). 3.8 Operadores Genéticos (OGs) Em AG, os OGs são os principais mecanismos de busca em regiões desconhecidas do espaço de soluções (LACERDA; CARVALHO; LUDERMIR, 1999). Os OGs consistem em um processo evolucionário que se consolida pelo uso de técnicas de randomização, baseadas na aptidão dos cromossomos, obtidas por meio de iterações computacionais que mimetizam fenômenos biológicos de seres vivos, no qual novos indivíduos são criados a partir da troca de material genético (HOLLAND, 1975; PACHECO, 1999; LINDEN, 2008). A função dos OGs é fazer com que a população inicial sofra sucessivas transformações a cada nova geração e se diversifique sem que ocorra a perda das características genéticas de adaptação adquiridas pelas gerações anteriores (ambos os genitores). A ideia é fazer com que 41 o AG melhore com o tempo, gerando indivíduos cada vez mais aptos, o que estende o espaço de busca e contribui para que as populações evoluam no decorrer das gerações até que se chegue a um resultado satisfatório (GOLDBERG, 1989; PACHECO, 1999; ROSA; LUZ, 2009). A ação dos OGs modifica as características dos cromossomos de forma a gerar uma nova descendência de diferentes indivíduos. Após vários ciclos de evolução a população deverá conter indivíduos mais aptos, que por sua vez incluirão mais descendentes, e terão uma maior chance de perpetuarem seus códigos genéticos nas próximas gerações (GOLDBERG, 1989; PACHECO, 1999). Existem diversos OGs com diferentes técnicas e específicos a cada caso, no qual suas aplicações estão intimamente relacionadas com as decisões da forma de representação que seja a mais adequada ao tipo de problema que se quer resolver (DE JONG, 1988). Os OGs classificam-se em (PACHECO, 1999; YANG, 2005; LINDEN, 2008): � Operadores de seleção (seleciona os indivíduos para o crossover e a mutação); � Operadores de recombinação (reprodução sexuada - crossover); � Operadores de mutação (mutação genética); � Operadores específicos ao domínio do problema (quaisquer outros que a imaginação dos programadores consiga produzir). É importante frisar que não há uma probabilidade que seja adequada para os operadores de crossover e mutação durante toda a execução do algoritmo. Outra característica relevante é que estes operadores são independentes e, portanto, suas percentagens não precisam somar 100%. Estudos mais avançados permitem a ação destes operadores com probabilidade variáveis, no qual é possível fazer dois sorteios com aplicações independentes e com porcentagens não relacionadas permitindo, assim, explorar de forma mais eficiente o espaço de soluções (PACHECO, 1999; LINDEN, 2008). Normalmente, no início do AG, se busca executar muita reprodução e pouca mutação e após um grande número de gerações os indivíduos tendem a apresentar, na sua maioria, características muito similares, podendo ocorrer a convergência genética. A partir daí, torna- se extremamente interessante que o operador de mutação seja escolhido mais frequentemente para dispersar a população, trazendo novo material genético para a formação de melhores indivíduos (PACHECO, 1999; LINDEN, 2008). 3.9 Operador de Seleção A seleção é executada logo após o cálculo de aptidão dos cromossomos gerados. É por meio deste operador que os indivíduos mais aptos da população são selecionados 42 (cromossomos pais) com base em suas avaliações para a reprodução, e que irão gerar descendentes (cromossomos filhos) por meio da aplicação dos operadores de cruzamento (crossover) e mutação (TANOMARU, 1995; MITCHELL, 1996; PACHECO, 1999; ARGOUD, 2007; ROSA; LUZ, 2009). Este operador simula o mecanismo de seleção natural, portanto, é baseado na competição e no favorecimento dos indivíduos com maiores valores de aptidão. A função deste operador é muito importante, se não houvesse o processo de seleção, além de o AG perder grande parte do caráter evolutivo, o mesmo seria um processo ineficiente e similar a uma busca aleatória (DE JONG, 1988; TANOMARU, 1995; YANG, 2005; ROSA; LUZ, 2009). A seleção pode ser qualquer função crescente na qual cada estrutura da população tenha uma aptidão associada a uma avaliação orientada (DE JONG, 1988; PREBYS, 1999). A seleção do AG canônico enfatiza uma regra de sobrevivência probabilística atrelada a um valor de aptidão para produzir mais ou menos descendentes. Portanto, conforme o principio Darwiniano de seleção, quanto melhor a avaliação do cromossomo, maior é a sua probabilidade de permanecer na nova geração e ser selecionado mais vezes para reprodução (BÄCK; SCHWEFEL, 1993; MITCHELL, 1996; LINDEN, 2008). Dessa forma, ao permitir aos pais mais aptos a possibilidade de gerar mais filhos, espera-se que as boas características predominem dentro das novas populações. É interessante notar que o fato do operador de seleção canônico utilizar-se de uma regra probabilística não impede que pais menos aptos também possam ser selecionados e gerar descendentes, porém em menor escala. Assim, é possível que nesse processo haja também certo nível de diversificação positiva, visto que, até os piores cromossomos podem conter certas características genéticas que em conjunto com outros gerem indivíduos ainda melhores (MITCHELL, 1996; PACHECO, 1999; YANG, 2005; LINDEN, 2008; ROSA; LUZ, 2009). O principal método de seleção utilizado em AG é a roleta, no entanto, para que se tenham ferramentas alternativas que se adéquem aos diversos problemas, existem vários outros métodos de seleção presentes na literatura. O fato é que ainda não há um consenso em relação a qual método é melhor, é uma questão em aberto, vai depender muito do tipo de problema que se quer resolver (MITCHELL, 1996; LINDEN, 2008). Porém, para qualquer mecanismo de seleção utilizado, o final do processo de escolha dos indivíduos é sempre o mesmo da roleta. As principais técnicas de seleção comumente usadas são: roleta acumulada e proporcional, ranking, torneios, truncamento, normalização 43 linear e normalização exponencial, amostragem estocástica uniforme e por seleção local (BLICKLE, 1996; PACHECO, 1999; ARGOUD, 2007; LINDEN, 2008). Um mecanismo de seleção é caracterizado pela pressão seletiva ou intensidade de seleção que o mesmo introduz no AG (PACHECO, 1999). A definição de intensidade de seleção empregada em genética é a variação na aptidão média da população induzida pelo método de seleção ou a razão entre o cromossomo de maior aptidão e a aptidão média da população (BLICKLE, 1996; LACERDA; CARVALHO; LUDERMIR, 1999). Se a pressão seletiva é muito baixa a aptidão é praticamente igual para toda a população e o AG apresenta um comportamento aleatório devido à competição próxima. Se a pressão seletiva é alta os super-indivíduos terão vários descendentes nas próximas gerações, enquanto que os cromossomos com baixo valor de avaliação poderão ser extintos. Consequentemente, o AG tenderá a convergir rapidamente e provavelmente para um máximo local (TANOMARU, 1995; LACERDA; CARVALHO; LUDERMIR, 1999). 3.9.1 Seleção por Roleta (Roulette Wheel) O método de seleção dos indivíduos pela Roleta (Roulette Wheel) foi inicialmente utilizado no AG clássico apresentado por Holland (1975). Este método é baseado no valor relativo de aptidão de cada indivíduo em relação à soma da avaliação de todos os cromossomos da população. Assim, a seleção dos indivíduos ocorre de forma proporcional ao seu valor de aptidão (MITCHELL, 1996; MICHALEWICZ, 1996; PACHECO, 1999; ROSA; LUZ, 2009). É um método simples e fácil de se entender, por isso é muito adotado. Neste método, cria-se uma roleta dividida em n faixas, onde n é o número de cromossomos representados. Cada faixa é rotulada de 1 a n, e o comprimento da circunferência do arco é proporcional ao espaço representado pelo valor de aptidão que cada cromossomo ocupa na roleta, que somadas as frações totalizam 100% (TANOMARU, 1995; ARGOUD, 2007; LINDEN, 2008; ROSA; LUZ, 2009). O quadro 3 descreve a lógica do algoritmo de implementação da roleta. Quadro 3 - Lógica do algoritmo de implementação da roleta (a) Some todas as avaliações para uma variável soma (b) Ordene todos os indivíduos em ordem crescente de avaliação (opcional) (c) Selecione um número s entre 0 e soma (Não incluídos) (d) i=1 (e) aux=avaliação do indivíduo 1 (f) enquanto aux