operator01.jpg


안녕하세요? 교주 LGS입니다.
오늘은 GA를 요리조리 맛있게 요리해 봅시다요~ o(^o^)o (GA에 관한 기본적인 설명은 여기를 참조하세요)
(본 강좌는 '멕렉렉' 님의 질문에 대한 답변이기도 합니다.)

GA를 가지고 놀다보면 종종 Selection(개체선택), Crossover(유전자 교환), Mutation(돌연변이) 등이  
MATLAB GA Toolbox가 기본적으로 제공하는 방법만으로는 해결되지 않는 경우가 있습니다.
그 한 예로 유명한 Traveling Salesman Problem이란 것이 있습죠.
GA0302.png
(이미지 출처: MATLAB Help Browser)

자~ 지금부터 여러분은 판매사원입니다. ^^  여러분에게 하달된 첫 임무는 미국 전역을 돌면면서 제품을 판매, 홍보하는 일입니다.
회사는 여러분에게 1달의 시간과 10만 달러의 경비를 주었습니다.
여행 스케줄을 잘 짠다면(즉 어떤 순서로 도시를 방문 할까를 잘 정한다면) 15일만에 모든 도시를 다 돌고  (임무 성공)
남은 시간과 돈으로 아릿다운 여성(또는 멋진 남자)와 즐거운 시간을 보낼 수도 있을 것이구요~ 예~ o(^o^)o
스케줄을 잘못 짜면 시간은 시간대로, 돈은 돈대로 날리고, 고생은 고생대로 하겠죠? -_-;;
잘못하다가는 한달안에 임무를 완수하지 못할 수도 있습니다. (비키니 여성이여 바이바이 ㅠㅠ)

그렇다면 어떻게!! 가장 짧은! 가장 효율적인! 최적의! 경로를 찾아낼 수 있냐이말이죠...
Optimization(최적화) 문제를 만나면 뭐라구요? 넵 (컴퓨팅  환경이 좋다면) 그냥 무조건 GA를 돌리시면 되죠? ㅋㅋ
우리의 GA는 그 어떠한 복잡, 괴기, 난해한 문제도 풀 수 있습니다.

그런데요... 씁... Traveling Salesman Problem의 경우 약간 생각할 부분이 있습니다.
통상의 경우 GA(또는 다른 optimization 기법)의 목적은 Cost function을 가장 작게하는 parameter의 값를 찾아내는 거잖아요?
머그컵의 예에서 보셨듯이 보통의 경우는 design variable(설계변수)의 값을 찾아내는 것이 목적입니다.
그런데 세일즈맨 문제는?? 넵 값이 중요한게 아니라 도시 방문 순서가 중요하죠?

예를 들어를 MATLAB에서 기본적으로 제공하는  Mutation(돌연변이) 방법(Gaussian, Uniform 등) 으로는
세일즈맨 문제를 풀 수 없습니다.(기본 제공 mutation 방법만으로는 풀기가 매우 어렵습니다.)

GA0301.png

도시를 방문하는 순서를 서로 바꿀 수는 있어도 도시 자체를 돌연변이를 시킬 수는 없습니다. 
뉴욕과 캘리포니아의 방문 순서를 바꿀 수는 있어도 캘리포니아를 뉴욕으로 돌연변이 시킬수는 없다는 말입니다요.
만약 캘리포니아를 뉴욕으로 돌연변이시킨다면 캘리포니아를 방문하지 못하므로 임무 실패입니다. ㅜㅜ
그림으로 나타내면 아래처럼 될거구요.

GA0303.png
그럼?? MATLAB 기본 제공 mutation 방법 말고 특별한 방법으로 돌연변이(mutation)을 시켜야 합니다.
즉 나만의 방법으로 돌연변이를 일으키고 싶다면 Mutation에 대한 Custom function을 직접 작성해주시면 된다~ 이 말이죠. 
이해가셨죠? ^^ 오늘은 여러분이 직접 mutation, crossover, creation 함수를 만들어 GA를 돌려 보겠다는 이야기!!

자~ 본격적으로 Customized GA에 대해서 알아봅시다요~ 허잇, 퉁!

(중략)

우선 진화시킬 population을 만드는 custom function을 만들어 봅시다.

GA0307.png

(중략)

다음으로 crossover(유전자교환)와 mutation(돌연변이)에 대한 custom function을 만들어 줍시다.
(다시한번 말씀드리지만 지금 우리가 이렇게 따로 각각의 custom function을 만들어주는 이유는 
MATLAB 기본 제공 create, crossover, mutation 함수만으로는 풀고자하는 문제를 표현할 수 없기 때문입니다.
통상의 경우는 fitness function만 작성해주시면 끝이예요~)

GA0309.png

(중략)

GA0314.png

유후~ 15일만에 임무를 완수하고 비키니 여성과 해변을 걸읍시다요.~ 케케
실제로 위의 Traveling Salesman Problem을 푸는 GA가 물류 등의 현장에서 쓰이고 있습니다.
예를 들어 수십대의 조립 기계가 있는 공장에서 부품을 나르는 AGV(Auto Guided Vehicle 자동으로 움직이는 자동차라고 생각하시면 됩니다.)의
경로를 최적화 할 때 GA를 사용합니다.

(이하생략)

생략된 본문 내용은 VIP 게시판에서 확인 가능합니다.
http://www.matlabinuse.com/index.php?mid=VIP_ONLY&page=1&document_srl=21466
profile