업무배치, 자원 할당, 일정 계획 등 현실 세계의 수많은 할당문제는 NP-Hard이며 다항 시간 근사 알고리즘(Polynomial-time Approximation Algorithm)이 없는 2차할당문제로 공식화할 수 있다. 더 일반적으로는, 모든 시설을 서로 다른 위치에 할당하되, 해당 흐름에 해당하는 거리의 합을 최소화하는 시설과 위치의 순열(Permutation)을 찾는 문제이다. 이러한 2차할당문제를 해결하고자 지난 수십 년 동안 다양한 휴리스틱 방법이 제안되었다. 그러나 지금까지 확실한 승자가 없고, 정확한 알고리즘이 존재하기도 하지만, n=25 또는 그 이상의 큰 인스턴스를 적시에 해결하는 방법은 많지 않다. 휴리스틱 방법의 하나인 밈틱 알고리즘(Memetic Algorithm)은 생물학에서의 진화 메커니즘을 모방한 유전적 집단 기반 메타휴리스틱 최적화 알고리즘의 일종으로, 유전 알고리즘(Genetic Algorithm)의 하위 알고리즘인 하이브리드(Hybrid)중 하나이며, 기존의 유전 알고리즘상에 로컬 탐색을 추가한 알고리즘이다. 로컬 탐색은 유전 알고리즘에서 얻어진 모집단 솔루션 주변의 솔루션을 확인하여 더 객관적인 값을 얻을 수 있도록 해 준다. 그러나, 이러한 로컬 탐색은 밈틱 알고리즘에서 가장 많은 시간이 소요 되는 서브루틴으로 전반적인 성능 및 솔루션 품질에 큰 영향을 미친다.
본 논문에서는 밈틱 알고리즘에서의 로컬 탐색을 GPU를 기반으로 하여 성능을 개선하고자 하였으며, 온도 어닐링 기반 소프트맥스 함수를 수정하여, 병렬화를 통해 O(n) 시간에 여러 개의 2차원 할당 행렬을 동시에 생성할 수 있는 방법(GPLSIMA-QAP; GPU-based Parallel Local Search Improvement in Memetic Algorithm for Quadratic Assignment Problem)을 설계 구현하였다(여기에서 n은 문제의 크기이다). 설계한 방법을 기반으로 2차할당문제(QAP: Quadratic Assignment Problem)를 푸는 것을 목표로 그 성능을 비교 평가하였다.
설계한 특수 소프트맥스 함수인 병렬 마스크드 소프트맥스(PM-Softmax; Parallel Masked Softmax) 기반의 GPLSIMA-QAP로 GPU 상에서, 2차할당문제에서 문제의 크기 100 이상의 대규모 인스턴스 10개에 대해 실험하였으며, 기존의 기술들과 유사한 솔루션 품질을 보이면서도 훨씬 더 짧은 실행 시간을 보여 주었고, 기존 연구들은 인스턴스에 따라 그 실행 시간이 크게 변동하는 반면 제안하는 GPLSIMA-QAP는 그 변동이 월등히 적은 것으로 나타났다. 또한, 병렬 실행 가능한 설계 덕분에 대규모 인스턴스에서도 통상적인 GPU 메모리를 최소로 사용하여 동시 구동됨을 확인할 수 있었다.