Upload
others
View
0
Download
0
Embed Size (px)
Citation preview
UNIVERSIDADE FEDERAL DE UBERLÂNDIA
FACULDADE DE ENGENHARIA ELÉTRICA
PÓS-GRADUAÇÃO EM ENGENHARIA ELÉTRICA
GERAÇÃO DE ROTAS URBANAS VIRTUAIS
USANDO ALGORÍTMOS GENÉTICOS
ELIANE RAIMANN
Uberlândia, Agosto de 2007
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
UNIVERSIDADE FEDERAL DE UBERLÂNDIA
FACULDADE DE ENGENHARIA ELÉTRICA
PÓS-GRADUAÇÃO EM ENGENHARIA ELÉTRICA
GERAÇÃO DE ROTAS URBANAS VIRTUAIS USANDO
ALGORÍTMOS GENÉTICOS
ELIANE RAIMANN
Dissertação apresentada à Universidade Federal de Uberlândia, perante a Banca
Examinadora abaixo, como parte dos requisitos necessários á obtenção do título de
Mestre em Ciências.
Alexandre Cardoso, Dr. (Orientador) – UFU
Edgard Lamounier Afonso Júnior (Co-Orientador) – UFU
Keiji Yamanaka – UFU
Márcio Sarroglia Pinho – PUCRS
Dados Internacionais de Catalogação na Publicação (CIP)
R153g
Raimann, Eliane. Geração de rotas urbanas virtuais usando algoritmos genéticos / Eliane Raimann. - 2007. 111 f. : il. Orientador: Alexandre Cardoso. Co-orientador: Edgard Lamounier Afonso Júnior. Dissertação (mestrado) – Universidade Federal de Uberlândia, Programa de Pós-Graduação em Engenharia Elétrica. Inclui bibliografia.
1. 1. Realidade virtual - Teses. 2. Algoritmos genéticos - Teses. I. Cardoso, Alexandre. II. Lamounier Júnior, Edgard. III. Universidade Federal de Uberlândia. Programa de Pós-Graduação em Engenha-ria Elétrica. III. Título.
CDU: 681.3:007.52
Elaborado pelo Sistema de Bibliotecas da UFU / Setor de Catalogação e Classificação
GERAÇÃO DE ROTAS URBANAS VIRTUAIS USANDO
ALGORÍTMOS GENÉTICOS
ELIANE RAIMANN
Texto da Dissertação apresentada por Eliane Raimann à Universidade
Federal de Uberlândia, como parte dos requisitos necessários á obtenção do título
de Mestre em Ciências.
_____________________________
Prof. Dr. Alexandre Cardoso
Orientador
_________________________________
Prof. Dr. Darizon Alves de Andrade
Coordenador do Curso de Pós-Graduação
i
DEDICATÓRIA
A todas as pessoas que amo e
admiro nesta vida,
pelo apoio,
compreensão,
força e incentivo necessário.
Sem vocês nada teria sentido.
ii
AGRADECIMENTOS
Agradeço primeiramente a Deus, que me fortaleceu nos momentos de
fraquezas e dificuldades e permitiu a finalização de mais uma etapa em minha vida e
principalmente pela impressionante forma como Ele se revela a cada instante,
mostrando os caminhos.
À minha família e à minha amada filha, por todo amor recebido, que me
sustenta e me faz sonhar.
Aos meus Orientadores, Alexandre, Edgard e Marcos Wagner Ribeiro,
obrigado pela paciência e dedicação durante todo o tempo.
E, a todos aqueles que contribuíram de forma direta ou indireta para a
realização deste trabalho.
MUITO OBRIGADA!
iii
RESUMO
Hoje em dia, o alto grau de complexidade imposta por tarefas em diversas áreas
está exigindo mais do homem do que seus sentidos naturais podem lhe oferecer. O
emprego de técnicas de Realidade Virtual pode auxiliar na melhora da percepção,
interação e conseqüentemente a produtividade no dia a dia. Baseando-se nesta
idéia, este trabalho tem como objetivo criar uma aplicação que forneça ao usuário
informações a respeito de rotas urbanas virtuais. Esta dissertação apresenta uma
arquitetura para construção de um ambiente virtual que reproduz rotas urbanas
virtuais tendo como instrumento de busca da melhor rota, um algoritmo baseado na
computação evolutiva, denominado Algoritmo Genético, e, como instrumento de
visualização do cenário da rota virtual, ruas de uma cidade em três dimensões, a
Realidade Virtual. Um protótipo foi construído tendo como referência um bairro de
uma cidade visto sob dois pontos de vista. O primeiro em duas dimensões
permitindo a escolha de um ponto inicial (origem) e o ponto final (destino) e o
caminho a ser percorrido entre os pontos com a menor distância possível. Por se
tratar de um problema probabilístico, onde existem inúmeras possibilidades de
solução, os algoritmos genéticos foram escolhidos por possibilitarem enquadramento
neste tipo de problema. O segundo ponto de vista, em três dimensões, além de
oferecer ser ambiente virtual com possibilidades de navegação livre pelo cenário de
uma cidade, proporciona ao usuário uma navegação pelo caminho construído pelo
modelo 2D. O modelo 3D foi construído com o apoio da biblioteca gráfica OpenGL e
o modelo geométrico da cidade foi desenhado com o uso de uma ferramenta
específica de modelagem gráfica sendo importada para o protótipo. O sistema utiliza
para os dois pontos de visão (2D e 3D) o mesmo modelo, o que proporciona uma
portabilidade em relação aos cenários (cidades), ou seja, basta ter um modelo
geométrico de um bairro ou cidade para o funcionamento da aplicação. O sistema foi
avaliado por pesquisadores e usuários específicos e os resultados alcançados
permitiram concluir que o mesmo é eficaz e aplicável.
Palavras-Chave: Algoritmos Genéticos, Rotas Virtuais, Realidade Virtual
iv
ABSTRACT
Nowadays, the high level of complexibility designated by duties in many areas are
expecting more from the man his natural senses can offered him. The use of Virtual
Reality techniques can auxiliate the development of perception, interaction and
consequently the every day productivity. Basing it in this idea, this research has as
objectivity to create an application to offer the user information about the virtual urban
rotes. This dissertation present a architecture for construction of a virtual environment
which reproduce virtual urban rotes having as instrument the search of the best rote,
a algorithm based on evolutive computation, denominated Genetic Algorithm, and, as
instrument of visualization of the scene of the virtual rote, streets of a city in three
dimensions, a Virtual Reality. A prototype was built having as references a
neighborhood of a city seen under two points of view. The first one in two dimensions
allowing the choice of a start point (origin) and an end point (destiny) and a way to be
covered between the points with the shortest distance possible. For treating of a
probabilistic problem, where there are innumerous possibilities of solution, the
genetic algorithm were choose for making framing in this type of problem possible.
The second point of view, in three dimensions, beyond offer to be virtual environment
with possibilities of free navigation on the scene of a city, proportionate to the user
navigation for ways built by the model 2D. The 3D model was built with the support of
the graphic library OpenGL and the geometric model of the city was drawn with the
use of a specific tool of graphic modeling been imported to the prototype. The system
use for both points of view (2D and 3D) the same model, which proportionate a
portability in relation to the scenes (cities), so it’s enough to have a geometric model
of a neighborhood or city to the application functioning. The system was evaluated by
researchers and specific users and the results reached allowed concluding that the
same is efficient and applicable.
Key words: Genetic Algorithm, Virtual Rotes, Virtual Reality
v
PUBLICAÇÕES
A seguir é apresentada a publicação resultante deste trabalho:
RAIMANN, Eliane; CARDOSO, Alexandre; RIBEIRO, Marcos Wagner de
Souza; LAMOUNIER, Edgard Jr. Modelagem de Rotas Turísticas Urbanas
usando Algoritmos Genéticos. Workshop de Aplicações em Realidade Virtual, II,
2006, Refice. Anais... Recife-PE: UFPE, 2006. 01 CD-ROM.
RAIMANN, Eliane; CARDOSO, Alexandre; RIBEIRO, Marcos Wagner de
Souza; LAMOUNIER, Edgard Jr. Determinação de Rotas Urbanas 3D Usando
Algoritmos Genéticos. IX Symposium on Virtual and Augmented Reality – SVR
2007, Proceedings. Petrópolis, RJ.
vi
SUMÁRIO
CAPITULO I ................................................................................................................1
1 INTRODUÇÃO.......................................................................................................1
1.1 Considerações Iniciais......................................................................................1
1.2 Contribuições desse trabalho ...........................................................................3
1.3 Objetivos...........................................................................................................4
1.4 Organização da Dissertação ............................................................................5
CAPITULO II ...............................................................................................................6
2 REALIDADE VIRTUAL E ALGORITMOS GENÉTICOS.......................................6
2.1 Realidade Virtual ..............................................................................................6
2.1.1 Imersão, Envolvimento e Interação................................................................7
2.1.2 Tipos de Sistemas de Realidade Virtual ........................................................8
2.1.3 Ambientes Virtuais .........................................................................................8
2.1.4 Modelagem de Mundos Virtuais...................................................................10
2.1.4.1 Modelagem Geométrica ....................................................................11
2.2 Algoritmos Genéticos......................................................................................11
2.2.1 Conceito e Definição de um AG...................................................................12
2.2.2 Vantagens e Desvantagens dos Algoritmos Genéticos ...............................13
2.2.3 Definições Básicas.......................................................................................14
2.2.4 Parâmetros Genéticos .................................................................................15
2.2.5 Métodos e Critérios para Implantação de um AG ........................................16
2.2.6 Seleção dos Indivíduos................................................................................17
2.2.7 Reprodução / Cruzamento (Crossover) .......................................................20
2.2.7.1 Operadores de Cruzamento - Crossover ..........................................23
2.2.8 Mutação .......................................................................................................25
2.2.9 Diversidade nos AG’s ..................................................................................26
2.2.9.1 Convergência x Elitismo....................................................................26
2.2.9.2 Pressão Seletiva ...............................................................................27
2.2.10 Condições de Término.................................................................................27
CAPITULO III ............................................................................................................29
3 TRABALHOS RELACIONADOS ........................................................................29
vii
3.1 Introdução.......................................................................................................29
3.2 Aplicação da Generalização Cartográfica em Mundos Virtuais ......................29
3.3 Aplicação de AG’s no Desenvolvimento de Rotas Turísticas. ........................30
3.4 Construção e Gestão da Complexidade de Cenários Urbanos 3D em AV’s
Imersivos. 31
3.5 O uso de Algoritmos Genéticos na solução de Rotas em trechos urbanos ....32
3.6 Roteamento de Veículos Dinâmico usando AG’s ...........................................33
3.7 Sistema Melhor Roteiro Belém. ......................................................................35
3.8 Otimização de Rotas de Veículos baseada em Operadores Genéticos. ........36
3.9 Uma Proposta de AG’s de Duas Fases para Roteamento .............................37
3.10 Uso de AG’s em Sistema de Apoio à Decisão................................................38
3.11 Uso de AG’s na Construção de Rotas Turísticas ...........................................39
3.12 Tabela Comparativa entre os trabalhos avaliados..........................................40
3.13 Considerações Finais .....................................................................................43
CAPÍTULO IV............................................................................................................44
4 ARQUITETURA DO SISTEMA............................................................................44
4.1 Introdução.......................................................................................................44
4.2 Tecnologia de apoio .......................................................................................44
4.2.1 OPENGL......................................................................................................45
4.3 Módulos da Arquitetura do Sistema................................................................46
4.3.1 Módulo Mapas .............................................................................................47
4.3.2 Módulo AG...................................................................................................47
4.3.3 Módulo AV ...................................................................................................47
4.4 Engenharia de Software/Engenharia de Requisitos .......................................48
4.4.1 Diagrama de Caso de Uso (Use Case)........................................................48
4.4.2 Casos de Uso ..............................................................................................48
4.4.2.1 Caso de Uso: Estabelecer ponto inicial e final no mapa ...................50
4.4.2.2 Caso de Uso: Definir taxa de cruzamento para o algoritmo..............51
4.4.2.3 Caso de Uso: Definir número de gerações para o algoritmo.............52
4.4.2.4 Caso de Uso: Executar o algoritmo em busca da melhor solução ....53
4.5 Considerações Finais .....................................................................................54
CAPÍTULO V.............................................................................................................55
5 DETALHES DA IMPLEMENTAÇÃO...................................................................55
viii
5.1 Introdução.......................................................................................................55
5.2 Estrutura do Cromossomo..............................................................................55
5.3 Geração do Melhor Indivíduo .........................................................................56
5.4 Definição da Aptidão (Fitness)........................................................................57
5.5 Codificação do Cromossomo..........................................................................58
5.6 Criação da População ....................................................................................58
5.7 Método de Seleção.........................................................................................59
5.8 Método de Cruzamento ..................................................................................61
5.9 Criação dos objetos ........................................................................................63
5.10 Modelagem Geométrica .................................................................................64
5.11 Conversão de Formatos .................................................................................65
5.12 Navegação e Visualização .............................................................................65
5.13 Desenvolvimento do Ambiente Virtual ............................................................67
5.14 Considerações Finais .....................................................................................67
CAPÍTULO VI............................................................................................................68
6 FUNCIONAMENTO DO SISTEMA......................................................................68
6.1 Introdução.......................................................................................................68
6.2 Parâmetros Genéticos ....................................................................................68
6.3 Processamento e Resultado...........................................................................69
6.4 Considerações Finais .....................................................................................75
CAPÍTULO VII...........................................................................................................77
7 RESULTADOS / LIMITAÇÕES ...........................................................................77
7.1 Introdução.......................................................................................................77
7.2 Ambiente Experimental...................................................................................77
7.3 Análise dos Resultados Obtidos.....................................................................77
7.3.1 Comparação com outros trabalhos ..............................................................78
7.4 Avaliação do Sistema .....................................................................................80
7.4.1 Quanto à finalidade do uso da ferramenta: ..................................................80
7.4.2 Quanto à interface com o usuário: ...............................................................81
7.4.3 Quanto à facilidade de uso: .........................................................................81
7.4.4 Quanto aos recursos do programa ..............................................................82
7.5 Considerações Finais .....................................................................................83
CAPITULO VIII..........................................................................................................85
ix
8 CONCLUSÕES E TRABALHOS FUTUROS.......................................................85
8.1 Introdução.......................................................................................................85
8.2 Conclusões.....................................................................................................85
8.3 Trabalhos Futuros ..........................................................................................86
REFERÊNCIAS BIBLIOGRÁFICAS.........................................................................87
APÊNDICE................................................................................................................92
x
LISTA DE FIGURAS
Figura 2.1. Seis graus de liberdade. (RIBEIRO, 2006)................................................9
Figura 2.2 - Sistema de Desenvolvimento de RV (KIRNER, 1997). ..........................10
Figura 2.3. Equação de probabilidade de seleção. Fonte (JUNIOR, 2000)...............18
Figura 2.4. Exemplo de seleção por roleta. Fonte (BARCELLOS, 2000) ..................19
Figura 2.5. Cruzamento de um ponto. Fonte (TEIXEIRA, 2004) ...............................21
Figura 2.6. Cruzamento de dois pontos. Fonte (TEIXEIRA, 2004)............................22
Figura 2.7. Cruzamento uniforme. Fonte (TEIXEIRA, 2004) .....................................23
Figura 2.8. Exemplo do Partially Mapped Crossover (PMX). Fonte (SOUZA, 2004).24
Figura 2.9 Exemplo do Cycle Crossover (CX). Fonte (SOUZA, 2004) ......................24
Figura 2.10. Exemplo do Operador de Mutação. Fonte (TEIXEIRA, 2004)...............25
Figura 3.1 - Generalização Cartográfica em Mundos Virtuais. ..................................30
Figura 3.2 - Algoritmos Genéticos no Desenvolvimento de Rotas Turísticas............31
Figura 3.3 - Construção e Gestão da Complexidade de Cenários Urbanos 3D em
AV’s Imersivos. ..................................................................................................32
Figura 3.4 - Algoritmos Genéticos na solução de rotas em trechos urbanos. ...........33
Figura 3.5 - Roteamento de Veículos Dinâmico usando AG’s. .................................34
Figura 3.6 - Sistema Melhor Roteiro Belém. .............................................................35
Figura 3.7 - Otimização de Rotas de Veículos baseada em Operadores Genéticos.37
Figura 3.8 - AG’s de Duas Fases para Roteamento de Veículos. .............................38
Figura 3.9 - AG’s em Sistema de Apoio à Decisão para Alocação de Recursos no
Campo e na Cidade. ..........................................................................................39
Figura 3.10 - AG’s na Construção de Rotas Turísticas . ...........................................40
Figura 4.1. Versão simplificada do pipeline OpenGL (WOO, 1999). .........................46
xi
Figura 4.2. Arquitetura do Sistema - Integração entre AG e RV................................47
Figura 4.4. Diagrama de Use-Case...........................................................................49
Figura 4.5. Use-Case “Estabelecer ponto inicial e final no mapa”.............................50
Figura 4.6. Use-Case “Definir taxa de cruzamento para o algoritmo”. ......................51
Figura 4.7. Use-Case “Definir número de gerações para o algoritmo”. .....................52
Figura 4.8. Use-Case “Executar o algoritmo em busca da melhor solução”. ............53
Figura 5.1. Estrutura do Cromossomo (Indivíduo).....................................................55
Figura 5.2. Pseudocódigo da geração da população. ...............................................56
Figura 5.3. Composição do indivíduo final. ...............................................................56
Figura 5.4. Equação para cálculo da aptidão. ...........................................................57
Figura 5.5. Composição do indivíduo final. ...............................................................58
Figura 5.6. Estrutura da População...........................................................................59
Figura 5.7. Pseudocódigo da seleção por roleta. ......................................................61
Figura 5.8. Pseudocódigo do Cruzamento. ...............................................................62
Figura 5.9. Exemplificação do cruzamento do híbrido do PMX. ................................63
Figura 5.10. Modelador 3D (3D Studio Max). ............................................................64
Figura 5.11. Código para importação do arquivo 3DS. .............................................65
Figura 5.12 Código que implementa a navegação e visualização do ambiente. .......66
Figura 5.13. Pseudo-código que implementa a navegação automática. ...................66
Figura 5.14. Barra de navegação do ambiente. ........................................................67
Figura 6.1. Parâmetros Genéticos.............................................................................68
Figura 6.2. Menu Conexões. .....................................................................................69
Figura 6.3. Interface inicial do sistema. .....................................................................70
Figura 6.4. Ponto Inicial e Ponto Final Definidos.......................................................71
Figura 6.5. Gráfico Menor Distância..........................................................................71
Figura 6.6 Interface após processamento. ................................................................72
xii
Figura 6.7 Botões Evoluir e Reiniciar. .......................................................................72
Figura 6.8 Menu Modelo de Visão.............................................................................73
Figura 6.9 Visão superior da Cidade Virtual. .............................................................73
Figura 6.10. Barra de Navegação do Sistema 3D. ....................................................74
Figura 6.11 Interface 3D do percurso. .......................................................................75
Figura 6.12 Visão do ambiente sem os objetos.........................................................75
Figura 7.1. Análise quanto à finalidade. ....................................................................80
Figura 7.2. Análise quanto a Interface.......................................................................81
Figura 7.3. Análise quanto à facilidade de uso..........................................................82
Figura 7.4. Análise quanto aos recursos do programa.............................................82
Figura 7.5. Análise dos aspectos de avaliação para softwares .................................83
xiii
LISTA DE TABELAS
Tabela 3.1. Principais características dos sistemas avaliados. .................................42
Tabela 4.1. Relação dos Casos de Uso. ...................................................................49
Tabela 4.2. Descrição do Caso de Uso ‘Estabelecer ponto inicial e final no mapa’. .50
Tabela 4.3. Descrição do Caso de Uso ‘Definir taxa de cruzamento para o algoritmo’.
51
Tabela 4.4. Descrição do Caso de Uso ‘Definir número de gerações para o
algoritmo’...................................................................................................................52
Tabela 4.5. Descrição do Caso de Uso ‘Executar o algoritmo em busca da melhor
solução’. ....................................................................................................................53
Tabela 6.1 Funções da Barra de Navegação. ...........................................................74
Tabela 7.1 Comparação com outros trabalhos..........................................................79
xiv
LISTA DE ABREVIATURAS E SIGLAS
2D – Bidimensional
3D – Tridimensional
AG – Algoritmo Genético
AGC - Algoritmo Genético Construtivo
API – Application Programming Interface
AV – Ambiente Virtual
CX – Operador Cycle
GUI – Graphics User Interface
HMD – Head Mounted Display
IA – Inteligência Artificial
OpenGL – Open Graphics Library
OX – Operador Order Crossover
PMX – Operador Partially Mapped Crossover
RV – Realidade Virtual
VRML – Virtual Reality Modeling Language
CAPITULO I – INTRODUÇÃO
1
CAPITULO I
1 INTRODUÇÃO
1.1 Considerações Iniciais
O grande avanço tecnológico ocorrido nas últimas décadas tem impulsionado
a modernização da Cartografia. Por conseqüência, é cada vez mais comum o uso de
mapas digitais em alternativa aos mapas impressos. A Realidade Virtual (RV) abre
um novo campo para a exploração de mapas digitais: a modelagem interativa
tridimensional. A Realidade Virtual tem possibilitado a modelagem de mundos
virtuais tridimensionais e através da Internet é possível a um grande número de
usuários acessá-los, a qualquer momento e sem nenhum custo. Assim, a
combinação da Cartografia com a Realidade Virtual torna-se possível para a criação
de um novo tipo de mapa, no qual o usuário poderá interagir com a representação, e
em alguns casos, até mesmo ter a sensação de fazer parte dela, através de um
processo imersivo ou semi-imersivo. (FOSSE, 2004).
Segundo MOORE (MOORE, 1999) essa “nova” Cartografia pode ser vista
como uma rica e sensorial combinação de mapas, modelos, sons e movimentos, em
que o usuário também poderá interagir com esse mapa. Além disso, o usuário
ganhará uma interface mais atraente que lhe proporcionará uma análise qualitativa
direta bem mais intuitiva que as já existentes. Em três dimensões pode-se prover
uma organização mais intuitiva de objetos espaciais, utilizando a percepção natural
e memória do usuário referente ao espaço e a relação espacial dos objetos
CAPITULO I – INTRODUÇÃO
2
representados. A Realidade Virtual estimula a atração e o entendimento do usuário
por meio de sua interatividade e dinamismo.
Segundo Pinho (PINHO, 2002), RV refere-se a uma tecnologia em que estão
agrupados meios através dos quais, o usuário pode livremente visualizar,
explorar/manipular e interagir dados complexos em um tempo real. Agrupando-se
alguns conceitos, pode-se dizer que a Realidade Virtual é uma técnica avançada de
interface, em que o usuário pode realizar a imersão (sensação de estar dentro do
ambiente virtual), navegação e interação em um ambiente tridimensional gerado por
computador.
Desta forma além da visualização em 3D e outras interações (permitir ao
usuário sair da rota, parar ou observar detalhes do caminho), a Realidade Virtual
(RV) pode ser útil criando um ambiente virtual a partir de um modelo em duas
dimensões.
Para construir a melhor rota urbana, uma das metodologias que pode ser
usada são os Algoritmos Genéticos, que sugerem a melhor rota a ser usada, em
termos de menor tempo e menor distância percorrida e atendimento aos pontos de
origem e destino previamente escolhidos. Como interface inicial, apenas um modelo
em 2D seria suficiente para o usuário que busca a melhor solução, porém a melhor
interface seria em 3D que oferece como resultado um passeio virtual pela rota
sugerida de acordo com a escolha do usuário. Desta forma além da visualização em
3D e outras interações (permitir ao usuário sair da rota, parar ou observar detalhes
do caminho), a Realidade Virtual pode ser útil criando um ambiente virtual a partir de
um modelo em duas dimensões.
Os AG’s possuem uma larga aplicação em muitas áreas científicas, entre as
quais podem ser citados problemas de otimização de soluções, aprendizado de
máquina, desenvolvimento de estratégias e fórmulas matemáticas, análise de
modelos econômicos, problemas de engenharia, diversas aplicações na Biologia
como simulação de bactérias, sistemas imunológicos, ecossistemas, descoberta de
formato e propriedades de moléculas orgânicas (POZO et al, 2000).
Os AG’s podem ser utilizados em várias aplicações. Em alguns casos em que
os métodos de busca exaustiva falham, e é necessário o uso de busca controlada
em espaço, eles são amplamente utilizados como otimizadores de funções. Sua
CAPITULO I – INTRODUÇÃO
3
vantagem sobre outros métodos neste aspecto é seu alto grau de adaptabilidade,
robustez e paralelismo (LUCAS, 2000) apud (ALMEIDA, 2005).
Entretanto, Andrade (ANDRADE, 2005) ressalta que em alguns problemas
podem não ter resultados satisfatórios ou não serem representados adequadamente
para o uso de técnicas de AG. Assim, é recomendável levar em consideração
algumas características relativas ao problema, antes de tentar usar as referidas
técnicas de Algoritmos Genéticos, como:
� O espaço de busca (possíveis soluções) do problema em questão deve
estar delimitado dentro de uma certa faixa de valores;
� Deve ser possível definir uma função de aptidão que indique quão boa ou
ruim é uma determinada resposta;
� As soluções devem poder ser codificadas de uma maneira que seja
relativamente fácil a sua implementação no computador.
A principal vantagem deles é que trabalham com população, ao contrário de
outros métodos que trabalham com um só ponto, avaliando apenas um candidato à
solução por vez. São muito flexíveis e aceitam uma infinidade de alterações na sua
implementação. Além disso, os AG’s têm resultados bastante aceitáveis com relação
à precisão e aos recursos empregados e pela ampla gama de problemas aplicáveis.
(MOREIRA e AGUIAR, 2005). Assim, ao desenvolver essa metodologia, será
facilitada a determinação de uma rota urbana, baseada na restrição dos
cruzamentos escolhidos, onde a melhor rota é determinada em um conjunto
específico de pontos definidos, e também na restrição dos sentidos, onde é possível
definir para qual outro ponto um determinado ponto pode ir, caracterizando as ruas
de mão única ou de mão dupla.
1.2 Contribuições desse trabalho
Este trabalho pretende contribuir com a descrição de uma abordagem
(arquitetura) que possibilite a criação de uma aplicação unindo duas áreas da
computação (Algoritmos Genéticos e Realidade Virtual) na construção de ambientes
virtuais que representem rotas virtuais, seguindo uma orientação dada pelo AG. Esta
aplicação facilitará a determinação de uma rota urbana, uma vez que, ao visitar a
CAPITULO I – INTRODUÇÃO
4
cidade pela primeira vez, e não souber a rota a percorrer, o usuário (um turista
provavelmente) poderia se perder ou demorar-se para atingir um destino.
Além de demonstrar que os Algoritmos Genéticos são capazes de solucionar
esse problema de forma otimizada, achando uma solução ótima, este trabalho
demonstra a importância do uso de técnicas de Realidade Virtual na melhoria da
visualização de cenários até então presos aos modelos em duas dimensões.
1.3 Objetivos
Esta dissertação tem por objetivo apresentar uma abordagem
computacional/algorítmica que seja suficiente para suportar o funcionamento de um
ambiente virtual (Cidade Virtual) que simule rotas de um ponto a outro de uma
cidade de acordo com o melhor caminho. Para atingir este objetivo, as seguintes
metas foram definidas:
1. Identificar um algoritmo que apresente eficácia na definição de rotas urbanas.
2. Escolher uma metodologia para elaboração do algoritmo, associada ao
estudo de caso específico (rotas urbanas).
3. Realizar a implementação de um protótipo, segundo a metodologia elaborada
no item anterior, visando a sua validação.
4. Implementar também no mesmo protótipo um ambiente virtual que simule as
rotas propostas pelo algoritmo.
5. Validar o protótipo junto a usuários, de forma a obter realimentação que
possibilite melhorias e adequações necessárias ao aprimoramento da
abordagem escolhida.
Durante o desenvolvimento deste trabalho, as seguintes estratégias foram
adotadas, norteando a consolidação do objetivo e metas propostas:
1. Modelagem de um bairro de uma cidade representando de forma genérica
qualquer referência urbana existente.
2. Implementar protótipo com demonstração da melhor rota numa visão 2D,
por meio de um algoritmo genético, seguindo as etapas:
CAPITULO I – INTRODUÇÃO
5
a. Composição da estrutura do indivíduo que representará a melhor
solução.
b. Definição dos mecanismos de seleção e cruzamento entre indivíduos.
c. Configuração dos parâmetros genéticos necessários na execução do
algoritmo.
d. Ampliar o modelo visão para três dimensões em forma de ambiente
virtual.
e. Aplicar o sistema a pesquisadores e usuários específicos da área.
1.4 Organização da Dissertação
O trabalho está dividido em oito capítulos, descritos resumidamente a seguir:
Capítulo I - Introdução: São apresentadas as considerações iniciais do
trabalho, assim como a motivação, os objetivos deste trabalho bem como a
organização da dissertação.
Capítulo II – Realidade Virtual e Algoritmos Genéticos: aborda o
referencial teórico com os principais conceitos sobre Realidade Virtual e Algoritmos
Genéticos, com suas características básicas e estrutura de funcionamento.
Capítulo III – Trabalhos Relacionados: Apresenta os Softwares existentes
relacionados à pesquisa.
Capítulo IV – Arquitetura do Sistema: Descreve a arquitetura do sistema, o
qual utilizará as técnicas de AG’s, para a determinação da melhor rota, e RV para a
visualização e interação da melhor rota determinada pelo sistema.
Capítulo V – Detalhes da Implementação: Apresenta a implementação do
sistema.
Capítulo VI – Funcionamento do Sistema: Descreve o funcionamento do
sistema proposto.
Capítulo VII – Resultados e Limitações: Apresenta as análises e resultados
obtidos com a implementação e teste do sistema, bem como as suas limitações.
Capítulo VIII – Conclusão e Trabalhos Futuros: Descreve as conclusões e
sugestões de trabalhos futuros.
CAPITULO II – REALIDADE VIRTUAL E ALGORITMOS GENÉTICOS
6
CAPITULO II
2 REALIDADE VIRTUAL E ALGORITMOS
GENÉTICOS
2.1 Realidade Virtual
Um dos recentes adventos do desenvolvimento tecnológico, que vem
firmando-se, como uma nova área da Computação é a Realidade Virtual. O termo
RV refere-se a uma experiência interativa baseada em imagens gráficas 3D geradas
em tempo-real por computador. Machover (MACHOVER, 1994) afirma que a
qualidade dessa experiência em RV é crucial, pois deve estimular ao máximo de
forma criativa e produtiva o usuário, a realidade precisa reagir de forma coerente aos
movimentos do participante, tornando a experiência consistente.
Segundo Kirner (KIRNER, 1997), RV pode ser considerada como uma
ferramenta para visualizar, manipular, explorar, interagir e modificar, através do
computador, dados complexos de uma forma natural, muito semelhante ao que se
faria no caso da ação sobre o dado real.
Uma outra definição um pouco mais refinada de RV é a seguinte: “uma forma
das pessoas visualizarem, manipularem e interagirem com computadores e dados
extremamente complexos" (AUKSTAKALNIS, 1992). Pode também ser definida
como sendo a forma mais avançada de interface do usuário de computador até
agora disponível (BYRNE, 2005), com aplicação na maioria das áreas do
CAPITULO II – REALIDADE VIRTUAL E ALGORITMOS GENÉTICOS
7
conhecimento, senão em todas, e com um grande investimento das indústrias na
produção de hardware, software e dispositivos de E/S especiais.
O uso da RV estende-se em várias áreas, porém com um destaque especial
para as áreas de simulação, que cria por meio do computador a sensação de
vivência de uma realidade, permitindo ao usuário a possibilidade de interferência
nessa “realidade”.
A RV pode possibilitar a criação /simulação de mundos reais ou imaginários
na tela do computador, com aplicação em diversas áreas, assumindo um papel de
relevo cada vez maior em campos específicos da vida econômica, social e cultural
de muitos países (CAMACHO, 2005).
2.1.1 Imersão, Envolvimento e Interação.
A idéia de imersão está ligada com o sentimento de se estar dentro do
ambiente, normalmente, um sistema imersivo é obtido com o uso de capacete de
visualização, mas existem também sistemas imersivos baseados em salas com
projeções das visões nas paredes, teto e piso, conhecido como CAVE (CRUZ-
NEIRA, 1992). Além do fator visual, os dispositivos ligados com os outros sentidos
também são importantes para o sentimento de imersão, como som, posicionamento
automático da pessoa e dos movimentos da cabeça, controles reativos, etc. A
visualização tridimensional pelo monitor é considerada de imersão subjetiva (ou não-
imersiva para alguns).
A idéia de envolvimento está ligada com o grau de motivação para o
engajamento de uma pessoa com determinada atividade. O envolvimento pode ser
passivo, como ler um livro ou assistir televisão, ou ativo, ao participar de um jogo
com algum parceiro (KIRNER, 1997). A RV tem potencial para os dois tipos de
envolvimento, ao permitir a exploração de um ambiente virtual e ao propiciar a
interação do usuário com um mundo virtual dinâmico.
A idéia de interação está ligada com a capacidade do computador detectar as
entradas do usuário e modificar instantaneamente o mundo virtual e as ações sobre
ele (capacidade reativa) (KIRNER, 1997).
CAPITULO II – REALIDADE VIRTUAL E ALGORITMOS GENÉTICOS
8
2.1.2 Tipos de Sistemas de Realidade Virtual
O que diferencia uma aplicação de RV é o tipo de interface entre o usuário e o
mundo virtual. Sob este aspecto, os tipos mais comuns são:
Sistemas Não-Imersivos: utilizam o monitor de computador para exibir o
mundo; Embora a RV com o uso de capacetes tenha evoluído e seja considerada
típica, com monitor apresenta ainda assim alguns pontos positivos como:
� Utilizar plenamente todas as vantagens da evolução da indústria de
computadores;
� Evitar as limitações técnicas e problemas decorrentes do uso de capacete;
� Facilidade de uso.
Sistemas Imersivos: são sistemas capazes de imergir completamente o
usuário no mundo virtual. Normalmente, esses sistemas são equipados com
capacetes (HMD), luvas especiais, cavernas ou outros dispositivos multi-sensoriais
(KIRNER, 1997).
Em alguns casos, como visualização, por exemplo, a RV com monitor é
aceitável, mas com a evolução da tecnologia, a tendência será a utilização de
capacetes ou salas de projeção (CAVE) para a grande maioria das aplicações
(KIRNER, 1997). Porém, no momento com a facilidade de uso de simples
computadores, há um crescimento acelerado no desenvolvimento de aplicações e
modelos em realidade virtual não imersiva.
Além desses dois principais tipos, outras formas comuns também podem ser
citadas, como a Teleprensença, Realidade Mista, Realidade Aumentada e
Virtualidade Aumentada (KIRNER, 1997).
2.1.3 Ambientes Virtuais
De acordo com Sementille (2000), um Ambiente Virtual (AV) é um ambiente
com o qual há a imersão do usuário em um ambiente tridimensional simulado. Um
AV também pode ser entendido como um sistema de software que cria a ilusão de
um mundo. Isto requer a combinação de entrada (interação do usuário), computação
(simulação de processos) e saída (estímulos multi-sensoriais).
CAPITULO II – REALIDADE VIRTUAL E ALGORITMOS GENÉTICOS
9
Os objetos no AV podem corresponder a objetos que existem no mundo real.
Quando isso acontece, espera-se que esses objetos reajam como os objetos reais.
Portanto, pode haver a necessidade de se modelar, no mínimo, uma parte da Física
(movimento e detecção de colisão entre objetos).
Alguns objetos no AV devem ser capazes de responder às ações dos
usuários e às ações de outros objetos: devem existir meios de especificar esses
comportamentos e associá-los aos objetos no modelo. Alguns objetos podem ter
comportamentos autônomos, como andar, por exemplo. Isto envolverá interações
entre os objetos e o tempo simulado dentro do ambiente. Existirá alguma
sobreposição entre as técnicas requeridas aqui e as técnicas que estão sendo
desenvolvidas em animação por computador e simulação.
Em um AV, o usuário deve poder navegar em três dimensões, ou seja, com
seis graus de liberdade. Cada grau se aplica a uma direção ou rotação do
movimento. Na verdade, conferem ao usuário a possibilidade de se movimentar em
seis direções simultâneas: translação em torno dos três eixos cartesianos (x, y e z) e
rotação em torno de cada um. A Figura 2.1 ilustra os seis graus de liberdade.
Figura 2.1. Seis graus de liberdade. (RIBEIRO, 2006)
CAPITULO II – REALIDADE VIRTUAL E ALGORITMOS GENÉTICOS
10
A modelagem visual de objetos é um dos processos consumidor de tempo,
exigindo, portanto, melhores ferramentas para suportá-la.
Uma vez que a produção de bons modelos exige considerável esforço, deve
existir algum mecanismo para o compartilhamento dos modelos existentes. Existem
dois aspectos para este compartilhamento:
� O primeiro aspecto: é a determinação de um formato padrão para a
codificação e a transmissão dos modelos (o formato deve ser capaz de
codificar toda a informação de modelagem, incluindo estrutura hierárquica,
propriedades físicas dos objetos, som e comportamento).
� O segundo aspecto: devem existir um ou mais lugares que armazenem,
mantenham e distribuam esses modelos.
2.1.4 Modelagem de Mundos Virtuais
A modelagem de mundos virtuais é de fundamental importância num sistema
de realidade virtual, definindo as características dos objetos como: forma; aparência;
comportamento; restrições; e mapeamento de dispositivos de E/S. Para isto, os
sistemas de desenvolvimento de realidade virtual levam em conta os diversos
aspectos de modelagem, mapeamento e simulação, conforme a Figura 2.2.
performance (BURDEA,G. & COIFFET,P, 1994) apud (KIRNER, 1997).
Figura 2.2 - Sistema de Desenvolvimento de RV (KIRNER, 1997).
CAPITULO II – REALIDADE VIRTUAL E ALGORITMOS GENÉTICOS
11
2.1.4.1 Modelagem Geométrica
A modelagem geométrica é um conjunto de várias descrições da forma dos
objetos virtuais através de polígonos, triângulos ou vértices, e sua aparência, usando
textura, reflexão da superfície, cores, etc.
As formas dos objetos podem ser criadas, usando-se bibliotecas gráficas,
como a biblioteca GL, ou usando-se modelos prontos de bancos de dados
comerciais ou digitalizadores tridimensionais. Esses objetos também podem ser
criados por programas CAD, como AutoCAD ou 3DStudio MAX, ou com o uso de
editores de realidade virtual. (WATT, A. & WATT, M., 1994) apud (KIRNER, 1997).
A aparência dada aos objetos esta relacionada principalmente com as
características de reflexão da superfície e com sua textura. Essa reflexão depende
do modelo de iluminação e sombreamentos por interpolação de Gourad; ou
interpolação de Phong. O sombreamento facetado é o mais simples e menos
realista, enquanto o de Phong é o mais complexo e mais realista.
Segundo Pinho (1997), a textura dos objetos é obtida a partir do
mapeamento de um padrão de textura do espaço bidimensional sobre os objetos
tridimensionais. Isto se dá como se um pedaço de plástico com o padrão da textura
fosse ajustado e colocado sobre o objeto, fazendo parte integrante dele. A textura
oferece várias vantagens para a realidade virtual, uma vez que aumenta o nível de
detalhe e de realismo de cena, fornece várias visões de profundidade, e permite a
redução substancial do número de polígonos da cena, propiciando o aumento da
taxa de quadros por segundo. (BURDEA,G. & COIFFET,P., 1994) apud (PINHO,
1997)
2.2 Algoritmos Genéticos
Os Algoritmos Genéticos (AG) pertencem a uma categoria de algoritmos
computacionais, inclusos nas técnicas de Inteligência Artificial (IA), os quais são
fundamentados no processo de seleção natural e buscam simular a evolução
biológica natural dos seres vivos e otimizando a resolução de questões que
necessitem da melhor solução. Uma grande aplicação dos AG’s é em problemas de
busca, onde dado um conjunto de elementos ou indivíduos, deseja-se encontrar
aquele ou aqueles que melhor atendam a certas condições especificadas.
CAPITULO II – REALIDADE VIRTUAL E ALGORITMOS GENÉTICOS
12
Algoritmo Genético é um algoritmo de procura baseado nos mecanismos de
seleção natural e genética natural. Ele combina a sobrevivência feita por uma função
de avaliação entre uma cadeia de caracteres com uma estrutura de informações
mudadas aleatoriamente, para formar um algoritmo de procura com algum talento
inovador, o mesmo de uma procura de um ser humano. Em toda geração, um novo
conjunto de criaturas artificiais (cadeia de caracteres) é criado usando bits e pedaços
do teste de avaliação da geração anterior; ocasionalmente uma parte nova é
testada. A procura mais eficiente das informações anteriores para especular os
pontos da nova procura resultam e um aumento na sua performance (GOLDBERG,
1989) apud (JUNIOR, 2000).
A natureza forneceu apenas a inspiração para o AG, mas não forneceu uma
descrição de suas operações. Conseqüentemente, enquanto a terminologia do
algoritmo e seu perfil ostentam suas raízes na evolução natural, ele cresceu além
dessas raízes, e agora representa a fusão dos Princípios Matemáticos e da
Evolução Natural (TEIXEIRA, 2004).
Os AG’s são muito eficientes para buscas de soluções ótimas ou
aproximadamente ótimas, e se for desenvolvido corretamente, a população (conjunto
de possíveis respostas) convergira à solução ótima, pois não impõem muitas das
limitações encontradas nos métodos de buscas tradicionais, sendo vistos como
otimizadores de funções.
Soluções ótimas, acontecem quando o valor da aptidão é a maior, ou seja,
quanto melhor o indivíduo, maior a probabilidade para melhor solução possível, pois
dentro das possibilidades geradas pelos cruzamentos dos indivíduos, e de acordo
com a quantidade de gerações, população e taxa de cruzamento configurado no
problema, o algoritmo tenta chegar na melhor resposta possível para os indivíduos
do problema.
2.2.1 Conceito e Definição de um AG
De acordo com Dalboni (2003), os AG’s são programas evolutivos, baseados
no princípio da seleção natural, onde os indivíduos mais aptos sobrevivem e os
menos aptos tendem a ser descartado; e da hereditariedade, onde as características
dos pais são transmitidas para os filhos. Assim, os candidatos mais promissores são
favorecidos para solucionar o problema específico.
CAPITULO II – REALIDADE VIRTUAL E ALGORITMOS GENÉTICOS
13
Junior (2000) relata que, de um modo geral, os algoritmos genéticos têm as
seguintes características:
� Operam numa população (conjunto) de pontos, e não a partir de um ponto
isolado;
� Operam num espaço de busca codificado, e não no espaço de busca
diretamente;
� Necessitam somente de informações sobre o valor de uma função aptidão
(objetivo para cada membro da população), e não requerem derivadas ou
qualquer outro tipo de conhecimento;
� Usam transições probabilísticas, e não regras determinísticas;
2.2.2 Vantagens e Desvantagens dos Algoritmos Genéticos
Segundo Andrade (2005), as vantagens do emprego de Algoritmos Genéticos
são consideráveis para os problemas de otimização, principalmente pela sua
versatilidade em obter soluções ótimas globais, enquanto que é possível sanar suas
desvantagens através do avanço das capacidades computacionais e de uma maior
consolidação da técnica.
Algumas das vantagens de se utilizar algoritmos genéticos são:
� Trabalham baseados na codificação do problema e oferecem suporte para a
elaboração de um programa computacional abrangente;
� São robustos e podem resolver uma grande diversidade de problemas
complexos de forma rápida e confiável;
� A construção de algoritmos genéticos e modelos existentes é geralmente
simples;
� São de fácil implementação e flexíveis para se implementarem
modificações;
� São mais resistentes a se prenderem a ótimos locais;
� São fáceis de combinar com outros métodos;
Algumas desvantagens em relação aos Algoritmos Genéticos são:
(ANDRADE, 2005).
CAPITULO II – REALIDADE VIRTUAL E ALGORITMOS GENÉTICOS
14
� Dificuldade para achar o ótimo global exato;
� Requerem um grande número de avaliações de funções de aptidão;
� Grandes possibilidades de configurações que podem complicar a resolução
do problema tratado.
2.2.3 Definições Básicas
Dentro do Algoritmo Genético existem algumas definições básicas a serem
consideradas:
� Indivíduo: simples membro da população. Nos AG’s, um indivíduo é
formado pelo cromossomo e sua aptidão, e representa cada candidato à
solução do problema.
� População: conjunto de indivíduos ou soluções.
� Gene: elemento que compõe os cromossomos. Nos AG’s, é a unidade
básica do cromossomo representada por um símbolo. Cada cromossomo tem
uma certa quantidade de genes, descrevendo uma certa variável do problema.
� Cromossomo: elemento portador do material genético. Nos AG’s
representa uma cadeia de bits associada a uma solução possível para o
problema. Deve ser observado que cada cromossomo, ou indivíduo,
corresponde a um ponto no espaço de soluções do problema de otimização. O
processo de solução adotado no AG consiste em gerar, através de regras
específicas, um grande número de indivíduos, população, de forma a promover
uma varredura tão extensa quanto necessária do espaço de soluções.
� Genótipo: conjunto de genes de um indivíduo.
� Fenótipo: conjunto de características de um indivíduo determinadas pelo
genótipo.
� Lócus (posição): posição em que um gene se encontra no cromossomo.
� Alelo: diferentes possibilidades de uma característica de um gene. Nos
AG’s, representa o valor que um gene pode assumir, ou seja, é cada símbolo,
presente no alfabeto, utilizado para codificação.
CAPITULO II – REALIDADE VIRTUAL E ALGORITMOS GENÉTICOS
15
� Geração: é cada passo do processo evolutivo. Considerada o ciclo de
criação e transformação de uma população, representada pelo número da
iteração que o AG executa.
� Operações Genéticas: operação que o AG realiza sobre as estruturas dos
cromossomos. Tais operações visam promover a evolução do indivíduo.
� Espaço de Busca: é o conjunto espaço ou região que compreende as
soluções possíveis ou viáveis para o problema a ser resolvido.
� Aptidão ou Adequação: representa a informação numérica do
desempenho de cada indivíduo da população e está associado à função
objetivo e às restrições do problema. Por meio da adequação ou aptidão de
cada indivíduo que é possível selecionar os melhores indivíduos de cada
população para aplicação das operações genéticas e evolução da solução.
2.2.4 Parâmetros Genéticos
É importante também, analisar de que maneira alguns parâmetros influenciam
no comportamento do AG, para que se possa estabelecê-los conforme as
necessidades do problema e dos recursos disponíveis. São listados a seguir alguns
Parâmetros Genéticos utilizados: (ANDRADE, 2005).
� Tamanho da População: O tamanho da população determina o número de
cromossomos na população, afetando diretamente o desempenho global e a
eficiência dos AG’s. Com uma população pequena o desempenho pode cair,
pois deste modo a população fornece uma pequena cobertura do espaço de
busca do problema. Uma grande população geralmente fornece uma cobertura
representativa do domínio do problema. No entanto, para se trabalhar com
grandes populações, são necessários maiores recursos computacionais, ou
que o algoritmo trabalhe por um período de tempo muito maior;
� Tipo de Cruzamento: O tipo de cruzamento a ser utilizado determina a
forma como se procederá a troca de segmentos de informação entre os
“casais” de cromossomos selecionados para cruzamento. O ideal seria testar
diversos tipos de cruzamento em conjunto com outras configurações do AG em
uso para verificar qual apresenta um melhor resultado;
CAPITULO II – REALIDADE VIRTUAL E ALGORITMOS GENÉTICOS
16
� Taxa de Cruzamento: Quanto maior for esta taxa, mais rapidamente novas
estruturas serão introduzidas na população. Mas se esta for muito alta, a maior
parte da população será substituída, e pode ocorrer perda de estruturas de alta
aptidão. Com um valor baixo, o algoritmo pode tornar-se muito lento;
� Taxa de Mutação: Mutação é utilizada para dar nova informação para a
população e também para prevenir que a população se sature com
cromossomos semelhantes. Uma baixa taxa de mutação previne que uma dada
posição fique estagnada em um valor, além de possibilitar que se chegue em
qualquer ponto do espaço de busca. Com uma taxa muito alta, a busca se torna
essencialmente aleatória além de aumentar muita a possibilidade de que uma
boa solução seja destruída. A melhor taxa de mutação é dependente da
aplicação, mas, para a maioria dos casos é entre 0,001 e 0,1;
� Cálculo da Aptidão (Fitness): Essa função é responsável pelo cálculo do
valor da aptidão de cada cromossomo, e é definida de acordo com o problema
em questão. Dado um cromossomo, a função de Fitness retorna o valor de
aptidão, que é proporcional à utilidade ou habilidade do indivíduo, que o
cromossomo representa. Para muitos problemas, particularmente em
otimização de funções, é óbvio o que a função de Fitness calcula, que é
simplesmente o valor da função. Comparando com as populações naturais, o
valor da aptidão é determinado pela habilidade dos indivíduos sobreviverem
aos seus predadores, a uma peste devastadora, e outros obstáculos à
maioridade e a subseqüente reprodução.
� Número Máximo de Gerações: Este parâmetro determina a quantidade
máxima de gerações que serão produzidas, ou seja, o número de evoluções
que o AG deverá atingir antes de terminar a sua execução.
2.2.5 Métodos e Critérios para Implantação de um AG
Para implantação de um AG, é necessário definir de forma correta alguns
métodos e critérios. A seleção de um ou outro método ou critério depende do tipo de
problema a ser revolvido, e também de que certos requisitos imprescindíveis ao bom
funcionamento do AG não sejam violados. A seguir são listados alguns desses
métodos e critérios utilizados:
CAPITULO II – REALIDADE VIRTUAL E ALGORITMOS GENÉTICOS
17
� Critério de codificação: tendo em vista que o AG trabalha com
manipulação de strings de determinados alfabetos (representação), deve-se
especificar a codificação com a qual se faz corresponder cada ponto do
domínio do problema com um gene ou conjunto de genes do cromossomo.
� Critério de tratamento dos indivíduos: nem sempre é possível
estabelecer uma correspondência ponto-a-ponto entre o domínio do problema e
o conjunto de strings binárias (ou de outro alfabeto utilizado) usadas para
resolvê-lo. Como conseqüência, nem todas as strings (indivíduos) codificam
indivíduos validos do espaço de busca e devem ser habilitados procedimentos
úteis para distingui-las.
� Critério de seleção: a seleção deve dirigir o processo de busca em favor
dos indivíduos mais aptos.
� Critério de substituição: os critérios com que se selecionam os criadores
não, necessariamente, têm que ser os mesmos usados para selecionar os
sobreviventes.
� Critério de inicialização: refere-se a como deve ser construída a
população inicial com a qual se inicializará o AG.
� Critério de parada: devem ser determinadas as condições nas quais se
considera que o AG encontrou uma solução aceitável ou tenha fracassado no
processo de busca e não faça sentido continuar.
� Funções de avaliação e aptidão: deve ser determinada a função de
avaliação mais apropriada para o problema, assim como a função de aptidão
que utilizará o AG para resolvê-lo.
� Operadores Genéticos: denominação dada aos operadores utilizados para
levar a cabo a reprodução. Um AG faz uso, normalmente, de três operadores
genéticos (levando em conta o AG básico): seleção, cruzamento e mutação.
Fique claro que estes não são os únicos possíveis e além de tudo admitem
variações.
2.2.6 Seleção dos Indivíduos
A operação de seleção é utilizada para selecionar os cromossomos que
estarão mais aptos para uma futura reprodução de seus descendentes, e que
CAPITULO II – REALIDADE VIRTUAL E ALGORITMOS GENÉTICOS
18
conseqüentemente apresentarão as melhores soluções ao problema. Para realizar
essa escolha utiliza-se o valor de aptidão de cada cromossomo, e o principal objetivo
é oferecer aos melhores indivíduos, preferência para o processo de reprodução.
Após a definição da codificação das soluções candidata do problema, a
segunda grande decisão, diz respeito à forma como os cromossomos são
selecionados ou reproduzidos, para, posteriormente, sofrerem as operações de
cruzamento e inversão, e conseqüentemente, gerar os descendentes que poderão
vir a sofrer o processo de mutação, ou não. (TEIXEIRA, 2004).
Esse processo desempenha o papel da seleção natural na evolução,
selecionando para sobreviver e reproduzir os organismos melhor adaptados ao
meio, no caso, os cromossomos com melhor valor na função de adequação. A
maneira pela qual os cromossomos são selecionados para reprodução pode variar,
dependendo do método de seleção utilizado. Entretanto, é certo que os
cromossomos melhor adaptados terão, necessariamente, uma probabilidade maior
de sobrevivência e reprodução que os de baixa função de adequação
(BARCELLOS, 2000).
Conforme (JUNIOR, 2000), uma população de N indivíduos é gerada de
acordo com a probabilidade proporcional à aptidão relativa de cada indivíduo na
população, onde a probabilidade de seleção de um cromossomo s, onde “a( )” é
função de adequação, conforme a Figura 2.3, é dada por:
Figura 2.3. Equação de probabilidade de seleção. Fonte (JUNIOR, 2000)
Usando esta equação, são selecionados N indivíduos, onde aqueles com
baixa aptidão tendem a desaparecer e se extinguirem, e os outros mais adequados
terão grandes chances de sobreviverem.
A cada dois cromossomos selecionados, são gerados dois novos
cromossomos, seus filhos. O processo de seleção termina quando o número de
CAPITULO II – REALIDADE VIRTUAL E ALGORITMOS GENÉTICOS
19
novos cromossomos se iguala ao da população antiga e um novo processo é
desencadeado, a troca da população antiga pela nova, onde uma nova geração de
indivíduos mais evoluídos e mais aptos é criada (BESSA, 2005).
A seguir são descritos alguns métodos de seleção mais conhecidos.
� Seleção por Roleta: Nessa seleção, cada indivíduo tem a oportunidade de
ser selecionado de acordo com o seu desempenho relativo ao da população, ou
seja, cada indivíduo da população é representado em uma roleta imaginária
proporcionalmente ao seu índice de aptidão. Nesse processo, somam-se todos os
valores das aptidões dos indivíduos de uma população. Para cada indivíduo divide-
se sua aptidão por esse valor da soma total das aptidões de todos os indivíduos,
chegando à probabilidade que cada um tem de ser selecionado dentro da
população.
A roleta é construída com setores correspondentes aos valores de fitness de
cada indivíduo, e o tamanho desses setores é determinado de acordo com a
probabilidade de seleção de cada indivíduo. Aos indivíduos com alta aptidão é dada
uma porção maior da roleta, enquanto aos de baixa aptidão é dada uma porção
relativamente menor. Assim, aqueles mais aptos terão mais chances de serem
sorteados. Com as probabilidades montadas, elabora-se a roleta, ilustrada na Figura
2.4.
Figura 2.4. Exemplo de seleção por roleta. Fonte (BARCELLOS, 2000)
CAPITULO II – REALIDADE VIRTUAL E ALGORITMOS GENÉTICOS
20
Gira-se a roleta um determinado número de vezes, de acordo com o tamanho
da população, e o setor no qual o ponteiro parar é o cromossomo selecionado que
irá participar da próxima geração.
� Seleção por Torneio: Esse processo consiste em selecionar um grupo de t
indivíduos aleatoriamente a partir da população total, com reposição (o indivíduo
selecionado retorna a população para possivelmente participar em outros torneios)
ou sem reposição (o indivíduo selecionado não pode participar novamente em outros
torneios). (SOUZA, 2004). Estes t indivíduos participam do torneio, o melhor
indivíduo que possuir melhor fitness é escolhido e o processo é repetido até que se
tenha uma nova população. Geralmente, este método é realizado apenas entre dois
indivíduos.
� Seleção por Truncamento: Na seleção por truncamento ou (µ, λ), uma
população de µ indivíduos (pais) gera λ > µ indivíduos (filhos), dos quais os µ
melhores são selecionados como os que irão compor a próxima geração. Esta
seleção não depende do valor de aptidão dos indivíduos da população, ou seja, os µ
melhores indivíduos sempre serão escolhidos (SOUZA, 2004).
� Seleção por Ordenação: Nessa seleção, os indivíduos são ordenados de
acordo com o seu valor de aptidão (fitness), onde a posição N é atribuída para o
melhor indivíduo e a posição 01 para o pior indivíduo (SOUZA, 2004). Na seleção
por ordenação linear, a cada indivíduo i é associada uma probabilidade pi de ser
selecionado. A seleção por ordenação exponencial se diferencia da ordenação linear
apenas no fato das probabilidades pi serem exponencialmente ajustadas (POZO et
al, 2000). O algoritmo para esse método é similar ao do método de ordenação
linear, diferindo apenas na forma como as probabilidades são calculadas.
2.2.7 Reprodução / Cruzamento (Crossover)
Através deste método é possível a obtenção de novos indivíduos. A partir da
população atual, uma nova é formada pelo cruzamento aleatório entre os
cromossomos, onde os filhos recebem informações de seus pais, através do material
genético proveniente deste cruzamento.
CAPITULO II – REALIDADE VIRTUAL E ALGORITMOS GENÉTICOS
21
Conforme (JUNIOR, 2000), o processo de recombinação é um processo
sexuado - ou seja, envolve mais de um indivíduo - que emula o fenômeno de
“crossover”, ou seja, a troca de fragmentos de genes entre pares de cromossomos.
Através do cruzamento são criados novos indivíduos misturando
características de dois indivíduos "pais". Esta mistura é feita tentando imitar (em um
alto nível de abstração) a reprodução de genes em células. Trechos das
características de um indivíduo são trocados pelo trecho equivalente do outro. O
resultado desta operação é um indivíduo que potencialmente combine as melhores
características dos indivíduos usados como base (POZO et al, 2000).
O processo depende, portanto, de dois parâmetros, escolhidos pelo
programador ou usuário, sendo eles: a probabilidade de recombinação (“crossover”),
denotada por PC, que possui tipicamente valores entre 0.5 e 1.0; e a probabilidade
de mutação, denotada por PM, que possui tipicamente valores entre 0.001 e 0.02
(BARCELLOS, 2004).
Existem muitos tipos de cruzamento, como mais utilizados pode-se destacar:
� Cruzamento de um ponto: neste cruzamento, um ponto aleatório é
escolhido nos indivíduos selecionados para o cruzamento e, o material genético que
precede o ponto é preservado, e o material posterior é trocado entre o par de
indivíduos (pais) participantes. A Figura 2.5 ilustra essa operação de cruzamento,
onde o ponto de corte está entre o sexto e o sétimo caractere (bit), sendo que os bits
em azul foram mantidos e os bits em laranja e amarelo foram trocados e
descendentes diferentes gerados.
Figura 2.5. Cruzamento de um ponto. Fonte (TEIXEIRA, 2004)
CAPITULO II – REALIDADE VIRTUAL E ALGORITMOS GENÉTICOS
22
� Cruzamento de dois pontos: o procedimento é similar ao cruzamento de
um ponto, com a diferença que neste são selecionados dois pontos de corte, e os
caracteres a serem trocados podem ser das extremidades ou do meio do
cromossomo, dependendo de cada problema. Na Figura 2.6 há um exemplo de
cruzamento de dois pontos, onde somente os caracteres em azul foram
preservados, e os caracteres das extremidades foram trocados.
Figura 2.6. Cruzamento de dois pontos. Fonte (TEIXEIRA, 2004)
� Cruzamento uniforme: esse cruzamento é radicalmente diferente do
cruzamento de um ponto e de dois pontos. Cada gene (caractere, bit) do
descendente é gerado copiando o gene correspondente de um dos pais, escolhido
de acordo com uma máscara de cruzamento gerada aleatoriamente a cada geração
de descendentes. Essa máscara é uma espécie de molde, tendo como objetivo
indicar quais genes serão copiados do primeiro pai, e quais serão copiados do
segundo. A Figura 2.7 ilustra esse processo, sendo que onde houver 1 (um) na
máscara, o gene correspondente será copiado do primeiro pai, caso contrário, onde
houver (0), o gene correspondente será copiado do segundo pai.
CAPITULO II – REALIDADE VIRTUAL E ALGORITMOS GENÉTICOS
23
Figura 2.7. Cruzamento uniforme. Fonte (TEIXEIRA, 2004)
Além destes, existem alguns outros operadores de cruzamento para
problemas de programação e otimização mais complexos, descritos nos tópicos a
seguir.
2.2.7.1 Operadores de Cruzamento - Crossover
� Operador Partially Mapped Crossover (PMX): No operador PMX, dois
pontos de corte de crossover são escolhidos aleatoriamente, e os genes dos pais
que estiverem entre essas posições são herdados pelo filho. A Figura 2.8 apresenta
um exemplo do operador PMX, demonstrando que os genes C, D, E e F, que estão
nas posições 3, 4, 5 e 6, respectivamente são herdados do primeiro pai. O gene a do
segundo pai está na mesma posição que o gene C do primeiro pai, portanto, deve-
se encontrar o gene c no segundo pai e ocupar essa posição com o gene a do filho.
Ao se repetir o procedimento para o gene j do segundo pai, nota-se que a posição 6
do filho já está ocupada, e no primeiro pai, essa posição pertence ao gene F, assim,
deve-se localizar o gene f no segundo pai e ocupar esta posição pelo gene j.
Repete-se o processo para todos os genes contidos dentro da região de crossover,
e os elementos que restarem são herdados do segundo pai nas mesmas posições
(SOUZA, 2004).
CAPITULO II – REALIDADE VIRTUAL E ALGORITMOS GENÉTICOS
24
Figura 2.8. Exemplo do Partially Mapped Crossover (PMX). Fonte (SOUZA,
2004)
� Operador Order Crossover (OX): O operador de cruzamento de ordem se
assemelha muito ao operador PMX. Nesse operador, dois pontos de corte são
selecionados aleatoriamente sobre os cromossomos pais. Para a geração de
descendentes, os genes contidos entre os pontos de corte são transferidos nas
mesmas posições em que se encontram em um dos pais, posteriormente o novo
cromossomo é completado com os genes do segundo pai, partindo do segundo
ponto de corte, evitando assim a geração de cromossomos inválidos (RODRIGUES,
2000) (BESSA, 2005).
� Operador Cycle Crossover (CX): No operador CX, as posições absolutas
dos genes dos pais são preservadas.
Figura 2.9 Exemplo do Cycle Crossover (CX). Fonte (SOUZA, 2004)
CAPITULO II – REALIDADE VIRTUAL E ALGORITMOS GENÉTICOS
25
A Figura 2.9 exemplifica esse processo, onde a posição 3 do primeiro pai foi
selecionada, dando início ao ciclo. Assim, o gene C é herdado pelo filho nessa
posição. O gene a, da posição 3, do segundo pai, é encontrado no primeiro pai na
posição 1, e então o gene A é herdado pelo filho na referida posição. Continuando o
ciclo, o gene e da posição 1 do segundo pai é encontrado na posição 5 do primeiro
pai, logo o gene E é herdado pelo filho na quinta posição. Isto completa o ciclo, pois
o gene c do segundo pai foi alcançado, e as posições não ocupadas do filho, são
herdadas do segundo pai nas mesmas posições (SOUZA, 2004).
2.2.8 Mutação
A mutação é um método utilizado para a introdução e manutenção da
diversidade genética da população que visa garantir uma maior varredura do espaço
de busca e evitar que o AG convirja muito cedo para mínimos locais, pois promove
alterações que direcionam a pesquisa para outros locais da superfície de resposta.
Após o cruzamento, o operador de mutação percorre toda a cadeia de bits do
cromossomo, gerando um evento baseado na probabilidade PM, se este evento
ocorrer o operador de mutação é executado e o valor do bit correspondente é
alterado. Se a alteração gerar indivíduos mais adaptados, estas novas
características serão transmitidas para os demais indivíduos ao longo das gerações.
Assim, como na mutação genética, o operador de mutação deve ter uma taxa baixa,
geralmente de (1/100), ocasionando mudanças em poucos indivíduos.
O operador de mutação exerce um papel importante dentro dos AG’s,
possibilitando restaurar a diversidade genética da população, caso a mesma a tenha
perdido durante o processo evolutivo desempenhado pelo algoritmo (GOLDBERG,
1989) apud (SOUZA, 2004).
A Figura 2.10 ilustra a operação de mutação em um cromossomo, no qual o
valor de um gene é alterado de 0 para 1.
Figura 2.10. Exemplo do Operador de Mutação. Fonte (TEIXEIRA, 2004)
CAPITULO II – REALIDADE VIRTUAL E ALGORITMOS GENÉTICOS
26
2.2.9 Diversidade nos AG’s
Um ponto fundamental para que o AG possa ter um bom funcionamento e um
ótimo desempenho é a existência de diversidade entre os indivíduos. Isto quer dizer
que é preciso que haja um certo grau de diversidade entre as aptidões dos
indivíduos que foram selecionados para as possíveis soluções. Caso contrário,
quando um AG possui em sua população indivíduos muito semelhantes, o operador
de cruzamento perde suas características em termos de capacidade na troca de
informações úteis entre os indivíduos da população, o que faz com que uma busca
possa progredir muito lentamente ou praticamente parar.
Em suma, é preciso que o AG possua uma certa variedade de aptidões, o que
implica também não ter uma disparidade muito grande de aptidões, pois isso pode
afetar negativamente a diversidade da população e ocasionar um grande esforço
computacional (ALMEIDA, 2005).
Nos tópicos a seguir, são descritos três conceitos intrinsecamente ligados
com a diversidade, que são: Convergência, Elitismo e Pressão Seletiva.
2.2.9.1 Convergência x Elitismo
Em um AG, a convergência ocorre quando um ou mais indivíduos assumem
um valor de aptidão muito superior aos demais (superindivíduos), tendo assim,
maiores chances de sobreviver e reproduzir a ponto de poderem até mesmo tomar
conta da população com sua descendência. Esse fato tende a ocorrer mais
freqüentemente no inicio do processo, quando um determinado indivíduo pode ser
privilegiado em relação ao resto da população, que pode apresentar aptidões
extremamente inferiores ao mínimo desejado. Esse fenômeno é chamado de
evolução em avalanche, ou seja, por serem privilegiados, os superindivíduos farão
com que a diversidade diminua e na geração seguinte se favoreçam ainda mais os
indivíduos mais aptos até o momento que eles dominam por completo a população,
o que termina acarretando em uma convergência prematura do AG (ANDRADE,
2005).
Durante as iterações que formam as gerações nos AG’s percebe-se que o
melhor indivíduo produzido em uma geração, desaparece na geração seguinte. O
método mais utilizado para melhorar a convergência dos AG’s é o Elitismo, um
CAPITULO II – REALIDADE VIRTUAL E ALGORITMOS GENÉTICOS
27
processo que garante que o certo percentual dos melhores indivíduos de uma
população não seja perdido e, assim, fazendo com que os melhores indivíduos de
uma população sejam reproduzidos na população seguinte (JUNIOR, 2000).
Assim, o elitismo é considerado como um método complementar aos vários
métodos de seleção, que força os AG’s a reterem um número de “melhores”
indivíduos a cada geração, pois os indivíduos que possuem características
importantes podem ser perdidos se caso não forem selecionados para reprodução
ou se forem destruídos por cruzamento ou mutação.
2.2.9.2 Pressão Seletiva
Para controlar a diversidade na população deve-se ter um controle sobre o
mecanismo de determinação de probabilidades de sobrevivência, pois, quanto maior
o favorecimento dos indivíduos mais aptos, menor será a variedade da população
podendo ocorrer uma convergência prematura para um ótimo local. Por outro lado,
se não há um favorecimento especial aos indivíduos mais aptos, haverá com certeza
maior diversidade na população, mas tornará o AG menos eficaz.
Assim, a pressão seletiva é outro conceito considerado importante para o
entendimento de um AG, e está relacionado à velocidade e direção no qual o AG
atuará em seu espaço de busca. Este método depende da avaliação e de qual tipo
de seleção será utilizada. A pressão seletiva tem como principal objetivo modular o
grau de privilégio de alguns indivíduos da população para sobreviver e se reproduzir
em relação aos indivíduos restantes (BARCELLOS, 2000).
A aplicação ideal para Pressão Seletiva seria: menor pressão seletiva no
início do processo, favorecendo a diversidade, e maior pressão seletiva na etapa
final do processo para favorecer a convergência para um ótimo global.
2.2.10 Condições de Término
Como os AG’s buscam a otimização de soluções, seria ideal que o algoritmo
só parasse ao encontrar a melhor solução. Porém, não se pode afirmar com certeza
se uma dada solução, encontrada pelo algoritmo, corresponde a um ótimo global.
Assim, usa-se como critério de parada, um número máximo de gerações ou um
tempo limite de processamento do algoritmo. Outro critério usado como condição de
parada do algoritmo, é a estagnação da população, ou seja, quando após algumas
CAPITULO II – REALIDADE VIRTUAL E ALGORITMOS GENÉTICOS
28
gerações, não se observa melhoria da população e ela não mais evolui ficando
estagnada sempre no mesmo nível de evolução (JUNIOR, 2000).
CAPITULO III – TRABALHOS RELACIONADOS
29
CAPITULO III
3 TRABALHOS RELACIONADOS
3.1 Introdução
O objetivo deste tópico é oferecer uma visão geral dos principais trabalhos
encontrados na literatura, expondo suas características mais importantes de acordo
com uma metodologia, onde foram analisados sistemas que:
� Geram de Rotas
� Geram Rotas utilizando Algoritmos Genéticos
� Cidades ou rotas em ambientes virtuais
� Visualização 2D ou 3D do resultado
� Integram RV e AG.
Abaixo seguem os trabalhos avaliados.
3.2 Aplicação da Generalização Cartográfica em Mundos Virtuais
Este trabalho aborda o problema de transpor ferramentas e conceitos
cartográficos para aplicações de realidade virtual, focando o uso da generalização
cartográfica em mundos urbanos virtuais para turismo. A Generalização Cartográfica
é uma área de Cartografia utilizada para se obter versões de mapas cartográficos
que utiliza um processo de abstração de informação que depende da escala, pois
determina o espaço disponível para a representação dos símbolos no mapa. A
seleção das informações importantes em uma base de dados deve resultar em uma
CAPITULO III – TRABALHOS RELACIONADOS
30
representação clara e informativa do fenômeno geográfico. A redução de escala é
acompanhada pela redução dos detalhes de representação de objetos individuais, e
ao mesmo tempo de exagero ou realce desses objetos para torná-los distinguíveis.
Em mundos virtuais este processo pode ser implementado com a geração de níveis
de detalhamento. Este trabalho também faz uso de técnicas de Inteligência Artificial,
onde o uso das regras de produção permite a escalabilidade, podendo inserir novas
regras e conseqüentemente novas funções. Na Figura 3.1, segue a demonstração
da seleção dos objetos a serem inseridos, e o mundo virtual pronto. (SILVA, 2004)
Figura 3.1 - Generalização Cartográfica em Mundos Virtuais.
3.3 Aplicação de AG’s no Desenvolvimento de Rotas Turísticas.
A intenção do trabalho de Carmo (CARMO, 2004), foi utilizar os conceitos e a
dinâmica de funcionamento dos algoritmos genéticos em uma aplicação para o
desenvolvimento de roteiros turísticos, com o objetivo de estudar a capacidade de
otimização destes algoritmos, ou seja, sua capacidade de identificar a melhor
solução entre inúmeras disponíveis. Para isto foram realizadas análises das
características do turismo e a segmentação dos seus principais fatores, para que
fosse possível avaliar cidades e regiões quanto ao seu potencial turístico. Utilizando
os conceitos dos AG’s, foi desenvolvido um algoritmo capaz de definir um roteiro
turístico a partir do perfil de um turista.
O problema que se propôs resolver com os algoritmos genéticos era que, a
partir de um perfil de turista e de um grupo de cidades que foram classificadas
quanto aos seus fatores turísticos, fosse possível avaliar as cidades e definir um
CAPITULO III – TRABALHOS RELACIONADOS
31
roteiro que possuísse a melhor combinação de cidades com características
semelhantes ao perfil do turista. Em resumo, trata-se da combinação de cidades em
grupos (roteiros) de tamanho definido e busca daquele com as características
desejadas. A visualização do sistema se dá através da relação dos nomes de cada
cidade inclusa do roteiro como mostra a Figura 3.2, não permitindo ao usuário a
possibilidade de acompanhar por um mapa.
Figura 3.2 - Algoritmos Genéticos no Desenvolvimento de Rotas Turísticas.
3.4 Construção e Gestão da Complexidade de Cenários Urbanos 3D em
AV’s Imersivos.
O trabalho de Pimentel (PIMENTEL, 2000) relata a dificuldade da construção
de cenários urbanos que possuem visualização interativa. A sua elevada
complexidade geométrica, a liberdade dada ao usuário de variar as perspectivas de
visibilidade de grande pormenor para panorâmica, o acréscimo do foto-realismo a
partir da utilização de imagens de alta qualidade, quer para as fachadas dos
edifícios, zonas arborizadas, até à fotografia aérea para texturização do modelo
digital de terreno, colocam um sem número de constrangimentos à capacidade do
hardware existente, só passíveis de serem ultrapassados com um planejamento
prévio rigoroso dos elementos disponíveis e das capacidades a oferecer aos seus
CAPITULO III – TRABALHOS RELACIONADOS
32
utilizadores. A estratégia escolhida para navegação através do modelo urbano
virtual baseia-se na metáfora do tapete voador.
De acordo com a Figura 3.3, são permitidas as translações segundo um
referencial XYZ com uma limitação intencional das rotações a dois eixos, para
minorar a desorientação espacial.
Figura 3.3 - Construção e Gestão da Complexidade de Cenários Urbanos 3D
em AV’s Imersivos.
3.5 O uso de Algoritmos Genéticos na solução de Rotas em trechos
urbanos
O uso do Algoritmo Genético possibilitou a resolução da problemática de
forma satisfatória. A implementação computacional, usando a orientação a objeto,
permite a fácil manutenção do código. Por sua vez, a estrutura simples do algoritmo
genético possibilita a introdução ou modificação de diferentes parâmetros e
operadores genéticos. Assim, alterações no modelo computacional são de fácil
manutenção, pois as funções do Algoritmo Genético são facilmente distinguíveis e
CAPITULO III – TRABALHOS RELACIONADOS
33
independentes. Além disso, para a execução dos Algoritmos Genéticos necessita-se
de um menor esforço computacional em relação à programação linear convencional.
O sistema obteve um desempenho satisfatório, conseguindo resolver o
problema de maneira rápida e eficiente. Em algumas execuções do sistema, a rota
demonstrada não foi precisamente a melhor rota, mas isso ocorre de forma
esporádica e de acordo com a configuração dos parâmetros genéticos.
A Figura 3.4 representa o sistema durante sua execução, utilizando a
visualização 2D, após o processamento do AG, demonstrando a melhor rota
encontrada, com base nos pontos de origem e de destino selecionados pelo usuário,
e obedecendo às restrições dos cruzamentos escolhidos e dos sentidos de cada
ponto. (BATISTA, 2006)
Figura 3.4 - Algoritmos Genéticos na solução de rotas em trechos urbanos.
3.6 Roteamento de Veículos Dinâmico usando AG’s
Ribeiro e Lorena (2005) apresentam um trabalho onde é analisada a
utilização de Algoritmos Genéticos no Problema de Roteamento de Veículos
Dinâmico com Janelas de Tempo, que tem por objetivo auxiliar o processo de
decisão reduzindo os custos logísticos durante a reprogramação das rotas. Neste
CAPITULO III – TRABALHOS RELACIONADOS
34
estudo, o desenvolvimento de algoritmos eficientes para resolver este problema é
direcionado às empresas de transporte de carga, uma vez que os autores acreditam
que tal problema venha a estar cada vez mais presente no dia-a-dia destas
empresas, influenciando significativamente nos custos logísticos.
Na classe de problemas em questão, conhecida por PRVDJT, as rotas podem
ser alteradas durante a operação dos veículos caso surja novas informações e,
assim, é possível que sejam realizadas mudanças após a fase de roteamento dos
veículos. Os AG’s foram aplicados para a resolução deste tipo de problema.
Foram realizados vários experimentos, testes e avaliações, e os resultados
obtidos com o AG, melhoraram as rotas existentes além de se igualarem ou serem
superiores aos da Heurística 2-opt, que é muito indicado e conhecido para a
resolução de problemas de roteamento quando se trata de melhorar as rotas. Em
muitos casos os resultados médios encontrados para 10 execuções do AG foram
melhores do que a Heurística 2-opt, como demonstra a Figura 3.5.
Figura 3.5 - Roteamento de Veículos Dinâmico usando AG’s.
CAPITULO III – TRABALHOS RELACIONADOS
35
3.7 Sistema Melhor Roteiro Belém.
O objetivo deste trabalho é desenvolver uma aplicação para auxiliar o turista
na elaboração do seu roteiro, através da possibilidade de escolha de pontos
turísticos, baseada na interpretação do seu interesse pessoal, utilizando a Teoria
dos Sistemas Nebulosos. Armazenados em um banco de dados, os resultados das
consultas podem ser reaproveitados para análises dos recursos da cidade sobre o
turismo. Devido à complexidade do problema e as inúmeras soluções possíveis,
procurou-se fazer na proposição e construção do protótipo, simplificações para
tornar o sistema eficiente e prático. Baseados no fato de que o turista busca em um
lugar, pontos turísticos que sejam de seu interesse e que, não necessariamente,
tenha conhecimento detalhado sobre estes pontos, conforme a Figura 3.6, foi
elaborado um método para sugestão de pontos turísticos a serem visitados e
proposição de um roteiro, juntamente com indicação de meios de locomoção,
compatível com o seu interesse e disponibilidade de tempo e recursos financeiros,
baseando-se principalmente no nível de hospedagem. (BURLAMAQUI, 2006)
Figura 3.6 - Sistema Melhor Roteiro Belém.
CAPITULO III – TRABALHOS RELACIONADOS
36
3.8 Otimização de Rotas de Veículos baseada em Operadores
Genéticos.
Schutz e Pires (2003) expõem em seu trabalho um AG para a versão básica
do Problema de Otimização de Rotas de Veículos (PORV), problema este que
consiste em determinar um conjunto de rotas a serem realizadas por uma frota de
veículos, para servir um conjunto fixo de clientes de modo a minimizar a distância
total percorrida.
Foram realizados vários testes com o AG descrito, comparando-se as
soluções obtidas através do AG com as melhores conhecidas, conforme a Figura
3.6, e comparando-se os tempos de execução computacional com outros dois
algoritmos: uma heurística de duas fases e a heurística construtiva de rotas. Foi
constatado que este AG é mais eficiente do que estas heurísticas, entretanto não é
tão eficiente em relação às melhores soluções conhecidas obtidas com métodos
muito mais elaborados.
Os autores concluíram então que o AG poderá ficar eventualmente mais
eficiente mediante algumas alterações, como: utilizar heurísticas mais eficientes para
a resolução dos PCV envolvidos; permitir requisições não admissíveis; alterar a
atuação dos operadores genéticos tendo em conta que as soluções podem ser
avaliadas segundo dois critérios, um relativo à violação das restrições de capacidade
e o outro às distâncias percorridas; gerar a maior parte da população inicial
aleatoriamente e somente alguns poucos indivíduos heuristicamente.
CAPITULO III – TRABALHOS RELACIONADOS
37
Figura 3.7 - Otimização de Rotas de Veículos baseada em Operadores
Genéticos.
3.9 Uma Proposta de AG’s de Duas Fases para Roteamento
Rebello e Hamacher (2000) propõem um trabalho com uma metodologia e
uma solução computacional para resolver o problema do recolhimento da
correspondência de 39 agências dos Correios no Rio de Janeiro, com o intuito de
minimizar o tempo total percorrido pelos veículos, levando em consideração
restrições de carga e de janelas de tempo em cada agência. O objetivo deste estudo
é mostrar a utilização da metaheurística dos Algoritmos Genéticos na resolução
deste problema de logística nos Correios do RJ, que pertence à categoria dos
problemas de roteamento de veículos (PRV), onde o resultado pode ser visualizado
na Figura 3.8 para os quais técnicas heurísticas dominam os procedimentos de
solução.
Os autores relatam que a técnica dos Algoritmos Genéticos possui resultados
comparáveis a métodos utilizados atualmente para problemas semelhantes ao
problema estudado, desde que o AG seja devidamente implementado e configurado.
CAPITULO III – TRABALHOS RELACIONADOS
38
Um das vantagens do AG é a flexibilidade, pois permite que o algoritmo incorpore
características do problema real que são dificilmente representáveis nas heurísticas
clássicas e facilita que alterações na função de avaliação sejam feitas.
A metodologia proposta pelo estudo era a de alternar fases de zoneamento e
roteamento, ambas utilizando AG, e esta se mostrou ser muito eficaz, permitindo a
geração de boas soluções com tempos computacionais razoáveis.
Figura 3.8 - AG’s de Duas Fases para Roteamento de Veículos.
3.10 Uso de AG’s em Sistema de Apoio à Decisão
Narciso e Lorena (2002) apresentam em seu trabalho uma aplicação da meta-
heurística denominada Algoritmo Genético Construtivo (AGC) e uma nova proposta
de mutação para resolver o Problema de Localização Capacitado e do P-mediano.
Este algoritmo, e mais um conjunto de algoritmos para roteamento e localização de
recursos, juntamente com um Sistema de Informação Geográfica (SIG), formam um
sistema de apoio à decisão (SAD) para problemas de roteamento e localização, que
pode resolver problemas tanto no domínio rural quanto no domínio urbano
CAPITULO III – TRABALHOS RELACIONADOS
39
(localização de silos, postos de saúde, roteamento de ônibus, caminhões para
escoamento da produção, localização de escolas, hospitais, armazéns,
supermercados, etc.).
Os resultados do algoritmo aplicado ao Problema de Localização Capacitado
e P-mediano melhoraram com a nova proposta de mutação conforme a Figura 3.9.
Testes computacionais foram realizados com resultados muito bons, usando
instâncias de larga escala disponíveis na literatura. O AGC teve um bom
desempenho quanto aos resultados obtidos nas instâncias do PLC. A abordagem de
usar o AGC para o PLC foi pioneira e os resultados obtidos foram muito próximos
do ótimo, considerando-se instâncias com solução ótima conhecida.
Figura 3.9 - AG’s em Sistema de Apoio à Decisão para Alocação de Recursos
no Campo e na Cidade.
3.11 Uso de AG’s na Construção de Rotas Turísticas
Bessa (2005) propõe um trabalho que visa diminuir os impactos gerados pelo
desconhecimento de uma rota a ser realizada, por meio da construção de uma
metodologia utilizando Algoritmos Genéticos que consiga demonstrar a melhor rota
turística a ser efetuada. Este trabalho tem por objetivo a determinação da melhor
CAPITULO III – TRABALHOS RELACIONADOS
40
rota turística urbana, com base em pontos turísticos a serem visitados, o ponto de
partida e o ponto de chegada.
Após a realização de testes com o sistema, o autor concluiu que a utilização
dos Algoritmos Genéticos possibilitou alcançar os objetivos do trabalho, com um
desempenho satisfatório e com um esforço computacional pequeno. Possibilitou a
resolução da problemática de forma satisfatória, sendo necessárias poucas linhas de
comandos, o que demonstrou sua robustez, simplicidade de programação e
facilidade de adaptação de mudanças no escopo original de implementação da
problemática.
Finalmente, o sistema desempenhou de maneira satisfatória seus objetivos,
conforme a Figura 3.10, conseguindo demonstrar a melhor rota de maneira imediata.
Figura 3.10 - AG’s na Construção de Rotas Turísticas .
3.12 Tabela Comparativa entre os trabalhos avaliados
As principais características observadas nos trabalhos avaliadas, foram
sintetizadas na Tabela 3.1. Alguns trabalhos apresentam características comuns
CAPITULO III – TRABALHOS RELACIONADOS
41
como os que utilizam AG’s, conseguiram gerar as rotas necessárias para o sistema,
porém possuem apenas a visualização em 2D, o que não permite uma maior
interação e envolvimento do usuário. Nos trabalhos em que existe a utilização do
ambiente virtual, nenhum utilizou a geração de rotas como mostra a tabela abaixo.
Essas características reforçam a necessidade da construção do trabalho utilizando o
AG para a geração da rota e a integração com RV para a visualização da rota em
um ambiente virtual.
CAPITULO III – TRABALHOS RELACIONADOS
42
Tabela 3.1. Principais características dos sistemas avaliados.
CAPITULO III – TRABALHOS RELACIONADOS
43
3.13 Considerações Finais
Os AG’s têm se demonstrado como uma poderosa ferramenta de otimização
de busca de soluções de questões complexas e que possuem várias soluções
possíveis, cabendo ao algoritmo selecionar a melhor entre elas.
Existem várias metodologias de implementação de um Algoritmo Genético,
com diferentes formas de cruzamento e seleção dos indivíduos, diversas formas de
parâmetros e valores que podem ser atribuídos a esses parâmetros, etc. Cabe
ressaltar que o foco deste trabalho é gerar rotas utilizando Algoritmos Genéticos e
possibilitar ao usuário, tanto a visualização em 2D, como principalmente a
possibilidade de um passeio dentro de Ambiente Virtual, o que possibilita maior
entendimento e conhecimento da rota e também envolvimento, imersão e interação
com o ambiente virtual gerado. Características que os sistemas avaliados não
contemplam.
CAPITULO IV – ARQUITETURA DO SISTEMA
CAPÍTULO IV
4 ARQUITETURA DO SISTEMA
4.1 Introdução
A partir do estudo realizado nos capítulos 2 e 3, foi possível perceber a
necessidade deste trabalho. Antes de mostrar detalhadamente a arquitetura do
sistema, será apresentada a tecnologia de apoio necessária ao funcionamento do
mesmo.
4.2 Tecnologia de apoio
Novas tecnologias têm sido criadas recentemente para o suporte ao
desenvolvimento de aplicações que utilizam a Realidade Virtual, com isso
possibilitam a utilização de computadores pessoais (PCs) melhores capacidades
gráficas.
Neste trabalho, a principal tecnologia utilizada foi o OpenGL, pois todas as
outras funcionalidades foram criadas por meio de algoritmos traduzidos em
linguagem de programação. Cabe ressaltar q apenas o objeto geométrico do
sistema (cidade) foi modelada (desenhada) em uma ferramenta modeladora 3D (3D
Studio Max), porem sua utilização foi necessária apenas como ferramenta auxiliar.
CAPITULO IV – ARQUITETURA DO SISTEMA
45
4.2.1 OPENGL
OpenGL não é uma linguagem de programação, mas é uma poderosa e
sofisticada API (Application Programming Interface) para criação de aplicações
gráficas 2D e 3D, ou seja, uma biblioteca de rotinas gráficas para trabalhar em duas
e três dimensões. Normalmente, se diz que um programa é baseado em OpenGL ou
é uma aplicação OpenGL, o que significa que ele é escrito em alguma linguagem de
programação que faz chamada a uma ou mais bibliotecas OpenGL (PINHO, 2004).
OpenGL é definido como um programa de interface para hardware gráfico. Na
verdade, OpenGL é uma biblioteca de rotinas gráficas e de modelagem, bi (2D) e
tridimensional (3D), extremamente portável e rápida. Usando OpenGL, é possível
criar gráficos 3D com uma alta qualidade visual. Entretanto, a maior vantagem na
sua utilização é a rapidez, uma vez que usa algoritmos cuidadosamente
desenvolvidos e otimizados pela Silicon Graphics, Inc., líder mundial em
Computação Gráfica e Animação (WOO, 1999).
As aplicações OpenGL variam de ferramentas CAD a programas de
modelagem usados para criar personagens para o cinema. Além do desenho de
primitivas gráficas, tais como linhas e polígonos, OpenGL dá suporte a iluminação,
colorização, mapeamento de textura, transparência, animação, entre muitos outros
efeitos especiais. Atualmente, OpenGL é reconhecida e aceita como um padrão API
para desenvolvimento de aplicações gráficas 3D em tempo real. (RIBEIRO, 2006)
Em vez de descrever a cena e como ela deve parecer, quando se está
utilizando OpenGL é preciso apenas determinar os passos necessários para
alcançar a aparência ou efeito desejado.
Por ser portável, OpenGL não possui funções para gerenciamento de janelas,
interação com o usuário ou arquivos de entrada/saída. Cada ambiente, como por
exemplo o Microsoft Windows, possui suas próprias funções para esses propósitos.
Não existe um formato de arquivo OpenGL para modelos ou ambientes virtuais.
OpenGL fornece um pequeno conjunto de primitivas gráficas para construção de
modelos, tais como pontos, linhas e polígonos. A biblioteca GLU (que faz parte da
implementação OpenGL) é que fornece várias funções para modelagem, tais como
superfícies quádricas, e curvas e superfícies NURBS (Non Uniform Rational B-
Splines) (WOO, 1999; WRIGHT, 2000).
CAPITULO IV – ARQUITETURA DO SISTEMA
46
A palavra pipeline é usada para descrever um processo, que pode ter dois ou
mais passos distintos. A Figura 4.1 mostra uma versão simplificada do pipeline
OpenGL. Como uma aplicação faz chamadas às funções API OpenGL, os comandos
são colocados em um buffer de comandos. Este buffer é preenchido com comandos,
vértices, dados de textura etc. Quando este buffer é "esvaziado", os comandos e
dados são passados para o próximo estágio.
Figura 4.1. Versão simplificada do pipeline OpenGL (WOO, 1999).
Após a etapa de aplicação das transformações geométricas e da iluminação,
é feita a rasterização, ou seja, é gerada a imagem a partir dos dados geométricos,
de cor e textura. A imagem final, então, é colocado no frame buffer, que é a memória
do dispositivo gráfico. Isto significa que a imagem é exibida no monitor (WRIGHT,
2000).
4.3 Módulos da Arquitetura do Sistema
Este trabalho tem o propósito de utilizar os AG para a geração de uma rota
dentro de uma cidade, e posteriormente à visualização desta mesma rota em um
Ambiente Virtual. Permitido ao usuário um passeio pela cidade seguindo o trajeto da
rota criada pelo algoritmo.
O sistema pode ser resumido como sendo a integração dos Algoritmos
Genéticos (interface 2D) com RV (interface 3D modelada e programada em
OpenGL). A Figura 4.2 ilustra essa arquitetura que reúne as duas áreas.
CAPITULO IV – ARQUITETURA DO SISTEMA
47
Figura 4.2. Arquitetura do Sistema - Integração entre AG e RV.
A arquitetura do sistema esta dividida entre a interface do usuário, o módulo
de AG, Mapas e AV.
4.3.1 Módulo Mapas
Os modelos geométricos dos mapas tanto 2D como 3D, foram construídos a
partir de um modelo real extraído da cidade de Uberlândia – MG. Esses modelos
foram desenhados com o uso do software de modelagem 3D Studio Max. O módulo
Mapa é responsável pela leitura e conversão destes modelos para posterior uso no
módulo de geração de rotas (Módulo AG) e visualização (Módulo AV).Módulo AG
O módulo AG é responsável pela geração de todas as rotas e tem como base
o uso de coordenadas de todos os cruzamentos presentes no módulo mapas. Este
módulo oferece ao módulo AV a seqüência de pontos necessários para a geração
da rota virtual.
4.3.3 Módulo AV
O módulo AV é a parte da arquitetura responsável pela visualização e
navegação do Ambiente virtual que representa a cidade. Este módulo tem como
CAPITULO IV – ARQUITETURA DO SISTEMA
48
principal tecnologia a biblioteca OpenGL responsável pela renderização dos objetos
geométricos do ambiente.
4.4 Engenharia de Software/Engenharia de Requisitos
O processo de construção do sistema utilizou-se de mecanismos e
instrumentos de Engenharia de Software para especificação e criação do projeto do
software. Para tanto foram utilizados diagramas UML (Unified Modeling Language)
que permitisse a exposição do projeto de forma eficaz e planejada.
4.4.1 Diagrama de Caso de Uso (Use Case)
Casos de Uso ou Use Cases são descrições narrativas dos processos do
sistema, envolvendo atores que estimulam ou recebem alguma coisa do use case.
Podem ser definidos também como estórias ou casos de uso sobre o sistema e
possuem dependência dos requisitos do sistema (Larman 1998). Os use cases são
identificados através da leitura dos documentos de requisitos e de reuniões com os
usuários envolvidos (brainstormings) (Larman 1998) e, em geral, são categorizados
em (Larman 1998) primário, secundário e opcional.
Os use cases primários representam processos comuns do sistema
(freqüentemente utilizados); os secundários representam processos pequenos e/ou
raros (raramente utilizados); e os opcionais representam processos que podem não
ser desenvolvidos ou utilizados.
4.4.2 Casos de Uso
A Figura 4.4 mostra o diagrama de Use-Case do sistema desenvolvido.
CAPITULO IV – ARQUITETURA DO SISTEMA
49
Figura 4.4. Diagrama de Use-Case.
Tabela 4.1. Relação dos Casos de Uso.
Func. Nome da Funcionalidade Relação dos Casos de Uso
1 Estabelecer ponto inicial e final Estabelecer ponto inicial e final no mapa
2 Definir tava de cruzamento Definir taxa de cruzamento para o algoritmo
3 Definir número de gerações Definir número de gerações para o algoritmo
4 Executar o AG Executar o algoritmo em busca da melhor solução
5 Gerar Rota Virtual Gerar o Modelo 3D com base na melhor solução
Definir taxa
de
cruzamento
Definir o
número de
gerações
Estabelecer ponto inicial
e final
Executar o
algoritmo
genético
Usuário
CAPITULO IV – ARQUITETURA DO SISTEMA
50
4.4.2.1 Caso de Uso: Estabelecer ponto inicial e final no mapa
� Diagrama:
Figura 4.5. Use-Case “Estabelecer ponto inicial e final no mapa”.
� Descrição:
Tabela 4.2. Descrição do Caso de Uso ‘Estabelecer ponto inicial e final no
mapa’.
Nome do Caso de Uso: Estabelecer ponto inicial e final no mapa
Funcionalidade: Definição dos pontos de origem e de destino para o percurso no
mapa.
Ator envolvido: Usuário (pessoa que irá fazer uso do sistema fornecendo as informações que estão disponíveis para que o mesmo possa gerar um resultado satisfatório).
PRÉ-CONDIÇÃO
1. O mapa deve estar desenhado e com os pontos e cruzamentos pré-definidos.
DESCRIÇÃO DO CASO
1. Indicar o ponto inicial (de origem) da rota.
2. Indicar o ponto final (de destino) da rota.
PÓS-CONDIÇÃO
1. Os pontos (inicial e final) serão cadastrados no mapa e no algoritmo.
Usuário
Estabelecer ponto inicial e final no mapa
CAPITULO IV – ARQUITETURA DO SISTEMA
51
4.4.2.2 Caso de Uso: Definir taxa de cruzamento para o algoritmo
� Diagrama:
Figura 4.6. Use-Case “Definir taxa de cruzamento para o algoritmo”.
� Descrição:
Tabela 4.3. Descrição do Caso de Uso ‘Definir taxa de cruzamento para o
algoritmo’.
Nome do Caso de Uso: Definir taxa de cruzamento para o algoritmo
Funcionalidade: Definição da taxa de cruzamento do AG
Ator envolvido: Usuário (pessoa que irá fazer uso do sistema fornecendo as informações que estão disponíveis para que o mesmo possa gerar um resultado satisfatório).
PRÉ-CONDIÇÃO
1. Os pontos em que se deseja realizar o percurso devem estar estabelecidos.
DESCRIÇÃO DO CASO
1. Indicar a taxa de cruzamento desejada para o algoritmo.
PÓS-CONDIÇÃO
1. O algoritmo será executado e a população evoluirá de acordo com a taxa de cruzamento estabelecida.
Usuário
Definir taxa de
cruzamento para
o algoritmo
CAPITULO IV – ARQUITETURA DO SISTEMA
52
4.4.2.3 Caso de Uso: Definir número de gerações para o algoritmo
� Diagrama:
Figura 4.7. Use-Case “Definir número de gerações para o algoritmo”.
� Descrição:
Tabela 4.4. Descrição do Caso de Uso ‘Definir número de gerações para o
algoritmo’.
Nome do Caso de Uso: Definir número de gerações para o algoritmo
Funcionalidade: Definição do número de gerações do AG
Ator envolvido: Usuário (pessoa que irá fazer uso do sistema fornecendo as informações que estão disponíveis para que o mesmo possa gerar um resultado satisfatório).
PRÉ-CONDIÇÃO
1. Os pontos em que se deseja realizar o percurso devem estar estabelecidos.
DESCRIÇÃO DO CASO
1. Indicar o número de gerações desejadas para o algoritmo.
PÓS-CONDIÇÃO
1. O algoritmo será executado e a população evoluirá de acordo com a quantidade de gerações estabelecida.
Usuário
Definir número de gerações
para o algoritmo
CAPITULO IV – ARQUITETURA DO SISTEMA
53
4.4.2.4 Caso de Uso: Executar o algoritmo em busca da melhor solução
� Diagrama:
Figura 4.8. Use-Case “Executar o algoritmo em busca da melhor solução”.
� Descrição:
Tabela 4.5. Descrição do Caso de Uso ‘Executar o algoritmo em busca da
melhor solução’.
Nome do Caso de Uso: Executar o algoritmo em busca da melhor solução
Funcionalidade: Execução e evolução do AG em busca da melhor solução
Ator envolvido: Usuário (pessoa que irá fazer uso do sistema fornecendo as informações que estão disponíveis para que o mesmo possa gerar um resultado satisfatório).
PRÉ-CONDIÇÃO
1. Os pontos em que se deseja realizar o percurso devem estar estabelecidos.
2. A taxa de cruzamento tem que estar definida.
3. A quantidade de gerações tem que estar definida.
DESCRIÇÃO DO CASO
1. Clicar no botão de evolução.
PÓS-CONDIÇÃO
1. O algoritmo será executado e a população evoluirá até encontrar a melhor solução, ou seja, a melhor rota ou percurso.
Usuário
Executar o algoritmo em
busca da melhor solução
CAPITULO IV – ARQUITETURA DO SISTEMA
54
4.5 Considerações Finais
A arquitetura do sistema segue a modelagem conceitual do AG Clássico,
com um fluxo básico de execução composto pela codificação do cromossomo,
criação da população, definição da aptidão, seleção dos indivíduos e cruzamentos
dos indivíduos na população. O melhor indivíduo é base para construção da rota 3D
ou rota virtual.
Além disso, o diagrama de Use Case representa os principais processos que
podem ser utilizados pelo usuário na execução do algoritmo, com o objetivo de se
chegar à uma melhor rota no mapa.
CAPITULO V – DETALHES DA IMPLEMENTAÇÃO
CAPÍTULO V
5 DETALHES DA IMPLEMENTAÇÃO
5.1 Introdução
Este capítulo apresenta a implementação do sistema, abordando todas as
fases necessárias à execução do AG e da conversão para Ambiente Virtual. A
implementação do modelo 3D começa com a modelagem dos objetos que serão
utilizados no ambiente virtual. A linguagem utilizada foi o Object Pascal, utilizando-se
a versão 6.0 do ambiente de programação Borland Delphi TM.
5.2 Estrutura do Cromossomo
A rota possui diversos pontos que podem ser visitados durante o percurso,
cada um desses pontos possui suas coordenadas cartesianas e o conjunto desses
pontos representa um indivíduo.
A Figura 5.1 ilustra a estrutura de um individuo que irá compor a população.
Figura 5.1. Estrutura do Cromossomo (Indivíduo).
CAPITULO V – DETALHES DA IMPLEMENTAÇÃO
56
A Figura 5.2 mostra o código que gera todos os indivíduos da população.
Cada um desses é formado por um vetor de coordenadas que representam cada um
dos cruzamentos (pontos) do mapa. Cada um desses pontos possui suas
coordenadas X e Y, que representam a sua posição em determinado local do mapa.
Para cada ponto P, existe outro vetor de possibilidades de tráfego. Um indivíduo
válido é aquele que possui uma seqüência válida entre o ponto inicial e o ponto final
e, o melhor indivíduo é aquele que possui a menor distância entre esses pontos.
Para i=1 até TamanhodaPopulacao Faça
Inicio
pop[i].ind[1] := ptini.ind;
for j:=2 to 500 do
begin
qtc := 0;
for k:=1 to 8 do
begin
if (Populacao.Individuo[pop[i].ind[j-1]].conexoes[k] <> 0) then
Inc(qtc);
end;
tent := 0;
repeat
Inc(tent);
cruz := RandomRange(1,qtc+1);
pop[i].ind[j] := Populacao.Individuo[pop[i].ind[j-1]].
conexoes[cruz];
until ((pop[i].ind[j] <> pop[i].ind[j-2]) or (tent > 7));
if (pop[i].ind[j] = ptfin.ind) then
begin
Inc(achou);
break;
end;
end;
Fim;
Figura 5.2. Pseudocódigo da geração da população.
5.3 Geração do Melhor Indivíduo
O melhor indivíduo encontrado pela execução do algoritmo genético é um
conjunto seqüencial de coordenadas que sugerem o melhor caminho a ser
percorrido pelo usuário do sistema tendo como referências o ponto inicial e o ponto
final. A Figura 5.3 ilustra a composição desse indivíduo.
Figura 5.3. Composição do indivíduo final.
CAPITULO V – DETALHES DA IMPLEMENTAÇÃO
57
O indivíduo final é a melhor solução encontrada pelo algoritmo, ou seja, a menor
distância válida entre o ponto inicial e o ponto final. Essa composição é conjunto de
coordenadas que serão os apontadores para objetos (cruzamentos) que estão no
modelo em três dimensões.
5.4 Definição da Aptidão (Fitness)
A aptidão da população é avaliada de acordo com a menor distância da rota
encontrada. A distância da rota é obtida, somando-se as distâncias entre o ponto de
origem e de destino escolhidos, e analisando-se as distâncias entre os possíveis
pontos intermediários que serão percorridos. E a cada nova iteração, essa aptidão é
reavaliada.
Quanto menor for à distância percorrida, mais evoluída a população está e
mais apta estará para resolver a problemática da execução do algoritmo. Assim,
chegará um determinado momento em que a aptidão da população não mais se
modificará, diz-se então, que a população chegou em seu estágio máximo de
evolução, o que caracteriza a parada da execução do algoritmo.
Primeiramente é necessário definir que cada indivíduo será formado por um
conjunto de ponto, onde cada ponto representa uma definição de mudança de
direção na rota, especificamente esquinas ou cruzamentos de uma cidade ou
organização similar, e é composto por uma coordenada (x, y). A Figura 5.4
representa a equação de aptidão, em que dist representa a distância da rota.
distaf
1)( =
Figura 5.4. Equação para cálculo da aptidão.
A Figura 5.5 representa o pseudocódigo que para geração da aptidão de cada
indivíduo.
CAPITULO V – DETALHES DA IMPLEMENTAÇÃO
58
Para i=1 até TamanhodaPopulacao Faça
Inicio
for j:=1 to 500 do if pop[i].ind[j] = 0 then break;
pontos := j-1;
Pop[i].distancia := 0.0;
for j:=1 to pontos-1 do
begin
x := Populacao.individuo[Pop[i].ind[j]].cruz.x -
Populacao.individuo[Pop[i].ind[j+1]].cruz.x;
y := Populacao.individuo[Pop[i].ind[j]].cruz.y -
Populacao.individuo[Pop[i].ind[j+1]].cruz.y;
try
Pop[i].distancia := Pop[i].distancia +sqrt(sqr(x)+sqr(y));
except
ShowMessage('Erro no cálculo de distância:
'+FormatFloat('0.00',x)+'-'+FormatFloat('0.00',y));
end;
end;
Pop[i].aptidao := (1 / Pop[i].distancia) * 10000;
Fim;
Figura 5.5. Composição do indivíduo final.
O pseudocódigo da Figura 5.5 apresenta um método para calculo da distância
de um ponto ao outro por meio da soma da distancia dos pontos intermediários. Por
se tratar de valores dos eixos X e Y, foi usada uma equação que propiciasse o
calculo da distancia entre um ponto P1(x1, y1) e outro ponto P2(x2, y2): raiz
quadrada((x2-x1)² +(y2-y1)²).
5.5 Codificação do Cromossomo
O cromossomo (indivíduo) foi definido como uma estrutura de dados do tipo
“array” (vetor) dinâmico com tamanho calculado em função da quantidade de
cruzamentos selecionados.
O cromossomo é composto por um conjunto de pontos (representando as
coordenadas x e y) e pelo seu índice ou posição. Além desses, ainda engloba a sua
aptidão (representando a sua distância no percurso) e as suas conexões (pontos por
onde pode passar).
5.6 Criação da População
A população é formada por um conjunto de indivíduos, sendo que cada um
representa uma rota. Por meio dos operadores genéticos (seleção e cruzamento), a
população irá evoluir e encontrar ou não, a melhor rota.
CAPITULO V – DETALHES DA IMPLEMENTAÇÃO
59
A Figura 5.6 mostra a representação da população, que é composta por um
determinado conjunto de indivíduos I, que irão ser selecionados e cruzados entre si
a fim de encontrar a melhor solução, ou seja, o melhor caminho a ser percorrido.
Figura 5.6. Estrutura da População.
A população é um conjunto de indivíduos, gerados aleatoriamente e tendo
como princípio o ponto de saída ou de origem (índice 1) e o ponto de chegada ou de
destino (índice n). A seqüência de pontos compreendidos entre esse intervalo será
dependente do número de pontos compreendidos entre os índices inicial e final.
Esses pontos presentes na configuração inicial do sistema referem-se aos locais por
onde uma pessoa tem que passar, para que possa ir de um lugar a outro.
A população foi definida como uma estrutura de dados do tipo “array” (vetor)
dinâmico que aponta para o primeiro vetor criado para armazenar todos os pontos
possíveis do cenário escolhido.
5.7 Método de Seleção
O método empregado para a seleção dos indivíduos para o cruzamento é o
método de seleção por roleta (descrito no item 2.2.6), uma vez que é o método mais
utilizado na maioria das implementações de AG’s e mostrou-se eficaz na solução
problema específico de rotas.
A roleta representa em sua totalidade a somatória das aptidões dos
cromossomos da população e cada cromossomo adquire percentualmente uma
“fatia” dessa roleta, conforme sua aptidão individual. Assim, aqueles indivíduos que
possuem uma aptidão maior, são os que caracterizam uma distância menor do
CAPITULO V – DETALHES DA IMPLEMENTAÇÃO
60
percurso, e, portanto, tem uma fatia maior da roleta e maior chance de serem
selecionados.
Pode-se representar a seleção pelo algoritmo genético em questão pelos
seguintes passos:
� Somar todas as aptidões das populações.
� Calcular o percentual individual de cada indivíduo em relação à população.
� Selecionar um valor percentual aleatoriamente.
� Percorrer o vetor representando a roleta, selecionando um indivíduo.
� Selecionar um valor percentual aleatoriamente.
� Percorrer o vetor representando a roleta, selecionando um indivíduo.
� Comparar os indivíduos que foram selecionados.
� Se estes forem iguais, retornar ao passo 5, caso contrário, realizar o
cruzamento.
A Figura 5.7 apresenta o pseudocódigo da seleção por roleta.
CAPITULO V – DETALHES DA IMPLEMENTAÇÃO
61
// soma todas as distancias
SomaAptidao:=0;
for i := 1 to MaxPop do
begin
SomaAptidao := SomaAptidao + Pop[i].aptidao;
end;
// calcula a probabilidade (porcentagem) de cada individuo na roleta
for i := 1 to MaxPop do
begin
Pi[i] := Pop[i].aptidao / SomaAptidao;
end;
Ci[1] := Pi[1];
for i := 2 to MaxPop do
begin
Ci[i] := Ci[i-1] + Pi[i];
end;
//METODO ROLETA - Escolhe aletoriamente o elemento para fazer o
cruzamento
E1 := SelecionaIndividuo((RandomRange(0,100)/100));
repeat
E2 := SelecionaIndividuo((RandomRange(0,100)/100));
until E1 <> E2;
Figura 5.7. Pseudocódigo da seleção por roleta.
De acordo com o código da Figura 5.7 o primeiro passo foi a totalização de
todas as aptidões dos indivíduos (SomaAptidão). Em seguida é calculada a
porcentagem de aptidão de cada individuo (Pi) usando o total da aptidão. Para
finalizar é calculada a porção que cada individuo terá na roleta simulada (Ci). Na
escolha do individuo um número é sorteado aleatoriamente numa faixa de 0 a 100,
mesmo conjunto de valores calculados para a roleta, portanto o individuo escolhido é
aquele que possui na sua porção o número sorteado (SelecionaIndividuo).
5.8 Método de Cruzamento
O método de cruzamento PMX (descrito no item 2.2.7), é o operador que
permite uma maior variação na troca dos genes entre os cromossomos envolvidos
no cruzamento, sem propiciar a repetição de um gene referente ao mesmo ponto, e,
também, é o mais utilizado na maioria das implementações de AG’s. Assim, foi
utilizado um operador de cruzamento baseado no método do PMX, caracterizando
um híbrido com determinadas variações necessárias de acordo com o problema
específico. A Figura 5.8 apresenta o pseudocódigo do cruzamento, que faz uso do
elitismo para preservar os melhores indivíduos.
CAPITULO V – DETALHES DA IMPLEMENTAÇÃO
62
Randomize();
for i:=1 to 500 do if pop[E1].ind[i] = 0 then break;
pontos1 := i-1;
for i:=1 to 500 do if pop[E2].ind[i] = 0 then break;
pontos2 := i-1;
tents :=0;
compativel := false;
repeat
inc(tents);
Corte1 := RandomRange(3,Pontos1-2);
for i:=pontos2 downto 1 do
if (pop[E2].ind[i] = pop[E1].ind[Corte1]) then
begin
compativel := true;
Corte2 := i;
end;
if tents > 10 then break;
until compativel;
if (Corte1 + (Pontos2-Corte2)) > 500 then exit;
if (Corte2 + (Pontos1-Corte1)) > 500 then exit;
for i:=1 to 500 do
begin
aux[i] := pop[E1].ind[i];
end;
filho1 := E1; filho2 := E2;
if (E1 = 1) then begin
for i:=1 to 500 do pop[maxpop].ind[i] := pop[E1].ind[i];
filho1 := MaxPop;
end;
if (E2 = 1) then begin
for i:=1 to 500 do pop[maxpop].ind[i] := pop[E2].ind[i];
filho2 := MaxPop;
end;
j := Corte2;
for i:=Corte1 to 500 do
begin
Pop[filho1].ind[i] := Pop[E2].ind[j];
Inc(j);
if j > 500 then break;
end;
j := Corte1;
for i:=Corte2 to 500 do
begin
Pop[filho2].ind[i] := Aux[j];
Inc(j);
if j > 500 then break;
end;
Figura 5.8. Pseudocódigo do Cruzamento.
O pseudocódigo da Figura 5.8 apresenta primeiramente a verificação da
compatibilidade de cruzamento dos dois indivíduos selecionados (E1 e E2). Após a
verificação um ponto de corte é escolhido aleatoriamente (Corte1) no primeiro
indivíduo, e em seguida o índice que representa o primeiro ponto de corte é
localizado no segundo indivíduo (Corte2). As partes posteriores aos pontos de corte
são trocadas finalizando o processo de cruzamento.
CAPITULO V – DETALHES DA IMPLEMENTAÇÃO
63
A Figura 5.9 ilustra o método de cruzamento do híbrido do cruzamento
binário, que ocorre entre dois indivíduos selecionados, denominados pais,
recombinando seus genes para originar outros indivíduos, denominados filhos, assim
como no sistema biológico natural. O processo de cruzamento obedece a uma
restrição eliminatória. Um ponto de corte aleatório, aponta para um cruzamento
(ponto ou coordenada x e y). Para haver o cruzamento é necessário que o outro
indivíduo escolhido também possua esse mesmo ponto, pois o indivíduo é
constituído de uma seqüência válida de coordenadas. Dessa forma é possível
melhorar o indivíduo sempre que uma parte considerada ruim (maior distância) seja
trocada por uma outra parte considerada boa (menor distância).
Pi 4 3 6 2 5 1
5
5
8
8
4
4
7
7
6
6
1
1
3
3
2
2
P i
P i
P f ...
P i 4 3 6 2 5 1 Pf ...
6 2 5 1 Pf ...
P f ...
6 1 3 2 P f ...
PA I 1
FIL H O 1
PA I 2
FIL H O 2
P i - Ponto Inicia l / Pf - Pon to F inal
Figura 5.9. Exemplificação do cruzamento do híbrido do PMX.
O método de cruzamento implementado pode ser descrito pelos seguintes
passos:
� Definir o primeiro ponto de corte.
� Verificar compatibilidade entre os indivíduos.
� Repetir: alterar os genes do indivíduo A com os genes do indivíduo B, entre
os pontos de corte, analisando as possíveis conexões entre os pontos.
5.9 Criação dos objetos
No protótipo são encontrados objetos que foram modelados por meio
de um modelador 3D (3D Studio Max). Este software permite a modelagem de
objetos bem como a renderização de imagens e animação de cenas. Na Figura 5.10
é demonstrado o ambiente do software com os objetos modelados, alguns destes
CAPITULO V – DETALHES DA IMPLEMENTAÇÃO
64
objetos utilizam formas básicas para a sua modelagem como esferas, cones e
cubos.
Figura 5.10. Modelador 3D (3D Studio Max).
5.10 Modelagem Geométrica
A modelagem geométrica teve início com o desenho de todos os
componentes do bairro usado neste protótipo. A base para o desenho foi o modelo
2D, portanto o modelo 3D segue exatamente as proporções e dimensões do modelo
anterior. Alguns objetos foram modelados seguindo com exatidão o objeto real (um
prédio público, uma referência histórica, e outros que merecem destaque), outros
objetos foram modelados seguindo uma generalização (casas e outros prédios).
Cada cruzamento do trecho urbano é um objeto e pode ser selecionado pelo usuário
para permitir uma prévia configuração do sistema (base de dados de cruzamentos,
definições de direções do cruzamento em relação a outros). Outros objetos da cena
são os espaços prediais, também selecionáveis e passíveis a associações a uma
biblioteca de outros objetos (casas, prédios, praças, e outros considerados turísticos:
aeroporto, zoológico, lagos, e etc.). Esses objetos são selecionáveis mediante o
comando OpenGL GlPicking. O resultado dessa modelagem construída com o uso
CAPITULO V – DETALHES DA IMPLEMENTAÇÃO
65
do software 3D Studio MAX foi transformada para um arquivo com extensão .3DS, o
qual possui detalhes geométricos divulgados pelo fabricante permitindo o uso do
mesmo.
5.11 Conversão de Formatos
A conversão do formato 3DS conforme a Figura 5.11, foi construída usando o
ambiente de programação Borland Delphi TM e baseia na geração de um objeto
contendo como propriedades matrizes de índices, vértices, normais, materiais e
texturas do modelo geométrico transformando em triângulos. O principal método
desse objeto é a função draw, que por meio da diretiva GL_TRIANGLES desenha
todo o objeto na cena. A Figura 5.11 apresenta o código que realiza a leitura do
arquivo 3DS.
CreateGLContext(Handle)
Model:=T3DModel.Create
Model.LoadFromFile('cidade.3ds')
glEnable(GL_LIGHT0)
glEnable(GL_LIGHTING)
glPointSize(4)
EnviromentMap
Figura 5.11. Código para importação do arquivo 3DS.
5.12 Navegação e Visualização
O processo de navegação baseia-se na seqüência de pontos, gerada pelo
algoritmo genético, e, se não houver interferência do usuário, o resultado final será
um passeio pela cidade virtual na rota estabelecida. O usuário poderá acelerar o
passeio, diminuir a velocidade, parar e dar um giro completo sobre o seu eixo.
Para tanto o usuário dispõe de teclas configuradas para essa operação, essas
teclas são: SETA PARA CIMA, SETA PARA BAIXO, SETA PARA ESQUERDA E
SETA PARA DIREITA. A sensação de navegação é propiciada por transformações
geométricas sofridas pelo ambiente, ou seja, o ponto de visão é sempre o mesmo, o
que altera é o posicionamento do ambiente. A Figura 5.12 apresenta o código
responsável por essa navegação e visualização do ambiente.
CAPITULO V – DETALHES DA IMPLEMENTAÇÃO
66
if Msg.wParam = VK_Down then begin
TX := TX - sin(ROT*pi/180);
TZ := TZ + cos(ROT*pi/180); end;
if Msg.wParam = VK_Up then begin
TX := TX + sin(ROT*pi/180);
TZ := TZ - cos(ROT*pi/180);
if Msg.wParam = VK_Left then begin
ROT := ROT - 1;
IF ROT < 0 THEN ROT := ROT + 360;
if Msg.wParam = VK_Right then begin
ROT := ROT + 1;
IF ROT > 360 THEN ROT := ROT - 360;
glRotate(ROT, 0, 1, 0);
glTranslatef(TX, TY, TZ);
Figura 5.12 Código que implementa a navegação e visualização do ambiente.
De acordo com a Figura 5.12 é possível perceber existe uma transformação
geométrica de rotação (glRotate) e uma outra de translação (glTranslate) calculadas
de acordo com o posicionamento inicial do ambiente e possíveis com o uso das
funções seno e co-seno do ângulo atual em que o objeto se encontra. Para a
navegação sem interferência do usuário, ou seja, a sugerida pelo Algoritmo
Genético, foi necessário calcular o ângulo para cada cruzamento da seqüência, e o
deslocamento na direção do cruzamento para calcular o novo ângulo para o
seguinte até encerrar o trajeto. A Figura 5.13 ilustra o código implementado para
essa situação.
PXI := PontoXInicial; PXF := PontoXFinal;
PYI := PontoYInicial; PYF := PontoYFinal;
DeltaX := (PXI - PXF); DeltaY := (PYI - PYF);
ângulo := RadtoDeg(ArcSin(abs(DeltaX / Hypot(DetaX,DeltaY))));
ROT := RotacaoOriginal + Angulo;
TX := TX + 0.1 * sin(ROT*pi/180);
TZ := TZ - 0.1 * cos(ROT*pi/180);
If TX = PontoXFinal and TY = PontoYFinal
RecalculaAngulo;
Figura 5.13. Pseudo-código que implementa a navegação automática.
A visualização da rota virtual inicia com o posicionamento do ponto de visão
sobre o objeto que representa o ponto inicial. E, para ter a sensação de estar por
exemplo dentro de um carro com um posicionamento acima do solo e tendo como
referência um ponto de visão baseado no horizonte foi usada uma diretiva OpenGL
de visualização (gluLookAt(0, 8, 0, 0, 5, 120, 0, 1, 0)). Outras interações possíveis
no ambiente (barra de navegação – Figura 5.15) foram possíveis por meio de outros
métodos do objeto criado. Apesar de não ser uma tendência na área de Realidade
CAPITULO V – DETALHES DA IMPLEMENTAÇÃO
67
Virtual, o uso de uma barra tradicional foi usada devido aos altos custos de
implementação de um sistema de Realidade Virtual Imersiva.
Figura 5.14. Barra de navegação do ambiente.
5.13 Desenvolvimento do Ambiente Virtual
O Ambiente Virtual, como já foi dito anteriormente, foi criado por meio do uso
da biblioteca gráfica OpenGL, sendo necessário o uso do ambiente de programação
Borland Delphi TM 6.0 para compilação do código e implementação da interação do
usuário com o ambiente e para as animações necessárias. A estrutura construída do
ambiente virtual foi desenvolvida para permitir que qualquer cidade modelada possa
ser manipulada na geração de rotas.
5.14 Considerações Finais
A implementação do sistema foi realizada utilizando-se uma linguagem de
programação orientada a objetos e a eventos, disponibilizando recursos para a
criação de uma estrutura de dados que modelasse de forma satisfatória a
problemática do algoritmo, o que facilitou bastante a implementação de uma
interface amigável ao usuário, bem com a programação de funções e estruturas
específicas da modelagem conceitual do Algoritmo Genético e para geração de um
Ambiente Virtual.
CAPITULO VI – FUNCIONAMENTO DO SISTEMA
CAPÍTULO VI
6 FUNCIONAMENTO DO SISTEMA
6.1 Introdução
Este capítulo descreve a forma de funcionamento do sistema, os parâmetros
de entrada necessários para a execução do algoritmo e os passos para que o
processamento do sistema seja desempenhado de forma correta. Também
apresenta as funcionalidades do ambiente virtual que simula o bairro de uma cidade.
6.2 Parâmetros Genéticos
Para o funcionamento do sistema são necessários alguns parâmetros de
entrada, os quais irão guiar o processamento do AG em busca da melhor solução,
ou seja, da melhor rota a ser seguida, como mostra a Figura 6.1, esses parâmetros
podem ser configurados dentro do próprio sistema.
Figura 6.1. Parâmetros Genéticos.
CAPITULO VI – FUNCIONAMENTO DO SISTEMA
69
Tais parâmetros são:
� Tamanho da população: este parâmetro define o tamanho da população,
isto é, a quantidade de indivíduos a serem gerados na população.
� Taxa de cruzamento: este parâmetro define a probabilidade com que um
cruzamento ocorrerá dentro da população, ou seja, define a porcentagem de
indivíduos que irão participar do cruzamento. O valor pré-definido é de 60%, pois
esta é a taxa adotada na maioria das implementações de Algoritmos Genéticos, no
entanto, o usuário pode alterar esse valor conforme sua necessidade.
� Quantidade de gerações: este parâmetro define o número de gerações que
deverão ocorrer no AG em busca da melhor solução. Este valor é determinado pelo
usuário de acordo com a problemática específica.
6.3 Processamento e Resultado
Inicialmente, o sistema apresentará além dos parâmetros genéticos,
parâmetros relacionados aos cruzamentos existentes que serão usados na rota, os
quais deverão ser definidos pelo usuário ou carregados diretamente, conforme
mostra a Figura 6.2, onde existe um menu para a configuração das conexões.
Figura 6.2. Menu Conexões.
A partir deste menu o usuário poderá:
� Iniciar Conexão: Inicia o processo de conexão que consiste em definir
diretamente no mapa quais cruzamentos serão usados.
� Definir Conexões: Definir a direção de cada conexão em relação à outra
(caso de ruas de mão única, esse passo é importante).
CAPITULO VI – FUNCIONAMENTO DO SISTEMA
70
� Ponto Inicial: Essa é uma das principais opções da interface, é responsável
por definir qual será o ponto de partida.
� Carregar Cruzamentos: Opção que possibilita o carregamento automático
de todos os pontos previstos como cruzamento no mapa.
� Limpar Cruzamentos: Essa opção é inversa a opção anterior, limpando
todos os cruzamentos cadastrados.
Após a configuração de cada conexão entre os pontos, o sistema apresentará
a interface principal, conforme mostra a Figura 6.3.
Figura 6.3. Interface inicial do sistema.
A Figura 6.4 ilustra também a interface com os cruzamentos já escolhidos e o
algoritmo disparado mostrando o gráfico da relação da distância para geração.
CAPITULO VI – FUNCIONAMENTO DO SISTEMA
71
Figura 6.4. Ponto Inicial e Ponto Final Definidos.
A Figura 6.5 ilustra também a interface com os cruzamentos já escolhidos e o
algoritmo disparado mostrando o gráfico da relação da distância para geração.
Figura 6.5. Gráfico Menor Distância.
O sistema após o processamento demonstra a melhor rota encontrada, que
poderá ou não ser realmente a melhor possibilidade, e irá plotar a mesma sobre o
mapa, conforme demonstrado na Figura 6.6.
CAPITULO VI – FUNCIONAMENTO DO SISTEMA
72
Figura 6.6 Interface após processamento.
Se o usuário deseja escolher outros cruzamentos a serem participantes da
trajetória, ou buscar uma nova rota baseadas nos mesmos pontos, deverá clicar no
botão “REINICIAR”. Para reiniciar o processamento do algoritmo, após a redefinição
ou não dos parâmetros. Logo após deverá clicar novamente no botão “EVOLUIR” e
o sistema irá plotar no mapa uma nova rota. Conforme mostra a Figura 6.7:
Figura 6.7 Botões Evoluir e Reiniciar.
CAPITULO VI – FUNCIONAMENTO DO SISTEMA
73
A interface 3D além de oferecer ao usuário uma navegação pela rota gerada
pelo algoritmo, que pode ser visualizada através do menu Modelo de Visão,
conforme a Figura 6.8.
Figura 6.8 Menu Modelo de Visão.
A seleção do modelo de visão 3D leva a interface 3D que melhor visualizada
pela Figura 6.9
Figura 6.9 Visão superior da Cidade Virtual.
A barra de navegação existente no sistema, apresenta funções para o auxilio
na navegação pelo ambiente, conforme apresentamos na Figura 6.10.
CAPITULO VI – FUNCIONAMENTO DO SISTEMA
74
Figura 6.10. Barra de Navegação do Sistema 3D.
A tabela 6.1 mostra as funções de cada botão da barra de navegação do
sistema 3D.
Tabela 6.1 Funções da Barra de Navegação.
ICONE NOME FUNÇÕES
Navegação Navegação (translação) no eixo Z do ambiente.
Iniciar Posição inicial da cidade com visão do topo.
Navegar Inicia a navegação por uma rota estabelecida ou permite ao usuário navegar livremente.
Ocultar imóveis
Oculta todos os imóveis da cidade mostrando apenas as ruas e cruzamentos.
Exibir imóveis Exibe todos os imóveis da cidade.
Ao iniciar o processo de Navegação do sistema, este vai direto ao ponto
inicial determinado pelo usuário e posiciona para percorrer o caminho, e inicia o
movimento. A cada “esquina” encontrada, é feita a parada e o reposicionamento
para a direção correta do percurso, conforme a Figura 6.11.
O que torna o ambiente mais interativo é de que não ha necessidade de
seguir apenas o caminho definido pelo sistema, podendo o usuário interferir e parar
a qualquer momento.
CAPITULO VI – FUNCIONAMENTO DO SISTEMA
75
Figura 6.11 Interface 3D do percurso.
Este Modelo de Visão 3D também propicia a visão do ambiente sem os
objetos (imóveis), que é acionada ocultando imóveis, conforme a Figura 6.12.
Figura 6.12 Visão do ambiente sem os objetos.
6.4 Considerações Finais
O sistema apresenta uma interface amigável para o usuário e fácil de ser
utilizada, onde o mesmo não necessita de conhecimentos computacionais
CAPITULO VI – FUNCIONAMENTO DO SISTEMA
76
específicos para utilizar o sistema, bastando apenas ter conhecimento do ambiente
operacional.
É necessário somente a correta definição dos parâmetros, e caso o usuário
não queira alterá-los, todos já estão pré-definidos, oferecendo suporte a um bom
processamento do algoritmo. Além disso, é preciso também uma correta escolha dos
cruzamentos participantes e definição das possíveis conexões.
CAPITULO VII– RESULTADOS /LIMITAÇÕES
CAPÍTULO VII
7 RESULTADOS / LIMITAÇÕES
7.1 Introdução
Neste capítulo, é apresentada uma análise do protótipo descrito nos Capítulo
5 e 6. Esta análise teve como objetivo demonstrar a viabilidade, a eficácia e
eficiência do protótipo. A análise realizada abrange os seguintes aspectos:
a) A obtenção da melhor rota por meio do Algoritmo Genético.
b) Reprodução da rota em um Ambiente Virtual.
Estes resultados são constatados visualmente e não foi necessária a
construção de uma metodologia específica para identificar o correto resultado
7.2 Ambiente Experimental
Como ambiente para o experimento, foi usado um microcomputador
compatível com IBM PC (Pentium IV 3.2 MHz; memória RAM 512 Mbytes e Disco
Rígido de 80 Gbytes). Não foi utilizada nenhuma placa de vídeo aceleradora,
portanto a parte gráfica não necessita de periféricos específicos.
7.3 Análise dos Resultados Obtidos
O estudo de caso usado foi apenas um bairro da cidade de Uberlândia-MG,
obedecendo às restrições de mão e contramão. Mesmo sendo um pequeno bairro,
existem no mesmo, 75 cruzamentos o que provoca, dependendo da escolha do
ponto inicial e do ponto final um número grande combinações. No entanto foi
CAPITULO VII– RESULTADOS /LIMITAÇÕES
78
possível analisar visualmente se algoritmo encontrou ou não a melhor solução. Os
parâmetros genéticos (População, Taxa de Cruzamento e Quantidade de Gerações)
devem ser configurados para exigir o menor esforço computacional possível. Dessa
forma o sistema apresenta em sua interface inicial o resultado de testes que
demonstraram que 90% dos casos os parâmetros genéticos foram suficientes:
� População: 50 indivíduos
� Taxa de Cruzamento: 50%
� Quantidade de Gerações: 20.
O processo de “paralisia” aconteceu freqüentemente nos testes
demonstrando que a melhor solução poderia ser encontrada em alguns casos nas
primeiras gerações. O sistema não possui opção de parada por paralisia, pois foram
constatados nos testes, que algumas situações depois de um período de paralisia,
havia sempre alteração na aptidão de indivíduos menos aptos, possibilitando
também melhoria na aptidão do melhor indivíduo.
Para o teste do ambiente virtual, o parâmetro de avaliação adotado foi a
verificação se a navegação obedecia a seqüência sugerida pelo algoritmo genético.
7.3.1 Comparação com outros trabalhos
De acordo com Tabela 7.1, o protótipo desenvolvido neste trabalho
denominado de Rota Virtual atendeu todos os itens avaliados, sendo seu principal
diferencial em relação aos outros trabalhos e a principal contribuição deste.
CAPITULO VII– RESULTADOS /LIMITAÇÕES
Tabela 7.1 Comparação com outros trabalhos
CAPITULO VII– RESULTADOS /LIMITAÇÕES
7.4 Avaliação do Sistema
O sistema foi apresentado a 20 (vinte) usuários, sendo 15 (quinze)
pesquisadores (professores e estudantes) da área de computação, além de usuários
específicos (cinco) da área de turismo de uma prefeitura.
Primeiramente, foi explicado a esses usuários o objetivo do sistema e, em
seguida, o grupo testou coletivamente o sistema. Após a execução do sistema, os
usuários responderam a um questionário.
Analisando as respostas nos questionários, foi possível avaliar os itens que
seguem abaixo e para cada item foi gerado um gráfico comparativo.
7.4.1 Quanto à finalidade do uso da ferramenta:
No gráfico da Figura 7.1, observa-se que a grande maioria dos usuários
respondeu que o sistema é muito útil. Algumas pessoas que responderam que o
sistema é útil justificaram as suas respostas, considerando que o sistema é
adequado apenas como recurso adicional na definição de rotas.
Figura 7.1. Análise quanto à finalidade.
CAPITULO VII– RESULTADOS /LIMITAÇÕES
81
7.4.2 Quanto à interface com o usuário:
Baseados na Figura 7.2, podem verificar que a maior parte das pessoas que
avaliou o sistema como muito intuitivo e intuitivo e apenas três usuários o
consideraram pouco intuitivo e não justificaram as suas respostas, a maioria das
pessoas elogiou sistema mesmo o considerando intuitivo, e outras citaram a
necessidade de um prévio conhecimento de Informática para a execução do mesmo.
Figura 7.2. Análise quanto a Interface.
7.4.3 Quanto à facilidade de uso:
Observando o gráfico na Figura 7.3, a maioria dos usuários considerou os comandos
apresentados de fácil entendimento, os demais justificaram a necessidade de um
prévio conhecimento de Informática, considerando que muitos usuários poderão ter
dificuldades em executar os comandos, exigindo antes da execução a apresentação
de algumas informações adicionais para operacionalização do sistema.
CAPITULO VII– RESULTADOS /LIMITAÇÕES
82
Figura 7.3. Análise quanto à facilidade de uso.
7.4.4 Quanto aos recursos do programa
O programa permitiu a definição clara de um ponto de origem e um ponto de
destino, demonstrando a melhor rota?
Figura 7.4. Análise quanto aos recursos do programa.
Pelo gráfico da Figura 7.4, pode-se observar que a maioria dos usuários, que
respondeu ao questionário, considerou que o programa permitiu a aquisição de
CAPITULO VII– RESULTADOS /LIMITAÇÕES
83
informações úteis a respeito de rotas virtuais.
Em uma outra avaliação do sistema, de acordo com as normas ISO/IEC 9126
(ISO, 1991), foram obtidos os seguintes resultados como mostra a Figura 7.5.
Figura 7.5. Análise dos aspectos de avaliação para softwares
Analisando todos os itens avaliados nos questionários, conclui-se que o
sistema protótipo desenvolvido foi bem aceito pelos usuários entrevistados. Estes
contribuíram com algumas sugestões, descritas a seguir:
� A interface do 2D que representa o funcionamento do algoritmo genético
foi criticada por aqueles que não conhecem o conceito de computação evolutiva,
principalmente pelos usuários específicos da área. A sugestão feita refere-se aos
parâmetros genéticos que deveriam ser colocados como meios para melhorar a
eficácia do protótipo.
� Para os pesquisadores da área a principal sugestão foi a inserção de
uma cidade completa com a existência de vários bairros.
� Analisando a avaliação feita pelos usuários e as sugestões propostas
pelos mesmos, constatou-se que houve motivação por parte deles na utilização do
sistema, comprovando a importância da utilização de sistema de rotas virtuais.
7.5 Considerações Finais
Os testes e as avaliações realizadas com o protótipo demonstraram a sua
eficácia e o potencial como produto para ser utilizado por prefeituras, hotéis e
CAPITULO VII– RESULTADOS /LIMITAÇÕES
84
empresas que necessitam de definição de rotas e principalmente que essas rotas
sejam visualizadas de forma atrativa com mecanismos interativos que conquistem o
usuário. Em automóveis já existem essas iniciativas que geram o trajeto para o
motorista. Porém a iniciativa de uma rota 3D traria mais confiabilidade ao motorista
ao confrontar o local onde está com que lhe é apresentado pelo protótipo.
CAPITULO VIII - CONCLUSÕES E TRABALHOS FUTUROS
85
CAPITULO VIII
8 CONCLUSÕES E TRABALHOS FUTUROS
8.1 Introdução
Este capítulo apresenta os principais tópicos discutidos nesse trabalho,
relaciona os possíveis trabalhos futuros advindos dessa pesquisa e avalia a principal
contribuição da mesma.
8.2 Conclusões
Durante a pesquisa, constatou-se que existem diversas iniciativas para
solucionar problemas relacionados à definição de rotas urbanas e interurbanas.
Também foi constatada a existência de modelos de cidades virtuais modeladas e
confeccionadas de acordo com as peculiaridades de cada trabalho.
A RV tem demonstrado ser uma poderosa ferramenta de apoio a projetos
cartográficos. A análise visual e a sensação de presença no mundo virtual são
alguns dos maiores benefícios trazidos por esta tecnologia.
CAPITULO VIII - CONCLUSÕES E TRABALHOS FUTUROS
86
Portanto, A maior contribuição deste trabalho foi criar uma Arquitetura que
uniu a área de AG e RV na construção de um AV que represente rotas virtuais
seguindo a orientação dada pelo AG.
8.3 Trabalhos Futuros
Como continuação deste trabalho, considera-se importante os seguintes
temas:
1 - Quanto ao algoritmo para busca de soluções ótimas:
� Testar outros modelos de algoritmos.
� Comparar o modelo atual com outros protótipos que possuem alteração nas
características dos operadores genéticos.
� Realizar testes com um universo maior de possibilidades, por exemplo, usar
uma cidade em sua totalidade.
� Avaliar o protótipo com métricas que calcule a complexidade do algoritmo e
o esforço computacional.
2 - Quanto às técnicas de RV:
� Construir modelos menores em bytes que podem ser portáveis para a WEB.
� Testar outras metodologias de busca e conversão de mapas para aproveitar
a modelagem 2D.
� Adaptação a outros modelos, como por exemplo CAD.
� Permitir a interação do usuário com os objetos existentes na cidade, por
exemplo, entrar em um Museu, Zoológico, Cinema e outros.
� Construir modelos geométricos a partir de coordenadas verdadeiras usando
GPS podendo estabelecer rotas virtuais de com base no posicionamento real do
usuário.
REFERÊNCIAS BIBLIOGRÁFICAS
87
REFERÊNCIAS BIBLIOGRÁFICAS
ALMEIDA, Marcelo Mazetto Aragão. Uso de Algoritmos Genéticos como
Proposta na Redução de Custos de Energia Elétrica em Armazéns Gerais. 6th
Encontro de Pesquisa e 4th Encontro de Iniciação Científica, Itumbiara-GO,
Novembro, 2005.
ANDRADE, Márcio Faria. Elaboração da Grade Horária de Trabalho para
Funcionários de uma Lavanderia usando Algoritmos Genéticos. 6th Encontro de
Pesquisa e 4th Encontro de Iniciação Científica, Itumbiara-GO, Novembro, 2005.
AUKSTAKALNIS, S; BLATNER, D. Silicon Mirage: The Art and Science of Virtual
Reality. Berkeley: Peatchpit Press, 1992. 235p.
BARCELLOS, João Carlos Holland de. Algoritmos Genéticos Adaptativos: Um
estudo comparativo. 2000, 143 p. Dissertação (Mestrado em Engenharia) – Escola
Politécnica, Universidade de São Paulo; São Paulo, 2000.
BATISTA, Rejaine Marques; RIBEIRO, Marcos Wagner de Souza. O Uso de
Algoritmos Genéticos na Solução de Rotas em Trechos Urbanos. VII Encontro
de Pesquisa, ILES/ULBRA – Instituto Luterano de Ensino Superior/ Universidade
Luterana do Brasil, Itumbiara-Goiás, Novembro de 2006.
BESSA, Wender Borges. Uso de Algoritmos Genéticos na Construção de Rotas
Turísticas. VI Encontro de Pesquisa, ILES-ULBRA – Instituto Luterano de Ensino
REFERÊNCIAS BIBLIOGRÁFICAS
88
Superior / Universidade Luterana do Brasil Itumbiara-Goiás, Novembro de 2005, 47
p.
BYRNE, C. M. The Use of Virtual Reality as Educational Tool. Washington
University. Disponível em <http://www.hitl.washington.edu/publications>. Acesso em:
10 junho 2005.
CAMACHO, M. de L. A. S. M. Realidade Virtual e Educação. Lisboa, Universidade
Aberta. Disponível em <http://phoenix.sce.fct.unl.pt/simposio/30.htm>. Acesso em:
10 junho 2006.
CARMO, Daniele Leite do. Aplicação de Algoritmos Genéticos no
Desenvolvimento de Rotas Turísticas. 2004. 67 p. Trabalho de Final de Curso
(Bacharel em Sistemas de Informação), Uniminas; Uberlândia, 2004.
CRUZ-NEIRA, C. et al. The CAVE Audio Visual Experience Automatic Virtual
Environment. Communication of the ACM, Jun. 1992. p.64-72.
DALBONI, Fábio Linhares. Algoritmos Evolutivos Eficientes para um Problema
de Roteamento de Veículo. 2003, 141 p. Dissertação (Mestrado em Computação
Aplicada e Automação) – Curso de Pós-Graduação em Computação Aplicada e
Automação, Universidade Federal Fluminense; Rio de Janeiro, 2003.
FOSSE, Juliana Moulin; VEIGA, Luis A.Koenig. Realidade Virtual como ferramenta
na Cartografia 3D. Universidade Federal do Paraná. 2003 Disponível
em:<http://geodesia.ufsc.br/geodesia-online/arquivo/geocoloq_2003/artigos/t031.pdf
> Acesso em 25 de Janeiro 2007.
GOLDBERG, David Edward. Genetic Algorithms in Search, Optimization, and
Machine Learning. Canadá: Addison-Wesley Publishing Company Inc., 1989, 412 p.
ISO/IEC 9126.. Software Product Evaluation - Quality Characteristics and
Guideline for their Use. International Standards Organization, 1991.
JUNIOR, Osmar de Oliveira Braz. Otimização de horários em instituições de
ensino superior através de algoritmos genéticos. 2000, 144 p. Dissertação
(Mestrado em Engenharia de Produção) – Programa de Pós-Graduação em
REFERÊNCIAS BIBLIOGRÁFICAS
89
Engenharia de Produção, Universidade Federal de Santa Catarina; Florianópolis,
2000.
KELNER, Judith et al. Modelagem Virtual Urbana: Perspectiva Histórica e
Estudo de Caso. In: V Symposium on Virtual Reality, 2002, Fortaleza, CE. Anais V
Symposium on Virtual Reality - Fortaleza: SBC, 2002, pp. 280-290.
KIRNER, Cláudio. PINHO, M. S. Sistemas de Realidade Virtual. Grupo de
Pesquisa em Realidade Virtual, Departamento de Computação – UFSCar. 1997.
Disponível em <http://www.dc.ufscar.br/~grv/>. Acesso em 20 de setembro 2006.
LUCAS, Diogo Correa. Algoritmos Genéticos: um estudo de seus conceitos
fundamentais e aplicação no problema da grade horária. 2000, 66 p. Monografia
(Bacharelado em Informática) – Instituto de Física e Matemática. Universidade
Federal de Pelotas; Pelotas, 2000.
MACHOVER, Carl Machover. The promise of virtual reality. Eurographics '94.
Oslo, Norway, September 1994. Tutorial Notes EG'94 TN1.
MOREIRA, Maria Isabel Giusti; AGUIAR, Dr. Marilton Sanchotene. Um Sistema
Classificador de Imagens de Sensoriamento Remoto Baseado em Algoritmos
Genéticos. In: XVIII Congresso Nacional de Matemática Aplicada e Computacional,
2005, São Paulo. Anais; São Paulo: SENAC, 2005. p. 1-6.
NARCISO, Marcelo Gonçalves; LORENA, Luiz A. Nogueira. Uso de Algoritmos
Genéticos em Sistemas de Apoio a Decisão para Alocação de Recursos no
Campo e na Cidade. In: III Congresso Brasileiro da SBI-AGRO - Sociedade
Brasileira de Informática aplicada a Agropecuária e Agroindústria, 2002, Foz do
Iguaçu. III Congresso da SBI-Agro; Campinas: Embrapa Informática Agropecuária,
2002.
PIMENTEL, João; BATISTA, Nuno; GOES, Luiz; DIONÍSIO, José. Construção e
Gestão da Complexidade de Cenários Urbanos 3D em Ambientes Virtuais
Imersivos. Disponível em <http://visualis.ist.pt.> Acesso em 20 de janeiro de 2006.
REFERÊNCIAS BIBLIOGRÁFICAS
90
PINHO, M. S. Biblioteca Gráfica OpenGL. Disponível em:
http://www.inf.pucrs.br/~pinho/CG/Aulas/OpenGL/OpenGL.html Acesso em: 18 jul.
2006.
_________. M. S. Manipulação Simultânea de Objetos em Ambientes Virtuais
Imersivos. 2002. 174f. Tese (Doutorado em Ciência da Computação) –
Universidade Federal do Rio Grande do Sul, UFRGS, Rio Grande do Sul, 2002.
POZO, Aurora; et all. Computação Evolutiva. Grupo de Pesquisas em Computação
Evolutiva – Departamento de Informática, Universidade Federal do Paraná; Curitiba,
[2000?], 61 p. Disponível em: <http://www.ufpr.br>. Acesso em: 10.05.2007
REBELLO, Fabrício Rocha; HAMACHER, Silvio. Uma Proposta de AG de Duas
Fases para Roteamento de Veículos. In: XXXII Simpósio Brasileiro de Pesquisa
Operacional, 2000, Viçosa. Anais; Viçosa, 2000. p. 672-688.
RIBEIRO, Glaydston Mattos; LORENA, Luiz A Nogueira. Roteamento de Veículos
Dinâmico Usando Algoritmos Genéticos. Disponível em:
<http://www.lac.inpe.br/~lorena/glaydston/Artigo_G_L_ANPET_2.pdf>. Acesso em
20 de fevereiro de 2007
__________. Glaydston Mattos; LORENA, Luiz A. Nogueira. Roteamento de
Veículos Dinâmico usando Algoritmos Genéticos. In: XIX ANPET - Congresso de
pesquisa e ensino em transportes, 2005, Recife. Panorama Nacional da Pesquisa
em Transportes. Rio de janeiro: ANPET, 2005. v. 19. p. 1593-1603.
RODRIGUES, Marco Antonio Pereira. Problema do Caixeiro Viajante: Um
algoritmo para a resolução de problemas de grande porta baseado em busca local
dirigida. 2000, 104 p. Dissertação (Mestrado em Engenharia) – Universidade Federal
de Santa Catarina; Florianópolis, 2000.
SCHUTZ, M. G. F e PIRES, F. M. Uma abordagem para o problema da
optimização de rotas de veículos baseada em operadores genéticos. Inv. Op.
[online]. dez. 2003, vol.23, no.2 [citado 27 Agosto 2007], p.197-209. Disponível em:
<http://www.scielo.oces.mctes.pt/scielo.php?script=sci_arttext&pid=S0874-
51612003000200006&lng=pt&nrm=iso>. ISSN 0874-5161. Acesso em: 10.05.2006
REFERÊNCIAS BIBLIOGRÁFICAS
91
________. M. G. F.; PIRES, F. M. Uma Abordagem para o Problema de
Optimização de Rotas de Veículos Baseada em Operadores Genéticos.
Investigação Operacional, Vol.23, Nº 2, pp.197-209 (2003).
SEMENTILLE, A.C. BREGA, J.R.F., KIRNER, C., KUBO, M.M.. Ambientes Virtuais
Distribuídos usando CORBA: Um Estudo de Caso. In: III Workshop de Realidade
Virtual – WRV´2000, 3, 2000, Gramado-RS. Proceedings Gramado-RS, 2000. p.145-
156.
SOUZA, Darlon Orlamunder de. Algoritmos Genéticos aplicados ao
planejamento do transporte principal de madeira. 2004, 184 p. Dissertação
(Mestrado em Ciências Florestais) – Setor de Ciências Agrárias, Universidade
Federal do Paraná; Curitiba, 2004.
TEIXEIRA, Otávio Noura. Computação Evolucionária: dos aspectos filosóficos à
implementação dos algoritmos genéticos aplicados na solução do problema do
caixeiro viajante simétrico. 2004, 267 p. Trabalho de Conclusão de Curso
(Bacharelado em Ciência da Computação) – Departamento de Informática,
Universidade Federal do Pará; Belém, 2004.
TEIXEIRA, S. Delphi 6, o Guia do desenvolvedor. Rio de Janeiro: Campus, 2002.
WOO, M. et al. OpenGL Programming Guide: the official guide to learning
OpenGL, 3.ed. Reading, Massachusetts: Addison Wesley, 1999. 730 p.
WRIGHT, Richard S. Jr.; SWEET, Michael. OpenGL SuperBible. 2nd ed.
Indianapolis, Indiana: Waite Group Press, 2000. 696 p.
APÊNDICE
92
APÊNDICE
MODELO DO QUESTIONÁRIO DE AVALIAÇÃO DO SISTEMA
APÊNDICE
93
Avaliação do Sistema que Simula o Processo
Avaliador: ___________________________________________
Data da Avaliação: ___/____/2007
Nível de Escolaridade:
( ) Ensino Médio ( ) Ensino Superior ( ) Pós-Graduação
Principais finalidades de utilização do computador: __________________________
___________________________________________________________________
Quanto ao Sistema proposto:
I. Quanto à Finalidade (Eficiência):
( ) Muito útil ( ) útil ( ) pouco útil
(Justificativa)____________________________________________________________________________________________________________________________
II. Quanto à Interface (Usabilidade):
( ) Fácil entendimento dos comandos
( ) Médio entendimento dos comandos
( ) Difícil entendimento dos comandos
(Justificativa)____________________________________________________________________________________________________________________________
III. Quanto à facilidade de uso (Funcionalidade):
( ) Muito intuitivo
( ) Intuitivo
( ) Pouco Intuitivo
(Justificativa)____________________________________________________________________________________________________________________________
IV. Quanto aos recursos do Programa, a experiência proposta (Manutenção):
( ) foi integralmente desenvolvida
( ) foi parcialmente desenvolvida
( ) não foi desenvolvida por completo
(Justificativa)____________________________________________________________________________________________________________________________
IV.b. Os objetos disponíveis permitem:
( ) conceber a experiência proposta
( ) conceber parte da experiência proposta
( ) não permitem conceber a experiência
APÊNDICE
94
(Justificativa)____________________________________________________________________________________________________________________________
IV.c. A relação entre os objetos disponíveis e suas propriedades:
( ) é simples de ser definida e permite o desenvolvimento proposto
( ) não é simples de ser definida, mas permite o desenvolvimento proposto
( ) não é simples de ser definida e não permite o desenvolvimento proposto
(Justificativa)____________________________________________________________________________________________________________________________
IV.d. ( ) Sugiro inserir novos objetos no experimento, tais como: _______________
___________________________________________________________________
IV.e. ( ) Sugiro inserir novas relações entre objetos no experimento, tais como:__________________________________________________________________________________________________________________________________
V. Conseguiu visualizar a rota definida por meio do Ambiente Virtual?
( ) sim
( ) não
( ) em parte
(Justificativa)____________________________________________________________________________________________________________________________
VII. Observações sobre o programa que achar relevante:
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
VIII. Sugestões Adicionais:
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
Assinatura do Avaliador: _______________________________________________
Livros Grátis( http://www.livrosgratis.com.br )
Milhares de Livros para Download: Baixar livros de AdministraçãoBaixar livros de AgronomiaBaixar livros de ArquiteturaBaixar livros de ArtesBaixar livros de AstronomiaBaixar livros de Biologia GeralBaixar livros de Ciência da ComputaçãoBaixar livros de Ciência da InformaçãoBaixar livros de Ciência PolíticaBaixar livros de Ciências da SaúdeBaixar livros de ComunicaçãoBaixar livros do Conselho Nacional de Educação - CNEBaixar livros de Defesa civilBaixar livros de DireitoBaixar livros de Direitos humanosBaixar livros de EconomiaBaixar livros de Economia DomésticaBaixar livros de EducaçãoBaixar livros de Educação - TrânsitoBaixar livros de Educação FísicaBaixar livros de Engenharia AeroespacialBaixar livros de FarmáciaBaixar livros de FilosofiaBaixar livros de FísicaBaixar livros de GeociênciasBaixar livros de GeografiaBaixar livros de HistóriaBaixar livros de Línguas
Baixar livros de LiteraturaBaixar livros de Literatura de CordelBaixar livros de Literatura InfantilBaixar livros de MatemáticaBaixar livros de MedicinaBaixar livros de Medicina VeterináriaBaixar livros de Meio AmbienteBaixar livros de MeteorologiaBaixar Monografias e TCCBaixar livros MultidisciplinarBaixar livros de MúsicaBaixar livros de PsicologiaBaixar livros de QuímicaBaixar livros de Saúde ColetivaBaixar livros de Serviço SocialBaixar livros de SociologiaBaixar livros de TeologiaBaixar livros de TrabalhoBaixar livros de Turismo