[보충 실험] D-Wave Leap의 DQM을 사용하여 최소한의 색깔로 지도의 페인트 문제를 해결한다.

개시하다

AIREV 주식회사의 상리.
이전에 투고한 DQM(Discrete Quadratic Model)으로 지도의 페인트 문제를 해결한 글에서는 캐나다의 주를 4가지 색깔로 칠해 보았다.D-Wave 공식 문서라는 예제를 사용해 페인트칠한 결과의 지도를 자세히 살펴보면 "3가지 색깔로도 떼어낼 수 있는 지도 아닌가?"나는 이 점을 알아차렸다.이번에는 더 적은 색으로 지도를 도장하기 위해 문제 공식화에 공을 들였는데, 실제 3가지 색으로 구분할 수 있는지 추가 실험을 해보고 싶다.

지난번 문제 공식화된 복습

DQM의 기초 지식과 D-Wave Leap 사용 방법 등은 생략하므로 적절히 참조공식 문서와저번 보도 하십시오.

캐나다 13개 주 지도 도장 문제

캐나다의 모든 13개 주(반주 포함)에서 양자 퇴화를 이용해 지도에 인접한 주에서 같은 색을 칠하지 않는 4가지 색 분배 방법을 찾았다.
13개 주 리스트provinces, 인접 주 대조 리스트borders, 4개 색깔 리스트colors.

provinces = [
  "AB", "BC", "ON", "MB", "NB", "NL", "NS",
  "NT", "NU", "PE", "QC", "SK", "YT"
]
borders = [
  ("BC", "AB"), ("BC", "NT"), ("BC", "YT"), ("AB", "SK"), ("AB", "NT"),
  ("SK", "MB"), ("SK", "NT"), ("MB", "ON"), ("MB", "NU"), ("ON", "QC"),
  ("QC", "NB"), ("QC", "NL"), ("NB", "NS"), ("YT", "NT"), ("NT", "NU")
]
colors = [0, 1, 2, 3]

변수 설정

DQM 인스턴스를 생성하고 변수를 추가합니다.우리는 주마다 어떤 색이 분배되었는지 표시하기 위해 변수를 만들 것이다.구체적으로 각 주에 변수colors의 색상 값{0, 1, 2, 3}을 생성합니다.

import dimod

dqm = dimod.DiscreteQuadraticModel()
for p in provinces:
  dqm.add_variable(len(colors), label=p)

목적 함수 벌칙의 디자인

지도상에 인접한 두 주에 같은 색깔이 배정된 경우1를 처벌한다.

for p0, p1 in borders:
  dqm.set_quadratic(p0, p1, {(color, color): 1 for color in colors})

지금까지 지난 글의 공식화입니다.

색상 유형에 대한 벌칙 설정

마지막 공식에서 색상은 정수 목록[0, 1, 2, 3]으로 표시됩니다.매번 사용1한 색깔은 처벌1, 매번 사용2한 색깔은 처벌2을 준다. 이렇게 DQM의set_linear 방법으로 벌칙을 설정하여 수치가 큰 색깔은 최대한 사용하지 않도록 한다.3와2의 색상은 상대적으로 사용하기 어려워서3 사용하지 않고 3가지 색상으로 칠한 솔루션을 최적의 솔루션으로 유도했다.

colors = [0, 1, 2, 3]

for p in provinces:
  dqm.set_linear(p, colors)

이때 인접한 주에서 같은 색깔이 분배되었을 때 벌칙의 값과 색깔의 종류에 따라 벌칙의 값의 상대적인 크기 관계가 문제가 되었다.이번에는 인접한 주에는 같은 색상을 할당하지 말고, 최대한 적은 양의 색상을 사용해 솔루션을 유도하는 것이 우선이기 때문에 인접한 주에는 같은 색상을 할당할 때 처벌을 상대적으로 크게 설정했다.
구체적으로 색상 종류에 대한 처벌이 가장 큰 합계치max(colors) * len(provinces)를 인접한 주에 같은 색상을 할당할 때의 처벌로 설정했다.

adj_penalty = max(colors) * len(provinces) + 1

for p0, p1 in borders:
  dqm.set_quadratic(p0, p1, {(color, color): adj_penalty for color in colors})

풀어보다

실제 해답의 결과는 다음과 같다.

7.0 # Energy
{'AB': 1, 'BC': 0, 'MB': 1, 'NB': 0, 'NL': 0, 'NS': 1, 'NT': 2, 
 'NU': 0, 'ON': 0, 'PE': 0, 'QC': 1, 'SK': 0, 'YT': 1} # Sample

(0: 파란색, 1: 빨간색, 2: 녹색)
인접한 주에는 같은 색을 할당하지 않고 3가지 색으로 칠해 분리한다.
이번 공식화는 사용된 색상 값을 벌칙으로 1한 색상을 5회, 2한 색상을 1회 사용한 결과 에너지 값1 * 5 + 2 * 1 = 7.0이 바뀌었다.
또 최소치0 색상을 7번 사용했고, 한 번3 색상도 사용하지 않았다.
이번 공식 제정의 목적은 "가급적 큰 수치의 색을 사용하지 않고 최적화하려는 것"이라고 밝힌 것으로 보인다.

두 컬러는 구분해서 바르면 안 되나요?

정말 이웃 주에 같은 색을 할당할 수 없어요.
신중을 기하기 위해 지난 글에서 색상 값을 포함하는 벌금의 공식화는 없었고, 색상 리스트를 colors = [0, 1]로 변경해 두 가지 색만 칠했는지 검증했다.

colors = [0, 1]

dqm = dimod.DiscreteQuadraticModel()
for p in provinces:
  dqm.add_variable(len(colors), label=p)

for p0, p1 in borders:
  dqm.set_quadratic(p0, p1, {(color, color): 1 for color in colors})

결과는 다음과 같다.

２.0 # Energy
{'AB': 1, 'BC': 0, 'MB': 1, 'NB': 0, 'NL': 0, 'NS': 1, 'NT': 1, 
 'NU': 0, 'ON': 0, 'PE': 1, 'QC': 1, 'SK': 0, 'YT': 0} # Sample

(0: 파란색, 1: 빨간색)
에너지의 가치2.0는 두 지방이 인접한 주에서 같은 색깔로 분배됐다.
(이전 기사의 공식화를 사용했기 때문에 색상 값으로 처벌받지 않습니다.)
이에 따라 3가지 색상이 캐나다주를 가르는 가장 적은 색상인 것으로 확인됐다.
이번 공식화는 예상대로 최소한의 색으로 칠했다.

총결산

이번에는 최소한의 색깔로 캐나다주를 도장하는 문제를 DQM으로 공식화했다.
그 결과 3가지 색으로 페인트를 칠할 수 있다는 것이 밝혀졌다.
앞으로는 좀 더 실용적인 문제 설정에 퇴화를 적용하고 싶다.