[논문]홉필드 네트웍에서 에너지 함수를 이용한 최적 경로 탐색에 관한 연구

고영훈; 김윤상

[국내논문] 홉필드 네트웍에서 에너지 함수를 이용한 최적 경로 탐색에 관한 연구
Study on the Shortest Path by the energy function in Hopfield neworks 원문보기

한국인터넷방송통신학회 논문지 = The journal of the Institute of Internet Broadcasting and Communication, v.10 no.5, 2010년, pp.215 - 221

고영훈 (협성대학교 컴퓨터공학과) , 김윤상 (한국기술교육대학교 인터넷미디어공학부)

초록
AI-Helper

홉필드 네트웍은 패턴 매칭과 더불어 최적화 문제를 푸는 도구로 사용될 수 있다. 특히 Zhang과 Ali는 홉필드 네트웍의 노드를 2차원으로 확장하여 최적화 문제를 해결하였다. 잠재적 브랜치의 총합인 노드의 제곱만큼 뉴런이 필요한 Ali 알고리즘은 탐색 네트워크가 커지면 많은 시간이 소요되는 단점이 있다. 본 논문에서는 Ali의 방식을 개선하여 계산량을 대폭 줄이고 효과적으로 최적 경로를 탐색할 수 있는 방식을 제안한다. 효과적인 최적 경로 탐색을 위하여 2단계로 구분하여 진행된다. 1단계에는 홉필드 네트웍을 2단계에는 eSPN 알고리즘을 사용하여 최적 경로를 탐색할 수 있다. 제안된 방식은 샘플 네트웍을 통하여 최적 경로 탐색이 확인되었으며, Ali 알고리즘보다 빠르고 간단하여 실제 최적화에 적용하기기 용이하다. 특히, 네트웍의 브랜치 비용이 변화할 경우에도 홉필드 네트웍의 연결 시냅스가 아닌 입력 바이어스를 조정하므로 동적으로 변화하는 네트웍의 최적 경로 탐색에도 유용하다.

Abstract ▼ AI-Helper

Hopfield networks have been proposed as a new computational tool for finding the shortest path of networks. Zhang and Ali studied the method of finding shortest path by expended neurons of Hopfield networks. Ali Algorithm is well known as the tool with the neurons of branch numbers. Where a network grows bigger, it needs much more time to solve the problem by Ali algorithm. This paper modifies the method to find the synapse matrix and the input bias vector. And it includes the eSPN algorithm after proper iterations of the Hopfield network. The proposed method is a tow-stage method and it is more efficient to find the shortest path.The proposed method is verified by three sample networks. And it could be more applicable then Ali algorithm because it's fast and easy. When the cost of brach is changed, the proposed method works properly. Therefore dynamic cost-varing networks could be used by the proposed method.

Keyword

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

. 본 논문에서는 Ali의 알고리즘을 단순화하고 홉필드 네트웍의 선처리 과정과 제안된 eSPN(Extended Shortest Path searching by Neuron) 알고리즘을 통하여 최적 경로를 찾는다.

가설 설정

는 첫 번째 샘플 네트웍으로 5개의 노드의 작은 네트웍이다. 브랜치는 비용을 담고 있으며, 브랜치는 양방향의 비용이 같다고 가정한다. 시작 노드는 0이고 끝 노드는 가장 큰 수인 4이다.

제안 방법

. 특히 TSP(traveling sales man problem)를 적용할 수 있는 모델을 제시하였다. Rauch와 Winarske는 네트웍에서 두 개의 노드 사이의 최적 경로를 찾는데 Hopfield Network을 사용하였다^[4].
본 논문에서는 Ali의 에너지 함수를 변형하여 3개의 항으로 에너지 함수를 구성한다. μ₁항과 μ₂항의 값을 α₁으로 통합하였다.
제안된 방식은 2단계 알고리즘을 사용한다. 우선 홉필드 네트웍을 통하여 뉴런에 최적 경로의 정보를 담게하고, 다음 단계로 eSPN 알고리즘을 통하여 최적 경로를 계산해낸다.
제안된 방식은 2단계 알고리즘을 사용한다. 우선 홉필드 네트웍을 통하여 뉴런에 최적 경로의 정보를 담게하고, 다음 단계로 eSPN 알고리즘을 통하여 최적 경로를 계산해낸다. 즉, 뉴런이 최종적으로 수렴하기 전에 뉴런의 데이타를 분석하여 최적 경로를 찾아낸다.
먼저 최적 경로를 찾고자 하는 네트웍의 노드와 브랜치를 분석하여 연결 시냅스와 입력 바이어스 값을 계산한다. 홉필드 네트웍의 계산을 반복하면서 다음 단계로 넘어가도 되는지 뉴런의 값을 체크한다.
홉필드 네트웍의 계산을 반복하면서 다음 단계로 넘어가도 되는지 뉴런의 값을 체크한다. 다음 단계로 넘어가도 될 정도로 뉴런의 값이 수렴했으면 eSPN 알고리즘을 통하여 최적 경로를 탐색한다.
Ali의 알고리즘이 안정적으로 수렴하는데 수천 번의 반복연산이 필요한 반면 eSPN 알고리즘을 사용할 경우 100번 정도의 반복연산으로 뉴런에 정보를 담을 수 있다. 세 개의 예제 네트웍을 사용하여 최적경로를 탐색하는지 실험한다.
d행렬값은 c행렬값으로 변환되어 홉필드 네트웍의 반복 연산 후의 뉴런의 값으로 eSPN 알고리즘을 통하여 최적 경로가 0->1->2->3->6->5->7 임을 찾을 수 있다. eSPN 알고리즘에는 빠르게 경로를 찾기 위해서 가능성이 있는 노드만을 선별하여 비교한다. 즉, 자기 자신에게로 연결된 브랜치나 브랜치 루프는 선택되지 않도록 처리한다.
본 논문에서는 보다 효과적이고 빠른 계산을 위하여 Ali의 에너지 함수를 변형시켰다. 그리고 2단계 기법을 통하여 홉필드 네트웍의 반복 연산의 횟수를 10분의 1 이상 줄이고, 제안된 eSPN 알고리즘을 통하여 빠르게 최적 경로를 계산할 수 있다.
그리고 2단계 기법을 통하여 홉필드 네트웍의 반복 연산의 횟수를 10분의 1 이상 줄이고, 제안된 eSPN 알고리즘을 통하여 빠르게 최적 경로를 계산할 수 있다. 세 개의 예제 네트웍을 통하여 제안된 알고리즘이 정확한 최적 경로를 탐색하는지 확인하였다.

이론/모형

특히 TSP(traveling sales man problem)를 적용할 수 있는 모델을 제시하였다. Rauch와 Winarske는 네트웍에서 두 개의 노드 사이의 최적 경로를 찾는데 Hopfield Network을 사용하였다^[4]. Zhang과 Thomopoulos는 n by m 매트릭스의 뉴런을 구성한 후 m을 확장하여 원치 않는 경로의 탐색을 제거하였다^[5].

성능/효과

에너지함수가 뉴런의 출력함수와 관계없이 구성되려면 고이득 회로로 구성되어야 한다. 또한 연결 시냅스 매트릭스인 C가 대칭일 경우 에너지 함수는 경사면으로 감소하는 것이 증명되었다. 경사면을 따라 감소하는 방식은 여러 가지가 있는데, 홉필드 네트웍에서는 현재 지점에서 가장 경사면이 급한 방향으로 감소한다.
본 실험에서는 α3의 값을 감소시켜 비용의 합계가 증가하는 문제를 해소하였다.
본 논문에서는 보다 효과적이고 빠른 계산을 위하여 Ali의 에너지 함수를 변형시켰다. 그리고 2단계 기법을 통하여 홉필드 네트웍의 반복 연산의 횟수를 10분의 1 이상 줄이고, 제안된 eSPN 알고리즘을 통하여 빠르게 최적 경로를 계산할 수 있다. 세 개의 예제 네트웍을 통하여 제안된 알고리즘이 정확한 최적 경로를 탐색하는지 확인하였다.

질의응답

핵심어	질문	논문에서 추출한 답변
	횹필드 네트웍은 어떤 구조인가?	1982년에 John Hopfield가 발표한 논문은 뉴럴 네트웍에 새로운 분야를 추가하는 계기가 되었다[1]. 횹필드 네트웍(Hopfield network)은 모든 뉴런의 출력이 입력으로 재귀되는 구조이며, 초기에는 저항과 커패시터를 이용한 전자회로로 소개되었다. 홉필드 네트웍에서는 뉴런간의 연결강도를 나타내는 연결 시냅스 매트릭스가 대칭적이다.
	eSPN 알고리즘은 무엇인가?	은 eSPN 알고리즘을 나타내고 있다. eSPN 알고리즘은 뉴런을 순회하면서 최대값과 최소값을 비교하여 각 행의 최적 뉴런을 찾아내는 알고리즘이다. 어느 정도 뉴런이 수렴하면 효과적으로 최적값의 뉴런을 찾아낼 수 있다.
	본 논문에서 제안한 Ali의 방식을 개선하여 계산량을 대폭 줄이고 효과적으로 최적 경로를 탐색할 수 있는 방식은 어떤 단계로 구성되어 있는가?	본 논문에서는 Ali의 방식을 개선하여 계산량을 대폭 줄이고 효과적으로 최적 경로를 탐색할 수 있는 방식을 제안한다. 효과적인 최적 경로 탐색을 위하여 2단계로 구분하여 진행된다. 1단계에는 홉필드 네트웍을 2단계에는 eSPN 알고리즘을 사용하여 최적 경로를 탐색할 수 있다. 제안된 방식은 샘플 네트웍을 통하여 최적 경로 탐색이 확인되었으며, Ali 알고리즘보다 빠르고 간단하여 실제 최적화에 적용하기기 용이하다.

참고문헌 (6)

J. J. Hopfield, "Neural networks and physical systems with emergent collective computational properties," Proceedings of the National Academy of Sciences, vol. 79, pp. 2554-2558, 1982.

상세보기
J. J. Hopfield, "Neurons with graded response have collective computational properties like those of two-state neurons," Proc. Nat. Acad. Sci., Vol. 81, pp.3088-3092, 1984.

상세보기
J. J. Hopfield and D. W. Tank, "Neural computations of decisions in optimization problems," Bol. Cybern, Vol. 52, pp. 141-152, 1986.
H. E. Rauch and T. Winarske, "Neural networks for routing communication traffic," IEEE Cont. Syst. Mag., pp. 26-30, Apr 1988.

상세보기
L. Zhang and S. C. A. Thomopoulos, "Neural networks implementation of the shortest path algorithm for traffic routing in communication networks," Proc. Int. Joint Conf. Neural Networks, Jun 1989.
Mustafa K. Mehmet Ali and Faouzi Kamoun, "Neural Networks for Shortest Path Computation and Routing in Computer Networks,"IEEE Trans. on Neural Networks, Vol. 4, no. 6, Nov 1993.

저자의 다른 논문 :

활용도 분석정보

상세보기

다운로드

내보내기

활용도 Top5 논문

해당 논문의 주제분야에서 활용도가 높은 상위 5개 콘텐츠를 보여줍니다.
더보기 버튼을 클릭하시면 더 많은 관련자료를 살펴볼 수 있습니다.

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증