Тесты - Оптимизация по алгоритму светлячков

В машинном обучении алгоритм численной оптимизации часто применяется для нахождения набора значений для переменных (обычно называемых весовыми значениями), которые минимизируют некую меру ошибки. Например, в классификации по логистической регрессии используется математическое уравнение, где при наличии n переменных-предикторов нужно определить n+1 весовых значений. Процесс определения весовых значений называют обучением модели. Идея заключается в использовании набора обучающих данных, имеющих известные правильные выходные значения. Алгоритм оптимизации находит весовые значения, которые минимизируют ошибку, т. е. разницу между вычисленными и правильными выходными значениями.

Алгоритмов оптимизации очень много. В этой статье поясняется сравнительно новый метод (впервые опубликованный в 2009 году), называемый оптимизацией по алгоритму светлячков (firefly algorithm, FA). Оптимизация FA вольно моделирует поведение роя светлячков.

Хороший способ получить представление о том, что такое оптимизация FA, и понять, куда я клоню в этой статье, - взглянуть на демонстрационную программу на рис. 1. Цель этой программы - использовать оптимизацию FA для нахождения минимального значения функции Михалевича (Michalewicz function) при пяти входных переменных. Функция Михалевича является стандартной тестовой функцией, применяемой для оценки эффективности алгоритмов численной оптимизации. При пяти входных значениях эта функция имеет минимальное значение z = -4.6877, находящееся в x = (2.2029 1.5707, 1.2850, 1.9231, 1.7205).

Рис. 1. Оптимизация по алгоритму светлячков в действии

Функция Михалевича трудна для большинства алгоритмов оптимизации, поскольку она имеет несколько локальных минимальных значений и несколько плоских областей (где все значения z почти одинаковы). Визуализировать функцию Михалевича с пятью входными значениями не так-то легко, но вы можете получить представление о характеристиках функции, изучив график функции для двух входных значений (рис. 2). Определение функции в математических терминах показано в нижней части этой иллюстрации.

Рис. 2. Функция Михалевича для двух переменных

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

Размерность задачи устанавливается в 5, поскольку у нас пять входных значений. FA является итеративным процессом и требует максимального значения счетчика цикла. Итерации цикла в оптимизации машинного обучения часто называют эпохами, и в демонстрационной программе максимальное значение равно 1000 итераций. Это значение варьируется в зависимости от задачи, но 1000 - вполне разумное начальное значение. В FA присутствует элемент случайности, а потому демонстрационная программа указывает для генератора случайных чисел произвольное начальное (зародышевое) значение, равное 0.

При выполнении демонстрационной программы (рис. 1) лучшая (наименьшая) ошибка, связанная с лучшей позицией, найденной на данный момент, показывалась через каждые 100 итераций. По окончании работы алгоритма лучшая найденная позиция для любого светлячка была x = (2.2033, 1.5711, 1.2793, 1.1134, 2.2216). Это решение близко, но не совсем точно соответствует оптимальному решению x = (2.2029 1.5707, 1.2850, 1.9231, 1.7205). Значение функции Михалевича в решении, найденном FA, было -4.45, что близко к истинному минимальному значению -4.69. Ошибка решения FA составила 0.0561.

В этой статье предполагается, что вы умеете программировать хотя бы на среднем уровне, но ничего не знаете о численной оптимизации или об алгоритме светлячков. Демонстрационная программа написана на C#, но у вас не должно возникнуть особых проблем, если вы захотите выполнить рефакторинг кода под другой язык вроде JavaScript или Python.

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

Общая структура демонстрационной программы

Общая структура программы представлена на рис. 3. Чтобы создать демонстрационную программу, я запустил Visual Studio и выбрал шаблон C# Console Application. Я назвал проект FireflyAlgorithm. В этой программе нет значимых зависимостей от .NET Framework, поэтому подойдет любая недавняя версия Visual Studio.

Рис. 3. Структура демонстрационной программы

После загрузки кода шаблона я переименовал в окне Solution Explorer файл Program.cs в более описательный FireflyProgram.cs, и Visual Studio автоматически переименовала класс Program за меня. В начале кода я удалил все лишние выражения using, оставив только ссылку на пространство имен верхнего уровня System.

Я кодировал демонстрационную программу, используя по большей части подход со статическими методами, а не полноценный объектно-ориентированный подход. Вся управляющая логика программы находится в Main. Этот метод начинает с отображения цели демонстрации:

Затем задаются параметры, необходимые для FA:

Значения параметров выводятся с помощью этих выражений:

Алгоритм светлячков запускается так:

Метод Main завершается отображением результатов FA:

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

Вникаем в алгоритм светлячков

Алгоритм светлячков, представленный в этой статье, основан на научно-исследовательской статье Син-Си Йенг (Xin-She Yang) «Firefly Algorithms for Multimodal Optimization» 2009 года. Процесс работы этого алгоритма показан графиком на рис. 4. График представляет упрощенную имитацию задачи нахождения минимума, где всего два входных значения, X и Y, а глобальное минимальное значение находится в X = 0 и Y = 0. Используется три светлячка. Firefly[0] находится в точке (2, 1) и поэтому он ближе всех к правильному решению. Firefly[1] находится в точке (-4, -4), а firefly[2] - в точке (-8, 8), т. е. дальше всех от решения.

Рис. 4. Алгоритм светлячков

Настоящие светлячки - это летающие насекомые, которые светятся благодаря биолюминесценции, предположительно для привлечения партнера. Каждый светлячок может светиться с разной интенсивностью. В FA светлячки, находящиеся в более лучшей позиции (подразумевающей меньшую ошибку), святятся с большей интенсивностью. В таком случае на рис. 4 firefly[0] светится с самой высокой интенсивностью, firefly[1] - со средней интенсивностью, а firefly[2] - со слабой.

Базовая идея FA в том, что светлячка будет привлекать любой другой светлячок, который светится ярче, и эта привлекательность (расстояние, преодолеваемое до более яркого светлячка) сильнее, если расстояние между двумя светлячками меньше. Поэтому на рис. 4 firefly[0] светится ярче всех и не движется. Он привлекает к себе firefly[1] и firefly[2], и они движутся к firefly[0]. Поскольку firefly[1] ближе, чем firefly[2] к firefly[0], firefly[1] переместится на большее расстояние, чем firefly[2].

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

Рис. 5. Алгоритм светлячков в псевдокоде

Первая серьезная проблема - определение интенсивности свечения светлячка. Поскольку FA является мета-эвристическим алгоритмом, вы вольны определять эту интенсивность как угодно при условии, что более высокая интенсивность связана с более хорошей позицией (более хорошим решением). Следующая серьезная проблема - определение привлекательности, чтобы к более ярко светящейся цели смещались более близкие светлячки, а не более отдаленные.

Реализация алгоритма светлячков

Определение метода Solve начинается с:

Локальные переменные minX и maxX устанавливают границы для позиции каждого светлячка. Значения, использованные здесь, 0.0 и 3.2 (приблизительно Pi), специфичны для функции Михалевича. Для оптимизации машинного обучения с нормализованными данными распространены значения -10.0 и +10.0.

Локальные переменные B0 (базовая бета), g (гамма) и a (альфа) управляют привлекательностью одного светлячка для другого. Используемые значения (1.0, 1.0 и 0.20) рекомендованы в исходной научно-исследовательской статье. Локальная переменная displayInterval контролирует то, насколько часто отображается сообщение о прогрессе.

Затем создается пустой рой светлячков:

Объект Firefly определен в программе и инкапсулирует позицию, связанную ошибку и соответствующую интенсивность свечения. Изначально все светлячки являются null-объектами. Определение класса Firefly будет представлено в следующем разделе этой статьи. Далее создается экземпляр роя (swarm) и помещается в случайную позицию. Для каждого светлячка вызывается конструктор объекта Firefly:

Конструктор неявно устанавливает позицию в (0.0, 0.0, 0.0, 0.0, 0.0), а связанной ошибке и интенсивности свечения присваивает фиктивные значения 0.0. Затем каждому компоненту массива position присваивается случайное значение между minX и maxX (0.0 и 3.2 соответственно). Далее вычисляются ошибка и интенсивность свечения текущего светлячка:

Функция Error будет вскоре представлена. Здесь интенсивность свечения светлячка определяется как инверсия ошибки, так чтобы малые значения ошибок имели высокую интенсивность, а большие значения ошибки - низкую. Число 1 в делителе предотвращает деление на ноль, когда ошибка равна 0. Инициализация завершается проверкой только что созданного светлячка на предмет того, имеет ли он лучшую найденную позицию:

Основной цикл обработки начинается с этих выражений:

Альтернатива фиксированному количеству итераций - прерывание, когда значение bestError падает ниже какого-то малого порогового значения (обычно 0.00001). Каждый светлячок сравнивается с остальными, используя вложенные циклы for:

Заметьте: так как индекс каждого цикла for начинается с 0, каждая пара светлячков на каждой итерации цикла while сравнивается дважды. Чтобы переместить светлячок к другому светлячку с более высокой интенсивностью свечения, нужно сначала вычислить привлекательность:

Переменная beta определяет привлекательность и будет использоваться в момент перемещения firefly[i]. Ее значение зависит от квадрата расстояния между firefly[i] и firefly[j], которое вычисляется вспомогательным методом Distance. Метод Distance возвращает евклидово расстояние между двумя позициями. Например, если firefly[i] в двух измерениях находится в точке (3.0, 4.0), а firefly[j] - в точке (5.0, 9.0), то расстояние между ними вычисляется как sqrt((5 - 3)^2 + (9 - 4)^2) = sqrt(4 + 25) = sqrt(29) = 5.4. Заметьте, что beta используется квадрат расстояния, что обратно операции извлечения квадратного корня, поэтому вычисление beta может быть упрощено за счет меньшей гибкости (в случае, если вы решите использовать другую меру расстояния).

Само перемещение осуществляется следующими выражениями:

Здесь k-й компонент позиции firefly[i] перемещается на долю beta расстояния между firefly[i] и firefly[j] к firefly[j]. Затем к каждому k-ому компоненту позиции добавляется небольшое случайное слагаемое (term). Это помогает предотвратить застревание алгоритма в неоптимальных решениях. Каждый компонент позиции проверяется, чтобы выяснить, выходит ли он за диапазон, и, если да, присваивается случайное значение, возвращающее его в диапазон.

Вложенные циклы в коде перемещения завершаются обновлением ошибки и интенсивности свечения только что перемещенного светлячка:

Метод Solve заканчивается следующими выражениями:

После сравнения каждой пары светлячков и перемещения менее интенсивно светящихся светлячков к более интенсивно светящимся массив объектов Firefly сортируется от наименьшей ошибки к наибольшей, чтобы лучшая ошибка была в swarm[0]. Этот объект проверяется, чтобы выяснить, найдено ли новое лучшее решение. Сортировка массива объектов Firefly также оказывает важное влияние на изменение их местоположения внутри массива, чтобы объекты обрабатывались в разном порядке на каждой итерации цикла while.

Вспомогательные методы

Метод Solve вызывается вспомогательные методы Distance и Error, которые в свою очередь вызывают вспомогательный метод Michalewicz. Вспомогательный метод Distance определяется так:

Вспомогательный метод Michalewicz определяется следующим образом:

Если вы обратитесь к математическому определению функции Михалевича внизу рис. 2, то увидите, что функция имеет порядок 2m. Однако значение m обычно приравнивается 10, поэтому в коде используется константа, равная 20. Вспомогательный метод Error определяется как:

Метод Error просто возвращает результат возведения в квадрат разности между известным минимальным значением функции Михалевича и вычисленным значением. Эта фиктивная функция ошибки вычисляется очень быстро, но в большинстве сценариев машинного обучения вычисление функции ошибки может оказаться весьма длительным.

Класс Firefly

Определение класса Firefly начинается с:

Этот класс наследует от интерфейса IComparable, чтобы массивы и списки, содержащие этот объект, можно было сортировать автоматически. Поля данных определены как public для простоты. Поскольку между ошибкой и интенсивностью свечения имеется сопоставление «один к одному», либое из этих двух полей можно было бы отбросить. Конструктор класса выглядит так:

Вы можете рассматривать множество проектировочных альтернатив. Здесь конструктор просто выделяет пространство под массив position. Единственный открытый метод - CompareTo:

Метод CompareTo упорядочивает объекты Firefly от наименьшей ошибки к наибольшей. Эквивалентная альтернатива - упорядочение от большей интенсивности свечения к меньшей.

Пара комментариев

Реализация алгоритма светлячков, представленная в этой статье, основана на уже упомянутой научно-исследовательской статье 2009 года. Исходный алгоритм породил несколько вариаций. В научно-исследовательской статье приведены некоторые данные, согласно которым предполагается, что FA превосходит оптимизацию на основе роя частиц, по крайней мере применительно к некоторым эталонным задачам оптимизации. Я отношусь к этому с долей скепсиса. Однако, по моему мнению, FA точно окажется очень полезным в сценарии, где целевая функция, подлежащая минимизации, имеет несколько решений. Хотя это не совсем очевидно, оказывается, что FA способен к автоматической самоорганизации во вторичные рои (sub-swarms), которые могут параллельно находить несколько решений.

Джеймс Маккафри (Dr. James McCaffrey) работает на Microsoft Research в Редмонде (штат Вашингтон). Принимал участие в создании нескольких продуктов Microsoft, в том числе Internet Explorer и Bing. С ним можно связаться по адресу jammc@microsoft.com.

Выражаю благодарность за рецензирование статьи эксперту Microsoft Тодду Беллоу (Todd Bello), Марсиано Морено Диасу Коваррубиасу (Marciano Moreno Diaz Covarrubias) и Элиссон Сол (Alisson Sol).

Источник: msdn.microsoft.com

Комментарии: