# -*- coding: utf-8 -*-
from myutil import consolePrintWithLineNumber as c
from myutil import filePrint
'''
Created on 2015. 9. 3.
@author: Administrator
'''
'''
5장 최적화
'''
'''
122p
5-1절 단체여행 - 부제:서울에서 만나요!!!
한국식으로 명칭을 변경한다.
LGA : 서울
BOS : 대전
DAL : 부산
CAK : 군산
ORD : 강릉
OMA : 세종
MIA : 대구
CAK : 전주
도시 구간별로 각 10개의 시간표가 있다.
'''
import time
import random
import math
people = [('아빠', '대전'),
('엄마', '부산'),
('누나', '군산'),
('남동생', '대구'),
('여동생', '강릉'),
('나', '세종')]
# Laguardia
destination = '서울'
total_flights = {}
for line in open('schedule2.txt', 'r', encoding='UTF-8'):
origin, dest, depart, arrive, price = line.strip().split(',')
total_flights.setdefault((origin, dest), [])
total_flights[(origin, dest)].append((depart, arrive, int(price)))
# 6:05 시간대를 분으로 환산 - 나중에 시간대 비교에 사용
def getminutes(t):
x = time.strptime(t, '%H:%M')
return x[3] * 60 + x[4]
c(total_flights)
# 124p 5-2 해답표현하기
def printschedule(r):
for d in range(int(len(r) / 2)): # len(r) / 2 결과가 float이다. 그런데 range(.)함수는 int를 받아야 한다. 그래서 int(.)로 변환하는 코드 추가
name = people[d][0]
origin = people[d][1]
out = total_flights[(origin, destination)][int(r[d])]
ret = total_flights[(destination, origin)][int(r[d + 1])]
c('%10s%10s %5s-%5s $%3s %5s-%5s $%3s' % (name, origin, out[0], out[1], out[2], ret[0], ret[1], ret[2]))
# 1, 4 : 첫번째 사람이 자신에게 해당하는 비행기중 2번째 출국, 5번째 귀국행 비행기를 사용한다.
sol = [1, 4, 3, 2, 7, 3, 6, 3, 2, 4, 5, 3]
printschedule(sol)
# 125p 5-3 비용함수 - 비용을 최소화하자!! - 비용을 수치화한다.
def schedulecost(sol):
total_price = 0
latest_arrival = 0 # 0시(하루의 처음)
earliest_dep = 24 * 60 # 24시(하루의 마지막)
for d in range(int(len(sol) / 2)):
origin = people[d][1]
outbound = total_flights[(origin, destination)][int(sol[d])] # 출국 비행기 정보
returnf = total_flights[(destination, origin)][int(sol[d + 1])] # 귀국 비행기 정보
'''
outbound[0] : 출발시각
outbound[1] : 도착시각
outbound[2] : 가격
'''
total_price += outbound[2] # 가격
total_price += returnf[2] # 가격
if latest_arrival < getminutes(outbound[1]):
latest_arrival = getminutes(outbound[1]) # 가장 늦은 도착(destination에)
if earliest_dep > getminutes(returnf[0]):
earliest_dep = getminutes(returnf[0]) # 가장 이른 출발(자기 origin으로)
'''
공식적인 일정 : 다같이 모였을 때
latest_arrival ~ earliest_dep
예)
도착(latest_arrival) 공식일정(18:10~12:10) 출발(earliest_dep)
아빠 14:10 14:10
엄마 16:10 ---------------12:10
누나 13:10 15:00
남동생 17:00 17:00
여동생 16:20 16:00
나 18:10---------------- 15:20
'''
# 모든 사람은 가장 늦게 공항에 도착하는 사람을 기다려야 한다.
# 또 이들은 출발 비행편을 기다려야 한다.
# 공식일정 이외의 시간들은 기다리는 시간이다.....;;; 이 시간을 최소화 해야 한다.
totalwait = 0
for d in range(int(len(sol) / 2)):
origin = people[d][1]
outbound = total_flights[(origin, destination)][int(sol[d])]
returnf = total_flights[(destination, origin)][int(sol[d + 1])]
totalwait += latest_arrival - getminutes(outbound[1])
totalwait += getminutes(returnf[0]) - earliest_dep
# ??? 항상 True 아닌가? 렌탈 하루 연장??
# latest_arrival - 18:10
# earliest_dep - 12:10
if latest_arrival > earliest_dep:
total_price += 50
# total_price(달러), totalwait(분)
return total_price + totalwait
c(schedulecost(sol))
# 128p 5-4 무작위 검색
def randomoptimize(domain, costfunction):
best = 999999999
bestr = None
for i in range(0, 1000): # 50000으로 하면 best 결과값으로 2855도 나온다.(1000으로 하면 보통 3000...) 낮을수록 좋음
# random.randint(0,8)은 0부터 8까지 정수
r = [float(random.randint(domain[i][0], domain[i][1])) for i in range(len(domain))] # len(domain)는 12
# c(r) # [6.0, 4.0, 1.0, 6.0, 2.0, 2.0, 0.0, 0.0, 4.0, 7.0, 4.0, 6.0]
cost = costfunction(r)
if cost < best:
best = cost
bestr = r # ???
return best, bestr
# (0, 9)은 min, max 범위. 여기서는 사람마다 모두 0,8로 min, max값이 같은 값이지만, 실제로는 사람마다 탈 수 있는 비행기의 시간대 개수가 다르므로 min, max 가 사람마다 다른 값을 가질듯...
domain = [(0, 9)] * (len(people) * 2) # [(0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9)]
best_cost, sol = randomoptimize(domain, schedulecost) # randomoptimize안에 이미 cost 값을 계산하므로 schedulecost 함수를 실행할 필요가 없다.
c(best_cost, sol)
printschedule(sol)
'''
129p 5-5 언덕등반
> 별로 효과를 모르겠다. 실행할 때마다 값이 다르게 나오니...
'''
def hillclimb(domain, costf):
fp = filePrint('output.txt')
# 무작위 해답을 하나 선정
sol = [random.randint(domain[i][0], domain[i][1]) for i in range(len(domain))]
c(sol)
while 1:
neighbors = []
# neighbors 찾기(에러 발생 : list index out of range)
# 원인 : min, max 범위가 잘못되어 있다. 소스 수정함
for j in range(len(domain)):
# domain[j][0]은 0
# domain[j][0]은 9
if sol[j] == domain[j][0]:
neighbors.append(sol[0:j] + [sol[j] + 1] + sol[j + 1:]) # next 이웃
elif sol[j] == domain[j][1]:
neighbors.append(sol[0:j] + [sol[j] - 1] + sol[j + 1:]) # before 이웃
elif domain[j][0] < sol[j] and sol[j] < domain[j][1]:
neighbors.append(sol[0:j] + [sol[j] + 1] + sol[j + 1:]) # next 이웃
neighbors.append(sol[0:j] + [sol[j] - 1] + sol[j + 1:]) # before 이웃
'''
neighbors 를 보면, 12자리의 각 하나씩 +1, -1을 한 값을 가지고 있다.(나머지11자리를 그대로 유지). 총 12*2 = 24개의 리스트이다.
sol이
[7, 3, 4, 3, 6, 4, 6, 1, 2, 7, 4, 7] 이라면,,,
neighbors는
[
[8, 3, 4, 3, 6, 4, 6, 1, 2, 7, 4, 7],
[6, 3, 4, 3, 6, 4, 6, 1, 2, 7, 4, 7],
[7, 4, 4, 3, 6, 4, 6, 1, 2, 7, 4, 7],
[7, 2, 4, 3, 6, 4, 6, 1, 2, 7, 4, 7],
,,,,
]
'''
cost_sol = costf(sol)
best = cost_sol
for j in range(len(neighbors)): # neighbors 리스트의 모든 경우에 대한 cost를 계산
cost_neighbor = costf(neighbors[j])
# fp.c(cost_neighbor)
if cost_neighbor < best:
best = cost_neighbor
sol = neighbors[j]
# neighbors로 cost를 검색해서 개선되지 않은 경우
if best == cost_sol:
break
# if best < 2500: # 가능한가 싶어서 테스트함
# break
return best, sol
best, sol = hillclimb(domain, schedulecost)
c(best, sol)
# 132p 5-6 시뮬레이티드 어닐링
def annealingoptimize(domain, costf, T=10000.0, cool=0.95, step=1):
# 무작위 초기값
sol = [float(random.randint(domain[i][0], domain[i][1])) for i in range(len(domain))]
while T > 0.1:
# 한개의 인덱스 선택
i = random.randint(0, len(domain) - 1)
# 변경할 방향 선택
dir = random.randint(-step, step)
sol2 = sol[:]
sol2[i] += dir
# 범위를 넘어가면 마지막 값으로 매칭
if sol2[i] < domain[i][0]:
sol2[i] = domain[i][0]
elif sol2[i] > domain[i][1]:
sol2[i] = domain[i][1]
ea = costf(sol)
eb = costf(sol2)
p = pow(math.e, (-eb - ea) / T)
# 더 좋거나 확률이 차단 기준 이하인 경우
if (eb < ea or random.random() < p):
sol = sol2
# 온도를 줄인다.
T = T * cool
return sol
sol = annealingoptimize(domain, schedulecost)
c(schedulecost(sol))
'''
134p 5-7 유전자 알고리즘
전혀 수학적이지 않아서 로직을 이해하기는 쉽다.
다분히 우연을 가장했지만.. 나름 성능은 괜찮다.
상위 20%만 기억하고, 나머지는 버리는 씁쓸한 알고리즘이지만... 어쩌겠나...
1등만 기억하는 ㄷㄹㅇ 세상이 생각나네-_-;;;
>
그래서,,, 상위 20%가 아닌 하위 20% 내에서 돌연변이와 교배연산을 시켜보았다. 결과는 나쁘지 않았다....
> 이것이야 말로 개천에서 용나는 격인가???
'''
def geneticoptimize(domain, costfunction, popsize=50, step=1, mutprob=0.2, elite=0.2, maxiter=100):
# 돌연변이 생성(111222333444 -> 118222333444)
def mutate(vec):
i = random.randint(0, len(domain) - 1)
if random.random() < 0.5 and vec[i] > domain[i][0]:
return vec[0:i] + [vec[i] - step] + vec[i + 1:]
elif vec[i] < domain[i][1]:
return vec[0:i] + [vec[i] + step] + vec[i + 1:]
# 교배연산(111222333, 555666777 -> 111222777)
def crossover(r1, r2):
i = random.randint(1, len(domain) - 2)
return r1[0:i] + r2[i:]
# 초기 실험 개체 생성 50개
pop = []
for i in range(popsize):
vec = [random.randint(domain[i][0], domain[i][1]) for i in range(len(domain))]
pop.append(vec)
# 엘리트로 선발할 개체수 선정(50개의 0.2 즉, 50의 20% 를 엘리트로. 10개)
topelite = int(elite * popsize)
# maxiter 진화시킬 세대 수 100, 100회 진화시킴.
for i in range(maxiter):
cost_sol = [(costfunction(v), v) for v in pop if v != None] # pop 안에 None 이 들어있다.왜??
cost_sol.sort()
ranked = [sol for (score, sol) in cost_sol]
# 엘리트 선발(20% 생존)
# pop = ranked[0:topelite]
# 하위 20%를 생존시켜보자
pop = ranked[len(ranked) - topelite:]
while len(pop) < popsize:
if random.random() < mutprob: # mutprob : 개체군의 새로운 멤버에, 교배보다 돌연변이가 발생할 확률 20%
num = random.randint(0, topelite) # topelite : 10
pop.append(mutate(ranked[num])) # 엘리트 10개중 임의 1개 선택해서 돌연변이 1개 생성해서 추가
else:
c1 = random.randint(0, topelite)
c2 = random.randint(0, topelite)
pop.append(crossover(ranked[c1], ranked[c2])) # 엘리트 10개중 2개를 임의 선택해서 교배 1개 생성해서 추가
c(cost_sol[0][0])
return cost_sol[0][1]
# 137p
geneticoptimize(domain, schedulecost)
57 > {('군산', '서울'): [('6:08', '8:06', 224), ('8:27', '10:45', 139), ('9:15', '12:14', 247), ('10:53', '13:36', 189), ('12:08', '14:59', 149), ('13:40', '15:38', 137), ('15:23', '17:25', 232), ('17:08', '19:08', 262), ('18:35', '20:28', 204), ('20:30', '23:11', 114)], ('강릉', '서울'): [('6:05', '8:32', 174), ('8:25', '10:34', 157), ('9:42', '11:32', 169), ('11:01', '12:39', 260), ('12:44', '14:17', 134), ('14:22', '16:32', 126), ('15:58', '18:40', 173), ('16:43', '19:00', 246), ('18:48', '21:45', 246), ('19:50', '22:24', 269)], ('서울', '대전'): [('6:39', '8:09', 86), ('8:23', '10:28', 149), ('9:58', '11:18', 130), ('10:33', '12:03', 74), ('12:08', '14:05', 142), ('13:39', '15:30', 74), ('15:25', '16:58', 62), ('17:03', '18:03', 103), ('18:24', '20:49', 124), ('19:58', '21:23', 142)], ('대구', '서울'): [('6:25', '9:30', 335), ('7:34', '9:40', 324), ('9:15', '12:29', 225), ('11:28', '14:40', 248), ('12:05', '15:30', 330), ('14:01', '17:24', 338), ('15:34', '18:11', 326), ('17:07', '20:04', 291), ('18:23', '21:35', 134), ('19:53', '22:21', 173)], ('서울', '부산'): [('6:09', '9:49', 414), ('7:57', '11:15', 347), ('9:49', '13:51', 229), ('10:51', '14:16', 256), ('12:20', '16:34', 500), ('14:20', '17:32', 332), ('15:49', '20:10', 497), ('17:14', '20:59', 277), ('18:44', '22:42', 351), ('19:57', '23:15', 512)], ('부산', '서울'): [('6:12', '10:22', 230), ('7:53', '11:37', 433), ('9:08', '12:12', 364), ('10:30', '14:57', 290), ('12:19', '15:25', 342), ('13:54', '18:02', 294), ('15:44', '18:55', 382), ('16:52', '20:48', 448), ('18:26', '21:29', 464), ('20:07', '23:27', 473)], ('서울', '군산'): [('6:58', '9:01', 238), ('8:19', '11:16', 122), ('9:58', '12:56', 249), ('10:32', '13:16', 139), ('12:01', '13:41', 267), ('13:37', '15:33', 142), ('15:50', '18:45', 243), ('16:33', '18:15', 253), ('18:17', '21:04', 259), ('19:46', '21:45', 214)], ('대전', '서울'): [('6:17', '8:26', 89), ('8:04', '10:11', 95), ('9:45', '11:50', 172), ('11:16', '13:29', 83), ('12:34', '15:02', 109), ('13:40', '15:37', 138), ('15:27', '17:18', 151), ('17:11', '18:30', 108), ('18:34', '19:36', 136), ('20:17', '22:22', 102)], ('세종', '서울'): [('6:11', '8:31', 249), ('7:39', '10:24', 219), ('9:15', '12:03', 99), ('11:08', '13:07', 175), ('12:18', '14:56', 172), ('13:37', '15:08', 250), ('15:03', '16:42', 135), ('16:51', '19:09', 147), ('18:12', '20:17', 242), ('20:05', '22:06', 261)], ('서울', '강릉'): [('6:03', '8:43', 219), ('7:50', '10:08', 164), ('9:11', '10:42', 172), ('10:33', '13:11', 132), ('12:08', '14:47', 231), ('14:19', '17:09', 190), ('15:04', '17:23', 189), ('17:06', '20:00', 95), ('18:33', '20:22', 143), ('19:32', '21:25', 160)], ('서울', '대구'): [('6:33', '9:14', 172), ('8:23', '11:07', 143), ('9:25', '12:46', 295), ('11:08', '14:38', 262), ('12:37', '15:05', 170), ('14:08', '16:09', 232), ('15:23', '18:49', 150), ('16:50', '19:26', 304), ('18:07', '21:30', 355), ('20:27', '23:42', 169)], ('서울', '세종'): [('6:19', '8:13', 239), ('8:04', '10:59', 136), ('9:31', '11:43', 210), ('11:07', '13:24', 171), ('12:31', '14:02', 234), ('14:05', '15:47', 226), ('15:07', '17:21', 129), ('16:35', '18:56', 144), ('18:25', '20:34', 205), ('20:05', '21:44', 172)]}
67 > 아빠 대전 8:04-10:11 $ 95 12:08-14:05 $142
67 > 엄마 부산 12:19-15:25 $342 10:51-14:16 $256
67 > 누나 군산 10:53-13:36 $189 9:58-12:56 $249
67 > 남동생 대구 9:15-12:29 $225 16:50-19:26 $304
67 > 여동생 강릉 16:43-19:00 $246 10:33-13:11 $132
67 > 나 세종 11:08-13:07 $175 15:07-17:21 $129
133 > 5285
154 > (3553, [4.0, 3.0, 4.0, 3.0, 4.0, 4.0, 1.0, 0.0, 5.0, 0.0, 4.0, 5.0])
67 > 아빠 대전 12:34-15:02 $109 10:33-12:03 $ 74
67 > 엄마 부산 10:30-14:57 $290 12:20-16:34 $500
67 > 누나 군산 12:08-14:59 $149 10:32-13:16 $139
67 > 남동생 대구 11:28-14:40 $248 12:37-15:05 $170
67 > 여동생 강릉 12:44-14:17 $134 12:08-14:47 $231
67 > 나 세종 12:18-14:56 $172 8:04-10:59 $136
165 > [5, 9, 7, 7, 6, 2, 9, 6, 1, 7, 5, 1]
214 > (2868, [7, 6, 7, 6, 6, 7, 6, 6, 1, 7, 5, 1])
249 > 2987
304 > 4138
304 > 4138
304 > 4070
304 > 4035
304 > 4035
304 > 3917
304 > 3793
304 > 3793
304 > 3675
304 > 3616
304 > 3616
304 > 3616
304 > 3616
304 > 3579
304 > 3412
304 > 3412
304 > 3375
304 > 3375
304 > 3324
304 > 3324
304 > 3016
304 > 3324
304 > 3324
304 > 3324
304 > 3324
304 > 3324
304 > 3324
304 > 3324
304 > 3324
304 > 3016
304 > 3016
304 > 3016
304 > 3016
304 > 3016
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
304 > 2789
언덕 등반 결과
'python 및 머신러닝 > 집단지성 프로그래밍' 카테고리의 다른 글
| [Programming Collective Intelligence] - 집단지성 프로그래밍 12장 알고리즘 요약 (0) | 2016.12.09 |
|---|---|
| [Programming Collective Intelligence] - 집단지성 프로그래밍 4장 정리 (0) | 2015.09.04 |
| [Programming Collective Intelligence] - 집단지성 프로그래밍 4장 7절 클릭 학습 (0) | 2015.09.02 |
| [Programming Collective Intelligence] - 집단지성 프로그래밍 2,3,4장 정리 (0) | 2015.09.01 |
| [Programming Collective Intelligence] - 집단지성 프로그래밍 4장 검색과 랭킹 (0) | 2015.08.31 |
