Содержание к диссертации
Введение 3
Литература к введению 19
Глава 1. Математические модели динамики функционирования
целевого коллектива 22
Литература к главе 1 46
Глава 2. Формирование целевых коллективов методами кластер-
анализа 50
Литература к главе 2 80
Глава 3. Формирование целевого коллектива на базе стохастических
дифференциальных уравнений 85
-
Анализ явных численных методов решения стохастических дифференциальных уравнений 97 Литература к разделу 3.1 97
-
Задача идентификации параметров стохастического дифференциального уравнения. 98 Литература к разделу 3.2 112
-
Феномен логистического уравнения 114 Литература к разделу 3.3 123 Заключение 124 Приложение 125
Введение к работе
Актуальность темы.
Закономерности современного этапа научно-технической революции можно по некоторым данным (см., например. [1]) охарактеризовать следующими количественными показателями развития техники в ведущих областях машиностроения: число различных классов технических систем удваивается в среднем через каждые 10 лет; сложность изделий по числу деталей и узлов возрастает вдвое за 15 лет; объем научно-технической информации, используемой в конструкторских разработках, удваивается за 8 лет.
В авиационной технике, например, самолеты конца семидесятых годов в 5-6 раз сложнее самолетов аналогичного назначения, построенных в пятидесятых годах. За 20 лет затраты человеческого труда на проектирование и изготовление единицы массы конструкции увеличились вдвое, а продолжительность разработки нового самолета возросла с 3-4 до 8-12 лет, а иногда и более. Объем проектно-конструкторских работ предположительно будет возрастать каждые 10 лет в 10 раз [1]. По статистическим данным распределение затрат предприятия-разработчика но этапам жизненного цикла летательного аппарата выглядит следующим образом: научные исследования и проектирование - 10%; создание опытных образцов - 20%; летные испытания и доводка - 50%; серийное производство и эксплуатация - 20%.
Если бы за счет увеличения объема и повышения качества, научно-исследовательских и проектных работ удалось вдвое сократить доводочные расходы, то это уменьшило бы суммарную стоимость создания самолета на
25-30%.
Усилия по решению этой проблемы привели к увеличению числа проектировщиков с 20-30 человек, работавших в течение нескольких месяцев над проектами первых сверхзвуковых самолетов, до нескольких сот инженеров, проектирующих современные самолеты в течение нескольких лет. Практика подтверждает, что затраты человеческого труда, потребный объем вычислений и потребное время на проведение экспериментов для создания перспективного летательного аппарата возрастает по экспоненциальному закону. Это отражает тот факт, что рост сложности решения задач управления, планирования и проектирования зависит от сложности структуры решаемых задач экспоненциально. Отсюда следует актуальность выбора оптимальной структуры целевого коллектива.
Цель работы.
Анализ известных и создание новых методик выбора оптимальной структуры целевого коллектива для повышения эффективности его функционирования.
Методы исследования.
Методы кластерного и комитетного анализа, направленные на поиск групп индивидуумов, отличающихся по своим индивидуальным показателям. Моделирование динамики взаимодействия коллектива на основе клеточных автоматов с переменной структурой и стохастических дифференциальных уравнений.
Научная новизна.
Предложена методика качественного и численного анализа по выбору оптимальной структуры целевого коллектива в смысле его эффективности.
Обоснованность научных положений.
Теоретические положения и выводы диссертации сформулированы в виде утверждений и теорем, которые строго доказаны.
Практическая ценность.
Результаты работы использовались в научных исследованиях и учебном процессе МФТИ, и в рамках гранта РФФИ (№ проекта 03-01-00678). Также результаты работы могут использоваться для качественного и численного анализа выбора оптимальной структуры целевого коллектива в различных областях науки и техники.
Апробация работ.
Основные результаты работы докладывались на семинарах МФТИ, ИПУ РАН, ВЦ РАН, ИММ РАН, ИСА РАН, ЦЭМИ РАН, МГУ, а также на научных конференциях МФТИ и международных конференциях (Брест 2005).
Личный вклад.
В совместных работах [2], [3], [4], [5] автору принадлежат результаты в равных долях.
Структура и объём работ.
Диссертация состоит из введения, 3-х глав, приложения, библиографического списка и содержит .... рисунков. Общий объём работы составляет ... страниц. Библиографический список включает ... наименований.
Содержание работы.
Во введении приводится обзор различных методов решения задач определения оптимальной структуры целевого коллектива. Для описания дискретных систем используются дискретные отображения и, в частности, клеточные автоматы.
В главе 1 сначала даётся понятие клеточной сети с переменной структурой связей. Класс моделей клеточных автоматов способен демонстрировать разнообразное поведение и является сравнительно легко моделируемым (на ЭВМ) объектом. Этот класс позволяет получить качественные ха- рактеристики процессов. Клеточные автоматы могут также служить для имитационного моделирования.
В последнее время появляются более сложные конструкции клеточных автоматов. В качестве примера укажем работу Gontar V. для моделирования химической реакции типа Белоусова-Жаботинского на основе анализа размерностей и П-теоремы. Данная работа допускает обобщение на базе стохастического подобия (Северцев Н.А. [11]). Впервые понятие клеточной сети с переменной структурой связей применяется в Препринте ИПМ им. М.В, Келдыша № 34 за 1997 г: Трофимова И.Н., Митин Н.А., Потапов А.Б., Малинецкий Г.Г., «Новые модели математической психологии. Описание ансамблей с переменной структурой». В этой работе подчеркивается важность способности к изменению связей в некоторой сложившейся, самоорганизующейся системе, а также указывается на ключевые признаки, которыми должны обладать система и ее элементы для того, чтобы в полной мере описать и исследовать систему с изменяющимися связями. Такого рода модели было бы естественно использовать для представления и исследования динамики живых систем - биологических, психологических и социальных. Основным результатом, изложенным в препринте, является создание принципиально нового класса математических моделей ансамблей (многоагентных сред), модель именно этого класса (клеточные сети с переменной структурой связей) и используется в настоящей работе.
Определение. Конечным автоматом К называется совокупность пяти объектов: К = {A,SfZ,f,g},rj\e А = {а0,...,ап} - конечный список входных символов (входной алфавит); Z = {z0,...,zn} - конечный список выходных символов (выходной алфавит); S = {s0,...,sr} - множество внутренних состояний; /: SxA->S - функция перехода, отображающая множество всех упорядоченных пар {spak) в множество S, g: SxA^Z - функция выхода, отображающая множество всех упорядоченных пар (Sj,ak) в множество Z. Здесь S х А - декартово произведение множеств S и А.
Если рассматривается функциональная модель конечного автомата без учета его структуры, то такой подход называется макроподходом. Если учитывается структурная модель конечного автомата, то такой подход называется микроподходом.
Определение. (Т. Тоффоли, Н. Морголус) Клеточные автоматы являются дискретными динамическими системами, поведение которых полностью определяется в терминах локальных зависимостей. В этом смысле клеточные автоматы в информатике являются аналогом физического понятия поля. Клеточный автомат может мыслиться, как стилизованный мир. Пространство представлено равномерной сеткой, каждая ячейка которой, или клетка, содержит несколько битов данных; время идет вперед дискретными шагами, а законы мира выражаются единственным набором правил, скажем, небольшой справочной таблицы, по которой любая клетка на каждом шаге вычисляет свое новое состояние по состоянию своих близких соседей. Таким образом, законы системы являются локальными и повсюду одинаковыми.
Другими словами, клеточный автомат представляет собой некоторое дискретное пространство, на котором происходит эволюция, и набор правил, по которым эта эволюция осуществляется.
Если структура автомата не фиксирована, то такой автомат называется автоматом с переменной структурой.
Математическая модель динамики системы целевого сообщества имеет следующие свойства: сложный состав; разнообразие элементов внутри системы; динамическая устойчивость; устойчивость структуры системы при замене отдельных элементов; открытость системы; диссипативность; интеграция; память системы.
Сама постановка вопроса о математическом моделировании какого-либо объекта порождает четкий план действий. Его условно можно разбить на три этапа: модель-алгоритм-программа.
Под структурой системы понимают фиксированные отношения между элементами.
Наиболее общее определение системы дается в терминах теории множеств. Предполагается, что задано некоторое семейство объектов элементов системы {А), г el. Тогда система может быть определена как некоторое собственное подмножество декартова произведения: Sys с Y\ Д
Наиболее информативными показателями изменения динамики системы являются входной Хвх и выходной Хвых сигналы. Поэтому систему можно характеризовать как принадлежность Sys с Хвх х Хшх.
Применительно к нашей работе любая модель, которая учитывает взаимодействия индивидов, является системой тогда и только тогда, когда в любой момент времени она является сильно связанной и устойчивой к разовому (импульсному воздействию). Это утверждение не исключает возможности того, что с течением времени система может стать неустойчивой и перейти в новое состояние.
Математической моделью называется некоторое множество с заданным на нем набором отношений М = {S,R), где S - множество состояний системы, R - множество отношений.
В первой главе приводятся три нелинейных модели динамики функционирования целевого коллектива. Оптимальное решение одной из этих моделей предлагается находить с помощью клеточного автомата с переменной структурой. В широком плане, все конечные автоматы с переменной структурой представляют собой рекуррентные, дискретные алгоритмы, построенные по некоторым правилам.
Приведем описание этих моделей.
Задача А
Определить max J(P), если и = {ujk)
ДР) = СХ(П P = {Pi},r = \,..Nl, N,
В работе доказана следующая теорема.
Теорема 1.1. Решение задачи А существует.
Доказательство этой теоремы опирается на результаты работы [12] и для ее решения предложен полуявный метод Эйлера: X ah N х = {р;}> х*« = TTtF+T7^-^u^)P^ к = {kJ]>pj* = W>h»= **«-'* і + клІ! і + кл п ы
Задача В.
Определить maxM[J(P)], если u = {u.k} m^LCrfV), P = {P,}, r = \,..Nv NX
0<Мл,<1 (1.8) где последние неравенства, являются ограничениями на управления.
Доказаны следующие теоремы.
Теорема 1.2. Для задачи В справедлив стохастический принцип максимума. Доказательство следует из результатов работы [13].
Теорема 1.3. Решение задачи В существует в сильном смысле.
Теорема 1.4. Для дискретно-непрерывной задачи А справедлив принцип максимума Понтрягина.
Задача С. Определить максимум функционала системы элементов іЛр^т), где динамика элементов входящих в рассматриваемую систему имеет вид р,=(кд -ptf+ї>да>t є{л><' *h /=1/ = {1.JV}, Д>0,^>0, Kj>0tP,(0) = Pl0 (1.9) где і - номер рассматриваемого элемента, Pt- его величина, Kn/3j ,ау- соответствующие константы.
Клеточным автоматом с переменной структурой мы будем называть следующий алгоритм, представляющий собой решение задачи С: Pj^=Pj,n-кЛ»ЛА+<*ь«ЖКР«> J*k или, что-то же самое,
Р ah N где коэффициенты а.к отражают близость элементов системы, а коэффициенты к. отражают особенности элементов.
Во введении главы 2 даны краткие характеристики малых групп и кластерного анализа (КА). Отмечается, что такие основные критерии психологической общности малой группы, как сходство, общность ее индивидов (общность мотивов, целей, ценностных ориентации и социальных установок) обосновывают применение алгоритмов (КА) для решения задач формирования целевого коллектива оптимальной структуры.
В разделе 2.2 отмечено, что для проведения классификации данного множества объектов
М = {Х1,Х2,..,Хп},п>5 (2.1) математическими методами необходимо дать описание каждого объекта Хі є М, числовыми признаками, ^=(^.,,^,...,^), р>\, (2.2) (р - число признаков) задать количественную меру близости объектов г.. =r{Xi,XJ), Xt,Xj еМ и правило классификации в соответствии с выбранной мерой близости.
Обычной математической основой для классификации объектов являются функции на парах элементов {Xi,Xj), например т -расстояние, где xjs значение 5-го признака для элемента Х}, т - целое положительное число, т > 1.
Перечислены и другие меры близости: коэффициент ассоциативности, коэффициент корреляции, условные вероятности P(Xt/cot) принадлежности элемента X, к классу со,, t є {1,2,...,к}.
Далее в разделе 2.3 даны основные виды функционалов качества классификации, используемые для выбора оптимального варианта классификации в тех случаях, когда невозможно оценить вероятность ошибки классификации Ротн. Оптимальный вариант классификации соответствует экстремальному значению функционала (минимальному или максимальному).
В разделе 2.4 перечислены основные условия, гарантирующие оптимальную классификацию:
1) представление объектов в виде р -мерных векторов в (2.2) должно полно отражать главные свойства каждого класса; наличие представительных (репрезентативных) подмножеств каждого класса; объекты, относящиеся к одному классу должны быть ближе друг другу по выбранному расстоянию (метрике) в пространстве наблюдений;
4) при формировании набора признаков, описывающих объекты, предпочтение следует отдавать информативным признакам, несущим ин формацию о наличии классов.
В разделе 2.5 излагаются методы обнаружения информативности признаков. Первый метод заключается в исследовании гистограммы каждого признака. Признак считается информативным, если его гистограмма имеет хотя бы один статистически значимый локальный минимум (СЗЛМ). (Дано определение СЗЛМ.) В этом случае исследуемое множество (2.1) имеет классы, далеко отстоящие друг от друга, и для числа классов к имеет место оценка к^»\т* +1> "Lx = max/w„ s = \,2,-,P где штах - число СЗЛМ гистограммы 5 - го признака.
Второй метод состоит в исследовании последовательности отношений уім> / = 1,2,-,^-2 расстояний между соседними членами вариационного ряда (ВР) s - го признака, s = 1,2,...,р.
В?: х0)<х{2)<...<х{п), vu+l = r(xii+2),x(M))/r(x{M),xu)), / = 1,2,...,«-2
Если при некотором значении /0 є {1,2,...,«-2} наблюдается скачок, т.е. то исследуемый признак информативен, а множество имеет классы, достаточно далеко отстоящие друг от друга. Тогда для числа классов имеет место неравенство ^'max+1» f = НЮХ*,, J = 1,2,...,/? где ts - число скачков s -то признака.
В разделе 2.6 излагаются методы предварительного анализа структуры множества (2.1) и оценивания параметра к без проведения классификации в многомерном случае р > 2.
Задав на множество М подходящее расстояние г и вычислив расстояние между всего его элементами гч=г(ХпХ^, Xi,Xj є Мполучим матрицу неотрицаельных чисел
О І2 Г13 (2.3) Vr«l Гп2 Гп,п-1 0 У в которой в силу аксиом метрики г„ = 0, rtj - rjt, i,j = 1,2,...,/?.
Полагая, что плотности, классов множества М статистически равны (отличаются незначительно), исследуем множества элементов матрицы (2.3), стоящие выше главной диагонали {W Упорядочив элементы множества (2.4) по возрастанию, получим основной вариационный ряд (ОВР) множества М. При рассмотрении ОВР возможны ситуации: Гистограмма ОВР имеет хотя бы один СЗЛМ. Тогда множество М имеет классы, далеко отстоящие друг от друга. Гистограмма ОВР не имеет ни одного СЗЛМ. Тогда множество М однородно или имеет, состоит из классов близко расположенных друг к другу. Гистограмма ОВР не имеет ни одного СЗЛМ, но имеет длинный хвост. В этом случае резко выделяющиеся элементы множества М составляют классы с малым числом элементов. В первом случае получаем оценку наибольшего диаметра классов max ' "max _ rq ' где rq - левый конец отрезка гистограммы ОВР [r(j,r +]], в котором наблюдается первый СЗЛМ (нумерация идет слева направо). Для выделения классов множества М следует использовать самые простые алгоритмы. Во втором случае, если удастся сформировать набор информативных признаков из исходных путем отбора или их преобразования, то исследуется гистограмма ОВР по новому признаковому пространству. Если не удается обнаружить ни одного информативного признака, то для классификации элементов множества М следует использовать более сложные алгоритмы. В первом случае имеем несколько оценок снизу для числа классов к. Теорема 2.1. Если гистограммы ОВР множества М имеет т СЗЛМ, то к>Е[(\ + (\ + Ш)1/2/2 + є], где Е[у] - целая часть у, 0 < є < 0,001. Теорема 2.3. Если гистограмма ОВР множества М имеет хотя бы один СЗЛМ, то к>Е[п2/(2Ї0 + п) + є)], где 0 < є < 0,001, /0 - оценка внутри классовых расстояний, содержащихся в ОВР. Наблюдается первый СЗЛМ (при нумерации слева направо): /r0 = argmaxr , г -левый конец отрезка [г ,/ ,] гистограммы ОВР. Для оценивания параметра к сверху введено понятие инвариантной пары точек. Пара точек (Xlo,Xj), Х^,ХЛ еМ инвариантна, если каждая ее точка является ближайшей для другой, тахг(Хіо,Х;) = г(ХіоХь), i0*j, 7 = 1,2,...,/7 тахг(Х.,Х.о) = г(ХіоХ.о), j0*i, / = 1,2,...,/7 Каждое множество, содержащее не менее двух элементов, имеет хотя бы одну инвариантную пару точек. Если число инвариантных пар множества М равно «;;„,,то k Эксперименты показали, что число инвариантных пар множества М растет с ростом числа его элементов, составляя от него 20% - 30%. Оценку (2.5) удобно использовать для наибольших значений п, п < 20. В разделе 2.8 описан метод выделения классов с резко различающимися плотностями точек (РРПТ), наличие которых может порождать дополнительные СЗЛМ на гистограмме ОВР. Классы cos, a>t, s,te{\,2,...,k} имеют резко различающиеся плотности точек, если все расстояния между ближайшими соседними точками класса cos сравнимы с диаметром класса cot. Для выделения подмножеств таких классов строится ВР минимальных расстояний Rmin, г1. Минимальное расстояние от точки Х{еМ - это расстояние от Xt до ее ближайшей соседней точки X., Птт = minr(X,,X), i*j\j = 1,2,...,« . J J Если гистограмма множества (2.6) имеет хотя бы один СЗЛМ, то множество М содержит классы с РРПТ, которые нетрудно выделить. Гистограмма множества (2.6) строится при п > 30, а в общем случае исследуется последовательность отношений y=rii+l)/rU) / = П /7-1 Лі 'mm /'nun' l i>~vj" * Если при некотором значении /0 є {1,2,...,/7-1} имеет место неравенство *<,»! (2.7) то множество М содержит классы с РРПТ. Если неравенство(2.7) выполняется v раз, то для параметра к имеем k>v + l. В разделе 2.9 дано подробное описание алгоритмов классификации (из группы интуитивно-геометрических), наиболее пригодных для решения задачи формирования целевого коллектива оптимальной структуры. К таким алгоритмам относятся FOREL, алгоритмы Мак-Клина, Себестиана, Дженси, KRAB. В разделе 2.10 описан алгоритм выбора целевого коллектива из множеств классов {со{,со2,...,сок}, полученных в оптимальном варианте классификации исходного множества индивидуумов. При этом рассмотрены два варианта: лидер целевого коллектива известен, такой лидер неизвестен. В главе 3 диссертации рассматривается задача оптимального выбора структуры целевого коллектива на базе системы стохастических дифференциальных уравнений. Пусть Р{ - потенциал элемента системы, который зависит от набора признаков элемента и взаимодействия с другими элементами системы. Для оценки эффективности элементов системы из К элементов используется феномен логистического уравнения. Логистическое уравнение может быть применено для описания самых различных процессов. С его помощью моделируются рост колонии дрожжевых грибов и сложные процессы развития человеческого общества. Динамика ресурсов в таких моделях описывается с помощью системы логистических уравнений: і = {!...#}, Д.>0,а..>0, К;>0, P,(0) = PI0, (3.1) где /-номер рассматриваемого ресурса, Pt- его величина,Kt,Д. ,ау- соответствующие константы, W\ - одномерный процесс Винера, //,.- неизвестные параметры, которые необходимо оценить. Рассматривается следующая задача: для фиксированного индекса K В качестве первого приближения для решения задачи (3.1), (3.2) используется методы кластерного анализа, а также методы решения несобственных задач линейного программирования, которые применяются для классификации. Для решения поставленной задачи сначала рассматривается уравнение Ланжевена в смысле среднеквадратического. Коэффициенты уравнений Ланжевена находятся из условий нормированной суммы признаков и коэффициентов корреляции. По решению указанной системы уравнений определяются коэффициенты //. Винеровского процесса. После решения уравнения (3.1) определяем максимум функционала (3.2). Для численного решения уравнений (3.1) и идентификации параметров ju, применяем идеи и методы, предложенные в работе [5] из списка публикаций автора. В приложениях приведены результаты расчетов модельных примеров различными методами. Сформулированы и доказаны теоремы существования и единственности для стохастической системы (3.1). Использован метод факторного анализа для решения несобственных задач линейного программирования. Литература к введению: Флеров Ю.А. Автоматизация проектирования сложных объектов машиностроения. В сб. Современные проблемы прикладной математики, под редакцией А.А. Петрова. М.: МЗ Пресс, 2005 г., стр. 75-98. Журавлев Ю.И., Рязанов В.В., Сенько О.В. «Распознавание» Математические методы, программная система, практические применения, М., Фазис, 2006 Апраушева Н.Н. Преобразование признаков при статистическом решении одной задачи автоматической классификации. Изв. АН СССР. Тех-нич. кибернетика. 1985. №2. С. 167-179. Шлезингер М., Главач В. Десять лекций по статистическому и структурному распознаванию. Киев, Наукова думка, 2004 г. Гардинер К.В. Стохастические методы в естественных науках. М.,Мир,1986 Баркин А.И., Зеленцовский А.Л., Паркшин П.В. Абсолютная устойчивость детерминированных и стохастических систем управления. М., МАИ, 1992 Маланин В.В., Полосков И.Е. Случайные процессы в нелинейных динамических системах. Ижевск, НИЦ «Регулярная и хаотическая динамика», 2001 г. Голиков А.И., Евтушенко Ю.Г. Ю.Г. Моллаверди Н. Применение метода Ньютона к решению задач линейного программирования большой размерности. ЖВМиМФ, 2004, том 44 № 9 С. 1564-1573. 9. Харман Г. Современный факторный анализ М. Статистика 1972 Ю.Еремин И. И. , Мазуров Вл. Д. Нестационарные процессы математиче ского программирования. -М.: Наука, 1979. 11. Северцев Н.А., Шолкин В.Г., Ярыгин Г.А. Статистическая теория подобия: надежность технических систем. М.: Наука, 1986 г. 12.Дикусар В.В., Милютин А.А. Качественные и количественные методы в принципе максимума. М., Наука, 1989. ІЗ.Аркин В.И., Саксонов М.Т. К теории стохастического принципа максимума в задачах с непрерывным временем. М., ЦЭМИ АН СССР, 1983. Список публикаций автора: Нечеухин О.В.. Вопросы оптимального управления и роста ресурсов в системе. Журнал «Вопросы теории безопасности и устойчивости систем», выпуск 6(2). Сообщения по прикладной математике. М., ВЦ РАН, 2004, стр 86-93. Дикусар В.В., Нечеухин О.В.. Проблема создания оптимальных структур научных коллективов. Журнал «Вопросы теории безопасности и устойчивости систем», выпуск 6(2). Сообщения по прикладной математике. М., ВЦ РАН, 2004, стр. 77-85. Дикусар В.В., Нечеухин О.В.. Методы создания оптимальных структур научных коллективов. Международный журнал «Вестник Брестского университета», серия естественных наук 3(42), 2004, Брест, изд. БрДУ, стр. 12-17. Дикусар В.В., Нечеухин О.В.. Использование кластерного анализа в формировании научных коллективов. Журнал «Исследование операций», М., ВЦ РАН, 2005, стр. 36-42. Дикусар В.В., Нечеухин О.В. О задаче идентификации параметров стохастического дифференциального уравнения. Труды ИСА РАН Динамика неоднородных систем, под. Ред. Члена-корр. РАН Ю.С. Попкова. Выпуск 9(2) 2005 г., M.URSS стр. 95-112. 6. Нечеухин О.В. Комитетные и факторные решения. Труды ИСА РАН Динамика неоднородных систем, под. Ред. члена-корр. РАН Ю.С. Попкова. Выпуск 9(2) 2005 г., M.URSS стр. 193-199.Похожие диссертации на Методы выбора оптимальной структуры целевого коллектива
