아래와 같은 지도에서 최적의 경로를 찾는 Q-Learning을 구현해보았다.
┌────────────┬───
│ A B C │ D
└───┐ │
E │ F │ G H │
└─── │
│ I J K L │
└──────── ────┘Q-Learning 구현에 앞서서 gamma와 alpha값을 설정한다.
gamma = 0.75
alpha = 0.9gamma(γ)는 미래 보상에 대한 가중치이다.(할인계수)
gamma가 1에 가까울수록 장기적인 보상을 크게 생각하고, 0에 가까울수록 현재 보상을 중요하게 생각한다.
alpha(α)는 새로운 경험이 Q값을 업데이트하는 정도를 조절한다.(학습률)
alpha가 1에 가까울수록 최근의 경험이 Q값에 큰 영향을 주고, 0에 가까울수록 과거의 경험을 계속 유지하려고 한다.
학습속도와 안정성의 상충관계이다.
위 파라미터를 설정한 후 마르코프 의사결정 모델에 필요한 변수들을 정의한다.
마르코프 결정 과정(MDP)은 튜플 (S, A, T, R)로 정의된다.
S, A, R은 각각 상태, 행동, 보상이다. 이전에 정리해둔 마르코프 의사결정 과정 글에서는
마르코프 의사결정 과정이 (S, A, P(s,s'), R(s,s'), γ) 5중쌍으로 구성된다고 했지만
γ(할인계수)는 위에서 정의했고, P(s,s') 대신 상태전이함수 T를 사용한다.
T는 상태전이 함수이다. P는 그에 대한 결과이고.
이는 새로운 행동을 선택할 때 사용된다.
S, A 정의
먼저 S와 A에 해당하는 state와 action을 정의한다.
location_to_state = {'A': 0,
'B': 1,
'C': 2,
'D': 3,
'E': 4,
'F': 5,
'G': 6,
'H': 7,
'I': 8,
'J': 9,
'K': 10,
'L': 11}
state_to_location = {state: location for location, state in location_to_state.items()}
# action 정의
actions = [0,1,2,3,4,5,6,7,8,9,10,11] # 현재 위치에서 숫자에 해당하는 위치로 가는 12가지 행동추후 작성할 Q-Learning 함수에서 사용하기 편하려면 각 알파벳에 숫자를 매핑해두는 것이 도움이 된다.
location_to_state로 알파벳 위치를 숫자로 변환하고,
state_to_location으로 숫자를 알파벳 위치로 변환한다.
actions는 현재 state에서 숫자에 해당하는 다음 위치로 이동하는 것을 의미한다.
R 정의
R에 해당하는 reward표를 작성해서 제공한다. 여기서 갈 수 있는 경로는 1의 보상을 주어 길이 있는 곳으로만 이동할 수 있도록 한다.
A B C D E F G H I J K L
A | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
B | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
C | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
D | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
E | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
F | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
G | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
H | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
I | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
J | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 |
K | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 |
L | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 |F를 예시로 들면, F에서 갈 수 있는 곳은 B, J 밖에 없다.
F행이나 F열을 보면 모두 B, J에만 1값이 있고 나머지는 0이다.
B에서 F로도 갈 수 있고, F에서 B로도 갈 수 있기 때문에 위 표는 대칭이다.
특정 위치에 1보다 높은 보상을 주어서 해당 지점을 목적지로 만들거나
특정위치에 음수값을 넣어서 장애물을 만들 수도 있다.
위 표대로 보상행렬 R을 정의한다.
R = np.array([[0,1,0,0,0,0,0,0,0,0,0,0],
[1,0,1,0,0,1,0,0,0,0,0,0],
[0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,0,0,0,0],
[0,0,0,0,0,0,0,0,1,0,0,0],
[0,1,0,0,0,0,0,0,0,1,0,0],
[0,0,1,0,0,0,1,1,0,0,0,0],
[0,0,0,1,0,0,1,0,0,0,0,1],
[0,0,0,0,1,0,0,0,0,1,0,0],
[0,0,0,0,0,1,0,0,1,0,1,0],
[0,0,0,0,0,0,0,0,0,1,0,1],
[0,0,0,0,0,0,0,1,0,0,1,0]])T
T : (st ∈ S, st+1 ∈ S, at ∈ A) → P(st+1|st, at)
여기서 P(st+1|st, at)는 상태 st에서 행동 at을 했을 때, 미래의 상태 st+1에 도달할 확률을 나타냅니다. 따라서 T는 시간 t+1에서의 미래 상태에 대한 확률 분포입니다. 이 분포 T에서 랜덤으로 선택하여 미래 상태 st+1을 예측할 수 있습니다:
st+1 ∼ T(st, ., at)
여기서 행동을 선택하는 규칙을 만들 수 있는데, 여기선 균등 분포로 구현했다.
쉽게 말해 랜덤으로 뽑는다는 얘기이다.
next_state = np.random.choice(playable_actions)더 발전된 방법으로는 학습이 진행되면서 점점 최적의 행동을 선택(exploitation)하도록 하는 ϵ-탐욕(ϵ-greedy) 전략이 있다고 한다.
Q-테이블 업데이트 함수(Q-Learning)
함수 정의 및 초기 설정
함수는 파라미터로 starting_location과 ending_location을 받는다.
보상 행렬을 수정하여 목적지를 설정해야 하기 때문에 복사본을 하나 만들고
복사한 보상 행렬에 1000이라는 보상값을 설정하여 ending_location 위치에 넣는다.
def route(starting_location, ending_location):
R_new = np.copy(R)
ending_state = location_to_state[ending_location]
R_new[ending_state, ending_state] = 1000Q 테이블 구현
행동에 대한 가치를 나타내는 Q테이블을 만들고, 1000번 Q테이블을 업데이트하는 기능을 넣는다.
현재 위치를 랜덤으로 정하고, 그 위치에서 할 수 있는 행동들을 배열에 담는다.
TD(현재의 보상 + 미래의 최대 Q-값)를 적용하여 현재 행동에 대한 Q-값을 업데이트한다.
이는 길찾기 학습을 하는 도중 점진적으로 값을 업데이트한다.
이때 미래의 최대 Q-값을 적용할 때 앞에서 정의한 gamma(할인계수)를 사용하고
TD를 사용하여 Q테이블을 업데이트할 때 앞에서 정의한 alpha(학습률)를 사용한다.
...
Q = np.array(np.zeros([12,12]))
for i in range(1000):
current_state = np.random.randint(0,12)
playable_actions = []
for j in range(12):
if R_new[current_state, j] > 0:
playable_actions.append(j)
next_state = np.random.choice(playable_actions)
TD = R_new[current_state, next_state] + gamma * Q[next_state, np.argmax(Q[next_state,])] - Q[current_state, next_state]
Q[current_state, next_state] = Q[current_state, next_state] + alpha * TD경로 탐색
이제 경로 탐색 기능을 구현한다
먼저 출력할 최적 경로를 담을 route 배열을 정의한다.
그리고 최종 목적지에 도달할 때까지
현재 상태에서 전이 가능한 상태 중에 가장 큰 Q값을 가지는 경로를 찾아
해당 경로를 route배열에 담아준다.
...
route = [starting_location]
next_location = starting_location
while (next_location != ending_location):
starting_state = location_to_state[starting_location]
next_state = np.argmax(Q[starting_state,])
next_location = state_to_location[next_state]
route.append(next_location)
starting_location = next_location
return route출력부
출발지 - 경유지 - 도착지 를 파라미터로 받는 best_route 함수를 정의하고 최적 경로 출력
def best_route(starting_location, intermediary_location, ending_location):
return route(starting_location, intermediary_location) + route(intermediary_location, ending_location)[1:]
# 최종 경로 출력
print('Route:', best_route('E', 'K', 'G'))처음으로 뭔가 동작하는 것을 구현해봤다. 그런데 이건 학습용으로만 쓰고 실제로는 더 복잡하고 성능 좋은 것들을 쓴다고 하니 열심히 더 공부해야겠다.
