GERAÇÃO AUTOMÁTICA DE ALOCAÇÃO DE TAREFAS (GAAT) UTILIZANDO ALGORITMOS GENÉTICOS Alessandro Moretti, Wellyngton Amorim, Douglas Peixoto de Carvalho Acadêmicos do Curso de Matemática pela Universidade Anhanguera Uniderp. Rua Ceará, 333 – Bairro Miguel Couto CEP. 79.003-010 – Campo Grande – MS [email protected]; [email protected] Celso Correia de Souza1, José Francisco dos Reis Neto2 Professor do Curso de Matemática da Universidade Anhanguera Uniderp. 2 Professor do Curso de Administração da Universidade Anhanguera Uniderp. [email protected], [email protected] 1 RESUMO: Introdução à grade horária diz respeito ao estudo dos principais fundamentos dos algoritmos genéticos, bem como seus objetivos e os recursos utilizados para alcançá-los. Este estudo esclarece as principais dúvidas a respeito da capacidade tecnológica, através de uma análise simplificada de sua estrutura, dando ênfase a questões de curto prazo, relacionadas com o nível de atividade, de emprego. Chegando a conclusão de que sozinhas os estudos não são suficientes para alcançar os objetivos desejados. Elas necessitam da intervenção do aluno e da dedicação do mesmo no sentido de regular a atividade e levar o seu simples conhecimento a um nível elevado. Palavras-chave: Geração e grade horária, aptidão e seleção, cuzamento e mutação, algoritmos genéticos. Tema: Matemática Aplicada INTRODUÇÃO O problema da elaboração de horário de aulas numa instituição de ensino, ou mesmo da elaboração de uma escala de serviços em uma empresa que depende de turnos de funcionários pode-se tornar um problema crônico para a instituição, obrigando a mesma a manter um quadro de pessoas capacitadas e treinadas para esse fim. A complexidade para a geração de horário de aulas ou das escalas de trabalho aumenta ou diminui, conforme a variação da demanda de serviços durante o dia e/ou durante a semana aumenta ou diminui. A montagem do horário é feita, na maioria dos casos, de forma manual e empírica, demandando um considerável tempo na sua elaboração. No planejamento de horários de aulas ou escalas de serviços, não basta inserir o funcionário ou o professor, respectivamente, numa escala de serviços ou de aulas, é necessário respeitar as restrições impostas pela legislação do trabalho, pelas regras da empresa e acordos sindicais, e também, algumas recomendações ergonômicas, além das restrições do próprio funcionário ou professor, quando o mesmo compartilha seu trabalho em outras empresas e afazeres domésticos imprescindíveis. 2 Na medida do possível, a escala de trabalho deve satisfazer algumas restrições, representadas pelas necessidades de todos os envolvidos, ou seja, funcionários e instituições. As restrições podem ser divididas em dois grupos: as com alta importância, que quando não satisfeitas geram horários inúteis; e as com baixa importância, cujas violações devem ser minimizadas, mas, caso ocorram, não invalidam a grade horária. Esse problema já foi abordado e resolvido por alguns pesquisadores, classificando-se como um problema de otimização, e que possui várias aplicações práticas. Tal problema já foi resolvido utilizando-se conceitos de programação linear, resultando em modelos lineares de grande porte, de difíceis soluções. Mais recentemente esse problema passou a ser tratado como um problema de otimização combinatório, utilizando conceitos de Algoritmos Genéticos para a sua solução. Com isso houve uma redução considerável no tamanho do problema. Neste trabalho de pesquisa utilizou-se o conceito de Algoritmos Genéticos hibridizado com outras ferramentas computacionais para a confecção de uma grade horária em uma instituição de ensino, que consistiu em organizar as aulas em um intervalo de tempo, geralmente uma semana, de modo que elas satisfaçam as restrições pré-definidas. REFERENCIAL TEÓRICO Os Algoritmos Genéticos, segundo vários estudos, “são uma classe particular de algoritmos evolutivos que usam técnicas inspiradas pela biologia evolutiva como hereditariedade, mutação, seleção natural e recombinação (ou crosover)”. São implementados como uma simulação de computador em que indivíduos pertencentes um conjunto de soluções compatíveis são selecionados, e evoluem através de gerações, sofrendo cruzamentos e mutações, na busca de soluções melhores. A evolução geralmente se inicia a partir de um conjunto de soluções criado aleatoriamente e avaliado, alguns dos melhores indivíduos são selecionados para a próxima geração (elitismo), os outros sofrem recombinações e mutações para formar uma nova população. A nova população então é utilizada como entrada para a próxima iteração do algoritmo. Os Algoritmos Genéticos, que são em geral algoritmos simples e fáceis de serem implementados, diferem dos algoritmos tradicionais de otimização em basicamente quatro aspectos: baseiam-se em uma codificação do conjunto das soluções possíveis, e não nos parâmetros da otimização em si; os resultados são apresentados como uma população de soluções e não como uma solução única; não necessitam que as funções envolvidas sejam deriváveis, apenas realizam avaliações dos resultados e; usam transições probabilísticas e não regras determinísticas. 3 Algoritmos Genéticos: conceituação Os Algoritmos Genéticos são algoritmos de busca, criados por John Holland em 1975, baseado nos processos observados na evolução natural das espécies. O conceito básico consiste em que, de forma similar à teoria biológica dos sistemas naturais, os “melhores” indivíduos sobrevivem e geram descendentes com suas características hereditárias, no qual esses novos elementos tendem a ter a mesma aparência, ou fenótipo, que seus antecessores (RODRIGUES, 2006). Conforme Rodrigues (2009, p. 3), “o que o AG faz é buscar aquela solução que seja muito boa ou a melhor do problema analisado, através da criação de população de indivíduos cada vez mais aptos, levando à otimização da função objetiva”. A implementação dos Algoritmos Genéticos parte de uma população indivíduos gerados aleatoriamente (configurações iniciais de um problema), realiza-se a avaliação de cada um (em relação à função objetiva), seleciona os mais aptos e promove os manipuladores ou operadores genéticos como cruzamento e mutação, originando novas gerações de indivíduos. Cada indivíduo na população representa uma possível solução para um dado problema (SOUZA, 2010). Na FIGURA 1 pode-se resumir os Algoritmos Genéticos através do fluxograma. Fonte: Adaptado de Rodrigues (2009, p. 3) Figura 1 – Fluxograma da solução de problemas de otimização com Algoritmos Genéticos Os Algoritmos Genéticos permitem uma simplificação na formulação e solução de problemas de otimização, pois imcorporam uma solução possivel para o problema utilizado numa estrutura semelhante à estrutura de um cromossomo, aplicam operadores de seleção e cruzamento a essas estruturas de forma a preservar informações importantes para a solução de problema (LINDEN, 2008). 4 Função de avaliação Segundo Linden (2008), a função de avaliação, também chamada de função de custo, calcula então o valor numérico que reflete quão bons os parâmetros representados no cromossomo resolvem o problema. Em virtude dos parâmetros do problema serem conflitantes, a função de aptidão é construída para encontrar o ponto ótimo, em problemas de otimização ela pode representar a função objetiva do problema. A função de avaliação deve, portanto, ser escolhida com grande cuidado. Ela deve embutir todo o conhecimento que se possui sobre o problema a ser resolvido, tanto suas restrições quanto seus de qualidade (LINDEN, 2008). Escolha da população inicial A inicialização da população é feita da forma mais simples possível, fazendo-se uma escolha aleatória independente para cada individuo da população inicial ou por processo heurístico, isto é, simplesmente escolher n indivíduos dentro do espaço de busca. Essa técnica permite gerar uma boa distribuição, cobrindo um espaço maior no espaço de busca, sem interessar se são boas soluções ou não, assim como na natureza para haver evolução é necessário diversidade (LINDEN, 2008; VIANA, 1998 e SOUZA, 2010). Aptdão Para a definição da função de aptidão, em geral, utiliza-se uma formulação que aplica penalidades às restrições que são infringidas. As restrições podem ser severas (obrigatórias) e, neste caso, não podem ser infringidas, ou leves (desejáveis), caso em que determinam a qualidade da Grade Horária. A classificação das restrições será determinada pelos responsáveis em elaborar a Grade Horária, geralmente, coordenadores de cursos, sendo este um ponto crítico para a obtenção de uma solução adequada. Seleção A seleção dos indivíduos da população deve simular o mecanismo de seleção natural, “sobrevivência dos mais fortes”, em que os pais mais aptos geram mais filhos. O algoritmo permite, também, que alguns indivíduos menos aptos gerem filhos, garantindo a diversidade entre os indivíduos melhores e os piores. Se apenas os melhores indivíduos se reproduzirem a população tenderá a ser cada vez mais semelhante, não ocorrendo à evolução (LINDEN, 2008 e VIANA, 1998). A seleção via roleta viciada emprega o principio da probabilidade de sobrevivência do mais apto, ou seja, que possui a melhor função objetiva associada. Com base nos valores de f i ( xi ) , onde 5 xi é o indivíduo i avaliado de n indivíduos amostrados. Os indivíduos mais aptos são selecionados e duplicados em substituição aos menos aptos. Nessa etapa é quantificada a probabilidade pi de iésimo indivíduo da população vir a ser selecionado é proporcional à sua probabilidade de seleção. Eletismo O elitismo visa preservar os melhores cromossomos de uma geração para outra sem alterações, garantindo sempre melhor solução encontrada em qualquer uma das gerações será mantida até o final do processo. Geralmente usa-se nos Algoritmos Genéticos uma taxa de elitismo de 30% do total de indivíduos gerados (LINDEN, 2008 e VIANA, 1998). A principal vantagem deste método é que a convergência é garantida, isto é, se o máximo global for descoberto, o Algoritmo Genético converge para esse máximo, entretanto, da mesma forma existe o risco da estagnação em um máximo local. Crossover O cruzamento ou crossover é em processo de recombinação de partes das seqüências de caracteres entre pares de cromossomos, com o objetivo de gerar nova descendência. Esta troca de material genético garante a recombinação da população, possibilitando, assim, uma probabilidade maior de produzir indivíduos mais evoluídos que seus pais. O operador crossover escolhe aleatoriamente dois pais e troca parte de seu padrão genético. A escolha do ponto de corte do cromossomo é feita aleatoriamente; após esses passos são gerados dois filhos em substituição aos pais. No cruzamento é usual atribuir um percentual PX (indivíduos para cruzamentos), na faixa de 25% a 75% da população, recomenda-se preservar os primeiros e últimos gens do cromossomo (LINDEN, 2008; VIANA, 1998; RODRIGUES, 2009 e SOUZA, 2010). Mutação Este operador é responsável pela introdução e manutenção da diversidade genética na população. O operador de mutação inverte os valores de bits, ou seja, muda o valor de dado bit de 1 para 0 ou de 0 para 1, com o objetivo de tentar regenerar algum individuo que possa ter sido eliminado de forma inesperada. Para que uma determinada população não sofra muitas alterações, esta operação é processada para um pequeno percentual PM de seus elementos, em torno de 1% de todos os genes. . MATERIAL E MÉTODOS A pesquisa é do tipo exploratória que, de acordo com Gil (1999, p. 43), “as pesquisas exploratórias têm como principal finalidade desenvolver, esclarecer e modificar conceitos e idéias, 6 tendo em vista formulação de problemas mais precisos ou hipóteses pesquisáveis para estudos posteriores”. Sobre o programa desenvolvido para atuar na geração da grade horária É um gerador de grade de horários que torna fácil e conveniente a inserção de todas as disciplinas, turmas, sala de aula, professores. Além de permitir a criação de divisões de turmas em grupos, horários quinzenais, a reunião de turmas em uma aula ou ter mais de um professor para uma aula. Inicialmente, é preciso estabelecer o conjunto de regras para satisfazer todas as restrições. O conjunto de restrições varia com as características da instituição e dos envolvidos no processo de desenvolvimento, geralmente os coordenadores. A solução ótima, para este caso, tem como característica cumprir, da melhor forma possível, com todas as regras definidas nesses dois grupos. Em poucos minutos, o programa gerará o horário completo de acordo com as suas especificações. O software verifica a entrada de dados e o ajuda a remover os erros. Ele também verifica se o horário gerado atende a todas as condições impostas. Ao realizar mudanças manualmente, o programa o informa se houver algum erro. O software faz o que todo coordenador faz, ou seja, monta na grade os professores, as disciplinas, as turmas e as salas de aulas em seus períodos. É claro que usando técnicas avançadas, e diversos algoritmos. Ao completar milhões de grades, o programa seleciona somente aquela que não possuía conflitos e respeitou todas as condições impostas. Apesar do programa adaptar-se à inúmeras situações, grande parte de seus cadastros é opcional, ou seja, o usuário só informa os dados que considerar importantes. Desde que as restrições impostas no cadastro não impeçam a obtenção do resultado, um horário com cerca de 20 turmas e 40 professores pode ser elaborado em menos de 5 minutos. Testes comparativos mostraram que ele elimina mais janelas que um especialista na montagem de horários escolares. Isso se deve à capacidade do programa, de gerar milhares de combinações diferentes, na busca do melhor resultado. Mesmo assim, a eliminação de “janelas” é apenas um entre dezenas de itens levados em consideração durante o processo. Programação Genética Por ser um algoritmo extremamente simples e eficiente, existem diversas variações em cima do algoritmo genético básico para se obter resultados melhores ou mesmo tratar novas classes de problemas. Uma dessas variações é a programação genética. Na programação genética os indivíduos representam pequenos programas de computador que serão avaliados de acordo com o resultado de sua execução. Estes programas podem ser expressões simples, como fórmulas aritméticas ou 7 programas complexos, com operações de laço e condicionais, típicas de uma linguagem de programação comum. Bibliotecas e Frameworks para Algoritmos Genéticos Existem rotinas prontas, bem como, bibliotecas e frameworks para Algoritmos Genéticos (LINDEN, 2008), a saber: framework open-source para Algoritmos Genéticos e programação genética – Python; biblioteca open-source para Algoritmos Genéticos e metaheurísticas - linguagem C; pacote open-source para Algoritmos Genéticos – Java; pacote open-source para Algoritmos Genéticos e programação genética – Java e; framework open-source para Algoritmos Genéticos - C++. Neste estudo, pretende-se estabelecer os principais fundamentos do algoritmo genético, bem como seus objetivos e os recursos utilizados para alcançá-los. Inicialmente relacionar-se á algumas linguagens de programação que serviram como suporte para o desenvolvimento do protótipo. Delphi 7.0 Geralmente a linguagem Object Pascal (delphi) é usada comercialmente para programas de controle (financeiro, estoque). Esse é um pequeno exemplo, pois projetos feitos em Delphi podem ser de pequeno porte (Sistema de uma padaria) como podem ser de grande porte (Sistema de um banco). Nessa pesquisa o delphi foi usado para ser a base e estrutura da Grade-Horária, e esse programa tem o suporte para receber, trabalhar e adaptar outros programas para melhorar o layout dar animações, trabalhar com a internet, simplificando para o administrador. Eclipse Um IDE – Integrated Development Environment (Ambiente de desenvolvimento integrado) consiste em um software que contém um conjunto de funcionalidades embutidas, cuja finalidade é prover um modo mais fácil e interativo de construir e manipular seus programas. Entre estas ferramentas geralmente figuram: um editor de texto com facilidades especialmente desenhadas para a linguagem; um compilador (e um interpretador, no caso de Java e outras linguagens interpretadas); um editor gráfico, com facilidades para criação e edição da interface gráfica do programa a ser desenvolvido; um debugger, uma ferramenta especialmente feita para se tirar os bugs do código. Ela possibilita um monitoramento mais elegante do funcionamento do seu programa, facilitando a detecção e remoção dos erros. Perceba que não estamos falando em erros de sintaxe, mas erros na própria lógica do programa, que fazem seu programa gerar resultados indesejados ou travar (apesar de ele compilar), e que geralmente são difíceis de encontrar simplesmente analisando o código. 8 Flash Ele é responsável pelas animações e efeitos do programa. Foi utilizado nessa pesquisa só para ter um diferencial dos outros programas e que possa atrair ou animar os administradores por causa de que fazer a Grade-Horaria é um trabalho muito cansativo estressante tanto quanto mental e como psicológico. Porem se o programa tiver animações ira facilitar o manuseio. Dreamweaver O Adobe Dreamweaver é um software voltado para criação e edição de web pages, ele está com versão nova, a CS4, que por sinal surpreende muito quem já conhecia as outras versões. E pode ser encontrado no pacote Creatice Suite Design Premium do Adobe. O bom dessa nova versão, é que ele trabalha com total compatibilidade com os outros programas desse pacote, ou seja, não é necessário mais criar um documento no Photoshop, gravá-lo e abrir no Dreamweaver, pois nesses programas, os formatos de arquivo se reconhecem em qualquer um desses programas. RESULTADOS E DISCUSSÃO O protótipo do software de Geração Automática de Alocação de Tarefas Utilizando Algoritmos Genéticos – GAAT-NEPES foi concebido para funcionar junto à coordenação de administradores de empresas e instituições de ensino cujas tarefas devem ser alocadas para a alimentação dos dados de entradas sobre as mesmas, bem como das possíveis restrições relativas aos funcionários que irão desempenhá-las. A aplicação do protótipo constou da elaboração da grade horária de uma instituição fictícia dos ensinos Fundamental e Médio, com a seguinte carga horária dos professores (Tabela 1). Tabela 1. Relação de docentes, as disciplinas que lecionam e respectivas cargas horárias Professores Disciplinas Antonio Pádua Português – 5ª. Série do Ensino Fundamental 5 Português – 6ª. Série do Ensino Fundamental 5 Português – 7ª. Série do Ensino Fundamental 5 Português – 8ª. Série do Ensino Fundamental 5 Português – 1ª. Série do Ensino Médio 4 Português – 2ª. Série do Ensino Médio 4 Português – 3ª. Série do Ensino Médio 4 Matemática – 5ª. Série do Ensino Fundamental 5 Marco Antonio Margarida CH 9 Matemática – 6ª. Série do Ensino Fundamental 5 Matemática – 7ª. Série do Ensino Fundamental 5 Matemática – 8ª. Série do Ensino Fundamental 5 Matemática – 1ª. Série do Ensino Médio 4 Matemática – 2ª. Série do Ensino Médio 4 Matgemática– 3ª. Série do Ensino Médio 4 Inglês – 5ª. Série do Ensino Fundamental 2 Inglês – 6ª. Série do Ensino Fundamental 2 Inglês – 7ª. Série do Ensino Fundamental 2 Inglês – 8ª. Série do Ensino Fundamental 2 Inglês– 1ª. Série do Ensino Médio 2 Inglês – 2ª. Série do Ensino Médio 2 Inglês – 3ª. Série do Ensino Médio 2 Geografia – 5ª. Série do Ensino Fundamental 3 Geografia – 6ª. Série do Ensino Fundamental 3 Geografia – 7ª. Série do Ensino Fundamental 3 Geografia – 8ª. Série do Ensino Fundamental 3 Geografia– 1ª. Série do Ensino Médio 2 Geografia – 2ª. Série do Ensino Médio 2 Geografia – 3ª. Série do Ensino Médio 2 Historia – 5ª. Série do Ensino Fundamental 3 História – 6ª. Série do Ensino Fundamental 3 História – 7ª. Série do Ensino Fundamental 3 História – 8ª. Série do Ensino Fundamental 3 Ciências – 5ª. Série do Ensino Fundamental 3 Ciências – 6ª. Série do Ensino Fundamental 3 Ciências – 7ª. Série do Ensino Fundamental 3 Ciências – 8ª. Série do Ensino Fundamental 3 Produção de Texto – 1ª. Série do Ensino Médio 1 P.Texto – 2ª. Série do Ensino Médio 1 Produção de Texto – 3ª. Série do Ensino Médio 1 Milanez Educação Física – 5ª. Série do Ensino Fundamental 2 (aula inicial ou Educação Física – 6ª. Série do Ensino Fundamental 2 final) Educação Física – 7ª. Série do Ensino Fundamental 2 Edson Carvalho Honório Aristides Maria Aparecida Edilene 10 Sérgio Maria Rita Hermano Germano Edgar Educação Física – 8ª. Série do Ensino Fundamental 2 Educação Física – 1ª. Série do Ensino Médio 1 Educação Física – 2ª. Série do Ensino Médio 1 Educação Física – 3ª. Série do Ensino Médio 1 Artes– 5ª. Série do Ensino Fundamental 2 Artes – 6ª. Série do Ensino Fundamental 2 Artes – 7ª. Série do Ensino Fundamental 2 Artes – 8ª. Série do Ensino Fundamental 2 Espanhol – 1ª. Série do Ensino Médio 2 Espanhol – 2ª. Série do Ensino Médio 2 Espanhol – 3ª. Série do Ensino Médio 2 Biologia– 1ª. Série do Ensino Médio 3 Biologia – 2ª. Série do Ensino Médio 3 Biologia – 3ª. Série do Ensino Médio 3 História– 1ª. Série do Ensino Médio 2 História – 2ª. Série do Ensino Médio 2 História – 3ª. Série do Ensino Médio 2 Filosofia– 1ª. Série do Ensino Médio 1 Filosofia – 2ª. Série do Ensino Médio 1 Filosofia – 3ª. Série do Ensino Médio 1 Sociologia – 1ª. Série do Ensino Médio 1 Sociologia – 2ª. Série do Ensino Médio 1 Sociologia – 3ª. Série do Ensino Médio 1 Física– 1ª. Série do Ensino Médio 3 Física – 2ª. Série do Ensino Médio 3 Física – 3ª. Série do Ensino Médio 3 Quimica– 1ª. Série do Ensino Médio 3 Quimica – 2ª. Série do Ensino Médio 3 Quimica– 3ª. Série do Ensino Médio 3 Algumas restrições apresentadas pela Instituição de Ensino: 1 – Um mesmo professor não pode estar em duas salas de aulas num mesmo horário; 2 – Evitar aulas geminadas; 11 3 – Aulas de Educação Física devem estar no início ou no final dos expedientes. Inseridos todos os dados oriundos da Tabela 1 no pacote computacional GAAT-NEPES, bem como as três restrições elencadas acima, foi gerado a grade horária da escola, estando representado na Figura 2 a grade horária semanal da 1ª. Série do Ensino Médio, com cinco horas aulas diárias. Figura 2 – Grade horária da 1ª. Série do Ensino Médio elaborado pelo protótipo GAAT-NEPES CONCLUSÃO Os resultados podem ser considerados bons, visto que o objetivo do trabalho, da elaboração de uma grade horária em uma instituição de ensino, foi alcançado. Os Algoritmos Genéticos se mostrou ser uma ferramenta eficiente na alocação de tarefas ou construção de grades horárias, além de não necessitar nenhuma propriedade especial sobre a função objetiva. O custo computacional na elaboração de grades é baixo, apesar de não ter sido possível a comparação com outros algoritmos clássicos. Os Algoritmos Genéticos possuem a vantagem da simplicidade na programação do software, pois utiliza conceitos da genética em sua programação, resultando algoritmos que trabalham com a geração de uma população, realizar melhorias sobre a mesma no espaço de busca, visando a otimização da função, não necessitando uma nova programação a cada vez que se for criada uma nova situação. Os benefícios proporcionados pela ferramenta na elaboração de grades horárias, ou mesmo alocação de tarefas, utilizando algoritmos genéticos são os seguintes: a elaboração de uma grade horária de um curso, ou a alocação de tarefas, que demorava dias para ser feito, com o software é 12 realizado em minutos, ou até segundos; esse tempo ganho pelo administrador poderá ser usado para melhor negociar o horário com o corpo docente; algumas simulações podem ser realizadas sobre o horário, como a de minimizar as janelas dos professores; aplicar as exigências psicoterapêuticas e pedagógicas, no sentido de melhorar o relacionamento entre professores, alunos e escola; controlar o deslocamento do professor entre prédios; exportar o horário para XML ou EXCEL, e assim usar os dados em outros aplicativos; imprimir muitos relatórios e grades. REFERÊNCIAS BIBLIOGRÁFICAS ALCALÁ, R, BENITEZ, J. M.,CASILLAS, J., CORDÓN, O., PÉREZ, R., Fuzzy Control of HVAC Systems Optimized by Genetic Algorithms. Applied Intelligence, v.18 n.2, p.155-177, March-April 2003 ALENCAR, C. E. R. de; CORRÊA, R. F., Ferramenta de suporte para a decisão de frentes de corte de cana-de-açúcar usando algoritmos genéticos. Trabalho de Conclusão de Curso. Recife: Escola Politécnica de Pernambuco, 2006. BREGALDA, P. F.; OLIVEIRA, A. F. de E BORNSTEIN, C. T., Introdução à Programação Linear. Rio de Janeiro: Editora Campus Ltda., 1988. CAIXETA FILHO, J. V., GOLDBARG, M. C. e PACCA, H. L. L., Otimização Combinatória e Programação Linear: Modelos e Algoritmos. Rio de Janeiro: Editora Campus, 2000. CARTWRIGHT, H. M. The Genetic Algorithm in Science. Physical and Theoretical Chemistry Laboratory. Oxford University, UK, 1996. Disponível em (http://www.citesser.ist.psu.edu/79259.html). Acessado em 28 de abril de 2010. GUERVÓS, J. J. M. Informática Evolutiva: Algoritmos Genéticos. Disponível em http://geneura.urg.es/~jmerelo/ie/ags.htm. Acessado em 22/11/2009. HILLIER, F. S. E LIEBERMAN, G. Introdução à Pesquisa Operacional. Rio de Janeiro: Editora Campus Ltda./Editora USP, 1988. KARR, C. L., Genetic algorithms for modelling, design, and process control. Proceedings of the second international conference on Information and knowledge management, p.233-238. November 01-05, 1993. Washington, D.C., United States. LANGDON, W. e POLI, R., Foundations of Genetic Programming. Springer Verlag Pub, 2002. LINDEN, R., Algoritmos Genéticos. Rio de Janeiro: Brasport, 2008. MACULAN N. F. e PERREIRA, M. V. F., Programação Linear. Rio de Janeiro: Editora Atlas, 1980. MIRANDA, M. N. de., Algoritmos Genéticos: Fundamentos e Aplicações. Disponível em http://www.gta.ufrj.br/~marcio/genetic.html. Acessado em 28 de abril de 2009. MITCHELL, M., An Introduction to Genetic Algorithms. The Mit Press, 1998. 13 MIYAZAWA, F. K. Otimização Combinatória. Disponível em http://www.ic.unicamp.br/~fkm/problems/combopt.html. Acessado em 28 de abril de 2010. PACHECO, M. A. C. Algoritmos Genéticos: Princípios e Aplicações. Disponível em http://www.ica.ele.puc-rio.br/Downloads/38/CE-Apostila-Comp-Evol.pdf. Acessado em 28 de abril de 2010. SANTA CATARINA, A. e BACH, S. L. Estudo do efeito dos parâmetros genéticos na solução otimizada e no tempo de convergência em algoritmos genéticos com codificações binária e real. Acta Scientiarum: Technology. Maringá, v. 25, n.2, p. 147- 152, 2003. VIANA, G. V. R. Meta-heuristicas e programação paralela em otimização combinatória. Fortaleza: EUFC, 1998.