유전 알고리즘 구현 소스 오류 디버깅

갑자기 소스를 고치다가, 돌려보니 진화가 올바르게 되지 않았다.

초반 (0~5) 세대 때 적합도가 잠깐 상승하더니, 그 이후에는 데이터가 그래프처럼 제자리 걸음을 반복했다.

아래 소스는 삽질을 반복한 소스이다. 당연한 부분에 오류가 있으니, 문제점을 찾아보자.

"""
Author Kcrong
"""
from random import randint as rand

from matplotlib.pyplot import plot, show, xlim, ylim, xlabel, ylabel
from numpy import mean


# 범위: x ~ y-1
def randint(x, y): return rand(x, y - 1)


# 원하는 값
WE_WANT = [1, 3, 2, 4, 1, 1, 1, 1]

# 우월 유전자 보존 갯수
GOOD_DNA_CNT = 10

# 돌연변이 확률은 fitness 와 반비례 한다.
# fitness 가 높을 수록, 돌연변이 확률이 적어진다.
MUTATION_PROBABILITY = 100  # 작을 수록 확률이 커짐


def integer_list_random(list_data: list, count: int = 1):
    """
    :param count: 반환할 데이터 갯수
    :param list_data: Integer list
    :return: 리스트의 무작위 데이터 리스트
    """
    return [list_data[randint(0, len(list_data))] for _ in range(count)]


class Generation:
    _cnt = 0

    def __init__(self, dna_list):
        Generation._cnt += 1
        self.generation_level = Generation._cnt
        self.DNA_list = dna_list
        self.fitness_list = [dna.fitness for dna in self.DNA_list]
        self.select_list = self.make_select_list()

    def __repr__(self):
        return "<Generation level %d>" % self.generation_level

    def make_parents_list(self):
        """
        인자로 받은 fitness 값을 가지는 모든 DNA 를 반환하는 함수
        """

        # 랜덤으로 선정된 적합도 (적합도가 클 수록 선출될 확률도 크다)
        parents_fitness = integer_list_random(self.select_list, 2)

        # 선정된 적합도를 가진 모든 DNA 데이터 가져옴.
        # 예비 부모 DNA 리스트
        fitness_dna_list = [dna for dna in self.DNA_list if dna.fitness in parents_fitness]

        return fitness_dna_list

    def make_select_list(self):
        # fitness_list 에서 중복값을 제거
        fitness_types = set(self.fitness_list)

        select_list = list()

        for fitness in fitness_types:
            select_list += [fitness for _ in range(fitness)]

        return select_list

    def make_child(self):
        """
        :return: Child Gene Object
        """

        # 돌연변이 경우
        if randint(0, (self.fitness * MUTATION_PROBABILITY)) == 0:
            return DNA([randint(min(WE_WANT), max(WE_WANT)) for _ in range(len(WE_WANT))])

        # 부모를 select_list 를 이용해 정함.
        # 부모로 선출될 확률은 fitness 과 비례한다.

        # 부모 후보 리스트
        all_parent_list = self.make_parents_list()

        # 후보 리스트에서 랜덤으로 두 객체 뽑음

        parents = (all_parent_list[randint(0, len(all_parent_list))],
                   all_parent_list[randint(0, len(all_parent_list))])

        # 자식 유전자
        gene_data = list()

        # 유전자 정보 길이
        gene_len = len(parents[0].gene_data)

        # 각 교차 포인트를 정한다.
        # rand 함수의 반환이 float 형이므로, 소수점을 버리기 위해 int() 형변한을 해준다.
        switch_point = (randint(1, gene_len // 2), randint(gene_len // 2, gene_len))

        # 처음 자식이 받는 유전자는 parent1
        # 다만 교차 포인트에 다다르면, 다른 parent 유전자 정보를 받아오기 시작한다. (parent = parent2)
        parent = parents[0]

        for i in range(gene_len):
            # 자식 유전자 정보는 부모 유전자에서 받아온다
            gene_data.append(parent.gene_data[i])

            if i in switch_point:
                # 유전자를 받아오는 부모 변경
                try:
                    parent = parents[parents.index(parent) + 1]
                except IndexError:
                    parent = parents[0]

                """
                a = parents.index(parent) --> 현재 부모의 index 값
                parents[a+1] --> 부모 리스트에서, 현재 부모 인덱스값보다 +1 된 값 가져옴
                IndexError --> 만약 1이 넘어가면
                parent = parents[0] 다시 0으로 돌아옴
                """

        # return DNA(gene_data)
        dna = DNA(gene_data)
        return dna

    def evolution(self):
        print("Start Evolution Generation level %d" % Generation._cnt)

        best_dna = self.best

        dna_list = [best_dna for _ in range(GOOD_DNA_CNT)]
        dna_list += [self.make_child() for _ in range(len(self.DNA_list) - len(dna_list))]

        return Generation(dna_list)

    @property
    def fitness(self):
        # 세대 객체의 평균 적합도
        return mean([dna.fitness for dna in self.DNA_list])

    @property
    def best(self):
        return sorted(self.DNA_list, key=lambda x: x.fitness, reverse=True)[0]


class DNA:
    def __init__(self, gene_data=None):
        # 유전자 정보
        if gene_data is None:
            self.gene_data = [randint(min(WE_WANT), max(WE_WANT) + 1) for _ in range(len(WE_WANT))]
        else:
            self.gene_data = gene_data

    def __repr__(self):
        return "< Gene %s | %d >" % ("_".join(str(x) for x in self.gene_data), self.fitness)

    @staticmethod
    def max_fitness():
        if max(WE_WANT) < 2:
            return len(WE_WANT) * max(WE_WANT)
        else:
            return len(WE_WANT) * (max(WE_WANT) // 2)

    @property
    def fitness(self) -> int:
        """
        적합도 계산 함수
        :return: 적합도 값
        """

        score = len(WE_WANT) * (max(WE_WANT) // 2)

        for gene, want in zip(self.gene_data, WE_WANT):
            if gene != want:
                score -= abs(gene - want)

        return score


def visualization(generations):
    fitness_list = [generation.fitness for generation in generations]

    # 최대 적합도를 그래프에 나타냄
    max_fitness = DNA.max_fitness()
    plot([max_fitness for _ in range(len(generations))])

    xlim([0, len(generations)])

    # 축의 lim 값을 데이터 보다 높게 잡아줌으로써, 그래프의 가독성을 높임
    ylim([int(min(fitness_list)), (max_fitness * 1.2)])

    xlabel('Generation')
    ylabel('Fitness Score')

    # 각 세대의 (평균) 적합도를 이용해 그래프에 나타냄
    plot(fitness_list)

    show()


if __name__ == '__main__':
    Generations = list()

    # 첫 세대 (조상 세대)
    Generations.append(Generation([DNA() for _ in range(100)]))

    i = 0
    while True:
        try:
            next_generation = Generations[i].evolution()
            Generations.append(next_generation)
            print("Fitness: %0.2f" % next_generation.fitness)
            print("Best DNA: %s" % next_generation.best)

            # 적합도가 최대일 경우, 반복문 종료
            if next_generation.fitness >= DNA.max_fitness():
                break


        except KeyboardInterrupt:
            break

    print("Last Generation's Best DNA: %s" % Generations[-1].best)

    visualization(Generations)

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

while True:
    try:
        next_generation = Generations[i].evolution()
        Generations.append(next_generation)
        print("Fitness: %0.2f" % next_generation.fitness)
        print("Best DNA: %s" % next_generation.best)

        # 적합도가 최대일 경우, 반복문 종료
        if next_generation.fitness >= DNA.max_fitness():
            break


    except KeyboardInterrupt:
        break

while 문의 i 변수가 변하지 않는다.

그래프는 1세대에서 진화를 반복한 결과를 내보낸 것이었다.

문제가 된 커밋이다.

https://github.com/Kcrong/Simple-Genetic-Algorithm/commit/87000c1b8a0ffa33c0b54b4311ce073ca20db201

i 의 증감연산자 오류는 git reset --hard [Commit_ID] 를 통해 문제가 된 커밋을 찾으면서 해결하였다.

그것도 모르고 애꿎은 자식 생성 함수나 부모 선정 루틴만 만지고 있었다.

다행히 push 된 커밋에서 i 의 증가 연산 루틴만 넣어주니 잘 돌아가준다.

git commit 을 세분화 시킨 덕에 오류를 찾을 수 있었다. 기능 별 커밋의 중요성을 몸소 느꼈다.