OneMax 질문

원맥스 문제는 [0,1,1,0,1,0,1,1,1,0]처럼 0/1로 구성된 수열의 합을 극대화하는 문제를 말한다.가장 큰 목표는 모든 요소가 1이 되는 것이다.
이번에는 OneMax 문제를 유전 알고리즘으로 해결한다.

유전 알고리즘

유전 알고리즘은 생물의 진화 과정을 모방하여 만든 알고리즘 중 확률 탐색 방법 중의 하나다.교차와 갑작스런 변이를 반복하여 개체를 진화시키다.
기본 절차는 다음과 같다.

선택 항목

부개체를 선택하여 차세대 개체를 생성하다.
부모 개체의 선택 방법은 다음과 같은 몇 가지가 있다.
휠 모드
- 랭킹 방식
- 엘리트 방식

엇갈리다

선택한 부개체를 교차시켜 자개체를 생성한다.
교차 방법은 다음과 같습니다.
- 균일 교차
엇갈리다
- 다중 교차

돌변하다

생성된 개체에 대해 돌연변이를 진행하다.

실천하다

그럼 실제 GA로 OneMax 문제를 해결한다.
실험의 설정은
유전인자 길이:100
세대수:100
선택:토너먼트 선택(토너먼트 크기:2)
교차
돌연변이 확률: 1/유전인자 길이
부모 개체 수: 100
하위 개수: 50
개체 갱신: 부개체의 우량 개체 50+자개체

# -*- coding: utf-8 -*-
import random
import copy

# 各種パラメータ
length = 100  # 遺伝子長
population = 100  # 親個体数
offspring_n = 50    # 子個体数
generation = 100     # 世代数
mutation_rate = 1.0/100.0    # 突然変異確率(1/遺伝子長)

# 初期個体群生成
def initialize():
    gene = [[random.randint(0,1) for i in range(length)] for j in range(population)]
    return gene

# 個体評価
def evaluate(gene):
    fitness = []
    for i in range(population):
        fitness.append(sum(gene[i])/length)
    return fitness

# minを見つける
def find_min(fitness):
    min = 10
    for i in range(population):
        if fitness[i] < min:
            min = fitness[i]
    return min

# maxを見つける
def find_max(fitness):
    max = 0
    for i in range(population):
        if fitness[i] > max:
            max = fitness[i]
    return max

# 親選択
def choice_parents(gene, fitness):
    father_index = random.randint(0,population-1)
    mother_index = random.randint(0,population-1)
    if fitness[father_index] > fitness[mother_index]:
        parents = gene[father_index]
    else:
        parents = gene[mother_index]
    return parents

# 交叉
def crossover(father, mother):
    offspring = []
    for i in range(length):
        p = random.random()
        if p < 0.5:
            offspring.append(father[i])
        else:
            offspring.append(mother[i])
    return offspring

# 突然変異
def mutation(offspring):
    for i in range(length):
        p = random.random()
        if p < mutation_rate:
            if offspring[i] == 0:
                offspring[i] = 1
            else:
                offspring[i] = 0
    return offspring

# 個体更新(親個体エリート50 + 子個体50 = 計100)
def elite(gene, fitness, next_gene):
    sort_fitness = sorted(fitness, reverse=True)
    gen_tmp = []
    for i in range(int(population/2)):
        index = fitness.index(sort_fitness[i])
        gen_tmp.append(gene[index])
    gen_tmp.extend(next_gene)
    return gen_tmp

def main():
    generation_count = 1
    next_gene = []

    # 初期個体群生成
    gene = initialize()

    while generation_count <= generation:
        next_gene.clear()
        #print(gene)
        # 個体評価
        fitness = evaluate(gene)
        min = find_min(fitness)
        max = find_max(fitness)
        print("generation:", generation_count)
        print("min", min)
        print("max", max)
        if min == 100:
            break
        # 次世代個体群生成
        for i in range(offspring_n):
            # 個体選択
            father = choice_parents(gene, fitness)
            mother = choice_parents(gene, fitness)
            # 交叉
            offspring = crossover(father, mother)
            # 突然変異
            offspring = mutation(offspring)
            next_gene.append(offspring)
        # 個体更新
        gene = elite(gene, fitness, next_gene)
        generation_count += 1
        print("--------------------------------")

if __name__ == "__main__":
    main()

결과는 다음과 같다.
1세대 민,max는 모두 저가입니다.
최종 세대 max가 최대치에 이르렀고min도 큰 값을 얻었다.
유전 알고리즘도 개체가 진화하고 있음을 증명했다.

generation: 1
min 0.37
max 0.62
--------------------------------
generation: 2
min 0.39
max 0.63
--------------------------------

.
.
.

generation: 99
min 0.96
max 1.0
--------------------------------
generation: 100
min 0.95
max 1.0
--------------------------------