[Programming Collective Intelligence] - 집단지성 프로그래밍 4장 정리

5.최적화
    5-1. 단체 여행

    5-2. 해답 표현하기

여러 다양한 최적화 기법을 적용 가능하도록 자료구조를 표현하는 것은 어찌보면 가장 중요하다.

우선 랜덤으로 표현이 가능해야 한다. 즉, 숫자로 표현이 되어야 한다. 그리고 랜덤으로 생성할 숫자의 범위도 집합으로 존재해야 한다.

 

[1,4,3,2,7,3,6,3,2,4,5,3]

0에서 9까지의 숫자 집합. 12개이다.

12는 6명*2개(출국행,귀국행)을 의미하고

0에서 9는 출국행의 가능성이 10개임을 의미한다.

 

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)]

도메인은 위의 가능성의 랜덤범위를 설정해 줄 수 있다. 실상 모든 사람에게 각 10개의 비행기편을 선택할 가능성이 있지는 않기 때문에

    5-3. 비용 함수
        비용을 결정하는 것도 중요하다.

        해답을 이용해서 비용을 결정해보는 것.

        고려사항을 결정하는 것 : 가격, 여행시간, 대기 시간(소모되는 시간), 출발 시간, 자동차 렌탈 시간 등등

    5-4. 무작위 검색

         랜덤으로 해답을 표현하는 것 -> 컴퓨터 성능이 엄청나게 뛰어나면 10^12 = 1조의 경우의 수를 다 체크해보면 된다. 밑에 여러 알고리즘을 할 필요도 없다. 하지만..ㅜ
    5-5. 언덕 등반

         랜덤으로 해답을 표현해 보고, 해답을 임의 변경해보는 것.(가장 근접한 이웃 데이터로...)
    5-6. 시뮬레이티드 어닐링

         p = e ^ ((-highcost + lowcost) / temperature)

         책에 쓰여진 수학 공식과 책에 나와있는 파이썬 소스가 다르다.(부호가 다름) 무엇이 맞는지 모르겠다-___-;;

         파이썬 소스

         p = pow(math.e, (-eb-ea) / T)

         알고리즘의 핵심은...

             국소 최소점 문제를 벗어나기 위해

             좋은 해답을 찾아가는 것이 아니라

             아주 나쁜 해답들에 비해 덜 나쁜 해답들을 선호하는 것이다.

         이것이 과연 의미있는 과정인지는 모르겠다.;;;;;
    5-7. 유전자 알고리즘

         좋은 성능을 내는 해답 中, 돌연변이와 교배를 이용해서 더 좋은 결과가 나타나길 바라는 마음이다.

    5-8. 비행편 검색 실제
    5-9. 선호도 최적화
    5-10. 네트워크 시각화
    5-11. 다른 가능성들
    5-12. 함께 풀어보기