휴리스틱(컴퓨터 과학)

수학적 최적화와 컴퓨터 과학에서 휴리스틱(그리스어 εὑρσσωωωωωωωωωωωωωωωωω "I find, discover"에서)은 고전적인 방법이 너무 느릴 때 문제를 더 빨리 해결하거나 고전적인 방법이 어떤 정확한 해결책을 찾지 못할 때 근사적인 해결책을 찾기 위해 고안된 기법이다.이것은 속도와 최적성, 완전성, 정확성 또는 정밀도를 교환함으로써 달성된다.어떻게 보면 지름길이라고 볼 수 있다.

단순히 휴리스틱스라고도 불리는 휴리스틱 함수는 어떤 분기를 따를지 결정하기 위해 이용 가능한 정보를 바탕으로 각 분기 단계에서 검색 알고리즘의 대안 순위를 매기는 함수다.예를 들어, 정확한 용액에 근사치가 있을 수 있다.^[1]

정의와 동기 부여

휴리스틱스의 목표는 당면한 문제를 해결하기에 충분한 합리적인 시간 내에 해결책을 도출하는 것이다.이 해결책은 이 문제에 대한 모든 해결책 중 최선이 아닐 수도 있고, 또는 단순히 정확한 해결책의 근사치일 수도 있다.그러나 그것을 발견하는 데는 엄청나게 오랜 시간이 필요하지 않기 때문에 여전히 가치가 있다.

휴리스틱스는 스스로 결과를 만들 수도 있고, 그 효율을 개선하기 위해 최적화 알고리즘과 함께 사용될 수도 있다(예: 좋은 시드 값을 생성하기 위해 사용될 수도 있다).

이론 컴퓨터 과학에서 NP 경직성에 대한 결과는 휴리스틱스가 실제 애플리케이션에서 일상적으로 해결되어야 하는 다양한 복잡한 최적화 문제에 대해 유일하게 실행 가능한 옵션으로 만든다.

휴리스틱스는 알려진 알고리즘이 없는 상황에서 사용될 수 있기 때문에 인공지능의 전 분야와 사고의 컴퓨터 시뮬레이션의 기초가 된다.^[2]

트레이드오프

주어진 문제를 해결하는 데 휴리스틱스를 사용할지 여부를 결정하는 절충 기준은 다음과 같다.

최적성:주어진 문제에 대해 몇 가지 해결책이 존재할 때, 경험적 발견은 최상의 해결책이 발견된다는 것을 보장하는가?최선의 해결책을 찾는 것이 실제로 필요한가?
완성도:주어진 문제에 대해 몇 가지 해결책이 존재할 때, 경험론자들은 그것들을 모두 찾을 수 있을까?정말 모든 해결책이 필요한가?많은 휴리스틱스는 단지 하나의 해결책을 찾기 위한 것이다.
정확성 및 정밀도: 경험적 접근방식이 보고된 솔루션에 대한 신뢰 구간을 제공할 수 있는가?솔루션의 오류 막대가 불합리하게 큰가?
실행 시간:이것이 이런 유형의 문제를 해결하기 위해 가장 잘 알려진 휴리스틱인가?어떤 휴리스틱스는 다른 휴리스틱스보다 더 빨리 수렴한다.일부 휴리스틱스는 고전적인 방법보다 약간 더 빠를 뿐이며, 이 경우 휴리스틱스 계산에 대한 '오버헤드'는 부정적인 영향을 미칠 수 있다.

어떤 경우에는 휴리스틱스의 기초가 되는 이론이 그리 정교하지 않기 때문에 휴리스틱스에 의해 발견된 해법이 충분한지 판단하기 어려울 수 있다.

예

더 간단한 문제

휴리스틱스에 기대되는 계산적 성능 향상을 달성하는 한 가지 방법은 초기 문제에 대한 해결책이기도 한 단순한 문제를 해결하는 것이다.

출장 세일즈맨 문제

근사치의 예는 여행 세일즈맨 문제(TSP)를 해결하기 위해 존 벤틀리가 설명한다.

"도시 목록과 각 도시 쌍간의 거리를 감안할 때 각 도시를 정확히 한 번 방문하고 원도심으로 돌아오는 가장 짧은 경로는 무엇인가?"

펜 플로터를 사용하여 그릴 순서를 선택하기 위해.TSP는 NP-Hard로 알려져 있어 적당한 크기 문제에도 최적의 솔루션을 찾기 어렵다.대신에 탐욕스러운 알고리즘을 사용하여 합리적으로 짧은 시간 내에 우수하지만 최적의 해법(최적 답안에 대한 근사치)을 제공할 수 있다.탐욕스러운 알고리즘 휴리스틱은 그것이 나중에 좋은 스텝을 예방하는지 혹은 심지어 불가능하게 하는지 여부와 상관없이 현재 최고의 다음 스텝을 선택하라고 말한다.이론은 더 나은 해결책이 있다고 말하고 심지어 어떤 경우에는 얼마나 더 나은지 알 수 있다고 말한다.^[3]

검색

알고리즘을 더 빠르게 만드는 경험적 경험의 또 다른 예는 특정 검색 문제에서 발생한다.처음에 휴리스틱은 전체 공간 검색 알고리즘처럼 각 단계에서 모든 가능성을 시도한다.그러나 현재의 가능성이 이미 발견된 최선의 해결책보다 더 나쁘다면 언제라도 검색을 중단할 수 있다.이러한 검색 문제에서는 나쁜 경로가 조기에 제거될 수 있도록 휴리스틱을 먼저 사용해 좋은 선택을 시도할 수 있다(알파베타 가지치기 참조).A* 검색과 같은 베스트 퍼스트 검색 알고리즘의 경우 휴리스틱이 허용되는 한 휴리스틱은 정확성을 유지하면서 알고리즘의 정합성을 향상시킨다.

뉴웰과 사이먼: 휴리스틱 검색 가설

그들의 튜링상 수상 연설에서 앨런 뉴웰과 허버트 A. Simon은 경험적 발견 가설을 논한다: 물리적 기호 시스템은 생성된 구조가 솔루션 구조와 일치할 때까지 알려진 기호 구조를 반복적으로 생성하고 수정할 것이다.각각의 다음 단계는 그 이전의 단계에 따라 달라지기 때문에, 경험적 발견은 현재 단계가 해결책에 얼마나 가까운지를 측정함으로써 어떤 방법을 추구해야 하고 어떤 것을 무시해야 하는지를 배운다.따라서 일부 가능성은 해결책의 완성 가능성이 낮은 것으로 측정되기 때문에 결코 생성되지 않을 것이다.

휴리스틱한 방법은 검색 트리를 사용하여 그 임무를 수행할 수 있다.그러나 가능한 모든 솔루션 분기를 생성하는 대신 휴리스틱스는 다른 분기에 비해 결과를 산출할 가능성이 더 높은 분기를 선택한다.그것은 각 결정 지점에서 선별적이며, 해결책을 도출할 가능성이 더 높은 지점을 선택한다.^[4]

안티바이러스 소프트웨어

바이러스 백신 소프트웨어는 종종 바이러스 및 다른 형태의 악성 프로그램을 탐지하기 위해 경험적 접근 규칙을 사용한다.휴리스틱스 스캐닝은 다른 바이러스에 대한 서로 다른 규칙 집합을 가진 바이러스 클래스 또는 제품군에 공통되는 코드 및/또는 행동 패턴을 찾는다.파일 또는 실행 프로세스가 일치하는 코드 패턴을 포함하거나 일련의 활동을 수행하는 것으로 확인되면 스캐너는 파일이 감염되었음을 주입한다.행동 기반 휴리스틱스 스캐닝의 가장 진보된 부분은 보다 단순한 문자열 스캐닝 방법으로는 쉽게 검출할 수 없는 고도로 무작위화된 자기수정/교화(폴리모르픽) 바이러스에 대항할 수 있다는 점이다.휴리스틱스 스캐닝은 바이러스를 다른 곳에서 먼저 검출할 필요 없이 미래의 바이러스를 탐지할 수 있는 잠재력을 가지고 있으며, 바이러스 스캐너 개발자에게 제출, 분석, 스캐너 사용자에게 제공되는 스캐너에 대한 탐지 업데이트 등이 있다.

함정스

어떤 휴리스틱스는 기초적인 이론이 강하다; 그것들은 이론으로부터 하향식으로 도출되거나 실험적인 혹은 실제적인 세계 데이터에 기초하여 도달된다.다른 것들은 이론의 눈길조차 주지 않고 실제의 관찰이나 경험에 근거한 경험에 근거한 경험의 법칙에 불과하다.후자는 더 많은 함정에 노출된다.

주어진 요구 사항을 충족한다는 것이 수학적으로 입증되지 않은 상태에서 하나의 맥락에서 "작업"하는 것으로 보여져 휴리스틱이 다양한 맥락에서 재사용되는 경우, 현재의 데이터 세트가 반드시 미래의 데이터 세트(: 오버피팅 참조)를 나타내지 않으며, 그 것으로 알려진 "솔루션"이 소음과 유사한 것으로 판명될 가능성이 있다.

부정확한 결과의 확률을 추정하기 위해 휴리스틱스를 채택할 때 통계 분석을 수행할 수 있다.검색 문제나 배낭 문제 해결에 휴리스틱스를 이용하려면 휴리스틱스가 허용되는지 확인할 필요가 있다.Given a heuristic function $h(v_{i},v_{g})$ meant to approximate the true optimal distance $d^{\star }(v_{i},v_{g})$ to the goal node $v_{g}$ in a directed graph $G$ containing ${\displaysty$ $le n}$ total nodes or vertices labeled $v_{0},v_{1},\cdots ,v_{n}$ , "admissible" means roughly that the heuristic underestimates the cost to the goal or formally that $h(v_{i},v_{g})\leq d^{\star }(v_{i},v_{g})$ for all $(v_{i},v_{g})$ ( $(v_{i},v_{g})$ i $(v_{i},v_{g})$ , $(v_{i},v_{g})$ $(v_{i},v_{g})$ ) ${\displaystyle (v_{i},v_{g}}},$ ${i,g}\in [0,1,...,n]$ 서 $(v_{i},v_{g})$ ${i,g}\in [0,1,...,n]$ , g ${i,g}\in [0,1,...,n]$ [ ${i,g}\in [0,1,...,n]$ ${i,g}\in [0,1,...,n]$ , ${i,g}\in [0,1,...,n]$ . . ${i,g}\in [0,1,...,n]$ {\ $displaystyle {i,g}\in$ 1,..., $n].$

경험적 휴리스틱이 허용되지 않는 경우, G ${\displaystyle$ G}의 막다른 끝에 도달하거나 $G$ ${i,j}\neq g$ 노드 $v_{i}$ $v_{i}$ ${\$ 와 $v_{i}$ $v_{j}$ $v_{j}$ $v_{j}$ ${\displaystyle$ $v_$ ${j}$ 를 $앞뒤$ 로 건너뛰어 ${i,j}\neq g$ 를 찾지 못할 수 있다 ${i,j}\neq g$

어원

"휴리스틱"이라는 단어는 19세기 초에 사용되기 시작했다.그것은 "찾아가는 것"^[5]이라는 뜻의 그리스어 heuriskein에서 불규칙적으로 형성된다.

참고 항목

알고리즘.
건설적 휴리스틱
유전 알고리즘
휴리스틱
휴리스틱 라우팅
휴리스틱스 평가:사용자 인터페이스에서 사용적합성 문제를 식별하는 방법.
메타휴리스틱:일반적으로 메모리 및 학습을 사용하여 기본 경험적 경험적 알고리즘을 제어하고 조정하는 방법.
수학:메타휴리스틱스와 수학 프로그래밍(MP) 기법의 상호작용으로 만들어진 최적화 알고리즘.
사후 대응적 검색 최적화:경험적 접근의 자가 조정을 위해 온라인 기계 학습 원리를 사용하는 방법.
재귀(컴퓨터 과학)
매크로(컴퓨터 과학)

참조

^ Pearl, Judea (1984). Heuristics: intelligent search strategies for computer problem solving. United States: Addison-Wesley Pub. Co., Inc., Reading, MA. p. 3. OSTI 5127296.
^ Apter, Michael J. (1970). The Computer Simulation of Behaviour. London: Hutchinson & Co. p. 83. ISBN 9781351021005.
^ Jon Louis Bentley (1982). Writing Efficient Programs. Prentice Hall. p. 11.
^ Allen Newell and Herbert A. Simon (1976). "Computer Science as Empirical Inquiry: Symbols and Search" (PDF). Comm. ACM. 19 (3): 113–126. doi:10.1145/360018.360022. S2CID 5581562.
^ "Definition of heuristic in English". Oxford University Press. Archived from the original on 23 October 2016. Retrieved 22 October 2016.

[1] Pearl, Judea (1984). Heuristics: intelligent search strategies for computer problem solving. United States: Addison-Wesley Pub. Co., Inc., Reading, MA. p. 3. OSTI 5127296.

[2] Apter, Michael J. (1970). The Computer Simulation of Behaviour. London: Hutchinson & Co. p. 83. ISBN 9781351021005.

[3] Jon Louis Bentley (1982). Writing Efficient Programs. Prentice Hall. p. 11.

[4] Allen Newell and Herbert A. Simon (1976). "Computer Science as Empirical Inquiry: Symbols and Search" (PDF). Comm. ACM. 19 (3): 113–126. doi:10.1145/360018.360022. S2CID 5581562.

[5] "Definition of heuristic in English". Oxford University Press. Archived from the original on 23 October 2016. Retrieved 22 October 2016.

[1]

[2]

[3]

[4]

[5]

Search