Комплекс алгоритмов генерации композиций для построения систем поддержки принятия решений

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

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

В последние десятилетия получили широкое распространение прикладные программы, использующие алгоритмы генерации и селекции различных комбинаторных объектов. Важное применение комбинаторные алгоритмы находят в современной информатике, где используются методы, предполагающие осуществление направленного перебора различных математических структур (конечных графов, переключательных схем, булевых функций, опорных планов и т. п.) (см., например, работы [22,23,25,26,36,46,47,72,80,86]).

Особенно следует отметить роль комбинаторных алгоритмов перебора структур разного вида (графы, деревья, разбиения и т. п.) в методах многокритериальной оптимизации (см. [56,78,79,97]), теории принятия многокритериальных решений (см. [48,51,52,99,106,124,127]), в методах теории расписаний [41], в системах искусственного интеллекта [54], в современных интерактивных системах анализа данных [28] и т. д. (см., например, [4,46,81,84]).

Критически важными являются комбинаторные алгоритмы для работы ряда экспертных систем [84,127]. Например, одна из немногих успешно действующих экспертных систем, — система SCENARIO-AGENT, разработанная еще в 1988 году в RAND Corporation для анализа стратегических конфликтов, базируется на комбинаторной генерации возможных сценариев развития конфликта, которые затем подвергаются экспертной селекции (см. 84]). Гибкость и универсальность алгоритмов генерации и селекции различных комбинаторных объектов обеспечили их широкое применение в различных прикладных областях, начиная от экономики и военного дела (см., например, [15−18,38,79,89,91,92,115]) и кончая химией [37,87], генетикой и экологией [29−31,42,65−67,69,71,101,102].

Важным частным случаем рассматриваемых комбинаторных алгоритмов являются алгоритмы генерации и селекции так называемых композиций (упорядоченных разбиений) (*(1),., х (т)), л (1) + .+х (т) = п, натурального числа п (см. [72,73,100,120]). Такие алгоритмы генерации и селекции композиций используются в различных экспертных системах и в системах поддержки принятия решений (СППР) по распределению дискретных ресурсов по конечному числу позиций. Например, в основе широко распространенной экспертной системы BATTLE, первый прототип которой был создан в 1988 году в Naval Research Laboratory (USA NAVY), лежит перебор всех возможных распределений (упорядоченных разбиений) боевых сил и средств по целям противника с последующим отбором эффективных вариантов (см. [84]). Особенно важную роль рассматриваемые комбинаторные алгоритмы играют в СППР, ориентированных на использование нечисловой, неточной и неполной информации о весовых коэффициентах и/или вероятностей.

Эти СППР в последнее время широко применяются для синтеза сводных оценок сложных объектов разной природы, например, для построение оценок многопараметрических технических систем военного назначения и НИР, направленных на разработку таких систем [38], для сводной оценки сложных финансово-экономических объектов (коммерческих банков, страховых компаний и т. п.) [1114,17,65−57,115], для формирования рациональных вариантов инвестиционного портфеля [89,91], для оценивания экологического состояния и устойчивости геосистем [29−31], для построения непараметрических байесовских оценок распределений случайных величин [40], для выявления статистических зависимостей по наблюдениям за траекториями стохастического процесса [10] и т. д.

Комбинаторные объекты (композиции и монотонно неубывающие траектории на целочисленной решетке), используемые в вышеуказанных прикладных методах, весьма многочисленны — их число N (m, n) очень быстро растет с увеличением параметров т и п (см. [93]). Действительно, даже для умеренных значений т и п число всех возможных композиций (число всех возможных монотонных траекторий на целочисленной решетке) весьма значительно: N (5,10)=1001- N (5,20)= 10 626- N (5,40)=135 751- N (10,10)=92 378- N (10,20)= 10 015 005- N (10−30)=211 915 132- N (10,40)=2 054 455 634. Поскольку время T (m, n), требуемое для полного перебора исследуемых комбинаторных объектов, можно в первом приближении оценить сверху величиной T (m, ri)& С-т-N{m, ri), где константа С определяется типом процессора, особенностями алгоритма, операционной системой и тому подобными обстоятельствами, постольку следует ожидать драматического увеличения времени работы соответствующих методов. Поэтому, весьма актуальной является задача повышения скорости вычислений за счет распараллеливания соответствующих вычислительных процессов.

Цель и задачи диссертационной работы.

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

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

• разработать и протестировать алгоритмы генерации, селекции и оценки соответствующих комбинаторных объектов;

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

• разработать программное обеспечение, основанное на созданных алгоритмах генерации целочисленных композиций, системы поддержки принятия решений, реализуемой на ПЭВМ в виде прикладной программы АСПИД-3У, позволяющей пользователю оценивать в интерактивном режиме сложные много-параметрические объекты.

• проверить работоспособность построенной СППР АСПИД-3У на примере построения по иерархической системе исходных характеристик сводных показателей предпочтительности различных вариантов архиваторов с использованием нечисловой, неточной и неполной информации о сравнительной значимости исходных характеристик эффективности работы этих архиваторов.

Методы исследования.

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

Научная новизна.

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

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

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

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

Практическая и теоретическая ценность.

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

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

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

Реализация результатов работы.

Система поддержки принятия решений АСПИД-3У и другие программные продукты, разработанные в рамках диссертационной работы, практически использовалась при выполнении перечисленных ниже НИР, проводимых в Санкт-Петербургском институте информатики и автоматизации РАН (СПИИРАН) лабораторией вычислительных систем и проблем защиты: «Анализ, классификация и оценка уровня защищенности информационных систем», «Анализ и оценка рисков нарушения безопасности в сложных информационных системах при дефиците информации», «Разработка метрик для оценки качественных аспектов моделей программ» (2001;2003 гг.).

В лаборатории интеллектуальных систем СПИИРАН разработанные в диссертации методы обработки композиций практически использовались в НИР «Разработка программных средств оптимизации планирования комплексного БСК», выполнявшейся по договору с ФГУП «Комета» лабораторией интеллектуальных систем СПИИРАН (2002;2003 гг.).

Результаты диссертационной работы были внедрены в ГУП «Санкт-Петербургский информационно-аналитический центр» и использованы при разработке Интегрированной системы информационно-аналитического обеспечения Администрации Санкт-Петербурга (2002;2003 гг.).

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

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

Основные результаты и выводы диссертации докладывались: на заседаниях кафедры информатики математико-механического факультета СПбГУ (2001;2003 гг.) — на Международной научной конференции «Информационно-управляющие и вычислительные комплексы на основе новых технологий» (СПб., 1992 г.) — на Международном научном конгрессе «Народы СНГ накануне третьего тысячелетия" — секция «Математические методы принятия предпринимательских решений» (СПб., 1996 г.) — на Всероссийской научной конференции «Инвестиционная политика России в современных условиях" — секция «Математические методы обоснования инвестиционных и финансовых решений» (СПб., 1997 г.) — на Пятой Международной конференции «Вероятностные методы в дискретной математике». (Петрозаводск, 2002).

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

В главе 1 определяются основные виды комбинаторных объектов, связанных с понятием целочисленной композиции (упорядоченным разбиением натурального числа на фиксированное число слагаемых): нормированные композиции', монотонные пути (траектории) с закрепленными концами, проходящие через узлы конечной целочисленной решеткенормированные монотонные пути (траектории) с закрепленными концами. Описывается процедура селекции введенных комбинаторных объектов на основе использования нечисловой (ординальной), неточной (интервальной) и неполной информации. Изучается вопрос о возможном усилении системы неравенств, формализующих интервальную информацию, имеющуюся у исследователя. Вводятся различные коллективные и индивидуальные оценки комбинаторных объектов, получаемых в результате селекции (§ 1.1).

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

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

В главе 2 проводится, прежде всего, теоретическое оценивание числа N (m, n) всех возможных целочисленных композиций (упорядоченных разбиений натурального числа п на т частей). Для этого исследуется асимптотика величины N (m, n) при различных соотношениях для параметров т, п, значения которых стремятся к бесконечности. Оценивается также влияние длины цепочки неравенств, задаваемых исследователем для компонент композиции, на общее число N (m, n-I) допустимых (с точки зрения данной системы неравенств /) композиций. Помимо исследования асимптотического поведения величины N (m, n), проводятся прямые вычисления этого числа для небольших значений параметров т, п (§ 2.1). Разрабатываются три алгоритма генерации целочисленных композиций, один из которых является модификацией известного алгоритма прямой генерации композиций в лексикографическом порядке, а два других представляют собой новые разработки, в которых используется предварительное генерирование монотонных путей на целочисленной решетке, с последующим переходом к соответствующим целочисленным композициям. Для всех трех алгоритмов дается их программная реализация. Обсуждается вопрос об использовании разработанных алгоритмов для построения единой процедуры распараллеливания процесса генерации целочисленных композиций с целью реализации генерирования этих комбинаторных объектов на многопроцессорных ЭВМ (§ 2.2). Проводится теоретический сравнительный анализ программных реализаций трех разработанных алгоритмов генерации целочисленных композиций. Кроме того, эти реализованные алгоритмы тестируются на реальной ПЭВМ с наработкой статистики, позволяющей в первом приближении оценить зависимость реального времени генерации композиций от значений параметров т, п. Определяются как среднее время генерации всех N (m, n) возможных целочисленных композиций, так и среднее время генерации одной композиции при различных значениях параметров т, п и при использовании различных алгоритмов (§ 2.3).

В главе 3 анализируется общая структура разработанной нами оболочки системы поддержки принятия решений (ОСППР) АСПИД-3У, реализующей описанный в § 1.3 метод рандомизированных сводных показателей (МРСП). Реализованный на ПЭВМ ОСППР АСПИД-3\^ официально зарегистрирован Российским агентством по правовой охране программ для ЭВМ, баз данных и топологий интегральных микросхем (РосАПО). Подробно излагаются основные схемы применения оболочки СППР АСПИД-3У для оценки сложных многопараметрических объектов и для оценки вероятностей альтернатив в условиях неопределенности (§ 3.1). Рассматриваются разработанные нами для ОСППР АСПИД-3У алгоритмы обработки неточной (интервальной) и нечисловой (ординальной) информации (инн-информации) о весовых коэффициентах, определяющих сравнительную значимость отдельных показателей. В предположении, что ннн-информация представима в виде систем равенств и неравенств, разрабатывается процедура согласования получаемых систем неравенств и проверки непротиворечивости этих систем (§ 3.2). Подробно рассматривается пример использования ОСППР АСПИД-ЗУ/ для рейтингования различных вариантов важного и широко распространенного типа программного обеспечения — архиваторов, используемых для «сжатия» информации, хранимой в компьютерах и передаваемой по линиям связи. Строится иерархическая система отдельных показателей, каждый из которых оценивает архиваторы с точки зрения определенного критерия. Последовательно строятся оценки рандомизированных сводных показателей предпочтительности различных вариантов программного обеспечения (архиваторов) и исследуется влияние на эти показатели дополнителной ннн-информации, которой располагает гипотетический субъект, оценивающий общую предпочтительность архиваторов. Анализируются результаты проведенного с помощью ОСППР ЛCПИД-ЗW исследования качества (предпочтительности) существующих архиваторов (§ 3.3).

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

В Приложениях 1−5 дается система окон СППР ЛСПИД-ЗШ (Прил.1), описывается основная схема использования системы АСПИД-ЗУ/ (Прил.2), указываются исходные характеристики архиваторов, для которых строятся сводные показатели предпочтительности (Прил.З), приводится таблица значений вероятностей попарного доминирования рандомизированных весовых коэффициентов (Прил.4) и дается пример полного отчета ОСППР АСПИД-3М об одном сеансе своей работы (Прил.5).

ЗАКЛЮЧЕНИЕ

.

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

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

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

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

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

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

Разработанные алгоритмы генерации, селекции и оценки композиций реализованы на ПЭВМ в виде комплекса программ, составляющих математическое обеспечение работы СППР АСПИД-3У, основанной на методе рандомизированных сводных показателей.

Разработан комплексный демонстрационный пример использования СППР АСПИД-3\Г для оценки предпочтительности различных вариантов важного и широко распространенного типа программного обеспечения — архиваторов, используемых для «сжатия» информации, хранимой в компьютерах и передаваемой по линиям связи. Построена иерархическая система тринадцати показателей, характеризующих различные аспекты работы архиваторов.