가변 근린 검색

1997년 ^[2]믈라데노비치와 한센이 제안한 VNS(^[1]Variable Neighborse Search)는 조합 최적화와 글로벌 최적화 문제를 해결하기 위한 메타휴리스틱 방법입니다.현재 솔루션의 먼 지역을 탐색하고 개선이 이루어진 경우에만 새로운 솔루션으로 이동합니다.로컬 검색 방법은 반복적으로 적용되어 인근 솔루션에서 로컬 옵티마로 이동합니다.VNS는 이산적이고 연속적인 최적화 문제에 대한 근사적인 해법을 위해 설계되었으며, 이에 따라 선형 프로그램 문제, 정수 프로그램 문제, 혼합 정수 프로그램 문제, 비선형 프로그램 문제 등을 해결하기 위한 것입니다.

서론

VNS는 2개의 단계로 인근 지역을 체계적으로 변경합니다.첫째, 로컬 최적치를 찾기 위한 하강과 마지막으로 대응하는 계곡을 벗어나기 위한 섭동 단계입니다.

응용 프로그램의 수는 급속히 증가하고 있으며 위치 이론, 클러스터 분석, 스케줄링, 차량 라우팅, 네트워크 설계, 로트 크기 조정, 인공지능, 엔지니어링, 풀링 문제, 생물학, 계통학, 신뢰성, 기하학, 통신 설계 등 다양한 분야에 관련되어 있습니다.

VNS를 이해하는 데 중요한 책이 몇 권 있다. 예를 들어 메타휴리스틱 핸드북, 2010,^[3] 메타휴리스틱 핸드북, 2003^[4] 및 검색 방법론, 2005.^[5]이 접근방식의 동기를 부여한 이전의 연구는 다음에서 확인할 수 있습니다.

데이비든, W.^[6]C.
플레처, R., 파월, M.J.^[7]D.
북부 ^[8]믈라데노비치
브림버그, J, 믈라데노비치,^[9] 노스캐롤라이나 주

VNS 방법론 및 다양한 애플리케이션에 대한 최근 조사는 4OR, 2008^[10] 및 Annals of OR, 2010에서 확인할 수 있습니다.

문제의 정의

다음과 같은 결정론적 최적화 문제를 정의합니다.

$\min {\{f(x)|x\in X,X\subseteq S\}}$ { $\min {\{f(x)|x\in X,X\subseteq S\}}$ ( $\min {\{f(x)|x\in X,X\subseteq S\}}$ ) $\min {\{f(x)|x\in X,X\subseteq S\}}$ $}$ { $displaystyle \min { f$ ( $x$ ) $x\in$ X, $X\subseteq$ S $\min {\{f(x)|x\in X,X\subseteq S\}}$ (1)

여기서 S, X, x 및 f는 각각 솔루션 공간, 실현 가능한 집합, 실현 가능한 솔루션 및 실가치의 목적함수이다.S가 유한하지만 큰 집합일 경우 조합 최적화 문제가 정의됩니다.S $=$ ${S=R^{n}}$ { $style {S=$ R ${S=R^{n}}$ n}}}이면 연속 최적화 모델이 있다.

${x^{*}\in X}$ x ${x^{*}\in X}$ x ${x^{*}\in X}$ X ( \ $display$ style { $x$ ^ { * } \ $in$ X ${x^{*}\in X}$ } )는 ${x^{*}\in X}$ 다음과 같은 경우에 최적입니다.

${f(x^{*})\leq f(x),\qquad \forall {x}\,\in X}$ ( ${f(x^{*})\leq f(x),\qquad \forall {x}\,\in X}$ ) ${f(x^{*})\leq f(x),\qquad \forall {x}\,\in X}$ ( x ${f(x^{*})\leq f(x),\qquad \forall {x}\,\in X}$ ) 、 ${f(x^{*})\leq f(x),\qquad \forall {x}\,\in X}$ x ${f(x^{*})\leq f(x),\qquad \forall {x}\,\in X}$ ( \ $displaystyle$ { f ( x ^ { * ) 、 $leq f$ ( x ) , \ $qquad \ forall$ { x } , \ $in$ X ${f(x^{*})\leq f(x),\qquad \forall {x}\,\in X}$ 。

문제 (1)에 대한 정확한 알고리즘은 최적의 구조를 검증하여 최적의 솔루션 x*를 찾는 것이며, 실현 불가능한 경우에는 X $X=\varnothing$ ${\$ \ $displaystyle$ X = \ $varnothing$ $X=\varnothing$ 과 $X=\varnothing$ 달성 가능한 솔루션이 없음을 보여야 한다.CPU 시간은 유한하고 짧아야 합니다.지속적인 최적화를 위해서는 어느 정도의 허용 오차를 허용하는 것이 합리적입니다. 즉, 다음과 같은 실현 가능한 $x^{*}$ x ${\$ (\ $displaystyle$ x $^{*})$ 가 $x^{*}$ 발견되었을 때 정지하는 것이 좋습니다.

${f(x^{*})\leq f(x)+\epsilon ,\qquad \forall {x}\,\in X}$ ( ${f(x^{*})\leq f(x)+\epsilon ,\qquad \forall {x}\,\in X}$ ${f(x^{*})\leq f(x)+\epsilon ,\qquad \forall {x}\,\in X}$ ) ${f(x^{*})\leq f(x)+\epsilon ,\qquad \forall {x}\,\in X}$ ( ${f(x^{*})\leq f(x)+\epsilon ,\qquad \forall {x}\,\in X}$ ) + ${f(x^{*})\leq f(x)+\epsilon ,\qquad \forall {x}\,\in X}$ 、 ${f(x^{*})\leq f(x)+\epsilon ,\qquad \forall {x}\,\in X}$ 、 $、$ \ $displaystyle$ ${ f$ ( x ${f(x^{*})\leq f(x)+\epsilon ,\qquad \forall {x}\,\in X}$ ^ { * ) \ $leq$ f ( x ) + \ $epsilon$ , \ ${(f(x^{*})-f(x))/f(x^{*})<\epsilon ,\qquad \forall {x}\,\in X}$ \ $forall$ { $x$ ${(f(x^{*})-f(x))/f(x^{*})<\epsilon ,\qquad \forall {x}\,\in X}$ , \ $in$ X ${(f(x^{*})-f(x))/f(x^{*})<\epsilon ,\qquad \forall {x}\,\in X}$ } ${(f(x^{*})-f(x))/f(x^{*})<\epsilon ,\qquad \forall {x}\,\in X}$ ( x ) / ${(f(x^{*})-f(x))/f(x^{*})<\epsilon ,\qquad \forall {x}\,\in X}$ ( x ${(f(x^{*})-f(x))/f(x^{*})<\epsilon ,\qquad \forall {x}\,\in X}$ ) 、 ${(f(x^{*})-f(x))/f(x^{*})<\epsilon ,\qquad \forall {x}\,\in X}$ ) ${(f(x^{*})-f(x))/f(x^{*})<\epsilon ,\qquad \forall {x}\,\in X}$ ${(f(x^{*})-f(x))/f(x^{*})<\epsilon ,\qquad \forall {x}\,\in X}$ 、 $。$

일부 휴리스틱스는 대략적인 솔루션 또는 최적 솔루션을 빠르게 받아들이지만 최적성은 검증되지 않습니다.이들 중 일부는 잘못된 인증서를 가지고 있습니다. 즉, 솔루션 $x_{h}$ h $(\$ h $x_{h}$ })는 다음을 만족시킵니다.

${(f(x_{h})-f(x))/f(x_{h})\leq \epsilon ,\qquad \forall {x}\,\in X}$ ${(f(x_{h})-f(x))/f(x_{h})\leq \epsilon ,\qquad \forall {x}\,\in X}$ ( ${(f(x_{h})-f(x))/f(x_{h})\leq \epsilon ,\qquad \forall {x}\,\in X}$ h ${(f(x_{h})-f(x))/f(x_{h})\leq \epsilon ,\qquad \forall {x}\,\in X}$ ) - ${(f(x_{h})-f(x))/f(x_{h})\leq \epsilon ,\qquad \forall {x}\,\in X}$ ( ${(f(x_{h})-f(x))/f(x_{h})\leq \epsilon ,\qquad \forall {x}\,\in X}$ x ${(f(x_{h})-f(x))/f(x_{h})\leq \epsilon ,\qquad \forall {x}\,\in X}$ ) / ${(f(x_{h})-f(x))/f(x_{h})\leq \epsilon ,\qquad \forall {x}\,\in X}$ ( ${(f(x_{h})-f(x))/f(x_{h})\leq \epsilon ,\qquad \forall {x}\,\in X}$ h ) / $f$ ( x h ) ${(f(x_{h})-f(x))/f(x_{h})\leq \epsilon ,\qquad \forall {x}\,\in X}$ 、 ${(f(x_{h})-f(x))/f(x_{h})\leq \epsilon ,\qquad \forall {x}\,\in X}$ " ${(f(x_{h})-f(x))/f(x_{h})\leq \epsilon ,\qquad \forall {x}\,\in X}$ " ${(f(x_{h})-f(x))/f(x_{h})\leq \epsilon ,\qquad \forall {x}\,\in X}$ X ( ${(f(x_{h})-f(x))/f(x_{h})\leq \epsilon ,\qquad \forall {x}\,\in X}$ / $f ( x$ _ { h $) \ leq$ \ $epsilon$ , \ $qquad$ \ $forall$ ${(f(x_{h})-f(x))/f(x_{h})\leq \epsilon ,\qquad \forall {x}\,\in X}$ { $x$ } , \ $in$ X $}$ ( ( ( $\epsilon$ is is is is is $this$ this is is is is is is is is is is is is is is ( ( ( ( ( ( ( ( ( ( ( ( is is is is ( ( ( ( ( ( ( \ \ \ ( ( ( ( ( ( \ \ ( ( ( ( ( ( ( ( ( ( ( ( ( ( {

휴리스틱스는 무한한 컴퓨팅 시간을 피함으로써 로컬 옵티마의 문제에 직면하고 있습니다.문제의 로컬 $x_{L}$ x $({$ })은 $x_{L}$ 다음과 같습니다.

${f(x_{L})\leq f(x),\qquad \forall {x},\in N(x_{L})\cap X$

$N(x_{L})$ 서 N $N(x_{L})$ L $)$ { $display Style$ N $(x_{L})$ 은 $N(x_{{L}})$ x $x_{L}$ { $display$ style $x_{L}$ 의 근방을 나타냅니다.

묘사

(Mladenovique, 1995)에 따르면, VNS는 지역 최소치로 내려가는 과정과 지역 최소치를 포함하는 계곡에서 탈출하는 지역 변화 절차를 체계적으로 수행하는 메타 휴리스틱이다.

VNS는 다음 인식을 바탕으로 구축됩니다.

1개의 근린구조에 관한 로컬 최소값이 다른 근린구조에 대한 로컬 최소값이 될 필요는 없습니다.
글로벌 최소값은 가능한 모든 네이버 구조에 대한 로컬 최소값입니다.
많은 문제에서 하나 또는 여러 이웃에 대한 로컬 최소값은 서로 상대적으로 가깝습니다.

다른 많은 메타 휴리스틱과는 달리 VNS 및 VNS 확장의 기본 스킴은 단순하고 소수의 파라미터가 필요하며 때로는 파라미터가 필요하지 않습니다.따라서 VNS는 다른 방법보다 간단한 방법으로 매우 우수한 솔루션을 제공할 뿐만 아니라 이러한 성능의 원인을 파악할 수 있으며, 결과적으로 보다 효율적이고 정교한 구현으로 이어질 수 있습니다.

최근에 언급된 논문들 중에 연구할 수 있는 논문들이 몇 개 있다(Hansen and Mladenovique 1999, 2001a, 2003, 2005; Moreno-Pérez 등).;^[11])

로컬 검색

초기해 x를 선택하고, 근방 N(x) 내에서 x로부터의 하강 방향을 검출해, 같은 방향으로 N(x) 내에서 f(x)의 최소값으로 진행하는 것으로 국소 탐색 휴리스틱을 실시한다.하강 방향이 없으면 휴리스틱이 중지되고, 그렇지 않으면 반복됩니다.일반적으로 가장 높은 하강 방향이 사용되며, 이 또한 최선의 개선사항으로 관련된다.이 규칙 세트는 알고리즘1에 요약되어 있습니다.알고리즘 1에서는 초기 솔루션x 가 주어져 있다고 가정합니다.출력은 로컬 최소값(x')과 그 값으로 구성됩니다.네이버 구조 N(x)이 모든 x' X에 대해 정의되어 있는지 확인합니다.각 단계에서 x의 근방 N(x)을 완전히 탐색한다.이 작업은 시간이 오래 걸릴 수 있으므로, 대안은 첫 번째 강하 휴리스틱을 사용하는 것입니다.다음으로 벡터 $x^{i}\in N(x)$ i $x^{i}\in N(x)$ N ( $x^{i}\in N(x)$ ) { $displaystyle$ x $^{i}\in$ N $(x)}$ 을 $x^{i}\in N(x)$ 체계적으로 열거하고 하강 방향을 찾는 즉시 이동한다.이는 알고리즘2에 요약되어 있습니다.

알고리즘 1: 최상의 개선(최고 강하) 경험적 접근

Function Best Improvement(x) 1: 반복 2: x' ← x 3: x ← argmin_{ f(y) }, y n N(x) 4: ~ ( f(x) f f(x' ) 5: 반환 x'

알고리즘 2: 첫 번째 개선(첫 번째 강하) 휴리스틱

함수 우선 개선(x) 1: 반복 2: x' ← x; i ← 0 3: 반복 4: i ← 1 5: x ← argmin{ f(x), f(x^i)}, x^i x N(x) 6: ~ f(x) 또는 i = N(x) (x) (f(x) : f(x )까지 반복한다.

${\mathcal {N}}_{k}(x)$ ${\mathcal {N}}_{k}(k=1,...,k_{max})$ ( ${\mathcal {N}}_{k}(k=1,...,k_{max})$ ${\mathcal {N}}_{k}(k=1,...,k_{max})$ , ${\mathcal {N}}_{k}(k=1,...,k_{max})$ . ${\mathcal {N}}_{k}(k=1,...,k_{max})$ , k ${\mathcal {N}}_{k}(k=1,...,k_{max})$ ${\mathcal {N}}_{k}(k=1,...,k_{max})$ ) { $displaystyle$ { $n }$ _ { k } ( $k =$ 1 , ... k _ { $max$ } ) ${\mathcal {N}}_{k}(k=1,...,k_{max})$ , 、 N ${\mathcal {N}}_{k}(x)$ ( ${\mathcal {N}}_{k}(x)$ ) \ displaystyle ${\mathcal {N}}_{k}(x)$ \ $mathcal { N} _$ { $k$ （ $x$ ）。

${\mathcal {N'}}_{k}(x),k=1,...,k'_{max}$ 로컬 디센트를 기술할 때 N ${\mathcal {N'}}_{k}(x),k=1,...,k'_{max}$ ${\mathcal {N'}}_{k}(x),k=1,...,k'_{max}$ ( ${\mathcal {N'}}_{k}(x),k=1,...,k'_{max}$ ) , ${\mathcal {N'}}_{k}(x),k=1,...,k'_{max}$ ${\mathcal {N'}}_{k}(x),k=1,...,k'_{max}$ 1, ${\mathcal {N'}}_{k}(x),k=1,...,k'_{max}$ . , ${\mathcal {N'}}_{k}(x),k=1,...,k'_{max}$ ${\mathcal {N'}}_{k}(x),k=1,...,k'_{max}$ a ${\mathcal {N'}}_{k}(x),k=1,...,k'_{max}$ { $displaystyle$ \ $mathcal$ { $N'}}_{k}(x),$ k ${\mathcal {N'}}_{k}(x),k=1,...,k'_{max}$ = ${\mathcal {N'}}_{k}(x),k=1,...,k'_{max}$ 1, $...k'_{max}$ ${\mathcal {N'}}_{k}(x),k=1,...,k'_{max}$ 을 ${\mathcal {N'}}_{k}(x),k=1,...,k'_{{max}}$ 사용합니다. ${\mathcal {N}}_{k}(x)$ ${\mathcal {N}}_{k}(x)$ ( ${\mathcal {N}}_{k}(x)$ x $){style {N}_{k}(x)}$ ${\mathcal {N'}}_{k}(x)$ N ${\mathcal {N'}}_{k}(x)$ k ${\mathcal {N'}}_{k}(x)$ ( $x){displaystyle$ {n $'}_{k}(x)}$ 는 ${\mathcal {N'}}_{k}(x)$ 솔루션 공간 S에 도입된 하나 이상의 메트릭(또는 준 메트릭) 함수로부터 유도될 수 있다.최적의 $x_{opt}$ $x_{opt}$ $x_{opt}$ p t $x_{opt}$ { $display x _$ { $x_{opt}$ opt $x_{opt}$ } (또는 글로벌 최소)는 최소한의 문제에 도달하는 실현 가능한 솔루션입니다. $f(x)<f(x')$ ' $x$ X local N k ${\mathcal {N}}_{k}(x)$ ( ${\mathcal {N}}_{k}(x)$ ) \ $displaystyle$ \ ${\mathcal {N}}_{k}(x)$ $x\in {\mathcal {N'}}_{k}(x)\subseteq X$ ${\mathcal {N}}_{k}(x)$ { $N$ $x\in {\mathcal {N'}}_{k}(x)\subseteq X$ _ { k ${\mathcal {N}}_{k}(x)$ $x\in {\mathcal {N'}}_{k}(x)\subseteq X$ ( $x$ ) $x\in {\mathcal {N'}}_{k}(x)\subseteq X$ X \ $display style$ x \ in \ $mathcal$ { N ' $} _$ { k $（$ x ) $f(x)<f(x')$ X $f(x)<f(x')$ （ ${\mathcal {N}}_{k}(x)$ $f(x)<f(x')$ ）。

여러 이웃을 사용하여 문제를 해결하기 위해, 사실 1-3은 (i) 결정론적, (ii) 확률론적, (ii) 결정론적 및 확률론적 세 가지 다른 방법으로 사용될 수 있다.알고리즘 3에서는 나중에 사용할 근린변화 함수의 단계를 먼저 제시합니다.함수 Neighborhood Change()는 새로운 값 f(x')를 네이버k(행 1)에서 얻은 현재 값 f(x)와 비교합니다.개선이 이루어지면 k는 초기값으로 되돌리고 새로운 기존 값을 갱신한다(2행).그렇지 않으면 다음 네이버가 고려됩니다(행 3).

알고리즘 3: – 네이버 변경

Function Neighborhood Change (x, x', k) 1: f(x) < f(x) 그렇다면 2: x ← x' // 이동하기 3: k ← 1 // 초기 근린 4: else 5: k ← k+1 // 다음 근린

VNS가 적절한 솔루션을 제공하지 않는 경우 로컬 검색의 첫 번째 및 최선의 개선 전략 비교, 인근 지역 감소, 흔들림 강화, VND 채택, FSS 채택, 파라미터 설정 실험 등 몇 가지 절차가 진행 중에 도움이 될 수 있습니다.

기본 VNS(Basic VNS) 방법(메타 휴리스틱스 핸드북, 2010)^[3]은 결정론적 및 확률적 이웃 변화를 결합한다.이 순서는 알고리즘4에 기재되어 있습니다.연속되는 ${\mathcal {N}}_{k}$ $($ 는 ${\mathcal {N}}_{k}$ 종종 중첩됩니다.결정론적 규칙이 적용되는 경우 발생할 수 있는 순환을 피하기 위해 4단계에서 점 x'가 임의로 생성된다는 점에 유의하십시오.스텝 5에서는 보통 가장 개선된 로컬 검색(알고리즘 1)이 채택됩니다.그러나 첫 번째 개선(알고리즘 2)으로 대체할 수 있습니다.

알고리즘 4: 기본 VNS

기능 VNS(x, kmax, tmax) 1: 반복 2:k ← 1 3: 반복 4:x' ← 흔들림(x, k) // 흔들림 5:x' ← 최적 개선(x') // 로컬 검색 6:x ← NeighborhoodChange(x, x'), k) /// 7: k:km ← 8:km까지 인접 변경

VNS 바리안트

기본 VNS는 랜덤화를 ^[3]통한 최적의 개선 하강법이다.별도의 노력 없이 내림차순 방식으로 변환할 수 있습니다.NeighborhoodChange() 함수에서는 솔루션이 기존 솔루션보다 더 나쁘더라도 x by x"를 약간의 확률로 바꿉니다.첫 번째 개선 방법으로 변경할 수도 있습니다.기본 VNS의 또 다른 변형은 k번째 근방에서 무작위로 생성된 b(파라미터) 용액 중 가장 좋은 것으로서 '흔들기' 단계에서 용액 x'를 찾는 것이다.이 확장에는 두 가지 종류가 있습니다. (1) b 포인트 중 최상의 로컬 검색만 수행하는 것과 (2) 모든 b 로컬 검색을 수행한 다음 가장 적합한 로컬 검색을 선택하는 것입니다.종이(Fleszar 및^[12] 힌디어)에서는 알고리즘을 찾을 수 있습니다.

내선번호

비디오^[13]

가변 근린 강하(VND) 방법은 근린변화가 결정론적 방식으로 수행되는 경우 얻어진다.알고리즘 설명에서는 초기 솔루션 x가 주어졌다고 가정합니다.하강 단계의 대부분의 지역 탐색 휴리스틱스는 매우 적은 수의 이웃을 사용합니다.최종 솔루션은 모든

k_{max}

a

k_{max}

{\

displaystyle k_{max}

개의

k_{max}

네이버에 대한 로컬 최소값이어야 합니다.따라서 VND를 사용하면 단일 네이버 구조보다 글로벌하게 도달할 가능성이 더 커집니다.

RVNS^[14]

RVNS

{\mathcal {N}}_{k}(x)

Reduced VNS) 방법은 N

{\mathcal {N}}_{k}(x)

(

{\mathcal {N}}_{k}(x)

) {

display

\

mathcal {N} _ {k}(x)}

에서

{\mathcal {N}}_{k}(x)

랜덤 포인트가 선택되고 강하하지 않을 경우 얻을 수 있습니다.오히려 이러한 새로운 포인트의 값을 기존 포인트와 비교하여 개선 시 업데이트가 이루어집니다.정지조건은

t_{max}

되는

t_{max}

CPU시간

({

또는

t_{max}

두 개선 사이의 최대 반복 횟수 등 선택되었다고 가정합니다.

알고리즘의 설명을 간단하게 하기 위해 아래 x

t_{max}

{\

displaystyle t_{max}

에

t_{max}

t_{max}

합니다.따라서 RVNS에서는 t

t_{max}

t_{max}

x

t_{max}

{

display style

t _ {

max

}

k_{max}

k_{max}

m

k_{max}

{

display style

k _ {

max

의 2개의 파라미터를 사용합니다.RVNS는 로컬 검색 비용이 많이 드는 매우 큰 경우에 편리합니다.

k_{max}

k_{max}

m

k_{max}

k_{max}

{\

displaystyle k_{max}}

의

k_{{max}}

최적값은 2인 경우가 많습니다.또, 통상, 2개의 개선 사이의 최대 반복 회수를 정지 조건으로 한다.RVNS는 Monte-Carlo 방식과 비슷하지만 더 체계적입니다.

비뚤어진 VNS

왜곡된 VNS(SVNS) 방법(Hansen ^[15]등)은 기존 솔루션과는 거리가 먼 계곡 탐색 문제를 해결합니다.사실, 넓은 지역에서 가장 좋은 해결책을 찾았으면, 더 나은 해결책을 얻기 위해 어떤 방법을 강구할 필요가 있다.먼 이웃에서 무작위로 도출된 솔루션은 현재와 상당히 다를 수 있으며, VNS는 어느 정도 다단계 휴리스틱(multistart 휴리스틱, 즉 매우 효율적이지 않은 휴리스틱)으로 퇴화할 수 있다.따라서 기존과의 거리에 대한 약간의 보상은 이루어져야 한다.

가변 근린 분해 검색

Variable Neighbor Decomposition Search(VNDS; 가변 근린 분해 검색) 방식(Hansen 등)은 문제의 분해에 근거하여 기본 VNS를 2단계 VNS 방식으로 확장합니다.^[16]표시하기 쉽지만 일반성을 잃지 않기 위해 솔루션 x는 일부 요소의 집합을 나타낸다고 가정합니다.

병렬 VNS

최근 p-Median 문제를 해결하기 위해 VNS를 병렬화하는 몇 가지 방법이 제안되었습니다.Garcia-Löpez ^[17]등에서는 (i) 로컬 검색 병렬화, (ii) 현재 인근 지역에서 도출된 솔루션 수를 늘리고 각 솔루션에서 로컬 검색을 병행하며 (ii)와 동일한 작업을 수행하지만 발견된 최적의 솔루션에 대한 정보를 업데이트한다.또한 Ochi ^[18]등의 여행 구매자 문제를 해결하기 위해 세 가지 병행 VNS 전략이 제안됩니다.

프라이머리 듀얼 VNS

대부분의 현대 휴리스틱에서 최적 솔루션과 얻어진 솔루션 사이의 값 차이는 완전히 알려져 있지 않습니다.목적 함수 값의 하한을 알고 있는 경우 원시 휴리스틱의 보장된 성능을 결정할 수 있다.이를 위해 표준 접근법은 문제의 수학적 프로그래밍 공식을 바탕으로 기본 변수에 대한 통합 조건을 완화하는 것이다.

그러나 문제의 차원이 클 경우, 이완된 문제조차도 표준 상용 해결사로는 정확하게 해결할 수 없을 수 있습니다.따라서 이중완화 문제도 휴리스적으로 풀어보는 것이 좋을 것 같습니다.원시 휴리스틱스 성능에 대한 보장된 한계를 얻었습니다.Primal-Dual VNS(PD-VNS)(Hansen 등)^[19]에서는 보장된 경계와 정확한 솔루션을 모두 달성하기 위한 하나의 가능한 일반적인 방법이 제안됩니다.

가변 네이버브런치^[20]

Mixed Integer Linear Programming(MILP; 혼합 정수 선형 프로그래밍) 문제는 선형 함수를 최대화 또는 최소화하는 것으로 구성되며, 등식 또는 부등식 제약 및 일부 변수에 대한 적분성 제약이 적용됩니다.

가변 근린 표현 공간^[21] 검색

FSS는 하나의 문제가 추가 제형에 정의될 수 있고 제형을 통해 이동하는 것이 합법적이기 때문에 매우 유용한 방법이다.로컬 검색은 공식 내에서 작동하며, 첫 번째 공식에서 초기 솔루션에서 시작할 때 최종 솔루션을 암시합니다.로컬 검색은 직교좌표에서 CPP의 비선형 프로그래밍 공식에 대한 정지점이 극좌표에서 엄밀하게 정지점이 아닌 원 패킹 문제(CPP)에 대해 조사된 다른 공식 사이를 체계적으로 교체한다.

적용들

VNS 또는 다양한 VNS의 응용 분야는 매우 풍부하고 다양합니다.과학 논문 컬렉션을 찾을 수 있는 일부 분야:

산업용 응용 프로그램
커뮤니케이션 설계상의 문제
로케이션
데이터 마이닝
그래프 문제
배낭 및 포장 문제
혼합 정수 문제
시간표 작성
스케줄
차량 배선 문제
아크 라우팅 및 폐기물 수집
플리트 시트의 문제
차량 경로 확장 문제
생명과학 및 화학 문제
연속 최적화
기타 최적화 문제
발견과학

결론

VNS는 한센과 믈라데노비치가^[22] 제시한 몇 가지 특징을 의미하며, 일부는 여기에 제시되어 있다.

심플성: VNS는 심플하고 명확하며 보편적으로 적용 가능
정밀도: VNS는 정확한 수학적 정의로 공식화됩니다.
일관성: 문제 해결을 위한 휴리스틱스의 모든 액션은 VNS 원칙에 따릅니다.
효과: VNS는 모든 인스턴스 또는 가장 현실적인 인스턴스에 최적 또는 거의 최적에 가까운 솔루션을 제공합니다.
효율성: VNS는 최적의 솔루션 또는 거의 최적의 솔루션을 생성하는데 적당한 컴퓨팅 시간이 소요됩니다.
견고성: VNS의 기능은 다양한 인스턴스에서 일관성이 있습니다.
사용자 친화성: VNS에는 파라미터가 없기 때문에 이해, 표현, 사용이 용이함
혁신: VNS는 새로운 유형의 애플리케이션을 생성하고 있습니다.
일반성: VNS는 다양한 문제에 대해 좋은 결과를 가져옵니다.
인터랙티브: VNS를 통해 사용자는 자신의 지식을 활용하여 해결 프로세스를 개선할 수 있습니다.
다양성: VNS는 사용자가 선택할 수 있는 최적의 솔루션을 제공할 수 있습니다.

VNS에 대한 관심은 급속히 증가하고 있습니다.이는 이 주제에 관한 논문의 수가 매년 증가하고 있음을 증명합니다(10년 전만 해도 불과 몇 년 전, 5년 전만 해도 약 12건, 2007년에는 약 50건).게다가 2005년 11월에 테네리페에서 개최된 제18회 EURO 미니 콘퍼런스는, VNS에 전념하고 있습니다.2007년에는 IMA Journal of Management Mathematics, 2008년에는 European Journal of Operational Research(http://www.journals.elsevier.com/european-journal-of-operational-research/),) 및 Journal of Huristics(https://www.springer.com/mathematics/applications/journal/10732/))가 발행되었습니다.

레퍼런스

^ Hansen, P.; Mladenović, N.; Perez, J.A.M. (2010). "Variable neighbourhood search: methods and applications". Annals of Operations Research. 175: 367–407. doi:10.1007/s10479-009-0657-6. S2CID 26469746.
^ Nenad Mladenović; Pierre Hansen (1997). "Variable neighborhood search". Computers and Operations Research. 24 (11): 1097–1100. CiteSeerX 10.1.1.800.1797. doi:10.1016/s0305-0548(97)00031-2.
^ ^a ^b ^c Gendreau, M.; Potvin, J-Y. (2010). "Handbook of Metaheuristics". Springer.
^ Glover, F.; Kochenberger, G.A. (2003). "Handbook of Metaheuristics". Kluwer Academic Publishers.
^ Burke, EK.; Kendall, G. (2005). Burke, Edmund K; Kendall, Graham (eds.). Search methodologies. Introductory tutorials in optimization and decision support techniques. Springer. doi:10.1007/978-1-4614-6940-7. ISBN 978-1-4614-6939-1.
^ Davidon, W.C. (1959). "Variable metric algorithm for minimization". Argonne National Laboratory Report ANL-5990.
^ Fletcher, R.; Powell, M.J.D. (1963). "Rapidly convergent descent method for minimization". Comput. J. 6 (2): 163–168. doi:10.1093/comjnl/6.2.163.
^ Mladenović, N. (1995). "A variable neighborhood algorithm—a new metaheuristic for combinatorial optimization". Abstracts of Papers Presented at Optimization Days, Montréal: 112.
^ Brimberg, J.; Mladenović, N. (1996). "A variable neighborhood algorithm for solving the continuous location-allocation problem". Stud. Locat. Anal. 10: 1–12.
^ Hansen, P.; Mladenović, N.; Perez, J.A.M (2008). "Variable neighbourhood search: methods and applications". 4OR. 6 (4): 319–360. doi:10.1007/s10288-008-0089-1. S2CID 538959.
^ Moreno-Pérez, JA.; Hansen, P.; Mladenović, N. (2005). "Parallel variable neighborhood search". In Alba, E (ed.). Parallel Metaheuristics: A New Class of Algorithms. pp. 247–266. CiteSeerX 10.1.1.615.2796. doi:10.1002/0471739383.ch11. ISBN 9780471739388.
^ Fleszar, K; Hindi, KS (2004). "Solving the resource-constrained project scheduling problem by a variable neighbourhood search". Eur J Oper Res. 155 (2): 402–413. doi:10.1016/s0377-2217(02)00884-6.
^ Brimberg, J.; Hansen, P.; Mladenović, N.; Taillard, E. (2000). "Improvements and comparison of heuristics for solving the multisource Weber problem". Oper. Res. 48 (3): 444–460. doi:10.1287/opre.48.3.444.12431.
^ Mladenović, N.; Petrovic, J.; Kovacevic-Vujcic, V.; Cangalovic, M. (2003b). "Solving spread spectrum radar polyphase code design problem by tabu search and variable neighborhood search". Eur. J. Oper. Res. 151 (2): 389–399. doi:10.1016/s0377-2217(02)00833-0.
^ Hansen, P.; Jaumard, B; Mladenović, N; Parreira, A (2000). "Variable neighborhood search for weighted maximum satisfiability problem". Les Cahiers du GERAD G–2000–62, HEC Montréal, Canada.
^ Hansen, P; Mladenović, N; Pérez-Brito, D (2001). "Variable neighborhood decomposition search". J Heuristics. 7 (4): 335–350. doi:10.1023/A:1011336210885. S2CID 31111583.
^ García-López, F; Melián-Batista, B; Moreno-Pérez, JA (2002). "The parallel variable neighborhood search for the p-median problem". J Heuristics. 8 (3): 375–388. doi:10.1023/A:1015013919497. S2CID 16096161.
^ Ochi, LS; Silva, MB; Drummond, L (2001). "Metaheuristics based on GRASP and VNS for solving traveling purchaser problem". MIC'2001, Porto: 489–494.
^ Hansen, P; Brimberg, J; Uroševi´c, D; Mladenović, N (2007a). "Primal-dual variable neighborhood search for the simple plant location problem". INFORMS J Comput. 19 (4): 552–564. doi:10.1287/ijoc.1060.0196.
^ Hansen, P.; Mladenović, N.; Urosevic, D. (2006). "Variable neighborhood search and local branching". Computers and Operations Research. 33 (10): 3034–3045. CiteSeerX 10.1.1.108.987. doi:10.1016/j.cor.2005.02.033.
^ Mladenović, N.; Plastria, F.; Urosevic, D. (2006). "Reformulation descent applied to circle packing problems". Computers and Operations Research. 32 (9): 2419–2434. doi:10.1016/j.cor.2004.03.010.
^ Hansen, P; Mladenović, N (2003). "Variable neighborhood search". In Glover F; Kochenberger G (eds.). Handbook of Metaheuristics. International Series in Operations Research & Management Science. Vol. 57. Dordrecht: Kluwer. pp. 145–184. CiteSeerX 10.1.1.635.7056. doi:10.1007/0-306-48056-5_6. ISBN 978-1-4020-7263-5.

외부 링크

[1] Hansen, P.; Mladenović, N.; Perez, J.A.M. (2010). "Variable neighbourhood search: methods and applications". Annals of Operations Research. 175: 367–407. doi:10.1007/s10479-009-0657-6. S2CID 26469746.

[.....-2] Nenad Mladenović; Pierre Hansen (1997). "Variable neighborhood search". Computers and Operations Research. 24 (11): 1097–1100. CiteSeerX 10.1.1.800.1797. doi:10.1016/s0305-0548(97)00031-2.

[HoM2010-3] Gendreau, M.; Potvin, J-Y. (2010). "Handbook of Metaheuristics". Springer.

[4] Glover, F.; Kochenberger, G.A. (2003). "Handbook of Metaheuristics". Kluwer Academic Publishers.

[5] Burke, EK.; Kendall, G. (2005). Burke, Edmund K; Kendall, Graham (eds.). Search methodologies. Introductory tutorials in optimization and decision support techniques. Springer. doi:10.1007/978-1-4614-6940-7. ISBN 978-1-4614-6939-1.

[6] Davidon, W.C. (1959). "Variable metric algorithm for minimization". Argonne National Laboratory Report ANL-5990.

[7] Fletcher, R.; Powell, M.J.D. (1963). "Rapidly convergent descent method for minimization". Comput. J. 6 (2): 163–168. doi:10.1093/comjnl/6.2.163.

[8] Mladenović, N. (1995). "A variable neighborhood algorithm—a new metaheuristic for combinatorial optimization". Abstracts of Papers Presented at Optimization Days, Montréal: 112.

[9] Brimberg, J.; Mladenović, N. (1996). "A variable neighborhood algorithm for solving the continuous location-allocation problem". Stud. Locat. Anal. 10: 1–12.

[10] Hansen, P.; Mladenović, N.; Perez, J.A.M (2008). "Variable neighbourhood search: methods and applications". 4OR. 6 (4): 319–360. doi:10.1007/s10288-008-0089-1. S2CID 538959.

[11] Moreno-Pérez, JA.; Hansen, P.; Mladenović, N. (2005). "Parallel variable neighborhood search". In Alba, E (ed.). Parallel Metaheuristics: A New Class of Algorithms. pp. 247–266. CiteSeerX 10.1.1.615.2796. doi:10.1002/0471739383.ch11. ISBN 9780471739388.

[12] Fleszar, K; Hindi, KS (2004). "Solving the resource-constrained project scheduling problem by a variable neighbourhood search". Eur J Oper Res. 155 (2): 402–413. doi:10.1016/s0377-2217(02)00884-6.

[13] Brimberg, J.; Hansen, P.; Mladenović, N.; Taillard, E. (2000). "Improvements and comparison of heuristics for solving the multisource Weber problem". Oper. Res. 48 (3): 444–460. doi:10.1287/opre.48.3.444.12431.

[14] Mladenović, N.; Petrovic, J.; Kovacevic-Vujcic, V.; Cangalovic, M. (2003b). "Solving spread spectrum radar polyphase code design problem by tabu search and variable neighborhood search". Eur. J. Oper. Res. 151 (2): 389–399. doi:10.1016/s0377-2217(02)00833-0.

[15] Hansen, P.; Jaumard, B; Mladenović, N; Parreira, A (2000). "Variable neighborhood search for weighted maximum satisfiability problem". Les Cahiers du GERAD G–2000–62, HEC Montréal, Canada.

[16] Hansen, P; Mladenović, N; Pérez-Brito, D (2001). "Variable neighborhood decomposition search". J Heuristics. 7 (4): 335–350. doi:10.1023/A:1011336210885. S2CID 31111583.

[17] García-López, F; Melián-Batista, B; Moreno-Pérez, JA (2002). "The parallel variable neighborhood search for the p-median problem". J Heuristics. 8 (3): 375–388. doi:10.1023/A:1015013919497. S2CID 16096161.

[18] Ochi, LS; Silva, MB; Drummond, L (2001). "Metaheuristics based on GRASP and VNS for solving traveling purchaser problem". MIC'2001, Porto: 489–494.

[19] Hansen, P; Brimberg, J; Uroševi´c, D; Mladenović, N (2007a). "Primal-dual variable neighborhood search for the simple plant location problem". INFORMS J Comput. 19 (4): 552–564. doi:10.1287/ijoc.1060.0196.

[20] Hansen, P.; Mladenović, N.; Urosevic, D. (2006). "Variable neighborhood search and local branching". Computers and Operations Research. 33 (10): 3034–3045. CiteSeerX 10.1.1.108.987. doi:10.1016/j.cor.2005.02.033.

[21] Mladenović, N.; Plastria, F.; Urosevic, D. (2006). "Reformulation descent applied to circle packing problems". Computers and Operations Research. 32 (9): 2419–2434. doi:10.1016/j.cor.2004.03.010.

[22] Hansen, P; Mladenović, N (2003). "Variable neighborhood search". In Glover F; Kochenberger G (eds.). Handbook of Metaheuristics. International Series in Operations Research & Management Science. Vol. 57. Dordrecht: Kluwer. pp. 145–184. CiteSeerX 10.1.1.635.7056. doi:10.1007/0-306-48056-5_6. ISBN 978-1-4020-7263-5.

[2]

[1]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

Search