유전 알고리즘은 언제 멈춰야 할까

유전 알고리즘은 세대를 오래 돌릴수록 항상 의미 있는 개선이 생기는 것은 아닙니다. 반대로 몇 세대 동안 정체됐다고 곧바로 최적해라고 말할 수도 없습니다. 종료 조건은 계산 예산과 해의 안정성을 함께 반영해야 합니다.

시간 한도를 먼저 정한다

실제 배치 결정이 10분 안에 내려져야 한다면 1시간 동안 조금 더 좋은 해를 찾는 알고리즘은 쓸 수 없습니다. 허용 실행 시간과 최소 수용 가능한 해 품질을 업무에서 먼저 정합니다. 종료 조건이 지나치게 빠르면 운에 따라 얻은 해를 최종 결과로 채택하게 됩니다. 반대로 개선 가능성이 거의 없는 상태를 오래 유지하면 운영 마감 시간을 놓칩니다. 두 손실을 실험으로 비교해 기준을 정하는 것이 중요합니다.

개선 정체를 측정한다

최근 일정 세대 동안 최선 비용이 얼마나 개선됐는지 봅니다. 절대 금액이나 비율의 임계값을 두되 목표함수의 규모가 바뀌면 기준도 바꿔야 합니다.

다양성이 남아 있는지 본다

집단의 개체들이 모두 비슷해졌다면 교차·돌연변이가 새로운 영역을 찾기 어렵습니다. 유전자의 다양성과 유효 해 비율을 함께 보면 단순 정체와 조기 수렴을 구분하는 데 도움이 됩니다.

여러 시드로 재현성을 본다

한 번의 실행에서 좋은 해를 얻었다고 늘 같은 수준을 얻는 것은 아닙니다. 여러 무작위 시드에서 최종 비용과 시간의 분포를 보고, 나쁜 실행이 현장 허용 범위를 넘는지 확인합니다.

정확해법의 하한이 있으면 활용한다

작은 문제의 최적값이나 큰 문제의 하한이 있다면 현재 해와의 차이를 기록합니다. 다만 하한이 약한 경우 차이가 커도 GA 해가 나쁘다는 뜻은 아니므로 지표의 의미를 설명해야 합니다.

현장에 적용할 때의 순서

1. 업무 마감 시간과 최소 해 품질 정의
2. 개선 정체와 집단 다양성 추적
3. 여러 시드로 해 품질 분포 검증

주의할 실패: 정체를 곧 최적성 증명으로 해석

관찰할 지표: 시간 내 수용 해 비율·최종 비용 분산

적용 전 체크리스트

• 현장 의사결정 마감 시간을 종료 조건에 반영한다
• 정체·다양성·유효 해 비율을 함께 관찰한다
• 여러 시드의 최종 비용 분산을 공개한다

참고 자료

Moon et al. (2014), Integrated Assembly Line Balancing with Skilled and Unskilled Workers. 세대 한도와 개선 정체를 함께 사용한 사례는 회사 연구자의 공개 논문을 참고했습니다. 다양성·반복 실험 기준은 실무 검증 제안입니다.

이미지와 도식은 이해를 돕기 위한 개념 시각화입니다. 특정 고객의 실제 설비·데이터·화면을 재현한 것이 아닙니다.

#유전알고리즘 #GA #종료조건 #조기수렴 #최적화 #메타휴리스틱 #스케줄링 #실험설계 #무작위시드 #해품질