[Local Search Algorithms - Hill climbing Algorithms] First Choice

1. First Choice

steepest ascent와 다르게 neighbor을 하나만 결정하여  min을 찾는 알고리즘이다.

 

이웃을 구할 때 random하게 이웃을 하나 결정한 후 current value보다 좋으면 update하고 안 좋으면 이동하지 않는 알고리즘이다. 

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

while:
    3) 현재 위치를 기준으로 랜덤하게 neighbor(successor)를 구함.
    4) successor의 value를 구함.
    5) best value와 current value 비교

def firstChoice(p):
    current = randomInit(p)   
    valueC = evaluate(current, p)
    i = 0
    while i < LIMIT_STUCK:
        successor = randomMutant(current, p)
        valueS = evaluate(successor, p)
        if valueS < valueC:
            current = successor
            valueC = valueS
            i = 0        
        else:
            i += 1
    return current, valueC

 

위 알고리즘을 통해 최솟값을 구할 수 있다. 
numeric와 tsp 문제에 따라 successor를 구하는 법은 다르지만 위의 큰 틀을 토대로 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) evalute : 현재 상태에서 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) randomMutant : random하게 successor 생성 

def randomMutant(current, p):
    i = random.randrange(0, len(p[1][0]))
    d = random.choice([DELTA, -DELTA]) # DELTA : 0.01
    
    return mutate(current, i, d, p) # [-10, 21, 3.01, 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

 

이 부분이 Steepest Ascent와 가장 다른 점이다.

 

neighbor(successor)를 구할 때 랜덤하게 하나만 return 한다.

 

4) successor의 value 구하기

 

evaluate를 사용하여 3)에서 구한 successor의 value를 구한다. 

 

5) current value와 successor value 비교

while i < LIMIT_STUCK: # LIMIT_STUCK은 1000이라고 가정
    if valueS < valueC:
        current = successor
        valueC = valueS
        i = 0        
    else:
        i += 1

 

current value와 successor value를 비교하면서 state를 update하거나, i+=1을 실행한다.

 

위 과정을 LIMIT_STUCK만큼 한다.

 

6) 실행 결과

- Convex

- Griewank

- Ackley

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의 세세한 내용이 다르다. 

 

Steeest Ascent

 

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]

 

Steeest Ascent와 마찬가지로 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 # 총 거리수

 

Steepest Ascent와 마찬가지로 value를 계산한다.

 

3) 현재 위치를 기준으로 랜덤하게 neighbor(successor)를 구함

def randomMutant(current, p):
    while True:
        i, j = sorted([random.randrange(p[0])
                    for _ in range(2)])
        if i < j:
            curCopy = inversion(current, i, j)
            break
    return curCopy # i: 0, j : 7 -> [2, 14, 4, 24, 15, 12, 20, 29, 27, 16, 21, 3, 26, 1, 0, 8, 9, 28, 10, 7, 23, 17, 18, 19, 13, 25, 5, 11, 6, 22]


def inversion(current, i, j):  # Perform inversion
    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를 구한다.

 

4) successor의 value를 구함

evaluate를 사용하여 3)에서 구한 successor의 value를 구한다. 

 

5) current value와 successor value 비교

while i < LIMIT_STUCK: # LIMIT_STUCK은 1000이라고 가정
    if valueS < valueC:
        current = successor
        valueC = valueS
        i = 0        
    else:
        i += 1

 

 

6) 실행결과

 

- tsp30

- tsp50

 

- tsp100

 

---

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

 

앞선 Steepest Ascent와 겹치는 부분이 많았다. 

 

차이점을 간단하게 보면 Steepest Ascent는 neighbors를 구할 때 여러개의 이웃을 구하는 반면, First Choice는 이름 그대로 이웃 하나만 구해서 value를 비교하여 min을 구한다. 

 

이웃을 하나만 구해서 연산 과정이 간단해져서 실행 속도가 빠르다.

 

무엇이 더 좋은지에 대한 판단은 아직 하기에는 이르다.

 

다른 알고리즘을 계속 공부하면서 알고리즘의 성능을 비교해보자.

 

한줄요약

First Choice : 현재 state에서 하나의 이웃만 구하여 그 value와 현재 value를 비교하여 좋은 쪽으로 이동하며 local min을 찾는 알고리즘