유전 알고리즘(GA)은 자연 선택 과정에서 영감을 받아 고품질의 해결책을 찾는 방법이다. 주로 최적화 문제를 해결하는 데 사용된다. 유전 알고리즘은 자연 선택의 생물학적 과정, 특히 선택(적합도), 교차, 뮤테이션 과정에 의존한다. 이 과정을 생물학적 관점에서 자세히 살펴보자:
생물학에서 선택이란 자연적 또는 인위적 통제 요인에 의해 특정 유전형(유전적 구성)을 가진 개체의 우선적인 생존과 번식, 또는 우선적 제거를 의미한다.
다시 말해, 적자생존을 뜻한다. 환경에 적응한 생물체는 더 많이 번식하는 경향이 있다. 유전 알고리즘(GA)에서는 적합도 모델을 생성해 개체의 순위를 매기고 더 나은 번식 기회를 제공한다.
염색체 교차(chromosomal crossover)는 생식 과정에서 상동 염색체 간에 유전 물질이 교환되어 재조합 염색체가 생성되는 현상을 말한다. Wikipedia
간단히 말해 생식 과정이다. 한 세대는 이전 세대의 혼합된 표현이며, 자손은 양쪽 부모로부터 DNA를 물려받는다. 유전 알고리즘(GA)은 이를 무작위적이지만 가중치를 두어 자손을 교배함으로써 새로운 세대를 생성한다.
뮤테이션은 생물체의 세포나 바이러스의 유전 물질(게놈)에 발생하는 영구적 변화를 의미한다. 이 변화는 세포나 바이러스의 후손에게 전달될 수 있다. 브리태니커
뮤테이션은 생물체가 시간이 지남에 따라 변화할 수 있도록 하는 무작위성을 제공한다. 유전 알고리즘(GA)에서는 개체군 내의 자손을 변이시켜 적합도 분산을 유도하는 무작위화 프로세스를 구축한다.
이 간단한 예제에서는 기본적인 유전 알고리즘을 사용해 최적화된 문자열을 생성한다. 구체적으로는 고정된 길이의 무작위로 생성된 원본 문자열을 선택한 최적의 문자열로 진화시키는 과정을 다룬다.
생물학적 영감을 받은 세계를 구축한다. 이 세계에서 절대적 존재는 Hello, World! 문자열이다. 이 우주에서 이보다 더 나은 것은 없으며, 생존을 위해 이 문자열에 최대한 가까워지는 것이 목표다.
핵심 프로세스를 알아보기 전에, 먼저 "우주"를 설정해야 한다. 우선 우리 우주에 존재하는 모든 것을 정의하는 어휘집을 만들어보자.
let lex: [UInt8] = " !\"#$%&\'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~".asciiArray더 쉽게 작업하기 위해 유니코드 값을 사용할 것이다. 이를 도와줄 String 확장을 정의해보자.
extension String {
var unicodeArray: [UInt8] {
return [UInt8](self.utf8)
}
}이제 우주를 위한 몇 가지 전역 변수를 정의해보자:
OPTIMAL: 최종 목표이며, 적합도를 평가하는 데 사용할 값이다. 실제 세계에서는 이 값이 존재하지 않는다.DNA_SIZE: 우리 집단에서 문자열의 길이이다. 유기체들이 서로 비슷해야 한다.POP_SIZE: 각 세대의 크기이다.MAX_GENERATIONS: 최대 세대 수이다. 최적값을 찾지 못하면 5000세대에서 스크립트가 중단된다.MUTATION_CHANCE: 무작위 뉴클레오타이드가 돌연변이를 일으킬 확률이다 (1/MUTATION_CHANCE).let OPTIMAL:[UInt8] = "Hello, World".unicodeArray
let DNA_SIZE = OPTIMAL.count
let POP_SIZE = 50
let GENERATIONS = 5000
let MUTATION_CHANCE = 100선택, 교차, 뮤테이션을 수행하기 전에 시작할 집단이 필요하다. 이제 우주를 정의했으니 해당 함수를 작성할 수 있다:
func randomPopulation(from lexicon: [UInt8], populationSize: Int, dnaSize: Int) -> [[UInt8]] {
guard lexicon.count > 1 else { return [] }
var pop = [[UInt8]]()
(0..<populationSize).forEach { _ in
var dna = [UInt8]()
(0..<dnaSize).forEach { _ in
let char = lexicon.randomElement()! // 초기 guard 문으로 nil이 아님을 보장
dna.append(char)
}
pop.append(dna)
}
return pop
}선택 과정은 두 부분으로 나뉜다. 첫 번째는 적합도를 계산하는 것으로, 각 개체에 점수를 부여한다. 이를 위해 유니코드 값을 사용해 개체가 최적 문자열에 얼마나 가까운지 계산한다:
func calculateFitness(dna: [UInt8], optimal: [UInt8]) -> Int {
guard dna.count == optimal.count else { return -1 }
var fitness = 0
for index in dna.indices {
fitness += abs(Int(dna[index]) - Int(optimal[index]))
}
return fitness
}위 함수는 개체의 적합도 값을 반환한다. "Hello, World"와 같은 완벽한 해답은 적합도가 0이다. "Gello, World"는 최적값과 한 글자 차이(H->G)이므로 적합도가 1이다.
이 예제는 매우 단순하지만, 설명에 충분하다. 실제 문제에서는 최적 해답을 알 수 없거나 불가능한 경우가 많다. 여기는 유명한 외판원 문제를 해결하기 위해 유전 알고리즘을 사용한 논문이다. 이 문제는 현대 컴퓨터로도 해결할 수 없지만, 이동 거리를 기준으로 개별 해답을 평가할 수 있다. 이 경우 최적 적합도는 0이지만, 이는 불가능하다. 해답이 0에 가까울수록 생존 확률이 높아진다. 이 예제에서는 목표인 적합도 0을 달성할 것이다.
선택 과정의 두 번째 부분은 가중치 선택, 또는 룰렛 휠 선택이다. 이는 현재 개체군에서 번식 과정에 참여할 개체를 선택하는 방법을 정의한다. 자연 선택에서 가장 적합한 개체가 항상 선택되는 것은 아니다. 개체가 절벽에서 떨어지거나, 이질에 걸리거나, 번식할 수 없는 상황에 처할 수도 있다.
왜 항상 가장 적합한 개체를 선택하지 않는지 잠시 생각해보자. 이 간단한 예제에서는 이해하기 어렵지만, 개 품종 개량을 생각해보자. 브리더는 이 과정을 생략하고 다음 세대를 위해 개를 직접 선택한다. 결과적으로 원하는 특성은 개선되지만, 그와 관련된 유전적 장애도 함께 전달된다. 특정 "진화 분기"가 현재 가장 적합한 해답을 나중에 능가할 수도 있다. 문제에 따라 괜찮을 수 있지만, 교육적 목적을 위해 생물학적 방식을 따를 것이다.
이를 바탕으로 가중치 선택 함수는 다음과 같다:
func weightedChoice(items: [(dna: [UInt8], weight: Double)]) -> (dna: [UInt8], weight: Double) {
let total = items.reduce(0) { $0 + $1.weight }
var n = Double.random(in: 0..<(total * 1000000)) / 1000000.0
for item in items {
if n < item.weight {
return item
}
n = n - item.weight
}
return items[1]
}위 함수는 계산된 적합도를 가진 개체 목록을 받아, 적합도 값을 기준으로 무작위로 하나를 선택한다. 1,000,000을 곱하고 나누는 부분은 소수점 계산을 정확하게 하기 위한 것이다. Double.random은 정수만 사용하므로, 정확한 Double 값으로 변환하기 위해 필요하다. 완벽하지는 않지만, 이 예제에서는 충분하다.
뮤테이션은 강력한 기능으로, 원래 존재하지 않던 적합성 차이를 만들어낸다. 이는 개체의 적합성을 떨어뜨리거나 향상시킬 수 있지만, 시간이 지남에 따라 더 적합한 개체군으로 진화를 이끈다. 초기 무작위 개체군에 H라는 문자가 누락된 상황을 가정해보자. 이 경우 최적의 해를 찾기 위해 뮤테이션을 통해 해당 문자를 개체군에 도입해야 한다.
func mutate(lexicon: [UInt8], dna: [UInt8], mutationChance: Int) -> [UInt8] {
var outputDna = dna
(0..<dna.count).forEach { i in
let rand = Int.random(in: 0..<mutationChance)
if rand == 1 {
outputDna[i] = lexicon.randomElement()!
}
}
return outputDna
}이 함수는 뮤테이션 확률과 개체를 받아, 뮤테이션이 발생한 개체를 반환한다. 이를 통해 개체군은 구성 요소의 모든 가능성을 탐색하고, 무작위로 더 나은 해결책을 발견할 수 있다. 뮤테이션이 너무 많으면 진화 과정이 제대로 진행되지 않는다. 반대로 너무 적으면 개체군이 너무 비슷해져 변화하는 환경에 적응하지 못한다.
크로스오버는 유전 알고리즘(GA)의 핵심 과정으로, 현재 세대에서 선택된 두 개체를 기반으로 새로운 후손을 생성한다. 부모 개체를 두 부분으로 나눈 후, 각 부모의 일부를 조합해 후손을 만든다. 다양성을 높이기 위해 부모를 나누는 지점을 무작위로 선택한다.
func crossover(dna1: [UInt8], dna2: [UInt8], dnaSize: Int) -> [UInt8] {
let pos = Int.random(in: 0..<dnaSize)
let dna1Index1 = dna1.index(dna1.startIndex, offsetBy: pos)
let dna2Index1 = dna2.index(dna2.startIndex, offsetBy: pos)
return [UInt8](dna1.prefix(upTo: dna1Index1) + dna2.suffix(from: dna2Index1))
}위 코드는 현재 세대를 기반으로 완전히 새로운 세대를 생성하는 데 사용된다.
이제 알고리즘을 시작하는 데 필요한 모든 함수를 갖췄다. 처음부터 시작해 보자. 먼저 시작점으로 사용할 무작위 개체군이 필요하다. 또한 가장 적합한 개체를 저장할 fittest 변수를 초기화한다. 이 변수는 무작위 개체군의 첫 번째 개체로 초기화한다.
var population:[[UInt8]] = randomPopulation(from: lex, populationSize: POP_SIZE, dnaSize: DNA_SIZE)
var fittest = population[0]이제 핵심 부분이다. 나머지 코드는 세대 루프에서 실행되며, 각 세대마다 한 번씩 실행된다:
for generation in 0...GENERATIONS {
// 실행
}이제 개체군의 각 개체에 대해 적합도와 가중치 값을 계산해야 한다. 0이 가장 좋은 값이므로 가중치를 나타내기 위해 1/fitness를 사용한다. 이 값은 퍼센트가 아니라 다른 값보다 선택될 가능성이 얼마나 더 높은지를 나타낸다. 만약 가장 높은 값이 가장 적합하다면, 가중치 계산은 fitness/totalFitness가 되며, 이는 퍼센트가 된다.
var weightedPopulation = [(dna:[UInt8], weight:Double)]()
for individual in population {
let fitnessValue = calculateFitness(dna: individual, optimal: OPTIMAL)
let pair = ( individual, fitnessValue == 0 ? 1.0 : 1.0/Double( fitnessValue ) )
weightedPopulation.append(pair)
}여기서 다음 세대를 구축할 수 있다.
var nextGeneration = []아래 루프는 모든 것을 종합하는 부분이다. POP_SIZE만큼 루프를 돌며, 가중치 선택으로 두 개체를 선택하고, 이들의 값을 교차시켜 자손을 생성한 후, 새로운 개체에 뮤테이션을 적용한다. 이 과정이 완료되면 이전 세대를 기반으로 완전히 새로운 세대가 생성된다.
0...POP_SIZE).forEach { _ in
let ind1 = weightedChoice(items: weightedPopulation)
let ind2 = weightedChoice(items: weightedPopulation)
let offspring = crossover(dna1: ind1.dna, dna2: ind2.dna, dnaSize: DNA_SIZE)
// 개체군에 추가하고 뮤테이션 적용
nextGeneration.append(mutate(lexicon: lex, dna: offspring, mutationChance: MUTATION_CHANCE))
}메인 루프의 마지막 부분은 개체군에서 가장 적합한 개체를 선택하는 것이다:
fittest = population[0]
var minFitness = calculateFitness(dna: fittest, optimal: OPTIMAL)
population.forEach { indv in
let indvFitness = calculateFitness(dna: indv, optimal: OPTIMAL)
if indvFitness < minFitness {
fittest = indv
minFitness = indvFitness
}
}
if minFitness == 0 { break; }
print("\(generation): \(String(bytes: fittest, encoding: .utf8)!)")가장 적합한 문자열을 찾았을 때 프로그램을 종료하기 위해 break를 추가했다. 루프 끝에서 가장 적합한 문자열을 출력한다:
print("fittest string: \(String(bytes: fittest, encoding: .utf8)!)")이제 프로그램을 실행할 수 있다! Playground는 개발하기 좋은 환경이지만, 이 프로그램을 매우 느리게 실행할 것이다. 터미널에서 실행하는 것을 강력히 권장한다: swift gen.swift. 실행하면 다음과 같은 결과를 볼 수 있으며, Hello, World를 얻는 데 너무 오래 걸리지 않아야 한다:
0: RXclh F HDko
1: DkyssjgElk];
2: TiM4u) DrKvZ
3: Dkysu) DrKvZ
4: -kysu) DrKvZ
5: Tlwsu) DrKvZ
6: Tlwsu) Drd}k
7: Tlwsu) Drd}k
8: Tlwsu) Drd}k
9: Tlwsu) Drd}k
10: G^csu) |zd}k
11: G^csu) |zdko
12: G^csu) |zdko
13: Dkysu) Drd}k
14: G^wsu) `rd}k
15: Dkysu) `rdko
16: Dkysu) `rdko
17: Glwsu) `rdko
18: TXysu) `rdkc
19: U^wsu) `rdko
20: G^wsu) `rdko
21: Glysu) `rdko
22: G^ysu) `rdko
23: G^ysu) `ryko
24: G^wsu) `rdko
25: G^wsu) `rdko
26: G^wsu) `rdko
...
1408: Hello, Wormd
1409: Hello, Wormd
1410: Hello, Wormd
1411: Hello, Wormd
1412: Hello, Wormd
1413: Hello, Wormd
1414: Hello, Wormd
1415: Hello, Wormd
1416: Hello, Wormd
1417: Hello, Wormd
1418: Hello, Wormd
1419: Hello, Wormd
1420: Hello, Wormd
1421: Hello, Wormd
1422: Hello, Wormd
1423: Hello, Wormd
1424: Hello, Wormd
1425: Hello, Wormd
1426: Hello, Wormd
1427: Hello, Wormd
1428: Hello, Wormd
1429: Hello, Wormd
1430: Hello, Wormd
1431: Hello, Wormd
1432: Hello, Wormd
1433: Hello, Wormd
1434: Hello, Wormd
1435: Hello, Wormd
fittest string: Hello, World
얼마나 걸릴지는 무작위성에 따라 다르지만, 거의 항상 5000 세대 이내에 완료된다. 우와!
우리는 간단한 유전 알고리즘을 성공적으로 구현했다. 이제 전역 변수인 POP_SIZE, OPTIMAL, MUTATION_CHANCE, GENERATIONS를 조절해 보며 실험해 보자. 단, 사전에 정의된 문자 집합에 있는 문자만 추가하거나 사전을 업데이트해야 한다.
예를 들어, 더 긴 문자열인 Ray Wenderlich's Swift Algorithm Club Rocks를 OPTIMAL에 입력하고 GENERATIONS를 10000으로 변경해 보자. 어느 정도 진전이 보이겠지만, 10,000 세대 내에 최적의 문자열에 도달하기는 어려울 것이다. 더 긴 문자열이므로 뮤테이션 확률을 200(1/2 확률로 뮤테이션)로 높여 보자. 완벽하게 도달하지 못할 수도 있지만, 이전보다는 훨씬 가까워질 것이다. 긴 문자열의 경우 뮤테이션이 너무 많으면 적합한 문자열이 생존하기 어려워진다. 이제 POP_SIZE를 늘리거나 GENERATIONS를 증가시켜 보자. 어느 쪽이든 결국 목표값에 도달하겠지만, 특정 크기의 문자열에 대한 "최적의 지점"이 존재할 것이다.
이 튜토리얼에 대한 업데이트나 추가 예제를 제출해 주면 감사하겠다!