[Programming Collective Intelligence] - 집단지성 프로그래밍 5장 최적화

# -*- 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

언덕 등반 결과