Funcionamento do algoritmo genético

O primeiro passo na implementação do algoritmo genético é gerar a população inicial.

No algoritmo genético aqui desenvolvido, cada membro desta população é um vetor de comprimento L denominado de cromossomo do indivíduo. O indivíduo formado é uma representação da matriz de transformação $T$.

Desse modo, os componentes do cromossomo do indivíduo são os elementos determinantes da matriz de escala $E$ e os ângulos que determinam a matriz $A$ (ver tabela 1).

Tabela 1: Elementos componentes do cromossomo de cada indiíduo da população gerada pelo algoritmo genético

Elementos da matriz $E$	Ângulos da matriz $A$
$e_{1}$,$e_{2}$,$e_{3}$	$x_{1}$,$y_{1}$,$x_{2}$,$y_{2}$,$x_{3}$,$y_{3}$

O algoritmo genético implementado gera a população inicial aleatoriamente (ver figura 4).

A partir de então os indivíduos que formam a população trocam as informações dos seus genes segundo o operador de recombinação (crossover), que possibilita formar novos indivíduos que podem possuir tanto as melhores como as piores características dos indivíduos iniciais. Os pontos de recombinação são estabelecidos aleatoriamente. A Figura 2 representa o código em MATLAB que implementa a função de crossover.

Figura 2: Operador de crossover implementado no MATLAB: pai 1 e pai 2 são os cromossomos que serão cruzados; prob cross representa a quantidade de pontos que sofreram recombinação; filho cross 1 é o resultado da recombinação dos cromossomos pais

Após serem gerados, os indivíduos passam através de um operador de mutação. Esse operador é responsável por alterar determinadas partes aleatórias do gene do indivíduo de forma a buscar uma melhoria do indivíduo gerado. O resultado desse operador pode ser positivo caso o indivíduo gerado seja melhor que os indivíduos geradores dele ou negativo caso o indivíduo mutado seja inferior aos indivíduos geradores. A Figura 3 representa o código em MATLAB que implementa a função de mutação.

Figura 3: Operador de mutação implementado no MATLAB: filho representa o cromossomo do indivíduo a sofre mutação; prob mutacao representa a porcentagem do indivíduo que sofrerá alteração; filho mutado representa o resultado da mutação sobre o cromossomo de entrada

Para definir quem são os indivíduos mais apropriados para resolver o problema deve-se definir uma função de avaliação (fitness) do algoritmo genético.

Após passar pela função de avaliação, os indivíduos são ordenados segundo os valores obtidos pela função de avaliação. O melhor indivíduo, isto é, aquele com menor valor de avaliação, é escolhido para integrar uma nova população. Os outros indivíduos que completarão a nova população são criados da mesma forma que os indivíduos iniciais.

Denomina-se de geração cada uma das interações feitas pelo algoritmo genético ao obter uma nova população.

Denominamos por execução cada uma das rodadas que o algoritmo realiza com uma população por um determinado número de gerações.

Desse modo são executadas tantas iterações quanto forem necessárias para que o algoritmo determine um resultado razoável.

Assim, tendo determinado um indivíduo que possua um valor de erro segundo a função de fitness que seja da ordem de $10^{-2}$, obtêm-se um cromossomo que gera um indivíduo próximo ao indivíduo representativo da matriz de transformação $T$ que leva as matrizes abstratas $R_{a}$ e $F_{a}$ calculadas às matrizes $\overline{R}$ e $\overline{F}$ respectivamente procuradas.

Figura 4: Visão geral de funcionamento do algoritmo genético