검색 공간에서 로컬 최적을 예측하는 방법이 있습니까?

Question

대부분의 실제 최적화 문제는 검색 공간에서 로컬 최적 조건을 갖지만 확실한지 알고 싶습니다.

로컬 최적 값이 없다는 것을 확실히 알면 간단한 언덕 오르기 알고리즘을 적용하여 GA와 같은 복잡한 검색 알고리즘 대신 문제를 해결할 수 있습니다. 이것은 약간의 기본 인 경우

죄송합니다

Answer 1

번호

대부분의 실제 최적화 문제는 NP-어려운 문제의 특정 인스턴스입니다. "NP-hard"는 최악의 경우 (NP)의 솔루션을 신속하게 확인할 수있는 모든 문제를 특별한 경우 ("-hard")로 인코딩 할 수 있음을 의미합니다.

각 단계가 최악의 경우 효율적으로 구현 될 수 있고 최적의 솔루션이 항상 반환되는 NP 어려운 문제에 대해서는 힐 클라이밍 휴리스틱을 아무도 모를 것이라고 생각합니다. (나는 이것에 대해 오해 할 수 있으며, 이것은 "NP-hard 문제에 대한 다항식 - 시간 알고리즘을 알지 못한다"보다 강한 진술이다.)

제쳐두고, 힐 - 클라이밍, 유전자 알고리즘, 시뮬레이트 된 어닐링 등에 너무 많이 기울이는 것은 권하지 않습니다. 어려운 문제의 큰 경우에 대해 세계적으로 최적의 솔루션을 찾는 데 관심이있는 경우이 방법을 사용하십시오. 간단한 문제가 많은 대규모 사례에 대해 세계적으로 최적의 솔루션을 찾는 데 관심이있는 경우에는 사용하지 않는 것이 좋습니다. 거의 항상 문제의 구조를 연구하고 개발하거나 적어도 발견 할 수있는 것을 사용할 수있는 혼합 정수 프로그래밍 또는 제약 프로그래밍과 같은 프레임 워크를 사용합니다.

Answer 2

확인할 수있는 몇 가지 사항이 있습니다. 만약 당신이 http://en.wikipedia.org/wiki/Convex_function을 가지고 있다는 것을 증명할 수 있다면, "볼록 함수의 국소 최소값 또한 전역 최소값입니다. 엄격하게 볼록 함수는 하나의 전역 최소값을가집니다".

x에서 로컬 최소값은 f (x)에서 로컬 최소값을 의미하는 것으로 나타낼 수 있습니다. 예를 들어 x의 좌표를 바꾸거나 x의 변수 이름을 바꿀 수 있습니다. 예를 들어, 여행 세일즈맨 문제에 대한 해결책은 순서대로 방문 할 점의 목록이며 그러한 솔루션에 대한 모든 순환 게재는 동일한 점수를 갖습니다. 이것은 최소한 커다란 힌트입니다. 최소한 최소화하려고하는 함수는 엄격하게 볼록하지 않으며 볼록하지 않을 수도 있습니다.

힐 - 클라이밍 솔버를 쓰는 경우, 물론 여러개의 랜덤 시작에서 실행할 수 있으며 항상 같은 장소로 수렴되는지 확인할 수 있습니다.