욕심 많은 임의의 적응형 검색 절차

Greedy randomized adaptive search procedure

탐욕스러운 무작위 적응형 검색 절차(일명 HIGHT)는 조합 최적화 문제에 공통적으로 적용되는 메타휴리스틱 알고리즘이다.HANCH는 일반적으로 탐욕스러운 무작위 솔루션의 연속적인 구성으로 이루어진 반복과 현지 검색을 통한 후속 반복적인 개선으로 구성된다.[1]탐욕스러운 무작위 해결책은 달성될 해결책의 질에 따라 탐욕스러운 함수에 의해 순위가 매겨진 요소 목록에서 문제의 해결책에 요소를 추가함으로써 생성된다.탐욕스러운 해결책의 후보 집합의 가변성을 얻기 위해, 잘 순위화된 후보 요소를 제한된 후보 리스트(RCL)에 배치하고, 솔루션을 구축할 때 무작위로 선택하는 경우가 많다.이런 종류의 탐욕스러운 무작위 건설방식은 하트와 쇼간(1987년)에 처음 묘사된 반자유적 휴리스틱으로도 알려져 있다.[2]

ALACH는 Feo와 Resende(1989년)에서 처음 도입되었다.[3]HIGH에 관한 조사 논문으로는 Feo와 Resende(1995년),[1] Resende와 Ribeiro(2003년)가 있다.[4]

리액티브 그립과 같은 고전 알고리즘의 변화도 있다. 이 변화에서 시공 단계 중 RCL의 제한성을 규정하는 기본 매개변수는 이전에 발견된 용액의 품질에 따라 자가 조정된다.[5]비용 섭동, 편향 기능, 암기 및 학습, 부분 구성 솔루션에 대한 국지적 검색 등 검색 속도 향상 기술도 있다.[4]

참조

  1. ^ a b Feo, Thomas A.; Resende, Mauricio G. C. (1995). "Greedy Randomized Adaptive Search Procedures". Journal of Global Optimization. 6 (2): 109–133. doi:10.1007/BF01096763. S2CID 2110014.
  2. ^ Hart, J. P.; Shogan, A. W. (July 1987). "Semi-greedy heuristics: An empirical study". Operations Research Letters. 6 (3): 107–114. doi:10.1016/0167-6377(87)90021-6.
  3. ^ Feo, Thomas A.; Resende, Mauricio G. C. (April 1989). "A probabilistic heuristic for a computationally difficult set covering problem". Operations Research Letters. 8 (2): 67–71. doi:10.1016/0167-6377(89)90002-3.
  4. ^ a b Resende, Mauricio G. C.; Ribeiro, Celso C. (2003). "Greedy Randomized Adaptive Search Procedures". Handbook of Metaheuristics. Springer. pp. 219–249. ISBN 978-0-306-48056-0.
  5. ^ Prais, Marcelo; Ribeiro, Celso C. (2000). "Reactive GRASP: An Application to a Matrix Decomposition Problem in TDMA Traffic Assignment". INFORMS Journal on Computing. 12 (3): 164–176. doi:10.1287/ijoc.12.3.164.12639.

참고 항목


Stub icon

이 콤비네이터 관련 기사는 단조롭다.위키피디아를 확장하여 도울 수 있다.