에듀테크 프로젝트 대시보드
유전 알고리즘 (Genetic Algorithm)
정답을 모르는 문제에서 "좋은 답"을 찾고 싶다. 그런데 후보가 너무 많아 전부 시도할 수는 없다.
자연은 이 문제를 진화로 풀었다 — 여러 개체를 만들고, 환경에 잘 맞는 놈을 더 많이 남기고,
자손에게 부모의 특징을 섞어(교차) 물려주되 가끔 실수(돌연변이)를 낸다.
이 과정을 반복하면 세대가 지날수록 집단 전체가 점점 나은 방향으로 이동한다.
아래 데모는 무작위 문자열 집단이 목표 문장 METHINKS IT IS LIKE A WEASEL 로
진화하는 과정을 보여준다 (리처드 도킨스의 1986년 사고 실험).
각 개체가 얼마나 좋은지 점수를 매긴다. 여기서는 목표 문장과 같은 위치에 같은 글자가 몇 개인지 센다.
부모를 고른다. 토너먼트 선택: 무작위로 k명을 뽑아 그중 가장 점수가 높은 개체를 부모로 삼는다. k가 클수록 엘리트 편향이 세진다.
두 부모의 유전자를 한 지점에서 잘라 앞·뒤를 이어 붙여 자식을 만든다. 좋은 조각끼리 결합될 기회를 준다.
자식의 각 글자를 낮은 확률로 무작위 글자로 바꾼다. 집단이 한 곳에 갇히는(조기 수렴) 것을 막는 탐험 장치.
새 자식들로 집단을 교체한다. 단, 역대 최고 개체 1명은 그대로 보존(엘리티즘)해 성능이 뒷걸음치지 않게 한다.
def evolve(target, pop_size=200, mut=0.03, k=5): pop = [random_string(len(target)) for _ in range(pop_size)] gen = 0 while best(pop) != target: scored = [(fitness(s, target), s) for s in pop] # 1) 평가 elite = max(scored)[1] nxt = [elite] # 5) 엘리트 보존 while len(nxt) < pop_size: p1 = tournament(scored, k) # 2) 선택 p2 = tournament(scored, k) c = crossover(p1, p2) # 3) 교차 c = mutate(c, mut) # 4) 돌연변이 nxt.append(c) pop = nxt gen += 1 return gen def fitness(s, target): return sum(a == b for a, b in zip(s, target)) def crossover(a, b): p = random.randint(1, len(a) - 1) return a[:p] + b[p:]
| 상황 | 유전 알고리즘 | 경사 하강법 |
|---|---|---|
| 탐색 공간 | 이산·조합·불연속도 OK | 연속·미분 가능해야 유리 |
| 기울기 정보 | 필요 없음 (점수만 있으면 됨) | 기울기 필수 |
| 지역 최적 | 집단+돌연변이로 탈출 시도 | 쉽게 갇힘 |
| 비용 | 평가를 수천~수만 번 (느림) | 보통 훨씬 빠름 |
| 대표 용도 | 스케줄링, 회로·안테나 설계, 하이퍼파라미터 탐색, 게임 AI | 신경망 학습, 회귀 |
유전 알고리즘은 메타휴리스틱이다 — 정답을 보장하지 않지만, 문제 구조를 거의 몰라도 "그럭저럭 좋은 답"을 넓은 공간에서 건져 올린다. 담금질 기법(Simulated Annealing), 개미 군집(ACO), 입자 군집(PSO)도 같은 계열의 친척이다.