ALGORITMO GENÉTICO PARA IDENTIFICAÇÃO DO MÍNIMO

DA FUNÇÃO PEAKS DO MATLAB

Antônio Ítalo Rodrigues Pedrosa. E-mail: antonio.italo@hotmail.com

Pós-Graduação em Engenharia Mecânica pelo Instituto Militar de Engenharia

1. INTRODUÇÃO

John Holland propôs em 1975 um modelo de algoritmo baseado nos conceitos de

seleção natural da espécie e na teoria da evolução, chamando de Algoritmo Genético.

Esse é um método de otimização estocástica livre de derivação funcional.

Essa proposta pode ser aplicada em sistemas de optimização contínua ou discreta,

sendo amplamente implantado em máquinas de processamento paralelo aumentando a

velocidade de processamento desses equipamentos.

Para isso, o modelo codifica cada ponto a ser analisado em uma representação

binária que será chamada de cromossomo. Cada um desses pontos deve ter associado

um valor de função objetivo, denominado de grau de aptidão em problemas de

maximização, ou seja, procura-se o menor valor para a função objetivo em problemas

de minimização, por outro lado, a aptidão de cada um dos pontos deve ser maximizada.

O conjunto de pontos então produz um novo conjunto de acordo com a aptidão de

cada um, produzindo uma nova geração. Aqueles que possuírem maior aptidão estão

mais aptos a cruzar seus valores para produzir uma geração de pontos que possam

produzir pontos com aptidão ainda maiores. Esse cruzamento se dá através do

crossover.

O crossover é a etapa em que se dá a troca de informações dos cromossomos,

alterando a cadeia binária associada anteriormente. Na geração, parte do material de um

cromossomo é trocada parte do material de mesmo tamanho de outro cromossomo.

A nova geração tem maior probabilidade de se adequar ao que é analisado pelo

problema, mas nem sempre isso acontece. Pode ser que os ‘filhos’ gerados pelo

crossover tenham aptidão menor que a dos ‘pais’. Então, utiliza-se o processo de

seleção natural proposto por Darwin, em que os mais adaptados sobrevivem. Esse

processo é chamado e elitismo, fazendo com que os pontos que possuem maior aptidão

permaneçam para as próximas gerações, fazendo com que sempre se caminhe para uma

solução viável. Consequentemente, esse valor pode estar associado a um estado de

mínimo local, que não representa a solução correta do problema, e a solução encontrada

para fugir desse dilema também é baseada no modelo proposto por Darwin, onde se

considera a possibilidade de mutação do gene em algum cromossomo.

A mutação ocorre de forma aleatória e não necessariamente em todos os

indivíduos, mas quando ocorre, pode resultar em uma variação considerável de alocação

dos pontos, o que pode aproximar o ponto de um mínimo global, ou afastá-lo ainda

mais.

Quanto maior o número de gerações, maior a probabilidade de se encontrar um

indivíduo com características ótimas, ou pelo menos mais adaptadas à situação, que é o

proposto pelo método.

2. PROBLEMA PROPOSTO

O comando ‘peaks’ do MATLAB representa uma função de duas entradas

definidas como:

( ) ( ) (

)

( )

(1)

A solução pode ser obtida unicamente digitando peaks no prompt de comando do

MATLAB, em que será apresentada uma superfície, como mostrada pela Fig. 1, para 49

valores igualmente espaçados de x e y variando de -3 a 3, ou seja, com um intervalo de

0.125 entre cada ponto. Para se encontrar o valor de z em qualquer ponto desejado,

deve-se usar a expressão z = peaks(x,y) para a coordenada desejada

Com isso, para se encontrar o valor do mínimo dessa função, deve-se encontrar a

coordenada (x,y) que retorne o menor valor de z. Obviamente, o espaço de busca

selecionado foi entre os pontos -3 e 3, com precisão na terceira casa decimal.

A codificação de um ponto na linguagem binária requer que o valor de entrada

seja inteiro e positivo. Logo, o intervalo deverá ser transladado para que todos os seus

valores se tornem positivos, ou seja, o novo intervalo deverá ser de 0 a 6. E para que a

precisão aconteça na terceira casa decimal, também se faz necessário que esse valor seja

multiplicado por 10³. Assim, a relação entre o indivíduo a ser utilizado para o algoritmo

e o dado de entrada na função peaks, segue na forma:

( ) ( ( ) ) (2)

Resultando no intervalo de 0 a 6000, o que requer um número de pelo menos 13

bits, ou seja, 2n deve ser maior que 6000.

Figura 1 – Função peaks do MATLAB

O cromossomo associado para cada ponto deve conter todas as suas

características, ou seja, as coordenadas x e y, logo, esse cromossomo será representado

por um número binário de 26 bits. O cruzamento entre os cromossomos irá acontecer de

acordo com uma probabilidade pré-definida, ocorrendo no crossover entre os

cromossomos escolhidos.

Será escolhido um número aleatório para que haja a troca da informação entre os

cromossomos a partir desse gene, como exemplificado na Fig. 2. A partir do ponto de

crossover, o material de um cromossomo é passado ao outro, resultando em dois

cromossomos filhos com material genético combinado.

-3-2

-10

12

3

-2

0

2

-5

0

5

x

Peaks

y

Figura 2 – Crossover entre cromossomos de 8 bits (Jang, 1997)

É definida também uma probabilidade de mutação que, se for atendida para o

crossover analisado, irá trocar um bit de um dos cromossomos filhos de 1 para 0, ou

vice-versa.

Quando a população de cromossomos filhos for igual à população de

cromossomos pais, então se tem uma nova geração de indivíduos. A aptidão desses

indivíduos é analisada para saber qual deles será o sobrevivente para a próxima geração

devido ao elitismo atribuído.

Para a análise da aptidão, retoma-se o valor decimal do cromossomo até a

conversão para o valor do dado(x,y) que será utilizado no comando peaks. Por se tratar

de um problema de máximo, a aptidão atribuída é calculada na forma:

( ) (3)

Em que S torna-se sempre positivo devido ao expoente quadrático.

O valor da aptidão irá aumentar até atingir um valor máximo, ou seja, para um

número maior de iterações, a diferença entre a nova variação e a anterior, será

minimizada até um erro admissível estimado para o problema.

3. ALGORITMO

Todas as linhas de programação abaixo foram feitas utilizando o software

MATLAB na versão 7.1.

Inicialmente, foram atribuídos valores necessários para inicialização do algoritmo

e para os parâmetros determinados pelo usuário. Assim, a precisão dos dados utilizados

é de 10³ e a máxima variação admissível é da ordem de 10-3

. Foi escolhida uma

população de 33 elementos, quantidade suficientemente grande para que os dados

aleatórios estejam bem distribuídos, e um número binário de 13 bits, como explicado

anteriormente. A taxa de mutação foi fixada em 10% da população (um número

considerado alto, mas que ajuda a fugir de mínimos locais) e com 80% de chance de que

ocorra crossover entre os cromossomos. Foi definido que a variação seria inicialmente

apenas como forma de dar procedimento ao método, e um contador de gerações foi

adicionado para que o algoritmo se repetisse até que um valor máximo de 1000 gerações

fosse atingido.

Com isso, é necessário conhecer o valor do mínimo que se deseja encontrar, o que

pode ser feito utilizando o comando min(min(Z)) para a matriz originada com o

comando peaks. Uma população de indivíduos será gerada com as coordenadas

aleatórias de números naturais variando entre 0 e 6000 como explicado anteriormente e

os dados obtidos utilizando a Eq. 1.

O processo iterativo então é iniciado até que se atinjam as condições necessárias

estipuladas acima. O cromossomo é obtido usado o comando ‘dec2bin’ em que os

parâmetros de entrada são as coordenadas do individuo e a quantidade de bits admitida

(é importante inserir a quantidade de bits utilizada para que todos os cromossomos

tenham o mesmo tamanho, por exemplo: o valor 2 pode ser representado como 10 em 2

bits ou 0000000000010 em 13 bits). A aptidão também é calculada, relativamente aos

dados de entradas inicialmente estimados aleatoriamente.

De todas as aptidões encontradas, o indivíduo que irá sobreviver ao processo de

seleção será o de maior aptidão, e fará parte da nova geração de indivíduos gerados.

O crossover irá acontecer entre dois indivíduos escolhidos por sorteio em que a

probabilidade de serem escolhidos será maior tão quanto maior a sua aptidão associada.

Para isso, faz-se um sorteio baseado no valor da soma de todas as aptidões e o

cromossomo escolhido é aquele que se encontra na posição. Por exemplo, seguindo o

modelo apresentado na Fig. 3, é mais provável que um número escolhido entre 0 e 100

faça parte do grupo em azul do que os demais.

Figura 3 – Esquema representativo do sorteio probabilístico

O processo de cruzamento de informações será realizado até que se atinja uma

quantidade de indivíduos igual à população da geração anterior. Para isso, foi criado o

algoritmo mostrado abaixo.

O mesmo procedimento será realizado para o segundo cromossomo do par em que

poderá ocorrer o crossover.

Depois de selecionados os indivíduos, é necessário saber se ocorrerá ou não o

crossover, baseado na taxa admitida anteriormente, escolhe-se um valor aleatório que

deverá atender ou não à margem considerada. Em caso positivo, deve-se escolher então

o ponto em que ocorrerá a troca de material com um novo número natural escolhido

aleatoriamente. Definido esse ponto, tem-se dois filhos com material genético igual ao

cruzamento dos pais. Uma variável foi criada para definir se ocorreu ou não o crossover,

definindo com 1 para ocorrência e 0 para o contrário.

Para evitar que os filhos tenham o mesmo material genético do pai, faz-se com

que o crossover não aconteça no caso de que os cromossomos escolhidos sejam os

mesmos.

A mutação ocorrerá apenas se o crossover acontecer e dentro da margem de

mutação estipulada, ou seja, um novo número aleatório é obtido e se a mutação ocorrer,

o bit que for igual a 1 irá se converter para 0 e vice-versa. Porém, a mutação só deve

acontecer em um dos filhos, então esse indivíduo também é sorteado.

O código do filho originado possui 26 bits, sendo que 13 deles corresponde à

coordenada x e os outros 13 correspondem à coordenada y. Com isso, deve-se dividir

esse código para que sejam convertidos em valores decimais e acrescentados à matriz de

indivíduos nas suas correspondentes posições.

Quando a quantidade de indivíduos for atingida, então tem-se uma nova geração,

consequentemente, novos dados e aptidões associadas. A variação é atualizada e

avaliada.

O ponto que possui maior aptidão é sempre selecionado pelo elitismo e

armazenado na primeira linha da matriz de indivíduos, ou seja, esse é o ponto mais

próximo do mínimo da função peaks, que representa a resposta encontrada.

Como se trata de um processo estocástico com entradas aleatórias, os resultados

podem ser dar em muitas ou poucas iterações cada vez que o processo for reinicializado,

mas o progresso pode ser acompanhado para os dados encontrados como mostrado

abaixo. Nesse caso, foi encontrado o ponto (x,y) = (0.228, -1.626) que origina um

mínimo z = - 6.551.

(a) (b)

(c) (d)

Figura 4 – Possíveis mínimos da função da geração 1, 250, 500 e 750

Nota-se pela Fig. 4 que os indivíduos tendem a se aproximar do mínimo a cada

geração. Em algumas gerações, é possível que alguns indivíduos se afastem

espontaneamente como na Fig. 4c, isso ocorre principalmente devido à mutação que

pode acontecer em alguns indivíduos para fugir de mínimos locais, mas que acabam se

adaptando ao mínimo global com o passar das gerações, como mostrado na Fig. 4d.

O mesmo procedimento foi utilizado para dados com menor quantidade de casas

decimais e quantidade de bits, mas a resposta pode tender a mínimos locais pela falta de

precisão. Também é importante que a população tenha tamanho suficiente para abranger

uma boa área pelo mesmo motivo.

4. CONCLUSÃO

O algoritmo se mostra bastante eficaz em relação ao resultado obtido, mas a

quantidade de iterações necessárias pode deixar o processo lento dependendo dos dados

iniciais, atingindo a quantidade máxima de iterações estipulada em algumas vezes.

-3 -2 -1 0 1 2 3-3

-2

-1

0

1

2

3

-3 -2 -1 0 1 2 3-3

-2

-1

0

1

2

3

-3 -2 -1 0 1 2 3-3

-2

-1

0

1

2

3

-3 -2 -1 0 1 2 3-3

-2

-1

0

1

2

3