Global Optimization Toolbox

주요 특징

  • 최적화 문제를 정의하고 해결하며 솔루션 진행을 모니터링하는 대화형 도구
  • 단일 또는 다중 전역 최적값을 찾기 위한 전역 검색 및 다중 시작 solvers
  • 선형, 비선형 및 경계 제약조건을 지원하는 유전 알고리즘
  • 선형 및 경계 제약조건을 포함하는 Pareto-front 식별 다목적 유전 알고리즘
  • 선형 비선형 및 경계 제약조건을 지원하는 Pattern Search solver
  • annealing 과정, 온도 예정 및 허용 기준을 정의하는 옵션으로 임의 검색 방법을 구현하는 simulated annealing 도구
  • Multi Start, 유전 알고리즘, Pattern Search solver의 병렬 컴퓨팅 지원
  • 유전 알고리즘, 다목적 유전 알고리즘, simulated annealing solver에서 사용자 정의 데이터 유형 지원
Plot of a nonsmooth objective function (bottom) that is not easily solved using traditional gradient-based optimization techniques. The Optimization Tool (middle) shows the solution found using pattern search in Global Optimization Toolbox. Iterative results for function value and mesh size are shown in the top figure.

기존의 증감 기반 최적화 기법으로 해를 쉽게 구할 수 없는 nonsmooth 목적함수의 플롯(아래) 최적화 도구(가운데)는 Global Optimization Toolbox에서 Pattern Search를 사용하여 찾은 해를 보여줍니다. 함수 값과 메시 크기에 대한 반복 결과는 위 그림에 표시되어 있습니다.

최적화 문제 정의, 해결, 평가

Global Optimization Toolbox는 명령줄과 Optimization Toolbox™Optimization 앱에서 액세스할 수 있는 함수를 제공합니다. 명령줄과 응용 프로그램을 통해 다음 작업을 수행할 수 있습니다.

  • Solver 선택 및 최적화 문제 정의
  • 최적화 옵션 설정 및 점검
  • 최적화 문제 실행 및 중간 및 최종 결과 시각화
  • Optimization Toolbox solver를 사용하여 유전 알고리즘, simulated annealing 및 Pattern Search를 조정
  • 최적화 문제와 결과를 MATLAB® 작업 공간으로 가져오기 및 내보내기
  • Optimization App에서 사용자의 최적화 작업 세팅을 한 뒤, MATLAB 코드 생성 기능을 통해 함수로 변환하여 코드 재사용

자체 알고리즘 옵션 및 사용자 정의 함수를 제공하여 solver를 사용자 정의할 수도 있습니다. Multi Start 및 Global Search solver는 명령행에서만 액세스할 수 있습니다.

Visualization of Rastrigin's function that contains many local minima and one global minimum (0,0). The genetic algorithm helps you determine the best solution for functions with several local minima, while the Optimization app provides access to all key components for defining your problem, including the algorithm options.

여러 개의 로컬 최솟값과 하나의 전역 최솟값(0,0)을 포함하는 Rastrigin 함수(오른쪽)의 시각화 유전 알고리즘(genetic algorithm)은 몇 개의 로컬 최솟값이 있는 함수에 대한 최적의 해를 결정하는 데 도움이 되며, Optimization 응용 프로그램(왼쪽)은 알고리즘 옵션을 포함하여 문제를 정의하는 데 필요한 모든 핵심 구성 요소에 대한 액세스를 제공합니다.

Toolbox에는 최적화를 시각화하기 위한 여러 플로팅 함수가 포함되어 있습니다. 사용자는 시각화를 통해 최적화 과정에 대한 라이브 피드백을 받아, solver 옵션을 수정하거나 solver를 중단하도록 결정할 수 있습니다. Toolbox는 유전 알고리즘과 Pattern Search 알고리즘 모두에 대한 사용자 정의 플로팅 함수를 제공합니다. 함수에는 목적함수 값, 제약 위반, 스코어 막대 그래프, 계통도, 메시 크기 및 함수 평가 등이 포함됩니다. 여러 플롯을 한번에 표시하거나, 특정 플롯을 새로운 창에 열어 자세히 보거나, 사용자의 플로팅 함수를 추가할 수 있습니다.

Run-time visualizations generated while the function is being optimized using genetic algorithm plot functions selected in the Optimization app.

Optimization 응용 프로그램(왼쪽)에서 선택한 유전 알고리즘(genetic algorithm) 플로팅 함수를 사용하여 함수를 최적화하는 동안 생성된 실시간 시각화(오른쪽)

출력 함수를 사용하여 결과를 파일로 기록하고 사용자 정의 중단 조건을 설정하고 툴박스 솔버(Solver) 실행을 위한 자체 응용 프로그램을 작성할 수도 있습니다. Optimization 응용 프로그램을 사용해 작업하면 문제와 알고리즘 옵션을 MATLAB 작업 공간으로 내보내거나, 작업을 저장했다가 나중에 사용자 인터페이스 로 재사용하거나, MATLAB 코드를 생성하여 완료한 작업을 캡처할 수 있습니다.

MATLAB file of an optimization created using the automatic code generation feature in the Optimization app. You can export an optimization from the app as commented code that can be called from the command line and used to automate routines and preserve your work.

Optimization 응용 프로그램의 자동 코드 생성 기능으로 생성된 최적화 MATLAB 파일 최적화를 응용 프로그램으로부터 주석 달린 코드로 내보내어 명령줄에서 호출, 루틴을 자동화고 작업을 보존하는 데 사용할 수 있습니다.

최적화를 수행하는 동안 유전 알고리즘, 다목적 유전 알고리즘, simulated annealing 및 패턴 검색 solver에서 일부 옵션을 수정하여 해를 세밀하게 조정하고 실행 결과를 업데이트할 수 있습니다. 예를 들면, Solver를 중단했다가 다시 시작할 필요 없이 실행 중에 플로팅 함수, 출력 함수, 명령행 반복 표시를 설정하거나 해제하여 중간 결과를 보거나 솔루션 진행 과정을 쿼리할 수 있습니다. 또한, 실시간 수행 피드백을 바탕으로 중단 조건을 수정하여 솔루션 진행 과정을 조정하거나 원하는 공차에 도달하는 데 필요한 반복 횟수를 줄일 수 있습니다.

Global Search 및 Multi Start Solver

Global Search 및 Multi Start Solver는 증감 기반 방식으로 지역 및 전역 최소값을 반환합니다. 두 solver 모두 여러 개의 시작점에서 지역 solver(Optimization Toolbox 내)를 시작하여 검색 과정에서 찾은 지역 및 전역 해를 저장합니다.

Global Search solver는:

  • scatter-search 알고리즘을 사용하여 여러 시작점을 생성합니다.
  • 이미 찾은 목적함수 및 연속함수 값과 지역 최소값을 바탕으로 가능성이 없는 시작점을 필터링합니다.
  • 제약조건을 포함한 비선형 최적화 solver를 사용하여 남은 시작점으로부터 지역 최소값을 검색합니다.

Multi Start solver는 미리 정의된 한계 내에서 균일하게 분산된 시작점이나 사용자 정의 시작점을 사용하여 단일 전역 최소값을 포함한 다중 지역 최소값을 찾습니다. Multi Start solver는 모든 시작점에서 지역 solver를 수행하며 직렬이나 병렬로 수행할 수 있습니다(Parallel Computing Toolbox™). 다중 시작 solver는 또한 다양한 지역 비선형 solver를 선택할 수 있는 유연성을 제공합니다. 사용 가능한 지역 solver에는 비제약 비선형, 제약 비선형, 비선형 최소제곱법, 비선형 최소제곱법 곡선 fitting.

다중 시작 Solver로 비선형 회귀 3:57
지수 모델에 가장 적합한 매개변수를 찾습니다.

Nonlinear Regression with the Multistart Solver 4:16
병렬 컴퓨팅으로 지수 모델에 가장 적합한 매개변수를 찾습니다..

유전 알고리즘 Solver

유전 알고리즘 Solver유전 알고리즘은 생물학적 진화의 원칙을 모방하여 생식 과정에서의 유전자 조합을 모델로 한 규칙을 사용하여 개별 포인트 집단을 반복적으로 수정함으로써 최적화 문제를 해결합니다. 유전 알고리즘은 그 임의성을 통해 전역 해를 찾을 가능성을 높여줍니다. 유전 알고리즘으로 비제약, 경계 제약 및 일반적인 최적화 문제를 해결할 수 있으며 미분 가능 함수나 연속함수일 필요가 없습니다.

다음 표는 Global Optimization Toolbox에서 제공되는 유전 알고리즘 옵션입니다.

단계유전 알고리즘 옵션
생성균일, 실행 가능
목적 함수(Fitness) 스케일링등급 기반, 비례, 위(잘라내기), 이동 선형
선택룰렛, SUS(stochastic uniform selection), 토너먼트, 단일, 잔여
교차Arithmetic, heuristic, inter­mediate, scattered, single-point, two-point
돌연변이적응 가능, Gaussian, 균일
플로팅최적합성, 최우수 개체, 개체간 거리, 집단 다양성, 개체의 기대, 최대 경계, 범위, 선택 지수, 중단 조건

Global Optimization Toolbox로 다음을 지정할 수 있습니다:

  • 집단 크기
  • 우수 자녀 수
  • 교차율
  • 하위 집단 간 이동(링 토폴로지 사용)
  • 최적화 문제에 대한 경계, 선형 및 비선형 제약

사용자 정의 함수를 제공하고 문제를 다양한 데이터 형식, 예를 들면, 정수, 혼합 정수, 범주형 또는 복소수 값 등으로 변수를 정의함으로써 알고리즘 옵션을 사용자 정의할 수 있습니다.

알고리즘의 중단 조건은 시간, 지연(stalling), 적합성 경계, 또는 세대 수 등을 기준으로 할 수 있습니다. 또한, fitness 함수를 벡터화하여 실행 속도를 향상시키거나 목적함수와 제약함수를 병렬 실행할 수 있습니다.(Parallel Computing Toolbox 사용).

Optimal Component Selection Using the Mixed-Integer Genetic Algorithm 5:25
Use the mixed-integer genetic algorithm to solve an engineering design problem.

다목적 유전 알고리즘 Solver

Multiobjective optimization는 제약 조건들의 모음을 대상으로하는 다목적 함수의 최소화에 사용합니다. 다목적 유전 알고리즘 solver는 균일하게 분포된 비지배(nondominated) 최적 해의 집합인 Pareto front를 식별하여 다목적 최적화 문제를 해결하는 데 사용됩니다. 이 solver를 사용하여 한계 또는 선형 제약이 있거나 없는, smooth 또는 nonsmooth 최적화 문제의 해를 구할 수 있습니다. 다목적 유전 알고리즘은 미분가능 함수나 연속함수가 필요 없습니다.

다음 표는 Global Optimization Toolbox에서 제공되는 다목적 유전 알고리즘 옵션입니다.

단계다목적 유전 알고리즘 옵션
생성균일, 실행 가능
목적 함수(Fitness) 스케일링등급 기반, 비례, 위(잘라내기), 선형 조정, 이동
선택토너먼트
교차Arithmetic, heuristic, inter­mediate, scattered, single-point, two-point
돌연변이적응 가능, Gaussian, 균일
플로팅Pareto 거리 평균, Pareto 평균 퍼짐, 개체간 거리, 집단 다양성, 개인의 기대, Pareto front, 등급 막대 그래프, 선택 지수, 중단 조건

Global Optimization Toolbox로 다음을 지정할 수 있습니다:

  • 집단 크기
  • 교차율
  • Pareto 비율
  • 개체 간 거리 측정
  • 하위 집단 간 이동(링 토폴로지 사용)
  • 최적화 문제에 대한 선형 및 경계 제약

사용자 정의 함수를 제공하고 문제를 다양한 데이터 형식, 예를 들면, 정수, 혼합 정수, 범주형 또는 복소수 값 등으로 변수를 정의함으로써 알고리즘 옵션을 사용자 정의할 수 있습니다.

알고리즘의 중단 조건은 시간, 목적함수(Fitness) 경계 또는 세대 수 등을 기준으로 할 수 있습니다. 또한, fitness 함수를 벡터화하여 실행 속도를 향상시키거나 목적함수를 병렬 실행할 수 있습니다(Parallel Computing Toolbox 사용).

Multiobjective genetic algorithm defined in the Optimization app, used to identify the Pareto front containing disconnected regions for the Kursawe function.

Optimization 앱(위)에서 지정되어 Kursawe 함수(아래)에 대한 불연속 지역(가운데)을 포함하는 Pareto front를 식별하는 데 사용된 멀티 오브젝트 유전 알고리즘

Pattern Search Solver

Global Optimization Toolbox에는 세 가지 직접 검색 알고리즘이 포함되어 있습니다: GPS(generalized pattern search), GSS(generating set search) 및 MADS(mesh adaptive search). 좀 더 일반적인 최적화 알고리즘이 증감에 대한 정확한 정보 또는 대략적인 정보나 고수준의 도함수를 사용하여 최적 포인트를 찾는 반면, 이 알고리즘은 최소 및 최대의 양수 기본 패턴을 구현하는 pattern search 메소드를 이용합니다. pattern search 메소드는 비선형, 선형 및 한계 제약 최적화 문제를 다루며 함수는 미분 가능하거나 연속일 필요가 없습니다.

다음 표는 Global Optimization Toolbox가 제공하는 Pattern Search 알고리즘 옵션을 보여줍니다. 명령행 또는 Optimization Tool에서 어떤 옵션도 변경 가능합니다.

Pattern Search 옵션설명
Polling 메소드패턴의 점을 생성하고 평가하는 방법과 각 단계에서 생성할 수 있는 점의 최대 수를 결정 효율성을 향상시키기 위해 점의 폴링 순서를 제어할 수도 있습니다.
Search 메소드폴링 단계보다 더 효율적인 검색 단계 선택 한 패턴 또는 전체 검색 공간에서 검색을 수행할 수 있습니다. Global search 메소드는 유전 알고리즘과 같이 적절한 시작점을 구하는 데 사용할 수 있습니다.
메시반복 시 패턴 변경 및 차원에 따라 다양한 크기의 문제에 적합하게 메시 조정 방식 제어. 최초의 메시 크기, 메시 조정 계수, 또는 메시 축소 계수를 선택할 수 있습니다. 메시 액셀러레이터는 최소값에 가까울 때 수속 지원이 빨라집니다.
캐시메모리 집약적(computationally expensive)인 목적함수 최적화 중 평가된 점을 저장 Pattern Search 알고리즘이 사용하는 캐시의 크기와 공차를 지정하고, 알고리즘이 진행됨에 따라 캐시 공차를 다양하게 하여 최적화 속도와 효율을 향상시킬 수 있습니다.
비선형 제약 알고리즘 설정보안 업데이트 계수 및 비선형 제약에 대한 매개변수 지정

Using the Optimization Tool (top) to find the peak, or global optima, of the White Mountains (middle and bottom) using pattern search.

Pattern Search를 통해 White Mountains(가운데와 아래)의 정점 또는 전역 최적값을 찾는 데 Optimization 앱(위) 사용

Simulated Annealing Solver

Simulated annealing은 최적화 문제를 해결합니다. 물질을 가열한 다음 서서히 온도를 낮춰 결함을 줄이고, 따라서 시스템 에너지를 최소화하는 풀림(annealing) 공정의 물리적 과정을 모방하는 확률적 검색 알고리즘을 사용합니다. 마찬가지로 simulated annealing 알고리즘도 반복될 때마다 서서히 검색 정도를 줄여 현재 최소값을 향상시키는 것입니다.

simulated annealing 알고리즘은 목적을 내리는 모든 새로운 점뿐 아니라, 어느 정도의 확률로, 목적을 올리는 점도 허용합니다. 목적을 올리는 포인트를 허용하면 그 알고리즘은 초기 반복 시 지역 최소값에 제한되는 것을 피할 수 있으며 전역에서 더 나은 해를 찾을 수 있습니다.

Simulated annealing을 사용하여 비제약 및 경계 제약 최적화 문제를 해결할 수 있으며 함수는 미분 가능하거나 연속일 필요가 없습니다. 명령줄이나 Optimization 앱에서 Toolbox 함수를 사용하여 다음 작업을 수행할 수 있습니다:

  • adaptive simulated annealing, Boltzmann annealing 또는 fast annealing 알고리즘을 사용하여 문제 해결
  • 사용자 정의 함수를 만들어 annealing 과정, 허용 기준, 온도 예정, 플로팅 함수, 시뮬레이션 결과 또는 사용자 정의 데이터 유형을 지정
  • 지정 간격 또는 일반 Solver 종료에 실행하기 위해 다른 최적화 메소드를 지정하여 하이브리드 최적화 수행
Using simulated annealing to solve a challenging problem that contains flat regions between basins.

simulated annealing을 사용하여 움푹한 부분 사이의 평평한 부분을 포함하는 어려운 문제 해결

병렬 컴퓨팅을 사용하여 최적화 문제 해결

병렬 연산을 통해 문제를 해결하기 위해 Optimization Toolbox를 Parallel Computing Toolbox와 함께 사용할 수 있습니다. 내장 병렬 컴퓨팅 기능을 사용하거나 최적화 문제의 사용자 정의 병렬 컴퓨팅 구현을 지정하여 해를 구하는 시간을 단축할 수 있습니다. 

병렬 컴퓨팅을 위한 내장 지원은 유전 알고리즘, 다목적 유전 알고리즘 및 Pattern Search solver에서 목적 및 제약 함수 평가 시간을 단축해 줍니다. 여러 지역 solver 호출을 여러 MATLAB 작업자에 분산시키거나 지역 solver에서 병렬 증감 계산을 설정하여 Multi Start solver 속도를 향상시킬 수 있습니다.

연료 효율성을 최대화하기 위해 변속 시점 최적화 5:33
듀얼 클러치 트랜스미션의 연료 소비율을 최대화하도록 변속 시점에서 20개의 매개 변수를 최적화합니다. Global optimization 알고리즘 및 병렬 컴퓨팅을 사용하여 최적화의 속도를 높입니다.

사용자 정의 병렬 컴퓨팅을 구현하려면 병렬 컴퓨팅 기능을 사용하기 위해 최적화 문제를 명시적으로 정의해야 합니다. 목적함수나 제약함수를 정의하여 병렬 컴퓨팅을 사용함으로써 목적/제약을 도출하기 위해 필요한 시간을 줄일 수 있습니다.

Nonlinear Regression with the Multistart Solver 4:16
병렬 컴퓨팅으로 지수 모델에 가장 적합한 매개변수를 찾습니다..

Global Optimization Toolbox 평가판 사용

평가판 신청

MATLAB을 이용한 전역최적화 기법 소개

웨비나 보기