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

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

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

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

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

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

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

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

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

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

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

Що це означає для розробників

Ця розробка відкриває нові можливості для розробників, дозволяючи автоматизувати створення складних алгоритмів оптимізації для різноманітних реальних задач, використовуючи креативні можливості LLM для генерації та вдосконалення евристик.

Ключові факти

Розклад гнучких супутників спостереження Землі (AEOS) є NP-складною проблемою через їхню підвищену гнучкість.
Продуктивність евристичних алгоритмів, таких як ALNS, сильно залежить від ручного проектування «евристик руйнування», що вимагає глибоких людських знань.
Дослідники розробили метод evALNS, який використовує великі мовні моделі (LLM) для автоматичного проектування та еволюції цих критичних евристик.
Фреймворк Dual-Population Co-Evolutionary Computing (DPEC) дозволяє LLM навчатися від експертних стратегій через періодичний обмін найкращими індивідами між двома популяціями евристик.
Стратегія Functional Natural Language Embedding (FNLE) допомагає LLM краще розуміти логіку евристик через описи природною мовою в коді.