[백준: Python] 2582 - 동전 뒤집기 2

[문제]

https://www.acmicpc.net/problem/2582

solved.ac에서 시뮬레이션 문제를 풀려고 검색하다가 재밌는 유형을 발견했습니다.

 

Simulated Annealing은 전역 최적화 알고리즘으로, 제가 석사 과정 시절 진화형 알고리즘 수업에서 배웠던 알고리즘입니다. 그 당시 배우기를 Hill-Climbing Search의 문제점을 해결하기 위해 고안된 알고리즘이라고 배웠습니다.

 

Hill-Climbing Search는 AI에 대해 학습하다 보면 한 번쯤은 접하게 되는 알고리즘입니다. 

https://www.javatpoint.com/hill-climbing-algorithm-in-ai

Hill-Climbing Search는 경사(기울기)를 따라가며 최적해를 찾습니다. 하지만 시작점에 따라 Local optima에 빠질 확률이 높다는 문제점을 가집니다.

 

위 그림처럼 Current state와 같은 상황이 주어졌다면, 최댓값을 찾는 것이 목표이므로 더 높은 값을 찾아가게 됩니다. 이때 알고리즘은 Local maxima에 빠지게 됩니다.

 

왜냐하면 Hill-Climbing Search는 Greedy한 알고리즘으로, Current와 Succesor의 값을 비교해 갱신된 Succesor가 Current와 같거나 작으면 탐색을 종료하기 때문입니다.(최댓값을 찾는 상황)

while current < successor:
    successor = generate_successor
    if current < successor:
        current = successor

이를 해결하기 위해 나온 것이 Simulated Annealing 알고리즘입니다.

 

Simulated Annealing은 Hill-Climbing Search의 Greedy한 성질에 무작위 이동을 추가한 알고리즘입니다. 취지는 항상 좋은 값만 선택하는 것이 아니라, 이따금씩 좋지 못한 값을 선택함으로써 Local optima를 벗어나기 위한 전략으로 사용하는 것입니다.

 

알고리즘의 특징적인 측면으로 보면 다음과 같습니다.

• 무작위 이동
  • 항상 Global optima 보장
  • 무작위 이동인만큼, 무수한 기회 중에 한 번은 도달하기 때문
  • 하지만 그만큼 시간의 의존적이며, 일반적으로 충분한 시간이 보장되어야 함
  • 그러므로 시간이 얼마나 걸릴지 모르는 큰 단점이 존재
• Hill-Climbing Search
  • 경사(기울기) 기반 탐색이기 때문에 빠르게 Optima에 수렴
  • 그만큼 Local optima에 빠질 가능성이 큼

즉 Simulated Annealing은 빠른 속도와 무작위 이동을 통해, 각각의 문제점을 보완한 알고리즘이라 할 수 있습니다.

https://www.researchgate.net/figure/Pseudocode-for-Simulated-Annealing_fig2_228341134

알고리즘의 슈도 코드입니다.

 

해당 알고리즘의 핵심 변수는 ∆E와 T입니다. 여기서 T는 온도(Temperature)를 의미하며 T를 서서히 감소시키며 Optima를 찾아갑니다. ∆E는 갱신된 Optima의 나빠진 정도를 나타나냅니다. T의 값이 높을수록 좋지 못한 값을 선택할 확률이 높습니다.

 

철제기구를 만들 때, 뜨거운 상태에서 온도를 낮추며 경도를 높이는 것처럼, 초기에 좋지 못한 값을 선택하다가 점점 좋을 값을 찾아내는 것이 Simulated Annealing 알고리즘입니다.

 

이제 해당 알고리즘을 이용해 확률에 따라 동전을 뒤집으며 최적의 값이 나오는지 확인해 보겠습니다.

---

[초기화]

    def __init__(self):
        self.n = int(input())
        self.board = [list(input().strip()) for _ in range(self.n)]
        self.T = 2  # 초기 온도
        self.cooling_rate = 0.99999
        self.max_iterations = 10000

온도와, 감소 정도, 반복 횟수를 지정합니다.

 

정해진 것은 없기 때문에, 저 같은 경우 Kaggle에 정답 제출하듯이 값을 조정하며 해당 값에 정착하였습니다.

 

참고로 초기 온도는 작을수록, 감소 정도는 1에 가까울수록 정답률이 높았습니다.

---

[풀이]

    def flip_coin(self, coin):
        return 'H' if coin == 'T' else 'T'

단순히 동전의 상태를 반전시키는 것을 모듈화 하였습니다.

    def generate_neighbor(self, current_board, pr=None):
        # 유전 알고리즘 특성상 다양성 확보를 위해 행, 열 다 생성했지만, 고정하는 것이 효과적
        # n x n의 크기라 행과 열을 함께 처리하면 원상복구되는 데이터가 있어서 그런 것으로 판단
        idx = random.randint(0, self.n - 1)
        new_board = [r[:] for r in current_board]
        # if pr < 0.5:  # 열 방향 뒤집기
        for row in new_board:
            row[idx] = self.flip_coin(row[idx])
        # else:  # 행 방향 뒤집기
        #     for i in range(self.n):
        #         new_board[idx][i] = self.flip_coin(new_board[idx][i])

        return new_board

무작위로 동전을 뒤집습니다.

 

처음엔 문제에 맞춰 한 행 혹은 열을 뒤집을 수 있도록 확률에 따라 뒤집었는데, 오히려 정답률이 떨어졌습니다.

 

제 생각엔 행 혹은 열을 뒤집을 때 독립적으로 수행되어야 하는데, 행과 열을 함께 뒤집으면 이전에 뒤집은 동전을 다시 원상 복구하면서 문제가 되는 것으로 보입니다.

 

알고리즘의 흐름은 다음과 같습니다.

1. 무작위로 뒤집을 열 선정
2. 행을 순회하며 선택된 열의 값 반전
3. 새롭게 만들어진 데이터 반환

    def count_tails(self, board, pr=None):  # 현재 행에서 뒤집거나 유지해서 만들 수 있는 T의 수 계산
        tails_count = 0
        # if pr < 0.5:  # 각 행에서 비교(열 방향 뒤집기)
        for r in range(self.n):  # 행을 검사하는 이유를 특정 열을 뒤집었을 때, 각 행들이 간섭받으므로
            tails_count += min(board[r].count('T'), self.n - board[r].count('T'))  # T의 수, H의 수
        # else:  # 각 열에서 비교(행 방향 뒤집기)
            # for c in range(self.n):
            #     col_tails = sum(1 for r in range(self.n) if board[r][c] == 'T')
            #     tails_count += min(col_tails, self.n - col_tails)
        return tails_count

해당 메서드는 Objective function 혹은 Fitness function이라 불리는 평가 함수를 정의한 것입니다.

 

새로 만들어진 데이터의 품질을 평가하게 되며 새롭게 만들어진 데이터의 뒷면의 값을 계산합니다. 

 

뒷면(T)이 많을 땐, 해당 뒷면들을 앞면으로 만들고, 앞면을 뒷면으로 만들어야 뒷면의 수를 최소화할 수 있습니다.

앞면(H)이 많을 땐 그만큼 뒷면의 수가 적다는 의미이므로 그대로 선택합니다.

 

즉, 해당 메서드는 현재 최소이거나, 최소가 될 뒷면의 수를 합산합니다.

 

주의할 점은, 해당 메서드는 새롭게 만들어진 데이터의 품질을 평가하는 것이므로 그에 맞게 평가를 진행해야 한다는 것입니다.

 

현재 코드에서는 열을 기준으로 뒤집었지만, 검사는 행을 기준으로 합니다. 이유는 하나의 열을 뒤집음으로써 모든 행에 영향을 미쳤기 때문입니다.

 

반대의 경우도 마찬가지입니다. 행을 뒤집었다면, 모든 열에 영향을 미쳤으므로, 검사를 열기준으로 진행합니다.

 

달리 생각하면 바뀐 데이터를 평가할 때, 열을 뒤집었을 경우 그 부분이 포함된 데이터를 검사하는 방법은 행을 검사하는 방법밖에 없기 때문에 위 코드와 같이 검사를 하게 되는 것입니다.

뒤집은 모양과 검사 방향

    def simulated_annealing(self):
        current_board = self.board
        current_energy = self.n**2
        best_energy = current_energy

        for _ in range(self.max_iterations):
            # pr = random.randint(0, 1)
            new_board = self.generate_neighbor(current_board)
            next_energy = self.count_tails(new_board)
            delta_E = next_energy - current_energy

            if delta_E < 0 or random.random() < exp(-delta_E / self.T):
                current_board = new_board
                current_energy = next_energy

            best_energy = min(best_energy, current_energy)

            self.T *= self.cooling_rate

        return best_energy

실제 알고리즘의 실행부입니다.

 

1. Optima 초기화
2. 지정한 횟수만큼 반복
   1. 새로운 데이터 생성
   2. 생성한 데이터 평가
   3. 나빠진 정도 평가
   4. 나빠진 정도에 따라 기존 데이터를 새로운 데이터로 교체
      • ∆E의 값이 음수라는 것은 새로운 데이터의 품질이 더 좋다는 것입니다. 즉 현재 보다 T의 수가 적다는 의미
      • 반대로 성능이 나아지지 않았다면 확률에 따라 부분적으로 채택합니다. 해당 부분은 슈도 코드와 일치합니다.
   5. 매 반복마다 찾아낸 Optima의 값을 저장합니다.
   6. 온도를 감소시킵니다.

---

[전체 코드]

import random
from math import exp


class Main:
    def __init__(self):
        self.n = int(input())
        self.board = [list(input().strip()) for _ in range(self.n)]
        self.T = 2  # 초기 온도
        self.cooling_rate = 0.99999
        self.max_iterations = 10000

    def flip_coin(self, coin):
        return 'H' if coin == 'T' else 'T'

    def count_tails(self, board, pr=None):  # 현재 행에서 뒤집거나 유지해서 만들 수 있는 T의 수 계산
        tails_count = 0
        # if pr < 0.5:  # 각 행에서 비교(열 방향 뒤집기)
        for r in range(self.n):  # 행을 검사하는 이유를 특정 열을 뒤집었을 때, 각 행들이 간섭받으므로
            tails_count += min(board[r].count('T'), self.n - board[r].count('T'))  # T의 수, H의 수
        # else:  # 각 열에서 비교(행 방향 뒤집기)
            # for c in range(self.n):
            #     col_tails = sum(1 for r in range(self.n) if board[r][c] == 'T')
            #     tails_count += min(col_tails, self.n - col_tails)
        return tails_count

    def generate_neighbor(self, current_board, pr=None):
        # 유전 알고리즘 특성상 다양성 확보를 위해 행, 열 다 생성했지만, 고정하는 것이 효과적
        # n x n의 크기라 행과 열을 함께 처리하면 원상복구되는 데이터가 있어서 그런 것으로 판단
        idx = random.randint(0, self.n - 1)
        new_board = [r[:] for r in current_board]
        # if pr < 0.5:  # 열 방향 뒤집기
        for row in new_board:
            row[idx] = self.flip_coin(row[idx])
        # else:  # 행 방향 뒤집기
        #     for i in range(self.n):
        #         new_board[idx][i] = self.flip_coin(new_board[idx][i])

        return new_board

    def simulated_annealing(self):
        current_board = self.board
        current_energy = self.n**2
        best_energy = current_energy

        for _ in range(self.max_iterations):
            # pr = random.randint(0, 1)
            new_board = self.generate_neighbor(current_board)
            next_energy = self.count_tails(new_board)
            delta_E = next_energy - current_energy

            if delta_E < 0 or random.random() < exp(-delta_E / self.T):
                current_board = new_board
                current_energy = next_energy

            best_energy = min(best_energy, current_energy)

            self.T *= self.cooling_rate

        return best_energy

    def solve(self):
        answer = self.simulated_annealing()
        print(answer)


problem = Main()
problem.solve()

평가 함수를 정의하는 부분에서 가장 많은 애를 먹었습니다. 단순하게 T의 수를 모두 합산하면 되는 줄 알았는데, 그렇게 되면 저조한 정답률이 나타났습니다.

 

그다음 시간을 많이 쓴 것을 파라미터 지정이었습니다. 항상 만점(71)을 받아내려고 여러 번 시도하며 AI 모델 평가할 때 하이퍼 파라미터 튜닝하는 느낌이 많이 났습니다.

 

아무래도 해당 알고리즘 자체가 AI와 밀접한 연관이 있어서 그런 거 같습니다.

 

시간을 많이 쓰긴 했지만 덕분에 재밌는 경험을 할 수 있던 문제였습니다.

---