초록 ▼

조합 최적화 문제는 컴퓨터 과학과 공학에서 상당히 중요한 문제로서, 많은 독립 변수들로 구성된 목적 함수의 최소값이나 혹은 최대값을 얻을 수 있는 효과적인 해를 찾는 것이다. 대표적 예로써 가장 널리 알려진 것이 순환 판매원 문제인데, 이문제를 해결하기 위해 많은 학자들이 연구하였는데 가장 널리 쓰인 방법이 신경회로망의 홉필드 신경망과 시뮬레이티드 어닐링이다. 기존의 방법을 보면 그 접근 방법면에서는 우수하였지만 외란 효과나 에너지 함수등의 면에서 약점을 가지고 있었으며, 임계온도 결정이나외란 효과의 양을 결정하는 면에서도

조합 최적화 문제는 컴퓨터 과학과 공학에서 상당히 중요한 문제로서, 많은 독립 변수들로 구성된 목적 함수의 최소값이나 혹은 최대값을 얻을 수 있는 효과적인 해를 찾는 것이다. 대표적 예로써 가장 널리 알려진 것이 순환 판매원 문제인데, 이문제를 해결하기 위해 많은 학자들이 연구하였는데 가장 널리 쓰인 방법이 신경회로망의 홉필드 신경망과 시뮬레이티드 어닐링이다. 기존의 방법을 보면 그 접근 방법면에서는 우수하였지만 외란 효과나 에너지 함수등의 면에서 약점을 가지고 있었으며, 임계온도 결정이나외란 효과의 양을 결정하는 면에서도 고려되지 못하였다. 이것으로 인하여 홉필드 신경망과 시뮬레이티드 어닐링의 결합은 좋은 방법임에도 불구하고 그 순환 판매원 문제에 적용한결과는 그다지 뛰어나지 못하였다.본 연구에서는 기존의 방법이 가지고 있던 단점들을 보안함으로써 일반화된 모델을 제시하였다. 기존의 단점을 보안한 부분은 다음과 같다.첫째, 에너지 함수에서 고려되지 않았던 부분을 고려함으로써 에너지함수를 일반화하였다.이는 홉필드 모델에서 가장 중요한 개념인 에너지 함수를 보안한 것이다. 둘째, 기존의 방법이 가지고 있지 않았던 모든 외란 효과를 고려해 줌으로써 좀더 일반화된 모델을 만들 수있었으며, 수렴중에 일어날 수 있는 오차를 줄일 수 있었다. 셋째, 임계온도를 결정하였다.임계온도를 결정함으로써 시뮬레이티드 어닐링이 가진 최적해를 구함에 있어 시간이 매우길다는 단점을 극복할 수 있었다. 이는 cooling의 초기 온도를 임계온도(보다 짧은 거리의도시를 경로로 선택하는 온도)에서 시작함으로써 그 시뮬레이션 시간을 줄일 수 있는 것이다. 넷째, 외란 효과의 양을 고려해 주었다. 외란 효과의 양을 고려해줌으로써 기존의 방법보다 보다 일반화되고 좋은 결과를 얻을 수 있었다. 다섯째, 시뮬레이션를 일반화된 방법으로 하였다. 기존의 논문에서는 고정된 1가지 도시분포에 대해서만 시뮬레이션을 하였지만, 본 연구에서는 랜덤(random)하게 발생된 100가지의 도시분포에 대하여 시뮬레이션을 하여 모든 도시분포에 대해 적용가능하다는 일반성을 제시하였다.본 연구의 결과가 조합 최적화 문제의 대표적인 예인 순환 판매원 문제를 해결하는 데홉필드 신경망과 시뮬레이티드 어닐링의 결합에 있어 일반화된 모델임을 보였다. 이로써다른 조합 최적화 문제인 VLSI circuit design (placement, routing, PLA folding,gate-matrix layout)등을 해결하는데 많은 성공적인 결과를 보여 줄것으로 기대되고, 시뮬레이티드 어닐링의 본성을 탐구함으로써 이것의 응용에 대한 기초가 될것이다. 또, 신경회로망의 하드웨어 구현에도 도움이 될것이다.

Abstract ▼

Combinatorial Optimization Problem, fairly important in computerscience and engineering, is to find out effective solution that makes it possible to getmaximum or minimum value of an objective function consists of many independentvariables. Typical and widespread example is TSP(Traveli

Combinatorial Optimization Problem, fairly important in computerscience and engineering, is to find out effective solution that makes it possible to getmaximum or minimum value of an objective function consists of many independentvariables. Typical and widespread example is TSP(Traveling Salesman Problem).Many scholars have done research to solve this problem. And, the most widely knownmethod to solve TSP is Hopfield Neural Network and Simulated annealing. Consideringthe conventional methods, they are superior in technique of approach, but inferior inperturbation effect and energy function. Moreover, they don't consider how to decidethe critical temperature and amount of perturbation effect. Because of these, the resultof applying Hopfield Neural Network and simulated annealing to TSP was not so good,although they are good method.So, our research proposes the generalized model by improving the weakness ofconventional method. The parts to improve the weakness of conventional methods areas following,First, we generalized the energy function by considering the aspects that theconventional method didn't. Second, we could make more generalized model and reducethe error of convergence by taking all the perturbation effect that the conventionalmethod didn't possess into account. Third, we decide the critical temperature. Doingso, we could overcome the weakness that it took too long time to find out the optimalsolution of simulated annealing. The simulation time could be reduced, because westarted the initial temperature of cooling as the critical temperature. Fourth, we tookthe amount of the perturbation effect. By doing so, we could get the more generalizedand better result than the conventional methods. Fifth, we performed the simulation ingeneralized way. The conventional papers performed the simulation for only onedistribution of cities. On the contrary, we did for one hundred distribution of citiesrandomly. And through this simulation, we find the generality of our proposed methodthat it is applicable to all distributions of cities.We showed that the result of our research was generalized model that combinedHopfield Network and simulated annealing to solve TSP, the representative example ofcombinatorial optimization problem. Herewith, it is expected that it will show manysuccessful results in other combinatorial optimization problem and routing incommunication system.

목차 Contents

• 1 서론...10
• 2 연구방법 및 이론...12
• 3 결과...21
• 4 고찰...23
• 5 결론...24
• 6 인용문헌...25
• 1 연구수행관련 논문발표 목록서...27
• 2 자체 평가서...28