Parte II - Sistemas de Aprendizado: Overview
Seminários 2007 – 2º Semestre
Maíra Gatti
Agenda
• Reinforcement Learning
– Exemplo SMA
• Algoritmos Genéticos
– Exemplo SMA
• Bibliografia
© LES/PUC-Rio
2
Aprendizado por Reforço (Reinforcement Learning)
• Sinal de reforço/ recompensa
– gerado pelo ambiente em resposta a transições de estado
produzidas pelas ações executadas pelo sistema aprendiz.
• O objetivo de um aprendiz AR consiste em aprender uma
política de escolha de ações, em cada estado, de forma a
maximizar o reforço cumulativo no tempo
Sinal de reforço
Meio externo
ações
Estado do meio
externo
© LES/PUC-Rio
Agente
inteligente
output
3
Q-Learning
• Usado quando o agente não conhece o modelo de transição
de estados do ambiente
• Ao invés de se considerar o valor do estado - V(o) -,
considera-se o valor de escolher uma ação em um estado –
Q(o,a)
• Definição Q
– Significa a recompensa de escolher a ação a (não
necessariamente a melhor) no estado o e depois continuar
escolhendo as ações ótimas
© LES/PUC-Rio
4
O Algoritmo para calcular o valor de Q
Política que o agente
utiliza para escolher a
ação:
- Começa explorando:
tenta uma ação de Q
mesmo que não tenha o
maior valor de Q
- Termina exploitando:
escolher a ação que tem
o maior valor de Q
© LES/PUC-Rio
5
Exemplo Simples
O Algoritmo para calcular o valor de Q
• O agente vai aprender através da experiência
• O agente vai explorar cada estado até atingir o estado
desejado
• Cada exploração é um episódio
• Em cada episódio o agente vai do estado inicial ao desejado
• Quando o agente atinge o estado desejado, o algoritmo
passa para o próximo episódio
• Dado: diagrama de estados com um estado desejado
– Representado pela matriz R
• Descubra: o menor caminho a partir de qualquer estado
inicial para o estado desejado
– Representado pela matriz Q
© LES/PUC-Rio
6
Exemplo Simples
O Algoritmo para calcular o valor de Q
Neste caso foi usado o modelo
do ambiente!
© LES/PUC-Rio
7
Exemplo com SMA:
Reinforcement Learning and Self-Organization
• Sherief Abdallah
– Multiagent Reinforcement Learning and Self-Organization in a
Network of Agents
• Alocação de tarefa usando uma rede de agentes
© LES/PUC-Rio
8
Exemplo:
Reinforcement Learning and Self-Organization
• Algoritmo de Aprendizado
• Estrutura de dados para cada agente i
– Qi -> valores de ação
• Qi = |Si| linhas ×|Ai| colunas (S é o conjunto de estados que o
agente se encontra)
 i -> valores de política
–
• célula Qi(s, a) contem o prémio que o agente i espera se executada
a ação a no estado s.
• célula  i(s, a) contem a probabilidade que o agente i tem de
executar a ação a no estado s
• Juntos, Q e
momento
 encapsulam o que o agente aprendeu até o
• Objetivo: calcular um gradiente aproximado de Q, usá-lo
para atualizar , em um passo curto η.

© LES/PUC-Rio
9
Exemplo:
Reinforcement Learning and Self-Organization
• Operações de reestruturação da rede
– Adicionar nós
– Remover nós
• Mecanismos de Auto-organização
– Qual vizinho adicionar ou remover?
– Quando parar de adicionar ou remover?
– Como ajustar Q e

após o processo de adição ou remoção?
• Mecanismo de Auto-organização usa informação de
aprendizado para guiar o seu processo
© LES/PUC-Rio
10
Exemplo:
Reinforcement Learning and Self-Organization
© LES/PUC-Rio
11
Algoritmos Genéticos
• Utilizam um procedimento de busca inspirado na evolução
natural
• Rotinas análogas, de uma certa forma,
– ao cruzamento de indivíduos,
– cruzamento de cromossomos,
– mutação de genes, e
– seleção natural.
• Assim como na evolução natural, os algoritmos genéticos
sacrificam parte da sua população em ótimos locais para
que outros indivíduos consigam atingir o ótimo global.
© LES/PUC-Rio
12
Algoritmos Genéticos
BEGIN /* genetic algorithm */
generate initial population
mérito da solução
compute fitness of each individual
WHILE NOT finished DO
BEGIN /* produce new generation */
FOR populationsize / 2 DO
BEGIN /* reproductive cycle */
select two individuals from old generation for mating
/* biassed in favour of the fitter ones */
recombine the two individuals to give two offspring
compute fitness of the two offspring
insert offspring in new generation
END
descendente
IF population has converged THEN
finished <- TRUE
END
END
© LES/PUC-Rio
13
Algoritmos Genéticos
• Várias aplicações em Aprendizado
– Sistemas de classificação
• AG tentam evoluir (aprender) um conjunto de regras if..then
• Ex.: jogos
– Controle
• Parâmetros de controle precisam ser ajustados para que o sistema
rode em um modo ótimo
© LES/PUC-Rio
14
Exemplo SMA com AG
• Iterative Multi-Agent Bidding and Co-ordination
Based On Genetic Algorithm
– M K LIM and Z ZHANG
• Sistema de manufatura
• SMA para
– integrar planejamento e agendamento de processo dinâmico
para aumentar tempo de resposta
– Otimizar utilização de máquina
– Prover uma plataforma para reconfigurar o sistema
– Minimizar custo na presença de mudanças dinâmicas
© LES/PUC-Rio
15
Exemplo SMA com AG
• Agentes
– Order handling agent: interpreta e processa as ordens de serviço
– Component agent: recomenda processos adequados para a construção
de componentes
– Tool agent: recomenda ferramentas a serem usadas na produção do
componente. Cada ferramenta tem seu preço.
– Material handling agent
– Machine agents: negociam entre si para ofertar trabalho
– Mecanismo de oferta iterativo facilita atribuição de trabalho para os
agentes (realizado entre o component agent e os machine agents)
• Arquitetura
– 3 seções:
• Atividades relacionadas a demanda
• Atividades relacionadas ao componente
• Atividades relacionadas a fábrica
© LES/PUC-Rio
16
Exemplo SMA com AG
• O component agent inclui um esquema de moeda para cada
processo de construção de componente
– O esquema contem todos os valores virtuais para cada feature
do componente
• Machine agents lançam ofertas para o trabalho de acordo
com o custo total
•
o valor atribuído para cada componente é ajustado de
acordo com a performance das ofertas, em termos de custo
e tempo de produção
– Objetivo de minimizar o custo de produção ao mesmo tempo
que cumpre deadlines.
=> AG
© LES/PUC-Rio
17
Exemplo SMA com AG
• Solução dada
– Passo1: Codificação
• Uma população de cromossomos, e número de gens são
determinados
• Os gens em cada cromossomo representam o valor corrente
para todas as features de um componente
– Passo2: Função de fitness
• Component agent anuncia todos os cromossomos para os
Machine agents.
• Baseados nos valores e em suas performances, machine
agents ofertam trabalho
© LES/PUC-Rio
18
Exemplo SMA com AG
• Funções de fitness
• ti : tempo para produzir feature i
• K: número de features de um componente
• Ci: custo total da produção da feature i
• O cromossomo com o menor custo e que esteja no prazo é
registrado como a melhor solução
© LES/PUC-Rio
19
Exemplo SMA com AG
– Passo3: Seleção dos cromossomos
• Todos são selecionados
– Passo4: Crossover
• Decide quem vai cruzar a partir de um threshold de probabilidade
• Cruzamento entre os cromossomos são realizados até que
descendentes sejam diferentes dos pais e atendam as funções de
fitness
– Passo5:Mutação
• Decide qual cromossomo vai mutar a partir de um threshold de
probabilidade
• Mutação no custo de uma feature
– Passo6: Reavaliação pelas funções de fitness
• Os cromossomos descendentes são reavaliados pelas funções de
fitness, isto é, cada machine agent recebe o anúncio dos
cromossomos
• Se os descendentes obtiverem melhor solução que os pais, os pais
são substituídos
• Passos 3 ao 6 são repetidos até que a condição seja satisfeita.
© LES/PUC-Rio
20
Frameworks
• Reinforcement Learning
– JReLM – Java Reinforcement Learning Module
• RL no Repast
• Release com o Repast
• http://www.cs.iastate.edu/~charlesg/
© LES/PUC-Rio
21
Bibliografia
• Reinforcement Learning:
http://www.inf.furb.br/~jomi/robotica/slides/rl.pdf
• Q-Learning:
http://people.revoledu.com/kardi/tutorial/ReinforcementLearning/QLearning-Algorithm.htm
© LES/PUC-Rio
22
Parte II - Sistemas de Aprendizado: Overview
Seminários 2007 – 2º Semestre
Maíra Gatti