김규태Sean Kim
연구 목록

연구 01 · 강화학습 · 그래프 신경망

강화학습으로 TSP 경로를 만드는 그래프 모델

2018.09–2021.06 · 학부연구생
공개 코드

도시를 그래프로 표현하고, 경로에 추가할 도시를 강화학습으로 고르는 탐색 프로그램을 구현했습니다.

  1. 1그래프로 표현

    도시, 거리, 방문 여부

  2. 2Structure2Vec + Q-learning

    도시마다 Q값 계산

  3. 3도시 선택과 경로 삽입

    모델이 고른 도시를 휴리스틱으로 삽입

강화학습 설계

상태
도시 연결(인접 행렬)과 거리, 이미 경로에 들어간 도시
행동
다음에 경로에 넣을 도시 고르기
보상
도시를 넣어 늘어난 경로 길이를 그대로 감점

NeurIPS 2017 그래프 조합 최적화 연구를 참고한 구현

Reinforcement learningStructure2VecDeep Q-learningGraph neural networkTensorFlowNumPy

직접 맡은 역할과 결과

연구 목표
도시가 늘수록 경우의 수가 급격히 커지는 TSP에서, 기존 알고리즘보다 빠르게 짧은 경로를 찾는 것이 목표였습니다. 지도교수님과 함께 강화학습으로 접근했습니다.
맡은 역할
참고 논문의 그래프 표현과 Q-learning 아이디어를 가져와 TSP 환경과 모델, 학습 루프, 삽입 규칙을 하나의 실험 코드로 구현했습니다.
만들어낸 결과
도시의 위치와 거리, 방문 여부를 그래프로 넣고, 모델이 고른 도시를 삽입 휴리스틱으로 경로에 추가하는 탐색 프로그램을 만들었습니다. 공개 코드로 기준선과 비교하는 실험을 하며 학습이 제대로 되지 않은 원인도 찾았습니다.

직접 구현·분석한 것

  • 노드, 엣지, 방문 상태를 담은 그래프 환경과 경로 비용 기록
  • Structure2Vec 임베딩과 Q값 평가
  • 여러 스텝 보상 누적과 경험 샘플링을 잇는 탐색 루프
  • 도시는 모델이 고르고 넣을 자리는 삽입 휴리스틱이 정하는 구조

바탕이 된 연구·공개 모델

  • NeurIPS 2017 그래프 조합 최적화 연구의 Structure2Vec·강화학습 접근

실험 결과와 시행착오

단축 학습에서는 무작위 삽입 대비 개선을 확인하지 못했습니다

원래 설정으로 학습해 보니, 정책이 모든 도시에 같은 Q값을 내며 번호 순서대로 도시를 골랐습니다.

  • TensorFlow 2.15
  • seed 3개
  • 에피소드 10,000 → 100
같은 도시 50개에서 학습 정책과 최원 삽입이 경로를 한 도시씩 쌓아 가는 애니메이션. 학습 정책은 번호 순서대로 도시를 골라 OR-Tools 대비 1.12배, 최원 삽입은 1.08배 경로를 만듭니다.
도시 50개인 한 문제의 경로 생성 과정입니다. 학습 정책(왼쪽)은 번호 순서대로 도시를 골라 OR-Tools 해보다 1.12배, 최원 삽입(오른쪽)은 1.08배 긴 경로를 만들었습니다. 아래 표는 여러 문제의 평균입니다.
  • +12%위 50도시 예시 · OR-Tools 해보다 긴 경로
  • 개선 미확인무작위 순서 삽입과 비교한 단축 학습
  • 2가지코드에서 찾은 원인
  1. 기대

    학습한 Q값이 경로를 짧게 만드는 도시를 고른다

  2. 당시 판단

    학습할수록 경로 비용은 줄었지만 최적해에는 못 미쳤고, 도시가 많아 충분히 탐색하지 못했다고 봤다

  3. 실제

    모든 도시의 Q값이 같아져 번호 순서대로 골랐다

  4. 원인

    정규화 없는 이웃 합으로 값이 폭증했고, TD 목표가 시작 도시만 봤다

문제와 해결

  1. 문제도시 수마다 행렬 크기가 달라, 크기가 고정된 신경망에 바로 넣을 수 없었습니다.

    해결Structure2Vec으로 도시마다 임베딩을 만들고, 평가 네트워크가 방문하지 않은 도시마다 Q값을 매기게 했습니다.

  2. 문제다음 도시를 고르는 것만으로는 경로의 어느 위치에 넣을지 정해지지 않습니다.

    해결도시 선택은 학습 모델이, 삽입 위치는 경로 길이가 가장 덜 늘어나는 자리를 찾는 휴리스틱이 맡도록 결합했습니다.

  3. 문제짧은 경로가 나와도 학습 효과인지 삽입 규칙의 효과인지 구분하기 어렵습니다.

    분석·검증무작위 도시 순서에도 같은 삽입 규칙을 적용해 비교하고 Q값과 TD 목표 계산을 추적했습니다. 단축 학습에서는 학습 정책의 개선을 확인하지 못했습니다.

실험 비교와 세부 결과

같은 도시 50개에서 학습 정책이 만든 경로와 OR-Tools 경로. 학습 정책 경로는 1.12배 길고 왼쪽에 긴 간선이 엇갈립니다.
완성된 두 경로입니다. 학습 정책의 경로(왼쪽)는 OR-Tools 경로보다 1.12배 길고, 긴 간선이 엇갈립니다.
도시 20개 문제에서 경로가 쌓이는 네 장면. 고른 도시, 끊긴 간선, 새 간선이 표시되어 있습니다.
경로를 만드는 방식입니다. 정책이 다음 도시(주황 점)를 고르면 삽입 함수가 경로가 가장 덜 늘어나는 자리의 간선(점선)을 끊고 새 간선으로 잇습니다.
도시 50개와 100개 문제에서 방법별 평균 경로 길이 비율. 학습 정책 1.13과 1.12, 무작위 순서 삽입 1.14와 1.13, 최원 삽입 1.05와 1.06.
OR-Tools를 1.00으로 둔 평균 경로 길이입니다. 학습 정책은 무작위 순서 삽입과 거의 같았고, 단순한 최원 삽입보다 길었습니다.
OR-Tools 해 대비 평균 경로 길이 비율 · 학습 범위는 도시 30–400개 · 세 seed의 학습 정책이 모두 같은 경로를 냈습니다
도시 수 (문제 수)학습 정책무작위 순서 + 삽입최원 삽입최근접 이웃학습 정책 vs 무작위 (Wilcoxon p)
20 (100) · 학습 범위 밖1.111.111.031.180.96
50 (50)1.131.141.051.210.24
100 (30)1.121.131.061.220.38

관찰한 원인과 남은 과제

  1. Q값 폭증

    정규화 없이 완전 그래프 전체를 더해 Q값이 수백만 단위로 커졌고, 갱신 손실이 10¹⁵ 단위까지 튀었습니다.

  2. TD 목표값 오류

    목표값이 남은 도시가 아니라 늘 시작 도시의 Q값으로 계산됐고, n-step 다음 상태도 한 칸 어긋나 있었습니다.

  3. 에피소드 100회로 줄임

    큰 그래프는 에피소드당 약 45초라 10,000회면 seed당 5일이 넘습니다. 횟수만 줄이고 나머지 설정은 그대로 뒀습니다.

결과를 읽는 기준

  • 원논문 그대로의 재현 아님 (target network 없음, n-step 방식 다름)
  • 설정된 에피소드의 1%만 학습
  • 끝까지 학습했을 때의 성능은 알 수 없음
다음 실험에서 보완할 점
  • 작은 문제에서 정답과 먼저 맞춰 보기
  • 이웃 합 정규화와 목표값 수정
  • 무작위 순서 기준선을 처음부터 두기
최근 프로젝트와 이어지는 점

처음으로 신경망을 직접 코드로 구현해 본 연구였습니다. 그래프의 요소와 관계를 학습 입력으로 표현해 본 경험이, 가구 패널과 면을 인식하는 지금의 연구로 이어졌습니다.

가구 패널을 인식해 크기 변경을 계산하는 AI