CAPÍTULO 3: TIC Y EDUCACIÓN FÍSICA
3.2. Implementación de las TIC en educación física
O algoritmo genético inicia o processo de otimização a partir de um conjunto de configurações (população inicial). A População em AG refere-se a um conjunto de indivíduos ou um conjunto de soluções do problema (GODBARG e LUNA, 2000). Em relação à população existem dois aspectos que devem ser especificados. O tamanho da população “n” e a forma em que é determinada a população inicial. O
tamanho da população deve ser escolhida levando em conta o tamanho do problema e os outros parâmetros genéticos, como a taxa de crossover e a taxa de mutação (ROMERO e GALLEGO, 2000).
A forma de gerar uma população inicial pode ser feita de duas maneiras diferentes: de forma aleatória ou utilizando heurísticas (IGNACIO, 2000). Ao se utilizar uma heurística com população aleatória, pode-se aprender muito sobre as características do problema e sobretudo, da evolução deste tipo de população pode- se obter uma configuração satisfatória para o problema de otimização (IGNACIO, 2000). Para algumas aplicações, pode ser conveniente iniciar a população usando-se métodos mais diretos, como os algoritmos gulosos, ou pode-se iniciar com a perturbação de uma solução gerada aleatoriamente.
Durante o processo evolutivo, esta população é avaliada e a próxima geração será uma evolução da anterior, para que isto ocorra, os mais aptos deverão possuir maior probabilidade de serem selecionados para dar origem à nova geração, que deverá ser melhor que a que lhe deu origem. Uma geração mais apta ao ambiente significa uma melhoria no valor da função objetivo. Em cada “passo evolutivo”, conhecido como geração, decodifica-se um indivíduo e avalia-se sua capacidade “reprodutiva”. A partir de então, cria-se uma nova população, por processos de seleção e posterior “cruzamento” de cromossomos da população anterior (GARCIA et al., 2000).
3.2.3. Seleção
Após decidir sobre a codificação a ser adotada e a geração da população inicial ter sido efetuada para o algoritmo genético, a decisão seguinte refere-se a forma de executar a seleção, isto é, como escolher os indivíduos "pais" na população que gerará os novos descendentes ou "filhos" para próxima geração. Uma função de aptidão (fitness) é utilizada para quantificar a qualidade genética dos cromossomos- pais, e geralmente corresponde à função de custo em problemas de otimização combinatória (IGNACIO, et. al, 2000). De acordo com este autor, esta função de aptidão também é utilizada para decidir se um cromossomo gerado, através de um
cromossomos-pais para o cruzamento é incrementar a probabilidade de reproduzir elementos da população que tenha bons valores na função objetivo. Um indivíduo com um valor de aptidão alto possui uma maior probabilidade de contribuir com um ou mais filhos na próxima geração.
Uma seleção muito forte reduz a diversidade da população necessária para sua evolução, ocorrendo a chamada "convergência prematura" do algoritmo, por outro lado, seleção muito fraca resultará em evolução muito lenta da população, o que significa uma convergência lenta do algoritmo (MITCHELL, 1996). De acordo com GARCIA et al (2000), no processo de otimização quando se implementa o algoritmo genético, a seleção é a etapa mais crítica, pois é a que consome mais tempo com cálculos da função de aptidão e probabilidade de sobrevivência de cada indivíduo. Desta forma, quanto maior o número de indivíduos, maior tempo será gasto no processo de seleção, e consequentemente, a velocidade de convergência do algoritmo genético está relacionada diretamente como o tamanho da população. Ainda, segundo os mesmos autores, grande parte do custo computacional do algoritmo está concentrado na fase de seleção.
Diversos esquemas de seleção tem sido propostos na literatura de AG. A seguir são descritos alguns dos métodos mais comuns. Tais descrições não provêm diretrizes rigorosas para prevê a adequacidade e eficiência dos métodos para um determinado problema. Esta é ainda uma questão aberta para os AGs, sendo que a experiência e os ensaios são ainda as melhores formas para selecionar um dado método. Existem vários métodos de seleção disponíveis para os AGs. Alguns desses métodos são: a seleção proporcional, seleção por escalonamento, seleção de
Boltzmann, seleção por ranqueamento, seleção tournament e o elitismo, conforme
descritos por MITCHELL (1996).
Na seleção proporcional, cada indivíduo i possui uma expectativa de sobrevivência (Ei) associada ao seu valor de aptidão, geralmente dada por:
∑
= = n i i i i f f E 1 (1) em que:f i = função objetivo avaliada no indivíduo i; e
n = tamanho da população.
Ao se utilizar a seleção proporcional, deve-se evitar a existência de "super indivíduos" no início do processo, proporcionados por cromossoma que possuem probabilidades de sobrevivência muito maiores do que a média da população (MITCHELL, 1996 e GARCIA et al., 2000). A existência desses indivíduos é indesejável, uma vez eles podem dominar o processo de seleção e reprodução e nesse caso, a população inteira pode convergir para uma solução logo no início do processo. Essa situação recebe o nome de “Convergência Prematura” (MITCHELL, 1996 e GARCIA et al., 2000).
A seleção por escalonamento utiliza a função sigma scaling para calcular a expectativa de sobrevivência dos indivíduos, dada por:
0 ) ( , 0 ) ( 1 ) ( 2 ) ( ) ( 1 ≠ = − + = − t se t se t t f i f Eit σ σ σ (2) em que:
Eit = expectativa de sobrevivência do indivíduo i no tempo t;
f(i) = fitness do indivíduo i;
) (t f −
= fitness média da população no tempo t; e
σ(t) = desvio padrão da fitness da população no tempo t.
Segundo MITCHELL (1996), a vantagem desse método é evitar a convergência prematura mantendo a pressão de seleção constante durante toda a busca. No início da corrida, onde o desvio padrão da população é geralmente maior, o método penaliza os indivíduos que apresentam fitness muito acima da média, reduzindo dessa forma as diferenças de probabilidade de sobrevivência entre indivíduos mais e menos aptos, propiciando dessa forma maiores chances de reprodução para os indivíduos menos aptos, o que aumenta a diversidade da população. Igualmente, no fim da corrida, onde geralmente reduz-se o desvio padrão
da população, os indivíduos mais aptos terão maior chance de sobrevivência, o que permite a convergência do algoritmo.
A seleção por escalonamento mantém a pressão de seleção constante ao longo do corrida. Entretanto, segundo MITCHELL (1996), freqüentemente variação na pressão de seleção ao longo da corrida pode ser uma importante estratégia para melhorar a performance do AG. Por exemplo, no início da corrida poder-se-ia manter uma baixa pressão de seleção, permitindo a reprodução de indivíduos menos aptos, caracterizando uma fase de maior diversificação da população. No final da corrida, aumentaria a pressão de seleção, selecionando indivíduos mais aptos para reprodução, caracterizando um processo de intensificação da busca em regiões mais promissoras.
Uma forma de implementar esta estratégia é utilizar a "Seleção de
Boltzmann", segundo MITCHELL (1996), uma abordagem similar a simulated annealing, na qual a "temperatura" controla continuamente a pressão de seleção. A
temperatura inicia alta, o que resulta em uma baixa pressão de seleção (i.e., cada indivíduo tem uma probabilidade razoável de reproduzir). A temperatura é diminuída gradualmente, de acordo com um esquema prefixado, o que gradualmente aumenta a pressão de seleção, assim permitindo o AG intensificar a busca em regiões mais promissoras, propiciada pela maior probabilidade de sobrevivência de indivíduos mais aptos.
A seleção de Boltzmann pode ser implementada da seguinte forma (MITCHELL, 1996): t T i f it
E
e
E
/ ) (=
(3) em que: T = a temperatura;n
e
E
n i T i f t∑
==
1 / ) ( (4)Et = média da população no tempo t;
A seleção por ranqueamento ou ordenamento é um outro método de seleção alternativo, cujo propósito é também prevenir convergência rápida do AG (MITCHEL, 2000). Segundo este mesmo autor, na versão proposta por Baker em 1985, os indivíduos na população são ranqueados de acordo com o seu fitness, e a probabilidade de sobrevivência de cada indivíduo depende de seu rank ao invés de seu fitness absoluto. As vantagens deste método, segundo MITCHELL (1996) é que ele diminui a pressão de seleção permitindo que indivíduos mais aptos dominem o processo de reprodução, uma vez que os valores absolutos das fitness não são considerados, e sim a sua posição no rank. As desvantagens são que, com a baixa pressão de seleção, pode haver problemas de convergência do algoritmo e o maior custo computacional necessário para classificar (ranquear) os indivíduos em cada geração.
Segundo MITCHELL (1996), o método de ranqueamento linear proposto por Baker é o seguinte: cada indivíduo na população é ranqueado em ordem crescente de fitness, de 1 a n. O usuário escolhe um valor esperado Max do indivíduo com rank n, com Max ≥ 0. A expectativa de sobrevivência de cada indivíduo i na população para o tempo t é então dado por:
1
1
)
(
−
−
−
+
=
n
rank
Min
Max
Min
E
it it (4) em que:Min = valor esperado do indivíduo com rank igual a 1.
Segundo MITCHELL (1996), dado a restrição de que Max ≥ 0 e ∑i E(i,t) = n
(uma vez que o tamanho da população mantém constante de geração a geração), pode-se mostrar que: 1 ≤ Max ≤ 2 e Min = 2 – Max. Ainda de acordo com MITCHELL (1996), Baker recomenda Max = 1.1.
Na seleção tournament, também conhecida como seleção por jogos, dois indivíduos são escolhidos ao acaso na população. Escolhe-se um parâmetro k (por exemplo 0.75) e, em seguida, um número aleatório r é então escolhido entre 0 e 1. Se r < k, os dois indivíduos são selecionados para serem pais; caso contrário; eles são recolocados na população original e podem ser selecionados novamente. As vantagens deste método, além de sua simplicidade, é a economia no processamento
de operações como cálculo de funções fitness, cálculo de médias, desvio padrão, classificação de indivíduos etc, típicos dos outros métodos de seleção. Com isso, um menor esforço computacional é requerido. Entretanto, por requerer poucas informações do sistema pode aprender pouco sobre as suas características, resultando em baixa performance do algoritmo em termos da qualidade da solução obtida (MITCHELL, 1996).
A seleção por elitismo força o AG a reter alguns dos melhores indivíduos em cada geração (De Jong (1975), citado por MITCHELL, 1996). O objetivo desse método é evitar a perda de bons indivíduos quando submetidos a crossover ou mutação.