병렬 메타휴리스틱

Parallel metaheuristic

병렬 메타휴리스틱(Parallel metehuristic)은 메타휴리스틱의 수작업과[clarification needed] 실행시간을 모두 줄일 수 있는 기법의 일종이다. 이를 위해 컴퓨터 과학의 병렬화 분야의 개념과 기술을 활용해 기존 메타휴리스틱스의 행동을 강화하고 심지어 완전히 수정한다. 진화 알고리즘, 입자 군집, 개미 군집 최적화, 시뮬레이션 어닐링 등과 같은 메타휴리스틱스의 긴 목록이 존재하듯이, 또한 이러한 기법들에 강하게 또는 느슨하게 기반을 둔 다양한 기법들의 집합도 존재하며, 이들의 행동은 어떤 식으로든 협력하는 알고리즘 구성요소의 다중 병렬 실행을 포괄한다.o 주어진 병렬 하드웨어 플랫폼에서 문제를 해결한다.

배경

동일한 PSO 메타휴리스틱 모델을 서로 다르게 구현한 예.

실제로 최적화(및 검색 및 학습) 문제는 NP 하드, 복잡, 시간 소모적인 경우가 많다. 두 가지 주요 접근방식은 전통적으로 이러한 문제들을 다루는데 사용된다: 정확한 방법과 메타휴리스틱스.[disputed – discuss] 정확한 방법은 정확한 해결책을 찾을 수 있지만 실제 문제(대규모 차원, 거의 구속되지 않음, 다중모드, 시간변환, 인식론적 문제)에 대해 매우 많은 시간이 소요되기 때문에 종종 비현실적이다. 반대로 메타휴리스틱스는 합리적인 시간 내에 최적(때로는 최적) 이하의 솔루션을 제공한다. 따라서 메타휴리스틱스는 산업 현장에서 부과되는 해결 지연을 충족시킬 수 있을 뿐만 아니라 특정 문제 사례 대신 일반 문제 클래스를 연구할 수 있게 한다. 일반적으로, 복잡하고 실제적인 문제들을 해결하기 위한 노력과 정밀하게 수행되는 많은 기술들은 메타휴리스틱스다. 이들의 응용 분야는 조합 최적화, 생물정보학, 통신에서 경제, 소프트웨어 공학 등에 이르기까지 다양하다. 이 분야들은 고품질의 빠른 해결책을 필요로 하는 많은 업무들로 가득 차 있다. 복잡한 응용프로그램에 대한 자세한 내용은 [1]을 참조하십시오.

메타휴리스틱스는 궤적 기반 메타휴리스틱스와 인구 기반 메타휴리스틱스의 두 가지 범주로 나뉜다. 이 두 종류의 방법의 주요한 차이는 (반복) 알고리즘의 각 단계에서 사용되는 잠정 해결책의 수에 의존한다. 궤적 기반 기법은 단일 초기 솔루션으로 시작하고, 검색의 각 단계에서 현재 솔루션은 이웃에서 발견된 다른 솔루션(종종 최고의 솔루션)으로 대체된다. 궤적을 기반으로 한 메타휴리스틱스(metehuristics)는 국소적으로 최적의 솔루션을 신속하게 찾을 수 있게 해, 이를 검색공간의 강화를 촉진하는 착취 위주의 방법이라고 한다. 반면에, 인구 기반 알고리즘은 해결책의 집단을 이용한다. 초기 모집단은 이 경우 무작위로 생성(또는 탐욕스러운 알고리즘으로 생성)한 다음 반복 과정을 통해 증가된다. 프로세스의 각 세대에서 전체 인구(또는 그 일부)는 새로 생성된 개인(흔히 가장 우수한 개인)으로 대체된다. 이러한 기법들은 주로 검색 공간의 다양화에 그 능력이 있기 때문에 탐사 지향적인 방법이라고 불린다.

대부분의 기본적인 메타휴리스틱스는 순차적이다. 이들의 활용은 검색 과정의 일시적 복잡성을 현저히 줄일 수 있지만, 이 후자는 학문적 영역과 산업적 영역 모두에서 발생하는 현실적 문제에서 높은 수준을 유지하고 있다. 따라서 병렬화는 검색 시간을 줄일 뿐만 아니라 제공된 솔루션의 품질을 향상시킬 수 있는 자연스러운 방법으로 다가온다.

병렬이 메타휴리스틱스와 어떻게 혼합될 수 있는지에 대한 포괄적인 논의는 [2]를 참조한다.

병렬 궤적 기반 메타휴리스틱스

최적화 문제 해결을 위한 메타휴러지스틱스는 당면한 문제의 솔루션 영역을 통해 검색 궤적을 추적하는 주변 지역을 통과하는 것으로 볼 수 있다. 

Algorithm: Sequential trajectory-based general pseudo-code     Generate(s(0));        // Initial solution     t := 0;                // Numerical step     while not Termination Criterion(s(t)) do         s′(t) := SelectMove(s(t)); // Exploration of the neighborhood         if AcceptMove(s′(t)) then             s(t) := ApplyMove(s′(t));             t := t + 1; 그 동안

워크는 솔루션 공간에서 한 솔루션에서 다른 솔루션으로 이동할 수 있는 반복적 절차에 의해 수행된다(위의 알고리즘 참조). 이러한 종류의 메타휴리스틱스는 현재 해결책의 근방에서 움직임을 수행한다. 즉, 그들은 동요하는 성격을 가지고 있다. 워크는 무작위로 생성되거나 다른 최적화 알고리즘에서 얻은 솔루션에서 시작한다. 반복할 때마다 현재 해결책은 주변 후보군에서 선택한 다른 솔루션으로 대체된다. 주어진 조건이 충족되면 검색 프로세스가 중지된다(최대 생성 횟수, 목표 품질을 가진 솔루션 찾기, 주어진 시간 동안 고착, ).

궤적 기반 방법으로 높은 계산 효율을 달성하는 강력한 방법은 병렬 처리의 사용이다. 궤적 기반 메타휴리스틱스에 대해 서로 다른 병렬 모델이 제안되어 왔으며, 그 중 세 가지 모델이 문헌에 공통적으로 사용되고 있다: 병렬 다중 시동 모델, 인접 지역(또는 병렬 이동 모델), 단일 솔루션(또는 이동 가속 모델)의 병렬 평가.

  • 병렬 다중 시동 모델: 그것은 더 좋고 강력한 솔루션을 계산하기 위한 궤적 기반 방법 몇 가지를 동시에 시작하는 것으로 구성된다. 이들은 이질적이거나 동질적일 수 있고, 독립적이거나 협력적일 수 있으며, 동일하거나 다른 솔루션에서 시작하여 동일하거나 다른 매개변수로 구성될 수 있다.
  • 병렬 이동 모델: 휴리스틱의 행동을 바꾸지 않는 낮은 수준의 마스터 슬레이브 모델이다. 순차적 검색은 동일한 결과를 계산하지만 속도가 느릴 것이다. 각 반복이 시작될 때 마스터는 분산 노드 간에 현재 솔루션을 복제한다. 각자가 후보/솔루션을 별도로 관리하고 그 결과를 마스터에게 돌려준다.
  • 가속 모델 이동: 각 이동의 질은 병렬 중앙 집중식으로 평가된다. 그 모델은 CPU 시간이 많이 걸리고 I/O 집약적이기 때문에 평가 기능 자체가 병렬화될 수 있을 때 특히 흥미롭다. 그 경우에 기능은 병렬로 실행할 수 있는 일정 수의 부분 함수의[clarification needed] 집합으로 볼 수 있다.

병렬인구 기반 메타휴리스틱스

인구 기반 메타휴리스틱은 많은 실제적이고 복잡한 애플리케이션(epistatic, multimodal, multi-objective 및 매우 제약적인 문제)에 성공적으로 적용된 확률적 검색 기법이다. 모집단 기반 알고리즘은 확률 연산자를 모집단: 모집단에 적용하는 반복 기법이다(아래 알고리즘 참조). 인구의 모든 개인은 잠정적인 해결책의 암호화된 버전이다. 평가 기능은 문제에 대한 적합성을 나타내는 모든 개인에 적합성 값을 연관시킨다. 반복적으로, 선정된 개인에 대한 변동 연산자의 확률적 적용은 모집단을 더 높은 품질의 잠정적인 해결책으로 인도한다. 솔루션 모집단의 조작에 기초하여 가장 잘 알려진 메타휴리스틱 계열은 진화 알고리즘(EAs), 개미 군집 최적화(ACO), 입자 군집 최적화(PSO), 산란 검색(SS), 차분 진화(DE), 추정 분포 알고리즘(EDA)이다. 

Algorithm: Sequential population-based metaheuristic pseudo-code     Generate(P(0)); // Initial population     t := 0;          // Numerical step     while not Termination Criterion(P(t)) do         Evaluate(P(t)); // Evaluation of the population         P′′(t) := Apply Variation Operators(P′(t)); // Generation of new solutions         P(t + 1) := 교체(P(t), P′′(t); // 다음 모집단 t := t + 1; 그러는 동안

비종교적 문제의 경우, 긴 개인 및/또는 큰 모집단에 대해 단순한 모집단 기반 방법의 생식 주기를 실행하려면 대개 높은 계산 자원이 필요하다. 일반적으로, 모든 개인에 대한 피트니스 기능의 평가는 종종 이 알고리즘의 가장 비용이 많이 드는 작업이다. 결과적으로, 효율적인 기법을 설계하기 위해 다양한 알고리즘 문제가 연구되고 있다. 이러한 문제는 대개 새로운 연산자, 하이브리드 알고리즘, 병렬 모델 등을 정의하는 것으로 구성된다.

병렬론은 인구수를 다룰 때 자연적으로 발생한다. 왜냐하면 그 개인에 속하는 각 개인은 독립된 단위(적어도 피츠버그 스타일에 따라, 미시건과 같은 다른 접근법이 있지만, 개인을 독립된 단위로 간주하지 않는다.)이기 때문이다. 실제로 병렬로 실행할 때 모집단 기반 알고리즘의 성능이 향상되는 경우가 많다. 두 가지 병렬화 전략은 특히 모집단 기반 알고리즘에 초점을 맞추고 있다.

  1. 각 개인에게 공통적으로 적용되는 연산을 병렬로 수행하는 연산
  2. 간단히 교환하거나 개별적으로 진화하여 나중에 합류할 수 있는 서로 다른 부분으로 인구를 분할하는 인구 병렬화.

이러한 알고리즘의 병렬화 이력의 초기에는 잘 알려진 마스터 슬레이브(글로벌 병렬화 또는 농업이라고도 함) 방식이 사용되었다. 이 접근방식에서, 관련 슬레이브 프로세서(노동자)가 변동 연산자와 피트니스 기능의 평가를 실행하는 동안 중앙 프로세서가 선택 작업을 수행한다. 이 알고리즘은 연산 효율은 향상되지만 특히 시간이 많이 걸리는 객관적 기능에 대해서는 순차적 알고리즘과 동일한 동작을 가진다. 반면에, 많은 연구자들은 순차 알고리즘의 실행을 가속화하기 위해 프로세서 풀을 사용한다. 단지 독립 실행은 하나의 프로세서를 사용하는 것보다 여러 프로세서를 사용함으로써 더 빠르게 이루어질 수 있기 때문이다. 이 경우 독립 실행 간에 교호작용이 전혀 존재하지 않는다.

그러나 실제로 문헌에서 발견되는 대부분의 병렬 모집단 기반 기술은 개인들을 위한 일종의 공간적 배치를 이용하고, 그 결과 발생하는 덩어리를 프로세서 풀에서 병렬화한다. 구조화된 메타휴리스틱스의 가장 널리 알려진 유형들 중, 분포된(또는 거친)과 셀룰러(또는 미세한) 알고리즘은 매우 인기 있는 최적화 절차다.

분산형 알고리즘의 경우, 모집단은 격리된 직렬 알고리즘이 실행되는 일련의 하위 집단(섬)으로 분할된다. 이러한 섬들 사이에서 개인들의 희박한 교류가 이루어지는데, 이는 하위 집단들에 어느 정도 다양성을 도입함으로써 지역적 최적화에 고착되는 것을 방지한다는 목표다. 분산된 메타휴리스틱을 설계하기 위해서는 몇[who?] 가지 결정을 내려야 한다. 그 중에서, 주요 결정은 토폴로지(섬 간의 논리적 연계), 이주율(모든 교환에서 이주를 겪는 개인 수), 이주 빈도(두 번의 연속적인 교환 사이의 모든 하위 인구에서의 단계 수), 이주자의 선택/교체 등의 이주 정책을 결정하는 것이다.

세포법의 경우, 이웃의 개념이 도입되어 개인은 단지 사육루프에서 가까운 이웃과 교류할 수 있다. 알고리즘의 작은 동네가 겹쳐져 있는 것은 인구를 통한 해결책의 느린 확산이 일종의 탐색을 제공하는 반면, 각 동네 내부에서 착취가 일어나기 때문에 탐색 공간 탐사에 도움이 된다. 세포 유전 알고리즘 및 관련 모델에 대한 자세한 내용은 [3]을 참조하십시오.

또한, 병렬화의 2단계 접근방식이 수행되는 하이브리드 모델이 제안되고 있다. 일반적으로 병렬화를 위한 상위 레벨은 거친 결로 구현이며 기본 섬은 셀룰러, 마스터슬레이브 방식 또는 다른 분산된 방식을 수행한다.

참고 항목

참조