Algoritmos genéticos

Centro de Ciências Naturais e Humanas – CCNH
Bacharelado em Ciência & Tecnologia

Algoritmos Genéticos
Solução em Roteamento de Veículos

Trabalho à ser apresentado na disciplina de:
Origens da Vida e Diversidade dos Seres Vivos (BC-0304)
Prof. Dr. Antônio Sérgio Kimus Braz

Santo André Dezembro de 2012

SUMÁRIO

1. Resumo 5
2. Introdução 5
2.1. Panorama Histórico 5
2.2. Conceitos 7
3. Desenvolvimento da Problemática 10
4. Aplicação 12
4.1. Resultados 14
5. Outros Casos 15
5.1. Petróleo e gás 15
5.2. Música 16
5.3. Telecomunicações 16
5.4. Médica 17
6. Análise e Conclusão 17
7. Referências Bibliográficas 17

Tabela 1 - Analogia entre GAs e Sistema Natural 7
Tabela 2 - Representação dos GAs 8
Tabela 3 - Representações dos GAs 8
Tabela 4 - Exemplo de um genoma 13
Tabela 5 - Parâmetros do Algoritmo Genético 14
Tabela 6 - Resultados obtidos 15

LISTA DE FIGURAS
Figura 1- Amostragem Estocástica Universal 9
Figura 2 – Aplicação do Crossover 9
Figura 3 – Aplicação da Mutação 9
Figura 4 - Possíveis trajetos a partir da localidade 4 12
Figura 5 - Determinação de um percurso 13

1. Resumo

Abordaremos neste trabalho conceitos e aplicação dos algoritmos genéticos em busca da otimização de rotas de transporte onde o número de parâmetros que influenciam no processo apresenta-se em quantidade relativamente elevado.
Palavras Chave: Algoritmos, Roteamento de Transporte, Seleção Natural.

2. Introdução

1. Panorama Histórico Até meados do século XIX, o conceito fixista reinava entre os naturalistas, onde acreditavam que as espécies eram imutáveis e que o surgimento delas se dava através da abiogênese. O trabalho dos naturalistas como de Jean Baptiste Lamarck, que sugeriu uma teoria evolucionária de escala de complexidade, onde os seres vivos se transformariam gradualmente; e de Thomas Robert Malthus, que propôs que fatores ambientais tais como doenças e carência de alimentos, limitavam o crescimento de uma população;