다목적 최적화? SCILAB으로 수행

원문출처 : www.openeering.com/sites/default/files/Multiobjective%20Optimization%20Scilab.pdf

1. 최적화? Scilab과 함께하십시오!

Openeering 팀 목표 중 하나는 회사의 일상 활동에서 최적화를 지원하는 것이다. 최적화의 중요성을 강조하고 최적화가 설계 주기에서 어떻게 중요한 역할을 할 수 있는지를 설명할 기회를 절대 놓치지 않는다. 최적화에 대해 이야기 할 때 독자들이 산업에서의 사례를 해결하기 위한 방법과 소프트웨어에 관심이 있다는 것을 알고 있으므로 항상 실제 응용 프로그램을 언급한다. 특히, 다중 및 비선형 목표가 관련된 문제를 언급한다.

이 글에서는 강력한 다목적 및 다 분야 최적화 소프트웨어로 간주되는 수치 컴퓨팅 환경인 Scilab을 소개한다. Scilab은 MATLAB®과 매우 유사한 구문을 가진 고수준 행렬 언어이다. MATLAB®과 똑같이 Scilab을 사용하면 수학적 모델을 정의하고 기존 라이브러리에 연결할 수 있다. MATLAB®의 경우와 같이, 최적화는 Scilab의 중요한 주제다. Scilab은 사용 가능한 대규모 알고리즘 모음을 통해 선형 및 비선형 최적화 문제(단일 및 다목적)를 모두 해결할 수 있는 기능을 갖추고 있다.

여기에서는 Scilab에서 사용할 수 있는 최적화 알고리즘에 대한 전반적인 아이디어를 제시한다. 독자는 Scilab 콘솔에서 입력하고 사용할 수 있는 코드를 찾아 매우 일반적인 산업 최적화 문제를 해결하기 위한, 이 수치 컴퓨팅 환경의 잠재력을 확인할 수 있다.

 

2. 선형 및 비선형 최적화

독자들이 이미 알고 있듯이 "최적화"는 가능한 다양한 선택 중에서 사용 가능한 최상의 옵션을 선택하는 것을 의미한다. 이 작업을 일상적인 활동으로 수행하는 것은 복잡한 작업이 될 수 있다, 무차별 대입 방식을 사용할 때 엄청난 수의 선택에 대한 시험을 해야하기 때문이다. 일반적인 최적화 문제의 수학적 공식은 다음과 같이 설명 할 수 있다.

      min $(f_{1} (x), ..., f_{k} (x))$, $x\in s^{n}$

      subject to $g_{i} (x) \leq 0 $

                          $g_{l} (x) = 0$

                          $x \in S^{n}$

($x1$,…, $xn$)은 변수, 영역 $S$에서 변할 수 있는 자유 매개 변수다. $k > 1$이 될 때마다 다목적 최적화에 대해 이야기한다.

이것은 연속 및 이산 변수, 혼합 정수 문제, 선형 및 비선형 함수, 선형 및 비선형 제약 조건에 대해 유효하기 때문에 매우 일반적인 정의이다. 관련된 변수, 함수 및 제약 조건의 수와 유형에 따라 최적화 문제를 해결하기 위한 여러 가지 맞춤형 접근 방식이 존재할 수 있다.

 

3. 그래픽 방식

Scilab은 단순히 그래픽 방식으로도 일상적인 최적화 문제를 해결하는 데 매우 유용하다. 예를 들어, Rosenbrock 함수의 최소점을 찾고 싶다고 가정하면, 등고선도는 최적의 영역을 식별하는데 시각적인 도움이 될 수 있다. Scilab을 시작하고 다음 Scilab 스크립트를 복사하면 그림 1의 그래프를 얻는다.

 

등고선도는 최적의 솔루션을 찾기 위한 첫 번째 단계가 될 수 있다. 그런데 그래픽 방법을 사용하여 최적화 문제를 해결하는 것은 제한된 수의 입력 변수(2 또는 3)가 있을 때만 가능하다. 다른 모든 경우에는 더 진전시키거나 수치 알고리즘을 사용하여 솔루션을 찾아야 한다.

 

4. 최적화 알고리즘

추가 조사를 위해 다양한 수치해석 방법의 대규모 모음을 사용할 수 있다. Scilab에는 수십 개의 최적화 알고리즘이 있으며 각 방법은 함수 $f$의 수와 평활도, 변수 $x$의 수와 유형, 제약 조건$g$의 수와 유형에 따라 특정 문제를 해결하는 데 사용할 수 있다. 일부 방법은 제한된 최적화에 더 적합 할 수 있고, 다른 방법은 볼록 문제에 더 적합 할 수 있으며, 다른 방법은 이산 문제를 해결하기 위해 맞춤화 할 수 있다. 특정 방법은 2차 프로그래밍, 비선형 문제, 비선형 최소 제곱, 비선형 방정식, 다목적 최적화 및 이진 정수 프로그래밍을 해결하는 데 유용 할 수 있다. 표 1은 Scilab에서 사용할 수있는 최적화 알고리즘의 개요를 나타낸다. 다른 많은 최적화 방법은 ATOMS 커뮤니티에서 사용할 수 있다.

http://atoms.scilab.org/

최적화 도구로서 Scilab의 잠재력을 보여주기 위해, 가장 많이 사용되는 최적화 기능인 optim으로 시작할 수 있다. 이 명령은 비선형 비구속 및 경계 구속 최적화 문제에 대한 알고리즘 세트를 제공한다. 이전 문제에 대해 optim 함수를 사용하면 어떻게 되는지 살펴보자.

x0 = [-1.2 1]을 초기 점으로 사용하면 함수는 f = 0.0 인 최적점 x * = [1,1]로 쉽게 수렴된다.

이전 예제는 최적화 방법에 기울기가 필요하므로 Rosenbrock 함수의 값과 기울기를 모두 계산한다. 많은 실제 애플리케이션에서 기울기는 계산하기가 너무 복잡하거나 단순히 사용할 수 없는 경우가 있다. 함수가 알려지지 않았고 외부 함수 계산에서 블랙 박스로만 사용할 수 있기 때문이다. 이러한 이유로 Scilab은 함수 미분 또는 numdiff 함수를 사용하여 유한 차분을 사용하여 기울기를 계산할 수 있다.

예를 들어 다음 코드는 함수 f를 정의하고 특정 점 x에 대한 기울기를 계산한다.

이 두 함수 (미분 및 numdiff)는 optim과 함께 사용하여 기울기가 프로그래밍 하기에 너무 복잡한 문제를 최소화 할 수 있다.

optim 함수는 로컬 최적화를 위한 정확한 알고리즘인 BFGS 공식을 기반으로 한 준 뉴턴 방법을 사용한다. 같은 예에서 fminsearch 함수에 구현된 미분없는 Nelder-Mead Simplex[1]와 같은 다른 최적화 접근 방식을 적용 할 수도 있다. 그렇게하려면 다음 줄을 대체해야한다.

with

 

이 Nelder-Mead Simplex 알고리즘은 동일한 초기 지점에서 시작하여 최적 지점에 매우 가깝고 f = 8.177661e-010을 사용하여 x * = [1.000022 1.0000422]에 정확하게 수렴한다. 이것은 두 번째 접근법이 이전 접근법보다 덜 정확하다는 것을 보여준다. 이것은 시끄러운 기능과 로컬 최적화의 영향을 덜 받는 보다 강력한 접근법을 갖기 위해 지불해야하는 비용이다.

그림 2는 Rosenbrock 함수에서 Nelder-Mead Simplex 방법의 수렴을 보여준다.

이전 예제에서 함수는 Scilab 스크립트를 통해 제공되었지만, 이는 단순화를 위한 것이다. 함수 f를 C, Fortran 또는 Java 프로그램이나 외부 상용 솔버와 같은 외부 함수로 항상 평가할 수 있다.

 

5. 측정 데이터를 이용한 매개 변수 식별

이 짧은 단락에서는 엔지니어링에서 매우 일반적인 특정 최적화 문제를 보여준다. 입력/출력 데이터를 기반으로 비선형 시스템의 매개 변수 식별을 얼마나 빠르고 쉽게 수행 할 수 있는지 보여준다.

예를 들어 행렬 X에 특정 수의 측정이 있고 벡터 Y에 출력 값이 있다고 가정한다. 매개 변수 p 세트와는 별도로 모델 (FF)을 설명하는 함수를 알고 있으며 해당 매개 변수의 값을 찾고 싶다고 가정한다. 문제를 해결하기 위해 몇 줄의 Scilab 코드를 작성하는 것으로 충분하다.

이 방법은 매우 빠르고 효율적이며 많은 입/출력 데이터에 대한 매개 변수를 찾을 수 있다. 또한 포인트에 대한 매개 변수 경계 및 가중치를 고려할 수 있다.

 

6. 진화 알고리즘 : 유전적 및 다목적

유전 알고리즘[3]은 자연 진화와 선택의 메카니즘에 기반한 검색 방법이다. 이러한 방법은 노이즈 및 로컬 최적화에 대해 강건하기 때문에 고도로 비선형적인 실제 문제를 해결하는 데 널리 사용된다. 유전 알고리즘은 "고전적인"방법으로 해결하기 어려웠던 여러 엔지니어링 응용 프로그램뿐만 아니라 실제 문제에서도 주로 사용된다.

Scilab에서 유전 알고리즘을 사용하는 것은 매우 간단하다. 몇 줄로 모집단 수, 모집단 규모, 교차 확률 및 돌연변이와 같은 필수 매개 변수를 설정할 수 있다. 그림 3은 Rosenbrock 함수에 대한 단일 객관적 유전 알고리즘 optim_ga를 보여준다. 20 개의 초기 무작위 포인트(노란색)는 최적의 포인트를 향해 50 세대에 걸쳐 진화한다. 최종 세대는 빨간색으로 표시된다.

 

7. 다목적

Scilab은 단일 목적 문제만을 위한 것이 아니다. 다목적 최적화 문제도 쉽게 접근 할 수 있다. Scilab 사용자가 사용 가능한 방법 중 하나는 NSGAII를 활용 이다. NSGA-II는 Prof. Kalyanmoy Deb[4]의 작업을 기반으로 한 유명한 "비 지배 분류 유전 알고리즘"의 두 번째 버전이다. NSGA-II는 빠르고 엘리트 주의적인 다목적 진화 알고리즘이다.

그림 4는 테스트 문제 ZDT1을 사용하여 NSGA-II로 실행된 다목적 최적화를 보인다. 테스트 문제는 다음과 같다.

ZDT1을 사용하여 f1과 f2를 모두 최소화 하려고 한다. 이것은 우리가 다목적 문제 앞에 있음을 의미한다. 이러한 문제로 인해 최적 솔루션의 개념이 바뀐다. 다목적 최적화는 고유한 솔루션이 아니라 솔루션 세트를 생성한다. 이러한 솔루션은 비 지배 또는 파레토 솔루션이라고 하며, 솔루션 세트는 파레토 전선이라고 할 수 있다.

그림 4는 ZDT1 문제를 해결하기 위해 Scilab의 NSGA-II 최적화 알고리즘이 제공하는 솔루션을 보여준다. 상단의 빨간색 점은 초기 무작위 모집단이고 하단의 검은 점은 최종 파레토 모집단이다. 실선은이 특정 예에서 연속 볼록 솔루션이며 알려진 실제 파레토 전선을 나타낸다. 이 예에서 파레토 지배의 개념은 분명하다. 빨간색 점은 목표의 F1과 F2 모두에 대한 검은 점보다 더 최악이기 때문에 상단에 빨간 점은 바닥에 검은 점에 의해 지배된다. 반대로 그림 아래쪽의 모든 검은 색 점이 서로를 지배하지 않는다. 이 경우 모든 검은색 점이 효율적인 솔루션 집합을 나타낸다고 말할 수 있다.

Scilab이 다목적 최적화의 중요성을 인식하는 방법을 이해하기 위해, 대규모 데이터 세트에서 비 지배적 솔루션을 필터링 할 수 있는 pareto_filter라는 내부 함수가 있음을 알 수 있다.

이전 코드는 1,000 개의 임의 입력 값을 생성하고 zdt1 함수를 평가하고 비 지배적 솔루션을 계산한다. 코드의 마지막 네 줄은 모든 포인트가 빨간색이고 Pareto 포인트가 파란색인 다음 차트 (그림 5)를 생성한다.

 

8. 절단 스톡 문제 해결 : 낭비 감소

절단재 문제는 산업에서 매우 일반적인 최적화 문제이며 경제적으로 중요하다. 반 가공품을 다양한 크기로 절단하는 최적의 방법을 찾아 가장 효율적인 방법으로 소재를 사용하여 고객의 요구를 충족시키는 것이다. 이러한 유형의 문제는 산업에서 매우 자주 발생하며 비용 최소화, 절단 횟수 최소화, 재료 낭비 최소화 및 결과적으로 낭비 비용 등 다양한 목표를 수반 할 수 있다. 목표가 무엇이든 절단 레이아웃을 조금만 개선하면 재료를 현저하게 절약하고 생산 비용을 크게 줄일 수 있다는 것은 항상 사실이다.

이 섹션에서는 Scilab을 사용하여 1 차원 (1D) 절단재 문제를 해결하는 방법을 보여준다. 1D 절단재 문제를 해결하는 것은 2D 절단재 문제 (예 : 시트에서 직사각형 절단)를 해결하는 것보다 덜 복잡하지만 흥미롭고 일반적인 문제를 나타낸다. 1D 문제는 예를 들어 건설산업에서 지정된 수량과 길이의 철근이 필요할때 표준 길이의 기존 긴 철근에서 절단하는 경우에 발생할 수 있다. 절단 손실이 낭비의 가장 큰 원인 일 수 있다는 것은 잘 알려져 있다.

일반적으로 절단 대기 길이가 고정된 파이프를 생산하는 회사에서 일하고 있다고 가정 하자. 이 튜브는 고객의 요청에 따라 다양한 길이로 절단된다. 총 낭비를 최소화하기 위해 어떻게 튜브를 절단 할 수 있을까?

1D 절단재 문제에 대한 수학적 공식은 다음과 같다.

      $min (x) \sum_{i=1}^{n} c_{i} x_{i}$

      subject to      $\sum_{i=1}^{n} a_{ij} x_{i} = q_{j}$ with $j=1, ..., m$

여기서, $i$는 패턴의 인덱스, $j$는 길이의 인덱스, $x_{i}$는 절단 패턴의 수 $i$ (결정 변수)이고 $c_{i}$는 패턴 {i}의 비용이다. $A = (a_{ij})$ 가능한 모든 패턴의 매트릭스와 $q_{j}$ 고객의 요청. 값 $a_{ij}$는 패턴 $i$에서 절단 된 하나의 파이프 내에서 길이 $j$의 조각 수를 나타낸다고 말할 수 있다. 이 모델의 목표는 절단 단계의 총 비용으로 구성된 목적 함수를 최소화하는 것이다. 모든 패턴에 대해 $c_{i}$가 1이면 목표는 요구 사항을 충족하는 데 필요한 총 파이프 수에 해당한다.

실례를 만들어 Scilab으로 해결해 보자. 55mm, 26mm, 24mm의 세 가지 가능한 크기가 있다고 가정한다. 여기서 100mm의 원래 파이프를 자를 수 있다. 가능한 패턴은 다음과 같습니다.

      1. 유형 1의 절단 1 개, 유형 2의 절단 1 개 및 유형 3의 0개 [1 1 0]

      2. 유형 1의 절단 1 개 및 유형 3의 절단 [1 0 1]

      3. 유형 2의 2 개 절단 및 유형 3의 2 개 [0 2 2]

이러한 패턴은 행렬 A를 정의한다. 그러면 패턴 1, 2 및 3에 대해 각각 4, 3 및 1의 비용이 있다. 고객의 총 요청은 길이 55mm 150 개, 길이 26mm 인 200 개, 길이 24mm 인 300 개이다. Scilab에서이 문제를 해결하기 위해 아래 스크립트를 사용할 수 있다.

Scilab에서 이 스크립트를 실행하면 xopt = [25, 125, 87.5]를 얻게된다. 이는 총 파이프 수를 줄이기 위한 요청을 충족하기 위해 패턴 (1)의 25 번, 패턴 (2)의 125 번 및 패턴 (3)의 87.5번을 잘라야 한다는 것을 의미한다.

여기에서는 세 가지 다른 요청과 세 가지 다른 패턴이 있는 간단한 사례를 보인다. 더 많은 옵션, 다양한 차원, 비용 및 요청으로 인해 문제는 훨씬 더 복잡해질 수 있다. 단일 조각에 대한 최대 컷 수를 포함 할 수 있으며 실행 가능한 패턴 목록 (예 : 행렬 A)을 생성하는 데 약간의 노력이 필요할 수 있다. 이러한 모든 어려움은 Scilab으로 코딩 할 수 있으며 접근 방식의 논리는 동일하게 유지된다.

앞의 스크립트는 이 선형 문제를 해결하기 위해 내부 점 방법 [5]을 사용한다. 결과는 정수 솔루션이 아닌 출력을 제공하므로 세 번째 패턴으로 87.5 개의 파이프를 절단 할 수 없기 때문에 근사치가 필요하다. 이 근사 솔루션은 다른 방법으로 개선 할 수 있다. 다른 최적화 알고리즘, 예를 들어 가장 가까운 정수 솔루션을 평가하거나 더 강력한 유전 알고리즘을 사용한다. 그러나 우리가 첫 번째 단계에서 멈추고 솔루션을 반올림하더라도 낭비를 크게 줄일 수 있다.

다른 요청으로 문제를 해결하고 "적어도" $q_{j}$를 얻으려면 제약 조건을 다음과 같이 작성해야한다는 점에 유의하는 것이 중요하다.

      subject to      $\sum_{i=1}^{n} a_{ij} x_{i} \leq q_{j}$   with   $j=1, ..., m$

부등식 제약 조건을 고려하는 Scilab 스크립트는 다음과 같다.

이 경우의 솔루션은 총 비용이 550 인 xopt = [0,150,100] 이 된다. 이러한 방식으로 공식화된 문제로 인해
우리는 이전에 562.5에 달했던 총 비용을 줄일 수 있으며 총 컷 수를 늘릴 수도 있다.

 

9. 결론

절단재 문제의 해결 방안에서 알 수 있듯이 Scilab은 교육 도구가 아니라 실제 산업 문제를 해결하기 위한 제품이다.
절단재 문제는 업계에서 흔히 발생하는 문제이며 좋은 솔루션은 상당한 비용 절감을 가져올 수 있다. 하여간, 이 글에서는 Scilab 사용자가 실제 문제를 해결하기 위해 가질 수 있는 가능성의 일부만 제시했다. Scilab 최적화 알고리즘 및 방법론에 대한 자세한 내용은 [6-9]를 참조한다.

간단하게하기 위해 이 글에서는 짧고 일반적인 튜토리얼을 만들기 위해 사용된 매우 사소한 기능만을 보여준다.
분명히 이러한 간단한 기능은 FEM 솔버 또는 외부 시뮬레이션 코드와 같이 더 복잡하고 시간이 많이 걸리는 기능으로 대체 될 수 있다.

MATLAB 사용자는 상용 소프트웨어와 Scilab의 유사점을 인식했을 것이다. 우리는 다른 모든 독자들이 문제와 방법을 스크립트로 작성해야 한다는 사실에 두려워하지 않았기를 바란다. 논리가 명확 해지면 스크립트를 작성하여 민첩하고 흥미로운 활동을 할 수 있다.

 

10. 참고문헌

[1] Nelder, John A.; R. Mead (1965). "A simplex method for function minimization". Computer Journal 7: 308–313

[2] Scilab Optimization Datasheet, http://wiki.scilab.org/Scilab%20Optimization%20Datasheet

[3] David E. Goldberg. Genetic Algorithms in Search, Optimization & Machine Learning. AddisonWesley, 1989

[4] Deb, K., Pratap. A, Agarwal, S., and Meyarivan, T. (2002). A fast and elitist multi-objective genetic algorithm: NSGA-II. IEEE Transaction on Evolutionary Computation, 6(2), 181-197

[5] Narendra Karmarkar (1984). "A New Polynomial Time Algorithm for Linear Programming", Combinatorica, Vol 4, nr. 4, p. 373–395

[6] Baudin, Couvert, Steer. "Optimization In Scilab", Digiteo, INRIA

[7] Baudin M. "Nelder mead user's manual", Digiteo

[8] Baudin M., Steer S. "Optimization with Scilab, present and future", in Proceedings of 2009 International Workshop On Open-Source Software For Scientific Computation (Ossc-2009)

[9] Baudin M. "Introduction to optimization in Scilab", Consortium Scilab - Digiteo