유전 알고리즘(간단, 정석 예제)

[알고리즘] 유전 알고리즘

개념적인 내용이 잘 정리되어 있다.

 

결국 유전 알고리즘이란, 유전자가 유전되는 특성(변이, 교배 연산)들을 본따서 만들어진 알고리즘으로, 최적화 문제를 해결하는 전역 최적화 기법(시간이 길더라도 전체 탐색영역에서 가장 좋은 해를 찾는 것)이다.

 

유전 알고리즘은 특정한 문제를 풀기 위한 알고리즘이라고 보기 보다는 문제를 풀기 위한 접근방법에 가까우며, 유전 알고리즘에서 사용할 수 있는 형식으로 바꾸어 표현할 수 있는 모든 문제에 대해 적용할 수 있다.

 

 

 

유전 알고리즘을 활용하기 위한 요구 조건

• 해를 유전자(gene)의 형식으로 표현할 수 있어야 한다.
• 해가 얼마나 적합한지를 적합도 함수를 통해 계산할 수 있어야 한다.
  • 적합도 함수 : 해가 얼마나 문제의 답으로 적합한지를 평가하기 위한 함수

 

 

구조

유전 알고리즘은 t에 존재하는 염색체들의 집합으로부터 적합도가 가장 좋은 염색체를 선택하고, 선택된 해의 방향으로 검색을 반복하면서 최적해를 찾아가는 구조로 동작한다. 유전 알고리즘의 동작을 단계별로 표현하면 아래와 같다.

1. 초기 염색체의 집합 생성
2. 초기 염색체들에 대한 적합도 계산
3. 현재 염색체들로부터 자손들을 생성
4. 생성된 자손들의 적합도 계산
5. 종료 조건 판별
   1. 종료 조건이 거짓인 경우, (3)으로 이동하여 반복
   2. 종료 조건이 참인 경우 ,알고리즘을 종료

 

 

 

 

 

 

 

* 간단한 예제(비밀번호 맞추기)

 

파이썬 유전알고리즘 예시 (비밀번호 맞추기, 돌연변이만 사용)

 

import numpy as np

password=[4,8,8,5,8,5]

#1) generate
def generate(N) :
    parent=np.random.randint(10,size=N)
    return parent

#2) fitness
def fitness(chromosome) :
    score = []
    for i,j in zip(password,chromosome) :
        if i==j :
            score.append(1)
    return sum(score)

#3) mutate
def mutate(chromosome) :
    index=int(np.random.randint(low=0,high=len(chromosome),size=1))
    newgene, alternate = np.random.randint(10,size=2)
    if chromosome[index]!=newgene :
        chromosome[index]=newgene
    else :
        chromosome[index]=alternate
    return chromosome


#4) run
parent=generate(6)
parent_fitness=fitness(parent)

i=0

while True :
    child = mutate(parent)
    child_fitness=fitness(child)
    i=i+1
    if child_fitness <= parent_fitness:
        continue    
    print("child chrosome : ",child,"| child_fitness :",child_fitness,"| iter:",i)
    if child_fitness >= len(password) :
        break
    parent=child
    parent_fitness=child_fitness

 

[결과값]

child chrosome : [0 6 7 5 9 3] | child_fitness : 1 | iter: 2
child chrosome : [4 9 3 5 1 1] | child_fitness : 2 | iter: 29
child chrosome : [4 8 7 0 8 9] | child_fitness : 3 | iter: 426
child chrosome : [4 2 5 5 8 5] | child_fitness : 4 | iter: 4376
child chrosome : [4 8 8 5 8 9] | child_fitness : 5 | iter: 11906
child chrosome : [4 8 8 5 8 5] | child_fitness : 6 | iter: 324223

324223번 만에 비밀번호를 찾아낼 수 있었다.

 

 

여기서 잘 이해 안 간 코드 부분 해석

 

 

1. for문의 zip()함수

for i, j in zip(password, chromosome):

 

 

x = [1, 2, 3]
y = [a, b, c]


for n1, n2 in zip(x, y):

    print(n1, n2)

"""
결과
    1, a

    2, b

    3, c
         """

 

 

 

 

 

 

2. np.random.randint 함수

np.random.randint(low=0, high=len(chromosome), size=1)

 

np.random.randint는 예전의 방식으로 지정된 범위 내에서 무작위 정수를 생성합니다. 기존 코드와 호환되며, 오래된 프로젝트에서 널리 사용되었습니다.

numpy.random.randint(low, high=None, size=None, dtype=int)

low: 이 인수는 생성될 값의 범위에서 가장 작은 정수를 지정합니다. high도 지정된 경우, 이 인수는 범위의 포함하는 하한값을 나타냅니다.
high: 이 인수는 생성될 값의 범위에서 가장 큰 정수를 지정합니다. 이 인수가 지정되지 않은 경우, 범위의 상한값은 2^31-1(32비트 시스템에서) 또는 2^63-1(64비트 시스템에서)으로 지정됩니다.
size: 이 인수는 생성될 정수의 개수를 지정합니다. 이 인수는 정수 또는 정수의 튜플로 지정할 수 있습니다. 예를 들어, size=3은 1차원 배열로 3개의 정수를 생성하고, size=(2,3)은 2차원 배열로 2개의 행과 3개의 열을 가진 배열을 생성합니다.
dtype: 이 인수는 생성될 값의 데이터 유형을 지정합니다. 이 인수의 기본값은 int로 32비트 정수입니다. 다른 데이터 유형을 지정하려면 numpy 데이터 유형 중 하나를 사용해야 합니다.

(출처: https://wikidocs.net/193810)

 

 

 

 

 

 

 

 

 

 

* 정석적인 예제

 

유전 알고리즘

 

 

import numpy as np

def generate_intial_population(N):
  initial_population = np.random.randint(0,2,(N,2,5))
  return initial_population

def evaluate_fitness(solution):
  x1 = sum([2**(4-i)*solution[0][i] for i in range(5)])
  x2 = sum([2**(4-i)*solution[0][i] for i in range(5)])

  constraint_1 = (100*x1 + 50*x2) <= 3000
  constraint_2 = (10*x1) <= 100
  if constraint_1 and constraint_2:
    fitness_value = 100 * x1 + 40 * x2
  else:
    fitness_value = 0
  return fitness_value

# Move crossover function outside of evaluate_fitness
def crossover(solution1, solution2):
  crossover_point_1 = np.random.randint(1,4)  # random하게 골라진 수가 0또는 4라면 부모 유전자가 그대로 내려오는 것이므로
  crossover_point_2 = np.random.randint(1,4)

  child = np.empty((2,5))

  child[0][:crossover_point_1] = solution1[0][:crossover_point_1]
  child[0][crossover_point_1:] = solution2[0][crossover_point_1:]

  child[1][:crossover_point_2] = solution1[1][:crossover_point_2]
  child[1][crossover_point_2:] = solution2[1][crossover_point_2:]

  return child

def mutation(child,p): #p는 각 개체에서 돌연변이가 일어날 확률
  for row in range(2):
    for col in range(5):
      if np.random.random() < p:
        child[row, col] = 1- child[row, col]
  return child

num_iter = 10             # 세대 수
N = 20                    # 한 세대에 포함되는 해의 개수
N_P = 10                  # 부모 개수
mutation_sol_prob = 0.1   # 유전자(해)가 돌연변이일 확률
mutation_gene_prob = 0.2  # 유전 개체가 돌연변이일 확률

current_population = generate_intial_population(N)
best_score = -1  # 지금까지 찾은 최대 적합도 초기화 

for _ in range(num_iter-1):
  fitness_value_list = np.array([evaluate_fitness(solution) for solution in current_population])

  if fitness_value_list.max() > best_score:
    best_score = fitness_value_list.max()
    best_solution = current_population[fitness_value_list.argmax()]     # argmax는 최대 값이 있는 index를 반환

  parents = current_population[np.argsort(-fitness_value_list)]  # 적합도 기준 상위 N_P개 해 선정(값이 큰 순으로 정렬하기 위해 -를 붙임)

  new_population = parents  # 새로운 해 집단 정의

  for _ in range(N-N_P):   # 자식 생성
      # 부모 선택
      parent_1_idx, parent_2_idx = np.random.choice(N_P, 2, replace = False)
      parent_1 = parents[parent_1_idx]
      parent_2 = parents[parent_2_idx]

      # 자식 생성
      child = crossover(parent_1, parent_2)

      # mutation_sol_prob의 확률로 돌연변이 연산 수행
      if np.random.random() < mutation_sol_prob:
        child = mutation(child, mutation_gene_prob)

      new_population = np.vstack([new_population, child.reshape(1,2,5)])  # new_population에 child 추가(child 구조가 (2,5)라서 vstack이 안되므로, 구조를 변경)

 

 

 

print(best_score)
#1260
print(best_solution)
# [[0 1 0 0 1]
#  [0 1 1 0 0]]

 

 

 

+) Numpy의 hstack, vstack 메서드

=> 둘 다 ndarray 형식의 배열을 결합할 때 유용하게 사용되는 함수이다.

 

hstack의 h는 'horizontal'로, 수평이라는 뜻에서 알 수 있듯이 가로로 행렬 결합이 이루어진다.  vstack의 v는 'vertical'로 세로로 행렬결합이 이루어진다.

 

 

 

 

 

 

* 참고 자료

 

[수리적 최적화] 유전 알고리즘 (Genetic Algorithm)과 전역 최적화

 

 

np.random.default_rng()

 

 

[Python] 구조의 재배열, numpy.reshape 함수

 

유전자 알고리즘 실습

 

유전 알고리즘