Применение СУБД ACCESS при решении задач оптимизации с использованием сеточных методов зондирования пространства изменения параметров

 просмотров

ПРИМЕНЕНИЕ СУБД ACCESS ПРИ РЕШЕНИИ ЗАДАЧ ОПТИМИЗАЦИИ С ИСПОЛЬЗОВАНИЕМ СЕТОЧНЫХ МЕТОДОВ ЗОНДИРОВАНИЯ ПРОСТРАНСТВА ИЗМЕНЕНИЯ ПАРАМЕТРОВ

1, 2

1Институт проблем управления РАН

2Microsoft Corporation

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

(1) ,

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

G - определяемая в процессе поиска область эффективности,

- область изменения значений стохастических параметров,

- функция, описывающая j-й показатель качества,

- вектор входных параметров с размерностью ,

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

t - время,

J - общее число критериев,

- плотность распределения, нормированная относительно области G,

- плотность распределения, удовлетворяющая условию:

.

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

,

(2) ,

или набор оценок из пространства оценок с заданной метрикой [2], для которых показатели качества составляют множество Парето. Для решения такой задачи предложено объединить метод статистического моделирования, метод Монте-Карло и методику -поиска с усреднением [2].

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

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

;

(3) .

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

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

,

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

Трудность определения области интегрирования G по результатам имитационных экспериментов вытекает из того факта, что часть таблицы, содержащая значения показателей качества , используется только для отбора значений параметров , соответствующих точкам проведения имитационных экспериментов, в которых выполняются условия (3). Исходя из особенностей исследуемых динамических стохастических систем, заранее предполагается сложный характер зависимости показателей качества от параметров системы. Значения показателей качества рассчитываются с помощью имитационного статистического моделирования. Не предпринимаются никакие попытки установить вид и определить параметры для непосредственной функциональной зависимости между выбранными значениями входных параметров и промоделированными значениями показателей качества. После формирования выборки в соответствии с условиями (3) решается плохо формализуемая задача определения такого индикатора для отбора элементов выборки, содержащей наборов значений входных параметров, по значениям которого эти элементы выделяются из всей совокупности проверенных значений входных параметров. Приближённый алгоритм решения, описанный в [2], включает этапы выполнения экспериментов с имитационной моделью стохастической системы, отбора точек пространства параметров, удовлетворяющих условиям (3), построения гипотез о виде области эффективности, формирования правила отбора точек, попадающих в область эффективности, проверки созданных гипотез об области эффективности.

Получить полный текст

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

,

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

.

Если функции подобрать не удаётся, оценки области эффективности можно представить последовательностью правил. Для первой оценки - Правило 1, для второй - Правило 2, . . . , для i-той оценки - Правило i и т. д.

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

,

где - минимальные значения координат входных параметров ,

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

Рассматриваемый алгоритм основан на использовании эмпирической процедуры в сочетании с развитым аппаратом запросов системы управления базами данных (СУБД) Access. Для снижения трудоёмкости анализа результаты имитационных экспериментов размещают в базе данных. На основе гипотез об области эффективности выполняется последовательное формирование выборок из результатов имитационных экспериментов. Анализ выборок и усреднённых значений показателей качества (1) позволяет найти приближённое решение поставленной многокритериальной многопараметрической задачи оптимизации. Выборки результатов имитационных экспериментов, для которых выполняются условия (3), соответствующие формируемым гипотезам об области эффективности, создаются автоматически средствами СУБД.

С помощью СУБД Access можно искать приближённое решение задачи определения области эффективности многократно применяя правила отбора (3) и проверяя разнообразные гипотезы о форме области эффективности G. Конструктор СУБД Access позволяет сформировать любой запрос по сортировке полной выборки из результатов имитационных экспериментов и созданию частичной выборки согласно условиям (3), наложенным на показатели качества

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

,

где - математические ожидания,

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

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

В качестве примера в Таблице 1 приведена часть выборки по полям базы данных Результат 2 (надёжность связи N) и глубина замираний m. Глубина замираний представляет собой отношение квадрата средней мощности принимаемого сигнала к дисперсии его мгновенной мощности и характеризует свойства случайного процесса, определяющего эффективность регулирования. Запрос на выборку сформулирован с помощью конструктора СУБД Access. Отобраны все результаты имитационных экспериментов, у которых .

Таблица 1. Результаты имитационных экспериментов для точек -последовательности с номерами от 1 до 14040.

Код

Номер точки

Координата 1

Координата 2

Координата 3

Результат 1

Результат 2

глубина замираний

458

360

0,88

0,88

1,66

2,77

0,92

1,05

4

720

0,44

1,16

0,83

4,04

0,977

1,39

665

864

0,26

1,49

1,83

2,56

0,91

1,07

21

1122

2,73

0,26

3,32

2,085

0,999

1,07

28

1224

0,75

0,22

1,25

3,43

0,96

1,027

632

1728

0,13

2,08

1,08

3,01

0,97

1,73

647

1904

0,58

0,58

1,25

3,51

0,96

1,03

656

1988

1,4

0,85

0,75

3,9

0,98

1,99

350

2124

1,96

0,43

1,63

2,65

0,928

1,23

363

2296

1,21

0,7

1,04

3,38

0,962

1,29

368

2376

0,73

1,66

1,3

2,89

0,935

1,32

372

2448

0,37

0,29

1,88

2,73

0,92

1

Возможность приближенного решения плохо формализованной задачи определения области эффективности при многопараметрической многокритериальной оптимизации с использованием -поиска с усреднением определяется наличием предварительно выполненных аналитических исследований, быстродействием программ для моделирования и качеством обработки полученных результатов. Вклад перечисленных составляющих алгоритма поиска решения можно оценить следующим образом. Время выполнения имитационных экспериментов связано с характером имитационной статистической модели, языком программирования, процессором ЭВМ. Оно не зависит от инструмента для обработки полученных результатов. Продолжительность заполнения базы данных определяется выбранной длиной записи, квалификацией оператора, объёмом собранной статистики. Естественно, для анализа и формирования гипотез о форме области эффективности требуется заранее непредсказуемое время. Применение средств современных СУБД ускоряет обработку полученных результатов и позволяет найти приближенное решение за приемлемое время. Приведённые в качестве примера выборки получены с использованием стандартных средств СУБД Access в течение нескольких минут. Объем обрабатываемой выборки из результатов имитационных экспериментов при этом превышал 10000. Можно с уверенностью утверждать, что просмотр статистики и отбор записей уже при объеме статистики, превышающем 100 экспериментов, c использованием СУБД выполняется и значительно быстрее, и качественно лучше.

Литература

1.  Антонова оптимизационно-имитационного подхода при выборе алгоритмов функционирования систем передачи данных // АиТ. 1996. № 9. С. 167-174.

2.  Антонова -поиска с усреднением для исследования динамических стохастических систем, представленных имитационными моделями. М., 2000 (Препринт / Институт проблем управления им. РАН). 76 с.

3.  Антонова процессов для поиска рационального решения // Информационные технологии. 1999. №11. С. 18-24.

4.  Антонова -оптимизации в рамках оптимизационно-имитационного подхода при выборе помехоустойчивых корректирующих кодов // АиТ. 1999. № 9. С. 162-168.

5.  Антонова алгоритм для исследования динамических стохастических процессов или систем, представленных имитационными моделями // Труды международной конференции "Параллельные вычисления и задачи управления (PACO`2001)". М., 2001. Т. 3. С. 30-41.

6.  -поиск с усреднением как новая технология поиска рациональных решений // Приложение к журналу "Информационные технологии". 2001. №6. С. 1-24.

7.  Antonova G. M. -search with averaging for stochastic system study // Proceedings of the international conference “Automation, Control and Information Technology”. Novosibirsk, 2002. P. 245-250.



Подпишитесь на рассылку:

Проекты по теме:

Основные порталы, построенные редакторами

Домашний очаг

ДомДачаСадоводствоДетиАктивность ребенкаИгрыКрасотаЖенщины(Беременность)СемьяХобби
Здоровье: • АнатомияБолезниВредные привычкиДиагностикаНародная медицинаПервая помощьПитаниеФармацевтика
История: СССРИстория РоссииРоссийская Империя
Окружающий мир: Животный мирДомашние животныеНасекомыеРастенияПриродаКатаклизмыКосмосКлиматСтихийные бедствия

Справочная информация

ДокументыЗаконыИзвещенияУтверждения документовДоговораЗапросы предложенийТехнические заданияПланы развитияДокументоведениеАналитикаМероприятияКонкурсыИтогиАдминистрации городовПриказыКонтрактыВыполнение работПротоколы рассмотрения заявокАукционыПроектыПротоколыБюджетные организации
МуниципалитетыРайоныОбразованияПрограммы
Отчеты: • по упоминаниямДокументная базаЦенные бумаги
Положения: • Финансовые документы
Постановления: • Рубрикатор по темамФинансыгорода Российской Федерациирегионыпо точным датам
Регламенты
Термины: • Научная терминологияФинансоваяЭкономическая
Время: • Даты2015 год2016 год
Документы в финансовой сферев инвестиционнойФинансовые документы - программы

Техника

АвиацияАвтоВычислительная техникаОборудование(Электрооборудование)РадиоТехнологии(Аудио-видео)(Компьютеры)

Общество

БезопасностьГражданские права и свободыИскусство(Музыка)Культура(Этика)Мировые именаПолитика(Геополитика)(Идеологические конфликты)ВластьЗаговоры и переворотыГражданская позицияМиграцияРелигии и верования(Конфессии)ХристианствоМифологияРазвлеченияМасс МедиаСпорт (Боевые искусства)ТранспортТуризм
Войны и конфликты: АрмияВоенная техникаЗвания и награды

Образование и наука

Наука: Контрольные работыНаучно-технический прогрессПедагогикаРабочие программыФакультетыМетодические рекомендацииШколаПрофессиональное образованиеМотивация учащихся
Предметы: БиологияГеографияГеологияИсторияЛитератураЛитературные жанрыЛитературные героиМатематикаМедицинаМузыкаПравоЖилищное правоЗемельное правоУголовное правоКодексыПсихология (Логика) • Русский языкСоциологияФизикаФилологияФилософияХимияЮриспруденция

Мир

Регионы: АзияАмерикаАфрикаЕвропаПрибалтикаЕвропейская политикаОкеанияГорода мира
Россия: • МоскваКавказ
Регионы РоссииПрограммы регионовЭкономика

Бизнес и финансы

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

Каталог авторов (частные аккаунты)

Авто

АвтосервисАвтозапчастиТовары для автоАвтотехцентрыАвтоаксессуарыавтозапчасти для иномарокКузовной ремонтАвторемонт и техобслуживаниеРемонт ходовой части автомобиляАвтохимиямаслатехцентрыРемонт бензиновых двигателейремонт автоэлектрикиремонт АКППШиномонтаж

Бизнес

Автоматизация бизнес-процессовИнтернет-магазиныСтроительствоТелефонная связьОптовые компании

Досуг

ДосугРазвлеченияТворчествоОбщественное питаниеРестораныБарыКафеКофейниНочные клубыЛитература

Технологии

Автоматизация производственных процессовИнтернетИнтернет-провайдерыСвязьИнформационные технологииIT-компанииWEB-студииПродвижение web-сайтовПродажа программного обеспеченияКоммутационное оборудованиеIP-телефония

Инфраструктура

ГородВластьАдминистрации районовСудыКоммунальные услугиПодростковые клубыОбщественные организацииГородские информационные сайты

Наука

ПедагогикаОбразованиеШколыОбучениеУчителя

Товары

Торговые компанииТоргово-сервисные компанииМобильные телефоныАксессуары к мобильным телефонамНавигационное оборудование

Услуги

Бытовые услугиТелекоммуникационные компанииДоставка готовых блюдОрганизация и проведение праздниковРемонт мобильных устройствАтелье швейныеХимчистки одеждыСервисные центрыФотоуслугиПраздничные агентства