유전 알고리즘에서 유효한 해만 만드는 표현법

유전 알고리즘이 빠르게 많은 후보를 만들더라도 대부분이 실행 불가능하면 탐색 능력을 낭비합니다. 복잡한 선후관계와 배정 규칙이 있는 문제에서는 염색체의 표현과 디코딩 과정부터 설계해야 합니다.

무엇을 유전자로 넣을지 고른다

작업 순서, 사람 배치, 보조 인력 투입을 모두 유전자로 만들면 탐색 공간이 크게 늘어납니다. 큰 구조를 탐색하는 값과 주어진 구조에서 결정적으로 계산할 값을 구분하면 후보 평가가 단순해집니다.

랜덤 키로 선후관계를 다룬다

각 작업에 우선순위 키를 부여하고, 매 단계에서 선행 작업이 이미 끝난 후보 중 키가 높은 작업을 선택합니다. 키 자체를 교차하거나 바꿔도 디코더가 선후관계를 지키므로 그 부분의 복구가 필요 없습니다. 단, 다른 제약까지 자동으로 만족한다는 뜻은 아닙니다.

유효성은 디코더가 보장해야 한다

작업 순서가 유효해도 인력 자격이나 스테이션 용량 때문에 전체 해는 실패할 수 있습니다. 스테이션을 구성하며 용량을 확인하고, 가능한 숙련공 후보가 적은 곳부터 배정하는 등 별도의 규칙을 둡니다.

복구·패널티·표현법을 비교한다

위반 해에 벌점을 주는 방식은 구현이 쉽지만 벌점 설정에 민감합니다. 복구 절차는 실행 가능 해를 늘리지만 시간이 들 수 있습니다. 처음부터 유효한 부분 해를 생성하는 표현법은 강력하지만 디코더 편향을 측정해야 합니다.

작은 문제에서 정확해법과 대조한다

소규모 사례는 MILP나 CP-SAT으로 최적값을 구해 GA의 품질을 확인합니다. 큰 사례에서는 최적을 보장한다고 쓰지 않고 비용, 위반율, 실행 시간, 여러 시드의 결과 분산을 공개해야 합니다.

현장에 적용할 때의 순서

1. 작업별 랜덤 키를 만든다
2. 선행 조건을 만족한 후보에서 순서를 디코딩한다
3. 인력·용량 제약은 별도 배정 규칙으로 확인한다

주의할 실패: 순서 유효성만으로 전체 해가 유효하다고 착각

관찰할 지표: 유효 해 비율과 최적값 대비 차이를 측정

적용 전 체크리스트

• 교차·돌연변이 후 유효 해 비율을 측정한다
• 디코딩 시간이 전체 실행 시간에서 차지하는 비중을 기록한다
• 소규모 최적값과 반복 실행 결과를 비교한다

참고 자료

Moon et al. (2014), Integrated Assembly Line Balancing with Skilled and Unskilled Workers. 랜덤 키와 숙련·비숙련 인력 배정 구조는 회사 연구자의 공개 논문을 참고했습니다. 다른 제약의 유효성은 별도 검증해야 한다는 실무 해석을 덧붙였습니다.

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

#유전알고리즘 #GA #랜덤키 #스케줄링 #최적화 #휴리스틱 #조립라인 #디코딩 #유효해 #운영연구