Solução através de Algoritmo Genético

A determinação da matriz $T$ não pode ser feita por métodos padrões pois as matrizes $\overline{R}$ e $\overline{F}$ reais não são conhecidas, tornando-se necessária a utilização de algum algoritmo de aproximação. Alguns métodos já foram sugeridos para a resolução do problema, como a utilização de redes neurais[5].

Buscando um novo método, optou-se por usar um algoritmo de busca por aproximação denominado Algoritmo Genético.

Os algoritmos genéticos são uma família de modelos computacionais inspirados na Teoria da Evolução estudada por Charles Darwin. Estes algoritmos modelam uma solução para um problema específico em uma estrutura de dados como a de um cromossomo e aplicam operadores que re-combinam estas estruturas preservando informações críticas.

O algoritmo genético propriamente dito foi inicialmente introduzido e estudado por John Holland (1975) e seus estudantes [7].

Um algoritmo genético é baseado em uma população, sendo tratada aqui como sendo um conjunto de vetores com diversas possibilidades da matriz de transformação $T$, e que utiliza operadores de seleção, re-combinação (crossover) e mutação para gerar novos indivíduos a partir da população inicial criada, surgindo assim novas variações da matriz $T$ que, juntamente com os elementos da população inicial, são capazes de solucionar o problema.

A partir de uma função de avaliação, o algoritmo genético decide qual a melhor solução dentre as soluções criadas, isto é, qual o indivíduo gerado melhor soluciona o problema.

Os algoritmos genéticos geralmente tratam de problemas não lineares. Isto significa que não é possível tratar cada parâmetro como uma varíavel independente que pode ser resolvida isolada das outras variáveis, como é o caso da matriz $T$. Existem algumas restrições que devem ser consideradas para maximizar ou minimizar a saída do problema . Essas restrições são geralmente referidas como Epistases (epistasis).

As primeiras restrições consideradas se referem aos parâmetros de entrada do algoritmo. Nesse caso, pode-se considerar como parâmetros os valores de restrição dos operadores, número de iterações que o problema executa e, principalmente, os valores limites de cada uma das partes dos indivíduos que formarão nossa população. Cada vetor representando um indivíduo destes é geralmente referenciado como genótipo ou cromossomo.

Subsections

• Funcionamento do algoritmo genético
• Função de Avaliação - Fitness