Embora as Redes de Computadores estejam bastante sofisticadas e dotadas de modernos algoritmos, observa-se a necessidade de novas tecnologias para melhorar o desempenho das mesmas no que diz respeito à convergência, segurança, confiabilidade entre outros parâmetros. Assim, algumas soluções vêm sendo propostas como Algoritmos Genéticos que também são explorados em outras áreas do conhecimento. Este artigo que venho compartilhar é referente ao meu trabalho de conclusão de curso (TCC) no ano de 2004 em conjunto com alguns colegas. O trabalho apresenta o conceito de Redes de Computadores e dos Algoritmos Genéticos, visto que estes tem-se mostrado eficiente em problemas de otimização e podem ser utilizados em conjunto com os algoritmos tradicionais, além de um estudo para alternativas de roteamento.
O Algoritmo Genético (AG) foi proposto inicialmente por John Holland no final da década de 60, e é um método de busca e otimização baseados no processo de seleção natural que simulam a evolução. Os AGs geram os indivíduos (cadeias de bits) também chamados de cromossomo, para evoluírem em busca da solução de um dado problema. Cada indivíduo representa uma possível solução para o problema, estes são analisados conforme as necessidades (competem entre si) e os mais aptos são selecionados e em seguida cruzados para gerarem um novo indivíduo mais apto e melhor que os anteriores, assim a cada geração, estaria próximo de uma solução para o problema. Se um AG for desenvolvido corretamente, a população (conjunto de possíveis respostas) convergirá a uma solução ótima para o problema proposto, e ao contrario dos processos de busca e otimização tradicionais os AGs trabalham num processo de busca sobre a população de indivíduos em paralelo, assim fazendo a busca em diferentes áreas.
Na estrutura básica de um AG contém quatro operações, o cálculo de aptidão, a seleção, o cruzamento e a mutação, assim os AGs são muito eficientes para busca de soluções ótimas, ou aproximadamente ótimas, em uma grande variedade de problemas. Na figura abaixo, temos a estrutura básica do AG.
Roteamento com Algoritmos Genéticos
O tema em questão consiste em utilizar os AGs para encontrar boas rotas para troca de informação em redes, conseguindo assim, otimizar esse processo. No lugar dos algoritmos tradicionais de roteamento, propõe-se a utilização dos AGs, tomando como base o algoritmo de vetor de distância. Assim, a partir da distância e do custo, poderíamos trabalhar com variáveis visando aumento da velocidade de roteamento e criando condições para futuros estudos com intuito de melhorar a confiabilidade e segurança em redes de computadores.
Abaixo na Figura 2, é mostrado uma pequena rede com os custos entre os nós. Utilizaremos esse pequeno modelo para explicar como empregar os AGs na tarefa de roteamento.
A rede acima (Figura 2), mostra um exemplo básico dos chamados nós de rede. Esses nós estão representados por valores de 0 a 7, sendo que cada um representa um dispositivo da rede (roteador). Cada dispositivo troca informação uns com os outros, analisando o melhor caminho para efetuarem tal troca.
Achou o tema interessante e ficou curioso para saber como e feito os cálculos para se obter a melhor rota? Leia o artigo na integra. Link para download
Git do Projeto