Новый супералгоритм NIGHS построен на принципах музыкальной импровизации

Каждый день мы сталкиваемся с разными задачами, которые требуют от нас выбора лучшего решения из множества возможных. Например, как спланировать свой день, как выбрать подарок для друга или как приготовить вкусный ужин. Для решения этих задач мы используем свой опыт, знания, интуицию и логику. Но что делать, если задача слишком сложная или не имеет однозначного решения? Например, как спроектировать самолет, как распределить электричество по городу или как найти лекарство от болезни. Для решения этих задач нужны специальные методы и алгоритмы, которые называются оптимизацией.


Оптимизация — это процесс поиска лучшего решения для задачи с учетом некоторых ограничений и критериев. Например, если мы хотим спроектировать самолет, то мы должны учитывать такие ограничения, как вес, размер, скорость и безопасность самолета, а также такие критерии, как стоимость, эффективность и надежность самолета. Лучшее решение — это такое решение, которое удовлетворяет всем ограничениям и имеет наилучшее значение критериев.

Существует много разных алгоритмов для решения задач оптимизации. Одни из них основаны на математических вычислениях и анализе градиента функции, которая описывает задачу. Например, метод наискорейшего спуска или метод Ньютона. Другие алгоритмы основаны на имитации некоторых явлений в природе или жизни и используют случайность и правила для поиска решения. Например, генетический алгоритм или алгоритм роя частиц.

Один из таких алгоритмов был предложен в 2001 году корейским ученым Зонг Ву Гим (Zong Woo Geem) и вдохновлен процессом музыкальной импровизации. Как вы знаете, музыканты могут создавать новые мелодии на ходу, используя свою память, воображение и интуицию. Они выбирают ноты из некоторого множества возможных нот (например, из тональности или аккорда) и сочетают их в разных соотношениях (например, по ритму или гармонии), чтобы получить красивую и гармоничную мелодию. При этом они могут использовать как мелодические ходы из своей памяти (например, из известных песен или композиций), так и новые сочетания из своего воображения или интуиции. Таким образом, они ищут лучшее решение для задачи создания музыки.

Можно ли применить этот метод к другим задачам, не связанным с музыкой? Оказывается, что можно. Ученые придумали специальный алгоритм, который называется гармоническим поиском (HS). Он работает по тому же принципу, что и музыкальная импровизация, но вместо нот он использует числа. Эти числа представляют собой параметры, которые нужно подобрать для решения какой-то задачи. Например, если мы хотим спроектировать самолет, то эти параметры могут быть весом, размером, скоростью и безопасностью самолета. А если мы хотим распределить электричество по городу, то эти параметры могут быть мощностью, напряжением и сопротивлением электрической сети.

Алгоритм HS хранит некоторое количество решений в своей памяти, которую называет гармонической памятью (HM). Каждое решение в HM — это набор чисел, которые аналогичны нотам в музыке. Алгоритм HS создает новые решения на основе трех действий: памяти, настройки и случайности. Действие памяти означает, что новое решение может быть скопировано из HM с некоторой вероятностью. Действие настройки означает, что новое решение может быть изменено с некоторой вероятностью и в некотором диапазоне. Действие случайности означает, что новое решение может быть сгенерировано случайным образом из всего пространства поиска. Таким образом, алгоритм HS ищет лучшее решение для задачи оптимизации.

Алгоритм HS имеет много преимуществ перед другими алгоритмами оптимизации. Он простой и не требует сложных вычислений. Он хорошо ищет решения в разных областях и может применяться к разным типам задач. Он также гибкий и может быть легко улучшен или изменен.

Однако алгоритм HS также имеет некоторые недостатки и ограничения. Он может не найти самое лучшее решение или застрять на одном решении при решении некоторых сложных задач. Он также имеет низкую точность и медленную скорость поиска. Эти проблемы связаны с тем, что алгоритм HS не может самостоятельно менять свою стратегию поиска в зависимости от ситуации.

Стратегия поиска — это способность алгоритма искать новые решения в разных областях или улучшать уже найденные решения. Эти две способности называются поиском и уточнением. Поиск помогает алгоритму не пропустить хорошие решения, которые могут быть где-то далеко. Уточнение помогает алгоритму сделать решение лучше, если оно уже близко к идеальному. Хороший алгоритм оптимизации должен уметь находить баланс между поиском и уточнением в зависимости от ситуации.

Ученые из Китая придумали как избавиться от недостатков алгоритма HS и предложили революционно новый интеллектуальный алгоритм поиска глобальной гармонии, основанный на улучшенной стратегии стабильности поиска (NIGHS).

Алгоритм NIGHS улучшает гармонический поиск за счет введения новых операторов, которые делают его более гибким и точным. Он ведет себя как музыкант, который хочет написать красивую песню. Музыкант помнит, какие звуки ему по душе, и он хранит их в своей памяти. Но он не хочет повторяться, а хочет создать что-то новое и оригинальное. Поэтому он берет мелодии из своей памяти и меняет их немного, чтобы получить новые. Иногда он берет звуки совсем случайно, чтобы добавить разнообразия. Так он генерирует новые песни и проверяет, насколько они ему нравятся. Если песня ему нравится больше, чем те, что он уже написал, он сохраняет ее в своей памяти и удаляет одну из старых песен. Так он постепенно улучшает свои песни и приближается к своей идеальной.

Алгоритм NIGHS делает то же самое, но не со звуками, а с числами. Он хочет найти такие числа, которые делают какую-то функцию минимальной или максимальной. Это может быть полезно для решения разных задач, например, как построить дом так, чтобы он был крепким и дешевым, или как распределить ресурсы так, чтобы получить максимальную прибыль. Алгоритм NIGHS хранит лучшие результаты в своей памяти и меняет их немного или случайно, чтобы получить новые. Он проверяет, насколько хороша функция с новыми числами, и если она лучше, чем со старыми, сохраняет новые числа в своей памяти и удаляет одни из старых. Так он постепенно улучшает свои результаты и приближается к оптимальным.

Алгоритм NIGHS умеет делать это лучше, чем другие алгоритмы, потому что он учитывает две вещи: скорость и точность. Он может менять размер шага, на который он меняет числа, в зависимости от того, насколько он близок к оптимальным числам. Если он далеко от них, он делает большие шаги, чтобы быстрее двигаться. Если он близко к них, он делает маленькие шаги, чтобы не пропустить их и уточнить их. Это помогает ему адаптироваться к разным формам функций и не застревать в плохих местах.