효율적인몬테칼로시뮬레이션을위한중요샘플링기법이내장된실험틀설계 http://dx.doi.org/10.5392/jkca.2013.13.04.053 Importance Sampling Embedded Experimental Frame Design for Efficient Monte Carlo Simulation 서경민 *, 송해상 ** 한국과학기술원전기및전자공학과 *, 서원대학교컴퓨터공학과 ** Kyung-Min Seo(kmseo@smslab.kaist.ac.kr) *, Hae-Sang Song(hssong@seowon.ac.kr) ** 요약 본논문은효율적인몬테칼로시뮬레이션을위하여중요샘플링 (Importance sampling) 기법이내장된실험틀을제안한다. 제안하는실험틀은중요샘플링기법을적용하기위해기능적으로세분화된중요표본기 (Importance Sampler) 와편향보상기 (Bias Compensator) 라는두개의하위모델을내장 (Embedded) 한다. 이러한하위모델은기존의시스템모델과실험틀의경계에플러그인됨으로써기존모델들의수정없이재사용할수있는장점이있다. 그리고제안하는실험틀은기능적측면에서중요사건에대하여동일한수준의결과를얻는데있어기존의몬테칼로시뮬레이션보다시뮬레이션시간을단축시킬수있다. 이러한효용성을입증하기위해두가지실험을수행하였는데, 실험결과, 본실험에대하여기존의몬테칼로시뮬레이션보다최대 400 배가량의시뮬레이션시간측면에서성능향상을확인하였다. 본논문에서제안하는실험틀은다양한콘텐츠분야에적용되어시뮬레이션성능을향상시킬수있는도구로활용할수있을뿐아니라, 교육적측면에서다양한사회현상을이해하고해석하는도구로도활용이가능하다. 중심어 : 확률모델 몬테칼로시뮬레이션 중요샘플링 실험틀 Abstract This paper presents an importance sampling(is) embedded experimental frame(ef) design for efficient Monte Carlo (MC) simulation. To achieve IS principles, the proposed EF contains two embedded sub-models, which are classified into Importance Sampler(IS) and Bias Compensator(BC) models. The IS and BC models stand between the existing system model and EF, which leads to enhancement of model reusability. Furthermore, the proposed EF enables to achieve fast stochastic simulation as compared with the crude MC technique. From the abstract two case studies with the utilization of the proposed EF, we can gain interesting experimental results regarding remarkable enhancement of simulation performance. Finally, we expect that this work will serve various content areas for enhancing simulation performance, and besides, it will be utilized as a tool to understand and analyze social phenomena. keyword : Stochastic Model Monte Carlo Simulation Importance Sampling Experimental Frame 접수번호 : #130315-003 접수일자 : 2013 년 03 월 15 일 심사완료일 : 2013 년 03 월 25 일교신저자 : 송해상, e-mail : hssong@seowon.ac.kr
54 한국콘텐츠학회논문지 '13 Vol. 13 No. 4 I. 서론입력변수혹은시스템의확률적 (Probabilistic) 특성으로인하여결과를정확하게예측할수없는확률모델 (Stochastic model) 은분석적인해 (Analytical solution) 을찾는것이불가능한경우가많다. 이러한경우수치적 (Numerical) 으로일련의난수 (Random number) 를반복적으로발생해서시뮬레이션을수행하면해를찾을수가있는데이러한기법을몬테칼로 (Monte Carlo) 시뮬레이션기법이라고한다. 몬테칼로시뮬레이션은알고리즘의반복과그로인한많은수의계산이포함되기때문에주로컴퓨터를이용한모델링시뮬레이션 (M&S: Modeling and Simulation) 분야에많이응용된다 [1]. 최근에는기술의급속한발달과시스템의복잡도증가로인해매우높은신뢰도와성능을필요로하는시스템이개발되고, 이러한시스템에서희귀사건 (Rare event) 의발생확률과그영향을추정하는것이중요한쟁점으로부각되고있다. 예를들어, 차량시스템에서돌발고장 (Catastrophic failure) 을일으키는고장율은 이하이지만이러한희귀사건이발생할경우막대한인명피해를유발할수있기때문에희귀사건과같은중요사건 (Important event) 의발생율을효율적으로추정할수있는도구가필요하다. 전통적몬테칼로시뮬레이션기법의경우, 주요한희귀사건의표본 1개를추출하기위해단순산술적으로 개이상의표본을추출해야하기때문에시뮬레이션소요시간이기하급수적으로증가하게된다 [2]. 이러한비효율성을극복하기위하여기존의입력분포함수대신에중요사건의발생을촉진시키는새로운분포함수를적용하여시뮬레이션을수행한후이로인해편향된확률분포를다시보정하는절차를거치는중요샘플링기법 (Importance Sampling) 이연구되어왔다 [3]. 따라서본논문은몬테칼로시뮬레이션을보다효율적으로수행하기위하여중요샘플링기법이내장된실험틀의설계방안과그활용방안을제안한다. 여기서실험틀은임의의시스템모델에대하여시뮬레이션실험을수행하기위해입력변수를생성하고출력변수를 수집 분석하는모델을말한다. 지금까지연구되어온실험틀이정의한입력확률변수를그대로이용하여몬테칼로시뮬레이션을수행하였다면, 제안하는실험틀은희귀사건등중요사건에대하여편향된확률밀도함수 (Probability Density Function) 를적용하여시뮬레이션을수행함으로써중요사건에대한전체시뮬레이션시간을효과적으로단축시킬수있는장점이있다. 또한제안하는실험틀의구조적측면에서는중요샘플링기법을적용하기위해중요표본기 (Importance Sampler) 와편향보상기 (Bias Compensator) 를설계한다. 따라서기존의실험틀을전혀수정하지않고사용할수있도록기존의실험틀에두모델을플러그인 (Plug-in) 함으로써모델재사용성을높일수있다. 제안하는실험틀은다양한콘텐츠분야에적용될수있는데. 특히교육적측면에서사회현상을쉽게이해하고해석할수있는도구로활용될수있다. 마지막으로사례연구에서는두가지실험을통하여제안하는실험틀을이용할경우기존의전통적몬테칼로시뮬레이션보다본사례연구의경우최대 400배까지시뮬레이션성능이개선되는것을알수있다. 본논문의구성은다음과같다. 2장에서는확률기반모델링에대하여설명하고두가지시뮬레이션기법을설명한다. 3장은본논문에서제안하는중요샘플링기법이내장된실험틀의구조와설계를설명하고제안하는실험틀이다양한콘텐츠분야에활용될방안을간단히제시한다. 4장에서는제안하는실험틀의효용성을입증하기위해두가지실험을수행하여기존의방식과제안방식의성능을비교하고, 마지막으로 5장에서는본논문의결론을맺는다. II. 관련연구본절에서는논문에서제안하는실험틀을설명하는데있어필요한개념인확률기반모델과이를반복시뮬레이션하는데사용하는두가지기법에대하여살펴보도록한다.
효율적인몬테칼로시뮬레이션을위한중요샘플링기법이내장된실험틀설계 55 1. 확률기반모델통계학에서는 [ 그림 1] 에서와같이 와 와같은모집단의양적인측도인모수 (Parameter) 를추정하기위하여모집단을샘플링 (Sampling) 한표본 (Sample) 을이용한다. 즉,, 와같은표본의특성을나타내는통계량 (Statistic) 을통하여모집단의모수를추정하게된다. 이러한모집단의통계치를추정하는과정은 M&S 공학에서도동일하게적용이된다. 가정하자. 번의시뮬레이션을수행한다고가정하면, 를추정하기위해서독립된시뮬레이션횟수마다사건 의발생여부를확인한다. 를독립된한번의시뮬레이션에대한베르누이 (Bernoulli) 확률변수라고하면 는식 (1) 과같이지시확률변수 (Indicator function) 를이용하여정의할수있다. (1) 따라서, 고전 (Crude) 몬테칼로시뮬레이션을이용한 의추정값 은식 (1) 의 를이용하면식 (2) 와같이표현할수있다. (2) 식 (2) 에서 은반복시뮬레이션횟수를의미하고, 는전체반복시뮬레이션횟수에대한사건 가 그림 1. 확률기반모델링과정 M&S 공학에서자연환경, 사회 경제, 공학등다양한실세계시스템의특성을추정하기위하여모델링목적 (Objective) 에따라추상화단계를거치면시스템모델로표현할수있다 [4]. 통계학에서와같이시스템모델은실세계의무한한크기의입력과출력변수, 를모델의목적에맞게추상화하여유한한크기의입력과출력변수, 으로실세계의동작 (Behavior) 을추정하게된다. 이때, 입력과출력변수들의관계가확실하여예측치를정확하게찾을수있는모델을확정모델 (Deterministic model) 이라고하고, 이와는달리입력변수혹은시스템의확률적 (Probabilistic) 특성으로인하여시스템의결과를정확하게예측할수없는모델을확률모델 (Stochastic model) 이라고한다 [5]. 따라서몬테칼로시뮬레이션을수행하기위해본논문에서는확률모델을대상시스템모델로이용한다. 2. 확률모델에대한시뮬레이션기법 2.1 몬테칼로 (Monte Carlo) 시뮬레이션기법먼저, 임의의사건 (Event) 가발생활확률을 라고 발생하는횟수의비로표현된다. 만약, 식 (2) 를역으로환산하여 에따른반복시뮬레이션횟수를도출하면식 (3) 과같다 [3]. (3) 식 (3) 에서 (Relative Error) 는 와 의상대적오차를나타내고, 여기서반복시뮬레이션횟수는상대적오차의제곱값과임의의사건 (Event) 가발생할확률 에반비례하기때문에임의의사건 가발생할확률이 이고,, 이면 은 근방이므로고전몬테칼로시뮬레이션의경우대략 10조번의반복시뮬레이션을수행하여야한다. 2.2 중요샘플링 (Importance Sampling) 기법중요샘플링 (Importance Sampling) 은변화량감소 (Variance reduction) 기법중하나로써시뮬레이션결과의정확도가주어졌을때반복시뮬레이션횟수를가능한한최대로줄일수있는개선된 (Advanced) 몬테칼로시뮬레이션방법을말한다 [3]. 즉, 식 (3) 에서일정한 를보장하면서도반복시뮬레이션횟수 을줄일수있는기법을말한다. 따라서중요샘플링기법은고전몬테칼로시뮬레이션에비해적은시뮬레이션횟
56 한국콘텐츠학회논문지 '13 Vol. 13 No. 4 수로비슷하거나동일한정도의시뮬레이션결과를추정할수있는효율적인기법으로사용된다. 시스템모델에중요샘플링기법을적용하는단계는다음과같다. 먼저, 시스템모델에서중요사건이많이발생할수있도록입력변수의확률밀도함수를수정한다. 다음으로수정된확률밀도함수를이용하여시스템모델에대하여몬테칼로시뮬레이션을수행하고, 마지막으로시뮬레이션결과에대하여적절히보상해준다. 이세가지과정에대한수학적이론은식 (4) 를통해증명된다. 로나눌수있다 [6]. 여기서실험틀은기본적으로입력변수를생성하는제너레이터 (Generator) 와시뮬레이션결과로시스템모델로부터전달받은출력변수를수집 분석하는트랜스듀서 (Transducer) 로구성이된다. 이렇게시스템모델과실험틀을분리하는모델설계는시스템모델과실험틀을독립적인모델로간주할수있어재사용성측면에서장점을지닌다 [6]. (4) 식 (4) 에서 는시스템모델 와기존의입력변수의확률밀도함수인 의적분으로계산할수가있는 데이를새로운확률밀도함수인 에따른적분식 으로바꿀수있다. 새로운 에대한적분식으로 바뀌면서추가적으로 가필요한데, 이항이시뮬레이션결과에대한적절한보상을해주는무게함수 (Weighting function) 이된다. 따라서중요샘플링기법을통한 의추정값 는식 (5) 와같다. (5) 이와같이, 중요샘플링기법은시뮬레이션결과의변화량감소를위해 와 의적절한설계와더불어이를시뮬레이션할수있는환경구축이중요한문제이다. III. 본론본론에서는먼저, 관련연구에서살펴본중요샘플링기법을실험틀에내장하기위해적용한설계방향및방법을설명하고, 그다음으로, 제안하는실험틀을실제여러콘텐츠분야에적용하는활용방안을제시한다. 1. 제안하는실험틀설계기법컴퓨터를이용한 M&S 공학의기본모델구조는대상시스템모델과이를시뮬레이션할수있는실험틀 그림 2. 기존의실험틀과제안하는실험틀의차이점 [ 그림 2] 의좌측모델은앞서설명한시스템모델인 와실험틀모델인 가분리된구조를나타낸다. 일반적으로시스템모델 는 SPICE, Verilog, MATLAB, DEVS(Discrete EVent System Specification) 등과같이잘알려진모델링명세또는소프트웨어언어로표현되거나, 특정알고리즘이나수치적분등과같이특수한함수로표현된다. 그리고실험틀 은입력변수의생성및출력변수의수집 분석을담당하므로입력확률변수 를시스템모델 로전달하고, 모델결과인 를전달받는다. 위과정에대하여반복시뮬레이션을수행하면고전몬테칼로시뮬레이션기법이된다. 근래에는기술의급속한발달로인해시스템모델의복잡도가증가하고이로인한시뮬레이션수행시간도상대적으로증가하였다. 또한, 다양한입력표본에대한시뮬레이션실험결과를요구하기도하는데, 특히매우높은신뢰도와성능을필요로하는시스템모델의경우시스템모델에서발생할수있는희귀사건 (Rare event) 의발생확률에대한시뮬레이션추정이요구되
효율적인몬테칼로시뮬레이션을위한중요샘플링기법이내장된실험틀설계 57 기도한다. 따라서시뮬레이션실험단계에서는효율적인시뮬레이션을위해시스템모델에서발생할수있는희귀사건과같은중요사건을먼저식별하고, 시스템모델에서중요사건들이선별적으로추출될수있도록입력표본을가공하여반복시뮬레이션을할수있는기법이필요하게되는데이중하나가중요샘플링기법이다. 이러한중요샘플링기법을활용하면기본적으로중요사건의발생확률에대하여시뮬레이션시간을단축시킬수있고, 실험결과의변화량을감소시킬수가있다. 특히, 이기법은중요사건의발생확률이극히낮은희귀사건의경우에효율적으로활용이가능하다. 본논문에서는이러한요구사항을만족시키는실험틀을 [ 그림 2] 의오른쪽과같이제안한다. 제안하는실험틀을설계하는데있어주안점은크게두가지인데, 첫째는모델재사용측면에서기존의시스템모델과실험틀을전혀수정하지않아야한다는것이고, 두번째는중요샘플링기법을적용하기위해새로추가하는모델을기능적으로잘세분화해야한다는것이다. 이를토대로본논문에서접근한설계기법은기존의시스템모델 와실험틀 의경계에인터페이스 (Interface) 와같이중요샘플링기법을구현한모델을플러그인하는방법을사용하였고, 이로인해기존모델들의재사용성을높일수있다. 그리고중요샘플링기법으로추가로내장된모델은기능적으로세분화하여두개의하위모델로설계하였는데중요표본기 (Importance Sampler) 와편향보상기 (Bias Compensator) 가그것들이다. 따라서제안하는실험틀은기존의 에중요표본기와편향보상기를내장하여중요샘플링기법을활용한효율적시뮬레이션이가능하게되고, 본논문에서는제안하는실험틀을 라명명한다. 제안하는실험틀 의개념적프레임워크는 [ 그림 3] 과같다. 먼저, 시스템모델 에대하여확률분포 를따르는입력확률변수 가존재하고, 의중요사건의발생확률추정을위해 의관심영역을붉은빗금부분으로설정한다고가정하자. 다시말하면, 에서관심영역에대한입력표본을상대적으로많이추 출하여시뮬레이션을하면그만큼시스템모델 의입장에서중요사건이빈번히발생한다는것을의미한다. 그림 3. 제안하는실험틀의개념적프레임워크중요표본기는관심영역에대한표본의추출빈도를높이기위해 를 로변경시키는역할을담당한다. [ 그림 3] 에서 보다 가관심영역의비중이더크기때문에반복시뮬레이션을수행하면해당영역의표본추출빈도는더높게된다. 따라서시스템모델 는 대신 를확률밀도함수로가지는 에대하여시뮬레이션을수행하고그결과인 를편향보상기로전달한다. 그러나이러한경우의 는사실상관심영역에대하여편향된확률분포를이용한결과이기때문에이를보정해주는과정이필요한데, 이러한역할을편향보상기가담당한다. 마지막으로, 편향보상기에의해보상된결과인 는 로전달되어결과를수집 분석한다. 세부절에서는 의가장중요한두기능모델인중요표본기와편향보상기에대하여자세히알아본다. 1.1 중요표본기 (Importance Sampler) 설계중요표본기의역할을설명하기위해중요표본기로입력되는확률변수가관심영역에따라서어떻게변경되는지를 [ 그림 4] 의예를통해설명하도록한다. [ 그림 4] 에서입력변수 의확률밀도함수가 라가정하자. 는간단하게 4개의영역을가지고각영역의길이는 이다. 그리고 의범위중에서시뮬레이션에관심있는영역은제 1영역과제 2영역이라고하자. 이러한경우, 관심있는영역에대한표본을
58 한국콘텐츠학회논문지 '13 Vol. 13 No. 4 많이추출하기위해서는해당영역의확률밀도를높여야하고, 는해당영역의확률밀도를높인편향된확률밀도함수가된다. 인특성을예측할수있는경우가있기때문에식 (8) 은그러한시스템에대하여최적은아니지만효율적인 를도출할수있는통찰력을제공해준다. 1.2 편향보상기 (Bias Compensator) 설계중요표본기의편향된확률밀도함수 를이용하면시스템모델의출력 역시편향된결과를갖게된다. 이러한편향된결과를보상하기위해편향보상기를설계한다. 그림 4. : 중요표본기설계 따라서 [ 그림 4] 의경우, 는아래조건을만족해야한다. (7) 이렇게관심영역에따른 의효율적인설계기술이중요샘플링기법의중요한연구쟁점중의하나이고, 를효율적으로설계하기위한여러가지 연구들이진행되고있다. 하지만본논문은 의효율적설계에집중하는것이아니라, 모델구조적관점에서중요샘플링기법을 M&S 공학의실험틀에효과적으로플러그인하는설계방법에초점을맞추고있다. 따라서 효율적설계에대한연구는 [2] 와 [3] 을참고하기바란다. 추가적으로, [3] 에의하면, 시스템모델 에대하여이론적으로 1회의시뮬레이션만으로도중요사건의발생확률을완벽하게추정할수있는최적의 인 가존재하는데, 그형태는식 (8) 과같다. (8) 식 (8) 을보면 를계산하기위해서는시스템모델 의모든정보를수식적으로파악해야하는데, 를완벽히파악한다는것은다면사실상시뮬레이션을하지않아도수식을통해분석적해도출이가능하다는것을의미한다. 따라서식 (8) 은현실적으로불가능하지만많은응용분야에서는시스템모델에대한대략적 그림 5. : 편향보상기설계 [ 그림 5] 는편향보상기의입 출력관계와편향보상기설계시가장중요한부분인무게함수의설계를나타낸다. 편향보상기는편향된출력 를보상하기위해 에보상비율을곱하여 로전달한다. 이때곱해주는보상비율이식 (4) 에서설명한무게함수이다. 식 (9) 는무게함수를수식으로나타낸것이다. (9) 무게함수의수학적인근거는식 (4) 에서찾아볼수있는데, 기존의 대신에 을이용하여 를도출하였기때문에두확률밀도함수의비가보상비율이된다. 1.1절과 1.2절을통하여본논문에서제안하는실험틀 에내장된두가지주요한모델 ( 중요표본기와편향보상기 ) 의역할과설계방법을설명하였다. 제안하는실험틀의설계기법은식 (5) 에서출발하였기때문에마지막으로지금까지설명한중요샘플링기법의과정을식 (5) 에대입하여간단하게설명하고, 다음절에서제안하는실험틀의활용방안에대하여제시하도록한다.
효율적인몬테칼로시뮬레이션을위한중요샘플링기법이내장된실험틀설계 59 그림 6. 중요샘플링을이용한몬테칼로시뮬레이션과정 [ 그림 6] 은식 (5) 를시뮬레이션단계별로나누어표시한그림이다. 먼저, 중요표본기를통해관심영역의표본을많이추출하기위해 를 에대한확률밀도함수로변경하고 (➀ 중요표본기 ), 이를바탕으로시스템모델은결과를도출한다 (➁ 시스템모델결과 ). 시스템모델의결과는편향된시뮬레이션결과이기때문에이를보정하기위해무게함수를곱하고 (➂ 중요표본기 ), 이러한과정을반복시뮬레이션을수행하면 (➃ 몬테칼로시뮬레이션 ), 중요사건에대하여좀더효율적으로발생확률을추정할수가있다 (➄ 추정치계산 ) 2. 제안하는실험틀의활용방안본론의 1절을통하여기존의실험틀을확장한중요샘플링기법이내장된실험틀을제안하였다. 이번절에서는제안된실험틀과중요샘플링기법이콘텐츠분야에서어떻게적용될수있는지에대하여몇가지응용분야를소개하고자한다. 결론적으로말하면, 많은콘텐츠분야에서부분적으로중요샘플링기법을적용해왔다. 이를 [ 그림 7] 을통해설명하도록한다. [ 그림 7] 에서와같이간단한문제를하나정의해보자. 정의하고자하는문제는가로와세로의길이가 1인정사각형내부에특정표적이존재하고, 문제의해결방법은이표적의넓이를구하는것이다. 이때, 우리가중요샘플링기법을적용한다고하면표적이존재할것이라고예측되는범위를관심영역으로설정하고관심영역에대하여상대적으로많은시뮬레이션을수행하게된다면기존의고전몬테칼로시뮬레이션보다시뮬레이션시간측면에서더나은성능을보일것이다. 이러한일반화된문제는여러가지콘텐츠분야에서발생할수있는특정한문제를추상화시킨결과로볼수있다. 그림 7. 제안하는실험틀의콘텐츠응용분야예를들어, 국방콘텐츠분야의경우, 마일즈 (MILES: Multiple Integrated Laser Engagement System, 다중통합레이저교전체계 ) 장비시스템 [7] 에서부착하고있는센서의취약영역 (Vurnarlable Area) 을계산하는데있어본논문에서제안하는실험틀을적용할수있다. 취약영역에대하여시뮬레이션을수행할때마일즈장비를착용한병사의신체부위전체를시뮬레이션하는것이아니라착용한장비의탐지가능범위를관심영역으로설정하여몬테칼로시뮬레이션을수행하는것이효율적이기때문이다. 또다른예로경찰수사시스템에도활용될수있다. [ 그림 7](b) 와지도에서빨간원이범죄발생지역과용의자제보지역이라고하면경찰인력배치시, 해당범위를관심영역으로설정하고이영역에대하여중요샘플링을수행할수있다. 세번째로감염예방시스템에도적용이가능하다. 최근 5년간, 돼지의신종플루감염과구제역확산등으로감염예방시스템이필요하게되었는데 [ 그림 7] 에서와같이감염위험지역을관심영역으로설정하여중요샘플링기법과제안하는실험틀을적용할수있다. 이뿐아니라, 영 유아의방사선검사시뮬레이션 [8], 중장기기술예측을위한시뮬레이션 [9], 프로젝트일정관리시뮬레이션 [10], 청소년범죄예방계획 [11] 등과같은다양한콘텐츠분야에적용이가능하다. 따라서제안하는실험틀은하나의현상에대하여효율적인시뮬레이션결과도출을위해서활용됨과동시에앞서열거한
60 한국콘텐츠학회논문지 '13 Vol. 13 No. 4 여러가지사회현상에대하여쉽게이해하고해석할수있는교육적자료로써의활용도기대할수있다. IV. 실험이번절에서는제안하는실험틀의효용성입증을위해두가지실험을수행한다. 본실험의목적은제안하는실험틀을이용하여시뮬레이션속도측면에서얼마나나은성능을보이는지를고전몬테칼로시뮬레이션과비교 분석하는것이목적이다. 이를위해실험설계, 구현, 실험결과, 결과고찰순서로설명하도록한다. 1. 실험설계그림 8. 관심영역에따른실험설계 1,2 실험하고자하는대상과실험설계방법은 [ 그림 7] 에서일반화시킨예제를바탕으로 [ 그림 8] 과같이정리하였다. 실험목적은가로와세로의길이가 1인정사각형범위내에위치하는표적의넓이를구하는것이고, 실제표적은정사각형중심을 2차원직교좌표계의원점이라고하였을때제 2사분면에위치한다고가정한다. 입력확률변수 는주어진정사각형범위내에서균일한분포를가지는 를따르고정사각형내부중에서표적에위치하는사건을 라고한다면확률모델 는다음과같이정의할수있다. (10) 본실험에서는중요샘플링기법을활용하기위해관심영역을두가지종류로설정한다. 실험 1은관심영 역을제 2사분면과제 3사분면으로설정하고, 실험 2는제 2사분면만을관심영역으로설정하여관심영역과비관심영역간의확률밀도가각각 과 로설정하였다. 두개의실험군의시뮬레이션결과를비교하기위하여대조군은기존의 를따르는입력확률변수를이용한고전몬테칼로시뮬레이션결과로설정하였다. 2. 실험구현 실험에사용된확률모델과제안하는실험틀은모두프로그래밍언어인 C++ 를이용하여구현하였다. [ 그림 9] 는 를따르는입력확률변수 와함께중요표본기와편향보상기에서사용하는, 의함수를나타내었고, [ 표 2] 와 [ 표 3] 을통해표본비율에따른실제파라미터값을나타내었다. 앞서설명하였듯이, 가커질수록 와 가 와 보다훨씬커지기때문에관심영역에대하여많은표본이추출된다. 표본의전체개수는실험 1과실험 2 모두 100,000개이고, 중요표본기는임의의확률밀도함수에대하여적절한표본을뽑을수있도록구현하였다. 편향보상기는하나의표본에대한모델의출력 에대하여무게함수를곱해서기존의실험틀 로전달한다. 는 100,000개의표본에대한실제표적에포함된표본의비를이용하여표적의넓이를구하였다. 표 2. 실험 1 의파라미터값 파라미터세트 표 3. 실험 2 의파라미터값 파라미터세트 파라미터값 파라미터값
효율적인 몬테 칼로 시뮬레이션을 위한 중요 샘플링 기법이 내장된 실험 틀 설계 61 그림 9. 중요 표본기와 편향 보상기의 함수 구현 3. 실험 결과 내에 수렴하여 약 24배의 성능 이득을 보였다. [그림 11] [그림 10]과 [그림 11]은 가 100, 10,000인 경우에 의 실험 2의 경우에는 1,121번째 샘플에서 수렴함으로써 대하여 표본 수에 따른 표적의 면적을 그린 그래프이 고전 몬테 칼로 시뮬레이션보다 약 80배 이상의 성능 이 다. 해는 득을 보임을 알 수 있다. 이 실험을 를 부터 까 로 알려져 있고, 시뮬레이션을 지 변경하면서 실험을 하면 최대 400배 이상의 성능 이 통하여 표본 수에 따라 얼마나 해석적인 해에 근접하는 득을 보일 수 있고, 이를 [표 3]을 통해 정리하였다. 표적의 면적에 대하여 해석적인 지 확인 하였다. 이 때 오차 범위는 실제 값의 1% 범위 이내이다. 두 그래프 모두 빨간 선은 대조군으로 고전 4. 결과 고찰 몬테 칼로 시뮬레이션의 경우를 나타내고, 초록 선과 실험 결과를 통해 시스템 모델의 정보를 알고, 관심 파란 선은 각각 실험 1과 실험 2의 결과를 나타낸다. 먼 영역을 효과적으로 설정한다면 시뮬레이션 성능 측면 저 [그림 10]의 경우를 살펴보면, 고전 몬테 칼로 시뮬 에서 이득을 볼 수 있음을 알 수 있었다. 본 실험의 경 레이션의 경우에서는 100,000개의 표본 중에 번 우, 제안하는 실험 틀을 이용하여 이미 잘 설계된 째 표본에서 오차 범위 이내에 들어오는 것을 알 수 있 를 활용하였기 때문에 시뮬레이션 성능 이득을 다. 이에 반해 제안하는 실험 틀을 이용한 실험 1과 2에 볼 수 있었다. 특히, 가 100,000인 실험 2의 경우에는 서는 각각 12,101번째와 3,877번째 표본에서 오차 범위 그림 10. 표본 수에 따른 원의 면적 그래프 ( )
62 한국콘텐츠학회논문지 '13 Vol. 13 No. 4 그림 11. 표본 수에 따른 원의 면적 그래프 ( ) 표적의 위치와 거의 유사하게 관심 영역을 설정하였기 양한 용도로 활용될 수 있다. 때문에 최대 400배의 성능 이득을 보일 수 있었다. 다시 말하면, 를 잘못 설계하는 경우에는 오히려 시 뮬레이션 성능 측면에서 떨어지는 결과를 얻을 수도 있 다. 또한, 와 의 관계가 함수 관계가 아닌 경우에는 무게 함수를 설정하는 것이 불가능하기 때문 에 제안하는 실험 틀을 사용하지 못하는 한계점이 있 다. 그렇다 하더라도 대부분의 시스템은 효율적인 설계가 가능하기 때문에 제안하는 실험 틀은 다 V. 결론 본 논문은 효율적인 몬테 칼로 시뮬레이션을 할 수 있도록 중요 샘플링 기법이 내장된 실험 틀 설계 기법 을 제안하였다. 본 논문에서 제안하는 실험 틀은 중요 샘플링 기법을 활용할 수 있도록 기능별로 세분화된 중 요 표본기와 편향 보상기 모델을 설계하였다. 제안하는 표 3. 전체 실험 결과 ( (Measurement Index) 1: 최종 면적의 1% 오차 범위 이내에 수렴하는 데 걸리는 시간 (단위: msec), (Measurement Index) 2: 최종 면적의 1% 오차 범위 이내에 수렴하는 데 필요한 샘플의 수) 가변 파라미터 측정 지수 몬테 칼로 기법 실험 사례 실험 1 768.99 실험 2 117.782 55,172 7,629 409.516 92.192 6,370 29,222 172.379 56.8 12,101 3,877 92.57 43.19 6,285 2,933 90.634 17.478 6,262 1,121 51.866 1.685 3 467
효율적인몬테칼로시뮬레이션을위한중요샘플링기법이내장된실험틀설계 63 실험틀은기존의시스템모델과실험틀을그대로사용할수있도록이들을시스템모델과실험틀사이에인터페이스개념으로플러그인함으로써구조적측면에서기존의모델을재사용할수있는장점을지닌다. 제안하는실험틀의효용성검증을위해두가지실험을수행하였는데, 본실험의경우고전몬테칼로시뮬레이션을이용한시뮬레이션의경우보다제안하는실험틀을이용하면시뮬레이션시간측면에서높은이득을얻을수있었다. 제안하는실험틀은하나의현상에대하여시뮬레이션성능측면에서의이득뿐아니라, 다양한콘텐츠분야에적용될수있는도구로활용가능하다. 또한교육적측면에서사회현상을이해하고해석하는데제안하는실험틀설계기법을도입함으로써사회현상을좀더쉽게이해하고교육할수있는좋은교육자료로활용될수있기를기대한다. [8] 김상태, 영 유아의입사피부선량측정을위한몬테카를로시뮬레이션, 한국콘텐츠학회논문지, 제 12권, 제6호, pp.346-352, 2012. [9] 유성열, 중장기기술예측을위한시뮬레이션기반방법론, 한국콘텐츠학회논문지, 제10권, 제1 호, pp.372-380, 2010. [10] 유정초, 황보택근, 통계분석을이용한 CCPM 기법에서의버퍼산정방법, 한국콘텐츠학회논문지, 제12권, 제8호, pp.29-36, 2012. [11] 이형복, 임윤택, 최봉문, 김낙수, 학교시설에서 CPTED 적용방안및원칙따른시뮬레이션, 한국콘텐츠학회논문지, 제12권, 제6호, pp.424-437, 2012. 저자소개 참고문헌 [1] 김탁곤, 국방 M&S 이론및기술 ( 입문편 )-산학협동공개강좌, KAIST 시스템모델링시뮬레이션연구실, 2012. [2] G. Rubino and B. Tuffin, Rare Event Simulation using Monte Carlo Methods, WILEY, 2009. [3] Rajan Srinivasan, Importance Sampling Applications in Communications and Detection, Springer, 2002. [4] 김탁곤, 모델링시뮬레이션공학 (M&S Engineering), 정보처리학회논문지, 제14권, 제6 호, pp.3-17, 2007. [5] 김탁곤, 국방 M&S 이론및기술 ( 모델개발편 ), 2012년산학협동공개강좌교재, 시스템 M&S 연구실, KAIST, 2012. [6] B. P. Zeigler, H. Praehofer, and T. Kim, Theory of Modeling and Simulation, ACADEMIC PRESS, 2000. [7] http://www.kctc.mil.kr/main.html 서경민 (Kyung-Min Seo) 정회원 2006년 2월 : 부산대학교전기전자통신공학부 ( 공학사 ) 2008년 2월 : 한국과학기술원전기및전자공학과 ( 공학석사 ) 2008년 3월 ~ 현재 : 한국과학기술원전기및전자공학과박사과정 < 관심분야 > : 국방모델링 / 시뮬레이션, 실험분석기법, 중요샘플링기법송해상 (Hae-Sang Song) 정회원 2000년 : 한국과학기술원전자전산학과 ( 공학박사 ) 1999년 ~ 2000년 : 고등기술연구원 2001년 ~ 2002년 : ( 주 ) 스페이스네트 2002년 ~ 현재 : 서원대학교컴퓨터공학과교수 < 관심분야 > : 시스템모델링시뮬레이션이론및응용, 국방시스템공학, 소프트웨어공학