개요
일반적인 프로그래밍 기법으로 해결이 힘든 복잡한 문제의 경우, 합리적인 시간 내에서 최적의 답을 제시하기란 쉽지 않다. 이 때 유전 알고리즘을 사용할 수 있다.
유전 알고리즘은 적합한 개체가 살아남는 자연 선택natural selection의 매커니즘과 유사하게 동작한다. 예를 들어, 추운 지방에 서식하는 생물은 긴 털과 두꺼운 피하지방과 같이 열을 보존할 수 있는 수단이 필수적이다. 그렇지 않은 개체는 혹독한 추위에 적응하지 못할 것이고, 세대가 교체될수록 점차 감소하다 끝내 사라질 것이다. 일정한 시간이 흐른 뒤에 남은 개체는 그 환경에 충분히 적합하다고 할 수 있다. 물론 그것이 완벽한 종의 탄생을 의미하지는 않는다. 그 환경에 최적화된 생명체를 얻기 위해서는 더 많은 세대가 진행되어야 하며, 그 과정에서 어느 정도 운에 의지한다. 게다가 그 생명체가 최적의 솔루션이라는 보장도 없다.
문제를 풀 시간이 한정적이고, 꼭 최적이 아니더라도 충분히 좋은 솔루션만으로도 괜찮다면 유전 알고리즘을 적용할 수 있다.
제네릭
유전 알고리즘의 전개
1. 생성
세로운 새대를 시작한다. 각 세대는 무작위 성질을 가진 염색체로 이루어진 집단이다.
2. 측정
적합도가 특정 임곗값을 넘었을 경우 알고리즘을 종료한다.
3. 선택
재생산을 위해 가장 높은 적합도를 가질 확률이 높은 개체(부모)를 선택한다.
-
룰렛휠 선택
개체 리스트에서 무작위로 개체를 둘 선택한다.
높은 적합도를 가진 개체일수록 선택될 가능성이 높다.
-
토너먼트 선택
개체 리스트에서 무작위로 개체를 n개 선택하고, 그 중 가장 높은 적합도를 가진 개체를 둘 선택한다.
4. 크로스오버
일정 확률로 선택된 염색체를 결합한다. 따라서 두 부모 개체의 성질이 섞인 개체가 탄생한다.
5. 돌연변이
일정 확률로 일부 염색체가 변이한다.
모든 과정이 끝나면 새로 생성된 개체들은 기존의 세대를 대체하고, 다시 측정 단계로 돌아가 반복한다.
Chromosome 클래스
문제의 유형에 따라 적합도, 개체 생성 방식, 크로스오버 방식, 돌연변이 방식이 다를 수 있다. 재정의가 필요하므로 추상 클래스를 사용해 구현한다.
chromosome.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from __future__ import annotations
from typing import TypeVar, Tuple, Type
from abc import ABC, abstractmethod
# 타입이 T인 변수는 Chromoosome 클래스의 인스턴스 혹은 서브클래스여야 한다.
T = TypeVar("T", bound="Chromosome")
class Chromosome(ABC):
@abstractmethod
def fitness(self) -> float:
...
@classmethod
@abstractmethod
def random_instance(cls:Type[T]) -> T:
...
@abstractmethod
def crossover(self:T, other:T) -> Tuple[T, T]:
...
@abstractmethod
def mutate(self) -> None:
...
Note
파이썬에서는 데코레이터 @staticmethod를 사용해 정적 메서드를 구현할 수 있다. random_instance는 클래스에 접근하기 때문에 대신 @classmethod를 사용한다.
GeneticAlgorithm 클래스
genetic_algorithm.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
from __future__ import annotations
from typing import Type, TypeVar, Generic, List, Tuple, Callable
from enum import Enum
from random import choices, random
from heapq import nlargest
from statistics import mean
from chromosome import Chromosome
# 즉 타입 C는 Chromosome의 메서드를 갖는다.
C = TypeVar("C", bound=Chromosome)
class GeneticAlgorithm(Generic[C]):
SelectionType = Enum("SelectionType", "ROULETTE TOURNAMENT")
def __init__(self,
initial_population:List[C],
threshold:float,
max_generations:int = 100,
mutation_chance:float = 0.01,
crossover_chance:float = 0.7,
selection_type:SelectionType = SelectionType.TOURNAMENT) -> None:
self._population:List[C] = initial_population
self._threshold:float = threshold
self._max_generations:int = max_generations
self._mutation_chance:float = mutation_chance
self._crossover_chance:float = crossover_chance
self._selection_type:GeneticAlgorithm.SelectionType = selection_type
self._fitness_key:Callable = type(self._population[0]).fitness
def _pick_roulette(self, wheel:List[float]) -> Tuple[C, C]:
return tuple(choices(self._population, weights=wheel, k=2))
def _pick_tournament(self, num_participants:int) -> Tuple[C, C]:
participants:List[C] = choices(self._population, k=num_participants)
return tuple(nlargest(2, participants, key=self._fitness_key))
def _reproduce_and_replace(self) -> None:
new_population:List[C] = []
while len(new_population) < len(self._population):
# 부모 선택
if self._selection_type == GeneticAlgorithm.SelectionType.ROULETTE:
parents:Tuple[C, C] = self._pick_roulette(
[x.fitness() for x in self._population]
)
else:
parents = self._pick_tournament(
len(self._population) // 2
)
# 크로스오버
if random() < self._crossover_chance:
new_population.extend(parents[0].crossover(parents[1]))
else:
new_population.extend(parents)
if len(new_population) > len(self._population):
new_population.pop()
self._population = new_population
def _mutate(self) -> None:
for individudal in self._population:
if random() < self._mutation_chance:
individudal.mutate()
def run(self) -> C:
best:C = max(self._population, key=self._fitness_key)
for generation in range(self._max_generations):
if best.fitness() >= self._threshold:
return best
print(f"세대 {generation} 최상 {best.fitness()} 평균 {mean(map(self._fitness_key, self._population))}")
self._reproduce_and_replace()
self._mutate()
highest:C = max(self._population, key=self._fitness_key)
if highest.fitness() > best.fitness():
best = highest
return best
각 메서드의 기능은 다음과 같다.
-
pick_roulette와 pick_tournament
각각 룰렛휠 선택과 토너먼트 선택으로, 문제에서 사용하는 선택 방식에 따라 호출된다.
-
reproduce_and_replace
선택 방식에 따라 결정한 두 부모 개체를 바탕으로 새로운 개체를 생성하며, 이 때 일정 확률로 크로스오버가 발생한다.
모든 세대 집단의 개체 수는 동일해야 한다. 선택 방식을 거쳐 생성되는 개체 수는 항상 짝수이므로, 만약 이전 세대 집단의 개체 수가 홀수라면 개체 수를 조절해야 한다.
-
mutate
생성된 개체는 일정 확률로 돌연변이가 발생한다.
-
run
첫 세대 생성 후, 임곗값을 넘는 적합도가 나올 때까지 측정 -> 선택 -> 크로스오버 -> 돌연변이 과정을 반복한다.
적용
간단한 방정식
- 방정식 $6x - x^2 + 4y - y^2$이 최댓값이 되는 $x$와 $y$를 구하라.
미적분을 사용한 해결
수학적으로 접근하면 편미분partial derivative을 사용해 해결할 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
import sympy as sp
x, y, z = sp.symbols("x y z")
f = 6*x - x**2 + 4*y - y**2
df_dx = sp.diff(f, x) # 변수 x에 대해 편미분
df_dy = sp.diff(f, y) # 변수 y에 대해 편미분
max_x = sp.solve(df_dx, x)
max_y = sp.solve(df_dy, y)
print("x =", *max_x) # 3
print("y =", *max_y) # 2
주어진 식에 x와 y의 값을 대입하면 최댓값은 13이다.
유전 알고리즘을 사용한 해결
simple_equation.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
from __future__ import annotations
from typing import Tuple, List
from chromosome import Chromosome
from genetic_algorithm import GeneticAlgorithm
from random import randrange, random
from copy import deepcopy
class SimpleEquation(Chromosome):
def __init__(self, x:int, y:int) -> None:
self.x:int = x
self.y:int = y
def fitness(self) -> float:
return (6 * self.x) - (self.x * self.x) + (4 * self.y) - (self.y * self.y)
@classmethod
def random_instance(cls) -> SimpleEquation:
return SimpleEquation(randrange(100), randrange(100))
def crossover(self, other:SimpleEquation) -> Tuple[SimpleEquation, SimpleEquation]:
child1:SimpleEquation = deepcopy(self)
child2:SimpleEquation = deepcopy(other)
child1.y = other.y
child2.y = self.y
return child1, child2 # y를 서로 바꾼다.
def mutate(self) -> None:
if random() > 0.5:
if random() > 0.5:
self.x += 1
else:
self.x -= 1
else:
if random() > 0.5:
self.y += 1
else:
self.y -= 1
def __repr__(self) -> str:
return f"X: {self.x} Y: {self.y} 적합도: {self.fitness()}"
| 필드 / 메서드 | 설명 |
|---|---|
| property | x, y |
| fitness | 최댓값 |
| random_instance | x, y는 각각 [0, 100)의 무작위 정수 |
| crossover | 생성된 두 개체의 y를 서로 바꾼다. |
| mutate | x 또는 y의 값이 1만큼 변한다(증가 또는 감소). |
문제의 적합도는 앞서 구한 값(13)을 사용한다.
simple_equation.py
1
2
3
4
5
6
7
8
9
10
11
if __name__ == "__main__":
initial_population:List[SimpleEquation] =\
[SimpleEquation.random_instance() for _ in range(20)]
ga:GeneticAlgorithm[SimpleEquation] =\
GeneticAlgorithm(initial_population=initial_population,
threshold=13.0,
max_generations=100,
mutation_chance=0.1,
crossover_chance=0.7)
result:SimpleEquation = ga.run()
print(result)
실행 결과
1
2
3
4
5
6
7
8
세대 0 최상 -320 평균 -4415.25
세대 1 최상 -312 평균 -1161.4
세대 2 최상 3 평균 -360.85
세대 3 최상 8 평균 -185.6
세대 4 최상 9 평균 -41.15
세대 5 최상 11 평균 8.5
세대 6 최상 12 평균 10
X: 3 Y: 2 적합도: 13
미적분을 사용한 해결과 동일한 결과를 얻을 수 있다.
SEND+MORE=MONEY
복면산 퍼즐은 제약 충족 문제로 해결한 적 있다.
send_more_money2.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
from __future__ import annotations
from typing import Tuple, List
from chromosome import Chromosome
from genetic_algorithm import GeneticAlgorithm
from random import shuffle, sample
from copy import deepcopy
class SendMoreMoney2(Chromosome):
def __init__(self, letters:List[str]) -> None:
self.letters:List[str] = letters
def fitness(self) -> float:
s:int = self.letters.index("S")
e:int = self.letters.index("E")
n:int = self.letters.index("N")
d:int = self.letters.index("D")
m:int = self.letters.index("M")
o:int = self.letters.index("O")
r:int = self.letters.index("R")
y:int = self.letters.index("Y")
send:int = s * 1000 + e * 100 + n * 10 + d
more:int = m * 1000 + o * 100 + r * 10 + e
money:int = m * 10000 + o * 1000 + n * 100 + e * 10 + y
difference:int = abs(money - (send + more))
return 1 / (difference + 1)
@classmethod
def random_instance(cls) -> SendMoreMoney2:
letters = ["S", "E", "N", "D", "M", "O", "R", "Y", " ", " "]
shuffle(letters)
return SendMoreMoney2(letters)
def crossover(self, other:SendMoreMoney2) -> Tuple[SendMoreMoney2, SendMoreMoney2]:
child1:SendMoreMoney2 = deepcopy(self)
child2:SendMoreMoney2 = deepcopy(other)
idx1, idx2 = sample(range(len(self.letters)), k=2)
l1, l2 = child1.letters[idx1], child2.letters[idx2]
child1.letters[child1.letters.index(l2)], child1.letters[idx2] = child1.letters[idx2], l2
child2.letters[child2.letters.index(l1)], child2.letters[idx1] = child2.letters[idx1], l1
return child1, child2
def mutate(self) -> None:
idx1, idx2 = sample(range(len(self.letters)), k=2)
self.letters[idx1], self.letters[idx2] = self.letters[idx2], self.letters[idx1]
def __repr__(self) -> str:
s:int = self.letters.index("S")
e:int = self.letters.index("E")
n:int = self.letters.index("N")
d:int = self.letters.index("D")
m:int = self.letters.index("M")
o:int = self.letters.index("O")
r:int = self.letters.index("R")
y:int = self.letters.index("Y")
send:int = s * 1000 + e * 100 + n * 10 + d
more:int = m * 1000 + o * 100 + r * 10 + e
money:int = m * 10000 + o * 1000 + n * 100 + e * 10 + y
difference:int = abs(money - (send + more))
return f"{send} + {more} = {money} 차이: {difference}"
| 필드 / 메서드 | 설명 |
|---|---|
| property | 문자 리스트 |
| fitness | SEND+MORE=MONEY를 만족 |
| random_instance | 각 문자는 한 자리 자연수 |
| crossover | 생성된 두 개체의 특정 문자의 위치(값)을 교환한다. |
| mutate | 개체 내에서 서로 다른 두 문자의 위치를 교환한다. |
send_more_money2.py
1
2
3
4
5
6
7
8
9
10
11
12
if __name__ == "__main__":
initial_population:List[SendMoreMoney2] =\
[SendMoreMoney2.random_instance() for _ in range(1000)]
ga:GeneticAlgorithm[SendMoreMoney2] =\
GeneticAlgorithm(initial_population=initial_population,
threshold=1.0,
max_generations=1000,
mutation_chance=0.2,
crossover_chance=0.7,
selection_type=GeneticAlgorithm.SelectionType.ROULETTE)
result:SendMoreMoney2 = ga.run()
print(result)
실행 결과
1
2
세대 0 최상 0.0136986301369863 평균 0.00013098383168095023
9567 + 1085 = 10652 차이: 0
리스트 압축
list_compression.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
from __future__ import annotations
from genericpath import getsize
from typing import Tuple, List, Any
from chromosome import Chromosome
from genetic_algorithm import GeneticAlgorithm
from random import shuffle, sample
from copy import deepcopy
from zlib import compress
from sys import getsizeof
from pickle import dumps
PEOPLE:List[str] = ["Michael", "Sarah", "Joshua", "Narine",
"David", "Sajid", "Melanie", "Daniel",
"Wei", "Dean", "brian", "Murat", "Lisa"]
class ListCompression(Chromosome):
def __init__(self, lst:List[Any]) -> None:
self.lst:List[Any] = lst
@property
def bytes_compressed(self) -> int:
return getsizeof(compress(dumps(self.lst)))
def fitness(self) -> float:
return 1 / self.bytes_compressed
@classmethod
def random_instance(cls) -> ListCompression:
mylst:List[str] = deepcopy(PEOPLE)
shuffle(mylst)
return ListCompression(mylst)
def crossover(self, other:ListCompression) -> Tuple[ListCompression, ListCompression]:
child1:ListCompression = deepcopy(self)
child2:ListCompression = deepcopy(other)
idx1, idx2 = sample(range(len(self.lst)), k=2)
l1, l2 = child1.lst[idx1], child2.lst[idx2]
child1.lst[child1.lst.index(l2)], child1.lst[idx2] = child1.lst[idx2], l2
child2.lst[child2.lst.index(l1)], child2.lst[idx1] = child2.lst[idx1], l1
return child1, child2
def mutate(self) -> None:
idx1, idx2 = sample(range(len(self.lst)), k=2)
self.lst[idx1], self.lst[idx2] = self.lst[idx2], self.lst[idx1]
def __repr__(self) -> str:
return f"순서: {self.lst} 바이트: {self.bytes_compressed}"
| 필드 / 메서드 | 설명 |
|---|---|
| property | 문자열 리스트 |
| fitness | 결정할 수 없음 |
| random_instance | 무작위 순서의 배열 |
| crossover | 생성된 두 개체의 특정 문자열의 위치를 교환한다. |
| mutate | 개체 내에서 서로 다른 두 문자열의 위치를 교환한다. |
유전 알고리즘만으로는 결과값이 실제로 최적의 솔루션인지 판별할 수는 없으며, 검증 과정도 방정식 문제에 비해 훨씬 복잡하다. 다만 모든 세대 중 가장 높은 압축률을 보이는 개체는 분명 존재할 것이고, 그 압축률을 만족시키는 문자열의 순서는 충분히 좋은 솔루션이라고 할 수 있다.
list_compression.py
1
2
3
4
5
6
7
8
9
10
11
12
if __name__ == "__main__":
initial_population:List[ListCompression] =\
[ListCompression.random_instance() for _ in range(100)]
ga:GeneticAlgorithm[ListCompression] =\
GeneticAlgorithm(initial_population=initial_population,
threshold=1.0,
max_generations=100,
mutation_chance=0.2,
crossover_chance=0.7,
selection_type=GeneticAlgorithm.SelectionType.TOURNAMENT)
result:ListCompression = ga.run()
print(result)
실행 결과
1
2
3
4
5
6
7
세대 0 최상 0.007142857142857143 평균 0.0069900226798442185
세대 1 최상 0.007194244604316547 평균 0.007101651591274427
...
세대 98 최상 0.0072992700729927005 평균 0.007279016258480505
세대 99 최상 0.0072992700729927005 평균 0.007283553494608659
순서: ['brian', 'Dean', 'Lisa', 'Joshua', 'Melanie', 'Narine', 'Daniel', 'Michael', 'Wei', 'Murat', 'David', 'Sajid', 'Sarah']
바이트: 137
연습문제
📝 5-1
체감 확률diminishing probability을 기반으로 두 번째 혹은 세 번째로 가장 좋은 염색체를 선택할 수 있는 고급 토너먼트 선택 유형을 GeneticAlgorithm 클래스에 추가하라.
genetic_algorithm.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
...
class GeneticAlgorithm(Generic[C]):
SelectionType = Enum("SelectionType", "ROULETTE TOURNAMENT ADVANCED")
...
def _pick_advanced(self, num_participants:int, rate:float) -> Tuple[C, C]:
participants:List[C] = choices(self._population, k=num_participants)
candidates:Tuple[C] = tuple(nlargest(3, participants, key=self._fitness_key))
if random() > rate:
return (candidates[0], candidates[1]) # 1순위 & 2순위
elif random() > rate:
return (candidates[0], candidates[2]) # 1순위 & 3순위
else:
return (candidates[1], candidates[2]) # 2순위 & 3순위
def _reproduce_and_replace(self) -> None:
new_population:List[C] = []
while len(new_population) < len(self._population):
# 부모 선택
if self._selection_type == GeneticAlgorithm.SelectionType.ROULETTE:
parents:Tuple[C, C] = self._pick_roulette(
[x.fitness() for x in self._population]
)
elif self._selection_type == GeneticAlgorithm.SelectionType.TOURNAMENT:
parents = self._pick_tournament(
len(self._population) // 2
)
else:
parents = self._pick_advanced(
len(self._population), 0.5
)
# 크로스오버
if random() < self._crossover_chance:
new_population.extend(parents[0].crossover(parents[1]))
else:
new_population.extend(parents)
if len(new_population) > len(self._population):
new_population.pop()
self._population = new_population
...
_pick_advanced 메서드는 기존의 토너먼트 유형에서, 비율을 나타내는 rate 인자를 추가로 받는다. 만약 rate의 값이 0.5라면 50%의 확률로 1순위, 2순위의 개체가 선택된다. 남은 확률 중 다시 50%의 확률로 1순위, 3순위의 개체가 선택되며, 나머지는 2순위, 3순위의 몫이다.
rate가 0.5일 경우 선택 확률은 각각 50%, 25%, 25%이지만, 더 높은 수치인 0.7일 경우 각각 70%, 21%, 9%로 차이가 벌어진다. rate의 수치가 높을수록 다양성이 감소하며, 1.0일 경우엔 토너먼트 유형과 동일한 역할을 수행한다.
SelectionType에 ADVANCED 유형을 추가 및 _reproduce_and_replace에 메서드 호출을 추가한다.
이제 추가된 유형으로 간단한 방정식 문제를 해결할 수 있다.
simple_equation.py
1
2
3
4
5
6
7
8
9
10
11
12
if __name__ == "__main__":
initial_population:List[SimpleEquation] =\
[SimpleEquation.random_instance() for _ in range(20)]
ga:GeneticAlgorithm[SimpleEquation] =\
GeneticAlgorithm(initial_population=initial_population,
threshold=13.0,
max_generations=100,
mutation_chance=0.1,
crossover_chance=0.7,
selection_type=GeneticAlgorithm.SelectionType.ADVANCED)
result:SimpleEquation = ga.run()
print(result)
📝 5-2
3장의 제약 충족 문제 프레임워크에 유전 알고리즘을 사용하여 임의의 제약 충족 문제를 해결하는 새로운 메서드를 추가하라.
적합도의 가능한 측정은 염색체에 의해 해결되는 제약 조건의 수다.
여덟 퀸 문제를 유전 알고리즘으로 해결한다.
Practice question 5-2.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
from __future__ import annotations
from typing import Tuple, List, Set
from chromosome import Chromosome
from genetic_algorithm import GeneticAlgorithm
from random import shuffle, sample, randrange, random
from copy import deepcopy
class Queen(Chromosome):
def __init__(self, rows:List[int], cols:List[int]) -> None:
self.rows:List[int] = rows
self.cols:List[int] = cols
def fitness(self) -> float:
# 퀸 중복 X
count = 0
for i in range(8):
for j in range(8):
if abs(self.rows[i] - self.rows[j]) != abs(self.cols[i] - self.cols[j]):
count += 1
return count
@classmethod
def random_instance(cls) -> Queen:
rows = [1, 2, 3, 4, 5, 6, 7, 8] # 퀸 1 ~ 8 의 행
cols = [1, 2, 3, 4, 5, 6, 7, 8] # 퀸 1 ~ 8 의 열
shuffle(rows)
shuffle(cols)
return Queen(rows, cols)
def crossover(self, other:Queen) -> Tuple[Queen, Queen]:
child1:Queen = deepcopy(self)
child2:Queen = deepcopy(other)
idx1, idx2 = sample(range(len(self.rows)), k=2)
l1, l2 = child1.rows[idx1], child2.rows[idx2]
child1.rows[child1.rows.index(l2)], child1.rows[idx2] = child1.rows[idx2], l2
child2.rows[child2.rows.index(l1)], child2.rows[idx1] = child2.rows[idx1], l1
return child1, child2
def mutate(self) -> None:
idx1, idx2 = sample(range(len(self.rows)), k=2)
if random() > 0.5:
self.rows[idx1], self.rows[idx2] = self.rows[idx2], self.rows[idx1]
else:
self.cols[idx1], self.cols[idx2] = self.cols[idx2], self.cols[idx1]
def __repr__(self) -> str:
lst = []
for i in range(8):
lst.append((self.rows[i], self.cols[i]))
result = ""
for r in range(1, 9):
for c in range(1, 9):
if (r, c) in lst:
result += "■ "
else:
result += "□ "
result += "\n"
return result
| 필드 / 메서드 | 설명 |
|---|---|
| property | 각 퀸이 위치하는 행, 열 좌표 |
| fitness | 모든 퀸은 같은 열, 행, 대각선에 위치하지 않음 |
| random_instance | 각 퀸이 위치하는 무작위 체스 좌표 |
| crossover | 생성된 두 개체의 특정 좌표를 교환한다. |
| mutate | 개체 내에서 서로 다른 두 좌표를 교환한다. |
퀸의 행과 열을 저장하는 두 리스트에서 중복되는 값이 없으므로, 두 퀸은 같은 행, 열에 위치하지 않는다. 따라서 같은 대각선에 위치하는 조건만 검사하면 된다. 총 8 * 7 = 56의 비교를 수행하며, 모든 비교에서 조건을 만족하면 적합하다고 할 수 있다.
Practice question 5-2.py
1
2
3
4
5
6
7
8
9
10
11
if __name__ == "__main__":
initial_population:List[Queen] =\
[Queen.random_instance() for _ in range(20)]
ga:GeneticAlgorithm[Queen] =\
GeneticAlgorithm(initial_population=initial_population,
threshold=56.0,
max_generations=1000,
mutation_chance=0.1,
crossover_chance=0.7)
result:Queen = ga.run()
print(result)
실행 결과
1
2
3
4
5
6
7
8
9
10
11
12
13
세대 0 최상 52 평균 45.2
세대 1 최상 52 평균 49.2
세대 2 최상 54 평균 50.1
세대 3 최상 54 평균 51.4
세대 4 최상 54 평균 52.9
□ □ □ ■ □ □ □ □
□ □ □ □ □ □ ■ □
□ □ ■ □ □ □ □ □
□ □ □ □ □ □ □ ■
□ ■ □ □ □ □ □ □
□ □ □ □ ■ □ □ □
■ □ □ □ □ □ □ □
□ □ □ □ □ ■ □ □
(실제로는 적합한 값을 찾아내기까지 걸리는 세대 수의 편차가 크게 나왔다)
📝 5-3
Chromosome 클래스를 상속받는 BitString 클래스를 생성하라. 비트 문자열에 대해서는 1장을 참조한다.
그리고 새로 생성한 클래스를 사용하여 5.3절 ‘간단한 방정식’ 문제를 해결하라. 문제를 어떻게 비트 문자열로 인코딩할 수 있을까?