최적화는 여러 가지 많은 수의 해답 찾기를 시도한 후에 그 해답에 대한 품질을 판단하여 점수를 매겨서 최적의 해답을 찾는 것을 말합니다. 지금 흘리듯이 이야기하지만 잘 알아둬야 할 정의입니다. 꼭요. ★★★★★(별 5개)
최적의 해를 구하기 위해서 하는 짓을 이해하려면 다음의 컨셉을 이해해야만 합니다.
어떤 최적해를 구하기 위해서는
이런 식으로 해답을 구하게 되는데요,
이게 무슨 소린가 싶은데 어떤 해답을 찾기 위해서는 해답이 가질 수 있는 범위(domain), 그리고 어떤 해답을 찾아갈 때 안 좋은 답일수록 비용이 커서 더 작은 비용을 갖는 해답을 찾도록 하는 임시 해답에 대한 비용(cost), 그리고, 그 해답을 찾아가기 위한 알고리즘인 해답을 찾는 방법(optimizer)이 필요하다고 할 수 있겠습니다.
요 컨셉을 이해하고 있다면, 여러모로 문제를 해결하는데 유용하게 적용할 수 있겠습니다. 최적화 해법을 찾기 위해서는,
⓵ 해답 표현방식을 결정
⓶ 해답에 대한 cost를 계산할 수 있도록 설계
⓷ 해답을 찾기 위한 Cost를 줄이는 방법 즉, optimizer 설계
요런 단계를 통해서 해답을 찾아갑니다. 바로 전에 유전자 알고리즘으로 간단한 문제를 풀어보았는데, 같은 스토리로 실제 예를 통해 들여다보면 이번엔 진짜 아하! 할 거라 생각합니다.
실전 예제, 가족 단체만남에 대한 최적해를 구하는 방법!
서로 다른 장소에서 출발해서 같은 목적지를 가는 단체여행이라는 문제를 풀어보도록 하겠습니다. 단체여행이라고는 했지만 당일날 출발해서 모두 얼굴을 보고 즐거워한 후에 하이파이브만 하고 곧바로 당일날 돌아가는 일정입니다. 후후. 흥미롭군요. 쿨한 가족 여행입니다. 이때 가장 Cost가 적은 (최적) 방법을 찾아내 보겠습니다.
처음에 가족 구성원을 정의해 보겠습니다. 도착지는 서울이고요.
people = [('아빠','부산'), # 이름과 출발지
('엄마','대전'),
('언니','청주'),
('오빠','마산'),
('남친','울릉'),
('동생','오산')]
destination='서울'
flights={}
그렇군요 모든 가족이 멀리멀리에 사네요. 여기에서 풀고 싶은 문제를 더 자세하게 늘어놓아 보면,
⓵ 모든 가족이 같은 날 출발해서 같은날 도착해야 하고,
⓶ 공항이용 요금을 공유하고,
⓷ 모든 가족의 출발지에서 서울에 도착하는 비행기가 많이 있음.
⓸ 전체 여행 비용을 최소화해야 함
해당 데이터가 있는데, 이것은 https://forms.gle/ovA7X42tkSb4XmyB7 에서 다운로드 신청을 하시면 다운로드할 수 있습니다. 막상 열어보면, 출발지, 도착지, 출발시간, 도착시간, 요금이 잔뜩 있습니다.
서울,오산,6:19,8:13,239
오산,서울,6:11,8:31,249
서울,오산,8:04,10:59,136
오산,서울,7:39,10:24,219
서울,오산,9:31,11:43,210
오산,서울,9:15,12:03,99
.....
이런 식으로 출발지, 도착지, 출발시간, 도착시간, 요금이 나와 있습니다.
자, 이 데이터를 (origin, dest)를 Dictionary key로 해서, 상세 비행 편 정보 리스트를 Dictionary value로 만들면 뭔가 우리가 다루기 편한 데이터 형태가 될 것 같군요.
txt_schedule = 'schedule.txt.out.txt'
file = open(txt_schedule)
lst_cities = []
# 파일에는 origin destination 출발시간 도착시간, 가격정보로 저장되어 있음
for line in file:
origin,dest,depart,arrive,price=line.strip().split(',')
flights.setdefault((origin,dest),[]) # key를 넣어보고 있으면 값을 반환, 없으면 default로 [] 값 반환
# Dictionary에 정보를 넣음
flights[(origin,dest)].append((depart,arrive,int(price))) # (Orgin, Dest)을 dictionary에 계속 추가
flights
이렇게 하고 보면, 거지 같던 flight를 Time Table로 만들 수 있겠습니다.
{('서울', '오산'): [('6:19', '8:13', 239),
('8:04', '10:59', 136),
('9:31', '11:43', 210),
('11:07', '13:24', 171)
...
('오산', '서울'): [('6:11', '8:31', 249),
('7:39', '10:24', 219),
('9:15', '12:03', 99),
....
그러니까, 이런 식의 Dictionary를 만들 수 있겠습니다.
자, 이제 가족들이 각자 어떤 비행기를 탑승해야 전체 여행경비를 최소로 줄일 수 있는지 찾아내 보도록 하겠습니다. 흥미진진.
이때 첫 번째로 중요한 것이 찾아낸 해답을 어떤 식으로 표현할 것인가가 필요합니다. 리스트로 해답을 표현해 보시죠. 아이디어는 각 가족마다 출발, 도착으로 2개씩 해답을 늘어놓는 것입니다. 설명을 위해서 아무 값을 아무렇게나 늘어놓은 마구잡이 Solution을 다뤄보겠습니다.
sol = [1, 4, 3, 2, 7, 3, 6, 3, 2, 4, 5, 3]
이라고 한다면 어떤 가족이 선택야 하는 비행기 편을 표현하는데, 각 가족마다 2개씩 해답을 갖습니다. 가족수가 6명이니까 12개의 원소를 갖게 되고요, 가족의 순서는 아빠, 엄마, 언니, 오빠, 남친, 동생순입니다. 숫자의 의미는 그날의 첫 비행기라면 0, 두 번째 비행기라면 1과 같이 표현하고 첫번째 숫자는 있던 곳 출발편, 두번째 숫자는 서울에서 돌아가는 출발 편을 의미하는데, 예를 들어 마구잡이 예시 해답을 해석해 보면 처음 1, 4가 아빠에 대한 해답이고요, 아빠가 부산에서 서울로 2번째 비행기를 타고 간 후에, 서울에서 부산으로 가는 5번째 비행기를 탄다고 생각하면 됩니다.
이 해답을 보기 쉽도록 출력하는 함수를 만든다면
def printschedule(sol):
for i in range(int(len(sol)/2)): #사람수 만큼
name=people[i][0]
origin=people[i][1]
out=flights[(origin,destination)][int(sol[i*2])] # sol[0] sol[2] sol[4]... 서울로 출발
ret=flights[(destination,origin)][int(sol[i*2+1])] # sol[1] sol[3] sol[5] ... 집으로 출발
# 출발,도착,운임 순
print ('%10s%10s %5s-%5s $%3s %5s-%5s $%3s' % (name,origin, out[0],out[1],out[2], ret[0],ret[1],ret[2]))
이렇게 해서 sol을 출력해 보면, - 운임은 1000원 단위입니다 - 예로 든 sol은 그냥 잘 출력되는지를 확인하는 예시 sol이니까 말이 안 되어 보여도 넘어가 주세요 -
print(sol)
>
아빠 부산 8:04-10:11 ₩ 95 12:08-14:05 ₩142
엄마 대전 10:30-14:57 ₩290 9:49-13:51 ₩229
언니 청주 17:08-19:08 ₩262 10:32-13:16 ₩139
오빠 마산 15:34-18:11 ₩326 11:08-14:38 ₩262
남친 울릉 9:42-11:32 ₩169 12:08-14:47 ₩231
동생 오산 13:37-15:08 ₩250 11:07-13:24 ₩171
오, 아무렇게나 만든 마구잡이 해답의 의미를 정리해서 읽어보면 아빠는 부산에서 8:04분 것을 타고, 10:11에 서울 도착, 9500원이 들고, 귀갓길은 서울에서 12:08분 것을 타고 14:05에 부산 도착, 14200원이 드네요.
이제 비용함수라는 것을 들여다볼 것인데, 비용함수는 최적화를 통해서 문제를 푸는데 가장 핵심적인 부분입니다. 최적화의 목적이 비용함수가 가장 작은 값을 돌려주는 해답을 찾는데 목적이 있고, 그렇기 때문에 비용함수는 어떤 해답이 얼마나 나쁜지를 표현하는 값을 돌려줘야 합니다. 더 나쁠수록 더 큰 값을 리턴하면 제일 좋겠죠.
가족여행을 위한 최적해를 구하기 위해 비용함수를 설계할 때 감안해야 하는 것들이 있다면,
⓵ 가격 (운임)
⓶ 여행시간
⓷ 대기시간
⓸ 출발시간
등을 고려해서 비용함수를 만들 수 있겠는데, 복잡한 문제애 대한 최적 해답을 찾아야 할 때, 중요한 요소가 무엇인지를 판단해서 더 큰 비용이 될 수 있도록 설계해야 합니다.
그렇다면, 가족 여행 문제에 대한 어떤 해답의 비용은
가격 : 모든 출발, 도착 비행편의 가격
대기 : 모든 사람들이 가장 늦게 도착하는 사람을 기다려야 하니까 그것도 비용으로 처리
뭐 대충 이런 식이 되겠습니다.
이런 식의 비용을 구체적으로 어떻게 계산할 거냐 하면, 해답 sol을 넣었을 때,
- 총운임의 합계
- 서울에서 모두 만나 하이파이브를 할 때까지의 대기시간과 하이파이브한 후의 다시 집으로 출발하기 위해 기다리는 대기 시간을 Cost로 산정
정도를 비용으로 설계하는 것이 합리적인 접근이라고 생각합니다. 자, 그럼 본격 비용함수 구현!
def schedulecost(sol):
totalprice=0
latestarrival=0 # 서울에 가장 늦게 도착
earliestdep=24*60
for d in range (int(len(sol)/2)): # 가족 각각에 대하여
# 서울 도착(outbound) 서울에서 출발(return) 확인
origin=people[d][1]
outbound=flights[(origin,destination)][int(sol[d*2])]
returnflight=flights[(destination,origin)][int(sol[d*2+1])]
# 총 비용은 모든 비행편에 대한 비용 합계
totalprice+=outbound[2]
totalprice+=returnflight[2]
# 가장 늦은 서울 도착과, 가장 빠른 서울 출발을 체크. 도착시간이 현재 가장 늦은 것 보다 더 늦으면 지금 것으로 업데이트
if latestarrival<getminutes(outbound[1]): latestarrival=getminutes(outbound[1])
# 출발시간이 현재 가장 빠른 것 보다 더 빠르면 지금 것으로 업데이트
if earliestdep>getminutes(returnflight[0]): earliestdep=getminutes(returnflight[0])
# 모든 가족은 마지막 사람이 도착할 때 까지 공항에서 기다려야 하고, 다시 출발 시간을 기다려야 함
totalwait=0
for d in range(int(len(sol)/2)):
origin=people[d][1]
outbound=flights[(origin,destination)][int(sol[d*2])]
returnflight=flights[(destination,origin)][int(sol[d*2+1])]
totalwait+=latestarrival-getminutes(outbound[1])
totalwait+=getminutes(returnflight[0])-earliestdep
# 만약 가장 늦은 서울 도착이 가장 빠른 서울 에서 출발보다 늦는다면, Cost를 추가 5만원 정도로
if latestarrival>earliestdep: totalprice+=50
return totalprice+totalwait
# 해당 시간을 Minutes 단위로 구하기 위한 함수
def getminutes(t):
x=time.strptime(t,'%H:%M')
return x[3]*60+x[4]
핵심은 단순하죠. Cost를 설계하다 보니까 추가로 감안한 비용은 가장 늦은 서울도착이 가장 빠른 서울에서 출발보다 늦으면 안 되니까 페널티를 추가해야 한다는 점을 감안합니다.
어쨌든 맨 처음에 예시로 든 마구잡이 solution의 cost가 얼마인지 본다면,
print(schedulecost(sol))
>
4619
로 비용을 볼 수 있겠습니다. 전체 비용이 4,619이군요. 즉, 4,619,000원입니다. 흠. 설계가 잘 된 것 같기도 하고요. - 물론 얼마든지 더 좋은 Cost를 설계할 수도 있습니다. -
비용 함수를 만들었으니, 어떻게 이 비용을 최소화할 수 있을까가 이제부터 관건입니다. 이것이 Optimizer가 해야 할 일이죠.
최적의 해를 구하기 위한 Optimizer 중에서 실제로는 쓸모없지만, 의미를 배울 수 있는 Optimizer로는 randomOptimizer가 있을 수 있겠습니다.
어떤 거냐면, 걍 random으로 solution을 정한 후에 이전거 보다 더 cost가 낮으면 이전 것을 버린 후, 그것으로 정하고 또 random으로 solution을 정한 후에 이전거보다 더 cost가 낮으면 그것으로 정하고 이런 루프를 계속 돌면서 Cost가 가장 작은 최적해를 구해 보는 것입니다.
그러니까, Solution을 찾아내고 그 Solution이 이전에 찾아낸 Solution보다 Cost가 작다면 그 Solution을 best Solution으로 유지하고, 최종적으로 찾아낸 Solution 중에 Cost가 가장 낮은 것을 return 합니다.
def randomoptimize(domain,costf):
best=999999999 # 최악으로 시작
bestr=None
for i in range(0,2000): # 2000번 정도 해봄
# domain에 맞는 random solution을 만들어 봄
r=[float(random.randint(domain[i][0],domain[i][1])) for i in range(len(domain))]
# 방금 정해본 solution r을 cost에 넣어서 cost를 구해봄
cost=costf(r)
# 만약에 만금 구한 cost가 이전 cost보다 더 작으면 best cost를 바꿔침
if cost<best:
best=cost
bestr=r
return r
이렇게 solution을 구해보면 - 순전히 운에 기댄 시도지만 - 어쨌든 이 optimizer에 의한 solution을 구할 수 있습니다. 여기에서 domain은 solution이 가질 수 있는 범위입니다. 데이터를 살펴보면 시간표가 10개씩 이거든요.
# domain은 [(0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9)] 임.
domain = [(0,8)]*(len(people)*2)
solution = randomoptimize(domain, schedulecost)
printschedule(solution)
>
schedulecost(solution) : 4945 # 최종 best cost
아빠 부산 11:16-13:29 ₩ 83 13:39-15:30 ₩ 74
엄마 대전 13:54-18:02 ₩294 10:51-14:16 ₩256
언니 청주 12:08-14:59 ₩149 9:58-12:56 ₩249
오빠 마산 18:23-21:35 ₩134 8:23-11:07 ₩143
남친 울릉 18:48-21:45 ₩246 18:33-20:22 ₩143
동생 오산 7:39-10:24 ₩219 8:04-10:59 ₩136
꺅!, 이런 식으로 나름의 최적해를 구할 수 있습니다. 이것은 여러 번 하면 매번 다른 해가 나올 텐데, random으로 solution을 만들어 내니까 당연한 이야기입니다.
그러면, 여기에서 optimizer가 어떤 일을 하는지 알겠지요? 그러니까, optimizer, cost, solution만 잘 정의하면 최적해라면 어디든지 이용할 수 있는 패턴이라고 할 수 있겠습니다.
random으로 2000씩 시도한 후에 Best Cost를 도출하는 과정을 10번 시도를 해서 본 cost는 둘쭉날쭉합니다. 뭐 어쩔 수 없죠. random이니까요. 당연한 이야기겠지만, 실행할 때마다 결과가 다릅니다.
뭐 이렇습니다. 2000번쯤 하니까 어쨌든 우연히라도 개선이 되긴 되는군요. x축은 iteration 횟수, y축은 cost입니다.
자! 그렇다면 이제 본격적으로 이 Optimizer라는 걸 개선해 볼까 하는데, Optimization 알고리즘을 유전알고리즘을 이용해서 해 보는 겁니다. 바로 전에 유전자알고리즘을 보았으니까 휴, 다행입니다.
Solution = Optimizer(domain, cost)의 이야기 중에 Optimizer가 random이 아니라 조금은 나은 방법으로 이미 살펴보았던 유전알고리즘을 활용하려고 하는 겁니다. 유전알고리즘이 Optimizer인 셈이죠. 유전알고리즘은 이미 구현해 보았으니까, 한 줄이면 갈아치워 집니다.
domain = [(0,9)]*(len(people)*2)
solution = geneticoptimize(domain, schedulecost)
printschedule(solution)
오. 간단하죠? Cost만 제대로 설계를 하면, 곧바로 Optimizer를 갈아 끼워서 문제를 해결할 수 있습니다. 짜잔! Optimizer가 찾아낸 Solution은
solution = [4, 3, 3, 3, 4, 3, 3, 4, 4, 3, 4, 3]
이렇습니다. 흠~
그리고, 이 기계가 찾아낸 솔루션을 print 해 보면, 전체 cost는 2356이고요, 나머지 가족들에 대한 스케쥴표는 다음과 같습니다.
schedulecost(solution) = 2356
아빠 부산 12:34-15:02 ₩109 10:33-12:03 ₩ 74
엄마 대전 10:30-14:57 ₩290 10:51-14:16 ₩256
언니 청주 12:08-14:59 ₩149 10:32-13:16 ₩139
오빠 마산 11:28-14:40 ₩248 12:37-15:05 ₩170
남친 울릉 12:44-14:17 ₩134 10:33-13:11 ₩132
동생 오산 12:18-14:56 ₩172 11:07-13:24 ₩171
어떻게 진화했는지 궁금하니까 100 세대동안 진화하면서 찾아낸 Cost를 보면 다음과 같습니다.
Random Optimizer에 비하면 훨씬 더 좋은 결과 아닌가요? 최종 Cost를 비교해 보면, 4945 VS 2356 이잖아요? 오호호. 훨씬 개선되었네요. 이것도 실행할 때마다 다를 수 있습니다. 왜냐하면 진화를 어떤 식으로 할 거냐에 따라 약간씩은 다른 결과를 가져올 테니까요.
어떤가요? 기계가 어떤 식으로 답을 찾아가는지에 대한 감이 와야 할 것 같은데 말이죠. 다시 한번 정리하면 기계는 최적 Solution을 찾기 위해 답을 찾아가는 Optimization 알고리즘과 그때 얼마나 정답과 다른지에 대한 Cost가 필요합니다. 이것만 알고 있으면 이제부터 다루는 기계학습의 큰 테두리는 맛봤다고 해야 하지 않을까 합니다. 왜냐하면 기계학습에서는 이 Cost를 통계적인 이론을 이용해서 설계하거든요.
이 이야기는 엄청난 내용을 담고 있는 "집단지성 프로그래밍"의 4장의 내용을 재구성하였습니다. 이 책은 엄청난 내용을 담고 있는 것에 비해서 번역이 너무 어렵고, Bug가 너무 많아서 곧바로 실행해 보기 어렵습니다. 이 부분을 감안하여 이해하기 쉽도록 재 구성하고 버그를 수정했습니다. 더 좋은 구성을 상상도 할 수 없기 때문에 이것이 최선이 아닌가 합니다. 흑흑
이런 식으로 여러 가지 조건에서 최적해를 찾아낼 수 있는데, 꼭 머신러닝등에서만 이용되는 것이 아니라, 어디든지 이것을 활용해서 최적해를 구하는 곳에 사용할 수 있겠습니다.
최적해를 찾는 방식이 이렇다면, 이것을 딥러닝에서 똑같이 이용할 수 있습니다. 조금 미리 이야기하자면, 딥러닝에서도 똑같은 term들이 사용됩니다. 예를 들면 optimizer라든가, cost라든가 하는 컨셉입니다. 이번 이야기를 잘 이해만 한다면 그런 것은 optimizer를 어떻게 구현할 것인지, cost를 어떻게 정의할 것인지, solution은 어떤 모양인지를 통해서 문제를 푼다는 점에서 똑같다는 것을 알 수 있을 것입니다.
친절한 데이터 사이언스 강좌 글 전체 목차 (링크) - 
댓글