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

п

005018754

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

Пивнева Светлана Валентиновна

МНОГОАСПЕКТНЫЙ ПОДХОД К МАТЕМАТИЧЕСКОМУ МОДЕЛИРОВАНИЮ ПРОЦЕССА ПРИНЯТИЯ РЕШЕНИЙ

05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание учёной степени [ доктора физико-математических наук

3 МАЙ 2012

Тольятти - 2012

005018754

Работа выполнена в ФГБОУ ВПО «Тольяттинский государственный университет» (ТГУ)

Научный консультант:

Официальные оппоненты:

доктор физико-математических наук, профессор Мельников Борис Феликсович Тольяттинский государственный университет

доктор физико-математических наук, профессор Угольницкий Геннадий Анатольевич Южный федеральный университет, г. Ростов-на-Дону

доктор физико-математических наук, профессор Соколов Андрей Владимирович Институт прикладных математических

исследований Карельского научного центра Российской академии наук, г. Петрозаводск

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

доктор технических наук, профессор Скобцов Юрий Александрович

Донецкий национальный технический университет, г. Донецк, Украина

ФГБОУ ВПО «Кабардино-Балкарский государственный университет», г. Нальчик

Защита диссертации состоится 30 мая 2012 г. в 14.00 на заседании диссертационного совета Д212.264.03 при Тольяттинском государственном университете по адресу: 445667, г. Тольятти, ул. Белорусская, 14.

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

Электронная версия автореферата размещена на официальном сайте Министерства образования и науки Российской Федерации http://vak.ed.gov.ru

Отзывы по данной работе в двух экземплярах, заверенные печатью организации, просим направлять по адресу: 445667, г. Тольятти, ул. Белорусская, 14, ТГУ, диссертационный совет Д212.264.03.

Автореферат разослан / Учёный секретарь

диссертационного совета Д212.264.03 доктор физико-математических наук

2012 г.

Решетов В. А.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Обычно эвристические методы не претендуют на получение оптимального решения, но при их применении ставится цель получить решение, близкое к оптимальному2. Обычно алгоритмы начинают работу с некоторых быстро получаемых стандартных решений, далее проводятся последовательные итерации для улучшения текущего (т. н. псевдооптимального) решения. При этом приходится «балансировать» между числом итераций и скоростью расчёта, которая не должна быть слишком низкой. Таким образом, эвристические алгоритмы позволяют находить решения гораздо более оптимальные, чем при случайном поиске.

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

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

1 Самарский А. А., Михаилов А. П. Математическое моделирование: Идеи. Методы. Примеры. - 2-е изд., испр. - M.: Физматлит, 2001.

2 Громкович Ю. Теоретическая информатика. - СПб.: БХВ-Санкт-Петербург, 2010.

3 Подиновский В. В., Ногин В. Д. Парето-оттшальиые решения многокритериальных задач. - М.: Наука, 2007.

«подходящего» алгоритма или же сравнительно узким их количеством.

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

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

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

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

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

- определение репрезентативности входных данных;

- непосредственное моделирование интеллектуальных систем, разработка и описание наиболее оптимального алгоритма принятия решения;

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

Для достижения поставленной цели решаются следующие задачи:

1) обобщение понятия репрезентативности на основании значений исследуемых характеристик в выборочной совокупности;

2) разработка и реализация подхода к определению репрезентативности входных

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

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

4) разработка и реализация различных вариантов обобщений следующих алгоритмов и методов искусственного интеллекта: генетические алгоритмы, методы математической статистики и статистики объектов нечисловой природы, аналитические методы, экспертные системы, нечёткая логика;

5) разработка и выбор наиболее оптимального алгоритма или алгоритмов принятия решения на основе многокритериального выбора;

6) анализ и апостериорная оценка качества принятого решения на адекватность выбранных алгоритмов и сравнение их эффективности с применением вспомогательных алгоритмов многокритериальной оптимизации;

7) обоснование применения многоаспектного подхода к решению задач в различных предметных областях.

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

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

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

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

4. Показано применение многоаспектного подхода для решения конкретных задач в нескольких различных предметных областях. Причём разные аспекты нового подхода могут применяться на разных этапах решения задач.

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

входных данных.

Теоретическая и практическая значимость работы

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

Полученные в работе результаты могут быть использованы в следующих прикладных задачах:

• для математического моделирования образовательного процесса, новых обучающих технологий в образовании, принятия решений для специальных обучающих, контрольных, психологических тестов [3,4, 14, 21, 35, 44,45];

• применение новых аспектов математического моделирования для эффективной организации рабочего процесса в камерах сгорания реактивных двигателей на псевдожидком топливе двигательных и энергетических установок нового поколения [5,38,40];

• при оптимизации процессов перемещения и складирования штампов в прессовом производстве ВАЗа [20];

• для исследования зависимости скорости коррозии от нескольких факторов [27, 29];

• оценки химической реакции [2,28].

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

Апробация результатов исследования

Результаты диссертационной работы докладывались на следующих российских и международных конференциях и семинарах:

• Международная научно-практическая конференция «Формирование профессиональной культуры специалистов XXI века в техническом университете» (Санкт-Петербургский государственный политехнический университет, Санкт-Петербург, 2003 г.).

• Всероссийская конференция-семинар «Проектирование, обеспечение и контроль качества продукции и образовательных услуг» (Самарский государственный технический университет, Самара, 2003 г.).

• Международная научная конференция «Актуальные проблемы науки и практики» (Тольятти, 2004 г.).

• Международная научно-практическая конференция «Системный анализ в проектировании и управлении» (Санкт-Петербургский государственный политехнический университет, Санкт-Петербург, 2005 г.).

• Международная научная конференция «Развитие космонавтики и фундаментальные проблемы газодинамики, горения и теплообмена» (Самарский государственный аэрокосмический университет имени академика

С. П. Королёва, Самара, 2006 г.).

• Международная научная конференция «Математика. Образование. Культура» (Тольятти, 2007 г., 2009 г., 2011 г.).

• ХХХП академические чтения по космонавтике «Актуальные проблемы Российской космонавтики» (РАН, Москва, 2008 г.).

• Международная научно-практическая конференция «Технологии искусственного интеллекта в экономике - 2008» (РАН, Москва, 2008 г.).

• Международная научная конференция «Дискретные модели в теории управляющих систем» (ф-т ВМК МГУ имени М. В. Ломоносова, Москва, 2009 г.).

• XVII всероссийский семинар «Нейроинформатика, её приложения и анализ данных» (ИВМ СО РАН, Красноярск, 2-4 октября 2009 г.).

• XXVI международная научно-техническая конференция «Математические методы и информационные технологии в экономике, социологии и образовании» (Пенза, Приволжский Дом знаний, 2010 г.).

• Международная научно-практическая конференция «Стохастическая оптимизация в информатике» (Санкт-Петербургский государственный университет НИИ информационных технологий, Санкт-Петербург, 2010 г.).

• VIII международный семинар «Физико-математическое моделирование систем (ФММС-8)» (Воронежский государственный технический университет, Воронеж, 2011 г.).

• VI международная научно-практическая конференция «Современные информационные технологии и ИТ-образование» (ВМК МГУ имени М. В. Ломоносова, Москва, 2011 г.).

Кроме того, результаты исследования вошли в материалы отчетов по госбюджетным научно-исследовательским работам:

• «Проектирование и диагностика учебного процесса» (2005-2006 гг.);

• «Экономические задачи в технологии управления бизнесом предприятия. Автоматизация мониторинга» (2006-2007 гг.);

• «Математическое моделирование социально-экономических процессов» (2007-2008 гг.);

• «Разработка и анализ распределенных эвристических методов решения задач дискретной оптимизации» (2010-2011 гг.).

По тематике диссертационной работы автор участвовала в выполнении гранта Федерального агентства по науке и инновациям № 0120.0.801981 -«Многоаспектный анализ эвристических алгоритмов оптимизации дискретных математических структур больших размерностей»(2009-2010 г.г.).

В настоящее время автором проводится научно-исследовательская работа в рамках государственного заказа по теме «Распределенные эвристические алгоритмы в задачах минимизации недетерминированных конечных автоматов» (ГБ№ 281203, 2012г.)

Содержание диссертационной работы легло в основу разработанных учебных курсов: «Численные методы математического моделирования», «Математическое моделирование социальных процессов», «Дополнительные главы математики для магистров», «Теория измерений в социологии», «Анализ данных в социологии»,

«Методы и модели в экономике».

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

Публикации. Основные результаты диссертации опубликованы в 48 работах, в том числе в 3 монографиях и 20 статьях в рецензируемых научных журналах и изданиях, рекомендованных ВАК Минобрнауки РФ для публикации результатов диссертаций на соискание ученой степени доктора наук.

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

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

2. Подход к определению репрезентативности входных данных.

3. Описание этапов решения задач дискретной оптимизации и обоснование их взаимосвязи.

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

5. Подход к апостериорной оценке качества принятого решения.

Структура работы. Диссертация состоит из введения, пяти глав основного текста, заключения и приложений. Объём работы - 237 страниц, включая рисунки и библиографический список из 130 названий.

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

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

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

Рассмотрены наиболее важные методы разработки алгоритмов, в частности комбинаторные и приближённые. При использовании точных методов приходится преодолевать трудности, связанные с возрастанием трудоёмкости решения задачи с ростом числа переменных, а также с доказательством оптимальности полученного решения. Кроме того, в прикладных задачах математическая модель является приближённым описанием реальной задачи. Поэтому в работе предлагается применять приближённые методы для решения задач дискретной оптимизации (ЗДО). В приближённых методах решение может проходить в два этапа: построение начального решения и улучшение начального решения. На первом этапе применяются эвристические алгоритмы (например, жадные алгоритмы, также метод ветвей и границ). На втором этапе применяются алгоритмы локального поиска.

Эвристические алгоритмы не гарантируют получение оптимального решения, но с достаточно большой вероятностью дают решение, близкое к оптимальному. На практике часто применяются т. н. апу^те-алгоритмы4 - которые в каждый определённый момент работы имеют лучшее (на данный момент) решение; при этом пользователь в режиме реального времени может просматривать эти псевдооптимальные решения, а последовательность таких решений в пределе обычно даёт оптимальное решение.

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

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

Во-вторых - несколько связанных между собой задач минимизации недетерминированных конечных автоматов (НКА). А именно - задачи вершинной, дуговой и звездно-высотной минимизации автоматов.

В-третьих - классическая задача минимизации дизъюнктивных нормальных форм (ДНФ).

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

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

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

Вторая глава содержит описание предлагаемого в работе многоаспектного подхода к моделированию процесса принятии решений.

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

4 Краткого русского термина, к сожалению, не существует.

5 Пивнева С. В. Определение функции качества при стохастическом моделировании образовательного процесса / С. В. Пивнева, О. А. Кузнецова И Известия Самарского научного центра Российской академии наук. - Самара : Изд-во Самарского научного центра РАН, 2006.

подхода к моделированию процесса принятия решения при решении задач дискретной оптимизации.

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

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

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

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

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

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

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

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

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

Известный метод ван Зейл рассматривает равновероятную случайную генерацию недетерминированного конечного автомата, имеющего п состояний. Однако в работе [22] (а также для другой предметной области - в [11]) были показаны недостатки этого алгоритма, в частности разрежённость графа переходов получаемого автомата. Поэтому был разработан другой алгоритм генерации недетерминированного конечного автомата, результатом работы которого являются автоматы, более соответствующие рассматриваемым характеристикам. Главное -это получить последовательность, которая должна являться случайной. Для проверки случайности сгенерированной последовательности чисел применяются несколько статистических критериев.

При определении репрезентативности к последовательности применяется несколько статистических критериев, и если она удовлетворяет этим критериям, то последовательность считается случайной6. Используются следующие критерии проверки случайных наблюдений: «хи-квадрат», критерий равномерности, серий, интервалов, покер-критерий (критерий разбиений), собирания купонов, сериальной корреляции.

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

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

6 Кнут, Дональд, Эрвин Искусство программирования. Т. 2 : Получисленные алгоритмы : пер. с англ. - 3-е изд. - М.: Изд. дом «Вильяме», 2003. - 832 с.

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

Теперь рассмотрим алгоритм репрезентативной генерации дизъюнктивных нормальных форм случайными гранями. Для повышения репрезентативности сгенерированных определенным алгоритмом ДНФ, репрезентативность которых оценивается в конкретной предметной области, необходимо, чтобы число настраиваемых параметров этого алгоритма было как можно большим. Так как чем больше мы сможем влиять на объекты генерации, тем более они будут адекватны объектам исследования, к которым мы хотим приблизить характеристики генерируемых объектов. В методе, основанном на подходе Журавлёва, у нас только один такой параметр. Поэтому мы изменяем саму структуру генерируемых объектов и будем добавлять в л-мерный куб вершины не по одной, а целыми плоскостями. Таким образом, мы сразу получим несколько параметров генерации:

• количество плоскостей;

• размерности плоскостей;

• их координаты.

На начальном этапе алгоритма генерации ДНФ случайными гранями нужно установить значения этих параметров. Сначала задаем п - количество переменных некой булевой функции. Затем случайно генерируем число помечаемых вершин п-мерного куба. Всё это задается как параметры. Для обеспечения равномерного распределения количества генерируемых точек и плоскостей после добавления каждой новой плоскости проверяем, не превысило ли общее число добавленных точек плоскостей число помечаемых вершин л-мерного куба. Для каждой плоскости случайные г координат заполняем 2, что означает выбор и 0 и 1 по данной переменной. А остальные (п-г) координат - случайно 0 или 1. Используя такой алгоритм, мы можем настроить параметры генерации ДНФ так, чтобы получать структуры с минимальной ошибкой репрезентативности, которая возможна при используемых параметрах генерации ДНФ.

Для проверки репрезентативности случайно сгенерированных ДНФ нами были рассмотрены следующие характеристики:

• отношение количества 0 к количеству 1;

• количество плоскостей, получающихся при минимизации сгенерированных ДНФ жадным алгоритмом;

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

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

12

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

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

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

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

Рассмотрим предлагаемый в работе многоаспектный подход в общем случае. Предположим, дана задача, для которой необходимо получить допустимое решение, подразумевая, что оно должно быть близким к оптимальному. В этом случае с помощью разделяющего элемента исходная задача разбивается на две подзадачи (а возможно, на несколько подзадач). Одна подзадача содержит разрешающий элемент, другая же, в свою очередь, его не содержит. Таким образом, мы продолжаем делить получившиеся задачи на следующие подзадачи, пока не получим задачи малой размерности. Определяем размерность экспериментально. Но законченный вариант не всегда гарантирует оптимальное решение задачи. Более того, мы можем получить вообще «плохое» решение.

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

7 Примерно 20 (переменных) в задаче минимизации ДНФ, 30 (состояний эквивалентного канонического автомата) в задаче вершинной минимизации конечного автомата, 70 (городов) в случайной ЗКВ.

размерность правой задачи на 1 меньше, чем левой.

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

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

Итак, эвристика заключается в следующем: путём такого деления на подзадачи мы получили текущее псевдооптимальное решение (рис. 1). Применяя эвристику локального поиска, мы выбираем соседнее решение. Таким образом, почти всегда получаем множество разрешающих элементов. При этом мы считаем, что то соседнее решение, которое получается рядом с текущим, с большой вероятностью тоже является «хорошим», т. е. близким к оптимальному.

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

Рис. 1. Эвристика получения текущего псевдооптхшальногорешения

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

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

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

Для проведения вычислительного эксперимента случайно генерируются входные данные рассматриваемой ЗДО, репрезентативность которых оценивается. При этом имеется возможность определить верхнюю границу Б стоимости оптимального решения (первоначальную оценку), вычисляемую согласно алгоритмам генерации входных данных. Отметим, что эта граница имеет большую аналогию с т. н. границей Хелда - Карпа10, т. к. используется для тех же самых целей, но вычисляется значительно более простым способом.

При этом входами каждого эксперимента могут быть:

• размерность оптимизационной задачи;

• количество случайно сгенерированных задач (например, для заданной размерности запускается 100 случайно сгенерированных задач; отметим, что, как и ожидалось, от входа «100 случайных задач» итоговые результаты практически не зависят);

• относительная величина превышения границы в (обычно это величина порядка 0.1, т. е. 10%)".

Для каждого конкретного варианта входных данных определяется время работы, в течение которого стоимость текущего псевдооптимального решения достигает этой границы О. Надо отметить, что в общем случае нельзя гарантировать, что достижение границы действительно произойдёт. Однако в рассматриваемых конкретных задачах дискретной оптимизации (прежде всего - в задачах минимизации ДНФ и вершинной минимизации НКА, но и не только в них)

* Мельников Б. Мультиэвристический подхол к задачам дискретной оптимизации // Кибернетика и системный анализ (HAH Украины). - 2006. - № 3. - С. 32-42.

4 Hromkovi£ J. Algorithmics for Hard Problems. Introduction to Combinatorial Optimization, Randomization. Approximation, and Heuristics. - Springer, 2003.

10 Held M., Karp R. The traveling-salesman problem and minimum spanning trees. - Operation Research, 18 (1970). - P. 1138-1162.

"Мельников Б., Радионов А. О выборе стратегии в недетерминированных антагонистических играх // Программирование (Известия РАН). 1998. № 5. С. 55-62.

достижение границы для рассматриваемых типичных «входных данных» происходит гораздо чаще, чем в 50% случаев. Это время (усреднённое для тех задач, где граница была достигнута) мы называем «обычным временем для данной размерности», «единицей времени» для входов данной размерности.

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

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

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

управление, диагностика, планирование, прогнозирование, обучение и т. д.

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

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

Рис. 2. Схема многоаспектного подхода к математическому моделированию процесса принятия

решений

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

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

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

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

отражает оптимизацию реальных объектов и систем.

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

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

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

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

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

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

f(x°)=mm fix) либо /(x°)=maxf(x), xeG, множество допустимых решений которой конечно, т. е. 0<|G|=N<°°13.

Таким образом, для любой оптимизационной задачи нужны описания:

• множества входов;

« ограничений для любого входа и допустимых решений;

• функции стоимости;

• цели (max или min).

Во многих задачах к условиям дискретности добавляются условия и другого вида -и тогда с ростом числа переменных объём вычислительной работы резко возрастает.

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

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

• Нерегулярность: ЗДО характеризуются тем, что область допустимых решений невыпуклая и несвязная, поэтому для их решения неприменимы стандартные методы, с помощью которых решают регулярные задачи математического программирования (задачи линейного и выпуклого

12 Шалыто А. А. SWITCH-технология. Алгоритмизация и программирование задач логического управления. - СПб.: Наука, 1998.-628 с.

13 Сигал И., Иванова А. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы. - M. : Физматлит, 2003.

J4 т-

Гам же.

программирования).

• Трудности при определении окрестности: в ЗДО: близость двух допустимых решений х' и х может быть оценена только по значениям функции стоимости fix') и fix2). В качестве примера рассмотрим, как можно ввести понятие окрестности в задаче коммивояжёра, где решение представляется последовательностью вершин некоторого гамильтонового цикла. Здесь под окрестностью некоторого решения х можно понимать все решения,- получаемые из х перестановкой двух вершин. При этом легко построить примеры задач (матриц стоимости), для которых такая перестановка может привести к значительному изменению стоимости решения.

• Невозможность выполнения большого перебора на компьютере. Многие методы решения ЗДО основаны на идее полного перебора допустимых решений. Объём вычислений в таких алгоритмах резко возрастает с ростом размера входных данных. Например, сложность переборного алгоритма для задачи коммивояжёра составляет О(п').

2. Математическое моделирование процесса принятия решения в классической задаче коммивояжёра

Задача коммивояжёра часто рассматривается как тестовая при разработке алгоритмов решения задач дискретной оптимизации. В работе она сформулирована в терминах теории графов15. Пусть задан полный взвешенный граф G(V,E) с множеством вершин V и множеством рёбер Е. Нужно найти в нём гамильтонов цикл минимальной стоимости. Входом для этой задачи является матрица стоимости. Допустимым решением является любой гамильтонов цикл графа, т. е. цикл, содержащий все вершины графа ровно один раз. Функция стоимости решения представляет собой сумму стоимостей ребер графа, включённых в цикл. Цель - найти решение, стоимость которого минимальна. В т. н. симметричном варианте ЗКВ заданный граф является неориентированным, и матрица стоимостей симметрична относительно главной диагонали.

3. Математическое моделирование процесса принятия решений при минимизации недетерминированных конечных автоматов по различным критериям

Рассмотрим задачу минимизации конечных автоматов. В работе приведены только самые необходимые сведения из теории автоматов, кратко рассматриваются недетерминированные конечные автоматы - автоматы Рабина - Скотта (Медведева)16, а также дано неформальное описание НКА и связанных с ними понятий.

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

• на их пересечениях стоят только 1;

• эту пару нельзя пополнить ни строкой, ни столбцом, не нарушив первого свойства.

15 Оре О. Графы и их применение. - M. : URSS, 2006.

16 Карпов Ю. Теория автоматов. - СПб. : Питер, 2002.

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

X Y Z U

A 0 0 1 1

В 1 0 0 1

С 1 1 1 /

D 1 1 1 1

Таблица 1

Таблица 1 представляет простой пример к этой задаче. В нём имеются следующие 5 блоков - a-¡A,B,C,D}x{U), fi={A,C,D}x(Z,U/ (элементы этого блока выделены курсивом), y={B,C,Djx{X,Uj, d={C,D¡x{X,Z,W « oj={D¡x{X,Y,Z,U}. Для покрытия всех значений 1 заданной матрицы достаточно использовать 3 из этих 5 блоков ~р,ууио.

Обозначим псевдоблок записью B(Q, R). Для такого псевдоблока В через а(В) обозначим соответствующие ему состояния Q С Q., а через Р(б) -соответствующие состояния17.

Однако в реальных задачах теории формальных языков эти множества псевдоблоков содержат слишком много элементов: так, блок, имеющий 4 «строки» и 3 «столбца», формирует (24-1)-(23-1)=105 псевдоблоков. Поэтому, по-видимому, одна из главных проблем для прикладных задач состоит в описании алгоритмов, использующих множества блоков вместо множеств псевдоблоков: обычно последние множества гораздо меньше.

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

18 19

алгоритм , мы получили возможные алгоритмы решения некоторых из этих проблем.

Очень кратко такие алгоритмы - причём для всех задач минимизации -можно описать следующим образом. Мы рассматриваем всё множество псевдоблоков на QKxQp, которое покрывает отношение #, и получаем все возможные дуги, а также стартовое и финальное состояния соответствующего автомата. Рассматривая все возможные подмножества такого множества дуг, мы решаем, определяет ли заданный язык полученный автомат. Среди всех таких автоматов мы выбираем «лучший», например с наименьшим числом дуг.

17 Эти определения приведены в:Мсльников Б. Ф. Построение автомата СОМ на основе базисного автомата / Б. Ф. Мельников, М. А. Зубова // Вектор науки Тольятгинского государственного университета. - 2010. - № 4 (14). - С. 30-32, а до того частично в: Melnikov В. Extended nondetermínistic finite autómata // Fundamenta Informaticae. - Vol. 104. - № 3 (2010). - P. 255-265.

18 Melnikov В., Sciarini-Guryanova N. Possible edges of finite automaton defining the given regular language // The Korean Journal of Computational and Applied Mathematics. - Vol. 9. - № 2 (2002). - P. 73-80.

19 Melnikov B. Once more on the edge-minimization of nondetermínistic finite autómata // Fundamenta informaticae. - Vol. 104.-№3 (2010).-P. 267-283.

4. Математическое моделирование принятия решений в задаче минимизации дизъюнктивных нормальных форм.

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

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

• LB - число букв переменных, встречающихся в записи ДНФ;

• Lk - число элементарных конъюнкций, входящих в ДНФ;

• L0 - число отрицаний, встречающихся в записи ДНФ.

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

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

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

Методы (или система) мультиагентной оптимизации (Multi-agent optimization system, или Ant-System, в дальнейшем AS) - это сравнительно недавно разработанные методы решения задач комбинаторной оптимизации, которые были успешно применены, в частности, для решения задачи коммивояжёра. Изучение данного подхода представляет значительный интерес, так как структура алгоритмов поражает своей гибкостью и возможностью комбинации с совершенно иными методами решения - точными и неточными, в частности с рассматриваемыми функциями риска21.

В базовом алгоритме AS (в дальнейшем - ASbase) построение решения задачи производится путём перемещения агентов из города в город на т. н. проблемном графе. На построение решений оказывает влияние искусственный след феромона, а также эвристическая информация, полученная на предыдущих итерациях алгоритма. При применении ASbaw к ЗКВ каждому ребру а,, графа G ставится в соответствие определённое количество феромона ti/t), где % - это числовая информация, модифицируемая во время работы алгоритма, at- номер итерации. При применении ASba.se к симметричной ЗКВ имеем T,J(t)=Tij{t), а в случае несимметричной задачи Tj/t)^/!).

20 Яблонский С. Введение в дискретную математику. - М.: Высшая школа, 2006.

Melnikov В., Vakhitova A. Some more on the finite automata // The Korean Journal of Computional and Applied Mathematics. 1998. Vol. 5. № 3. p. 495-506.

На начальной стадии алгоритма каждый из т агентов помещается в произвольно выбрайный город, а затем каждый агент применяет следующее правило изменения своего местонахождения. Все агенты строят туры следующим образом. Находясь в городе ¿, агент выбирает ещё не посещённый город ], основываясь на величине феромона т;><0, соответствующего ребру а„, и локально доступной эвристической информации, которая является функцией от ребра я,у. Агенты выбирают с большей вероятностью города, которые расположены ближе к текущему и соединены рёбрами с большим количеством феромона. Для получения допустимого решения каждому агенту выделяется ограниченная область памяти, называемая табу-листом, в которой записан текущий тур. Табу-лист используется для определения непосещённых городов, а также даёт возможность заново пройти тур и сделать необходимые изменения.

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

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

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

В обоих случаях (АБ и МВГ) требуется определённым образом принять решение о выборе (конкретной реализации подалгоритма построения феромона

либо элемента матрицы И для ветвления). В обоих случаях «имеется информация, данная разными экспертами» - разными локальными агентами в первом случае и разными эвристиками во втором. При этом очень часто эксперты дают противоречивую информацию - и надо её каким-то образом «усреднять». Усреднение делается с помощью набора коэффициентов, и автором для усреднения используются динамически подобранные функции риска.

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

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

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

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

1. Для каждой помеченной символом '#' клетки посчитаем И(У) = С(Н(11(0),11(С(]))), где (¡о) - номер столбца и строки соответственно.

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

22 Мельников Б. Ф. Недетерминированные конечные автоматы : монография. - Тольятти : Изд-во ТГУ, 2009. - 161 с.

23

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

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

Будем использовать схему турнира, где каждый игрок проводит серию раундов (матч) с каждым соперником. Схема туров имеет вид:

1. Последовательно выбирается (0<1<М-1) из полученного на вход множества 14, где N - его мощность.

2. Для 0| последовательно выбирается соперник 0|

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

a) генерируется игровое поле;

b) выполняется программа, определяемая хромосомой О)-,

c) выполняется программа, определяемая хромосомой О/,

<1) той хромосоме, чья программа набирает меньшее количество очков в раунде, засчитывается выигрыш (в нашем случае под очками будем понимать количество отобранных эвристическим алгоритмом блоков);

е) в случае ничьи (оба алгоритма выбрали одинаковое количество блоков) обе хромосомы получают по выигрышу.

4. Количество побед в матче добавляется к текущему количеству побед для каждой хромосомы О; и .

5. Общее количество побед каждой хромосомы есть значение относительной приспособленности (мера превосходства одного эвристического алгоритма над другими).

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

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

1. Генерируется начальная популяция - множество хромосом N мощностью N.

2. Для каждой хромосомы на основе турнирной системы вычисляется её ФФ

3. Оператор отбора. Производится т. н. рулеточный отбор N особей в множество Я, для репродукции. Хромосома попадает в Я с вероятностью РДХР,).

4. Оператор кроссовера. Множество К случайным образом разбивается на пары

для п-точечного кроссовера (рекурсия одноточечного кроссовера глубиной п); оба потомка текущей пары заносятся в М.

5. Оператор мутации. С заданной вероятностью Рм каждая хромосома из М подвергается мутации с плотностью мутации 1 бит. Потомки родителей с одинаковым генотипом мутируют с плотностью Мс = М^Ь (где Ь - длина хромосомы).

6. Одинаковые хромосомы в новой популяции уничтожаются при помощи оператора мутации.

7. Для каждой хромосомы множества М вычисляется функция её приспособленности (фитнес-функция) на основе результатов турнира.

8. Из множества N выбирается К лучших хромосом и помещается на место К худших особей М (принцип элитаризма - лучшая особь всегда выживает). В множестве М можно выделить худшие хромосомы, т. к. для каждого элемента этого множества была посчитана фитнес-функция либо на предыдущем цикле алгоритма, либо на шаге 2.

9. Для нового множества М проводится турнир и на основе этого турнира для каждого элемента М вычисляется его финтес-функция.

10. Если не выполнено условие останова, то алгоритм возвращается на шаг 2. Условием остановки может служить как факт сходимости ГА к какому-либо

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

1) N - численность популяции;

2) п - размерность кроссовера;

3) РМ - вероятность применения оператора мутации. Целесообразными считаются небольшие значения порядка 0.01;

4) М1 - фактор, влияющий на плотность мутации при инцесте (0<К^< I), т. е. мутирует МГ*Ь (где Ь - длина хромосомы);

5) к - количество игр в матче.

Предлагаемая модель ГА обладает следующими особенностями:

1. Фиксированная популяция - N особей, фиксированная длина хромосомы - Ь.

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

3. Возможность применять любую стратегию отбора.

4. С точки зрения п-точечного кроссовера (2<п<Ь) хромосома является циклической, что позволяет организовать более полный перебор вариантов при создании новых особей.

5. Самоадаптнрующийся оператор мутации. В основе механизма самоадаптации лежит стратегия «инцеста» - у генетически близких родителей потомки мутируют с вероятностью 100% и с повышенной плотностью мутации. Это даёт следующее преимущество: при попадании ГА в локальный оптимум последствия мутации становятся более ощутимыми.

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

Г,= ЩХ,,М),

где Xi - хромосома из популяции М, для которой вычисляется значение фитнес-функции. Будем вычислять её следующим образом, на основе результатов проведённого турнира. Пусть wbw2,...,wn - количество побед каждого элемента популяции.

1. Найдём Wmjn = min(Wi).

2. Для каждой хромосомы вычислим fj = (Wi - Wmin)*A+B.

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

Стоит отметить, что до того, как была реализована подпрограмма эвристического алгоритма, работоспособность предлагаемой модели ГА проверялась (успешно, популяция сходилась в оптимуму в 90-120 поколении) на задаче оптимизации т. н. функции Rosenbrock's saddle (также известная как DeJong2)23. Причём фитнес-функция вычислялась по тому же принципу (на основе турнира), что и планировался для эвристического алгоритма. Функция DeJong2 выглядит следующим образом:

f(x) = 2СЮОСх,^ + -I)2)

Опишем алгоритм выбора максимального блока с максимальным рейтингом.

Пусть на вход алгоритма подана таблица Т, ячейки которой произвольным образом помечены символом '#'. Всего возможно 2N вариантов множеств столбцов, которые содержатся в блоках. Будем последовательно перебирать все элементы (множества столбцов) этого множества вариантов. Пусть бинарное представление (в двоичной системе счисления) числа j (0<j<2N) соответствует множеству столбцов Rj следующим образом: в множестве Rj содержатся те столбцы, которым в соответствующем номеру столбца разряде бинарного представления числа j соответствует 1. Например, числу 105ш (11010012) соответствуетRWS={0,1,3,6}.

Опишем алгоритм по шагам:

1. j = 0.

2. j=j+l; пусть текущий элемент - множество столбцов Rj.

3. Последовательно просмотрим все строки, и из тех, на пересечении которых со столбцами из множества Rj нет ячеек, не помеченных символом '#', образуем множество строк С.

4. Для блока (Rj,C) посчитаем его рейтинг, равный сумме рейтингов его ячеек. Сравним с текущим максимальным и примем за текущий максимальный (Rj,C), если его рейтинг окажется выше.

5. Если j=2N, максимальный блок найден и равен текущему максимальному блоку.

Очевидно, что ввиду перебора из 2N вариантов и того, что максимальный блок в одной таблице будет искаться до тех пор, пока блоками не покроются все ячейки, помеченные символом '#', данная процедура будет самой ресурсоёмкой. 3. Специальные алгоритмы принятия решения в случае многих экспертов-предикторов

J' Rosenbrock H. H. (1960) «An automatic method for finding the greatest or least value of a function». The Computer Journal. T.3.-P. 175-184.

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

Пусть экспертные оценки перспективности изменяются в пределах отрезка [0,1]. Пусть для 1-й стратегии 1 эксперт дал оценку 1 и 35 экспертов - оценку 0.055. А для 2-й стратегии 2 эксперта дали оценку 0.95, а остальные 34 эксперта -оценку 0. Отметим, что, по-видимому, на основе этих данных практически любой пользователь (человек) выберет 2-ю стратегию. (Поскольку в 1-й стратегии имеется 1 «очень хороший» результат и 35 «очень плохих», а для 2-й стратегии -соответственно 2 «очень хороших» и 34 «очень плохих»; «средних» же результатов ни в одном из двух случаев нет.) Однако усреднение по простейшему алгоритму (т. е. просто среднее арифметическое экспертных оценок) даёт 0.081 в 1-м случае и 0.053 во 2-м, т. е. надо выбирать 1-ю стратегию?

Проведём вычисления, аналогичные алгоритму построения динамических функций риска24. Для 1-й стратегии получаем функцию риска

-0.685 ■ х2 + 1.300 х + 0.386,

а для 2-й

-0.694 -х2 + 1.374 х + 0.321.

Окончательные значения усреднения экспертных оценок с помощью этих функций риска составляют 0.111 в 1-м случае и 0.147 - во 2-м. То есть применение алгоритмов динамического построения функций риска и усреднения экспертных оценок с их помощью даёт «более естественные» результаты.

При этом двукратное применение усреднения (т. е. усреднения с помощью предварительных значений, полученных в результате первого применения динамических функций риска) снова «даёт преимущество» 1-й стратегии. Однако в пределе снова получаются «естественные» результаты. Опишем эти результаты в виде следующей таблицы, где обозначения столбцов равны номеру усреднения с помощью динамической функции риска (другими словами - количеству применений алгоритма построения динамической функции риска). При этом столбец 0 - простое усреднение (среднее арифметическое оценок), а столбец ее —

0 1 2 3 4 5 ©о

1 -я стратегия 0.081 0.111 0.104 0.106 0.105 0.105 0.105

2-я стратегия 0.053 0.147 0.094 0.118 0.106 0.112 0.110

Эта таблица (а также результаты вычислительных экспериментов) свидетельствует в пользу применения описанных здесь эвристик.

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

24 Мельников Б. Ф. Программирование недетерминированных игр // Программирование (РАН). -80.

2001. -

№5,-

63-

проведённым автором статистическим исследованиям, составляют около 10%. 4. Локальные алгоритмы

Для минимизации ДНФ легко написать алгоритм, связанный с перебором большого числа вариантов, но он не является эффективным.

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

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

Например, локальные алгоритмы построения ДНФ 91 Кв и ДНФ 9? 2Т обладают определённой спецификой. Они базируются на специальном изучении покрытия Ы/ системой всех максимальных граней, в результате которого накапливается определенная информация о каждой максимальной грани. Выясняется, является ли грань Nко ядровой (входит в каждое неприводимое покрытие) или нет; выясняется,

является ли грань NК<1 регулярной (не входит ни в одно неприводимое покрытие)

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

Описанные здесь алгоритмы предполагают соответственный подход к проверке их основных характеристик. Для чего необходим алгоритм генерации множества ДНФ в виде /¡-мерных кубов.

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

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

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

25 Умрюхин Е. А. Целенаправленное поведение и самообучение живых организмов // Изв. РАН. ТиСУ. - 2003. - № 3. -С. 114-124.

м Судаков К. В. Системокванты жизнедеятельности // Устойчивое развитие. - 2003. 3/03. - С. 127-140.

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

Отметим также, что выделение генетической программы в отдельный блок не означает пространственного или органного выделения этого блока в организме. Выделение какого-то блока - это прежде всего выделение функции. Взаимодействие мозга и среды рассматривается в виде траекторий поведения, представляющих собой последовательность сигналов X и действий У. При этом если при сигнале Ха действие У вызывает переход к сигналу Х„, то будем называть такой переход ситуацией Ха->У—>ХВ. Отметим, что траектории поведения - это не только двигательные акты, но и речевые и мыслительные процессы.

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

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

Для математического моделирования обучения приводится обоснование применения предлагаемого в работе подхода.

Определим модель обучения как конечный автомат А с выходным языком как кортеж28

А = (Q, X, Y, 5, к, 1, F),

где

• Q — конечное множество состояний; в нашей модели они выражают принятие решения в процессе обучения;

• X — входной алфавит (Н, С} (сигналы)-,

• Y- выходной алфавит {Н, С} (действия);

• S - функция переходов состояний (transition function) или траектории поведения под действием символов входного алфавитах, т. е. §:Q>di—> 2й ;

• л — функция выходов под действием символов входного алфавита X, т. е. k:QXX-4>Y\

• / - множество начальных состояний;

• F - множество заключительных состояний. Рассмотрим две возможные ситуации:

1) правильно принятое решение;

2) неправильно принятое решение.

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

27 Анохин К. В., Судаков К. В. Геном нейронов мозга в организации системных механизмов поведения // Бюл. эксперим. биологии и медицины. - 2003. - T. 135. - № 2. - С. 124-131.

28 Бухараев Р. Г. Вероятностные автоматы. - Казань : Изд-во Казанского ун-та, 1970. - 188 с.

Человек принимает решения по потоку информации в каждый момент времени, оценивая ее. Он может правильно оценивать ситуацию, состояние (С), а может и неправильно - состояние (А) (рис. 3).

с/с

с/н

н/н

и/о

Рис. 3. Пример автомата А, моделирующего обучение

С конечным автоматом А естественно связывается конечная марковская цепь с вероятностями переходов р,^ из состояния г в состояние ] (рис. 4).

Для вероятностей перехода ри выполняются естественные соотношения Ри> 0 и £/>,.;= I, т. е. если мы находимся в состоянии /, то в какое-нибудь

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

0,9

0,1

0,2

0,8

Рис. 4. Пример автомата Л с вероятностями переходов

Рассмотрим теперь оптимальное обучение, т. е. детерминированные траектории поведения. Пусть автомат А/ задан таблицей состояний ~* 1 -» 1 л ест

а [2,4,7] [1] [5] [1]

Ь [3] [6] [1]

Граф автомата Л; можно преобразовать (упростить) без потери допускающих путей, объединяя состояния 4, 2, 7 в одно состояние, а затем объединяя новое полученное состояние с состоянием 3. Результат преобразования автомата А/ представлен на рис. 5 в виде графа состояний автомата А2.

Регулярное выражение (ааиааЬЬиаЬа)* определяет язык недетерминированного автомата А/, а регулярное выражение (ЬЫ1аЬ*а)* - язык детерминированного автомата А2. Языки, определяемые этими выражениями, различны, но все пути/циклы автомата А, находятся среди путей/циклов автомата А2. Таким образом, детерминированный автомат А2 имеет меньшее число состояний, и язык ЦА2) включает язык ЦА,). Такой алгоритм сворачивания ребер графа состояний эквивалентен выделению системы образующих подгруппы в конечно порожденной свободной группе и может использоваться в качестве вспомогательного, эвристического алгоритма для поиска недетерминированного

состояния, эквивалентного заданному состоянию обучения.

детерминированного А;

Регулярное выражение (ааиааЬЫ/аЬа)* определяет язык недетерминированного автомата А1, а регулярное выражение (ЬЫ/аЬ*а)* - язык детерминированного автомата Аг. Языки, определяемые этими выражениями, различны, но все пути/циклы автомата А/ находятся среди путей/циклов автомата Аг. Таким образом, детерминированный автомат Л2 имеет меньшее число состояний, и язык ЦАт) включает язык ЦАд- Такой алгоритм сворачивания ребер графа состояний эквивалентен выделению системы образующих подгруппы в конечно порожденной свободной группе и может использоваться в качестве вспомогательного, эвристического алгоритма для поиска недетерминированного состояния, эквивалентного заданному состоянию обучения.

Для серии регулярных выражений (аа1]ааЪЫ]аЪа)*Ь(а11Ь)к (для к > 2) при увеличении к количество состояний детерминированного конечного автомата (ДКА), построенного по недетерминированному конечному автомату, будет экспоненциально увеличиваться, а у соответствующего зеркального НКА и зеркального ДКА количество состояний увеличится пропорционально количеству букв справа от буквы Ь в вышеприведенном регулярном выражении. Сокращённая таблица позволяет найти НКА, покрывающий ДКА и имеющий наименьшее количество состояний. Его можно найти методом перебора, используя так называемые блоки, покрывающие рассматриваемые состояния.

Теперь рассмотрим более сложную модель обучения. Удобно представить модель Ь, имеющую состояние <7, разделив ее на три части, фактически на три языка: ¡Лс(я) ~ входящий (параметры внешнего воздействия) язык состояния д, 1!к(ч)~ язык внутреннего цикла состояния ц, Ск(с]) - выходящий (действия) язык состояния ц. Понятно, такие языки для любого состояния 9 будут регулярными и соединение соответствующих слов, этих языков по всем состояниям даст исходный язык Ь. Для зеркального языка Ьк движение по состояниям происходит в обратном

порядке, поэтому входящий язык становится зеркальным для правого языка

ЬТ(Ч), исходного языка Ь, слова языка внутреннего цикла проходятся в

обратном направлении по отношению к словам языка ¿.'¡¡(я)* аналогично и для выходящего языка Таким образом, двойственность или зеркальность

сохраняется и для входящего языка, выходящего языка и языка внутреннего цикла.

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

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

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

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

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

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

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

- исследовать структуру и характеристики течения однофазных (воздушных) и двухфазных (алюминиево-воздушных) потоков ограниченными стенками канала;

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

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

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

Для некоторой конкретной ¿-ограниченной сети Петри <Р,Т,1,О.М> с множеством позиций P={pt,...p„) рассмотрим НКА К = (Q, Z, <? S, F), элементы которого определяются следующим образом31:

• Q = М (множество маркировок ¿-ограниченной сети с множеством позиций Р, т. е. <2={0,1.....кП

• £={au\ije{l.....Л7;

• для некоторых маркировок сети M¡,Mjs М полагаем Mjg <5f M¡, a,j) тогда и только тогда, когда буква ац соответствует срабатыванию соответствующего перехода;

• S=fMo) (Mo - стартовая маркировка);

• F специально не задаётся; конкретные варианты задания F определяют смысл рассматриваемого нами варианта сети Петри.

В качестве позиций P={pi,...p„J в контексте нашей задачи определяем влияние геометрических и режимных параметров на границы зажигания. В частности, диаметр камеры сгорания, скорость потока, начальная турбулентность, температура воздуха, состав алюминиево-воздушной смеси, размер частиц алюминия.

При этом язык определённого НКА отображает все возможные варианты функционирования заданной сети Петри.

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

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

Заключение содержит основные выводы и результаты диссертации.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

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

29 Питерсон Дж. Теория сетей Петри и моделирование систем : пер. с англ. - М.: Мир. 1984. - 264 с.

Зубова Т. Н., Мельников Б. Ф. Использование сетей Петри для моделирования процесса принятия управленческих решений//Вектор науки ТГУ.-№ 3 (17). - Тольятти, 2011. 1 Все приведённые определения согласованы с:

Питерсон Дж. Теория сетей Петри и моделирование систем : пер. с англ. - М.: Мир. 1984. - 264 с.

Melnikov В. Once more on the edge-minimization of nondetenninistic finite autómata and the connected problems //

Fundamenta Informaticae. - 2010. - P. 267-283.

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

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

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

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

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

ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

Публикации в рецензируемых научных журналах и изданиях:

1. Пивнева С. В. Статистическая проверка гипотез по выборке II Научно-технический журнал «Наука - производству». - 2004. - № 8 (76). - М„ 2004. - С. 34-37. (из списка ВАК)

2. Пивнева С. В. Криволинейная корреляция в химической технологии // Научно-технический журнал «Наука - производству». - 2004. - № 8 (76). - М., 2004. - С. 38-40. (из списка ВАК)

3. Пивнева С. В. Постановка задачи стохастического управления образовательными процессами // Вестник Костромского гос. ун-та. - 2005. - № 2. -С. 117-123. (из списка ВАК)

4. Пивнева С. В. Определение функции качества при стохастическом моделировании образовательного процесса / С. В. Пивнева, О. А. Кузнецова // Известия Самарского научного центра Российской академии наук. - Самара : Изд-во Самарского научного центра РАН, 2006. - С. 170-175. (из списка ВАК)

5. Егоров А. Г. Организация рабочего процесса в камерах сгорания двигательных и энергетических установок нового поколения / А. Г. Егоров, С. В. Пивнева // Вестник Самарского гос. аэрокосмического ун-та. № 2 (10). Ч. 1. -Самара: Изд-во СГАУ, 2006. - С. 104-110. (из списка ВАК)

6. Кузнецова О. А. Управление качеством подготовки инженеров-менеджеров на основе предмета «Моделирование систем» / О. А. Кузнецова, С. В. Пивнева // Известия Самарского научного центра Российской академии наук. -Самара : Изд-во Самарского научного центра РАН, 2006. - С. 168-170. (из списка ВАК)

7. Пивнева С. В. Прогнозирование с помощью линейных регрессионных моделей // Известия Самарского научного центра Российской академии наук. Вып. 2. - Самара : Изд-во Самарского научного центра РАН, 2006. - С. 214-217. (из списка ВАК)

8. Пивнева С. В. Реконструкция динамических систем // Известия Самарского научного центра Российской академии наук. Вып. 3 - Самара : Изд-во Самарского научного центра РАН, 2007. - С. 179-185. (из списка ВАК)

9. Пивнева С. В. Учет априорной стохастической информации обобщенным методом максимального правдоподобия // Известия Самарского научного центра Российской академии наук. Вып. 4. - Самара : Изд-во Самарского научного центра РАН, 2007. - С. 111-116. (из списка ВАК)

10. Пивнева С. В. Алгоритмы прогнозирования и их применение для решения практических задач // Известия Самарского научного центра Российской академии наук. Вып. 6. - Самара : Изд-во Самарского научного центра РАН, 2008. - С. 83-91. (из списка ВАК)

11. Пивнева С. В. Принятие решений в гуманитарных областях - подходы к репрезентативности входных данных и сравнению эффективности алгоритмов // Информационные технологии моделирования и управления. - № 8 (51) - Воронеж : Изд-во «Научная книга», 2008. - С. 888-896. (Импакт-фактор РИНЦ - 0,104)

12. Пивнева С. В. Реализации методов прогнозирования // Известия Самарского научного центра Российской академии наук. Вып. 7. - Самара : Изд-во Самарского научного центра РАН, 2008. - С. 171-178. (из списка ВАК)

13. Пивнева С. В. Алгоритм определения репрезентативности недетерминированного конечного автомата / С. В. Пивнева, О. А. Рогова // Электронное научное периодическое издание «Электроника и информационные технологии» № 1 (5), зарегистрировано под номером 04200900067/0003 - Саранск : Изд-во Мордовского гос. ун-та им. Н. П. Огарева, 2009. (http://fetmag.mrsu.ru)

14. Мельников Б. Ф. Эвристические алгоритмы принятия решений в гуманитарных областях / Б. Ф. Мельников, С. В. Пивнева // Известия Самарского научного центра Российской академии наук. Вып. 8. - Самара : Изд-во Самарского

научного центра РАН, 2009. - С. 137-143. (из списка ВАК)

15. Пивнева С. В. Моделирование задач дискретной оптимизации / С. В. Пивнева, М. А. Трифонов II Вектор науки. - № 3 (13). - Тольятти : Тольят. гос. унт, 2010. -С. 31-34. (из списка ВАК)

16. Пивнева С. В. Модель турнирного самообучения // Вектор науки. - № 3

(13)'. - Тольятти : Тольят. гос. ун-т, 2010. - С. 25-28. (из списка ВАК)

17. Пивнева С. В. Принятие решений в прикладных задачах с применением динамически подобранных функций риска / С. В. Пивнева, Б. Ф. Мельников // Вестник транспорта Поволжья. - № 3.(23). - Самара : Самарский гос. ун-т путей сообщения, 2010. - С. 28-34. (из списка ВАК)

18. Пивнева С. В. Математическое моделирование принятия решений в различных предметных областях I С. В. Пивнева, Б. Ф. Мельников // Вектор науки. - № 3 (13). - Тольятти : Тольят. гос. ун-т, 2010. - С. 22-25. (из списка ВАК)

19. Пивнева С. В. Метод случайной генерации недетерминированных конечных автоматов и проверка репрезентативности сгенерированных структур I С. В. Пивнева, О. А. Рогова II Вестник Воронежского государственного университета. Серия: Системный анализ и информационные технологии. - 2010. - № 2. — С. 5-8. (из списка ВАК)

20. Пивнева С. В. Моделирование процессов перемещения и складирования штампов в прессовом производстве / С. В. Пивнева, А. В. Коженов // Вектор науки. - № 4 (14). - Тольятти : Тольят. гос. ун-т, 2010. - С. 25-26 (из списка ВАК)

21. Пивнева С. В. Имитационное моделирование принятия управленческих решений в системе обучения / С. В. Пивнева, С. С. Сытник // Вектор науки. - № 4

(14). - Тольятти : Тольят. гос. ун-т, 2010.- С. 23-24 (из списка ВАК)

22. Мельников Б. Ф. Репрезентативность случайно сгенерированных недетерминированных конечных автоматов с точки зрения соответствующих базисных автоматов / Б. Ф. Мельников, С. В. Пивнева, О. А. Рогова II Стохастическая оптимизация в информатике. Т. 6 / Санкт-Петербургский государственный университет, НИИ информационных технологий. - СПБ. : Изд-во Санкт-Петербург, гос. ун-та, 2010. - С. 74-82. (ISSN 1992-2922)

23. Пивнева С. В. Минимизация недетерминированных конечных автоматов по различным критериям // Вектор науки. - № 1 (15). - Тольятти : Тольят. гос. ун-т, 2011. - С. 19-21 (из списка ВАК)

Монографии:

24. Кустов Ю. А. Естественнонаучная подготовка специалиста (теория, исследование, практика) : монография / Ю. А. Кустов, С. В. Пивнева, В. А. Гусев (Рекомендовано Учебно-методическим объединением по профессионально-педагогическому образованию в качестве монографии). - Тольятти : Изд-во Поволжского отделения Российской академии образования, 2003. - 243 с.

25. Баумгертнер С. В. Мультиэвристический подход к проблеме звёздно-высотной минимизации недетерминированных конечных автоматов / С. В. Баумгертнер, Б. Ф. Мельников, С. В. Пивнева // Математические и компьютерные методы в технических, гуманитарных и общественных науках : монография. -Пенза : Изд-во «Приволжский дом знаний», 2011. - 188 с. (С. 101-112).

26. Пивнева С. В. Математическое моделирование процесса решения задач

: монография / С. В. Пивнева, Б. Ф. Мельников. - Тольятти : Изд-во ПВГУС, 2012. -128 с.

Материалы и статьи конференций, семинаров, симпозиумов:

27. Пивнева С. В. Применение метода корреляции для исследования зависимости скорости коррозии от нескольких факторов // Вестник автомеханического института.- Тольятти: Тольят. гос. ун-т, 2002. - С. 207-208

28. Пивнева С. В. Оценка нелинейной корреляционной связи в химической реакции // Вестник автомеханического институт.- Тольятти : Тольят. гос. ун-т, 2002. - С. 208-209.

29. Пивнева С. В. Математическое моделирование задачи по расчету нитрующих смесей / С. В. Пивнева, Г. В. Купцова // Проблема математического образования и культуры : сб. ст. международ, науч. конф. - Тольятти, 2003. - С. 26-29.

30. Пивнева СВ. Моделирование образовательной среды в условиях глобализации общественной жизни / С. В. Пивнева, С. Ш. Палферова // Формирование профессиональной культуры специалистов XXI века в техническом университете : труды 3-й международ, науч.-практ. конф.- СПб. : Санкт-Петербургский гос. политех, ун-т, 2003. - С. 145-147.

31. Пивнева С. В. Оптимальное управление обучающейся системой // Проектирование, обеспечение и контроль качества продукции и образовательных услуг : материалы VI всерос. конференции-семинара. - Самара : Самарский гос. тех. ун-т, 2003. - С. 156-160.

32. Пивнева С. В. Математическое моделирование оптимального управления образовательной средой // Татищевские чтения: актуальные проблемы науки и практики : материалы международ, науч. конф. - Тольятти, 2004. - С. 8488.

33. Пивнева С. В. Регрессионный анализ как математический метод оптимизации обучения // Управление качеством подготовки специалистов на основе профессиограмм : сб. докл. всерос. науч.-практ. конф. по профессиографическому проектированию образования и образовательных услуг. -М. - Тольятти, 2004. - С. 101-103.

34. Пивнева С. В. Математическое определение устойчивости динамической системы // Системный анализ в проектировании и управлении : труды IX меясдународ. науч.-практ. конф,- СПБ. : Санкт-Петербургский гос. политех, ун-т, 2005. - С. 177-179.

35. Пивнева С. В. Математическое моделирование процесса обучения // Проблемы университетского образования: содержание и технологии : труды П всерос. науч.-метод. конф. - Тольятти: Тольят. гос. ун-т, 2005. - С. 67-71.

36. Пивнева С. В. Информационная динамическая модель обучения // Многопрофильное профессиональное образование : сб. науч.-метод. работ / Российская академия естественных наук, Тольятгинский гос. ун-т. - Тольятти, 2007.-С. 143-149.

37. Пивнева С. В. Флуктуация параметров при математическом моделировании динамических систем // Математика. Образование. Культура (к 85-летию со дня рождения В. И. Крупича): III международная научная конференция. Ч. 4 (17-25 апреля 2007.). - Тольятти, 2007. - С. 122-128.

'38. Егоров А'. Г. Организация рабочего процесса в камерах сгораййя: реактавных двигателей на псевдожидком топливе / А. Г. Егоров, С. В. Пивнева, А. Н. Попов И Актуальные проблемы российской космонавтики : труды ХХХП академических чтений по космонавтике (29 января - 1 февраля 2008 г.). - М., 2008. -С. 180-182.

39. Панин А. Г. Прогнозирование временных рядов на основе системы эвристических правил / А. Г. Панин, С. В. Пивнева // Технологии искусственного интеллекта в Экономике-2008 : XIV научно-практическая конференция. РАН -«Научно-технологический парк «Дубна», 2008. - С. 156-158.

40. Пивнева С. В. Новые аспекты моделирования принятия решений в многокритериальных задачах // Проведение научных исследований в области машиностроения : труды всерос. науч.-технич. конф. Ч. 3 (27-28 ноября 2009 г.). -Тольятти, 2009. - С. 3-5.

41. Мельников Б. Ф. Мультиэвристический подход к задачам дискретной оптимизации / Б. Ф. Мельников, С. В. Пивнева // Методы и средства обработки информации : труды Третьей всерос. науч. конф. (ВМК МГУ 6-8 октября 2009 г.). -М., 2009.-С. 268-280.

42. Мельников Б. Ф. Применение мультиэвристического подхода в задаче вершинной минимизации недетерминированных конечных автоматов / Б. Ф. Мельников, С. В. Пивнева, А. В. Цыганов // Нейроинформатика, ее приложения и анализ данных: материалы XVII всерос. семинара (ИВМ СО РАН, 2-4 октября 2009 г.). - Красноярск, 2009. - С. 73-78.

43. Пивнева С. В. Математическое моделирование социальных процессов / С. В. Пивнева, Ю. Ф. Кустов // Актуальные проблемы непрерывного профессионального образования : сб. науч. тр. - Тольятти : ТГУ, 2010. - С. 233-241.

44. Пивнева С. В. Новые аспекты применения информационных технологий в управлении обучением // Математические методы и информационные технологии в экономике, социологии и образовании : сб. ст. XXVI международ, науч.-технич. конф. - Пенза : Приволжский дом знаний, 2010. - С. 232-235.

45. Пивнева С. В. Моделирование и реализация адаптивной обучающей системы / С. В. Пивнева, С. С. Сытник // Современные информационные технологии и ИТ-образование : труды VI международ, науч.-практ. конф. / ВМК МГУ имени М. В. Ломоносова. - М„ 2011. - С. 408-422.

46. Пивнева С. В. Еще раз о репрезентативности случайно сгенерированных недетерминированных конечных автоматов / С. В. Пивнева, Б. Ф. Мельников, О. А. Рогова // Некоторые вопросы математического моделирования дискретных систем : сб. науч. тр. - Тольятти : ТГУ, 2011. - С. 175-183.

47. Пивнева С. В. Программная реализация задач дискретной оптимизации / С. В. Пивнева, М. А. Трифонов // Некоторые вопросы математического моделирования дискретных систем : сб. науч. тр. - Тольятти : ТГУ, 2011. - С. 210219.

48. Пивнева С. В. Подход к репрезентативности входных данных для случайной генерации дизъюнктивных нормальных форм / С. В. Пивнева, М. А. Трифонов // Физико-математическое моделирование систем : материалы УШ международ. семинара ' (ФММС-8). - Воронеж, 2011. http://www.vorstu.ru/conferences/79/86/529/

Подписано в печать с электронного оригинал-макета 03.04.2012. Бумага офсетная. Печать трафаретная. Усл. печ. л. 2,0. Тираж 120 экз. Заказ 62/02.

Отпечатано в Издательско-полиграфическом центре Поволжского государственного университета сервиса. 445677, г. Тольятти, ул. Гагарина, 4. тел. (8482) 222-650.