안내된 로컬 검색

Guided Local Search는 메타휴리스틱 검색 방법이다.메타휴리스틱(meta-heuristic) 방법은 로컬 검색 알고리즘의 맨 위에 앉아 동작을 변경하는 방법이다.

Guided Local Search는 검색 중에 벌칙을 만든다.지역 검색 알고리즘이 지역 미니마와 고지로부터 탈출할 수 있도록 위약금을 사용한다.주어진 로컬 검색 알고리즘이 로컬 최적 상태로 정착되면 GLS는 특정 체계(아래 설명)를 사용하여 목표 기능을 수정한다.그런 다음 로컬 검색은 로컬 최적에서 검색 범위를 벗어나도록 설계된 증강 목표 기능을 사용하여 작동된다.열쇠는 객관적 기능이 수정되는 방식이다.

개요

솔루션 기능

GLS를 적용하려면 주어진 문제에 대해 솔루션 기능을 정의해야 한다.솔루션 특성은 서로 다른 특성을 가진 솔루션을 구별하기 위해 정의되며, 국소 최적화 주변의 유사 영역을 인식하고 피할 수 있다.솔루션 기능의 선택은 문제 유형과 로컬 검색 알고리즘에 따라 일정 정도 달라진다.각 형상 $f_{i}$ $f_{i}$ ${\$ 에 대해 비용 $f_{i}$ 함수 $c_{i}$ i ${\$ 가 정의된다 $c_{i}$ .

또한 각 형상은 $p_{i}$ p $p_{i}$ {\ $displaystyle p_{i}($ 초기 0으로 설정됨)와 연관되어 로컬 미니마에서 형상의 발생 횟수를 기록한다.

특징과 비용은 종종 객관적인 기능에서 직접 나온다.예를 들어, 여행 판매원 문제에서 "투어가 도시 X에서 도시 Y로 직접 가는지 여부"를 특징으로 정의할 수 있다.X와 Y 사이의 거리는 비용으로 정의할 수 있다.SAT 및 가중 MAX-SAT 문제에서 특성은 "현재 할당으로 절 C가 충족되는지 여부"가 될 수 있다.

구현 $i$ 에서는 각 기능I {\ $displaystyle$ i}에 $i$ 대해 해당 기능이 현재 솔루션에 있는지 여부를 나타내는 $I_{i}$ 표시기 $I_{i}$ $I_{i}$ ${\$ 를 정의한다. $I_{i}$ $I$ ${\displaystyle I_{$ $i}$ 은(는) 솔루션x {\displaystyle x}이( $가$ ) 속성 i {\ $displaystyle i}$ 을(를) 표시할 $x$ 때 1이고 $I_{i}$ $i$ 그렇지 않으면 0이다 $.$

선택적 벌칙 수정

GLS는 각 형상을 처벌하는 효용성을 계산한다.로컬 검색 알고리즘이 로컬 최소 x를 반환할 때 GLS는 최대 효용이 있는 솔루션에 존재하는 모든 기능(특징의 페널티까지 증분)에 대해 아래에 정의된 대로 $\operatorname {util} (x,i)$ $\operatorname {util} (x,i)$ ) $\operatorname {util} (x,i)$ {\ $displaysty \operatorname {util}(x,i$ 을(를) $\operatorname {util} (x,i)$ 하여 불이익을 준다.

\propertname {util}(x,i)=I_{i}(x){\frac {c_{i}(x)}{1+p_{i}}}.

그 아이디어는 비용이 많이 드는 특징들을 처벌하는 것인데, 비록 그렇게 하는 것의 효용은 그 특징들이 점점 더 자주 처벌될수록 감소한다.

증강 비용 함수를 통한 검색

GLS는 증강 비용 함수(아래 정의)를 사용하여 로컬 최소값에서 로컬 최소값으로 존재하는 벌칙 기능을 통해 로컬 검색 알고리즘을 유도할 수 있다.그 아이디어는 이러한 특징들이 존재하지 않는 주변 검색 공간보다 최소의 비용이 드는 지역을 만드는 것이다.

g(x)=f(x)+\lambda a\sum _{1\leq i\leq m}I_{i}(x)p_{i}}}}}{i}}}}}

λ 매개변수를 사용하여 해결책 탐색의 강도를 변경할 수 있다.λ의 값이 높을수록 고지와 분지를 더 거칠게 검색하는 보다 다양한 검색이 이루어질 것이며, 낮은 값을 가질수록 검색 환경의 고지와 분지를 더 세밀하게 검색하는 해결책에 대한 보다 집중적인 검색이 이루어질 것이다.계수 $a$ $a$ 은(는) 목표함수의 페널티 부분을 목표함수의 변화에 비례하여 균형을 이루도록 하는데 사용되며 $a$ 문제를 특정한다. $a$ 을(를) 설정하기 위한 간단한 경험적 접근법은 객관적 기능의 평균 변화를 첫 번째 로컬 최소값까지 기록한 다음 $a$ 을 $a$ (를) 문제 인스턴스의 GLS 특징 수로 나눈 값으로 설정하는 것이다 $a$ .

현지 안내 검색의 확장

밀스(2002)는 무작위 이동과 페널티 기반 계획을 위해 특별히 설계된 흡인 기준을 활용하는 확장 안내 로컬 검색(EGLS)을 설명하였다.결과 알고리즘은 특히 2차 배정 문제의 경우 파라미터 설정 범위에 걸쳐 GLS의 강건성을 개선했다.제약조건 만족도와 최적화를 위해 부분적으로 GENTER를 기반으로 하고 Min-conflicts 기반 언덕 등반가(Minton et al. 1992)를 사용하는 GLS 알고리즘의 일반 버전도 Computer Aided Restriction Programming 프로젝트에서 구현되었다.

Alcheddy(2011)는 Guided Local Search를 다중 객체 최적화로 확장하고, 직원들에게 스케줄링^{[citation needed]} 권한을 부여하는 것을 시연했다.

참고 문헌 목록

A, A, 권한 부여 스케줄링: Guided Local Search, PhD Statement, School of Computer Science and Electronic Engineering, 2011 [1]
최, K.M.F, Lee, J.H.M & Stuckey, P.J., A Lagrangian Reconstruction of GENT, 인공지능, 2000, 123(1-2), 1-39
Davenport A, Tsang E.P.K, 강민 주&C J Wang, GENTER: 반복적 개선에 의한 제약조건 만족도 문제 해결을 위한 연결론적 아키텍처, Proc, AAAI, 1994, p.325-330 [2]
Lau, T.L. & Tsang, E.P.K., 변이 기반 유전자 알고리즘으로 프로세서 구성 문제 해결 IJAIT(Intelligence Intelligence Tools) World Scientific, Vol.6, No.4, 1997년 12월, 567-585
Lau, T.L. & Tsang, E.P.K., 유도 유전 알고리즘과 무선 링크 주파수 할당 문제, 제약 조건, Vol.6, No.4, 2001, 373-398 [3]
Lau, T.L. & Tsang, E.P.K., Guided Genetic 알고리즘과 일반 과제 문제 적용, IEEE 10차 인공지능 도구 국제회의(ICTAI'98), 대만, 1998년 11월
밀스, P. & Tsang, E.P.K., SAT 문제 해결을 위한 현지 검색 안내 및 가중 MAX-SAT 문제, 자동 추론 저널, 만족도 문제에 대한 특별 이슈, 클루워, Vol.24, 2000, 205-223 [4]
밀스, P. & Tsang, E.P.K. & Ford, J, 2차 배정 문제에 대한 확장 안내 지역 검색 적용, 운영 연구 연보, 클루워 학술 출판사, Vol.118, 2003, 121-135 [5]
Minton, S, Johnston, M, Philips, A.B. & Laird, P, 갈등 최소화: 제약 만족도와 스케줄링 문제를 위한 휴리스틱 보수 방법, 인공지능(제약 기반 추론에 관한 특별 책), Vol.58, No.1-3 1992, 161-205
Tsang, E.P.K. & Voudouris, C, Fast local search and guided their application to British Telecom의 인력 스케줄링 문제, Operation Research Letters, Exvier Science Publishers, Vamsterdam, Vol.20, No.3, 1997년 3월, 119-127 [6]
Voudouris, C, 조합 최적화 문제에 대한 현지 검색 안내, 컴퓨터 과학 학부의 박사 논문, 영국 에섹스 대학교, 콜체스터, 1997년 7월 [7]
Voudouris, C, Guided Local Search—기능 최적화 예시, BT Technology Journal, Vol.16, No.3, 1998년 7월, 46-50[8]
Voudouris, C. & Tsang, E.P.K., Guided Local Search 및 그 응용 프로그램인 Traveling Salesman 문제, European Journal of Operational Research, Anbar Publishing, Vol.113, 1999년 3월 2호, 469-499 [9]
Voudouris, C. & Tsang, E.P.K. Guided local search는 이산 최적화의 엘리트, 이산수학 및 이론 컴퓨터 과학 제57권, 2001, 29-39권 [10]
부두리스, C. & Tsang, E.P.K. 안내 지역 검색, F.글로버(edd.), Kluwer, 2003, 185-218 [11]
Voudouris, C, Tsang, E.P.K. & A.A., Gendreau & J-Y Potvin (ed.), M. Gendreau & J-Y Potvin (ed.), 메타휴리스틱스 핸드북, Springer, 2010, 321-361

외부 링크

안내된 로컬 검색 홈 페이지

Search