Algoritmo Genético Aplicado à Simulação

Jeosafá do N. Moreira – 1423331074 – Inteligência Computacional II - UEZO

Algoritmo Genético Aplicado à Simulação

Introdução

Modelos computacionais tem sido muito utilizado na área de simulação, para tomar decisões e resolver problemas. Modelos antigos de simulação já não satisfazem mais os resultados que se desejam obter atualmente.

Estabelecer objetivos; usar simulação quando existem abordagens mais simples para determinados problemas; ter resultados mal interpretados. Esses são os problemas mais encontrados no processo de simulação.

Para minimizar tais problemas, um software precisa conseguir analisar muito bem os dados (parte mais difícil no processo), e é na busca por alternativas de análises de dados, que iremos apresentar como solução o Algoritmo Genético (AG).

Simulação Apoiada por AG

AG é um dos novos paradigmas da Computação, onde é criada uma população de indivíduos que representam soluções de um problema. São então avaliados levando em conta uma função objetivo (F.O) que satisfaça o problema. Gera-se uma nova população que será submetida ao uso de operadores genéticos. Uma nova população é formada, que deve ser melhor que a anterior. O processo pode se repetir quantas vezes necessárias, onde a solução é o melhor da última geração criada.

Nem sempre o AG achará a melhor solução, isso dependerá do quão bom será a técnica utilizada, mas ele é bom para encontrar uma solução razoavelmente boa e rápida. A ideia é utilizar o AG onde outras técnicas não são suficientes.

SimAG – Ferramenta de simulação

Foi criada uma ferramenta para simulação com AG, onde a modelagem é representada por um grafo, onde os nós estão interconectados por arcos direcionais. Os valores inicias aplicados ao grafo, são um indivíduo. Os valores resultantes serão analisados pela F.O, e então será gerada a nova população.

A seleção usa a estratégia elitista, onde a integridade do melhor atual é garantida para a próxima geração.

Procura-se evitar o cruzamento de pais idênticos, pois os filhos serão exatamente iguais a eles, desperdiçando assim tempo de processamento. A solução aqui foi, antes da combinação, os pares são analisados e se forem iguais, serão passados diretos para a próxima geração. Essa análise é feita no início do processo evolutivo, chamada de cruzamento analítico, onde houve uma economia de tempo em torno de 30% comparada ao método tradicional.

A mutação aplicada é a exponencial, onde dobra quando metade do número de gerações já foi processada, quando três quartos, e por fim, sete oitavos foram processados.

É normal haver várias restrições impostas em modelos complexos. Quando essas restrições não são obedecidas, deve haver uma política de penalização do indivíduo. Deve-se ter uma atenção nessa política, pois quem tiver violado as restrições não pode contaminar toda a população, mas ainda assim devem ter seus filhos gerados, pois eles sim podem ser boas soluções para o problema.

O Processo de Simulação Apoiada por AG Proposto

Exemplos de

...