[Local Search Algorithms - Hill climbing Algorithms] Steepest Ascent

1. Steepest Ascent

현재 위치에서 주변의 모든 neighbors를 보고 그중 가장 좋은(best) value인 state로 이동하면서 min을 찾는 알고리즘이다. 

 

domain이 x1일 때를 예를 들어보자.

 

현재 state에서 neighbors를 구해보면 x'1과 x''1이다.

 

이 중 best value는 x'1이므로 current state를 x'1으로 update한다.

 

이 과정을 더 이상 더 좋은 이웃이 없을 때까지 반복한다.

1) 현재 위치를 random으로 초기화
2) 현재 위치의 value 계산

while:
    3) 현재 위치를 기준으로 모든 neighbors를 구함.
    4) neighbors 중 best value를 구함.
    5) best value와 current value 비교

def steepestAscent(p):
    current = randomInit(p)
    valueC = evaluate(current, p)
    while True:
        neighbors = mutants(current, p)
        successor, valueS = bestOf(neighbors, p)
        if valueS >= valueC:
            break
        else:
            current = successor
            valueC = valueS
    return current, valueC

 
위 알고리즘을 통해 최솟값을 구할 수 있다. 

numeric와 tsp 문제에 따라 neighbors 중 best value를 구하는 법, 비교하는 법 등은 다르지만 위의 큰 틀을 토대로 min을 구할 수 있다.
 
아래를 참고하여 문제 유형에 따른 중요함수를 살펴보자.

2. Numeric

Convex로 문제를 풀어보자.

(x1 - 2) ** 2 +5 * (x2 - 5) ** 2 + 8 * (x3 + 8) ** 2 + 3 * (x4 + 1) ** 2 + 6 * (x5 - 7) ** 2
x1,-30,30
x2,-30,30
x3,-30,30
x4,-30,30
x5,-30,30

 
1) randomInit : 현재 위치를 random으로 초기화

def randomInit(p):
    """
    p : [expr, [varNames, low, up]]
    varNames : [x1, x2, x3 . .]
    low : [-30, -30, . . .]
    up : [30, 30, . . .]
    """
    varNames = p[1][0]
    low = p[1][1]
    up = p[1][2]
    init = []
    
    for i in range(len(varNames)):
        val = random.randint(int(low[i]), int(up[i]))
        init.append(val) 
    return init # 초기값 : [-10, 21, 3, 17, -28]

 

가장 처음에 현재 위치를 random하게 초기화하는 함수다.

 

단순하게 for문을 돌면서 각 value에 -30, 30사이의 수를 리스트에 담아 return 한다.

 

 
2) evaluate : 현재 위치의 value 계산

def evaluate(current, p): # current : [-10, 21, 3, 17, -28]
    """
    NumEval : 계산 횟수를 세기 위한 변수
    expr : (x1 - 2) ** 2 +5 * (x2 - 5) ** 2 + 8 * (x3 + 8) ** 2 + 3 * (x4 + 1) ** 2 + 6 * (x5 - 7) ** 2
    valNames : [x1, x2, . . .]
    """
    global NumEval
    
    NumEval += 1
    expr = p[0]     
    varNames = p[1][0] 
    for i in range(len(varNames)):
        assignment = varNames[i] + '=' + str(current[i])
        exec(assignment, globals())
    return eval(expr) # value

 

for문을 통해 exec를 실행시키면 다음과 같이 변수에 값을 넣는다.

x1=-10

x2=21

x3=3

x4=17

x5=-28

 

이후 eval을 통해 expr에 각 변수를 대입하여 value를 return 한다.
 
3. mutants : 현재위치를 기준으로 neighbors를 구함.

def mutants(current, p): # current : [-10, 21, 3, 17, -28]
    neighbors = []
    for i in range(len(current)):
        # 각 변수에 대해 DELTA를 더하고 빼서 이웃을 생성
        # DELTA : 0.01 
        neighbors.append(mutate(current, i, DELTA, p)) 
        neighbors.append(mutate(current, i, -DELTA, p))
    return neighbors # [[-9.99, 21, 3, 17, -28], [-10.01, 21, 3, 17, -28], [-10, 21.01, 3, 17, -28], [-10, 20.99, 3, 17, -28] . . . ]


def mutate(current, i, d, p):
    curCopy = current[:]
    domain = p[1]        # [VarNames, low, up]
    l = domain[1][i]     # Lower bound of i-th
    u = domain[2][i]     # Upper bound of i-th
    if l <= (curCopy[i] + d) <= u:
        curCopy[i] += d
    return curCopy

 

mutants함수를 통해 현재 위치에서 각각의 변수(x1 ~ x5)마다  neighbors를 생성한다.

 

이웃은 현재 위치에서 DELTA만큼 더하고 뺀 위치가 neighbors가 된다.

 

변수가 5개이므로 총 10개의 neighbors가 만들어진다.


4) bestof : 이웃 중 best value를 구함

def bestOf(neighbors, p):
    best = neighbors[0] # 0번째 이웃을 best로 가정
    bestValue = evaluate(best, p) # best에서의 value 계산
    for i in range(len(neighbors)):
        newValue = evaluate(neighbors[i], p)
        if newValue < bestValue: # 더 좋은 value 찾기
            best = neighbors[i]
            bestValue = newValue
    return best, bestValue # 더 좋은 이웃을 return

 

10개의 neighbors를 다 돌면서 가장 좋은(best) value를 찾아서 그때의 value와 state를 return한다.

 

5) current value와 successor value를 비교

while True:
    neighbors = mutants(current, p)
    successor, valueS = bestOf(neighbors, p)
    if valueS >= valueC:
        break
    else:
        current = successor
        valueC = valueS

while(True)를 거치면서 더 좋은 값이 안 나올 경우 실행을 종료하고 그 값을 best라고 결정한다.

6) 실행결과

- Convex

 

Convex를 Steepest-Ascent로 구현한 결과이다.

총 125,412번의 연산을 통해 최솟값 0.000을 구할 수 있다.

 

- Griewank

 

Griewank는 수많은 local min이 있어서 초기값에 따라 항상 다른 결과가 나온다. 

 

- Ackley

 

Ackley도 마찬가지로 수많은 local min이 있어서 초기값에 따라 항상 다른 결과가 나온다. 

3. TSP

Tsp에서 도시 수가 30일 때로 문제를 풀어보자

30
(8, 31)
(54, 97)
(50, 50)
(65, 16)
(70, 47)
(25, 100)
(55, 74)
(77, 87)
(6, 46)
(70, 78)
(13, 38)
(100, 32)
(26, 35)
(55, 16)
(26, 77)
(17, 67)
(40, 36)
(38, 27)
(33, 2)
(48, 9)
(62, 20)
(17, 92)
(30, 2)
(80, 75)
(32, 36)
(43, 79)
(57, 49)
(18, 24)
(96, 76)
(81, 39)

 

첫 번째 줄에는 도시 수를 나타내고

두 번째 줄부터는 도시의 좌표이다.

 

Tsp 문제도 numeric와 같은 알고리즘으로 구현된다. 하지만 각 function의 세세한 내용이 다르다. 

 

0) 문제를 생성할 때 각 도시마다의 거리 table을 생성

def calcDistanceTable(numCities, locations):
    """
    numCities : 30 
    locations : [[8, 31], [54, 97], [50, 50] . . .]
    """
    table = [[0] * numCities for i in range(numCities)]

    for i in range(numCities):
        for j in range(i+1, numCities):
            x1, y1 = locations[i]
            x2, y2 = locations[j]
            distance =  math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)

            table[i][j] = distance
            table[j][i] = distance

    return table
    
    """ 
    table 출력
    [[0,80.44874144447506, 46.09772228646444, 58.9406481131655, . . . ], 
    [80.44874144447506, 0, 47.16990566028302, 81.74350127074322, 52.49761899362675, . . .],
    ...
    ... ]
    
    """

 

각 도시마다의 거리를 저장한 table이다. 

 

1번 도시를 기준으로 2, 3, 4, ... , 30 도시의 거리

2번 도시를 기준으로 1, 3, 4, ... , 30 도시의 거리

.

.

30번 도시를 기준으로 1, 2, 3, ... , 29 도시의 거리

 

1) randomInit :  현재 위치를 random으로 초기화

def randomInit(p):  
    """ 
    p : [numCities, locations, table]
    numCities : 30 
    locations: [[8, 31], [54, 97], [50, 50] . . .]
    table : 각 도시마다의 거리 테이블 
    """
    n = p[0]
    init = list(range(n))
    random.shuffle(init)
    return init # [29, 20, 12, 15, 24, 4, 14, 2, 27, 16, 21, 3, 26, 1, 0, 8, 9, 28, 10, 7, 23, 17, 18, 19, 13, 25, 5, 11, 6, 22]

 

random하게 초기 도시 순서 결정한다.

 

2) evaluate : 현재 위치의 value 계산

def evaluate(current, p):
    
    """
    current : [29, 20, 12, 15, 24, 4, 14, 2, 27, 16, 21, 3, 26, 1, 0, 8, 9, 28, 10, 7, 23, 17, 18, 19, 13, 25, 5, 11, 6, 22]
    p : [numCities, locations, table]
    
    """
    global NumEval
    NumEval += 1

    n = p[0]
    table = p[2]
    cost = 0

    for i in range(n-1):
        locFrom = current[i]
        locTo = current[i+1]
        cost += table[locFrom][locTo]

    cost += table[current[-1]][current[0]]
    return cost # 총 거리수

 

도시마다의 거리를 다 더한값인 cost를 return한다.

 

3) 현재 위치를 기준으로 모든 neighbors를 구함.

def mutants(current, p):
    n = p[0]
    neighbors = []
    count = 0
    triedPairs = []
    while count <= n:  
        i, j = sorted([random.randrange(n) for _ in range(2)])
        if i < j and [i, j] not in triedPairs:
            triedPairs.append([i, j])
            curCopy = inversion(current, i, j)
            count += 1
            neighbors.append(curCopy)
    return neighbors

def inversion(current, i, j):
    curCopy = current[:]
    while i < j:
        curCopy[i], curCopy[j] = curCopy[j], curCopy[i]
        i += 1
        j -= 1
    
    return curCopy

 

neighbors를 생성할 때 i, j를 random하게 뽑은 후 현재 state의 i ~ j 를 inversion한 것을 neighbor이라고 한다.

 

밑의 예시를 통해 보자.

 

첫 번째 neighrbor은 현재 state([29, 20, 12, 15, 24, 4, 14, 2, 27, 16, 21, 3, 26, 1, 0, 8, 9, 28, 10, 7, 23, 17, 18, 19, 13, 25, 5, 11, 6, 22])에서 16 ~ 19번째를 inversion한 것이다.

 

총 31개의 neighbors를 구한다.

neighbors 출력

[[29, 20, 12, 15, 24, 4, 14, 2, 27, 16, 21, 3, 26, 1, 0, 8, 9, 23, 7, 10, 28, 17, 18, 19, 13, 25, 5, 11, 6, 22], 
[29, 20, 12, 15, 24, 4, 14, 2, 27, 10, 28, 9, 8, 0, 1, 26, 3, 21, 16, 7, 23, 17, 18, 19, 13, 25, 5, 11, 6, 22], 
[29, 24, 15, 12, 20, 4, 14, 2, 27, 16, 21, 3, 26, 1, 0, 8, 9, 28, 10, 7, 23, 17, 18, 19, 13, 25, 5, 11, 6, 22], 
[29, 15, 12, 20, 24, 4, 14, 2, 27, 16, 21, 3, 26, 1, 0, 8, 9, 28, 10, 7, 23, 17, 18, 19, 13, 25, 5, 11, 6, 22], 
.
.
.]

 

4) neighbors 중 best value를 구함

def bestOf(neighbors, p):
    best = neighbors[0] 
    bestValue = evaluate(best, p)
    for i in range(len(neighbors)):
        newValue = evaluate(neighbors[i], p)
        if newValue < bestValue:
            best = neighbors[i]
            bestValue = newValue

    return best, bestValue

 

이웃 중 가장 거리가 짧은 것을 찾는다.

 

5) current value와 successor value를 비교

while True:
    neighbors = mutants(current, p)
    successor, valueS = bestOf(neighbors, p)
    if valueS >= valueC:
        break
    else:
        current = successor
        valueC = valueS

 

while(True)를 거치면서 더 좋은 값이 안 나올 경우 실행을 종료하고 그 값을 best라고 결정한다.

 

6) 실행결과

 

- tsp 30

- tsp50

- tsp100

 

 

 

numeric와 tsp 문제 둘 다 초기값에 따라 min값이 달라진다. 

 

 

---

Local Search Algorithms - Hill climbing Algorithms를 Steepest Ascent를 사용하여 numeric과 tsp 문제를 해결했다.

 

두 문제를 풀 때 같은 같은 알고리즘으로 : 초기값 설정 -> value 구하기 -> 이웃 구하기 -> 값 비교하기 . . . 를 통해 문제를 풀었다. 

 

 

한줄요약

steepest Ascent : 현재 state의 이웃 중 가장 좋은 value와 현재 state의 value를 비교하여 좋은 쪽으로 이동하며 local min을 찾는 알고리즘