순위 기반 표현형 특징 추출을 활용한 대리 모델 지원 유전 프로그래밍: 동적 다중 모드 프로젝트 스케줄링

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

동적 다중 모드 자원 제약 프로젝트 스케줄링 문제(DMRCPSP)는 변화하는 프로젝트 상태 및 자원 가용성 하에서 실시간 의사 결정을 요구하므로 실제적으로 중요한 문제입니다. 유전 프로그래밍(GP)은 이러한 의사 결정 작업에 대한 휴리스틱 규칙을 효과적으로 진화시키는 것으로 나타났지만, 진화 과정은 일반적으로 많은 수의 시뮬레이션 기반 적합도 평가에 의존하며, 이는 높은 계산 비용을 초래합니다. 대리 모델은 평가 비용을 줄이는 유망한 해결책을 제공하지만, GP에 대리 모델을 적용하려면 문제 특정적인 휴리스틱 규칙의 표현형 특징 추출(PC) 체계가 필요합니다. 현재 DMRCPSP에 적용되는 GP를 위한 적절한 PC 체계가 부족합니다. 본 논문에서는 휴리스틱 기반 활동-모드 쌍 및 활동 그룹의 순위를 활용하여 순위 기반 PC 체계를 제안합니다. 결과적으로 생성된 PC 벡터는 대리 모델이 평가되지 않은 GP 개체의 적합도를 추정하는 데 사용됩니다. 이 체계를 기반으로 대리 모델 지원 GP 알고리즘이 개발되었습니다. 실험 결과는 제안된 대리 모델 지원 GP가 최첨단 GP 접근 방식보다 일관되게 더 빠르고 고품질의 휴리스틱 규칙을 식별할 수 있으며, 동시에 미미한 계산 오버헤드만 발생한다는 것을 보여줍니다. 추가 분석 결과, 대리 모델은 자손 선택에 유용한 지침을 제공하여 진화 효율성을 향상시키는 것으로 나타났습니다.

The dynamic multi-mode resource-constrained project scheduling problem (DMRCPSP) is of practical importance, as it requires making real-time decisions under changing project states and resource availability. Genetic Programming (GP) has been shown to effectively evolve heuristic rules for such decision-making tasks; however, the evolutionary process typically relies on a large number of simulation-based fitness evaluations, resulting in high computational cost. Surrogate models offer a promising solution to reduce evaluation cost, but their application to GP requires problem-specific phenotypic characterisation (PC) schemes of heuristic rules. There is currently a lack of suitable PC schemes for GP applied to DMRCPSP. This paper proposes a rank-based PC scheme derived from heuristic-driven ordering of eligible activity-mode pairs and activity groups in decision situations. The resulting PC vectors enable a surrogate model to estimate the fitness of unevaluated GP individuals. Based on this scheme, a surrogate-assisted GP algorithm is developed. Experimental results demonstrate that the proposed surrogate-assisted GP can identify high-quality heuristic rules consistently earlier than the state-of-the-art GP approach for DMRCPSP, while introducing only marginal computational overhead. Further analyses demonstrate that the surrogate model provides useful guidance for offspring selection, leading to improved evolutionary efficiency.