- 최대 커버리지 센서 배치를 위한 유전 알고리즘
- ㆍ 저자명
- 윤유림,김용혁,Yoon. You-Rim,Kim. Yong-Hyuk
- ㆍ 간행물명
- 한국지능시스템학회 논문지
- ㆍ 권/호정보
- 2010년|20권 3호|pp.406-412 (7 pages)
- ㆍ 발행정보
- 한국지능시스템학회
- ㆍ 파일정보
- 정기간행물| PDF텍스트
- ㆍ 주제분야
- 기타
이 논문은 한국과학기술정보연구원과 논문 연계를 통해 무료로 제공되는 원문입니다.
본 논문에서는 실세계에서 센서를 배치할 때 발생하는 최적화 문제인 최대 커버리지 센서 배치 문제를 정의하고 문제의 해 공간의 특성을 분석하였다. 또한 최대 커버리지 센서 배치 문제의 좋은 해를 얻기 위해 유전 알고리즘을 설계하고 그 우수성을 비교 실험을 통해 보였다. 이 문제에 유전 알고리즘을 적용할 때 중요하게 고려되어야 할 부분은 평가 함수를 어떻게 구현하느냐 인데 몬테카를로법을 통해 해결할 수 있었다. 유전 알고리즘의 몬테카를로법을 이용한 평가 부분에서 샘플 생성 횟수를 조절함으로써 동일한 성능을 내면서 계산 시간을 크게 줄일 수 있었다.
In this paper, we formally define the problem of maximizing the coverage of sensor deployment, which is the optimization problem appeared in real-world sensor deployment, and analyze the properties of its solution space. To solve the problem, we proposed novel genetic algorithms, and we could show their superiority through experiments. When applying genetic algorithms to maximum coverage sensor deployment, the most important issue is how we evaluate the given sensor deployment efficiently. We could resolve the difficulty by using Monte Carlo method. By regulating the number of generated samples in the Monte Carlo evaluation of genetic algorithms, we could also reduce the computing time significantly without loss of solution quality.