Journal Search Engine

ISSN : 2005-0461(Print)
ISSN : 2287-7975(Online)

Journal of Society of Korea Industrial and Systems Engineering Vol.49 No.3 pp.200-215
DOI : https://doi.org/10.11627/jksie.2026.49.3.200

A Self-Adaptive Genetic Algorithm for Assembly Line Balancing with Soft Constraints

Seong-Hoon Choi†

Department of Management Engineering, Sangmyung University

^† Corresponding Author: shchoi@smu.ac.kr

Received 26/08/2026 Finally Revised 16/09/2026 Accepted 16/09/2026

Abstract

Assembly line balancing with soft assignment constraints (AC) requires search methods that preserve feasibility while responding to managerial preferences. This study extends the previously developed GAsac (genetic algorithm for soft AC), which uses fixed crossover probability (Pc) and mutation probability (Pm), by proposing GAsam, a self-adaptive GA for generalized assembly line balancing problems. In GAsam, each task-priority chromosome carries its own Pc and Pm as strategy genes, allowing the solution and its parameter values to be inherited and varied together during the search.

The underlying representation, feasibility repair, improved workstation allocation, fitness evaluation, selection, and chromosome-level operators are retained. The baseline reimplemented in this study is denoted GAsac_new. A staged experimental framework examines parameter distributions, configures the self-adaptive mechanism, and evaluates the final algorithm across four benchmark datasets with ten AC environments each. In 2,400 main-experiment runs, GAsam matched or exceeded GAsac_new in dataset-level mean best attainment ratio (BestAR) on three benchmarks and achieved higher AC-level means in all ten environments of MUKHERJE, the realistic-scale benchmark considered in this study. However, GAsac_new achieved a higher dataset-level mean BestAR on SAWYER30, with statistically significant advantages in eight of the ten AC environments under dataset-wise Holm correction, indicating that the relative performance of the two algorithms depends on the problem setting. These results characterize the final GAsam design, including its parameter bounds; they do not isolate the effect of self-adaptation alone. The study contributes an individual-level joint adaptation mechanism for Pc and Pm and a transparent tuning and evaluation framework, providing an empirical basis for problem-aware parameter control in assembly line balancing.

Key Words : Assembly Line Balancing , Soft Constraints , Self-Adaptive Genetic Algorithm , Parameter Control

소프트 제약 조립라인 밸런싱을 위한 자기 적응형 유전 알고리즘

최성훈†

상명대학교 경영공학과

초록

키워드 :

This article has been cited by 0 article in crossref

Cited-By

Funding:

1. 서 론

1.1 연구 배경과 목적

조립라인 밸런싱 문제(assembly line balancing problem, ALBP)는 작업 간 선행관계와 작업장 용량 제약을 만족하면서 요소작업을 여러 작업장에 배정하는 대표적인 조합 최적화 문제이다. 전통적인 단순 조립라인 밸런싱 문제(simple assembly line balancing problem, SALBP)뿐만 아니라 실제 생산환경의 다양한 제약을 반영하는 일반 조립라인 밸런싱 문제(generalized assembly line balancing problem, GALBP)가 폭넓게 연구되어 왔으며, 문제 규모가 증가할수록 조합공간이 빠르게 확대되므로 휴리스틱이 중요한 해법으로 사용되고 있다[3, 5, 6, 7, 16].

실제 조립라인에서는 물리적으로 반드시 만족해야 하는 하드 제약 이외에도 특정 작업을 같은 작업장에 배치하거나 서로 떨어뜨리고 싶은 요구, 특정 작업장의 사용 선호 또는 회피와 같은 관리적 요구가 존재한다. Choi and Lee[9] 는 이러한 요구를 소프트 할당제약(assignment constraints, AC)으로 표현하고, 요소작업-요소작업 및 요소작업-작업장 관계행렬과 가중 충족도에 기초한 유전 알고리즘(genetic algorithm, GA), GAsac(GA for soft AC)을 제안하였다. GAsac은 SALBP의 목적 달성을 우선하면서 가능한 한 많은 소프트 제약을 충족하는 해를 탐색한다.

그러나 GAsac은 탐색 전 과정에서 고정된 교차확률(crossover probability, $P_{c}$ )과 돌연변이확률(mutation probability, $P_{m}$ ) 값을 적용한다. GA의 성능은 표현, 선택, 교차․돌연변이 연산자 및 제어 파라미터의 설계에 영향을 받을 수 있으며[10, 11, 15, 18], 고정 파라미터는 탐색 초기의 다양성 확보와 후기의 우수해 보존이라는 상이한 요구에 동일한 값을 적용한다는 한계를 가진다. 진화연산의 파라미터 제어(parameter control)는 결정론적(deterministic), 적응형(adaptive), 자기 적응형(self-adaptive) 방식으로 구분되며,자기 적응형 방식은 파라미터 자체를 개체의 유전정보에 포함하여 해와 함께 선택․상속․변이시키는 접근이다[2, 10]. ALBP 분야에서도 적응형 GA가 제안되어 왔지만[8, 20], 개체 수준의 $P_{c}$ 와 $P_{m}$ 을 함께 진화시키고 전략 파라미터 동역학을 단계적으로 확인한 연구는 상대적으로 제한적이다.

본 연구는 소프트 제약 GALBP를 위한 기존 GAsac을 확장하여 자기 적응형 유전 알고리즘, GAsam(GA with self-adaptation mechanism)을 제안한다. GAsam은 작업순서 유전자와 함께 개체별 $P_{c}$ 와 $P_{m}$ 을 보유하며, 동일한 선택․해 복구․적합도 구조 아래에서 전략 파라미터가 진화하도록 설계된다. 본 연구의 목적은 다음과 같다.

(1) 개체별 전략 파라미터의 표현, 상속 및 변이 규칙을 명확히 정의하여 자기 적응 메커니즘을 체계적으로 설계한다.
(2) 단계적 실험을 통하여 $P_{m}$ 의 자기 적응 메커니즘과 상위 운영 파라미터를 선정한다.
(3) 고정 파라미터 GAsac_new와의 직접 비교를 통해 해 품질과 강건성을 중심으로 최종 설계된 GAsam의 성능특성과 한계를 규명한다. 특히 전체 평균만으로 우열을 단정하지 않고 데이터 셋과 소프트 제약 환경에 따른 문제 의존성을 함께 평가한다.

1.2 연구의 차별성과 논문 구성

기존 적응형 GA는 외부 규칙이나 개체군(population) 통계에 따라 $P_{c}$ 와 $P_{m}$ 을 조정하는 경우가 많은 반면[8, 17, 20], 본 연구의 GAsam은 $P_{c}$ 와 $P_{m}$ 을 개체의 전략 유전자로 직접 보유하여 해와 함께 선택되도록 한다. 기존 GAsac의 작업 우선순위 표현, 소프트 제약 적합도, 토너먼트 선택, 부분사상교차(partially mapped crossover, PMX), 가능해 복구 및 개선된 작업장 할당법을 유지하면서 전략 유전자의 상속․변이를 추가하였다. 본 연구에서 재구현한 고정 파라미터 알고리즘을 GAsac_new, 선행연구의 게재 결과를 GAsac_old로 구분한다. 본 비교는 선행연구의 고정 $P_{c}$ ․ $P_{m}$ 을 계승한 GAsac_new와 최종 설계된 GAsam을 공통 운영조건에서 평가하며, 성능 차이를 파라미터 제어 방식과 허용범위를 포함한 설계의 종합적 차이로 해석한다.

논문의 구성은 다음과 같다. 제2장에서는 소프트 제약을 고려한 ALBP 모형과 관련 연구 개요에서 본 연구의 위치를 정리한다. 제3장에서는 기존 GAsac의 서술 흐름과 대응되도록 GAsam의 염색체(chromosome), 가능해 복구,적합도, 유전연산 및 자기 적응형 파라미터 갱신을 단계별로 기술한다. 다음으로 제4장에서는 테스트 문제와 전체 실험 구조를 먼저 제시한 뒤, 전략 파라미터 동역학 확인, $P_{m}$ 메커니즘 및 상위 운영 파라미터의 두 단계 튜닝, 그리고 GAsam 성능평가 실험이 이루어진다. 끝으로 제5장에 서는 결론과 향후 연구과제를 제시한다.

2. 소프트 제약을 고려한 ALBP 모형 및 관련 연구 개요

2.1 관련 연구와 본 연구의 위치

ALBP 연구는 단순 문제의 최적해법에서 현실적 제약과 다목적성을 포함하는 GALBP로 확장되어 왔다[5, 6, 7].GA는 순열 표현(permutation representation)과 문제 특화 디코딩(problem-specific decoding)을 결합하기 용이하여 다양한 ALBP에 적용되었으며[15, 18], 실제 성능은 개체군 크기(population size, Pop.Size), 연산자 및 제어확률의 설정에 영향을 받는다. 본 연구는 작업 우선순위의 순열과 연속형 $P_{c}$ ․ $P_{m}$ 전략 유전자를 하나의 개체에 결합하고,개체군의 선택․교차․상속․변이를 통해 해와 전략값을 함께 진화시키기 위해 GA를 채택하였다. 또한 GAsac의 평가․복구․할당 구조를 계승하여 공통 해법구조 안에서 자기 적응형 설계를 비교할 수 있다는 점을 고려하였다. 이는 GA가 다른 메타휴리스틱보다 보편적으로 우수하다는 의미는 아니다.

최근 라인 밸런싱 연구는 공정계획․인력계획․자원일정계획 등과 결합된 문제로 확장되고 있으며[4], GA 기반 연구도 작업장 수, 사이클 타임 및 작업부하 평활화와 같은 복수 목적을 함께 다루는 방향으로 발전하고 있다[13].이러한 연구는 ALBP에 대한 진화연산의 적용범위를 넓혔지만, 소프트 할당제약 GALBP에서 개체별 $P_{c}$ 와 $P_{m}$ 을 전략 유전자로 함께 진화시키고 그 동역학과 성능을 단계적으로 검토하는 본 연구와는 초점이 다르다.

기존 GAsac은 다양한 예비 실험을 통해 고정 $P_{c}$ =0.40 과 $P_{m}$ =0.50을 선정하였다[9]. 본 연구는 이를 선행연구에 근거한 기준 설정으로 계승하였다. 여기서 $P_{m}$ 은 개체의 작업부에 RE 돌연변이를 적용할 확률이므로, 각 유전자를 50%의 확률로 변이시키는 의미와는 다르다. 선행연구에는 $P_{c}$ ․ $P_{m}$ 탐색 조합과 조합별 성능이 상세히 제시되어 있지 않으므로, 해당 값이 본 연구의 운영조건에서도 최적이라고 주장하지 않는다. 이번 연구에서는 고정 $P_{c}$ ․ $P_{m}$ 의 추가 격자 탐색(grid search)이나 민감도 실험을 수행하지 않았으며, GAsam이 다른 허용범위에서 개체별 파라미터를 진화시킨 결과를 기준 설정과 비교한다.

SALBP와 GALBP의 차이는 단순히 제약식의 수가 증가하는 데 있지 않다. GALBP에서는 작업장 설비, 작업자, 구역 제약(zoning), 작업 적합성(task compatibility)과 같은 현실적 조건이 해의 가능성과 목적함수에 동시에 영향을 줄 수 있으므로, 해 표현과 디코딩은 문제구조를 안정적으로 보존해야 한다[6, 7]. 본 연구의 소프트 제약은 물리적가능성을 훼손하지 않으면서 관리적 선호의 만족도를 목적함수의 후순위 기준으로 평가한다는 점에서 이러한 일반화된 틀의 한 형태이다[9].

GA의 파라미터 제어 관점에서도 적응형과 자기 적응형은 구분할 필요가 있다. Srinivas and Patnaik[17] 의 적응형 GA는 적합도 상태를 관찰하여 $P_{c}$ 와 $P_{m}$ 을 외부 규칙으로 변화시키는 대표적 접근인 반면, Eiben et al.[10] 의 분류에서 자기 적응은 전략 파라미터가 염색체에 포함되어 선택과 변이 연산의 직접적인 대상이 되는 경우를 의미한다. 본 연구는 후자의 정의를 채택하되, 순열형 염색체에 연속형 전략 유전자를 결합하는 혼합 표현(hybrid representation)을 사용한다. 따라서 전략 유전자의 상속과 돌연변이 설계 자체가 알고리즘의 중요한 구성요소가 된다.

다른 접근으로는 여러 부분해 제거․재구성 연산자의 활용을 탐색 성과에 따라 조정하는 적응형 대규모 이웃탐색(adaptive large neighborhood search, ALNS)이 있다. Ropke and Pisinger[14] 는 수거․배송 문제에서 이러한 방법을 제시하였다. 해당 연구는 소프트 제약 GALBP에서의 우열을 입증하는 근거는 아니지만, 문제 특성에 맞춘 제거․재구성 연산자를 설계하여 GAsam과 비교할 수 있는 방법론적 대안이다. 본 연구는 개체 수준의 $P_{c}$ ․ $P_{m}$ 공동 자기 적응 설계에 초점을 두며, 다른 메타휴리스틱과의 직접 비교는 향후 연구과제로 둔다.

2.2 하드 제약과 소프트 할당제약

본 연구의 문제 구조는 Choi and Lee[9] 의 소프트 제약 GALBP를 따른다. 모든 해는 먼저(i) 각 작업의 단일 작업장 할당, (ii) 선행관계 보존, (iii) 작업장 부하의 사이클 타임 제한이라는 SALBP 하드 제약을 만족해야 한다. 그 위에서 관리적 선호는 소프트 제약으로 평가한다. 요소작업-요소작업 관계행렬은 친밀/비친밀(compatible/ incompatible) 작업, 최소거리 및 최대거리와 같은 작업 간 관계를 나타내고, 요소작업-작업장 관계행렬은 특정 작업장의 배치 선호 또는 회피를 표현한다. 소프트 할당제약의 5개 범주와 표현 방식을 정리하면 <Table 1>과 같다.

자동차 조립라인에서는 공구의 이동과 준비를 줄이기 위해 동일한 공구를 사용하는 작업을 같은 작업장에 배치하려는 요구를 친밀 제약으로 표현할 수 있다. 가전 조립라인에서는 작업 간 간섭을 줄이기 위해 일부 작업의 분산을 선호하는 요구를 비친밀 또는 최소거리 제약으로, 전자 조립라인에서는 부품 장착과 후속 검사 사이의 이동을 줄이려는 요구를 최대거리 제약으로 표현할 수 있다. 작업 편의와 자재 공급 여건에 따른 특정 작업장의 선호․회피도 작업장 관련 제약으로 나타낼 수 있다. 관리자는 이러한 선호의 상대적 중요도를 가중치로 부여하여 배치 대안의 충족 수준을 비교할 수 있다. GAsam은 하드 제약을 만족하고 작업장 수의 최소화를 우선하는 범위에서 소프트 제약 충족도가 높은 배치를 탐색하여 신규 라인의 설계와 기존 라인의 작업 재배치를 지원할 수 있다. 위 사례는 적용 가능성을 설명하는 예시이며 실제 산업 실증 결과가 아니다. 안전이나 필수 설비 등 반드시 지켜야 하는 조건은 소프트 제약으로 대체하지 않는다.

소프트 제약 $h$ 의 가중치를 $w_{h}$ 라 하고, 해 $E_{k}$ 가 해당 제약을 만족하는지 나타내는 지시함수를 $I_{h} (E_{k})$ 라 하면, 해의 가중 충족도 $a_{k}$ 는 다음과 같이 식 (1)로 표현할 수 있다.

a_{k} = \sum_{h \in H} w_{h} I_{h} (E_{k})

(1)

해의 소프트 제약 달성 정도를 정규화하고 서로 다른 AC 집합 간의 결과를 비교하기 위해, 모든 소프트 제약을 만족한다고 가정한 이론적 최대 가중치 합을 $a_{T}$ 라 하고 달성률(attainment ratio, AR)을 다음과 같이 식(2)로 정의한다.

{AR}_{k} = 100 \times \frac{a_{k}}{a_{T}} (%)

(2)

동일 AC에서는 $a_{T}$ 가 상수이므로 $a_{k}$ 와 ${AR}_{k}$ 는 동일한 해 순위를 제공한다. 따라서 알고리즘 내부의 적합도 평가는 기존 GAsac과의 일관성을 위해 $a_{k}$ 를 사용하고, 서로 다른 AC 및 데이터 셋의 결과 보고와 통계분석에는 정규화된 AR을 사용한다.

2.3 적합도와 비교 지표

ALBP의 대표적인 목적에는 주어진 작업장 수에서 사이클 타임을 최소화하는 경우와, 주어진 사이클 타임에서 작업장 수를 최소화하는 경우가 있다[6, 9]. 본 연구에서는 Choi and Lee[9] 의 실험 설정을 계승하여 주어진 사이클 타임에서 작업장 수를 최소화하는 문제를 대상으로 한다. 이에 따라 본 연구의 적합도는 기본 ALBP 목적에 큰 우선 가중치를 부여하고 소프트 제약 충족도를 후순위로 반영하는 구조이다. 해 $E_{k}$ 의 사용 작업장 수를 $n_{k}$ 라 하면 기본 형태는 식(3)과 같다.

f_{k} = β n_{k} - a_{k}, β > \max_{e \in E} a_{T, e}

(3)

본 실험의 40개 AC 환경으로 이루어진 집합을 ℰ, 환경 e의 총 소프트 제약 가중치를 $a_{T,e}$ 라 하면, 해당 환경에서 0≤ $a_{k}$ ≤ $a_{T,e}$ 이다. 따라서 식(3)의 최댓값은 40개 환경에 대한 가중치 합의 최댓값을 의미한다. 실제 가중치와 AC 입력자료를 대조한 결과 데이터 셋별 최댓값은 MANSOOR 5.51, SAWYER30 9.95, WARNECKE 19.02, MUKHERJE 35.26이었다. 전체 최댓값은 MUKHERJE_AC05의 35.26 이므로, 선행연구에서 계승한 $β = 100$ 은 우선순위 조건을 충족한다. 작업장이 하나 증가할 때의 불이익을 소프트 제약 충족점수의 증가로 상쇄할 수 없으며, 작업장 수가 동일한 해 사이에서는 $a_{k}$ 가 큰 해를 우선한다. 본 실험에서는 평활화 보상항을 사용하지 않아 코드의 적합도도 식(3)과 일치한다. 이는 적합도의 평가 우선순위에 관한 설명이며, 모든 실행에서 전역 최소 작업장 수를 얻었음을 의미하지는 않는다.

주 성능지표는 각 독립 실행에서 얻은 최선 달성률(best attainment ratio, BestAR)이며, 30회 BestAR의 반복(run) 간 표준편차(run-to-run standard deviation, SDrun)와 10번째 백분위수(10th percentile, P10)를 하방 안정성 지표로 사용하였다. 각 반복 종료 개체군 내부의 AR 표준편차(SdAR)는 SDrun과 구분하여 해석하였다.

3. 자기 적응형 유전 알고리즘(GAsam)

본 장의 서술 순서는 기존 GAsac의 알고리즘 설명[9] 과 직접 비교할 수 있도록 해 표현과 초기화, 적합도 및 가능해 복구, 선택․교차․돌연변이, 자기 적응 파라미터 갱신, 종료 절차의 순서로 구성하였다. GAsam의 핵심적인 추가 요소는 개체가 해 유전자뿐만 아니라 자신의 $P_{c}$ 와 $P_{m}$ 을 전략 유전자로 함께 보유한다는 점이다.

3.1 염색체 표현과 초기집단

GAsam의 개체 i는 $ξ_{i}$ =( $π_{i}$ , $P_{c, i}$ , $P_{m, i}$ )로 표현된다. $π_{i}$ 는 요소작업의 우선순위를 나타내는 순열형 작업부이며, $P_{c, i}$ 와 $P_{m, i}$ 는 해당 개체가 유전연산에 참여할 확률을 나타내는 실수형 전략 유전자이다. GAsam에서 각 개체의 초기 $P_{c}$ 는 U(0.5, 1.0)에서, 초기 $P_{m}$ 은 U(0.01, $PmInitMax$ )에서 독립적으로 생성한다( $P_{m}$ InitMax는 $P_{m}$ 의 초기 상한값을 의미함). 초기 $P_{c}$ 범위는 3.4절에서 설명한 사전 설계값을 사용한다. 예비 실험을 통해 $PmInitMax$ =0.30으로 선정하였으므로, 본 실험에서는 초기 $P_{m}$ 을 U(0.01, 0.30)에서 생성하였다(4.2.1절 참조).

본 실험의 Pop.Size는 350이며(4.2.2절 참조), 초기집단의 2%에는 SALBP에서 얻은 우수해를 시드(seed)로 삽입하고, 나머지는 현재 선행작업이 모두 해제된 후보 집합에 서 작업을 무작위 선택하는 위상정렬 기반 방식으로 생성하였다. 이 구성은 기존 GAsac[9] 과 동일한 해 생성 기반을 유지하면서 전략 유전자만 추가하기 위한 것이다.

3.2 가능해 복구와 적합도 평가

교차 또는 돌연변이 후의 작업 우선순위는 선행관계를 직접 만족하지 않을 수 있으므로 기존 GAsac과 동일한 재배열․복구(rearranging/repair) 절차를 사용한다[9]. 현재 배치 가능한 작업 집합 중 원래 순열에서 가장 앞선 작업을 반복 선택하여 선행관계를 만족하는 순서로 복구한다. 이후 선행연구의 개선된 작업장 할당법을 GAsac_new와 GAsam에 공통으로 적용한다. 현재 작업을 잔여시간 때문에 해당 작업장에 배치할 수 없으면, 순서상 뒤따르는 두 작업을 대상으로 선행관계와 잔여시간 조건을 확인하여 먼저 배치할 수 있는 작업을 검토한다. 이미 배치된 작업은 후속 순회에서 제외한다. 두 알고리즘의 작업장 할당 절차는 동일하며, 본 실험은 네 데이터 셋 모두 이 개선된 할당법을 사용하는 문제 유형 3으로 설정하였다. 할당 결과에 대해 식(1)의 충족도와 식(3)의 적합도를 계산하므로, 해 복구․작업 할당․적합도 평가의 차이가 비교에 영향을 주지 않도록 하였다.

3.3 선택과 작업부 유전연산자

선택에는 두 개체를 무작위 추출하여 더 작은 적합도 값을 갖는 개체를 선택하는 이진 토너먼트 선택(binary tournament selection)을 사용한다. 교차는 순열형 표현에 적합한 부분사상교차(partially mapped crossover, PMX)를 적용하며[9, 11, 12], GAsac_new에서는 고정 $P_{c}$ =0.40,GAsam에서는 각 개체의 $P_{c, i}$ 가 교차 후보 여부를 결정한다. 본 실험의 작업부 돌연변이는 상호교환 돌연변이(reciprocal exchange, RE)이며, GAsac_new는 고정 $P_{m}$ =0.50, GAsam은 개체별 $P_{m, i}$ 를 사용한다. 매 세대의 최우수 개체는 엘리트 보존(elitism) 방식으로 유지한다.

본 연구의 $P_{m}$ 은 개체별로 작업부 돌연변이의 수행 여부를 결정하는 확률이다. 돌연변이가 선택된 개체에서는 서로 다른 두 위치를 무작위로 선택하여 작업 순서를 교환한다. 따라서 GAsac_new의 $P_{m}$ =0.50은 작업부를 구성하는 각 유전자에 0.50의 확률을 독립적으로 적용한다는 의미가 아니다.

구현에서는 토너먼트 선택 시 작업부 염색체와 개체별 $P_{c}$ 및 $P_{m}$ 전략 유전자를 함께 복사한다. 교차 단계에서는 각 개체마다 독립적인 균등난수를 생성하여 그 값이 해당 개체의 $P_{c, i}$ 이하이면 교차 후보로 포함한다. 후보 수가 홀수이면 후보목록의 마지막 개체를 그 세대의 교차에서 제외하고, 나머지 후보는 현재 개체군 인덱스 순서대로 두개체씩 짝지어 PMX를 수행한다. 교차가 수행된 쌍의 $P_{c}$ 는 두 부모 값의 산술평균으로 상속되고, $P_{m}$ 은 4.2.1절에 서 선정한 상속규칙을 따른다. 교차 후보가 아니거나 홀수 후보로 제외된 개체는 교차 단계에서는 선택 직후의 작업부와 전략 유전자 값을 유지한다. 이후 돌연변이 단계에서는 모든 개체를 순회하여 개체별 $P_{m, i}$ 에 따라 작업부 돌연변이를 적용하고, 작업부 돌연변이 또는 교차 수행 여부와 관계없이 모든 개체의 $P_{c}$ 와 $P_{m}$ 전략 유전자에 각각 식(4)와 식(5)~(6)의 변이를 적용한다. 따라서 그 세대에 교차하지 않은 개체의 전략 유전자도 다음 세대로 그대로 고정되는 것이 아니라 계속 진화한다. 이와 같이 개체별 $P_{c}$ 가 해당 개체의 교차 참여빈도에 직접 영향을 미치게 함으로 써, 교차 참여전략 자체가 작업순서 해 구조와 함께 선택되도록 하였다.

3.4 전략 유전자의 자기 적응

PMX가 수행된 두 부모의 $P_{c}$ 는 산술평균하여 두 자손에 상속한다. $P_{m}$ 의 상속 방식은 예비 실험에서 세 가지 방법을 비교하였으며, 최종적으로 두 부모 $P_{m}$ 의 산술평균을 사용하는 평균 상속(average inheritance)을 선택하였다(4.2.1절 참조). 자기 적응형 진화연산에서는 전략 파라미터를 해의 유전정보와 함께 상속․변이시켜 탐색 과정에서 진화하도록 할 수 있다[2, 10]. 본 연구에서는 이러한 원리에 따라 $P_{c}$ 와 $P_{m}$ 에 서로 다른 전략 파라미터 변이 규칙을 적용하였다.

$P_{c}$ 에는 식(4)의 가산형 가우시안 교란(Gaussian perturbation)을 적용하고, 실행 중 허용범위를 [0.40, 1.00]으로 제한하였다. 가우시안 교란은 현재 전략값 주변에서 확률적으로 작은 변화를 발생시켜 전략 파라미터가 해와 함께 진화하도록 하는 자기 적응의 기본 원리와 부합한다[2, 10]. 이제 $clip (x, L, U)$ 를 범위를 벗어난 값만 경계값으로 제한하는 함수, 즉 $\min {\max (x, L), U}$ 라고 할 때,

P_{c, i}^{'} = clip (P_{c, i} + N (0, {0.05}^{2}), 0.40, 1.00)

(4)

식(4)의 수치는 별도 요인 실험으로 최적화한 값이 아니라 문헌의 자기 적응 원리[2, 10] 와 기존 GAsac[9] 을 기준으로 정한 사전 설계값이다. 정규분포는 N(평균, 분산)으로 표기하므로 $N (0, {0.05}^{2})$ 의 표준편차는 0.05이다. 평균 0은 변이 방향에 편향을 두지 않기 위한 것이며, 표준편차 0.05는 초기 $P_{c}$ 구간 [0.5, 1.0] 폭의 10%로서 국소적 전이를 유도하도록 정하였다. 하한 0.40은 기존 GAsac의 고정 $P_{c}$ =0.40과 일치시키고[9], 상한 1.00은 확률의 자연적 최대값으로 두었다. 이 값들의 통계적 최적성은 주장하지 않으며, 주어진 갱신 규칙 아래에서의 전략값 분포 변화는 4.1절에서 관찰하였다.

$P_{c}$ 와 $P_{m}$ 은 모두 GA의 탐색 거동에 영향을 주므로 $P_{m}$ 이 보편적으로 더 중요하다고 단정하지 않는다. 그러나 돌연변이는 기존 해에 새로운 순열 변화를 직접 유입하여 탐색 다양성을 회복하는 연산이며[2, 11], ALBP 연구에서도 교차․돌연변이 연산자와 제어값은 주요 문제 특화 설계 요소로 다루어져 왔다[15, 18]. 따라서 본 연구에서는 ALBP의 순열형 탐색에서 다양성 유지에 직접 관여하는 역할과 GAsam의 $P_{m}$ 메커니즘이 초기․실행 중 상한, 변동폭 및 상속 방식 등 더 많은 설계 자유도를 갖는다는 점을 함께 고려하여, $P_{m}$ 을 $P_{c}$ 보다 우선적인 튜닝 대상으로 두었다. $P_{m}$ 은 경계 부근의 비대칭과 범위 이탈을 줄이기 위해 로짓 척도(logit scale)에서 변이시킨다. $P_{\min} = 0.005$ , $P_{\max} = 0.30$ 일 때 $q_{i} = \frac{P_{m, i} - P_{\min}}{P_{\max} - P_{\min}}$ , $z_{i} = \log (\frac{q_{i}}{1 - q_{i}})$ 로 두고 식(5)~(6)을 적용한다.

z_{i}^{'} = z_{i} + N (0, {σ_{p m}}^{2}), σ_{p m} = 0.02

(5)

P_{m, i}^{'} = P_{\min} + \frac{P_{\max} - P_{\min}}{1 + \exp (- z_{i}^{'})}

(6)

식(5)의 $σ_{p m}$ =0.02는 로짓 척도에서 적용하는 가우시안 변동의 표준편차이며, 분포의 두 번째 인자는 분산 $σ_{pm}^{2}$ 이다.

자기 적응은 전략 파라미터의 사전 설정을 완전히 제거하는 것이 아니며[2, 10], 본 연구는 계산비용을 고려하여 튜닝 범위를 제한하였다. $P_{m}$ 메커니즘에서도 모든 상위 설계값을 요인화한 것은 아니며, 초기 하한 0.01과 실행 중 하한 0.005는 사전 설계값으로 유지하였다. 초기 하한 0.01은 작업부 돌연변이가 완전히 배제되지 않도록 하는 사전 설계값으로 두었다. 실행 중 하한 0.005는 초기 하한보다 더 낮은 탐색강도까지 자기 적응이 가능하도록 하면서도 $P_{m}$ =0이 되지 않게 하는 경계값으로 설정하였다. 이 두 하한값의 통계적 최적성을 주장하지는 않는다. $P_{m}$ 선별 실험만으로도 3×3×2×3=54개 조합, 54×10 AC×10회=5,400회가 필요하였다. ALBP의 선행 GA 연구에서도 모든 요인을 동시에 탐색하기보다 계산 부담을 줄이기 위해 일부 제어값을 파일럿 결과에 근거하여 고정한 사례가 있다. Sabuncuoglu et al.[15] 은 추가 계산시간을 줄이기 위해 파일럿 실행 결과에 따라 $P_{m}$ 을 0.05로 고정한 뒤 다른 요인을 분석하였다. 이는 식(4)의 $P_{c}$ 수치를 직접 정당화하는 근거가 아니라, 계산 가능한 실험범위를 위해 일부 설계값을 사전 고정하는 실험설계의 선행 사례로 사용하였다. 여기에 식(4)의 가우시안 교란 표준편차를 세 수준으로 변화시키는 요인까지 추가한다고 가정하면, 162개 조합, 16,200회가 필요하며, 실행 중 $P_{c}$ 하한까지 세 수준으로 요인화 하면 486개 조합, 48,600회로 증가한다. 따라서식(4)의 $P_{c}$ 설정은 사전 설계값으로 유지하고, 상대적으로 설계 자유도가 큰 $P_{m}$ 메커니즘을 4.2.1절에서 집중 튜닝하였다. 이는 $P_{c}$ 의 중요성이 낮거나 식(4)의 값이 최적 임을 의미하지 않고, 실험범위를 단계적으로 통제한 연구 설계상의 선택이다.

3.5 알고리즘 절차와 종료

각 독립 실행에서 초기 개체군을 생성한 직후 전체 개체를 평가하여 최우수해(elite)를 등록한다. 이후 세대별로 가능해 복구와 적합도 평가, 최우수해 갱신, 토너먼트 선택, 개체별 $P_{c}$ 에 의한 PMX, 개체별 $P_{m}$ 에 의한 RE, 전략 유전자 변이 및 엘리트 보존을 반복한다. 최우수해가 갱신된 이후 연속하여 미개선 종료규칙(no-improvement stopping rule, StopRule)에서 정한 세대 수만큼 추가 개선이 없으면 탐색을 종료한다. 본 실험에서는 StopRule=4,000을 적용하였다(4.2.2절 참조). 최대 세대수 20,000은 안전 상한(soft cap)으로 두고 두 알고리즘에 동일하게 적용하였다. 두 알고리즘의 주요 공통점과 차이점은 <Table 2>에, GAsam의 세대별 진행 절차는 <Table 3>에 정리하였다.

<Table 2>에서 알 수 있듯이 GAsac_new는 $P_{c}$ =0.40과 $P_{m}$ =0.50을 고정하고, GAsam은 개체별 자기 적응 $P_{c}$ 와 $P_{m}$ 을 사용한다. 본 비교에서는 Pop.Size, StopRule, 선택,PMX/RE, 가능해 복구, 개선된 작업장 할당, 적합도 평가 및 엘리트 보존을 동일하게 통제하였다.

4. GAsam 성능평가 실험

GAsam의 성능평가를 위해서 Choi and Lee[9] 의 실험문제 구성을 계승하여 벤치마크 문제 4개, MANSOOR, SAWYER30, WARNECKE, 그리고 MUKHERJE를 사용하였다. 각 문제의 요소작업 수는 각각 11, 30, 58, 그리고 94개이다. 이 가운데 MUKHERJE는 나머지 세 데이터 셋보다 규모가 크며, 본 연구에서는 현실에 준하는 규모의 벤치마크 문제로 해석하였다. 각 벤치마크에는 AC01~AC10의 10개 소프트 할당제약 환경을 구성하였고, 작업의 약 30%에 친밀/비친밀 관계, 약 10%에 최소/최대 거리 관계, 작업장 관련 관계에는 약 15%의 선호․회피 제약을 부여하였다. 불가능하거나 의미 없는 제약 생성을 줄이기 위해 사이클 타임과 선행관계 아래에서 각 작업의 할당가능 작업장 범위를 고려하였다[9].

모든 신규 실험은 12th Gen Intel(R) Core(TM) i7-1260P (2.10 GHz)와 PyPy 3.11 환경에서 수행하였다. PyPy는 적시(just-in-time, JIT) 컴파일을 지원하는 파이썬 구현으로, 반복 연산이 많은 본 GA 구현의 실행환경으로 채택하였다[19].전체 실험은 전략 파라미터 분포 변화에 대한 예비 관찰, $P_{m}$ 메커니즘과 운영 파라미터에 대한 두 차례의 단계적 튜닝, 그리고 GAsac_new-GAsam 직접 비교의 순서로 구성하였다. 각 단계의 데이터 셋, 실험규모, 목적과 최종 산출물을 요약하면 <Table 4>와 같다.

4.1 전략 파라미터 분포 변화에 대한 예비 관찰

본격적인 파라미터 튜닝에 앞서 설계된 전략 유전자 갱신 아래에서 파라미터 분포가 세대에 따라 어떻게 변화하는지를 기술적으로 관찰하기 위한 예비 실험을 수행하였다. 네 데이터 셋의 AC01~AC10에 대해 각 5회, 총 200회 독립 실행하였다. 이 실험은 $PmInitMax$ =0.20 조건에서 수행된 전략 파라미터 분포 변화 관찰용 예비 실험이며, 최종 GAsac_new-GAsam 효과를 추정하는 본 실험과 구분한다. 또한 이 절의 목적은 사전 설계한 $P_{c}$ 갱신 규칙 아래에 서 나타나는 전략 파라미터 분포의 변화 양상을 기술하는 데 있다. 이러한 관찰만으로 자기 적응의 작동기제나 성능 효과를 인과적으로 검증하지 않으며, $P_{c}$ 관련 설계값의 최적성을 비교하는 튜닝 실험도 아니다. 동일 데이터 셋의 50회 실행에서 1세대와 4,000세대의 개체군 평균 $P_{m}$ (AvgPm), 평균 $P_{c}$ (AvgPc), $P_{m}$ 표준편차(SdPm) 및 $P_{c}$ 표준편차(SdPc)를 비교하였다.

AvgPm은 네 데이터 셋 모두에서 감소했으며 Wilcoxon 부호순위검정에서도 모두 유의하였다. 감소폭은 SAWYER30, WARNECKE 및 MUKHERJE에서 약 31~34%였다. AvgPc는 MANSOOR에서는 거의 유지되어 유의하지 않았으나, 나머지 세 데이터 셋에서는 4.6~8.4% 감소했고 그 변화가 유의하였다. SdPm과 SdPc는 모든 데이터 셋에서 약 30% 이상 유의하게 감소하였다. 이 결과는 주어진 갱신 규칙 아래에서 세대가 진행되며 파라미터 분포가 변화한 관찰 사실을 보여준다. 다만 평균상속 자체가 분산 축소에 기여할 수 있으므로, 이러한 변화만으로 선택에 의한 전략 학습, 자기 적응의 성공 또는 성능 향상에 대한 인과적 증거 가 성립하지는 않는다. 따라서 최종 성능은 별도의 직접 비교 실험으로 평가하였다. 주요 변화량과 통계적 검정 결과를 요약하여 정리한 것이 <Table 5>이다.

그리고 세대별 AvgPm의 변화 양상은 <Figure 1>에 제시하였다. 그래프에서 각 곡선은 10개 AC와 5회 반복으로 구성된 50개 실행의 평균이며, 회색 띠는 제10~제90백분위수 범위를 나타낸다.

4.2 단계적 파라미터 튜닝

자기 적응형 GA도 전략 유전자의 허용범위와 반응성을 정하는 상위 설계값이 필요하므로[10], 본 연구는 모든 상위 설계값을 동시에 튜닝하지 않았다. 식(4)의 $P_{c}$ 갱신 관련 값은 3.4절의 근거에 따라 사전 설계값으로 유지하였다. 선별(screening)-확인(confirmation)의 2단계 구조를 두 차례 적용하여, 1차 예비 실험에서는 $P_{m}$ 자기 적응 메커니즘의 주요 설계값을, 2차 예비 실험에서는 Pop. Size와 StopRule을 결정하였다. 두 실험 모두 평균 BestAR를 최우선으로 하고 AC별상대순위, 최대 후회값(maximum regret, MaxRegret), P10과 계산비용을 순차적으로 검토하였다.

4.2.1 예비 실험 1차: 자기 적응 $P_{m}$ 메커니즘 튜닝

1단계 선별 실험은 WARNECKE에서 수행하였다. 실험인자는 $σ_{p m}$ ={0.02, 0.04, 0.06}, 실행 중 $P_{m}$ 상한( $PmRunMax$ )={0.30, 0.40, 0.50}, 초기 $P_{m}$ 상한( $PmInitMax$ )={0.20, 0.30}, 상속 방식={평균, 우수 부모, 무작위 부모}의 3×3×2×3=54개 조합으로 구성하였다. 각조합을 AC01~AC10에서 10회 독립 반복하여 총 5,400회를 분석하였고, Pop.Size=200과 StopRule=2,500은 대표 수준으로 고정하였다. 각 AC를 서로 다른 문제 환경으로 구분하여 평균/중앙값 BestAR, 반복 간 표준편차(SD_run), 변동계수(coefficient of variation, CVrun), P10/P90, 개체군 내부 SdAR과 CPU 시간을 집계하고, 요인효과․교호작용과 Pareto 구조를 이용하여 확인 실험 후보를 선별하였다.

선별 결과, 평균 상속은 다른 상속 방식에 비해 전반적으로 우수한 성능을 보였으며, 평균 상속 조건에서는 $PmInitMax$ =0.30이 0.20보다 유리하였다. 반면 $σ_{p m}$ 과 $P_{m}$ RunMax는 일부 AC에서 주효과 및 교호작용이 남아 있어 특정 수준으로 조기에 고정하지 않았다. 이에 따라 평균 상속과 $PmInitMax$ =0.30을 고정하고, $σ_{p m}$ ={0.02,0.04, 0.06}과 $PmRunMax$ ={0.30, 0.40, 0.50}을 완전히 교차한 3×3 축소 완전요인설계를 구성하여 9개 조합을 확인 실험 후보로 선정하였다.

2단계에서는 규모가 가장 큰 네 번째 벤치마크 문제인 MUKHERJE에서 선별된 9개 후보를 AC01~AC10별로 각각 30회 반복하여 총 2,700회로 비교하였다. 후보는 평균 BestAR를 최우선 기준으로 두고 평균순위(average rank, AvgRank), MaxRegret 및 하방 성능을 함께 평가하였으며, 계산시간은 보조적인 구현 지표로만 참고하였다. 그 결과 C01( $σ_{p m}$ =0.02, $PmRunMax$ =0.30, $PmInitMax$ =0.30, 평균 상속)이 평균 BestAR 61.9372%, MaxRegret 2.4582 퍼센트 포인트(percentage points,%p)로 최종 선정되었다. 후보 간 Friedman 검정은 p=0.0811로 전역 차이를 명확히 검출하지 못했으므로, 이 선정은 모든 후보에 대한 통계적 우월성 주장이 아니라 사전에 정한 성능․강건성 우선 규칙에 근거한다.

4.2.2 예비 실험 2차: Pop.Size와 StopRule 튜닝

1단계에서는 $P_{m}$ 메커니즘을 C01로 고정하고 WARNECKE 에서 Pop.Size={100, 150, 200, 250, 300, 350}와 StopRule={1,500, 2,000, 2,500, 3,000, 3,500, 4,000}의 6×6 완전요인설계(full factorial)를 구성하였다. 36개 조합을 AC01~AC10에서 각 10회 반복하여 총 3,600회를 분석하였다. 정보성 9개 AC에 대한 정렬순위변환(aligned rank transform, ART) 요인분석과 AC 내부 Holm 보정에서는 Pop.Size와 StopRule의 주효과가 각각 8/9 AC에서, 두 인자의 교호작용은 4/9 AC에서 유의하였다. 따라서 각 인자의 주변평균만으로 최종 수준을 결정하지 않고 조합 수준의 성능과 강건성을 함께 평가하였다.

확인 실험 후보 수는 사전에 고정하지 않았다. 먼저 Mean BestAR, AvgRank 및 MaxRegret를 기준으로 성능․강건성 측면의 비지배 조합을 우선 포함하고, 이후 보조적인 품질–계산시간 관계, AC별 경험적 최우수 성능 및 미해결 교호작용을 대표하는 수준을 추가하여 인자 공간의 포괄성을 확보하였다. 그 결과(Pop.Size, StopRule)={(100, 2500), (200, 3500), (250, 2000), (250, 3000), (250, 3500), (300, 3500), (350, 1500), (350, 2500), (350, 4000)}의 9개 조합을 확인 실험 후보로 선정하였다. 이들 후보는 확인 단계에서 각각 DS01~DS09로 다시 부호화하여 비교하였다.

2단계에서는 이들 9개 후보를 MUKHERJE의 AC01~AC10에서 각 30회 반복하여 총 2,700회로 비교하였다. DS09=(Pop.Size=350, StopRule=4,000)은 전체 평균 BestAR 63.2751%, AvgRank 1.70, MaxRegret 2.3615%p를 기록하였고 10개 AC 중 9개에서 상위 3위(Top-3)에 포함되어 주요 성능․강건성 지표에서 가장 우수하였다. 또한 주요 성능․강건성 기준과 추가 민감도 검토에서 일관되게 비지배 후보로 나타났다. 평균 CPU 시간은 가장 컸으며, 9개 확인 후보의 해 품질과 계산비용 사이의 관계를 <Figure 2>에 제시하였다.<Figure 2>는 9개 확인 후보의 Overall Mean BestAR와 평균 CPU 시간의 관계를 나타낸다. 각 점의 BestAR은 AC01~AC10의 평균 BestAR를 동일가중한 값이며, CPU 시간은 후보별 300회 실행의 평균이다. DS09는 가장 높은 Overall Mean BestAR(63.2751%)를 기록하였고, DS06보다 0.5574%p 높았다. 점선은 Mean BestAR와 CPU 시간을 기준으로 한 Pareto 경계를 표시한다. 본 연구는 조립라인 설계문제에서 최종 해 품질과 강건성을 우선한다는 사전 선정원칙에 따라 DS09를 최종 운영 파라미터로 선정하였으며, CPU 시간은 이 결정에서 보조적인 구현 지표로만 사용하였다.

두 차례 확인 실험의 최종 결정과 MUKHERJE 데이터 셋을 이용한 확인 단계의 Mean BestAR 및 MaxRegret를 <Table 6>에 요약하였다. 1차 예비 실험에서 확정한 $P_{m}$ 메커니즘은 2차 예비 실험의 고정조건으로 사용하였고, 2차에 서 확정한 Pop.Size=350과 StopRule=4,000은 GAsac_new와 GAsam의 본 비교 실험에 동일하게 적용하였다. <Table 6>과 <Figure 2>의 MUKHERJE 값은 파라미터 확인 실험 결과이며, 4.3절의 본 실험에서는 이 자료를 재사용하지 않고 GAsam 300회를 독립적으로 새로 실행하였다.

이 단계적 절차는 튜닝 데이터에 대한 단일 평균 최적화보다 서로 다른 AC에서의 성능 일관성과 하방 위험을 함께 고려하여 최종 설정이 특정 제약환경에 과도하게 의존하는 위험을 줄이기 위한 것이다.

4.3 본 실험: GAsac_new와 GAsam의 비교

본 실험에서는 GAsac_new와 GAsam을 MANSOOR,SAWYER30, WARNECKE, MUKHERJE 순으로 비교하였다. 각 데이터 셋은 AC01~AC10의 10개 서로 다른 소프트 할당제약 문제 환경으로 구성하고, 각 문제 환경에서 알고리즘마다 30회 독립 반복하여 총 2,400회를 분석하였다. 두 알고리즘에는 Pop.Size=350과 StopRule=4,000을 동일하게 적용하고, 초기화, 선택, PMX/RE 연산자, 가능해 복구,적합도 평가 및 엘리트 보존 조건도 동일하게 유지하였다. 본 비교에서의 주요 알고리즘 차이는 GAsac_new의 고정 $P_{c}$ 와 $P_{m}$ 및 GAsam의 개체별 자기 적응 $P_{c}$ 와 $P_{m}$ 에 있으며,GAsam에는 사전․예비 실험에서 정한 전략 파라미터 허용범위가 함께 적용된다. GAsam의 $P_{c}$ 갱신 관련 값은 3.4절의 사전 설계를, 돌연변이확률 메커니즘은 4.2.1절에서 선정한 C01 설정을 적용하였다.

따라서 본 실험은 선행연구의 고정 $P_{c}$ ․ $P_{m}$ 을 계승한 GAsac_new와 최종 설계된 GAsam을 공통 운영조건에서 평가한 것이다. 공통 Pop.Size와 StopRule은 GAsam의 튜닝 결과로 선정하였으므로 각 알고리즘을 독립적으로 최적화한 best-vs-best 비교는 아니다. 또한 고정 $P_{c}$ ․ $P_{m}$ 의 추가 민감도 실험이나 GAsam과 낮은 $P_{m}$ 범위를 맞춘 고정 파라미터 비교군은 포함하지 않았다. 이에 따라 관찰된 차이는 자기 적응 여부만의 단일 요인 효과가 아니라 파라미터 제어 방식과 허용범위를 포함한 최종 설계의 종합적 차이로 해석한다. Appendix A의 GAsac_old–GAsac_new 비교는 재구현한 기준 알고리즘의 성능을 점검하는 보조자료이며,고정 파라미터의 최적성을 입증하는 근거는 아니다.

원자료에 대한 데이터 품질보증(data quality assurance, QA) 결과, 두 알고리즘에서 각각 1,200개의 반복 실험이 존재하여 계획된 총 2,400개 표본이 완전하게 구성되었다. 모든 알고리즘×데이터 셋×AC 조합은 정확히 30회의 반복을 포함했다. 또한 Pop.Size=350과 StopRule=4,000이 모든 반복에서 일치하였다. 이러한 QA를 통과한 후 통계분석을 수행하였다.

4.3.1 실험설계, 평가기준 및 통계분석

알고리즘 g, 데이터 셋 d, AC a, 독립 반복 r의 BestAR를 $AR (g, d, a, r)$ 로 두면 환경별 평균과 반복 실험 간 표준편차는 식(7)~(8)로 계산할 수 있다. 각 환경은 30회 독립 실행을 유지하며 서로 다른 AC의 원자료 반복 실험을 하나의 표본으로 통합하지 않았다.

MeanAR (g, d, a) = \frac{1}{30} \sum_{r = 1}^{30} AR (g, d, a, r)

(7)

{SD}_{run} (g, d, a) = \sqrt{\frac{\sum_{r = 1}^{30} {(AR - MeanAR)}^{2}}{29}}

(8)

${CV}_{run}$ 은 $\frac{{SD}_{run}}{MeanAR}$ 로 정의하고, 백분위수, P10과 P90은 30개 반복 실험별 BestAR의 표본 분위수로 계산하였다. 원자료의 SdAR은 각 반복 실험 종료 시 개체군 내부의 AR 산포이므로 SDrun과 구분하였다. 환경별 알고리즘 평균차는 식(9), 데이터 셋 수준의 동일가중 평균효과와 하방 위험은 식(10)~(11)로 계산하였다.

Δ AR (d, a) = MeanAR (GAsam, d, a) - MeanAR (GAsac_new, d, a)

(9)

MeanDeltaAR (d) = \frac{1}{10} \sum_{a = 1}^{10} Δ AR (d, a)

(10)

{WorstDelta}_{GAsam} (d) = \min_{a = 1, \dots, 10} Δ AR (d, a)

(11)

CPU 시간은 실행시간을 나타내는 보조지표로 기록하였다. 데이터 셋별 300회 반복의 평균 CPU 시간과 CPU 시간비(CPU ratio)=MeanCPUGAsam/MeanCPUGAsac_new를 제시하며, CPU 시간비가 1보다 크면 GAsam의 평균 실행시간이 더 길다는 의미이다.

정규성 판단은 Shapiro-Wilk p값 하나에 의존하지 않고 분위수-분위수(quantile-quantile, Q-Q) 도표, 동률․이산성및 이상치 구조를 함께 고려하였으며, 등분산성은 Levene 검정으로 확인하였다. 정규성과 등분산성이 대체로 수용되는 환경에는 독립표본 t-검정, 이분산 환경에는 Welch t-검정, 비정규․강한 동률 환경에는 평균차를 통계량으로 하는 독립표본 순열검정(permutation test)을 사용하였다. 평균차의 95% 신뢰구간(confidence interval, CI)은 부트스트랩(bootstrap)으로 추정하였다. 재표본추출의 재현성을 위해 난수 시드를 20260817로 고정하고, 순열검정과 부트스트랩을 각각 100,000회 수행하였다. 데이터 셋별 문제 환경의 구조를 유지하기 위해 주 다중검정 집합(primary multiplicity family)은 각 데이터 셋 내부의 AC01~AC10, 10개 검정으로 정의하고 Holm 단계적 보정을 적용하였다. Holm 보정 p값<0.05이면서 ΔAR의 방향이 일치할 때만 통계적 우위로 판정하였다. 주 분석의 결론이 검정집합의 정의에 민감한지 확인하기 위해 40개 환경 전체를 하나의 검정집합으로 하는 Holm 보정을 추가적으로 수행하였다.

최근 최적화 휴리스틱 벤치마킹에서는 문제 정의, 비교조건, 통계분석 및 재현가능성을 투명하게 보고하는 것이 공정한 성능평가의 핵심으로 강조된다[1]. 본 연구는 두 알고리즘에 동일한 StopRule과 최대 세대수 안전상한을 적용하고, 각 알고리즘이 공통 종료조건에 도달할 때까지 탐색하도록 하였다. 비교의 주지표는 BestAR이며 CPU 시간은 실행시간을 나타내는 보조 정보로 보고하였다.

4.3.2 선행 GAsac과의 확장 비교

현재 구현의 비교 가능성을 확인하기 위해 Choi and Lee[9] 의 GAsac 실험 결과를 GAsac_old, 본 연구에서 동일 문제에 다시 적용한 GAsac을 GAsac_new로 구분하고, 자기 적응형 GAsam과 동일한 소프트 할당제약 기준으로 확장 비교하였다. <Appendix A>는 선행연구(Choi and Lee[9])의 <Table 8> 구조를 확장한 것으로, 각 데이터 셋의 AC01~AC10에 대해 30회 반복의 최고(B), 평균(A), 최저(W) AR과 실행당 평균계산시간(average computing time, ACT)을 제시한다. SO는 선행연구에서 SALBP 최선해 기준값을 나타내기 위해 사용한 표기이며, 해당 해의 소프트 제약 충족률을 의미한다. 개선비율(improvement ratio, IR)은 10개 AC 중 해당 통계량이 SO를 초과한 비율이며 B/A/W 순서로 제시하였다.<Appendix A>는 현재 GAsac_new 구현이 선행 GAsac_old의 해 품질 패턴을 대체로 재현하면서도 일부 AC에서 더 높은 최고․평균 값을 얻고 있음을 보여준다. GAsam의 효과는 데이터 셋에 따라 상이하여 SAWYER30에서는 GAsac_new의 평균 AR이 더 높은 AC가 다수인 반면, MUKHERJE에서는 GAsam이 여러 AC에서 더 높은 평균과 최고 성능을 보인다. GAsac_old는 다른 컴퓨터에 서 Excel VBA로 구현된 반면[9], GAsac_new와 GAsam은 동일한 컴퓨터 환경에서 실행되었다. 따라서 세 구현 간 ACT는 기술적 참고자료로만 제시하고, 통계적 유의성 검정은 동일한 실행환경에서 얻은 GAsac_new와 GAsam의 30회 독립 반복 자료를 대상으로 수행하였다.

AC별 평균 AR을 비교하면 GAsac_new는 GAsac_old보다 SAWYER30의 9/10 AC, WARNECKE의 9/10 AC(1개동률), MUKHERJE의 10/10 AC에서 높았고, MANSOOR에서는 사실상 동일하였다. 이는 이번 재구현의 해 품질을 점검하는 보조적 근거이다. 그러나 실행환경과 운영조건이 함께 달라졌으므로 공통 Pop.Size와 StopRule의 효과만을 분리한 비교는 아니며, 해당 설정이 GAsac_new의 독립적인 최적 설정임을 증명하지도 않는다.

4.3.3 해 품질과 강건성

<Table 7>은 데이터 셋 수준의 해 품질과 강건성을 요약하고 CPU 시간비를 보조지표로 제시한 것이다. Mean ΔAR는 GAsam과 GAsac_new의 평균 BestAR 차이로, 양수이면 GAsam의 평균이 높음을 의미한다. StatWin은 각 데이터 셋 내부의 10개 AC를 검정집합으로 한 Holm 보정후 유의수준 0.05에서 차이가 유의하고 효과의 방향이 해당 알고리즘의 우세와 일치하는 경우이다. NS(not statistically significant)는 유의한 차이가 검출되지 않은 경우이며 통계적 동등성을 뜻하지 않는다. WorstDelta_GAsam은 식(11)과 같이 10개 AC의 평균 BestAR 차이 중 최솟값으로, 개별 실행의 최저 BestAR와 구분한다. SDrun은 독립 반복간 BestAR의 표준편차, P10은 제10백분위수이며, CPU ratio가 1보다 크면 GAsam의 평균 실행시간이 더 길다는 것을 의미한다.

표에서 알 수 있듯이 MANSOOR에서는 두 알고리즘의 데이터 셋 평균 BestAR이 모두 63.6337%로 동일하였다. SAWYER30에서는 GAsac_new 79.1775%, GAsam 75.4683%로 GAsam의 평균 ΔAR가 -3.7092%p였으며, 10개 AC 중 8개에서 GAsac_new의 Holm 보정 후 통계적 우위(StatWin)가 확인되었다. WARNECKE에서는 GAsam이 +0.2148%p 높았지만 Holm 보정 후 StatWin은 없었다. 반면 MUKHERJE에서는 GAsam이 +2.6359%p 높고 10개 모든 AC 평균에서 GAsac_new보다 낮지 않았으며, 4개 AC에서 GAsam StatWin을 기록하였다.

데이터 셋별 10개 AC를 주 Holm 보정 집합으로 사용한 결과 SAWYER30에서 GAsac_new StatWin 8개, MUKHERJE에서 GAsam StatWin 4개가 나타났다. 추가적인 엄격한 민감도 분석으로 40개 환경 전체를 하나의 Holm 보정 집합으로 처리하면 GAsac_new StatWin 7개와 GAsam StatWin 3개가 남았다. 이 경우에도 SAWYER30의 GAsac_new 우세와 MUKHERJE의 GAsam 우세라는 방향적 구조는 유지되었으나, MUKHERJE의 GAsam StatWin은 주 분석 4개에서 민감도 분석 3개로 줄었다.

4개 데이터 셋의 평균 ΔAR를 동일가중하면 전체 평균은 -0.2146%p이나, 이 값은 SAWYER30의 큰 음의 효과와 MUKHERJE의 큰 양의 효과가 상쇄된 결과이다. 이 전체 평균은 서로 다른 네 벤치마크를 동일가중한 기술적 요약 치이며 모집단 효과나 동등성 추정치로 해석하지 않는다. 따라서 전체 평균이 0에 가깝다는 사실만으로 두 알고리즘이 동등하다고 결론을 내리는 것은 부적절하다. 핵심 결과는 최종 GAsam 설계의 상대 성능 방향이 문제 환경에 따라 반전된다는 점이다.

AC별 30회 독립 실행 평균을 나타낸 <Figure 3>(각 점은 30회 독립 실행의 평균을 나타냄)에서 알 수 있듯이, SAWYER30은 AC01, AC02, AC04를 포함한 여러 환경에 서 GAsam의 손실이 크게 나타난 반면, MUKHERJE에서는 10개 AC의 평균 모두 GAsam이 우세하였다. GAsam의 WorstDelta_GAsam은 SAWYER30에서 -12.7018%p였으나 MUKHERJE에서는 +0.0411%p로, 가장 불리한 AC에 서도 평균 성능이 GAsac_new보다 낮지 않았다. 따라서 <Figure 3>의 두 패널은 본 실험에서 확인된 문제 의존적 성능 반전을 보여준다.

대표 효과크기에서도 문제 의존성이확인되었다. SAWYER30의 ΔAR는 AC01, AC02, AC04에서 각각-9.3683, -10.5302, -12.7018%p였고 모두 Holm 보정 p값=0.0001이었다. 반대로 MUKHERJE의 AC02와 AC09는 각각 +6.5125%p(95% CI [4.2026,8.7267])와 +5.8458%p ([2.2979,9.3500])였으며, AC04․AC05를 포함한 4개 환경(AC02, AC04, AC05, AC09)에서 GAsam의 통계적 우위가 확인되었다.

4.3.4 반복 안정성과 계산시간의 보조적 검토

SAWYER30에서는 GAsam의 평균 SDrun이 3.0611로 GAsac_new의 1.0933보다 크고 평균 P10도 72.7153%로 GAsac_new의 79.0422%보다 낮았다. 즉 평균 성능 열위와 함께 반복 실험 간 하방 위험도 증가하였다. 반면 MUKHERJE에서는 GAsam의 평균 SDrun이 3.5936으로 GAsac_new의 2.8225보다 컸음에도 평균 P10이 59.3212%로 GAsac_new의 58.2010%보다 높았다. 분산의 크기와 하방 성능 수준은 서로 다른 개념이므로 함께 해석할 필요가 있다.

보조적으로 측정한 CPU 시간은 GAsam이 네 데이터 셋 모두에서 더 길었으며, GAsam/GAsac_new CPU 시간비는 1.016~1.113이었다. MUKHERJE에서는 평균 CPU 시간이 44.033초에서 49.005초로 11.29% 증가하였다. 본 연구는 조립라인 설계문제에서 최종 해 품질을 우선하고, 두 알고리즘이 동일한 StopRule에 도달할 때까지 각자의 탐색과정을 수행하도록 하였으므로 동일 CPU 시간을 비교조건으로 설정하지 않았다. 따라서 CPU 시간은 실행시간을 나타내는 보조적 특성으로 해석하며, 본 연구는 GAsam의 계산효율 우위를 주장하지 않는다.

4.3.5 종합 해석 및 논의

본 연구의 핵심 결과는 최종 설계된 GAsam의 상대 성능이 문제 환경에 따라 반전된다는 점이다. MANSOOR에 서는 두 알고리즘의 성능이 동일했고, SAWYER30에서는 GAsac_new가 뚜렷하게 우세했으며, WARNECKE에서는 차이가 작았다. 반면 현실에 준하는 규모의 MUKHERJE에서는 GAsam이 10개 AC 평균 모두에서 우세하였다. 일반적으로 GA에서 해집단의 다양성 손실은 조기수렴과 국소 최적해 정체의 주요 원인이 될 수 있으며[11], 자기 적응형 파라미터 제어에서는 전략 파라미터가 해와 함께 선택되므로 탐색과정에 따라 그 값의 분포가 변화할 수 있다[2, 10]. 본 연구의 예비 실험에서도 SAWYER30과 MUKHERJE에서 평균 $P_{m}$ 이 크게 감소하였으나, 두 데이터 셋에서 최종 성능의 방향은 서로 반대로 나타났다. 따라서 문제 규모만으로 이러한 성능 반전을 설명하기는 어려우며, 문제구조와 탐색공간의 특성에 따라 자기 적응에 의해 형성되는 탐색–활용 균형이 다르게 작용했을 가능성이 있다. 다만 본 실험에서는 세대별 전략 파라미터와 염색체 다양성의 관계를 직접 측정하지 않았으므로 이러한 설명은 후속 검증이 필요한 가설로 해석한다.

또한 본 실험의 일반화 성능을 해석할 때 파라미터 선정에 사용된 데이터 셋과 그렇지 않은 데이터 셋을 구분할 필요가 있다. WARNECKE와 MUKHERJE는 각각 선별 및확인 단계에서 파라미터 선정에 직접 사용되었다. 본 비교의 MUKHERJE GAsam 300회는 확인 실험 자료와 독립적으로 새로 실행했으므로 동일 실행자료 재사용에 따른 선택 편향은 제거하였다. 그러나 MUKHERJE 데이터 셋 자체가 파라미터 선정에 노출되었다는 한계는 남는다. 반면 MANSOOR와 SAWYER30은 파라미터 선정에는 사용되지 않았으며, 특히 SAWYER30에서 GAsac_new가 뚜렷하게 우세했다는 결과는 최종 GAsam 설정의 성능이 새로운 문제 환경에서 일관되게 유지된다고 볼 수 없음을 보여준다.

전략 파라미터 동역학 예비 확인에서 AvgPm과 전략 파라미터 산포가 감소한 것은 설계된 자기 적응 과정과 일치하는 분포 변화를 보여주지만, 그 감소가 항상 해 품질 향상을 뜻하지는 않는다. SAWYER30에서 GAsam은 낮은 P10과 큰 SDrun을 보인 반면 MUKHERJE에서는 P10이 향상되었다. 또한 GAsam은 고정 확률의 사전 설정을 완전히 제거하는 것이 아니라 전략 유전자 범위, 변동폭, 상속 방식과 같은 메커니즘 수준의 상위 파라미터 설계를 필요로 한다. 특히 식(4)의 $P_{c}$ 관련 설계값과 $P_{m}$ 의 초기․실행 중 하한은 별도 요인 실험으로 튜닝하지 않았으므로,본 결과를 모든 자기 적응 상위 설계값이 최적화된 GAsam의 성능으로 해석해서는 안 된다.

본 실험은 세대별 $P_{c}$ 와 $P_{m}$ 및 염색체 다양성 로그를 저장하지 않았다. 따라서 SAWYER30과 MUKHERJE의 상반된 결과를 특정 파라미터 변화 궤적의 인과효과로 단정하지 않는다. 또한 SAWYER30과 MUKHERJE의 상반된 결과에 식(4)의 사전 설계값이 어느 정도 기여했는지도 현재 자료만으로 분리할 수 없다. 향후 연구에서는 동일한 문제 환경에서 전략 파라미터 궤적, 다양성, 성공․실패 반복 실험을 함께 기록하고, 필요하면 문제 특성에 따라 자기 적응 범위 자체를 조정하는 방식을 검토할 필요가 있다.

파라미터 설정에 관한 한계도 있다. GAsac_new는 선행연구의 고정 $P_{c}$ =0.40과 $P_{m}$ =0.50을 사용하지만, GAsam은 $P_{c}$ ․ $P_{m}$ 을 개체별로 진화시키고 실행 중 $P_{m}$ 을 [0.005,0.30] 으로 제한한다. MUKHERJE에서는 10개 AC 모두에 서 GAsam의 평균 BestAR가 높았으며, 데이터 셋별 Holm 보정 기준으로 AC02, AC04, AC05 및 AC09에서 통계적 우위가 확인되었다. 그러나 이는 허용범위와 자기 적응 메커니즘을 함께 적용한 최종 설계의 성능이다. 낮은 $P_{m}$ 범위의 고정 파라미터 비교군을 별도로 평가하지 않았으므로, 향상을 자기 적응만의 독립적 효과로 귀속할 수 없다. GAsac_new에 다른 고정 조합을 적용하면 상대 성능이 달라질 가능성도 배제할 수 없다. MANSOOR의 동일 성능, 통계적 우위가 확인되지 않은 WARNECKE의 소폭 평균차이, SAWYER30의 GAsac_new 우위와 함께 고려하여 문제 의존적인 결과로 해석해야 한다.

공통 Pop.Size와 StopRule은 GAsam의 튜닝 결과를 두 알고리즘에 동일하게 적용했으므로, 각 알고리즘의 독립적 최적 성능을 비교한 것은 아니다. 본 연구의 기여는 고정 파라미터 방식에 대한 보편적 우월성의 입증보다는 소프트 할당제약 GALBP를 위한 개체 수준의 공동 자기 적응 설계와 그 성능특성의 제시에 있다. Appendix A의 결과도 비교 알고리즘의 재구현 성능을 점검하는 보조자료로 한정하여 해석한다.

5. 결 론

본 연구는 소프트 AC를 고려하는 GALBP의 해법으로 기존 고정 파라미터 유전 알고리즘 GAsac을 확장한 자기 적응형 유전 알고리즘 GAsam을 제안하였다. GAsam은 작업순서와 개체별 $P_{c}$ ․ $P_{m}$ 을 하나의 염색체에 보유하고 선택․교차․상속 및 전략변이를 거치면서 해와 파라미터가 함께 진화하도록 설계하였다. 선행연구의 해 표현, 가능해 복구, 개선된 작업장 할당법, 적합도 평가, 선택 및 작업부 연산자를 계승하고, 재구현한 기준 알고리즘 GAsac_new와 공통 운영조건에서 비교하였다. 또한 전략 파라미터 분포의 관찰, $P_{m}$ 메커니즘과 운영 파라미터의 단계적 선별․확인, 최종 성능평가를 구분한 실험절차를 제시하였다. 핵심 기여는 소프트 AC를 포함하는 GALBP에 개체 수준의 $P_{c}$ ․ $P_{m}$ 공동 자기 적응 설계를 제시하고 문제 특성 기반 파라미터 제어 연구의 실증적 토대를 마련한 데있다.

2,400회의 본 실험에서 GAsam의 데이터 셋 수준 평균 BestAR는 MANSOOR에서 GAsac_new와 동일하였고, WARNECKE와 MUKHERJE에서는 각각 0.2148%p와 2.6359%p 높았다. 이에 따라 4개 벤치마크 중 3개에서 같거나 높은 평균 BestAR를 보였으나, WARNECKE에서는 통계적 우위가 확인된 AC가 없었다. 현실에 준하는 규모의 벤치마크인 MUKHERJE에서는 10개 AC 모두에서 GAsam의 평균 BestAR가 높았고, 데이터 셋별 Holm 보정 기준으로 AC02, AC04, AC05 및 AC09에서 통계적 우위가 확인되었다. 이 결과는 본 연구에서 선정한 허용범위와 자기 적응 메커니즘을 포함한 최종 GAsam 설계의 성능으로 해석한다. 반면 SAWYER30에서는 GAsac_new의 평균 BestAR가 3.7092%p 높았고 8개 AC에서 통계적 우위가 확인되었다. 따라서 상대 성능은 문제 환경에 따라 달라졌으며, 데이터 셋 간 차이를 문제 규모 자체의 인과적 효과로 해석할 수는 없다.

본 연구에는 다음과 같은 한계가 있다. 첫째, 고정 파라미터 값․허용범위의 영향과 자기 적응 메커니즘의 효과를 분리하지 못했으며, 각 알고리즘을 독립적으로 최적화한 비교도 아니다. 둘째, $P_{c}$ 갱신 관련 값과 $P_{m}$ 의 초기․실행 중 하한은 별도 요인 실험으로 튜닝하지 않고 사전 설계값으로 유지하였다. 셋째, WARNECKE와 MUKHERJE는 각각 선별과 확인 단계의 파라미터 선정에 사용되었다. MUKHERJE 본 실험자료는 확인 실험과 독립적으로 생성했지만 데이터 셋 수준의 선정 영향이 남으므로 완전히 독립적인 외부검증으로 보기 어렵다. 자동차․가전․전자 조립라인의 관리적 선호를 반영하는 설계 및 재배치 지원이 기대되지만, 실제 산업 현장에 대한 적용 효과는 추가 검증이 필요하다.

향후 연구에서는 세대별 $P_{c}$ ․ $P_{m}$ 변화와 염색체 다양성을 함께 저장하여 실행별 탐색 과정을 비교할 필요가 있다. 고정 $P_{c}$ ․ $P_{m}$ 및 전략 유전자의 초기․실행 범위에 대한 민감도 분석과 $P_{c}$ 단독, $P_{m}$ 단독, 공동 자기 적응 변형의 비교를 통해 구성요소별 효과를 구분해야 한다. 또한 파라미터 선정에 사용되지 않은 벤치마크와 실제 산업자료로 외부 일반화 성능을 평가하고, 선행관계 밀도․소프트 제약 밀도․제약 충돌 정도를 반영하는 문제 특성 기반 자기 적응을 검토할 수 있다. 다른 메타휴리스틱과의 비교를 위해 소프트 제약 GALBP에 적합한 ALNS의 제거․재구성 연산자를 설계하고 동일한 문제 정의와 평가기준 아래에서 해 품질과 강건성을 평가할 필요가 있다. 아울러 알고리즘 구현을 효율화하여 실행시간을 단축하는 연구도 수행할 수 있다.

Figure

<Figure 1>.

Evolution of Average P_m during Self-Adaptation

<Figure 2>.

Quality-Cost Trade-off among Pop.Size-StopRule Candidates

<Figure 3>.

Contrasting AC-Level Performance Profiles

Table

<Table 1>.

Soft Assignment Constraint Categories

Categories	Managerial meaning	Evaluation rule
Compatible tasks	Assign specified tasks to the same workstation	station(i)=station(j)
Incompatible tasks	Separate specified tasks	station(i)≠station(j)
Minimum distance	Keep tasks at least a prescribed number of stations apart	\|station(i)−station(j)\|≥dmin
Maximum distance	Keep tasks within a prescribed station distance	\|station(i)−station(j)\|≤dmax
Task–workstation preference / avoidance	Prefer or avoid assigning a task to a specified workstation	weighted reward if the preferred relation is satisfied

<Table 2>.

Comparison of GAsac_new and GAsam

Items	GAsac_new	GAsam	Roles
Representation	Task-priority permutation	Task-priority permutation + individual Pc and Pm	Strategy parameters are encoded with each solution
Pop.Size	350	350	Controlled in the main comparison
Crossover	PMX; fixed Pc = 0.4	PMX; individual Pc	Same chromosome operator; rate control differs
Mutation	RE; fixed Pm = 0.5	RE; individual Pm	Same chromosome operator; rate control differs
Pc update	None	Arithmetic inheritance + N(0, 0.05²); bound [0.40, 1.0]	Self-adaptive strategy gene; update setting pre-specified
Pm update	None	Average inheritance + logit-scale Gaussian; bound [0.005,0.3]	Self-adaptive strategy gene; key mechanism parameters tuned; lower bound pre-specified
Workstation allocation	Improved two-task look-ahead [9]	Same	Controlled
Selection	Binary tournament	Binary tournament	Controlled
Elitism	Best solution preserved	Best solution preserved	Controlled
Stopping	No improvement for 4,000 generations	Same	Max generation soft cap = 20,000

<Table 3>.

Pseudocode-Level Procedure of GAsam

Steps	Procedures
1	Generate the initial population and individual Pc and Pm strategy genes.
2	Repair/decode task priorities and evaluate the weighted soft-constraint attainment.
3	Update the run elite and no-improvement counter.
4	If no elite improvement has occurred for StopRule generations, terminate the run.
5	Apply binary tournament selection.
6	Build crossover candidates using individual Pc; if odd, drop the last candidate, pair the remainder sequentially, apply PMX, and inherit Pc and Pm.
7	For all individuals, apply reciprocal-exchange mutation using individual Pm and then mutate the Pc and Pm strategy genes.
8	Insert the elite and continue to the next generation; enforce the 20,000-generation soft cap.

<Table 4>.

Experimental Design and Evaluation Framework

Experiment	Stage	Dataset and Design	Main Purpose	Final Output
Descriptive parameter-dynamics observation	Pilot	4 datasets × 10 AC × 5 runs = 200	Describe how individual Pc and Pm distributions change during search	Observed generation-level changes in parameter distributions
Preliminary Exp. 1: Pm mechanism	Screening	WARNECKE; 54 combinations × 10 AC × 10 runs = 5,400	Screen σ_pm, running/initial Pm upper bounds, and inheritance	9 confirmation candidates, C01~C09
Preliminary Exp. 1: Pm mechanism	Confirmation	MUKHERJE; 9 candidates × 10 AC × 30 runs = 2,700	Recheck robustness on a larger instance	C01: 0.02/0.30/0.30/average
Preliminary Exp. 2: Pop.Size × StopRule	Screening	WARNECKE; 6 × 6 combinations × 10 AC × 10 runs = 3,600	Assess factor effects, interactions, and robustness	9 confirmation candidates, DS01~DS09
Preliminary Exp. 2: Pop.Size × StopRule	Confirmation	MUKHERJE; 9 candidates × 10 AC × 30 runs = 2,700	Select final operating parameters	DS09: Pop.Size=350; StopRule=4,000
Main experiment	Comparison	2 algorithms × 4 datasets × 10 AC × 30 runs = 2,400	Compare solution quality and robustness; record computing time as supplementary information	Problem-dependent GAsac_new-GAsam performance

<Table 5>.

Summary of the Self-Adaptation Pilot

Note: Gen1 and Gen4000 denote generations 1 and 4,000, respectively. Change rates were calculated using unrounded run-level means, whereas Gen1 and Gen4000 values are displayed to four decimal places.

Dataset	AvgPm Gen1→Gen4000	ΔP_m (%)	AvgPc Gen1→Gen4000	ΔP_c (%)	ΔSdPm (%)	ΔSdPc (%)
MANSOOR	0.1061 → 0.0919	-13.38	0.7504 → 0.7485	-0.25	-31.91	-36.46
SAWYER30	0.1054 → 0.0718	-31.92	0.7481 → 0.7138	-4.58	-33.32	-34.32
WARNECKE	0.1064 → 0.0730	-31.41	0.7527 → 0.7160	-4.87	-31.85	-31.52
MUKHERJE	0.1052 → 0.0693	-34.14	0.7523 → 0.6891	-8.40	-30.48	-34.03

<Table 6>.

Final Tuning Decisions

Tuning target	Key self-adaptive Pm parameters	Operating parameters
Selected ID	C01	DS09
Final setting	σ_pm=0.02; PmRunMax=0.30; PmInitMax=0.30; average inheritance	Pop.Size=350; StopRule=4,000
Mean BestAR (%)	61.9372	63.2751
MaxRegret (%p)	2.4582	2.3615
Selection evidence	Mean P10=58.1488%; lower CPU time than C08	AvgRank=1.70; Top-3 in 9/10 AC; non-dominated across the principal robustness criteria

<Table 7>.

Integrated Solution Quality and Robustness Summary with CPU Reference

Note: sac_new=GAsac_new; sam=GAsam. ΔAR=mean BestAR(GAsam) − mean BestAR(GAsac_new). StatWin: favorable difference with dataset-wise Holm-adjusted p < 0.05 (10 AC tests); NS: no significant difference, not equivalence. WorstDelta_GAsam: minimum of the ten AC-level mean differences, not an individual-run minimum. SDrun: run-to-run SD; P10: 10th percentile; both averaged across AC sets. CPU ratio: mean time of GAsam / GAsac_new.

Dataset	Mean ΔAR (%p)	StatWins sac_new / sam / NS	WorstDelta_GAsam (%p)	SDrun sac_new / sam	Mean P10 sac_new / sam	CPU ratio sam / sac_new
MANSOOR	+0.0000	0/0/10	+0.0000	0.0000/0.0000	63.6337/63.6337	1.016
SAWYER30	-3.7092	8/0/2	-12.7018	1.0933/3.0611	79.0422/72.7153	1.055
WARNECKE	+0.2148	0/0/10	-0.1753	0.4142/1.0761	57.4681/57.4680	1.071
MUKHERJE	+2.6359	0/4/6	+0.0411	2.8225/3.5936	58.2010/59.3212	1.113

<Appendix A>.

Extended Comparison of Solution Performance for GAsac_old, GAsac_new, and GAsam

Note: B/A/W = Best/Average/Worst of 30 independent runs; IR is reported in B/A/W order. SO is the common SALBP reference achievement ratio retained to three decimals in the verification dataset. IR (%) is the percentage of the ten AC sets for which the corresponding statistic is greater than SO. ACT is mean computing time per run. GAsac_old was implemented in Excel VBA on a different computer, whereas GAsac_new and GAsam used the same PyPy 3.11 / Intel i7-1260P environment; cross-generation ACT is descriptive only.

Data	AC	SO	GAsac_old (B/A/W)	GAsac_new (B/A/W)	GAsam (B/A/W)	ACT (Sec) Old/New/Sam
MANSOOR	AC01	34.950	34.950/34.950/34.950	34.946/34.946/34.946	34.946/34.946/34.946	3.42/6.90/6.85
	AC02	41.520	80.510/80.510/80.510	80.507/80.507/80.507	80.507/80.507/80.507	3.46/7.07/7.33
	AC03	63.210	63.210/63.210/63.210	63.212/63.212/63.212	63.212/63.212/63.212	3.38/6.94/7.35
	AC04	64.100	67.310/67.310/67.310	67.308/67.308/67.308	67.308/67.308/67.308	3.44/6.86/6.69
	AC05	62.260	62.260/62.260/62.260	62.264/62.264/62.264	62.264/62.264/62.264	3.34/6.41/6.46
	AC06	41.700	78.040/78.040/78.040	78.040/78.040/78.040	78.040/78.040/78.040	3.52/6.39/6.61
	AC07	81.970	81.970/81.970/81.970	81.967/81.967/81.967	81.967/81.967/81.967	3.36/6.33/6.41
	AC08	58.680	58.680/58.680/58.680	58.678/58.678/58.678	58.678/58.678/58.678	3.34/6.36/6.67
	AC09	9.910	9.910/9.910/9.910	9.910/9.910/9.910	9.910/9.910/9.910	3.33/6.45/6.34
	AC10	0.500	99.500/99.500/99.500	99.505/99.505/99.505	99.505/99.505/99.505	3.43/6.47/6.56
	IR (%)	–	40/40/40	60/60/60	60/60/60	–
SAWYER30	AC01	10.340	96.020/90.697/74.160	94.261/93.113/77.043	94.261/83.745/76.870	15.63/10.42/10.46
	AC02	42.650	97.220/96.924/95.890	97.219/97.219/97.219	97.219/86.689/70.728	16.54/10.17/11.65
	AC03	88.270	89.800/89.800/89.800	89.804/89.804/89.804	89.804/89.804/89.804	13.43/9.49/9.74
	AC04	56.000	94.260/85.854/77.040	94.261/92.539/77.043	94.261/79.837/76.870	23.82/10.17/11.78
	AC05	65.530	76.680/75.793/75.580	76.683/76.050/75.779	75.779/75.776/75.678	22.14/11.29/10.18
	AC06	37.710	64.340/63.732/62.060	64.343/64.343/64.343	64.343/63.200/62.057	23.48/9.69/11.49
	AC07	58.330	96.210/96.210/96.210	96.212/96.212/96.212	96.212/96.212/96.212	19.32/9.40/9.46
	AC08	62.510	77.810/77.410/76.720	77.814/77.814/77.814	77.814/77.085/76.721	23.72/10.19/10.60
	AC09	1.710	10.290/8.542/7.430	10.286/9.943/7.714	10.286/7.905/4.571	23.32/10.40/10.74
	AC10	48.250	94.740/94.740/94.740	94.737/94.737/94.737	94.737/94.430/93.202	18.77/9.39/10.00
	IR (%)	–	100/100/100	100/100/100	100/100/100	–
WARNECKE	AC01	63.450	64.930/64.267/63.450	72.240/72.240/72.240	77.497/72.065/61.725	43.83/14.96/15.98
	AC02	58.710	58.710/58.710/58.710	58.710/58.710/58.710	66.864/60.514/58.710	35.80/13.58/16.20
	AC03	38.390	38.530/38.395/38.390	38.531/38.420/38.392	39.917/38.688/38.392	36.64/14.30/15.58
	AC04	61.520	61.520/61.520/61.520	61.524/61.524/61.524	61.524/61.524/61.524	35.69/13.36/13.95
	AC05	50.610	60.620/51.277/50.610	60.623/51.620/50.612	60.623/51.620/50.612	36.44/14.80/15.15
	AC06	61.720	72.240/69.785/61.720	72.240/72.240/72.240	72.240/72.240/72.240	42.25/15.02/15.96
	AC07	74.670	76.120/74.762/74.670	76.121/74.916/74.670	76.121/75.105/74.670	36.69/15.37/17.17
	AC08	50.230	51.500/50.548/50.320	51.496/51.170/50.680	51.496/51.366/50.317	44.07/19.86/21.42
	AC09	39.800	39.800/39.800/39.800	39.803/39.803/39.803	39.803/39.803/39.803	35.16/13.33/15.35
	AC10	53.140	56.000/55.443/54.100	56.000/55.943/55.810	56.000/55.809/54.095	44.62/21.06/19.95
	IR (%)	–	70/70/20	90/90/80	100/100/70	–
MUKHERJE	AC01	64.490	70.440/70.091/69.540	78.530/71.641/69.951	83.539/72.852/69.540	295.26/42.56/46.91
	AC02	27.970	46.470/36.330/29.340	54.946/41.308/33.533	55.032/47.820/37.901	277.05/48.95/52.19
	AC03	42.130	47.160/46.773/46.390	47.545/46.919/46.772	48.357/47.222/46.386	281.82/33.78/37.45
	AC04	36.970	62.540/55.389/49.440	62.574/56.015/49.476	69.483/59.504/52.718	289.02/38.87/43.11
	AC05	43.820	52.980/47.457/44.130	56.665/50.697/44.186	57.317/54.548/43.817	293.94/50.42/57.27
	AC06	65.800	75.890/75.148/74.980	76.804/75.240/74.977	76.895/75.282/74.977	287.50/37.69/34.39
	AC07	60.570	81.740/67.370/65.140	86.814/74.569/65.141	88.478/78.270/60.566	266.76/52.63/59.72
	AC08	69.780	78.160/78.069/77.720	78.952/78.189/77.720	79.349/78.377/77.720	255.29/32.44/44.84
	AC09	34.280	57.930/45.520/34.730	69.948/51.783/42.590	70.397/57.629/47.493	279.49/52.43/64.79
	AC10	57.630	64.190/58.935/58.130	63.889/59.938/58.232	80.404/61.155/57.626	277.94/50.56/49.37
	IR (%)	–	100/100/100	100/100/100	100/100/70	–

Reference

Auger, A., Bosman, P.A.N., Kerschke, P., Whitley, D., and Schäpermeier, L., Challenges in Benchmarking Optimization Heuristics (Dagstuhl Seminar 23251), Dagstuhl Reports, 2024, Vol. 13, No. 6, pp. 55-80, .
Bäck, T., Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms, Oxford University Press, New York, 1996.
Battaïa, O. and Dolgui, A., A taxonomy of line balancing problems and their solution approaches, International Journal of Production Economics, 2013, Vol. 142, No. 2, pp. 259-277, .
Battaïa, O. and Dolgui, A., Hybridizations in line balancing problems: A comprehensive review on new trends and formulations, International Journal of Production Economics, 2022, Vol. 250, 108673, .
Baybars, I., A survey of exact algorithms for the simple assembly line balancing problem, Management Science, 1986, Vol. 32, No. 8, pp. 909-932, .
Becker, C. and Scholl, A., A survey on problems and methods in generalized assembly line balancing, European Journal of Operational Research, 2006, Vol. 168, No. 3, pp. 694-715, .
Boysen, N., Fliedner, M., and Scholl, A., A classification of assembly line balancing problems, European Journal of Operational Research, 2007, Vol. 183, No. 2, pp. 674-693, .
Chen, J.C., Chen, Y.Y., Chen, T.L., and Kuo, Y.H., Applying two-phase adaptive genetic algorithm to solve multi-model assembly line balancing problems in TFTLCD module process, Journal of Manufacturing Systems, 2019, Vol. 52, pp. 86-99, .
Choi, S.H. and Lee, G.C., Optimizing Assembly Line Balancing Problems with Soft Constraints, Journal of Korean Society of Industrial and Systems Engineering, 2018, Vol. 41, No. 2, pp. 105-116, .
Eiben, A.E., Hinterding, R., and Michalewicz, Z., Parameter control in evolutionary algorithms, IEEE Transactions on Evolutionary Computation, 1999, Vol. 3, No. 2, pp. 124-141, .
Goldberg, D.E., Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, Reading, MA, 1989.
Goldberg, D.E. and Lingle, R., Alleles, loci, and the traveling salesman problem, Proceedings of the First International Conference on Genetic Algorithms and Their Applications, Lawrence Erlbaum Associates, Hillsdale, NJ, 1985, pp. 154-159.
Li, S., Butterfield, J., and Murphy, A., A new multi-objective genetic algorithm for assembly line balancing, Journal of Computing and Information Science in Engineering, 2023, Vol. 23, No. 3, 034502, .
Ropke, S. and Pisinger, D., An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows, Transportation Science, 2006, Vol. 40, No. 4, pp. 455-472, .
Sabuncuoglu, I., Erel, E. and Tanyer, M., Assembly line balancing using genetic algorithms, Journal of Intelligent Manufacturing, 2000, Vol. 11, No. 3, pp. 295-310, .
Scholl, A., Balancing and Sequencing of Assembly Lines, 2nd ed., Physica-Verlag, Heidelberg, 1999.
Srinivas, M. and Patnaik, L.M., Adaptive probabilities of crossover and mutation in genetic algorithms, IEEE Transactions on Systems, Man, and Cybernetics, 1994, Vol. 24, No. 4, pp. 656-667, .
Tasan, S.O. and Tunali, S., A review of the current applications of genetic algorithms in assembly line balancing, Journal of Intelligent Manufacturing, 2008, Vol. 19, No. 1, pp. 49-69, .
The PyPy Team, Performance, Available from: https://pypy.org/performance.html (accessed August 26, 2026).
Yu, J. and Yin, Y., Assembly line balancing based on an adaptive genetic algorithm, The International Journal of Advanced Manufacturing Technology, 2010, Vol. 48, No. 1-4, pp. 347-354, .