Авторефераты по всем темам  >>  Авторефераты по техническим специальностям  

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

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

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

Специальность 05.13.18 - Математическое моделирование,

численные методы и комплексы программ

АВТОРЕФЕРАТ

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

доктора физико-математических наук

Тольятти

2011

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

Научный консультант:        доктор физико-математических наук, профессор

Мельников Борис Феликсович

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

Угольницкий Геннадий Анатольевич (ЮФУ)

доктор физико-математических наук, профессор

Соколов Андрей Владимирович (ИПМИ КарН - РАН)

доктор технических наук, профессор

Скобцов Юрий Александрович (ДонНТУ)

       

Ведущая организация:        ФГБОУ ВПО Кабардино-Балкарский

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

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

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

Электронная версия автореферата размещена также на официальном сайте Министерства образования и науки Российской Федерации

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

Автореферат разослан нн__ _______________ 2012 г.

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

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

доктор физико-математических наук                                                Решетов В.А.

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

Актуальность темы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Научная новизна работы заключается в следующем.

1. Предложен качественно новый многоаспектный подход к математическому моделированию процесса принятия решений. Данный подход состоит из следующих взаимосвязанных этапов: проверка репрезентативности входных данных; непосредственное моделирование интеллектуальных систем, разработка и описание наиболее оптимального алгоритма принятия решения; анализ и апостериорная оценка качества принятого решения на адекватность выбранных алгоритмов и сравнение их эффективности.
2. Разработан и реализован подход к определению репрезентативности входных данных, состоящий в случайной генерации структур с характеристиками, удовлетворяющими рассматриваемой предметной области. Такая случайная генерация комбинаторных структур позволяет не только проверять алгоритмы, основанные на этой структуре, но и выполнять обратную задачу - исследовать поведение этих структур. После такого исследования можно не только выяснять, насколько адекватно они описывают реальные объекты, поведение которых мы моделируем, но и улучшать их репрезентативность - путём реализации более приемлемых алгоритмов генерации. То есть можно сказать, что разработанная модель генерации сама определяет репрезентативность для конкретной предметной области.
3. Обоснована взаимосвязь трёх этапов многоаспектного подхода при решении задач дискретной оптимизации - поскольку изменения в условиях задачи, исходных данных или принципов определения репрезентативности могут привести к выбору существенно отличающихся эвристик. В работе предложен алгоритм генерации, обладающий параметрами, влияющими на репрезентативность случайно генерируемых структур (на примерах недетерминированных конечных автоматов и дизъюнктивных нормальных форм). При этом генерация структур с характеристиками, удовлетворяющими предметной области, повышает качество этих алгоритмов и организует эти структуры адекватные реально моделируемым объектам.
4. Показано применение многоаспектного подхода для решения задач дискретной оптимизации в различных предметных областях. Причём разные аспекты нового подхода могут применяться на разных этапах решения задач дискретной оптимизации. Рассматриваются разные алгоритмы-предикторы (либо подпрограммы-предикторы), которые в результате работы дают свои оценки качества ситуаций, получаемые при принятии конкретных решений - например, при выборе разных разрешающих элементов в модификациях метода ветвей и границ. При этом про данные оценки ничего не известно заранее. Разрешающими элементами в различных ЗДО могут быть: блок - в задаче вершинной минимизации недетерминированных конечных автоматов; конкретная дуга - в задаче их дуговой минимизации; вершина - в задаче их звёздно-высотной минимизации; упорядоченная пара городов - в задаче коммивояжёра и др. Далее возможны две модели. Либо каждый квалификационный признак оценивается разными программами-предикторами, и в результате общее решение принимается на основе построенного нами результирующего мнения обо всех признаках. Либо каждый эксперт независимо принимает итоговое решение и при этом мы (т.е. наша система) должны принять одно решение путем лусреднения - причём не частичных, а литоговых их мнений. Обе эти модели действительно нужны для решения задач дискретной оптимизации, но, кроме этого, могут быть применены ещё и для разработки конкретных экспертных систем.
5. Предложен подход к апостериорной оценка качества принятого решения, описывающий проверку результатов (сравнение значений т.н. фитнесс-функций), причём опять же на основе нескольких подходов. Сама же фитнесс-функция здесь - это например, время работы разных алгоритмов на одних и тех же входных данных. Примеры оценки ситуаций, также получаемых с помощью эвристических вспомогательных алгоритмов - это оценка оставшегося времени работа алгоритма; оценка вероятности завершения алгоритма за заранее заданное время; оценка вероятности получения в результате завершения работы алгоритма нового псевдо-оптимального допустимого решения и др.

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

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

Полученные в работе результаты могут быть использованы для математического моделирования образовательного процесса, новых обучающих технологий в образовании, принятия решений для специальных обучающих, контрольных, психологических тестов [3, 4, 14, 21, 37, 46, 47]. Создание двигательных и энергетических установок нового поколения требует применение новых аспектов математического моделирования для эффективной организации рабочего процесса в камерах сгорания реактивных двигателей на псевдожидком топливе [5, 39, 40]. Применение программных комплексов для решения псевдогеометрического варианта задачи коммивояжёра является актуальным при оптимизации процессов перемещения и складирования штампов в прессовом производстве ВАЗа [20], исследовании зависимости скорости коррозии от нескольких факторов [29], оценки химической реакции [2, 30].

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

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

• Международная научно-практическая конференция Формирование профессиональной культуры специалистов XXI века в техническом университете, Санкт-Петербургский государственный политехнический университет, Санкт-Петербург, 2003 г.
• Всероссийская конференцияЦсеминар Проектирование, обеспечение и контроль качества продукции и образовательных услуг, Самарский государственный технический университет, Самара, 2003 г.
• Международная научная конференция Актуальные проблемы науки и практики, Тольятти, 2004 г.
• Международная научно-практическая конференция Системный анализ в проектировании и управлении, Санкт-Петербургский государственный политехнический университет, Санкт-Петербург, 2005 г.
• Международная научная конференция Развитие космонавтики и фундаментальные проблемы газодинамики, горения и теплообмена, Самарский государственный аэрокосмический университет им. Академика С.П.Королёва, Самара, 2006г .
• Международная научная конференция Математика. Образование. Культура, Тольятти, 2007 г. , 2009 г. , 2011 г.
• XXXII академические чтения по космонавтике Актуальные проблемы Российской космонавтики, РАН, Москва, 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 - Многоаспектный анализ эвристических алгоритмов оптимизации дискретных математических структур больших размерностей.

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

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

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

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

1. Многоаспектный подхода к математическому моделированию процесса принятия решений.
2. Подход к определению репрезентативности входных данных.
3. Описание этапов решения задач дискретной оптимизации и обоснование их взаимосвязи.
4. Описание вариантов применения разработанного многоаспектного подхода к решению конкретных задач дискретной оптимизации.
5. Подход к апостериорной оценке качества принятого решения.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• количество плоскостей;
• размерности плоскостей;
• их координаты.

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

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

• Отношение количества 0 к количеству 1.
• Количество плоскостей, получающихся при минимизации сгенерированных ДНФ жадным алгоритмом.
• Количество получающихся после такой минимизации плоскостей, покрывающих каждую точку в n-мерном кубе.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• размерность оптимизационной задачи;
• количество случайно сгенерированных задач (например, для заданной размерности запускается 100 случайно сгенерированных задач; отметим, что, как и ожидалось, от входа л100 случайных задач итоговые результаты практически не зависят);
• относительная величина превышения границы G (обычно это - величина порядка 0.1, т.е. 10%).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

f (x0)=min f(x)  либо  f (x0)=max f(x),  xG,

множество допустимых решений которой конечно, т.е 0|G|=N<. 12

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

• множества входов;
• ограничений для любого входа и допустимых решений;
• функции стоимости;
• цели (max или min).

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

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

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

• Нерегулярность: ЗДО характеризуются тем, что область допустимых решений невыпуклая и несвязная - поэтому для их решения неприменимы стандартные методы, с помощью которых решают регулярные задачи математического программирования (задачи линейного и выпуклого программирования).
• Трудности при определении окрестности: в ЗДО: близость двух допустимых решений x1 и x2 может быть оценена только по значениям функции стоимости f(x1) и f(x2). В качестве примера рассмотрим, как можно ввести понятие окрестности в задаче коммивояжёра, где решение представляется последовательностью вершин некоторого гамильтонового цикла. Здесь под окрестностью некоторого решения x можно понимать все решения, получаемые из x перестановкой двух вершин. При этом легко построить примеры задач (матриц стоимости), для которых такая перестановка может привести к значительному изменению стоимости решения.
• Невозможность выполнения большого перебора на компьютере. Многие методы решения ЗДО основаны на идее полного перебора допустимых решений. Объём вычислений в таких алгоритмах резко возрастает с ростом размера входных данных. Например, сложность переборного алгоритма для задачи коммивояжёра составляет O(n!).

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

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

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

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

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

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

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

	X	Y	Z	U
A	0	0	1	1
B	1	0	0	1
C	1	1	1	1
D	1	1	1	1

Таблица 1

Таблица.1 представляет простой пример к этой задаче. В нём имеются следующие 5 блоков - ={A,B,C,D}{U}, ={A,C,D}{Z,U} (элементы этого блока выделены курсивом), ={B,C,D}{X,U}, ={C,D}{X,Z,U} и ={D}{X,Y,Z,U}. Для покрытия всех значений 1 заданной матрицы достаточно использовать 3 из этих 5 блоков - , и .

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

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

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

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

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

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

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

• LB - число букв переменных, встречающихся в записи ДНФ;
• LK - число элементарных конъюнкций, входящих в ДНФ;
• L0 - число отрицаний, встречающихся в записи ДНФ.

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

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

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

1. Методы мультиагентной оптимизации

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

В базовом алгоритме AS (в дальнейшем - ASbase) построение решения задачи производится путём перемещения агентов из города в город на т.н. проблемном графе. На построение решений оказывает влияние искусственный след феромона, а также эвристическая информация, полученная на предыдущих итерациях алгоритма. При применении ASbase к ЗКВ каждому ребру aij графа G ставится в соответствие определённое количество феромона τij(t), где τij - это числовая информация, модифицируемая во время работы алгоритма, а t - номер итерации. При применении ASbase к симметричной ЗКВ имеем τij(t)=τij(t), а в случае несимметричной задачи τij(t)≠τij(t).

На начальной стадии алгоритма каждый из m агентов помещается в произвольно выбранный город, а затем каждый агент применяет следующее правило изменения своего местонахождения. Все агенты строят туры следующим образом. Находясь в городе i, агент выбирает ещё не посещённый город j, основываясь на величине феромона τij(t), соответствующего ребру aij, и локально доступной эвристической информации, которая является функцией от ребра aij. Агенты выбирают с большей вероятностью города, которые расположены ближе к текущему и соединены рёбрами с бльшим количеством феромона. Для получения допустимого решения каждому агенту выделяется ограниченная область памяти, называемая табу-листом, в которой записан текущий тур. Табу-лист используется для определения непосещённых городов, а также даёт возможность заново пройти тур и сделать необходимые изменения.

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

2. Специальные варианты применения генетических алгоритмов. Технология турнирного самообучения

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

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

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

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

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

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

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

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

Схема туров имеет вид:

1. Последовательно выбирается Oi (0i<N-1) из полученного на вход множества N где N - его мощность.
2. Для Oi последовательно выбирается соперник Oj (i<j<N).
3. Проводится матч из k раундов между текущей парой соперников. Игра проводится следующим образом:
1. генерируется игровое поле;
2. выполняется программа, определяемая хромосомой Oi;
3. выполняется программа, определяемая хромосомой Oj;
4. той хромосоме, чья программа набирает меньшее количество очков в раунде, засчитывается выигрыш (в нашем случае под очками будем понимать количество отобранных эвристическим алгоритмом блоков).
5. в случае ничьи (оба алгоритма выбрали одинаковое количество блоков) обе хромосомы получают по выигрышу.
4. Количество побед в матче добавляется к текущему количеству побед для каждой хромосомы Oi и Oj .
5. Общее количество побед каждой хромосомы есть значение относительной приспособленности (мера превосходства одного эвристического алгоритма над другими).

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

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

fi=FF(Xi,M),

где Xi - хромосома из популяции M для которой для которой вычисляется значение фитнесс-функции, на основе результатов проведённого турнира. Пусть w1,w2,Е,wn - количество побед каждого элемента популяции.

1. Найдём wmin = min(wi).
2. Для каждой хромосомы вычислим fi = (wнi - wminн)*A+B.

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

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

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

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

В работе представлен алгоритм по шагам:

1. j = 0.
2. j=j+1; пусть текущий элемент - множество столбцов Rj.
3. Последовательно просмотрим все строки, и из тех, на пересечении которых со столбцами из множества Rj нет ячеек, не помеченных символом С#Т, образуем множество строк C.
4. Для блока (Rj,C) посчитаем его рейтинг, равный сумме рейтингов его ячеек. Сравниваем с текущим максимальным, и принимаем за текущий максимальный блок (Rj,C), если его рейтинг оказывается выше.
5. Если j=2N, максимальный блок найден и равен текущему максимальному блоку.

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

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

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

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

Ц0.685 ⋅ x2 + 1.300 ⋅ x + 0.386 ,

а для 2-й Ц

Ц0.694 ⋅ x2 + 1.374 ⋅ x + 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 при равномерном распределении всех значений dij они, согласно проведённым автором статистическим исследованиям, составляют около 10%.

4. Локальные алгоритмы

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

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

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

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

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

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

1 . Математическое моделирование обучения

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

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

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

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

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

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

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

Aа=а(Q,аX,аYа, δ,а,аI, F),

где:

• Q - конечное множество состояний; в нашей модели они выражают принятие решения в процессе обучения;
• X - входной алфавит {Н, С} (сигналы);
• Y - выходной алфавит {Н, С} (действия);
• δ - функция переходов состояний (transition function) или траектории поведения, под действием символов входного алфавита X, т.е. δа:Q×X→ ;
• - функция выходов, под действием символов входного алфавита X, т.е. а:Q×X→ ;
• I - множество начальных состояний;
• F - множество заключительных состояний,.

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

Рассмотрим две возможные ситуации:

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

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

С конечным автоматом естественно связывается конечная марковская цепь с вероятностями переходов из состояния в состояние .

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

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

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

	1	2	3	4	5	6	7
a	[ 2, 4, 7 ]		[ 1 ]	[ 5 ]			[ 1 ]
b		[ 3 ]			[ 6 ]	[ 1 ]

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

Рис 5. Графы состояний исходного недетерминированного автомата A1 и свёрнутого детерминированного A2.

Регулярное выражение (aaUaabbUaba)* определяет язык недетерминированного автомата A1, а регулярное выражение (bbUab*a)* - язык детерминированного автомата A2 . Языки, определяемые этими выражениями, различны, но все пути/циклы автомата A1 находятся среди путей/циклов автомата A2. Таким образом, детерминированный автомат A2 имеет меньшее число состояний, и язык L(A2) включает язык L(A1). Такой алгоритм сворачивания ребер графа состояний эквивалентен выделению системы образующих подгруппы в конечнопорожденной свободной группе и может использоваться в качестве вспомогательного, эвристического алгоритма для поиска недетерминированного состояния, эквивалентного заданному состоянию обучения.

Для серии регулярных выражения (aaUaabbUaba)*b(aUb)k (для k 2) при увеличении k количества состояний детерминированного конечного автомата (ДКА), построенного по недетерминированному конечному автомату, будет экспоненциально увеличиваться, а у соответствующего зеркального НКА и зеркального ДКА количество состояний увеличится пропорционально количеству букв справа от буквы b в вышеприведенном регулярном выражении. Сокращённая таблица позволяет найти НКА, покрывающий ДКА и имеющий наименьшее количество состояний. Его можно найти методом перебора, используя, так называемые блоки, покрывающие рассматриваемые состояния.

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

В работе более подробно рассмотрена взаимосвязь между этими тремя языками и состояниями автомата как тернарное отношение на такое, что , если и (I, w) и R(F, vR) и , в противном случае. Отношение определяет представление слова в виде конкатенации слова входящего языка и слова выходящего языка состояния q.

Рис.6. Модель обучения, на основе НКА

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

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

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

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

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

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

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

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

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

Для некоторой конкретной k-ограниченной сети Петри <P,T,I,O,M> со множеством позиций P={p1,...pn} рассмотрим НКА K = ( Q, ∑, δ, S, F ), элементы которого определяются следующим образом28:

• Q = M (множество маркировок k-ограниченной сети со множеством позиций P, т.е. Q={0,1,...,k}n);
• = {aij | i,j{1,...,N};
• для некоторых маркировок сети Мi,MjM полагаем Mjδ( Мi , aij) тогда и только тогда, когда буква aij соответствует срабатыванию соответствующего перехода;
• S={M0) (M0 - стартовая маркировка);
• F специально не задаётся; конкретные варианты задания F определяют смысл рассматриваемого нами варианта сети Петри.

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

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

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

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

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

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

1. Предложен качественно новый многоаспектный подход к математическому моделированию процесса принятия решений. Данный подход состоит из следующих взаимосвязанных этапов: проверка репрезентативности входных данных; непосредственное моделирование интеллектуальных систем, включающее разработку и описание наиболее оптимального алгоритма принятия решения; анализ и апостериорная оценка качества принятого решения на адекватность выбранных алгоритмов и сравнение их эффективности.
2. Разработан и реализован подход к определению репрезентативности входных данных, состоящий в случайной генерации структур с характеристиками, удовлетворяющими рассматриваемой предметной области. Такая случайная генерация комбинаторных структур позволяет: проверять алгоритмы, основанные на этой структуре; а также исследовать поведение этих структур. Далее, после этого исследования, можно не только выяснять, насколько они описывают реальные объекты, поведение которых мы моделируем (т.е. насколько они репрезентативны) - но и улучшить их репрезентативность путём реализации более приемлемых алгоритмов генерации. То есть разработанная модель генерации сама определяет репрезентативность для конкретной предметной области.
3. Обоснована взаимосвязь трёх этапов многоаспектного подхода при решении задач дискретной оптимизации. Изменения в условиях задачи, исходных данных или принципов определения репрезентативности могут привести к выбору существенно отличающихся эвристик. В работе предложен алгоритм генерации, обладающий параметрами, влияющими на репрезентативность случайно генерируемых структур (на примере НКА и ДНФ). При этом генерация структур с характеристиками, удовлетворяющими предметной области, повышает качество этих алгоритмов и организует эти структуры адекватные реально моделируемым объектам.
4. Показано применение многоаспектного подхода для решения задач дискретной оптимизации в различных предметных областях. Причём разные аспекты нового подхода могут применяться на разных этапах решения задач дискретной оптимизации. Рассматриваются разные программы-предикторы (точнее - лалгоритмы-предикторы), которые в результате работы дают свои оценки качества ситуаций, получаемые при выборе разных разрешающих элементов. При этом заранее про данные оценки ничего не известно. Разрешающими элементами в различных ЗДО могут быть: блок - в задаче вершинной минимизации недетерминированных конечных автоматов; конкретная дуга - в задаче их дуговой минимизации; вершина - в задаче их звёздно-высотной минимизации; упорядоченная пара городов - в задаче коммивояжёра и др. Далее возможны две модели. Либо каждый квалификационный признак оценивается разными программами-предикторами и в результате общее решение принимается на основе построенного нами результирующего мнения обо всех признаках. Либо каждый эксперт независимо принимает итоговое решение и при этом мы (т.е. наша система) должны принять одно решение путем лусреднения - причём не частичных, а литоговых их мнений. Обе эти модели действительно нужны для решения задач дискретной оптимизации, но, кроме этого, могут быть применены ещё и для разработки конкретных экспертных систем.
5. Проведена апостериорная оценка качества принятого решения. Это - проверка результатов (сравнение значений т.н. фитнесс-функций), опять же на основе нескольких пододов. В данном случае сама фитнесс-функция может представлять собой: ожидаемое время работы разных алгоритмов на одних и тех же входных данных; оценка вероятности завершения алгоритма за заранее заданное время; оценка вероятности получения в результате завершения работы алгоритма нового псевдо-оптимального допустимого решения и др.

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

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

1. Пивнева, С.В. Статистическая проверка гипотез по выборке / С.В. Пивнева // Научно-технический журнал Наука производству. №8(76)/2004, август. - Москва, 2004г. (из списка ВАК)
2. Пивнева, С.В. Криволинейная корреляция в химической технологии / С.В. Пивнева // Научно-технический журнал Наука производству. №8(76)/2004, август. - Москва, 2004г. (из списка ВАК)
3. Пивнева, С.В. Постановка задачи стохастического управления образовательными процессами / С.В. Пивнева // Вестник Костромского государственного университета. № 2 2005, -Кострома, 2005 г (из списка ВАК)
4. Пивнева, С.В. Определение функции качества при стохастическом моделировании образовательного процесса / С.В. Пивнева, О.А. Кузнецова // Известия Самарского научного центра Российской академии наук - г. Самара: Изд-во Самарского научного центра РАН, 2006. (из списка ВАК)
5. Егоров, А.Г. Организация рабочего процесса в камерах сгорания двигательных и энергетических установок нового поколения/ С.В. Пивнева, А.Г. Егоров // Вестник Самарского государственного аэрокосмического университета. №2(10). Часть 1. - г. Самара: Изд-во СГАУ, 2006. Ц104с. (из списка ВАК)
6. Кузнецова, О.А. Управление качеством подготовки инженеров-менеджеров на основе предмета Моделирование систем/ О.А. Кузнецова, С.В. Пивнева // Известия Самарского научного центра Российской академии наук - г. Самара: Изд-во Самарского научного центра РАН, 2006. (из списка ВАК)
7. Пивнева, С.В. Прогнозирование с помощью линейных регрессионных моделей / С.В. Пивнева // Известия Самарского научного центра Российской академии наук, Вып. 2 - г. Самара: Изд-во Самарского научного центра РАН, 2006. (из списка ВАК)
8. Пивнева, С.В. Реконструкция динамических систем / С.В. Пивнева // Известия Самарского научного центра Российской академии наук, Вып. 3 - г. Самара: Изд-во Самарского научного центра РАН, 2007. (из списка ВАК)
9. Пивнева, С.В. Учет априорной стохастической информации обобщенным методом максимального правдоподобия / С.В. Пивнева // Известия Самарского научного центра Российской академии наук, Вып. 4 - г. Самара: Изд-во Самарского научного центра РАН, 2007. (из списка ВАК)
10. Пивнева, С.В. Алгоритмы прогнозирования и их применение для решения практических задач / С.В. Пивнева // Известия Самарского научного центра Российской академии наук, Вып. 6 - г. Самара: Изд-во Самарского научного центра РАН, 2008. (из списка ВАК)
11. Пивнева, С.В. Принятие решений в гуманитарных областях - подходы к репрезентативности входных данных и сравнению эффективности алгоритмов / С.В. Пивнева // Информационные технологии моделирования и управления, №8(51) - г. Воронеж: Изд-во Научная книга, 2008. - 888 с. (Импакт-фактор РИН - - 0,104)
12. Пивнева, С.В. Реализации методов прогнозирования / С.В. Пивнева // Известия Самарского научного центра Российской академии наук, Вып. 7 - г. Самара: Изд-во Самарского научного центра РАН, 2008. (из списка ВАК)
13. Пивнева, С.В. Алгоритм определения репрезентативности недетерминированного конечного автомата/ С.В. Пивнева, О.А. Рогова // Электронное научное периодическое издание Электроника и информационные технологии ( - г. Саранск: Изд-во Мордовского государственного университета им. Н.П. Огарева, вып.1- 2009г.
14. Мельников, Б.Ф. Эвристические алгоритмы принятия решений в гуманитарных областях / Б.Ф. Мельников, С.В. Пивнева // Известия Самарского научного центра Российской академии наук, Вып. 8 - г. Самара: Изд-во Самарского научного центра РАН, 2009. (из списка ВАК)
15. Пивнева, С.В. Моделирование задач дискретной оптимизации / С.В. Пивнева, М.А. Трифонов // Вектор науки №3(13) - г. Тольятти: Тольяттинский государственный университет, 2010 г. (из списка ВАК)
16. Пивнева, С.В. Модель турнирного самообучения/ С.В. Пивнева // Вектор науки №3(13) - г. Тольятти: Тольяттинский государственный университет, 2010 г. (из списка ВАК)
17. Пивнева, С.В. Принятие решений в прикладных задачах с применением динамически подобранных функций риска / С.В. Пивнева, Б.Ф. Мельников // Вестник транспорта Поволжья №3(23) - г. Самара: Самарский государственный университет путей сообщения, 2010 г. (из списка ВАК)
18. Пивнева, С.В. Математическое моделирование принятия решений в различных предметных областях/ С.В. Пивнева, Б.Ф. Мельников // Вектор науки №3(13) - г. Тольятти: Тольяттинский государственный университет, 2010 г. (из списка ВАК)
19. Пивнева, С.В. Метод случайной генерации недетерминированных конечных автоматов и проверка репрезентативности сгенерированных структур / С.В. Пивнева, О.А. Рогова // Вестник Воронежского государственного университета. Серия: Системный анализ и информационные технологии, 2010.№2. С.5Ц8 (из списка ВАК)
20. Пивнева, С.В. Моделирование процессов перемещения и складирования штампов в прессовом производстве/ С.В. Пивнева, А. В. Коженов // Вектор науки №4(14) - г. Тольятти: Тольяттинский государственный университет, 2010г (из списка ВАК)
21. Пивнева, С.В. Имитационное моделирование принятия управленческих решений в системе обучения / С.В. Пивнева, С.С. Сытник // Вектор науки №4(14) - г. Тольятти: Тольяттинский государственный университет, 2010г. (из списка ВАК)
22. Мельников, Б.Ф. Репрезентативность случайно сгенерированных недетерминированных конечных автоматов с точки зрения соответствующих базисных автоматов / Мельников Б.Ф., Пивнева С.В., Рогова О.А.//Стохастическая оптимизация в информатике. Том 6. Санкт-Петербургский государственный университет НИИ информационных технологий. Изд-во: Санкт-Петербургского государственного университета - 2010 г. ISSN 1992-2922
23. Пивнева, С.В. Минимизация недетерминированных конечных автоматов по различным критериям // Вектор науки №1(15) - г. Тольятти: Тольяттинский государственный университет, 2011 г. (из списка ВАК)

Монографии:

24. Кустов, Ю.А. Естественно-научная подготовка специалиста (теория, исследование, практика) / Ю.А. Кустов, С.В. Пивнева, В.А. Гусев. Монография. Рекомендовано Учебно-методическим объединением по профессионально-педагогическому образованию в качестве монографии. - г. Тольятти: Изд-во Поволжского отделения Российской академии образования, 2003 г.
25. Пивнева, С.В. Многоаспектный подход к принятию решений в прикладных оптимизационных задачах / Пивнева С.В. // Монография. - Тольятти: Изд-во ТГУ, 2009 г.
26. Баумгертнер, С.В. Мультиэвристический подход к проблеме звёздно-высотной минимизации недетерминированных конечных автоматов / С.В. Баумгертнер, Б.Ф. Мельников, С.В. Пивнева // Математические и компьютерные методы в технических, гуманитарных и общественных науках: Монография. - Пенза: Изд-во Приволжский Дом знаний, 2011. - . С. 101-112.
27. Пивнева, С.В. Математическое моделирование процесса решения задач / Б.Ф. Мельников, С.В. Пивнева // Монография, - г. Тольятти: Изд-во ТГУ, 2011г.
28. Пивнева, С.В. Некоторые вопросы математического моделирования дискретных систем / С.В. Пивнева //Монография. - Москва: Изд-во РАН, 2011г.

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

29. Пивнева, С.В. Применение метода корреляции для исследования зависимости скорости коррозии от нескольких факторов/ С.В. Пивнева // Вестник автомеханического института. Труды всероссийской конференции. Тольяттинский государственный университет - г. Тольятти, 2002г.
30. Пивнева, С.В. Оценка нелинейной корреляционной связи в химической реакции/ С.В. Пивнева // Вестник автомеханического института. Труды всероссийской конференции. Тольяттинский государственный университет - г. Тольятти, 2002г.
31. Пивнева, С.В. Математическое моделирование задачи по расчету нитрующих смесей / С.В. Пивнева, Г.В. Купцова // Проблема математического образования и культуры. Международная научная конференция: Сборник научных статей - г. Тольятти - 2003. Ц
32. Пивнева, С.В. Моделирование образовательной среды в условиях глобализации общественной жизни / С.В. Пивнева, С.Ш. Палферова // Формирование профессиональной культуры специалистов XXI века в техническом университете. Труды 3-й Международной научно-практической конференции. Санкт-Петербургский государственный политехнический университет. - г.Санкт-Петербург, 2003. Ц
33. Пивнева, С.В. Оптимальное управление обучающейся системой / С.В. Пивнева // Проектирование, обеспечение и контроль качества продукции и образовательных услуг. Материалы VI Всероссийской конференции - семинара. Самарский государственный технический университет. - г.Самара, 2003г. Ц
34. Пивнева, С.В. Математическое моделирование оптимального управления образовательной средой / С.В. Пивнева // Татищевские чтения: Актуальные проблемы науки и практики. Материалы международной научной конференции. - Тольятти, 2004.Ц
35. Пивнева, С.В. Регрессионный анализ как математический метод оптимизации обучения / С.В. Пивнева // Управление качеством подготовки специалистов на основе профессиограмм. Сборник докладов Всероссийской научно-практической конференции по профессиографическому проектированию образования и образовательных услуг. - Москва-Тольятти, 2004.Ц
36. Пивнева, С.В. Математическое определение устойчивости динамической системы/ С.В. Пивнева // Системный анализ в проектировании и управлении. Труды IX Международной научно-практической конференции. Санкт-Петербургский государственный политехнический университет. - Санкт-Петербург,2005. Ц
37. Пивнева, С.В. Математическое моделирование процесса обучения / С.В. Пивнева // Проблемы университетского образования: содержание и технологии. Труды II Всероссийской научно-методической конференции. Тольяттинский государственный университет. - Тольятти, 2005. Ц
38. Пивнева, С.В. Информационная динамическая модель обучения / С.В. Пивнева // Многопрофильное профессиональное образование. Сборник научно-методических работ. Российская академия естественных наук, Тольяттинский государственный университет. - Тольятти, 2007. Ц
39. Пивнева, С.В. Флуктуация параметров при математическом моделировании динамических систем / С.В. Пивнева // Математика. Образование. Культура (к 85-летию со дня рождения В.И. Крупича). III Международная научная конференция, 17-25 апреля 2007г., часть 4. Тольятти, 2007г. Ц
40. Егоров, А.Г. Организация рабочего процесса в камерах сгорания реактивных двигателей на псевдожидком топливе / Егоров А.Г., С.В. Пивнева, А.Н. Попов // Актуальные проблемы Российской космонавтики. Труды XXXII академических чтений по космонавтике. 29 января - 1 февраля 2008г. - Москва, 2008.
41. Панин, А.Г., Прогнозирование временных рядов на основе системы эвристических правил / А.Г. Панин, С.В. Пивнева //Технологии искусственного интеллекта в Экономике-2008, XIV научно-практическая конференция. РАН - Научно-технологический парк Дубна, 2008г.
42. Пивнева, С.В. Новые аспекты моделирования принятия решений в многокритериальных задачах / С.В. Пивнева // Проведение научных исследований в области машиностроения. Всероссийская научно-техническая конференция, 27-28 ноября 2009г. Часть 3. Тольятти- 2009
43. Мельников, Б.Ф. Мультиэвристический подход к задачам дискретной оптимизации/ Б.Ф. Мельников, С.В. Пивнева // Методы и средства обработки информации. Третья Всероссийская научно конференция, ВМК МГУ 6-8 октября 2009г., Москва - 2009
44. Мельников, Б.Ф. Применение мультиэвристического подход в задаче вершинной минимизации недетерминированных конечных автоматов/ Б.Ф. Мельников, С.В. Пивнева, А.В. Цыганов // Нейроинформатика, ее приложения и анализ данных. XVII Всероссийский семинар, ИВМ СО РАН 2-4 октября 2009г., Красноярск - 2009
45. Пивнева, С.В. Математическое моделирование социальных процессов/ С.В. Пивнева, Ю.Ф. Кустов // Актуальные проблемы непрерывного профессионального образования: сборник научных трудов. - Тольятти: ТГУ, 2010г
46. Пивнева, С.В. Новые аспекты применения информационных технологий в управлении обучением/ С.В. Пивнева //Математические методы и информационные технологии в экономике, социологии и образовании: сборник статей XXVI Международной научно-технической конференции. - Пенза: Приволжский Дом знаний, 2010. -232с. ISBN 978-5-8356-1087-7
47. Пивнева, С.В. Моделирование и реализация адаптивной обучающей системы/ С.В. Пивнева, С.С. Сытник // Современные информационные технологии и ИТ-образование: труды VI Международной научно-практической конференции. ВМК МГУ имени М.В. Ломоносова - Москва, 2011г.
48. Пивнева, С.В. Подход к репрезентативности входных данных для случайной генерации дизъюнктивных нормальных форм / С.В. Пивнева, М.А. Трифонов // Физико-математическое моделирование систем: VIII Международный семинар (ФММС-8) - Воронеж, 2011г.

---

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

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

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

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

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

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

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

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

9 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), pp. 1138Ц1162.

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

12 Сигал И., Иванова А. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмыю. - М.: ФИЗМАТЛИТ, 2003.

13 Там же.

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

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

16 Эти определения приведены в:

Мельников, Б.Ф. Построение автомата COM на основе базисного автомата / Б.Ф. Мельников, М.А. Зубова // Вектор науки Тольяттинского государственного университета. - Тольятти, 2010. - № 4 (14). - С. 30Ц32;

а до того частично в:

Melnikov, B. Extended nondeterministic finite automata / B. Melnikov // Fundamenta Informaticae, Vol.104, No.3 (2010). - P. 255Ц265.

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

18 Melnikov, B. Once more on the edge-minimization of nondeterministic finite automata / B. Melnikov // Fundamenta Informaticae, Vol.104, No.3 (2010). - P. 267Ц283.

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

20 Rosenbrock, H. H. (1960), "An automatic method for finding the greatest or least value of a function", The Computer Journal Т. 3: 175-184.

21 Мельников Б. Программирование недетерминированных игр. - Программирование (РАН), 2001, № 5, 63-80.

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

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

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

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

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

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

28Все приведённые определения согласованы с:

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

Melnikov B.:аOnce more on the edge-minimization of nondeterministic finite automata and the connected problems // Fundamenta Informaticae, 2010. - 104:3, P.267-283.

Авторефераты по всем темам  >>  Авторефераты по техническим специальностям