Charles Darwin 유전 알고리즘은 찰스 다윈의 ‘자연 선택' 개념을 구현한 알고리즘 입니다. Show
진화과정이 계속적으로 아주 오랫동안 진행이 되면, 단세포에서 진화를 거듭하여 지금의 인류가 탄생했듯이 환경에 아주 잘 적응된 종이 나타날 수 있습니다. 유전 알고리즘1. begin유전 알고리즘은 개체들이 모인 집단에서 시작합니다. 각 개체(노드)는 1과 0에 의한 바이너리 형태(무조건은 아니지만 바이너리로 표현되는 것이 좋다고 합니다)로 표현이 됩니다. 이런 개체들이 집단을 형성하고 있습니다. 2. 적합도 계산적합도(fitness)는 주어진 환경에 얼마나 적합한지를 나타냅니다. 적합도를 구하는 함수는 환경에 따라 달라집니다. 3. selection상위 n%를 선택합니다. 적자생존의 원리에 따라 환경에 더 적합한 개체들이 살아남습니다. n의 값은 설계에 따라 달라집니다. 4. 유전 연산선택된 개체들은 유전 연산을 통해 후손을 생산합니다. 유전 연산에는 교배(crossover), 돌연변이(mutation)이 있습니다. 5. 반복새로운 집단이 형성되면 다시 앞의 과정들을 반복합니다. 반복은 목표로하는 적합도를 찾을 때 까지 혹은 특정 값의 이상을 찾을 때까지 반복합니다. Crossover, 교배DNA 염색체가 꼬여서 어머니의 유전 형질의 반, 아버지의 유전 형질의 반을 가지게 되는 것과 비슷한 원리입니다. Mutation 돌연변이돌연변이가 언제 나타날 지 알 수 없습니다. 약 0.04프로 확률로 돌연변이가 발생한다고 합니다. 문제에 따라서 돌연변이는 좋은 영향을 주기도 하고 나쁜 영향을 주기도 합니다. 돌연변이 연산은 종류가 매우 다양합니다. 위의 그림처럼 랜덤한 위치의 값이 바뀔 수도 있고, 특정한 위치의 값이 복제(duplication) 될 수도 있고, 삭제(deletion) 될 수도 있습니다. 또한 특정 위치 부터 특정 위치까지의 순서가 반대로 뒤집힐 수도(Inversion) 있고 두 개체의 특정 부분끼리 서로 스위칭(Translocation)되기도 합니다. 유전 알고리즘 활용 예영상은 그네 타는 법을 유전 알고리즘으로 해결하는 과정을 보여줍니다. programming GA기본적인 genetic algorithm 의 pseudo code 입니다. 이를 바탕으로 간단한 문제를 genetic algorithm으로 풀어보겠습니다. 예제 : 금괴 담기10kg을 담을 수 있는 가방이 있습니다. 다음과 같이 6개의 금괴가 존재할 때, 금괴들이 10kg을 넘지 않으면서 가장 값어치가 높도록 금괴들을 선택하여 가방에 담아야 합니다. 개체 : size 6인 배열. 각 인덱스는 금괴 번호, 배열의 값은 1( 해당 금괴를 선택 ) 또는 0 ( 해당 금괴를 선택하지 않음 ) 금괴에 해당하는 Gold 클래스와 개체에 해당하는 Chromosome 클래스를 생성했습니다. Chromosome의 sum은 선택한 금괴들의 총합이며, val는 값어치의 총합입니다. GAController는 적합도 계산, selection, 유전 연산을 수행하는 클래스 입니다.
최초의 집단을 생성하는 메서드 입니다. 개체의 각 값은 랜덤하게 선택하되 금괴들의 총합이 10이 넘지 않아야 합니다. mutation 연산은 전체 집단에서 랜덤하게 하나의 개체를 선택하여 해당 개체의 랜덤한 위치의 값을 변경합니다. crossover는 선택된 개체들을 대상으로 수행됩니다. 선택된 개체들의 모든 가능한 쌍을 crossover합니다. 가능한 두 쌍을 모두 구하기 위해 조합 (combination ) 알고리즘을 사용했습니다. crossover 할 두 크로모좀이 선택되면, 앞에서 부터 2개의 값을 서로 교환합니다. 만약 교환 했는데 sum이 10을 넘어간다면 그 다음 것을 교환합니다. 결과10번 정도 시도하면 7~8번 정도 정답을 찾아냅니다. 어떻게 하면 정확성을 더 높일 수 있을지 생각해보고 알고리즘을 수정해보면 좋을 것 같습니다. 2018-11-15 20:08:32 유전 알고리즘으로 엄마가 걸어놓은 비밀번호를 손쉽게 뚫어봅시다! 유전자 생성 - 유전자 평가 - 교배 - 진화 Source code(Github): https://github.com/kairess/password_cracker Dependencies:
|