1. Simulated Annealing
Steepest Ascent, First Choice, Stochatic 알고리즘은 모두 current state에서 좋은 쪽으로만 이동하려고한다.
Simulated Annealing은 확률적으로 value가 더 안 좋은 곳으로 state를 update 하면서 local min에서 벗어나 더 좋은 min으로 이동하게 만든다.
아래 예시를 보면 현재 state에서 확률적으로 값이 value가 좋아질 수도, 안 좋아질 수도 있다.
계속 좋은 쪽으로만 이동하면, local min에 빠지지만, 확률적으로 안 좋은 쪽으로 이동하고 계속 이동하다 보면, 보라색 점인 global min으로 이동할 수 있다.
이때 annealing이란 담금질을 의미하는데 금속을 녹이고 서서히 냉각시키는 기법이다. 여기에서 중요한 것은 온도(t)를 점점 낮추면서 실행해야 한다는 점이다.
1) 현재 위치를 random으로 초기화
2) 현재 위치의 value 계산
3) 초기 온도를 설정
while:
4) 온도를 업데이트
5) random 하게 이웃을 생성
6) mutant value와 current value 비교
7) 확률적으로 state 업데이트
8) best업데이트
def SimulatedAnnealing(p):
current = randomInit(p)
valueC = evaluate(current, p)
best, valueBest = current, valueC
whenBestFound = i = 1
t = initTemp(p)
while i < LIMITEVAL:
t = tSchedule(t) # 온도 업데이트
mutant = randomMutant(current, p) # 랜덤 mutant 생성
valueM = evaluate(mutant, p) # mutant 평가
# mutant 값이 더 좋다면 update
if valueM < valueC:
current, valueC = mutant, valueM
else:
# mutant 값이 더 안 좋다면 확률적으로 업데이트
de = valueM - valueC
prob = math.exp(-de / t) # 확률 계산
if random.random() < prob: #
current, valueC = mutant, valueM
# best 값보다 좋다면 best 업데이트
if valueC < valueBest:
best, valueBest = current, valueC
whenBestFound = i
i += 1 # iteration 증가
return best, valueBest
neighbor의 value가 좋다면 좋은 쪽으로 이동하지만, 반대의 상황이면 확률적으로 안 좋은 쪽으로 이동한다.
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) initTemp : 초기 온도를 설정
def initTemp(p):
diffs = []
for i in range(numSample):
c0 = p.randomInit() # random한 위치
v0 = p.evaluate(c0)
c1 = p.randomMutant(c0) # c0의 이웃
v1 = p.evaluate(c1)
diffs.append(abs(v1 - v0))
dE = sum(diffs) / numSample
t = dE / math.log(2)
return t
가장 초기 온도를 random하게 설정한다.
ex) t : 0.012472329805111601
4) tSchedule : 온도 업데이트
def tSchedule(t):
return t * (1 - (1 / 10**4)) # 온도를 조금씩 낮춤
5) randomMutant : random 하게 이웃을 생성
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
neighbor(successor)를 구할 때 랜덤하게 하나만 return 한다.
6) mutant value와 current value 비교
# mutant 값이 더 좋다면 update
if valueM < valueC:
current, valueC = mutant, valueM
else:
# mutant 값이 더 안 좋다면 확률적으로 업데이트
de = valueM - valueC
prob = math.exp(-de / t) # 확률 계산
if random.random() < prob: # ex) 0.7878286006010926
current, valueC = mutant, valueM
neighbor의 value와 current value를 비교한다.
if valueM(neighbor)가 더 낮으면(좋으면) -> state update
else 확률적으로 state를 좋은 쪽 or 안 좋은 쪽으로 update
7) 확률적으로 state 업데이트
# mutant 값이 더 안 좋다면 확률적으로 업데이트
de = valueM - valueC
prob = math.exp(-de / t) # 확률 계산
if random.random() < prob: # ex) 0.7878286006010926
current, valueC = mutant, valueM
de는 neighbor에 따른 random한 값이므로 prob도 항상 random이다.
if random.random() < prob 조건에 만족하면 state가 안 좋은 쪽으로 update된다.
8) best 업데이트
if valueC < valueBest:
best, valueBest = current, valueC
whenBestFound = i
current value가 더 좋으면 best를 update한다.
9) 실행 결과
- Convex
다른 알고리즘과 다르게 항상 좋은 쪽으로 이동하는 것이 아니라 확률적으로 안 좋은 쪽으로 이동하는 알고리즘이라서 LIMITEVAL을 작게 설정할 경우(위 사진) min이 이상하게 나오는 것을 볼 수 있다.
LIMITEVAL을 크게 설정할 경우(아래 사진) min이 0으로 잘 최적화된 것을 확인할 수 있다.
- 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의 세세한 내용이 다르다.
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) initTemp : 초기 온도를 설정
def initTemp(p):
diffs = []
for i in range(numSample):
c0 = p.randomInit() # random한 위치
v0 = p.evaluate(c0)
c1 = p.randomMutant(c0) # c0의 이웃
v1 = p.evaluate(c1)
diffs.append(abs(v1 - v0))
dE = sum(diffs) / numSample
t = dE / math.log(2)
return t
가장 초기 온도를 random하게 설정한다.
ex) t : 0.012472329805111601
4) tSchedule : 온도를 업데이트
def tSchedule(t):
return t * (1 - (1 / 10**4)) # 온도를 조금씩 낮춤
5) randomMutant : random하게 이웃을 생성
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
neighbor(successor)를 구할 때 랜덤하게 하나만 return 한다.
6) mutant value와 current value 비교
# mutant 값이 더 좋다면 update
if valueM < valueC:
current, valueC = mutant, valueM
else:
# mutant 값이 더 안 좋다면 확률적으로 업데이트
de = valueM - valueC
prob = math.exp(-de / t) # 확률 계산
if random.random() < prob: # ex) 0.7878286006010926
current, valueC = mutant, valueM
neighbor의 value와 current value를 비교한다.
if valueM(neighbor)가 더 낮으면(좋으면) -> state update
else 확률적으로 state를 좋은 쪽 or 안 좋은 쪽으로 update
7) 확률적으로 state 업데이트
# mutant 값이 더 안 좋다면 확률적으로 업데이트
de = valueM - valueC
prob = math.exp(-de / t) # 확률 계산
if random.random() < prob: # ex) 0.7878286006010926
current, valueC = mutant, valueM
de는 neighbor에 따른 random한 값이므로 prob도 항상 random이다.
if random.random() < prob 조건에 만족하면 state가 안 좋은 쪽으로 update된다.
8) best 업데이트
if valueC < valueBest:
best, valueBest = current, valueC
whenBestFound = i
current value가 더 좋으면 best를 update한다.
9) 실행결과
- tsp30
- tsp50
- tsp100
Simulated Annealing의 경우 다른 알고리즘과 다르게 확률적으로 안 좋은 방향으로 이동하기 때문에 LIMITEVAL을 작게 설정할 시 최솟값을 못 찾는다. 반대로 말하면 LIMITEVAL을 크게 설정하면 시간은 더 걸리지만, global min을 찾을 확률이 높아진다.
한줄요약
Simulated Annealing : 현재 state에서 하나의 이웃만 구하여 그 value와 현재 value를 비교하여 더 좋으면 update, 안 좋으면 확률적으로 update하는 알고리즘
'인공지능 > Local Search Algorithms' 카테고리의 다른 글
| [Local Search Algorithms - Meta Heuristic Algorithm] Genetic Algorithm (0) | 2024.12.10 |
|---|---|
| [Local Search Algorithms] Gradient Descent (1) | 2024.12.07 |
| [Local Search Algorithms - Hill climbing Algorithms] Stochastic (0) | 2024.12.05 |
| [Local Search Algorithms - Hill climbing Algorithms] First Choice (0) | 2024.12.04 |
| [Local Search Algorithms - Hill climbing Algorithms] Steepest Ascent (0) | 2024.12.01 |