[클린코드] 휴리스틱(heuristics)이란? : 휴리스틱 이론과 휴리스틱 알고리즘

클린코드 책을 읽던 중 디미터 법칙에 대한 이야기가 나왔다.

디미터 법칙이 잘 알려진 휴리스틱이라는 서술이 있었는데, 나는 휴리스틱의 제대로 된 의미조차 모르고 있었다.

 

그래서

휴리스틱의 기본 개념과 CS(Computer Science)에서의 휴리스틱의 의미의 차이,

휴리스틱 알고리즘에 대해 알아보고자 이 글을 작성하게 되었다.

 

| 휴리스틱 이론

휴리스틱(heuristics) 또는 발견법(發見法)이란 불충분한 시간이나 정보로 인하여 합리적인 판단을 할 수 없거나, 체계적이면서 합리적인 판단이 굳이 필요하지 않은 상황에서 사람들이 빠르게 사용할 수 있게 보다 용이하게 구성된 간편추론의 방법이다.
문제해결에 있어서 복잡한 문제의 경우 초기에는 휴리스틱을 이용하여 과제를 단순화시킨 후 후기에 규범적(normative)인 의사결정 규칙을 사용하고, 단순한 과업 상황에서는 처음부터 최종 의사결정에 이르기까지 규범적 규칙을 이용하여 이를 해결하려한다는 가설은 허버트 사이먼(Simon, Herbert A)이 주창한 ‘제한된 합리성(bounded rationality)’에서 시작되었고 앨런 뉴얼(Newell, Allen)등이 공동 참여하였다. ‘제한된 합리성’이란 다양한 의사결정 상황에서 인간의 인지적인 한계로 인해 발생하는 의사결정 문제를 인지적 한계 안에서 다룰 수 있는 범위로 축소시키고, 간단해진 과업의 수행에 한해 규범적 규칙을 이용한다는 것을 의미한다.
휴리스틱의 어원은 라틴어의 ‘heuristicus’ 와 그리스어 ‘heuriskein’ 에서부터 시작되었으며, “찾아내다(find out)” 그리고 발견하다(discover)”라는 의미를 뜻한다.

https://ko.wikipedia.org/wiki/%ED%9C%B4%EB%A6%AC%EC%8A%A4%ED%8B%B1_%EC%9D%B4%EB%A1%A0 

 

즉, 휴리스틱이란 시간이나 정보가 부족하여 합리적인 판단을 할 수 없거나 굳이 판단하지 않아도 사람들이 빠르게 사용할수 있도록 한 간편추론의 방법이라고 할 수 있다.

 

#컴퓨터공학에서의_휴리스틱

컴퓨터 공학에서 발견법은 해결법이 정확히 해결되는지에 대한 문제를 무시하고 일반적으로 좋은 해결법이나 보다 간단한 해결법으로 풀고자 하는 문제 해결법이다. 예를 들어 상업적인 컴퓨터 바이러스 검색 소프트웨어들은 발견법으로 특정 속성이나 특징들을 찾아 바이러스나 나쁜 소프트웨어를 찾아낸다. 하지만 잠재적인 정확도 하락의 요인이 되기도 한다.

컴퓨터 공학에서는 해당 해결법이 정답이든 아니든 문제를 해결하는 간단한 해결법을 일컫는다.

 

 

영어원문의 위키를 참조하여 아래에서 부가적으로 설명을 덧붙여보자면

Heuristic (computer science)

https://en.wikipedia.org/wiki/Heuristic_(computer_science) 

수학적 최적화 및 컴퓨터 과학 휴리스틱을 위해 설계된 기술이다. 

어떠한 해결책을 찾기 위해 고전적인 방법을 사용했을 때 너무 느린 경우 더 빨리 또는 대략적인 해결책으로,

최적성, 완전성, 정확성, 정밀도보다는 속도를 위한 지름길이라고 생각된다.

 

휴리스틱의 목적

당면한 문제를 해결하기에 충분한 합리적인 시간 프레임에 솔루션을 생성하는 것이다. 

이 솔루션은 이 문제에 대한 모든 솔루션 중 최선이 아닐 수도 있고 단순히 정확한 솔루션에 근접할 수도 있습니다. 

-> 이 용어에 대해 설명할 때 가장 많이 사용되는 문구인 것 같네요

그러나 그것을 찾는 데 엄청나게 오랜 시간이 필요하지 않기 때문에 여전히 가치가 있습니다.

휴리스틱은 자체적으로 결과를 생성하거나 효율성을 개선하기 위해 최적화 알고리즘과 함께 사용할 수 있습니다(예: 좋은 시드 값을 생성하는 데 사용할 수 있음).

이론적 컴퓨터 과학에서 NP-경도 에 대한 결과는 발견적 방법을 실제 응용 프로그램에서 일상적으로 해결해야 하는 다양한 복잡한 최적화 문제에 대한 실행 가능한 유일한 옵션으로 만듭니다.

휴리스틱은 알려진 알고리즘 이 없는 상황에서 사용될 수 있으므로 인공 지능 및 사고의 컴퓨터 시뮬레이션의 전체 분야의 기초가 됩니다

 

Trade Off(균형)

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

• 최적성: 주어진 문제에 대해 여러 솔루션이 존재할 때 발견적 방법이 최상의 솔루션을 찾을 수 있음을 보장합니까? 실제로 최상의 솔루션을 찾는 것이 필요합니까?
• 완전성: 주어진 문제에 대해 여러 솔루션이 존재할 때 휴리스틱이 모든 솔루션을 찾을 수 있습니까? 실제로 모든 솔루션이 필요합니까? 많은 휴리스틱은 하나의 솔루션을 찾기 위한 것입니다.
• 정확성 및 정밀도: 발견적 방법 이 알려진 솔루션에 대한 신뢰구간 을 제공할 수 있습니까 ? 솔루션의 오차 막대가 부당하게 큰가요?
• 실행 시간 : 이것이 이러한 유형의 문제를 해결하기 위해 가장 잘 알려진 휴리스틱입니까? 일부 휴리스틱은 다른 것보다 빠르게 수렴합니다. 일부 휴리스틱은 기존 방법보다 약간만 빠르며, 이 경우 휴리스틱을 계산하는 '오버헤드'가 부정적인 영향을 미칠 수 있습니다.

어떤 경우에는 휴리스틱에 의해 발견된 솔루션이 충분히 좋은지 여부를 결정하기 어려울 수 있습니다. 이는 휴리스틱의 기본 이론이 매우 정교하지 않기 때문입니다.

 

 

 

다음 포스팅에서는 컴퓨터과학에서 사용하는 휴리스틱들에 대해 다뤄보도록 하겠습니다!

 

 

---