Расчеты эволюции на C# - Предсказание временного ряда и задача коммивояжёра
ОГЛАВЛЕНИЕ
Предсказание временного ряда
Задача предсказания временного ряда нацелена на построение модели, предсказывающей будущие значения функции на основе истории – прошлых значений функции. Для выполнения задачи модель строится (обучается) на основании предоставленных учебных выборок данных и, когда модель начинает давать удовлетворительные результаты на основании учебного набора, модель используется для предсказания будущих значений функции.
// временной ряд для предсказания
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 примера показывают, что библиотека реализовала начальную цель – сделать ее гибкой, расширяемой, повторно применимой и простой в применении. Хотя есть еще много несделанной работы из-за нынешнего обширного диапазона эволюционных вычислительных методов, тем не менее библиотека подходит для решения множества разных задач и легко расширяется для решения новых задач. Работа над библиотекой позволила глубже узнать эволюционные методы и изучить алгоритмы генетического программирования и программирования выражений генов.