Algoritmos Genéticos em Java - Java Magazine 82

O aumento da concorrência no mercado de software tem direcionado a atenção de desenvolvedores para conceitos, técnicas e tecnologias que criem diferenciais competitivos e contribuam para que seus produtos ocupem uma posição de destaque.

Neste contexto, técnicas de Inteligência Artificial (IA) desempenham um papel importante, uma vez que, se utilizadas com bom senso, bem planejadas e desenvolvidas, podem ampliar e tornar mais úteis e interessantes as funcionalidades de uma aplicação.

Para chegar a tal conclusão, basta comparar a utilidade de um software de controle de empréstimos bancários, por exemplo, que possui apenas funcionalidades para o registro e consulta de empréstimos realizados, com outro que utiliza técnicas de IApara determinar o risco da concessão de um empréstimo para um cliente em função do seu perfil e de dados históricos de inadimplência.

Exemplos de aplicações de técnicas de IA incluem a criação de interfaces adaptativas, alocação de profissionais em tarefas, detecção de intrusão e predição de falhas em redes de computadores, detecção de SPAM, inteligência em jogos, entre outros. Veja as referências, no final do artigo, com links para alguns exemplos disponíveis na Web.

Pode-se definir Inteligência Artificial como sendo uma área multidisciplinar, inspirada em processos naturais e relacionada à reprodução de capacidades normalmente associadas à inteligência humana, como a aprendizagem, adaptação, o raciocínio, entre outras.

Para reproduzir estas capacidades, diversas foram as abordagens adotadas no decorrer da história da IA, como a abordagem simbolista, também conhecida como simbólica ou cognitiva, baseada em aspectos cognitivos e algorítmicos – procurando reduzir a inteligência a um conjunto de símbolos, regras e passos –, a conexionista, baseada na simulação das estruturas consideradas responsáveis pela produção de comportamentos inteligentes, como os neurônios, e a evolutiva, inspirada na teoria da evolução das espécies.

Na Tabela 1estão listados, para as abordagens citadas, exemplos de subáreas e suas respectivas inspirações.

Tabela 1. Principais abordagens da IA, exemplos de subáreas e suas respectivas inspirações.

As Redes Neurais Artificiais (RNA) são modelos computacionais inspirados na estrutura e comportamento do cérebro humano e são geralmente utilizadas na reprodução do processo de aprendizagem, associação e generalização. São efetivas principalmente no aprendizado de padrões – reconhecimento de caracteres e voz, dados em imagens, entre outros.

Os Sistemas Especialistas (SE) são sistemas computacionais que procuram apresentar um comportamento semelhante ao de um especialista de um determinado domínio, possuindo a capacidade de armazenar conhecimentos e os utilizar na solução de problemas.

Por sua vez, os Algoritmos Genéticos (AG) são algoritmos de busca e otimização inspirados na teoria da evolução das espécies, e consideram a busca pela solução de um problema como um processo de competição entre soluções candidatas.

Devido ao seu potencial de uso em diferentes áreas, há um crescente número de aplicações de AGs, incluindo a geração de casos de teste de software, redução do acoplamento e o aumento da coesão em modelos de classes, a alocação de profissionais em tarefas, alocação de docentes e salas em instituições de ensino, definição de escalas de plantão médico, rotas de entrega, otimização de projetos de carros e aviões, inteligência em jogos, entre outras.

Neste artigo, serão apresentados os principais conceitos de Algoritmos Genéticos e uma biblioteca voltada para a implementação deste tipo de algoritmo em Java – JGAP. Para ilustrar a aplicação deste tipo de algoritmo e da biblioteca, será apresentado um exemplo de otimização de rotas de distribuição de produtos.

Algoritmos Genéticos

Inspiração Biológica

Os Algoritmos Genéticos fazem parte de uma classe de algoritmos, conhecidos como Algoritmos Evolutivos, inspirados na teoria da evolução das espécies, proposta simultaneamente por Charles Robert Darwin e Alfred Russel Wallace.

Esta teoria descreve os mecanismos regentes do processo de evolução das espécies e, para entendê-la, é apresentada, a seguir, uma breve descrição dos seus principais conceitos.

Em uma comunidade biológica qualquer, a limitação na disponibilidade de recursos necessários à sobrevivência – como alimento e abrigo – faz com que haja uma competição, direta ou indireta, entre os indivíduos da comunidade.

Os indivíduos que possuem diferenciais competitivos – que são mais fortes, rápidos, com maior tolerância ao frio ou ao calor, entre outros – têm maior chance de acesso a esses recursos – ou fazem melhor uso deles – e maior tolerância às agressões impostas pelo ambiente, o que, consequentemente, aumenta suas chances de sobrevivência. Estes diferenciais competitivos, bem como outras características desejáveis e indesejáveis, surgem da combinação genética decorrente do processo de reprodução e de mutação. A informação genética envolvida nesse processo de combinação é representada nos indivíduos através de uma sequência de genes, conhecida como cromossomo.

Aqueles indivíduos que sobrevivem podem transmitir a seus descendentes algumas das características genéticas que lhes conferem uma condição privilegiada, caso estas sejam hereditárias. Em longo prazo, a tendência é que as características genéticas dos indivíduos melhor adaptados ao ambiente estejam presentes em grande parte da população." [...] continue lendo...