LLM-асистований пошук оптимізує розклад супутників спостереження Землі

Супутники спостереження Землі (EOS) відіграють ключову роль у моніторингу навколишнього середовища та управлінні ресурсами. Нове покоління гнучких супутників спостереження Землі (AEOS) пропонує розширену гнучкість, але водночас створює надзвичайну складність у плануванні їхнього розкладу, перетворюючи це на NP-складну проблему.

Проблема ручного проектування евристик

Хоча евристичні алгоритми, такі як адаптивний пошук у великих околицях (ALNS), є ефективними, їхня продуктивність значною мірою залежить від вручну розроблених «евристик руйнування» — правил, які визначають, як інтелектуально розбивати та перебудовувати потенційний розклад. Цей процес проектування є значним вузьким місцем, що вимагає глибоких знань та досвіду людини.

Новий підхід: evALNS та LLM

Для подолання цієї проблеми дослідницька група розробила новий метод, який використовує великі мовні моделі (LLM) для автоматичного проектування та еволюції цих критично важливих евристик. Їхній запропонований алгоритм, evALNS, використовує креативну силу LLM для генерації нових та ефективних стратегій планування.

Фреймворк DPEC для навчання LLM

Визнаючи, що LLM бракує спеціалізованих знань у цій складній предметній області, дослідники представили інноваційний фреймворк ко-еволюційних обчислень з подвійною популяцією (DPEC). Цей фреймворк створює дві еволюціонуючі популяції евристик: одна генерується LLM, а інша заснована на перевірених, розроблених експертами правилах. Дві популяції періодично обмінюються своїми найкращими індивідами, дозволяючи LLM навчатися від експертних стратегій та інтегрувати ці знання у власні креативні рішення.

Цей процес додатково посилюється стратегією функціонального вбудовування природної мови (FNLE), де описи природною мовою, вбудовані в код, допомагають LLM краще «розуміти» логіку та призначення евристик, які вона розвиває.

Результати та нова парадигма

Широкі експерименти показали, що алгоритм evALNS, що працює на базі фреймворку DPEC, значно перевершив традиційний ALNS, який використовував лише оператори, розроблені експертами. Новий підхід досяг середнього покращення прибутку на 8.48% у різних складних сценаріях. Ця робота не тільки пропонує більш ефективне рішення для планування супутників, але й встановлює потужну нову парадигму для використання LLM для автоматизації проектування складних алгоритмів для інших комплексних реальних задач оптимізації.