지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 저널정보
- Korean Institute of Information Scientists and Engineers 정보과학회논문지 : 소프트웨어 및 응용 정보과학회논문지 : 소프트웨어 및 응용 제32권 제4호
- 발행연도
- 2005.4
- 수록면
- 268 - 276 (9page)
이용수
초록· 키워드
오류제보하기
본 논문은 최적 통신 걸침 나무 문제(Optimum Communication Spanning Tree Problem : OCST)를 다룬다. 일반적으로, OCST문제는 NP-hard 문제로 알려져 있으며 최근에 Papadimitriou 와 Yannakakis에 의해서 MAX SNP-hard로 밝혀졌다. 그럼에도 불구하고 OCST 문제를 해결하기 위한 기존의 주된 접근법은 polynomial time 알고리즘들 이었다. 본 논문에서는 OCST 문제를 해결하기 위한 진화 알고리즘을 소개한다. 특히, 진화 알고리즘을 어떤 문제에 적용할 때 가장 우선적으로 고려되어야 하는 사항은 해를 어떻게 표현할 것인가 하는 표현법(representation)에 관한 것이다. 따라서 본 논문에서는 기존에 차수 제약 걸침 나무 문제를 해결하기 위해 제안한 표현법의 단점을 개선하는 새로운 표현법을 제안하고 이 표현법을 이용해서 트리(tree)를 만들어 내는 decoding 방법 또한 소개한다. 그리고 제안하는 해 표현법에 맞는 유전 연산자를 찾기 위해 네트워크의 정보 및 부모세대가 지닌 유전 정보를 이용하는 3가지 방법을 실험하였다. 결론적으로, 다양한 실험을 통해서 제안하는 방법이 기존의 방법에 비해 우수한 결과를 보여 준다는 것을 확인할 수 있었다.
목차
요약
Abstract
1. 서론
2. OCST 문제
3. 다양한 트리 표현법
4. 유전 연산자
5. 실험 결과
6. 결론
참고문헌
저자소개
참고문헌 (16)
참고문헌 신청
[학술지(정기간행물)] - Garey / 1979 / A Guide to the Theory of NP- Completeness
[학술지(정기간행물)] - F. Goldberg / 2002. / Network Random Keys - A Tree Network Representation Scheme for Genetic and Evolutionary Algorithms tionary computation 10 : 75 ~ 97
[학술지(정기간행물)] - Yu Li / 2001. / An Effective Implementation of a Direct Spanning Tree Representation in GAs 2001 2037 : 11 ~ 19
[학술지(정기간행물)] - / 1991 / Journal of Computer and System Science : 425 ~ 440
[학술지(정기간행물)] - Yu Li / 1999. / A New Genetic Algorithm for the Optimal Communication Spanning Tree Problem Proceedings of Artificial Evolution : 162 ~ 173
[학술지(정기간행물)] - F. Goldberg / 2002. / Network Random Keys - A Tree Network Representation Scheme for Genetic and Evolutionary Algorithms tionary computation 10 : 75 ~ 97
[학술지(정기간행물)] - Yu Li / 2001. / An Effective Implementation of a Direct Spanning Tree Representation in GAs 2001 2037 : 11 ~ 19
[학술지(정기간행물)] - / 1991 / Journal of Computer and System Science : 425 ~ 440
[학술지(정기간행물)] - Yu Li / 1999. / A New Genetic Algorithm for the Optimal Communication Spanning Tree Problem Proceedings of Artificial Evolution : 162 ~ 173
함께 읽어보면 좋을 논문
논문 유사도에 따라 DBpia 가 추천하는 논문입니다. 함께 보면 좋을 연관 논문을 확인해보세요!
-
유전 알고리즘(GA)을 이용한 신뢰성 있는 최적 정보 통신 신장 트리(OCST) 설계 문제에 대한 해법
대한산업공학회 춘계공동학술대회 논문집
2008 .05
-
최적 통신 걸침 나무 문제해결을 위한 유전알고리즘의 유전자 표현법에 대한 연구
한국정보과학회 학술발표논문집
2007 .10
-
차수 제약 걸침 나무 문제를 해결하기 위한 트리 표현법
한국정보과학회 학술발표논문집
2003 .10
-
진화 알고리듬을 위한 새로운 트리 표현 방법
대한산업공학회지
2005 .03
-
최소걸침나무(Minimum Spanning Tree)기법을 이용한 대중교통 대안노선 설계방법 연구
대한교통학회 학술대회지
2009 .10
-
Minimum Spanning Tree 응용 문제에 대한 유전연산의 개선
산업공학 (IE interfaces)
2002 .09
-
공진화알고리듬을 이용한 최소걸침나무문제에서 k-지명호의 결정에 관한 연구
대한산업공학회 추계학술대회 논문집
2001 .11
-
신장 트리 기반 표현과 MAX CUT 문제로의 응용
제어로봇시스템학회 논문지
2012 .12
-
타부 리스트가 결합된 유전자 알고리즘을 이용한 트리형 네트워크의 경제적 설계
산업경영시스템학회지
2012 .01
-
유전 프로그래밍을 위한 트리 구조 기반의 진화연산자
제어로봇시스템학회 논문지
2008 .11
-
높은 신뢰도의 네트워크 설계를 위한 진화 연산에 기초한 알고리즘
정보과학회논문지 : 소프트웨어 및 응용
2005 .04
-
영상의 표현을 위한 tree 구조의 구성 ( The Tree Data Structure Generation for Image Representation )
한국통신학회 워크샵
1987 .01
-
고정비용 수송문제를 위한 유전 알고리즘의 성능비교
대한산업공학회 춘계공동학술대회 논문집
2008 .05
-
트리형 컴퓨터 네트워크 설계를 위한 유전자 접근방법의 성능 분석
한국정보기술학회논문지
2011 .09
-
Determining the Most Vital Arcs using the Library of Evolutionary Algorithm Framework in Minimum Spanning Tree Problem
대한산업공학회 추계학술대회 논문집
1999 .10
-
형상모델의 위상표현법에 관한 연구
한국멀티미디어학회 학술발표논문집
2004 .11
-
Auto-tuning Evolutionary Algorithm for a Capacitated QoS Model in Communication Network
대한산업공학회 춘계공동학술대회 논문집
2008 .05
-
Tree-Structure-Aware Genetic Operators in Genetic Programming
Journal of Electrical Engineering & Technology
2014 .03
-
O-tree 표현법을 이용한 개선된 플로어플랜 알고리즘
한국정보과학회 학술발표논문집
2007 .06
이 논문의 저자 정보
최근 본 자료
댓글(0)
0
UCI(KEPA) : I410-ECN-0101-2009-569-017824636