언덕 오르기

III. 힐 클라이밍

이전 섹션에서는 가능한 모든 솔루션을 살펴보고 그 중에서 가장 좋은 솔루션을 선택하여 최적화를 수행하는 방법을 배웠습니다. 우리는 대안의 수가 천문학적으로 커지면 이 단순한 '무차별적인' 접근 방식이 실행 불가능해질 수 있다고 언급했습니다. 더 나아가려면 더 스마트한 기술이 필요합니다. 그 중 하나가 힐 클라이밍(hill climb)이라고 불리는 것입니다.

기본 아이디어는 다음 비유로 설명할 수 있습니다. 여러분이 북유럽 숲을 거닐며 깨끗하고 야생의 자연을 즐기고 있다고 상상해 보세요. 하지만 친구에게 전화를 걸어 괜찮다고 알리고 싶을 수도 있고, 팔로워 수를 늘리기 위해 Instagram에서 아름다운 사진을 공유해야 한다고 느낄 수도 있습니다. 야생에서는 때때로 휴대폰 수신이 제한될 수 있으므로 수신 상태가 더 좋은 언덕 꼭대기를 찾으십시오. 나무들 사이에서는 근처 가장 높은 언덕이 어디인지 잘 알 수 없지만, 항상 지금 있는 곳에서 오르막길을 걸어볼 수 있으며, 계속 올라가면 좋은 자리를 찾을 수 있기를 바랍니다.

주요 용어

언덕 오르기 방법

위의 전략은 소위 언덕 오르기 방법에 해당합니다. 최적화 측면에서 현재 위치는 특정 솔루션이 되며 현재 고도(예: 해수면에서 미터 단위로 측정)는 최적화 기준의 값이 됩니다. 숲의 다른 방향은 현재 솔루션의 작은 변화에 해당합니다.

분명히, 가장 높은 언덕 꼭대기를 찾지 못할 수도 있고, 이 전략을 매우 엄격하게 따르고 자신이 올라가기만 하도록 허용한다면 실제 언덕이 아닌 작은 융기 부분에 직면하게 될 수도 있습니다. 최적화의 언덕 오르기 기술도 마찬가지입니다. 이는 절대적인 최상의 솔루션을 찾는다는 것을 보장하지 않으며 단지 작은 변화로는 개선할 수 없는 솔루션일 뿐입니다. 출발점이 모든 차이를 만듭니다. 가장 높은 봉우리 근처에서 시작할 수 있을 만큼 운이 좋다면 아마도 찾을 수 있을 것입니다.

아이디어를 더 잘 이해하기 위해 실제 언덕 등반과 관련된 간단한 시나리오를 고려하는 것부터 시작하겠습니다. 우리의 용감한 영웅 등산가 Venla Gustafsson은 또 다른 산을 정복하기로 결심했습니다. 불행하게도 그녀는 안경을 가져가는 것을 잊었고 팔이 닿는 곳까지만 볼 수 있습니다. 그래서 그녀는 위로 올라가서 정상에 도달하면 멈춥니다. 무슨 일이 일어나는지 봅시다.

Venla가 'x'로 표시된 인근 정상에 도달하는 것을 볼 수 있지만 이는 산의 가장 높은 정상이 아닙니다. Venla는 실망했지만 낙담하지는 않았습니다. 그녀는 위로 올라가기만 하면 가장 높은 정상에 도달할 수 있는 산의 한 지점으로 데려가 달라고 요청합니다.

슬라이더를 조정하여 Venla가 가장 높은 정상에 도달할 수 있는 지역을 표시하세요. Venla는 지역 내 무작위 위치에서 시작하여 왼쪽이나 오른쪽으로 가장 높은 봉우리까지 올라갈 것입니다.

참고: 정답을 선택하려면 슬라이더를 끌어서 크기를 조정해야 합니다.

언덕 오르기 방법의 한 가지 문제점은 우리가 좋은 솔루션이지만 최적이 아닌 솔루션에 쉽게 갇힐 수 있다는 것입니다. 이를 '지역적 최적'(참고: 최적의 복수형은 optima)이라고 하며, 절대적인 최선의 솔루션을 '전역적 최적'이라고 합니다. (때때로 똑같이 훌륭하고 최상의 솔루션이 여러 개 있을 수 있으며, 이 경우 글로벌 최적해라고도 말해야 합니다.)

주요 용어

탐욕스러운 솔루션

위쪽으로만 올라가는 단순한 언덕 오르기 솔루션은 종종 탐욕스러운 방법이라고 일컬어집니다. 이는 탐욕스럽게 단기 이익을 최적화하고 더 나은 장기적 이익으로 이어지더라도 일시적인 손실을 거부합니다.

이 문제를 해결하기 위해 많은 솔루션이 고안되었습니다. 그리고 우리는 실제로 많은 솔루션, 즉 수백 개의 솔루션을 의미합니다. 최적화 분야는 개미 군집 알고리즘, 유전자 알고리즘, 모의 어닐링, 금기 검색, 뻐꾸기 검색(농담이 아닙니다) 등 이국적인 알고리즘이 야생으로 돌아다니는 동물원과 같습니다.

주요 용어

모의 어닐링

가장 간단하고 효과적인 솔루션 중 하나는 모의 어닐링입니다. 이는 1983년 Scott Kirkpatrick, Daniel Gelatt 및 Mario P. Vecchi가 야금학에서 영감을 받아 발명했습니다. 금속 물체를 천천히 냉각시키면 결정 구조가 최소 에너지 구성을 찾을 수 있게 됩니다. 방법은 의외로 간단합니다. 솔루션을 개선하는 변경(오르막 이동)만 허용하는 대신 솔루션을 악화시키는 일부 변경(내리막 이동)도 일정 확률로 허용됩니다. 하향 전환을 허용할 가능성은 두 가지, 즉 하향 이동 정도와 소위 '온도'에 따라 달라집니다. 온도가 높을수록 내리막 이동이 허용될 확률이 높아집니다. 아이디어는 높은 온도에서 시작하여 변화가 어느 정도 무작위로 이루어지도록 하지만 점차적으로 온도를 낮추어 결국 온도가 내려갈 확률이 거의 없게 되는 것입니다.

모의 어닐링을 구현하는 데 필요하므로 먼저 Python에서 무작위성을 사용하는 방법을 연습해 보겠습니다. 프로그래밍 연습을 하고 있지 않다면 이 부분을 건너뛰어도 됩니다. 다음 프로그램은 'dog'이라는 단어를 출력합니다.
20
%
20% 확률.

"20% 확률" 대신 "0.2 확률"이라고 말할 수도 있습니다. 우리는 또한 "5개 중 1개" 또는 "10개 중 2개"와 같은 표현을 사용하는 경향이 있습니다. 이것들은 모두 같은 것을 의미합니다. "10개의 경우 중 2개"는 반드시 10번의 반복 중에 정확히 2개의 경우에 어떤 일이 발생한다는 의미는 아닙니다. 오히려 이는 단순히 장기적으로 빈도가 10분의 2가 될 것임을 의미하며, 이는 확률을 정의하는 한 가지 방법입니다.

우리는 확률을 사용하여 로컬 최적점을 탈출하도록 도와 최적화 기술을 향상시킬 것입니다. 다음 소규모 예를 고려하십시오. 목표는 울퉁불퉁한 표면 위 B로 표시된 가장 낮은 지점에 공을 떨어뜨리는 것입니다.

여기서는 낮은 것이 더 좋다는 점에 유의하세요. 따라서 우리는 목표가 올라가는 언덕 등반 예시와 정반대를 수행하고 있습니다.

공은 처음에 국소 최적점인 D점에 있습니다. 공이 튕겨 나가도록 표면을 흔들 수 있다고 가정해 보세요. 표면을 부드럽게 흔들면 공이 초기 위치 D에서 벗어날 가능성이 거의 없습니다. 표면에 매우 강한 충격을 한 번만 가하면 공은 무작위로 튕겨 나온 다음 전역 최적 B일 수도 있고 아닐 수도 있는 로컬 최적 위치로 언덕 아래로 굴러갑니다.

다음 중 공을 멈춘 후 가장 낮은 지점 B에 떨어뜨리는 데 성공할 가능성이 가장 높은 흔들림 전략은 무엇이라고 생각하시나요?

모의 어닐링의 아이디어는 최적화가 반복적으로 진행되어 점진적으로 더 나은(더 높은 점수) 솔루션을 향해 이동한다는 점에서 욕심 많은 검색과 유사합니다. 중요한 차이점은 모의 어닐링에서는 현재 솔루션보다 점수가 낮더라도 새로운 솔루션이 때때로 허용될 수 있다는 것입니다. 이는 수용 규칙에 무작위성을 도입하여 수행됩니다. 현재 솔루션보다 점수가 낮은 새로운 솔루션은 새 점수와 현재 점수의 차이에 따라 달라지는 확률로 승인됩니다.

참고!

모의 어닐링: 수학

-S
새로운
​

)│티)

참고: 수학에 대해 걱정하지 마세요. 컴퓨터가 실제 계산을 할 수 있으므로 올바른 숫자만 입력하면 됩니다.

모의 어닐링을 사용하면 현재 점수보다 점수가 즉시 더 높지 않더라도 이 새로운 점수를 수락할 가능성이 있습니다.

이 상황에서 우리가 새로운 점수를 선택할 확률은 얼마나 됩니까?

힌트: 검색창에 방정식을 입력하면 대부분의 웹 브라우저를 사용하여 이러한 공식을 계산할 수 있습니다.

이 모든 것이 실제로 어떻게 작동하는지 살펴보겠습니다.

다음은 가지고 놀 수 있는 작은 예시입니다. 여러 로컬 최적값(더 작은 피크)을 사용하여 무작위로 생성된 풍경을 보여줍니다. 가장 높은 봉우리는 보라색 깃발로 표시됩니다. 현재 솔루션은 흰색 플래그로 표시됩니다. 가장 높은 피크의 높이 또는 점수와 현재 솔루션도 숫자로 표시됩니다.

하단의 "시뮬레이션 어닐링 시작" 버튼을 클릭하면 현재 솔루션이 움직이기 시작합니다. 각 단계에서 새로 제안된 솔루션은 현재 솔루션 근처에서 무작위로 선택되며 모의 어닐링 규칙에 따라 승인되거나 거부됩니다. 현재 솔루션을 언덕 아래로 가져가는 이동이 허용되는 빈도를 결정하는 온도는 지도 바로 아래에 있는 슬라이더를 사용하여 조정할 수 있습니다.

예시을 사용해 보세요. 온도를 매우 높게 설정하면 검색은 본질적으로 더 높거나 낮을 목적 없이 이리저리 돌아다니는 무작위 보행이 되어야 합니다. 온도를 0으로 설정하면 검색이 근처의 로컬 최적값을 향해 곧바로 올라갑니다. 상당한 행운이 따르는 경우를 제외하고는 어느 쪽도 여러분을 최고봉으로 데려갈 수 없는 것 같습니다. 원한다면 어떤 전략이 최고점에 도달하는 데 도움이 되는지 시도해 볼 수 있습니다. 낮은 온도에서 시작하여 점차 온도를 높여야 할까요, 아니면 그 반대일까요?

온도가 어떤 역할을 하는지 이해하려면 여기에서 잠시 멈춰서 다음 질문에 대해 생각하고 답해 보는 것이 좋습니다.

연습문제

연습 3. 가장 높은 정상에 도달하기

아래 지형에서 한 지점을 선택한 뒤 더 높은 방향으로만 이동한다고 생각해 보세요. 지역 최고점에 멈추지 않고 전체에서 가장 높은 봉우리에 도달하려면 시작 구간에 어떤 조건이 필요할까요?

01최고봉에 도달할 가능성이 가장 높은 시작 구간은 무엇인가요?

낮은 골짜기 반대편의 작은 봉우리 주변최고봉과 같은 경사면에 있고 중간에 더 낮아지는 지점이 없는 구간이미 작은 봉우리의 꼭대기에 도달한 지점경사의 방향을 알 수 없는 임의의 모든 지점

답안 확인하기