NP-Hard 문제의 최상의 솔루션을 찾기 위한 아날로그 솔버

• 연구원은 MaxSAT라는 본질적인 이산 최적화 문제를 해결할 수 있는 새로운 시스템을 구축합니다.
• 이 아날로그 솔버는 디지털 컴퓨터보다 성능이 우수하며 다른 최적화 문제로도 확장될 수 있습니다.

오늘날의 디지털 컴퓨터는 대부분의 작업을 잘 수행합니다. 특정 계산, 워드 프로세싱, 웹 서핑 및 그래픽 아트에 적합합니다. 그러나 이진 코드(0과 1)에 의존하기 때문에 모든 문제를 해결하는 데 이상적이지는 않습니다.

디지털 컴퓨팅은 거의 최대 잠재력에 도달했으며 일부 수학자들은 아날로그 컴퓨팅 부활에 관심을 갖기 시작했습니다. 디지털 프레임워크를 넘어 컴퓨팅을 발전시키는 데 도움이 될 수 있습니다.

최근 루마니아의 노틀담 대학교와 Babes-Bolyai 대학교의 연구원들은 NP-hard 문제의 최상의 솔루션을 평가할 수 있는 새로운 아날로그 솔버를 개발했습니다.

NP-hard 문제는 다항식 시간에 문제를 해결할 수 있는 알고리즘이 없음을 의미합니다. 솔루션에 도달하는 데 필요한 시간은 문제 크기에 따라 기하급수적으로 증가합니다. 일반적으로 이러한 문제는 의료 영상, 생물 정보학, 단백질 접힘 및 일정과 관련이 있습니다.

연구원은 광범위한 NP-hard 문제에서 아날로그 솔버를 테스트했으며 이 새로운 방법이 더 짧은 시간에 더 나은 솔루션으로 이어질 가능성이 있음을 발견했습니다.

아날로그 컴퓨팅이 필요한 이유

아날로그 컴퓨터는 20세기 중반에 매우 인기가 있었습니다. 역학 문제와 관련된 모든 큰 행정부와 회사에는 거대한 아날로그 컴퓨팅 센터가 있었습니다. 로켓을 우주로 발사하고, 전함에서 무기를 유도하고, 항공기 역학을 시뮬레이션하는 데 사용되었습니다.

디지털 컴퓨터와 달리 아날로그 컴퓨터는 전압, 무게, 속도, 온도 및 압력과 같은 비이산 데이터를 사용합니다. 그리고 연속 값을 사용하기 때문에 양자화 노이즈에 영향을 받지 않습니다.

아날로그 컴퓨터는 다양한 문제를 해결하도록 설계할 수 있습니다. 수학 연산을 직접 수행할 수 있습니다. 예를 들어, 3에서 8을 빼려면 아날로그 컴퓨터가 해당 값에 해당하는 전압을 뺀 다음 즉시 올바른 출력을 제공합니다.

실시간 작업 및 동시 계산에 사용할 수 있습니다. 아날로그 문제의 경우 문제 및 오류에 대한 통찰력을 제공할 수 있습니다. 그리고 양자화가 필요 없기 때문에 신호 변조/복조 및 고속 모터 제어에 완벽합니다.

참조:네이처 커뮤니케이션즈 | 도이:10.1038/s41467-018-07327-2 | 노트르담 대학교

그러나 1980년대에 디지털 컴퓨터가 시장을 장악했습니다. 그들은 일반적인 작업을 수행할 때 충분히 유연하고 빠르고 정확했습니다. 효율적인 알고리즘이 등장하면서 성능이 더욱 향상되었습니다.

빈티지 아날로그 AMF665D 컴퓨터 | 이미지 제공:Francis Massen / YouTube

그러나 현대 컴퓨터를 포함한 디지털 컴퓨터는 변수가 큰 NP-hard 문제를 해결할 수 없습니다. 대부분의 최적화 문제의 어려움은 솔루션이 최적인지 여부를 결정할 수 없다는 것입니다. 더 나은 솔루션이 없는지 확인하는 것은 문제 자체만큼이나 어렵습니다.

고성능 아날로그 솔버

새로운 연속 시간 동적 시스템은 MaxSAT라고 하는 전형적인 이산 최적화 문제를 해결할 수 있습니다. 이 방법은 결정론적 상미분 방정식 세트와 최적 솔루션이 아날로그 시간 t에 의해 평가되었을 가능성을 예측하는 발견적 기술에 의존합니다.

아날로그 회로에서 von Neumann 병목 현상이 제거되었습니다. 회로 자체가 프로세서와 메모리 역할을 합니다. 반면에 디지털 컴퓨터에서 접근 방식을 구현하려면 연속 시간 방정식을 이산화하고 오류를 처리하는 동안 단계별로 해결하는 일반 미분 방정식 적분기 알고리즘을 사용해야 합니다.

디지털 형식에서는 역학이 수천 개의 결합 상미분 방정식을 발전시키므로 시간이 많이 소요되는 통합 프로세스이므로 솔버가 효율적으로 수행되지 않습니다.

읽기:양자 컴퓨터에 대한 가장 흥미로운 사실

그리고 접근 방식은 일반 문자를 사용하기 때문에 다른 최적화 문제로도 확장될 수 있습니다. 연구원은 이 새로운 접근 방식을 기반으로 장치를 설계하고 구축할 계획입니다.