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

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

АБДРАХАНОВ Сергей Валерьевич

РАЗРАБОТКА МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ И КОМБИНИРОВАННЫХ АЛГОРИТМОВ ЧИСЛЕННОЙ ОПТИМИЗАЦИИ СТРУКТУРЫ МОДУЛЬНЫХ ОБЪЕКТОВ

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

5 ДЕК 2013

АВТОРЕФЕРАТ ДИССЕРТАЦИИ НА СОИСКАНИЕ УЧЕНОЙ СТЕПЕНИ КАНДИДАТА ТЕХНИЧЕСКИХ НАУК

Воронеж-2013

005541604

005541604

Работа выполнена в ФГБОУ ВПО «Воронежский государственный технический университет»

Научный руководитель Львович Яков Евсеевич,

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

Официальные оппоненты: Лапшина Марина Леонидовна,

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

Каширина Ирина Леонидовна,

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

Ведущая организация ФГБОУ ВПО «Московский государ-

ственный университет приборостроения и информатики»

Защита состоится «12» декабря 2013 г. в 1500 часов в конференц-зале на заседании диссертационного совета Д 212.037.01 ФГБОУ ВПО «Воронежский государственный технический университет» по адресу: 394026, г. Воронеж, Московский проспект, 14.

Автореферат разослан «12» ноября 2013 г.

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

диссертационного совета ^МЧ^ Барабанов Владимир Федорович

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

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

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

В отечественной и зарубежной литературе (Банди Б., Батищев Д.И., Гилл Ф., Львович Я.Е., Маккорник Г., Моцкус И.Б., Мюррей У., Подвальный С.Л., Поляк Б.Т., Пшеничный Б.Н., Растригин Л.А., Соболь И.М., Статнитков Р.Б., Юдин Д.Б. и др.) предложен ряд подходов к структурной оптимизации, основанных на многоэтапной процедуре: генерация варианта структуры, идентификация параметров, соответствующих структуре объекта, анализ значений показателей эффективности при этих значениях параметров, сравнение вариантов по показателям и выбор наилучшего. Возможность интеграции этих этапов в едином цикле для объектов с варьируемой структурой достигается на основе применения методов многоальтернативной оптимизации. Однако они не позволяют одновременно с оптимальным выбором модульной структуры движущегося объекта осуществлять оптимальный выбор алгоритма движения. Кроме того, построение эффективной для данного класса объектов численной процедуры поиска наилучшего решения и последующего использования ее в практических приложениях требует предварительного исследования на основе вычислительного эксперимента с комбинированными алгоритмами многовариантного выбора. Одновременно с организацией исследовательского процесса в рамках системы компьютерного моделирования положительной тенденцией в создании таких систем является включение в них натурных экспериментов и имитационного моделирования.

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

Тематика диссертационной работы соответствует основному научному направлению ФГБОУ ВПО «Воронежский государственный технический университет» «Интеллектуальные информационные системы».

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

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

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

осуществить математическое моделирование объектов с модульной структурой в виде модели многоальтернативной и многокритериальной оптимизации;

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

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

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

Тематика работы соответствует следующим пунктам паспорта специальности 05.13.18:

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

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

п.8. Разработка систем компьютерного и имитационного моделирования.

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

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

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

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

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

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

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

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

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

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

По результатам работы направлены 9 заявок на патенты РФ, получено 1 положительное решение по заявке 2012 117 133.

Апробация работы. Основные положения докладывались и обсуждались на Всероссийской конференции «Интеллектуальные информационные системы» (Воронеж, 2011), Международных молодежных научных школах «Молодежь и современные информационные технологии» (Воронеж, 2011), «Управление, информация и оптимизация» (Воронеж, 2011), Международной конференции «Ме-хатронные системы (теория и проектирование)» (Тула, 2011), Всероссийской молодежной научной школе «Инженерия знаний. Представление знаний: состояние и перспективы» (Воронеж, 2012), Международных молодежных научных школах «Теория и численные методы решения обратных и некорректных задач» (Воронеж, 2012), «Теория сложности вычислений» (Воронеж, 2012), «Россия-ЕС. Инженерия знаний и технологии семантического веб-анализа» (Воронеж, 2012), Международной молодежной конференции «Математические проблемы современной теории управления системами и процессами» (Воронеж, 2012), Международной молодежной конференции в рамках фестиваля науки «Микроэлектронные информационно-управляющие системы и комплексы» (Воронеж, 2012), на ежегодных научно-практических конференциях ППС и аспирантов ВГТУ.

Публикация результатов работы. По теме диссертации опубликовано 10 научных работ, в том числе 2 в изданиях, рекомендованных ВАК РФ. В работах, опубликованных в соавторстве и приведенных в конце автореферата, лично соискателю принадлежат: математические модели модульных объектов на множестве

альтернативных переменных [2, 7], комбинированные алгоритмы численной оптимизации и результаты вычислительных экспериментов [1, 4].

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

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

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

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

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

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

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

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

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

порядка блочно-модульной сборки;

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

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

Г=(у2+г2)/ЫЫу, (1),

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

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

п = Ш

Тогда в двоичном исчислении имеем при N<16

п= 1+х1+2х2+4х3+8х4,

где х1, х4 = (0.

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

1+х5п+2х6„,

где п = 1,М,хБп,х6п =

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

Ппл.п-

1+х7п+2х8п+4х9п<8 ,

где п = 2,М,х7,их9п =

Если номер площадки п,1Л П при определенных значениях альтернативных переменных х7п, х9п превышает их фактическое значение п на выбранной стороне конструкции, то в качестве номера площадки берется значение

Пи, = гпос1(|г.,,„, п^ п), где шос1(Ь/с) - функция определения остатка от деления целых чисел Ь и с.

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

A1=A+Bsin(tt>t+<p),

где А1 - новое значение обобщенной координаты, А- значение обобщенной координаты (у или z), относительно которой происходит периодическое движение; В -амплитуда периодического колебания обобщенной координаты; суммарная величина |А|+|В| не должна превышать максимально допустимого отклонения обобщенной координаты модуля; ф - смещение фазы периодического движения.

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

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

=1 +х, 0п+2х,, п+4х, 2п+8х, зп, Пвш=1 +х14п+2х 1 5п+4х 16n+8x| 7т псо, „= 1+x, 8п+2х 1 9п+4х2оп+8х2 1 „, Пф 1 „= 1 +х22п+2х23„+4х24п+8х25п.

Для координаты z

nA2n= 1 +X26n+2x27n+4x28n+8x29n> пв2п= 1 +х30п+2х3 1п+4хз2п+8хззп, пга2п=1+хз4п+2хз5п+4хз6п+8хз7п, — 1 +хз8п+2хз9п+4х40п+8х4 i п.

В этом случае задача оптимизации структуры модульного объекта состоит в выборе значений альтернативных переменных xl,x¿ln обеспечивающих максимальное значение функции (1):

f = [yfai ■x*vQ]I+lz(xi -^«пЛ2 тах ^2)

ni

при ограничениях

\Лг И + (x14n.*17n)| < V™", \Az {^x29n) + B2 (х30я,*з,я)| < z™", (3)

где ymaxf z™"- максимально допустимые отклонения обобщенной координаты модуля относительно ее нулевого значения.

Обозначим вектор оптимизируемых переменных

х=( Х1 ,хЛ1п, п = 1 ,N). В качестве оптимизируемой функции F(x) будем использовать функцию Ла-гранжа, которая дает возможность перейти от задачи оптимизации, включающей

целевую функцию (2) и ограничения (3), к эквивалентной задаче оптимизации без ограничений

Р(хД,, А.2)=Ц;х)+ иутах-|А,(х)+В,(х)|)+ ^(гтах-|А,(х)+В1(х)|). где Л] >0, Х2 >0- неопределенные множители функции Лагранжа.

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

Для расширения вариантов реализации процедуры оптимизации структуры предложена многокритериальная модель. В качестве критериев оптимизации примем следующие: максимизацию перемещения по обобщенной координате у- Ч^; максимизацию перемещения по обобщенной координате ъ- Ч'2; максимизацию величины обратно пропорциональной числу модулей в объекте - 4^=—; максимизацию величины обратно пропорциональной сложности алгоритма управления -

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

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

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

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

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

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

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

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

Используем итерационную вариационную процедуру многоальтернативной оптимизации, основанную на определении на каждом к - ом (к = 1,2.....) шаге поиска вариации оптимизируемой функции Р по переменной ху.

Л- Р(х~к/х, = 0) - = 1), (4)

где хк = (хТ,..., ..., X]) ж = 1,], к ^/- вектор случайных реализаций альтернативных переменных, имеющих распределение

Р*„=Р(^ = 1), ях= = 0), рх+ цх=\, р(.) - обозначение вероятности случайного события.

На начальном этапе вычислительного эксперимента вариации определяются на основе результатов натурного эксперимента, а при накоплении информации, достаточной для построения имитационной модели, в соответствии с этой моделью, в которой значения переменных N. Аь Вь а>1, ф), А2, В2, со2 , фг вычисляются по значениям, соответствующим значениям альтернативных переменных х;,

В качестве исследовательского компонента предлагается внутри этой процедуры осуществлять движение не по одному набору вероятностей рч, ]= 1,/ а по п (п= 1,Л?) наборам pxjn, используя при этом комбинированную процедуру с методом роя частиц.

В этом случае имеем п= 1,Л'Г частиц с координатами Р|п, п= I, А'г, ]= 1,/ которые изменяются на каждом к - ом шаге по схеме:

Г)к+1 =рк. +ук+1 (5)

где - координаты вектора скорости п - й частицы

<„+1 = р^Ч^гМ^/) - р^ЫипП)-

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

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

этой целью вводится случайная дискретная величина п, принимающая значение

71= 1, Л'г с вероятностью рп. На первом шаге

ТЖ.

г

Далее изменение значений при условии 1 р1,': = 1 осуществляется следующим образом.

Определяется значение случайной величины п . Пусть Я = V. Тогда скорости изменения координат на (к+1} - м шаге вычисляются:

' ш (rtj jyij,?) - vl,a-^snf)).n - v,

а значение вероятностей р„

и* _

Fn Vn = 1, Ay п Ф v

Р" I +

-i—Г.71 = V,

где е^"1"1 = £кexp(p.(sign(Av~1V*)')), ц > о - параметр, который задаётся в процессе поиска.

При этом величина s > о определяет степень рекордности движения v - й частицы в направлении к экстремуму оптимизируемой функции F:

где Ry = max (F(ri/:v)1,=0), Aj-„=1)) - рекорд по функции F для частицы v при определении вариации по j-й альтернативной переменной, R% = шах!=^ (F(x; /a)s=0), F(x£/xjs=l)) - рекорд по функции F для s = соседних частиц при определении вариации по j-й альтернативной переменной, s- номер соседней частицы в соответствии с понятием соседства частиц, которое определено в методе роя частиц.

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

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

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

Наконец, третий вариант (алгоритм 3) основан на комбинации рандомизированной схемы поиска многоальтернативной оптимизации и диалоговой процедуры

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

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

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

11

роятностью Pd, ^¿=1Pd = 1- На к-м шаге параллельно с настройкой вероятностей альтернативных переменных, вероятностей значимости критериев \|/,(х) для формирования оптимизируемых функций осуществляется настройка вероятностей Pj.

Основу настройки вероятности характеристик составляют формализованные оценки мнений экспертов. Структурная схема диалогового алгоритма многокритериальной оптимизации приведена на рис. 3.

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

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

На рис 4. приведена структура программного обеспечения.

ПО вычислительных процедур написано в среде разработки приложений Borland С++ Builder и состоит из нескольких частей. Графический интерфейс позволяет управлять процессом вычисления, управлять геометрическими моделями, создавать и сохранять значения координат объектов, элементы расчетной сетки, граничные условия, управлять графическим отображением моделей и результатов расчета. Алгоритмы, созданные в разработанной программе, дают возможности совмещения различных алгоритмов при моделировании, что ведет к повышению достоверности получаемых результатов, а в некоторых случаях, за счет использования более простого и наглядного метода, упростить и ускорить процесс получения решения.

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

Рис. 3. Структурная схема диалогового алгоритма многокритериальной оптимизации на множестве альтернативных переменных 13

ПО вычислительных процедур

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

Модуль синтеза структуры ММР по алгоритму 1 Модуль синтеза структуры ММР по алгоритму 2 Модуль синтеза структуры ММР по алгоритму 3

Модуль обработки и вывода результатов вычислительного эксперимента

Модуль документирования полученного решения ММР

Модуль ввода исходных данных

Модуль соорки программных блоков в соответствии со структурой конструкции ММР

Модуль управления движением робота

Модуль анализа по определению показателей эффективности функцио нироб алия рооота

Рис. 4. Структура программного обеспечения

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

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

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

Результаты экспериментальных исследований сведены в таблицы 1, 2.

Таблица 1

Результаты многокритериальной оптимизации структуры ММР с использованием комбинированного алгоритма многоальтернативного выбора и метода роя частиц (алгоритм 1)

№ варианта Число модулей % см см Рг Г, Ре Вычислительная трудоемкость процедур структурного синтеза, мин Конфигурация ММР

1 5 4 5,5 0,6 0,47 0,4 0,7 0,2 0.3 0,5 6,2 4 ТГ

2 15 4.1 5,1 0,55 0,51 0,5 0,4 0,3 0,1 0,6 5,3 1 1

3 25 3 2 0.4 0,5 0,6 0,3 0,4 0,9 0,2 1,2 20

4 35 5,4 4 0,5 0,6 0,5 0,2 0,6 0,2 0,3 6.5 29

5 40 1 2 0,5 0,3 0,4 0,1 0,3 0,8 0,4 0,3 34

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

Таблица 2

Результаты многокритериальной оптимизации структуры ММР с использованием комбинированного алгоритма многоальтернативного выбора и генетического алгоритма (алгоритм 2)

№ варианта Число модулей см см % Рг Р6 Вычислительная трудоемкость , мин Конфигурация ММР

1 5 3 4,5 0,5 0,47 0,4 0,6 0,2 0,4 0,3 3,17 2 Ж

2 15 5,1 2,2 0,41 0,51 0,5 0,3 0,3 0,3 0,5 2,35 9 <3^5

3 25 4 3,1 0,35 0,5 0,3 0,2 0,4 0,7 0,3 2,17 20

4 35 4,4 3 0,3 0,6 0,5 0,4 0,5 0,3 0,4 2,38 33

5 40 2 3 0,45 0,3 0,3 0,3 0,2 0,6 0,3 0,81 40

Вычислительная 40 трудоемкость процедур 35

структурного синтеза, мин

Рис. 5. Зависимость трудоемкости процедуры оптимизации структуры от числа модулей (размерность задачи) по результатам вычислительного эксперимента 16

10 15 20 25 30 35 40 45

Число модулей и деталей

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

6. Сформирована процедура участия экспертов при многокритериальном выборе структуры модульных объектов.

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

Публикации в изданиях, рекомендованных ВАК РФ

1. Львович Я.Е. Интеграция процедур многоальтернативной оптимизации и метода роя частиц / Я.Е. Львович, C.B. Андраханов // Вестник Воронежского государственного технического университета. - 2010. — Т. 6. - № 12. — С. 29-31.

2. Андраханов C.B. Многоальтернативная оптимизационная модель автоматизации структурного синтеза мехатронно - модульных роботов / C.B. Андраханов, Я.Е. Львович // Вестник Воронежского государственного технического университета. - 2011. - Т.7. - № 3. - С.75-77.

Статьи и материалы конференций

3. Андраханов C.B. Многовариантная оптимизационная модель автоматизации структурного синтеза мехатронно-модульных роботов с интеграцией рандомизированных процедур оптимизации и метода роя частиц / C.B. Андраханов //

Интеллектуальные информационные системы: труды Всероссийской конференции. - Воронеж: ВГТУ, 2011. - С. 72-76.

4. Андраханов C.B. Многоальтернативный синтез структуры мехатронно-модульных роботов на основе формализации экспертных знаний / C.B. Андраханов, Я.Е. Львович // Инженерия знаний. Представление знаний: состояние и перспективы: материалы Всероссийской молодежной научной школы. - Воронеж: ИПЦ «Научная книга», 2012. - С. 70-74.

5. Андраханов C.B. Многоальтернативная оптимизация управления ме-хатронно-модульным роботом / C.B. Андраханов // Математические проблемы современной теории управления системами и процессами: материалы Международной молодежной конференции. — Воронеж: ИПЦ «Научная книга», 2012. - С. 207209.

6. Андраханов C.B. Применение процедур формализации экспертных знаний при проектировании мехатронно-модульных роботов / C.B. Андраханов // Россия-ЕС. Инженерия знаний и технологии семантического веб-анализа: материалы Международной молодежной научной школы. - Воронеж: ИПЦ «Научная книга»,

2012.-С. 125-128.

7. Львович Я.Е. Многоуровневая оптимизационная модель автоматизации структурного синтеза мехатронно-модульных роботов / Я.Е. Львович, C.B. Андраханов // Вестник Тульского государственного университета. Серия «Системы управления». - 2012. - Вып. 1. — С. 6-8.

8. Андраханов C.B. Разработка численного метода и алгоритма оптимизации на основе метода роя частиц / C.B. Андраханов // Информационные технологии моделирования и управления. — 2013. -№ 5. — С. 412-417.

9. Андраханов C.B. Алгоритмизация процесса моделирования для решения задач оптимизации управления мехатронно-модульными роботами / C.B. Андраханов // Информационные технологии моделирования и управления. -

2013.-№5.-С. 474-480.

10. Андраханов C.B. Комбинированный алгоритм многоальтернативной оптимизации и метода роя частиц // C.B. Андраханов / Моделирование, оптимизация и информационные технологии. - 2013. - № 2. http://moit.vivt.ru/wp-content/uploads/2013/1 l/andrahanov_2_13_l .pdf.

Подписано в печать 07.11.2013 Формат 60x84/16. Бумага для множительных аппаратов. Усл. печ. л.1,0. Тираж 80 экз. Заказ № 219.

ФГБОУ ВПО «Воронежский государственный технический университет» 394026, Воронеж, Московский просп., 14

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

04201453555

ФГБОУ ВПО «Воронежский государственный технический университет»

Андраханов Сергей Валерьевич

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

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

и комплексы программ

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

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

Заслуженный деятель науки РФ Я.Е.Львович

Воронеж-2013

Введение.............................................................................. 3

1.Анализ и пути развития математических методов моделирования и

численных методов оптимизации структуры модульных объектов...... 10

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

многоальтернативных оптимизационных моделей........................ 10

1.2.Развитие численных методов оптимизации модульной структуры... 14 1.3.Особенности построения проблемно-ориентированных моделей и численных процедур при оптимизации структуры технических реализаций модульных объектов................................................ 21

2.Формирование математических моделей оптимизации структуры модульных объектов................................................................ 48

2.1.Многоальтернативная оптимизационная модель структурного синтеза ММР........................................................................... 49

2.2.Многокритериальное оптимизационное моделирование.............. 54

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

оптимизационное моделирование............................................... 56

Выводы второй главы............................................................... 62

3.Разработка комбинированных алгоритмов численной оптимизации структуры модульных объектов.................................................. 63

3.1.Комбинированный алгоритм многоальтернативной оптимизации и метода роя частиц.................................................................... 64

3.2.Интеграция алгоритма многоальтернативного выбора и генетического алгоритма.......................................................... 72

3.3. Диалоговый алгоритм многокритериальной оптимизации на

множестве альтернативных переменных....................................... 78

Выводы третьей главы.............................................................. 82

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

/ V ' , ' N ' ,

* \ » ' '

!' 1

4.1 .Характеристика компонентов системы.....................................

4.2.Структура программного вычислительного экспериментального комплекса................................................................................

93

4.3.Оценка эффективности по результатам натурных и вычислительных

экспериментов................................................................................................................................................112

Выводы четвертой главы........................................................................................................................120

Заключение........................................................................................................................................................121

Литература..........................................................................................................................................................123

Приложения........................................................................................................................................................134

Введение

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

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

В отечественной и зарубежной литературе (Банди Б., Батищев Д.И., Гилл Ф., Львович Я.Е., Маккорник Г., Моцкус И.Б., Мюррей У., Подвальный С.Л., Поляк Б.Т., Пшеничный Б.Н., Растригин Л.А., Соболь И.М., Статнитков Р.Б., Юдин Д.Б. и др.) предложен ряд подходов к структурной оптимизации, основанных на многоэтапной процедуре: генерация варианта структуры, идентификация параметров, соответствующих структуре объекта, анализ значений показателей эффективности при этих значениях параметров, сравнение вариантов по показателям и выбор наилучшего. Возможность интеграции этих объектов в едином цикле для объектов с варьируемой структурой достигается на основе применения методов многоальтернативной оптимизации. Однако они не позволяют одновременно оптимальным выбором модульной структуры движущегося объекта осуществлять оптимальный выбор алгоритма движения.

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

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

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

Тематика диссертационной работы соответствует основному научному направлению ФГБОУ ВПО «Воронежский государственный технический университет» «Интеллектуальные информационные системы».

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

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

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

осуществить математическое моделирование объектов с модульной структурой в виде модели многоальтернативной оптимизации;

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

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

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

Тематика работы соответствует следующим пунктам паспорта специальности 05.13.18:

п.1. Разработка новых математических методов моделирования объектов и явлений.

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

п.8. Разработка систем компьютерного и имитационного моделирования.

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

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

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

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

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

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

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

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

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

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

По результатам работы направлены 9 заявок на патенты РФ, получено 1 положительное решение.

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

научной школе «Инженерия знаний. Представление знаний: состояние и перспективы» (Воронеж, 2012 г.), Международных молодежных научных школах «Теория и численные методы решения обратных и некорректных задач» (Воронеж, 2012 г.), «Теория сложности вычислений» (Воронеж, 2012 г.), «Россия-ЕС. Инженерия знаний и технологии семантического веб-анализа» (Воронеж, 2012 г.), Международной молодежной конференции «Математические проблемы современной теории управления системами и процессами» (Воронеж, 2012 г.), Международной молодежной конференции в рамках фестиваля науки «Микроэлектронные информационно-управляющие системы и комплексы» (Воронеж, 2012 г.), на ежегодных научно-практических конференциях ППС и аспирантов ВГТУ.

Публикация результатов работы. По теме диссертации опубликовано 11 научных работ, в том числе 3 в изданиях, рекомендованных ВАК РФ. В работах, опубликованных в соавторстве и приведенных в конце автореферата, лично соискателю принадлежат:

математические модели модульных объектов на множестве альтернативных переменных [3, 39], комбинированные алгоритмы численной оптимизации и результаты вычислительных экспериментов [4, 5, 38]. Структура и объем работы:

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

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

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

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

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

Вторая глава посвящена математическим моделям СВЭ оптимизации структуры модульных объектов.

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

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

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

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

£=(у2+г2)/№Чу (1),

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

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

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

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

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

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

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

Возможности изменения перечисленных компонентов определяются разнообразием двух множеств и связей между ними [1, 53]:

модулей

Ксх{Г]:]е.Г},(1.1)

где с - знак отношения; х - знак декартова произведения; 1^=1, Щ -

множество номеров типов модулей ]-го наименования 0=1, Щ ;

И-число модулей в объекте;

Усх{у^еТ},(1.2)

где у1 —1,- множество номеров реализаций 1>го блока алгоритма управления движением 0=1, Му); 1чГу - количество блоков в алгоритме управления движением.

Под структурой модульного объекта будем �