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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

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

КУШЕРБАЕВА Виктория Тимуровна

ТЕОРЕТИЧЕСКОЕ И СТАТИСТИЧЕСКОЕ ИССЛЕДОВАНИЕ МЕТОДОВ ПРИНЯТИЯ РЕШЕНИЙ С ИСПОЛЬЗОВАНИЕМ АЛГОРИТМА СЛУЧАЙНОГО ПОИСКА

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

программ

АВТОРЕФЕРАТ

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

-6 ОПТ 2011

Санкт-Петербург - 2011

55328

Работа выполнена на кафедре статистического моделирования ыатематико-механического факультета Санкт-Петербургского государственного университета.

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

профессор СУШКОВ Юрий Акимович

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

профессор ГРАНИЧИН Олег Николаевич (Санкт-Петербургский государственный университет)

кандидат технических наук, доцент АНКУДИНОВ Иван Георгиевич (Северо-Западный государственный заочный технический университет)

Ведущая организация: Санкт-Петербургский государственный

электротехнический университет «ЛЭТИ»

Защита состоится « » 2011 г. в ^ЗРчасов на заседа-

нии совета Д.212.232.51 по защите докторских и кандидатских диссертаций при Санкт-Петербургском государственном университете по адресу: 198504, Санкт-Петербург, Петергоф, Университетский пр., 28, математико-механиче-ский факультет, ауд. 405.

С диссертацией можно ознакомиться в Научной библиотеке им. М. Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб., 7/9.

Автореферат разослан «_[2_» 2011 г.

Ученый секретарь диссертационного совета доктор физико-математических наук, доцент

Кривулин Н. К.

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

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

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

Для решения подобного рода задач оптимизации широко применяются различные методы, в частности, рекуррентные алгоритмы стохастической аппроксимации, появившиеся в работах X. Роббинса и С. Монро, Дж. Кифера и Дж. Вольфовица и развитые в работах Б. Т. Поляка, Я. 3. Цыпкина, А. Б. Цы-бакова, О. Н. Граничина и др.; метод отжига: Н. К. Метрополис, С. С. Кирк-патрик; случайный поиск: Ю. А. Сушков, Л. А Растригин, С. М. Ермаков, А. А. Жиглявский, А. Г. Жилипскас; эволюционные алгоритмы: Дж. X. Хол-ланд и др.

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

Отдельные аспекты подобного рода алгоритмов могут быть изучены как теоретически (например, в работах А. А. Жиглявского, С. С. Киркпатри-ка, С. Д. Гелатта, М. П. Веччи, А. С. Тихомирова получены общие верхние оценки параметров алгоритмов), так и статистически, с помощью тестовых

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

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

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

В процессе подготовки принятия решения методом анализа иерархий возникает множество проблем, связанных со спецификой конкретной задачи и наличием «человеческого фактора». При этом многие исследователи отмечали недостаточную математическую обоснованность различных аспектов метода (В. Бэлтон и Т. Гиар, Т. Стюарт, Р. Д. Холдер и др.). В частности, актуальной является проблема выбора и обоснованности шкалы, а также проблема универсальности шкалы для некоторого класса задач. В работах П. Жи, Р. Жиапга, Ю. Донга, М. Биена, С. И. Гасса, М. Бернаскони и др. проводится сравнение альтернативных шкал, предложенных Д. Ма и К. Зен-гом, Ф. Ж. Доддом, X. А. Донеганом и Т. Б. М. МакМастером, Ф. А. Лутсма, А. А. Сало и Р. П. Хамалайненом, со шкалой Т. Саати. Большинство используемых шкал основано на предположении о мультипликативной природе различий альтернатив. Все рассмотренные у этих авторов шкалы удовлетворяют условию обратной симметричности, однако, как показывается в диссертации,

выполнение этого условия не всегда даст наилучшие результаты.

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

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

1. Статистическое исследование алгоритма СП и его модификации. Выявление универсальных значений параметров алгоритма как внутри отдельных трёх классов тестовых функций, так и для объединения этих классов. Разработка и обоснование методики выбора параметров алгоритма СП с использованием МАИ.

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

3. Нахождение рациональной шкалы МАИ на основе оптимизационной модели и её обоснование с помощью статистического эксперимента.

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

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

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

2. Асимптотические свойства параметров шкал МАИ. Связь между относительными приоритетами сравниваемых объектов, видом шкалы и её параметрами.

3. Рациональная шкала МАИ, найденная с помощью алгоритма СП.

4. Комплекс программ для анализа и решения задач глобальной и многокритериальной оптимизации.

Научная новизна. Все результаты, выносимые на защиту, являются новыми.

Теоретическая и практическая ценность. В работе исследуется шкала МАИ, основанная на логистическом уравнении, получены асимптотические свойства шкал МАИ, введены критерии, по которым найдена рациональная шкала. На основе статистического исследования алгоритма СП выявлены универсальные значения параметров алгоритма для трёх классов тестовых функций.

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

Апробация работы. Основные результаты диссертации докладывались и обсуждались на семинаре кафедры статистического моделирования матема-тико-механического факультета СПбГУ, а также на международных конференциях: XIX Международная Интернет-ориентированная конференция молодых ученых и студентов по проблемам машиноведения (Москва, 2007, доклад был удостоен почётного диплома за наиболее интересное научное сообщение); XIV Всероссийская школа-коллоквиум по стохастическим методам и VIII Всероссийский симпозиум по прикладной и промышленной математике (Сочи-Адлер, 2007); 5th Spring Young Researchers Colloquium on

Databases and Information Systems (SYRCoDIS, Санкт-Петербург, 2008); 19th European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning (ESANN, Брюгге, Бельгия, 2011); llth International Symposium on the AHP (ISAHP, Сорренто, Италия, 2011).

Публикации. Материалы диссертации опубликованы в работах [1-8]. Из них работы [1, 2] — в списке журналов, рекомендованных ВАК.

В работах [1-4], написанных в соавторстве с Ю. А. Сушковьш, автору диссертации принадлежит реализация задач, численные результаты, соавтору — общая постановка задач. В работе [5] автору диссертации принадлежит постановка задачи применения алгоритма СП к задаче кластеризации в био-ннформатике, соавтору — общая концепция, описание области исследования; в работе [6] автору диссертации принадлежит реализация задачи и численные результаты, соавторам — постановка задачи и верификация результатов. В работе [7] автору диссертации принадлежит исследование шкал МАИ, Г. С. Та-мазяну — исследование мер согласованности информации, Ю. А. Сушкову — постановка задачи и верификация результатов. В работе [8] автору диссертации принадлежит разработка общей концепции, представление иерархии, интерфейс программы, работа со шкалами и пр., соавторам — меры согласованности информации, верификация результатов и пр.

Результаты диссертации были частично использованы в работе по гранту РФФИ 07-07-00268-а [5], а также в проектах компании ООО «Сименс» [6] и компании «Finnlamclli Eesti».

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

Содержание работы

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

ЖС1ШЯ.

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

Пусть F — ограниченная снизу целевая функция, заданная на множестве X. Как правило, множество X имеет довольно сложную структуру и задается совокупностью равенств и неравенств. Будем считать, что X = [0, l]n, а все ограничения на множество X учтены при построении целевой функции, например, с помощью штрафных функций. Под оптимумом функции на X будем понимать её глобальный минимум на этом множестве. Задача имеет следующий вид:

F(x) —> min . ze[o,i]n

Предполагается, что решение х* = arg min F единственно.

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

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

Параметрами СП, которые может варьировать пользователь, являются: число шагов алгоритма nstep, точность поиска минимума е, параметр крутизны логистической кривой /г и параметр Vo, задающий её асимптоту, а также другие параметры, позволяющие задавать соотношение «локальных» и «глобальных» шагов к их общему количеству и тем самым определять общее поведение СП.

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

В разделах 1.4-1.6 проводится статистическое исследование сходимости алгоритма СП на множестве тестовых функций, описанных в приложении,

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

Лемма 1. Для того, чтобы в логистическом законе сужения перспективной области СП ширина перспективного интервала за п5(ер шагов стала равной 2дерз = £, параметры Уо, ¡1 должны иметь следующий вид:

>-и — — .1

^-е*1 -)-1

1>=':((Н(Н)-

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

В разделе 1.7 находится наиболее рациональный закон сужения перспективной области поиска. Критерием эффективности работы алгоритма является вероятность нахождения минимума с фиксированной точностью и за фиксированное число шагов. Решением является кусочно-линейная функция, задающая закон изменения перспективной области. Проведённое исследование подтверждает использование логистического закона сужения перспективной области как наиболее рационального. Результатом применения логистического закона является повышение вероятности нахождения глобального минимума с заданной точностью в среднем на 1.5% для унимодальных функций, на 5% для многоэкстремальных функций, на 10% для овражных функций в сравнении с показательным законом.

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

Использованные при исследовании случайного поиска тестовые функции

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

Результаты первой главы опубликованы в работах [1, 3-6].

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

Пусть X = {х\,... ,хп} — набор объектов (альтернатив), которые оцениваются набором критериев (подкритериев). Задача оптимизации, решаемая с помощью МАИ, представляется лицом, принимающим решение (ЛПР) в виде особой структуры — иерархии: на низшем уровне располагаются объекты (решения), которые необходимо ранжировать по предпочтениям ЛПР, наивысший уровень состоит из главного критерия (цели), в качестве которого выступает ЛПР, на промежуточных уровнях задаются подкритерии (подцели). Задача принятия решения здесь сводится к задаче ранжирования объектов по степени их предпочтительности, с учётом главной цели и подцелей.

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

К = {«равная важность», «слабое превосходство», «сильное превосходство» и т. д.}. Для сравнения двух объектов относительно заданного критерия (под-критерия) ЛПР вводится бинарное метризованное отношение предпочтения на X х X, в соответствии с которым для любых = 1 ..п паре (а^х,) е X х X присваивается некоторое значение из К. Поставим в соответствие каждому элементу из К целые числа А следующим образом: 1) 0 — эквивалентность объектов, 2) положительное целое число — первый объект в паре превосходит второй, 3) отрицательное — второй объект в паре превосходит первый, 4) чем больше по модулю целое число, тем больше степень превосходства одного объекта над другим.

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

р(-А) = 1/<р(А).

Таблица 1. Различные шкалы, применяемые р методе анализа иерархий.

Название шкалы Функция шкалы Параметры

Саати ЫА) = (1 + |АЫ^Л х$ — масштаб

Брука <£я(А) = Сц + \Хц сц — центр, Хв — масштаб

Логистическая Viog(A) = 2/(1 + ехр(-дЛ)) /1 — крутизна

Ma-Zheng VMz(A) = (9/(9-|A|))si^ -

Donegan-Dodd-McMaster ¥>Д(А)= (cxp(arth7j§T))b,SnA Я — диапазон, Я = 1 + б/л/3, Я = 1 + 14/л/З

Lootsma VlW = сЛ с — степенной параметр с = с = 2

Salo-Hamalainen я = 0.05, з = 1/17

В разд. 2.1-2.2 описываются основные понятия МАИ, шкалы МАИ и их недостатки. В разд. 2.3 проводится теоретическое исследование шкал МАИ, выявляются асимптотические свойства параметров шкал, которые формулируются в виде теоремы 1. Полученные результаты устанавливают связь между относительными приоритетами сравниваемых объектов (весами), видом шкалы и её параметрами.

Теорема 1. Пусть А = {lyl^i ~ матрица попарных сравнений объектов, где a,ij = <p(\ij), п — количество объектов, w = (wi,..., wn) — итоговый вектор относительных приоритетов объектов в методе собственного вектора. Для шкал из табл. 1 выполняются следующие соотношения. Для шкалы Брука:

1) для любых св,хв таких, что св/хв = const, вектор w остаётся неизменным;

2) lim^^ooWi = 1/п прн фиксированном хв, Vi = l..n;

3) limX/J^oWj = 1/п при фиксированном сд, Vi = l..n. Для шкалы Саати:

1) Шп15_оо И^ = <

1 /к, для объектов с максимальным весом, щ — \ где А; — количество таких объектов;

О, для остальных объектов.

2) Нт^-^о^г = 1/п, Уг = 1 ..п.

Для логистической шкалы:

1) при ц —> оо компоненты т будут стремиться к некоторым предельным значениям.

2) Нт^о^« = 1/п, Уг = 1 ..п.

Для шкалы Lootsma: при с —> оо вектор ш ведёт себя точно так же, как в случае шкалы Саати.

Для шкалы Donegan-Dodd-McMaster. при Н —> оо компоненты и> будут стремиться к 1/п.

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

Доказательство теоремы 1 приведено в разделе 2.3. В разделе 2.4 проводятся два статистических эксперимента. В первом эксперименте фиксируется исходное упорядочение п оцениваемых объектов: Х\ >- Х2 >- ■ ■ ■ >- хп, оценки Ау — независимые реализации случайной величины, имеющей равномерное распределение на Л = —10 : 10, где г= 1..п, матрица попарных сравнений имеет вид: А = = {</?(Ау +£у)}у=1,

где <р — функция шкалы, £у — ошибка, имеющая равномерное распределение на {0, ±1}. Применив метод собственного вектора, получим некоторое итоговое ранжирование объектов но значениям весов. В качестве критерия

с

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

Во втором эксперименте критерием оценки качества шкалы была выбрана вероятность совпадения первых к мест объектов, к = 1..п, в итоговом

ранжировании с исходным ранжированием при разных значениях параметров шкалы. В результате было получено: наибольшую вероятность совпадения полученного ранжирования с исходным имеет логистическая шкала, затем шкала Саати и, наконец, шкала Брука. Из шкал Lootsma, Ma-Zheng, Salo-Hamalaincn, Donegan-Dodd-McMaster наиболее устойчивой шкалой по рассмотренному критерию является шкала Salo-Hamalaincn. Однако в сравнении со шкалами Саати, Брука и логистической эта шкала им также уступает.

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

Результаты второй главы опубликованы в работах [2, 7].

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

Пусть имеется некоторая функция F, требуется найти ее глобальный минимум в заданной области. Используя результаты, полученные в главе 1 для параметров СП, строится иерархия: альтернативами выступают значения параметров алгоритма, которые требуется выбрать, нодкритериями являются классы функций: унимодальные, многоэкстремальные, овражные. Целью задачи принятия решений с помощью МАИ является выбор значений параметров алгоритма СП для оптимизации исходной функции F. Таким образом, ЛПР, отдав предпочтение тому или иному классу функций, получает соответствующие значения параметров алгоритма СП для каждой конкретной задачи оптимизации.

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

Пусть имеются объекты х\,... ,хп, оценки A,j — независимые реализации случайной величины, имеющей равномерное распределение на Л, i,j = l..n. Добавим к этим оценкам некоторую ошибку, имеющую равномерное распределение на подмножестве Л. Найдём новую шкалу, задаваемую функцией tp, и назовём оптимальной или рациональной, если ip удовлетворяет условиям:

k E"=i D(wi) тЧ>;

#>(А) > 0, <р'(\) > 0; ^(А) + ^(-А)=2^(0),

где D(w,) - дисперсия объекта Х{, г = 1 ..п.

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

В четвёртой главе описывается комплекс программ, разработанный для проведения вычислительных экспериментов в главах 1-3. Программы написаны на языках С++, Matlab, реализуют исследуемые алгоритмы и позволяют отслеживать зависимости между параметрами методов и получаемыми результатами. Помимо этого реализована диалоговая система поддержки принятия решений МАИМенеджер (AHPManager), написанная на языке С# в среде Microsoft Visual Studio 2008 с использованием DLL (динамически подключаемых библиотек), а также в главе 2 представлена программа для практической задачи принятия решения. Обе программы обеспечивают диалог с конечным пользователем - ЛПР.

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

грамм, создания удобного отчёта по результатам работы, получения подробной справочной информации по работе с программой и применению МАИ.

Для корректной работы программы необходимо наличие среды .NET Framework 3.5 или выше.

Результаты четвертой главы опубликованы в работе [8].

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

Список публикаций автора по теме диссертации Статьи в журналах, рекомендованных ВАК:

1. Кушербаева В. Т., Сушков Ю. А. Оптимизации и выбор режима случайного поиска на базе методов принятия решений // Обозрение прикладной и промышленной математики. 2008. Т. 15. Москва: Редакция «ОПиПМ». С. 92-92.

2. Кушербаева В. Т., Сушков 10. А. Шкалы и их свойства в методе анализа иерархий // Известия Кабардино-Балкарского центра РАН. 2010. Т. 5. С. 15-23.

Остальные публикации:

3. Кушербаева В. Т., Сушков Ю. А. Статистическое исследование случайного поиска // Стохастическая оптимизация в информатике / Под ред. О. Н. Граничина. 2007. Т. 3. С. 21-36.

4. Кушербаева В. Т., Сушков Ю. А. Оптимизация и выбор параметров случайного поиска на базе методов принятия решений // Сборник XIX Международной Интернет-ориентированной конференции молодых ученых и студентов по проблемам машиноведения (МИКМУС). 2007. С. 61-61.

5. Kusherbaeva V., Vyahhi N. Stochastic Approach to Binary Matrix Partitioning for Phylogenetic Networks // Proc. of the Fifth Spring Young Researchers

Colloquium on Databases and Information Systems (SYRCoDIS). 2008. Vol. B. Pp. 24-27.

6. Zimmermann H. G., Minin A., Kusherbaeva V. Comparison of the Complex Valued and Real Valued Neural Networks Trained with Gradient Descent and Random Search Algorithms // Proc. of the 19th European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning. 2011. Pp. 185-192.

7. Kusherbaeva V., Sushkov Yu., Tamazyan G. Comparative study of scales and consistency measures in the AHP // Online proc. of the 11th International Symposium on the AHP. 2011. Pp. 1-6.

8. Kusherbaeva V., Sushkov Yu., Tamazyan G. AHPManager — a decision making support system based on the AHP // Online proc. of the 11th International Symposium on the AHP. 2011. Pp. 1-6.

Подписано в печать 03.09.11 Формат 60x847)6 Цифровая Печ. л. 1.0 Уч.-изд. л. 1.0 Тираж 100 Заказ 06/09 печать

Отпечатано в типографии «Фалкон Принт» (197101, г. Санкт-Петербург, ул. Большая Пушкарская, д. 54, офис 8)

Введение

Глава 1. Случайный поиск.

1.1. Постановка задачи поиска минимума функции.

1.2. Описание алгоритма случайного поиска

1.3. Использование логистической кривой в алгоритме случайного поиска.

1.4. Оптимальное значение параметра логистической кривой для трёх классов функций.

1.5. Сравнение логистического и показательного законов.

1.6. Исследование алгоритма СП при различных параметрах

1.7. Нахождение наиболее эффективного закона сужения перспективной области алгоритма СП.

Глава 2. Исследование и обоснование шкал и их параметров в методе анализа иерархий.

2.1. Основные понятия метода анализа иерархий (МАИ).

2.2. Шкалы в методе анализа иерархий.

2.3. Теоретическое исследование шкал.

2.4. Статистическое исследование шкал.

2.5. Примеры.

Глава 3. Совместноеиспользованиеслунайного-поиска-и-.мето^да анализа иерархий.

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

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

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

4.1. Общая характеристика.

4.2. Описание GUI.

4.3. Результаты разработки.

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

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

Для решения подобного рода задач оптимизации широко применяются различные методы, в частности; рекуррентные алгоритмы стохастической аппроксимации, описанные в работах X. Роббинса и С. Монро [70], Дж. Кифера и Дж. Вольфовица [55], и развитые в работах Б. Т. Поляка, Я. 3. Цыпкина, А. Б. Цыбакова [24, 25], М. Б. Невельсона и Р. 3. Хасьминского [23], В. Н. Фомина, А. Л. Фрадкова и В. А. Якубовича [32], О. Н. Граничина [11], Дж. Спал-ла-[78, 79]; метод отжига: Н. К. Метрополис [63], С. С. Киркпатрик [56]; случайный поиск: Ю. А. Сушков [28, 29], Л. А Растригин [26], С. М. Ермаков [12], А. А. Жиглявский [13], А. Г. Жилинскас [15]; эволюционные алгоритмы: Дж. X. Холланд [49] и др.

Основа рассматриваемого в диссертации алгоритма глобальной оптимизации была заложена в работе Ю. А. Сушкова [28]; позже появились его модификации в работах А. Ш. Абакарова и Ю. А. Сушкова [1, 2], где для известных тестовых функций было исследовано поведение алгоритма и показано, что для некоторых значений параметров поиска алгоритм даёт приемлемые результаты. Однако оставались »нерешёнными следующие проблемы метода: недостаточная обоснованность выбора значений параметров алгоритма при решении различных задач, а также проблема выбора в некотором смысле универсальных значений.

Отдельные аспекты подобного рода алгоритмов изучались как теоретически (например, в работах А. А. Жиглявского [13], С. С. Киркпатрика, С. Д. Ге-латта, М. П. Веччи [56], А. С. Тихомирова [31, 81] получены общие верхние оценки параметров алгоритмов), так и статистически с помощью тестовых функций, предназначенных для оценки эффективности работы алгоритмов оптимизации (в работах В. В. Захарова [16], А. Ш. Абакарова, Ю. А. Сушкова [1] и др.). В,свою очередь, тестовые функции делятся на классы в зависимости от своих свойств и могут соответствовать определённым задачам оптимизации, возникающим на практике. Поскольку на практике полученные в теории оценки параметров методов оказываются завышенными, в этой работе основное внимание уделяется статистическому исследованию алгоритма случайного поиска с целью выявления закономерностей в поведении алгоритма в зависимости от вида функции, её сложности и параметров алгоритма.

АлЕоритм-слунайного-поиска-[28]-принадлежит-к-семейству-адаптивныхметодов и характеризуется тем, что в процессе работы, путём уменьшения дисперсии распределения точек определённым образом, алгоритм получает информацию о целевой функции и использует её для увеличения вероятности сходимости к оптимуму. При этом используется понятие «перспективной области» — области, в которой наличие минимума, по нашим предположениям, наиболее вероятно. Рассматриваются различные законы сужения этой области. При решении практических задач актуальной является проблема выявления наилучших значений параметров алгоритма.

В случае, если решаемая задача принятия решения не может быть представлена с использованием количественных характеристик объетов, то используются методы, оперирующие качественными характеристиками рассматриваемых альтернатив. Одним из наиболее распространенных методов подобного рода является метод анализа иерархий (МАИ), разработанный Б. Н. Бруком и В. Н. Бурковым [7], а также Т. Л. Саати [71, 72]. Ключевой особенностью МАИ является оперирование качественными суждениями о парах сравниваемых объектов, для чего используется понятие шкалы [10] — численного представления качественных суждений о сравниваемых объектах. Для обработки результатов попарных сравнений основным, хотя и не единственным методом, является метод собственного вектора, предложенный,К. Бержем [5]. Также используется метод геометрических средних, предложенный Г. Кро-уфордом и С. Вильямсом [37], исследованный в работах Дж. Барзилая [33], Н. Хованова [50] и др.

В процессе подготовки принятия решения методом анализа иерархий возникает множество проблем, связанных со спецификой конкретной задачи и наличием «человеческого фактора». При этом многие исследователи отмечали недостаточную математическую обоснованность различных аспектов метода: В. Бэлтон и Т. Гиар [34], Т. Стюарт [80], П. Жи, Р. Жианг [52], .Л.Уоррен[82],^.Д.^Холдер447.,^8^^ альной является проблема выбора и обоснованности шкалы, а также проблема универсальности шкалы для некоторого класса задач. В работах П. Жи, Р. Жианга [52], Ю. Донга [40], М. Биена [36], С. И. Гасса [43], М. Бернаскони, С. Чоират и Р. Сери [35] и др. проводится сравнение альтернативных шкал, предложенных Д. Ма и К. Зенгом [62], Ф. Ж. Доддом, X. А. Донеганом и Т. Б. М. МакМастером [38], Ф. А. Лутсма [60, 61], А. А. Сало и Р. П. Хама-лайненом [77], со шкалой Т. Саати [71].

В работах Т. Саати [27], П. Жи, Р. Жианг [52], Ю. Донга [40], А. Иши-зака и др. [51] большинство используемых шкал основано на предположении о мультипликативной природе различий альтернатив. Все рассмотренные у этих авторов шкалы удовлетворяют условию обратной симметричности, однако, как будет показано в диссертации, выполнение этого условия не всегда даёт наилучшие результаты.

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

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

1. Статистическое исследование алгоритма СП и его модификации. Выявление универсальных значений параметров алгоритма как внутри отдельных трёх классов тестовых функций, так и для объединения этих классов. Разработка и обоснование методики выбора параметров алгоритма СП с использованием МАИ.

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

3. Нахождение рациональной шкалы МАИ на основе оптимизационной модели и её обоснование с помощью статистического эксперимента.

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

Теоретическая и практическая ценность. В работе исследуется шкала МАИ, основанная на логистическом- уравнении, получены асимптотические свойства шкал МАИ, введены критерии, по которым найдена рациональная шкала. На основе статистического исследования алгоритма СП' выявлены универсальные значения параметров алгоритма для трёх классов тестовых функций.

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

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

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

2. Асимптотические свойства параметров шкал МАИ. Связь между относительными приоритетами сравниваемых объектов, видом шкалы и её параметрами.

3. Рациональная шкала МАИ, найденная с помощью алгоритма СП.

4. Комплекс программ для анализа и решения задач глобальной и многокритериальной оптимизации.

Научная новизна. Все результаты, выносимые на защиту, являются новыми.

Апробация работы. Основные результаты диссертации докладывались и обсуждались на семинаре кафедры статистического моделирования ълагге-матико-механического факультета СПбГУ, а также на международных: конференциях:

• XIX Международная Интернет-ориентированная конференция молодых ученых и студентов по проблемам машиноведения, Москва, 200Т, доклад был удостоен почётного диплома за наиболее интересное научное сообщение.

• XIV Всероссийская школа-коллоквиум по стохастическим методам и VIII Всероссийский симпозиум по прикладной и промышленной математике, Сочи-Адлер, 2007.

• 5th Spring Young Researchers Colloquium on Databases and Information Systems (SYRCoDIS), Санкт-Петербург, 2008.

• 19th European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning (ESANN), Брюгге, Бельгия, 2011.

• 11th International Symposium on the AHP (ISAHP), Сорренто, Италия, 2011.

Публикации. Материалы диссертации опубликованы в работах [17—20, 57-59, 83]. Из них работы [19, 20] — в списке журналов, рекомендованных ВАК.

В работах [17-20], написанных в соавторстве с Ю. А. Сушковым, автору диссертации принадлежит реализация задач, численные результаты, соавтору — общая постановка задач. В работе [59] автору диссертации принадлежит постановка задачи применения алгоритма СП к задаче кластеризации в биоинформатике, соавтору — общая концепция, описание области исследования; в работе [83] автору диссертации принадлежит реализация задачи и численные результаты, соавторам — постановка задачи и верификация результатов. В работе [58] автору диссертации принадлежит исследование шкал МАИ, Г. С. Тамазяну — исследование мер согласованности информации, Ю. А. Сушкову — постановка задачи и верификация результатов. В работе [57] автору диссертации принадлежит разработка общей концепции, представление иерархии, интерфейс программы, работа со шкалами и пр., соавторам — меры согласованности информации, верификация результатов и пр.

Результаты диссертации были частично использованы в работе по гранту РФФИ. 07-07-00268-а [59], а также в проектах компании ООО «Сименс» [83] и компании «Ртп1атеШ Ееэ1л».

Структура и объем диссертации. Работа состоит из четырёх глав.

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

Во второй главе работе исследуется проблема обоснованности шкал в МАИ: шкалы Б. Брука [7], шкалы Т. Саати [71], шкалы Д. Ма и К. Зенга [62], X. Донегана, Ф. Додда и Т. МакМастера [38, 39], Ф. Лутсма [60], А. Сало и Р. Хамалайнена [77]; а также логистической шкалы [21], [58]. Вводятся параметризованные варианты шкал и исследуются связи- между результатами МАИ И' значениями параметров шкал, как теоретически, так и статистически. В конце главы приводятся примеры использования МАИ для решения практических задач.

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

В четвёртой главе результаты диссертации находят своё отражение в программе МАИМенеджер (AHPManager), реализованной в рамках работы. В отличие от прочих программных реализаций МАИ (Expert Choice, lOOOMinds [45], MakeltRational, MPRIORITY 1.0 [3], T-Choice 1.0 [4] и др.), при использовании МАИМенеджер с помощью диалога пользователь полностью отделён от математической стороны МАИ. Также к отличительным особенностям программы можно отнести возможность выбора шкалы и её параметров.

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

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

Основные обозначения и сокращения:

R — множество действительных чисел;

Z — множество целых чисел;

N — множество натуральных чисел;

1 .п — множество целых чисел от 1 до п включительно; X —> А — отображение / множества X в множество А

А х В — декартово произведение множеств А и В; — евклидова норма в Rn; def

А = В — А равно В по определению; i G а : b : с — i принимает значения от а до с с шагом 6;

ЛПР — лицо, принимающее решение;

СП — случайный поиск;

МАИ — метод анализа иерархий;

AHPManager — Analytic Hierarchy Process Manager.

Заключение

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

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

2. Предложена методика выбора параметров алгоритма СП с использованием МАИ.

3. Найден наиболее эффективный с точки зрения выбранных критериев закон сужения перспективной области СП.

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

5. Предложены рекомендации по выбору значений параметров МАИ для решения практических задач.

6. Найдена рациональная шкала МАИ.

7. Разработан комплекс программ для анализа и решения задач глобальной и многокритериальной оптимизации.

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

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

1. Абакаров А. Ш., Сушков Ю. А. Статистическое исследование одного алгоритма глобальной оптимизации / / Труды физического общества республики Адыгея. 2004. Т. 9. С. 8-19.

2. Абакаров А. Ш., Сушков Ю. А. Адаптация случайного поиска с использованием логистической кривой // Математические модели. Теория и приложения. 2005. Т. 6. С. 67-75.

3. Абакаров А. Ш., Сушков Ю. А. Программная система поддержки принятия рациональных решений «МРШОШТУ 1.0» // Электронный научный журнал «Исследовано в России». 2005. С. 2130-2146.

4. Абакаров А. Ш., Сушков Ю. А. Двухэтапная процедура отбора перспективных альтернатив на базе табличного метода и метода анализа иерархий // Наука и образование: электронное научно-техническое издание. 2008. Т. 7. С. 1-16.

5. Берж К. Теория графов и ее применения. -Москва: Издательство иностранной литературы, 1962. 320 с.

6. Блюмберг В. А., Глущенко В. Ф. Какое решение лучше? Метод расстановки приоритетов. -Л.: Лениздат, 1982. 195 с.

7. Брук Б. Н., Бурков В. Н. Методы экспертных оценок в задачах упорядочения объектов // Известия АН СССР. Техническая кибернетика. 1972. № 3. С. 29-39.

8. Вольтерра В. Математическая теория борьбы за существование. -Москва: Наука., 1976. 285 с.

9. Гантмахер Ф. Р. Теория матриц. -Москва: Наука, 1988. Т. 4. 549 с.

10. Гохмаи О. Г. Экспертное оценивание. -Воронеж, 1991. С. 153.

11. Граничин О. Н. Введение в методы стохастической оптимизации и оценивания. -СПб: СПбГУ, 2003. 131 с.

12. Ермаков С. М., Жиглявский А. А. О случайном поиске глобального экстремума. 1983. Т. 28. С. 129—134.

13. Жиглявский А. А. Математическая теория глобального случайного поиска. -Ленинград: ЛГУ, 1985. 292 с.

14. Жиглявский А. А., Жилинскас А. Г. Методы поиска глобального экстремума. -Москва: Наука, 1991. 248 с.

15. Жилинскас А. Г. Глобальная оптимизация. -Вильнюс: Мокслас, 1986. 165 с.

16. Захаров В. В. Многоэкстремальные тестовые функции. Случайный поиск в задачах оптимизации // Вопросы кибернетики. -Москва: Изд. научного совета по комплексной проблеме «Кибернетика» АН СССР, 1978. Т. 45. С. 110-124.

17. Кушербаева В. Т., Сушков Ю. А. Статистическое исследование случайного поиска // Стохастическая оптимизация в информатике. 2007. Т. 3. С. 21-36.

18. Кушербаева В. Т., Сушков Ю. А. Оптимизации и выбор режима случайного поиска на базе методов принятия решений // Обозрение прикладной и промышленной математики. Т. 15. -Москва: Редакция «ОПиПМ», 2008. С. 92-92.

19. Кушербаева В. Т., Сушков Ю. А. Шкалы и их свойства в методе анализа иерархий // Известия Кабардино-Балкарского центра РАН. 2010. Т. 5. С. 15-23.

20. Матвеев Д. С., Сушков Ю. А. Метод собственного вектора и логистическая кривая // Обозрение прикладной и промышленной математики. 2008. Т. 15, № 2. С. 331-332.

21. Миллер Г. Магическое число семь плюс или минус два. О некоторых пределах нашей способности перерабатывать информацию // Инженерная психология. 1964. С. 192-225.

22. Невельсон М. В., Хасьминский Р. 3. Стохастическая аппроксимация и рекуррентное оценивание. -Москва: Наука, 1972. 304 с.

23. Поляк Б. Т., Цыбаков А. Б. Оптимальные порядки точности поисковых алгоритмов стохастической аппроксимации // Проблемы передачи информации. 1990. № 2. С. 45-53.

24. Поляк Б. Т., Цыпкин Я. 3. Псевдоградиентные алгоритмся адаптации и обучения // Автоматика и телемеханика. 1973. № 3. С. 45-68.26~Растригин ЛГАГСтатистические методы поиска. -Москва: Наука, 1968. 376 с.

25. Саати Т. Принятие решений. Метод анализа иерархий. -Москва: Радио и связь, 1993. 320 с.

26. Сушков Ю. А. Метод, алгоритм и программа случайного поиска: Тех. доклад. -Ленинград: Всесоюзный научно-исследовательский институт транспортного машиностроения, 1969.

27. Сушков Ю. А. Об одном способе организации случайного поиска // Исследование операций и статистическое моделирование. Издательство Ленинградского государственного университета, 1972. Т. 1. С. 180-185.

28. Сушков Ю. А. Многокритериальность в многорежимных системах // Архитектура и программное оснащение цифровых систем. 1984. С. 71-77.

29. Тихомиров А. С. О быстрых алгоритмах случайного поиска // Вестник Новгородского государственного университета. 2006. Т. 39. С. 34-37.

30. Фомин В. Н., Фрадков А. Л., Якубович В. А. Адаптивное управление динамическими объектами. -Москва: Наука, 1981. 448 с.

31. Barzilai J. Deriving weights from pairwise comparison matrices // Journal of Operational Research Society. 1997. Vol. 48. Pp. 1226-1232.

32. Belton V., Gear T. On a Shortcoming of Saaty's Method of Analytical Hierarchies // Omega. 1983. no. 3. Pp. 228—230.

33. Bernasconi M., Choirat C., Seri R. The Analytic Hierarchy Process and the Theory of Measurement // Management Science. 2010. Vol. 56, no. 4. Pp. 699-711.

34. Beynon M. An analysis of distributions of priority values from alternative comparison scales within AHP // European Journal of Operational Research. 2002. Vol. 140, no. 1. Pp. 104-117.

35. Crawford G., Williams C. A note on the analysis of subjective judgment matrices // Journal of Mathematical Psychology. 1985. Vol. 29. Pp. 387—405.119

36. Dodd F. J., Donegan H. A., McMaster T. B. M. Scale horizons in analytic hierarchies // Multi-criteria Decision Analysis. 1995. Vol. 4. Pp. 177-188.

37. Donegan H. A., Dodd F. J., McMaster T. B. M. A new approach to AHP decision-making // Statistician. 1992. Vol. 41. Pp. 295-302.

38. Dong Y.¡ Xu Y., Li H., Dai M. A comparative study of the numerical scales and the prioritization methods in AHP // European Journal of Operational Research. 2008. Vol. 186. Pp. 229-242.

39. Gass S. I. Tournaments, transitivity and pairwise comparison matrices // Journal of the Operational Research Society. 1998. Vol. 49. Pp. 616-624.

40. Gass S. I. Model World: The Great Debate MAUT Versus AHP // Interfaces. 2005. Vol. 35, no. 4. Pp. 308-312.

41. Gass S. I., Standard S. M. Characteristics of positive reciprocal matrices in the analytic hierarchy process // Journal of the Operational Research Society. 2002. Vol. 53. Pp. 1385-1389.

42. Hansen P., Ombler F. A new method for scoring multi-attribute value models using pairwise rankings of alternatives // Journal of Multi-Criteria Decision Analysis. 2009. Vol. 15. Pp. 87-107.

43. Harker P. T., Vargas L. G. The Theory of Ratio Scale Estimation: Saaty's Analytic Hierarchy Process // Management Science. 1987. Vol. 33, no. 11. Pp. 1383-1403.

44. Holder R. D. Some Comments on the Analytic Hierarchy Process // Journal of Operational Research Society. 1990. Vol. 41, no. 11. Pp. 1073-1076.

45. Holder R. D. Response to the Response to Holder's Comments on the Analytic Hierarchy Process // Journal of the Operational Research Society. 1991. Vol. 42, no. 10. Pp. 914-918.

46. Holland J. H. Adaptation in natural and artificial systems. University of Michigan Press, 1975. 183 pp.

47. Hovanov N., Kolari J. W., Sokolov M. V. Deriving weights from general pair-wise comparison matrices // Mathematical Social Sciences. 2008. Vol. 55. Pp. 205—220.

48. Ishizaka A., BalkenBorg D., Kaplan T. Influence of aggregation and measurement scale on ranking a compromise alternative in AHP // Journal of Operational Research Society. 2011. Vol. 62, no. 4. Pp. 700-710.

49. Ji P., Jiang R. Scale transitivity in the AHP // Journal of the Operational Research Society. 2003. Vol. 54. Pp. 896-905.

50. Kendall M., Smith B. On the method of pair comparisons // Biometrika. 1940. Vol. 31. Pp. 324-345.

51. Khompatraporn C., Zabinsky Z. B., Pinter J. D. Comparative Assessment of Algorithms and Software for Global Optimization // Journal of Global Optimization. 2005. Vol. 31. Pp. 613-633.

52. Kiefer J., Wolfowitz J. Stochastic Estimation of the Maximum of a Regression Function // Annals of Mathematical Statistics. 1952. Vol. 23, no. 3. Pp. 462-466.

53. Kirkpatrick S. S., Gelatt C. D., Jr., Vecchi M. P. Optimization by Simulated Annealing // Science. 1983. Vol. 220, no. 4598. Pp. 671-680.

54. Kusherbaeva V., Sushkov Y., Tamazyan G. "AHPManager" — a decision making support system based on the AHP // Proc. of the 11th International Symposium on the AHP. 2011. Pp. 1-6.

55. Kusherbaeva V., Sushkov Y., Tamazyan G. Comparative study of scales and consistency measures in the AHP // Proc. of the 11th International Symposium on the AHP. 2011. Pp. 1-6.

56. Kusherbaeva V., Vyahhi N. Stochastic Approach to Binary Matrix Partitioning for Phylogenetic Networks // The Fifth Spring Young Researchers Colloquium on Databases and Information Systems (SYRCoDIS). Vol. B. 2008. Pp. 24-27.

57. Lootsma F. A. Scale sensitivity in the multiplicative AHP and SMART // Multi-criteria Decision Analysis. 1993. Vol. 2. Pp. 87-110.

58. Lootsma F. A. Multi-criteria decision analysis via ratio and difference judgment. Springer Netherlands, 1999. 304 pp.

59. Ma D., Zheng X. Scale Method of AHP // Proc. of the Second International Symposium on the AHP. 1991. Vol. 1. Pp. 197-202.

60. Metropolis N. C., Rosenbluth A. W., Rosenbluth M. N. et al. Equation of State Calculations by Fast Computer Machines //J. Chemical Physics. 1953.-Volr2l7noT6rP^1087-1092. ——

61. Mikhalevich M. V. Remarks on the Dyer-Saaty controversy // Cybernetics and Systems Analysis. 1994. Vol. 30, no. 1. Pp. 75-79.

62. Mishra S. K. Some new test functions for global optimization and performance ofrepulsive pARTICLE swarm method. http://mpra.ub.uni-muenchen.de/2718/l/MPRApaper2718.pdf.

63. Molga M., Smutnicki C. Test functions for optimization needs, http: / / www.zsd.ict.pwr.wroc.pl / files / docs/functions.pdf.

64. Perez J., Jimeno J. L., Mokotoff E. Another Potential Shortcoming of AHP // Sociedad de Estadistica e Investigación Operativa. 2006. Vol. 14. Pp. 99-111.

65. Pinter J. D. Global Optimization, Software, Test Problems, and Applications // Handbook of Global Optimization / Ed. by P. M. Pardalos, H. E. Romeijn. Springer, 2002. Vol. 62 of Nonconvex Optimization and its Applications. 580 pp.

66. Poyhonen M. A., Hámáláinen R. P., Salo A. A. An experiment on the Numerical Modelling of Verbal Ratio Statements // Journal of Multi-Criteria Decision Analysis. 1997. Vol. 6. Pp. 1-10.

67. Robbins H., Monro S. A stochastic approximation method // Annals of Mathematical Statistics. 1951. Vol. 22. Pp. 400-407.

68. Saaty T. L. A scaling method for priorities in hierarchical structures // Journal of Mathematical Psychology. 1977. Vol. 15. Pp. 234-281.

69. Saaty T. L. Axiomatic Foundation of the Analytic Hierarchy Process // Management Science. 1986. Vol. 32, no. 7. Pp. 841-855.

70. Saaty T. L. Response to Holder's Comments on the Analytic Hierarchy Process // Journal of Operational Research Society. 1991. Vol. 42, no. 10. Pp. 909-914.

71. Saaty T. L. Response to the Response to the Response to Holder's Comments on the Analytic Hierarchy Process // Journal of Opeational Research Society 1991. Vol. 42, no. 10. Pp. 918-924.

72. Saaty T. L. Decision-making with the AHP: Why is the principal eigenvector necessary // European Journal of Operational Research. 2003. Vol. 145. Pp. 85-91.

73. Salo A. A., Hamalainen R. P. On the measurement of preferences in the analytic hierarchy process // Multi-criteria Decision Analysis. 1997. Vol. 6. Pp. 309-319.

74. Spall J. C. Introduction to stochastic search and optimization: estimation, simulation, and control. Wiley-Interscience John Wiley & Sons., 2003. 620 pp.

75. Spall J. C., Member S. Multivariate Stochastic Approximation Using a Simultaneous Perturbation Gradient Approximation // IEEE Transactions on Automatic Control. 1992. Vol. 37. Pp. 332-341.

76. Warren L. Uncertainties in the Analytic Hierarchy Process: Technical Note DSTO-TN-0597. Edinburgh, Australia: Information Sciences Laboratory, 2004.

77. Zimmermann H. G., Minin A., Kusherbaeva V. Historical Consistent Complex Valued Recurrent Neural Network // International Conference on Artificial Neural Networks. 2011. Pp. 1-9.