조선소 마킹 경로 최적화를 위한 이중 탐색 전략 기반의 상태 적응형 카오스 회색 늑대 최적화

1. 서 론

조선 산업의 핵심 선행 단계인 마킹 공정은 강재 표면에 설계 정보를 가시화하여 후속 공정의 기준을 제공하는 절차로 전체 건조 원가와 리드타임을 결정짓는 주된 요인이다. 물리적 제약이 엄격한 절단 공정과 달리 마킹 공정은 경로 설정의 유연성이 높아 최적화 적용 시 토치의 비가공 이동 거리를 획기적으로 단축할 수 있는 잠재력이 크다. 본질적으로 마킹 경로 문제는 방문 순서와 진입 방향을 동시에 결정해야 하는 방향성 제약이 포함된 조합 최적화 문제이며 Dewil et al. (2016)이 문헌 고찰을 통해 역설하였듯 공정 효율화의 필수 과제이다. 그러나 Bennell and Oliveira (2008)가 지적한 바와 같이 비정형 부재가 고밀도로 배치된 네스팅 환경은 방대한 해 공간을 형성하며 Laporte (1992)에 따르면 이러한 NP-hard 문제는 규모가 커질수록 연산 시간이 지수적으로 증가하여 정확한 전역 최적해를 도출하기 어렵다는 난점이 있다.

이를 해결하기 위해 초기 연구들은 다양한 기법을 적용하는데 집중하였다. Dewil et al. (2015)은 일반화된 TSP(Generalized Traveling Salesman Problem, GTSP)로 모델링하여 해법을 모색하였으나 복잡한 제약 반영에 한계를 보였고, 이후 문제의 복잡도를 극복하기 위해 다양한 메타휴리스틱(Meta-heuristic)기법이 활발히 도입되었다. Han and Jang (2000)은 유전 알고리즘을 활용하여 부재의 절단 순서와 피어싱 위치를 동시에 탐색하는 최적화 모델을 제안하였다. Wang and Xie (2005)는 군집 기반 메타휴리스틱인 개미 군집 최적화(Ant Colony Optimization, ACO)를 적용하였으나 초기 탐색 지연과 파라미터 민감성으로 인해 대규모 문제에서 수렴 속도가 저하되는 구조적 한계를 드러냈다. 이후 Hajad et al. (2019)은 단일 해 기반 탐색 기법인 담글질 기법(Simulated Annealing, SA)에 적응형 대규모 이웃 탐색(Adaptive Large Neighborhood Search, ALNS)을 결합하여 탐색 효율을 개선하고자 하였다. Zhu and Tang (2020)은 유전 알고리즘(Genetic Algorithm, GA)과 ACO를 결합한 하이브리드 기법을 제안하였다. 그러나 이러한 하이브리드 방식은 연산 자원의 소모가 커 잦은 설계 및 배치 변경에 따른 경로 재설정이 요구되는 조선소 현장의 실무 적용에 한계가 있다.

이에 최근에는 연산 효율성이 뛰어난 단일 알고리즘을 고도화하는 연구가 주목받고 있다. 대표적으로 Qu and Du (2023)는 레비 비행, 거듭제곱 함수 및 카오스 맵을 결합한 입자 군집 최적화(Levy Flight, power function, and Singer map employed particle swarm optimization, LPSPSO)를 제안하였으나 과도한 변동성으로 인해 탐색 후반부의 미세 조정 능력이 떨어져 최종 수렴 정밀도가 저하되는 한계가 지적되었다. 한편 Mirjalili et al. (2014)이 제안한 회색 늑대 최적화(Grey Wolf Optimizer, GWO)는 간결한 구조로 부상하였으나 Faris et al. (2018)의 분석대로 탐색 후반부에 다양성이 상실되며 지역 최적해에 고착되는 고질적인 문제가 있다. 이를 보완하기 위해 Kohli and Arora (2018)와 Lu et al. (2020)은 카오스 맵을 도입하였으나 단순한 난수 대체나 정적 적용에 그쳐 우수 해의 정보가 소실될 위험이 있었고 Zhang et al. (2024)의 적응형 파라미터 전략 역시 탐색 효율 가속화에 국한되어 정체 상황에 대한 능동적 대처가 부족하다.

Blum and Roli (2003)가 성공적인 최적화의 핵심으로 전역 탐색과 지역 활용의 균형을 강조하였듯 대규모 문제 해결을 위해서는 보다 능동적인 상태 기반 제어 기제가 필수적이다. 이에 본 연구는 상태 적응형 카오스 회색 늑대 최적화(SAC-GWO)를 제안한다. 구체적으로 제안 기법은 실시간으로 군집의 다양성 상태를 진단하고 이에 따라 탐색과 활용의 균형을 능동적으로 조절하는 이중 탐색 전략과 로지스틱 카오스 맵을 결합하여 알고리즘의 유연성을 확보하였다. 이를 통해 기존 기법의 고질적인 문제인 조기 수렴 현상을 근본적으로 방지하고 대규모 네스팅 도면의 복잡한 제약 조건 하에서도 안정적으로 최적 경로를 도출하는 것을 목표로 한다. 아울러 본 연구에서 제안한 알고리즘의 최적화 성능과 실무적 유효성을 객관적으로 검증하기 위해 수리 최적화 분야의 상용 솔버인 gurobi optimizer의 연산 결과와 정량적인 비교 분석을 수행한다.

2. 문제 정의

본 연구에서 다루는 네스팅 도면의 마킹 순서 결정 문제는 주어진 N개의 마킹 작업을 수행할 때 총 마킹 길이는 일정하므로 비가공 이동 거리의 총합을 최소화하는 작업순서와 각 작업의 진입 방향을 결정하는 문제로 정의된다. 실제 마킹 궤적은 형상이 매우 복잡하나 경로 최적화 관점에서는 마킹 토치가 궤적을 그리기 위해 하강하는 지점과 가공을 완료하고 이탈하는 지점의 좌표만이 비용 함수에 영향을 미친다. 따라서 연산의 효율성을 위해 전체 마킹 작업 집합 $$ M=\left\{M_1,M_2,\dots ,M_N\right\}$$의 개별 작업 M_i를 식(1)과 같이 한 쌍의 시작 위치 벡터 S_i와 종점 위치 벡터 E_i으로 정식화한다. 이때, 각 마킹 작업의 두 끝점 중 x축 좌표값이 작은 지점을 S_i, 큰 지점을 E_i로 정의한다. x축 좌표가 동일한 경우에는 y축 좌표값이 작은 지점을 S_i로 설정한다.

마킹 공정의 제약으로 인해 마킹 헤드는 각 작업을 수행하기 위해 두 노드 S_i, E_i중 하나를 반드시 진입점으로 선택해야 하며, 반대쪽 노드는 자동적으로 종출점이 된다. 마킹 헤드의 기준 원점을 $$ P_0=\left(\mathrm{0,0}\right)$$로 정의한다. 본 문제의 결정 변수는 작업 i의 진입 방향을 결정하는 이진 변수 $$ y_i\in \left\{\mathrm{0,1}\right\}$$와 노드 i에서 j로의 이동 여부를 나타내는 이진 변수 $$ x_{ij}\in \left\{\mathrm{0,1}\right\}$$로 구성된다. 방향 결정 변수 y_i에 의해 동적으로 결정되는 작업 M_i의 실제 진입 노드 $$ P_i^{in}$$와 종출 노드 $$ P_i^{out}$$는 다음과 같은 대수식으로 정의된다.

수리 모델의 정식화 과정에서 선형성을 확보하고 수식의 간결성을 도모하기 위하여 각 노드 쌍 간의 유클리드 거리를 상수로 사전 산출하여 다음과 같이 거리 매개변수 d_0j,d_ij,d_i0를 정의한다.

정의된 결정 변수와 매개변수를 바탕으로, 비가공 이동 거리의 총합을 최소화하기 위한 본 연구의 목적 함수는 식 (7)과 같이 도출된다.

본 최적화 모델은 모든 작업의 완전한 방문과 경로의 연속성을 보장해야 하며, 특히 경로 내에 독립된 소순환이 발생하는 것을 차단하기 위해 MTZ(Miller-Tucker-Zemlin) 제약식을 포함한 다음의 제약 조건식 (8)~(13)을 반드시 만족해야 한다.

식 (8)은 원점에서의 유출 및 유입이 각각 1회임을 보장하며 식 (9)와 (10)은 각 작업 노드의 진출입 차수 제약으로 모든 마킹 작업이 중복 없이 수행되어야 함을 나타낸다. 식 (11)과 (12)는 각 노드의 방문 순서를 정의하는 연속 변수를 도입한 부분 경로 제거 제약식으로 전체 탐색 경로가 분절 없이 하나의 폐경로로 연결되도록 수리적 한계를 부여한다. 마지막으로 식 (13)은 각 결정 변수의 범위를 정의한다.

3. 제안 방법

3.1 제안 알고리즘의 전체 구조

제안하는 SAC-GWO는 서로 다른 알고리즘을 결합하는 기존 하이브리드 방식과 달리 GWO의 단일 프레임워크 내에서 상태에 따라 연산자를 적응형으로 교체하는 경량화된 구조를 채택하여 연산 효율성과 탐색 성능을 동시에 확보하였다. Fig. 1에 도식화된 바와 같이 본 알고리즘은 상태 적응형 파라미터 제어(adaptive parameter control), 이중 탐색 전략(dual search strategy), 리더 갱신(leader update)으로 이어지는 계층적 순환 구조를 통해 매 세대 최적해를 탐색한다. 최적화 과정은 초기 모집단의 품질을 확보하는 단계에서 시작된다. 이를 위해 무작위 생성 방식과 최근접 이웃(Nearest Neighbor, NN) 기법을 병행하는 하이브리드 초기화 전략을 적용하여 수렴 속도를 제고하였다. 모집단이 구성되면 알고리즘은 매 세대 군집의 다양성 지표를 정량적으로 산출하여 탐색 상태를 실시간으로 진단한다. 이 진단 결과는 탐색 강도를 조절하는 핵심 변수인 비선형 제어 파라미터 a를 업데이트하는 핵심 지표로 활용된다. 이때 파라미터 a는 각 객체의 탐색 범위를 결정하는 수렴 계수 벡터 A를 산출하는 기준이 된다. 수렴 계수 A는 아래 식 (14)와 같이 파라미터 a와 난수 r의 연산을 통해 결정되며, 최종적으로 |A|의 크기는 현재 군집의 상태가 광역 탐색이 필요한 단계인지 혹은 국소 활용이 필요한 단계인지를 결정하는 수학적 임계치가 된다.

$\[ A=2\cdot a\cdot r_1-a \]$

(14)

Fig. 1

Proposed framework of SAC-GWO

산출된 A의 크기에 따라 현재 시점이 탐색이 필요한 단계인지 혹은 활용이 필요한 단계인지를 능동적으로 결정한다. 확정된 상태 정보는 하위 계층인 이중 탐색 전략을 결정하는 기준으로 작용한다. 구체적으로 수렴 계수 벡터 |A|의 크기에 따라 탐색영역의 확장 여부가 판별된다. |A| ≥ 1인 발산 단계에서는 탐색 영역의 확장이 필요하다고 판단하여 삽입 연산자를 수행하며, 이를 통해 해의 순열 구조를 전역적으로 재배열함으로써 탐색 공간을 넓게 확보한다. 반면, |A| < 1인 수렴 단계에서는 해의 정밀도를 높이기 위해 탐색 기제가 세분화된다. 이때 0과1 사이의 난수 r이 적응형 임계값 τ보다 작은 경우에는 역전 연산자를 통해 개체별 독자적인 국소 탐색을 수행하고 리더 정보 기반 탐색이 요구되는 경우에는 로지스틱 카오스 맵을 적용하여 리더 개체를 변이시킨 후 교차 연산을 수행한다. 특히 카오스 맵의 도입은 우수 해를 참조하는 과정에 비선형적 불규칙성을 주입함으로써 집단 전체가 지역 최적해에 동반 고착되는 현상을 효과적으로 차단한다. 이러한 계층적 과정을 거쳐 생성된 신규 해는 최종적으로 리더 갱신 단계에서 검증된다. 그리디 선택 기법을 적용하여 신규 해가 기존 해보다 우수할 경우에만 해당 개체를 갱신하며 이후 알파(α), 베타(β), 델타(δ) 늑대의 위치를 업데이트하고 종료 조건을 검토한다. 결과적으로 이러한 유기적인 순환 구조는 탐색 초기에는 불필요한 무작위성을 배제하고, 후반부에는 적응형 제어를 통해 조기 수렴을 방지함으로써 대규모 네스팅 문제에서도 안정적으로 최적 경로를 도출하도록 유도한다.

3.2 이중 계층 인코딩

마킹 경로의 방문 순서와 진입 방향이라는 서로 다른 설계 변수를 효율적으로 처리하기 위해 Fig. 2와 같이 해를 두 가지 독립된 계층으로 인코딩한다. 상위 순서 계층은 마킹 부재 번호를 나열한 정수형 순열 벡터로 구성되며, 이는 제2장에서 정의한 이진 변수 방식보다 설계 변수의 수를 축소하여 연산 복잡도를 낮추는 장점이 있다. 하위 방향 계층은 부재별 진입 지점을 결정하는 이진 벡터로 정의되며, 도식에 명시된 바와 같이 이진 값 0과 1은 각각 제2장에서 정의한 노드 S_i와 노드 E_i에 대응된다. 이에 따라 방향 값이 0이면 노드 S_i를 진입점으로 선택하고 1이면 노드 E_i를 선택함으로써 수리 모델의 방향성 제약을 충족한다.

Fig. 2

Dual-layer encoding and decoding schematic

두 계층은 회색 늑대 최적화 알고리즘의 위치 갱신 메커니즘에 따라 상호 종속적으로 갱신되며, 특히 방향 계층의 갱신 시각 작업의 진입 지점은 부재 번호와 독립적으로 처리된다. 일반 개체인 오메가 늑대는 해당 방문 순서 위치에서 알파, 베타, 델타 리더가 보유했던 방향 패턴 중 하나를 무작위로 계승하며 해를 갱신한다. 이러한 위치 기반의 확률적 승계는 리더가 발견한 우수한 경로의 기하학적 형태를 군집 전체에 효과적으로 전파하여 탐색 효율과 다양성을 유지하는 역할을 수행한다. 인코딩된 정보는 디코딩 프로세스를 거쳐 물리적 경로로 변환되는데, 예로 Fig. 2 (b)의 step 2와 같이 부재 번호 1과 노드 E₁이 결합하면 해당 지점이 실제 진입점으로 확정된다. 확정된 진입점은 경로 실행 지도에서 비가공 이동인 점선과 실제 마킹 경로인 실선의 연결로 최종 구현된다.

4. 실 험

제4장에서는 제안한 SAC-GWO의 최적화 성능 및 현장 적용 가능성을 입증하기 위한 다각적인 실험 및 분석결과를 제시한다. 본 실험은 알고리즘의 통계적 강건성 검증을 위한 가상 데이터셋 실험과 실제 산업 현장의 복잡한 기하학적 특성을 반영한 실적 데이터셋 실험으로 구성된다. 또한, 수리 계획 기반의 상용 솔버인 gurobi optimizer를 비롯하여 기존의 대표적인 메타휴리스틱 알고리즘들과의 정량적 비교 분석을 수행함으로써 제안 기법의 해 품질과 연산 효율성을 다각도에서 종합적으로 고찰한다.

4.1 실험 환경 및 설정

본 연구는 제안하는 SAC-GWO 알고리즘의 최적화 성능을 객관적으로 검증하기 위해 통계적 특성이 제어된 가상 데이터셋과 실제 현장의 복잡성을 반영한 실적 데이터셋을 상호 보완적으로 활용하였다. 우선 가상 데이터셋은 알고리즘의 성능을 전역 탐색, 지역 최적해 탈출, 그리고 일반화 능력이라는 세 가지 관점에서 평가하기 위해 설계되었다. 데이터 생성 모델을 정의하기 위해 N개의 마킹 작업 집합에서 i번째 작업의 시작점과 끝점 좌표 벡터를 각각 $$ L_{i1},L_{i2}\in R^2$$로 정의한다. 이를 바탕으로 설계된 세 가지 데이터 생성 시나리오의 수리적 모델과 평가 목적은 Table 1과 같다.

Table 1

Data generation scenarios

Table 1에 제시된 각 시나리오의 구체적인 설계 의도는 다음과 같다. 첫째, case 1은 식 $$ L_{i1},L_{i2}\sim U{\left(\mathrm{0,1}\right)}^2$$과 같이 시작점과 끝점이 단위 공간 내에서 서로 독립적으로 생성되는 환경이다. 이는 문제 공간에 특정한 구조적 패턴이나 상관관계가 존재하지 않는 무질서한 상태를 가정하며 특정 휴리스틱에 편향되지 않고 알고리즘 본연의 탐색 능력만으로 전역 최적해를 도출할 수 있는지 판단하는 기준점이 된다. 둘째, case 2는 수식 $$ L_{i2}=L_{i1}+\mathrm{\Delta }{L}_i$$에 의해 정의된다. 여기서 변위 벡터 $$ \mathrm{\Delta }{L}_i$$는 $$ \left[-\mathrm{0.1,0.1}\right]$$의 좁은 범위 내에서 추출되므로 마킹선의 길이가 전체 작업 공간 대비 매우 짧게 제한된다. 이러한 구조는 작업 간 이동 거리보다 작업 자체의 길이가 짧은 객체들이 다수 존재하는 환경을 모사하며 잘못된 순서 결정 시 비용이 급증하는 다수의 지역 최적해 함정을 형성한다. 이는 제안 알고리즘이 국소 영역 내에서 효율적인 순서를 결정하고 정체 없이 탐색을 지속할 수 있는지 검증하는 척도로 활용된다. 셋째, case 3은 실제 조선소 현장의 통계적 특성을 반영한 시나리오이다. 다변량 정규 분포를 통해 강판의 가로·세로 규격 S_p를 먼저 샘플링한 후 그 규격에 맞춰 마킹 좌표를 스케일링하는 방식을 적용한다. 이를 통해 고정된 정사각형 공간이 아닌 가로로 긴 직사각형 등 다양한 형상비를 갖는 탐색 공간을 구현함으로써 알고리즘이 실제 공정의 기하학적 제약 조건 하에서도 안정적인 성능을 유지하는지 평가한다. 특히 본 실험에서는 조합적 복잡도가 높아 조기 수렴이 빈번하게 발생하는 대규모 문제를 대상으로 제안 기법의 확장성과 탐색 안정성을 체계적으로 검증하였다. 실험 결과의 통계적 신뢰성을 확보하기 위해 각 조건별로 무작위 생성된 100개의 독립적인 인스턴스를 사용하여 반복 실험을 진행하였다.

실험은 intel core ultra 7 265KF 프로세서와 64GB 메모리가 탑재된 워크스테이션의 단일 스레드 환경에서 python 3.10으로 구현되었다. 특히 제안 기법의 해 품질을 객관적인 절대 기준에서 평가하기 위해 상용 최적화 도구인 gurobi optimizer 13.0을 도입하여 기준값을 산출하였다. gurobi는 제2장의 정식화 모델을 기반으로 최적해를 탐색하되 문제의 복잡도를 고려하여 연산 시간을 1,800초로 제한하였다.

제안하는 SAC-GWO의 성능 우위를 입증하기 위해 서로 다른 탐색 메커니즘을 갖는 대표적인 메타휴리스틱 알고리즘들을 대조군으로 선정하였다. 여기에는 진화 연산 기반의 유전 알고리즘(GA), 군집 지능 기반의 개미 군집 최적화(ACO), 입자 군집 최적화(PSO), 그리고 표준 GWO가 포함된다. 실험의 공정성을 기하기 위해 모든 알고리즘은 동일하게 개체 수 100, 최대 반복 횟수 1,000으로 설정하여 목적함수 호출 횟수를 동일 수준으로 통제하였다. 또한, 초기해 품질에 따른 성능 편차를 배제하고 공정한 비교를 수행하기 위해, 제안 기법뿐만 아니라 모든 비교 대상 알고리즘(GA, ACO, LPSPSO, GWO)의 초기 개체군 생성에 최근접 이웃(NN) 기법을 동일하게 적용하였다.

각 알고리즘의 구체적인 파라미터 설정은 Table 2와 같다. 비교 알고리즘의 설정에 있어 유전 알고리즘(GA)은 해의 구조적 보존과 다양성 확보를 위해 학계에서 통용되는 표준 설정값을 적용하였다. 반면, 개미 군집 최적화(ACO)는 공정한 비교를 위해 선행 연구 Wang & Xie (2005)의 권장값을 준용하여 페로몬 및 거리 정보의 중요도를 조절하였으며, LPSPSO는 Qu & Du (2023)에 따라 singer map을 적용하여 탐색의 임의성을 부여하였다. 이에 대비하여 제안하는 SAC-GWO는 제3장에서 정의된 카오스 역학을 기반으로 상태 적응형 메커니즘의 민감도를 조절하는 결합 계수와 상태 전환의 기준이 되는 임계값을 사전 실험을 통해 최적값으로 선정하여 적용하였다.

Table 2

Algorithm parameter settings

4.2 실험 결과 및 성능 분석

본 절에서는 다양한 공간 분포 특성을 지닌 가상 데이터셋과 실제 조선소 현장의 실적 데이터셋을 활용하여 제안하는 SAC-GWO와 비교 알고리즘의 최적화 성능을 정량적으로 평가한다. 성능 분석을 위한 핵심 척도로는 해의 품질, 수렴의 일관성, 그리고 알고리즘의 연산 효율성을 선정하였다. 구체적인 평가지표로는 100회 독립 시행에 따른 평균 목적함수 값과 사분위수 범위, 그리고 평균 연산 시간을 산출하였으며 상용 최적화 도구인 gurobi optimizer는 이론적 최적해를 도출하므로 이를 성능 비교를 위한 절대적 기준 지표로 활용하였다. 제안 알고리즘의 최적해 탐색 성능을 객관적으로 비교하기 위해 기준 해 대비 상대적 오차율(gap)을 식 (20)와 같이 정의하여 평가 지표로 활용하였다.

$\[ Gap\left(\mathrm{\%}\right)=\frac{Z_{avg}-Z_{ref}}{Z_{ref}}\times 100 \]$

(20)

여기서 Z_avg는 각 알고리즘이 100회 독립 시행을 통해 도출한 평균 목적함수 값을 의미하며, Z_ref는 gurobi optimizer가 도출한 기준 목적함수 값을 나타낸다. 단, gurobi가 제한 시간 내에 최적해를 확정하지 못한 경우에는 해당 시점까지 탐색된 최선 해를 Z_ref로 설정하였다. 특히 각 문제의 규모에 따른 목적함수 값의 수치적 편차를 제거하고 객관적인 비교를 수행하기 위해 모든 좌표 데이터는 [0, 1]구간으로 정규화하여 적용하였다. 이에 따라 본 연구에서 정의하는 비용은 실제 물리적 이동 거리가 아닌 강판의 최대 길이 대비 상대적인 이동 거리 비율을 의미한다. 마지막으로 도출된 데이터의 비정규성을 고려하여 윌콕슨 순위 합 검정을 실시함으로써 유의 수준 p < 0.05 하에서 알고리즘 간 성능 차이에 대한 통계적 유의성을 검증하였다.

4.2.1 가상 데이터셋 실험 결과

대규모 문제로 구성된 세 가지 가상 시나리오에 대한 실험 결과는 Table 3과 같다. 제안하는 SAC-GWO는 모든 실험 조건에서 가장 낮은 평균 비용과 오차율을 기록하여 수치적인 성능 우위를 입증하였으며, 데이터 분포 형태에 따른 세부 분석 결과는 다음과 같다. 우선 균등 분포 환경인 case 1에서 표준 GWO는 47.5%의 오차율(gap)을 기록하며 탐색의 한계를 보인 반면, SAC-GWO는 이를 42.5% 수준으로 낮추며 약 5.0%p의 유의미한 성능 개선을 달성하였다. 이는 제안 기법에 적용된 적응형 파라미터 제어 전략이 방대한 탐색 공간에서도 개체 간의 적절한 분산도를 유지하며 전역 탐색 효율을 극대화했기 때문으로 풀이된다. 특히 지역 최적해 고착 위험이 높은 case 2의 군집 환경에서 알고리즘 간의 성능 편차가 더욱 현저하게 관찰되었다. 해당 환경에서 개미 군집 최적화(ACO)는 67.0%라는 매우 높은 오차율을 기록하며 특정 군집에 고착되는 조기 수렴 현상을 보였다. 이와 대조적으로 SAC-GWO는 비교군 중 가장 낮은 36.9% 의 오차율을 기록하였으며, 이는 GA(41.8%), LPSPSO(42.2%) 대비 약 5% 이상 향상된 결과이다. 이는 카오스 기반의 리더 갱신 전략이 국소 영역 탈출에 결정적인 기여를 했음을 시사한다. 또한 gurobi가 1,126초를 소요한 반면 SAC-GWO는 17.2초 만에 고품질의 해를 도출하여 연산 효율성 면에서도 우위를 보였다. 실제 조선소 현장의 통계적 특성을 반영한 case 3에서도 SAC- GWO는 48.0%의 가장 낮은 오차율을 기록하였다. 특히 알고리즘의 안정성을 나타내는 IQR 지표에서 SAC-GWO는 0.76을 기록하여, GA(0.90)나 GWO(0.88) 대비 변동성이 적고 일관된 최적화 성능을 제공함을 확인하였다. 이는 복잡한 기하학적 제약 조건 하에서도 제안 기법이 강건하게 작동함을 입증한다.

Table 3

Performance comparison on virtual datasets

4.2.2 실적 데이터셋 실험 결과

Table 4는 국내 A 조선소의 소형(35개), 중형(78개), 대형(123개) 실적 데이터를 대상으로 수행한 실험 결과를 나타낸다. 소형 강판 실험 결과, SAC-GWO는 16.7%의 오차율을 기록하며 GA(36.6%) 및 PSO(41.9%) 대비 월등한 최적해 근접성을 보였다. 이러한 성능 격차는 중형 강판에서 더욱 확대되었는데 타 알고리즘이 90% 이상의 높은 오차율로 난항을 겪은 반면 제안 기법은 37.6%를 기록하여 2배 이상의 성능 우위를 달성하였다.

Table 4

Performance comparison on real datasets

특히 Table 4의 대형 강판 실험 결과에서 gurobi optimizer는 NP-hard 문제의 한계로 인해 제한 시간 내 탐색을 완료하지 못하였으나, SAC-GWO는 26.3초 만에 16.0%의 오차율로 고품질 해를 도출하였다. 이는 제안 기법이 복잡한 제약 조건 하에서도 해의 품질과 실시간성을 동시에 확보하여 실제 생산 계획 시스템에 즉각 적용 가능한 효율적인 대안임을 입증한다.

4.3 제안 알고리즘 분석

본 절에서는 4.2절에서 입증된 정량적 성능 우위의 원인을 규명하기 위해 SAC-GWO의 탐색 과정에서 나타나는 수렴 특성과 내부 제어 파라미터의 동적 변화를 심층 분석한다. 이를 위해 최적화 난이도가 가장 높은 대형 실적 데이터셋(123 parts) 환경에서의 실험 데이터를 활용하였다.

4.3.1 수렴 곡선 분석

Fig. 3은 해당 인스턴스에 대한 주요 알고리즘들의 목적함수 값 변화 추이를 나타낸다. 비교군인 유전 알고리즘과 표준 GWO는 탐색 초기인 200회 반복 이내에 급격한 기울기로 수렴하는 경향을 보였으나 이후 그래프의 기울기가 소멸하며 4.6 부근의 지역 최적해에 조기 고착되는 한계를 드러냈다. 이는 대상 문제의 복잡한 기하학적 제약 조건으로 인해 탐색 초기에 군집의 다양성이 빠르게 상실되면서 탐색 능력이 저하되었기 때문으로 판단된다. 반면, 제안하는 SAC-GWO는 탐색 중반까지 비교군 대비 다소 완만한 수렴 속도를 유지하였다. 이는 알고리즘이 성급한 수렴을 지양하고 해 공간을 충분히 탐색하기 위해 의도된 전략이다. 이후 SAC-GWO는 400회와 900회 구간에서 계단식 성능 향상을 보이며 기존 알고리즘들의 수렴 한계를 돌파하였으며 최종적으로 1,000회 반복 시점까지 해의 개선을 지속하여 비교군 중 가장 우수한 해를 도출하였다.

Fig. 3

Comparison of convergence curves

4.3.2 적응형 파라미터 동적 분석

SAC-GWO가 보여준 후반부 수렴 성능 향상의 원인을 규명하기 위해 알고리즘의 탐색과 활용 균형을 결정하는 핵심 변수인 파라미터 a의 변화를 Fig. 4에 도시하였다. 반복 횟수에 따라 2에서 0으로 선형적으로 감소하는 표준 GWO와 달리 SAC-GWO의 적응형 파라미터는 탐색의 약 75% 구간 동안 최댓값인 2.0 수준에서 유지되는 양상을 보였다. 이는 별도의 인위적인 설정이 아닌 알고리즘 내부의 상태 인식 메커니즘이 작동한 결과이다. 구체적으로 본 문제는 해 공간이 협소하여 탐색 초반부터 개체 간 다양성 지표가 임계치를 하회하는 현상이 발생하였다. 이에 SAC-GWO는 이를 탐색 정체 상태로 진단하고 파라미터 a를 능동적으로 상향 조정하여 광역 탐색 단계를 자율적으로 연장하였다. 특히 Fig. 3의 400회 부근 해 개선은 파라미터 a의 수치 변화가 없는 구간일지라도 높은 탐색 강도가 유지됨에 따라 전역 탐색 능력이 보존되면서 새로운 유망 영역을 발견했기 때문에 나타나는 결과이다. 즉, 파라미터 a를 최댓값으로 유지하는 행위 자체가 조기 수렴을 방해하고 추가적인 해 개선 기회를 창출하는 명확한 인과관계를 갖는다. 이러한 작동 원리는 초반의 지역 해 쏠림 현상을 효과적으로 방지하였으며 충분한 탐색이 이루어진 750회 이후 파라미터가 감소하며 진행된 집중 탐색 단계에서 앞서 Fig. 3에서 확인된 최종적인 해 품질 향상을 견인한 주된 요인으로 작용하였다.

Fig. 4

Comparison of parameter a variations

4.4 요소별 유효성 검증

본 절에서는 제안하는 SAC-GWO의 핵심 전략들이 성능에 미치는 기여도를 검증한다. 실험은 합성 데이터셋 중 탐색 난이도가 가장 높은 case 3를 대상으로 100회 독립 시행하여 통계적 지표를 비교 분석하였다. 비교군은 표준 GWO를 기준으로 파라미터 제어 전략을 적용한 A-GWO, 카오스 맵을 적용한 C-GWO, 두 전략을 결합한 AC-GWO, 그리고 계층적 연산자까지 통합된 최종 모델인 SAC-GWO로 단계적으로 구성하였다. 평가지표로는 해의 품질을 나타내는 평균 비용과 알고리즘의 통계적 안정성을 나타내는 IQR을 사용하였다.

Table 5의 분석 결과, 각 요소의 역할은 명확히 구분된다. 파라미터 제어를 단독 적용한 A-GWO는 평균 비용이 3.77로 나타나 성능 개선은 미미했으나, IQR은 0.88에서 0.87로 소폭 감소하여 탐색 과정의 편차를 줄이고 안정성을 높이는 데 기여함을 확인하였다. 반면, 카오스 맵을 적용한 C-GWO는 평균값을 3.77에서 3.63으로 약 3.7% 낮추며 뚜렷한 성능 향상을 보였다. 이는 고밀도 환경에서 비선형적 난수 생성이 다양성 유지와 지역 최적해 탈출에 결정적 동력임을 시사한다.

Table 5

Component performance analysis

주목할 점은 두 전략이 결합된 AC-GWO의 성능이다. 해당 모델은 평균값의 추가 개선과 동시에 IQR을 0.76으로 유의미하게 감소시켰는데, 이는 카오스 맵의 탐색 능력과 적응형 파라미터의 안정성이 상호 보완적 시너지를 발휘했음을 입증한다. 최종적으로 계층적 연산자가 통합된 SAC-GWO는 표준 GWO 대비 약 4.2% 향상된 평균값 3.61과 최저 IQR인 0.76을 동시에 달성하며, 제안하는 세 가지 핵심 모듈이 대규모 네스팅 문제에서 최상의 효율과 강건성을 보장함을 정량적으로 입증하였다.

5. 결 론

본 연구에서는 조선소 마킹 경로 최적화 문제의 효율적 해결을 위해 상태 적응형 회색 늑대 최적화(SAC-GWO) 기법을 제안하였다. 제안 기법은 탐색 과정에서 군집의 다양성 상태를 실시간으로 진단하고 이에 따라 삽입 및 역전 연산자를 능동적으로 전환하는 이중 탐색 전략을 통해 기존 메타휴리스틱의 고질적인 문제인 조기 수렴과 탐색 정체 현상을 효과적으로 극복하였다.

대규모 가상 데이터셋 및 실제 조선소 실적 데이터를 활용한 실험 결과, SAC-GWO는 난이도가 높은 고밀도 네스팅 환경에서도 상용 최적화 도구인 gurobi가 도출한 기준 해의 품질에 근접하면서도, 현장 적용이 가능한 수준의 고품질 해를 현실적인 시간 내에 도출함으로써 그 실무적 유효성을 입증하였다. 특히 적응형 파라미터 제어와 카오스 이론의 결합은 복잡한 기하학적 제약 조건 하에서도 일관된 성능을 보장하는 핵심 기제로 작용함을 확인하였다.

본 연구는 생산 계획 시스템에 적용 가능한 고효율 알고리즘을 제시했다는 점에서 실무적 의의를 지니며 향후 연구에서는 순차형 설계 변수를 활용한 수리 모델의 개선을 통해 상용 솔버의 연산 효율을 제고하는 방안을 검토하고 경로 꼬임을 미세 보정하는 지역 탐색 기법을 추가하여 해의 정밀도를 더욱 개선할 계획이다.

Acknowledgments

본 연구는 다음의 지원을 받아 수행되었습니다.

(1) 정부(과학기술정보통신부)의 재원으로 한국연구재단의 지원 (RS-2025-00555741)

(2) 산업통상자원부의 재원으로 기술혁신사업의 지원 (RS-2025-02372996)

(3) 산업통상자원부와 한국산업기술진흥원(KIAT)의 지원 (국제공동기술개발사업 0022929, 산업혁신인재성장지원사업 RS-2025-02263945, RS-2023-KI002688)

(4) 해양수산부 재원으로 해양수산과학기술진흥원의 지원 (첨단선박 블루테크 인재양성 RS-2025-02221147)

References

• Bennell, J.A. and Oliveira, J.F., 2008. The geometry of nesting problems: A tutorial. European Journal of Operational Research, 184(2), pp.397-415. [https://doi.org/10.1016/j.ejor.2006.11.038]
• Blum, C. and Roli, A., 2003. Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys (CSUR), 35(3), pp.268-308. [https://doi.org/10.1145/937503.937505]
• Dewil, R., Vansteenwegen, P. and Cattrysse, D., 2016. A review of cutting path algorithms for laser cutters. The International Journal of Advanced Manufacturing Technology, 87(5), pp.1865-1884. [https://doi.org/10.1007/s00170-016-8609-1]
• Dewil, R., Vansteenwegen, P., Cattrysse, D., Laguna, M. and Vossen, T., 2015. An improvement heuristic framework for the laser cutting tool path problem. International Journal of Production Research, 53(6), pp.1761-1776. [https://doi.org/10.1080/00207543.2014.959268]
• Faris, H., Aljarah, I., Al-Betar, M.A. and Mirjalili, S., 2018. Grey wolf optimizer: a review of recent variants and applications. Neural Computing and Applications, 30(2), pp.413-435. [https://doi.org/10.1007/s00521-017-3272-5]
• Hajad, M., Tangwarodomnukun, V., Jaturanonda, C. and Dumkum, C., 2019. Laser cutting path optimization using simulated annealing with an adaptive large neighborhood search. The International Journal of Advanced Manufacturing Technology, 103(1), pp.781-792. [https://doi.org/10.1007/s00170-019-03569-6]
• Han, Y. and Jang, C., 2000. A study on the cutting path optimization using improved genetic algorithm. Journal of the Society of Naval Architects of Korea, 37(3), pp.90-98.
• Kohli, M. and Arora, S., 2018. Chaotic grey wolf optimization algorithm for constrained optimization problems. Journal of Computational Design and Engineering, 5(4), pp.458-472. [https://doi.org/10.1016/j.jcde.2017.02.005]
• Laporte, G., 1992. The traveling salesman problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(2), pp.231-247. [https://doi.org/10.1016/0377-2217(92)90138-Y]
• Lu, C., Gao, L., Li, X., Hu, C., Yan, X. and Gong, W., 2020. Chaotic-based grey wolf optimizer for numerical and engineering optimization problems. Memetic Computing, 12(4), pp.371-398. [https://doi.org/10.1007/s12293-020-00313-6]
• Mirjalili, S., Mirjalili, S.M. and Lewis, A., 2014. Grey wolf optimizer. Advances in Engineering Software, 69, pp.46-61. [https://doi.org/10.1016/j.advengsoft.2013.12.007]
• Qu, P. and Du, F., 2023. Improved particle swarm optimization for laser cutting path planning. IEEE Access, 11, pp.4574-4588. [https://doi.org/10.1109/ACCESS.2023.3236006]
• Wang, G.G. and Xie, S.Q., 2005. Optimal process planning for a combined punch-and-laser cutting machine using ant colony optimization. International Journal of Production Research, 43(11), pp.2195-2216. [https://doi.org/10.1080/00207540500070376]
• Zhang, T., Hu, H., Liang, Y., Liu, X., Rong, Y., Wu, C. and Huang, Y., 2024. A novel path planning approach to minimize machining time in laser machining of irregular micro-holes using adaptive discrete grey wolf optimizer. Computers & Industrial Engineering, 193, 110320. [https://doi.org/10.1016/j.cie.2024.110320]
• Zhu, C. and Tang, F., 2020. Laser processing path planning based on GA improved ACO. In 2020 12th International Conference on Measuring Technology and Mechatronics Automation (ICMTMA), IEEE, pp.80-84. [https://doi.org/10.1109/ICMTMA50254.2020.00026]