Расчеты эволюции на C#

Written on 09 Января 2014.

В данной статье будет рассмотрена библиотека C# для расчета эволюции. Применение библиотеки показано на четырех примерах: оптимизация функции, символическая регрессия (приближение), предсказание временного ряда, задача коммивояжёра.

• Скачать исходники - 113 Кб
• Скачать демонстрационный проект - 97 Kb

Введение

Было проведено много разных исследований в области расчета эволюции, обусловивших появление ряда различных эволюционных алгоритмов. Много исследователей тщательно изучило эти методы и пыталось применить их к большому диапазону задач. Известно, что имеется много разных задач, которые невозможно решить точно за приемлемый период времени с помощью традиционных методов. Также есть много задач, не имеющих формального пути решения, что делает их решение очень трудным или даже невозможным с помощью традиционных методов. Примером является задача коммивояжёра (TSP), где требуется найти кратчайший путь вокруг заданного количества городов, посетив их все всего однажды и вернувшись к начальному городу в конце. Применение к некоторым из таких задач расчетов эволюции зачастую позволяет найти хорошее решение за приемлемый период времени. Эти методы не гарантируют отыскание точного решения конкретной задачи, но они находят очень хорошее решение, близкое к лучшему решению. Вот почему эти методы широко используются для решения множества разных задач, которые нельзя решить (или их решение слишком трудное) традиционными методами.

В данной статье будет рассмотрена библиотека C# для расчета эволюции. Библиотека реализует несколько известных эволюционных алгоритмов, таких как генетические алгоритмы (GA), генетическое программирование (GP) и программирование выражений генов (GEP), и может применяться для решения множества разных задач. Применение библиотеки показано на четырех примерах: оптимизация функции, символическая регрессия (приближение), предсказание временного ряда, задача коммивояжёра. Библиотека гибкая и повторно применимая, что позволяет решать разные задачи с ее помощью. В статье нет подробного описания эволюционных алгоритмов. Вместо этого статья кратко знакомит с идеей этих алгоритмов и дает список ссылок, позволяющий детально изучить эти методы.

Расчеты эволюции

История генетических расчетов начинается в 1960-е годы, когда первый труд по данной теме был опубликован Джоном Холлэндом, представившим первые идеи о генетических алгоритмах (GA) на основе теории эволюции. С тех пор было сделано много исследований в области расчетов эволюции, обусловивших появление множества разных методов. Большинство из этих методов было тщательно изучено и применено к решению множества разных задач, дав очень хорошую эффективность для большинства из них. Несмотря на весьма долгую историю генетических расчетов, эти методы все еще активно изучаются, и появляются разные новые подходы, увеличивающие число задач, решаемых с помощью этих методов.

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

Простейший вид кроссовера – одноточечный кроссовер: выбирается случайная точка из двух хромосом, и эти две хромосомы обмениваются своими частями:

Другой популярный вид операции кроссовера – двуточечный кроссовер: выбираются две случайные точки, и хромосомы обмениваются своими частями между этими двумя точками. Эти два вида кроссовера наиболее популярны в GA, но они не единственные имеющиеся. В действительности есть много разных вариантов этого оператора, варьирующихся от задачи к задаче. Есть задачи, где эти два классических варианта кроссовера вообще не применимы, поэтому у них есть собственный специальный вариант, специфичный для задачи.

Оператор мутации работает только с одной хромосомой, меняя хромосому произвольно. Одноточечная мутация меняет всего один ген в хромосоме:

Как в случае кроссовера, оператор мутации тоже имеет много разных вариантов, более характерных для конкретных типов задач.

После создания начальной популяции каждая итерация алгоритма GA состоит из следующих шагов:
1.    Кроссовер – выбираются случайные индивидуумы, и к ним применяется операция кроссовера;
2.    Мутация – выбираются случайные индивидуумы, и к ним применяется оператор мутации;
3.    Вычисляется значение пригодности каждого индивидуума;
4.    Селекция – выбираются индивидуумы для новой генерации.

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

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

В 1992 году Джон Коза предложил существенно новый подход – генетическое программирование (GP). В GP отдельные члены популяции (хромосомы) не являются линейными символьными строками фиксированной длины, кодирующими возможное решение задачи, как в GA, но они являются программами, дающими решение задачи при выполнении. Эти программы выражаются в виде деревьев разбора GP различных размеров и форм, что делает эти методы гибкими в применении к широкому диапазону задач. Различие в представлении хромосом – главное и почти единственное различие между этим методом и GA. Общий дарвиновский принцип выживания сохраняется, но меняются операторы мутации и кроссовера и расчет функции пригодности. Вместо мутации отдельного гена в строковой хромосоме в GP оператор мутации может переродиться как отдельный узел дерева, как целая ветвь дерева хромосомы. То же самое происходит с кроссовером – вместо обмена частями хромосом одинаковой длины, в GP хромосомы обмениваются своими ветвями, различающимися по размеру и по форме. Однако всегда необходимо проверять хромосомы и урезать их, если они выросли слишком длинными.

Чтобы вычислить значение пригодности отдельной хромосомы в GP, хромосома не просто передается в качестве значения некоторой функции, вычисляющей значение пригодности. Вместо этого выполняется программа, представленная хромосомой, и вычисляется значение пригодности в зависимости от вывода программы.

В 2001 году Кандидо Феррейра ввел еще один метод под названием программирование выражений генов (GEP). Идея метода походит на генетическое программирование и генетические алгоритмы. Метод тоже работает с программами, дающими решение после выполнения, что уподобляет его GP. Но представление этих программ в GEP отличается. В данном методе хромосомы не представляются как деревья, а являются линейными объектами фиксированной длины, как в GA. Такое изменение в представлении хромосомы упрощает реализацию таких генетических операторов, как мутация и кроссовер, но имеет ряд небольших ограничений, чтобы сделать этот оператор безопасным.

* + / a b c a
(a) (b)

Представление хромосомы в GP (a) и GEP (b)

Рисунок выше показывает различие в представлении хромосомы в методах GP и GEP. Обе хромосомы кодируют одну и ту же программу – алгебраическое выражение (a + b) * (c / a). GP представляет хромосому как дерево разбора выражения, но GEP представляет ее как линейную строку, где узлы вышеуказанного дерева разбора записаны в порядке: слева направо, сверху вниз. Строку GEP можно легко преобразовать обратно в дерево разбора, заполнив его слева направо и сверху вниз, учитывая информацию о количестве параметров каждой функции.

Применение библиотеки

При создании библиотеки главной идеей было придание ей гибкости и многоразовости, что позволяет применять ее для решения разных задач. Код библиотеки не зависит ни от какой конкретной задачи, но реализует общие принципы расчетов эволюции и таких алгоритмов, как генетические алгоритмы, генетическое программирование и программирование выражений генов. Такие сущности расчета эволюции, как популяция, хромосомы, методы селекции и функции пригодности, реализованы в виде отдельных классов, что облегчает их объединение для решения конкретной задачи. В большинстве случаев пользователю библиотеки необходимо лишь определить функцию пригодности для своей задачи, а затем определить тип хромосомы, алгоритм селекции и ряд других параметров, таких как размер популяции, частота мутации и кроссовера, и т.д. Если конкретная задача требует специфических вариантов хромосом или генетических операторов мутации и кроссовера, пользователь может создать собственный класс хромосомы, реализовав интерфейс IChromosome или унаследовав от одного из уже имеющихся классов хромосом. То же самое касается методов селекции и функций пригодности – если требуется специальный алгоритм селекции или функция пригодности, надо создать класс, реализующий интерфейс ISelectionMethod или IFitnessFunction, соответственно. После создания любых пользовательских классов, реализующих определенные выше интерфейсы, эти классы будут работать со всеми остальными классами библиотеки, расширяя ее и позволяя решать специфические задачи.

Для демонстрации применения библиотеки будут описаны 4 примеры, использующие разные алгоритмы расчета эволюции:
•    Оптимизация функции (генетические алгоритмы);
•    Символическая регрессия (генетическое программирование и программирование выражений генов);
•    Предсказание временных рядов (генетическое программирование и программирование выражений генов);
•    Задача коммивояжёра (генетические алгоритмы).

Оптимизация функции

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

// определить функцию оптимизации
public class UserFunction : OptimizationFunction1D
{
    public UserFunction( ) :
        base( new DoubleRange( 0, 255 ) ) { }

    public override double OptimizationFunction( double x )
    {
        return Math.Cos( x / 23 ) * Math.Sin( x / 50 ) + 2;
    }
}
...
// создать генетическую популяцию
Population population = new Population( 40,
    new BinaryChromosome( 32 ),
    new UserFunction( ),
    new EliteSelection( ) );
// запустить одну эру популяции
population.RunEpoch( );

В примере выше создается популяция из 40 хромосом, каждая из которых является двоичной хромосомой длиной 32 бита, используется метод селекции элиты, и используется функция пригодности, предназначенная для оптимизации линейных функций. В примере выше и во всех остальных примерах нет четких ссылок на генетические алгоритмы или другие эволюционные методы. Создание популяции одинаково во всех реализованных генетических методах. В основном сама хромосома определяет тип используемого метода, потому что хромосома определяет представление решения задачи и реализацию используемых генетических операторов.

Символическая регрессия (приближение)

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

Код для решения задачи похож на вышеприведенный код. Используется тот же класс популяции и тот же класс метода селекции. Единственное отличие – функция пригодности, что очевидно, потому что задача и класс хромосомы другие. Для решения задачи можно использовать класс GPTreeChromosome – если надо применить метод генетического программирования, или класс GEPChromosome – если надо применить метод программирования выражений генов.

// приближаемая функция
double[,] data = new double[5, 2] {
    {1, 1}, {2, 3}, {3, 6}, {4, 10}, {5, 15} };
// создать популяцию
Population population = new Population( 100,
    new GPTreeChromosome( new SimpleGeneFunction( 6 ) ),
    new SymbolicRegressionFitness( data, new double[] { 1, 2, 3, 5, 7 } ),
    new EliteSelection( ),
    0.1 );
// запустить одну эру популяции
population.RunEpoch( );

В примере выше приближаемая функция определяется с двумерным массивом пар (X, Y). Еще одна любопытная особенность примера выше – последний аргумент конструктора класса Population – значение указывает, что 10% из новой генерации будет состоять из новых случайных хромосом, но 90% будут лучшими членами текущей генерации.

Предсказание временного ряда

Задача предсказания временного ряда нацелена на построение модели, предсказывающей будущие значения функции на основе истории – прошлых значений функции. Для выполнения задачи модель строится (обучается) на основании предоставленных учебных выборок данных и, когда модель начинает давать удовлетворительные результаты на основании учебного набора, модель используется для предсказания будущих значений функции.

// временной ряд для предсказания
double[] data = new double[13] { 1, 2, 4, 7, 11, 16, 22, 29, 37, 46, 56, 67, 79 };
// константы
double[] constants = new double[10] { 1, 2, 3, 5, 7, 11, 13, 17, 19, 23 };
// размер скользящего окна
int windowSize = 5;
// создать популяцию
Population population = new Population( 100,
new GPTreeChromosome( new SimpleGeneFunction( windowSize + constants.Length ) ),
new TimeSeriesPredictionFitness( data, windowSize, 1, constants ),
new EliteSelection( ) );
// запустить одну эру популяции
population.RunEpoch( );

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

Задача коммивояжёра

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

// создать популяцию
Population population = new Population( populationSize,
    new PermutationChromosome( citiesCount ),
    new TSPFitnessFunction( map ),
    new EliteSelection( )
    );

Учитывая, что класс PermutationChromosome входит в библиотеку, необходимо создать лишь новую функцию пригодности (TSPFitnessFunction) для новой задачи и использовать остальной существующий код для решения новой задачи. Однако можно повысить эффективность алгоритма. Стандартный обобщенный класс PermutationChromosome позволяет найти более или менее хорошее решение, но наследование класса и переопределение операции кроссовера повышает эффективность. Пользовательский класс TSPChromosome (смотрите исходники приложения) реализует так называемый жадный кроссовер, позволяющий найти лучшее решение за меньшее время.

Долгие годы метод генетических алгоритмов давал лучшие результаты для решения задачи коммивояжера. Задача столь популярна и актуальна, что ежегодно проводится соревнование на лучший метод решения задачи. В конце 1990-х для решения задачи был применен другой подход, показавший эффективность повыше. Новый метод пришел из области искусственного интеллекта и основан на идее муравьиных куч (смотрите алгоритмы системы муравьев (AS) и системы муравьиной кучи (ACS)).

Заключение

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

форум разработчиков