라마르크 진화와 볼드윈 효과에 대한 새로운 관점

볼드윈 진화 (Baldwinian evolution)와 라마르크 진화 (Lamarckian evolution)는 진화 알고리즘 (Evolutionary Algorithms, EAs) 분야에서 오랫동안 존재해 왔으나, 학술 문헌이나 실제 응용 분야를 지배한 적은 없었습니다. 본 연구에서는 현대적인 경험적 및 이론적 방법론을 사용하여 라마르크 진화와 볼드윈 진화를 재조명하고, 이를 일반적인 다윈 진화 (Darwinian evolution)와 엄격하게 비교합니다. 경험적 측면에서는, 최근 GraphBench 벤치마크의 최대 독립 집합 (Maximum Independent Set) 및 최대 컷 (Maximum Cut) 문제에 관한 6개의 서로 다른 데이터셋 그래프를 대상으로 포괄적인 실험 세트를 실행합니다. 우리의 결과는 볼드윈 진화와 라마르크 진화가 다윈 진화보다 일관되게 우수한 성능을 보임을 나타내며, 이는 국소 탐색 (Local search)이 강화된 진화 알고리즘의 큰 잠재력을 확인시켜 줍니다. 특히, 대다수의 사례에서 모든 진화 알고리즘 (EAs)은 최근의 딥러닝 (Deep learning) 베이스라인보다 우수한 성능을 보였으며, 고도로 특화된 휴리스틱 (Heuristic) 및 정확한 해법 (Exact solvers)의 성능에 근접했습니다. 나아가, 우리는 연구된 모든 진화 유형에 대해 성능이 뛰어난 범용 파라미터 세트를 보고하며, 이것이 향후 실무자들에게 유용하게 쓰이기를 바랍니다. 이론적 측면에서는, 기존의 기만적 선도 블록 (Deceptive Leading Block) 벤치마크를 임의의 블록 길이로 확장하고, 현대적인 이론적 실행 시간 분석 (Theoretical runtime analysis) 도구를 사용하여 기대 실행 시간의 상한 및 하한을 증명합니다. 블록 길이가 2보다 큰 경우, 볼드윈 진화는 점근적으로 라마르크 진화보다 빠르며, 라마르크 진화는 점근적으로 다윈 진화보다 빠릅니다. 적합도 평가 (Fitness evaluations) 시 국소 탐색 절차의 비용을 고려할 때, 그 순서는 구현 방식에 따라 달라지지만 볼드윈 진화는 작은 블록 길이부터 가장 빠른 상태를 유지하며, 이는 볼드윈 진화의 강력한 경험적 성능을 설명해 줍니다.