автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Адаптивные эволюционные алгоритмы решения сложных задач оптимизации

На правах рукописи

ВОРОЖЕЙКИН АНТОН ЮРЬЕВИЧ

АДАПТИВНЫЕ ЭВОЛЮЦИОННЫЕ АЛГОРИТМЫ РЕШЕНИЯ СЛОЖНЫХ ЗАДАЧ ОПТИМИЗАЦИИ

05.13.01 - системный анализ, управление и обработка информации (космические и информационные технологии)

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Красноярск - 2008

003453042

Работа выполнена в ФГОУ ВПО «Сибирский федеральный университет»,

г. Красноярск

Научный руководитель:

Доктор технических наук, профессор Семенкин Евгений Станиславович

Официальные оппоненты: Доктор технических наук, профессор

Терсков Виталий Анатольевич

кандидат технических наук Галыгин Артем Николаевич

Ведущая организация:

Томский государственный университет

Защита состоится 11 декабря 2008 г. в 14 часов на заседании диссертационного совета Д 212.249.02 при Государственном образовательном учреждении высшего профессионального образования «Сибирский государственный аэрокосмический университет имени академика М.Ф. Решетнева» по адресу: 660014, г. Красноярск, пр. им. газеты «Красноярский рабочий»,

С диссертацией можно ознакомиться в научной библиотеке Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнева.

Автореферат разослан 7 ноября 2008 г.

Ученый секретарь

31.

диссертационного совета

/ /О

Е.П. Моргунов

А

/

Общая характеристика работы

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

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

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

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

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

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

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

Сформулированная цель предопределила следующую совокупность решаемых задач:

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

2. Разработать вероятностный ГА для решения задач условной и безусловной многокритериальной оптимизации.

3. Провести сравнительный анализ эффективности стандартного и вероятностного ГА на тестовых задачах условной и безусловной многокритериальной оптимизации.

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

5. Выполнить апробацию разработанных алгоритмов при решении реальных практических задач.

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

Научная новизна результатов диссертационной работы состоит в следующем:

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

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

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

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

Работа выполнена при финансовой поддержке Фонда содействия развитию малых форм предприятий в научно-технической сфере в рамках НИОКР «Разработка математического и алгоритмического обеспечения системы поддержки принятия решений для задач инвестиционного анализа», в соответствии с тематическим планом ЕЗН СибГАУ «Бионические методы идентификации и оптимизации сложных систем» (№ Б 1.1.05), а также поддерживалась грантами на выполнение молодежных проектов, проводимых в рамках программы развития СФУ (2007, 2008 гг.) и грантами для молодых ученых Красноярского краевого фонда науки (17С045, 180022).

Реализация результатов работы. Созданные в ходе работы над диссертацией программные системы прошли государственную экспертизу и зарегистрированы в Отраслевом фонде алгоритмов и программ Государственного координационного центра информационных технологий Федерального агентства образования.

Разработанные учебные программные системы используются студентами института математики Сибирского федерального университета и факультета информатики и систем управления Сибирского государственного аэрокосмического университета как лабораторные установки. Данные программные системы включены в качестве инструмента для выполнения лабораторных работ в УМКД по эволюционным алгоритмам моделирования и оптимизации, разработанного для студентов магистратуры в рамках реализации инновационной образовательной программы института математики СФУ.

Программные системы и разработанные алгоритмы прошли апробацию при решении реальных задач управления инвестициями и переданы для использования на производственных предприятиях: Химзавод-филиал

ФГУП «Красмаш» (пос. Подгорный Красноярского края) и ЗАО «ОКБ APT» (г. Красноярск).

Работа дважды признана лучшей на конкурсе международного научного фонда экономических исследований им. Н.П. Федоренко (2006, 2007 гг.). В июле 2008 г. по результатам данной работы диссертанту присуждена Государственная премия Красноярского края за значительные успехи в области разработки математического и алгоритмического обеспечения поддержки принятия решений при управлении реальными инвестициями (распоряжение губернатора Красноярского края от 16.07.2008 № 210-рг).

Основные защищаемые положения:

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

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

3. Новый вероятностный генетический алгоритм для задач'многокритериальной оптимизации с автоматической настройкой вероятности мутации позволяет получать более представительное множество эффективных решений.

Публикации. По теме диссертации опубликовано двадцать семь работ, в том числе четыре в изданиях из перечня ВАК. Список основных публикаций приведен в конце автореферата.

Апробация работы.

Результаты диссертационной работы были доложены и обсуждены на XII Международной научно-технической конференции «Системный анализ в проектировании и управлении», Санкт-Петербург, 2008; Конференции лауреатов и стипендиатов конкурсов международного научного фонда экономических исследований академика Н.П. Федоренко, Москва, 2007; Всероссийской научно-практической конференции «Евразийское пространство - Сибирь: перспективы развития, проблемы, решения», Барнаул, 2007; Международных научно-технических конференциях «Интеллектуальные системы» AIS'07 и AIS'08, Дивноморское, 2007, 2008; Конференции-конкурсе «Технологии Microsoft в теории и практике программирования», г. Новосибирск, 2007; XIII Международном симпозиуме «Сложные системы в экстремальных условиях», г. Красноярск, 2006, и на восьми молодежных научных конференциях.

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

Первая глава диссертации посвящена разработке и исследованию вероятностного генетического алгоритма для решения задач безусловной и условной однокритериальной оптимизации. :

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

В общем виде работу ВГА можно представить следующим образом:

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

2. С помощью оператора селекции выбрать г наиболее пригодных индивидов текущей популяции (родителей). Вычислить вектор вероятностей по формуле:

г 1=1

где п - длина хромосомы, х} -у'-й бит г'-го индивида.

3. В соответствии с распределением Р сформировать популяцию потомков с помощью датчика псевдослучайных чисел.

4. Из популяции родителей и потомков создать новую рабочую популяцию.

5. Новую популяцию подвергнуть мутации.

6. Повторять шаги 2-5 пока не выполнится условие остановки.

Сравнение эффективности ГА и ВГА проводилось на шестнадцати

тестовых задачах безусловной однокритериальной оптимизации. Данный набор задач включает сложные многоэкстремальные функции одной и нескольких переменных, такие как функция Растригина, Розенброка, Катков-ника, Гриванка, Шекеля и др., и входит в стандартный набор тестовых задач для оценки эффективности стохастических алгоритмов оптимизации. Нахождение оптимума данных функций классическими методами оптимизации сильно затруднено в силу наличия большого количества локальных

экстремумов, незначительно отличающихся от глобального, узких зон притяжения и плато.

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

В качестве исследуемых характеристик были выбраны: процент запусков, в которых было найдено оптимальное решение (%); средний номер итерации, на которой впервые было найдено оптимальное решение (Щ.

В результате исследований было установлено, что в целом (по надежности и скорости) при наилучших настройках в 64% случаев стандартный ГА оказывается эффективнее ВГА, однако при наихудших настройках в 91% случаев более эффективным является вероятностный ГА. В среднем, вероятностный ГА в 67% случаев оказывается эффективнее стандартного ГА. Кроме того, вероятностный ГА более эффективен по скорости сходимости (IV) как при наилучших, так и при наихудших настройках.

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

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

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

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

После этого было проведено сравнение стандартного и вероятностного ГА с использованием метода динамических штрафов для учета ограничений. При наилучших настройках стандартный ГА оказался эффективнее в 67% случаев. Однако при наихудших и средних настройках в целом более эффективным оказался вероятностный ГА в 100% и 75% случаев соот-

ветственно. Фрагмент численных результатов сравнения приведен в таблице 1.

Таблица 1. Результат сравнения стандартного и вероятностного ГА

Задача Наилучшие настройки Наихудшие настройки Средняя эф активность

ГА ВГА ГА ВГА ГА ВГА

% N % N % N % N % N % N

Линейная задача 1 76 31,05 64 32,81 12 16,83 14 14,14 41,78 27,67 40,22 26,2

Нелинейная задача 1 58 32,28 66' 32,39 8 25 24 18,25 34,22 28,95 41,33 26,49

Нелинейная задача 2 ТОО 21,22 98 15,02 44 9,93 68 9,12 76,07 14,49 83,56 12,24

Нелинейная задача 3 20 18,В 68 29,94 0 0 22 13,6.4 7,41 19,45 40,89 24,68

Нелинейная задача 4 .94 35,77 92 36,09 52 43,42 48 42,96 72,81' 33,07 72,44 31,86

Процент , "60% 40% 20% 80% 40% 60%

Нетрудно видеть, что даже в тех случаях, когда ВГА уступает стандартному ГА, разница в эффективности незначительна.

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

1. Определить шаг прогноза К.

2. Через каждые К поколений по набранной статистике Р,, г = \,Ик, Л^ ? е {1,2,...} рассчитать изменение вектора вероятностей: АР,=Р, -Рм.

3. Каждому поколению придавать вес, в зависимости от его номера:

4. Рассчитать взвешенное изменение вектора вероятностей:

1=1

5. Рассчитать прогнозируемое оптимальное решение: х""' =(*7')' где х°р' = 1 если Л^ > 0, и х°р' = 0 иначе.

6. Добавить полученное решение в текущую рабочую популяцию и продолжить работу ВГА.

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

В результате исследований алгоритма на задачах безусловной оптимизации было установлено, что при наихудших и усредненных настройках в большинстве случаев (69% и 56% соответственно) ВГА с прогнозом находит оптимальное решение задачи на более ранней стадии работы алгорит-

ма. Также было установлено, что в целом при наихудших настройках ВГА с прогнозом в 56% случаев эффективнее стандартного ГА.

При исследовании алгоритма на задачах условной оптимизации было установлено, что при наилучших настройках ВГА с прогнозом в целом эффективнее ГА в 60% случаев, а при наихудших настройках эффективнее в 67% случаев. Кроме того, как и в случае безусловной оптимизации, алгоритм с прогнозом находит оптимальное решение на более ранней стадии работы алгоритма.

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

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

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

Для решения задач многокритериальной оптимизации генетические алгоритмы должны быть оснащены методами учета многих целевых функций. В качестве базовых были выбраны четыре наиболее распространенные многокритериальные схемы: VEGA (генетический алгоритм векторных оценок), FFGA (генетический алгоритм Фонсеки и Флеминга), NPGA (Паретовский генетический алгоритм с нишами), SPEA (усиленный по Па-рето эволюционный алгоритм). -

Сравнение эффективности стандартного ГА и ВГА проводилось на тестовых задачах безусловной двух-, трех- и четырехкритериальной нелинейной оптимизации с квадратичными целевыми функциями. В качестве исследуемых характеристик были выбраны: разброс точек в пространстве решений (X) и в пространстве критериев (У'), процент Паретовских точек {%) в итоговой популяции. В двухкритериалышй задаче множество Парето представляет собой отрезок прямой, поэтому в данном случае исследовалось среднее расстояние (Ср.р.) от решений до отрезка. Поскольку алгоритмы являются стохастическими, то для каждой настройки алгоритмов эксперименты проводились по 50 раз и исследуемые характеристики усреднялись. Для проверки того, являются ли различия между алгоритмами случайными, применялся тест Колмогорова-Смирнова с 5% уровнем зна-

чимости. Сравнение эффективности проводилось для наилучших и наихудших настроек генетических операторов алгоритмов.

В таблице 2 приведена средняя эффективность ВГА по отношению к стандартному ГА. Представленные в таблице результаты следует интерпретировать следующим образом: положительное число указывает на то, что ВГА эффективнее, чем ГА; отрицательное - ГА эффективнее, чем ВГА. Модуль числа показывает, на сколько процентов один алгоритм эффективнее другого. Из таблицы видно, что ВГА со схемами VEGA, FFGA и NPGA эффективнее, чем ГА, обеспечивает наилучший процент Паретов-ских точек, а ВГА со схемами NPGA и SPEA эффективнее, чем ГА, обеспечивает более репрезентативное множество Парето.

Таблица 2. Í

Схема X У %/Cp.p.

VEGA -2,66 -2,62 - 1,75 -

FFGA -6.61 -6,6 7,88 .

NPGA -0,08 . 0,66 ' .0,69 -

SPEA ' 3,08. - 2,55 -6,27

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

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

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

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

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

Таблица 3. Сравнение методов динамического и адаптивного штрафов

Схема X У %/Ср.р. % доп.

VEGA 8,23 9,4 51,02 47,61

FFGA 120,46 107,65 41,65 330,95

NPGA 83,58 196,96 42,51 153,32

SPEA 7,96 4,05 13,42 21,19

Далее необходимо было установить, какая из многокритериальных схем является наиболее эффективной. В результате проведенных исследований было установлено, что наиболее эффективной является схема 8РЕА. В таблице 4 приведено обобщенное сравнение многокритериальных схем для каждой исследуемой характеристики. Здесь, для учета ограничений использовался метод динамических штрафов, так как ранее было установлено, что он является наиболее эффективным.

Таблица 4. Сравнение многокритериальных схем

Характеристика Стандартный ГА Вероятностный ГА

Разброс точек в X SPEA SPEA

Разброс точек в У SPEA SPEA

Процент Паретовских точек SPEA, VEGA SPEA

Процент допустимых точек SPEA, FFGA SPEA, FFGA

После этого, было проведено сравнение вероятностного и стандартного ГА, использующих метод динамических штрафов. В таблице 5 приведена средняя относительная эффективность ВГА по отношению к стандартному ГА (в процентах). Результаты следует интерпретировать аналогичным образом, как для таблицы 2. Из таблицы видно, что ВГА со схемой SPEA эффективнее, чем ГА обеспечивает наилучший процент допустимых точек и наилучших разброс точек в пространствах X и Y. Однако это различие меньше 1%, и может быть признано незначительным. Кроме того, во всех случаях ВГА обеспечил наилучший процент допустимых точек.

Таблица S. Средняя эффективность ВГА по отношению к ГД (в процентах)

Схема X У % J Cp.p. % доп.

VEGA -15,02 -13,52 -4,3 ■ Л 1,3 -

FFGA -11,79 -10,49 -8,22 - 6.47

NPGA -19,44 -19,19 . -X.4,12 '-.-•5,64'

SPEA 1 0.59 .0,19 -6,51 "'• 0.2? .

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

оператор мутации вручную. На каждом шаге работы алгоритма вероятность мутации рассчитывается автоматически по следующей формуле:

= 0)ч

-> л

иггаче,

где и - длина хромосомы; Д.; и Х^ - разбросы точек в пространстве решений на (Ы)-м и на к-м поколении соответственно; ¿функция Я определяет силу мутации. Таким образом, вероятность мутации увеличивается, если решения-индивиды начинают группироваться около какого-либо локального оптимума, и уменьшается в противном случае. В таблице 6 приведена средняя эффективность адаптивного ВГА по отношению к стандартному ГА (в процентах).

Таблица 6. Средняя эффективность адаптивного ВГА по отношению к ГА (в процентах)

Задача № X У % % доп.

1 ■■ 1,22 -0,49 -2,44 0,51 '

2 -0,18 0 ' 0.28' -0,04

3 -0,28 -0,93 1,68 ' • 1,69

4 9.52 : '42,24 -2,7 3,02 ■

Среднее '■'•2,57 - - - 2,71 - -0,8 1,3

Результаты следует интерпретировать аналогичным образом, как для таблицы 2. Из таблицы б видно, что в большинстве случаев адаптивный ВГА эффективнее, чем ГА. А в тех случаях, когда ВГА уступает ГА, это различие не превышает 3%. Поэтому, можно считать, что адаптивный ВГА также эффективен, как и ГА.

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

1. Определить шаг прогноза К.

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

3. Каждому поколению придавать вес, в зависимости от его номера:

<7, =2;/л^+1), 1 = 1,...,^. _ _

4. Через каждые К поколений по набранным статистикам Р,, г = \,ИК, Л^ = I ■ К, г 6 {1,2,...} рассчитать вектор вероятностей по формуле:

5. Используя вектор Р сгенерировать с помощью датчика псевдослучайных чисел заданное количество прогнозируемых решений.

6. Добавить полученные на шаге 5 решения в текущую рабочую популяцию и продолжить работу ВГА.

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

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

Таблица 7. Средняя эффективность ВГА с прогнозом по отношению к ВГА, безусловная оптимизация

Задача JV® X Y % Скор.

1 -1,55 -0,87 Л) -1,02

2 -0,41 -0,57 -0,13 22.7

3 " 0,45 0 ■ -3,94 29,29 •'

Среднее -0,5 -0,48 -1,36 ■ 17 :

Задача № X Y % % доп. Скор.

1 • • 0 ' - 0,49",- '1,49 - - 0,19. ,• -.38,31

2 -0,91 -1,14 " ,0,54 - . - - 0.79 - 13,92 --

3 -0,27 -0,46 -,0,78 -' - -' 0,78 " -6,09

4 -4,35 -1,82 4,-55 - . ■ -.4,13-. --' '9,44 ■

Среднее -1,38 -0,73 . 1,84' : -. 1.47 . .| '.•,89

Из таблиц 7 и 8 видно, что скорость сходимости алгоритма с прогнозом в среднем на 17% выше, чем алгоритма без прогноза для задач безусловной оптимизации, и на 14% выше для задач условной оптимизации. Различия в остальных характеристиках в среднем не превышают 3%, что можно признать несущественным. Поэтому, можно считать, что ВГА с прогнозом является более эффективным по скорости сходимости к множеству Парето.

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

пространстве и пространстве решений, а ВГЛ в большинстве случаев обеспечивает наилучший процент Паретовских и допустимых точек.

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

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

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

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

Содержательная постановка задачи оценки проекта реальных инвестиций состоит в следующем: имеется план производства нескольких видов продукции на одном основном производственном фонде (ОПФ). Известны прогнозные значения спроса по каждому виду продукции, технико-экономические показатели ОПФ и здания цеха (ЗЦ): нормативный срок службы и стоимость, производительность оборудования и стоимость единицы производимой на нем продукции. Требуется определить объемы внешних инвестиций, осуществляемые инвестором в заданный период времени, платежей поставщику за ОПФ и ЗЦ, а также объемы продаж по каждому виду продукции в период производства, при которых стоимость инвестиционного проекта по критерию чистого приведенного дохода за определенный интервал времени будет наибольшей.

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

ления меняется во времени. Кроме того, допустимая область является достаточно сложной, а ее размер довольно мал по сравнению со всем поисковым пространством. Для решения данной задачи был применен ВГА с прогнозом оптимального решения, описанный в главе 1.

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

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

Математические модели задач формирования оптимальных портфелей представляют собой задачи условной оптимизации с бинарными переменными. Они допускают однокритериальную и многокритериальную постановки. В однокритериальной постановке суммарная рискованность портфеля выступает в роли ограничения, а в многокритериальной - в роли критерия, который необходимо минимизировать. В данной работе портфельные задачи решались в обеих постановках. Для решения задачи в однокритериальной постановке применялся вероятностный ГА с оптимальными настройками, полученными в ходе исследований и описанными в главе 1. Для решения задачи в многокритериальной постановке применялся многокритериальный вероятностный ГА с оптимальными настройками, которые были получены в результате исследований и описаны в главе 2.

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

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

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

При помощи данной программы были успешно решены указанные задачи. Для задачи оценки проекта реальных инвестиций было получено оптимальное решение. Для задачи формирования оптимального инвестиционного портфеля предприятия была получена аппроксимация множества Парето в многокритериальной постановке и получено оптимальное решение в однокритериальной постановке. Для задачи формирования оптимального кредитного портфеля банка в многокритериальной постановке было получено субоптимальное недоминируемое по Парето множество решений. В однокритериальной постановке данная задача была решена в двух вариантах - с бинарными и со смешанными переменными. В обоих случаях были получены субоптимальные решения. Применение ВГА с прогнозом оптимального решения в задаче со смешанными переменными позволило улучшить ранее известное решение на 32%.

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

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

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

Полученные результаты были переданы специалистам для апробации.

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

Основные результаты и выводы:

В диссертационной работе получены следующие результаты:

1. Разработан вероятностный ГА с прогнозом оптимального решения для задач условной однокритериальной оптимизации.

2. Разработан вероятностный ГА с прогнозом эффективных решений для задач условной и безусловной многокритериальной оптимизации.

3. Разработан вероятностный ГА с адаптивной мутацией для решения задач условной и безусловной многокритериальной оптимизации.

4. Проведен сравнительный анализ стандартного и вероятностного ГА на тестовых задачах условной и безусловной однокритериальной и многокритериальной оптимизации.

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

6. Разработаны, апробированы и внедрены программные системы, реализующие указанные алгоритмы. Программы зарегистрированы в отраслевом фонде алгоритмов и программ.

7. С помощью разработанных программных систем решены реальные практические задачи.

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

Публикации по теме диссертации

Статьи в ведущих рецензируемых научных журнала и издапиях

1. Медведев A.B. Поддержка принятия решений при управлении региональным экономическим развитием на основе оптимизационных моделей и алгоритмов [Текст] / A.B. Медведев, Е.С. Семенкин, А.Ю. Ворожейкин // Экономика и управление. - 2007. - №4. - С. 63-64.

2. Ворожейкин А.Ю. Вероятностный генетический алгоритм для задач многокритериальной оптимизации [Текст] / А.Ю. Ворожейкин, Е.С. Семен-кин // Вестник Сибирского государственного аэрокосмического университета. -Вып. 3(16). - 2007. - С. 41-45.

3. Семенкин Е.С. Модели и алгоритмы поддержки принятия решений инвестиционного аналитика [Текст] / Е.С. Семенкин, A.B. Медведев, А.Ю. Ворожейкин // Вестник Томского государственного университета. - Вып. 293. -2006.-С. 63-70.

4. Ворожейкин А.Ю. Вероятностный генетический алгоритм с прогнозом в задачах оценки и планирования реальных инвестиций [Текст] / А.Ю. Ворожейкин, A.B. Медведев, Е.С. Семенкин // Вестник Красноярского государственного университета. - Вып. 9. - 2006. - С. 174-178.

Публикации в журналах и сборниках

5. Ворожейкин А.Ю. Система поддержки принятия решений инвестиционного аналитика [Текст] / А.Ю. Ворожейкин, Е.С. Семенкин // Вестник университетского комплекса. - Вып. 7 (21). — 2006. - С. 190-205.

6. Ворожейкин А.Ю. Программная система решения задач математического программирования вероятностным генетическим алгоритмом [Текст] / А.Ю. Ворожейкин, Е.С. Семенкин // Вестник университетского комплекса. -Вып. 6(20).- 2005. -С.253-261.

Публикации в сборниках трудов конференций

7. Ворожейкин А.Ю. Разработка и исследование адаптивного вероятностного генетического алгоритма для многокритериальных задач условной оптимизации [Текст] / А.Ю. Ворожейкин, Е.С. Семенкин // Труды международных научно-технических конференций «Интеллектуальные системы» (AIS'08) и «Интеллектуальные САПР» (CAD-2008). - М.: Физматлит, 2008, Т.1.-С. 15-21.

8. Ворожейкин А.Ю. Разработка и исследование вероятностного генетического алгоритма с адаптивной мутацией для решения многокритериальных задач условной оптимизации [Текст] / А.Ю. Ворожейкин, Е.С. Семенкин // Системный анализ в проектировании и управлении: Труды XII Между-нар.научн.-практ. Конф. 4.2. СПб.: Изд-во Политехи, ун-та, 2008. - С. 109116.

9. Ворожейкин А.Ю. Программная система для решения многокритериальных задач оптимизации эволюционными алгоритмами [Текст] // Системный анализ в проектировании и управлении: Труды ХП Междунар.научн.-практ. Конф. 4.2. СПб.: Изд-во Политехи, ун-та, 2008. - С. 107-109.

10. Ворожейкин А.Ю. Разработка и исследование вероятностного генетического алгоритма многокритериальной оптимизации [Текст] / А.Ю. Ворожейкин, Е.С. Семенкин // Труды международных научно-технических конференций «Интеллектуальные системы» (AIS'07) и «Интеллектуальные САПР» (CAD-2007).-М.: Физматлит, 2007, Т.1. - С. 10-19.

11. Ворожейкин А.Ю. Система поддержки принятия решений при управлении реальными инвестициями [Текст] / А.Ю. Ворожейкин, Е.С. Семенкин // Труды международных научно-технических конференций «Интеллектуальные системы» (AIS'07) и «Интеллектуальные САПР» (CAD-2007). - М.: Физ-матлит, 2007, Т.1. - С. 19-21.

12. Медведев A.B. Поддержка принятия решений при управлении региональным экономическим развитием на основе оптимизационных моделей и алгоритмов [Текст] / A.B. Медведев, Е.С. Семенкин, А.Ю. Ворожейкин // Материалы Всероссийской научно-практической конференции «Евразийское пространство - Сибирь: перспективы развития, проблемы, решения», - Барнаул, 2007.-С. 113-117.

13. Ворожейкин А.Ю. Система поддержки принятия решения для задач инвестиционного анализа [Текст] / А.Ю. Ворожейкин // Труды конференции-конкурса «Технологии Microsoft в теории и практике программирования». -Новосибирск: НГУ, 2007. - С. 98-101.

14. Ворожейкин А.Ю. Решение многошаговой задачи линейного программирования вероятностным генетическим алгоритмом с поведенческой памятью [Текст] / А.Ю. Ворожейкин // Труды XIII Международного симпозиума «Сложные системы в экстремальных условиях». - Красноярск: КНЦ РАН, 2Ж.-С. 16.

Зарегистрированные программные системы

15. Ворожейкин А.Ю. Программа для решения многокритериальных задач оптимизации генетическими алгоритмами [Текст] / А.Ю. Ворожейкин, Е.С. Семенкин. - М.: ВНТИЦ, 2008. - 5с. - № гос. per. 50200800641.

16. Ворожейкин А.Ю. Вероятностный генетический алгоритм решения задач условной оптимизации [Текст] / А.Ю. Ворожейкин, Е.С. Семенкин. -М.: ВНТИЦ, 2006. - 8с. - № гос. per. 50200600371.

17. Ворожейкин А.Ю. Автоматизированное рабочее место инвестиционного аналитика [Текст] / А.Ю. Ворожейкин, A.B. Медведев, Е.С. Семенкин. -М.: ВНТИЦ, 2006. - 7с. - № гос. per. 50200600629.

Ворожейкин Антон Юрьевич

Адаптивные эволюционные алгоритмы решения сложных задач оптимизации

Подписано в печать

Объем п.л. 1,0

Автореферат 6 ноября 2008 г. Тираж 100 экз.

Формат 60x84/16 Заказ № т

Отпечатано в отделе копировально-множительной техники СибГАУ 660014, г. Красноярск, пр. им. газ. «Красноярский рабочий», 31.

ВВЕДЕНИЕ

ГЛАВА 1. Разработка и исследование вероятностного генетического 9 алгоритма для решения задач однокритериальной оптимизации

1.1 Стандартный генетический алгоритм

1.2 Вероятностный генетический алгоритм

1.3 Условная оптимизация эволюционными алгоритмами

1.4 Экспериментальное исследование эффективности алгоритмов

1.5 Выводы

ГЛАВА 2. Разработка и исследование вероятностного генетического 27 алгоритма для решения задач многокритериальной оптимизации

2.1 Многокритериальная оптимизация генетическими алгоритмами

2.2 Экспериментальное исследование

2.3 Результаты исследований эффективности алгоритмов

2.4 Выводы

ГЛАВА 3. Практическая реализация разработанных алгоритмов

3.1 Программная система для решения однокритериальных задач

3.2 Программная система для решения многокритериальных задач

3.3 Реальные практические задачи

3.4 Система поддержки принятия решения для инвестиционного 94 аналитика

3.5 Результаты решения практических задач 103 ЗАКЛЮЧЕНИЕ 124 СПИСОК ЛИТЕРАТУРЫ 126 ПРИЛОЖЕНИЯ

Необходимость в разработке моделей сложных систем возникает в различных областях науки и техники: математика, экономика, медицина, управление космическими аппаратами и т.д. [1,2]. При разработке моделей часто возникают задачи оптимизации, которые обладают такими свойствами, как многоэкстре-мальность, многокритериальность, алгоритмическое задание функций, сложная конфигурация допустимой области, наличие нескольких типов переменных и др. [3,4,5]. Такие задачи не решаются с помощью классических процедур оптимизации, что приводит к необходимости разрабатывать и применять более мощные и универсальные методы [6,7]. К таким методам относятся, в частности, эволюционные алгоритмы (ЭА), доказавшие свою эффективность при решении многих сложных задач [8,9,10].

Современное состояние исследований в области разработки и применения ЭА заключается в экстенсивном развитии направления — специалисты в области ЭА разрабатывают новые схемы, исследуют их на тестовых задачах и предлагают для решения прикладных задач [11,12,13]. Специалисты предметных областей берут готовые разработки, адаптируют их или пытаются реализовать алгоритмы по-своему [14,15]. В этом случае можно услышать, что ЭА обладают низкой эффективностью и требуют значительных вычислительных затрат.

Проблема возникает потому, что эффективность ЭА определяется тщательной настройкой их параметров [16,17]. Это с трудом удается ученым, разрабатывающим ЭА, и практически не удается специалистам других областей. При произвольном выборе параметров неподготовленным пользователем эффективность алгоритма может быть как очень низкой, так и очень высокой, а его надежность может изменяться от нуля до ста процентов .для одной и той же задачи [18,19]. Такая ситуация препятствует более широкому распространению эволюционных алгоритмов, так как требует от конечных пользователей высокой квалификации и большого опыта в применении ЭА, что редко наблюдается на практике [20,21].

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

Вероятностные ГА ранее также показали свою эффективность и применимость к некоторым сложным задачам оптимизации [24,25]. Это дало основания полагать, что совершенствуя данный подход к самоадаптации, удастся уменьшить количество настраиваемых параметров, сохранив при этом эффективность алгоритмов.

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

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

• Сформулированная цель предопределила следующую совокупность решаемых задач:

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

2. Разработать вероятностный ГА для решения задач условной и безусловной многокритериальной оптимизации.

3. Провести сравнительный анализ эффективности стандартного и вероятностного ГА на тестовых задачах условной и безусловной многокритериальной оптимизации.

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

5. Выполнить апробацию разработанных алгоритмов при решении реальных практических задач.

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

Научная новизна результатов диссертационной работы состоит в следующем:

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

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

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

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

Работа выполнена при финансовой поддержке Фонда содействия развитию малых форм предприятий в научно-технической сфере в рамках НИОКР «Разработка математического и алгоритмического обеспечения системы поддержки принятия решений для задач инвестиционного анализа», в соответствии с тематическим планом E3H СибГАУ «Бионические методы идентификации и оптимизации сложных систем» (№ Б 1.1.05), а также поддерживалась грантами на выполнение молодежных проектов, проводимых в рамках программы развития СФУ (2007, 2008 гг.) и грантами для молодых ученых Красноярского краевого фонда науки (17G045, 18G022).

Реализация результатов работы. Созданные в ходе работы над диссертацией программные системы прошли государственную экспертизу и зарегистрированы в Отраслевом фонде алгоритмов и программ Государственного координационного центра информационных технологий Федерального агентства образования.

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

Программные системы и разработанные алгоритмы прошли апробацию при решении реальных задач управления инвестициями и переданы для использования на производственных предприятиях: Химзавод-филиал ФГУП «Красмаш» (п. Подгорный Красноярского края) и ЗАО «ОКБ APT» (г. Красноярск).

Работа дважды признана лучшей на конкурсе международного научного фонда экономических исследований им. Н.П. Федоренко (2006, 2007 гг.). В июле 2008 г. по результатам данной работы диссертанту присуждена Государственная премия Красноярского края за значительные успехи в области разработки математического и алгоритмического обеспечения поддержки принятия решений при управлении реальными инвестициями (распоряжение губернатора Красноярского края от 16.07.2008 № 210-рг).

Основные защищаемые положения:

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

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

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

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

Апробация работы.

Результаты диссертационной работы были доложены и обсуждены на XII Международной научно-технической конференции «Системный анализ в проектировании и управлении», Санкт-Петербург, 2008; Конференции лауреатов и стипендиатов конкурсов международного научного фонда экономических исследований академика Н.П. Федоренко, Москва, 2007; Всероссийской научно-практической конференции «Евразийское пространство - Сибирь: перспективы развития, проблемы, решения», Барнаул, 2007; Международных научно-технических конференциях «Интеллектуальные системы» AIS'07 и AIS'08, Дивноморское, 2007, 2008; Конференции-конкурсе «Технологии Microsoft в теории и практике программирования», г. Новосибирск, 2007; XIII Международном симпозиуме «Сложные системы в экстремальных условиях», г. Красноярск, 2006, и на восьми молодежных научных конференциях.

Структура работы. Диссертация содержит 141 страницу основного текста и состоит из введения, трех глав, заключения, списка литературы на 108 источников и 5 приложений, содержащих 36 страниц.

ЗАКЛЮЧЕНИЕ

В диссертационной работе получены следующие результаты:

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

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

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

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

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

6. Разработаны, апробированы и внедрены программные системы, реализующие указанные алгоритмы. Программы зарегистрированы в Государственном отраслевом фонде алгоритмов и программ.

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

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

1. Аоки М. Введение в методы оптимизации. Перев. с англ., — М.: Наука. Главная редакция физико-математической литературы, 1977. 344 с.

2. Абдеев Р.Ф. Философия информационной цивилизации. — М.: ВЛАДОС, 1994.

3. Семенкин Е.С., Лебедев В.А. Метод обобщенного адаптивного поиска для синтеза систем управления сложными объектами. М.: МАКС Пресс, 2002. - 320 с.

4. Семенкин Е.С. Модели и алгоритмы поддержки принятия решений инвестиционного аналитика / Е.С. Семенкин, А.В. Медведев, А.Ю. Ворожейкин // Вестник Томского государственного университета. Вып. 293.-2006.-С. 63-70.

5. Медведев А.В. Поддержка принятия решений при управлении региональным экономическим развитием на основе оптимизационных моделей и алгоритмов / А.В. Медведев, Е.С. Семенкин, А.Ю. Ворожейкин // Экономика и управление. 2007. - №4. - С. 63-64.

6. Ворожейкин А.Ю. Анализ и планирование инвестиций эволюционными алгоритмами // Молодежь и наука: начало XXI века, материалы всероссийской научно-технической конференции: в 3 ч. Ч. 2. -Красноярск: ИПЦ КГТУ, 2006. С.8-10.

7. Branke J. Evolutionary Approaches to Dynamic Optimization Problems. Updated Survey. Institute AIFB, University of Karlsruhe, 1999.

8. Baluja S. The Equilibrium Genetic Algorithm and the Role of Crossover. 1993.

9. Baluja S., Caruana R. Removing the Genetic from the Standard Genetic Algorithm. In Proc. Of the Twelfth International Conference on Machine Learning, 1995.

10. Spears W.M. Adapting Crossover in Evolutionary Algorithms.

11. Andersson J., Multiobjective Optimization in Engineering Design -Application to Fluid Power Systems, Dissertation, Thesis No. 675, Linkoping University, Sweden, 2001.

12. Andersson J., Krus P. and Wallace D., «Multi-objective optimization of hydraulic actuation systems», ASME Design Automation Conference, Baltimore, September 11-13,2000.

13. Редько В. Прикладное эволюционное моделирование. Генетический алгоритм. Оценка эффективности генетического алгоритма. URL:http://www.keldysh.ru/BioCvber/LecturelQ.html

14. Adewuya, A. A. New methods in genetic search with real-valued chromosomes. Master's thesis. Massachusetts Institute of Technology, Cambridge, 1996.

15. Booker, L. Improving search in genetic algorithms. In L. Genetic algorithms and Simulated Annealing. London: Pitman, 1987. p. 61-73.

16. Haupt R.L., Haupt S.E. Practical Genetic Algorithms / R.L. Haupt, S.E Haupt // led., Wiley, 2004.

17. Janikow, С. Z. Genetic algorithms simulating nature's methods of evolving the best design solution. / C. Z. Janikow, D. St. Ciair // IEEE Potentials 14, 1995. pp. 31-35.

18. Wright, A. Genetic algorithms for real parameter optimization. Foundations of Genetic Algorithms. San Mateo, CA: Morgan Kaufmann, 1991. pp. 205-218.

19. Сопов E.A. Вероятностный генетический алгоритм и его исследование // VII Королевские чтения. Том 5. Самара: Изд-во Самарского научного центра РАН, 2003. - С. 38-39.

20. Сопов Е.А. Вероятностный генетический алгоритм с прогнозированием сходимости // Вестник университетского комплекса. -Красноярск: ВСФ РГУИТП, НИИ СУВПТ, 2004. Вып 1 (15). - С. 219-227.

21. Сопов Е.А. Вероятностный генетический алгоритм решения сложных задач оптимизации и его исследование // Молодежь Сибири — науке России. Красноярск: СИБУП, 2004. - С. 26-29.

22. Holland J. Н. Adaptation in natural and artificial systems / J. H. Holland. Ann Arbor. MI: University of Michigan Press, 1975.

23. Goldberg D. E. Genetic algorithms in search,.optimization, and machine learning / D. E. Goldberg. Reading, MA: Addison-Wesley, 1989.

24. Семенкин E.C., Семенкина О.Э., Коробейников С.П. Оптимизация технических систем: Учебное пособие. Красноярск: СИБУП, 1996.

25. Ворожейкин А.Ю. Вероятностный генетический алгоритм с прогнозом в задачах оценки и планирования реальных инвестиций / А.Ю. Ворожейкин, А.В. Медведев, Е.С. Семенкин // Вестник Красноярского государственного университета. Вып. 9. - 2006. - С. 174-178.

26. Хайниш С.В., Клешков В.М., Бородин А.Н. Российское предприятие ВПК: выжить и развиваться. (На примере реформирования и развития Химзавода филиала ФГУП «КРАСМАШ»). - М.: Рохос, 2003. - 240 с.

27. Фогель JI., Оунэнс А., Уолш М. Искусственный интеллект и эволюционное моделирование. Пер с англ. Зайченко Ю. П. Под ред. Ивахненко А. Г. М.:Мир, 1969.

28. Parmee I. (Ed.) Adaptive computing in engineering design and control. Proceedings of the International Conference / I. Parmee. Plymouth, 1996. - 325 pp.

29. Вороновский Г.К., и др. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности. X.: ОСНОВА, 1997.

30. Стариков A. BaseGroup Labs. Генетические алгоритмы -математический аппарат. URL: http://www.basegroup.ru/genetic/math.htm

31. Растригин Л.А., Фрейманис Э.Э. Решение задач разношкальной оптимизации методом бинаризации. Вопросы разработки ТАСУ. Кемерово, 1984, вып. 3.

32. Растригин JI.A. Бинаризация задач оптимизации решений в САПР. -В кн.: Моделирование и оптимизация решений в САПР. Таллин, 1983, ч.2.

33. Емельянов В.В., Курейчик В.В., Курейчик В.М. Теория и практика эволюционного моделирования. М.: Физматлит, 2003.

34. Handbook of Genetic Algorithms, Edited by Lowrence Davis, Van Nostrand Reinhold, New York, 1991, 385 p.

35. Muhlenbein H., Voigt H.-M. Gene Pool Recombination in Genetic Algorithms. In Proc. Of the Metaheuristics Inter. Conf., 1995.

36. Гладков JI.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. Ростов-на-Дону: Росиздат, 2004. - 400 с.

37. Spears W.M. The Role of Mutation and Recombination in Evolutionary Algorithms. PhD dissertation, George Mason University, Virginia, USA, 1998. -240 p.

38. Сопов Е.А. О вероятностном генетическом алгоритме // Современные техника и технологии. В 2-х т. Томск: Изд-во Томского политехи, ун-та, 2004. - Т.2. - С. 197-199.

39. Michalewicz Z. Genetic algorithms, numerical optimization and constraints // Proc. of the Sixth Int. Conf. on Genetic Algorithms and their Applications, Pittsburgh, PA, 1995.

40. Deb K. Optimization for engineering design: Algorithms and examples. Prentice-Hall, New Delhi, India, 1995.

41. Deb K. An efficient constraint handling method for genetic algorithms. Computer Methods in Applied Mechanics and Engineering, North-Holland, Amsterdam, Netherlands, 1999.

42. Michalewicz Z. and Schoenauer M. Evolutionary Algorithms for Constrained Parameter Optimization Problems. Evolutionary Computation, 4(1):1—32, 1996.

43. Jimenez F. and Verdegay J. Evolutionary techniques for constrained optimization problems. In 7th European Congress on Intelligent Techniques and Soft Computing (EUFIT'99), Aachen, Germany. Springer-Verlag, 1999.

44. Растригин Л.А. Статистические методы поиска. М.: Наука, 1968. 376 с.

45. Рубан А.И. Методы оптимизации: Учебное пособие. Изд. 2-ое. Красноярск НИИ ИЛУ, 2001. 528 с.

46. Deb К., Horn J., Goldberg D. E. Multi-Modal deceptive functions. Complex Systems, 7:131-153, 1993.

47. Гилл Ф., Мюррэй У. Численные методы условной оптимизации. М.: МИР, 1977.

48. Whitley D. Building Better Test Functions. Proceedings of the Sixth International Conference on Genetic Algorithms, 1995.

49. Ворожейкин А.Ю. Вероятностный генетический алгоритм решения задач условной оптимизации / А.Ю. Ворожейкин, Е.С. Семенкин // Компьютерные учебные программы и инновации. №3. - 2007. - С. 28.

50. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. М.: Наука. Главная редакция физико-математической литературы, 1982. - 256 с.

51. Подиновский В.В., Гаврилов В.М. Оптимизация по последовательно применяемым критериям. М., «Сов. радио», 1975, 192 с.

52. Семенкин Е.С., Терсков В.А. Модели и методы оптимизации сложных систем. Красноярск: СибЮИ MB РФ, 2000. - 211 с.

53. Coello Coello С.А. A comprehensive survey of evolutionary-based multiobjective optimization techniques.

54. Horn J. Multicriterion decision making. In Baeck, Т., Fogel, D. B. and Michalewicz, Z., editors, Handbook of Evolutionary Computation, pages F 1.9:115, Oxford University Press, New York, New York. Evolutionary Computation Volume 7, Number 3 229, 1997.

55. Schaffer J.D. Multiple objective optimization with vector evaluated genetic algorithms. In J. J. Grefenstette (Ed.), Proceedings of an International Conference on Genetic Algorithms and Their Applications, Pittsburgh, PA, 1985. -P. 93-100.

56. Fonseca C.M., Fleming P.J. Multiobjective optimization and multiple constraint handling with evolutionary algorithms Part I: A unified formulation. Technical report 564, University of Sheffield, Sheffield, UK, January 1995.

57. Fonseca C.M., Fleming PJ. Multiobjective optimization and multiple constraint handling with evolutionary algorithms Part II: Application example. Technical report 565, University of Sheffield, Sheffield, UK, January 1995.

58. Horn J., Nafpliotis N., Goldberg D. E. A niched Pareto genetic algorithm for multiobjective optimization. In Proceedings of the First IEEE Conference on Evolutionary Computation, Vol. 1, Piscataway, 1994. P. 82-87.

59. Гарипов В.P. Многокритериальная оптимизация систем управления сложными объектами методами эволюционного поиска. — Дисс. канд. техн. наук. Красноярск: САА, 1999.

60. Zitzler Е., Thiele L. Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach // IEEE Transactions on Evolutionary Computation, Vol. 3, No. 4, pp. 257-271, 1999.

61. Schaffer J. D. Some experiments in machine learning using vector evaluated genetic algorithms. Doctoral Dissertation, Vanderbilt University, Nashville, Tennessee, 1984.

62. Fonseca С. M., Fleming P. J. An overview of evolutionary algorithms in multiobjective optimization. Evolutionary Computation, 3:1-16, 1995.

63. Перегудов Ф.И., Тарасенко Ф.П. Основы системного анализа: Учеб. 2-е изд., доп. Томск: Изд-во НТЛ, 1997. - 369 с.

64. Coello Coello С.A. An empirical study of evolutionary techniques for multiobjective optimization in engineering design. PhD thesis. Department of computer science, Tulane university. New Orleans, LA, 1996.

65. Курейчик B.M. и др. Методы генетического поиска / Под редакцией Курейчика В.М. Таганрог: Изд-во ТРТУ, 2002.

66. Айвазян С.А. и др. Прикладная статистика: Основы моделирования и первичная обработка данных. Справочное изд. / С.А. Айвазян, И.С. Енюков, Л.Д. Мешалкин. М.: Финансы и статистика, 1983. - 471 с.

67. Гмурман В.Е. Теория вероятностей и математическая статистика. -Учебное пособие. М.: Высш. шк., 2000, 479 с.

68. Моденов П.С. Аналитическая геометрия / П.С. Моденов. М.: Изд-во Московского университета, 1967. — 699 с.

69. Ворожейкин А.Ю. Вероятностный генетический алгоритм для задач многокритериальной оптимизации / А.Ю. Ворожейкин, Е.С. Семенкин // Вестник Сибирского государственного аэрокосмического университета. -Вып. 3(16). 2007. - С. 41-45.

70. Ворожейкин А.Ю. Вероятностный генетический алгоритм решения задач условной оптимизации / А.Ю. Ворожейкин, Е.С. Семенкин. М.: ВНТИЦ, 2006. - 8с. - № гос. per. 50200600371.

71. Ворожейкин А.Ю. Вероятностный генетический алгоритм решения задач условной оптимизации / А.Ю. Ворожейкин, Е.С. Семенкин // Инновации в науке и образовании. №3(14). - 2006. - С.16-17.

72. Ворожейкин А.Ю. Программная система решения задач математического программирования вероятностным генетическим алгоритмом / А.Ю. Ворожейкин, Е.С. Семенкин // Вестник университетского комплекса. Вып. 6(20). - 2005. - С.253-261.

73. Ворожейкин А.Ю. Программа для решения многокритериальных задач оптимизации генетическими алгоритмами / А.Ю. Ворожейкин, Е.С. Семенкин. М.: ВНТИЦ, 2008. - 5с. - № гос. per. 50200800641.

74. Ворожейкин А.Ю. Программа для решения многокритериальных задач оптимизации генетическими алгоритмами / А.Ю. Ворожейкин, Е.С. Семенкин // Компьютерные учебные программы и инновации. №9. - 2008. -С. 42.

75. Медведев А.В. Численное исследование одной модели реальных инвестиций / А.В. Медведев, П.Н. Победаш // Вестник КемГУ, серия «Математика».-2003.-Вып.4 (16). С. 21-24.

76. Васильев Ф.П. Численные методы решения экстремальных задач / Ф.П. Васильев М.: Наука, 1988. - 552 с.

77. Крылов И.А. О методе последовательных приближений для решения задач оптимального управления / И.А. Крылов, Ф.Л. Черноусько // ЖВМ и МФ. 1962. - Т.2, №6.-С. 1132-1139.

78. Крылов И.А. Алгоритм метода последовательных приближений для задач оптимального управления / И.А. Крылов, Ф.Л. Черноусько // ЖВМ и МФ.- 1972.- Т. 12, №1.-С. 14-34.

79. Любушин А.А. Метод последовательных приближений для расчета оптимального управления / А.А. Любушин, Ф.Л. Черноусько // Известия АН СССР. Сер.Техническая кибернетика. 1983, №2.-С. 147-159.

80. Грачев Н.И. Библиотека программ для решения задач оптимального управления / Н.И. Грачев, Ю.Г. Евтушенко // ЖВМ и МФ. 1979. - Т. 19, №2. -С. 367-387.

81. Любушин А.А. Модификации и исследование сходимости метода последовательных приближений для задач оптимального управления / А.А. Любушин // ЖВМ и МФ. 1979. - Т. 19, №6.-С. 1414-1421.

82. Любушин А.А. О применении модификаций метода последовательных приближений для задач оптимального управления / А.А. Любушин // ЖВМ и МФ. 1982. - Т.22, №1.-С. 30-35.

83. Клешков В.М. Модели и алгоритмы распределения общих ресурсов при управлении инновациями реструктурированного предприятия ВПК. — Дисс. канд. техн. наук. Красноярск: НИИ СУВПТ, 2003, 165 с.

84. Пуртиков В. А. Оптимизация управления формированием кредитного портфеля банка. Дисс. канд. техн. наук. Красноярск: САА, 2001. - 148 с.

85. Ворожейкин А.Ю. Автоматизированное рабочее место инвестиционного аналитика / А.Ю. Ворожейкин, А.В. Медведев, Е.С. Семенкин. М.: ВНТИЦ, 2006. - 7с. - № гос. per. 50200600629.

86. Ворожейкин А.Ю. Автоматизированное рабочее место инвестиционного аналитика / А.Ю. Ворожейкин, А.В. Медведев, Е.С. Семенкин // Инновации в науке и образовании. №5(16). - 2006. - С. 3-4.

87. Ворожейкин А.Ю. Автоматизированное рабочее место инвестиционного аналитика / А.Ю. Ворожейкин, Е.С. Семенкин, А.В. Медведев // Компьютерные учебные программы и инновации. №3. - 2007. -С.38.

88. Ворожейкин А.Ю. Система поддержки принятия решений инвестиционного аналитика / А.Ю. Ворожейкин, Е.С. Семенкин // Вестник университетского комплекса. Вып. 7 (21). - 2006. - С. 190-205.

89. Ворожейкин А.Ю. Программная система для решения многокритериальных задач оптимизации эволюционными алгоритмами // Системный анализ в проектировании и управлении: Труды XII Междунар.научн.-практ. Конф. 4.2. СПб.: Изд-во Политехи, ун-та, 2008. С. 107-109.

90. Ворожейкин А.Ю. Программа для решения многокритериальных задач оптимизации генетическими алгоритмами / А.Ю. Ворожейкин, Е.С. Семенкин. М.: ВНТИЦ, 2008. - 5с. - № гос. per. 50200800641.

91. Ворожейкин А.Ю. Программа для решения многокритериальных задач оптимизации генетическими алгоритмами / А.Ю. Ворожейкин, Е.С. Семенкин // Компьютерные учебные программы и инновации. №9. - 2008. - С. 42.

92. Медведев А.В. Поддержка принятия решений при управлении региональным экономическим развитием на основе оптимизационных моделей и алгоритмов / А.В. Медведев, Е.С. Семенкин, А.Ю. Ворожейкин // Экономика и управление. 2007. - №4. - С. 63-64.

93. Ворожейкин А.Ю. Вероятностный генетический алгоритм решения задач условной оптимизации / А.Ю. Ворожейкин, Е.С. Семенкин // Компьютерные учебные программы и инновации. №3. - 2007. — С. 28.

94. Ворожейкин А.Ю. Автоматизированное рабочее место инвестиционного аналитика / А.Ю. Ворожейкин, Е.С. Семенкин, А.В. Медведев // Компьютерные учебные программы и инновации. №3. - 2007. -С.38.

95. Ворожейкин А.Ю. Вероятностный генетический алгоритм для задач многокритериальной оптимизации / А.Ю. Ворожейкин, Е.С. Семенкин // Вестник Сибирского государственного аэрокосмического университета. Вып. 3(16). - 2007. - С. 41-45.

96. Семенкин Е.С. Модели и алгоритмы поддержки принятия решений инвестиционного аналитика / Е.С. Семенкин, А.В. Медведев, А.Ю. Ворожейкин // Вестник Томского государственного университета. -Вып. 293. 2006. - С. 63-70.

97. Ворожейкин А.Ю. Вероятностный генетический алгоритм с прогнозом в задачах оценки и планирования реальных инвестиций / А.Ю. Ворожейкин, А.В. Медведев, Е.С. Семенкин // Вестник Красноярского государственного университета. Вып. 9. - 2006. - С. 174178.

98. Ворожейкин А.Ю. Вероятностный генетический алгоритм решения задач условной оптимизации / А.Ю. Ворожейкин, Е.С. Семенкин. М.: ВНТИЦ, 2006. - 8с. - № гос. per. 50200600371.

99. Ворожейкин А.Ю. Вероятностный генетический алгоритм решения задач условной оптимизации / А.Ю. Ворожейкин, Е.С. Семенкин // Инновации в науке и образовании. №3(14). - 2006. - С. 16-17.

100. Ворожейкин А.Ю. Автоматизированное рабочее место инвестиционного аналитика / А.Ю. Ворожейкин, А.В. Медведев, Е.С. Семенкин. М.: ВНТИЦ, 2006. - 7с. - № гос. per. 50200600629.

101. Ворожейкин А.Ю. Автоматизированное рабочее место инвестиционного аналитика / А.Ю. Ворожейкин, А.В. Медведев, Е.С. Семенкин // Инновации в науке и образовании. №5(16). - 2006. - С. 3-4.

102. Ворожейкин А.Ю. Анализ и планирование инвестиций эволюционными алгоритмами // Молодежь и наука: начало XXI века, материалы всероссийской научно-технической конференции: в 3 ч. Ч. 2. — Красноярск: ИПЦКГТУ, 2006. С.8-10.

103. Ворожейкин А.Ю. Система поддержки принятия решений инвестиционного аналитика / А.Ю. Ворожейкин, Е.С. Семенкин // Вестник университетского комплекса. -Вып. 7 (21). 2006. - С. 190-205.

104. Ворожейкин А.Ю. Программная система решения задач математического программирования вероятностным генетическим алгоритмом / А.Ю. Ворожейкин, Е.С. Семенкин // Вестник университетского комплекса. Вып. 6(20). - 2005. - С.253-261.