GECCO 21 Parallel GA KNP

알고리즘 선택 문제의 해결 속도를 높이는 병렬 유전 알고리즘

저자:

• 알레한드로 마레로 --- @amarrerod
• 에두아르도 세그레도 --- @esegredo
• 코로모토 레온 --- @cleon

추상적인:

특정 최적화 문제를 해결하기 위해 사용할 최적화 기술을 결정하는 것은 수십 년 동안 최적화 분야에서 직면해 온 중요하고 힘든 작업입니다. 위의 문제는 알고리즘 선택 문제(ASP)로 알려져 있습니다. 많은 연구자들이 다양한 문제에 대해 ASP를 해결하려고 노력해 왔습니다. 이전 연구에서 고려된 최적화 기법들은 주로 빠른 속도로 실행될 수 있는 최적화 기법들이었습니다. 그러나 진화 알고리즘과 같은 ASP 해결을 위한 보다 정교한 최적화 접근 방식을 고려하면 관련된 계산 비용이 크게 증가합니다. 우리는 잘 알려진 NP-하드 0/1 배낭 문제(KNP)에 적용되는 유전 알고리즘(GA)의 다양한 구성을 고려하여 ASP를 해결하는 데 관심이 있습니다. 위의 작업에는 계산 비용이 많이 드는 작업인 KNP의 다양한 기능을 가진 광범위한 인스턴스에 적용될 때 성능을 평가하기 위해 해당 GA의 상당수 구성을 실행하는 작업이 포함됩니다. 따라서 현재 연구의 주요 목표는 ASP 문제를 해결하기 위한 첫 번째 단계로 짧은 시간 내에 최적의 목표 값 측면에서 경쟁력 있는 결과를 얻을 수 있는 효율적인 병렬 GA를 제공하는 것입니다. 계산 결과에 따르면 우리의 접근 방식은 효율적으로 확장할 수 있고 KNP 인스턴스를 해결하는 데 걸리는 평균 경과 시간을 상당히 줄일 수 있습니다.

---

종이

결과

확장성 테이블