Neuroevolução: uma aplicação em Aprendizado por Reforço.
Introdução
Neste projeto vamos tratar de Aprendizado por Reforço e Neuroevolução para solucionar um problema clássico em teoria do controle, o carrinho com pêndulo invertido (Cart Pole).
Para gerar o programa, vamos utilizar a plataforma GymOpenAI, um toolkit para desenvolvimento e comparação de algoritmos em Aprendizado por Reforço. Lá encontramos diversos environments legais como jogos de Atari, problemas em robótico e outros problemas em teorio do controle. Mais informações podem ser encontradas no site da plataforma.
O carrinho com pêndulo invertido é o environment básico gerado pelo Gym, e será utilizado neste projeto como um baseline para nosso Algoritmo Genético.
Aprendizado por Reforço
Em aprendizado por reforço, temos um agente que interage com o ambiente através de sensores e cria um conjunto de estados e ações no qual o objetivo é maximizar uma recompensa. No nosso exemplo, temos como agente o carrinho, que recebe informações do ambiente como velocidade e posição ângular do pêndulo, velocidade e posição dele próprio. E a partir destas informações ele define um estado e toma uma ação, no caso ir para esquerda (0) ou direita (1). A sua recompensa então será avaliada se o pêndulo permance em equilíbrio, sendo positivo se assim for, ou zero caso ele saia de uma posição que não estabelece mais este critério, no caso ±21.7º.
*Imagem retirada do site Wikipedia.
Problema
O jogo se diz terminado quando obtemos um score de 200 para a versão Cart-Pole-v0, ou 500 para a versão v1. Para este projeto foi utilizado como baseline a versão v1, onde o limite de tempo ou frames para o pêndulo permanacer equilibrado pode chegar a 500. Nosso objetivo será criar um algoritmo capaz de desenvolver uma técnica para equilibrá-lo o maior tempo possível, e se ultrapassar 500, ganhar o jogo.
Algoritmos Genéticos e Redes Neurais
Para atuar no problema então, serão utilizados dois algoritmos muito bem conhecidos na área de Inteligência Artificial, que juntos vem sendo denominados de Neuroevolução.
Neuroevolução trata-se da evolução dos pesos de uma rede neural através de algoritmos genéticos. Assim, nosso objetivo será gerar uma rede neural que será capaz de performar a tarefa de forma adequada.
Topologia da Rede
Para este projeto, vamos utilizar redes de topologia fixa, isto é, a sua estrutura não mudará, somente os seus pesos. A rede utilizada tem o seguinte formato:
Implementação
Algoritmos genéticos são algoritmos que tem como fonte de inspiração as teorias da evolução de Darwin e teorias genéticas de Mendel. É um algoritmo que gera uma população de indivíduos iniciais e gera uma competição entre eles, baseado em uma função denominada fitness. Assim, a parte desta definição, os melhores indivíduos da população permanecem e os outros são excluídos, para preenchimento do restante da população é realizado crossover, ou cruzamente entre os melhores indivíduos (pais), assim saímos de uma geração para outra.
Algoritmos Genéticos tem portanto um caráter probabilístico, onde é realizado uma busca que maximiza uma função. No nosso caso, nossa função a ser maximizada será a recompensa ou o tempo em equilíbrio que o pêndulo permanecerá no carrinho.
Seguindo esta linha estrutural, temos as seguintes caracteríscas implementadas neste projeto:
1. População
Tudo começa com a população inicial, ela foi implementada da seguinte maneira:
```
def population(size):
pop = []
for i in range(size):
model = rede_neural()
fit = fitness(model)
pop.append((fit,model))
return pop
```
Aqui temos como entrada o número da população inicial, onde rede_neural() trata-se de uma função que gera uma rede com topologia definida anteriormente e pesos aleatórios. Assim, temos como retorna uma lista, com tuplas no seguinte formato (fitness, rede_neural)
2. Fitness
Para o fitness, calculamos a performance da rede ao longo de 10 iterações e retiramos um valor médio, pois a rede apresentava valores variáveis, assim uma performance média trazia resultados mais adequados e confiáveis.
3. Crossover
Para crossover, utilizamos crossover de um ponto, sendo que este ponto representa um neurônio da rede neural, assim, se escolhido, trocamos os pesos do pai com o da mãe para este ponto e assim geramos os filhos. Para cada filho, é medido seu fitness, e aquele com maior fitness sobrevive e começa a fazer parte da população.
4. Mutação
No caso da mutação, definimos como uma adição para um peso um valor aleatório distribuído uniformemente entre (-0.5, 0.5). Assim, para cada nova geração, calcula-se a probabilidade de um ponto sofrer mutação, e caso ocorra, um peso dentre os 34 seria mudado.
```
def mutate(weights):
mutate_layer = random.sample([0,1,2,3], 1)[0]
mutate_point = random.sample([0,1,2,3], 1)[0]
change = random.uniform(-0.50,0.50)
try:
weights[mutate_layer][mutate_point] += change
except:
weights[mutate_layer] += change
return weights
```
5. Seleção e Evolução
Por fim, temos o processo de seleção, onde a evolução ocorrerá, saindo de uma população inicial com um fitness baixo para uma população final com fitness do objetivo do projeto.
Nesta parte, nossa opção foi de manter 40% na população, o que pode ser alterado no parâmetro ‘retain_length’ da função ‘evolve’, como visto abaixo:
```
def evolve(population, retain_lenght=0.4, mutate_rate=0.3, max_pop=10):
new_weights = []
graded = population
# Aplica o sort baseado nos scores
graded = sorted(population, key=lambda x: x[0], reverse=True)
retained = int(len(graded)*retain_lenght)
parents = graded[:retained]
...
```
Análise
Os resultados gerados são satisfatórios e mostram que Algoritmos Genéticos são apropriados para tarefas de Aprendizado por Reforço. Algumas dificuldades giraram entorno de estabelecer a taxa de crossover e mutação adequadas. Outra dificuldade pode ser descrita pela tendência de AG a permancerem em máximos locais, podendo existir uma lentidão na conversão de uma rede satisfatória.
Baseline
Como baseline, geramos mil indivíduos de forma aleatória e obtemos somente um capaz de performar de forma adequada. O que torna-se pouco, pois existem várias estratégias diferentes que um agente pode tomar, então obter um conjunto de soluções ótimas se torna uma tarefa mais recompensadora. Outra fator neste caso é o alto custo computacional e o fato de uma busca direta não ser possível em outras tarefas mais complexas, como por exemplo, o jogo Super Mario World.
Tabela com estatísticas:
| Núm de Individuos | 1000 |
| Fitness Máximo | 499 |
| Fitness Mínimo | 8.9 |
| Fitness Médio | 22.3 |
| Desvio Padrão | 43.4 |
Algoritmos Genéticos - Performance
Para testar nosso algoritmo, iniciamos uma população com somente dez indivíduos, o resultado foi o seguinte:
|
Indivíduo |
Fitness |
|
1 |
9.8 |
|
2 |
13.7 |
|
3 |
10.1 |
|
4 |
9.7 |
|
5 |
170.9 |
|
6 |
9.3 |
|
7 |
9.3 |
|
8 |
12.5 |
|
9 |
9.4 |
|
10 |
9.5 |
Vemos então que, nenhum deles apresenta um performance satisfatória, além de que, somente um consegue um resultado mediano, todos os outros estão muito abaixo do ideal.
Usando o algoritmo genético em questão, evoluímos esta população inicial por 50 gerações, e o resultado obtido foi o seguinte:
Aqui vemos como foi a evolução do fitness máximo obtido por geração, percebemos uma evolução do tipo escada, o que pode signifcar que em certos momentos a população fica presa em um ótimo local. Portanto, são necessárias algumas iterações para que a combinação entre crossover, mutação e seleção gere um indivíduo com fitness melhor e impulsione o fitness para um ótimo global.
Em outro teste, foi realizado 3 iterações com a mesma população para ver a taxa de convergência e como o algoritmo evoluia. Assim, novamente uma população inicial foi gerada de forma aleatória, com os seguintes indivíduos:
|
Indivíduo |
Fitness |
|
1 |
9.8 |
|
2 |
36.4 |
|
3 |
9.3 |
|
4 |
21 |
|
5 |
79.0 |
|
6 |
9.3 |
|
7 |
9.3 |
|
8 |
12.5 |
|
9 |
9.4 |
|
10 |
9.5 |
br />
Obtemos também, o gráfico por evolução:
Fica claro que o processo de convergência ocorre, mesmo para o número de gerações reduzido e teoricamente com uma população inicial mais ‘fraca’, vemos que em alguns casos a convergência só ocorre no final (Iteração 2), e em outros o valor ótimo obtido não seria o ideal, mas bem próximo deste (Iteração 1).
Conclusão
Como vemos, o modelo produzido por neuroevolução é mais eficiente computacionalmente do que o realizado por busca direta. E além do mais necessita muito menos interações com o espaço de busca. A eficiente deste se torna óbvia não somente para este caso específico, mas para aqueles onde o espaço em que o agente interage é complexo e extremamente variável.
Durante o desenvolvimento da implantação, alguns pontos foram necessários para que o modelo conseguisse atingir ótimo globais (definidos no escopo do projeto). Inicialmente, o desenvolvimento de crossover de um ponto juntamente com uma taxa de mutação baixa (em torno de 0.15) não traziam grandes benefícios aos indivíduos. Por muitas vezes estes ficavam presos em ótimos locais, e sem variabilidade não conseguiam evoluir. Porém, com a implementação de mais pontos de crossover e uma taxa de mutação por neurônio em volta de 0.50 proporcionou uma convergência rápida e com menos gerações obtivemos resultados ainda melhores do que antes.
Este exemplo ilustra como os Algoritmos Genéticos dependem dos seus parâmetros de definição.
Outro fator que contribui para um melhor retorno foram mudanças na topologia da rede neural. A função de ativação das camadas intermediárias foi definida inicialmente como funções sigmoid, <que gera uma probabilidade de ativação do neurônio. Porém por se tratar de uma função mais complexa, ela não se adaptou bem à uma rede neural somente com 4 neurônios por camada intermediária. Assim, a mudança para a função ReLu< (Rectifier Linear Unit) proporcionou uma considerável melhora nos resultados. Alguns dos motivos giram em torno da função ReLu zerar somente para valores negativos, e por se tratar de uma função linear, torna a rede neural mais leve e mais adaptativa para casos mais simples, onde a decisão gira em torno de dois comandos somente, 0 ou 1.
Outra técnica que gera bons resultados, porém não foi implementada neste projeto e são encontradas na literatura são as NeAT (Neuroevolution of augmenting topologies). Para estes modelos, não somente os pesos das redes são modificados no processo de evolução, bem como sua topologia como número de camadas intermediárias, número de neurônios por camada, função de ativação, etc. Estes demonstraram ser mais eficientes em casos onde o espaço de busca ou espaço de percepção do agente é significativamente maior, requerindo modelos mais complexos e processos de adaptação mais robustos.
Portanto, concluimos com o fato de que neuroevolução serve bem aos casos onde não temos dados de entrada para treinar um modelo, como em aprendizado supervisionado, e supera em performance e qualidade a busca por exaustão. Contudo, conseguimos perceber alguns problemas clássicos gerados por AG, isto é, a não certeza da sua convergência para mínimos absolutos, bem como uma tendência a gerar e ficar preso a mínimos locais, sendo extremamente variável o desempenho geral do algoritmo às taxas de mutação, crossover e seleção.
Referências