Desenvolvimento do projeto I da disciplina de Sistemas Evolutivos Aplicados a Robótica resolvendo o problema da mochila com uma estratégia de algoritmo genético
- Definição de Algoritmo Genético
- Como funciona?
- Estrutura padrão de um Algoritmo Genético
- O Problema da Mochila
- Código do Projeto
- Vídeo Explicativo
- Referências
Algoritmo de otimização baseado na Teoria da Evolução de Charles Darwin
A Teoria da Evolução de Darwin é fundamentada no mecanismo da Seleção Natural, que explica como as espécies evoluem e se adaptam ao ambiente ao longo do tempo. Esse processo ocorre por meio de etapas evolutivas como cruzamento (crossover), mutação, elitismo e seleção por torneio, entre outras. Essas etapas permitem o desenvolvimento de indivíduos mais adaptados, aumentando suas chances de sobrevivência.
Analogamente, os algoritmos genéticos são técnicas inspiradas na evolução biológica que buscam soluções aproximadas para problemas complexos. Eles passam por várias gerações de indivíduos (ou soluções candidatas) para encontrar respostas ótimas. Esse método é especialmente útil para resolver problemas da classe NP-difícil, como o "Problema do Caixeiro Viajante" e o "Problema da Mochila".
Sendo assim, especificamente para este projeto, vamos trabalhar com o algoritmo evolutivo para o Problema da Mochila!
-
Inicialização da População
O primeiro passo é criar uma população inicial de soluções candidatas. O tamanho dessa população é crucial: se for muito pequena, o algoritmo pode convergir rapidamente para soluções não tão ótimas, ficando preso em máximos locais. Por outro lado, populações muito grandes aumentam o custo computacional, tornando o processo mais lento. O ideal é encontrar um equilíbrio que permita uma boa exploração do espaço de soluções. -
Avaliação de cada indivíduo
Cada indivíduo da população é avaliado por meio de uma função chamada Fitness. Essa função mede a qualidade da solução que o indivíduo representa. Indivíduos com valores de fitness mais altos são considerados mais aptos, ou seja, têm maior chance de "sobreviver" e contribuir para as próximas gerações. -
Seleção de alguns indivíduos
Com base na avaliação, selecionamos os indivíduos que participarão da próxima fase. O objetivo aqui é garantir que as melhores soluções sejam priorizadas, mas sem perder a diversidade da população. Algumas das estratégias de seleção mais comuns incluem:- Proporcional ao Fitness: Indivíduos com fitness mais alto têm maior probabilidade de serem escolhidos, mas isso pode levar à convergência precoce.
- Ranking: Os indivíduos são ordenados com base no fitness, garantindo uma pressão seletiva equilibrada, o que favorece a exploração contínua do espaço de soluções.
- Proporcional ao Fitness: Indivíduos com fitness mais alto têm maior probabilidade de serem escolhidos, mas isso pode levar à convergência precoce.
-
Crossover e Mutação
Crossover (ou cruzamento): Esta é a fase em que dois indivíduos "pais" combinam suas características para gerar novos "filhos". Genes (cromossomos) de cada pai são selecionados aleatoriamente, criando uma nova solução que pode herdar as melhores características de ambos.
Mutação: Aqui, pequenas alterações são introduzidas nos genes dos indivíduos, com o objetivo de preservar a diversidade genética e evitar que o algoritmo fique preso em soluções subótimas. A taxa de mutação deve ser cuidadosamente ajustada — muito alta pode gerar caos (muita aleatoriedade entre os indivíduos), enquanto muito baixa pode reduzir a capacidade de exploração. -
Concepção da nova geração
A nova geração deve ter o mesmo tamanho da anterior. Uma técnica comum nessa etapa é o elitismo, que preserva os melhores indivíduos da geração atual, garantindo que as soluções mais promissoras não sejam descartadas. Isso contribui para uma convergência mais eficiente, mantendo o progresso acumulado. -
Finaliza algoritmo (ou repete os passos até que estar satisfeito com as soluções encontradas)
O algoritmo genético continua iterando até que uma condição de parada seja atendida. As condições mais comuns incluem:- Falta de progresso significativo entre as gerações (convergência).
- Alcance de um nível de fitness considerado satisfatório.
- Um número máximo de gerações predefinido.
- Falta de progresso significativo entre as gerações (convergência).
O problema da mochila consiste na escolha de itens de um conjunto m segundo um limite de capacidade do sistema L, costumeiramente dado por peso ou tamanho.
Deve-se preencher a mochila de forma a obter o máximo valor de utilidade. Cada item possui um peso p_i e um valor v_i.
Especificamente para este projeto, o problema é formulado da seguinte forma:
O acesso para o código do projeto e visualização detalhada do funcionamento do algoritmo, podem ser vistos aqui.
O código pode ser executado na plataforma Colab Research da Google, basta acessar o link mencionado, acessar a aba de Ambiente de Execução e clicar em Executar Tudo (ou utilizar o atalho CTRL+F9)
O vídeo explicando o Problema da Mochila com Algoritmo Evolutivo pode ser acessado aqui