질문의 성격으로 인해 많은 배경 정보를 포함해야합니다 (왜냐하면 질문의 범위를 좁히는가?). 다음과 같이 요약 할 수 있습니다.

매우 큰 조합 검색 공간에서 지역 최적을 찾는 방법은 무엇입니까?

배경

툴 지원 슈퍼 플레이 커뮤니티에서는 비용을 최소화하기 위해 비디오 게임 콘솔 또는 에뮬레이터에 특수 제작 된 (실시간으로 생성되지 않은) 입력을 제공하려고합니다 (보통 완료 시간). 현재이 작업을 수행하는 방법은 프레임 단위로 게임을하고 각 프레임에 대한 입력을 지정하여 종종 실행 부분을 여러 번 다시 실행하는 것입니다 (예 : 최근 에 젤다의 전설 : 오카리나의 시간에 대해 최근에 게시 된 실행 은 재시도 횟수는 총 198,590 회입니다.

이러한 런을 목표로 삼는 것은 일반적으로 경로 계획과 순회라는 두 가지 주요 요소로 이어집니다. 전자는 후자보다 훨씬 “창의적”이다.

경로 계획은 플레이어가 게임을 완료하기 위해 전체적으로 탐색해야하는 방법을 결정하는 것으로, 종종 런에서 가장 중요한 부분입니다. 예를 들어 사용할 정렬 방법을 선택하는 것과 유사합니다. 세계 최고의 버블 정렬은 단순히 백만 요소에 대한 빠른 정렬을 능가하지 않습니다.

그러나 완벽을 추구함에있어서 순회 (경로 수행 방법)도 큰 요소입니다. 유추를 계속하면 정렬 알고리즘이 구현되는 방식입니다. 특정 경로를 입력하지 않으면 일부 경로를 수행 할 수도 없습니다. 이것은 가장 지루한 도구 보조 프로세스이며 완료된 생산을 몇 달 또는 몇 년이 걸리게하는 것입니다. 그것은 같은 아이디어를 다른 것으로 변형시키는 것이 가장 좋을 때까지 내려 가기 때문에 (인간 에게는) 어려운 과정은 아니지만, 인간은 그들의 관심 범위에서 너무 많은 변형을 시도 할 수 있습니다. 이 작업에 기계를 적용하는 것이 여기에 적절 해 보입니다.

나의 목표는 이제 닌텐도 64 시스템에 대해 일반적으로 순회 프로세스를 자동화하는 것 입니다. 이 문제에 대한 검색 공간은 지금까지 무차별 대입 방식으로 공격에 너무 큽니다. N64 실행의 N 프레임 세그먼트 2 개 보유 ^30N 입력의 단지 30 프레임 (30 프레임 초)이 개 갖는 의미 가능한 입력, ⁹⁰⁰ 가능한 입력하는 단계; 완전한 2 시간 실행을위한 솔루션은 물론 이러한 잠재적 인 솔루션을 테스트하는 것은 불가능합니다.

그러나 나는 전체 실행의 전체 글로벌 최적화를 시도하는 데 관심이 없습니다 (또는 오히려 시도조차하지 않을 것입니다). 오히려 초기 입력이 주어지면 런 의 특정 세그먼트 에 대한 로컬 최적 (또는 반 전역 최적화의 경우 가장 가까운 n 로컬 최적)을 근사하고 싶습니다 . 즉, 경로와 해당 경로의 초기 통과가 주어지면 비용을 최소화하기 위해 해당 통과의 이웃을 검색하지만 문제를 해결할 수있는 모든 경우를 시도하는 것으로 변질하지 마십시오.

따라서 내 프로그램은 시작 상태, 입력 스트림, 평가 기능을 수행하고 평가 결과를 최소화하여 로컬 최적을 출력해야합니다.

현재 상태

현재 모든 프레임 워크를 관리하고 있습니다. 여기에는 에뮬레이터 조작, 설정 및 해제, 구성 등을 통해 입력 스트림을 평가하는 것이 포함됩니다. 그리고 일종의 자리 표시 자로서 옵티마이 저는 매우 기본적인 유전자 알고리즘입니다. 입력 스트림의 모집단을 평가하고, 승자를 저장 / 교체하며, 우승자 스트림을 변경하여 새로운 모집단을 생성합니다. 이 프로세스는 시간 또는 생성 번호와 같은 임의의 기준이 충족 될 때까지 계속됩니다.

이 프로그램의 가장 느린 부분은 입력 스트림의 평가입니다 . 이것은 n 개의 프레임에 대한 게임 에뮬레이션을 포함하기 때문 입니다. (내가 이런 종류의 물건에 후크를 제공하는 내 자신의 에뮬레이터를 쓸 시간이 있었지만 지금은 다른 프로세스에서 기존의 에뮬레이터의 메시지를 합성하고 메모리를 수정하는 중입니다.) 200 프레임을 평가하는 데 약 14 초가 걸립니다. 따라서 함수 평가 수를 최소화하는 알고리즘 (선택권 제공)을 선호합니다.

에뮬레이터를 동시에 관리하는 프레임 워크에서 시스템을 만들었습니다. 따라서 선형 성능 규모 로 한 번에 여러 스트림을 평가할 수 있지만 실제로 실행중인 에뮬레이터의 수는 시스템 성능이 저하되기 전에 8 ~ 32 (및 32는 실제로 푸시) 일 수 있습니다. 이는 평가가 진행되는 동안 처리를 수행 할 수있는 알고리즘이 알고리즘을 선택하는 데 도움이된다는 것을 의미합니다.

테스트로, 내 평가 기능 (게임 Banjo Kazooie )은 프레임 당 플레이어에서 목표 지점까지의 거리를 합산하는 것이 었습니다. 이것은 최적의 솔루션이 가능한 한 빨리 그 지점에 가까워 야한다는 것을 의미했습니다. 아날로그 스틱으로 만 돌연변이를 제한하면 괜찮은 해결책 을 얻는 데 하루가 걸렸습니다 . (이것은 동시성을 구현하기 전에였습니다.)

동시성을 추가 한 후 A 버튼 누름의 돌연변이를 활성화하고 점프가 필요한 영역에서 동일한 평가 기능을 수행했습니다. 24 개의 에뮬레이터를 실행하면 초기에 비어있는 입력 스트림에서 목표에 도달하는 데 약 1 시간이 걸렸지 만, 최적의 상태에 근접한 것을 얻으려면 며칠 동안 실행해야 할 것입니다.

문제

내가 직면하고있는 문제는 수학 최적화 필드에 대해 내 최적화 문제를 올바르게 모델링하는 방법을 알지 못한다는 것입니다 ! 예를 들어 Wikipedia에 설명 된 많은 알고리즘의 개념을 대략적으로 따를 수는 있지만 문제를 분류하거나 해당 범주에 대한 최신 알고리즘을 선택하는 방법을 모르겠습니다.

내가 알 수 있듯이, 나는 매우 큰 이웃과의 조합 문제가 있습니다 . 또한 평가 기능은 매우 불 연속적이며 기울기가 없으며 고원이 많습니다 . 또한 제약이 많지는 않지만 문제를 해결하는 데 도움이 될 경우이를 표현할 수있는 기능을 기꺼이 추가 할 것입니다. 예를 들어 시작 버튼을 사용하지 말도록 지정하고 싶지만 일반적인 경우는 아닙니다.

질문

내 질문은 : 어떻게 모델링합니까? 어떤 종류의 최적화 문제를 해결하려고합니까? 어떤 알고리즘을 사용해야합니까? 나는 연구 논문을 읽는 것을 두려워하지 않으므로 내가 무엇을 읽어야하는지 알려주십시오!

직관적으로, 유전자 알고리즘은 실제로 배우지 않는 것처럼 보이기 때문에 최고 일 수는 없습니다. 예를 들어, 시작을 누르면 항상 평가가 더 나빠지는 것처럼 보이면 (게임을 일시 중지하기 때문에) “언제든지 시작을 누르는 것은 쓸모가 없습니다.” 그러나 Super Mario 64의 이른바 “뒤로 긴 점프 일시 중지”와 같이 시작을 누르는 것이 최적 이기 때문에이 목표조차 들리는 것처럼 사소한 것은 아닙니다 ! 여기서 뇌는 훨씬 더 복잡한 패턴을 배워야 할 것이다. “플레이어가이 특정 상태에 있고 버튼 누름 조합을 계속할 때를 제외하고는 시작을 누르는 것은 쓸모가 없습니다 .”

수정에 더 적합한 다른 방식으로 입력을 나타내야합니다 (또는 기계가 배울 수 있음). 실제로 필요한 것은 여러 프레임에 걸쳐있을 수있는 “액션”이기 때문에 프레임 당 입력이 너무 세밀 해 보입니다. 그러나 많은 발견이 프레임별로 이루어 지므로 완전히 배제 할 수는 없습니다. 위에서 언급 한 후진 점프는 프레임 수준의 정밀도를 요구합니다. 또한 입력이 직렬로 처리된다는 사실은 대문자로 표시 할 수있는 것이어야하지만 어떻게 해야할지 모르겠습니다.

현재 (반응 형) 타부 검색, 매우 큰 이웃 검색, 교육 학습 기반 최적화 및 Ant 식민지 최적화에 대해 읽고 있습니다.

이 문제는 무작위 유전자 알고리즘 이외의 다른 문제로 다루기가 너무 어렵습니까? 아니면 실제로 오래 전에 해결 된 사소한 문제입니까? 읽어 주셔서 감사합니다. 모든 답변에 미리 감사드립니다.

답변