[인공지능] Local Search

[인공지능] Local Search - 3

7_JUN_7 2023. 9. 25. 01:35

Local Beam Search

Local Beam Search는 로컬 검색 알고리즘의 변형 중 하나로, 여러 검색 경로를 동시에 탐색하여 지역 최적해에 갇히는 문제를 극복하려한다.

Basic idea:

𝐾 copies of a local search algorithm, initialized randomly : 알고리즘은 𝐾개의 로컬 검색 알고리즘 복사본을 동시에 무작위로 초기화되어 실행( initialized randomly )하여 다양한 시작점에서 탐색을 시작한다.
각 반복마다 다음 단계를 수행한다 :
- Generate ALL successors from 𝐾 current states : 현재 𝐾개의 상태( 𝐾 current states )에서 가능한 모든 후속 상태( ALL successors )를 생성한다. 이렇게 하면 다양한 방향으로 탐색이 확장된다.
- Choose best 𝐾 (Or, 𝐾 chosen randomly with a bias towards good ones) of these to be the new current states : 생성된 후속 상태 중에서 최상의 𝐾개의 상태를 선택하여 새로운 현재 상태로 설정한다. 이 선택은 후속 상태의 품질에 따라 이루어진다. 또는, 좋은 상태에 편향된 확률(bias towars good ones)로 𝐾개의 상태를 무작위로 선택할 수도 있다.

Local Beam Search의 장점은 여러 검색 경로를 동시에 탐색함으로써 지역 최적해에 빠지는 위험을 줄일 수 있다는 것이다. 그러나 𝐾의 값이 크면 계산 비용이 증가하므로 적절한 𝐾 값을 선택하는 것이 중요하다.

Beam Search Example (K=4)

1. 초기화 :

알고리즘은 𝐾개의 초기 상태 또는 솔루션으로 시작된다.
이 경우 𝐾=4이므로 " 8, 8, 7, 6 " 의 4개의 초기 상태가 있다.

2. 각 단계에서 :

현재 𝐾개의 상태 각각에 대해 가능한 모든 후속 상태를 생성한다.
이렇게 생성된 모든 후속 상태 중에서 최상의 𝐾개의 상태를 선택한다. 선택은 휴리스틱 함수 또는 비용 함수에 따라 이루어진다.
선택된 𝐾개의 상태는 다음 단계의 현재 상태가 된다.
이 경우 " 8, 8, 7, 6 " 의 4개의 초기 상태에서 각각 " 8=>7,9 , 8=>9,9 , 7=>8,6 , 6=>7,7 " 의 successor가 만들어진다.
이렇게 생성된 모든 후속 상태 중에서 최상의 4개의 상태는 " 9 , 9 , 9 , 8 " 이다. ( 가장 높은 수 4개 )
이렇게 선택된 " 9 , 9 , 9 , 8 " 4개의 상태는 다음 단계의 current state가 되며 단계를 반복한다.

3. 종료 조건 :

알고리즘은 목표 상태에 도달하거나 더 이상 확장할 수 있는 상태가 없을 때 종료된다.
" 9, 9, 9, 8 " 의 4개의 상태에서 각각 " 9=>7,8 , 9=>9,10 , 9=>10,5 , 8=>3,9 " 의 successor가 만들어진다.
이렇게 생성된 모든 후속 상태 중에서 최상의 4개의 상태는 " 9 , 10 , 10 , 9 " 이다. ( 가장 높은 수 4개 )
더 이상 확장할 수 없느 상태가 되어 알고리즘을 종료한다.

Local Beam Search

"Local Beam Search"는 여러 개의 로컬 검색 알고리즘을 동시에 실행하는 것처럼 보이지만, 몇 가지 핵심 차이점이 있다.

Local Beam Search는 𝐾개의 독립적인 로컬 검색을 동시에 실행하는 것과는 다르다.

The searches communicate! “Come over here, the grass is greener!”
- "Local Beam Search"에서 각 검색은 다른 검색과 정보를 공유한다. 즉, 한 검색이 좋은 결과를 찾으면 다른 검색도 그 방향으로 이동할 수 있다. 이러한 통신은 각 검색이 독립적으로 작동하는 것보다 더 넓은 검색 공간을 탐색할 수 있게 해준다.

Local Beam Search는 다른 알려진 알고리즘과 유사한 특성을 가지고 있다.

Evolution!
- Local Beam Search는 진화 알고리즘과 유사한 특성을 가지고 있다. 진화 알고리즘에서는 여러 후보 솔루션 (개체)이 서로 경쟁하면서 가장 적합한 솔루션을 찾아나간다. 각 개체는 다른 개체와 교배하거나 변이를 통해 새로운 솔루션을 생성한다. "Local Beam Search"에서도 여러 검색이 서로 정보를 공유하면서 최적의 솔루션을 찾아나가는 것과 유사한 메커니즘이 작동한다.

결론적으로, "Local Beam Search"는 여러 로컬 검색 알고리즘을 동시에 실행하는 것과는 다르게, 각 검색이 서로 정보를 공유하면서 더 넓은 검색 공간을 탐색한다. 이러한 특성은 진화 알고리즘과 유사한 방식으로 작동한다.

Genetic Algorithms(유전 알고리즘)

Fitness 함수에 따라 가중치를 계산해 개체를 선별한다. 여기선 가중치가 가장 낮은 '32543213'이 제외되고 쌍별로 섹션을 나누어 교차 연산자로 다른 유전자끼리 결합한다. 이후 더 다양성을 늘리기 위해 추가적으로 돌연변이로 숫자를 바꾼다. ( 설명을 좀 더 찾아보자)

유전 알고리즘은 자연 선택 원리(natural selection metaphor)를 사용하는 최적화 및 검색 알고리즘이다. 유전 알고리즘은 생물학적 진화의 원리를 모방하여 솔루션의 세대를 거쳐 최적의 솔루션을 찾아나간다.

Genetic algorithms use a natural selection metaphor : 유전 알고리즘은 자연 선택의 원리를 모방하여 작동한다. 이 원리는 가장 적합한 개체가 생존하고 번식하는 생물학적 진화의 기본 개념이다.

Resample 𝐾 individuals at each step (selection) weighted by fitness function : 각 단계에서 적합도 함수(fitness function)에 따라 가중치가 부여된 𝐾개의 개체를 재샘플링한다.
Combine by pairwise crossover operators, plus mutation to give variety : 각 쌍 별로 교차 연산자로 결합되며, 돌연변이를 추가해 다양성을 늘린다.
- 개체들은 교차(crossover) 연산자를 사용하여 조합된다. 교차는 두 개체의 유전자를 결합하여 새로운 개체를 생성하는 과정이다. 예를 들어, 두 개체의 유전자가 "ABCD"와 "WXYZ"라면, 교차 후의 결과는 "ABXZ" 또는 "WBCD"와 같은 다양한 조합이 될 수 있다.
- 돌연변이"(mutation)는 개체의 유전자에 작은 변화를 주어 다양성을 증가시키는 과정이다.

Example: 𝑁-Queens

유전 알고리즘을 "𝑁-Queens" 문제에 적용할 때 고려해야 할 몇 가지 주요 사항은 다음과 같다.

1. Does crossover make sense here? :

교차 (crossover)는 두 개체의 유전자를 결합하여 새로운 개체를 생성하는 과정이다. 𝑁-Queens 문제에서 각 개체는 퀸의 배치를 나타내는 유전자를 가집니다. 교차는 두 배치의 일부를 결합하여 새로운 배치를 생성할 수 있다. 그러나 교차의 결과로 생성된 새로운 배치가 항상 유효한 해결책인지 확인해야 한다.

2. What would mutation be? :

돌연변이 (mutation)는 개체의 유전자에 작은 변화를 주는 과정이다. 𝑁-Queens 문제에서 돌연변이는 퀸의 위치를 무작위로 변경하여 새로운 배치를 생성할 수 있다. 예를 들어, 특정 행의 퀸을 다른 열로 이동시키는 것이 돌연변이의 예가 될 수 있다.

3. What would a good fitness function be? :

𝑁-Queens 문제에서 좋은 적합도 함수는 퀸들 사이의 충돌 수를 기반으로 할 수 있다. 예를 들어, 퀸들 사이에 충돌이 없는 배치는 높은 적합도 값을 가질 것이다. 반면, 많은 충돌이 있는 배치는 낮은 적합도 값을 가질 것이다.

Local Search in Continuous Spaces

대부분의 Local Search 알고리즘은 이산 공간(Discrete Space)에서 작동하지만, 연속 공간(Continuous Space)에서도 지역 검색을 적용할 수 있다.

정의 : 연속 공간은 변수가 연속적인 값을 가질 수 있는 공간을 의미한다. 예를 들어, 실수 범위 내에서 값을 가지는 변수가 있는 최적화 문제는 연속 공간에서의 문제로 볼 수 있다.
이웃의 정의 : 연속 공간에서는 이웃을 정의하는 것이 이산 공간보다 복잡할 수 있다. 일반적으로, 주어진 솔루션 주변의 작은 영역 내에서 무작위로 솔루션을 선택하여 이웃을 생성할 수 있다.
탐색 방법 : 연속 공간에서의 지역 검색은 경사 하강법(Gradient Descent) 또는 경사 상승법(Gradient Ascent)와 같은 방법을 사용하여 최적의 솔루션을 찾을 수 있다. 이러한 방법은 현재 솔루션에서 함수의 경사(또는 기울기)를 계산하고, 경사의 방향으로 솔루션을 업데이트하여 최적의 솔루션을 찾아나간다.
문제점 및 해결책 : 연속 공간에서의 지역 검색은 지역 최적해에 갇힐 위험이 있다. 이를 해결하기 위해 다양한 전략, 예를 들어 모멘텀 추가, 학습률 조정, 무작위 재시작 등을 사용할 수 있다.

Example: Siting Airports in Romania

이 예제는 루마니아에서 3개의 공항을 위치시키는 문제이다. 목표는 각 도시와 가장 가까운 공항 간의 제곱 거리의 합을 최소화하는 것이다.

1. 문제 정의 :

3개의 공항을 루마니아 내에 위치시키려고 한다.
각 공항의 위치는 좌표 (𝑥_𝑎, 𝑦_𝑎)로 표현된다.
각 도시의 위치는 좌표 (𝑥_𝑐, 𝑦_𝑐)로 표현된다.

2. 변수 정의 :

Airport locations 𝑿: 3개의 공항의 위치를 나타내는 좌표 집합이다. 𝑿={(𝑥₁,𝑦₁), (𝑥₂,𝑦₂), (𝑥₃,𝑦₃)}
City locations (𝑥_𝑐, 𝑦_𝑐): 각 도시의 위치를 나타내는 좌표이다.
𝐶_𝑎: 공항 a에 가장 가까운 도시들의 집합이다.

3. 목표 함수 :

목표(Objective): 목표는 각 도시와 그 도시에 가장 가까운 공한 간의 제곱 거리의 합을 나타내는 𝑓(𝒙)를 최소화 하는 것이다.
𝑓(𝒙) = ∑_a ∑ _{c ∈ C_a}(x_a-x_c)²+(y_a-y_c)² : 𝑓(𝒙)는 각 도시와 그 도시에 가장 가까운 공항 간의 제곱 거리의 합을 나타낸다. 도시들의 집합 𝐶_𝑎 중에 한 도시 𝑐에 대해 공항 a를 기준으로 (x_a-x_c)²+(y_a-y_c)²를 계산하고 모든 도시들과의 거리를 합한 뒤 나머지 공항들에 대해서도 계산하여 전부 합한다.

Handling a Continuous State/Action Space

연속적인 상태/행동 공간을 다루는 것은 많은 최적화 및 검색 문제에서 중요한 고려사항이다. 연속 공간을 처리하는 데 사용할 수 있는 몇 가지 일반적인 방법에 대해 설명한다.

1. Discretize it!

연속 공간을 이산 공간으로 변환(이산화)하는 방법이다.
그리드(grid) 정의 : 증분(increment) 𝛿를 사용하여 그리드를 정의하고, 이 그리드 위에서 이산 알고리즘(discrete algorithm)을 사용하여 문제를 해결할 수 있다.
예를 들어, 0에서 10 사이의 값을 가지는 변수가 있고 𝛿를 1로 설정하면, 가능한 값은 0, 1, 2, ..., 10이 된다.

2. Choose random perturbations to the state

현재 상태에 무작위 변동(random perturbations) 을 추가하여 새로운 상태를 생성하는 방법이다.
First-choice hill-climbing : 상태를 개선하는 무언가를 찾을 때까지 계속 시도한다. 즉, 첫 번째로 발견된 개선 사항을 채택하는 방식이다.
Simulated annealing : 무작위 변동을 추가하여 새로운 상태를 생성하고, 특정 확률에 따라 현재 상태를 개선하지 않는 상태도 수용한다. 이 확률은 시간에 따라 감소하는 "온도" 파라미터에 의해 결정된다.

3. Compute gradient of 𝑓(𝑥) analytically

𝑓(𝑥)의 기울기(gradient)를 분석적으로 계산하는 방법이다.
경사는 𝑓(𝑥)의 변화율을 나타내며, 경사 하강법 또는 경사 상승법과 같은 알고리즘을 사용하여 𝑓(𝑥)를 최소화하거나 최대화하는 방향으로 상태를 업데이트할 수 있다.

Finding Extrema in Continuous Space

연속 공간에서 극값(Extrema : 최대값 또는 최소값)을 찾는 방법

1. Gradient vector (∇𝑓(𝑥)): ∇𝑓(𝑥) = (∂f/∂ 𝑥₁ ,∂f/∂y_1,∂f/∂ 𝑥₂ , …)T

기울기 벡터는 함수 𝑓의 각 변수에 대한 편미분 값들로 구성됩니다.
𝑓(𝑥)의 변화율을 나타내며, 각 변수의 방향으로 얼마나 빠르게 변하는지를 나타냅니다.

2. For the airports, 𝑓(𝑥) : 𝑓(𝑥) =∑_a∑_(c∈C_a)( 𝑥 _a- 𝑥 _c )^2+(y_a-y_c )^2

주어진 𝑓(𝑥) 함수는 각 공항과 해당 공항에 가장 가까운 도시 간의 거리의 제곱 합을 나타냅니다.

3. 편미분 : (𝜕𝑓/𝜕𝑥₁ =∑_(c∈C_1)2( 𝑥 _1- 𝑥 _c )

𝑓의 𝑥₁에 대한 편미분은 𝑥₁ 공항과 𝐶₁ 집합에 속하는 도시 간의 거리의 합을 나타냅니다.

4. At an extremum, ∇𝑓(𝑥) = 0:

극값에서 기울기 벡터의 값은 0입니다. 이는 함수가 극값에서 최대 또는 최소 값을 가짐을 의미합니다.

5. Closed form solution : x_1=(∑_(c∈ 𝑥₁ )x_c )/| 𝐶₁ |

𝑥₁의 값은 𝐶₁ 집합에 속하는 도시들의 𝑥 좌표의 평균 값으로 계산됩니다.

6. Is this a local or global minimum of 𝑓?

주어진 정보만으로는 𝑓의 극값이 지역 최소값인지 전역 최소값인지 판단하기 어렵다. 기울기 벡터만으로는 극값의 유형을 결정할 수 없다.

7. Gradient descent: 𝑥 ← 𝑥 -α∇𝑓(𝑥)

경사 하강법( Gradient descent )은 현재 위치에서 기울기의 반대 방향으로 일정 거리(𝛼)만큼 이동하여 함수 값을 줄이는 방법이다.
𝑥에 α∇𝑓(𝑥)만큼 뺀 값을 다시 𝑥에 대입하여 반복한다.
𝛼는 학습률로, 얼마나 빠르게 최소값을 찾아갈 것인지를 결정한다.
많은 알고리즘이 gradient 방법으로 극값을 찾는다.

Summary

많은 구성(configuration) 및 최적화(optimization) 문제는 지역 검색으로 표현될 수 있다. 지역 검색은 주어진 상태에서 시작하여 이웃 상태를 탐색하고, 목표 함수를 개선하는 방향으로 상태를 변경하는 방식으로 작동한다.

일반적인 알고리즘 유형 :

Hill-climbing, continuous optimization :
- 현재 상태의 이웃 중에서 가장 좋은 상태로 이동하는 방식이다. 연속 최적화에서는 기울기 정보를 사용하여 최적의 방향으로 이동한다.
Simulated annealing (and other 확률적 방법stochastic methods) :
- 확률적으로 "나쁜" 이동을 허용하여 지역 최적해에서 벗어나려고 시도한다. 시간이 지남에 따라 나쁜 이동을 허용하는 확률이 감소한다.
Local beam search: multiple interaction searches :
- 여러 검색을 동시에 수행하며, 각 반복에서 가장 좋은 상태들만 유지된다. 이러한 방식은 여러 검색이 서로 정보를 공유하게 된다.
Genetic algorithms: break and recombine states**: - 상태를 "부모"로 사용하여 새로운 "자식" 상태를 생성하는 방식입니다. 이는 자연 선택의 원리를 사용하여 최적의 솔루션을 찾는다.
많은 기계 학습 알고리즘(ex : 신경망 훈련등의 최적화 문제)은 지역 검색의 형태를 취한다. 이는 매개변수의 최적 값을 찾기 위해 지역 검색 기법을 사용하는 것을 의미한다.