정올반 프로젝트 - 그래프 컬러링2

작성일 | In

GCP를 테스트할 때 자주 쓰이는 데이터셋을 기존에 구현했던 알고리즘으로 테스트해보니 만족할만한 성과가 나오지 않아 간단한 최적화 기법을 도입했습니다.

유전자가 생성이 되면, 해당 유전자를 그래프에 대입을 시킨 후 다음과 같이 BFS를 이용한 지역 최적화를 수행합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function localOptimize(gen){
  Q <- empty Queue
  V <- choose a vertex randomly
  Q.enqueue(V)

  while Q is not empty
    V <- Q.dequeue()
    adjColor <- all adjacent Color
    canColor <- all Color - adj Color
    V.color <- choose a color in canColor randomly

  for each U adj to V
    if not visited[u] then
      Q.enqueue(U)
}

이 최적화를 적용한 뒤 다시 한 번 돌려보았습니다.
기존의 코드에서는 50만 세대, 10분이 넘도록 정답이 나오지 않던 데이터셋에서 57세대만에 정답이 나왔습니다. 또한, 기존의 코드에서 85세대만에 해를 찾는 데이터셋에서는 최대 2세대 이내에서 해를 찾는 모습을 보여주었습니다.

수정된 코드와 보고서, 발표 슬라이드는 깃허브에서 볼 수 있습니다.