마그노닉 조합 장치를 이용한 순회 판매원 문제 해결

Scientific Reports 13권, 기사 번호: 11708(2023) 이 기사 인용

207 액세스

측정항목 세부정보

여행하는 외판원 문제(TSP)는 다양한 실제 응용에 필수적인 의사결정 문제입니다. 오늘날 이 문제는 가능한 경로 수를 하나씩 확인하여 부울 유형 아키텍처를 활용하는 디지털 컴퓨터에서 해결됩니다. 본 연구에서는 TSP 솔루션을 위한 특별한 유형의 하드웨어를 설명합니다. 활성 링 회로에 연결된 자기 부품과 전기 부품으로 구성된 마그노닉 조합 장치입니다. 위상 천이기, 주파수 필터 및 감쇠기로 구성된 자기 메시에는 여러 가지 가능한 전파 경로가 있습니다. 위상 시프터는 TSP의 도시를 모방하는 반면 도시 간의 거리는 신호 감쇠로 인코딩됩니다. 주파수 필터 세트는 서로 다른 주파수의 파동이 서로 다른 경로를 통해 전파되도록 합니다. 작동 원리는 고전적인 파동 중첩을 기반으로 합니다. 서로 다른 위상 변이와 진폭 감쇠를 누적하면서 가능한 모든 경로로 들어오는 여러 파동이 있습니다. 그러나 일정한 위상 변화가 축적된 파동만 전기 부품에 의해 증폭됩니다. 증폭은 전파 손실이 가장 적은 파동에 먼저 발생합니다. 이러한 유형의 장치는 파도가 동시에 가능한 모든 경로로 이동하는 판매원과 유사한 TSP 솔루션에 적합합니다. 우리는 4개 도시와 6개 도시에 대한 TSP 솔루션을 설명하는 수치 모델링 결과를 제시합니다. 또한 4개 도시의 TSP 솔루션에 대한 실험 데이터를 제시한다. 프로토타입 장치는 자기 위상 시프터/필터, 동축 케이블, 스플리터, 감쇠기 및 광대역 증폭기를 포함하여 시판되는 구성 요소로 제작되었습니다. 세 가지 다른 도시 간 거리 집합에 대해 도시 간 최단 경로를 찾는 세 가지 예가 있습니다. 제안된 접근 방식은 더 많은 수의 도시를 갖춘 TSP로 확장 가능합니다. 신체적 한계와 과제도 논의됩니다.

TSP는 가장 잘 알려진 조합 최적화 문제 중 하나입니다1. "도시 목록과 각 도시 쌍 사이의 거리가 주어지면 각 도시를 정확히 한 번 방문하고 원래 도시로 돌아오는 최단 경로를 찾으십시오." 이는 비결정론적 다항식 시간 경도(NP-hard) 문제로, 최적의 경로를 얻을 것이라는 보장이 없고 다항식 시간에 이를 해결하기 위한 정확한 알고리즘이 없음을 의미합니다. TSP는 운송2, 일정3, 유전체학4을 포함한 다양한 실제 응용 분야에서 중요합니다. 수학적으로, 이는 \(\left\{{c}_{1},{c}_{2},\dots,{c}_{n이라는 이름의 \(n\)개 도시 집합으로 정의될 수 있습니다. }\right\}\) 및 순열 \(\left\{{\sigma }_{1},{\sigma }_{2},\dots ,{\sigma }_{n!}\right\} \). 목표는 투어에서 도시 간 모든 유클리드 거리의 합이 최소화되도록 \({\sigma }_{i}\)를 선택하는 것입니다. TSP는 그림 1과 같이 무방향 가중치 그래프로 모델링할 수 있습니다. 여기서 도시는 그래프의 꼭지점, 경로는 그래프의 가장자리, 경로의 거리는 가장자리의 가중치입니다. TSP는 가능한 모든 \(\left(n-1\right)!/2\) 가능한 경로를 하나씩 확인하여 해결할 수 있습니다. 소수의 도시에 대해 가능한 모든 경로를 확인하는 것은 비교적 쉽습니다. 예를 들어, 4개의 도시가 있는 TSP에는 \(\left(4-1\right)!/2=3\) 경로가 있습니다. 가능한 경로의 수는 \(n\) 계승에 비례하여 증가하므로 기존 컴퓨팅 장치를 사용하여 많은 수의 도시를 해결하기가 어렵습니다.

4개 도시의 TSP에 대한 무방향 가중치 그래프입니다. 도시는 그래프의 정점이고, 경로는 그래프의 가장자리이며, 경로의 거리는 가장자리의 가중치입니다.

TSP 솔루션5,6을 위한 특수 하드웨어를 구축하려는 시도가 여러 번 있었습니다. 예를 들어, 6개 도시 TSP는 코호넨(Kohonen)형 광 네트워크를 사용하여 해결되었습니다6. 그러나 이러한 접근 방식 중 어느 것도 실제로 실행 가능한 장치로 이어지지 않았습니다. 최근에는 인공지능(AI)에 사용되는 다양한 최적화 기법이 TSP7에 적용됐다. 이는 TSP 솔루션의 속도를 크게 향상시킬 수 있지만 기존 하드웨어에 구현되는 근본적인 이점을 제공할 수는 없습니다.