DBPIA-NURIMEDIA

Size: px

Start display at page:

Download "DBPIA-NURIMEDIA"

광식 계
7 years ago
Views:

1 74 선호도기반최단경로탐색을위한휴리스틱융합알고리즘옥승호외 논문 TC-8-11 선호도기반최단경로탐색을위한휴리스틱융합알고리즘 (A Combined Heuristic Algorithm for Preference-based Shortest Path Search ) 옥승호 *, 안진호 **, 강성호 ***, 문병인 **** * (Seung-Ho Ok, Jin-Ho Ahn, Sungho Kang, and Byungin Moon ) 요 약 본논문에서는개미군집최적화 (Ant Colony Optimization; ACO) 및 A* 휴리스틱알고리즘이융합된선호도기반경로탐색알고리즘을제안한다. 최근 ITS (Intelligent Transportation Systems) 의개발과함께차량용내비게이션의사용이증가하면서경로탐색알고리즘의중요성이더욱높아지고있다. 기존의 Dijkstra 및 A* 와같은대부분의최단경로탐색알고리즘은최단거리또는최단시간경로탐색을목표로한다. 하지만이러한경로탐색결과는더안전하고특정경로를선호하는운전자를위한최적의경로가아니다. 따라서본논문에서는선호도기반최단경로탐색알고리즘을제안한다. 제안된알고리즘은주어진맵의링크속성정보를이용하며, 각링크에대한사용자선호도는내비게이션사용자에의해설정되어진다. 제안된알고리즘은 C 로구현하였으며, 64 노드및 118 링크로구성된맵에서다양한파라미터를통해성능을측정한결과본논문에서제안한휴리스틱융합알고리즘은선호도기반경로뿐만아니라최단경로탐색에도적합함을알수있었다. Abstract In this paper, we propose a preference-based shortest path algorithm which is combined with Ant Colony Optimization (ACO) and A* heuristic algorithm. In recent years, with the development of ITS (Intelligent Transportation Systems), there has been a resurgence of interest in a shortest path search algorithm for use in car navigation systems. Most of the shortest path search algorithms such as Dijkstra and A* aim at finding the distance or time shortest paths. However, the shortest path is not always an optimum path for the drivers who prefer choosing a less short, but more reliable or flexible path. For this reason, we propose a preference-based shortest path search algorithm which uses the properties of the links of the map. The preferences of the links are specified by the user of the car navigation system. The proposed algorithm was implemented in C and experiments were performed upon the map that includes 64 nodes with 118 links. The experimental results show that the proposed algorithm is suitable to find preference-based shortest paths as well as distance shortest paths. Keywords : Shortest path search, navigation, ant colony optimization, A* algorithm, heuristic algorithm * 정회원, 경북대학교전자전기컴퓨터학부 (School of Electrical Engineering and Computer Science, Kyungpook National University) ** 정회원, 호서대학교전자공학과 (Department of Electronic Engineering, Hoseo University) *** 평생회원, 연세대학교전기전자공학과 (Department of Electrical and Electronic Engineering, Yonsei University) **** 평생회원, 경북대학교전자공학부 (School of Electronics Engineering, Kyungpook National University) 본논문은지식경제부산업기술개발사업으로지원된연구결과임 ( 과제번호 : ). 접수일자 : 2010년5월27일, 수정완료일 : 2010년8월13일 (716)

2 2010 년 8 월전자공학회논문지제 47 권 TC 편제 8 호 75 Ⅰ. 서론경로탐색알고리즘은교통시스템, 통신네트워크, 운송시스템은물론이동로봇의경로설정등다양한분야에사용되는알고리즘으로써, 최근 ITS (Intelligent Transportation Systems) 의개발과함께차량용내비게이션의사용이증가하면서경로탐색알고리즘의중요성이더욱높아지고있다 [1~2]. 현재차량용내비게이션은멀티미디어및정보통신기술의결합과함께다양한기능및정보를사용자에게제공하고있으며, 이러한기능과정보를사용해서목적지점까지의최단경로를탐색하는것이내비게이션시스템의핵심기능이다. 그동안 Dijkstra, A* 및휴리스틱알고리즘등다양한최단경로탐색알고리즘이적용된차량용내비게이션시스템이연구되었다 [2~5]. Sara Nazari 등은 Dijkstra 알고리즘에사용되는많은량의메모리및연산량을줄이기위해경로탐색영역을제한하는수정된 Dijkstra 알고리즘을제안하였다 [2]. Hao Yue 등은 A* 알고리즘을사용하여동적교통환경에서실시간경로탐색이가능한시스템을제안하였으며 [3], M. Noto 및 H. Sato는짧은시간내에 Dijkstra 알고리즘의성능에가까운최단경로탐색결과를얻는방법을제안하였다 [4]. 하지만기존의경로탐색알고리즘은대부분이최단거리및최소비용탐색을위한알고리즘으로써, 최근사용자의선호에따른경로탐색이중요해지면서최단경로가아닌사용자및특정상황에최적화된최적경로탐색에대한연구가필요하게되었다. 이에본연구에서는선호도에기반을둔경로탐색알고리즘을제안한다. 본논문의 Ⅱ장에서는기존의경로탐색알고리즘에대해간단히살펴보며, Ⅲ장에서는선호도기반경로탐색알고리즘을제안한다. 이후 Ⅳ장에서제안된알고리즘의구현및다양한성능측정결과에대해논하며, 이후 Ⅴ장에서본논문의결론을맺는다. Ⅱ. 경로탐색알고리즘기존의 dijkstra 등과같이 polynomial time의시간복잡도를가지는최단경로탐색알고리즘은노드의수가증가함에따라경로탐색시간이오래걸리는단점이있다. 이에본연구에서는최단경로탐색문제를 NP-complete 문제로보고노드의수가증가하더라도빠른시간내에적절한경로를탐색하는휴리스틱알고 리즘인 ACO 및 A* 를사용하여선호도기반최단경로를탐색한다. ACO 및 A* 는 NP-complete 문제를해결하기위한휴리스틱알고리즘이기때문에시간복잡도를다항시간으로나타낼수는없다. 본장에서는기존의가중무향그래프 (weighted undirected graph) 모델에서각링크의가중치및휴리스틱정보를기반으로최단경로를탐색하는알고리즘인 ACO 및 A* 에대해간략히설명하고, 각알고리즘의특징에대해서살펴본다. 1. Ant Colony Optimization 알고리즘 Dorigo 등에의해제안된개미군집최적화 (ACO) 알고리즘은개미군집의형태를모방하여최적화문제를해결하는생물학적기반의메타휴리스틱접근법이다 [6~9]. 군집에속한개미들은목표지점을찾아가는동안페로몬 (pheromone) 이라는물질을분비하는데, 이러한페로몬은시간이지남에따라일정하게증발하는특징이있다. 따라서페로몬은목표지점까지의최단경로에많이누적되는특징이있으며, 군집에속한다른개미들에게최단경로를알리는정보로사용된다. 최초의개미알고리즘은 Dorigo 등에의해개발된개미시스템 (ant system; AS) 알고리즘이며 [6], AS 알고리즘의성능을개선한알고리즘이개미군집시스템 (ant colony system; ACS) 알고리즘이다 [7]. ACS 알고리즘은기존의 AS 알고리즘과다른노드전이규칙 (node transition rule) 및페로몬업데이트규칙이사용되고, 지역페로몬업데이트규칙및노드후보리스트 (candidate lists) 의사용이가장큰차이점이다 [8~9]. ACS 알고리즘에서노드 i에위치한, 개미 k는수식 (1) 을사용해서다음노드 j를선택한다. (1) 여기서 는개미 k가노드 i에서선택가능한노드들의집합을나타내며, 는노드 i와 j를연결하는링크의페로몬을나타낸다. 그리고 는휴리스틱함수로써일반적으로노드 i, j사이거리의역수로정의된다. 는휴리스틱함수의지수를나타내는파라미터로써양의실수로설정된다. 은 [0, 1] 사이의랜덤값이며, 는노드선택방법의확률을결정하는파라미터값이다. 만약 인경우는노드 i에서노드 j로이동할때페로몬및휴리스틱함수를이용해서선험적인정보를이용하여노드를선택한다. 반면 인경우개 (717)

3 76 선호도기반최단경로탐색을위한휴리스틱융합알고리즘옥승호외 미는확률함수 (2) 를통해확률적으로노드를선택하기때문에페로몬및휴리스틱값이큰노드가선택될가능성이높다. 하지만선험적인정보에만의존해서노드를선택하지않기때문에개미들은다양한경로를탐색할수있다. (2) ACS 알고리즘은기존의 AS 알고리즘과는달리최단거리를찾은개미의경우에만전역페로몬업데이트 (global pheromone update) 규칙 (3) 을사용해서자신의경로에페로몬을증가시킨다. 은페로몬증발량을결정하는파라미터로써 (0, 1) 사이의값으로설정되며, 는링크 i, j 사이에누적되는페로몬양을나타낸다. (3) ACS는각개미가지나가는모든링크를지역페로몬업데이트 (local pheromone update) 수식 (4) 를사용해서페로몬을증가시킨다. (4) 수식 (4) 에서 은페로몬증발량을결정하는파라미터로써 (0, 1) 사이값으로설정되며, 는양의실수값으로써페로몬갱신양을나타낸다. 2. A* 알고리즘 A* 알고리즘은 ACS 알고리즘과달리목표지점까지의일직선거리값을휴리스틱함수로사용하여목적지까지의최단경로를찾는알고리즘이다 [4]. A* 알고리즘은수식 (5) 를이용해현재노드에서 F 값이가장작은노드를연속적으로선택함으로써목표노드를찾아나가는알고리즘이다. (5) 수식에서 F는적합도 (fitness) 를나타내며, G는목표 (goal) 를의미하는값으로써시작노드부터현재노드까지의누적된비용을나타낸다. 그리고 H는휴리스틱 (heuristic) 을의미하는값으로써현재노드에서목표노드까지의추정된비용을나타내며, 일반적으로 H는현재노드에서목표노드까지의일직선거리값으로설정된다. Ⅲ. 선호도기반경로탐색알고리즘본장에서는기존의최단경로탐색알고리즘인 ACS 및 A* 알고리즘의한계를살펴보고, 두알고리즘의장점이융합된선호도기반경로탐색알고리즘을제안한다. 선호도기반경로탐색알고리즘은기존의가중무향그래프의각링크마다선호도및비선호도값이할당된새로운그래프모델에서선호도를기반으로최단경로를탐색하는알고리즘이다. 1. 기존경로탐색알고리즘의한계기존의 ACS 및 A* 알고리즘은최단경로를탐색하는알고리즘으로써, 사용자의선호도에기반을둔경로탐색알고리즘으로는부적절하다. 이는기존의 ACS 알고리즘은각링크의거리값을휴리스틱함수로사용하며, A* 알고리즘은현재노드부터도착노드까지의일직선거리를휴리스틱함수로사용하기때문이다. 각알고리즘의특징을살펴보면, ACS 알고리즘의경우파라미터변화에따라성능변화가심하기때문에최단경로탐색결과가 sub-optimal 할수있으며, 노드의수가증가할수록경로탐색을위한연산이증가하는문제가발생한다. 그리고 A* 알고리즘은 Dijkstra 알고리즘과는달리모든노드를탐색하지않기때문에최단경로를보다빠르게탐색하는특징이있지만, 선호도기반경로탐색시 sub-optimal 한경로를탐색하는문제를가진다. 다음 2절에서는이러한문제를간단히살펴본후휴리스틱융합알고리즘을제안한다. 2. 휴리스틱융합경로탐색알고리즘제안 A* 알고리즘은그림 1과같은맵에서최단경로를찾지못한다. 그림 1에서각링크옆의수는링크의거리 (distance) 를의미하며, 시작노드는 0, 도착노드는 15 이다. 참고로각노드들의위치는실제기하학적지리위치와는다르다. A* 알고리즘은 1점쇄선으로표시된 (0 -> 7 -> 10 -> 15) 의경로를출력하며, 이때총거리는 51이된다. 하지만실제최단경로는 (0 -> 1 -> 11 -> 15) 이며, 이때총거리는 34가된다. 이와같이 A* 알고리즘이선호도기반최단경로를탐색하지못하는이유는 1번노드를다음현재노드로선택하지못하기때문이다. 즉, A* 는이웃노드까지의비용 (G) 및휴리스틱 (F) 의합을기준으로다음현재노드를설정하는데, A* 의경우 1번노드까지의 G 값이 (718)

4 2010 년 8 월전자공학회논문지제 47 권 TC 편제 8 호 77 : distance of link (i, j) : path of the kth ant : path of best ant in each iteration : current best path of ACO Loop : cost of path x initialize parameters; place all ants to the source node; // Try Loop repeat (0 ~ MaxTry); ; ( ) 그림 1. 링크의선호도가포함된맵 Fig. 1. Map that contains the preference of the links. 크기때문에 F 값이커지고, 따라서 1번노드를현재노드로설정하지못한다. 이외에도 A* 알고리즘이 1번노드를현재노드로설정하지못하는이유는선호도가반영된맵임에도불구하고, 휴리스틱값을현재노드와목표노드의일직선거리로설정하기때문이다. 결론적으로 A* 는현재노드를중심으로최단경로탐색이이루어지기때문에 1번노드를현재노드로설정하지못할경우선호도가반영된맵에서최적경로탐색이불가능하다. 하지만 A* 알고리즘에서 (0 -> 1) 링크의거리가일정값이하로감소되면, 1번노드가현재노드로설정될수있고, 따라서상기실제최단경로를찾을수있다. 본논문에서는이러한문제를변형된 ACS 알고리즘을적용하여해결한다. ACS 알고리즘에서는확률에기초하여개미들이여러경로를탐색하기때문에, (0 -> 1) 링크를포함하는경로를찾는개미가존재할수있다. 개미들이찾은경로중에서최소비용경로에속하는링크들에대해서는거리를감소시키고 (ACS 알고리즘에서페르몬을증가시키듯이 ), 다시 A* 알고리즘에의한경로탐색을수행하도록함으로써, (0 -> 1) 링크를포함하는최단경로를찾을수있게한다. 추가적으로, 제안되는알고리즘은링크의선호도개념을사용함으로써, 선호도에기반한경로를찾을수있도록한다. 변형된 ACS 알고리즘은개미들이선호도가높은링크를선택할가능성을높이고, 경로의비용계산시에도선호도가높은링크에대해서는비용을감소시킨다. 이 = A* algorithm( ); if return ; // ACO Loop repeat (0 ~ MaxACO); for each ant k = 1,, do ; repeat if then choose from candidate list; choosing j using the rule (6); else choosing j using the rule (7); end else choose using the rule (7); end until full path has been constructed ; end select ; if then for each link do end end (719)

5 78 선호도기반최단경로탐색을위한휴리스틱융합알고리즘옥승호외 until number of MaxACO; // End of the ACO Loop = A* algorithm( ); return as the solution until number of MaxTry; // End of the Try Loop 그림 2. 선호도기반최단경로탐색알고리즘의사코 드 Fig. 2. Pseudo code of preference-based shortest path search algorithm. 렇게함으로써, 선호도가높은링크들로이루어진경로는최소비용경로선택되고, 여기에속하는링크들의거리는감소한다. 앞에서도설명하였듯이, 다시 A* 알고리즘에의한경로탐색시에는선호도가높은링크들을포함하는경로를탐색하게된다. 이경우변형된 ACS 알고리즘은최단경로로수렴할필요가없기때문에많은연산이필요하지않으며, 뛰어난적응성을가 지기때문에동적특성을가지는환경에매우적합한알고리즘이다. 그림 2는제안하는알고리즘의의사코드 (pseudo code) 를나타낸다. 알고리즘동작시초기화파라미터로는개미의수 ( ), 노드선택기준값 ( ), 휴리스틱함수의지수 ( =0), 최대 MaxTry 및 MaxACO 가있다. 그리고모든개미의출발지는시작노드로설정된다. 알고리즘의초기파라미터가설정된후각링크의페로몬은주어진맵의각링크거리값으로초기화되며, A* 알고리즘은초기화된페로몬을사용하여최단경로를탐색후 를설정한다. Try Loop의첫번째 iteration 에서는선호도가반영되지않은최단경로탐색결과를출력하고 ACO Loop 수행없이다음 iteration으로넘어간다. 그림 2의 ACO Loop 에서는모든개미가노드선택수식 (6) 및 (7) 을사용해서도착노드까지의경로를탐색해간다. 수식 (7) 에서페로몬과휴리스틱함수의역수가사용된이유는초기페로몬이링크의거리값으로설정되고, 휴리스틱함수는수식 (8) 과같이정의되기때문이다. 수식 (8) 에서링크의선호도및비선호도는사용자의설정에따라맵의거리정보와함께알고리즘에입력된다. (6) (7) (8) 노드선택시매우작은값의 가사용된다면, 대부분의개미는수식 (7) 을사용해서확률적으로다음노드를선택하기때문에매우다양한경로를탐색하는특징을가진다. 이와달리만약큰값의 가사용된다면대부분의개미들이수식 (6) 에의해서현재노드에서가장저비용의노드만선택하기때문에특정경로를벗어나서탐색하기어려운특징을가진다. 따라서 값은알고리즘의성능에큰영향을미치는파라미터이다. 그리고모든개미의경로탐색이완료되면각개미들이생성한경로의비용을계산하는데, 이때경로의비용계산은페로몬및휴리스틱함수의곱으로이루어진다. 따라서경로의비용계산에링크의거리뿐만아니라링크의선호도도포함될수있다. 링크의페로몬업데이트는 ACO Loop에서현재까지가장낮은비용을가지는개미의경로에서만수행된다. 각 ACO Loop가완료되면변경된거리인 를적용하여 A* 알고리즘에의한경로탐색을다시수행함으로서, 선호도가반영된최단경로탐색이이루어진다. Try Loop의각 iteration 끝에서는휴리스틱함수의지수 ( ) 값을일정량 만큼증가시키고, 다음 Try Loop iteration 을수행한다. 를일정하게증가시키는이유는선호도에따른다양한경로를탐색하기위함이다. 즉, Try Loop가진행됨에따라선호도가더많이반영된경로를탐색할수있으며, 따라서사용자는선호도반영정도가다른여러가지최단경로중에서자신에게적절한경로를선택할수있다. 본논문에서제안하는알고리즘에서는경로탐색시모든노드를탐색하지않는다. 그리고 ACO Loop 안에서한번의 iteration을마친후 iteration best ant의경로에대한페로몬값업데이트로인해링크의비용이변한다. 만약선호도와비선호도를거리 (weight value) 와함께하나의최종비용으로미리모두계산한후경로탐색알고리즘을수행하는방법을사용한다면, 경로 (720)

6 2010 년 8 월전자공학회논문지제 47 권 TC 편제 8 호 79 탐색에사용되지않는노드를미리계산하는경우가발생되며, 맵의크기가커질수록그리고개미의수가작아질수록이러한오버헤드는더욱커지게된다. 따라서본논문에서는모든링크의선호도와비선호도를거리와함께하나의최종비용으로미리계산하지않고, 현재선택된링크에대해서만비용을계산한다. 그리고 polynomial time의최단경로탐색알고리즘은노드의수및링크의수가증가함에따라경로탐색시간이급격히증가하는단점이있기때문에, 본논문에서는적절한최단경로를최대한빠른시간내에찾을수있는휴리스틱융합알고리즘을제안한다. Ⅳ. 성능측정및평가본장에서는제안된알고리즘구현및성능측정환경에대해설명한후다양한파라미터를변경하여측정된결과를토대로알고리즘의성능을비교평가한다. 1. 성능측정환경제안된알고리즘은 C언어를사용하여구현되었으며, 성능측정에는 64개의노드및 118개의링크를가진맵이사용되었다. 각링크에는링크의거리값뿐만아니라, 링크의선호도 (preference) 및비선호도 (avoidance) 를나타내는값이포함된다. 만약특정링크의선호도값및비선호도의값이같다면, 제안된알고리즘은이링크를일반링크 (common link) 로판단한다. 하지만특정링크의선호도값이비선호도값보다크다면, 이링크를선호링크 (preferred link) 로판단하고, 이와반대로비선호도값이선호도값보다크다면, 이링크를비선호링크 (avoidance link) 로판단한다. 성능측정에사용된링크의수및링크의선호도및비선호도값은표 1 과같이설정되었다. 선호도기반경로탐색결과의적절한비교평가를위해각링크의선호도및비선호도값은 1 또는 2로설정되었다. 표 1. 맵을구성하는링크의선호도및비선호도특성 Table 1. Properties of the links of the map. 일반링크의수선호링크의수비선호링크의수총링크선호도비선호도선호도비선호도선호도비선호도수 파라미터설정및성능측정방법 제안된알고리즘의다양한파라미터중개미의수 ( ), 노드선택시사용되는확률값 ( ), 휴리스틱함수의지수 ( ) 그리고 MaxACO 값은알고리즘의성능에큰영향을미친다. 이러한파라미터의변화에따른알고리즘의성능변화를살펴보기위해표 2와같이다양한파라미터셋을설정하여성능을측정하였다. 표 2에서파라미터셋 2번은개미의개체수 ( ) 증가에따른알고리즘의성능변화를측정하기위해설정되었으며, 파라미터셋 3번은노드선택방법의확률을결정하는값 ( ) 변화에따른알고리즘의성능변화를측정하기위해사용되었다. 그리고 MaxACO 값의증가에따른알고리즘의성능변화를측정하기위해파라미터셋 4번이사용되었으며, 휴리스틱함수의지수값 ( ) 변화에따른알고리즘의성능변화를측정하기위해파라미터셋 5번이사용되었다. 모든성능측정과정에서 MaxTry 의값은 11, 후보노드 (candidate node) 목록의수는 3으로설정되었으며, 값의증가량 는 0.3으로설정되었다. 그리고시작노드및도착노드는모두동일하게설정되었다. 표 2. 성능측정에사용된파라미터셋 Table 2. Set of parameters for the simulation. 파라미터셋번호 MaxACO ~ ~ ~ ~ ~ ~ ~ 4 10 ~ ~ ~ 성능측정결과및평가 그림 3 및 4는표 2의파라미터셋 1번을사용하여측정된결과를나타낸다. 그림 3을통해초기경로탐색결과 ( =0) 를살펴보면선호링크가포함되어져있지않고비선호링크및일반링크로총 19개의링크로구성되어짐을알수있다. 하지만 가 1.9로증가되면서부터선호링크가포함된경로가탐색되기시작하고, 가 2.5가되는시점이후부터는비선호링크가포함되지않은경로를탐색하는것을알수있다. 선호링크가포함 (721)

7 80 선호도기반최단경로탐색을위한휴리스틱융합알고리즘옥승호외 그림 3. 의증가에따른링크수의변화 (MaxACO = 30, = 20, = 0.5) Fig. 3. Total number of the links as a function of. (MaxACO = 30, = 20, = 0.5) 그림 5. 의증가에따른링크수의변화 (MaxACO = 30, = 50, = 0.5) Fig. 5. Total number of the links as a function of. (MaxACO = 30, = 50, = 0.5) 그림 4. 의증가에따른경로의총비용및거리의변 화 (MaxACO = 30, = 20, = 0.5) Fig. 4. Total cost and distance of the paths as a function of. (MaxACO = 30, = 20, = 0.5) 그림 6. 의증가에따른경로의총비용및거리의변 화 (MaxACO = 30, = 50, = 0.5) Fig. 6. Total cost and distance of the paths as a function of. (MaxACO = 30, = 50, = 0.5) 되면서총링크의수가증가하는것은선호링크를선택하기위해우회로가선택되었기때문이다. 그림 4를살펴보면, 가 1.9로설정되는시점부터비용은감소하는것을알수있다. 이는비용계산은거리와휴리스틱함수의곱으로측정되기때문이다. 그리고총거리가증가하는것은선호링크가포함되면서우회로가포함되기때문이다. 파라미터셋 1번을사용해성능을측정한결과선호경로는 가 1.9일때부터탐색되며, 가 2.5가되는 시점부터최대선호경로가탐색되고, 이때거리는최대가되고, 비용은최소가되는것을알수있다. 그림 5~8은파라미터셋 2번을사용하여측정된결과를나타낸다. 그림 5 및 6을통해개미의수가 50으로설정되었을경우를살펴보면, = 30 인파라미터 그림 7. 의증가에따른링크수의변화 (MaxACO = 30, = 70, = 0.5) Fig. 7. Total number of the links as a function of. (MaxACO = 30, = 70, = 0.5) (722)

8 2010 년 8 월전자공학회논문지제 47 권 TC 편제 8 호 81 그림 8. 의증가에따른경로의총비용및거리의변 화 (MaxACO = 30, = 70, = 0.5) Fig. 8. Total cost and distance of the paths as a function of. (MaxACO = 30, = 70, = 0.5) 그림 11. 값증가에따른링크수의변화 (MaxACO = 30, = 70, = 0.9) Fig. 11. Total number of the links as a function of. (MaxACO = 30, = 70, = 0.9) 그림 9. 의증가에따른링크수의변화 (MaxACO = 30, = 70, = 0.1) Fig. 9. Total number of the links as a function of. (MaxACO = 30, = 70, = 0.1) 그림 12. 값증가에따른경로의총비용및거리의 변화 (MaxACO = 30, = 70, = 0.9) Fig. 12. Total cost and distance of the paths as a function of. (MaxACO = 30, = 70, = 0.9) 셋 1번과달리 가 1.9가되는시점부터선호경로가탐색되고비용은감소된다. 이는개미의수증가에따라탐색되는경로의수가다양해지기때문이다. 특히그림 7 및 8을통해개미의수가 70으로증가되었을경우성능측정결과를살펴보면선호경로는 1.3부터탐색되어짐을알수있다. 하지만개미수가증가하더라도최대선호경로는 가 2.5일경우부터수렴되기시작하는특징이있다. 그림 9 ~ 12는파라미터셋 3번을사용하여측정된 그림 10. 값증가에따른경로의총비용및거리의 변화 (MaxACO = 30, = 70, = 0.1) Fig. 10. Total cost and distance of the paths as a function of. (MaxACO = 30, = 70, = 0.1) 결과를나타낸다. 그림 9 및 10을통해노드선택방법의확률을결정하는값 ( ) 이 0.1로설정되었을경우를살펴보면, 선호경로는 가 1.6이되는시점부터탐색되어지며, 최대선호경로는 가 2.5부터탐색되어수렴하는것을알수있다. 그리고총 3가지종류의선호경로 (723)

9 82 선호도기반최단경로탐색을위한휴리스틱융합알고리즘옥승호외 가탐색되어진다. 그림 11 및 12를통해 가 0.9로설정되었을경우를살펴보면, 선호경로는 가 1.9가되는시점부터탐색되어지며, 최대선호경로는 가 2.5가되는시점부터탐 색되어수렴하는것을알수있다. 그리고이경우 가 0.1인경우보다적은총 2가지종류의선호경로가탐색되어지는데, 이는 값이클수록알고리즘은후보노드 (candidate node) 를우선적으로사용하여경로를탐색하기때문이다. 그림 13은파라미터셋 4번을사용하여측정된결과를나타낸다. 그림을통해 MaxACO 값증가에따른알고리즘의성능변화를살펴보면, MaxACO 값이증가함에따라평균선호링크는증가하는반면, 평균비선호링크는감소하는것을알수있다. 이는 MaxACO 값이증가함에따라경로에누적되는페로몬의크기가커지 기때문이다. 그림 14 ~ 16는파라미터셋 5번을사용하여측정된결과를나타낸다. 그림을통해휴리스틱함수의지수값변화에따른알고리즘의성능변화를살펴보면, 그림 14에서와같이 가 1.9일경우선호경로는 MaxACO 값이 30일때부터탐색되며, 최대선호경로는 MaxACO 값이 70이되는시점부터탐색되어지는것을알수있다. 반면에그림 15에서와같이 가 2.5일경우선호경로는 MaxACO 값이 20 되는시점부터탐색되어지며, MaxACO 값이 30이되면최대선호경로가탐색되는것을알수있다. 그리고그림 16에서와같이 가 4.0인경우는 MaxACO 값이 10이되는시점부터부터선호경로가탐색되며, MaxACO 값이 20일때부터최대선호경로를탐색하는것을알수있다. 따라서 값이클수록작은값의 MaxACO 만으로도선호도 그림 13. MaxACO 값증가에따른평균링크수의변화 ( = 20, = 0.5, = 0 ~ 4) Fig. 13. Average number of links as a function of MaxACO. ( = 20, = 0.5, = 0 ~ 4) 그림 15. MaxACO 값증가에따른링크수의변화 ( = 30, = 0.5, = 2.5) Fig. 15. Total number of the links as a function of MaxACO. ( = 30, = 0.5, = 2.5) 그림 14. MaxACO 값증가에따른링크수의변화 ( = 30, = 0.5, = 1.9) Fig. 14. Total number of the links as a function of MaxACO. ( = 30, = 0.5, = 1.9) 그림 16. MaxACO 값증가에따른링크수의변화 ( = 30, = 0.5, = 4.0) Fig. 16. Total number of the links as a function of MaxACO. ( = 30, = 0.5, = 4.0) (724)

10 2010 년 8 월전자공학회논문지제 47 권 TC 편제 8 호 83 은파라미터의변화에따른성능변화가크지않아, 비교적적은수의개미및작은값의 MaxACO 를사용해서도선호경로를찾는특징을나타내었으며, 값이클수록작은값의 MaxACO 만으로도선호도에기반한경로를탐색할수있음을알수있었다. 제안된알고리즘은기존의최단경로탐색을위한시스템뿐만아니라, 선호도에기반한경로탐색이필요한다양한시스템에적용될수있을것으로기대된다. 그림 17. 개미의수 ( ) 증가에따른 A* 및 ACO 알고리즘수행시간비율의변화 ( = 0.5, = 4.0) Fig. 17. The variation of execution time rate between the ACO and A* algorithm as a function of. ( = 0.5, = 4.0) 에기반한경로를빨리탐색할수있음을알수있다. 그림 17은개미의수 ( ) 증가에따른 ACO Loop의각 iteration에서 ACO의평균수행시간및 Try Loop 의각 iteration에서 A* 의평균수행시간비율의변화를나타낸것이다. 그림을통해 ACO Loop의각 iteration 평균수행시간비율을살펴보면개미의수가 10일경우 34.1% 이지만개미의수가 70일경우 ACO의평균수행시간비율이 81.9% 까지증가하여, 전체알고리즘수행에서 ACO가차지하는비율이높은것을알수있다. 이는개미의수가증가할수록각 iteration에서모든개미들이경로를탐색하는데걸리는시간이증가하기때문이다. 따라서적절한개미수의선택이전체알고리즘의수행시간을결정짓는중요한요소인것을알수있다. V. 결론 본논문에서는기존의최단경로탐색을위한 A* 및 ACS 알고리즘을융합하여, 최단경로뿐만아니라사용자의링크선호도에기반한경로탐색이모두가능한알고리즘을제안하였으며, 다양한파라미터를사용하여성능을측정및평가하였다. 성능측정및평가결과제안된알고리즘은휴리스틱함수의지수 ( ) 값이 0일경우 A* 알고리즘에의한최단경로를탐색하며, 이후 가증가함에따라최단경로탐색결과에서선호링크수는증가하고, 비선호링크의수는감소하는특징을나타내었다. 그리고본알고리즘 참고문헌 [1] 최병호, 정문호, 전희영, T-DMB 상용교통정보서비스시스템소개, 대한전자공학회, 전자공학회지, 제 35 권, 제 9 호, 쪽, 2008 년 9 월 [2] Sara Nazari, M.Reza Meybodi, M. Ali Salehigh, Sara Taghipour, An Advanced Algorithm for Finding Shortest Path in Car Navigation System, International Workshop on Intelligent Networks and Intelligent Systems, pp , Wuhan, China, Nov [3] Hao Yue, Chunfu Shao, Study on the Application of A* Shortest Path Search Algorithm in Dynamic Urban Traffic, Third International Conference on Natural Computation, vol. 3, pp , Haikou, Hainan, China, Aug [4] Noto, M.; Sato, H. A method for the shortest path search by extended Dijkstra algorithm, Proc. of IEEE International Conference on Systems, Man and Cybernetics, Nashville, TN, vol. 3, pp , Oct [5] Salehinejad, H. Talebi, S. A new ant algorithm based vehicle navigation system: A wireless networking approach, International Symposium on Telecommunications, pp , Tehran, Iran, Aug [6] M Dorigo, V Maniezzo, A Colorni, Ant system: optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics-Part B, vol. 26(1), pp , [7] LM Gambardella, M Dorigo, Solving Symmetric and Asymmetric TSPs by Ant Colonies, Proceedings of the IEEE Conference on Evolutionary Computation, pp , Nagoya, Japan, May [8] 안진호, 김홍식, 김현진, 박영호, 강성호, 규칙적인 NoC 구조에서의네트워크지연시간최소화를위한어플리케이션코어매핑방법연구, 대한전자공학회, 전자공학회논문지 SD 편, 제 45 권, 제 4 호, (725)

11 84 선호도기반최단경로탐색을위한휴리스틱융합알고리즘옥승호외 쪽, 2008 년 4 월 [9] Marco Dorigo, Thomas Stützle, Ant Colony Optimization, pp , MIT Press, 저자소개 옥승호 ( 정회원 ) 2006 년동의대학교메카트로닉스공학과학사졸업 년경북대학교전자공학과석사졸업 년현재경북대학교전자전기컴퓨터학부박사과정. < 주관심분야 : SoC 설계및응용, 디지털 VLSI> 안진호 ( 정회원 ) 1995 년연세대학교전기공학과학사졸업 년연세대학교전기공학과석사졸업 년엘지전자 DTV 연구소연구원 년연세대학교전기공학과박사졸업 년현재호서대학교전자공학과교수. < 주관심분야 : SoC 설계및응용, 테스트 > 강성호 ( 평생회원 ) 1986 년서울대학교제어계측공학과학사졸업 년 The University of Texas, Austin 전기및컴퓨터공학과석사졸업 년 The University of Texas, Austin 전기및컴퓨터공학과박사졸업 년미국 Schlumberger 연구원 년미국 Motorola 선임연구원 년현재연세대학교전기전자공학과교수. < 주관심분야 : SoC 설계및테스트 > 문병인 ( 평생회원 )- 교신저자 1995 년연세대학교전자공학과학사졸업 년연세대학교전자공학과석사졸업 년연세대학교전기전자공학과박사졸업 년 ~2004 년하이닉스반도체선임연구원 년 ~2005 년연세대학교연구교수 년 ~ 현재경북대학교전자공학부조교수. < 주관심분야 : SoC, 디지털 VLSI, 컴퓨터구조 > (726)

<33312D312D313220C0CCC7D1C1F820BFB0C3A2BCB12E687770>

<33312D312D313220C0CCC7D1C1F820BFB0C3A2BCB12E687770> Journal of the Society of Korea Industrial and Systems Engineering Vol No pp March 8 Scatter Search를 이용한 신뢰성 있는 네트워크의 경제적 설계 * ** * ** Economic Design of Reliable Networks Using Scatter Search HanJin Lee*