유전 알고리즘(Genetic Algorithm )

Genetic Algorithm

• 존 홀랜드(John Holland)가 1975년에 저서 "Adaptation on Natural and Artificial Systems" 에서 처음 소개한 최적화 기법
• 실제 생물 진화를 모방해서 문제를 해결하는 진화 연산의 대표적인 방법
• HyperParameter Search를 할 때도 여전히 유효하게 쓰이고 있는 방법
• "초기화 → 적합도 함수에 기반해서 적합한 유전자를 선별 → 해당 유전자를 바탕으로 후대 유전자 후보를 교배로 통해 생성 → 특정 확률로 변이 생성 → 현재 세대를 후대 유전자 세대로 교체"를 최적의 값이 나올 때까지 반복한다.

Implementation

• 이 알고리즘은 Target으로 하는 문자열을 생성하기 위해서 유전알고리즘을 활용한 사례이다.

Initialization

• 초기값으로 Target으로 하는 최종 결과값과, Population_size를 설정한다. Population Size를 크게 설정해도 되고 1로 설정해되 되지만, 이 부분은 결국 이 알고리즘의 반복횟수와 Trade Off를 가지기 때문에 적절히 설정할 필요가 있다.
• Mutation_rate는 변이가 발생할 확률이다. 변이는 일반적으로 부모에 존재하지 않았던 경우를 추가함으로써 탐색 공간을 넓히기 위해 넣는 연산이라고 보면 된다.

def __init__(self, target_string, population_size, mutation_rate):
        self.target = target_string
        self.population_size = population_size
        self.mutation_rate = mutation_rate
        self.letters = [" "] + list(string.ascii_letters)

Calculate Fitness Function

• 어떤 유전자가 살아남을 것인가를 판단하기 위한 적합도 함수(Fitness Function)이다.
• 여기서는 임의로 생성한 문자열과 목표 문자열의 Ascii Code를 비교하는 형태로 평가를 한다. 최종적으로 적합도는 1 / (loss + 1e-6)이기 때문에 정답에 가까울 수록 Fitness 값은 증가하게 된다. 그렇게 population의 각 유전자별로 Fitness를 평가한다.

def _calculate_fitness(self):
    """ Calculates the fitness of each individual in the population """
    population_fitness = []
    for individual in self.population:
        # Calculate loss as the alphabetical distance between
        # the characters in the individual and the target string
        loss = 0
        for i in range(len(individual)):
            letter_i1 = self.letters.index(individual[i])
            letter_i2 = self.letters.index(self.target[i])
            loss += abs(letter_i1 - letter_i2)
        fitness = 1 / (loss + 1e-6)
        population_fitness.append(fitness)
    return population_fitness

Mutate

• 해당 연산에서는 변이와 관련되어 각 유전자의 확률이 존재하지 않기 때문에 임의로 정의된 사전 확률과 np.random.random()으로 도출한 확률을 비교해서 변이 여부를 결정한다.

def _mutate(self, individual):
    """ Randomly change the individual's characters with probability
    self.mutation_rate """
    individual = list(individual)
    for j in range(len(individual)):
        # Make change with probability mutation_rate
        if np.random.random() < self.mutation_rate:
            individual[j] = np.random.choice(self.letters)
    # Return mutated individual as string
    return "".join(individual)

Crossover

• 교배는 살아남은 적합한 유전자를 대상으로 임의로 교배를 한다. np.random.randint()를 이용해서 유전자가 섞이는 비율을 임의로 설정한다.

def _crossover(self, parent1, parent2):
    """ Create children from parents by crossover """
    # Select random crossover point
    cross_i = np.random.randint(0, len(parent1))
    child1 = parent1[:cross_i] + parent2[cross_i:]
    child2 = parent2[:cross_i] + parent1[cross_i:]
    return child1, child2

Iteration

• 이제 여기가 중요한 부분이다. 앞서 언급한 모든 기능들이 세대를 거듭하면서 최적의 값에 도달하게 된다. 보면 반복 횟수(iteration)에 기준해서 Iteration을 돌면서 각 유전자의 fitness를 계산하고 이후에 가장 건강한 유전자를 선발한다.
• 그리고 Fitness에 기반해서 각 부모유전자별로 확률을 계산한 다음에 새로운 후대 Population을 생성하는데, 두개씩 유전자를 선별해서 이를 교배하고 교배한 유전자들을 새로운 Population으로 바꾼다. 이를 반복하면서 중간에 Target과 동일한 String 값을 찾게 되면 정지하게 된다.

def run(self, iterations):
    # Initialize new population
    self._initialize()

    for epoch in range(iterations):
        population_fitness = self._calculate_fitness()

        fittest_individual = self.population[np.argmax(population_fitness)]
        highest_fitness = max(population_fitness)

        # If we have found individual which matches the target => Done
        if fittest_individual == self.target:
            break

        # Set the probability that the individual should be selected as a parent
        # proportionate to the individual's fitness.
        parent_probabilities = [fitness / sum(population_fitness) for fitness in population_fitness]

        # Determine the next generation
        new_population = []
        for i in np.arange(0, self.population_size, 2):
            # Select two parents randomly according to probabilities
            parent1, parent2 = np.random.choice(self.population, size=2, p=parent_probabilities, replace=False)
            # Perform crossover to produce offspring
            child1, child2 = self._crossover(parent1, parent2)
            # Save mutated offspring for next generation
            new_population += [self._mutate(child1), self._mutate(child2)]

        print ("[%d Closest Candidate: '%s', Fitness: %.2f]" % (epoch, fittest_individual, highest_fitness))
        self.population = new_population

실행 결과

target_string = "Lee BongHo"
population_size = 100
mutation_rate = 0.05
genetic_algorithm = GeneticAlgorithm(target_string,
                                    population_size,
                                    mutation_rate)
                                    
genetic_algorithm.run(iterations=1000)

References

• ML From Scratch
• Holland, J.H. (1975), Adaptation on Natural and Artificial Systems, The University of Michigan Press, Ann Arbor.
• 유전 알고리즘의 연산자들