GA (Genetic Algorithm)

개인적 해석

• 최적의 해를 찾는 알고리즘이라고 생각함 Ex. Cost 최소화, 이익 최대화
• GA가 정확하고, 최적의 값을 찾기 위해서는 모델의 정당성, 신뢰도가 확보되어야 함
  • 부모 염색체가 정확하지 않은 값이라면 당연히 자손 염색체도 좋은 결과 값이 나올 수 없다고 생각함
• Fitness function을 얼마나 창의적으로 설계하느냐가 GA의 핵심이라는 생각이 듦

의미

• 최적의 해를 구하는 방법론인 GA라고 불리는 유전 알고리즘
• 지도학습, 비지도학습이라고 오해할 수 있지만 GA는 모델의 종류가 아닌 파라미터의 최적화 문제를 풀기 위한 일종의 방법

개념 정의

• 염색체(Chromosome) : 여러개의 유전자를 담고 있는 하나의 집합을 의미한다. GA에서는 하나의 해(파라미터)를 표현한다.
• 유전자(Gene) : 염색체를 구성하고 있는 요소로서, 하나의 유전 정보를 나타낸다. 예를 들어, 하나의 특정한 염색체가 [A,B,C,D] 라고 정의된다면 해당 염색체의 유전자는 A,B,C,D로 4개의 유전자가 존재한다.
• 자손(Offspring) : 특정 시간(t)에 존재했던 염색체들(예를 들어, A,B 두 개의 염색체가 있다고 가정.)로부터 생성된 새로운 염색체들(C,D라고 가정.)이다. 즉 C,D 는 A,B 염색체들의 자손이라고 할 수 있다. 자손 염색체는 부모 염색체의 비슷한 유전 정보를 갖는다.
• 정확도(Fitness) : 특정한 염색체가 갖고 있는 고윳값으로서, 특정한 염색체가 표현하는 해(파라미터)가 해결하려는 문제에 대해 얼마나 적합한지를 나타낸다.

연산정의

초기에 어떠한 문제에 적용하기 위해서 총 5개의 연산을 정의해야함.

• 초기 염색체를 생성하는 연산
  • 최초의 염색체를 생성하기 위해서는 이전의 염색체가 존재하지 않기 때문에 최초의 염색체를 생성하는 연산을 따로 정의해주어야 한다. GA에서 가장 많이 이용되는 방법은 규칙 없이 임의의 값으로 초기 염색체를 생성하는 것이다.
• 적합도를 계산하는 연산
  • 염색체에 표현된 정보를 토대로 적합도를 계산하는 연산이다. 이 연산은 해결하려는 문제에 따라 달라진다.
• 적합도를 기준으로 염색체를 선택하는 연산
  • 자손 염색체를 생성할 때 흔히 적합도가 가장 높은 염색체들을 선택하는 것이 최고의 방법이라고 생각할 수 있다. 하지만 이러한 방법은 염색체의 다양성을 손상시키기 때문에 Global optimum을 찾기에는 부적합하다. 이러한 문제를 피하기 위해서 GA에서는 룰렛 휠 선택(Roulette Wheel Selection) 방법을 이용한다. 룰렛 휠 선택이란, 우리가 흔히 생각하는 원판을 돌리면서 확률에 기반해 결과가 도출되는 룰렛의 개념과 비슷하다고 생각하면 된다. 밑의 그림은 룰렛 휠 선택에 대한 확률적 수식이며 다음 그림은 수식을 룰렛 그림으로 나타낸 그림이다. 룰렛 그림에서 면적의 총 합은 1(100%)이다. 왜냐하면 각각이 확률값이며 확률의 합은 1이기 때문이다.
• 선택된 염색체들로부터 자손을 생성하는 연산
  • 방금 언급했던 룰렛 휠 선택 방법으로 선정된 두 개의 부모 염색체들로부터 하나의 자손 염색체를 생성한다. 이 때 GA에서는 자손 염색체를 생성하는 연산으로서 주로 Crossover이라는 연산을 사용한다. Crossover 연산에 대해 그림으로 설명하자면 다음과 같다.

• 돌연변이 (mutation) 연산
  • 룰렛 휠 선택을 통해 Crossover 연산만을 사용한다면 Local optimum에 빠지는 문제를 발생시킬 수 있다. 이러한 문제를 피하기 위해서 자손 염색체에 돌연변이 연산을 추가적으로 적용하는 방법이 있다.
  • 보통은 0.1%나 0.05%등의 아주 낮은 확률로 돌연변이가 발생하도록 한다.

알고리즘 구조

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

1. 초기 염색체의 집합 생성
2. 초기 염색체들에 대한 적합도 계산
3. 현재 염색체들로부터 자손들을 생성
4. 생성된 자손들의 적합도 계산
5. 종료 조건 판별

6-1) 종료 조건이 거짓인 경우, (3)으로 이동하여 반복

6-2) 종료 조건이 참인 경우, 알고리즘을 종료

Fitness Function 

• 일반적으로 지도학습을 사용하는 분류 작업의 경우 유클리드 거리 및 맨해튼 거리와 같은 오류 측정이 피트니스 함수로 널리 알려져서 사용되어 왔음.
• 최적화 문제의 경우 문제 영역과 관련된 계산, 매개 변수 집합의 합과 같은 기본기능을 피트니스 함수로 사용할 수 있음

# array	                                    commands	                      return
#[1, 5, 2, 6, 3, 7, 4]	        [[2, 5, 3], [4, 4, 1], [1, 7, 3]]	         [5, 6, 3]


array = [1,5,2,6,3,7,4]
commands = [[2,5,3],[4,4,1],[1,7,3]]


def solution(array, commands):
    answer = []

    for i in range(len(commands)) :
        temp = array[commands[i][0]-1 : commands[i][1]]
        #print(temp)
        sort = sorted(temp)
        #print(sort)
        answer.append(sort[commands[i][2]-1])
        
    return answer

비교적 쉬웠던 문제였던 것 같다. 숫자를 정렬하고 자릿수만 잘 찾아서 배열안에 있는 값을 뽑아주면 해결되는 문제였다.

#    phone_book	                            return
# ["119", "97674223", "1195524421"]	         false
# ["123","456","789"]	                     true
# ["12","123","1235","567","88"]	         false


phone_book = ["119", "97674223", "1195524421"]

def solution(phone_book):
    for i in range(1,len(phone_book)) :    
        if phone_book[i].find(phone_book[0]) != -1 :
            return False
    return True
    
    
print(solution(phone_book))

find 함수를 이용해서 풀어 보았는데 위에 예시로 나온 세개의 문제는 해결 됐는데 확장성이 없었고, 효율성도 떨어졌다. find 함수 이외의 방법을 좀 더 연구해 봐야겠다는 생각을 하였고, 아직 내 수준이 한참 못미친다는 것도 인지하는 문제였던 것 같다.

#  수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
#  마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때,
#  완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

#participant	                                       completion	                             return
#["leo", "kiki", "eden"]	                         ["eden", "kiki"]	                         "leo"
#["marina", "josipa", "nikola", "vinko", "filipa"]	 ["josipa", "filipa", "marina", "nikola"]	"vinko"
#["mislav", "stanko", "mislav", "ana"]               ["stanko", "ana", "mislav"]	             "mislav"

왼쪽 참가자와 오른쪽 완주자를 보고 참가자 중에 완주하지 못한 사람을 찾는 알고리즘을 완성시켜야 한다.

participant = ["mislav", "stanko", "mislav", "ana"]
completion = ["stanko", "ana", "mislav"]

print(participant[-1])

def solution(participant, completion):
    participant.sort()
    completion.sort()
    for i in range(len(completion)) :
        if participant[i] != completion[i] :
            return participant[i]

    return participant[-1]



print(solution(participant, completion))

mislav

두 배열을 먼저 정렬시키고 배열을 비교해 가며 참가자 배열에서 완주자 배열에 없는 값들을 찾아내는 방식으로 해결하였다. 프로그래머스 Level 1 수준의 알고리즘이라 아직 할만 하다고 생각했는데, Level2 부터는 막히는 부분이 자주 있었다.