선호도 최적화

 앞서 최적화로 해결할 수 있는 문제에 대한 예를 보았다. 하지만 전혀 관련이 없어보여도 동일한 방법을 사용할 수 있는 문제들이 많이 있다. 

 최적화 요건으로 문제를 풀기위해 필요한 조건

 1. 문제가 정의된 비용 함수를 가지는지 -> 비용함수를 구할 수 있는지

 2. 유사한 해답이 유사 결과를 내는지 -> 입력값에 따라 합리적인 결과가 도출되는지

 이런 속성을 가진 모든 문제를 최적화로 다 풀 수는 없지만 전혀 생각치 못한 흥미로운 결과를 최적화를 통해서 얻어낼 수 있다!

 

 이번에는 최적화 결과를 내는 다른 문제를 살펴본다. 제한된 자원을 선호를 표현한 사람들에게 분배하여 가능한 모두 행복하게 하는 방법을 찾는 문제를 생각해보자.

 

 학생 기숙사 최적화 

 학생들을 그들의 1지망, 2지망 선택을 반영해서 기숙사에 배치하는 문제다. 이를 여러 다른 문제에도 적용해볼 수 있다. 일의 분배나 선수 배치 즉, 개인에게 정보를 받고 결합하여 최적 결과를 만드는 용도가 그런 것이다.

 

 이 문제는 다섯 개의 기숙사가 있고 각각 두 개의 공간이 있어 학생 열명이 이 공간을 가지고 경쟁해야하는 상황이다. 각 학생은 1지망, 2지망 선택을 한다.

 

import random
import math

# 두명을 수용할 수 있는 기숙사들
dorms=['Zeus','Athena','Hercules','Bacchus','Pluto']

# 1,2지망을 선택한 사람들 목록
prefs=[('Toby', ('Bacchus', 'Hercules')),
       ('Steve', ('Zeus', 'Pluto')),
       ('Karen', ('Athena', 'Zeus')),
       ('Sarah', ('Zeus', 'Pluto')),
       ('Dave', ('Athena', 'Bacchus')), 
       ('Jeff', ('Hercules', 'Pluto')), 
       ('Fred', ('Pluto', 'Athena')), 
       ('Suzie', ('Bacchus', 'Hercules')), 
       ('Laura', ('Bacchus', 'Hercules')), 
       ('James', ('Hercules', 'Athena'))]

 

 

def printsolution(vec):
    slots=[]
    
    #각 기숙사 마다 방을 2개씩 만듬
    for i in range(len(dorms)):
        slots+=[i,i]
        
    #루프를 돌면서 학생들을 배정함
    for i in range(len(vec)): #i: 0,1,2, ... ,9
        x = int(vec[i])
        print(x)
        #남은 것 중에 방을 선택함
        dorm=dorms[slots[x]]
        print(dorm)
        #학생과 배정받은 기숙사를 출력
        print(prefs[i][0], dorm) #이름, 긱사
        #배정된 방을 제거함
        del slots[x]
        
#[(0,9), (0,8), ... ,(0,0)]
domain=[(0,(len(dorms)*2)-i-1) for i in range(len(dorms)*2)]


def dormcost(vec):
    cost=0
    #방 목록을 생성함
    slots=[0,0,1,1,2,2,3,3,4,4]
    
    #각 학생별로 루프를 돔 
    for i in range(len(vec)):
        x=int(vec[i])
        dorm=dorms[slots[x]]
        pref=prefs[i][1] #1,2지망
        #1지망 비용0, 2지망 비용1, 1/2지망 비용 3
        if pref[0]==dorm: cost+=0
        elif pref[1]==dorm: cost +=1
        else: cost +=3 
        
        #배정한 방을 삭제함
        del slots[x]
        
    return cost
    
    

 

from python import dorm
from python import optimization
s=optimization.randomoptimize(dorm.domain, dorm.dormcost)
dorm.dormcost(s)

#결과: 16

 

dorm.printsolution(s)

 

dorm.dormcost(s)
#결과: 10

s=optimization.annealingoptimize(dorm.domain, dorm.dormcost)
dorm.printsolution(s)

시뮬레이티드 어닐링을 가져다 쓴결과 위처럼 비용함수값도 적게 나오고 결과도 조금 더 낫게 나온듯 하다. 아쉽게도 아래의 유전자 알고리즘을 적용하는데 에러가 살짝나서 결과를 알 수 없었다. 

 

optimization.geneticoptimize(dorm.domain, dorm.dormcost) #디버깅필요

 

도메인을 계속 같은 형식으로 일치시켜주고, 해답 또한 리스트 형식으로 계속 일치 시켜주어서, optimization.py에 있는 함수를 가져다가 그대로 적용해볼 수 있다. 중요한 부분이다.

 

 

 

가장 중요한 단계는 해답 표현과 비용함수를 결정하는 것이다.

이거만 할 줄 알면 어디든 적시적소에 알맞게 최적화를 사용할 수 있다. 정말 훌륭한 기술이고 어느 곳에서나 이러한 최적화 방법을 사용하고 싶어하기 때문에 훈련을 해야한다. 뭐랄까 알고리즘이나 코딩연습등을 하면서 유사 문제나 혹은 실생활에서 적용할 만한 것을 창의하여 해답을 찾는 연습이 필요하다고 생각한다.