정답도 기울기도 모를 때, 자연의 방법: 잘하는 놈을 골라(선택) 섞고(교배) 가끔 실수하게(변이) 두면 답이 진화합니다.
가로축은 세대, 세로축은 적합도(목표와 맞은 글자 수)예요. 초록 선은 세대별 최고 적합도, 회색 선은 인구 평균이에요. 초록 선이 점선(만점)에 닿으면 완성! 변이율이 0%면 어느 높이에서 딱 멈추고, 너무 높으면 만점 근처에서 요동치는 걸 볼 수 있어요.
2~30자. 바꾸면 처음부터 다시 진화해요.
적합도는 목표와 같은 위치에 같은 글자가 있는 개수예요. 최고 적합도가 글자 수와 같아지면 진화 완료!
import random
TARGET = "인공지능은 정말 재미있다!"
POOL = list(set(TARGET + "가나다라마바사아자차카타파하 !?.,")) # 목표 글자가 꼭 들어가야 해요
POP, MUT = 120, 0.03
def fitness(ind): # 적합도 = 위치가 맞는 글자 수
return sum(a == b for a, b in zip(ind, TARGET))
pop = ["".join(random.choices(POOL, k=len(TARGET))) for _ in range(POP)]
for gen in range(100000):
pop.sort(key=fitness, reverse=True) # ① 선택: 잘하는 순 정렬
if fitness(pop[0]) == len(TARGET): # 완성되면 종료
print(f"{gen}세대: {pop[0]}"); break
elite = pop[: POP // 4] # 상위 25%만 생존
children = list(elite)
while len(children) < POP: # ② 교배: 부모 둘 섞기
a, b = random.sample(elite, 2)
cut = random.randrange(1, len(TARGET))
children.append(a[:cut] + b[cut:])
pop = ["".join(random.choice(POOL) if random.random() < MUT else c
for c in ind) for ind in children] # ③ 변이: 가끔 실수