http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
- 中文 을 입력하시려면 zhongwen을 입력하시고 space를누르시면됩니다.
- 北京 을 입력하시려면 beijing을 입력하시고 space를 누르시면 됩니다.
RISS 인기검색어
- 검색키워드
- 저자 : 이강구(Kang-Ku Lee) (검색결과 4 건)
- 무료
- 기관 내 무료
- 유료
-
이강구(Kang-Ku Lee),한승기(Seung-Kee Han),이성환(Seong-Whan Lee) 한국정보과학회 1995 정보과학회논문지 Vol.22 No.4
본 연구에서는 N 개의 도시를 방문하는 TSP 문제의 최단 경로를 찾기 위하여 유전자 알고리즘을 적용하였다. 유전자 알고리즘에서는 새로운 경로를 만들어 내기 위하여 교차 연산자, 돌연변이 연산자 및 전위 연산자가 자주 도입된다. 최근 전치(前値) 행렬을 이용한 교차 연산자인 Union 연산자가 기존의 연산자보다 훨씬 효과적으로 최단의 경로를 찾는 것으로 알려졌다. 그러나 전치 행렬을 사용한 방법에서의 Union 연산자는 N×N 행렬을 사용하기 때문에 계산 시간이 많이 걸리게 된다. 이러한 문제를 해결하기 위하여 Union 연산자를 N 개의 도시에 대한 연산으로 바꾸어 주었다. 그 결과 계산 시간이 현저하게 줄어 들었으며, 그 결과를 30 도시 문제에 적용한 결과 연산자의 성능이 partially matched crossover 연산자와 edge-recombination crossover 연산자보다 더 나은 결과를 주었다. In this paper, we apply the genetic algorithm to find out the optimal path in the N-city traveling salesman problem. Crossover, mutation and inversion operators are usually introduced to generate a new path from an old one in the genetic algorithm. Recently, the Union operator in the precedence matrix representation was found to be efficient in generating optimal path. In the precedence matrix representations, the Union operators require N×N matrix manipulations, which demand much computing time To solve this problem, we introduce a new Union operator in the standard representation of N cities. As results, the computing times are considerably reduced and the optimal path for 30-cities problem are easily obtained comparing with the results using the partially matched crossover and edge-recombination crossover operator.
-
이강구(Kang Ku Lee),한승기(Seung Kee Han) 한국정보과학회 1994 한국정보과학회 학술발표논문집 Vol.21 No.2A
본 연구에서는 유전자 알고리즘에서 나타나는 조기 수렴(premature convergence)현상을 해결하기 위하여 유전자 알고리즘에 엔트로피-볼쯔만 선택 방법을 도입하였다. 엔트로피-볼쯔만 선택 방법은 Monte Carlo 방법의 볼쯔만 샘플링과 엔트로피 샘플링을 결합한 것이다. 엔트로피 샘플링에서 엔트로피의 효과는 개체의 분포가 적은 쪽으로 다음 세대가 진화하게 하는 것이다. 따라서 유전자 알고리즘의 엔트로피 샘플링은 국소 최소점으로부터 쉽게 빠져 나오게 하는 역할을 한다. 반면에 볼쯔만 샘플링에서 온도의 역소로 정의 되는 β는 국소 최소점으로의 수렴 속도(convergence rate)와 탈출 시간(escape time)을 조절할 수 있게 한다. TSP의 30 도시 문제에 이 방법을 적용한 결과에서 우리는 β가 증가할수록 수렴 속도는 감소하지만 국소 최소점으로부터 빠져 나오는데 걸리는 시간이 짧아짐을 알 수 있었다.
-
이강구(Kang ku Lee),한승기(Seung Kee Han) 한국정보과학회 1994 한국정보과학회 학술발표논문집 Vol.21 No.1
본 연구에서는 TSP에 유전자 알고리즘을 적용하여 최단 경로를 찾아내는 방법에 대해서 조사하였다. 유전자 알고리즘을 TSP에 적용하기 위해서는 N개의 도시 순서에 적절한 돌연변이, 교차 및 전위 연산자를 도입하여야 한다. 최근에 많은 관심을 끌고 있는 Precedence 행렬을 이용한 교차 연산인 UNION 연산자는 기존의 연산자보다 훨씬 쉽게 최적의 경로로 접근함을 보였다. 그러나 이 방법은 Precedence 행렬 계산 때문에 메모리가 많이 필요하고 매 단계마다 걸리는 계산시간이 길어지는 단점이 있다. 본 연구에서는 UNION 연산자를 기존의 방법처럼 N개의 도시에 대한 연산을 바꾸어 주었다. 그 결과 매 단계마다 걸리는 시간도 줄어들고, 경로도 최적의 경로로 쉽게 접근함을 보였다.
-
이강구,한승기 충북대학교컴퓨터과학연구소 1994 컴퓨터과학연구 Vol.2 No.1
본 연구에서는 TSP에 유전자 알고리즘을 적용하여 최단 경로를 찾아내는 방법에 대해서 조사하였다. 유전자 알고리즘을 TSP에 적용하기 위해서는 N개의 도시 데이터에 적절한 돌연변이, 교차 및 전위 연산자를 도입하여야 한다. 최근에 많은 관심을 끌고 있는 Precedence 행렬을 이용한 교차 연산인 UNION 연산자는 기존의 연산자보다 훨씬 쉽게 최적의 경로로 접근함을 보였다. 그러나 이 방법은 Precedence 행렬 계산 때문에 메모리가 많이 필요하고 매 단계마다 걸리는 계산시간이 길어지는 단점이 있다. 본 연구에서는 UNION 연산자를 기존의 방법처럼 N개의 도시에 대한 연산으로 바꾸어 주었다. 그 결과 매 단계마다 걸리는 시간도 줄어들고, 경로도 최적의 경로로 쉽게 접근함을 보였다.
연관 검색어 추천
이 검색어로 많이 본 자료
활용도 높은 자료
