Surrogate-Assisted Genetic Programming with Rank-Based Phenotypic Characterisation for Dynamic Multi-Mode Project Scheduling

이 논문은 동적 다중 모드 프로젝트 스케줄링 문제 (DMRCPSP) 에 적용되는 유전 프로그래밍의 계산 비용을 줄이기 위해 활동 및 모드 쌍의 순위 기반 표현형 특성화 기법을 도입한 대리 모델 보조 알고리즘을 제안하고, 이를 통해 기존 최첨단 방법보다 더 일찍 고품질 휴리스틱 규칙을 발견할 수 있음을 입증합니다.

핵심

1. 문제 상황: 예측 불가능한 공사 현장

想像해 보세요. 여러분이 거대한 건물을 짓는 프로젝트 매니저라고 가정해 봅시다.

• 일정: 200 개의 작업 (벽돌 쌓기, 배관 설치 등) 이 있습니다.
• 문제: 각 작업은 '빠른 모드'나 '느린 모드'로 할 수 있는데, 정확히 얼마나 걸릴지 미리 알 수 없습니다. 비가 오거나 자재가 늦으면 시간이 달라집니다.
• 자원: 동시에 할 수 있는 작업 수와 인력 (자원) 에 한계가 있습니다.

이런 상황에서는 "어떤 작업을 먼저 하고, 어떤 방식으로 할지" 실시간으로 결정해야 합니다. 이때 **유전 프로그래밍 (GP)**이라는 AI 가 등장합니다. 이 AI 는 수천 가지의 "작업 우선순위 규칙"을 만들어내며, 가장 좋은 규칙을 찾아냅니다.

하지만 큰 문제가 하나 있습니다.
AI 가 만든 규칙이 정말 좋은지 확인하려면, 컴퓨터로 수천 번의 시뮬레이션을 돌려봐야 합니다. 마치 새로운 레시피를 개발할 때마다 100 번씩 요리를 해봐야 맛을 알 수 있는 것처럼, 시간과 비용이 너무 많이 듭니다.

2. 해결책: "가상 시뮬레이션"을 쓰는 똑똑한 조수 (대리 모델)

이 논문은 이 문제를 해결하기 위해 **대리 모델 (Surrogate Model)**이라는 '똑똑한 조수'를 도입했습니다.

• 기존 방식: 모든 규칙을 실제 공사 현장 (시뮬레이션) 에 투입해 보고 결과를 확인함. → 시간이 너무 오래 걸림.
• 새로운 방식: AI 가 만든 규칙의 '성격'을 분석해서, 실제 시뮬레이션 없이도 "이 규칙은 아마 잘할 거야"라고 예측하는 조수를 만듦. → 시간을 대폭 절약함.

3. 핵심 기술: 규칙의 '성격'을 숫자로 바꾸기 (표현형 특징화)

여기가 이 논문의 가장 창의적인 부분입니다. AI 가 만든 규칙이 어떤 '성격'을 가졌는지 어떻게 숫자로 나타낼까요?

저자들은 **순위 (Rank)**에 주목했습니다.

• 비유: 가상의 공사 현장에서 10 가지 작업이 기다리고 있다고 칩시다.
  • 규칙 A 는 "벽돌 쌓기를 1 순위, 배관 설치를 5 순위"로 정합니다.
  • 규칙 B 는 "벽돌 쌓기를 1 순위, 배관 설치를 3 순위"로 정합니다.
• 방법: 이 규칙들이 다양한 상황에서 어떤 작업을 1 순위로, 2 순위로, 3 순위로 뽑아내는지 그 **순서 (순위)**를 기록합니다.
• 결과: 이렇게 규칙의 행동 패턴을 일련의 숫자 (벡터) 로 변환합니다. 이를 **'표현형 특징 (PC)'**이라고 부릅니다.

이제 컴퓨터는 실제 시뮬레이션을 돌리지 않아도, "이 규칙의 성격 (숫자 패턴) 을 보니, 이전에 본 '성공한 규칙'과 매우 비슷하네. 그래서 이 규칙도 잘할 거야!"라고 추측할 수 있게 됩니다.

4. 실험 결과: 더 빠르고 더 똑똑해짐

이 새로운 방식 (SKGGP) 을 기존 방식 (KGGP) 과 비교한 결과는 다음과 같습니다.

1. 더 빠른 발견: 같은 품질의 규칙을 찾아내는 데 훨씬 적은 시간 (시뮬레이션 횟수) 이 걸렸습니다. 마치 100 번 요리해 볼 필요 없이, 60 번만 해봐도 최고의 레시피를 찾아낸 것과 같습니다.
2. 효율적인 선택: AI 가 무작위로 만든 1,000 개의 규칙 중, 실제로 시뮬레이션해 볼 가치가 있는 '유망한 규칙'만 골라내는 능력이 뛰어나졌습니다.
3. 적은 비용: 이 '조수'를 부르는 데 드는 비용은 실제 시뮬레이션 비용의 1/20~1/40 수준으로 매우 저렴합니다.

5. 결론: 왜 이 연구가 중요한가요?

이 논문은 **"실제 실행하기 전에, 규칙의 성격을 분석해서 미리 예측하는 방법"**을 개발했습니다.

• 기존: "일단 다 해봐. 결과가 나쁘면 버리고, 좋으면 가져가." (비효율적)
• 새로운 방법: "이 규칙의 성격을 보니, 저 규칙과 비슷하네. 저 규칙은 잘했으니 이 규칙도 잘할 거야. 실제 실행은 나중에 해보자." (효율적)

이 기술은 프로젝트 관리뿐만 아니라, 시간이 많이 걸리는 복잡한 의사결정이 필요한 모든 분야 (예: 신약 개발, 항공기 설계 등) 에서 시간과 비용을 아끼는 데 크게 기여할 수 있습니다.

한 줄 요약:

"매번 실험을 해보는 대신, 규칙의 '성격'을 분석해서 미리 점수를 매겨주는 똑똑한 AI 조수를 만들어, 프로젝트 관리 규칙을 훨씬 빠르고 저렴하게 찾아냈습니다."

기술 요약

1. 연구 배경 및 문제 정의 (Problem)

• 동적 다중 모드 자원 제약 프로젝트 스케줄링 문제 (DMRCPSP):
  • 프로젝트 관리에서 예산과 시간 제약 내에서 프로젝트를 완료하기 위해 필수적인 문제입니다.
  • 기존 MRCPSP 와 달리, 동적 환경에서 활동의 실제 소요 시간이 사전에 알려지지 않고 실행 중에만 revealed 됩니다.
  • 따라서 프로젝트 상태가 업데이트됨에 따라 온라인 (실시간) 으로 어떤 활동을 어떤 모드로 실행할지 결정해야 합니다.
• 기존 접근법의 한계:
  • 유전 프로그래밍 (GP) 은 이러한 동적 의사결정을 위한 휴리스틱 규칙을 진화시키는 데 효과적이지만, 개체의 적합도 (Fitness) 를 평가하기 위해 수많은 시뮬레이션이 필요합니다.
  • 이로 인해 계산 비용이 매우 높고, 동적 환경에서의 실용적 적용이 제한됩니다.
• 대리 모델 (Surrogate Model) 의 필요성:
  • 계산 비용이 높은 적합도 평가를 줄이기 위해 대리 모델을 사용할 수 있으나, GP 에 적용하려면 휴리스틱 규칙의 행동 차이를 포착할 수 있는 문제 특화 표현형 특성 (Phenotypic Characterisation, PC) 체계가 필요합니다.
  • 현재 DMRCPSP 에 적용 가능한 적절한 PC 체계가 부재하여 대리 모델 보조 GP 가 이 문제에 직접 적용되지 못하고 있었습니다.

2. 제안된 방법론 (Methodology)

이 논문은 DMRCPSP 를 위한 새로운 순위 기반 표현형 특성 (Rank-based PC) 체계와 이를 활용한 대리 모델 보조 GP 알고리즘 (SKGGP) 을 제안합니다.

A. 새로운 표현형 특성 (PC) 체계

• 기존 체계의 한계: 기존 연구 [4] 의 PC 체계는 단일 선택 (Single-choice) 시나리오에 적합하지만, DMRCPSP 는 활동 순서 결정 (Ranking) 과 활동 그룹 선택 (Subset selection) 이 모두 포함되는 복잡한 구조라 적용이 불가능했습니다.
• 제안된 접근:
  1. 의사결정 상황 (Decision Situations) 정의:
     • 활동 순서 상황: 후보 활동 - 모드 쌍 (Activity-Mode Pairs) 을 우선순위로 정렬하는 상황.
     • 활동 그룹 선택 상황: 가능한 활동 그룹 중 실행할 그룹을 선택하는 상황.
  2. 순위 벡터 추출: 각 의사결정 상황에서 GP 휴리스틱이 모든 후보에 대해 부여한 순위 (Rank) 를 추출합니다. (작은 우선순위 값 = 높은 순위)
  3. PC 벡터 구성: 모든 의사결정 상황에서의 순위 정보를 연결하여 GP 개체의 행동 특성을 나타내는 수치 벡터로 변환합니다. 이는 휴리스틱의 행동을 정량화하여 개체 간 유사성을 측정할 수 있게 합니다.

B. 대리 모델 보조 GP 알고리즘 (SKGGP)

• 워크플로우:
  1. 초기 개체군 생성 및 PC 벡터 계산.
  2. PC 벡터가 중복된 개체 제거 (중복 제거 메커니즘).
  3. 대리 모델 구축: 현재 개체군의 PC 벡터와 실제 적합도 값을 기반으로 모델 학습.
  4. 후손 생성 및 평가:
     • $k \times |P|$ 개의 중간 후손 (Intermediate Offspring) 생성.
     • 생성된 후손의 PC 벡터를 계산하고, 대리 모델 (가장 가까운 이웃, Nearest-Neighbour) 을 사용하여 실제 시뮬레이션 없이 적합도를 추정합니다.
  5. 선택: 추정된 적합도가 높은 상위 $|P|$ 개의 개체만 전체 적합도 평가 (Full Fitness Evaluation) 를 수행하여 다음 세대로 전달합니다.
• 대리 모델: Manhattan 거리를 기반으로 한 가장 가까운 이웃 (k-NN) 회귀 모델을 사용하여 적합도를 예측합니다.

3. 주요 기여 (Key Contributions)

1. DMRCPSP 전용 PC 체계 개발: 활동 순서 결정과 그룹 선택이라는 두 가지 복잡한 의사결정 행동을 포착할 수 있는 순위 기반 (Rank-based) 표현형 특성을 최초로 설계했습니다.
2. 효율적인 대리 모델 보조 GP 프레임워크: 제안된 PC 체계를 통합하여, 실제 시뮬레이션 비용을 크게 줄이면서도 고품질 휴리스틱 규칙을 진화시키는 알고리즘 (SKGGP) 을 구현했습니다.
3. 성능 검증 및 분석: 기존 최첨단 GP (KGGP) 와의 비교를 통해, 제안된 방법이 더 적은 평가 횟수로 더 우수한 성능을 달성함을 입증하고, 후손 배수 (Offspring Multiplier, $k$) 가 진화 효율에 미치는 영향을 심층 분석했습니다.

4. 실험 결과 (Results)

• 실험 설정: 200 개의 활동, 3 가지 실행 모드, 12 가지 자원을 가진 다양한 난이도 (Order Strength: 0.75, 0.5, 0.25) 의 프로젝트 시나리오에서 30 회 독립 실행.
• 성능 비교:
  • SKGGP-2 및 SKGGP-4는 기존 KGGP 보다 모든 시나리오에서 통계적으로 유의미하게 우수한 성능을 보였습니다.
  • 수렴 속도: SKGGP 는 KGGP 보다 훨씬 빠르게 최적 해에 수렴했습니다.
  • 평가 비용 절감: 동일한 성능을 달성하는 데 KGGP 대비 약 20~40% 의 평가 예산 (Full Fitness Evaluations) 을 절감할 수 있었습니다.
• 후손 배수 ($k$) 의 영향:
  • $k=1.5$일 때 대리 모델의 정밀도 (Precision) 가 가장 높았으나 (8090%), $k=4$로 증가하면 정밀도가 하락 (5060%) 했습니다.
  • 그러나 $k=2$와 $k=4$ 모두 KGGP 보다 우수한 전체 성능을 보였으며, 추가 생성된 후손 중 상당 부분이 실제 품질 향상에 기여함을 확인했습니다.
• 계산 오버헤드: 대리 모델 추정 시간은 전체 시뮬레이션 평가 시간의 약 1/20 ~ 1/40 수준으로 매우 낮아, 계산 효율성이 크게 향상되었습니다.

5. 의의 및 결론 (Significance & Conclusion)

• 실용적 가치: DMRCPSP 와 같은 복잡한 동적 의사결정 문제에서 GP 기반 휴리스틱의 계산적 확장성 (Scalability) 문제를 해결했습니다.
• 방법론적 혁신: 시뮬레이션 비용 없이 개체의 행동 특성을 정량화하는 새로운 PC 체계를 통해, 대리 모델이 GP 진화 과정에 효과적으로 개입할 수 있는 기반을 마련했습니다.
• 향후 과제: 현재 대리 모델의 정밀도가 후손 수가 매우 많을 때 감소하는 한계를 극복하기 위해, 대리 데이터베이스 확장, 더 정교한 PC 체계 개발, 그리고 다양한 머신러닝 모델 도입 등을 향후 연구 과제로 제시했습니다.

요약하자면, 이 논문은 동적 프로젝트 스케줄링 문제에서 시뮬레이션 비용을 획기적으로 줄이면서도 고품질의 의사결정 규칙을 자동으로 생성할 수 있는 새로운 유전 프로그래밍 프레임워크를 제안하고 실험적으로 입증한 의미 있는 연구입니다.