최적화 유도 연산자를 갖는 유전 알고리즘에 대한 수학적 관점

최근 머신러닝(ML) 분야의 연구들은 추론 시간(inference time)에 유전 알고리즘을 적용하여 최적화 문제의 해답을 반복적으로 개선합니다. 이 과정에서 사용되는 기본적인 돌연변이(mutation) 및 재조합(recombination) 연산자는 전통적으로 연구되던 것들과 질적으로 다릅니다. 돌연변이는 더 이상 무작위적이지 않습니다. ML 알고리즘은 목적 함수를 개선하는 것을 목표로 해답을 돌연변이시킵니다. 마찬가지로, 재조합 역시 부모 해답들의 무작위적인 콜라주에 기반하지 않습니다. 대신, 이는 입력값으로부터 개선된 해답을 합성하는 것이 목표인 ML 최적화 기반 연산자입니다. 따라서 이러한 돌연변이 및 재조합 연산자는 목적 함수를 개선할 가능성이 더 높지만, 계산 비용은 훨씬 높습니다. 우리는 유전 알고리즘의 일반적인 모델을 도입하고, 강화학습(reinforcement learning)의 언어를 사용하여 이 모델 내에서 최적화를 질의 복잡도 문제(query-complexity problem)로 공식화합니다. 그런 다음 특수화된 모델들을 연구합니다. 우리는 일부 최적화 문제가 해결되기 위해 생성(generation), 돌연변이, 그리고 재조합을 필요로 함을 보여줍니다. 이후 우리는 실제 ML 유전 알고리즘의 핵심 특징인 해답 풀(solution pool) 내 다양성의 비자명한 역할을 포착하는 이 프레임워크 내의 문제군에 대해 질적으로 타이트한 알고리즘들을 얻습니다.