Программные продукты и системы

Для многих реальных практических задач характерна ситуация, когда существует большая БД с результатами наблюдений за сложной системой, но адекватной модели этой системы пока нет. В таких случаях применяют интеллектуальные информационные технологии (ИИТ) для предварительного решения задач моделирования, классификации, прогнозирования и пр. Однако само по себе проектирование ИИТ является достаточно сложной интеллектуальной процедурой, включающей еще и выбор их эффективных структур. Так, при проектировании генетического алгоритма (ГА) необходимо выбирать его оптимальные настройки, при создании искусственных нейронных сетей (ИНС) – структуру нейросети (количество слоев, количество нейронов на слое, типы функций активации, наличие связей между нейронами), для построения аналитических математических моделей алгоритмом генетического программирования (ГП) – структуру функциональной зависимости.

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

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

Описание подхода

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

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

Данные алгоритмы используют динамическую адаптацию на уровне популяции в ходе решения задачи и централизованную форму управления процессом настройки параметров, хотя и несколько отличную от обычных подходов [4]. Все операторы могут использоваться в одном поколении для создания потомков. Время выполнения операторов не возрастает от поколения к поколению, но увеличивается вместе с размером популяции.

Наиболее известными и часто используемыми ЭА являются ГА и алгоритмы ГП, которые, как и ГА, требуют тщательной настройки параметров для обеспечения их эффективной работы. Вариант самоконфигурации, описанный выше, может применяться и для ГА, и для алгоритма ГП, поскольку порядок и способ подключения операторов селекции, скрещивания и мутации одинаковы. Кроме того, предложенная методология самоконфигурации алгоритма может быть применена также для любых других ЭА. При самоконфигурации алгоритма ГП будем применять самоконфигурируемый ГА (SelfCGA) [5] для тонкой подстройки числовых параметров.

По результатам тестирования предложенных алгоритмов был сделан вывод, что самоконфигурируемые ЭА (SelfCЕA), использующие случайный выбор генетических операторов в соответствии с адаптивно настраивающимся распределением вероятностей, могут быть рекомендованы для практического применения вместо стандартных ЭА, так как демонстрируют более высокую надежность и сопоставимую скорость работы, не требуя затрат на выбор комбинации настроек. Предложенный способ самоконфигурации для ЭА не только позволяет сэкономить время и ресурсы на нахождение лучшей настройки, но и может повысить эффективность алгоритма даже в сравнении с лучшими известными настройками обычных ЭА. Эти результаты подтверждают гипотезу [6] о том, что для сложных задач не существует единственного оптимального алгоритма, так как на разных этапах решения задачи оптимальными являются разные алгоритмы. Предложенные алгоритмы с самоконфигурированием устраняют большинство трудностей для неспециалистов в области эволюционного моделирования и оптимизации при работе с ЭА, не создавая при этом новых проблем.

Формирование ИИТ

Самоконфигурируемый алгоритм ГП (Self­CGP) является подходящим инструментом для автоматизированного проектирования ИИТ, таких как символьные выражения [7] и ИНС с произвольной архитектурой [8], не требует затрат времени и ресурсов на настройку самих инструментов. Перед реализацией данного алгоритма задаются терминальное и функциональное мно- жества проектирования. Для алгоритма ГП, решающего задачу символьной регрессии, функциональное множество состоит из математических функций и процедур, а терминальное – из набора переменных и констант. Для настройки структуры нейронной сети при помощи алгоритма ГП [8] в терминальное множество включают функции активации нейронов, а также входные нейроны для нейросети. При генерации нейросетей алгоритм ГП имеет дело не с числами, а с нейронами, поэтому и допустимые операции из функционального множества специфические:

–      постановка нейронов (блоков нейронов) в один слой, являющаяся ассоциативной;

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

При выполнении первой операции новые связи между нейронами не появляются, при выполнении второй операции выходы нейронов из левой ветви подаются на вход нейронам из правой ветви.

Кроме этого, самоконфигурируемый алгоритм ГП позволяет формировать ансамбли ИИТ, то есть выбирать членов коллектива и способ принятия коллективных решений. Алгоритм включает в себя различные арифметические операции и математические функции и использует модели (ИИТ) разных видов для обеспечения разнообразия среди участников ансамбля. В численных экспериментах в качестве членов ансамбля использовались символьные выражения и нейронные сети, автоматически сгенерированные при помощи SelfCGP. ИИТ отбирались в ансамбль из пула предварительных ИИТ, который включал в себя 20 ИНС и 20 символьных формул (СФ), заранее порожденных SelfCGP. Алгоритм автоматически выбирает конкретные ИИТ, которые вносят существенный вклад в эффективность коллективного решения, и не использует другие.

Программные системы и результаты численных экспериментов

Описанные самоконфигурируемый ГА и самоконфигурируемый алгоритм ГП, ЭА для автоматического генерирования нейросетевых моделей, самоконфигурируемый алгоритм ГП для автоматического создания коллективов ИИТ были реализованы как программный комплекс адаптивных ЭА. Данный программный комплекс включает в себя программные системы «Самоконфигурируемый генетический алгоритм для решения сложных задач безусловной оптимизации (SelfCGA)», «Самоконфигурируемый алгоритм генетического программирования для решения задач символьной регрессии (SelfCGP+SRF)», «Самоконфигурируемый алгоритм генетического программирования для автоматического генерирования нейронных сетей (SelfCGP+ANN)» и «Самоконфигурируемый алгоритм генетического программирования для автоматического создания коллективов интеллектуальных информационных технологий (SelfCGP+ +Ensemble)». Они были протестированы на репрезентативном множестве общепринятых тестовых задач для эволюционных алгоритмов [9] и в дальнейшем применялись при исследовании и сравнении эффективности включенных в них вариантов алгоритмов.

Самоконфигурируемый ГА SelfCGA был успешно апробирован при настройке весовых коэффициентов нейронных сетей, решающих задачи классификации, а также при решении практической задачи выбора эффективного варианта аппаратно-программного комплекса систем управления космическими аппаратами.

Самоконфигурируемые алгоритмы ГП SelfCGP (+SRF, +ANN, +Ensemble) были апробированы на ряде задач аппроксимации, а также при решении реальных практических задач моделирования, классификации и прогнозирования из области техники, медицины, банковского скоринга, компьютерной безопасности и распознавания речи. В общей сложности решено девять практических задач: классификация ирисов, диагностирование рака молочной железы, диагностирование диабета, банковский скоринг в Австралии, банковский скоринг в Германии, прогнозирование деградации солнечных батарей космического аппарата, выявление PROBE-атак, обнаружение спама, ISOLET (распознавание речи). Большинство задач взято из репозитория данных Калифорнийского университета для автоматического обучения [10]. Характеристики решенных задач приведены в таблице. В большинстве из них данные не только числовые, но и категориальные.

Числовые характеристики практических задач

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

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

Результаты решения данной задачи при помощи различных подходов к формированию коллективов следующие: SelfCGP+ANNE – 4,18 %, Self­CGP+SRFE – 5,48 %, SelfCGP+ANN+SRFE – 4,65 %, ANN s.a. – 5,42 %, ANN w.a. – 5,03 %, SRF s.a. – 6,28 %, SRF w.a. – 6,05 %, ANN+SRF s.a. – 6,17 %, ANN+SRF w.a. – 5,56 %, SelfCGP+SRF – 6,21 %, SelfCGP+ANN – 5,43 %.

Для их обозначения использовались сокращения: ANNE – ансамбль нейронных сетей, SRFE – ансамбль символьных выражений, ANN+SRFE – ансамбль из ИНС и символьных выражений, s.a. – простое усреднение, w.a. – взвешенное усреднение. SelfCGP+SRF и SelfCGP+ANN содержат оценку эффективности отдельных ИИТ, сгенерированных SelfCGP.

Данные результаты показывают, что ансамбли, сгенерированные SelfCGP из ИНС или из ИНС и символьных выражений, превосходят другие подходы к формированию коллективов. Кроме того, отдельные ИИТ, сгенерированные SelfCGP, показывают результативность не хуже, чем обычные методы формирования коллектива. Аналогичные выводы могут быть сделаны и для других задач.

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

Литература

1.     Eiben A.E., Smith J.E. Introduction to Evolutionary Computing. Springer Verlag Berlin, 2003.

2.     Haupt R.L., Haupt S.E. Practical genetic algorithms. John Wiley & Sons, Inc., Hoboken, New Jersey, 2004.

3.    Schaefer R., Cotta C., Kołodziej J., Rudolph G. (Eds.). Parallel Problem Solving from Nature PPSN XI 11th International Conf., Kraków, Poland, September 11–15, 2010.

4.     Meyer-Nieberg S., Beyer H.-G. Self-Adaptation in Evolutionary Algorithms. Parameter Setting in Evolutionary Algorithm, 2007.

5.    Semenkin E., Semenkina M. Self-configuring Genetic Algorithm with Modified Uniform Crossover Operator. In: Advances in Swarm Intelligence. Lecture Notes in Computer Science 7331. Springer-Verlag Berlin Heidelberg, 2012, pp. 414–421.

6.    Karafotias G., Smit S.K., Eiben A.E. Tuning Evolutionary Algorithms and Tuning Evolutionary Algorithm Controllers. Bioinspired Optimization Methods and their Applications: Proceedings of the Fifth International Conf. BIOMA-2012. Lyublyana: Jozef Stefan Institute, 2012, pp. 291–300.

7.    Semenkin E., Semenkina M. Self-Configuring Genetic Programming Algorithm with Modified Uniform Crossover Operator. In: Proc. of the IEEE CEC, 2012, Brisbane, Australia.

8.    Semenkin E., Semenkina M. Artificial neural networks design with self-configuring genetic programming algorithm: Bioinspired Optimization Methods and their Applications: Proceedings of the Fifth International Conf. BIOMA-2012. Lyublyana: Jozef Stefan Institute, 2012, pp. 291–300.

9.    Finck S., Hansen N., Ros R. and Auger A. Real-parameter black-box optimization benchmarking 2009. In: Presentation of the noiseless functions. Technical Report, Researh Center PPE, 2009.

10. Frank A., Asuncion A. UCI Machine Learning Repository Irvine, CA: University of California, School of Information and Computer Science. URL: http://archive.ics.uci. edu/ml (дата обращения: 10.07.2012).