본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

이웃해 탐색 기법을 이용한 Maximal Covering 문제의 해결
Neighborhood Search Algorithms for the Maximal Covering Problem

황준하   (금오공과대학교 컴퓨터공학부UU0000297  );
  • 초록

    지금까지 maximal covering문제를 해결하기 위해 다양한 기법들이 적용되어 왔다. 타부 탐색 역시 그 중의 하나이다. 그러나 기존 연구에서는 타부 탐색을 비롯한 언덕오르기 탐색이나 시뮬레이티드 어닐링과 같은 이웃해 탐색 기법들에 대한 종합적인 분석과 성능 향상을 위한 노력이 부족하였다. 본 논문에서는 다양한 실험과 분석을 통해 이웃해 탐색 기법들의 성능을 향상시키기 위한 방안을 소개한다. 기본적으로 모든 이웃해 탐색 기법들은 k-exchange 이웃해 생성 방법을 사용하고 있으며 다양한 파라미터 설정에 따라 각 기법의 성능이 어떻게 달라지는가를 분석하였다. 실험 결과 단순 언덕오르기 탐색과 시뮬레이티드 어닐링이 다른 기법들에 비해 훨씬 우수한 탐색 성능을 보였으며, 일반적인 경우와는 달리 단순 언덕오르기 탐색이 시뮬레이티드 어닐링과 비슷한 성능을 보임을 확인하였다.


    Various techniques have been applied to solve the maximal covering problem. Tabu search is also one of them. But, existing researches were lacking of the synthetic analysis and the effort for performance improvement about neighborhood search techniques such as hill-climbing search and simulated annealing including tabu search. In this paper, I introduce the way to improve performance of neighborhood search techniques through various experiments and analyses. Basically, all neighborhood search algorithms use the k-exchange neighborhood generation method. And I analyzed how the performance of each algorithm changes according to various parameter settings. Experimental results have shown that simple hill-climbing search and simulated annealing can produce better results than any other techniques. And I confirmed that simple hill-climbing search can produce similar results as simulated annealing unlike general case.


  • 주제어

    이웃해 탐색 .   언덕오르기 탐색 .   시뮬레이티드 어닐링 .   maximal covering 문제.  

 저자의 다른 논문

  • 황준하 (15)

    1. 2002 "병렬 타부 탐색을 이용한 발전기 기동정지계획의 최적화" 정보과학회논문지. Journal of KIISE. 소프트웨어 및 응용 29 (9): 645~653    
    2. 2004 "승무일정계획의 최적화를 위한 이웃해 탐색 기법과 정수계획법의 결합" 정보과학회논문지. Journal of KIISE. 소프트웨어 및 응용 31 (6): 829~839    
    3. 2004 "대규모 Maximal Covering 문제 해결을 위한 유전 알고리즘" 정보과학회논문지. Journal of KIISE. 소프트웨어 및 응용 31 (5): 570~576    
    4. 2004 "반복적 개선 탐색을 이용한 최적 선석 및 크레인 일정계획" 韓國컴퓨터情報學會論文誌 = Journal of the Korea Society of Computer and Information 9 (4): 117~125    
    5. 2008 "C 코딩 스타일 검증기의 설계 및 구현" 韓國컴퓨터情報學會論文誌 = Journal of the Korea Society of Computer and Information 13 (2): 31~40    
    6. 2009 "비선형 최적화 문제의 해결을 위한 정수계획법과 이웃해 탐색 기법의 결합" 韓國컴퓨터情報學會論文誌 = Journal of the Korea Society of Computer and Information 14 (2): 27~35    
    7. 2010 "웹 카메라와 LEGO Mindstorms를 활용한 영상 처리 알고리즘의 교육에 관한 연구" 공학교육연구 = Journal of engineering education research 13 (6): 171~179    
    8. 2010 "제약 만족 최적화 문제의 해결을 위한 지역 탐색과 제약 프로그래밍의 결합" 韓國컴퓨터情報學會論文誌 = Journal of the Korea Society of Computer and Information 15 (5): 39~47    
    9. 2010 "선형 제약 만족 최적화 문제를 위한 정수계획법 기반 지역 탐색 기법" 韓國컴퓨터情報學會論文誌 = Journal of the Korea Society of Computer and Information 15 (9): 47~55    
    10. 2012 "다차원 배낭 문제를 위한 정수계획법 기반 지역 탐색 기법" 韓國컴퓨터情報學會論文誌 = Journal of the Korea Society of Computer and Information 17 (6): 13~27    

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 이용한 콘텐츠
이 논문과 함께 출판된 논문 + 더보기