Dissertação - IME
Transcrição
Dissertação - IME
INSTITUTO MILITAR DE ENGENHARIA TEN QEM DANIEL WANDER FERREIRA MELO EMPREGO DE ALGORITMOS GENÉTICOS NA GENERALIZAÇÃO DE MODELOS DIGITAIS DE SUPERFÍCIE Dissertação de Mestrado apresentada ao Curso de Mestrado em Engenharia Cartográfica do Instituto Militar de Engenharia, como requisito parcial para a obtenção do título de Mestre em Engenharia Cartográfica. Orientador: Luiz Felipe Coutinho Ferreira da Silva - D.E. Rio de Janeiro 2008 C2008 INSTITUTO MILITAR DE ENGENHARIA Praça General Tibúrcio, 80 – Praia Vermelha Rio de Janeiro - RJ CEP: 22290-270 Este exemplar é de propriedade do Instituto Militar de Engenharia, que poderá incluí-lo em base de dados, armazenar em computador, microfilmar ou adotar qualquer forma de arquivamento. É permitida a menção, reprodução parcial ou integral e a transmissão entre bibliotecas deste trabalho, sem modificação de seu texto, em qualquer meio que esteja ou venha a ser fixado, para pesquisa acadêmica, comentários e citações, desde que sem finalidade comercial e que seja feita a referência bibliográfica completa. Os conceitos expressos neste trabalho são de responsabilidade do autor e do orientador. 519.62 M 528 Melo, Daniel Wander Ferreira Emprego de Algoritmos Genéticos na Generalização de Modelos Digitais de Superfície / Daniel Wander Ferreira Melo - Rio de Janeiro: Instituto Militar de Engenharia, 2008. 131 p. : il., graf., tab. Dissertação (mestrado) - Instituto Militar de Engenharia – Rio de Janeiro, 2008. 1. algoritmos genéticos 2. modelagem de superfície. I. Título. II. Instituto Militar de Engenharia. CDD 519.62 2 INSTITUTO MILITAR DE ENGENHARIA Ten DANIEL WANDER FERREIRA MELO EMPREGO DE ALGORITMOS GENÉTICOS NA GENERALIZAÇÃO DE MODELOS DIGITAIS DE SUPERFÍCIE Dissertação de Mestrado apresentada ao Curso de Mestrado em Engenharia Cartográfica do Instituto Militar de Engenharia, como requisito parcial para obtenção do título de Mestre em Ciências em Engenharia Cartográfica. Orientador: Prof. Luiz Felipe Coutinho Ferreira da Silva – D.E. Aprovada em 16 de dezembro de 2008 pela seguinte banca examinadora: ______________________________________________________________________ Prof. Luiz Felipe Coutinho Ferreira da Silva – D.E. do IME – Presidente ______________________________________________________________________ Prof. Paulo Márcio Leal de Menezes – D.C. da UFRJ ______________________________________________________________________ Prof. Marcello Goulart Teixeira – D.C. do IME ______________________________________________________________________ Prof. Leonardo Castro de Oliveira – D.E. do IME Rio de Janeiro 2008 3 A Deus que tornou tudo possível e, para as maiores bênçãos a mim concedidas: companheira Fabiana, de todos amada os momentos, e Maria Clara, filha querida e razão de tantos esforços. 4 AGRADECIMENTOS Agradeço à minha esposa Fabiana pelo apoio e compreensão nas horas de ausência, pelos muitos finais de semana e feriados dedicados à pesquisa. A meus pais e familiares pela força e incentivo. Ao Prof. , orientador e amigo, Luiz Felipe Coutinho por ter embarcado nessa jornada. Suas idéias, sugestões, conselhos e, sobretudo, sua confiança - abrindo espaço e liberdade na medida certa ao seu orientando - foram cruciais para o andamento da pesquisa e para meu aprendizado, científico e humano. Ao Cap Morett, eterno companheiro de turma e de jornadas, por sua amizade sincera e apoio. Ao meu irmão e companheiro Michael Anderson pela ajuda especial. Aos demais colegas da turma de mestrado de 2007: Aline Cristina, Emily Watanabe, Renata Marenga, Marco Vieira e Patrick Calvano. Aos companheiros Ricardo Vieira e Cap Marcos, pela amizade, conselhos e ensinamentos. Ao professor Leonardo, Cap Marcos e Cap Felipe Costa pelas preciosas contribuições. Ao Cap Basto e Ten Santos, por nossas conversas inspiradoras. Ao Cap Roberto Gomes, pelas conversas pertinentes e elucidativas na pesquisa. Ao Cap Ivanildo, Maj Wilson, Cap Ermírio e demais professores da Seção de Cartografia do IME, pelas dicas muito importantes. Aos demais integrantes da Seção de Cartografia do IME. Ao Exército Brasileiro, à Diretoria de Serviço Geográfico e ao IME pela oportunidade ímpar de aperfeiçoamento. Com todos vocês foi muito mais fácil. Obrigado a todos. 5 “Não custa nada pensar grande. E pensar grande significa pensar além do próprio tempo, no tempo dos outros. Não com arrogância, mas com humildade. Vale a pena pensar grande! Não temos que plantar árvores para que colhamos os frutos, temos que plantá-las para nossos descendentes do próximo milênio. O simples ato de plantar vale a pena, quando se dá um sentido a ele.” Amyr Klink 6 SUMÁRIO LISTA DE ILUSTRAÇÕES ................................................................................................... 11 LISTA DE TABELAS ............................................................................................................ 13 1 INTRODUÇÃO ......................................................................................................... 16 1.1 A questão dos dados na Modelagem de Superfícies .................................................. 16 1.2 Problemas de Otimização........................................................................................... 19 1.3 Algoritmos Genéticos................................................................................................. 19 1.4 Generalização de Modelos Digitais de Superfície ..................................................... 20 1.5 Objetivo...................................................................................................................... 21 1.6 Estrutura do Trabalho................................................................................................. 21 2 MODELOS DIGITAIS DE SUPERFÍCIE ............................................................ 23 2.1 Amostragem ............................................................................................................... 24 2.2 Interpolação ................................................................................................................ 25 2.2.1 Estruturas de Dados.................................................................................................... 26 2.2.1.1 Grade Retangular Regular.......................................................................................... 26 2.2.1.2 Malha Triangular Irregular......................................................................................... 27 2.2.2 Interpoladores Locais ................................................................................................. 28 2.2.3 Interpoladores Globais ............................................................................................... 29 3 GENERALIZAÇÃO EM CARTOGRAFIA .......................................................... 30 3.1 O Esforço de Representação da Realidade................................................................. 30 3.2 Tipos de Generalização .............................................................................................. 32 3.3 Motivação para a Generalização ................................................................................ 33 3.4 Quantificação dos Erros em Generalização ............................................................... 34 3.5 Generalização de Modelos Digitais de Superfície ..................................................... 35 3.5.1 Modelos de Representação......................................................................................... 35 3.5.2 Objetivo da Generalização de Modelos Digitais........................................................ 38 3.5.3 Técnicas de Generalização ......................................................................................... 39 3.5.3.1 Uso de Funções Matemáticas ..................................................................................... 39 7 3.5.3.2 Similaridade de Seções............................................................................................... 40 3.5.3.3 Generalização por Algoritmos Genéticos .................................................................. 41 4 ALGORITMOS GENÉTICOS ............................................................................... 45 4.1 Algoritmos Genéticos na Computação Evolutiva ...................................................... 45 4.2 Principais Conceitos................................................................................................... 46 4.3 Evolução nos Sistemas Naturais ................................................................................ 46 4.4 Ciclo Básico dos Algoritmos Genéticos..................................................................... 50 4.5 Representações dos Cromossomos............................................................................. 51 4.5.1 Representação Binária................................................................................................ 51 4.5.2 Representação Real .................................................................................................... 51 4.6 Parâmetros dos Algoritmos Genéticos ....................................................................... 52 4.6.1 População Inicial ........................................................................................................ 52 4.6.2 Função Objetivo ......................................................................................................... 53 4.6.3 Aptidão ....................................................................................................................... 53 4.6.3.1 Ordenamento .............................................................................................................. 54 4.6.3.2 Escalonamento ........................................................................................................... 55 4.6.4 Operadores de Seleção ............................................................................................... 55 4.6.4.1 Roda da Roleta ........................................................................................................... 56 4.6.4.2 Seleção por Torneio ................................................................................................... 57 4.6.5 Operadores Genéticos ................................................................................................ 57 4.6.5.1 Operador Cruzamento ................................................................................................ 57 4.6.5.2 Operador Mutação...................................................................................................... 61 4.6.6 Substituição dos Cromossomos.................................................................................. 63 4.6.6.1 Geracional .................................................................................................................. 63 4.6.6.2 Steady State ................................................................................................................ 63 4.6.7 Critérios de Convergência.......................................................................................... 64 4.7 configuração dos Algoritmos Genéticos .................................................................... 65 4.8 Características Gerais dos Algoritmos Genéticos ...................................................... 65 5 ALGORITMO DE GENERALIZAÇÃO............................................................... 67 5.1 Codificação do Problema ........................................................................................... 67 5.1.1 Estrutura dos Cromossomos....................................................................................... 67 8 5.1.2 Formação da População Inicial .................................................................................. 69 5.1.3 Função Objetivo ......................................................................................................... 70 5.1.4 Função Aptidão .......................................................................................................... 74 5.1.6 Técnica de Seleção ..................................................................................................... 76 5.1.7 Técnicas de Substituição ............................................................................................ 76 5.1.7.2 Steady state................................................................................................................. 77 5.1.8 Critério de Parada....................................................................................................... 78 5.2 Parâmetros do Algoritmo Genético............................................................................ 79 5.2.1 Tamanho da População .............................................................................................. 80 5.2.2 Função Objetivo ......................................................................................................... 80 5.2.3 Tipo de Cruzamento ................................................................................................... 80 5.2.4 Técnica de Substituição de Indivíduos....................................................................... 80 5.2.5 Taxa de Cruzamento................................................................................................... 81 5.2.6 Taxa de Mutação ........................................................................................................ 81 5.2.7 Percentual de Convergência ....................................................................................... 82 5.3 Parâmetros de Geração do Modelo ............................................................................ 82 5.3.1 Interpoladores............................................................................................................. 82 5.3.2 Resolução do Modelo................................................................................................. 82 5.4 Seleção dos Parâmetros.............................................................................................. 83 6 DESCRIÇÃO DOS EXPERIMENTOS ................................................................. 86 6.1 Características das Amostras...................................................................................... 86 6.2 Estrutura dos Testes ................................................................................................... 88 6.3 Influência da Precisão Numérica................................................................................ 89 6.4 Testes de Configuração dos Parâmetros..................................................................... 90 6.4.1 Análise dos Critérios de Aptidão ............................................................................... 91 6.4.2 Análise dos Tipos de Cruzamento.............................................................................. 94 6.4.3 Análise das Técnicas de Substituição da População .................................................. 98 6.4.4 Análise dos Interpoladores ....................................................................................... 101 6.4.5 Considerações Finais dos Testes de Configuração dos Parâmetros ........................ 104 6.5 Testes do Percentual de Generalização .................................................................... 105 6.5.1 Teste do Percentual de Convergência ...................................................................... 106 6.5.2 Testes com a População Inicial ................................................................................ 109 9 6.5.2.1 Testes da População com Percentual Fixo .............................................................. 111 6.6 Testes de Generalização Sucessiva ......................................................................... 112 6.6.1 Generalização Sucessiva com Aptidão Baseada na Diferença de Volume ............. 113 6.6.2 Aptidão Baseada em Valores de Volume, de Área Plana e de Área Superficial ... 116 6.6.2.1 Variação Percentual do Volume............................................................................. 118 6.6.2.2 Variação Percentual da Área Plana ........................................................................ 119 6.6.2.3 Variação Percentual da Área Superficial ............................................................... 121 6.6.3 Conclusão dos Testes de Generalização Sucessiva................................................ 122 7 CONCLUSÕES .................................................................................................... 125 7.1 Conclusões ............................................................................................................. 125 7.2 Sugestões para Trabalhos Futuros.......................................................................... 129 8 REFERÊNCIAS BIBLIOGRÁFICAS ............................................................... 130 10 LISTA DE ILUSTRAÇÕES FIG. 2.1 Amostragem regular (a), semi-regular (b) e irregular (c). ......................................... 25 FIG. 2.2 Grade regular de um modelo digital de elevação. ..................................................... 26 FIG. 2.3 Malha Triangular Irregular. ....................................................................................... 27 FIG. 3.1 Representação de uma realidade em um mapa. ......................................................... 30 FIG. 3.2 Modelo digital de terreno original. ............................................................................ 37 FIG. 3.3 Modelo digital de terreno generalizado. .................................................................... 37 FIG. 3.4 Seções verticais paralelas de um modelo digital (Adaptado de FIRKOWSKI 2002, p. 61)............................................................................................................................................. 41 FIG. 3.5 Método empírico para generalização. ........................................................................ 42 FIG. 3.6 Etapas de um algoritmo genético para generalização. ............................................... 43 FIG. 4.1 Ramos da computação evolutiva. .............................................................................. 45 FIG. 4.2 Cruzamento de 1 Ponto.............................................................................................. 58 FIG. 4.3 Cruzamento de 3 pontos. ........................................................................................... 59 FIG. 4.4 Cruzamento uniforme (adaptado de LACERDA & CARVALHO, 1999). ............... 59 FIG. 5.1 Correlação de pontos na cadeia cromossômica. ........................................................ 68 FIG. 5.2 Uso de pontos de controle.......................................................................................... 71 FIG. 5.3 Diferença de volume entre modelos, sob três perspectivas diferentes. ..................... 72 FIG. 5.4 Comparação de perfis de modelos: original (verde) e generalizado (azul). .............. 73 FIG. 5.5 Combinações possíveis de parâmetros. ..................................................................... 84 FIG. 6.1 Amostra de pontos 1. ................................................................................................. 86 FIG. 6.2 Amostra de pontos 2. ................................................................................................. 87 FIG. 6.3 Amostra de pontos 3. ................................................................................................. 87 FIG. 6.4 Influência da precisão da aptidão por pontos de controle.......................................... 89 FIG. 6.5 Influência da precisão da aptidão por diferença de volume....................................... 90 FIG. 6.6 Comparação dos critérios de aptidão para a amostra 1.............................................. 91 FIG. 6.7 Comparação dos critérios de aptidão para a amostra 2.............................................. 92 FIG. 6.8 Seleção de pontos: amostra original (à esquerda) e amostra generalizada (à direita). .................................................................................................................................................. 93 FIG. 6.9 Comparação dos tipos de cruzamento na amostra 1. ................................................. 95 FIG. 6.10 Comparação dos tipos de cruzamento na amostra 2. ............................................... 96 FIG. 6.11 Aptidão média por geração para a substituição geracional...................................... 97 FIG. 6.12 Aptidão média por geração para a substituição geracional com elitismo................ 98 11 FIG. 6.13 Comparação das técnicas de substituição para malha regular interpolada por Krigagem para a amostra 1....................................................................................................... 98 FIG. 6.14 Comparação das técnicas de substituição para malha regular interpolada por Krigagem para a amostra 2....................................................................................................... 99 FIG. 6.15 Comparação das técnicas de substituição para TIN com a amostra 1. .................... 99 FIG. 6.16 Comparação das técnicas de substituição para TIN com a amostra 2. .................. 100 FIG. 6.17 Aptidão média para as técnicas de substituição com cruzamento de 1 ponto. ...... 100 FIG. 6.18 Resultados obtidos com TIN e Krigagem para a amostra 1. ................................. 101 FIG. 6.19 Resultados obtidos com TIN e Krigagem para a amostra 2. ................................. 102 FIG. 6.20 Interpolação de cotas negativas: modelo original (esquerda) e modelo com cota negativa (direita). ................................................................................................................... 102 FIG. 6.21 Comparação de modelos TIN: original (esquerda) e generalizado (direita).......... 103 FIG. 6.22 Comparação dos testes com diferentes percentuais de convergência para a amostra 1.............................................................................................................................................. 107 FIG. 6.23 Comparação dos testes com diferentes percentuais de convergência para a amostra 2.............................................................................................................................................. 107 FIG. 6.24 Aptidão média da solução para diferentes percentuais de convergência na amostra 2.............................................................................................................................................. 108 FIG. 6.25 Mínimos, máximos e amplitudes das populações iniciais da amostra 1................ 109 FIG. 6.26 Mínimos, máximos e amplitudes das populações iniciais da amostra 1................ 111 FIG. 6.27 Evolução da função aptidão em testes de generalização sucessiva. ...................... 114 FIG. 6.28 Evolução de modelos TIN: original (acima), segunda iteração (centro) e sexta iteração (abaixo)..................................................................................................................... 115 FIG. 6.29 Variação da área plana para as amostras 1 e 2 na generalização sucessiva........... 117 FIG. 6.30 Variação da área superficial para as amostras 1 e 2 na generalização sucessiva... 117 FIG. 6.31 Diferença de volume para as amostras 1 e 2......................................................... 119 FIG. 6.32 Variação da área plana no primeiro teste............................................................... 119 FIG. 6.33 Variação da área plana no segundo teste. .............................................................. 120 FIG. 6.34 Variação da área superficial no primeiro teste....................................................... 121 FIG. 6.35 Variação da área superficial no segundo teste. ...................................................... 121 12 LISTA DE TABELAS TAB. 2.1 Diferenças principais entre Grade Regular Retangular e Malha Triangular Irregular (adaptado de FELGUEIRAS, 2001)......................................................................................... 28 TAB. 4.1 Probabilidades de seleção pela Roda da Roleta. ...................................................... 56 TAB. 5.1 Parâmetros envolvidos na generalização de modelos. ............................................. 83 TAB. 5.2 Valores a priori do tamanho da população, taxas de cruzamento e mutação e de percentual de convergência. ..................................................................................................... 85 TAB. 6.1 Valores limite dos parâmetros para os testes de generalização sucessiva.............. 123 13 RESUMO A generalização de modelos digitais ganha espaço atualmente com a multiplicação do uso da modelagem digital e o incremento do número de fontes de dados, constituindo um dos objetivos da presente dissertação, sendo implementado um sistema de generalização de modelos digitais baseado em algoritmos genéticos. O objetivo dos testes realizados inicialmente foi o reconhecimento do comportamento do algoritmo para diferentes configurações de parâmetros e diferentes amostras de dados; em seguida os testes visaram o estudo dos fatores de maior influência no percentual de generalização do algoritmo e, por fim, foi analisada a qualidade dos modelos generalizados na tentativa de identificação de padrões de variação da aptidão. Os resultados iniciais permitiram o reconhecimento da substituição steady state, do cruzamento de 1 ponto e da aptidão calculada por volume como uma configuração de melhor rendimento, comprovando ainda a independência do rendimento das configurações com relação ao conjunto de pontos. Os testes subseqüentes demonstraram a capacidade de evolução das soluções e a forte dependência do algoritmo com relação à população inicial. Os testes finais demonstraram degradação acentuada na qualidade dos modelos e sua desvinculação com relação aos valores de aptidão, ressaltando a importância da função aptidão bem estruturada e a necessidade de avanço das pesquisas de generalização de modelos. 14 ABSTRACT The generalization of digital models currently gains space with the multiplication of the use of the digital modeling and the increment of the number of sources of data, constitutes one of the objectives of the present research, being implemented a genetic algorithm system for generalization of digital models. The objective of the tests carried through initially was the recognition of the behavior of the algorithm for different configurations of parameters and different samples of data; after that the tests had aimed at the study of the factors of bigger influence in the percentage of generalization of the algorithm and, finally, the quality of the models generalized in the attempt of identification of standards of variation of the fitness was analyzed. The initial results allowed to the recognition of the substitution steady state, the crossover of 1 point and the fitness calculated by volume as a configuration of better income, proving still the independence of the income of the configurations with regard to the set of points. The subsequent tests demonstrated the limited capacity of evolution of the solutions and the strong dependence of the algorithm with regard to the initial population. The final tests had demonstrated the degradation accented in the quality of the models and its independence with regard to the values of fitness, standing out the importance of the function aptitude structuralized and the necessity of advance of the research of generalization of models well. 15 1 INTRODUÇÃO 1.1 A QUESTÃO DOS DADOS NA MODELAGEM DE SUPERFÍCIES Por modelagem de superfície entende-se a reconstrução de formas a partir de um conjunto de amostras, contendo informações relacionadas a algum tema e com atributos espaciais. Essas formas da representação de um fenômeno ou superfície são modelos que recebem diferentes denominações técnicas, uma das mais comuns é a de Modelos Digitais de Superfície (MDS). Modelos Digitais de Superfície são modelos de dados estruturados, obedecendo a critérios matemáticos pré-definidos, para a representação de feições ou de fenômenos distribuídos no terreno. A apresentação formal do conceito de MDS e dos principais fatores relacionados à sua elaboração será feita com maior rigor no Capítulo 2. São ferramentas úteis para a reconstrução tridimensional do relevo com grande potencial para o desempenho de atividades que necessitem do conhecimento da altitude, tais como projeto de estradas. Podem servir ainda como modelos para a representação da distribuição espacial de outros fenômenos naturais e de dados socioeconômicos, por exemplo. Em função disso, esses modelos vêm sendo aplicados em atividades diversas como telecomunicações, engenharia civil, geologia e agronomia. A qualidade dos dados empregados é fator de grande influência na exatidão e representatividade em uma modelagem de terreno. A primeira relaciona-se ao grau de acerto das informações apresentadas no modelo com relação à realidade representada enquanto a última está ligada à presença das informações características e relevantes para a representação dos detalhes principais dessa mesma realidade. A título de ilustração, para a coleta de dados para a geração de modelos digitais de superfície no início do século XX, os principais meios de obtenção de coordenadas de pontos estavam relacionados, principalmente, a trabalhos de campo e de aerofotogrametria. Tais métodos são caracterizados por serem geralmente demorados e dispendiosos. Atualmente, com o surgimento de novas fontes para a coleta de dados, a geração de modelos digitais foi amplamente facilitada. O emprego de tecnologia do Sistema de Posicionamento Global (GPS, do inglês: Global Positioning System), que permite a obtenção de malhas de pontos diretamente por meio do rastreamento de satélites, em um tempo bem 16 inferior aos métodos topográficos tradicionais, o advento de sistemas de medição a Laser (LIDAR, do inglês: Light Detection and Ranging) e a evolução de sensores orbitais ópticos e de radares de abertura sintética (SAR, do inglês: Synthetic Aperture Radar), que permitem visadas laterais e recobrimento estereoscópico de cenas, são importantes exemplos dessa evolução. Essas mesmas tecnologias SAR e GPS, tão adotadas atualmente em modelagem de terrenos, são importantes para coletas de informações georreferenciadas para diferentes especialidades. Informações espaciais relativas a dados geológicos, geofísicos, estatísticos, ambientais, por exemplo, podem ser coletadas de forma mais rápida e em maior quantidade. A multiplicação de meios para a modelagem digital reduz o peso da aquisição de dados enquanto fator limitante para a geração de modelos e, em vista disso, contribui para a disseminação de seu uso em diferentes áreas de conhecimento. Contudo, como outra conseqüência, esses novos meios de coleta podem fornecer dados em quantidades excessivas para a modelagem de uma superfície ou fenômeno. Excesso de dados na modelagem digital pode resultar, dentre outros fatores, em redundância, maior tempo de processamento e em problemas de armazenamento dos modelos. Por redundantes entendem-se aqueles dados cuja inserção não afete a representatividade dos modelos ou que não interfira positivamente em sua qualidade. Dados redundantes de uma realidade, quando não participarem do conjunto de dados utilizado na elaboração de um modelo, podem ser utilizados como instrumento de controle servindo como importante meio para aferição de sua qualidade. Entretanto, modelos com redundância de dados exigem maiores recurso para armazenamento e processamento sem resultar necessariamente em uma melhor qualidade final. A questão da quantidade de dados está relacionada a cada problema de modelagem em particular. Com relação a uma mesma escala de representação, áreas continentais demandam certamente uma maior quantidade de dados para suas modelagens do que áreas menores de regiões metropolitanas, por exemplo, de tal forma que um número de dados suficiente para representar aquelas pode ser excessivo para a representação das últimas. De forma semelhante, modelos representando áreas continentais podem se tornar excessivamente pesados para processamento e exibição. A divisão de áreas continentais em áreas menores reduz o custo computacional envolvido na modelagem. Nesse caso, modelos de representação de áreas menores podem ser gerados 17 em substituição a um único modelo geral, de processamento mais demorado. Entretanto, essa estratégia não elimina a redundância de dados que por ventura possa existir no conjunto de dados original relacionado à área continental e que permanece mesmo com a divisão em modelos menores. Por isso, atualmente, a discussão em torno da redução da quantidade de dados para a modelagem digital de superfícies é tão necessária quanto a questão das fontes de dados a serem utilizadas. Em paralelo aos métodos de aquisição de dados para a modelagem digital é importante o estudo de mecanismos e ferramentas para a redução das amostras obtidas. Essa redução da quantidade de dados que compõem uma amostra constitui um tipo de generalização cartográfica e pode também ser chamada de generalização de modelos. A redução de dados de um modelo digital não pode, entretanto, ser realizada por métodos puramente aleatórios sem considerar os modelos resultantes gerados. O objetivo de redução da massa de dados gera a necessidade de seleção daquelas informações que melhor representam a superfície em questão, caso contrário a redução dos dados pode ser prejudicial e resultar em modelos degradados em relação à qualidade e aos objetivos da modelagem. Outros fatores, além da quantidade de pontos, podem exercer influência e, por isso, devem ser relevados na escolha de pontos, como por exemplo, a forma, a área da superfície e a freqüência de variação dos dados. Esses parâmetros admitem diferentes combinações e podem resultar em escolhas de malhas de pontos diferentes para a criação de um modelo, tornando o objetivo de generalização de modelos ainda menos trivial. Diferentes técnicas de redução de dados de modelos digitais já existem e levam em consideração diferentes critérios, como geometria de pontos, resposta de séries matemáticas e análise de conteúdo informativo, por exemplo. Ao longo deste trabalho serão abordados alguns estudos envolvidos nesse esforço. Problemas de redução de pontos, que envolvem a seleção de subconjuntos de pontos a partir de uma quantidade inicial, podem envolver um grande número de combinações, impossíveis de serem analisadas e exauridas. Situações desse tipo, com um domínio muito amplo de soluções, podem ser mais bem resolvidas com o auxílio de técnicas de otimização. 18 1.2 PROBLEMAS DE OTIMIZAÇÃO Para BÄCK et al. (1997), problemas de otimização podem ocorrer em projetos técnicos, científicos e econômicos abrangendo questões de maximização (de qualidade, eficiência ou de lucros, por exemplo) ou de minimização (de tempo, custo ou de risco, por exemplo). Dentre as estratégias adotadas para o tratamento de problemas de otimização destaca-se um ramo da computação chamada de evolutiva. Esse ramo abriga diferentes estratégias de manipulação dos parâmetros envolvidos em um fenômeno em estudo. Para os mesmos autores, a computação evolutiva pode ser considerada uma ferramenta bem adaptada para resolução de problemas de otimização, não dotada de uma estrutura prédefinida de algoritmos mas capaz de se adaptar a uma tarefa em questão por meio de mecanismos de evolução. Ressaltam ainda a sua promissora aplicação nos setores de finanças e de gestão. Citam como exemplos de situações práticas, nas quais a aplicação de computação evolutiva é comum, aplicações de design e de engenharia, envolvendo parâmetros contínuos ou discretos. Por fim, cabe aqui levantar que a tarefa de generalização de modelos, proposta da presente pesquisa, apresenta características típicas de um problema de otimização. O esforço de seleção de pontos envolve a escolha de um critério de avaliação e, dada uma massa inicial de pontos, permite um número incontável de combinações de pontos que atendem à solução do problema. Há um esforço de representar um fenômeno espacial com menos pontos, sem envolver necessariamente perdas significativas de informação, aumentando o peso ou carga informativa individual de cada unidade no contexto de todo o modelo. 1.3 ALGORITMOS GENÉTICOS Algoritmos genéticos são uma das principais estratégias de otimização presentes na computação evolutiva. São capazes de partir de um conjunto inicial de soluções para um problema e de realizar combinações e arranjos com o objetivo de determinar melhores soluções aplicáveis aos casos em estudo. O surgimento da técnica e do termo “algoritmo genético” datam de 1975, representando grande avanço no campo dos sistemas evolutivos nas técnicas de busca e de otimização existentes naquela época. Desde então, vêm sendo utilizados para o estudo e solução de diferentes problemas em diversas áreas de pesquisa. De sua concepção inicial até a atualidade, 19 em função de sua versatilidade e difusão do uso, houve um considerável avanço na quantidade e na qualidade de operadores de cruzamento e de mutação, estratégias de evolução e de outros parâmetros. Uma abordagem pormenorizada será conduzida no Capítulo 4. Apesar do avanço, as características principais da técnica de algoritmos genéticos, aplicáveis em problemas com muitos parâmetros e com um conjunto indefinido de soluções, ainda se mantêm e são responsáveis por sua difusão a áreas de conhecimento diversificadas. Tendo em vista essas características, é possível identificar a tarefa de generalização de modelos digitais de superfície como mais uma área afim para sua aplicação. 1.4 GENERALIZAÇÃO DE MODELOS DIGITAIS DE SUPERFÍCIE A principal idéia por trás da prática de generalização de modelos é o melhor aproveitamento dos dados, estabelecendo uma quantidade suficiente de informação para representar um fenômeno espacializado. É dita generalização justamente por envolver a retirada de elementos sem relevância para o modelo e seleção daqueles de maior peso. Dentro do esforço do melhor aproveitamento de um conjunto de dados, modelos generalizados devem ser tão próximos quanto possível, em termos de precisão ou conteúdo informativo, dos modelos originais formados pelo conjunto inicial dos dados. A generalização e, conseqüente eliminação de dados redundantes, permite o estudo do comportamento de amostras de dados sob diferentes circunstâncias. Por exemplo, a generalização está relacionada a fatores como a quantidade inicial de dados para um modelo, do fenômeno a ser representado, do modelo matemático adotado para descrever o comportamento do fenômeno. Cada combinação desses fatores poderá resultar em diferentes processos de generalização. Dessa forma, a realização de testes com generalização de modelos poderá permitir a compreensão de padrões de comportamento de dados para casos específicos. Para um dado fenômeno representado em uma região, podem ser feitos testes de generalização de amostras a fim de se estudar o comportamento das amostras de dados. Os resultados poderão estar dentro de um intervalo ou padrões de comportamento refletindo um espaçamento médio das amostras e sua quantidade. Esses padrões poderão ser adotados para futuras coletas de dados relacionados ao mesmo fenômeno representado na mesma região, permitindo a aquisição de informações na 20 quantidade e na distribuição adequada para a elaboração de modelos semelhantes aos modelos estudados. Os mesmos padrões poderão ser extrapolados para outras regiões que guardem certa semelhança com a região inicialmente estudada, orientando a amostragem de dados para a elaboração de modelos. 1.5 OBJETIVO Desenvolver um algoritmo genético voltado a generalização de modelos digitais de superfície. A partir de uma massa inicial de pontos, o algoritmo deve investigar outras conformações ou subconjuntos de pontos que sejam capazes de gerar modelos próximos ao modelo primitivo envolvendo um número menor de pontos. Como objetivos secundários destaca-se: 1. Identificação das configurações do algoritmo genético que garantam um maior rendimento para a tarefa de generalização. 2. Testes com mais de uma amostra de dados visando a identificação de uma possível influência do conjunto de dados no rendimento de uma configuração do algoritmo. 3. Estudo da qualidade dos modelos generalizados a partir dos valores de aptidão e perda de detalhes. 1.6 ESTRUTURA DO TRABALHO Na parte introdutória foram apresentados aspectos genéricos principais relacionados à tarefa de generalização de modelos e aos algoritmos genéticos, propostos e estudados como ferramenta na presente dissertação. No Capítulo 2 são levantados os principais conceitos relacionados à modelagem digital de terreno. No Capítulo 3 são apresentados os principais conceitos e questões relativas à generalização cartográfica e generalização de modelos digitais, para o posicionamento e condução da pesquisa desenvolvida. No Capítulo 4 são apresentados conceitos e descritos os aspectos principais da teoria de algoritmos genéticos, visando o entendimento dos operadores adotados nessa dissertação. 21 O Capítulo 5 é voltado para a descrição da codificação do problema de generalização e para considerações acerca dos critérios de aptidão levantados, dos operadores de seleção, de recombinação de soluções e de substituição de indivíduos. O Capítulo 6 abriga resumos dos resultados obtidos para os testes de generalização de modelos digitais. O Capítulo 7 contém as conclusões e sugestões para futuras pesquisas. O Capítulo 8 contém as referências bibliográficas utilizadas na pesquisa. 22 2 MODELOS DIGITAIS DE SUPERFÍCIE Modelo digital de superfície (MDS) é uma representação da distribuição de determinado fenômeno espacializado. Pode fornecer valores distribuídos no espaço de diversos fenômenos em estudo. Essas representações podem abranger dados sociais, econômicos e físicos, sendo utilizadas em diversas áreas de conhecimento. Existem diferentes denominações para os modelos digitais. Os termos Modelo Digital de Elevação (MDE) e Modelo Digital de Terreno (MDT) estão associados, na literatura científica, a modelos digitais cujo fenômeno espacialmente representado é a superfície topográfica, sendo muito úteis para a representação do relevo. Por fatores como o surgimento de novas tecnologias para a coleta de dados como GPS e SAR, por exemplo, a quantidade e o tipo de informações coletadas para a geração de modelos aumentaram significativamente, havendo uma verdadeira difusão da técnica de modelagem digital para a representação de fenômenos outros além da altitude. Dessa forma, alguns autores como BURROUGH (1989 apud ASSUNÇÃO, 2007) adotam o termo Modelo Digital de Superfície para designar as representações que abrangem outras feições no terreno, além da superfície topográfica. Na presente pesquisa, com o intuito de evitar uma restrição a modelos voltados para a representação da superfície topográfica, o termo Modelo Digital de Superfície será adotado para designar modelos voltados para a representação de superfícies de diversas fontes de dados, não restritas à altimetria. Maiores informações acerca da terminologia de modelos digitais podem ser encontradas em GOMES (2006) ou ARNAUT (2001). De acordo com FELGUEIRAS (2001) o processo de geração de modelos numéricos de terreno possui três etapas principais, sendo a primeira denominada amostragem, abrangendo a coleta de pontos para a geração do modelo, a segunda chamada de interpolação que corresponde à criação do modelo especificamente e a última relacionada às aplicações do modelo. As duas primeiras etapas são as mais relevantes no contexto da presente pesquisa e serão abordadas sumariamente a seguir. 23 2.1 AMOSTRAGEM Corresponde à fase inicial da criação de um modelo numérico e compreende a coleta dos dados que comporão o modelo. O correto planejamento dessa etapa é decisivo para as etapas seguintes de elaboração do MDS. Fatores como quantidade, precisão e distribuição dos dados coletados devem ser levados em consideração. Amostras com quantidade insuficiente de pontos ou a coleta de pontos de baixa precisão, por exemplo, podem comprometer significativamente o modelo digital resultante, não atendendo à expectativa inicial do planejamento. Por outro lado, uma coleta excessiva de pontos pode introduzir maiores distorções caso não haja uma boa distribuição dos dados. Além disso, amostras maiores ocasionam um aumento do tempo de processamento e manipulação, além da maior demanda de espaço de armazenamento. A amostragem deve refletir, da melhor forma possível, a morfologia de uma região ou deve ser feita em quantidade suficiente para representar a distribuição de um fenômeno. A quantidade de pontos coletados e sua distribuição requerem que seja considerada a variação do fenômeno a ser representado, acompanhando a quantidade de informação presente em uma área. Assim, regiões com muitas variações exigem uma quantidade de pontos maior que aquelas áreas com poucas variações. A escolha dos pontos deve ser feita levando em consideração outros fatores, como a exatidão esperada do modelo digital e a exatidão dos recursos disponíveis. Caso o modelo seja feito em uma escala cadastral, por exemplo, a coleta de pontos altimétricos deverá ser feita com um menor espaçamento além de demandar um levantamento por técnicas mais acuradas, como perfilamento a laser ou nivelamento geométrico. Cartas topográficas, pares estereoscópicos de fotografias aéreas ou de imagens orbitais, pontos GPS constituem alguns exemplos de fontes de dados para os MDS. Cada um desses meios apresenta restrições de precisão e de tempo de levantamento. Segundo FELGUEIRAS (2001), as amostragens podem ser classificadas quanto ao espaçamento dos pontos em: regular, com os pontos igualmente espaçados nas direções dos eixos cartesianos x e y; semi-regular, mantendo o espaçamento uniforme somente ao longo de uma direção, e irregular na qual a uniformidade dos espaçamentos não é mantida, conforme ilustrado na FIG. 2.1. 24 (a) (b) (c) FIG. 2.1: Amostragem regular (a), semi-regular (b) e irregular (c). 2.2 INTERPOLAÇÃO Consiste na fase de obtenção de novos valores do atributo representado no modelo a partir do conjunto inicial de dados. Trata-se de uma densificação dos pontos que compõem o modelo resultante. Existe uma grande quantidade de interpoladores que podem ser aplicados na geração de grades regulares. Cabe ao usuário a escolha do interpolador mais adequado a seu conjunto de dados e que melhor atenda às características planejadas para o modelo resultante. Segundo FELGUEIRAS (2001), esse processo de interpolação pode ser global, quando utiliza todos os pontos amostrados para determinar um ponto na grade, ou local, quando utiliza somente os pontos vizinhos ao ponto a ser determinado. Apesar da etapa de interpolação estar diretamente relacionada à geração da grade regular, é importante destacar que modelos organizados por malhas triangulares irregulares também necessitam da escolha de um interpolador para a determinação de pontos não situados nos vértices dos triângulos. De acordo com NEVES (1988 apud SIMÕES, 1993), existem dois aspectos de interesse na geração de uma malha triangular irregular. O primeiro está relacionado ao critério adotado para a elaboração da triangulação utilizada na criação do modelo e o segundo relaciona-se à escolha do interpolador, relacionado à forma de apresentação do modelo resultante. A seguir serão apresentados sumariamente os principais aspectos de interesse relacionados aos interpoladores. Antes, porém, serão feitas algumas considerações acerca das estruturas de dados presentes na modelagem digital. As estruturas de dados relacionam-se, 25 principalmente, à disposição final dos pontos do modelo, se regular ou irregular, e sua determinação constitui um fator de grande importância para a escolha de um interpolador. 2.2.1 ESTRUTURAS DE DADOS Os modelos de grade retangular regular e modelos de malha triangular irregular (TIN, do inglês: Triangular Irregular Network) são as estruturas mais comumente utilizadas em modelagem digital. 2.2.1.1 GRADE RETANGULAR REGULAR Essa estrutura de dados representa o terreno por meio de pontos igualmente espaçados compondo o aspecto de uma grade formada por retângulos (FIG. 2.2). FIG. 2.2: Grade regular de um modelo digital de elevação. Cada ponto dessa grade é gerado pela intercessão das linhas das arestas dos retângulos sendo chamado de nó aquele que possui a sua localização definida pelas coordenadas (x, y, z), conforme SIMÕES (1993). O espaçamento entre os pontos define a resolução do modelo de grade e pode ser igual ou inferior à menor distância presente nas amostras coletadas. Os pontos da grade são obtidos 26 por interpolação a partir dos pontos coletados na etapa de amostragem, exceto para os casos onde os pontos amostrados coincidem com a posição de algum ponto na grade regular. 2.2.1.2 MALHA TRIANGULAR IRREGULAR A malha triangular é formada por um conjunto de pontos interconectados organizando triângulos que não se interceptam. Cada triângulo formado pode variar em tamanho e conforme os ângulos internos. Para a estrutura de dados triangular, os pontos coletados na etapa de amostragem são utilizados diretamente como vértices dos triângulos que comporão a superfície poliédrica de representação do terreno, conforme ilustração na FIG. 2.3 . FIG. 2.3: Malha Triangular Irregular. A estrutura triangular está definida com o conjunto de triplas de vértices dos triângulos que compõem uma representação irregular. Segundo FIRKOWSKI (2002), neste método de representação não ocorre ambigüidade de valor para pontos situados nas arestas dos triângulos em vista do caráter contínuo da representação e da concordância entre triângulos adjacentes. Existem diferentes formas ou critérios para a ligação dos pontos amostrais que formarão os triângulos, resultando em diferentes superfícies. O método de triangulação mais conhecido e consagrado pelo uso em modelagem digital de terreno é a Triangulação de Delaunay. Esse método baseia-se no critério de maximização dos ângulos internos dos triângulos, aproximando-os à forma de triângulos eqüiláteros. 27 Segundo FELGUEIRAS (2001), a estrutura triangular é a estrutura mais propícia para a inserção de linhas de restrição. Essas linhas retratam importantes aspectos do terreno como fundos de vale (linhas de drenagem) ou pontos culminantes de relevo (linhas divisoras de águas) e são úteis para orientar o processo de formação dos triângulos para a geração de um modelo mais representativo da superfície real. Após a formação da malha triangular é importante que o modelo forneça informações sobre outros pontos situados na superfície representada e que não pertençam ao conjunto de pontos amostrados. Isso é feito por meio do uso de interpoladores. A TAB. 2.1 apresenta algumas diferenças presentes entre os modelos de grade regular e malha triangular irregular, apontadas por FELGUEIRAS (2001). TAB. 2.1: Diferenças principais entre Grade Regular Retangular e Malha Triangular Irregular (adaptado de FELGUEIRAS, 2001). GRADE REGULAR RETANGULAR MALHA TRIANGULAR IRREGULAR Apresenta regularidade na distribuição espacial dos vértices. Os vértices são estimados a partir das amostras. Apresenta problemas para representar variação local acentuada de superfícies. Relações topológicas entre os retângulos são explicitas. Não apresenta regularidade na distribuição espacial dos vértices. Os vértices dos triângulos pertencem ao conjunto amostral. Representa melhor superfícies não homogêneas com variações acentuadas. É necessário identificar e armazenar as relações topológicas entre os triângulos 2.2.2 INTERPOLADORES LOCAIS São aqueles voltados para a determinação de pontos a partir de um conjunto vizinho e limitado de pontos. Um operador matemático comumente envolvido nessa operação é a média aritmética, por isso, existe um grupo de operadores que são classificados como operadores de média móvel, havendo variação somente quanto ao critério para inclusão dos pontos vizinhos no cálculo. FELGUEIRAS (2001) ressalta os seguintes interpoladores por média móvel: 1 - Vizinho mais próximo 2 - Média Simples 3 - Média Ponderada 4 - Média Ponderada por Quadrante 28 5 - Média Ponderada por Quadrante e por Cota 2.2.3 INTERPOLADORES GLOBAIS Interpoladores globais são aqueles que consideram todo o conjunto de amostras para se determinar a cota de um dado ponto. Séries de Fourier e polinômios são exemplos de interpoladores locais. São também conhecidos como superfícies de tendência, que são superfícies aproximadas por um ajuste polinomial aos dados através de uma regressão entre os valores dos atributos e os valores das posições geográficas, conforme FELGUEIRAS (2001). Em outras palavras, por meio de um processo de regressão obtém-se a equação de um polinômio que descreve os valores dos pontos de acordo com as suas posições. Entretanto, apesar de um interpolador global poder ajustar-se ao conjunto inicial de pontos, pode haver uma degradação da precisão do modelo final, em comparação aos interpoladores locais. Dependendo da variação do atributo representado, um interpolador global, pode não representar com precisão as variações sofridas pelo fenômeno em todas as áreas representadas. As maiores perdas de informação encontram-se principalmente nas regiões com grandes variações do fenômeno representado. 29 3 GENERALIZAÇÃO EM CARTOGRAFIA 3.1 O ESFORÇO DE REPRESENTAÇÃO DA REALIDADE A representação de uma realidade complexa, composta pela presença de inúmeras feições simultâneas, mostra-se como uma tarefa não tão simples e geralmente envolve um trabalho intenso de seleção de informações e escolha das respectivas formas de representação. Isso ocorre porque as representações criadas apresentam limitações de várias ordens, que impedem a inserção de todos os elementos presentes no meio a ser representado exatamente da forma como acontecem. A representação do espaço e de seus fenômenos traz como principal necessidade a formulação / escolha de uma linguagem capaz de traduzir os principais aspectos de interesse. Dentro desse objetivo, representações cartográficas surgem como importantes meios para a representação espacial de forma simbólica. Para MÜLLER et al. (1995), mapas são os meios mais eficientes de comunicação visual para a transmissão de informação geográfica para o leitor. A tarefa de descrição de uma realidade complexa por meio da linguagem cartográfica é feita de forma resumida e com perda de detalhes do mundo físico. Durante a elaboração de um mapa, há uma atividade de identificar, abstrair as informações de interesse e de sintetizá-las em uma representação simbólica, conforme ilustrado na FIG. 3.1. FIG. 3.1: Representação de uma realidade em um mapa. Essa escolha das informações relevantes para representação em detrimento de outros aspectos é inerente à atividade de mapear em vista da impossibilidade de inserção da totalidade de elementos gráficos e alfanuméricos que podem descrever uma realidade em foco. Segundo ISSMAEL (2003), cada documento cartográfico é um modelo da realidade, 30 construído a partir da redução da quantidade de elementos, simplificação de relações e criação de representações. O processo de seleção e de simplificação de informações para a criação de modelos é chamado generalização. De forma geral, tem como principal objetivo aumentar o poder informativo das representações geradas, representando as informações de interesse de forma eficiente. Sobre isso, ROBINSON (1995) afirma que, no contexto de mapeamento, generalização pode ser sintetizada como um processo de redução de detalhes de forma a ressaltar somente os principais aspectos de interesse das feições originais. Em função dessa característica marcante da generalização, MOREHOUSE (1995) comenta que generalização de mapas é um termo geralmente aplicado na compilação de mapas a partir de outros de escalas maiores ou de outras fontes de dados. A tarefa de generalização, contudo, é muito ampla, possuindo outras características e propriedades que vão além da simples redução de informações para a geração de modelos. Sua conceituação e abrangência não são de fácil definição além de não apresentarem unanimidade no meio acadêmico. Segundo MÜLLER et al. (1995), generalização pode ser vista como um processo interpretativo que resulta em uma visão de um fenômeno em um nível mais alto, significando uma menor escala. Sob esse ponto de vista, a pura coleta de dados e de informações para a elaboração de representações já consiste em uma forma de generalização. Ao se definir os dados de interesse para uma representação e que devam ser coletadas, faz-se um trabalho prévio de generalização ao simplificar a quantidade e tipo de informações representadas. Por estar envolvida no esforço de representação de uma realidade diversificada, não há atualmente um conjunto geral de regras que possa ser aplicado para diferentes circunstâncias. A generalização abrange um conjunto diferenciado de operadores que podem ser bem aplicados, sob determinada ordem, para a representação de determinadas regiões e com feições específicas, mas que ao mesmo tempo podem não ser os mais recomendáveis para outra região. Por fim, resume-se que a generalização está estreitamente ligada ao esforço de representação, sendo feita por mecanismos diversos dependentes de fatores principalmente subjetivos. D’ALGE & GOODCHILD (1996) lembram que a prática de generalização é predominantemente intuitiva e pouco formal. 31 3.2 TIPOS DE GENERALIZAÇÃO Conforme MÜLLER et al. (1995), é possível distinguir a atividade de generalização em dois tipos, sendo um primeiro tipo de generalização orientada a modelos e o segundo como generalização cartográfica. A generalização orientada a modelos está relacionada à manipulação de dados. Envolve a criação de métodos para representação e manipulação dos dados dando suporte a atividades como inserção a atualização de dados, por exemplo. Fornece meios para a manipulação de dados acerca dos objetos representados e de seus relacionamentos. A generalização cartográfica está relacionada principalmente a aspectos gráficos e geométricos, contando com ferramentas elaboradas a partir de técnicas desenvolvidas na atividade de generalização de mapas analógicos. De acordo com RUAS & LAGRANGE (1995), existe uma tendência comum em associar a atividade de generalização exclusivamente a simplificações na geometria de feições, reduzindo a quantidade de objetos representados conforme um fator de escala. Essa generalização gráfica é mais perceptível para o usuário final de um mapa. Entretanto, é importante ressaltar que para que essa generalização seja possível, é necessária uma outra generalização, a de modelos, voltada para atividades como a definição dos dados a serem inseridos na base, seus atributos e relacionamentos principais. Enfim, o trabalho de generalização pressupõe outros detalhes além da questão geométrica das feições representadas. Segundo JONES (1997 apud GABOARDI & FIRKOWSKI, 2006) a generalização é um processo de abstração dependente da escala de representação que incorpora as tarefas de classificação estatística, simbolização, manipulação de escala e redução de dados digitais armazenados. Modelos Digitais de Superfície, por partirem das amostras discretas de dados, em contraposição a uma realidade contínua, também constituem representações com uma carga de generalização. O termo modelo sugere perda de alguns detalhes e significa que essas representações não correspondem exatamente à realidade. A generalização de modelos digitais de superfície refere-se à redução da quantidade de informações da realidade para a geração de modelos. Sua finalidade principal é garantir um melhor aproveitamento e redução da redundância de dados dentro do esforço de representação de uma realidade. 32 A generalização de modelos, também chamada por alguns autores de generalização estatística, segundo WEIBEL (1995), “tem como um de seus principais objetivos a redução de dados nos domínios espacial, temático e/ou temporal”, sendo um dos mais conhecidos a redução do volume de dados de maneira a garantir economia de espaço e velocidade de processamento. O mesmo autor aponta a importância de se realizar estudos sobre generalização com dados discretos e contínuos, como os modelos digitais de terreno e levanta alguns pré-requisitos importantes para os métodos de generalização de modelos: • A previsibilidade e possibilidade de repetir resultados; • a obtenção de modelos com desvios mínimos em relação ao modelo original; • redução de dados maximizada; • visa a redução de dados com o objetivo de tornar seu processamento mais rápido; • do ponto de vista do usuário, o processo deve depender de uma quantidade mínima de parâmetros. 3.3 MOTIVAÇÃO PARA A GENERALIZAÇÃO Dentro do modelo de generalização proposto por MACMASTER & SHEA, FIRKOWSKI (2002) enuncia algumas razões filosóficas para generalização e que deverão servir como guias deste processo. Um primeiro objetivo da generalização é a redução da complexidade dos elementos representados tendo em vista facilitar o processo de comunicação. Com relação aos atributos, sua acurácia deve ser mantida mesmo com a alteração da escala. A manutenção da estética e da hierarquia lógica também deve estar entre as finalidades da generalização. Através da seleção de entidades essenciais para uma dada representação é possível reduzir a quantidade de elementos representados e melhorar aspectos de representação dos elementos selecionados. Além disso, o estabelecimento de uma hierarquia permite criação de uma seqüência de inserção de informações gráficas na qual as informações mais importantes precedem as de menor interesse. SPIESS (1995) ressalta dentre os principais benefícios da generalização a possibilidade de descrever a realidade com diferentes graus de abstração, separando, realçando e ilustrando a informação principal para cada grupo de usuários. Segundo JOÃO (1995), uma das razões da necessidade de generalização em GIS é a redução de dados. A generalização de dados permite uma redução no tempo de processamento 33 e no espaço necessário para o armazenamento. Essa generalização voltada para a redução de dados ou para análise está dentro da chamada generalização de modelos. De acordo com FIRKOWSKI (2002), a redução na quantidade de coordenadas necessárias para representar uma entidade no espaço acarreta também uma redução no volume de armazenamento de dados. Dentro desse caso, a generalização busca a manutenção de um poder de informação máximo com a redução dos requisitos de armazenamento. 3.4 QUANTIFICAÇÃO DOS ERROS EM GENERALIZAÇÃO A generalização, por imprimir alterações na quantidade de dados, na geometria e na topologia, produz desvios de precisão geralmente não mensuráveis ou estudados. Contudo, o estudo dos erros decorrentes da etapa de generalização na produção de novas bases é tão importante quanto a pesquisa de operadores e de algoritmos de generalização mais eficientes. A etapa de generalização cartográfica introduz uma série de erros indefinidos, imprevisíveis, diversificados e geralmente ignorados com o uso dessas mesmas bases como fontes de dados para análises. A respeito dessa grande variabilidade de erros, JOÃO (1995) afirma servir como o principal fator de diferenciação entre a generalização cartográfica e a generalização de modelos. Usuários de SIG geralmente ignoram os efeitos negativos da generalização cartográfica ao montarem suas bases de dados a partir da compilação de outras fontes que, por sua vez, também são produtos de generalização. Esses efeitos podem ser percebidos por diferenças encontradas em medições de distâncias e no posicionamento de feições bem definidas entre mapas de escalas menores generalizados e suas respectivas fontes de dados. A generalização de MDS, de forma semelhante à cartográfica, também deve ser feita levando-se em consideração os erros inseridos. A compreensão e quantificação desses erros permite um processo de generalização mais seguro, com limites de redução de informação bem definidos e com um maior conhecimento acerca da qualidade dos modelos generalizados. Considerar os erros resultantes dos processos de generalização tendo como objetivo a sua compreensão e redução é uma tarefa muito importante na elaboração de bases. O simples conhecimento dos tipos de erros gerados e de suas magnitudes permite o adequado uso das bases cartográficas para diferentes fins. O ideal da generalização, da seleção e realce das informações de interesse em um modelo deve ser feito de forma criteriosa e sem comprometer a qualidade final dos dados. Para isso, é 34 fundamental que todo processo de generalização de uma base de dados, seja ela voltada a modelos ou cartográfica, considere os erros inseridos ou a degradação dos modelos originais e tenha a minimização destes erros como um de seus objetivos. MACMASTER & SHEA (1992 apud FIRKOWSKI, 2002) apontam que a generalização cartográfica deve ocorrer dentro dos limites da comunicação cartográfica e do projeto cartográfico. Para mais detalhes acerca de generalização, sua conceituação e histórico bem como os principais operadores, recomenda-se a leitura de ISSMAEL (2003). A autora traça um paralelo com as principais correntes teóricas acerca de generalização e resume de forma clara seus operadores. 3.5 GENERALIZAÇÃO DE MODELOS DIGITAIS DE SUPERFÍCIE 3.5.1 MODELOS DE REPRESENTAÇÃO Modelos surgem da necessidade de representação e da impossibilidade de inserção exata de todos os detalhes tal qual aparecem no original. A utilização do termo “modelo” em diferentes contextos permeia uma idéia de aproximação com relação a uma cena, área ou objeto em foco. De acordo com GRÜNREICH (1996), modelos são ferramentas para várias disciplinas, sendo orientados com o propósito de classificação e de redução do original. São elaborados por um processo primário de generalização. Conforme o mesmo autor, as origens da teoria dos modelos cartográficos estão relacionadas com o mapeamento de ambiente necessário à sobrevivência humana. Dessa forma, mapas, por exemplo, são modelos de fenômenos naturais ou antrópicos na superfície terrestre, representados por meio de um conjunto de símbolos e outras representações em menor escala. Modelos são produtos de uma atividade criativa e representam aspectos importantes, sob determinado ponto de vista, de uma realidade. Para um mesmo espaço, é possível construir diferentes modelos conforme o ponto de vista de quem elaborou, o tema principal representado e o objetivo a que se destina. 35 A geração de modelos decorre invariavelmente da prática de generalização e redução da quantidade de dados a ponto de sempre restarem diferenças com relação ao original, por mais dados que sejam utilizados para a geração de um modelo. Para um mesmo modelo existem diferentes representações. Por exemplo, para a tarefa de representação do relevo a partir de um conjunto de pontos cotados, diferentes estratégias podem ser adotadas como a interpolação de um conjunto de curvas de nível, a geração de mapas de declividade, definição de cores hipsométricas, sombreamento ou, por fim, o uso direto dos próprios pontos com suas respectivas informações altimétricas. Para as diferentes estratégias apresentadas anteriormente, o modelo assume diferentes aspectos e repassa a informação do tema por meios diferentes em maior ou menor grau. Entretanto, trata-se de um único modelo em questão, independentemente de sua forma de exibição, uma vez que os dados usados como fonte são os mesmos. A coleta de dados é a etapa predominante para a criação de um modelo. É nessa fase que se determina a escala de representação do modelo resultante, sendo um fator que definirá suas aplicações subseqüentes. Após a reunião dos dados, envolvendo estágios de planejamento e de coleta em campo, pode-se dizer que há um modelo formado e que poderá ser visualizado de diferentes formas. A geração de modelos digitais geralmente envolve, além da coleta de dados, uma etapa extra de interpolação. Essa etapa tem por objetivo recompor uma superfície original a partir dos pontos de coordenadas conhecidas e procura aproximar as coordenadas de pontos intermediários. A função matemática adotada é o principal diferencial entre os diferentes tipos de interpolação. Como estruturas de dados disponíveis na etapa de interpolação, existem a grade retangular regular e a malha triangular irregular. Quando, a partir de uma amostra de dados, define-se uma estrutura de dados e um interpolador, há a formação de um novo modelo digital de superfície. Esse novo modelo terá características diferentes da amostra original de dados. Entretanto, as bases para a geração desse novo modelo foram lançadas na etapa de amostragem, a ponto de não ser possível melhorar o modelo resultante pela escolha de um interpolador e respectivos parâmetros para a tarefa. A prática de generalização também resulta em novos modelos. Mesmo com o objetivo de minimizar a perda de informações com a retirada de dados, a generalização resulta em modelos com diferentes cargas de elementos informativos. A FIG. 3.2 ilustra um modelo 36 digital de terreno, obtido pelo método da krigagem a partir de uma amostra de 516 pontos. A FIG. 3.3 ilustra um outro modelo digital de terreno, correspondente a uma generalização do primeiro, obtido a partir de um subconjunto de pontos da amostra original com o uso do interpolador krigagem, adotando os mesmos parâmetros. FIG. 3.2: Modelo digital de terreno original. FIG. 3.3: Modelo digital de terreno generalizado. Partindo-se de uma amostra escassa de dados não é possível recompor, por interpolação, uma superfície de distribuição de um fenômeno para escalas maiores a ponto de incluir detalhes menores antes não abrangidos. De modo semelhante à interpolação, uma 37 generalização bem sucedida, não tem o potencial de aprimorar a qualidade do modelo. Há somente a remoção de pontos redundantes e o esforço de manutenção da qualidade. A etapa de amostragem de dados determina como serão os modelos resultantes. Em função dessa relevância, é pertinente considerar os produtos originados da amostragem também como modelos de representação. No escopo da presente pesquisa não se considera a diferença formal entre amostras e modelos. A referência a um termo, apresentada até esse ponto ou nas partes subseqüentes, remete implicitamente a outro. Modelos representam uma visão de mundo particular, são frutos de um trabalho de planejamento e coleta de dados, de generalização. Podem assumir diferentes representações e podem ser ponto de partida para outros modelos. São aproximações de uma realidade. 3.5.2 OBJETIVO DA GENERALIZAÇÃO DE MODELOS DIGITAIS A elaboração de modelos digitais apresenta a amostragem ou coleta de dados como uma de suas principais etapas. A quantidade de dados e sua distribuição devem ser consideradas de forma cautelosa a ponto de uma amostra suficiente e bem distribuída de dados ser empregada para a geração de um MDS. Os termos “suficiente” e “bem distribuída”, empregados anteriormente, são por natureza vagos e imprecisos quando se trata da geração de modelos digitais de superfície, uma vez que não existem quantidades exatas pré-estabelecidas para cada tipo de modelo. Entende-se por suficiente a quantidade de dados que descreve uma variável espacial em um modelo de forma próxima ao inicialmente planejado ou imaginado; nessa configuração, todos os dados apresentam uma mesma importância na geração do modelo, a ponto da retirada de um dado poder resultar em degradação do modelo resultante ou da inserção de mais dados não produzir melhoras significativas, traduzindo redundância de dados. Segundo FIRKOWSKI (2003), a redundância de dados é dada por um descompasso entre quantidade de dados e o conteúdo informativo, a ponto do crescimento do primeiro não resultar necessariamente em uma melhoria do segundo. A distribuição de dados está ligada a uma disposição adequada dos dados para representação de todas as características principais de um modelo, sendo muito dependente da variação do fenômeno representado e da escala de representação. 38 Quantidade e distribuição são fatores estreitamente relacionados. Amostras densas, com menor distância entre os dados, relacionam-se a maiores quantidades de dados e vice-versa. Outros fatores também influenciam na questão da configuração de dados, tornando a sua determinação ainda mais complexa, tais como a variabilidade do fenômeno representado e a qualidade dos dados coletados. Dessa forma, por exemplo, dada uma amostra inicial de milhões de registros que compõem um modelo digital, a separação de uma amostra menor de dados em quantidade e densidade suficientes para a composição de um modelo semelhante ao modelo original não é uma tarefa trivial. Uma configuração de pontos nesse caso dificilmente pode ser considerada como ideal ou a que melhor se aproxima do modelo original em função da impossibilidade de considerar a totalidade das inúmeras configurações existentes. Além disso, diferentes configurações de dados podem resultar em modelos semelhantes, com volume e morfologias bem próximas. O estabelecimento de uma configuração de dados adequada para um modelo digital voltado para a representação de um fenômeno específico em foco, com todas as implicações anteriormente apresentadas é, ao mesmo tempo, motivação e objetivo da tarefa de generalização de modelos digitais de superfície. A redução de pontos para a geração de modelos digitais pode receber diferentes denominações. ASSUNÇÃO et al. (2007), chama essa tarefa de filtragem ao estudar a redução de amostras de pontos coletadas pelo sistema LIDAR. GABOARDI & FIRKOWSKI (2006) chamam esse processo de generalização. 3.5.3 TÉCNICAS DE GENERALIZAÇÃO São métodos empregados para orientar a prática de redução de pontos de um modelo e indicam quando ou até quando generalizar. 3.5.3.1 USO DE FUNÇÕES MATEMÁTICAS Modelos digitais podem ser gerados com o uso de funções contínuas, como polinômios ou Séries de Fourier. Partindo de um conjunto inicial de pontos, são determinados os coeficientes polinomiais ou determinados os termos de uma série, respectivamente, capazes de descrever o fenômeno espacial em questão. Superfícies geradas por esse método são conceituadas como contínuas globais por JONES (1997, apud FIRKOWSKI, 2002). 39 Seu uso também é possível como ferramentas auxiliares na generalização de dados, conforme apontam GABOARDI & FIRKOWSKI (2006), que estudam a redução de amostras de dados para a geração de modelos digitais por meio de Transformadas Wavelet e de Fourier. 3.5.3.2 SIMILARIDADE DE SEÇÕES Técnica criada por FIRKOWSKI (2002), que adota o conceito de similaridade, da Teoria Matemática da Comunicação (TMC), entre seções verticais paralelas de um modelo digital como parâmetro para a retirada de dados. O princípio envolvido fixa que a quantidade de informação de uma base é “o montante de informação necessária para atingir o propósito para o qual a base de dados se destina”. A redução da complexidade, a aplicação consistente das regras de generalização e a manutenção da qualidade estética podem ser auxiliadas pela aplicação da teoria da informação, de acordo com BJORKE (1996, apud FIRKOWSKI 2002). Uma grade regular, gerada a partir de pontos coletados com precisão compatível a uma escala E, ou provenientes de uma base na escala E, apresenta uma determinada quantidade de informação útil, determinada a partir de uma função de similaridade µ baseada em uma tolerância t. Para cada MDT é recomendado um valor de tolerância t e diferentes tolerâncias conduzem a diferentes valores de informação útil. O modelo é segmentado em seções paralelas verticais e são analisadas as similaridades entre as seções paralelas duas a duas. A similaridade é calculada em função das coordenadas dos pontos de duas seções verticais paralelas e dos valores dos desníveis de pontos homólogos dessas seções (FIG. 3.4). Quanto menor for o desnível entre pares de pontos de duas seções verticais paralelas, maior a similaridade. A ocorrência de valores de similaridade acima do valor estipulado de tolerância pode significar uma quantidade excessiva e redundante de dados. Sua retirada permite um aumento da informação útil do modelo, isto é, todos os dados restantes representam um peso importante no conteúdo informativo do novo modelo. Para cada par de pontos homólogos é determinado o desnível (∆h) e comparado com o valor de tolerância t. Caso o desnível seja menor ou igual à tolerância, há um incremento no valor da similaridade entre as duas seções verticais enquanto os desníveis maiores que t não contribuem para um aumento da mesma. Desse modo, quanto menor o valor da tolerância, 40 menor será a similaridade das seções e quanto maior a tolerância maior a similaridade e, consequentemente, maior a generalização do modelo. Pontos Homólogos Seções Verticais Paralelas FIG. 3.4: Seções verticais paralelas de um modelo digital (Adaptado de FIRKOWSKI 2002, p. 61). A remoção é aplicada para seções verticais paralelas aos eixos X e Y. Ao fim do processo, de acordo com FIRKOWSKI (2002), o modelo resultante será uma grade retangular, porém apresentando conformação irregular. 3.5.3.3 GENERALIZAÇÃO POR ALGORITMOS GENÉTICOS Essa técnica é a proposta dentro da presente pesquisa e consiste no emprego de algoritmos genéticos para otimizar a seleção de pontos que comporão a amostra de dados resultantes. Os principais aspectos teóricos relacionados aos algoritmos genéticos serão tratados no Capítulo 4. Para uma melhor compreensão, basta realizar uma analogia com um método bastante intuitivo baseado em séries de tentativas, chamado de Método Empírico ou de Tentativa e Erro. Nesse método, a partir de uma amostra inicial há a seleção aleatória de alguns pontos que serão candidatos a modelos generalizados. O critério adotado para avaliar cada candidato a solução pode ser objetivo (como a comparação do modelo com um conjunto de pontos de controle, por exemplo), ou subjetivo (perda mínima de detalhes, por exemplo). Segundo o critério escolhido, há como avaliar uma 41 amostra a partir da comparação de seu rendimento com o rendimento de outras amostras. Para cada amostra comparada é possível realizar a seleção daquela que melhor corresponde ao critério fixado. Após alguns testes realizados, e caso não sejam encontradas melhorias, a melhor amostra encontrada pode ser considerada como solução para o problema. O método é ilustrado na FIG. 3.5 . Geração Aleatória de Amostras Generalizadas Critério Amostras Avaliadas Amostra de Referência Seleção Melhor Amostra SIM NÃO A melhor amostra encontrada é mais apta que a Amostra de Referência? FIG. 3.5: Método empírico para generalização. Como principal desvantagem presente nesse método empírico, ressalta-se a falta de critério na criação de amostras generalizadas. Por ser feito aleatoriamente, é possível que as amostras geradas ao longo de uma iteração não apresentem diferenças marcantes entre si, bem como estejam bem aquém do nível de generalização esperado, sem que o usuário tenha uma noção do quanto o algoritmo progrediu, ou se poderá apresentar mais algum progresso. O entendimento desse método é útil para compreender parte do funcionamento de um algoritmo genético e ajuda a entender o porquê de seu uso ser vantajoso. Dentro desse contexto, os algoritmos genéticos surgem como notável método de busca. Atuam exatamente no ponto fraco principal de geração de novas amostras, permitindo a geração de novas soluções a partir de soluções anteriores por meio de mecanismos de seleção e de recombinação. À semelhança do método empírico, em um algoritmo genético a população inicial também pode ser gerada de forma aleatória. Contudo, a principal diferença está ligada à 42 geração das novas soluções, que são produzidas a partir da recombinação das soluções anteriores. A etapa de seleção visa a identificação e separação das melhores soluções/indivíduos, que deverão ser recombinadas posteriormente para produzir novas soluções. Os melhores indivíduos, no caso, são aqueles que atendam mais precisamente ao critério estabelecido. Uma vez selecionados, os pares de soluções (pais) são recombinados para a geração de novas soluções (FIG. 3.6). Esse artifício efetua a troca de informação entre os pais e garante que as novas soluções geradas apresentem características mistas das soluções anteriores, significando, na maioria das vezes, uma melhora nos resultados encontrados. A principal vantagem do uso de algoritmos genéticos é a possibilidade de aperfeiçoamento das soluções geradas inicialmente ao longo de cada iteração, chamada de geração. Dessa forma, apesar da população inicial ser composta por indivíduos ou soluções geradas aleatoriamente, com o curso das seleções e recombinações há uma melhoria das soluções presentes até atingir um patamar. Geração Aleatória de Amostras Generalizadas População de Amostras Critério Amostras Selecionadas Recombinação FIG. 3.6: Etapas de um algoritmo genético para generalização. A estratégia de algoritmos genéticos proposta considera cada ponto presente em um conjunto inicial de dados isoladamente. Um único ponto é o bastante para diferenciar duas amostras de dados enquanto modelos válidos para generalização, ou seja, a técnica permite a retirada de somente um ponto do conjunto, caso seja a melhor opção. 43 A técnica proposta pode ser aplicada tanto para a generalização de grades regulares quanto para malhas irregulares de pontos. Isso porque cada ponto pode ser considerado isoladamente para ser selecionado ou não no modelo final, não havendo obrigatoriedade de se considerar somente seções verticais paralelas como unidades mínimas de generalização. Por fim, não é necessária a definição de valores de tolerância para a criação de critérios de retirada de pontos, tal como acontece com alguns outros mecanismos de generalização. Nestes, há a necessidade de definição de um valor absoluto que servirá como referência para a retirada de pontos e, caso os desníveis encontrados em uma determinada área sejam inferiores ao valor de tolerância, um ponto poderá ser retirado. Uma desvantagem clara desses métodos baseados em um valor de tolerância é a dependência da generalização com relação a um único valor numérico, apresentando grandes variações conforme o valor definido. Dentro da abordagem de generalização de modelos digitais por algoritmos genéticos, outros métodos podem ser adotados em substituição ao valor de tolerância como critério para a seleção/retirada de pontos. Esses métodos podem ser baseados em um conjunto de pontos de valores de atributo conhecidos utilizados para controle ou a partir do modelo original adotado como referência. Conforme esses métodos, cada modelo generalizado candidato a solução pode ser comparado com um conjunto de pontos de controle ou com o modelo original adotado como referência. Aqueles modelos que apresentarem um menor desvio com relação ao método adotado poderão ser selecionados e participar de uma próxima geração dentro do algoritmo. 44 4 ALGORITMOS GENÉTICOS 4.1 ALGORITMOS GENÉTICOS NA COMPUTAÇÃO EVOLUTIVA Os algoritmos genéticos foram introduzidos e disseminados em sua forma clássica, com os conceitos que originaram e influenciaram as abordagens desenvolvidas atualmente, por John Holland , em 1975. De acordo com BÄCK et al. (1997), a estratégia de programação denominada algoritmos genéticos constitui apenas uma das abordagens existentes na área de computação evolutiva. Dentro dessa área os autores apontam os algoritmos genéticos, estratégias evolutivas e programação evolutiva, ressaltando que as mesmas permaneceram em estudo separadamente até o início dos anos 90 (FIG. 4.1). Computação Evolutiva Algoritmos Genéticos Programação Evolutiva Estratégias Evolutivas Sistemas Classificadores FIG. 4.1: Ramos da computação evolutiva. Para MICHALEWICZ (1994), a computação evolutiva reúne técnicas inspiradas nos mecanismos de evolução natural dos seres vivos. Basicamente aplicam conceitos de aptidão, seleção e evolução das soluções de um problema apresentando uma mesma estrutura geral. Para o mesmo autor os algoritmos genéticos surgem como uma das primeiras abordagens da computação evolutiva que simulam a evolução natural. A principal diferença entre as abordagens existentes dentro da computação evolutiva, conforme os mesmos autores, diz respeito à representação dos indivíduos, projeto dos operadores de variação e mecanismos de seleção/reprodução. Os algoritmos genéticos apresentavam inicialmente somente a codificação binária, tendo o cruzamento como o principal operador genético e a mutação aplicada em menor escala. 45 4.2 PRINCIPAIS CONCEITOS A introdução de alguns conceitos relacionados ao campo da biologia, fonte inspiradora dos algoritmos genéticos, é de grande importância e faz-se necessária antes da apresentação formal dos algoritmos genéticos. Cromossomos: uma unidade de código genético, responsável pelo aparecimento de determinadas características em um indivíduo. Na abordagem proposta, cada cromossomo é tratado como um indivíduo e representa uma solução característica para um problema. A informação genética de um indivíduo é chamada de genótipo e suas manifestações na estrutura são chamadas de fenótipo. Em algoritmos genéticos, os parâmetros que deverão ser otimizados constituem o chamado espaço-fenótipo, conforme BÄCK et al. (1997), são eles que ajudarão a compor a função objetivo do problema e estão relacionados ao comportamento ou resultados das combinações ou indivíduos gerados ao longo das gerações. O espaço-genótipo diz respeito à informação genética dos indivíduos, e é representado segundo codificações dos parâmetros. De acordo com isso, é importante que se tenha uma função de mapeamento entre os espaços fenótipo e genótipo do problema. Gene: é uma unidade genética que compõe a cadeia cromossômica. Cada gene pode assumir um rol de valores diferentes, denominados de alelos. Cruzamento (Crossover) : combinação dos cromossomos envolvendo troca de material genético e geração de características intermediárias. Mutação: alteração aleatória ou acidental do material genético. 4.3 EVOLUÇÃO NOS SISTEMAS NATURAIS Algoritmos genéticos, em conjunto com outras técnicas evolutivas, são chamados de sistemas evolutivos artificiais. Contudo, antes de apresentar os principais conceitos relacionados a algoritmos genéticos, é válido e oportuno fazer algumas considerações acerca de aspectos sobre o comportamento populacional e evolutivo de sistemas naturais. A propósito, o conceito principal de evolução de sistemas artificiais e demais mecanismos envolvidos foi inspirado pela observação e tentativa de simulação da capacidade de adaptação dos seres vivos a diferentes situações presentes em seu meio. Segundo DE JONG (1975), a capacidade de adaptação de alguns sistemas consiste na estratégia de gerar 46 melhores soluções para um problema por meio de um melhor conhecimento adquirido a partir da evolução ou melhoria de algumas soluções. Essa característica de seleção das melhores qualidades e aperfeiçoamento dos organismos ante um fator natural crítico é o que motiva e inspira pesquisas ao longo de várias décadas para a elaboração de sistemas voltados para a resolução de situações complexas. Alguns conceitos adotados hoje em sistemas evolutivos encontram paralelo na biologia. A adoção de termos como “indivíduo”, “cromossomo”, “população”, “aptidão”, dentre outros, é freqüente. Além, é claro, das tentativas de emulação do processo evolutivo natural em sistemas virtuais, envolvendo mecanismos de seleção, de cruzamento e mutação de indivíduos.Esse paralelo, entre uma realidade inspiradora e um modelo, justifica o uso de algumas situações expressas em sistemas naturais como meio auxiliar na compreensão do funcionamento de certos sistemas adaptativos. As características dos seres vivos são armazenadas em estruturas de DNA e RNA, organizados por cadeias menores denominadas cromossomos, que por sua vez são compostas por unidades menores denominadas genes. Esse conjunto é chamado de material genético e orienta tanto o surgimento de características próprias de uma espécie, desde os primeiros estágios embrionários de formação dos organismos, como também induz pequenas variações em cada organismo, úteis para a distinção entre indivíduos de uma mesma espécie no meio. As pequenas características aqui referidas podem ser, por exemplo, a cor do pêlo, tamanho e peso e servem para atribuir pequenas diferenciações a indivíduos, podendo contribuir para tornar um organismo mais apto para enfrentar uma adversidade do meio em que vive. Os indivíduos mais adaptados a um meio ganham como prêmio a possibilidade de permanecerem vivos e de se reproduzirem gerando descendentes, perpetuando assim suas características em gerações futuras. Para o caso de pequenos animais, cuja sobrevivência depende de sua capacidade de escapar dos predadores naturais, alguns fatores podem ser relevantes. Citando o exemplo da lebre do ártico, a cor branca do pêlo favorece a camuflagem em zonas cobertas por neve, dificultando a sua visualização pelos predadores, enquanto sua velocidade e agilidade são fundamentais para garantir uma fuga em caso de perseguição. Dessa forma, durante o inverno, essas duas características pequenas de agilidade e cor do pêlo podem ser fundamentais para a sobrevivência de um indivíduo. Outros fatores relacionados à competição dentro de uma mesma espécie exercem grande peso na sobrevivência e reprodução de organismos. Em comunidades de mamíferos, como a 47 dos leões e dos elefantes – marinhos, por exemplo, há o predomínio de um único macho para o conjunto de fêmeas de um grupo. Para esses casos, os machos tendem a disputar entre si o direito de acasalar com as fêmeas e de gerar descendentes, disseminando suas características de força e resistência. Outro fato marcante de competição ocorre com os leões. Em disputas pela liderança de um grupo, caso o desafiante saia como vencedor, uma das primeiras atividades do novo leão líder é matar os filhotes de seu antecessor, eliminando a carga genética do antigo líder e permitindo que as fêmeas entrem em um novo ciclo reprodutivo. Os indivíduos melhor adaptados a diferentes fatores do meio tendem a perpetuar suas características nas gerações futuras. Os seres mais adaptados são aqueles que reúnem um conjunto diversificado de qualidades que se mostraram adequadas para diferentes situações. Essa tendência de predomínio dos seres portadores de determinadas qualidades em detrimento de outros é chamada em algoritmos genéticos de elitismo e está relacionada à permanência das melhores qualidades de sobrevivência em um meio. O termo reprodução não significa, porém, a construção de uma réplica exata de um indivíduo. A reprodução de indivíduos sexuados geralmente envolve a recombinação da carga genética individual dos participantes para gerar indivíduos de uma nova geração. Os filhos gerados tenderão a apresentar características intermediárias de seus progenitores. Um mecanismo que ajuda a explicar esse fato é o cruzamento ou recombinação de cadeias cromossômicas dos pais durante a formação de um novo indivíduo. Por meio do cruzamento, as melhores características dos pais podem ser evidenciadas nos filhos, resultando em indivíduos ainda mais adaptados ao meio. Outro processo possível durante a formação de novos indivíduos, e que ocorre em menor escala, é a mutação. Esse processo envolve a alteração de forma aleatória de alguns genes de um indivíduo e pode surtir efeitos acentuados em seu fenótipo, caso ocorra nos estágios iniciais de formação. As alterações inseridas podem ser favoráveis ou não à adaptação com relação a um fator do meio. A seleção das melhores características de uma espécie, efetuada ao longo de várias gerações, provoca, por outro lado, a redução numérica de indivíduos com as chamadas características “desfavoráveis”. Isso significa uma redução da variabilidade genética de uma população, caso as condições ambientais não sofram alterações. Contudo, uma característica importante do meio natural é a sua variação em potencial. A sucessão de estações do ano, seguidas de períodos de variação climática com períodos longos 48 de estiagem ou períodos de chuvas em excesso, são exemplos de variações drásticas que podem ocorrer em intervalos curtos de tempo. Essas alterações ambientais afetam o relacionamento do meio com os seres vivos e repercutem diretamente na sua sobrevivência. Características que em um período eram favoráveis podem deixar de sê-lo posteriormente ou vice-versa. A natureza, complexa e imprevisível, atua de forma maternal com os indivíduos mais aptos e de forma implacável com os menos adaptados. Desse modo, o predomínio de um fenótipo, ou seja, a existência de indivíduos com determinadas características semelhantes, pode ser negativa. Caso ocorram modificações repentinas no meio para as quais os organismos não estejam adequadamente preparados, poderá haver uma redução numérica acentuada da população de baixa variabilidade genética, susceptível a essas modificações. Nesse caso, a disseminação de um único vírus, por exemplo, pode ser responsável pelo extermínio de milhares de indivíduos em uma população. Em que pese o predomínio de determinadas características nos indivíduos, a manutenção da variabilidade genética é fundamental para garantir a evolução de um conjunto de indivíduos. Algumas características outrora consideradas inservíveis podem mostrar-se preponderantes para a sobrevivência em um outro momento ou podem ser potencializadas positivamente quando combinadas com outras características. A manutenção de um repositório genético vasto em sistemas naturais é garantido por fatores como ciclos reprodutivos curtos e presença de populações compostas por milhares de indivíduos. O conhecimento exato do termo adaptação não é trivial e abrange um incontável conjunto de fatores. Do tamanho da população ao número de indivíduos de um mesmo sexo, do regime de chuvas ao tipo de terreno, da espécie vegetal predominante em uma região à população de predadores, existem diferentes fatores que podem ser correlacionados e servem para indicar o grau de aptidão de um indivíduo ao meio. A inserção de mais de um fator de adaptação em um sistema artificial ainda é algo relativamente novo. Algumas abordagens propõem a formação de mais de uma população, sendo uma dependente da outra, simulando basicamente a relação presa-predador. São tentativas ainda simples, comparadas ao modelo natural, de aumentar a complexidade dos sistemas artificiais e permitir que os mesmos sejam capazes de abordar uma quantidade cada vez maior de situações. Conforme DE JONG (1975), existem na natureza diversos exemplos de adaptação de comunidades de organismos a diferentes condições do meio ambiente ao longo de várias gerações. Pesquisas de sistemas com mecanismos adaptativos simples, mesmo não modelando 49 inteiramente a dinâmica populacional - ciclos de vida, regras de cruzamento, sexos, diferenças de espécies, aptidão, mobilidade, por exemplo – apresentam uma considerável capacidade de evolução. 4.4 CICLO BÁSICO DOS ALGORITMOS GENÉTICOS Os algoritmos genéticos operam com uma população de soluções para um dado problema em vez de tratar cada solução individualmente. Esse conjunto passa por uma série de seleções, pareamentos e recombinações com o intuito de geração de novas soluções e de melhoria das aptidões dos indivíduos. Inicialmente é gerada uma população inicial, contendo todos os indivíduos que serão avaliados no processo evolutivo. A geração pode ser aleatória ou por meio de algum método de intervenção dado pelo usuário. Os indivíduos da população inicial são então avaliados em função de sua capacidade de resolução do problema. Isso, em outros termos, é chamado de aptidão e reflete o quão próximo cada indivíduo está do resultado esperado para um problema. Em alguns casos, após essa avaliação, os indivíduos são ordenados segundo seus valores de aptidão. Após a avaliação e conhecimento das aptidões são selecionados os indivíduos que participarão de uma nova etapa de cruzamento. Dois indivíduos selecionados recombinam-se gerando dois novos indivíduos. Além do cruzamento, o operador mutação pode atuar sobre os indivíduos, alterando os valores de alguns genes e provocando o surgimento de novas informações. Após recombinações e cruzamentos novos indivíduos são gerados e deverão ingressar na população inicial em substituição a alguns indivíduos, de acordo com um critério específico. A inserção de novos indivíduos e modificação da população cria uma nova geração. Esses ciclos de gerações repetem-se até o algoritmo atingir um critério de parada pré-definido que pode ser dado pela chegada a um valor limite ou pela geração de indivíduos com valores de aptidão semelhantes. 50 4.5 REPRESENTAÇÕES DOS CROMOSSOMOS Cromossomos são as codificações dos parâmetros de um problema dentro de um algoritmo. Após a codificação, cada cromossomo é tratado como uma solução ou componente desta, podendo assumir a denominação de “indivíduos”. De acordo com DE JONG (1975), a representação do material genético de uma população pode ser feita através de indivíduos compostos por um único cromossomo (haplóides) ou formados por mais de uma cadeia cromossômica (poliplóides). A seguir são ilustradas as principais formas de representação. 4.5.1 REPRESENTAÇÃO BINÁRIA A representação binária dos cromossomos foi originalmente introduzida por John Holland. Uma das principais vantagens dessa representação diz respeito à facilidade de manipulação dos indivíduos, refletida, por exemplo, por uma aplicação mais fácil e intuitiva de operadores genéticos de cruzamento. Como desvantagem principal do modo de representação, SILVA (2006) ressalta que, para a resolução de problemas de natureza contínua que exigem uma boa precisão, a representação binária pode resultar em cromossomos muito extensos. As EQ. 4.1 e EQ. 4.2 estão voltadas para o cálculo de genes por cromossomo. 2m = (gmax -gmin).10n + 1 (4.1) m =log2.[(gmax -gmin).10n + 1] (4.2) onde m é o número de genes necessários para a representação binária em um cromossomo, n é a quantidade de casas decimais para a precisão requerida no problema e gmax e gmin são os limites superior e inferior do intervalo no domínio. 4.5.2 REPRESENTAÇÃO REAL A representação real surge como principal opção à tradicional representação binária dos cromossomos. Enquanto esta pode resultar em largas cadeias de cromossomos de acordo com o número de parâmetros considerados no problema e com a precisão requerida, a 51 representação real tem como principal vantagem a possibilidade de codificação de cromossomos menores e com uma boa precisão para os parâmetros representados. Cadeias longas de cromossomos podem dificultar a convergência do algoritmo, além de geralmente exigir uma maior capacidade de processamento e de demandar mais tempo para a execução, segundo LACERDA & CARVALHO (1999). Outra vantagem da representação real está relacionada à facilidade de interpretação dos resultados pelos usuários e de programação de operadores genéticos. 4.6 PARÂMETROS DOS ALGORITMOS GENÉTICOS 4.6.1 POPULAÇÃO INICIAL Compreende o primeiro conjunto de indivíduos ou soluções do problema que serão alvo de análise e aprimoramento pelos operadores genéticos. Não existe uma regra certa quanto ao número correto de indivíduos da população inicial. Entretanto, é importante considerar que uma população reduzida dificilmente pode abranger todas as opções de soluções em um espaço de busca, tornando lenta a busca de solução ao necessitar de uma maior quantidade de gerações. Por outro lado, uma população extensa pode tornar as etapas de avaliação dos indivíduos e de seleção lentas ao impor a necessidade de se pesquisar uma grande quantidade de indivíduos. Conforme os resultados obtidos por DE JONG (1975), o aumento do tamanho da população tende a evitar a convergência prematura e perda da variabilidade de informações antes de se atingir um resultado razoável. Entretanto, o aumento da população também pode reduzir a taxa de convergência para valores abaixo do esperado. Com efeito, populações maiores podem resultar em melhores soluções apesar de aumentarem o tempo de processamento. Cada aplicação deve ser analisada separadamente e concebida com um número de indivíduos razoável para permitir a obtenção da solução rápida, sem envolver muitas gerações desnecessariamente e com baixo custo computacional. A população inicial pode ser gerada de forma aleatória, sem envolver necessariamente todos os espaços de busca do universo de soluções, correndo o risco, entretanto, de os indivíduos estarem concentrados todos em uma região pequena dentro do espaço de soluções. Uma técnica interessante para iniciar a aplicação de um algoritmo genético é chamada de seeding. De acordo com LACERDA & CARVALHO (1999), consiste na inserção de soluções 52 obtidas por outros métodos ou por outras iterações na população inicial. Dessa forma, estaria se garantindo que o resultado da aplicação da estratégia evolutiva não seria inferior ao resultado obtido por outros métodos. Os mesmos autores indicam como alternativa a opção de gerar metade da população aleatoriamente e a segunda metade como uma inversão da primeira, garantindo uma abrangência maior dentro do espaço de busca. 4.6.2 FUNÇÃO OBJETIVO Corresponde à formulação matemática que inclui os parâmetros de interesse que interferem na solução dos problemas. É essa função que fornece valores objetivos para a qualificação dos indivíduos e seus resultados podem servir como grau de adaptabilidade dos indivíduos candidatos à solução. Em grande parte das abordagens evolutivas existentes a função objetivo não envolve uma grande complexidade formal, uma vez que não visa descrever todo o espaço de busca do problema de modo contínuo. Além disso, funções objetivo complexas tendem a exigir um maior tempo de processamento, resultando em iterações mais lentas, podendo ser aproximadas por outras formulações com comportamento semelhante e de resolução mais simples. Por outro lado, como o campo de aplicação dos algoritmos genéticos é bem amplo e não se resume ao campo das ciências exatas, em determinadas realidades estudadas não há uma formulação matemática exata que retrate um problema com todos os seus parâmetros, conforme lembra BÄCK et. al.(1997). Dessa forma, seja por questões de simplificação ou de necessidade de aproximação matemática, geralmente a função objetivo surge como o somatório dos parâmetros considerados no problema com seus respectivos pesos. 4.6.3 APTIDÃO Segundo LACERDA & CARVALHO (1999), a forma mais simples de se definir a aptidão de indivíduos é considerar o seu valor como sendo igual ao da função objetivo. 53 O conceito de aptidão de um indivíduo candidato à solução está relacionado à sua respectiva capacidade de resolução do problema, sendo necessária apenas para definir os indivíduos mais adaptados. Existem métodos alternativos para a atribuição da aptidão dos indivíduos em um GAS (do inglês Genetic Algorithm System). SILVA (2006), destaca o ordenamento (linear e exponencial) e o escalonamento como métodos principais para a determinação da aptidão de cromossomos. Existem outras formas de escalonamento para a determinação de aptidão de cromossomos tais como o escalonamento exponencial, logarítmico e com truncamento sigma, por exemplo. Mais detalhes podem ser buscados em SILVA (2006) e LACERDA & CARVALHO (1999). 4.6.3.1 ORDENAMENTO O método de ordenamento consiste em dispor os cromossomos em uma seqüência do melhor para o pior cromossomo. Essa seqüência pode ser feita de forma crescente ou decrescente dos valores dados pela função objetivo, conforme o problema seja de minimização ou de maximização. Se o problema é voltado para a determinação do mínimo da função objetivo, os cromossomos mais aptos serão aqueles de menor valor da função e o ordenamento deve ser em ordem crescente dos valores da função objetivo. Se o alvo é a determinação do ponto de máximo, os melhores indivíduos serão aqueles de maior valor da função e o ordenamento deve ser feito em ordem decrescente dos valores da função aptidão. Os dois valores extremos de aptidão (fmax e fmin) são geralmente arbitrados pelo usuário, podendo receber valores normalizados ou não. A aptidão pode ser definida de forma linear, conforme EQ. 4.3, proposta por BAKER (1987 apud SILVA, 2006), sendo fi o valor da aptidão calculado, fmin o valor mínimo de aptidão, fmax o máximo valor de aptidão presente, i a posição do cromossomo no ordenamento e N o tamanho da população. fi = fmin + (fmax - fmin).(N- i)/(N-1) 54 (4.3) 4.6.3.2 ESCALONAMENTO O escalonamento consiste em aproximar o valor da aptidão de indivíduos segundo uma equação matemática em função de parâmetros como pressão de seleção e da função objetivo, por exemplo. Pressão de seleção de uma população é definida como a razão entre a aptidão máxima e a aptidão média. Pequenos valores de pressão de seleção indicam pouca variabilidade dos indivíduos de uma população. Indivíduos com valores correspondentes da função objetivo muito próximos entre si, tenderão, da mesma forma, a permanecer com valores próximos de aptidão, dificultando sua distinção e seleção. O método de escalonamento linear utiliza a EQ. 4.4, conforme ilustrado em LACERDA & CARVALHO (1999). fi = a.g i + b (4.4) sendo g o valor da função objetivo e os coeficientes a e b determinados de maneira a regular a variabilidade da população e evitando aptidões negativas (fmin < 0). 4.6.4 OPERADORES DE SELEÇÃO Dentro das estratégias de programação evolutiva, a seleção dos melhores indivíduos é um fator crucial para o aperfeiçoamento das soluções. Dessa forma, o critério de seleção deve se basear no valor das aptidões dos indivíduos de uma população e ser abrangente, permitindo que os cromossomos selecionados reflitam uma avaliação representativa da população e não de um grupo somente. Essa tarefa aparentemente simples torna-se complexa ao se considerar populações contendo centenas de indivíduos. Por isso, métodos eficientes de seleção devem ser buscados. Adiante são apresentadas as duas principais técnicas de seleção de indivíduos: roda da roleta e seleção por torneio. Outros métodos de seleção de indivíduos. Como Amostragem Estocástica Universal e Amostragem Determinística podem ser vistos em SILVA (2006). 55 4.6.4.1 RODA DA ROLETA A denominação do método pode ser em virtude da forma de considerar os cromossomos, geralmente remetendo a gráficos do tipo torta ou a uma roleta, na qual cada espaço é diretamente proporcional à probabilidade acumulada de cada indivíduo. É um método de busca aleatória que envolve o cálculo das probabilidades de seleção dos indivíduos e das probabilidades de seleção acumuladas. A probabilidade de seleção de um indivíduo é definida como a razão entre sua aptidão e a soma total das aptidões de todos os indivíduos em uma população (EQ. 4.5). pi = f i / ∑ f j (4.5) Uma vez determinadas as probabilidades, os cromossomos são ordenados de acordo com o seu valor de aptidão. A probabilidade acumulada de seleção é obtida por meio da soma das probabilidades de seleção de cada cromossomo na seqüência, como mostra a TAB. 4.1 para oito indivíduos. TAB. 4.1: Probabilidades de seleção pela Roda da Roleta. Indivíduo Aptidão (fi) Probabilidade de Seleção Simples (%) Acumulada (%) 1 1 18,94 18,94 2 0,9 17,05 35,98 3 0,82 15,53 51,52 4 0,74 14,02 65,53 5 0,68 12,88 78,41 6 0,53 10,04 88,45 7 0,41 7,77 96,21 8 0,2 3,79 100,00 Uma vez dispostos os cromossomos em seqüência, é gerado um número aleatório r de uma distribuição uniforme, geralmente entre 0 e 1. Segundo LACERDA & CARVALHO 56 (1999), o cromossomo selecionado será o primeiro que tiver uma probabilidade de seleção acumulada maior ou igual a r . De acordo com SILVA (2006) este método tem como desvantagens o fato de necessitar de um ordenamento prévio dos cromossomos, de não funcionar com aptidões negativas e, diante de mínimos ou máximos locais com alta pressão de seleção, a convergência tende a ser prematura. 4.6.4.2 SELEÇÃO POR TORNEIO Esse método consiste na seleção aleatória de n cromossomos da população e, dentre esse conjunto, escolher aquele de maior aptidão. A principal vantagem desse método é a de poder aceitar diretamente os valores da função objetivo e de não necessitar de escalonamento ou ordenamento dos cromossomos para a seleção, segundo LACERDA & CARVALHO (1999). Os cromossomos selecionados em cada torneio ajudarão a compor a população intermediária, reunindo os indivíduos que se combinarão para formar uma nova geração. 4.6.5 OPERADORES GENÉTICOS 4.6.5.1 OPERADOR CRUZAMENTO Consiste na troca de informações entre dois indivíduos gerando um descendente com características intermediárias. Para cada par de indivíduos selecionados previamente, somente uma parcela passará por uma recombinação de características. O fator que identifica a quantidade de indivíduos em uma população que passarão por cruzamento é chamado de taxa de cruzamento. O operador de cruzamento é o principal responsável pelo aperfeiçoamento contínuo dos indivíduos nos algoritmos genéticos. De acordo BÄCK (1997) a principal característica da técnica de programação dos algoritmos genéticos, que ajuda a distinguir de outras técnicas de programação evolutiva, é a presença de altas taxas de cruzamento em paralelo ao uso do operador mutação com pequenas taxas. Os operadores de cruzamento, inicialmente propostos com as primeiras abordagens, relacionam-se com a representação binária clássica nos algoritmos genéticos canônicos. Para esses operadores, dado um par de indivíduos selecionados previamente, escolhe-se 57 aleatoriamente um ponto na cadeia binária, denominado ponto de cruzamento, que delimita os indivíduos em dois ou mais segmentos (de acordo com seu número) e os lados homólogos dos dois indivíduos são trocados gerando um novo indivíduo (FIG. 4.2). Existem ainda outras variantes dependendo do problema a ser tratado e conforme a codificação adotada. Para a codificação real dos cromossomos, por exemplo, existem outras formas de se realizar uma recombinação de indivíduos. Pai 1_ 1 1 0 1 0 0 1 1 Pai 2_ 1 0 0 1 1 0 1 0 Filho1 1 0 0 1 0 0 1 1 Filho 2 1 1 0 1 1 0 1 0 FIG. 4.2: Cruzamento de 1 Ponto. LACERDA & CARVALHO (1999) chamam de convencionais as técnicas de cruzamento aplicáveis a cromossomos de representação binária enquanto os operadores aplicáveis em representações reais são chamados aritméticos. Por fim, se o problema estudado for do tipo de permutação, também existem operadores próprios para tal situação. Esse resumo adotará essa mesma classificação para os cruzamentos aqui apresentados. Por maior que seja a quantidade de operadores de cruzamento, BÄCK (1997) lembra que não existe um operador geral e ideal para todos os problemas. 4.6.5.1.1 OPERADORES CONVENCIONAIS 4.6.5.1.1.1 CRUZAMENTO DE N PONTOS A partir da abordagem clássica binária proposta por Holland, outras modificações podem ser inseridas no operador aumentando o número de pontos de cruzamento, configurando o chamado cruzamento de n pontos (FIG. 4.3). A escolha dos n pontos que envolverão troca de bits geralmente é feita de forma aleatória. 58 Pai 1_ 1 1 0 1 0 0 1 1 Pai 2_ 1 0 0 1 1 0 1 0 Filho1 1 0 0 1 1 0 1 1 Filho 2 1 1 0 1 0 0 1 0 FIG. 4.3: Cruzamento de 3 pontos. 4.6.5.1.1.2 CRUZAMENTO UNIFORME Técnica de cruzamento adotada para cromossomos com codificação binária que envolve o uso de uma máscara binária com o mesmo número de bits dos cromossomos que passarão por uma recombinação (pais). Segundo LACERDA & CARVALHO (1999), se um bit da máscara tiver o valor 1 ou 0, o bit correspondente do cromossomo filho receberá o valor presente no cromossomo pai 1 ou do pai 2, respectivamente, conforme ilustrado na FIG. 4.4 . Máscara_ 1 0 0 1 0 1 0 0 Pai 1_ 1 1 0 1 0 0 1 1 Filho 1 0 0 1 1 0 1 0 Pai 2_ 1 0 0 0 1 0 1 0 FIG. 4.4: Cruzamento uniforme (adaptado de LACERDA & CARVALHO, 1999). 59 4.6.5.1.2 OPERADORES ARITMÉTICOS 4.6.5.1.2.1 CRUZAMENTO MÉDIA Segundo DAVIS (1991 apud LACERDA & CARVALHO, 1999), o cromossomo filho é obtido a partir da média aritmética dos dois cromossomos pais p1 e p2. Como variantes ao método são apontados os cruzamentos média geométrica, aplicável para cada um dos genes dos cromossomos envolvidos. O principal ponto fraco apontado para o operador média é a sua tendência em levar os cromossomos filhos para zonas intermediárias do espaço de busca, reduzindo a variabilidade dos indivíduos das gerações seguintes. 4.6.5.1.2.2 CRUZAMENTO LINEAR Os cromossomos filhos são obtidos por uma combinação linear dos cromossomos pais, multiplicados por coeficientes que somados dão o valor 1. Segundo WRIGHT (1991 apud LACERDA & CARVALHO, 1999), são formas de obtenção dos cromossomos filho, por meio de cruzamentos lineares. As equações 4.6 e 4.7 são exemplos de cruzamentos lineares de dois pais p1 e p2, gerando dois filhos C1 e C2. C1= -0,5.p1 + 1,5.p2 (4.6) C2= 0,5.p1 + 0,5.p2 (4.7) 4.6.5.1.2.3 CRUZAMENTO BLX-α Uma forma de evitar a redução de variabilidade conseqüente dos operadores de média é a utilização desse operador, também chamado de cruzamento mistura (BL do inglês: blend). O valor de α é definido previamente pelo usuário. Os novos filhos são gerados por meio de uma combinação linear dos pais, ilustrado por ESHELMAN & SHAFFER (1993 apud LACERDA & CARVALHO, 1999), de acordo com a EQ. 4.8. C = p1 + β.(p2 - p1) 60 (4.8) Na EQ. 4.8 p1 e p2 são dois cromossomos pais situados em um intervalo real I; C o cromossomo filho e β um valor real situado no intervalo (-α, 1+α). O valor de β pode ser o mesmo para todos os cromossomos ou variável. Quanto maior o valor de α , maior a amplitude do intervalo resultante para os cromossomos filhos. Caso seja utilizado um mesmo valor β, os cromossomos filhos estarão situados sobre uma mesma reta. Se forem aplicados valores diversos de β para as recombinações realizadas, os filhos estarão situados em uma região n-dimensional, conforme o número de parâmetros considerados no problema. 4.6.5.1.2.4 CRUZAMENTO ARITMÉTICO MICHALEWICS (1994 apud LACERDA & CARVALHO, 1999) aponta a geração de novos cromossomos a partir das combinações dadas pelas EQ. 4.9 e EQ. 4.10, sendo β um número aleatório compreendido entre 0 e 1. Desse modo, não há uma extrapolação do intervalo original dos cromossomos pais. C1 = β.p1 + (1- β).p2 (4.9) C2 = (1- β).p1 + β.p2 (4.10) 4.6.5.2 OPERADOR MUTAÇÃO O operador genético de mutação é descrito geralmente como um operador de fundo em algoritmos genéticos, isto é, sendo aplicado de forma cautelosa e geralmente associado a uma baixa probabilidade. Autores recomendam geralmente uma baixa taxa de mutação em algoritmos genéticos (inferior a 1%). Isso principalmente porque o emprego da mutação em larga escala pode apagar as melhores informações presentes nos indivíduos, segundo SILVA (2006). Para DE JONG (1975), é esperado que o operador mutação acarrete tanto um aumento da variabilidade quanto a perda de informação genética relevante, principalmente após decorridas várias gerações e as soluções aproximam-se de um valor de parada ótimo. A principal vantagem da mutação está na redução da perda de alelos, ao passo que sua desvantagem está em modificar ou alterar indivíduos candidatos à solução, degradando o resultado final. 61 Trata-se, portanto, de um operador importante que pode garantir um maior rendimento ou melhores resultados de um algoritmo genético, mas que deve ser adequado a cada situação. Uma opção é a adoção de taxas variáveis de mutação, sensíveis a fatores como a variabilidade genética da população, número de gerações e aptidão média dos indivíduos. De acordo com BÄCK et al. (1997), alguns estudos demonstraram que taxas elevadas de mutação e decrescentes ao longo das gerações mostraram-se favoráveis à velocidade de convergência e solução por um algoritmo genético. Boa parte dos operadores de mutação consiste em uma escolha aleatória dos genes a serem alterados e na sua substituição por um número também aleatório, dentro do intervalo de pesquisa. A distribuição numérica associada ao sorteio desse número aleatório que ocupará o gene é o principal fator diferencial entre as técnicas de mutação encontradas. Assim, por exemplo, define-se a mutação uniforme como sendo a mutação que ocorre pela substituição de um gene por um número gerado por uma distribuição uniforme. 4.6.5.2.1 MUTAÇÃO GAUSSIANA Segundo SILVA (2006), a mutação gaussiana consiste na substituição de um gene por um número gerado por uma distribuição gaussiana com média igual ao valor inicial do gene e desvio padrão (σ) dependente do intervalo de valores que os genes podem assumir. 4.6.5.2.2 MUTAÇÃO LIMITE Essa mutação tem o principal efeito de expandir os valores dos genes para os limites do intervalo definido para o problema e pode ser indicado para aumentar a variabilidade de genes com valores muito concentrados em porções intermediárias do intervalo. A formulação é proposta por MICHALEWICS (1994 apud SILVA, 2006) e envolve a seleção de um número aleatório r para e definição do novo valor (EQ. 4.11 e EQ. 4.12). Gene i = ai, se r < 0.5 (4.11) Gene i = bi, se r ≥ 0.5 (4.12) sendo ai o valor mínimo do intervalo e bi , o valor máximo do intervalo permitido. 62 4.6.6 SUBSTITUIÇÃO DOS CROMOSSOMOS A etapa de substituição sucede as etapas de cruzamento e de mutação e pretende formar uma nova população que representará uma nova geração e dará início a uma nova rotina de busca de soluções. As substituições geracional e steady state são os dois métodos principais para a substituição de indivíduos. 4.6.6.1 GERACIONAL Essa forma de substituição de indivíduos, segundo SILVA (2006), consiste na substituição de todos os indivíduos de uma população por uma nova geração. Dessa forma, os pais serão integralmente substituídos por seus filhos para formar a próxima população. A desvantagem latente desse método de substituição é o risco de perda de boas soluções para o problema e a possibilidade de substituição de indivíduos com boa aptidão por indivíduos de aptidão inferior. Em função desse risco de perda das melhores soluções, essa técnica de substituição pode ser aplicada com baixas taxas de cruzamento e de mutação, aumentando a chance dos indivíduos retornarem à população sem sofrerem recombinação ou mutação. Uma alternativa para diminuir o risco de perda das melhores soluções pode ser a manutenção dos k melhores indivíduos de uma população. Essa técnica é conhecida como elitismo e, segundo LACERDA & CARVALHO (1999), é mais indicada a manutenção de somente um melhor indivíduo (k = 1) por população sob pena de aumentar-se o risco de convergência prematura do algoritmo. 4.6.6.2 STEADY STATE Face o risco de inserção de indivíduos com pior aptidão no sistema pelo método geracional, a substituição steady state envolve a substituição de n novos indivíduos pelos n piores indivíduos na população, segundo SILVA (2006). Para LACERDA & CARVALHO (1999), na substituição steady state são criados somente dois em cada geração que substituirão dois outros indivíduos da população. A determinação dos que serão substituídos pode ser feita considerando os de pior aptidão ou 63 aqueles com maior tempo na população. Uma forma geral de se considerar essa técnica é a substituição de n indivíduos por n filhos oriundos de recombinação. 4.6.7 CRITÉRIOS DE CONVERGÊNCIA Convergência pode ser entendida como o surgimento de um padrão de respostas para um caso em estudo. Ao longo das gerações, com a seleção e recombinação dos indivíduos, é natural que as aptidões tenham uma melhoria. Entretanto, essa melhoria pode ser inicialmente nítida e não alterar-se significativamente ao longo das gerações seguintes, dando a entender que atingiu um máximo (ou um mínimo). A repetição das aptidões de determinados indivíduos em torno de certos pontos e a manutenção de aptidões médias em uma população são indícios de que o algoritmo atingiu um patamar em termos de aptidão. Em outras palavras, o sistema pode ter convergido para uma resposta. Existem diferentes critérios de parada para a determinação da convergência em um algoritmo genético. SILVA (2006) destaca como principais critérios: convergência da aptidão; número de gerações; e convergência para um mesmo valor. Além desses, a chegada no ponto de máximo (ou mínimo) da função, quando conhecido, pode ser outro critério adotado. Por convergência da aptidão entende-se a obtenção de um valor de aptidão que tende a ser repetido ao longo das gerações ou em torno do qual as aptidões encontradas oscilem. A convergência para um mesmo valor ocorre quando a maioria dos cromossomos em uma população possui o mesmo valor de aptidão. Para esses casos, pode acontecer um fenômeno conhecido como convergência prematura, caracterizado como a multiplicação excessiva de indivíduos relacionados a máximos (ou mínimos) locais. A convergência prematura acontece principalmente quando não existem indivíduos com aptidões correspondentes aos pontos de máximo (ou mínimo) global, mas somente indivíduos ligados a máximos (ou mínimos) locais. Esses últimos tendem a se reproduzir em maior intensidade que os demais e a gerar mais descendentes até que, após certo tempo, os indivíduos resultantes concentrem-se em torno do ponto de máximo (ou mínimo) local. O critério de parada por número de gerações pode ser adotado principalmente quando não se conhece a solução exata para o problema e o número de combinações a serem exploradas é 64 muito grande. Para esses casos complexos, onde o algoritmo pode permanecer em iteração por um período extenso, limitar o número de gerações é ser uma alternativa. 4.7 CONFIGURAÇÃO DOS ALGORITMOS GENÉTICOS Os parâmetros dos algoritmos genéticos dizem respeito às opções de configuração e escolha dos operadores que deve ser feita antes de cada iteração. Consiste na definição, por exemplo, do tamanho da população, da técnica de substituição adotada e dos tipos de cruzamento e de mutação, bem como de suas respectivas taxas. Não existem configurações que sejam eficientes e de uso geral, sendo que, para cada espécie de problema, pode haver uma configuração diferente que seja mais adequada. A escolha de uma configuração de parâmetros e de operadores adequada ao problema tende a aumentar a eficiência de um algoritmo genético. De acordo com HINTERDING et al (1997), o ajuste dos parâmetros e operadores em um algoritmo evolutivo é uma tarefa que consome muito tempo e esforço havendo pesquisas para estudar sua automatização. A definição dos parâmetros utilizados no algoritmo proposto é feita por meio da realização de testes em diferentes configurações. À medida que diferentes configurações são testadas e comparadas entre si, são selecionadas as melhores alternativas de configuração e realizados novos testes. Segundo HINTERDING et al (1997), esse método de adequação do algoritmo a um problema por meio da realização de testes por um agente externo é chamado de adaptação estática. As taxas de aplicação dos operadores genéticos podem ser fixas ou variar conforme as gerações de forma a dosar a variabilidade de indivíduos das populações. 4.8 CARACTERÍSTICAS GERAIS DOS ALGORITMOS GENÉTICOS BÄCK et al. (1997) ressaltam os aspectos gerais dos Sistemas de Algoritmos Genéticos (GAS) ao enunciar as principais dificuldades encontradas na criação de um algoritmo genético para a otimização de um problema real. Em primeiro lugar, o desenvolvimento de um GAS depende da representação apropriada dos parâmetros que influenciam no problema em estudo e, baseado nisso, dos operadores genéticos correspondentes à representação escolhida. A definição dos parâmetros é importante para a formulação da função objetivo em estudo. Por exemplo, caso seja adotada uma 65 representação real para os cromossomos, deverão ser escolhidos operadores de cruzamento e de mutação próprios para essa representação. Sendo assim, é fundamental que se tenha um conhecimento especializado do problema a ser estudado para levantar os parâmetros realmente importantes. Esse conhecimento vai orientar a definição dos parâmetros e da função objetivo. Os parâmetros do algoritmo devem ser ajustados conforme resultados obtidos por outras aplicações ou resultados obtidos em testes sobre o problema em questão. Esse ajuste é necessário para definir as configurações de operadores genéticos e outros parâmetros mais adequados para o estudo do problema. Por fim, como dito anteriormente, o que diferencia os algoritmos genéticos de outras estratégias evolutivas é o predomínio de operadores de cruzamento com relação à mutação na formação de novos indivíduos. 66 5 ALGORITMO DE GENERALIZAÇÃO Esse Capítulo é voltado para a explicação dos operadores e estruturas considerados para o algoritmo genético no problema de generalização de MDS. Resume-se à montagem da estrutura do algoritmo aplicado ao problema, envolvendo etapas como a formulação da função objetivo, escolha da estrutura dos cromossomos e definição de operadores. 5.1 CODIFICAÇÃO DO PROBLEMA 5.1.1 ESTRUTURA DOS CROMOSSOMOS A estrutura geral formulada para os trabalhos aqui realizados foi uma estrutura semelhante ao algoritmo genético clássico, ou canônico, formulado por seu criador John Holland, em 1975. Essa estrutura caracteriza-se por cromossomos de cadeias binárias. Essa opção pelo algoritmo genéticos simples foi feita primeiramente em função de ser uma estrutura clássica, relativamente intuitiva, e por não terem sido verificadas, dentro da literatura pesquisada, outras tentativas e abordagens de generalização de modelos digitais de superfície por algoritmos genéticos que fornecessem uma referência suplementar acerca do assunto. Ressalta-se que a tarefa de generalização envolve a consideração de todos os pontos em um universo de dados como uma unidade específica. A estratégia adotada foi a geração aleatória de amostras menores a partir de conjunto total de pontos. Cada amostra aleatória corresponde a um indivíduo que representa informação sobre a ausência / presença de um ponto específico. Seguindo essa estratégia, a estrutura binária dos cromossomos mostrou-se a mais adequada para simbolizar a presença de um ponto na amostra, uma vez que cada ponto presente na amostra de dados apresenta um locus correspondente na cadeia cromossômica. Assim, o primeiro ponto é simbolizado no primeiro locus, o segundo ponto no segundo locus e assim sucessivamente até cobrir todos os pontos, conforme a FIG. 5.1. Por essa codificação, 0 significa a ausência do ponto na amostra e 1 a presença do ponto. 67 Cada ponto dessa forma é tratado como um parâmetro diferente e igualmente importante. Não são atribuídos pesos aos pontos existentes que sirvam para favorecer a sua permanência na amostra generalizada. Cromossomo Ponto X Y Z 1 7999781,66 5000218,61 51.431 0 Ausente 2 7999786,34 5000232,27 631.442 0 Ausente 3 7999794,12 5000248,84 749.184 1 Presente 4 7999799,75 5000267,30 786.248 1 Presente 5 7999838,79 5000279,48 100.932 1 Presente 6 7999841,04 5000377,14 206.204 0 Ausente 7 7999840,67 5000371,42 385.162 0 Ausente 8 7999840,37 5000361,92 560.029 1 Presente 9 7999839,65 5000349,24 709.194 0 Ausente 10 7999838,83 5000333,74 832.675 1 Presente FIG. 5.1: Correlação de pontos na cadeia cromossômica. Observando um cromossomo é possível ter noção do tamanho de espaço de busca para a generalização de modelos digitais. Uma vez que cada locus pode assumir dois valores, o número total de configurações de pontos possíveis de serem examinadas, excluindo as possibilidades da amostra já conhecida com todos os pontos e de uma amostra com nenhum ponto, é dada pela EQ. 5.1. W = 2j – 2 (5.1) sendo j o número de pontos presentes na amostra original de pontos. Essa equação expressa o número de possibilidades sem desconsiderar algumas opções bem extremas, como por exemplo, o caso de amostras com 1 ou 2 pontos apenas. Assim o algoritmo corre o risco de perder tempo analisando indivíduos (ou amostras) praticamente infactíveis. Uma forma de contornar esse risco é um controle maior sobre os indivíduos que serão inseridos na população inicial e darão origem a todas as outras gerações. Uma desvantagem clara da codificação binária para a representação de pontos é a susceptibilidade de formação de cadeias cromossômicas muito extensas, segundo a quantidade de pontos em uma amostra a ser generalizada. Esse fato certamente tende a limitar 68 a quantidade de pontos nas amostras de teste sob pena do tempo de processamento ser demasiadamente moroso. O desenvolvimento de uma codificação real ou divisão das regiões em estudo em áreas menores, no sentido de reduzir a quantidade de pontos analisados por iteração, podem ser soluções viáveis ao problema das grandes cadeias numéricas. 5.1.2 FORMAÇÃO DA POPULAÇÃO INICIAL Segundo a seção anterior, cada cadeia binária representa um subconjunto específico de pontos, candidato a solução do problema de generalização. As populações formadas por esses cromossomos serão, conseqüentemente, conjuntos de amostras de pontos, candidatos a modelos generalizados que deverão passar por sucessivas etapas de seleção e de recombinação para obtenção de melhores amostras. As populações iniciais podem ser obtidas por duas formas. Primeiramente, podem ser geradas a partir de indivíduos/cromossomos formados por iterações anteriores, sendo essa opção chamada seeding. Podem também ser geradas de forma aleatória. A técnica seeding garante a inserção de indivíduos factíveis na população inicial, uma vez que os cromossomos que compõem a população inicial são provenientes de outras iterações. Além disso, há a garantia de que não serão encontradas soluções de pior qualidade que aquelas inseridas inicialmente no sistema. A geração aleatória da população inicial, por outro lado, abre espaço para a criação de indivíduos infactíveis. Por infactíveis entenda-se aqueles que representem amostras com percentuais de generalização acentuados e prejudiciais e cuja inserção em uma população pode prejudicar a evolução geral das respostas. A prática de generalização ou eliminação de pontos tem um limite para sua execução, além do qual a retirada de pontos significa a degradação do modelo com a perda extrema de conteúdo informativo. Um mecanismo útil para a geração da população aleatória foi a inserção de um limitador de percentual de generalização para os cromossomos iniciais. Por meio deste, o usuário especifica percentuais mínimo e máximo de generalização e, durante a formação aleatória dos indivíduos, o programa confere se foi formado algum com percentual de generalização abaixo ou acima do limite. Os indivíduos que ultrapassarem o limite serão descartados e substituídos por outros. A geração da população encerra-se quando todos os indivíduos foram formados dentro do limite de generalização. 69 Essa técnica controla a qualidade dos indivíduos na população inicial. Entretanto, com a ocorrência das seleções e cruzamentos ao longo das gerações, pode ser que os indivíduos resultantes apresentem um percentual de generalização acima do limite estipulado pelo usuário. Isso ocorre em função da possibilidade de dois indivíduos que participam de uma recombinação trocarem, por exemplo, seus segmentos de maior percentual de generalização de pontos formando um novo indivíduo que represente uma amostra de dados ainda mais generalizada (com menos pontos). Por isso, a generalização de uma amostra não é restrita ao limitador, podendo extrapolar o percentual inicialmente acertado. Porém, tal como acontece com a possibilidade de geração de indivíduos com um percentual elevado de generalização, pode ocorrer a formação de indivíduos com um baixo percentual de generalização na população inicial, vindo a limitar a tarefa de generalização e resultando em soluções com um baixo percentual de redução de pontos. A possibilidade de inserção de indivíduos de baixo ou elevado percentuais de generalização, que representam soluções indesejadas em uma população inicial, justifica a importância da definição de percentuais limitadores que assegurem uma boa generalização sem permitir a criação de amostras infactíveis de dados na população inicial. 5.1.3 FUNÇÃO OBJETIVO A função objetivo para o problema de generalização de pontos deve constituir um referencial para a retirada de dados da amostra que permita a redução de informação redundante sem reduzir o conteúdo informativo do modelo ou degradá-lo. Ao mesmo tempo, a função objetivo deve fornecer valores que permitam verificar a qualidade dos modelos generalizados. Para garantir essas características foram levantados dois critérios para a verificação da qualidade dos indivíduos. No caso da presente pesquisa, os indivíduos correspondem a modelos digitais. Um primeiro critério é a separação de pontos de controle para a verificação das amostras, que consiste em utilizar um conjunto de pontos no terreno com valores de atributo conhecido e compará-los com o valor do atributo fornecido pelo modelo. As diferenças ou erros absolutos de atributos (fornecido pelo modelo – atributo do ponto) servem para conceituar os modelos, sendo o valor resultante obtido em função da média dos erros absolutos encontrados para os pontos de controle, pela EQ 5.2. 70 f j = | ∑n dj | / n (5.2) sendo fj o valor da função objetivo para o modelo candidato à solução j , n o número de pontos de controle, di o erro para cada ponto. O critério de comparação com pontos de controle sofre interferência de fatores como a quantidade de pontos considerados para controle bem como de sua distribuição. Além disso, os pontos usados como controle não podem fazer parte da amostra de dados utilizada para gerar o modelo a ser avaliado. A FIG. 5.2 ilustra um conjunto de pontos de controle, com altitudes definidas, que servem como critério de comparação para os valores de altitudes presentes no modelo a ser avaliado. FIG. 5.2: Uso de pontos de controle. Um segundo critério possível para a função objetivo é o cálculo da diferença de volume entre os modelos generalizados e o modelo formado por todos os pontos. Essa técnica, a de estabelecer a diferença de volume como referência, considera o conjunto inicial de todos os pontos como padrão para os modelos generalizados. A FIG. 5.3 ilustra as diferenças de volume para dois modelos de uma mesma região, sendo vistos sob três perspectivas diferentes. Os valores numéricos da diferença de volume entre dois modelos geralmente são elevados e podem dificultar a identificação dos melhores modelos pelo usuário. Além disso, a diferença simples de volumes entre modelos pode apresentar valores negativos. 71 V1 V2 ∆V = | V2 - V1 | FIG. 5.3: Diferença de volume entre modelos, sob três perspectivas diferentes. Dessa forma, para garantir valores positivos e normalizados da função objetivo, optou-se por considerar a diferença absoluta percentual de volume com relação à amostra inicial de 72 pontos, ou seja, a função objetivo corresponde ao módulo da diferença de volume entre os modelos, dividido pelo valor do volume do modelo de referência. Assim, para o critério de diferença de volume, a função objetivo assume a forma da EQ. 5.3 . fj = |V’ - V| / V (5.3) sendo V’ é o volume do modelo candidato a solução e V o modelo de referência, correspondente ao volume do modelo original contendo todos os pontos. O critério da diferença de volume garante que os modelos resultantes tenham um valor numérico de volume tão próximo quanto possível do valor de referência do modelo original. Testes preliminares mostraram que o critério de volume força, indiretamente, que os modelos resultantes cubram uma área quase igual à do modelo original, evitando reduções mais drásticas da área coberta pelos pontos escolhidos. Além disso, o fato dos modelos generalizados terem volumes próximos ou iguais ao volume do modelo original pode indicar uma menor alteração no conteúdo informativo, significando que foram retirados dos modelos somente aqueles pontos que pouco interferiam na formação do volume inicial. Entretanto, como desvantagem, o critério da diferença de volume não fixa que o modelos resultantes tenham uma morfologia semelhante ao modelo original, abrindo margem a variações na forma dos modelos generalizados que aparecerão com pequenos detalhes de diferença do modelo original. A FIG 5.4 ilustra a comparação de dois perfis entre um modelo original e outro generalizado, sendo possível perceber a perda de detalhes do terreno neste último. FIG. 5.4: Comparação de perfis de modelos: original (verde) e generalizado (azul). Quanto a isso, é importante observar que a retirada de pontos poderá causar alterações na forma do modelo resultante, envolvendo a perda de alguns detalhes. A determinação da 73 diferença de volume, embora mais abrangente que os pontos de controle, não é um critério ainda completo o suficiente para evitar a retirada de detalhes do modelo. Segundo GOMES (2006) a tarefa de análise qualitativa de modelos geralmente é subjetiva, por se utilizar frequentemente da análise visual da superfície. Essa subjetividade é expressa por uma dependência do sistema com relação a um usuário para identificação da perda de características importantes e na conseqüente alteração de critérios, específicos para cada usuário em particular. O esforço de minimizar a eliminação de detalhes pode passar pela formalização matemática da presença de elementos relacionados à forma do modelo e, respectivamente, ao seu conteúdo informativo. É importante a obtenção de funções ou de propriedades numéricas que descrevam um modelo em seus aspectos principais a fim de se reduzir o caráter subjetivo da comparação de modelos digitais. Outros critérios capazes de retratar essa perda de detalhes na generalização merecem ser avaliados em uma pesquisa à parte. Podem significar a inclusão de outros fatores a serem considerados no momento de se determinar a aptidão de um indivíduo além da diferença numérica de volume pura e simples. 5.1.4 FUNÇÃO APTIDÃO A função aptidão efetua a conversão dos valores obtidos pela função objetivo para uma forma mais simples, geralmente normalizada, com valores compreendidos em uma escala menor (de 0 a 1, por exemplo). Dentro da presente pesquisa, optou-se por considerar o valor da função objetivo normalizada como valor de aptidão para o problema. Essa decisão elimina uma etapa de cálculo das aptidões a partir de valores da função objetivo, resultando em um ganho de tempo ao término de uma iteração. A redução de uma etapa apresenta um peso importante no tempo final de processamento e pode ser explicada considerando-se alguns fatores críticos. Para os dois critérios de determinação da função objetivo há necessidade de interpolação dos dados para a formação dos modelos. Só com os modelos prontos é possível a determinação dos atributos para comparação com pontos de controle e o cálculo do volume para a determinação da diferença de volume com a superfície de referência. O processo de geração de um modelo, dependendo da quantidade de pontos, da estrutura de dados adotada e da técnica de interpolação, pode ser demorado e tornar as iterações bem 74 lentas. Quanto maior o tempo de interpolação de um modelo digital, maior será o tempo de determinação do valor de aptidão e mais lento será o algoritmo. Além disso, existe uma seqüência de rotinas intrínsecas aos algoritmos genéticos que prevê tarefas de formação da população inicial, determinação das aptidões de todos os indivíduos da população, seu ordenamento, seleção, cruzamento e mutação para cada geração diferente. Esses passos, aliados ao tempo gasto para resolução da função objetivo, terminam por tornar cada iteração do algoritmo genético lenta, podendo chegar a horas. A escolha de igualar os valores de aptidão com os valores da função objetivo foi possível pela forma como foi elaborada a função objetivo. Para os dois critérios, pontos de controle e diferença de volume, os valores não podem assumir valores negativos uma vez que são retornados os valores absolutos das diferenças de atributos e de volume, respectivamente. Além disso, para a diferença de volume, a função objetivo retorna valores percentuais inferiores a um, bem semelhantes aos valores atribuídos convencionalmente por uma função aptidão. 5.1.5 OPERADORES DE CRUZAMENTO E DE MUTAÇÃO Em função da codificação binária adotada para o problema, o modelo de cruzamento adotado foi o cruzamento convencional de n pontos que prevê a troca de segmentos da cadeia entre dois indivíduos originais. Foram inseridos dois tipos de cruzamento convencionais com um e dois pontos para o algoritmo proposto. Nesses dois tipos de cruzamento, a escolha dos pontos de corte é feita aleatoriamente pelo algoritmo, sem considerar informações determinísticas ou provenientes de outros indivíduos da população. Como restrições impostas para os pontos de corte selecionados destaca-se a impossibilidade de pertencerem a qualquer uma das extremidades dos cromossomos, no caso dos dois tipos de cruzamento, uma vez que essa situação inviabiliza a quebra da cadeia binária e conseqüente troca de segmentos homólogos. Com relação exclusivamente ao cruzamento de 2 pontos, há a restrição dos dois pontos de corte selecionados não poderem ser coincidentes. O operador de mutação adotado prevê a inversão do valor de um bit na cadeia cromossômica, escolhido aleatoriamente. 75 5.1.6 TÉCNICA DE SELEÇÃO A técnica de seleção adotada para a estruturação do algoritmo foi a seleção por torneio (com n = 3, isto é, com três indivíduos participando de cada disputa). Conforme explicado anteriormente no Capítulo 4, essa técnica de seleção retira aleatoriamente três indivíduos da população para comporem um torneio particular. Aquele que tiver a maior aptidão será o escolhido para compor a população intermediária. A escolha dessa técnica de seleção justifica-se por questões práticas de redução de etapas, uma vez que não necessita do ordenamento dos indivíduos em uma população segundo seu valor de aptidão. Desse modo, a exemplo de se considerar os valores de aptidão iguais aos valores da função objetivo, houve uma redução de etapas com o intuito de tornar o processamento do algoritmo mais rápido. 5.1.7 TÉCNICAS DE SUBSTITUIÇÃO São estratégias adotadas para a inserção de novos indivíduos na formação de novas populações. Para a estruturação do sistema de generalização de modelos foram consideradas as técnicas de substituição geracional e steady state. No algoritmo proposto, para ambas as técnicas há a formação de uma população intermediária que abriga os melhores indivíduos selecionados e que participarão de cruzamento para a geração da nova população. A escolha de uma população intermediária formada por indivíduos selecionados e não por indivíduos cruzados foi feita com o objetivo de se reduzir a chance dos indivíduos menos aptos de participarem da etapa de cruzamento. Para a formação dessa população intermediária há um controle para não efetuar a seleção do mesmo indivíduo mais de uma vez. Outra observação importante cabe à restrição do tamanho da população intermediária ser metade do tamanho da população original. Como somente os melhores indivíduos selecionados comporão a população intermediária e não podem ser selecionados mais que 50% dos indivíduos de uma população para compor a população intermediária, há uma redução ainda maior das chances de seleção de indivíduos com baixa aptidão. Uma vez na população intermediária, os indivíduos serão selecionados aleatoriamente dois a dois para a etapa seguinte de cruzamento, podendo ou não gerar seus descendentes, 76 conforme a taxa de cruzamento adotada. Após a seleção do par de cromossomos que passará por recombinação, a geração de um número aleatório compreendido entre 0 e 1 determina a ocorrência do cruzamento. Se esse número for maior que a taxa de cruzamento, não haverá recombinação; caso contrário, são realizadas as trocas de segmentos. Na etapa de cruzamento um mesmo indivíduo pode ser selecionado para mais de um cruzamento. Durante a etapa de cruzamento os filhos são inseridos em uma nova população, iniciando uma nova população. 5.1.7.1 GERACIONAL A substituição geracional prevê a substituição de todos os indivíduos a cada geração. Eventualmente, em função da taxa de cruzamento, pode ocorrer de dois indivíduos selecionados não passarem por recombinação e retornarem à população. Baixas taxas de cruzamento favorecem ocorrências desse tipo. Como variante da técnica de substituição geracional, o usuário pode optar pelo recurso de elitismo. Esse mecanismo mantém o melhor indivíduo observado na população impedindo a sua substituição por um descendente menos apto. Para essa situação, somente um (1) indivíduo pode ser preservado a título de elitismo como forma de redução do risco de convergência prematura. 5.1.7.2 STEADY STATE Dentro do objetivo de generalização de modelos, foi utilizada uma versão geral da substituição steady state, onde os N piores indivíduos são substituídos pelos N filhos gerados por cruzamento. Para cada substituição realizada, é forçada a inserção de um novo indivíduo proveniente de recombinação. Essa restrição adotada equivale a considerar a taxa de cruzamento igual a 100%. Isso implica em um maior índice de cruzamento, uma vez que, para cada geração, obrigatoriamente um número específico de indivíduos deve ser substituído por novos indivíduos gerados por recombinação. Caso não houvesse essa obrigatoriedade de inserção de novos indivíduos, e a recombinação dependesse da taxa de cruzamento, a substituição steady state correria o risco de ser menos efetiva que a substituição geracional, uma vez que o espaço de ocorrência de 77 cruzamento aberto na substituição steady state (N indivíduos na forma geral) é menor que o total de indivíduos, enquanto que, na geracional, toda a população pode ser substituída por novos indivíduos. Para o caso da substituição steady state, a taxa de cruzamento foi aplicada exclusivamente como fator para determinar o número de indivíduos que deveriam ser substituídos a cada nova geração. Por exemplo, caso a taxa de cruzamento seja de 60%, o número de novos indivíduos inseridos em uma população de 20 indivíduos será de 12. 5.1.8 CRITÉRIO DE PARADA Abrange os elementos utilizados para finalizar cada iteração. Os critérios adotados foram o de convergência populacional e número de gerações. Por convergência populacional entende-se a formação de populações com indivíduos de mesma aptidão. Apesar do grande número de combinações possíveis para cada cromossomo, ao longo dos ciclos evolutivos é possível que alguns indivíduos destaquem-se dos demais em termos de aptidão e terminem gerando uma quantidade maior de descendentes. Após um dado número de gerações é possível que um percentual de indivíduos na população tenha o mesmo valor de aptidão. Nesse estágio, caso o número de indivíduos seja maior ou igual a um percentual definido pelo usuário, o processo será interrompido. Esse percentual limite de indivíduos semelhantes definido pelo usuário, aqui denominado de percentual de convergência, é estabelecido no início de cada iteração, caso o critério de parada seja a convergência populacional. O critério de convergência populacional permite a evolução dos indivíduos até que boa parte dos indivíduos seja semelhante. Como ponto negativo, esse critério não considera o valor final de aptidão dos indivíduos, vindo a finalizar o processamento mesmo que os indivíduos não tenham evoluído o suficiente. Além disso, o algoritmo pode permanecer em operação mesmo após a geração de respostas com uma aptidão limite. Isso ocorre com a função objetivo determinada pela diferença de volume, quando encontram-se modelos generalizados com diferença percentual de volume praticamente nula com relação ao modelo de referência, mas há uma continuidade nos ciclos enquanto o número de indivíduos de mesma aptidão estiver abaixo do percentual de convergência. O outro critério de parada adotado foi o número fixo de gerações. A escolha desse critério pode ser feita quando o usuário tiver a intenção de formar uma população a partir de 78 indivíduos obtidos como solução por iterações de poucos ciclos. Essa população poderá ser então usada como população inicial em um outro processo mais longo (seeding). A restrição do número de gerações pode ser escolhida também caso haja conhecimento prévio do comportamento do algoritmo de generalização em uma amostra de dados, a ponto de saber um número aproximado de gerações para a obtenção do grau de generalização desejado. Essa técnica pode significar uma grande redução de tempo de processamento final. 5.2 PARÂMETROS DO ALGORITMO GENÉTICO Parâmetros do algoritmo genético são os valores ou configurações adotados em cada iteração e que podem interferir em aspectos importantes do processo de generalização, tais como percentual final de generalização e tempo total gasto na iteração. Definida a codificação do problema de generalização de modelos digitais a partir de algoritmos genéticos, foi iniciada uma segunda etapa que consistiu na implementação de um sistema de generalização de modelos. Para a construção do programa foram aproveitadas ferramentas de geração de modelos digitais disponibilizadas no software ArcView 9.2, disponível no departamento de cartografia do IME na versão acadêmica. Esse software disponibiliza um módulo denominado ArcObjects que abriga todas as classes de objetos relacionados às rotinas de manipulação de arquivos e geração de modelos disponíveis no ArcView e que podem ser acessadas por códigos elaborados em VBA (do inglês: Visual Basic for Applications). Para o usuário interessado nessas rotinas e em conhecer mais sobre programação em VBA utilizando ArcObjects, KANG (2008) fornece bons exemplos de algoritmos em VBA. O portal ArcScripts, da ESRI, (http://arcscripts.esri.com/) constitui também uma interessante fonte de códigos e rotinas implementadas para ArcGis. A seguir, são ilustradas as principais características dos parâmetros existentes no algoritmo implementado e que devem, posteriormente, ser alvo de testes. 79 5.2.1 TAMANHO DA POPULAÇÃO Para a estruturação do algoritmo de generalização as populações que participam da evolução apresentam um tamanho fixo e igual ao tamanho da população inicial. Cada indivíduo separado na população é tratado como uma possível solução para o problema. Em função da codificação binária adotada e das cadeias cromossômicas extensas, há a necessidade de se restringir o número de indivíduos para a população sob pena de se aumentar muito o tempo de processamento. 5.2.2 FUNÇÃO OBJETIVO A função objetivo adotada pode utilizar informações de pontos de controle ou de diferença de volume para uma superfície de referência para avaliar os modelos gerados em uma iteração. Os dois critérios de determinação da aptidão podem apresentar diferentes resultados em termos de generalização de modelos, tanto com relação ao percentual de redução de pontos quanto à qualidade dos modelos resultantes. Dessa forma, é necessária a realização de alguns testes para efeito de comparação e de adoção de um dos critérios. 5.2.3 TIPO DE CRUZAMENTO O usuário pode selecionar um dos dois tipos de cruzamento (de 1 e de 2 pontos). Cada um dos dois tipos influencia na geração de novos indivíduos e na velocidade de convergência do algoritmo. 5.2.4 TÉCNICA DE SUBSTITUIÇÃO DE INDIVÍDUOS É possível definir se a substituição será geracional, geracional com elitismo ou steady state. As duas primeiras, por suas características podem resultar em iterações com um maior 80 número de gerações enquanto última pode apresentar uma velocidade de convergência maior por efetuar a troca dos piores indivíduos. 5.2.5 TAXA DE CRUZAMENTO Refere-se à definição da probabilidade dos indivíduos selecionados passarem por uma recombinação. Altas taxas de cruzamento podem aumentar a velocidade de convergência, mas aumentam também o risco de convergência prematura. Quanto à taxa de cruzamento, DE JONG (1975) defende que taxas elevadas (100%) podem levar à alteração brusca de indivíduos de alta aptidão, ou seja, candidatos à solução, enquanto taxas abaixo de 40% reduzem a busca de novas soluções, fato que aliado à perda de variabilidade da população pode levar a convergências com valores abaixo de um patamar mínimo de qualidade. Dentro do algoritmo proposto, a definição da taxa de cruzamento é feita de maneira estática pelo usuário e permanece a mesma durante todas as gerações. 5.2.6 TAXA DE MUTAÇÃO Refere-se à definição da probabilidade dos indivíduos selecionados passarem por uma mutação. Controla o surgimento de novas características na população mas implica no risco de geração de indivíduos infactíveis. Normalmente, nos algoritmos genéticos a taxa de mutação é bem inferior à taxa de cruzamento, estando situada em valores próximos a 1%. Para DE JONG (1975), na natureza a probabilidade de um gene sofrer mutação é menor que 0,1% , indicando que esse não é o principal operador genético, servindo, contudo, como um mecanismo de garantia do não desaparecimento de determinados alelos em uma população. Uma forma simples de determinar a taxa de mutação é proposta pelo mesmo autor, sendo obtida pelo inverso do número de indivíduos da população. Conforme o autor, taxas maiores que essa geralmente podem resultar em perda de qualidade final. Para o algoritmo elaborado, a definição da taxa de mutação é feita de maneira estática pelo usuário e permanece a mesma durante todas as gerações. 81 5.2.7 PERCENTUAL DE CONVERGÊNCIA Esse limite irá determinar o fim de uma iteração. Percentuais pequenos de convergência podem finalizar o algoritmo antes de se atingir uma solução satisfatória, ao passo que percentuais elevados podem prolongar desnecessariamente o processo evolutivo sem efetuar uma melhora significativa das soluções. A definição do percentual mais apropriado exige conhecimento do comportamento do algoritmo de generalização para uma amostra de dados específica, caso esse seja um valor sensível para cada conjunto de dados, ou para diferentes amostras de dados, caso possa ser adotado um único valor geral. 5.3 PARÂMETROS DE GERAÇÃO DO MODELO 5.3.1 INTERPOLADORES O usuário pode optar entre as estruturas de dados de grade regular, com o interpolador estatístico krigagem, e a Malha Triangular Irregular (TIN). Interpoladores / estruturas de dados diferentes geram modelos em tempos distintos, interferindo significativamente no tempo total de processamento. A definição do interpolador e da estrutura de dados pode também interferir no percentual final de generalização. 5.3.2 RESOLUÇÃO DO MODELO Esse parâmetro é aplicável somente para a estrutura de dados retangular regular e interfere no número de linhas e de colunas que o modelo resultante terá. Influi notadamente no tempo final de processamento dos modelos. Para os casos estudados não serão considerados os efeitos da variação da resolução dos modelos, devendo ser adotada uma única resolução padrão que não resulte em modelos muito pesados e de processamento demorado. 82 5.4 SELEÇÃO DOS PARÂMETROS Com relação ao objetivo generalização de modelos digitais, um primeiro ponto a ser observado diz respeito ao grande número de opções que podem ser escolhidas para a generalização, conforme o método proposto na presente pesquisa. A origem dessa gama de opções está relacionada à escolha dos parâmetros do algoritmo genético implementado e na geração dos modelos digitais de terreno, os dois núcleos relacionados à pesquisa. Portanto, para a execução dos testes, existem diferentes configurações possíveis para a definição dos parâmetros do algoritmo genético bem como dos parâmetros relacionados à geração dos modelos digitais de terreno, conforme apresentado nas seções 5.2 e 5.3, resumidos na TAB. 5.1. Dentre os parâmetros relacionados à geração do modelo digital, será considerada e analisada somente a escolha do interpolador e sua possível influência na generalização de modelos. TAB. 5.1: Parâmetros envolvidos na generalização de modelos. PARÂMETRO VALORES Tamanho da População Inteiros Positivos Função Objetivo Pontos de Controle Volume Tipo de Cruzamento 1 Ponto 2 Pontos Técnica de Substituição de Geracional Indivíduos Geracional com Elitismo Steady State Taxa de Cruzamento 0 ≤ tc ≤ 1 Taxa de Mutação 0 ≤ tm ≤ 1 Percentual de Convergência 0 < pc ≤ 1 Interpolador Krigagem Malha Triangular Irregular 83 No universo dos parâmetros considerados existem alguns que apresentam valores discretos, abrangendo duas ou três opções, como a escolha da função objetivo, do tipo de cruzamento e da técnica de substituição. Outros, como tamanho da população e a configuração das taxas de mutação e de cruzamento, apresentam valores em um intervalo numérico e admitem um número maior de opções. As configurações que admitem variações em todos os parâmetros são inúmeras e difíceis de serem analisadas em paralelo. O ideal, portanto, é a redução no número de possibilidades para a realização de testes e definição paulatina dos parâmetros que garantam um melhor rendimento do algoritmo. A comparação dos parâmetros exige então a definição prévia de valores para alguns e variação de outros para o estudo de sua influência no comportamento do algoritmo genético. À medida que o conhecimento acerca de alguns parâmetros for sendo ampliado, é possível definir as melhores opções e então estudar a variação de outros parâmetros. Seguindo esse método, para os testes realizados são arbitrados os valores do tamanho da população, das taxas de cruzamento e de mutação e do percentual de convergência. As combinações efetuadas dizem respeitos somente ao interpolador adotado para a geração dos modelos (duas opções), ao tipo de cruzamento (duas opções), à função objetivo (duas opções) e às técnicas de substituição de indivíduos (três opções). Nesse caso, com a fixação de valores para os parâmetros numéricos, inicialmente restarão 24 combinações possíveis de serem exploradas, apresentadas na FIG. 5.5 . Geracional TIN Krigagem Pontos de Controle Volume CrossOver 1 Ponto CrossOver 2 Pontos Geracional c Elitismo Testes FIG. 5.5: Combinações possíveis de parâmetros. 84 Steady State Os valores arbitrados de tamanho da população, taxa de cruzamento, taxa de mutação e percentual de convergência são ilustrados na TAB. 5.2. Uma vez definidos o interpolador a ser adotado, o critério de aptidão, o tipo de cruzamento e a técnica de substituição de indivíduos, será possível realizar os demais testes previstos no objetivo da pesquisa. TAB. 5.2: Valores a priori do tamanho da população, taxas de cruzamento e mutação e de percentual de convergência. Tamanho da População 20 Taxa de Cruzamento 50% Taxa de Mutação 1% Percentual de Convergência 75% 85 6 DESCRIÇÃO DOS EXPERIMENTOS Para a realização dos testes de generalização de modelos digitais, um ponto importante é a definição de amostras de dados que servirão de base para os modelos estudados. As amostras escolhidas para a realização dos testes são de modelos digitais de terreno, que têm a altimetria como atributo chave. Apesar das amostras escolhidas serem de modelos digitais de terreno, a pesquisa visa abranger a prática de generalização para modelos digitais de superfície de uma forma geral, a ponto dos testes realizados aqui poderem ser repetidos para cojuntos de dados que modelem fenômenos variados. 6.1 CARACTERÍSTICAS DAS AMOSTRAS Foram escolhidas para a realização dos testes iniciais de generalização 3 amostras de pontos. A primeira amostra de pontos utilizada (amostra 1) contém 516 pontos e foi elaborada em laboratório pela Universidade Federal do Rio de Janeiro. A FIG. 6.1. ilustra a distribuição de pontos da amostra 1 e um modelo gerado a partir desta. Uma característica importante da amostra relaciona-se à variação brusca de altitude em alguns pontos vizinhos, apresentando regiões de grande declividade. Além disso, também apresenta uma distribuição de pontos bem heterogênea, com certas áreas apresentando grande densidade de pontos e outras áreas sem apresentar pontos. FIG. 6.1: Amostra de pontos 1. 86 O segundo conjunto de pontos (amostra 2) utilizado foi desenvolvido no laboratório de cartografia da Seção de Engenharia Cartográfica do Instituto Militar de Engenharia, a partir de pontos amostra 1. Essa amostra possui 510 pontos e apresenta uma menor variação de altitude entre os pontos e uma distribuição mais homogênea em comparação à primeira amostra, conforme ilustrado na FIG 6.2 . FIG. 6.2: Amostra de pontos 2. O terceiro conjunto de pontos (amostra 3) utilizado nos testes também foi elaborado no laboratório de cartografia do IME, em conjunto com a amostra 2. Foi desenvolvido a partir do desenho de curvas de nível, de altitudes definidas arbitrariamente, a partir da imagem de um vulcão. Essa amostra possui 1394 pontos e apresenta uma única elevação principal. Os pontos também são distribuídos por toda a região e sua densidade aumenta com a proximidade da cratera central (FIG. 6.3). FIG. 6.3: Amostra de pontos 3. 87 As amostras adotadas apresentam número de pontos diferentes bem como diferentes tipos de distribuição de pontos e de relevo. As diferenças entre as amostras são importantes para a verificação de uma possível dependência da generalização de modelos com relação ao tipo de terreno e às características da amostra. 6.2 ESTRUTURA DOS TESTES A partir do exposto no item 5.4 do Capítulo 5, foram fixados os valores de tamanho da população, taxa de cruzamento e de mutação e percentual de convergência para a comparação dos tipos de cruzamento, das técnicas de substituição populacional e dos critérios de aptidão. Para cada interpolador foram realizados testes envolvendo os dois critérios de aptidão disponíveis, pontos de controle e volume. Para cada um destes critérios, foram testados os dois tipos de cruzamento e, para cada uma destas, foram testadas as três variações de substituição populacional. Essas 12 combinações foram testadas para cada um dos dois interpoladores, totalizando 24 configurações diferentes. Para cada configuração foram realizados cinco testes e determinados os valores médios das iterações. Dessa forma, para a definição dos parâmetros de critério de aptidão, técnica de substituição e tipo de cruzamento foram realizados 120 testes com as 24 combinações por conjunto de dados. Para a realização desses testes foram utilizadas as amostras 1 e 2. Os fatores observados e que podem servir para a definição das melhores combinações, não necessariamente em ordem, são: 1- Percentual de generalização alcançado. 2- Aptidão da solução. 3- Geração de formação da solução. 4- Número de gerações. Dessa forma, por exemplo, as configurações que apresentarem um melhor desempenho em uma maior quantidade de fatores poderão ser escolhidas. Um segundo grupo de testes foi voltado para a investigação dos principais parâmetros de influência no percentual final de generalização do algoritmo, envolvendo também as amostras de dados 1 e 2. O último conjunto de testes foi o de investigação da qualidade dos modelos, aqui denominado de generalização sucessiva, que foi efetuado sobre as três amostras de dados consideradas. 88 6.3 INFLUÊNCIA DA PRECISÃO NUMÉRICA A quantidade de casas decimais também surge como um fator de grande influência no algoritmo de generalização. Por isso, antes de se iniciar a seqüência de testes planejada, foi necessário realizar alguns testes adicionais para o estudo da influência das casas decimais no algoritmo de generalização. A seleção de indivíduos, por meio da comparação de seus respectivos valores de aptidão, mostrou-se, pelos testes realizados ser bem sensível à quantidade de casas decimais consideradas. Para estudar a influência da precisão numérica foram realizados testes similares com uma mesma amostra de dados envolvendo as precisões de três e de doze casas decimais. Para esse caso, foi escolhido como único interpolador a ser aplicado nos testes a krigagem. Considerando inicialmente a aptidão calculada por pontos de controle, percebe-se uma queda no número médio de gerações para a ocorrência de convergência. Também houve uma redução na média de gerações para se chegar às soluções. Os valores de aptidão passaram por uma pequena melhoria para os testes com três casas decimais e o percentual médio de generalização da amostra de dados permaneceu estável em torno dos 50% (FIG 6.4). Aptidão por Pontos de Controle 120,00 100,00 80,00 60,00 40,00 20,00 0,00 111,59 110,63 50,08 14 Melhor Aptidão : 25 9 Geração da Solução: 12 Casas Decimais 50,26 12 Nº de Gerações: Generalização 3 Casas Decimais FIG. 6.4: Influência da precisão da aptidão por pontos de controle. De forma semelhante, para a determinação da aptidão por diferença de volume, houve uma redução na média de gerações para a geração da solução e para a ocorrência de convergência. A aptidão (diferença percentual de volume) e percentual médio de generalização permaneceram com valores bem próximos para as duas configurações (FIG 6.5). 89 Aptidão por Diferença de Volume 60,00 50,00 40,00 30,00 20,00 10,00 0,00 48,97 49,52 22 13 1,42 1,82 Melhor Aptidão : 12 7 Geração da Solução: 12 Casas Decimais Nº de Gerações: Generalização 3 Casas Decimais FIG. 6.5: Influência da precisão da aptidão por diferença de volume. Para ambos os critérios de aptidão, o principal efeito da redução de casas decimais foi a diminuição da média de gerações para o surgimento da solução e para se atingir a convergência da população. No caso da aptidão calculada a partir de pontos de controle, houve cerca de 5 gerações na média de geração da solução e de 13 gerações para a média de gerações. Para a aptidão determinada por diferença de volume, a queda foi de 6 gerações na média de geração da solução e de 10 gerações na média de gerações. A queda do número de gerações para convergência em função da redução de casas decimais está relacionada principalmente à redução do número de cruzamentos. Esse operador genético promove a recombinação das informações contidas entre dois indivíduos, contribuindo para o surgimento de indivíduos com novas características e para o aumento da variabilidade. Desse modo, com as aptidões dos indivíduos sendo distintas por três e não por doze casas decimais, será mais adequada a formação de indivíduos com mesmo valor de aptidão, havendo redução da quantidade de cruzamentos para a geração de indivíduos semelhantes. A queda da média de gerações e a manutenção do percentual de generalização em valores próximos a 50%, para a amostra testada, demonstram que a redução para três casas decimais é viável para a diminuição no tempo de processamento das iterações, sem risco de comprometer a eficiência do algoritmo. 6.4 TESTES DE CONFIGURAÇÃO DOS PARÂMETROS São testes que visam verificar a influência da configuração de parâmetros na tarefa de generalização de modelos. Sabe-se que diferentes combinações têm o efeito de alterar a 90 velocidade do processo e de gerar amostras resultantes com diferentes níveis de generalização. A definição de configurações mais eficientes é importante para uma segunda etapa dos testes, voltada para a identificação do potencial e eficiência de generalização do algoritmo. Os testes de configuração dos parâmetros do algoritmo foram realizados somente para as amostras 1 e 2. 6.4.1 ANÁLISE DOS CRITÉRIOS DE APTIDÃO A análise dos critérios de aptidão levantados deve ser feita considerando os valores médios de percentual de generalização, de número de gerações e de geração da solução. Em suma, esses valores indicam a influência de uma configuração na quantidade de pontos retirados da amostra bem como permite a identificação daquelas configurações que apresentam uma convergência mais rápida. As figuras 6.6 e 6.7 ilustram, para a amostra 1 e para a amostra 2, respectivamente; valores médios de geração da solução, de número de gerações e de percentual de generalização para iterações baseadas em pontos de controle e em volume como critérios de aptidão. Essas três medidas foram feitas para a malha triangular irregular e para a grade regular interpolada por krigagem. Esses valores basearam-se em médias de iterações, observando somente a diferença de estrutura de dados para a elaboração dos modelos. Dessa forma, quando se apresentam valores médios de número de gerações para pontos de controle, por exemplo, consideram-se os resultados obtidos por diferentes tipos de cruzamento e diferentes técnicas de substituição. 60 49,86 49,34 50,26 49,52 50 40 30 20 10 10 6 9 13 7 11 12 12 0 Geração da Solução Pontos de Controle TIN Nº Gerações Volume TIN Pontos Descartados (%) Pontos de Controle Krg FIG. 6.6: Comparação dos critérios de aptidão para a amostra 1. 91 Volume Krg 60 48,31 49,67 48,80 50,19 50 40 30 20 20 10 9 10 10 9 23 23 12 0 Geração da Solução Pontos de Controle TIN Nº Gerações Volume TIN Pontos Descartados (%) Pontos de Controle Krg Volume Krg FIG. 6.7: Comparação dos critérios de aptidão para a amostra 2. De acordo com a FIG. 6.6, para a amostra 1, considerando a malha triangular irregular, iterações baseadas em pontos de controle apresentaram médias maiores de geração da solução e de número de gerações, em 4 e em 2 gerações, respectivamente, maiores que as médias baseadas em cálculo de volume. A técnica de pontos de controle apresentou um maior percentual de generalização, 49,86% contra 49,34% da técnica de cálculo do volume, uma diferença de 0,52%. Considerando a malha regular interpolada por krigagem, as iterações baseadas em pontos de controle apresentaram médias maiores de geração da solução, em 2 gerações, e mantiveram o mesmo número médio de gerações que as iterações baseadas em cálculo do volume. Para o interpolador krigagem, a aptidão determinada a partir de pontos de controle apresentou uma média de generalização de 50,26% contra 49,52% para a aptidão determinada por diferença de volume (diferença de 0,74%). Por outro lado, para a amostra 2, considerando a TIN, a aptidão determinada por volume apresenta um número médio de gerações maior que a média gerada por pontos de controle e também um maior percentual de generalização médio (cerca de 1.36%). Para a grade regular, a aptidão por volume apresenta uma média de gerações aproximadamente igual à gerada por pontos de controle e um percentual de generalização ligeiramente maior (cerca de 1,39%). A partir do comportamento observado nas duas amostras, percebe-se que para a amostra 1 o critério de volume apresenta médias menores de geração da solução, de número de gerações e um percentual de convergência ligeiramente menor, enquanto para a amostra 2 a aptidão por pontos de controle passa a ter as menores médias dos três parâmetros analisados. A TIN combinada com uma aptidão determinada por pontos de controle apresentou resultados com comportamento mais estável para as duas amostras de dados, permanecendo 92 com valores semelhantes de média de geração da solução, de número de gerações e de percentual de generalização. Para a maioria dos casos, o critério de aptidão por diferença de volume tende a apresentar médias menores de geração da solução e de número de gerações, ao passo que a aptidão determinada por pontos de controle apresenta maiores valores de generalização. Dentro do objetivo de generalização de modelos proposto no presente trabalho, o percentual de generalização assume um maior peso que o fator velocidade do algoritmo para a obtenção de soluções. Entretanto, ressalta-se que o aumento médio de gerações ocasionado pelo uso de pontos de controle é bem mais significativo que o aumento do percentual de generalização (inferior a 1,5% nos dois casos analisados). É importante considerar que uma boa qualidade da generalização dos dados também é um objetivo importante a ser alcançado e que deve ser devidamente considerado na identificação das melhores soluções. Isso significa que percentuais elevados de generalização não estão relacionados necessariamente a modelos bem generalizados. Desse modo, a disposição final dos pontos nos modelos generalizados pode servir como um critério auxiliar para a definição do modelo de aptidão. Uma explicação para a tendência da maior generalização com o uso dos pontos de controle está na seleção de pontos do modelo mais próximos aos pontos de controle. A FIG. 6.8 ilustra essa tendência comparando os pontos originais e os pontos selecionados com os pontos de controle. FIG. 6.8: Seleção de pontos: amostra original (à esquerda) e amostra generalizada (à direita). 93 Outro fator importante a ser considerado diz respeito à escolha da amostra de pontos de controle a ser adotada. Diferentes configurações de pontos de controle podem conduzir a diferentes resultados de generalização. Dessa forma, ao se realizar a generalização de modelos digitais tendo a aptidão determinada por pontos de controle, deveriam ser consideradas algumas questões adicionais como quantidade e espaçamento dos pontos de controle, por exemplo. Seja por apresentar médias menores de número de gerações, mantendo aproximadamente constante o percentual de generalização médio, seja por não apresentar a necessidade de definição de uma amostra de pontos auxiliar, ou por não apresentar um risco tão alto de seleção de pontos em torno de pontos específicos, o emprego de volume como critério de aptidão mostra-se uma melhor opção que o uso puro de pontos de controle, segundo o método de determinação da aptidão adotado na presente pesquisa. Mesmo incorrendo em uma queda na média de percentual de generalização resultante da adoção desse critério, é importante ressaltar que a mesma não mostrou-se significativa, ficando, para os casos analisados, inferior a 1,5%. Esse percentual em uma amostra de 2000 pontos, por exemplo, significa a presença de aproximadamente 30 pontos a mais no modelo resultante, não sendo significativo a ponto de alterar fatores como o tempo de processamento e demanda de armazenamento. O uso de pontos de controle como critério de aptidão deve ser analisado com maior cuidado que o dispensado na presente pesquisa, a ponto de não se descartar de todo essa técnica. Para se garantir bons níveis de generalização com o emprego de pontos de controle é importante definir um número adequado e bem distribuído de pontos a ser adotado como referência. Contudo, esses dois atributos não são fáceis de identificar a priori, exigindo uma pesquisa auxiliar mais rigorosa. Talvez o uso conjugado de pontos de controle, localizados estrategicamente em regiões sensíveis, com informações de volume possa se mostrar, no futuro, um critério mais completo de aptidão. Essas são questões importantes que não dizem respeito diretamente ao escopo da presente pesquisa e que, por ora, ficarão como uma sugestão para trabalhos futuros. 6.4.2 ANÁLISE DOS TIPOS DE CRUZAMENTO Uma vez definido o critério para cálculo da aptidão, a próxima análise deve ser baseada nos operadores genéticos que apresentam um melhor desempenho na prática de generalização. 94 Para a definição do tipo de cruzamento, existem somente duas opções (cruzamento de 1 ponto e cruzamento de 2 pontos), que foram comparadas para a geração de modelos com o uso de estruturas de dados distintas. O gráfico apresentado na FIG. 6.9 resume testes de generalização envolvendo as duas estruturas de dados testadas, com o critério de aptidão baseado em volume. Independentemente da estrutura de dados adotada, o percentual de generalização mantém-se próximo de 50% quando comparados os dois tipos de cruzamento, com o cruzamento de 1 ponto apresentando um percentual pouco superior ao cruzamento de 2 pontos. Esse resultado análogo não se mantém, entretanto, quando se considera o número de gerações, fator no qual o cruzamento de 1 ponto apresenta uma menor média de gerações para a geração da solução e necessita de menos gerações para convergir em comparação ao cruzamento de 2 pontos. 60 50,4 50 48,29 49,61 49,43 40 30 20 10 5 7 6 9 10 13 11 13 0 Geração da Solução 1 Ponto_TIN Nº Gerações 2 Pontos_TIN Pontos Descartados (%) 1 Ponto_Krg 2 Pontos_Krg FIG. 6.9: Comparação dos tipos de cruzamento na amostra 1. Esse comportamento sofre alteração quando considerados os testes da amostra 2. Nessa nova situação, o cruzamento de 2 pontos apresenta médias menores para geração da solução e de número de gerações para a TIN e um menor número médio de gerações para krigagem, conforme ilustra a FIG. 6.10 . O percentual de generalização mantém-se próximo de 50%. Para as amostras 1 e 2 os dois tipos de cruzamento apresentaram variação de comportamento para os parâmetros analisados, com o cruzamento de 1 ponto apresentando melhores resultados para a amostra 1 e sendo superado pelo cruzamento de 2 pontos para a amostra 2. Como exceção, o percentual de generalização permaneceu com valores médios próximos de 50% para os dois tipos de cruzamento, tanto para a amostra 1 quanto para a amostra 2. Esse fato não deixa de ser relevante uma vez que indica que a escolha do tipo de cruzamento não altera significativamente a quantidade de pontos retirados de uma amostra e o 95 risco que se corre ao escolher um ou outro está limitado ao número de gerações de uma iteração. 60 50,44 51,92 50,27 50 48,12 40 30 19 20 12 10 24 24 10 9 21 11 0 Geração da Solução 1 Ponto_TIN Nº Gerações 2 Pontos_TIN Pontos Descartados (%) 1 Ponto_Krg 2 Pontos_Krg FIG. 6.10: Comparação dos tipos de cruzamento na amostra 2. Para realizar tomar uma decisão tecnicamente apropriada entre os dois tipos de cruzamento é importante considerar um outro parâmetro. Como as duas técnicas de cruzamento apresentaram resultados próximos de generalização, o novo parâmetro deve estar relacionado à capacidade específica de cada uma delas de aperfeiçoar soluções de uma população no menor intervalo de tempo. Esse fator pode estar relacionado ao avanço da média de aptidões para cada geração. Não é necessariamente o mesmo que número de gerações, uma vez que este fator está relacionado somente à rapidez, ao tempo gasto por uma iteração e não ao avanço das aptidões ou da qualidade média dos indivíduos com o tempo. Essas informações de média foram levantadas somente para a amostra 2, a partir dos testes realizados para as configurações testadas, tendo a aptidão determinada a partir do volume. As configurações avaliadas estão com as mesmas taxas de cruzamento e de mutação e com populações de mesmo tamanho. Há somente a variação dos tipos de cruzamento e das técnicas de substituição da população. A FIG. 6.11 indica um gráfico da aptidão média por geração para os dois tipos de cruzamento analisados para a substituição de indivíduos geracional. O ideal de uma configuração é que a aptidão média chegue próxima do valor da solução o mais rápido possível, ou seja, que a curva da aptidão média aproxime-se dos menores valores de aptidão em um menor número de gerações. Conforme esse critério, o cruzamento de 1 ponto apresenta uma melhor evolução da aptidão média, uma vez que sua curva no gráfico mostra uma diminuição mais acentuada que o cruzamento de 2 pontos até a sétima geração. 96 Geracional 0,03 0,02 Aptidão 0,01 0 -0,01 1 3 5 7 9 11 13 15 17 19 21 Nº Geração Crsv_1Ponto Crsv_2Pontos FIG. 6.11: Aptidão média por geração para a substituição geracional. Uma aptidão média próxima dos valores mínimos não significa necessariamente uma redução da variabilidade dos indivíduos de uma população. É somente um indicador do quão próximos estão os indivíduos de uma população com relação à solução. É isso o que acontece, por exemplo, com o teste envolvendo o cruzamento de 1 ponto na FIG 6.11, que mesmo apresentando uma aptidão média mais baixa inicialmente, apresentou 22 gerações enquanto o teste realizado com o cruzamento de 2 pontos convergiu com 17. Um outro fenômeno interessante relacionado à aptidão média está relacionado à possibilidade de perda de qualidade da população. Pode ser que entre uma geração e outra, os indivíduos resultantes dos cruzamentos tenham sofrido uma involução, ou seja, apresentem piores aptidões. Esse fato é expresso por inflexões na curva do gráfico de aptidão média, conforme ilustrado na FIG. 6.12 . O gráfico em questão apresenta a curva do teste realizado com o cruzamento de 2 pontos com pontos de inflexão no gráfico nas gerações 3, 5, 11 e 16, com as gerações 4, 6, 12 e 17, respectivamente, apresentando médias piores. Em vista do exposto, o ideal para um tipo de cruzamento é que o gráfico da aptidão média aproxime-se rapidamente de um comportamento assintótico e, ao mesmo tempo, não apresente muitas sinuosidades. Dentre os testes examinados, a maioria dos testes baseados no cruzamento de 1 ponto originou gráficos de aptidão média que mais se aproximaram do comportamento do esperado. Somente em uma configuração, para a substituição geracional na malha triangular irregular, o cruzamento de 1 ponto apresentou pontos de sinuosidade e rendimento inferior ao cruzamento de 2 pontos. 97 Geracional c Elitismo 0,03 0,02 Aptidão 0,01 0 -0,01 1 3 5 7 9 11 13 15 17 19 Nº Geração Crsv_1Ponto Crsv_2Pontos FIG. 6.12: Aptidão média por geração para a substituição geracional com elitismo. 6.4.3 ANÁLISE DAS TÉCNICAS DE SUBSTITUIÇÃO DA POPULAÇÃO A comparação das técnicas de substituição populacional segue os mesmos moldes adotados para a comparação das técnicas de cruzamento, ou seja, são analisadas as técnicas de interesse com relação a testes realizados para a aptidão determinada a partir do volume, variando o tipo de cruzamento e a estrutura de dados dos modelos. A FIG. 6.13 ilustra o desempenho das técnicas de substituição de população para modelos representados por grades retangulares regulares, interpoladas por krigagem. Para essa configuração, a substituição geracional e a steady state apresentaram melhores resultados considerando o número médio de gerações além de uma menor média para a geração da solução. As três técnicas apresentaram percentuais de generalização próximos a 50%. 60,00 50,3949,7348,45 50,00 40,00 30,00 20,00 10,00 7 1,96 1,96 1,54 10 11 12 12 6 0,00 Aptidão Geracional Geração da Solução Nº Gerações Geracional c Elitismo Pontos Descartados (%) Steady State FIG. 6.13: Comparação das técnicas de substituição para malha regular interpolada por Krigagem para a amostra 1. 98 Os mesmos testes realizados na amostra 2, ilustrados na FIG. 6.14, também resultaram na substituição steady state apresentando menores médias de geração da solução e de número de gerações, com diferenças ainda maiores com relação às duas outras técnicas. De forma semelhante aos testes realizados para a amostra 1, todos os percentuais permaneceram próximos a 50% . 60,00 49,8648,5349,20 50,00 40,00 28 30,00 20,00 14 26 14 11 10,00 5 0,01 0,01 0,01 0,00 Aptidão Geração da Solução Geracional Nº Gerações Geracional c Elitismo Pontos Descartados (%) Steady State FIG. 6.14: Comparação das técnicas de substituição para malha regular interpolada por Krigagem para a amostra 2. As figuras 6.15 e 6.16 ilustram os testes com modelos gerados por TIN a partir das amostras 1 e 2, respectivamente. Os menores valores de média de geração da solução e de número de gerações ficaram com a substituição steady state para a amostra 2 e permaneceram praticamente iguais entre as três técnicas para a amostra 1. O percentual de generalização também permaneceu próximo a 50%. 60,00 49,0948,83 50,11 50,00 40,00 30,00 20,00 11 6 10,00 5 11 13 6 0,13 0,04 0,02 0,00 Aptidão Geracional Geração da Solução Nº Gerações Geracional c Elitismo Pontos Descartados (%) Steady State FIG. 6.15: Comparação das técnicas de substituição para TIN com a amostra 1. Os resultados obtidos indicam que a substituição steady state tende a resultar em iterações mais rápidas comparada às duas outras técnicas em questão. Somente em um caso, a 99 geracional com elitismo apresentou resultados melhores que a steady state (FIG. 6.15), entretanto, sem diferenças significativas. 60,00 52,22 50,86 50,47 50,00 40,00 30,00 23 20,00 14 9 10,00 25 15 10 0,04 0,01 0,01 0,00 Aptidão Geração da Solução Geracional Nº Gerações Pontos Descartados (%) Geracional c Elitismo Steady State FIG. 6.16: Comparação das técnicas de substituição para TIN com a amostra 2. A análise do avanço de aptidão média para as técnicas de substituição serve como parâmetro adicional para compreensão do comportamento das técnicas de substituição, à semelhança do que foi feito anteriormente para o estudo dos tipos de cruzamento. A FIG. 6.17 ilustra três testes envolvendo as três técnicas de substituição para o cruzamento de 1 ponto e malha regular interpolada por krigagem. Percebe-se que o teste realizado com a substituição steady state apresenta um maior avanço da aptidão média comparado aos dois outros testes, sem a presença de grandes sinuosidades no gráfico. Técnicas de Substituição - Cruzamento de 1 Ponto 0,03 0,02 Aptidão 0,01 0 -0,01 1 3 5 7 9 11 13 15 17 19 21 Nº Geração Geracional Geracional com Elitismo Steady state FIG. 6.17: Aptidão média para as técnicas de substituição com cruzamento de 1 ponto. Como último ponto a ser ressaltado quanto às técnicas de substituição de população, nota-se que as diferenças apresentadas nos gráficos anteriores apontam, à semelhança dos 100 operadores de cruzamento que, dentre os operadores implementados na presente pesquisa, a escolha do tipo de cruzamento e da técnica de substituição não exerce influência significativa no percentual de generalização de uma amostra, mantendo-se praticamente constantes os patamares alcançados em torno de 50%. 6.4.4 ANÁLISE DOS INTERPOLADORES Uma vez definido o tipo de cruzamento e a técnica de substituição populacional, é importante conhecer o comportamento das estruturas de dados / interpoladores adotados na presente pesquisa de generalização de modelos digitais. Foram utilizadas a malha triangular irregular e a grade regular interpolada por krigagem. As figuras 6.18 e 6.19 indicam os resultados obtidos de aptidão média da solução, de número médio de geração da solução, de número de gerações e de percentual de generalização para as duas estruturas escolhidos. Os resultados próximos para as duas estruturas indicam que o comportamento do algoritmo não sofre alteração significativa em termos desses quatro parâmetros, ou seja, a escolha da estrutura de dados / interpolador não exerce grande influência no rendimento de uma configuração de parâmetros do algoritmo genético. 60,000 50,72 50,000 47,95 40,000 30,000 20,000 10,000 12 8 7 12 0,033 0,100 0,000 Aptidão Geração da Solução TIN Nº Gerações Pontos Descartados (%) Krigagem FIG. 6.18: Resultados obtidos com TIN e Krigagem para a amostra 1. Essa independência entre a estrutura de dados e o rendimento do algoritmo na configuração escolhida pode estar baseada no fato de que todos os modelos em uma mesma iteração são gerados em uma mesma estrutura, com o mesmo interpolador e parâmetros. Essa uniformidade de estruturas e de parâmetros não gera características específicas que possam servir para distinguir um modelo de outro com relação ao valor de aptidão. 101 60,000 50,27449,332 50,000 40,000 30,000 15 20,000 8 10,000 16 4 0,003 0,009 0,000 Aptidão Geração da Solução TIN Nº de Gerações Pontos Descartados Krigagem FIG. 6.19: Resultados obtidos com TIN e Krigagem para a amostra 2. Uma vez que não há interferência perceptível com o rendimento do algoritmo, o que se espera de uma estrutura de dados / interpolador é a geração de modelos mais próximos o possível do conjunto de pontos, sem inserção ou remoção de informações importantes. Dentro da estrutura regular foi adotado o interpolador krigagem. A estimativa das novas coordenadas é feita estatisticamente a partir das amostras mais próximas por meio de um semivariograma. Apesar de proposto como um estimador não tendencioso, ainda há a possibilidade de serem gerados picos altimétricos a partir de pontos de grande variabilidade do atributo representado. Como exemplo de uma das implicações dessa possibilidade de inserção de valores muito acima ou muito abaixo dos valores esperados para o terreno, cita-se que utilizando a krigagem universal com semivariograma linear na amostra 1, foram encontradas cotas com valores negativos no modelo resultante. A FIG 6.20 ilustra esse efeito por meio de uma comparação do modelo original com o modelo generalizado. FIG. 6.20: Interpolação de cotas negativas: modelo original (esquerda) e modelo com cota negativa (direita). 102 Esse fato significa que diferentes conformações de pontos resultarão em estimativas igualmente distintas para a interpolação de coordenadas. Em outros termos, o impacto da retirada ou inserção de uma quantidade de pontos de uma amostra pode resultar em modificações críticas na forma do modelo resultante. A TAB. 2.1 indica, como uma das características da grade regular a dificuldade de representação de superfícies com variação local acentuada, caso do problema citado anteriormente. Considerando a malha triangular irregular, existem vantagens significativas para a representação de variações acentuadas em comparação à grade regular. Além disso, a TIN é uma estrutura relativamente leve e de processamento mais rápido para a geração do modelo, resultando em iterações em um menor espaço de tempo. Contudo, ressalta-se que modelos gerados com TIN também são susceptíveis a alterações bruscas na forma quando da retirada de alguns pontos. Nesse caso, as alterações bruscas na forma surgem como retirada de feições da superfície ou inserção de formas antes inexistentes. A FIG. 6.21 ilustra as modificações ocorridas em uma TIN generalizada, em comparação ao modelo original. Ao se observar o modelo generalizado da direita, percebe-se nitidamente a retirada de uma feição e inserção de uma forma não existente no modelo original. Essas modificações inseridas no modelo certamente interferem no cálculo do volume e dificultam a comparação dos modelos resultantes de generalização com o modelo original. FIG. 6.21: Comparação de modelos TIN: original (esquerda) e generalizado (direita). Apesar de possibilitar modificações bruscas dos modelos resultantes de generalização, como vantagem da TIN com relação à grade regular interpolada por krigagem cita-se o fato de não inserir valores de altitude que extrapolam o intervalo das cotas dos pontos presentes na 103 amostra inicial. Além disso, é uma estrutura que permite processamentos em intervalos mais curtos. A rigor é tecnicamente difícil a definição e escolha de um interpolador que não incorpore modificações críticas na forma dos modelos resultantes de generalização. Isso porque, quando se faz a comparação de um modelo original com outro modelo generalizado para determinação da aptidão, na prática é feita a comparação de dois modelos distintos, apesar de retratarem uma mesma região e dos pontos do modelo generalizado estarem dentro de um subconjunto do modelo original. 6.4.5 CONSIDERAÇÕES FINAIS DOS TESTES DE CONFIGURAÇÃO DOS PARÂMETROS A realização dos testes com diferentes configurações de critério de aptidão, tipo de cruzamento e técnica de substituição populacional para as amostras de dados 1 e 2, de características distintas, resultaram em um comportamento análogo das amostras para os dois conjuntos de pontos, isto é, as configurações mais rápidas para uma amostra tenderam a ser mais rápidas para outra amostra também. Esse fato facilitou a definição de uma melhor combinação de parâmetros, possível de ser aplicada a futuros testes e com outras amostras de dados. Somada a essa constância de rendimentos, em todas as configurações testadas os percentuais de generalização permaneceram próximos a 50%, nas duas amostras. Se, por um lado, esse fato pode ser considerado de forma positiva, uma vez que o percentual de generalização não depende significativamente da configuração adotada e das características da amostra, por outro revela que o fator de maior influência no percentual de generalização ainda não foi considerado nos testes. Em vista das configurações estudadas apresentarem o mesmo grau de generalização final para suas soluções, o critério adotado para a definição de uma configuração passa a ser a rapidez da configuração para atingir a convergência, isto é, a geração média da solução e o número médio de gerações. Sob esse critério, a substituição steady state combinada com o cruzamento de 1 ponto surge como uma melhor combinação a ser adotada em futuros testes. Quanto à estrutura de dados mais indicada, a TIN surge como melhor alternativa em função de ser a estrutura otimizada e que apresentou processamento mais rápido para as amostras de dados utilizadas, conforme exposto no item 6.4.4 . 104 Os testes e as análises aqui propostos abrangem somente quatro parâmetros dentro do conjunto de possibilidades de escolha no algoritmo. Dentre os demais parâmetros não abrangidos nos testes de configuração ressalta-se o tamanho da população, as taxas de cruzamento e mutação e o percentual de convergência do algoritmo. Os parâmetros não abrangidos exercem influência principalmente no número de gerações, na quantidade dos cruzamentos realizados, no número de novos indivíduos introduzidos por conta da mutação e, consequentemente, podem afetar o percentual final de generalização dos modelos resultantes. Não se descarta a importância da escolha criteriosa de tais parâmetros. Contudo, não serão realizados testes para análise dos mesmos, uma vez que esse não constitui o escopo principal da presente pesquisa e por ser uma tarefa que demanda uma quantidade de testes relativamente grande a fim de se definir as taxas de cruzamento e de mutação mais adequadas para se atingir um determinado percentual de generalização. Os valores da população na presente pesquisa, conforme mencionado anteriormente, estão reduzidos a números pequenos em função do risco de tornar lenta em demasia cada iteração do algoritmo. As taxas de cruzamento e de mutação constituem tema de diferentes pesquisas de sistemas de algoritmos genéticos. Em diversos estudos há um consenso de que, em sistemas de algoritmos genéticos, a taxa de mutação, por exemplo, deve ser bem inferior à taxa de cruzamento, recebendo geralmente valores próximos a 1%, conforme a bibliografia pesquisada. Da mesma forma, a taxa de cruzamento foi inicialmente arbitrada em 50% e deverá ser mantida nos próximos testes. Além da quantidade de pontos eliminados e da rapidez das iterações, um fator que merece destaque está relacionado à qualidade dos modelos resultantes. Dessa forma, a compreensão da qualidade final dos modelos generalizados ganha uma relevância ainda maior que o estudo dos parâmetros que interferem no percentual de generalização do algoritmo genético. Os próximos testes realizados tratam do percentual de generalização e da questão da qualidade da generalização final 6.5 TESTES DO PERCENTUAL DE GENERALIZAÇÃO Em todos os testes realizados anteriormente a quantidade de pontos retirados das amostras em estudo sempre esteve próxima a 50%, para quaisquer configurações testadas. Em princípio, os resultados obtidos conduzem a uma conclusão de que a atividade de 105 generalização de modelos digitais pelo algoritmo implementado geralmente resulta na redução de aproximadamente metade da quantidade de pontos de uma amostra. Entretanto, com o intuito de verificar a tendência encontrada nos testes anteriores, alguns testes adicionais voltados especificamente para o estudo do percentual de generalização do algoritmo genético tornam-se necessários para a correta identificação do(s) parâmetro(s) de maior interferência. 6.5.1 TESTE DO PERCENTUAL DE CONVERGÊNCIA Todos os testes realizados tiveram como critério de parada a convergência da população utilizando o percentual de convergência fixado em 75%. Isso significa que cada iteração termina quando 75% ou mais de sua população for formada por indivíduos com mesma aptidão. Intuitivamente, é possível prever que o percentual de convergência exerce uma influência mais significativa no número de gerações, uma vez que para se atingir o percentual fixado de indivíduos iguais em uma população são necessárias diferentes gerações para seleção, cruzamento e formação de novos indivíduos. Entretanto, o número de gerações pode ter correlação estreita com o percentual de generalização do algoritmo. Dessa forma, testes com diferentes percentuais de convergência são importantes para a verificação de sua possível interferência na quantidade de pontos eliminados de uma amostra. Foram realizados testes com percentuais de convergência de 15% , 30%, 45% , 60% e 90%, sendo efetuados cinco testes para cada novo percentual. As taxas de cruzamento e de mutação adotadas permaneceram em 50% e 1%, respectivamente. A população permaneceu com tamanho de 20 indivíduos. A figuras 6.22 e 6.23 ilustram os resultados alcançados pelos testes com todos os percentuais de convergência considerados, para as amostras 1 e 2 respectivamente. Da mesma forma que para os testes anteriores, serão comparados os valores de geração média da solução, número médio de gerações e percentual de convergência 106 60 50,23 51,51 51,32 51,09 46,16 50 48,02 40 30 18 20 11 10 9 11 8 15 14 13 9 10 5 3 0 Geração da Solução 90% Nº de Gerações 75% 60% Pontos Descartados (%) 45% 30% 15% FIG. 6.22: Comparação dos testes com diferentes percentuais de convergência para a amostra 1. 60 54,00 52,39 50,86 49,8051,22 47,10 50 40 30 20 20 11 12 16 12 6 10 17 11 6 10 5 4 0 Geração da Solução 90% 75% Nº de Gerações 60% 45% Pontos Descartados (%) 30% 15% FIG. 6.23: Comparação dos testes com diferentes percentuais de convergência para a amostra 2. Os resultados comprovam a idéia de que o percentual de convergência exerce influência principalmente no número de gerações de uma iteração. Percebe-se um aumento correspondente no número médio de gerações das iterações, à medida que o percentual de convergência aumenta. A média da geração da solução, contudo, não apresentou um crescimento tão regular conforme o aumento do percentual de convergência Os limites de 90%, 75% e de 60% apresentaram médias de geração da solução quase duas vezes maiores comparadas aos outros limites. O percentual de generalização permaneceu em patamares próximos a 50% para todos os percentuais testados, sendo a maior discrepância desse comportamento apresentada pelo percentual de generalização de 46,16% para a amostra 1. Isso comprova que o percentual de generalização também não é afetado significativamente pelo percentual de convergência limite de uma iteração. 107 Considerando o valor da aptidão da solução, há um acréscimo do valor da aptidão conforme ocorre a redução do percentual de convergência, conforme mostra a FIG. 6.24 . Esse fato deve-se à redução da quantidade de cruzamentos dos indivíduos, uma vez que para se atingir o número limite de indivíduos de mesma aptidão em uma população é necessário recombinar uma menor quantidade de indivíduos. Ocorrendo menos cruzamentos, menor será conseqüentemente a evolução da aptidão dos indivíduos. 0,070 0,057 0,060 0,050 0,040 0,030 0,020 0,013 0,010 0,002 0,002 0,016 0,006 0,000 Melhor Aptidão 90% 75% 60% 45% 30% 15% FIG. 6.24: Aptidão média da solução para diferentes percentuais de convergência na amostra 2. Esses resultados indicam que os percentuais de convergência influenciam principalmente na quantidade de gerações, na quantidade de cruzamentos e na qualidade final dos indivíduos. Quanto menos gerações forem realizadas, menor a quantidade de cruzamentos e menor a evolução dos indivíduos da população inicial. Por exemplo, percentuais de convergência com valor de 15% para populações de 20 indivíduos, reduziram o número médio de gerações para 5, considerando as duas amostras testadas, e aumentaram a aptidão média da solução de 0,002% para 0,057% (mais de 28 vezes), no caso da amostra 2. Apesar do aumento do valor da aptidão ser aparentemente pouco significativo, ao se definir um percentual de convergência limite é importante considerar o seu aumento, a fim de não comprometer a qualidade dos indivíduos gerados. Considerando os percentuais testados, o valor de 45% como convergência surge como limite mais razoável para realização de testes nas amostras 1 e 2, uma vez que representa uma redução da quantidade de gerações das iterações sem alterar o valor médio da aptidão para as soluções em comparação aos percentuais de convergência mais elevados. A não interferência dos percentuais de convergência nos percentuais de generalização do algoritmo genético indica uma preponderância da população inicial na redução de pontos. 108 Esse fato mostra-se mais evidente para os pequenos percentuais de convergência, nos quais, mesmo com poucas gerações, é possível obter níveis de generalização muito próximos a 50%. Dessa forma, caso o percentual de generalização fosse crescente / decrescente com o número de gerações isso seria perceptível com a variação dos limites de convergência. 6.5.2 TESTES COM A POPULAÇÃO INICIAL No caso dos testes realizados anteriormente, a população inicial foi formada por indivíduos gerados aleatoriamente. A partir da melhor configuração encontrada, foram realizados novos testes com o intuito de testar a interferência da população inicial no resultado final do algoritmo. Para cada amostra foram realizados então 20 novos testes e observados seus resultados e as respectivas composições de suas populações iniciais. Os resultados encontrados demonstraram que a composição da população inicial para todos os testes influenciou fortemente o resultado das iterações. Para as populações iniciais geradas, todos os indivíduos gerados aleatoriamente apresentavam um percentual de generalização bem próximo a 50%. Para os testes realizados com a amostra 1, as diferenças de percentual de generalização dos indivíduos com relação ao valor de 50% sempre ficaram inferiores a 6% e a diferença entre os percentuais mínimo e máximo de generalização (amplitude), entre indivíduos de uma mesma população inicial, não ultrapassou a marca de 5,5%. Para a amostra 2, as diferenças de percentual de generalização dos indivíduos com relação ao valor de 50% sempre ficaram inferiores a 5,5% e a amplitude de percentuais de generalização não ultrapassou a marca de 10%. A FIG. 6.25 ilustra os resultados das populações iniciais encontradas para 20 testes realizados com a amostra 1. 60,00 50,00 40,00 (%) 30,00 20,00 10,00 0,00 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Testes Mínimo Máximo Amplitude FIG. 6.25: Mínimos, máximos e amplitudes das populações iniciais da amostra 1. 109 Indivíduos com amplitude tão reduzida traduzem uma falta de variabilidade na população inicial, fato que geralmente leva a convergências prematuras e reduz as chances de geração de indivíduos com novas características. Isso somado à característica dos percentuais de generalização dos indivíduos estarem próximos a 50% explicam a tendência encontrada anteriormente de generalização de amostras sempre em níveis próximos à metade da quantidade de pontos. Uma vez diagnosticado o fato, entretanto, é preciso entender o porquê da geração de indivíduos com percentuais de generalização concentrados em torno do valor de 50%. A explicação a esse fato vem do algoritmo adotado inicialmente para a geração da população inicial. A estratégia adotada inicialmente previu a atribuição do valor de cada locus de um cromossomo por meio de uma função randômica, que deveria atribuir valores 0 ou 1 para cada gene dos cromossomos. A atribuição de valores deve ser feita de forma aleatória com cada indivíduo, podendo receber qualquer número de genes contidos dentro do intervalo definido inicialmente pelo usuário. Contudo, a prática ilustra resultados diferentes do esperado, uma vez que o número de pontos ausentes em cada cromossomo surge com valores bem próximos ao número de pontos considerados, ou seja, a distribuição dos números zero (0) e um (1) ocorre aproximadamente na mesma proporção nas cadeias cromossômicas. Em virtude desses resultados, foram realizadas alterações na forma de geração dos indivíduos das populações iniciais. A atribuição de valores zero e um na cadeia cromossômica deixou de ser feita diretamente a partir de uma variável randômica e foi criado um número auxiliar que armazena o total de pontos que devem ser inseridos em cada indivíduo. Esse número recebe o valor numérico de uma variável randômica que pode assumir valores dentro do intervalo de mínimo e de máximo de pontos para cada iteração. Uma vez recebido o valor, o número 1 é inserido em diferentes locus da cadeia, determinados aleatoriamente, em quantidade equivalente ao valor fixado pela variável. Como o número de pontos é definido anteriormente à distribuição para cada indivíduo, há uma menor chance da ocorrência de valores iguais ou próximos a 50% de pontos. Além disso, há a redução das chances de ocorrência de indivíduos com o mesmo número de pontos e, mesmo que haja tal coincidência, a distribuição de pontos na cadeia cromossômica será diferente. A partir dessa nova configuração do algoritmo foram repetidos os testes para geração da população inicial. Para as amostras 1 e 2 foram realizados 20 testes com as mesmas 110 configurações, sendo verificadas alterações significativas na geração dos indivíduos que passaram a apresentar percentuais de generalização em intervalos bem mais amplos e não mais restritos às faixa de 50%. A FIG. 6.26 ilustra os novos testes. Nota-se na nova configuração um aumento considerável na terceira coluna da esquerda, relacionada com a amplitude dos indivíduos na população inicial. 120,00 100,00 80,00 (%) 60,00 40,00 20,00 0,00 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Testes Mínimo Máximo Amplitude FIG. 6.26: Mínimos, máximos e amplitudes das populações iniciais da amostra 1. Como principal resultado do novo método de geração da população inicial houve uma maior dispersão dos resultados de generalização retornados pelo algoritmo. Para a amostra 2, por exemplo, os novos percentuais encontrados vão de pouco mais 28% a valores próximos a 90%. 6.5.2.1 TESTES DA POPULAÇÃO COM PERCENTUAL FIXO Esses testes têm com principal objetivo a verificação dos resultados que podem ser obtidos a partir de indivíduos formados com um mesmo percentual de generalização. Foram realizados testes diferentes para populações organizadas por indivíduos com quantidades de pontos iguais a 5%, 25%, 50% , 75% e 95%, percentuais, que representam uma expectativa prévia de generalização. As amostras 1 e 2 foram adotadas nos testes, sendo realizados 5 testes para cada configuração de população inicial. As soluções encontradas para todos os testes afastam-se muito pouco do percentual de pontos presente na população inicial. Por exemplo, para populações organizadas por indivíduos formados com 5% dos pontos, as soluções apresentaram percentuais de generalização próximos a 95%, o valor do complemento. Resultados semelhantes foram 111 obtidos com os outros percentuais estudados, sendo que para todos os percentuais as diferenças das soluções encontradas com relação aos respectivos percentuais complementares não superam 2% para as duas amostras de dados testadas. Em resumo, na prática o algoritmo genético com as configurações adotadas, mostrou-se muito dependente da qualidade dos indivíduos considerados inicialmente na primeira população. Uma vez definida uma população, o sistema apresentou pouco potencial para a obtenção de soluções melhores com a variabilidade da população seja reduzida. Com as configurações escolhidas, sua atuação principal é a de otimizar as expectativas prévias de generalização. 6.6 TESTES DE GENERALIZAÇÃO SUCESSIVA Os testes realizados anteriormente foram voltados principalmente para um melhor conhecimento do algoritmo sob diferentes configurações. Foram testadas diferentes combinações de operadores genéticos, de técnicas de substituição populacional, de critérios de função aptidão e de estruturas de dados. A partir desses resultados foi possível reconhecer alguns fatores de maior influência no algoritmo genético, bem como reconhecer uma configuração mais adequada para os testes subseqüentes. Não há dúvida quanto à importância dos testes rendimento, contudo, o conhecimento da qualidade dos modelos generalizados é tão ou mais importante quanto o conhecimento do desempenho do algoritmo em diferentes configurações. O termo qualidade dos modelos na forma aqui considerada refere-se ao grau de semelhança dos modelos resultantes com relação ao modelo original, sendo que valores altos de semelhança indicam uma menor degradação dos modelos generalizados e, conseqüentemente, uma melhor qualidade dos modelos. A semelhança deve ser estabelecida não só com referência ao volume, mas por meio de comparações visuais dos modelos resultantes com o modelo original. Assim, existem dois critérios principais para a semelhança de dois modelos, relacionados à proximidade numérica de volumes e também à manutenção das principais características de forma. O primeiro critério é objetivo, numérico e facilmente reconhecido enquanto o segundo envolve a comparação de modelos pelo usuário, portanto, subjetivo. O estudo do comportamento do algoritmo pode fornecer alguns indicativos de perda de qualidade. Uma forma de conhecimento do comportamento do algoritmo genético na generalização de modelos digitais é a execução de generalizações partindo de uma amostra e 112 utilizando a amostra resultado como amostra original em uma generalização posterior. Diferente do realizado nas seções anteriores, nas quais os testes eram realizados sempre partindo da amostra original com todos os pontos. Como indícios de perda de qualidade fornecidos pelo sistema cita-se, por exemplo, a generalização das amostras em percentuais decrescentes, à medida que são reduzidos os pontos de uma amostra. Isso pode significar a chegada a um limiar de generalização que, por sua vez, indica uma quantidade de pontos além da qual a retirada de pontos pode degradar significativamente uma amostra. Essa classe de testes, aqui denominada de generalização sucessiva, tem como principal objetivo identificar eventuais variações no comportamento do algoritmo conforme ocorre a progressão da retirada de pontos em um modelo original. Alterações de comportamento podem ser traduzidas por variações nos percentuais de generalização, nos valores de aptidão e no número de gerações conforme ocorre a sucessiva remoção de pontos da amostra. Uma vez detectadas essas alterações dos valores considerados como parâmetros, são investigadas tendências de comportamento que possam permitir a conclusão de um comportamento semelhante dos parâmetros para diferentes amostras. 6.6.1 GENERALIZAÇÃO SUCESSIVA COM APTIDÃO BASEADA NA DIFERENÇA DE VOLUME Os testes de generalização sucessiva foram realizados com as amostras 1 e 2. Para ambos os casos, foram realizadas iterações até que a amostra atingisse um percentual pré-definido de generalização. Para ambas, foram retirados pontos até um limite de 85% da amostra original,. A FIG. 6.27 ilustra a variação dos valores de aptidão até a décima iteração nas amostra 1 e 2. O gráfico indica que não há um comportamento uniforme dos valores de aptidão baseada na diferença de volumes. Ao longo das iterações, conforme ocorre a retirada de pontos, os valores de aptidão apresentam tendência de crescimento em determinadas iterações e de redução em outras. Além disso, as curvas de aptidão são diferentes para as amostras testadas. Em tese, o resultado esperado para os testes era o aumento numérico dos valores de aptidão dos modelos acompanhando a redução de pontos. Vale lembrar que a função aptidão escolhida é baseada na diferença percentual de volumes entre o modelo generalizado e o modelo original. Segundo esse ponto de vista, a retirada de pontos de um modelo tenderia a 113 afastar cada vez mais o volume do modelo resultante do volume original e, em conseqüência, aumentar os valores da aptidão (originando indivíduos menos aptos). A prática, entretanto, Dif Volume (%) demonstrou um comportamento diverso do esperado. 0,080 0,070 0,060 0,050 0,040 0,030 0,020 0,010 0,000 -0,010 1 2 3 4 5 6 7 8 9 10 Nº Geração Amostra 1 Amostra 2 FIG. 6.27: Evolução da função aptidão em testes de generalização sucessiva. Comparando os modelos gerados percebe-se, na prática, que os valores de aptidão fornecem indicações que não condizem com a real situação dos modelos, ou qualidade dos modelos. Para a amostra 1, por exemplo, considerando somente os valores de aptidão presentes no gráfico, o modelo resultante da sexta iteração apresenta uma melhor qualidade que o modelo resultante da segunda iteração. Entretanto, pela comparação dos dois modelos, percebe-se uma perda de detalhes claramente mais acentuada no modelo da sexta iteração, conforme ilustra a FIG. 6.28. Apesar de o modelo da sexta iteração apresentar um volume numericamente mais próximo ao volume do modelo original, sua forma encontra-se bem diferente e de qualidade degradada quando comparado ao modelo da segunda iteração, de menor aptidão. A retirada de feições de relevo, em paralelo à inserção de novas formas ao modelo, comentadas na seção 6.4.4, explicam a relativa compensação dos valores de volume encontrados, tornando um modelo degradado mais apto que outro de melhor qualidade. Isso reforça a necessidade de incorporar parâmetros de forma à função aptidão. A criação de modelos degradados com a preservação de valores de aptidão em patamares baixos demonstra, por outro lado, a grande capacidade do algoritmo genético em otimizar soluções. Obedecendo à forma de cálculo da aptidão inserida no sistema, o algoritmo exerceu a tarefa de explorar combinações de pontos que minimizassem a diferença de volume com 114 relação ao modelo de referência, não importando a qualidade dos mesmos e de forma independente do percentual de generalização. FIG. 6.28: Evolução de modelos TIN: original (acima), segunda iteração (centro) e sexta iteração (abaixo). 115 Os resultados encontrados demonstram a insuficiência da função aptidão inserida para a generalização de modelos digitais. Espera-se, nesse caso, uma função que forneça dados objetivos acerca da qualidade dos modelos resultantes, que tenha um comportamento regular e confiável de acordo com a variação dos modelos. O valor de volume, passível a variações e deformações bruscas capazes de mascarar degradações, é incompleto para ser adotado como critério exclusivo na formação da função aptidão. Outros parâmetros e atributos de modelos digitais, que traduzam objetivamente e com fidelidade a qualidade dos modelos, devem ser inseridos para compor os valores de aptidão dos modelos. 6.6.2 APTIDÃO BASEADA EM VALORES DE VOLUME, DE ÁREA PLANA E DE ÁREA SUPERFICIAL A variação irregular da aptidão baseada unicamente no critério de volume traz consigo a necessidade do aperfeiçoamento de uma função aptidão capaz de expressar numericamente alterações na qualidade dos modelos. Alterações na qualidade referidas passam não só por variações em valores numéricos mas relacionam-se, principalmente, à forma dos modelos. Esse atributo forma, entretanto, não é facilmente codificado para valores objetivos. Apesar de não ser um estudo tão trivial a tarefa de traduzir objetivamente alterações de forma, um passo nesse sentido pode ser o estabelecimento correto dos parâmetros objetivos de modelos que, em conjunto, melhor traduzem degradações acentuadas de forma. Um fato desejável para esses parâmetros deve ser a previsibilidade de seus valores conforme ocorre a retirada de pontos de um modelo. Um comportamento previsível de um parâmetro ao menos permite a correlação de seus valores com diferentes estados de qualidade dos modelos e a procura de padrões. Como parâmetros candidatos a integrarem a função aptidão serão estudados os valores de área plana e de área superficial. A área plana refere-se à área projetada do modelo em um plano horizontal e a área superficial relaciona-se à área da superfície do modelo. Considerando os testes realizados na seção anterior, com a aptidão determinada a partir de 116 valores de volume, é possível acompanhar a variação desses dois novos parâmetros, ilustrada Dif Area Plana (%) nas figuras 6.29 e 6.30. 14,000 12,000 10,000 8,000 6,000 4,000 2,000 0,000 1 2 3 4 5 6 7 8 9 10 Nº Geração Amostra 1 Amostra 2 Dif Area Superfical (%) FIG. 6.29: Variação da área plana para as amostras 1 e 2 na generalização sucessiva. 50,000 40,000 30,000 20,000 10,000 0,000 1 2 3 4 5 6 7 8 9 10 Nº Geração Amostra 1 Amostra 2 FIG. 6.30: Variação da área superficial para as amostras 1 e 2 na generalização sucessiva. Para os dois casos os gráficos apresentam uma tendência predominante de crescimento. Apesar de pequenas reduções de valores, perceptíveis a partir da sétima e oitava iterações, os dois valores de área plana e superficial apresentaram um comportamento bem mais confiável que o valor de volume, dentro do que se espera de uma função aptidão. Esse comportamento favorável sugere a inserção das duas áreas ao valor da aptidão em conjunto com o valor do volume. 117 A aptidão baseada em volume é determinada a partir da diferença entre os volumes do modelo generalizado e do modelo original dividida pelo valor do volume do modelo original. Em suma, indica o percentual de afastamento dos volumes dos modelos com relação ao volume de referência, conforme expresso na EQ. 5.3 . A inserção de dois novos parâmetros à função aptidão será a média aritmética composta pela soma das diferenças percentuais de volume, de área plana e de área superficial, indicada na EQ. 6.1 . F = ( | A’2D – A2D| / A2D + | A’3D – A3D| / A3D + | V’ – V| / V ) / 3 (6.1) sendo A’2D; A’3D; V’ os valores de área plana, área superficial e de volume do modelo candidato a solução e A2D; A3D; V os valores de área plana, área superficial e de volume do modelo original de referência. A partir da nova função aptidão, teve início uma nova bateria de testes de generalização sucessiva com as amostras 1 , 2 e 3, com um percentual de generalização limite de 95%, ou seja, as iterações param quando chega-se a amostras contendo somente 5% dos pontos das amostras originais. Os novos testes em questão foram repetidos por duas vezes com cada uma das amostras, visando verificar possíveis padrões de comportamento do algoritmo em redução de pontos. Como fato importante a ser ressaltado, o percentual de generalização obtido em cada iteração é variável e independente da quantidade de pontos. Contudo, os valores encontrados para as três amostras estiveram geralmente abaixo de 50%. Isso faz com que para se atingir um percentual de generalização limite sejam necessárias mais iterações. Para todas as amostras, foram necessárias mais de 30 iterações para a retirada de 95% dos pontos. 6.6.2.1 VARIAÇÃO PERCENTUAL DO VOLUME O valor da diferença de volume apresentou variações irregulares para todas as amostras mesmo com a nova função aptidão. A FIG. 6.31 indica a variação percentual da diferença de volumes dos modelos em testes realizados nas amostras 1 e 2. Esse comportamento irregular do volume foi constatado e repetido para todas as amostras em todos os testes realizados, o que impede a correspondência de seus valores com níveis de qualidade do modelo. 118 Dif Volume (%) 4,000 3,000 2,000 1,000 0,000 -1,000 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 Nº Geração Amostra 1 Amostra 2 Amostra 2 Amostra 1 FIG. 6.31: Diferença de volume para as amostras 1 e 2. 6.6.2.2 VARIAÇÃO PERCENTUAL DA ÁREA PLANA Os gráficos expressos nas figuras 6.32 e 6.33 ilustram os resultados de variação da área Dif Area Plana (%) plana obtidos para as três amostras utilizadas nos dois testes de generalização sucessiva. 14,000 12,000 10,000 8,000 6,000 4,000 2,000 0,000 -2,000 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 Nº Geração Amostra 1 Amostra 2 Amostra 3 FIG. 6.32: Variação da área plana no primeiro teste. Os valores de área projetada apresentaram uma variação mais regular em comparação aos valores de volume, apesar da ocorrência de inflexões de valores principalmente na amostra 1. Para todas as amostras testadas, a diferença de área plana dos modelos generalizados tendeu predominantemente a crescer. 119 A amostra 1, organizada por pontos com distribuição muito irregular, apresentando boa parte de seus pontos concentrada em pequenas áreas, apresentou gráficos com maior irregularidade que as demais amostras. A amostra 3 apresentou os menores resultados de variação da área plana, com os resultados não ultrapassando 2,5% de variação, apresentando D if A re a P la n a (% ) também gráficos mais retilíneos. 12 10 8 6 4 2 0 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 Nº Geração Amostra 1 Amostra 2 Amostra 3 FIG. 6.33: Variação da área plana no segundo teste. Em vista da regularidade dos valores apresentados é possível tentar realizar o acompanhamento da evolução da variação de forma dos modelos por meio da comparação visual. Ainda que subjetiva e, portanto, imprecisa, essa prática pode servir para identificar valores críticos de variação de área plana a partir dos quais a forma dos modelos originais sofre profundas alterações. Considerando a amostra 1 no primeiro teste, percebe-se que os modelos preservam grande semelhança com o modelo original até a sétima iteração, com 0,21% de alteração de área plana e generalização acumulada de aproximadamente 43%. No segundo teste, alterações significativas na forma surgem a partir da terceira iteração, com diferença de área plana de 0,79% e aproximadamente 25% de generalização total. A amostra 2 no primeiro teste apresentou alterações bruscas de forma logo a partir da primeira iteração, com diferença de 0,36% na área plana e generalização acumulada de aproximadamente 23% . No segundo teste, a forma sofre alteração abrupta a partir da sexta iteração com diferença de 0,88% na área plana e generalização de aproximadamente 27% . Para a amostra 3, em função da mesma permanecer com valores invariavelmente baixos e com pequenas variações de diferença de área plana entre as iterações, não é tão fácil realizar a 120 associação de seus valores com modificações de forma. Para o primeiro teste percebe-se que as modificações profundas na forma surgem somente a partir da décima nona iteração, com 2,12% de variação de área plana e generalização acumulada pouco superior a 83%. No segundo teste, as deformações surgiram a partir da décima terceira iteração, com 0,65% de variação de área plana e aproximadamente 76% de generalização. 6.6.2.3 VARIAÇÃO PERCENTUAL DA ÁREA SUPERFICIAL O último parâmetro considerado nos testes de generalização sucessiva é a variação de área superficial dos modelos. As figuras 6.34 e 6.35 apresentam os resultados de variação da Dif Area Superficial (%) área superficial para os testes realizados com as amostras 1, 2 e 3. 45,000 40,000 35,000 30,000 25,000 20,000 15,000 10,000 5,000 0,000 -5,000 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 Nº Geração Amostra 1 Amostra 2 Amostra 3 Dif Area Superficial (%) FIG. 6.34: Variação da área superficial no primeiro teste. 30 25 20 15 10 5 0 -5 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 Nº Geração Amostra 1 Amostra 2 FIG. 6.35: Variação da área superficial no segundo teste. 121 Amostra 3 Os valores de área superficial não se apresentaram tão regulares quanto a variação de área plana. Em vários pontos dos gráficos dos dois testes percebem-se zonas alternadas de crescimento e de redução do parâmetro em questão, principalmente com relação às amostras 1 e 2. Esse comportamento imprevisível prejudica o estudo de correlações dos níveis de degradação dos modelos com a variação de área superficial, tornando o parâmetro menos confiável. O primeiro teste da amostra 1 mostrou que os modelos não apresentaram alterações morfológicas críticas até a sétima iteração, com 0,41% de variação de área superficial e com aproximadamente 57% dos pontos. No segundo teste as alterações mais significativas surgem a partir da terceira iteração, com diferença de área superficial de 0,82% e 25% de generalização total. Para a amostra 2, no primeiro teste as alterações críticas ocorrem já na primeira iteração, com 2,61% de diferença de área superficial e generalização acumulada de cerca de 23%. No segundo teste as alterações significativas surgem a partir da sexta iteração com 0,04% de diferença área superficial e aproximadamente 27% de generalização. A amostra 3 para o primeiro teste apresenta suas maiores alterações para variações de área superficial com diferença de área superficial a partir de 3,4% e generalização acumulada de aproximadamente 83%. No segundo teste, as modificações de forma mais pronunciadas surgem a partir de 1,64% de diferença de área superficial e aproximadamente 76% de generalização acumulada. 6.6.3 CONCLUSÃO DOS TESTES DE GENERALIZAÇÃO SUCESSIVA Os testes de generalização sucessiva de amostras tiveram por principal objetivo a análise do processo de retirada de pontos de uma amostra visando identificar possíveis limites para a retirada de pontos sem o comprometimento da qualidade dos modelos. O reconhecimento de limites de generalização a partir da verificação da qualidade dos modelos resultantes não é uma tarefa simples em função da essência subjetiva do critério qualidade e da forma de verificação aqui adotada. No presente estudo, os modelos foram conceituados segundo sua semelhança visual com relação ao modelo original. Em vista dessa dificuldade, a descoberta de novos parâmetros capazes de descrever modificações na qualidade dos modelos é de fundamental importância. 122 Os testes iniciais de generalização sucessiva demonstraram uma aptidão baseada em diferença de volume bastante irregular. Com intuito de conhecimento de novos parâmetros próprios para o aprimoramento da função aptidão foram estudadas as variações das áreas plana (projetada) e superficial. Os resultados obtidos apresentaram comportamentos mais previsíveis e confiáveis, razoáveis para serem introduzidos na função aptidão. A partir dos resultados preliminares foi montada uma nova função aptidão baseada na média aritmética das diferenças de área plana, de área superficial e de volume. Dos dois novos parâmetros incorporados à função aptidão, somente a área plana apresentou um comportamento previsível, com tendência de crescimento na maioria dos testes realizados. A curva da área superficial, ainda que menos sinuosa que a curva da variação de volume, apresentou trechos com tendências de aumento e de redução que dificultam o seu estabelecimento como parâmetro confiável de qualidade. Além disso, mostrou-se mais sensível à redução de pontos apresentando maiores variações percentuais que a área plana, atingindo valores próximos a 40% em algumas iterações. Nenhuma das três amostras estudadas apresentou resultados semelhantes para os dois testes realizados. As curvas das diferenças de área superficial e de área plana apresentaram desenhos variados para os testes realizados, não sendo observado um padrão de comportamento na retirada de pontos. A TAB.6.1 resume os resultados atingidos de generalização sucessiva, envolvendo os testes para a nova função aptidão para as três amostras de dados. TAB. 6.1: Valores limite dos parâmetros para os testes de generalização sucessiva. Teste 2 Amostra Teste 1 Área Plana 1 0,21 % 0,41 % 42,83 % 0,79 % 0,81 % 25,00 % 2 0,36 % 2,61 % 22,55 % 0,88 % 0,04 % 26,67 % 3 2,12 % 3,43 % 83,64 % 0,65 % 1,64 % 76,33 % Área % Gen. Área Plana Superficial Área % Gen. Superficial Essa variabilidade das curvas e de resultados para testes diferentes pode ser explicada pelo caráter estocástico do algoritmo genético. A geração aleatória da população inicial, seguida da seleção e cruzamentos aleatórios em iterações diferentes, impossibilita a geração 123 de modelos com percentuais de generalização, configuração de pontos e valores de aptidão semelhantes. Assim, por exemplo, se em um teste foram necessárias 5 iterações para se atingir um percentual de generalização de 30% não é plenamente certo que o mesmo percentual seja alcançado com o mesmo número de iterações em outro teste. Ressalta-se ainda que a configuração das amostras influencia o comportamento do algoritmo. A amostra 1, por exemplo, formada por pontos de distribuição bastante heterogênea, concentrados em regiões pequenas e ausentes em outras, apresentou os gráficos mais imprevisíveis. A amostra 3, organizada por pontos que descrevem unicamente a forma geométrica de um vulcão, apresentou variações dos parâmetros com tendência predominante de crescimento. 124 7 CONCLUSÕES 7.1 CONCLUSÕES Dentro do foco de generalização de modelos foi introduzida e testada uma abordagem de emprego de algoritmos genéticos como ferramenta. O sistema de algoritmos genéticos foi voltado a geração, aprimoramento e definição de melhores combinações de pontos a partir de um modelo original. O algoritmo implementado apresenta uma estrutura simples e guarda semelhanças de forma com o algoritmo clássico, proposto por John Holland, principalmente com relação à codificação binária adotada para os cromossomos. A partir dos operadores genéticos implementados abrem-se diferentes combinações possíveis de parâmetros para a generalização de modelos, seja pela escolha dos parâmetros do algoritmo genético ou da estrutura de dados do modelo. Para reduzir a quantidade de testes voltados para o estudo do algoritmo genético houve a necessidade de fixar valores numéricos de determinados parâmetros, obedecendo às restrições do sistema em teste e resultados obtidos bem como recomendações dentro da bibliografia pesquisada. O tamanho da população foi definido como de 20 indivíduos, as taxas de cruzamento e de mutação definidas em 50% e 1%, respectivamente. O critério de parada adotado foi o de convergência, com percentual de convergência fixado inicialmente em 75% sendo posteriormente testados diferentes percentuais. Os testes dos operadores genéticos foram realizados para as amostras de dados 1 e 2, ambas desenvolvidas em laboratório com diferentes características de quantidade e de distribuição de pontos. Considerando os dois conjuntos de pontos utilizados nos testes, os resultados apontam para a independência do rendimento dos operadores com relação ao conjunto de pontos utilizado na generalização podendo uma mesma combinação ser a mais eficiente para diferentes modelos adotados. Quanto à melhor configuração, o uso da substituição steady state e do cruzamento de um ponto surge como combinação mais eficiente. Com relação aos critérios de aptidão estudados, o volume apresentou melhor desempenho que o critério de pontos de controle. 125 Reconhecida a combinação de parâmetros mais indicada restava pendente a explicação do parâmetro de maior responsabilidade no comportamento tendencioso do algoritmo de reduzir as amostras de dados submetidas em quantidades próximas a 50%. O estudo do mecanismo de geração aleatória revelou que os indivíduos gerados aleatoriamente apresentavam percentuais de generalização próximos entre si e sempre próximos a 50%. Esse fato ensejou algumas modificações na forma de geração da população inicial do algoritmo, vindo a aumentar a amplitude dos resultados obtidos posteriormente e eliminando a tendência de generalização de 50% a cada iteração. O maior peso exercido pela população inicial no resultado dos testes aponta uma característica importante do algoritmo genético implementado. Uma vez definidos os indivíduos que compõem uma população, o papel do sistema resume-se a selecionar os melhores indivíduos, segundo um critério específico, e estabelecer recombinações visando à evolução ou a adaptação das soluções ao problema proposto. Entretanto, esse poder de melhoria das soluções é limitado, não sendo possível ao algoritmo atingir resultados de generalização muito diferentes da média dos indivíduos gerados na população inicial. O sistema é, portanto, limitado no sentido de geração de novas soluções uma vez que indivíduos de quaisquer qualidades podem ser gerados e passar por cruzamentos. Além disso, ficou comprovado que a baixa variabilidade da população inicial limita o espaço de busca inicial e reduz ainda mais a capacidade de geração de novas soluções. Esse fato ficou latente com os testes de geração da população inicial com percentual de generalização fixo: todos os resultados apresentaram pequena discrepância com relação aos indivíduos gerados inicialmente. Um terceiro grupo de testes realizados teve por objetivo avaliar a qualidade dos modelos generalizados. Esses novos testes consistiram em séries de iterações onde o modelo resultado de uma iteração é utilizado como modelo inicial na iteração subseqüente, sendo aqui denominados de generalização sucessiva. Os resultados dos primeiros testes de generalização sucessiva apontaram um comportamento irregular da aptidão baseada nos volumes dos modelos solução. Seus valores apresentaram tendências alternadas de crescimento e de redução, à medida que ocorre a redução na quantidade de pontos. Na prática, esse fato significou a formação de conformações de pontos com altos níveis de generalização cujos modelos formados apresentavam valores muito próximos ao valor volume do modelo original. 126 Segundo o critério expresso na função aptidão o algoritmo procurou estabelecer combinações que minimizassem seus valores, independentemente da qualidade dos modelos resultantes gerados. Isso demonstra dois pontos principais: primeiro a capacidade de otimização desses sistemas de algoritmos genéticos, aptos a explorar simultaneamente um grande número de combinações de soluções para um problema e de obter resultados de melhor aptidão. Segundo, a função aptidão é um dos componentes de maior importância em um algoritmo genético e, como tal, deve ser desenvolvida da forma mais completa possível, abrangendo os principais parâmetros que afetem as soluções. A função aptidão proposta inicialmente contou como único componente o valor da diferença de volume entre modelos. Os testes, entretanto, demonstraram não ser um critério completo em virtude da possibilidade de geração de modelos amplamente generalizados e modificados, mas com valores de volumes muito próximos ao volume do modelo original. Esse fato motivou a pesquisa de novos parâmetros de possível inserção na população inicial. Foi testada a inserção dos valores de área plana e de área superficial como parâmetros auxiliares, por apresentarem variações razoavelmente uniformes e com tendências predominantes de crescimento. A nova função aptidão passou a ter uma configuração de média aritmética das diferenças percentuais de área pana, de área superficial e de volume. Dos novos valores inseridos cabe destaque à área plana que apresentou variações mais regulares sem oscilações. A área superficial mostrou-se mais sensível à redução de pontos, atingindo valores próximos a 40% em alguns casos, bem acima das diferenças encontradas para a área plana e para o volume. A rigor nenhum dos parâmetros inseridos na função aptidão apresentou crescimento constante. A variabilidade dos testes encontrados pode ser decorrente também da capacidade de otimização do algoritmo genético. A verificação da qualidade dos modelos generalizados foi realizada por meio da comparação visual direta. Esse método, por ser subjetivo, dificulta a quantificação exata de deformações e dificulta o reconhecimento de limites de generalização dos modelos. A grande variabilidade dos testes, o comportamento inconstante dos parâmetros em alguns casos e as dificuldades intrínsecas de comparação visual de modelos tornam a análise dos parâmetros e a identificação de padrões complexas. Para as três amostras, os valores limiares dos parâmetros de área plana e área superficial encontrados – valores além dos quais foram gerados modelos com grandes deformações – não foram constantes para os testes realizados. 127 O estabelecimento de limites de generalização certamente só poderá ser feito com um conhecimento bem definido das alterações impostas aos modelos generalizados. Em termos técnicos, esse conhecimento e quantificação das alterações passam pela montagem correta da função aptidão na generalização de modelos. De certo modo, ao se considerar modelos tridimensionais, a quantificação de seus principais aspectos não pode ser feita com poucos valores numéricos mas a partir de um conjunto de parâmetros relevantes. Definir esses parâmetros certamente é o maior desafio. Por fim, ressalta-se que algoritmos genéticos mostraram-se uma promissora ferramenta na generalização de modelos digitais para pesquisas futuras. Apresentaram capacidade de exploração de um grande número de soluções e de otimização dos resultados. São métodos ainda bem flexíveis que facultam ao usuário a escolha de uma gama de parâmetros voltados para a otimização de um problema. Exigem, entretanto, um correto e adequado conhecimento do problema que se deseja otimizar para a correta construção da função aptidão e alcance de soluções desejáveis. Por isso, o uso de algoritmos genéticos na generalização de modelos digitais demanda um conhecimento apropriado acerca da prática de generalização. 128 7.2 SUGESTÕES PARA TRABALHOS FUTUROS Como sugestões de possíveis pesquisas para dar continuidade ao presente trabalho, ressalta-se: 1) estudo de uma codificação real para os cromossomos em sistemas de algoritmos genéticos para generalização de modelos digitais. A codificação real pode permitir a consideração de amostras com quantidades maiores de pontos, sem o peso de cadeias binárias muito extensas; 2) inserção e teste de novos operadores genéticos de cruzamento e de mutação, e verificação mais detalhada da influência das taxas de cruzamento; 3) realização de testes com outras amostras de dados; 4) estudo de um algoritmo genético com estrutura de indexação capaz de atuar simultaneamente em pequenas áreas de uma amostra com características homogêneas de relevo. Esse fato equivale à formação de diferentes populações e passando por evolução simultaneamente em porções separadas de um mesmo modelo, atuando preferencialmente em ambiente de paralelismo; 5) pesquisa de outros parâmetros para inserção na função aptidão, capazes de traduzir a perda de qualidade dos modelos; 6) inserção de novos parâmetros e testes de atribuição de pesos diferenciados para aqueles parâmetros que apresentarem um comportamento previsível e forem mais sensíveis a pequenas variações do modelo; 7) pesquisa da inserção de mecanismos de controle de qualidade para a geração de indivíduos da população inicial. A geração de indivíduos mais aptos na população inicial pode aumentar a capacidade do algoritmo de melhorar os resultados. O estudo também mais detalhado de outros operadores de mutação e de suas respectivas taxas pode servir para aumentar a capacidade de procura do algoritmo dentro do espaço de soluções possíveis; 8) pesquisa detalhada do critério de pontos de controle como função aptidão, envolvendo parâmetros como sua quantidade e distribuição. 129 8 REFERÊNCIAS BIBLIOGRÁFICAS ASSUNÇÃO, Márcio Geovani T., et al.. Filtragem e Classificação de Pontos LIDAR para Geração de Modelos Digitais do Terreno. In: XIII Simpósio Brasileiro de Sensoriamento Remoto [online], 2007, Florianópolis, Anais eletrônicos. São Paulo: Instituto Nacional de Pesquisas Espaciais. p. 3681-3688. Disponível: http://marte.dpi.inpe.br/col/dpi.inpe.br/sbsr%4080/2006/ 11.14.21.45 /doc/3681-3688.pdf [Capturado em 10 dez 2007]. ARNAUT, A. A. Metodologia Para Conversão Da Representação 2D Para 3D Do Relevo. Dissertação (Mestrado em Engenharia Cartográfica). Instituto Militar de Engenharia – IME. Rio de Janeiro, 2001. BÄCK, Thomas; HAMMEL, Ulrich; SCHWEFEL, Hans P. Evolutionary Computation: Comments on the History and Current State IEEE Transactions on Evolutionary Computation, Vol .1, No 1, April 1997. D'ALGE, J.C., GOODCHILD, M.F. Generalização Cartográfica, Representação do Conhecimento e GIS. In: VIII SIMPÓSIO BRASILEIRO DE SENSORIAMENTO REMOTO - SBSR, 1996, Salvador, Brasil. Anais.[online], 1996. Disponível: http://marte.dpi.inpe.br/col/sid.inpe.br/deise/1999/01.28.11.14/doc/T125.pdf [Capturado em 15 mai 2008]. DE JONG, KENETH ALAN. Analysis of the Behavior of a Class of Genetic Adaptive Systems. Dissertation (Doctor in Philosophy – Computer and Comunication Sciences) . The University of Michigan. College of Literature, Science, and the Arts. Computer and Comunication Sciences Departament. 1975. 271 p. ESRI SUPPORT CENTER ONLINE - ArcScripts Acesso em 06 de abril de 2008. ARCOBJECTS ONLINE - http://edndoc.esri.com/arcobjects/8.3/ Acesso em 08/04/2008. FELGUEIRAS, C. A., CÂMARA, G. Modelagem Numérica de Terreno. In: CÂMARA, Gilberto; DAVIS, Clodoveu; et al.. Introdução à Ciência das Geoinformação. Instituto Nacional de Pesquisas Espaciais São José dos Campos, [online] 2001. São Paulo. Disponível: http://www. dpi.inpe.br/gilberto/livro/introd/ . [Capturado em 29 jan de 2008]. FIRKOWSKI, Henrique. Generalização Cartográfica de Grades Retangulares Regulares Baseada na Teoria Matemática da Comunicação. Tese (Doutorado em Ciências Geodésicas). Setor de Ciências da Terra - Universidade Federal do Paraná-UFPr. Curitiba 2002. 158 p. FIRKOWSKI, Henrique . Relacionamento Entre Linhas de Grade de um MDT e o Conceito de Entropia da Teoria da Informação. In: XXI Congresso Brasileiro de Cartografia [online], 2003, Belo Horizonte. Anais eletrônicos. Disponível: http://www.cartografia.org.br/xxi_cbc/213-G36.pdf [Capturado em 7 mar 2008]. GABOARDI, Clóvis; FIRKOWSKI, Henrique. A Utilização da Transformada Wavelet e da Transformada de Fourier na Generalização de Modelo Digital do Terreno 130 (MDT). In: Congresso Brasileiro de Cadastro Técnico Multifinalitário [online], 2006, Florianópolis. Anais Eletrônicos. Disponível: http://ufsc.br/Geodesiaonline/arquivo/cobrac_2006/135.pdf [Capturado em: 7 mar 2008]. GOMES, Francisco Roberto da Rocha. Avaliação de Discrepâncias entre Superfícies no Espaço Tridimensional. Dissertação (Mestrado em Engenharia Cartográfica). Instituto Militar de Engenharia – IME. Rio de Janeiro 2006. 61 p.. GRUNREICH, D. Developmente of computer-assisted generalization on the basis of cartografic model theory. In: MULLER, J.C.,et al. GIS and Generalization Methodology and Practice. London: Taylor & Francis, 1995.p 47-75. HINTERDING, R., MICHALEWICZ, Z., AND EIBEN, A.E., Adaptation in Evolutionary Computation: A Survey. In: Proceedings of the 4th IEEE International Conference on Evolutionary Computation, Indianapolis, Abril 13-16, 1997, p.65-69. Disponível em: http://www.cs.adelaide.edu.au/~zbyszek/papers.html [Capturado em 07 de julho de 2008]. ISSMAEL, Linda Soraya. Generalização Cartográfica: Determinação de Operadores e de Escalas Catastróficas. Dissertação (Mestrado em Engenharia Cartográfica). Instituto Militar de Engenharia - IME. Rio de Janeiro 2003. 249 p.. JOÃO, E. M. . The importance of quantifying the effects of generalization. In: MULLER, J.C., et al. GIS and Generalization - Methodology and Practice. London: Taylor & Francis, 1995. p183-193. KANG, TSUNG CHANG. Programming ArcObjects With VBA: A Task Oriented Approach. 2th Edition. CRC Press. ISBN: 978-1-58488-580-1. 342p. LACERDA, Estéfane G. M., CARVALHO, André C.P.L. F.. Introdução aos Algoritmos Genéticos. In: GALVÃO, Carlos Oliveira; VALENÇA, Mêuser Jorge Silva; et al. Sistemas Inteligentes – Aplicações a Recursos Hídricos e Ciências Ambientais. 1.ed. Porto Alegre: UFRGS/ABRH,1999. p. 99 – 148. ISBN: 85-7025-527-6. MICHALEWICZ, Z., A Perspective on Evolutionary Computation. In: Workshop on Evolutionary Computation, November 21-22, 1994, University of New England, Armidale, Australia, p. 76-93. Disponível em: http://www.cs.adelaide.edu.au/~zbyszek/papers.html [Capturado em 07 de julho de 2008]. MOREHOUSE, S. GIS-based map compilation and generalization. In: MULLER, J.C.,et al. GIS and Generalization - Methodology and Practice. London: Taylor & Francis, 1995.p 21-30. MÜLLER, J.C., et al. Generalization: State of the Art and Issues. In: MULLER, J.C.,et al. GIS and Generalization - Methodology and Practice. London: Taylor & Francis, 1995. p. 3-18. ROBINSON, G.J. . A hierarchical top-down bottom-up approach to topographic map generalization. In: MULLER, J.C.,et al. GIS and Generalization - Methodology and Practice. London: Taylor & Francis, 1995. p 235-245. 131 RUAS, A., LAGRANGE J.P. . Data and knowledge modelling for generalization. In: MULLER, J.C.,et al. GIS and Generalization - Methodology and Practice. London: Taylor & Francis, 1995. p 73-90. SILVA, ALYSSON C.A. Calibração Automática de Rugosidade de Tubulações em Sistemas de Distribuição de Água com Aplicação de Algoritmos Genéticos. Dissertação (Mestrado em Engenharia – Área de Concentração: Recursos Hídricos). Universidade Federal do Ceará. Fortaleza. 2006. SIMÕES, M. G. Modeladores Digitais de Terreno em Sistemas de Informação Geográfica. Tese (M.Sc, Engenharia de Sistemas e Computação). Universidade Federal do Rio de Janeiro – COPPE. 167 p. Rio de Janeiro. [online] 1993. Disponível em: http://www.inf.ufrgs.br/~rmpillat/Art4.pdf [Capturado em 15 out 2007]. SPIESS, E. The need for generalization in a GIS environment. In: MULLER, J.C.,et al. GIS and Generalization - Methodology and Practice. London: Taylor & Francis, 1995. p 31-46. WEIBEL, R. Three essential building blocks for automated generalization. In: MULLER, J.C.,et al. GIS and Generalization - Methodology and Practice. London: Taylor & Francis, 1995. p 56-70. 132