파이썬에서 인공지능을 위한 Hill Climbing 알고리즘 구현

Python

힐 클라이밍 알고리즘은 인공 지능과 컴퓨터 과학에서 가장 초기이자 가장 간단한 최적화 알고리즘 중 하나입니다. 이는 해결책을 점진적으로 향상시키는 방법으로 해결책을 찾는 지역 탐색 알고리즘 카테고리에 속합니다.

이 알고리즘의 이름은 유용한 비유에서 나온 것입니다: 눈가림을 한 하이커가 언덕의 정상에 도달하려고 노력한다고 상상해보십시오. 전체 풍경을 볼 수 없기 때문에 주변 지형만 느낄 수 있습니다. 각 단계에서 그들은 올라가는 방향으로 이동합니다. 이것은 알고리즘이 작동하는 방식을 반영합니다 – 주변의 해결책을 평가하고 반복적으로 더 나은 해결책으로 이동하여 최적의 해결책(언덕의 정상)을 찾으려고 시도합니다.

이 기사에서는 힐 클라이밍 알고리즘을 깊이 있게 탐구하고, 그 변형들 및 파이썬에서 구현하는 방법을 살펴볼 것입니다. AI에 처음이라면, 반드시 우리의AI 기초 기술 트랙을 확인하여 기본을 익히세요.

AI에서 힐 클라이밍 알고리즘이란 무엇인가?

힐 클라이밍은 컴퓨터가 가장 좋은 답을 찾아 문제를 해결하는 간단한 방법으로, 마치 등산객이 산 정상에 도달하려는 것과 같습니다. 인공지능(AI)에서 우리는 종종 많은 선택지 중에서 최적의 해법을 찾아야 합니다. 이를 최적화라고 합니다.

“핫 앤 콜드” 게임을 할 때 최고점을 찾으려고 노력하는 것을 상상해보세요. 이 게임에서는 움직이면서 “더 따뜻해지고”(좋아짐) 또는 “더 차가워지고”(나빠짐) 하는지만 확인할 수 있습니다. Hill climbing도 마찬가지입니다 – 주변 솔루션을 살펴보고 더 나은 솔루션 쪽으로 움직입니다.

간단한 단계로 설명하면 다음과 같습니다:

임의의 가능한 솔루션으로 시작합니다
주변 솔루션을 살펴봅니다
주변 솔루션이 더 나은 경우, 해당 솔루션으로 이동합니다
더 나은 솔루션이 발견되지 않을 때까지 단계 2-3을 반복합니다

예를 들어, 로봇에 걷는 방법을 가르치려고 한다면, Hill Climbing은 다음과 같이 작동할 수 있습니다:

랜덤한 다리 움직임으로 시작합니다
약간 다른 움직임을 시도합니다
로봇이 더 잘 걷도록 도와주는 움직임을 유지합니다
최적의 걷기 패턴을 찾을 때까지 반복합니다

힐 클라이밍은 항상 AI에서 가장 고급 방법은 아니지만, 컴퓨터가 문제를 스스로 해결하는 방법을 이해하는 데 도움이 되는 중요한 기본 요소입니다. 이는 미니맥스 알고리즘과 유사합니다.

힐 클라이밍 알고리즘의 유형

힐 클라이밍 알고리즘은 각기 다른 솔루션 탐색 방식으로 세 가지 주요 유형이 있습니다:

1. 간단한 힐 클라이밍

간단한 힐 클라이밍은 발견한 첫 번째 좋은 단계를 밟는 것과 같습니다. 이 버전에서는:

알고리즘은 인근 솔루션을 하나씩 살펴봅니다
더 나은 솔루션을 찾으면 즉시 채택합니다
다른 옵션을 확인하지 않습니다
이는 빠르지만 조금 더 멀리에 있는 더 나은 솔루션을 놓칠 수 있습니다

2. 가파른 상승 힐 클라이밍

이 버전은 간단한 힐 클라이밍보다 철저합니다:

움직이기 전에 모든 인근 솔루션을 살펴봅니다
그것이 찾은 모든 것 중에서 가장 좋은 옵션을 선택합니다
더 많은 시간이 걸리지만 일반적으로 더 나은 해결책을 찾습니다
한 발 내딛기 전에 모든 경로를 주의 깊게 확인하는 것과 같습니다

3. 확률적 힐 클라이밍

이 유형은 탐색을 더 흥미롭게 만들기 위해 약간의 무작위성을 추가합니다:

항상 가장 좋은 해결책을 선택하는 대신, 더 나은 옵션 중에서 무작위로 선택합니다
더 나은 해결책이 선택될 확률이 더 높습니다
이러한 무작위성은 나쁜 상황에 갇히는 것을 피하는 데 도움이 됩니다
가끔은 다른 길을 택해서 어디로 이끌리는지 보는 것과 같습니다

각 유형은 각각의 강점을 가지고 있으며 다른 종류의 문제에 대해 더 잘 작동합니다. 단순한 언덕 오르기는 빠르지만 기본적이며, 가파른 상승은 철저하지만 느리며, 확률적인 방법은 갇히지 않도록 도와줄 무작위성을 더합니다.

언덕 오르기 알고리즘 작동 방식

언덕 오르기 알고리즘은 최상의 해결책을 찾을 때까지 단계적으로 작은 개선을 수행함으로써 작동합니다. 작동 방식을 주요 부분으로 나눠 살펴봅시다.

1. 시작하기

모든 언덕 등반 알고리즘은 시작점이 필요합니다. 이를 산에서 하이킹을 시작할 곳을 선택하는 것과 같다고 생각해보세요. 무작위로 시작할 수도 있고, 문제에 대해 알고 있는 것을 활용하여 좋은 시작점을 선택할 수도 있습니다.

시작하는 위치는 정말 중요합니다 – 좋은 장소를 선택하면 빠르게 최적해를 찾을 수 있습니다. 나쁜 곳을 선택하면 산정상이 아닌 작은 언덕에 갇힐 수도 있습니다.

예를 들어, 훈련 중 신경망에서 시작점은 뉴런 간 연결의 초기 가중치를 선택하는 것을 의미합니다. 이러한 가중치를 무작위로 초기화할 수 있으며, 이것은 산의 임의의 지점에서 하이킹을 시작하는 것과 같습니다. 또는 네트워크 구조를 기반으로 지식 있는 초기 가중치를 선택하는 Xavier 초기화와 같은 기술을 사용할 수 있습니다.

좋은 초기화는 네트워크가 더 빨리 학습하고 더 나은 솔루션을 찾도록 돕고, 나쁜 초기화는 네트워크가 정확도가 개선되지 않는 낮은 정확도로 갇혀 있게 만들 수 있습니다.

2. 주변 솔루션 살펴보기

알고리즘이 검색을 시작하면 현재 위치와 유사한 이웃 솔루션을 평가합니다. 작은 단계로 주변을 탐험하는 것과 같습니다. 예를 들어, 도시 간 배송 경로를 최적화하려고 하며 현재 경로가 [A -> B -> C -> D]인 경우, 알고리즘은 [A -> B -> D -> C] 또는 [A -> C -> B -> D]와 같은 유사한 경로를 검토하여 총 이동 거리를 줄일 수 있는지 확인합니다. 경로에 대한 각 작은 변경은 현재 것보다 더 나은 “이웃” 솔루션을 나타낼 수 있습니다.

이러한 비교를 수행하기 위해 알고리즘은 “목적 함수”에 의존합니다 – 가능한 각 솔루션에 점수나 값을 할당하는 수학 공식입니다.

이 기능은 나침반처럼 작용하여 알고리즘이 “언덕” 방향으로 더 나은 해결책을 제시하고 “내리막길” 방향으로 나쁜 해결책을 이해하도록 돕습니다. 배송 경로의 경우, 목적 함수는 총 이동 거리를 계산할 것입니다 – 더 짧은 총 이동 거리는 더 나은 해결책을 의미합니다.

따라서 X 경로가 100마일을 이동하고 Z 경로가 90마일을 이동한다면, B 경로가 더 나은 (낮은) 점수를 가질 것입니다. 알고리즘은 이후 B 경로와 유사한 해결책 방향으로 이동해야 함을 알게 됩니다. 목적 함수는 본질적으로 경로 최적화의 복잡한 문제를 비교하고 최소화할 수 있는 간단한 숫자로 변환합니다.

3. 다음 단계 선택하기

주변 해결책을 살펴본 후, 알고리즘은 다음으로 어디로 이동해야 하는지 결정해야 합니다. 알고리즘은 주변 해결책의 점수를 현재 해결책과 비교합니다. 더 나은 해결책을 찾으면 해당 위치로 이동합니다. 언덕 오르기의 다양한 버전은 이 선택을 다양한 방식으로 수행합니다:

간단한 버전은 찾은 첫 번째 더 나은 해결책을 채택합니다
신중한 버전은 최고의 해결책을 선택하기 전에 모든 인근 해결책을 확인합니다
임의의 버전은 가끔 최상의 해결책이 아닌 해결책을 선택하기도 합니다. 이는 멈추는 것을 피하는 데 도움이 될 수 있습니다

4. 멈추는 시점 파악

알고리즘은 더 나은 해결책을 찾는 것을 멈춰야 합니다. 보통, 다음 중 하나가 발생하면 멈춥니다:

인근에서 더 나은 해결책을 찾을 수 없을 때
너무 오랫동안 실행되었을 때
충분히 좋은 해결책을 찾았습니다.

알고리즘은 일반적으로 일정한 패턴을 따릅니다. 먼저 가파른 언덕을 큰 걸음으로 빨리 올라가는 것처럼 더 나은 해결책을 찾습니다. 그런 다음 꼭대기에 가까워질수록 작은 개선을 하며 느리게 움직이다가 결국 멈춥니다.

가끔은 경로가 부드럽고 직선적이지만 다른 때에는 업다운이 많은 꼬리표가 있는 경우도 있습니다.

인공 지능에서 힐 클라이밍의 장단점

힐 클라이밍을 사용할 때 유용한 점과 마주치는 문제점에 대해 살펴보겠습니다.

장점

힐 클라이밍은 이해하고 프로그래밍하기 가장 간단한 최적화 알고리즘 중 하나입니다. 이는 기본 규칙을 따르는 것과 같습니다: “더 나아졌으면 그쪽으로 이동하세요.” 이는 많은 문제를 해결하는데 좋은 시작점이 됩니다.

문제가 간단할 때 힐 클라이밍은 빠르게 좋은 해결책을 찾을 수 있습니다. 모든 가능한 해결책을 탐색하는 데 시간을 낭비하지 않고 그저 위로 올라가는 경로를 따릅니다.

이 알고리즘은 많은 컴퓨터 메모리나 처리 능력이 필요하지 않습니다. 단지 현재 위치를 기억하고 근처 해결책을 살펴보기만 하면 되므로 많은 실세계 문제에 실용적입니다.

제한사항

물론, 다른 모든 방법과 마찬가지로 일부 잠재적인 단점이 있습니다:

1. 작은 언덕에 갇히는 것

힐 클라이밍의 가장 큰 문제는 “지역 최댓값”에 갇힐 수 있다는 것입니다. 이는 실제로 근처에 산이 있는데 작은 언덕에 갇힌 것과 같습니다. 알고리즘이 작은 언덕 꼭대기에 도달하면 주변이 낮아져 더 나은 해결책이 다른 곳에 있을지라도 멈추게 됩니다.

2. 평지 문제

가끔 알고리즘이 주변 해결책이 모두 동등하게 좋은 평지(plateau)에 있다는 것을 발견합니다. 평평한 축구장을 걸어가면서 가장 높은 지점을 찾으려는 것을 상상해보세요. 어느 쪽으로 가야할지 알기 어렵습니다!

3. 마루 문제

좁은 산마루 위를 걷려고 하는 것처럼 상상해보세요. 알고리즘이 정상으로 나아가는 대신 산마루를 오가며 시간을 낭비할 수 있습니다. 이는 측면으로 한 걸음씩 나아가는 것이 목표로 한 방향으로 진행하는 것만큼 좋아 보이기 때문에 발생합니다.

4. 시작점이 매우 중요합니다

시작하는 곳에 따라 알고리즘이 얼마나 잘 작동하는지에 큰 차이가 있을 수 있습니다. 그것은 하이킹을 시작하는 것과 같습니다 – 잘못된 곳에서 시작하면 결코 가장 높은 봉우리를 찾을 수 없을지도 모릅니다.

이러한 제약은 힐 클라이밍이 나쁜 선택이라는 것을 의미하는 것은 아니며, 그저 언제, 어떻게 사용하는지에 대해 주의해야 한다는 것을 의미합니다. 때로는 이러한 문제를 극복하기 위해 다른 기술과 결합할 수 있으며, 다음 섹션에서 논의할 것입니다.

제한을 극복하기 위한 전략

힐 클라이밍을 사용할 때, 우리는 이전에 논의한 문제를 해결하기 위해 몇 가지 똑똑한 전략을 사용할 수 있습니다. 힐 클라이밍이 더 잘 작동하도록 도와주는 두 가지 주요 접근 방식을 살펴보겠습니다.

랜덤 재시작 힐 클라이밍

작은 언덕에 갇히지 않으려면 다양한 시작점에서 오르는 방법 중 가장 좋은 방법 중 하나는 무작위 재시작 힐 클라이밍을 시도하는 것입니다. 이 접근 방식은 이름 그대로 작동하며, 갇히면 새로운 곳에서 다시 시작합니다.

안개 낀 산맥에서 가장 높은 산을 찾으려고 시도해보는 것을 상상해보세요. 만나는 첫 번째 작은 언덕을 오르다가 정상에 도달하면 주변에 훨씬 더 높은 산을 놓칠 수도 있습니다. 그러나 다른 위치로 순간이동하여 다시 오르기 시작한다면 결국 가장 높은 봉우리를 찾을 가능성이 훨씬 높아질 것입니다.

작동 방식: 먼저 일반적인 언덕 오르기 알고리즘을 실행하여 멈출 때까지 진행합니다. 포기하지 않고 찾은 최적의 해결책을 저장한 다음 임의의 새로운 지점에서 다시 시작합니다. 이를 여러 번 시도하다가 마지막에 여러 시도 중 최고의 해결책을 선택합니다.

랜덤 재시작의 장점은 간단하지만 효과적이라는 것입니다. 각 재시작은 최고봉을 찾기 위한 새로운 기회를 제공합니다. 보통의 언덕 오르기보다 더 많은 시간이 소요되지만, 최적의 해결책을 찾을 가능성이 훨씬 높습니다.

모의 담금질

기술적으로는 산 오르기가 아니지만, 모의 담금질은 산 오르기의 많은 문제를 해결하는 데 도움이 되는 간단한 변형입니다. 이는 금속 가공에서 금속이 식고 단단해지는 방식에서 영감을 받았습니다. 금속이 천천히 식을 때, 원자들이 더 나은 위치를 찾아 금속이 더 강해집니다.

이 방법에서 알고리즘은 때때로 목적지로 더 나쁜 솔루션을 의도적으로 수용합니다, 특히 처음에는. 시간이 흐를수록, 수용하는 솔루션에 대해 더 까다로워집니다. 이는 고르지 않은 표면을 튕겨 내려가는 공과 같습니다 – 처음에는 언덕을 넘어 올라가기에 충분한 에너지가 있지만, 에너지를 잃으면서 좋은 위치로 안착합니다.

작동 방식입니다.: 시작할 때, 알고리즘은 현재 솔루션보다 나쁜 솔루션을 상당히 높은 확률로 수락할 수 있습니다. 이 확률은 새로운 솔루션이 얼마나 나쁜지와 알고리즘이 실행된 시간에 따라 달라집니다. 시간이 지남에 따라 알고리즘은 나쁜 솔루션을 받아들일 가능성이 줄어들어 결국 일반적인 Hill Climbing처럼 더 작동합니다.

모의 담금질의 실제 장점은 작은 언덕과 평평한 지역에서 특히 초기에 탈출할 수 있다는 것입니다. 때로는 나쁜 솔루션을 수락함으로써 다음을 할 수 있습니다:

지역 최대값(작은 언덕)을 벗어납니다.
고원(평평한 지역)을 횡단합니다.
마루(좁은 봉우리)를 탐험합니다
솔루션 공간을 더 탐구합니다

예를 들어, 공간을 극대화하기 위해 방 안의 가구를 배치하려고 합니다. 의자를 옮기면 일시적으로 방이 더 혼잡해질 수 있지만, 그렇게 하면 다른 조각들을 훨씬 더 좋은 위치로 옮길 수 있을지도 모릅니다. 모의 담금질은 이러한 일시적으로 나빠진 배열을 시도할 것이며, 특히 프로세스 초반에는 가장 좋은 전체 배열을 찾기 위해 이를 시도할 것입니다.

이러한 전략은 때로 문제를 해결하는 가장 좋은 방법이 항상 명백한 한 걸음을 따르는 것이 아님을 보여줍니다. 무작위성과 통제된 혼돈의 요소를 추가함으로써, 우리는 종종 직진하는 대신 더 나은 해결책을 찾을 수 있습니다.

파이썬에서 간단한 ‘언덕 오르기’ 알고리즘 구현

이제 우리는 랜덤 재시작과 모의 담금질과 같은 전략으로 언덕 오르기를 개선하는 방법을 이해했으니, 이를 실제 금융 문제에 적용해 보겠습니다:포트폴리오 최적화.

포트폴리오 최적화는 투자자가 자신의 돈을 다양한 투자에 분산하는 방법을 결정하는 데 도움을 줍니다. 투자자가 포트폴리오를 구성할 때, 가능한 높은 수익을 올리면서 리스크를 낮추고 싶어합니다. 이 균형을 찾는 것은 까다롭습니다 – 다양한 재료로 완벽한 레시피를 찾는 것과 비슷합니다.

1952년, 해리 마코위츠(Harry Markowitz)라는 경제학자가 이 문제를 해결하는 똑똑한 방법을 발견했습니다. 그는 투자자가 함께 움직이지 않는 투자를 섞음으로써 리스크를 줄일 수 있다는 것을 보여주었습니다. 이를 다양화라고 합니다 – 모든 달걀을 하나의 바구니에 넣지 않는 것과 유사합니다.

포트폴리오를 구축할 때, 세 가지 주요 사항을 파악해야합니다:

기대 수익률 (예상 수익)
투자의 위험 정도 (포트폴리오 리스크)
잠재 수익이 위험에 어떻게 대비하는지 (위험 조정 수익)

힐 클라이밍은 이 문제에 대해 잘 작동합니다. 왜냐하면 자본을 어떻게 분할하는지에 대한 작은 변경은 일반적으로 포트폴리오의 성과에 대한 작은 변경으로 이어집니다. 각 점이 자본을 투자하는 다른 방법을 나타내는 부드러운 언덕을 상상해보십시오. 더 높은 지점은 더 나은 투자 선택을 보여줍니다.

힐 클라이밍을 사용하여 좋은 포트폴리오를 찾으려면 다음을 수행합니다:

투자의 무작위 혼합으로 시작합니다
약간 다른 혼합을 시도하여 더 나은지 확인합니다
더 나은 옵션을 찾을 수 없을 때까지 작은 개선을 계속합니다
찾은 최상의 혼합을 사용합니다

이러한 방식으로 힐 클라이밍을 사용하면 투자자들이 수백만 가지 가능한 조합 중에서 더 나은 포트폴리오를 찾을 수 있습니다. 이는 리스크와 수익을 잘 균형잡힌 투자 혼합을 찾기 위해 다양한 투자 혼합을 신속히 테스트할 수 있는 스마트 어시스턴트가 있는 것과 같습니다.

먼저 목표 함수를 정의해 봅시다. 이 함수는 예상 수익과 위험을 균형있게 고려한 포트폴리오 성과 측정 지표입니다. 포트폴리오 가중치 목록을 입력으로 받아들이고 높은 점수일수록 더 좋은 포트폴리오를 나타냅니다.

def objective_function(state):
   """
   Portfolio optimization objective function that maximizes expected returns while minimizing risk.
   The state represents portfolio weights for different assets.

   Args:
       state (list): List of portfolio weights for different assets (should sum to 1)

   Returns:
       float: Portfolio score combining returns and risk
   """
   # 자산의 예상 연간 수익률 (예시 값)
   expected_returns = [0.1, 0.12, 0.18, 0.1, 0.15]  # 8%, 12% 등

   # 각 자산의 리스크(변동성)
   volatilities = [0.1, 0.2, 0.3, 0.2, 0.2]  # 10%, 20% 등

   # 입력 길이가 예상 수익률/변동성과 일치하는지 확인
   if len(state) != len(expected_returns):
       return float("-inf")  # 잘못된 상태에 대해 최악의 점수 반환

   # 예상 포트폴리오 수익률 계산
   portfolio_return = sum(w * r for w, r in zip(state, expected_returns))

   # 포트폴리오 리스크 계산 (간소화, 공분산 행렬 미사용)
   portfolio_risk = sum(w * v for w, v in zip(state, volatilities))

   # 가중치가 1의 합이 되지 않으면 패널티 부여 (유효하지 않은 포트폴리오)
   weight_sum_penalty = abs(sum(state) - 1) * 100

   # 음수 가중치에 대해 패널티 부여 (공매도 금지)
   negative_weight_penalty = sum(abs(min(0, w)) for w in state) * 100

   # 리스크 회피 계수 2를 사용하여 수익과 리스크 결합
   # 높은 점수가 더 좋음: 수익 극대화, 리스크와 패널티 최소화
   score = (
       portfolio_return
       - 2 * portfolio_risk
       - weight_sum_penalty
       - negative_weight_penalty
   )

   return score

위의 objective_function은 특정 투자 포트폴리오가 얼마나 좋은지를 평가하는 데 도움을 줍니다. 작동 방식을 살펴보겠습니다:

먼저, 다양한 자산(주식 또는 채권과 같은)에 투자하고 싶은 우리의 자금 비율을 나타내는 숫자 목록을 입력합니다. 예를 들어, 다섯 개의 자산이 있다면 각각에 20%를 투자할 수 있습니다.

함수는 두 가지 중요한 정보를 사용합니다:

예상 수익: 각 자산으로부터 얼마나 벌어들일 것으로 기대되는 돈(예를 들어 연간 8% 또는 12%)
변동성: 각 자산의 위험 정도를 나타내는 지표 — 숫자가 높을수록 자산 가치의 변동이 예측하기 어려워집니다(암호화폐와 같은)

함수는 그런 다음:

각 자산의 예상 수익을 해당 자산에 투자한 양으로 곱해 우리 포트폴리오의 총 예상 수익을 계산합니다
각 자산의 변동성을 살펴 전체 리스크를 파악합니다
투자 비율이 100%가 되는지 확인합니다(되어야 합니다!)
소유하지 않은 자산을 판매하려고 하는지 확인합니다(음수 비율은 안 됩니다)

마지막으로, 이 모든 정보를 하나의 점수로 결합합니다. 높은 점수는 더 좋은 포트폴리오를 의미합니다. 점수는 높은 수익과 함께 증가하지만 높은 리스크와 함께 감소합니다. 또한 투자 비율이 100%가 되지 않거나 음수 비율을 사용하려고 하면 점수가 크게 나빠집니다.

이 함수는 다음에 설명할 힐 클라이밍 알고리즘을 사용하여 최상의 투자 조합을 찾는 데 도움을 줄 것입니다. 목표 함수를 완전히 이해하지 못하더라도 걱정하지 마세요 — 핵심 아이디어는 특정 투자 조합이 얼마나 좋은지를 알려주며, 이를 통해 점점 더 나은 조합을 찾는 데 사용할 것입니다.

이제 가중치에 작은 조정을 가하여 이웃 포트폴리오 상태를 생성하는 새로운 함수를 정의해 보겠습니다.

def get_neighbors(state):
   """
   Generates neighboring states by making small adjustments to portfolio weights

   Args:
       state (list): Current portfolio weights

   Returns:
       list: List of neighboring portfolio weight configurations
   """
   neighbors = []
   step_size = 0.01  # 가중치에 대한 작은 조정 (1%)

   for i in range(len(state)):
       for j in range(len(state)):
           if i != j:
               # 자산 i에서 자산 j로 가중치 전이
               neighbor = state.copy()
               if neighbor[i] >= step_size:  # 충분한 가중치가 있을 경우에만 전이
                   neighbor[i] -= step_size
                   neighbor[j] += step_size
                   neighbors.append(neighbor)

   return neighbors

get_neighbors 함수는 현재 포트폴리오 가중치에 작은 조정을 가하여 유사한 포트폴리오 할당을 생성하는 힐 클라이밍 알고리즘의 중요한 부분입니다. 작동 방식은 다음과 같습니다:

포트폴리오의 각 자산 쌍에 대해 한 자산에서 다른 자산으로 소량(1%)을 전이하여 새로운 포트폴리오 할당을 생성합니다. 예를 들어, 다섯 개의 자산이 있을 경우 다음을 시도합니다:

자산 1에서 자산 2로 1% 이동
자산 1에서 자산 3로 1% 이동
자산 1에서 자산 4로 1% 이동
자산 1에서 자산 5로 1% 이동
자산 2에서 자산 1로 1% 이동 그리고 가능한 모든 쌍에 대해 계속 진행합니다.

이 함수에는 소스 자산에 충분한 할당(최소 1%)이 있는 경우에만 가중치를 전이하도록 하는 안전 검사가 포함되어 있습니다. 이는 실제 포트폴리오에서 의미가 없는 음수 가중치를 방지합니다.

각각의 작은 조정은 “이웃”을 만들어냅니다 – 현재의 것과 매우 유사하지만 약간 다른 포트폴리오 할당입니다. 그런 다음, Hill Climbing 알고리즘은 이러한 이웃을 평가하여 더 나은 포트폴리오 할당을 찾습니다.

1%의 단계 크기는 서로 다른 할당을 탐색하고 제어된 변경을 만드는 좋은 균형을 제공합니다. 더 큰 단계 크기는 최적의 해를 놓칠 수 있고, 더 작은 것은 검색을 너무 느리게 만들 수 있습니다.

이제 간단한 Hill Climbing 알고리즘을 구현해 봅시다:

def simple_hill_climbing(initial_state, max_iterations=1000):
   """
   Implements Simple Hill Climbing algorithm
  
   Args:
       initial_state (list): Starting point for the algorithm
       max_iterations (int): Maximum number of iterations to prevent infinite loops
  
   Returns:
       tuple: (best_state, best_value) found by the algorithm
   """
   current_state = initial_state
   current_value = objective_function(current_state)
  
   for _ in range(max_iterations):
       # 이웃 상태 가져오기
       neighbors = get_neighbors(current_state)
      
       # 더 나은 이웃을 찾았는지 확인하는 플래그
       found_better = False
      
       # 하나씩 이웃 확인하기 (단순 Hill Climbing)
       for neighbor in neighbors:
           neighbor_value = objective_function(neighbor)
          
           # 더 나은 이웃을 찾으면 즉시 이동
           if neighbor_value > current_value:
               current_state = neighbor
               current_value = neighbor_value
               found_better = True
               break
      
       # 더 나은 이웃을 찾지 못했다면, 우리는 정점에 도달했습니다
       if not found_better:
           break
  
   return current_state, current_value

이 함수는 초기 상태에서 시작하여 지역 최대치나 최대 반복 횟수에 도달할 때까지 더 나은 이웃 상태로 반복적으로 이동합니다.

이 함수는 두 개의 매개변수를 사용합니다:

initial_state: 최적화를 위한 시작점으로, 값 목록으로 표시됩니다
max_iterations: 무한 루프를 방지하기 위한 안전 매개 변수로, 기본적으로 1000번 반복됩니다

알고리즘은 다음과 같이 작동합니다:

initial_state에서 시작하여 목적 함수 값을 계산합니다
각 반복마다 다음을 수행합니다:

get_neighbors()를 사용하여 이웃 상태를 생성합니다
각 이웃을 한 번에 평가합니다
더 나은 이웃(더 높은 목적값)을 찾으면 즉시 해당 상태로 이동합니다
더 나은 이웃을 찾을 수 없을 경우, 국부 최댓값에 도달하고 종료됩니다

함수는 다음을 포함하는 튜플을 반환합니다:

찾은 최상의 상태(값 목록)
해당 상태의 목적 함수 값

이 “간단한” 힐 클라이밍 변형은 탐욕적입니다 – 발견한 첫 번째 더 나은 이웃으로 이동하여 최상의 이웃을 찾기 위해 모든 이웃을 평가하는 대신합니다. 이것은 빠르게 만들지만, 보다 철저히 접근함으로써 찾을 수 있는 더 나은 해결책을 놓칠 수 있습니다

이 알고리즘은 국부 최적점을 찾는 데 유용하지만 이러한 국부 최댓값에 갇힐 수 있으며, 전역 최댓값을 놓칠 수 있습니다. 이러한 제한 사항에도 불구하고, 이 알고리즘은 간단함과 효율성으로 널리 사용되고 있습니다.

샘플 포트폴리오에서 테스트해 봅시다:

# 예제 사용법
initial_state = [0.15, 0.25, 0.1, 0.3, 0.2]
best_state, best_value = simple_hill_climbing(initial_state)
print(f"Initial State: {initial_state}")
print(f"Best State Found: {best_state}")
print(f"Best Value: {best_value}")

[OUT]:

Initial State: [0.15, 0.25, 0.1, 0.3, 0.2]
Best State Found: [0.9700000000000006, 0.009999999999999913, 1.0408340855860843e-17, 0.009999999999999858, 0.009999999999999969]
Best Value: -0.1053000000000444

출력 결과는 포트폴리오를 최적화할 때 우리의 언덕 등반 알고리즘 결과를 보여줍니다. 다섯 자산에 대한 무작위 가중치에서 시작하여, 목적 함수 값을 향상시키는 새로운 가중치 집합을 찾았습니다. 이 솔루션은 초기 포트폴리오를 개선했지만, 알고리즘이 찾은 첫 번째 peak에서 멈추기 때문에 국부 최적점일 수 있습니다.

인공지능에서의 언덕 등반 애플리케이션

언덕 등반 알고리즘은 인공지능 및 기계 학습의 여러 영역에 실용적으로 적용됩니다. 몇 가지 주요 응용 사례를 살펴보겠습니다:

1. 기계 학습 모델 최적화

힐 클라이밍은 기계 학습 모델을 조정하는 데 여러 가지 방법으로 도움을 줍니다:

특성 선택: 모델을 위한 최적의 특성 부분 집합 찾기
하이퍼파라미터 튜닝: 학습 속도나 트리 깊이와 같은 모델 매개변수 최적화
신경망 훈련: 네트워크 가중치 및 구조 미세 조정
모델 압축: 성능 유지하면서 모델 크기 축소

예를 들어, 예측 모델을 위한 특성 선택 시, Hill Climbing은 모든 특성을 시작으로 하여 모델 성능에 따라 반복적으로 제거하거나 추가합니다. 이를 통해 모델 정확도와 복잡성을 균형있게 유지하는 최적 특성 집합을 찾을 수 있습니다.

2. 로봇공학과 경로 계획

로봇공학에서, 힐 클라이밍은 다음과 같은 부분에 도움을 줍니다:

움직임 계획: 물리 공간을 효율적으로 통과하는 경로 찾기
조인트 각도 최적화: 로봇 팔의 최적 위치 결정
센서 배치: 최대 범위를 위한 센서 위치 최적화
배터리 관리: 전력 소비 패턴 최적화

로봇 청소기는 효율적인 청소 경로를 찾기 위해 힐 클라이밍을 사용할 수 있으며, 방 범위와 배터리 수명에 따라 경로를 계속 조정합니다.

3. 자연어 처리

NLP 응용 프로그램은 다음과 같습니다:

텍스트 요약: 요약 콘텐츠 선택 최적화
단어 임베딩: 단어 벡터 표현 미세 조정
문서 클러스터링: 문서를 최적 그룹으로 구성
검색 엔진 최적화: 검색 결과 순위 향상

예를 들어, 텍스트 요약에서 Hill Climbing은 정보 콘텐츠를 최대화하고 중복을 최소화하는 문장을 선택하는 데 도움이 될 수 있습니다.

4. 컴퓨터 비전 이미지 처리 및 컴퓨터 비전에서

이미지 분할: 객체 간의 최적 경계 찾기
카메라 보정: 더 나은 이미지 품질을 위한 카메라 매개변수 조정
물체 감지: 경계 상자 위치 최적화
특징 일치: 이미지 간에 해당 점을 찾는 것

A 얼굴 인식 시스템은 전처리 중 얼굴 특징의 정렬을 최적화하기 위해 힐 클라이밍을 사용할 수 있습니다.

5. 게임 AI 및 의사결정

힐 클라이밍은 다음과 같은 부분에서 도움이 됩니다:

게임 전략 최적화: 보드 게임에서 승리하는 수를 찾기
자원 할당: 전략 게임에서 자원 분배 최적화
NPC 행동: 비플레이어 캐릭터 의사 결정 개선
레벨 생성: 균형 잡힌 흥미로운 게임 레벨 생성

체스 엔진은 종종 게임 플레이 중에 움직임 순서를 평가하고 최적화하기 위해 힐 클라이밍 변형을 사용합니다.

6. 비즈니스 및 운영

실용적인 비즈니스 응용 프로그램은 다음과 같습니다:

공급망 최적화: 효율적인 배송 경로 찾기
자원 일정 관리: 직원 일정 또는 기계 사용 최적화
포트폴리오 관리: 투자 포트폴리오 균형 맞추기
재고 관리: 재고 수준 최적화

배송 회사는 교통 패턴과 패키지 우선순위에 따라 배송 경로를 지속적으로 최적화하기 위해 힐 클라이밍을 사용할 수 있습니다.

힐 클라이밍은 항상 절대적으로 최적의 해답을 찾지는 못할 수 있지만, 그 간단함과 효율성으로 실제 응용 프로그램에서 가치를 인정받습니다. 특히 다음의 경우에 유용합니다:

속속들이 필요한 경우
문제 공간이 완전 탐색에 너무 커서
대략적인 해결책이 허용되는 경우
해결 공간이 비교적 부드러운 경우
알고리즘이 다른 기술과 결합되어 더 나은 결과를 얻을 수 있는 경우

결론

힐 클라이밍은 인공 지능에서 기본 알고리즘으로 자리 잡고 있으며 최적화 문제에 대한 직관적이면서도 강력한 접근 방식을 제공합니다.

우리의 탐구를 통해, 이 간단한 개념이 더 나은 해결책으로 점진적으로 이동함으로써 기계 학습, 로봇 공학, 자연 언어 처리 및 비즈니스 운영 분야의 복잡한 도전 과제에 적용될 수 있는 것을 볼 수 있었습니다.

알고리즘에는 지역 최적해에 갇히는 한계와 같은 제약이 있지만, 임의 재시작 및 모의 담금질과 같은 전략들이 이러한 도전에 효과적으로 대응하기 위해 발전해 왔습니다.

AI가 계속 발전함에 따라, 언덕 오르기는 실용적인 도구로서만 아니라, 보다 복잡한 최적화 알고리즘을 이해하는 발판으로서 여전히 중요합니다. 직관적인 성격으로 인해 AI 분야에 진입하는 사람들에게 우수한 시작점이 되고, 다재다능성은 현실 세계 응용에서 계속 사용되도록 보장합니다.

신경망 가중치 최적화, 로봇 경로 계획, 투자 포트폴리오 관리 등을 최적화하려면, 언덕 오르기의 원리가 컴퓨터가 도전적인 문제에 대해 체계적으로 더 나은 해결책을 찾을 수 있는 가치 있는 통찰을 제공합니다.

AI 및 그 뒤에 있는 알고리즘에 대해 더 배우고 싶다면, 다음 리소스를 확인해보세요:

Source:
https://www.datacamp.com/tutorial/hill-climbing-algorithm-for-ai-in-python