Коллективный самонастраивающийся метод оптимизации на основе бионических алгоритмов

Актуальность темы исследования. При решении многих практических задач часто возникает необходимость выбора наилучшего решения по некоторому критерию из множества возможных. Математически такой выбор формализуется в виде задачи оптимизации.
Широко известные методы математического программирования для решения задач оптимизации представляют собой детерминированную итерационную процедуру пошагового улучшения одного текущего решения. Эффективность таких алгоритмов основывается на полном использовании удобных с точки зрения оптимизации свойств (выпуклость, гладкость, и т.п.) целевой функции, которые, к тому же, полагаются известными заранее. Для многих практических задач такие свойства либо не выполняются, либо неизвестны заранее, поэтому применение данных методов нецелесообразно. Для решения таких задач в настоящее время используются недетерминированные (стохастические), работающие одновременно с большим количеством текущих решений (многоагентные) алгоритмы, являющиеся более эффективными и универсальными. Например, генетический алгоритм [46], метод роя частиц [101], муравьиный алгоритм [79] и т.д.
Многоагентные алгоритмы, основанные на использовании популяции, работают с набором потенциальных решений. Каждое решение постепенно улучшается и оценивается, таким образом, каждое потенциальное решение влияет на то, как будут улучшены другие решения. Большинство популяционных методов заимствовало эту концепцию из биологии: процесс поиска наилучшего решения «копирует» некоторый природный процесс либо поведение определенных видов животных, причем учитываются их видовые особенности. Класс сложных систем, именуемых как алгоритмы стайного типа, также часто употребляется термин «бионические алгоритмы», – богатый источник нестандартных численных методов, с помощью которых можно решать сложные задачи, когда известно недостаточно информации об оптимизируемой функции.
5
Один из особенно популярных и часто используемых бионических методов известен как стайный алгоритм оптимизации (Particle Swarm Optimization, PSO), также называемый методом роя частиц (МРЧ). Данный метод был предложен для решения задач безусловной оптимизации с вещественными переменными Кеннеди и Эберхартом в 1995 году [101]. Идея стайного алгоритма была почерпнута из социального поведения стада копытных, стаи птиц, косяка рыб и т.д., то есть процесс поиска оптимального решения данным методом имитирует поиск пищи группой животных, насекомых или птиц одного вида без уточнения самого вида.
Помимо метода роя частиц есть множество других алгоритмов, аналогичных ему, но имитирующих некоторые свойства или поведение уже конкретных видов животных. Например, алгоритм поиска кукушек (Cuckoo Search Algorithm, CSA), разработанный Янгом и Дэбом в 2009 году [4], имитирующий гнездовой паразитизм некоторых видов кукушек, подкладывающих свои яйца в гнезда других птиц. Тем же Янгом были разработаны и другие алгоритмы стайного типа: в 2009 году алгоритм светлячков (Firefly Algorithm, FFA) [140], использующий свойство свечения этих насекомых, в 2010 году алгоритм летучих мышей (Bat Algorithm, BA) [139], имитирующий процесс поиска пищи летучими мышами, учитывая их способность к эхолокации. Также как пример можно привести еще один бионический метод, но разработанный уже Карабогом в 2005 году [99] – искусственный алгоритм пчелиной семьи (ABC), который тоже часто используется для решения оптимизационных задач и имитирует поведение кормовых медоносных пчел. Кроме того, следует упомянуть алгоритм поиска стаей волков (Wolf Pack Search, WPS) [75], речь о котором пойдет далее. Примеров бионических методов можно приводить множество, ведь с каждым годом их разрабатывается все больше.
Следует также отметить, что большинство алгоритмов стайного типа изначально разработано для решения задач безусловной оптимизации с вещественными переменными, и все они имеют некоторые параметры, которые необходимо подбирать при решении той или иной задач (наиболее значимый в

6
этом понимании «параметр» – размер популяции потенциальных решений). Однако год за годом предлагаются различные модификации этих методов:
1. Модификации, связанные с гибридизацией алгоритмов (например, гибридный алгоритм на базе метода роя частиц и алгоритма поиска кукушек, представленный в статье [135]; или гибридный метод на базе алгоритма светлячков и муравьиного алгоритма [91]);
2. Модификации для расширения круга решаемых задач (например, решение оптимизационных задач с бинарными переменными алгоритмом летучих мышей [115] или решение задач многокритериальной оптимизации алгоритмом светлячков [68]);
3. Модификации для настройки параметров алгоритмов (например, уже в 1998 году Ши и Эберхарт опубликовали работу [127], а в 2000 году они же ввели еще один параметр для алгоритма PSO [81]).
Однако исследования показали, что невозможно заранее определить, какой именно из этих алгоритмов следует применить для решения той или иной оптимизационной задачи, кроме того, как уже было упомянуто, для каждого алгоритма нужно выбирать заранее размер популяции потенциальных решений, что в свою очередь также является сложной задачей.
Таким образом, цель диссертационной работы состоит в повышении эффективности решения задач оптимизации бионическими алгоритмами за счет автоматизации их выбора и настройки параметров.
Поставленная цель предопределила необходимость решения следующего комплекса взаимосвязанных задач:
1. Исследовать эффективность различных бионических методов для решения задач условной и безусловной оптимизации с вещественными и бинарными переменными, определить наиболее успешный из них;
2. Разработать коллективный самонастраивающийся бионический алгоритм для решения задач условной и безусловной оптимизации с вещественными переменными;

7
3. Разработать модификации нового алгоритма для решения задач условной и безусловной оптимизации с бинарными переменными;
4. Реализовать разработанные алгоритмы в виде программных систем и оценить их эффективность на репрезентативном множестве тестовых задач;
5. Провести апробацию разработанных алгоритмов при решении реальных практических задач.
Научная новизна диссертационной работы состоит в следующем:
1. На основе пяти известных бионических алгоритмов разработан, реализован и исследован новый коллективный метод решения задач безусловной оптимизации с вещественными переменными, отличающийся от известных способом организации взаимодействия популяций и настройки параметров;
2. Разработана, реализована и исследована модификация нового метода для решения задач безусловной оптимизации с бинарными переменными;
3. Разработана, реализована и исследована модификация нового метода для решения задач условной оптимизации с вещественными и бинарными переменными;
4. На основе разработанного метода оптимизации предложены новые алгоритмы автоматического проектирования нейронных сетей и машин опорных векторов.
Апробация работы. Процесс разработки алгоритмов и результаты проведенных исследований докладывались в период 2010-2015 гг. на 35 конференциях различного уровня, среди которых 11 зарубежных, 8 Международных, 1 Всероссийская с международным участием и 15 молодежных научных конференций, в том числе: International Conference on Swarm Intelligence (ICSI, Hefei, China, 2014; Beijing, China, 2015), Informatics in Control, Automation and Robotics (ICINCO, Vienna, Austria, 2014; Colmar, France, 2015), International Congress on Advanced Applied Informatics (AAI, Okayama, Japan, 2015), Congress on

8
Evolutionary Computations of the IEEE World Congress on Computational Intelligence (CEC WCCI, Beijing, China, 2014), International Conference on Computer Science and Artificial Intelligence (ICCSAI, Wuhan, China, 2014), Conference on Engineering and Applied Sciences Optimization (OPT-I, Kos Island, Greece, 2014), Workshop on Computational Approaches to Subjectivity, Sentiment and Social Media Analysis, (Baltimore, USA, 2014), Congress on Evolutionary Computations (CEC, Cancun, Mexico, 2013), Genetic and Evolutionary Computation Conference (GECCO, Amsterdam, Holland, 2013), International Workshop on Mathematical Models and its Applications (IWMMA, Baykal, Russia, 2012; Krasnoyarsk, Russia, 2013, 2014, 2015), XIV Национальная конференция по искусственному интеллекту с международным участием (КИИ, г.Казань, 2014), V Международная конференция «Системный анализ и информационные технологии» (САИТ, Красноярск, 2013), XVI, XVIII и XIX Международные научные конференции «Решетневские чтения» (г. Красноярск, 2012, 2014, 2015 гг.), и др. Отдельные результаты работы обсуждались на научном семинаре института информационных технологий университета г. Ульм (Германия, 2014). Диссертация в целом обсуждалась на научно-технических семинарах кафедры системного анализа и исследования операций СибГАУ и кафедры систем автоматизированного проектирования (РК6) НИУ МГТУ им. Н.Э.Баумана.
Разработанные алгоритмы использованы при выполнении исследований в рамках российско-германских проектов (совместно с университетом г. Ульм) «Распределенные интеллектуальные информационные системы обработки и анализа мультилингвистической информации в диалоговых информационно- коммуникационных системах» (ФЦП ИР, ГК No11.519.11.4002) и «Математическое и алгоритмическое обеспечение автоматизированного проектирования аппаратно-программных комплексов интеллектуальной обработки мультилингвистической информации в распределенных высокопроизводительных системах космического назначения» (ФЦП НПК, ГК No 16.740.11.0742), российско-словенского проекта (совместно с университетом г. Марибор) «Manpower control strategy determination with self-adapted evolutionary

9
and biologically inspired algorithms» (ARRS Project BI-RU/14-15-047), а также в рамках проекта No8.5541.2011 «Развитие теоретических основ автоматизации математического моделирования физических систем на основе экспериментальных данных» и проекта No 140/14 «Разработка теоретических основ эволюционного проектирования интеллектуальных информационных технологий анализа данных» тематического плана ЕЗН СибГАУ. Данная работа поддержана грантом Фонда содействия развитию малых форм предприятий в научно-технической сфере в рамках программы У.М.Н.И.К., стипендией имени Аниты Борг от компании Google (Google Anita Borg Scholarship) и стипендией Президента РФ молодым ученым и аспирантам, осуществляющим перспективные научные исследования и разработки по приоритетным направлениям модернизации российской экономики.
Зарегистрированы следующие программные системы: «Коллективный метод безусловной оптимизации на основе стайных бионических алгоритмов» (Свидетельство о государственной регистрации программ для ЭВМ No2014610132), «Коллективный метод условной оптимизации на основе стайных бионических алгоритмов» (Свидетельство о государственной регистрации программ для ЭВМ No2013661150), «Коллективный метод безусловной оптимизации на основе стайных бионических алгоритмов для решения задач с бинарными переменными» (Свидетельство о государственной регистрации программ для ЭВМ No2014611007), «Машины опорных векторов, автоматически сгенерированные коллективными методами условной и безусловной оптимизации на основе стайных бионических алгоритмов» (Свидетельство о государственной регистрации программ для ЭВМ No2014610968), «Автоматическое генерирование нейронных сетей алгоритмами стайного типа» (Свидетельство о государственной регистрации программ для ЭВМ No2014616237), «Проектирование SVM- классификаторов коллективными бионическими алгоритмами с выбором информативных входов» (Свидетельство о государственной регистрации программ для ЭВМ No2015611847).

10
Публикации. По материалам данной работы опубликовано 22 печатные работы, в том числе 6 статей в научных изданиях Перечня ВАК, 10 в изданиях, индексируемых в международной базе Scopus, из них 4 индексированы также в Web of Science (публикации в сборниках ведущих международных конференций, а также публикации в сборниках различных всероссийских, региональных конференций).