휴리스틱 알고리즘 + 지렁이 게임 코드리뷰

'알고리즘'으로 모든 문제를 해결할 수 있을까?? 아쉽게도 그렇지 않다.

의사결정을 위해서는 다양한 변수를 고려해야 하지만 정보의 부족과 시간제약으로 완벽한 의사결정을 할 수 없다. 우리는 실현 가능한 해답이 필요하다. 휴리스틱은 이런 경우를 위해 현실적으로 만족할 만한 수준의 해답을 찾는 것을 의미한다.

특히 경험이나 직관을 사용하거나 시행착오를 거쳐서 충분히 효율적인 해답이나 지식을 얻게 된다. 

---

휴리스틱 알고리즘 중에서도 다가가기 쉬운 메타 휴리스틱 알고리즘에 대해 다뤄보자! 

특정 문제에 특화되지 않고 ​

자연에서 영감을 얻은 경험적 방법​

&​

휴리스틱 알고리즘 중 여러 도메인에서 활용할 수 있도록 일반화되어 발전된 ​

알고리즘​

휴리스틱 알고리즘에는 다양한 종류가 있는데
(1) 자연의 진화과정을 모방한 진화 알고리즘(evolutionary algorithm: EA)​​
(2) 군집(Swarm & colony) 생활하는 생물들의 행위를 모방하는 알고리즘
​​(3) 자연 및 사회 현상을 모방한 알고리즘
​​(4) 체계적인 반복으로 이웃을 탐색하는 알고리즘
등이 있다. Neural Network가 우리 몸의 뉴런에서 기인한 알고리즘인 것처럼, 이 또한 동물의 행위 또는 진화과정에서 착안한 알고리즘이라는 것이 매우 독특하다.

그 중 GA(Genetic) 알고리즘은 동물의 번식 패턴, 진화 과정을 구현한 휴리스틱이다.
다음 그림은 GA 알고리즘의 대표적인 사례로, 최단 경로 검색이다. 
우리가 최적 경로를 찾을 때 쓰는 다익스트라 알고리즘과 비슷한 문제를 해결할 수 있는 또다른 알고리즘이라고 생각하면 된다.(이 둘의 효율성에 대한 많은 논문이 있다). 둘의 차이는 다익스트라는 '최적화'를, GA는 '만족하기'를 목표로 한다. (알고리즘과 휴리스틱의 차이)

---

​그럼 이걸 기반으로 실질적인 코드를 한 번 보자! - 유전알고리즘 GA를 이용한 지렁이 게임
(코드 리뷰 출처는 다음과 같습니다 올려도된다고 하셨댱 https://github.com/kairess/genetic_snake )

유전알고리즘 절차 요약 (사실 간단하게 말하면 진짜 이게 다인데, 코드로 학습시킨다는 것이 아주 놀랍다,,)

해당 코드를 살펴보면 이렇게 Evolution.py, Genome.py, Snake.py 의 세 개의 코드로 나누어져 있다. 
나는 이 코드가 실행되는 과정을 보면서 '인공지능', '학습 과정'이라는 단어를 눈으로 손으로 느낀 기분이었다. 그정도로 왕흥미로웠다✨✨
유전 알고리즘이라 생명과학을 조금 알면 더 도움이 되는 부분이 있다.🤣🤣

Evolution.py 
전체적인 설명으로는, 세대가 한 번씩 돌아가면서 snake가 자신의 fitness와 score의 값을 매기는 과정이라고 할 수 있다.

이 안에서 또 크게 3가지 과정으로 나눌 수 있는데 
먼저 1번째 세대를 형성한다. 한 세대 당 염색체 수를 의미하는 population은 50개로 지정하고 이 때 best_genomes는 빈 문자열로 놓는다.

genomes = [Genome() for _ in range(N_POPULATION)]
best_genomes = None

이제 for문으로 snake가 자신의 길을 가도록 실행시키는 run 함수를 실행시킵니다. 3번째 파일(snake.py)에서 세부적인 것을 가져온다. 그리고 이 때 snake가 가지는 유전자가 genome이다.

for i, genome in enumerate(genomes):
    snake = Snake(s, genome=genome)
    fitness, score = snake.run()

    genome.fitness = fitness

 

이렇게 세대가 돌아갈 때마다 fitness가 훌륭한 것들을 내림차순으로 해서 유전자들을 best_genomes 리스트에 정렬합니다. 

  if best_genomes is not None:
    genomes.extend(best_genomes)
  genomes.sort(key=lambda x: x.fitness, reverse=True)

  print('===== Generaton #%s\tBest Fitness %s =====' % (n_gen, genomes[0].fitness))
  # print(genomes[0].w1, genomes[0].w2)

  best_genomes = deepcopy(genomes[:N_BEST])

 crossover 함수에서는 이제 이 리스트에서 최고의 genome 5개를 뽑아 그 genome들에 있는 유전체들끼리 임의로 change해서 교배시킨다. 그렇게 이 과정을 꾸준히 반복. 

# crossover
  for i in range(N_CHILDREN):
    new_genome = deepcopy(best_genomes[0])
    a_genome = random.choice(best_genomes)
    b_genome = random.choice(best_genomes)

    cut = random.randint(0, new_genome.w1.shape[1])
    new_genome.w1[i, :cut] = a_genome.w1[i, :cut]
    new_genome.w1[i, cut:] = b_genome.w1[i, cut:]
    ###

    best_genomes.append(new_genome)

mutation함수는 변이를 하나씩 만드는 것인데요, 저번에 설명했다시피 우리가 지역변수에 빠질수 있으므로 전역 변수에 있는 더 좋은 genome을 만들기 위해 random함수를 이용해 예상지 못한 값을 만드는 것이다. (이쪽 코드는 끝내 잘 이해하지 못했다 ㅠㅠ)

  # mutation
  genomes = []
  for i in range(int(N_POPULATION / (N_BEST + N_CHILDREN))):
    for bg in best_genomes:
      new_genome = deepcopy(bg)

      mean = 20
      stddev = 10

      if random.uniform(0, 1) < PROB_MUTATION:
        new_genome.w1 += new_genome.w1 * np.random.normal(mean, stddev, size=(6, 10)) / 100 * np.random.randint(-1, 2, (6, 10))
        
        ###

 

genome.py에는 numpy를 이용한 행렬 곱셈이나 softmax함수를 이용해서 classification에 사용하였다. (단순 모델 생성 코드라 생략)

class Genome():
  def __init__(self):
    ###
  def forward(self, inputs):
    ###
  def relu(self, x):
    ###
  def softmax(self, x):
    ###
  def leaky_relu(self, x):
    ###

snake.py는 대략적으로 말하면 이제 뱀이 어떻게 움직이게 할지에 대한 코드이다.
먼저 snake가 다니는 범위를 우리는 코드로 up, down, right, left로 각각 1차원 배열로 이렇게 나타낼 수 있다.

DIRECTIONS = np.array([
  (0, -1), # UP
  (1, 0), # RIGHT
  (0, 1), # DOWN
  (-1, 0) # LEFT
])

우리는 뱀의 시작위치를 한 군데로 고정해 준다음에, 과일은 뱀이 있는 곳을 제외한 무작위배치로 지정해준다. 

타이머도 0으로 맞추고 과일을 찾는 시간도 일단 0으로 맞춰준 후 뱀의 이동하는 과정은 머리를 기준으로 direction을 지정해 준다. 뱀이 스크린을 벗어나게 될 때는 false값을, 과일을 먹게 된다면 보상을 매우 크게 주고 다시 시작한다. 뱀 입장에서는 우리가 센서를 달아주어 먹이가 나를 기준으로 왼쪽에 있니 오른쪽에 있니 또는 앞에 있니 없니 로  판단한다고 생각하자.

class Snake():
  snake, fruit = None, None

  def __init__(self, s, genome):
    ###self.genome, self.s, self.score, self.snake, self.direction, self.place_fruit(), self.timer, self.last_fruit_time
    
    # fitness
    ###self.fitness, self.last_dist(np.inf)

  def place_fruit(self, coord=None):
    ###난수로 fruit를 grid에 놓는 함수

  def step(self, direction):
    ###sanke를 이동시키되 snake가 벽에 부딪히면 벌점을 급격하게 준다.
    # eat fruit
    if all(new_head == self.fruit):
      ###fruit를 먹으면 상점 +1
    else:
      ###아닐 때는 이동(head를 direction에 맞게 한 칸 가고 tail 또한 한 칸 이동)

  def get_inputs(self):

    # check forward, left, right
    possible_dirs ###앞/왼/오로 갈 수 있다. 지정해주는 함수

    # 0 - 1 ... danger - safe
    for i, p_dir in enumerate(possible_dirs):
		###지렁이가 어디로 갈지에 대한 센서

    # finding fruit
    # heading straight forward to fruit
   	 ###센서로 앞/오른/왼 중 어디로 갈지 결정 ,,
    # fruit is on the left side
    if np.sum(head * possible_dirs[1]) < np.sum(self.fruit * possible_dirs[1]):
      result[4] = 1
    # fruit is on the right side
    # if np.sum(head * possible_dirs[2]) < np.sum(self.fruit * possible_dirs[2]):
    else:
      result[5] = 1

    return np.array(result)

  def run(self):
    ###py.game이라는 툴을 이용해서 지렁이가 가는 길을 게임 형태의 픽셀로 표현해준다. 
    ###이 때 epoch마다 받게 되는 보상 값 등이 출력됨

 

이 때 코드에서의 주의해야 할 점은 지렁이가 뒤로 가려고 할 때나 아니면 가려는 방향이 자신의 몸과 겹치게 되는 상황을 어떻게  해결할 것이냐이다. 지렁이가 이렇게 멍청한 판단을 내리려고 한다면 우리는 벌을 매우 많이 줘서 Terminate!멈춰!라는 벌을 줄 수 있다.  

이제 지렁이는 자신의 머리와 과일까지의 거리를 반환한 후 가까워지면 +1 멀어졌으면 -1.5로 fitness값을 갖게 되고 결국 세대마다의 fitness값은 점점 유전함에 따라 증가하게 된다.

최종적으로 이렇게 구현된다

공부해보면서 들었던 다양한 질문!?

1. 지렁이에게 센서를 달아서​ 먹이가 왼쪽에 있는지 오른쪽에​ 있는지 또는 앞에 있는지 없는지를​ 판단하게 한 것이 딥러닝 측면에서 지렁이가​ 학습하기 위해 가지는 최소의 skill일까?​

2. 코드를 짜다보면 생기는,​ 다양한 +의 상황 또는 -의 상황에서​ Fitness값의 크기를 어떻게​줘야 가장 이상적인 best fitness값을​ 가지며 성장할 수 있을까?​
​
3. 파이썬 함수로 공부해봤는데, 우성을 판별할 때​ List에 내림차순 배열했던 것처럼​ 이렇게 코드화 시키는 것에​ 대한 고민​을 더 하자.