2011 GA Project 1: Traveling Salesman Problem 2011. 3. 21 due: 4월 4일오후 11시 59분 과제개요물류회사의운전기사인철수는배달을위해 명의고객을방문하고회사에돌아와야한다. 각고객의위치는이차원실수좌표 로주어지고두위치사이의거리는실수 으로계산된다 ( ). 고객들의좌표는모두다르고, 회사의좌표와도다르다. 회사에서출발하여 명의고객을모두방문하고회사로돌아오는순환경로 (Hamiltonian cycle) 중가능한짧은것을찾으려한다. Genetic algorithm을이용하여가능하면짧은경로를찾으라. 프로그램은 C 또는 C++ 언어를사용한다. 컴파일러의최적화옵션은 -O3까지만사용할수있다. 불가피하게 Java, Python을사용하는경우에는시간상의불이익을감수해야한다. 여러개의언어를동시에사용하는것도 Makefile만잘만든다면가능하다. 시간제한과 Test 기기환경테스트는학부에서제공된리눅스환경에서수행된다. 해당서버는수강생들에게공개될예정이며, 모든수강생은해당서버에서자신이제출한과제물이올바르게동작함을확인하여야한다. 서버의접속에대한사항은게시판에추후공지될예정이다. 해당서버는가상서버이며, 실제로는한대의물리적서버에여러개의가상화서버가올라가있는상황이다. 따라서굉장히제한된자원만이사용되므로이점에유의한다. 실제개발은별도의개인컴퓨터에서수행하고, 테스트만해당서버에서해보는것이유리할것이다. 테스트가제한된시간동안만이루어지므로, 제한시간안에파일에결과를출력하고정상적으로프로그램을종료해야한다. CPU Cache size : Intel(R) Xeon(R) CPU E5530 @ 2.40GHz (1 core only) : 8192 KB 채점에사용되는컴퓨터의사양은위와같다. 제한시간은문제의크기 에따라다른데, 이 10, 20, 50, 100일때각각 6, 20, 60, 180초로주어진다. 만일프로그램이그이상의시간동안수행될경우에는해당데이터에대해서점수를받을수없다. 시간은 user time 기준이아니라 real time 기준이다. 따라서특히시간측정과관련하여 system call을빈번하게사용하면문제가생길수도있음을염두에두는것이좋다. 프로그램이계산을위하여사용할수있는자원은한개의 CPU core로만제한한다. 따라서직접또는간접적으로멀티스레딩과관련된기법등이들어가거나, GPU등을사용해서는
안된다. 또한프로그램이사용할수있는메모리크기는 512MB 이하이다. 이는별문제가없는부분이지만혹시사용할지모르는특이한방법을금지하기위함이다. 제출한프로그램이위와관련하여문제가생길소지가있다면이를보고서에명시하도록한다. GA의구조제한고객의수 은 1차프로젝트에서는각각 10, 20, 50, 100 중의하나로주어질것이다. 1 차프로젝트에서는순수 GA의틀을벗어나면안된다. 지역최적화 (Local Optimization) 과정이명시적으로포함되어서는안되고, 교차나변이등에서도지역최적화성격의작업이포함되면안된다. 이를명확하게정의하는것은어려운데, 기본적으로교차나변이과정에서해의품질을계산하거나활용할수없다고생각하면된다. 물론선택이나대치에서는얼마든지가능하다. 1차프로젝트는순수한형태의 GA가갖는한계를경험해보라는것이므로결과에대해실망감을좀느껴도좋다. 그렇지만순수 GA로낼수있는최대한의품질은내도록노력하라. 과제물의프로그래밍점수는여러분이제출한 GA가구한해의품질에따라주어진다. 입출력양식입력입력파일의이름은 cycle.in 이다. 이파일은실행파일과같은디렉토리, 정확하게는현재작업디렉토리 (Current Working Directory) 에제공된다. 첫번째줄에는고객의수 이주어진다. 은 10, 20, 50, 100 중의하나다. 그다음줄에는회사위치의좌표가주어지고, 그다음 개의줄에는각고객의위치의좌표가주어진다. 각좌표값 는공백으로분리되어주어지며, 소수점아래둘째자리까지주어질수있다. 출력출력파일의이름은 cycle.out 이다. 이파일은실행파일과같은디렉토리로, 정확하게는 CWD에출력되어야한다. 먼저첫째줄에는자신이제시하는경로의길이를출력한다. 다음줄에는자신이제시하는경로를출력한다. 경로는방문한순서대로도시의번호를출력하도록하며, 도시의번호는입력에서주어진순서대로 1부터 까지이다. 실제경로의길이는 회사 - 해답경로 - 회사 의총길이가됨에유의한다. 출력한경로의길이는참고용으로만사용되므로, 소수점아래로적절한자리수를출력하도록한다. 채점시에는출력한경로에따라서길이를다시계산하여채점에사용한다. 구한경로의길이가짧더라도경로를잘못출력한경우에는점수를받을수없다. 따라서도시의번호를잘못출력하거나중복해서출력하는등의실수를하지않도록유의한다. 입력예
5 4 5.0 0.00 0 4.0 3.0 0 4 2.51 5.0 1.0 5.00 출력예 15.4142 4 5 3 1 2 보고서및 Source Code 제출방법먼저게시판을통해테스트에사용할수있는데이터가각 에대해서제공된다. 보고서에는기본적으로위에서제공된데이터에대한실험결과를모두수록하도록하며, 필요에따라추가적인실험을개인적으로수행하여도좋다. 이와별도로다양한테스트데이터에대해여러분이제출한 source code를컴파일하여위에서명시한수행시간범위에서확인을할것이다. 다양한문제에대한적응력을보려면비슷한문제를직접여러개만들어확인해보는것이좋다. 보고서와소스코드의 due date 는같으므로유의하여야한다. 제출장소 : 302동 313-2호로보고서를출력하여제출소스코드 : 주의사항에따라압축하여 ga_ta@soar.snu.ac.kr로제출 보고서는아래의내용을반드시포함해야하며, A4 여덟페이지이하의논문형식으로작성한다. 글자크기나줄간격등을지나치게조절할경우감점요인이될수있으며, 필요에따라서원하는만큼의부록을첨가할수있다. 부록은기본적으로채점의대상이아니므로, 본문에들어가야할내용을부록으로넣지않도록한다. 1. 사용한 GA의구조 2. 사용한연산자에대한설명 (Selection, Crossover, Mutation, Replacement) 3. 문제의표현 (chromosome design) 4. 각케이스에대하여각 GA를최소 30번수행하여, " 가장좋은결과," " 평균결과," 표준편차 를한테이블에기록하고, 실험환경및사양을명시할것. 5. 실험한데이터중 인데이터에대해대표적인 run을하나정하고, 세대가진행됨에따라 population 내의해들의평균품질과최고품질의모양을 plotting 할것. 6. Discussion( 느낀점, 잘안되는점, 의외의현상, 예상대로된점, 등등 )
소스코드제출을위해서먼저자신의학번으로디렉토리를만들고, 그안에컴파일에필요한모든파일과 makefile을담도록한다. 설치가필요한외부라이브러리 (boost 등 ) 는원칙적으로사용할수없으며, 반드시필요한경우에는컴파일에필요한모든파일을첨부하고관련사항을보고서에기재하도록한다. 첨부한 makefile을이용하여컴파일과실행을모두해볼수있어야하며, 리눅스환경에서문제없이구동되어야한다. Makefile은최소한다음의세가지내용을포함해야한다. 1. make all : 실행에필요한파일들을모두생성한다. 컴파일과관련된모든과정이이를통해이루어져야한다. 여러파일이필요한경우의존성관계를마음대로넣을수있으며, 컴파일최적화옵션은 -O3 까지만사용가능하다. 2. make run : 프로그램을실행한다. 생성된실행파일을실행하는내용을포함해야하며, 현재디렉토리 (.) 가 path에잡혀있지않을수있음에유의한다. 프로그램이실행되면 cycle.in에서입력을읽고, 제한된시간동안프로그램이동작된후, cycle.out에결과를기록한후자동으로종료되어야한다. 3. make clean : 생성된파일을모두지운다. 채점시프로그램을실행할경우환경변화가있을수있으므로, 컴파일작업을다시수행하게된다. 이과정이원만하게이루어질수있도록필요한파일을삭제한다. 채점시에는차례로 make clean, make all, make run을수행하게된다. 세과정중하나라도정상적으로수행되지않을경우감점요인이된다. 시간측정은 time make run의형태로이루어질예정이므로참고하도록한다. 위와같이프로그램과 Makefile을정리한후, 학번을파일명으로하여 zip 또는 tar(+gz) 형식으로압축한다. 그후, 자신의학번을제목으로하여조교에게이메일로제출한다. 메일내용에는자신의학번과이름을반드시포함한다. 보고서제출을증명하기위해보고서파일을함께첨부하는것을권장하며, 이경우에는반드시 PDF로제출하도록한다. 특이폰트를사용하는경우반드시임베딩하도록한다. 채점방식기본적으로보고서와프로그램이각각 1:1의비율로반영된다. 둘모두상대평가에의해점수가부여될수있으며, 특히프로그램의경우에는여러분의프로그램이구한해의품질에따라점수차이가크게벌어질수있다. 단, 첫번째과제의경우에는순수 GA의특성을감안하여기본점수의비중을높게부여한다. 이후과제에서는점수차이가늘어날예정이다. 보고서는앞에서언급한필수적인내용을모두갖춘경우기본점수를받게된다. 좋은실험내용이나논의사항이포함된경우, 각각의품질에따라추가점수를받을수있다. 역으로, 내용이부실한경우등에는그정도에따라감점이있을수있다. 보고서는우리말로작성하는것을원칙으로한다. 위와같이채점한후, 가장우수한보고서가만점이되도록
점수가조정된다. 프로그램은준비된여러개의테스트데이터에대해서여러분의프로그램이구한해의품질에따라평가된다. 각케이스마다프로그램은한번수행된다. 프로그램이제한시간을초과하여수행된경우, 출력의형식이나내용이잘못된경우에는그케이스에대해서 0점을받게된다. 그외의경우에는각케이스에대해서가장좋은품질의해가만점을받게되며, 다른해는그품질의차이에따라부분점수를받게된다. 부분점수는품질차이의절대치와상대치 ( 비율 ) 에따라부여된다. 외부프로그램도경쟁에포함될수있다. 주의사항 * 타인의 source code는절대보지말것. 자동 Copy detection program에의하여카피를판별한후원본과복사본공히 0점처리한후최종학점에서한 grade 강등함. 일부든전부든모두카피로처리함. Source code copy 후변경도 detection 됨. 선배들의 source code도비교대상임. * 절대로보고서에 30회의수행결과를일일이기록하지말것. 평균, 표준편차등의통계치로충분함. 쓸데없는 detail로보고서를채울경우감점요인이됨. * 수강생이많은관계로프로그램채점의많은부분이자동적으로이루어질예정이다. 수강생의실수로인해예외적인상황이발생하여전체채점이지연될경우큰감점요인이될수있다. * 과제물을늦게제출한경우, 조교에게최종적으로도착한시간을기준으로매 24시간마다 20% 씩감점된다. 이메일이반송된경우, 첨부파일이누락된경우, 각종파일의형식이나이름이맞지않는경우등에는다시제출하는것이가능하다. 이때에는위의딜레이규정에따라늦게제출한과제물로처리될수있다. 여러번제출하는것이가능하며, 채점및규정적용은제일마지막제출물에따라처리된다. 보고서와프로그램을따로제출할수있으며, 각각에대해따로딜레이규정을적용한다.