[ML/Lecture] Assignment #1. solving N-Queens (using genetic -algorithm) report.

 

본 내용은 제가 제출한 리포트의 일부 이며, 워드 리포트 제출물의 내용을, 포스팅을 위해 복사& 붙여넣는 과정에서 과정의 설명을 위한 표나 내용의 일부가 누락될 수 있음을 말씀드립니다.

 

 

[ 서론 ] 

1.1   N(5) queens problem

 

이번 과제는 다음과 같이 5 by 5 matrix안에 5개의 queen들을 각각 배치하는 경우를 구하는 것입니다. 여기서 queen이란 체스에서 queen 말을 뜻하는 것으로, 해당 queen이 위치한 행과 열, 그리고 대각선 방향에는 말이 위치하면 안됩니다. 이 경우의 수를 따져보면 다음과 같은 10개의 해답이 나올 수 있습니다. 이를 수업시간에 배운 genetic -algorithm을 통해 풀어내는 것이 이번 과제의 목표입니다.

 

1.2   풀이 방법: Genetic Algorithm

 

<그림 1>

유전 알고리즘은 자연계의 생물 유전학에 기본 이론을 두며, 전역적인 탐색 알고리즘으로서, 다윈의 적자생존 이론을 기본 개념으로 합니다. 유전 알고리즘은 풀고자 하는 문제에 대한 가능한 해들을 정해진 형태의 자료구조로 표현한 다음, 이들을 점차적으로 변형함으로써 점점 더 좋은 해들을 만들어 냅니다. 유전알고리즘의 단계는 순서대로 1) chromosome design, 2) Initialization, 3) Fitness evaluation, 4) Selection, 5) Crossover, 6) Mutation, 7) Update generation, 8) go back to 3 로 나타낼 수 있습니다. 

<그림1>에서는 1),2)번의 1)chromosome(염색체) 설계 단계와 2)초기화 단계가 생략되어 있습니다. 이후 좌측 하단에 나타난 것처럼 3)Fitness evaluation을 수행합니다. 얼마나 찾고자 하는 해에 적합한지를 평가하는 것입니다. 이후에4)selection단계를 수행합니다. 어떤 부모세대를 통해 자녀 세대를 선택할지를 정합니다. 그 이후에 5)cross-over와6)mutation을 거쳐서 7)update generation을 합니다. 이 작업을 8)반복하면 원하는 답에 가까워 지게 됩니다. 이제 이를 문제에 적용시켜서 풀어보도록 하겠습니다.

 

[ 본론 ] 

앞서 소개한 genetic-algorithm을 문제에 적용시키기 위해서는 genetic algorithm의 step에 따라 문제를 정의할 필요가 있습니다. 따라서 step1. chromosome design 에서 시작해서 step8. go back to step3까지 어떤 방식으로 문제를 풀었는지 소개하도록 하겠습니다. 

 

2.1     Chromosome design

 

제일 먼저 염색체 조직인 chromosome을 어떻게 정의할 것인지 생각해야 합니다. 아래 그림을 보면 5x5 matrix위에 5queens의 solution중 하나의 모습이 있습니다. 결국 이 5 x 5 matrix가 한chromosome이 되어야 하는데 5x5행렬 전체를 chromosome 유닛으로 만드는 것 보다 1x5 행렬로 5x5 matrix에 위치한 queen을 표현할 수 있습니다.

이처럼 matrix위에 놓인 queen의 위치를, 1x5의 matrix위에 높이 값으로 근사해서 표현할 수 있습니다. 또한 한 칼럼에 한 queen만 배치하게 되므로 자연히 같은 열에 또다른 queen이 놓이는 것을 방지할 수 있습니다. 따라서 chromosome의 디자인은 각 원소의 값이 1~5의 값으로 이루어진1 x 5 matrix가 됩니다.  

2.2     Initialization

다음은 Initialization입니다. Chromosome을 1x5 matrix로 설계하였으며, 저는 첫 generation의 chromosome 개수를 100개로 설정하였습니다. Random하게 구성한 100개의 chromosome을 가지고 genetic algorithm에 적용시킵니다. 그중 10개의 chromosome을 랜덤으로 표시한 화면은 아래와 같습니다. (python파일 결과 화면 캡쳐)

 2.3     Fitness evaluation

  100개의 chromosome을 만든 다음에는 각각의 chromosome이 문제와 얼마나 부합하는지를 평가해야 합니다. 이를 위해서는 evaluation function을 정의할 필요가 있는데, 저는 ‘chromosome에서 각 퀸을 짚어가면서 발생 가능한 충돌의 횟수’로 정의하였습니다. 예를 들어 <그림 2>의 chromosome의 evaluation 값은 그림과 같습니다.

<그림 3>

목적은 evaluation-function값인 collision값을 최소화 해서 충돌 횟수가 적은 상위 10개(rank 1~ rank10)을 뽑아내는 것입니다. 처음에 chromosome을 설계할 때 같은 열의 collision은 막았기 때문에 같은 행에서의 충돌 횟수와, 같은 대각선에서의 충돌 횟수, 두가지 경우로 나누어 (행-충돌 횟수) + (대각선-충돌 횟수) 가 최종 fitness value가 됩니다. 

따라서 [ 2 , 2, 3 , 2 , 3 ]의evaluation값은 7이 됩니다. 

이와 같은 작업을 통해 만약에 충돌 값이 0인 경우는 solution이므로 해당 chromosome을 출력합니다. 아닐 경우에는 다음 세대를 만들기 위해 step 4로 넘어갑니다. 

2.4     Selection

Step3. Fitness evaluation에서 collision이 0인 값이 나오지 않았다면 상위 10개의 chromosome을 선택합니다. 이때 선택의 기준은 evaluation function값으로 하며, 저는 collision의 횟수가 evaluation function값이고, 충돌 횟수가 적으면 적을수록 solution에 가깝기 때문에 collision값이 작은 순서대로 10개를 선택하게 합니다.

 

2.5     Crossover

 Selection 단계가 끝나면 다음은 cross-over입니다. Chromosome의 일부를 다른 chromosome의 일부와 바꿔 치기 해주는 작업입니다. 원소가 5개 이므로, 앞의 원소 2개는 남겨두고 뒤의 원소 3개를 각각 다른chromosome의 원소3개와 교환하도록 하겠습니다

이런 방식으로 <그림 4>에cross-over 를 수행하면 다음과 같다.

 

Cross over 단계에서는 다음 step인 mutation에 본래 selection에서 넘어온 본래 10개의 chromosome과, cross-over한 10개를 더해 20개의 chromosome을 넘기도록 하겠습니다.

2.6     Mutation

Step.6 mutation 단계에서는 cross-over한 결과물 20개를 가지고 mutation 작업을 수행합니다. 말그대로 변이를 만드는 것이며 일정 확률(저의 경우 50%의 확률로 1개 염색체 변이)로 변이가 일어나게 코드를 작성하였습니다. 변이는 다음과 같이 다양한 형태로 만들 수 있습니다. 이 중에서 저는 chromosome의 원소2개를 random하게 선택하여 서로 바꿔 치기를 하는 swap mutation을 수행하였습니다.  

Mutation 출처 : https://www.tutorialspoint.com/genetic_algorithms/genetic_algorithms_mutation.htm

2.7     Update generation 

Mutation작업을 수행하면 cross over에서 넘어온 20개의 chromosome중에서 1개의 염색체가 50%의 확률로 변이가 일어납니다. 이 작업을 5번을 반복해서 결과물을 한곳에 모으면 총 100개의 chromosome이 완성됩니다. 100개의 chromosome을 모은 이유는 초기에 100개로 시작한 부모 세대와 수를 맞추기 위함입니다. 

2.8     Go back to step 3

결과적으로 100개의 새로운 generation이 만들어 지면 이를 다시 3번 스텝으로 돌아가 100개의 chromosome에 대한 evaluation을 진행하고, 나온 결과값을 통해 solution이 있다면 도출하고, 없는 경우 다시 step4.로 넘어갑니다.

 

[결론]

결론적으로는 10개의 답안을 모두 구할 수 있었으며, 한번에 10개를 구하는 것은 시간이 오래걸려 과제 제출 양식에 맞게 프로그램을 실행시킬 경우 10개중 하나의 답을 구해 랜덤으로 표시하도록 수정하였습니다. 아래 그림의 경우, 답인 [ 1, 3 , 5, 2 , 4 ]가 3번째 세대 만에 나타났으며 다른 답안의 경우 더 많은 세대가 걸리는 경우도 있었습니다.

python library인 numpy와 matplotlib를 통해 그림으로 나타내었습니다. 

< 제출한 코드 내용 >

#  ----------------------
#     < 머신러닝 및 응용 >
#
#     과제명 : 5-Queens
#     교수님 : 송길태 교수님
#     작성자 : 이승엽
#     학 번 : 201445825
#     작성일 : 2020.04.11
#  ----------------------

import matplotlib.pyplot as plt
import numpy as np
import random


# step 1. chromosome design 은 1x5 matrix
def chromosome_design():
    print("===== 1) Chromosome design =========\n")
    print("          1 x 5 matrix           ")
    print("     | 5 | 2 | 3 | 1 | 3 |      \n")

    print("5 -> | o |   |   |   |   |      ")
    print("4 -> |   |   |   |   |   |      ")
    print("3 -> |   |   | o |   | o |      ")
    print("2 -> |   | o |   |   |   |      ")
    print("1 -> |   |   |   | o |   |      ")

    print()


# step 2. 처음 100개 chromosome 초기
def make_unit_chromosome():
    return [random.randint(1, 5) for _ in range(5)]


def initialization():
    print("===== 2) initialization ============\n")
    first_100 = [make_unit_chromosome() for _ in range(100)]
    print("top 10 in first 100:\n")
    for u in range(0, 10):
        print("       {}".format(first_100[u]))

    print()
    return first_100


# step 3. Fitness evaluation, step 4. selection
def unit_collision_check(unit):
    horizon_collision = sum([unit.count(pos) - 1 for pos in unit]) / 2
    diagonal_collision = 0
    index = 0
    for pos in range(0, 4):
        for j in range(1, 5-pos):
            if abs(unit[pos] - unit[pos + j]) == j:  # 다음원소와 차이가 1인경우 대각선 충돌이므로 +1
                diagonal_collision += 1

    return int(horizon_collision + diagonal_collision)


def fitness_evaluation(chromosome_list):
    print("===== 3) Fitness evaluation =========\n")

    for unit in chromosome_list:  # 결과값 print
        print("unit : {},  collision : {}"
              .format(str(unit), str(unit_collision_check(unit))))

    selected = []
    chromosome_list.sort(key=lambda x: unit_collision_check(x))

    print()
    print("===== 4) selection ===================\n")
    print("top 10:")
    for i in range(0, 10):  # 상위 10개값 저장
        selected.append(chromosome_list[i])
        print("unit : {},  collision : {}"
              .format(str(selected[i]), str(unit_collision_check(selected[i]))))
    print()
    return selected


# step 5. Cross-over
def cross_over(ranked_list):  # 원래 입력받은 10개 + cross over 한 10개를 반환한다.

    cross_over_list = []
    for i in range(0, 5):
        cross_up = []
        cross_down = []
        key_list_up = ranked_list[i*2]
        key_list_down = ranked_list[i*2+1]

        for j in range(0, 2):
            cross_up.append(key_list_up[j])
            cross_down.append(key_list_down[j])

        for k in range(2, 5):
            cross_down.append(key_list_up[k])
            cross_up.append(key_list_down[k])

        cross_over_list.append(cross_up)
        cross_over_list.append(cross_down)

    print("===== 5) cross-over ===================\n")
    print("cross-over:")
    for i in range(0, 10):  # 상위 10개값 저장
        print("unit : {},  collision : {}"
              .format(str(cross_over_list[i]), str(unit_collision_check(cross_over_list[i]))))
    print()

    print("original:")
    for i in range(0, 10):  # 상위 10개값 저장
        print("unit : {},  collision : {}"
              .format(str(ranked_list[i]), str(unit_collision_check(ranked_list[i]))))
        cross_over_list.append(ranked_list[i])
    print()

    print("total:")
    for i in range(0, 20):  # 상위 10개값 저장
        print("unit : {},  collision : {}"
              .format(str(cross_over_list[i]), str(unit_collision_check(cross_over_list[i]))))
    print()

    return cross_over_list


# step 6. Mutation
def make_random_swap(input_list):
    key_head = random.randint(0, 4)
    key_end = random.randint(0, 4)
    tmp = input_list[key_head]
    input_list[key_head] = input_list[key_end]
    input_list[key_end] = tmp

    return input_list


def mutation(un_mutated_list):
    key_value = random.randint(1, 100)
    which_chromosome = random.randint(0, 19)

    if (key_value % 2) == 0:  # 50%의 확률로
        make_random_swap(un_mutated_list[which_chromosome])
        print("mutation!")

    print()
    return un_mutated_list


# step 7. Update Generation
def update_generation(to_be_mutation_list):

    print("===== 6) cross-over + 7) update generation =====\n")
    total_list = []
    for i in range(0, 5):
        tmp_list = mutation(to_be_mutation_list)
        for j in range(0, 20):
            total_list.append(tmp_list[j])

    print("total list:")
    for i in range(0, 100):  # 상위 10개값 저장
        print("unit : {},  collision : {}"
              .format(str(total_list[i]), str(unit_collision_check(total_list[i]))))

    print()
    return total_list


# numpy 로 array 형식으로 변환
def change_into_array(list_form):

    array_form = []
    pos_1 = [1, 0, 0, 0, 0]
    pos_2 = [0, 1, 0, 0, 0]
    pos_3 = [0, 0, 1, 0, 0]
    pos_4 = [0, 0, 0, 1, 0]
    pos_5 = [0, 0, 0, 0, 1]

    for i in range(0, 5):
        if list_form[i] == 1:
            array_form.append(pos_1)
        elif list_form[i] == 2:
            array_form.append(pos_2)
        elif list_form[i] == 3:
            array_form.append(pos_3)
        elif list_form[i] == 4:
            array_form.append(pos_4)
        else:
            array_form.append(pos_5)

    return np.array(array_form)


if __name__ == "__main__":

    chromosome_design()
    population = initialization()

    total_answer_list = []
    answer_list = []
    check_collision = 1
    # while len(total_answer_list) < 10: # 10개의 답안을 전부 찾고자 하는 경우

    generation_no = 1
    while len(total_answer_list) < 1:  # 1개만 찾는 경우
        print("========== generation {} =========\n".format(generation_no))
        selected_list = fitness_evaluation(population)
        crossed_list = cross_over(selected_list)
        new_population = update_generation(crossed_list)
        new_population.sort(key=lambda x: unit_collision_check(x))
        generation_no += 1
        answer_list = new_population[0]

        check_collision = unit_collision_check(new_population[0])
        if answer_list not in total_answer_list:
            if check_collision == 0:
                total_answer_list.append(answer_list)

        print("best chromosome : {}".format(answer_list))
        print("present generation no : {}".format(generation_no))
        print()

    print("========== total answer list ===========")
    for answer in total_answer_list:
        print(answer)  # 전체 답안 출력

    print("  왼쪽에서 바라보시면 됩니다.  ")
    answer_array = change_into_array(total_answer_list[0])

    print(answer_array)
    plt.imshow(answer_array, cmap='binary')
    plt.savefig('answer.png')
    plt.show()