Software & Systems

Среди множества различных многоагентных стохастических алгоритмов оптимизации одним из наиболее изученных является стайный алгоритм, или Particle Swarm Optimization (PSO) [1]. Идея данного метода почерпнута из социального поведения некоторых видов животных, например, стай птиц, косяка рыб или стада копытных. Исследования показали эффективность алгоритма и целесообразность его применения при решении задач как безусловной, так и условной оптимизации функций вещественных переменных. Постоянно предлагаются новые варианты алгоритма для повышения эффективности метода либо для расширения круга решаемых задач.

Помимо PSO, существуют и другие алгоритмы, использующие социальные и биологические идеи, имитирующие поведение определенных видов животных. Наибольший интерес из последних разработок представляют следующие бионические алгоритмы: алгоритм стай волков (Wolf Pack Search, WPS) [2], алгоритм светлячков (Firefly Algorithm, FFA) [3], алгоритм поиска кукушек (Cuckoo Search Algorithm, CSA) [4] и алгоритм летучих мышей (Bat Algorithm, BA) [5]. Перечисленные метаэвристики, как и PSO, изначально были разработаны для решения вещественных оптимизационных задач и наиболее близки к PSO, что отличает их от других аналогичных подходов (пчелиные алгоритмы, алгоритм умных капель и т.п.). Как уже было сказано, каждый из упомянутых алгоритмов имитирует некоторую характеристику определенного вида животных: CSA – способ откладывания яиц кукушками, BA – эхолокацию летучих мышей, FFA – излучение, исходящее от светлячков, WPS – процесс охоты стаи волков.

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

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

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

Таблица 1

Результаты сравнения составляющих алгоритмов

Кооперативный бионический алгоритм (Co-Operation of Biology Related Algorithms, COBRA)

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

Главный параметр, настраиваемый для всех алгоритмов, – размер популяции. Сама по себе задача выбора числа индивидов достаточно сложна, так как нужно определить такой размер попу- ляции, чтобы за определенное количество вычислений целевой функции было достигнуто оптимальное решение, с одной стороны, и чтобы этих вычислений было как можно меньше – с другой. Поэтому было принято решение автоматизировать процесс настройки размера популяции, а именно: размер каждой популяции может как увеличиваться, так и уменьшаться в зависимости от изменения значения функции пригодности. Другими словами, если на t-й итерации средняя пригодность индивидов k-й популяции лучше средней пригодности других популяций, k-я популяция считается победителем, а все остальные проигравшими. Из проигравших популяций удаляются индивиды – они добавляются к победившей популяции. Таким образом, определяется лучший алгоритм для задачи на каждой итерации.

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

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

Разработанный коллективный метод оптимизации на основе стайных бионических алгоритмов был реализован в виде единой программной системы и назван COBRA (Co-Operation of Biology Related Algorithms) [6].

Тестирование разработанного алгоритма

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

Далее все пять составляющих алгоритмов и COBRA были исследованы на 28 тестовых функциях из CEC 2013 Special Session on Real-Para­meter Optimization [7], среди которых пять унимодальных функций, 15 базовых многоэкстремальных функций и 8 составных функций, являющихся специальными комбинациями базовых. Размерность задач – 2, 3, 5, 10 и 30. В соответствии с методикой проведения экспериментов [7] для каждой задачи программа запускалась 51 раз. В итоге сравнение проводилось по двум критериям: самый лучший результат, полученный алгоритмом для данной задачи, и лучший средний результат.

В процессе исследований было установлено, что СOBRA показывала все более и более лучшие результаты по обоим критериям с увеличением размерности задач. По первому критерию коллективный алгоритм выигрывал у остальных 2 раза при размерности 2, 11 раз при размерности 3 и столько же раз при размерности 5. По второму критерию были следующие результаты: 19 побед, 22 победы, 24 победы при размерностях 2, 3 и 5 соответственно. При размерности 10 по первому критерию коллективный алгоритм выигрывал у остальных 18 раз, PSO – 5 раз, WPS – 4 раза, FFA – 1 раз. При размерности 30 по первому критерию только у PSO и WPS было по одной победе, во всех остальных случаях выигрывал коллективный алгоритм. По второму критерию при размерности 10 у PSO было 2 победы, в то время как COBRA выиграла 26 раз, а при размерности 30 по всем функциям «победителем» оказалась COBRA.

Применение разработанного алгоритма для настройки нейронных сетей

Разработанный кооперативный алгоритм был использован для настройки весовых коэффициентов искусственных нейронных сетей (ИНС), структура которых была определена заранее: полносвязные перцептроны с 3 и 5 нейронами на одном скрытом слое, биполярные функции активации.

С помощью этих ИНС решались две практические задачи анализа данных: банковский скоринг по БД из Австралии и Германии. Исходные данные для этих задач были взяты из репозитория автоматического обучения Калифорнийского университета [8]. Для задачи банковского скоринга в Австралии число входов равно 14 (6 категориальных, 8 вещественных), 1 выход, 2 класса, размер выборки равен 690. Для задачи банковского скоринга в Германии число входов равно 20, 1 выход, 2 класса, размер выборки равен 1 000. На выходе получается положительное или отрицательное решение о выдаче кредита, то есть определение кредитоспособности клиента по его анкетным данным и предыстории.

С точки зрения оптимизации настройка нейросетевых классификаторов сводится к настройке от 45 до 105 вещественных весовых коэффициентов, то есть является серьезной задачей для алгоритма оптимизации. В таблице 2 приведена информация о результатах решения этих двух задач, полученных другими исследователями альтернативными алгоритмами. Данная информация почерпнута из научной периодики.

Таблица 2

Результаты решения задач банковского скоринга

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

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

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

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

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

Расширение класса решаемых задач путем адаптации алгоритма к задачам условной и/или многокритериальной оптимизации тоже представляется вполне возможным и естественным.

Литература

1.     Kennedy J., Eberhart R. Particle Swarm Optimization. Proc. of IEEE Intern. Conf. on Neural Networks, 1995, vol. IV, pp. 1942–1948.

2.     Yang Ch., Tu X., Chen J. Algorithm of Marriage in Honey Bees Optimization Based on the Wolf Pack Search. Intern. Conf. on Intelligent Pervasive Computing «IPC2007», 2007, pp. 462–467.

3.     Yang X.S. Firefly algorithms for multimodal optimization. Lecture Notes in Computer Sc., 2009, no. 5792, pp. 169–178.

4.     Yang X.S., Deb S. Cuckoo search via L´evy flights. Proc. of World Congress on Nature & Biologically Inspired Computing «NaBic 2009», IEEE Publications, USA, 2009, pp. 210–214.

5.     Yang X.S. A new metaheuristic bat-inspired algorithm. Nature Inspired Cooperative Strategies for Optimization «NICSO 2010», Springer, SCI 284, 2010, pp. 65–74.

6.     Akhmedova Sh., Semenkin E. Co-Operation of Biology Related Algorithms. Proc. of the 2013 IEEE Congress on Evolutionary Computation, Cancún, México, 2013, pp. 2207–2214.

7.     Liang J.J., Qu B.Y., Suganthan P.N., Hernández-Díaz A.G. Problem Definitions and Evaluation Criteria for the CEC 2013 Special Session on Real-Parameter Optimization. Technical Report 2012, Computational Intelligence Laboratory, Zhengzhou Univ., Zhengzhou China, and Technical Report, Nanyang Technological Univ., Singapore.

8.     Frank A., Asuncion A. UCI Machine Learning Repository. URL: http://archive.ics. uci.edu/ml (дата обращения: 01.07.2013).

References

1.     Kennedy J., Eberhart R. Proc. of IEEE Int. Conf. on Neural Networks. IV. 1995, pp. 1942–1948.

2.     Yang Ch., Tu X., Chen J. Int. Conf. on Intelligent Perva­sive Computing – IPC2007. 2007, pp. 462–467.

3.     Yang X.S. Lecture Notes in Computer Science. 2009, no. 5792, pp. 169–178.

4.     Yang X.S., Deb S. Proc. of World Congress on Nature & Biologically Inspired Computing (NaBic 2009). IEEE Publ., USA, 2009, pp. 210–214.

5.     Yang X.S., Nature Inspired Cooperative Strategies for Optimization (NICSO 2010). Springer, 2010, vol. 284, pp. 65–74.

6.     Akhmedova Sh., Semenkin E. Proc. of the 2013 IEEE Congress on Evolutionary Computation. Cancún, México, 2013, pp. 2207–2214.

7.     Liang J.J., Qu B.Y., Suganthan P.N., Hernández-Díaz A.G. Problem Definitions and Evaluation Criteria for the CEC 2013 Special Session on Real-Parameter Optimization. Tech. Report, Zhengzhou Univ., Zhengzhou, China, Nanyang Technological Univ., Singapore, 2013.

8.     Frank A., Asuncion A. UCI Machine Learning Repository. Available at: http://archive.ics. uci.edu/ml (accessed 01 July 2013).