LOGISPLAN está desenvolvido segundo técnicas de optimização baseadas em algoritmos genéticos. A aplicação de algoritmos genéticos na optimização permite resolver problemas do tipo NP-Completo. Este tipo de problemas necessitaria de um tempo praticamente infinito para ser resolvido e, mediante as técnicas utilizadas por .Evolution Algorithms, pode resolver-se em poucos minutos.
Características
Um algoritmo é uma série de passos, organizados, que descreve o processo a seguir, para dar solução a um problema específico.
Os algoritmos genéticos possuem várias características que os tornam especialmente adequados para a resolução de problemas muito complexos.
- Os algoritmos genéticos são assim chamados porque se inspiram na evolução biológica e na sua base genético-molecular.
- Estes algoritmos fazem evoluir uma população de indivíduos submetendo-a a acções aleatórias, semelhantes às que actuam na evolução biológica (mutações e recombinações genéticas), como também a uma Selecção, de acordo com algum critério, em função do qual se decide quais os indivíduos mais adaptados, os que sobrevivem, e quais os menos aptos, os que não sobrevivem.
- Os algoritmos genéticos eliminam um dos maiores obstáculos que condiciona o desenho clássico da programação, que é a necessidade de especificar todas as características e peculiaridades de um problema, bem como as acções necessárias para as satisfazer.
- Através dos algoritmos genéticos é possível solucionar problemas que se revelam de impossível definição no que diz respeito à pura multiplicidade das suas potenciais variáveis.
- A aproximação à solução de problemas de alta complexidade é realizada com uma estrutura, também ela, de alta complexidade, de modo que podemos dizer, que sondamos a complexidade com a complexidade.
Equivale a utilizar uma rede/malha de sondas sobre uma paisagem de vales e montes (mínimos e máximos da função de avaliação), em lugar de realizar medições sequenciais com determinados critérios (que é aquilo que os algoritmos clássicos costumam fazer).
- Todo o processo evolutivo da natureza funciona com um elevado grau de paralelismo: todos os indivíduos contemporâneos de uma população são submetidos à função de avaliação do ambiente (meio-ambiente, predadores, etc.), e sobrevivem, reproduzem-se e morrem sem interferências quanto à simultaneidade de tais acontecimentos. Ao utilizar um mecanismo semelhante, os algoritmos genéticos, ainda que sejam programados de forma sequencial, obedecem, pela sua natureza, a um desenho conceptual que os permite operar num processo muito semelhante. Com o desenvolvimento futuro dos sistemas com grandes quantidades de processadores em paralelo, estes algoritmos são muito adequados à sua implementação nesses sistemas, com o consequente benefício em termos de rendimento.
- Muitos algoritmos são desenhados para que os coeficientes que intervêm no problema permaneçam fixos. Por exemplo, no problema associado à atribuição de postos de trabalho, que passa por fazer corresponder pessoas a postos de trabalho de acordo com os seus perfis, o algoritmo húngaro (método clássico utilizado para a sua solução) considera que os coeficientes se mantêm constantes. Isto significa que se os valores utilizados no cálculo e as condições do meio ambiente se alterarem durante o processo, o método deve ser suspenso e reiniciar-se. Os algoritmos genéticos reorientam-se automaticamente para o novo objectivo e continuam no seu processo de convergência até ao valor óptimo definido pelas novas condições. Podemos dizer que os algoritmos genéticos são capazes de convergir para soluções óptimas mesmo que os coeficientes variem. Por exemplo, o método húngaro não permite ter em conta, que o coeficiente de atribuição/qualificação de uma pessoa para um posto de trabalho, muda em função do posto de trabalho que é ocupado por outra pessoa, que é o que acontece quando se atribui um posto de trabalho a uma pessoa na mesma secção em que trabalha o seu cônjuge. O algoritmo genético adapta-se perfeitamente a este tipo de circunstâncias de um problema.
- Os algoritmos genéticos surgiram nos anos 70 pela mão de John Henry Holland e David Goldberg, desde então a sua aplicação na resolução de problemas de procura e optimização tem sido fortemente comprovada.
Funcionamento
Um algoritmo genético pode apresentar diversas variações dependendo de como se aplicam os operadores genéticos (cruzamento, mutação), de como se realiza a selecção e de como se decide a substituição dos indivíduos para formar a nova população.
Um esquema de funcionamento básico resume-se nos seguintes passos:
- Inicialização: Gera-se aleatoriamente a população inicial, que é constituída por um conjunto de cromossomas os quais representam as possíveis soluções do problema. É importante garantir que a população inicial possua a diversidade estrutural destas soluções de forma a ter uma representação da maior parte da população ou pelo menos de forma a evitar uma convergência prematura.
- Avaliação: A cada um dos cromossomas da população é aplicada a função de aptidão para saber "quão boa" é a solução que se está a calcular.
- Fim: O algoritmo genético deve ter em conta quando se alcança a solução óptima, no entanto a solução óptima é desconhecida, portanto devem ser utilizados outros critérios de detecção. Normalmente utilizam-se dois critérios: correr o algoritmo genético o número máximo de repetições ou pará-lo quando não existam alterações na população. No entanto quando não se cumprem as condições de fim faz-se o seguinte:
- Selecção: Depois de determinar qual a aptidão de cada cromossoma são identificados os cromossomas que são cruzados na próxima geração. Os cromossomas mais aptos têm maior probabilidade de ser seleccionados.
- Sobrecruzamento: O cruzamento é o principal operador genético, representa a reprodução sexual, actua sobre dois cromossomas de cada vez para gerar os descendentes a partir dos quais se combinam as características de ambos os cromossomas pais.
- Mutação: Modifica aleatoriamente parte dos cromossomas dos indivíduos e permite alcançar zonas do espaço associadas à procura que não estavam cobertas pelos indivíduos da população actual.
- Substituição: Uma vez aplicados os operadores genéticos, são seleccionados os melhores indivíduos para modelar a população da geração seguinte.
|
