산업공학에서의 시스템 최적화: 역사적 고찰, 발전 및 전망

1. 서 론

전통적 의미에서 최적화는 주어진 함수 f(x)와, 변수 x가 취할 수 있는 값의 범위를 나타내는 집합 X에 대해 함수값의 최소치를 찾기 위한 문제, 즉 min_x∈Xf(x)의 최적해를 찾는 학문 분야로 정의할 수 있다. 수리계획(mathematical programming)으로도 불리며, 수학적 도구 사용이 강조되어 온 이유로 ‘최적화는 수학의 일부’라는 시각도 존재한다. 이 논문에서는 대한산업공학회 설립 50주년을 맞이하여, 산업공학적 관점에서 ‘시스템 최적화’에 대해 새롭게 고찰한다.

이 논문은 시스템 최적화가 산업공학의 학문적 기초를 형성하는 과정을 발전 시기별로 분석하고, 미래 사회에서 산업공학의 학문적 발전에 시스템 최적화가 담당할 주요 이슈들을 조망하는 것을 목적으로 한다. 이를 위해 시대 상황적 요구에 따른 최적화 문제 해결의 접근 방식을, 전통적 의미의 고전 최적화, 시스템적 사고 기반의 의사결정을 다루는 근대 최적화, 그리고 다학제적·복합학적·동적·확률적 시스템에서 발생하는 의사결정 문제를 다루는 현대 최적화로 구분하여 발전 과정을 논의한다. 또한, 현대 최적화의 범위를 넘어선, 확장된 개념에서 바라본 시스템 최적화의 미래 역할과 양자 컴퓨팅 기반 최적화의 가능성을 전망한다. 본 논문은 기존 문헌을 종합 분석하는 조사(survey) 논문을 지양하고, 산업공학 전공자들이 시스템 최적화의 미래 방향성을 논의할 수 있는 기초를 제공하는 것을 목표로 한다.

산업공학에서 주된 분석 대상인 시스템은 인간, 기계, 사물 등 물리적 구성 요소와 이들 개체의 속성 및 상호작용 관계를 나타내는 다양한 정보에 의해 구성되는 메타 구조체이다. 산업공학의 근간을 이루는 시스템적 사고는 시스템 구성요소 각각의 효율성/효과성을 개별적으로 최대화하기보다는 이들로 구성된 시스템 전체의 성능을 제고하는 접근 방식을 추구한다. 1900년대 초반 산업공학의 효시로 알려진 프레드릭 테일러(F. Taylor)는 효율적인 경영 관리는 법칙과 규칙, 원리를 사용하는 과학의 영역으로 보아야한다고 주장하며, 생산성 향상은 소수의 우수한 작업자 선택에 의존하기보다는 작업 방식의 표준화와 인센티브 제도를 통해 일반 작업자를 체계적으로 훈련시키고, 직관과 경험에 의존하지 않는 체계적인 관리방법론을 적용해야 달성할 수 있다고 강조했다(Taylor, 1911). 방점은 시스템 분석에 기반을 둔 과학적 관리 방법론의 설계, 분석, 생성, 실행이 산업공학의 본질을 정의한다는 데 있다.

이러한 관점에서 경영과학적 접근 방식은 과학적 관리 방법을 위한 필수 도구에 해당한다. 특히, 경영과학 분야에서 처방적 접근으로 분류되는 시스템 최적화는 의사결정 분석 목적에 따라 대상 시스템의 분석 범위를 설정하고, 대상 시스템에서 관찰된 데이터를 정보 단위로 가공한 후, 시스템 구성 요소 간의 상호관계 및 정보 교류를 논리적 구조 수식으로 표현하고, 표현된 수식의 최적해를 찾는 과정을 포함한다. 넓은 의미에서, 전통적 의미의 수학적 또는 고전적 최적화는 산업공학에서 다루어 온 시스템 최적화 영역과 큰 교집합을 형성한다.

고전적 최적화는 효율적 해 ‘탐색’을 위한 문제 속성의 이론적 이해가 주된 목표인 반면, 산업공학에서 다루는 시스템 최적화는 ‘의사결정’과 ‘탐색’이 병합된 양상을 가지며 차별화된다. ‘의사결정’ 요소는 대상 시스템을 정의하고 탐색 방법의 효율성을 결정하는 데에 중요한 역할을 한다. 이러한 의사결정 요소를 포함하는 시스템 최적화는 이미 산업공학에서는 잘 알려진 연구 분야로서 기존의 생산 시스템 분석을 포함한 다양한 경제․사회 시스템 분석에 적용되어 왔다. 최근에는, 빅데이터와 기계학습 등 인공지능 시스템의 발전과 함께 최적화의 중요성이 새롭게 부각되고 있다.

빅데이터와 인공지능은 시스템 최적화 학문의 진화 방향에서 볼 때 필연적으로 등장하는 연구 주제이자 동시에 지속적 관심과 탐구가 요구되는 미래 도전 과제이다. 기존에 연구된 분석 대상 시스템들을 통합하여 얻게 되는 거대 시스템이나, 세분화된 관찰에 의해 얻어지는 미시 시스템에서 공통적으로 나타나는 빅데이터 분석과, 이를 통해 얻게 되는 심층 지식의 지능화 과정의 이해는 기계학습 및 인공지능의 중요한 연구 주제이다. 시스템 최적화 관점에서 보면 분석 대상 시스템 규모가 커짐에 따라 분석 소요 시간을 단축하기 위한 방법론 개발과 논리 구조 표현 방식의 획기적 개선 등이 주요 연구 주제이다.

산업공학의 ‘관리’ 관점에서, 시스템 최적화는 효율적 관리를 위한 ‘계획’과 관련된 의사결정에 주된 초점을 맞춰 왔다. 그러나, 시간의 변화에 따른 시스템의 동적 변화와 확률적 상황 변화에 대처할 실시간 ‘통제’를 가능하게 하는 시스템 최적화가 미래 사회에서는 중요한 역할을 할 것으로 전망된다. 이 경우, 초거대시스템을 대상으로 신속하고 효과적인 의사결정을 실행하기 위해 새로운 미래형 계산 패러다임을 어떻게 효율적으로 접목하느냐가 실시간 시스템 최적화 연구에 중요한 이슈로 부상하게 된다.

이 논문에서는 이들 이슈를 포함한 시스템 최적화 관련 주요 쟁점 사항들을 다룬다. 시스템 최적화 발전 과정을 역사적 전환점을 제공하는 사건(발견)들 중심으로 그 (시대적) 의미와 함께 살펴보고, 현대 시스템 최적화의 현황과 접근법들, 그리고 산업체에서 활용되는 실제 사례들을 검토한다. 또한, 빅데이터와 인공지능 등을 포괄하는 확장된 개념의 단일 프레임 시스템 최적화 모형을 제시하고, 미래 사회 시스템 최적화 문제를 해결하기위한 새로운 해 찾기 방법론 및 새로운 논리구조 표현 방식에 근거한 수학적 모형화의 필요성에 대해 논한다.

이 논문은 다음과 같이 구성된다. 다음 2장에서는 시스템 최적화와 관련된 발전사를 살펴보고, 제3장에서는 현대 시스템 최적화의 동향과 중요한 현실 산업체 응용을 다룬다. 제4장에서는 양자 컴퓨팅 관련 시스템 최적화의 역할을 중심으로 미래 시스템 최적화 연구 방향을 점검한다. 마지막으로, 제5장에서는 시스템 최적화 저변 확대를 위한 도전 과제와 몇 가지 관련 제언을 제시한다.

2. 최적화 및 경영과학의 발전사

많은 의사결정 문제는 암묵적으로 최적화 문제에 해당하며, 그 근저에는 대응하는 시스템이 존재한다. 원시인들이 사냥을 나갈 때에도 탐색 경로와 시기를 최적으로 결정하려 했다고 볼 수 있다. 최적해는 정의된 시스템에 의해 결정되므로, 원시인의 관점에서 이 문제는 4-5개의 대안 중 하나를 선택하는 매우 단순한 구조의 이산 최적화 문제에 해당한다. 그러나 최적화가 ‘독립된’ 연구 분야로 주목받기 시작하는 시기는 17세기 중반에 들어서다.

2.1 고전적 최적화

최적화가 의사결정과 관련된 학문적 가치를 갖기 시작한 시점은 1947년 댄치그(GB Dantzig)에 의해 선형계획법과 심플렉스 알고리즘이 소개된 시기 전후로 볼 수 있다. 그 이전 시기에는 최적화 연구는 주로 수학의 변방에 있는 소분야로 여겨졌다. 1630년대 페르마(P. Fermat)에 의해 처음으로 미분 가능한 일반 함수의 국지적 극대값과 극소값을 찾기 위한 문제 min_x∈R¹f(x)에 대해 일반적 접근법이 소개되고, 1670년대 뉴턴(I. Newton)의 미적분학에 기반한 계산 방식이 개발된 이래, 1755년 오일러(L. Euler)가 다변수 함수의 극대값과 극소값 문제 min_x∈Rⁿf(x)를 다루었고, 1799년 라그랑지(G. Lagrange)가 방정식 제약식을 포함한 다변수 함수의 최적화 문제 min_x∈Rⁿ{f(x)|g_j(x) = 0, j ∈ E}로 연구를 확장시켰다. 이와 같은 일련의 연구는 고전적 의미의 최적화 연구에 해당한다. 컴퓨터 개발 이전 시기인 이 시대에는 주로 최적화 문제의 적용 범위 확대와 함께 고유한 수학적, 이론적 속성에 대한 연구가 주류를 이뤘다. 한편, 이 시기 뉴턴과 가우스(J. Gauss) 등에 의해 최적화 문제의 속성 연구 외에도 극대/극소 문제의 해를 찾기 위한 반복 계산 방법론이 제시되기도 했다.

이차함수 f(x) = ax² + bx + c의 극대/극소값을 구하는 일반식은 1630년대 이전에 이미 알려져 있었으며, 가우스, 갈릴레이(G. Galilei), 페르마 등에 의해 다양한 특수 구조를 갖는 함수의 극대/극소값을 분석적으로 구하는 방식들이 알려져 있다. 예를 들면, 두 이차함수의 분수함수 f(x) = (x² + x + 1) / (x² + 2x + 3)값의 범위가 $$ 2\left(3-\sqrt{3}\right)\le f\left(x\right)\le 2\left(3+\sqrt{3}\right)$$라는 결과는 복잡한 최적화 기법이 아닌 수학식 전개를 통해 얻을 수 있다(Pardalos et al., 2009). 이 시기 최적화 연구는 최적해의 속성 파악과 탐색 방식에 대한 일반적 연구가 주를 이루었다. 예를 들면, 슈타이너 트리(Steiner tree) 문제의 시초로 알려진, 3개 좌표 (a_i, b_i), i = 1, 2, 3 로부터의 거리 합을 최소화하는 중앙위치(x, y)를 결정하는 문제인, $$ \mathrm{m}\mathrm{i}\mathrm{n}f\left(x\right)=\sum \sqrt{{\left(x-a_i\right)}^2+{\left(y-b_i\right)}^2}$$는 이미 1800년대 기하적 분석에 의해 해를 찾을 수 있음이 밝혀지고, 이후 다수 좌표의 문제로 확장되어 여러 수학자들의 관심을 끌게 된다. 이를 n개의 좌표에 다수의 중간 위치(x_k, y_k)를 사용하여 구성된 네트워크에서 이동거리를 최소화하는 현재의 슈타이너 트리 문제는 가우스가 슈마커(H. Schumacher)에 1836년 보낸 편지에서 제기되었다(Pardalos et al., 2009).

고전적 최적화 시기에서 근대 최적화로의 전환은 몬지(G. Monge)와 함께 수송이론을 창시하고 노벨 경제학상을 수상한 수학자 칸토로비치(L. Kantorovich)에 의해 시작되었다. 그의 수송 계획 이론은 댄치그에 의해 개발된 선형 계획법의 원형으로 간주되기도 한다.

Figure 1.

Steiner Tree for Four Points(Wikipedia)

2.2 근대 최적화

1947년 선형 계획법이 소개되며, 고전적 최적화는 중요한 변화를 맞게 된다. 의사결정 요소를 명시적으로 포함하는 시스템 최적화와 함께, 컴퓨터를 이용한 기계적 계산 능력의 활용이 본격화되었다. 근대 최적화 모형은 앞서 언급한 고전 최적화 문제를 포함하여 다음과 같이 압축적으로 표현될 수 있다.

$\[ {\mathrm{m}\mathrm{i}\mathrm{n}}_{x\in X}f\left(x\right) \]$

이 모형은 의사결정 문제의 해 공간 범위를 집합 X로 그리고 의사결정 문제의 평가함수를 f : X → Y로 확장한 시스템을 의미하며, 함수 f와 집합 X와 Y의 성격에 따라 다양한 범위의 최적화 모형을 구성하게 된다. 예를 들어, 함수 f가 벡터 함수인 경우에는 다목적 최적화 모형이 형성되고, 집합 X가 볼록(convex) 집합이며 f가 볼록 함수인 경우 볼록함수 최적화모형(convex program)을 이루게 된다. <Table 1>은 함수 f, 집합 X에 대한 변화에 따라 최적화 문제를 분류한 결과를 요약한 도표이다. 이 표에는 대표적 최적화 모형들이 포함되어 있으며, 일부 모형이 포함하는 하위 모형들, 예를 들어 수송 모형이나 네트워크 흐름 모형, 또는 동적 계획법과 같이 해 찾기 방법론에 해당하는 내용은 제외되어 있다.

Table 1.

Classification Table of Optimization Problems Based on Changes in Function f and Set X

선형계획 모형은 이전의 고전 최적화에서 다루던 문제 적용 범위와 비교할 때 사회과학과 경제 응용 영역을 포함한 폭넓은 영역에 적용될 수 있어, 과학적 관리학으로 알려진 산업공학에서 특히 유용하게 사용되기 시작했다. 특히, 이 모형의 해결 방식으로 제시된 심플렉스 알고리즘은 반복계산 수행 능력이 요구되어 컴퓨터의 역할이 중요해졌다. 이러한 이유로 선형계획의 중요성은 산업공학 시각에서 특별한 의미를 갖는다. 선형계획 모형은 처방적 데이터 분석 모형의 기초가 되었으며, 심플렉스 알고리즘은 계산 최적화의 현실 적용 시대를 여는 계기로 간주된다.

1940년대 이후, 근대 최적화는 비약적 도약을 이루게 된다. 1950년대 벨만(R. Bellman)이 소개한 동적계획법(dynamic programming), 1951년에 소개된 비선형계획 모형의 최적해 조건(Karush-Khun-Tucker, KKT conditions)과 이에 기반한 다양한 알고리즘 개발 연구, 다변수 이차 함수 최적화 문제를 해결하기 위한 다양한 해법 절차와 그 문제 속성에 대한 연구, 포드(L. Ford)와 풀커슨(D. Fulkerson)에 의해 연구된 그래프 및 네트워크 흐름모형 분석과 이후 이를 기반으로 한 이산 변수 최적화와 조합 최적화 등은 현재에도 다양한 형태의 최적화 문제로 이어져 해결방법에 대한 연구가 계속되고 있다. 이들 연구는 공통적으로 국지적 최적해(local optimizer)를 찾는 것을 목표로 했으며, 국지적 최적해가 전역 최적해가 되는 조건 등에 대한 연구가 다수 진행되었다.

1950년대 이래 최근까지의 시스템 최적화에 대한 시대적 연구 주제 변화 동향을 각 시대별 인용횟수에 따라 요약한 내용이 <Table 2>에 제시되어 있다. 구글 학술검색(https://scholar.google.com)을 활용해 연대별로 최적화 관련 논문을 1,000건씩 검색하고, 가장 많이 인용된 논문들을 중심으로 연구 주제의 변화를 요약했다.

Table 2.

Impact of Optimization Research Achievements in the Modern and Contemporary Periods on the Future: The Five Most Influential Papers by Decades

<Table 2>에 나타난 바와 같이, 최적화 연구는 1950-60년대의 선형계획법과 동적계획법 연구를 시작으로 1970년대 계산 복잡성 이론에 따른 최적화 문제 범위 확장과 조합 최적화의 발전을 통해 다양한 문제 해결로 확장되었다. 1980년대에는 컴퓨터 성능 향상을 기반으로 실질적 문제 해결을 위한 네트워크 최적화와 휴리스틱 기법이 부상했고, 1990년대에는 유전 알고리즘(genetic algorithms)과 같은 진화 알고리즘이 복잡한 최적화 문제를 다루는 데 사용되기 시작하였다. 2000년대에는 메타휴리스틱과 비선형 최적화, 그리고 기계학습 기반 기법이 발전했고, 2010년대에는 확률적 경사 하강법 등 기계학습과 최적화의 통합이 이루어지면서 데이터 기반 최적화가 주목받았다. 2020년대에 이르러 강화 학습, 인공지능, 양자 컴퓨팅이 결합된 적응형 최적화 기법들이 등장하며, 고차원 문제와 동적 최적화 문제에 대한 새로운 해결책으로 자리 잡고 있다.

Figure 2.

An Analysis of the Citation Counts and Trends in Interest over the Decades for the top 10 Most Cited Publications in the Field of Optimization

또한, <Figure 2>는 구글 학술검색을 기준으로 최적화 관련 분야에서 인용 횟수가 가장 많은 10대 저술서를 기준으로 각 연대별 인용 횟수 및 관심도를 도표화한 결과이다.

연구에 참조되는 최적화 관련 저서들의 관심도를 나타내는 그림(<Figure 2>)에서 볼 수 있듯이, ‘Computers and Intractability (1979)’와 ‘Convex Optimization(2004)’이 각각 79,288회와 77,538회의 가장 높은 총 인용 수를 기록하고 있으며, 특히 후자의 경우, 비교적 최근에 출판되었음에도 2000년대에 급격한 인용 증가를 보였다. 1970년대 발표된 초기 출판물들은 1980년대에 처음 주목을 받기 시작했으며, 이후의 연구들이 2000년대와 2010년대에 특히 많은 인용을 받았다. ‘Genetic Algorithms +Data Structures = Evolution Programs(1999)’와 같은 1990년대의 자연 모사(nature inspired) 최적화 기법들은 2000년대에 인용 수가 크게 증가했으나 이후 소폭 감소하며, ‘Nonlinear Programming(1995)’, ‘Convex Optimization(2004)’과 같은 출판물들로 관심이 분산되었다. 최근에는 주요 출판물들이 일정 수준의 인용을 유지하고 있다.

3. 현대 시스템 최적화의 동향 및 산업체 응용

선형계획이 고전 최적화에서 근대 최적화로의 전환점에 해당한다면, 조합 최적화(combinatorial optimization)로도 불리는 이산 변수 최적화는 비선형 최적화와 함께 현대 시스템 최적화를 대표하는 연구주제이다. 조합 최적화는 이진 결정 변수인 ‘예’와 ‘아니오’를 사용하여 논리적 의사결정 추론 방식을 수식으로 표현할 수 있는 능력을 제공한다. 예를 들어, 업무 A를 수행하려면 업무 B를 먼저 수행하거나 업무 A와 B는 동시에 수행할 수 없다는 논리적 제약을 수식으로 나타낸다. 업무 A(B)를 수행할 경우를 x = 1 (y = 1), 수행하지 않는 경우를 x = 0 (y = 0)으로 표기하면, x ≤ y, y ∈ {0, 1} 또는 xy = 0, x, y ∈ {0, 1}로 나타낼 수 있다. 이산 변수 최적화는 산업공학의 관리(management) 방법론에 직관 대신 논리 기반의 과학적 접근법을 적용 가능하게 하는 강력한 도구이다.

이산 변수 최적화 모형에 대한 알고리즘들은 이미 근대 최적화 시기에 활발히 연구되어 분지한계법(branch and bound method), 절단면법(cutting plane method), 동적계획법 등 대표적 접근법을 포함한 다양한 방법론이 다수 개발되었다. 그러나, 이들 방법론은 암묵적 또는 명시적 열거법에 해당하여 작은 규모의 문제에서만 최적해를 얻을 수 있었다. 현대 최적화 시기에 들어서면서 비로소 현실적 규모의 모형을 범용 솔버를 통해 다룰 수 있게 된다. CPLEX와 Gurobi 같은 선형(정수)계획 모형 범용 솔버가 사용되는 현대 최적화 시기는 1970년대 말 카치안(L. Khachiyan)이 선형계획 문제을 위한 이론적 다항 시간 알고리즘(ellipsoid algorithm)을 발표하고, 곧 이어 카마카르(N. Karmarkar)가 내부점 해법 절차(interior point algorithm)을 제시하면서 시작되었다.

현대의 최적화 모형들은 다양한 논리적 상황을 표현할 수 있는 장점을 가지고 있다. 그러나 1970년대 중반에 완성된 전산학의 계산 복잡도 이론에 따르면, 이들 모형의 대부분은 NP-완전(NP-Complete) 문제에 속하는 어려운 문제들이다. NP-완전 문제 집단에 속한 문제들은 이론적으로 동일한 난이도(시간 복잡도)를 가지며, 이 집단의 문제 중 하나라도 쉬운 문제 집단(P)에 속한다면, 모든 NP-완전 문제들이 쉬운 문제로 분류된다는 특성을 가지고 있다. P와 NP-완전 문제들이 서로 구분되는 집단인지 여부는 여전히 이론적으로 밝혀지지 않은 상태이다. 1970년대 중반, 쿡(S. Cook)은 논리적 문제인 충족 가능성 문제(SAT: Satisfiability Problem)가 NP-완전 문제임을 증명하면서, 이 문제가 P에 속하지 않은 경우, NP-완전 문제들은 문제를 설명하는 데이터 크기에 대해 다항식 시간 내에 최적해를 구하는 것이 불가능하다는 점을 제시하였다. 이로 인해 휴리스틱 접근법은 최적화 연구분야에서 실용적 의미뿐만 아니라 학술적으로도 중요한 위치를 차지하게 되었다.

<Table 1>에서, 가능해 영역이 정수 격자 집합의 부분집합일 경우, 이는 이산 변수 최적화 문제에 해당한다. 이러한 모형은 논리적 구조를 수식화하여 연산을 통해 의사결정을 가능하게 만드는 중요한 도구로 발전해왔다. 산업공학뿐만 아니라 물리, 컴퓨터, 경영학 전공자들도 익숙하게 알고 있는 방문 외판원 문제(traveling salesman problem)(실제로는 최소 거리 해밀토니안 경로 문제가 더 정확한 표현)는 이산최적화 모형의 대표적 사례에 해당한다.

방문외판원 문제는 NP-완전 문제임에도 불구하고, 다면체 이론에 기반한 다양한 최적화 알고리즘을 통해 현재 약 600개 도시 규모의 문제를 쉽게 해결할 수 있으며, 85,000여 개 도시 문제의 최적해를 구하는 것도 가능하다. 또한, 약 200만 개 도시 문제에 대해서도 최적해로부터 0.4% 이내의 입증 가능한 범위 내에서 현실적으로 유용한 해를 찾을 수 있다(Applegate, 2006). 이 같은 발전은 또 다른 최적화 이론의 갈래에 해당하는, 분지한계법과 절단면 방법론을 결합한 분지절단면법(branch and cut method)에 기인한다. 이론 측면에서 오랜 연구 역사를 갖는 절단면법은 선형정수계획 문제의 가능해 영역을 다루는 다면체 이론을 활용하여 최적화 문제를 해결한다.

이산 최적화 모형에서 높은 품질의 해를 찾기 위해서는 근대 최적화 연구에서 개발된 다양한 모형과 방법론뿐만 아니라 현대 시스템 최적화 방법론이 필수적이다. 현대의 시스템 최적화는 기존 이진 컴퓨터가 갖는 단점을 보완하기 위해, 알고리즘 개발 측면에서 다양한 새로운 발상의 전환을 맞이하고 있다. 근대 최적화가 주로 국지적 최적해를 찾는 데 집중했다면, 현대 최적화는 전역 최적해에 가까운 해를 빠른 시간 내에 찾을 수 있는 다양한 방법론 연구에 초점이 맞춰져 있다. 근/현대를 막론하고 시스템 최적화의 관건은 문제 해결을 위한 기저 시스템 구조의 파악과 수식적 표현, 그리고 이 수학적 모형의 해결을 위한 ‘빠르고’ ‘정확한’ 해 탐색 방법론 개발 두 가지 영역으로 요약할 수 있다. 물론, 다양한 형태의 의사결정 모형을 신규로 개발하는 일도 포함되나, 이는 주로 산업공학 또는 해당 응용 도메인 지식이 풍부한 해당 분야의 역할로 보는 것이 타당할 것이다.

현대 최적화는 다양한 형태의 이산 최적화 문제에서 전역 최적해에 가까운 좋은 최적해를 찾기 위한 다양한 휴리스틱 개발 연구에 집중하고 있다. 1970년대 홀랜드(J. Holland)에 의해 이론적 근거를 마련하는 유전 알고리즘, 1983년 커크패트릭(S. Kirkpatrick), 겔라트(C. Gellatt), 베키(M. Vecchi)에 의해 조어된 담금질 기법(simulated annealing), 1989년 글로버(F. Glover)에 의해 제시된 터부 탐색(tabu search), 1990년 도리코(M. Dorigo)에 의한 개미 군집 최적화(ant colony optimization), 1995년 케네디(J. Kennedy), 에버하트(R. Eberhart), 시(Y. Shi)에 의해 소개된 입자 군집 최적화(particle swarm optimization) 등은 이후 수많은 변형 방법론을 생성하며 변화를 거쳐 진화하고 있다. 기본형 타부 탐색을 제왼하면, 이들의 공통점은 기존 최적화 연구에서 주로 사용되던 접근 방식인 확정적 방식으로 이동하는 점대점 탐색에서 확률적 이동 방식으로 탐색하는 방법으로 전환한 점이다. 즉, min_x∈Xf(x)의 전역 최적해를 찾기 위해 전통적/근대적 최적화의 해 탐색 방식은 갱신 방식 x⁺ ← x + λs과 확정적 탐색 방향 s를 사용하여 새로운 탐색 해를 찾는 반면, 현대 최적화는 X⁺ ← X + ΛS로 해 집합 일부로부터 확률적 탐색 방향 S를 사용하여 군집적 탐색 방식을 사용해 새로운 해 탐색을 실행한다. 여기서, X는 해 ‘벡터’(벡터의 벡터)를 표기한다. 이들 접근 방식의 또 다른 공통점은 국지적 최적해를 벗어나기 위해선 현재 탐색 중인 해보다 더 나쁜 해로의 이동이 필요하다는 점을 인식하고 이용한다는 점이다. <Table 3>은 대표적인 메타휴리스틱 알고리즘들을 위와 같은 관점에서 설명한 표이다.

Table 3.

Classification of Metaheuristic Update Mechanisms

현대 시스템 최적화는 컴퓨터 연산 능력의 향상에 힘입어 더 빠른 속도로 더 큰 시스템의 해를 찾기 위한 방법론의 필요성에 따라 개발된 메타휴리스틱 접근법들이 주류를 이룬다. 특히, 실시간 통제(real-time control) 영역이 관리에 포함되면서, 계산 기반의 확장된 직관 접근법이 실시간 최적화에 사용되기 시작한다. 이 새로운 접근법은 고전/근대/현대 최적화 접근법을 혼용하며, 컴퓨터 계산 능력의 비약적 향상에 힘입어 어렵고 복잡한 시스템 최적화 문제의 ‘현실적’ 해를 제시해 주게 된다. 예를 들면, 차량 경로 문제(vehicle routing problem)의 해결에서는 근대적 최적화 접근법인 다면체 이론 기반의 분지절단 방법론에 인공지능을 포함한 메타휴리스틱 기반의 절단면 생성과 우수한 상한(upper bound)을 제공하는 잠재적 해 생성을 통해 기존 접근법으로는 얻기 어려운 해를 도출할 수 있게 된다(Gournaris, 2011).

현대 최적화의 적용 범위, 접근 예시, 그리고 고전적 및 근대적 접근법의 필요성은 최적화 관련 추세 분석과 현실 기업 사례 분석을 통해 잘 드러난다. 국내 등록된 특허 자료 중 ‘최적화’, ‘휴리스틱’, ‘기계학습’, ‘인공지능’ 키워드를 포함한 자료의 추세를 파악한 결과(<Figure 3>), 최적화 관련 실용 사례가 2000년대 이후 꾸준히 증가하는 추세를 보였으나, 2018년도 이후 인공지능 기반 해결 방법론들이 눈에 띄게 주목받고 있음을 알 수 있다.

Figure 3.

Number of Domestic Patent Containing Specific Keywords: Optimization, Heuristic, Machine Learning, AI

이러한 추세는 2024년 현재까지 국내에 등록된 특허 자료 중 ‘최적화’ 키워드를 포함한 특허의 기술 분류 코드에 따른 빈도 수 추세를 도식화한 <Figure 4>에서도 잘 나타나 있다.

Figure 4.

Yearly Frequency of Optimization-Related Patent by IPC Code

2000년대 들어 ‘최적화’ 키워드를 포함한 특허가 다양한 분야에서 점차 등장하기 시작했으며, 초기에는 교통 관리 시스템과 광학 시스템 분야에서 증가세가 관찰되었다. 2010년대에는 전자 상거래, 광고/마케팅 데이터 처리, 신경망 기반 데이터 처리, 의료 및 헬스케어 시스템과 같은 새로운 분야에서 최적화 관련 특허가 급속히 증가하였다. 2020년대에 이르러 일부 분야에서 정체되거나 감소하는 경향이 있지만, 최적화 관련 특허는 여전히 다양한 기술 분야에서 널리 다변화되고 있다.

이러한 시스템 최적화의 응용 사례 추세는 연구에서도 유사하게 나타난다. 이를 파악하기 위해, 최적화 분야의 산업적 적용 사례를 다룬 약 97,000편의 논문 제목 및 초록 데이터를 대상으로, 데이터 전처리, 분석, 시각화 과정으로 구성된 실험을 수행하였다. 데이터 전처리 단계에서는 토큰화, 불용어 제거, 어간 추출 등을 통해 텍스트를 정제하였다. 키워드 기반 분석 단계에서는 초기 키워드 목록을 수립한 후, 정규표현식, TF-IDF, NLP 기반 매칭을 활용하여 특정 방법론 및 적용 분야의 키워드를 데이터에서 식별하였다. 또한, 사전에 정의된 포함 관계 사전을 통해 상위 및 하위 키워드 구조를 반영하고, TF-IDF 기반 유사도를 이용하여 추가적인 관련 키워드를 도출하고 분석에 활용하였다. 이러한 과정을 통해 텍스트 데이터를 특정 키워드와 매칭하여 구조화된 정보를 생성하고, 주요 키워드의 단어 구름 표현(<Figure 5>)과 연대별, 적용 분야별, 사용된 방법론별로 그룹화하여 시각화(<Figure 6>)하였다.

Figure 5.

Word Cloud for Methodologies and Application Areas

Figure 6.

Decadal Trends in Application Areas and Methodologies of Optimization

위 실험 결과(<Figure 6>)는 적용 분야와 문제 해결 방법론 간의 관계 변화를 시대별로 보여준다. 1950년대부터 1980년대까지는 최적화 기법의 산업적 활용 빈도가 낮았고, 생산시스템 최적화가 주요 분야였다. 1990년대에 접어서면서 최적화 기법의 산업적 적용이 급격히 증가하며, 제조, 에너지, 공급망 관리 분야가 주요 영역으로 자리잡았고, 특히 메타휴리스틱의 활용이 두드러졌다. 2000년대에는 산업 전반에서 최적화 기법의 활용 빈도가 전반적으로 확대되었고, 메타휴리스틱, 강건 최적화, 혼합 정수 선형 계획법의 사용이 크게 증가하였다. 2010년대에는 메타휴리스틱 활용이 이전에 비해 약 3배 증가하여 모든 분야에서 확대되었으며, 기계학습 기반 방법론의 활용 또한 크게 증가하였다. 2020년대에도 메타휴리스틱이 핵심적 역할을 수행하는 가운데, 강건 최적화, 조합최적화, 기계학습 접근법이 그 뒤를 이어 자주 사용되었다. 적용 분야 측면에서는 2020년대 자료가 5년간의 데이터라는 점을 고려할 때, 제조 분야는 감소하는 추세에 있고 수송 최적화, 운영 관리, 에너지 최적화는 증가하는 추세를 보인다.

근대 및 현대 최적화 연구에서 제시된 시스템 최적화 기법들은 산업 현장에서의 응용으로 이어지고 있으며 실제 기업 문제를 해결하는 데 중요한 역할을 하고 있다. 예를 들어, 공급망 관리, 제조 공정 최적화 뿐만 아니라 서비스 및 운영 관리에서도 연구를 통해 개발된 최적화 기법들이 현실 문제에 적용되어 실질적인 성과를 내고 있다. <Table 4>는 국내 최적화 컨설팅 기업의 과제 수행 사례를 예시로 제시한다.

Table 4.

A Case Study of a Leading Domestic Optimization Consulting Firm

<Table 4>에 나타나듯이 국내 산업계에서 시스템 최적화 응용은 다양한 분야에 적용되고 있으나, 사용된 최적화 기법은 근대 최적화 기법이 주로 사용되고 기계학습이나 메타휴리스틱 같은 현대 최적화 기법은 제한적으로 적용되고 있다. 이러한 상황은 산업 현장의 기존 시스템과의 통합에 따른 상당한 기술적 조정의 필요, 대규모 데이터와 고성능 연산 자원 확보에 요구되는 높은 구현 비용, 산업 현장의 즉각적인 성과 중시 환경으로 인해 발생한다. 이에 따라, 컨설팅 기업은 근대적 최적화 기법과 현대 기법을 적절히 혼합해 현실적이고 실행 가능한 솔루션을 제공하는 데 중점을 두고 있다. 현대 시스템은 복잡한 상호작용과 다변수로 이루어진 동적 환경 속에서 운영된다. 예를 들어, 검색광고 키워드의 입찰가를 결정하기 위해서는, 실시간으로 이루어지는 입찰에 의한 상대적 입찰가 순위와 해당 키워드의 광고 효과를 동시에 고려하여야 한다. 이러한 특징을 가지는 복합적인 문제를 실질적으로 해결하기 위해서는 앞서 언급된 현대 최적화 기법의 활용이 필수적이다.

4. 미래의 최적화 전망과 양자 컴퓨팅의 역할

시스템 최적화 연구는 의사결정 응용 분야의 확대 적용과, 대규모 최적화 모형의 해를 효과적으로 탐색하는 알고리즘 개발이라는 두 가지 주요 방향에서 기존 연구 흐름을 이어갈 것으로 보인다. 구체적으로, 기존 동질적(homogeneous) 시스템에서 이질적/복합적(heterogeneous) 시스템으로의 확장 연구와 더불어, 규모 확장성(scalability)과 해의 품질(solution quality)을 보장하는 탐색 방법론에 대한 연구가 더욱 활발하게 이루어질 것으로 예상된다. 공급망 관리와 다국가 관세 시스템의 연계 모형, 초대규모 에너지 및 환경 시스템의 복합 관리 모형, 대규모 기업 집단의 자본구조 유지 전략 관리와 국제 금융 시스템 변동 연계 모형 등 거대규모 시스템 분석이 이에 해당한다. 또한, 신소재 물성 분석을 위한 이미지 자동 획득, 신약 개발을 위한 단백질 합성, 혁신 기술 시스템 분석 등이 미래 사회 최적화가 적용될 주요 예시에 해당한다.

이진(디지털) 컴퓨터의 하드웨어 성능 향상과 알고리즘 발전을 통해 현재의 계산 최적화 연구 방향성을 일정 수준까지 유지할 수 있으나, 미래 사회에 예상되는 초대규모의 최적화 문제를 해결하기 위해서는 새로운 계산 패러다임에 적합한 새로운 계산 최적화 이론 모형 개발과 접근법이 필요하다. 이런 측면에서 시스템 최적화 연구 분야에서 계산 최적화의 중요성은 점차 강조되고 있다. <Figure 7>은 시스템 최적화, 산업공학, 컴퓨터 성능의 발전 과정을 요약하여 시각적으로 제시한다. 그림에서, 새로운 성능의 컴퓨터 개발은 시스템 최적화의 주요 변화를 선도하며, 산업공학에서 다루는 주요 주제의 변화는 이러한 최적화 발전의 변곡점을 뒤따르는 양상을 보인다.

Figure 7.

Transformative Events and Evolutionary Trends in Optimization, Computing, and Industrial Engineering over Time

시스템 최적화의 미래 이슈들을 대표하는 주요 연구 주제는 아래와 같이 요약될 수 있다.

• 1. 비선형 이산 최적화 모형의 최적해 입증을 위한 계산 최적화 이론 연구: 최적화 기초 모형들 중 NP-난해인 문제들과 기술 혁신에 따른 미래 사회 최적화 문제에 대해 최적해를 계산적으로 입증하기 위한 이론적 특성 규명 및 이를 이용한 새로운 알고리즘 개발
• 2. 확률적, 동적 변화를 포함한 시스템 대상의 새로운 실시간 의사결정 모형 개발: 확률적, 동적 변화 요소를 고려한 이질적 복합 시스템에서 발생하는 실시간 의사결정 모형 개발 및 계산 최적화 알고리즘 개발
• 3. 새로운 메타 휴리스틱 개발 및 이론적 속성 발견: 초대규모 최적화 문제 해결을 위해 기존 메타휴리스틱의 성능을 대폭 능가하는 새로운 메타휴리스틱 최적화 접근 방법의 개발
• 4. 빅데이터와 기계학습에서 ‘설명 가능한 AI’ 실현을 위한 시스템 최적화 연구: 데이터 기반 의사결정 과정과 그 결과의 신뢰성과 투명성을 확보하기 위해, ‘설명 가능성’을 강화한 빅데이터 분석 및 기계학습을 위한 시스템 최적화 기반의 새로운 분석방법론 개발
• 5. 양자 컴퓨팅을 활용한 새로운 모형화 방법론 및 양자 알고리즘 개발: 앞선 항목들에서 언급된 문제들을 해결하기 위한 양자 컴퓨팅 기반의 최적화 방법론 및 알고리즘 개발

위 연구 주제들은 기존 시스템 최적화 연구의 연장선에서 접근할 수 있지만, 후반의 두 가지 주제는 시스템 최적화 연구 관점에서 새로운 이슈로, 향후 상당한 연구 자원의 투입이 필요할 것으로 전망된다.

4.2 양자 컴퓨팅 개요

양자 컴퓨터는 기존 이진 디지털 컴퓨터와 완전히 다른 컴퓨팅 체계를 가진다. 하드웨어 외관상으로는 냉각 목적의 장치가 커다란 부피를 차지하고 양자 정보처리 칩(QPU: Quantum Processing Unit)은 작은 손톱 크기에 불과하다. 양자 컴퓨팅은 양자역학 기본 가설을 중심으로, 중첩(superposition)과 얽힘(entanglement)이라는 양자적 특성을 활용하며 기존 디지털 이진 정보처리로는 불가능한 정보처리 능력을 갖는다. 물리학에 기반한 다양한 양자역학적 특성들이 다수 존재하고 이들을 활용하는 방식에 따라 기존 디지털 알고리즘과는 차별화되는 성능을 발휘한다. 양자 컴퓨팅 알고리즘의 핵심은 양자 병렬 처리 능력을 효과적으로 활용하는 데 있다.

양자역학 가설은 (1) 단일 큐빗 양자상태의 정의, (2) 양자상태의 변이에 대한 수학적 표현 (3) 양자상태 관측 값의 수학적 표현 (4) 다수 양자 큐빗 상태의 정의 등 네 가지로 나뉜다.

디지털 컴퓨터의 비트가 {0,1}의 한 상태를 나타내는 정보처리 단위인 것처럼, 큐빗은 양자 컴퓨터의 정보처리 단위에 해당한다. 큐빗의 상태 |ψ>는 힐버트 공간의 벡터로 아래와 같이 표현된다. 여기서, α와 β는 α^†α + β^†β = 1을 만족하는 복소수이다 (α^†는 켤레 복소수).

$\[ |\psi ⟩=\alpha |0⟩+\beta |1⟩ \]$

여기서 |0>과 |1>은 큐빗을 특정한 방식으로 측정했을 때 확률적으로 관찰되는 기저상태를 의미한다. 위 양자 상태를 갖는 큐빗은 기저 상태 |0>을 확률 |α|²로 기저 상태 |1>을 확률 |β|²로 관찰하게 된다. α와 β가 0이 아닌 경우에 위 상태를 |0>과 |1>의 중첩 상태라 부르며, 한 개 큐빗은 무한히 많은 양자 상태를 표시할 수 있어서 이진 비트 정보보다는 더 많은 잠재정보를 연산에 이용할 수 있게 된다. 양자의 중첩 상태는 이론적으로 양자 게이트라 불리는 유니터리 행렬을 적용하여 얻을 수 있다.

이진 디지털 시스템에서는 비트를 ‘0’에서 ‘1’로 바꾸는 행위를 ‘NOT’이라는 논리 게이트를 사용하여 실행할 수 있다. 즉, ‘0’이 아니면 ‘1’이기 때문에 ‘NOT’게이트 하나만을 통해서 상태의 전환이 가능하다. 그러나 양자 컴퓨팅에서는 양자 상태 |ψ>에 ‘NOT’을 취해 얻을 수 있는 상태(NOT|ψ> = α|1> + β|0>)이외에도 다른 상태들이 존재하고, 이들 상태로의 변이가 가능할 수 있게 하는 ‘NOT’이외의 연산자가 필요하다. 양자역학 두 번째 가설은 양자 상태의 변이가 유니터리 행렬을 이용하여 이뤄진다는 것이다. 즉, 유니터리 행렬 U는 양자 상태 |ψ>를 새로운 양자 상태 |ϕ>로 변환(|ϕ> = U|ψ>)한다. 세 번째 가설은 양자 상태의 측정과 관련되어 있고, 네 번째 가설은 다수의 큐빗 시스템으로 구성된 다중 큐빗 양자상태에 대해 정의하고 있다.

<Figure 8>은 양자 상태와 연산자를 도식화한 예시이다. 빨간 점은 동일한 위상을 가지는 기저 상태 |0>을 나타내며, 파란 점은 하다마드(Hadamard) 양자게이트를 통해 형성된 중첩 상태 $$ 1/\sqrt{2}|0⟩+1/\sqrt{2}|1⟩$$을 나타낸다. 초록색 궤적은 하다마드 양자게이트에 의한 양자 상태의 변화방식을 모사한다.

Figure 8.

Trajectory from a Basis State to a Superposition State on the Bloch Sphere(Kim et al., 2021)

위 양자역학 가설을 기반으로 한 양자 컴퓨터는 하드웨어 설계와 알고리즘 적용 방식에 따라 크게 두 가지 유형으로 구분된다: IBM을 중심으로 하는 게이트 기반 양자 컴퓨터와 D-Wave를 중심으로 한 단열 모사(adiabatic) 양자 컴퓨터. 게이트 기반 양자 컴퓨팅 알고리즘은 주어진 이진 정보(일반적으로 벡터 형식)를 다중 큐빗 양자 상태로 전환한 후, 설계된 양자 알고리즘에 따라 일련의 양자 게이트들 순차적으로 적용하여 초기 양자 상태를 변환한다. 최종적으로 변환된 다중 큐빗의 양자 상태를 측정하여 알고리즘의 해 값을 결정한다. 이 일련의 양자 게이트 구성이 양자 회로에 해당한다(<Figure 9>).

Figure 9.

The Quantum Circuit for Grover's Algorithm that Finds an Input x for the Function y = f(x), where f : B2 → B3(Jun, 2024)

게이트 기반 양자 컴퓨팅의 정확도는 게이트와 큐빗의 오류 범위에 의해 크게 좌우된다. 이러한 문제를 해결하기 위해 하드웨어 개선과 양자 오류 수정 알고리즘이 활발히 연구되고 있으나, 아직 현실 문제 해결에는 한계가 존재한다. <Table 5>는 IBM에서 발표한 양자 컴퓨팅 로드맵 중 최적화와 관련한 로드맵 단계를 요약하고 있다.

Table 5.

Description of IBMQ Roadmap for Optimization

단열 모사 양자 컴퓨터는 주로 QUBO(Quadratic Unconstrained Binary Optimization)라 불리는 이차 이진 변수 최적화 모형의 해를 양자 어닐링 과정을 통해 찾는다. 이산 최적화 문제의 해를 찾기 위해 열(heat)을 이용한 단열 과정을 디지털 컴퓨터로 모사한 휴리스틱인 담금질 기법에 대응하는 양자 어닐링 과정은 열 대신 전자기파를 이용하여 양자 상태에 단열과정을 물리적으로 구현하는 휴리스틱이다. 단열 모사 방식은 현재 게이트 기반 양자 컴퓨팅보다 상용화 과정이 빠르게 진행되고 있다. 아래 그림과 표는 D-Wave 양자 컴퓨터를 사용하여 최적화 문제를 해결하기 위한 절차 및 D-Wave에서 사용하는 큐빗 네트워크 구조와, 발표된 D-Wave의 산업체 협업 사례들을 나타낸다(<Figure 10>, <Table 6>).

Figure 10.

Illustration of the D-Wave Application Process and Method (Ziyaei et al., 2022)

Table 6.

The Industrial Applications of D-Wave

4.5 산업 적용 가능성과 전망

양자 컴퓨팅이 복잡한 최적화 문제를 해결하는 데에 많은 가능성을 제시하지만, 현재 기술 수준에서는 특정 산업의 일부 문제에만 제한적으로 사용될 수 있다. 예를 들어, 금융 분야에서의 포트폴리오 최적화, 물류 분야에서의 경로 최적화 문제 등은 양자 컴퓨팅의 높은 병렬 처리 능력을 통해 실질적인 효율성을 기대할 수 있는 사례들이다(Mohseni et al., 2017). 그러나 대규모 최적화 문제의 해결을 위해 양자 컴퓨터가 디지털 컴퓨터를 완전히 대체하기보다는, 근미래에는 디지털 컴퓨터와의 협력을 기반으로 한 체계적 하이브리드 접근 방식이 필요할 것으로 전망되고 있다(Li et al., 2017). 하이브리드 접근 방식에서, 기존 계산 자원 최적화 접근법들이 폭넓게 사용될 것으로 보인다.

양자 컴퓨팅은 디지털 컴퓨터의 한계를 넘어서 복잡하고 비선형적인 최적화 문제에 대한 새로운 해결 방안을 제시할 가능성이 크다. 특히 금융, 물류, 약물 개발 등 복잡한 계산이 요구되는 분야에서 양자 컴퓨팅이 제시하는 가능성은 매우 크다. 그러나 현재로서는 기술적 한계와 안정성 문제로 모든 최적화 문제에 즉각적인 혜택을 제공하기는 어렵다. 양자 컴퓨팅의 발전은 점진적으로 이루어질 것이며, 기술적 한계를 극복하기 위한 디지털 컴퓨팅과 양자 컴퓨팅의 협업 최적화 모델이 앞으로 중요한 역할을 할 것이다.

양자 컴퓨팅의 발전과제와 현실 적용 과제는 시스템 최적화와 밀접한 관계를 갖는다. <Table 7>은 양자 컴퓨팅 관련 해결해야할 이슈들 가운데 국내에서 진행된 일부 기존 연구들을 보여준다. 이들 연구 주제는 양자 컴퓨팅 관련 시스템 최적화 연구의 실험적 초기 시도로써 동일 주제에 대해 많은 추가 연구가 필요하다.

Table 7.

Research Cases from Domestic Quantum Computing System Optimization Laboratories

이와 관련하여, 시스템 최적화의 양자 컴퓨팅 관련 주요 연구 주제는 다음과 같이 전망할 수 있다.

• 1. 양자 이점을 보일 수 있는 ‘킬러 애플리케이션(killer application)’ 생성: 양자 컴퓨터의 가치 입증을 위해서는, 전통적 컴퓨터로는 해결이 어렵지만 양자 컴퓨터로는 효율적으로 해결할 수 있는 문제를 식별하고 정의하는 것이 필수적이다. 이를 위해 체계적으로 문제를 선정하고, 문제의 정의를 새롭게 정립하며, 문제 난이도를 분석하고 양자 알고리즘을 개발하는 과정이 필요하다. 시스템 최적화는 이러한 과정 전반에 걸쳐 새로운 관점을 제시하고 실질적인 양자 컴퓨팅 활용 사례를 도출할 도구로 사용될 가능성이 크다.
• 2. 양자 하드웨어의 기술적 문제 해결: 양자 컴퓨팅의 성능 향상과 안정적인 연산, 더 나아가 실질적 문제 해결을 위해 하드웨어적 한계를 극복하는 연구는 필수적이다. 관련해서 시스템 최적화가 적용될 수 있는 주요 연구 영역은 다음과 같다:
  • ① 큐빗 토폴로지(qubit toplogy): 양자 컴퓨터의 확장성과 연관된 큐빗 간의 물리적 연결성 및 상호작용 제약을 최적화하여 안정적인 양자 연산을 효율적으로 수행할 수 있게 하는 연구이다. 큐빗의 배열 및 연결 방식을 결정함으로써 효율적이고 안정적인 양자 연산이 가능하도록 설계한다.
  • ② 회로 최적화(circuit optimization): 양자 알고리즘과 연산 구현 시, 양자 컴퓨터의 물리적 제약을 고려하여 회로의 깊이와 폭을 최적화하는 방법론을 개발하는 것이 필요하다. 최적화된 회로는 노이즈에 대한 민감도를 줄이고 연산 속도를 개선하며, 양자 연산의 성공률을 높인다.
  • ③ 문제의 분해(decomposition) 및 완화(relaxation): 현실적인 문제를 해결하기 위해 문제를 실행 가능한 규모로 분해하거나, 실용적인 모형으로 완화하는 방식이 요구된다. 이러한 접근은 제한된 자원을 가진 양자 컴퓨터가 실질적인 해법을 도출할 수 있도록 지원한다.

위 연구 주제들은 시스템 최적화가 양자 컴퓨팅 분야에서 기존 연구의 연장선상에 있으면서도 새로운 문제 영역을 탐구하며 독창적인 연구 주제를 파생시킬 잠재력을 보여준다. 시스템 최적화는 양자 컴퓨팅 분야에서 다른 학문과 차별화된 접근 방식과 연구 성과를 도출할 수 있을 것으로 전망된다.

5. 결론 및 제언

이 논문은 산업공학의 시각에서 시스템 최적화의 발전과정과 미래 전망에 대해 살펴보았다. 시스템 최적화는 여러 학문 분야와 현실 상황에서 폭넓게 나타나며, 그 접근법과 이론적 이해가 깊어지고 있다. 따라서, 시스템 최적화 연구의 세부 분야를 모두 섭렵하는 것은 현실적으로 불가능한 일이다. 이 논문은 논리적 의사결정에 중요한 역할을 담당하는 시스템 최적화를 고전, 근대, 현대로 구분하여 둘러보고, 계산 최적화를 중심으로 미래 산업공학 학문에서 예상되는 최적화 연구의 방향성을 전망하였다.

근미래 초대규모 시스템 최적화 문제는 동적, 확률적, 이질적 시스템의 혼합된 형태로 나타날 것으로 예상되며, 이를 해결하기 위해서는 컴퓨터 연산 능력의 비약적인 도약이 필요하다. 새로운 컴퓨팅 패러다임으로 큰 잠재력을 보유한 양자 컴퓨팅은 현존하는 이진 디지털 컴퓨터와는 다른 차원에서의 문제 해결 접근 방식과 사고력을 요구하고, 시스템 최적화 분야에서 파급력이 큰 연구결과를 유도할 것으로 기대된다.

앞서 언급한 산업공학 시스템 최적화에서 오랜 기간 심도있게 연구되어 온 현실 기반 의사결정 문제들은, 현재 양자 컴퓨팅 분야의 숙원 과제인 킬러 앱 개발의 유력한 후보로 발전할 가능성이 매우 높다. 이러한 과제는 물리학자나 컴퓨터공학자, 또는 전자공학자 보다도 해당 도메인 지식이 풍부한 산업공학 전공자의 역할을 더 필요로 한다. 더불어, 양자 오류 검출 및 회복, 양자 기계학습, 양자 회로 최적화 등은 산업공학 시스템 최적화에서 다룰 수 있는 유망한 근미래 양자컴퓨팅 관련 연구과제이다.

산업공학 내 시스템 최적화 연구의 학문적 가치와 중요성이 공유되고 있음에도 불구하고, ‘수학의 일부인 최적화’로 관습적으로 인식되는 경향으로 인해 여러 유능한 인재들이 시스템 최적화를 도외시 하는 현상은 연구외적으로 시스템 최적화 분야에 새로운 과제를 안겨 준다. 이 같은 인식을 전환하기 위해, 전공 초기 단계에서 시스템 최적화에 쉽게 접근할 수 있는 기초 지식 편람, 입문서, 현실 사례집 등의 개발과 접근성 향상이 필요하다. 나아가, 산업공학 내 시스템 최적화의 학술적/현실적 가치에 대한 실질적 평가를 바탕으로 미래 도전과제와 학문적 가치를 확산시키기 위한 체계적인 노력이 요구된다.

References

• Abadi, M., Barham, P., Chen, J., Chen, Z., Davis, A., Dean, J., ... and Zheng, X. (2016), TensorFlow: A system for large-scale machine learning. In Proceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation, 265-283.
• Abadi, M., Barham, P., Chen, J., Chen, Z., Davis, A., Dean, J., ... and Zheng, X. (2016), TensorFlow: Large-scale machine learning on heterogeneous distributed systems. arXiv preprint arXiv:1603.04467.
• Abualigah, L., Diabat, A., Mirjalili, S., Abd Elaziz, M., and Gandomi, A. H. (2021), The arithmetic optimization algorithm, Computer Methods in Applied Mechanics and Engineering, 376, 113609. [https://doi.org/10.1016/j.cma.2020.113609]
• Ahuja, R. K., Magnanti, T. L., and Orlin, J. B. (1988), Network flows: Theory, algorithms, and applications, Prentice Hall. [https://doi.org/10.21236/ADA594171]
• Applegate, D. L. (2006), The Traveling Salesman Problem: A Computational Study (Vol. 17), Princeton University Press.
• Bengio, Y., Lodi, A., and Prouvost, A. (2021), Machine learning for combinatorial optimization: A methodological tour d'horizon, European Journal of Operational Research, 290(2), 405-421. [https://doi.org/10.1016/j.ejor.2020.07.063]
• Bertsekas, D. P. (1995), Nonlinear programming, Athena Scientific.
• Bertsimas, D. and Kallus, N. (2020), From predictive to prescriptive analytics, Management Science, 66(3), 1025-1044. [https://doi.org/10.1287/mnsc.2018.3253]
• Boyd, S. and Vandenberghe, L. (2004), Convex optimization, Cambridge University Press. [https://doi.org/10.1017/CBO9780511804441]
• Boyd, S., Parikh, N., Chu, E., Peleato, B., and Eckstein, J. (2011), Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations and Trends® in Machine Learning,history of optimization 3(1), 1-122. [https://doi.org/10.1561/2200000016]
• Charnes, A. and Cooper, W. W. (1961), Management models and industrial applications of linear programming (Vol. 1), Wiley.
• Charnes, A., Cooper, W. W., and Rhodes, E. (1978), Measuring the efficiency of decision making units, European Journal of Operational Research, 2(6), 429-444. [https://doi.org/10.1016/0377-2217(78)90138-8]
• Choi, H. and Choi, I. C. (2021), An integer programming model for the optimal qubit allocation, Journal of the Korean Institute of Industrial Engineers, 47(2), 199-207 [https://doi.org/10.7232/JKIIE.2021.47.2.199]
• Christofides, N. (1976), Worst-case analysis of a new heuristic for the travelling salesman problem, Operations Research Forum, 21(4), 679-687.
• Clarke, G. and Wright, J. W. (1964), Scheduling of vehicles from a central depot to a number of delivery points, Operations Research, 12(4), 568-581. [https://doi.org/10.1287/opre.12.4.568]
• Dantzig, G. B. (1955), Linear programming under uncertainty, Management Science, 1(3-4), 197-206. [https://doi.org/10.1287/mnsc.1.3-4.197]
• Dantzig, G. B. and Wolfe, P. (1960), Decomposition principle for linear programs, Operations Research, 8(1), 101-111. [https://doi.org/10.1287/opre.8.1.101]
• Dantzig, G. B., Fulkerson, D. R., and Johnson, S. M. (1954), Solution of a large-scale traveling-salesman problem, Operations Research, 2(4), 393-410. [https://doi.org/10.1287/opre.2.4.393]
• Dorigo, M. and Stützle, T. (2006), Ant colony optimization, IEEE Computational Intelligence Magazine, 1(4), 28-39. [https://doi.org/10.1109/MCI.2006.329691]
• Dorigo, M., Maniezzo, V., and Colorni, A. (1996), Ant system: optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics - Part B: Cybernetics, 26(1), 29-41. [https://doi.org/10.1109/3477.484436]
• Du, D. Z., Pardalos, P. M., and Wu, W. (2009), History of Optimization. In Encyclopedia of Optimization (pp.1-6), Charm: Springer International Publsihing.
• Fletcher, R. (1987), Practical methods of optimization (2nd ed.), Wiley.
• Frank, M. and Wolfe, P. (1956), An algorithm for quadratic programming, Naval Research Logistics Quarterly, 3(1-2), 95-110. [https://doi.org/10.1002/nav.3800030109]
• Fredman, M. L. and Tarjan, R. E. (1987), Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM, 34(3), 596-615. [https://doi.org/10.1145/28869.28874]
• Garey, M. R. and Johnson, D. S. (1979), Computers and intractability: A guide to the theory of NP-completeness, W.H. Freeman.
• Garey, M. R., Johnson, D. S., and Sethi, R. (1976), The complexity of flowshop and jobshop scheduling, Mathematics of Operations Research, 1(2), 117-129. [https://doi.org/10.1287/moor.1.2.117]
• Geem, Z. W., Kim, J. H., and Loganathan, G. V. (2001), A new heuristic optimization algorithm: Harmony search, Simulation, 76(2), 60-68. [https://doi.org/10.1177/003754970107600201]
• Gilmore, P. C. and Gomory, R. E. (1961), A linear programming approach to the cutting-stock problem, Operations Research, 9(6), 849-859. [https://doi.org/10.1287/opre.9.6.849]
• Glover, F. (1986), Future paths for integer programming and links to artificial intelligence, Computers & Operations Research, 13(5), 533-549. [https://doi.org/10.1016/0305-0548(86)90048-1]
• Glover, F. and Laguna, M. (1998), Tabu search. In Handbook of Combinatorial Optimization, Springer, 2093-2229. [https://doi.org/10.1007/978-1-4613-0303-9_33]
• Glover, F., Kochenberger, G., Hennig, R., and Du, Y. (2022), Quantum bridge analytics I: A tutorial on formulating and using QUBO models, Annals of Operations Research, 314(1), 141-183. [https://doi.org/10.1007/s10479-022-04634-2]
• Gounaris, C. E., Repoussis, P. P., Tarantilis, C. D., & Floudas, C. A. (2011). A hybrid branch-and-cut approach for the capacitated vehicle routing problem. In Computer Aided Chemical Engineering (Vol. 29, pp. 507-511), Elsevier. [https://doi.org/10.1016/B978-0-444-53711-9.50102-4]
• Graham, R. L., Lawler, E. L., Lenstra, J. K., and Rinnooy Kan, A. H. G. (1979), Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics, 5, 287-326. [https://doi.org/10.1016/S0167-5060(08)70356-X]
• Hakimi, S. L. (1964), Optimum locations of switching centers and the absolute centers and medians of a graph, Operations Research, 12(3), 450-459. [https://doi.org/10.1287/opre.12.3.450]
• Hsu, C. W. and Lin, C. J. (2002), A comparison of methods for multiclass support vector machines, IEEE Transactions on Neural Networks, 13(2), 415-425. [https://doi.org/10.1109/72.991427]
• Ibm (2024), Development & innovation roadmap, IBM.
• Jun, Y. M. (2024), A study on cofactor-based optimization techniques for quantum algorithms: Enhancing the implementability of Grover’s oracle circuit (Publication No. 1804: 11009-000000279877) [Doctoral dissertation, Korea University]. Korea University Repository. http://www.dcollection.net/handler/korea/000000279877
• Jung, J. (2022). On a branch-and-cut method for optimal quantum reversible circuit synthesis (Publication No. 1804: 11009-000000257368) [Doctral dissertation, Korea University]. Korea University Repository.
• Jung, J., & Choi, I. C. (2024). A new multicommodity network flow model and branch and cut for optimal quantum Boolean circuit synthesis. INFORMS Journal on Computing. [https://doi.org/10.1287/ijoc.2024.0562.cd]
• Karaboga, D. and Basturk, B. (2007), A powerful and efficient algorithm for numerical function optimization: Artificial bee colony (ABC) algorithm, Journal of Global Optimization, 39(3), 459-471. [https://doi.org/10.1007/s10898-007-9149-x]
• Katoch, S., Chauhan, S. S., and Kumar, V. (2021), A review on genetic algorithm: Past, present, and future, Multimedia Tools and Applications, 80(5), 8091-8126. [https://doi.org/10.1007/s11042-020-10139-6]
• Kennedy, J. and Eberhart, R. (1995), Particle swarm optimization. In Proceedings of ICNN'95 - International Conference on Neural Networks, IEEE, 1942-1948. [https://doi.org/10.1109/ICNN.1995.488968]
• Khan, A., Sohail, A., Zahoora, U., and Qureshi, A. S. (2020), A survey of the recent architectures of deep convolutional neural networks, Artificial Intelligence Review, 53(8), 5455-5516. [https://doi.org/10.1007/s10462-020-09825-6]
• Kim, J., Park, H., Kim, K., and Choi, I.-C. (2021), 3D Bloch sphere visualization modeling with global phase information, Presented at the Spring Conference of the Korean Societya for Simulation.
• Kingma, D. P. and Ba, J. (2015), Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980.
• Lawler, E. L. and Wood, D. E. (1966), Branch-and-bound methods: A survey, Operations Research, 14(4), 699-719 [https://doi.org/10.1287/opre.14.4.699]
• Li, J., Yang, X., Peng, X., and Sun, C. P. (2017), Hybrid quantum- classical approach to quantum optimal control, Physical review letters, 118(15), 150503.. [https://doi.org/10.1103/PhysRevLett.118.150503]
• Lin, S. and Kernighan, B. W. (1973), An effective heuristic algorithm for the traveling-salesman problem, Operations Research, 21(2), 498-516. [https://doi.org/10.1287/opre.21.2.498]
• Liu, D. C. and Nocedal, J. (1989), On the limited memory BFGS method for large scale optimization, Mathematical Programming, 45(1-3), 503-528. [https://doi.org/10.1007/BF01589116]
• Luenberger, D. G. and Ye, Y. (1973), Linear and nonlinear programming, Springer.
• Michalewicz, Z. (1999), Genetic algorithms + data structures = evolution programs (3rd ed.), Springer.
• Mirjalili, S. and Lewis, A. (2016), The whale optimization algorithm, Advances in Engineering Software, 95, 51-67. [https://doi.org/10.1016/j.advengsoft.2016.01.008]
• Myerson, R. B. (1981), Optimal auction design, Mathematics of Operations Research, 6(1), 58-73. [https://doi.org/10.1287/moor.6.1.58]
• Papadimitriou, C. H. and Steiglitz, K. (1982), Combinatorial optimization: Algorithms and complexity. Prentice Hall.
• Sakoe, H. and Chiba, S. (1978), Dynamic programming algorithm optimization for spoken word recognition, IEEE Transactions on Acoustics, Speech, and Signal Processing, 26(1), 43-49. [https://doi.org/10.1109/TASSP.1978.1163055]
• Schrijver, A. (1986), Theory of linear and integer programming, Wiley.
• Solomon, M. M. (1987), Algorithms for the vehicle routing and scheduling problems with time window constraints, Operations Research, 35(2), 254-265. [https://doi.org/10.1287/opre.35.2.254]
• Srinivas, N. and Deb, K. (1994), Multiobjective optimization using nondominated sorting in genetic algorithms, Evolutionary Computation, 2(3), 221-248. [https://doi.org/10.1162/evco.1994.2.3.221]
• Storn, R. and Price, K. (1997), Differential evolution - a simple and efficient heuristic for global optimization over continuous spaces, Journal of Global Optimization, 11(4), 341-359. [https://doi.org/10.1023/A:1008202821328]
• Taylor, F. W. (1911), Principles and methods of scientific management, Journal of Accountancy, 12(3), 3.
• Wagner, H. M. and Whitin, T. M. (1958), Dynamic version of the economic lot size model, Management Science, 5(1), 89-96. [https://doi.org/10.1287/mnsc.5.1.89]
• Wolsey, L. A. and Nemhauser, G. L. (1999), Integer and combinatorial optimization, Wiley.
• Yang, L., Shami, A., and Shami, A. (2020), On hyperparameter optimization of machine learning algorithms: Theory and practice, Neurocomputing, 415, 295-316. [https://doi.org/10.1016/j.neucom.2020.07.061]
• Zhang, Q. and Li, H. (2007), MOEA/D: A multiobjective evolutionary algorithm based on decomposition, IEEE Transactions on Evolutionary Computation, 11(6), 712-731. [https://doi.org/10.1109/TEVC.2007.892759]
• Zhou, L., Wang, S. T., Choi, S., Pichler, H., and Lukin, M. D. (2020), Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices, Physical Review X,ﾠ10(2), 021067. [https://doi.org/10.1103/PhysRevX.10.021067]
• Ziyaei, P., Choi, H., Singgih, I. K., and Choi, I. C. (2022), An experimental study on the limiting behavior of D-Wave's qbsolv for solving large-sized TSP. In Proceedings of the Korean Operations Research and Management Science Society Conference, 1647-1647.