수상권 팀들이 모두 정답을 찾았고, 대회 기간이 절반정도 지나서 제가 사용했던 방법을 간단하게 공유해보려 합니다.

(몇 함수는 code7monkey님이 공유하신 코드에서 찾을 수 있습니다.)

1 데이터 읽기

• TOWN들의 단순 유클리드 거리를 계산하여 75x75 크기의 리스트(거리 행렬)에 저장했습니다.

2 Helper 함수 구축

• Route 적합성 검사
• 주어진 route가 demand 용량(25)을 초과하지 않는지 확인합니다. 초과 시 DEPOT으로 돌아가는 경로를 추가해 나눕니다.
• route 총 거리 계산
• 하나의 route를 여러 sub-route로 나눕니다. 각 sub-route는 DEPOT에서 출발해 해당 경로를 순회하고 DEPOT으로 돌아오는 거리로 계산합니다.
• 모든 sub-route 거리의 합이 해당 route의 총 이동 거리입니다.
• 초기 population 생성
• 무작위로 TOWN 순열을 생성하며, demand 용량(25)을 넘지 않는 순열만 초기 population에 포함합니다.

3 유전 알고리즘 functions 구축

• 부모 population 선택 function
• 여러 후보 중 랜덤으로 선택한 뒤, 거리 합이 최소인 해를 부모로 선택합니다. 다양한 부모를 선택하기 위해 동일한 과정을 두 번 반복합니다.
• 자식 population 생성 function
• 두 부모 해(parent1, parent2)를 입력받아 새로운 자손을 생성합니다.
• parent1에서 연속 구간을 복사하고, 남은 부분은 parent2 순서를 따라 겹치지 않게 채웁니다.
• 돌연변이 생성 function
• 일정 확률(mutation_rate)로 경로 상의 TOWN 두 개를 단순히 스왑하여 변이를 발생시킵니다.
• Local search function
• 이 함수는 핵심적인 역할을 합니다. 변별력을 위해 구체적인 내용은 비공개합니다.

4 유전 알고리즘 loop

(1) 현재 population 중 가장 좋은 해를 다음 세대로 그대로 넘깁니다.

(2) 토너먼트 선택 → 교차 → 돌연변이 과정을 통해 자손을 생성한 후, Local Search를 적용해 자손의 품질을 개선합니다.

(3) demand 용량(25)을 초과하지 않는 자손들만 새 generation에 포함합니다.

(4) 새 세대가 완성되면 각 자손의 거리를 계산하고, 가장 적합한 해(best population)와 최소 거리(best Euclidean Distance)를 갱신합니다.

(5) (1) ~ (4)를 반복합니다.

이렇게 구성하여 최적 경로를 탐색했습니다.

많은 참가자 분들에게 도움이 되었으면 합니다.

감사합니다.