Содержание к диссертации
стр.
ВВЕДЕНИЕ 5
ГЛАВА I. МЕТОД АНАЖЗА СТРУКТУРЫ ОПТИМИЗАЦИОННЫХ
ЗАДАЧ И ЕГО ПРИМЕНЕНИЕ ДЛЯ ПОВЫШЕНИЯ
ЭФФЕКТИВНОСТИ ОПТИМИЗАЦИИ 30
1.1. Интегральные характеристики 03 и их
оценка 30
1.2. Применение методов многомерного статистичес
кого анализа для обработки результатов
оценки интегральных характеристик 03 40
Применение метода главных компонент 40
Метод экстремальной группировки параметров и его применение 43
1.3. Оценка степени влияния переменных и их
групп на точность решения задачи 51
1.4. Методы оптимизации и анализ структуры 03 54
ЛП-поиск, учитывающий структуру задачи.. 54
Покоординатный поиск, учитывающий структуру задачи 56
Метод локальной оптимизации, основанный на анализе структуры задачи 58
1.5. Выводы по главе 1 64
ГЛАВА II. ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ МЕТОДА АНАЛИЗА
СТРУКТУРЫ 03 И С НИМ СВЯЗАННЫХ МЕТОДОВ
ОПТИМИЗАЦИИ 66
Тестовые задачи 66
Экспериментальное обоснование наличия для
03 оптимальной системы координат 73
стр.
Исследование качества оценки интегральных характеристик задачи и определения оптимальной системы координат 78
Исследование эффективности реализации метода экстремальной группировки параметров 85
Сравнение эффективности методов анализа структуры 03 89
Исследование качества оценки степени влияния переменных и их групп на точность решения 03.. 92
Пример использования метода анализа
структуры 03 95
2.8. Исследование методов оптимизации, связанных
с анализом структуры 03 98
Эффективность ЛП-поиска, учитывающего структуру задачи 98
Исследование эффективности покоординатного поиска, учитывающего структуру задачи 104
Эффективность реализаций метода локальной оптимизации, основанного на анализе структуры задачи 105
2.9. Выводы по главе II 112
ГЛАВА III. ПАКЕТ ПРИКЛАДНЫХ ПРОГРАММ И ЕГО ПРИМЕНЕНИЕ
ДЛЯ РЕШЕНИЯ ПРАКТИЧЕСКИХ 03 ИЗ
3.1. ППП для решения и анализа структуры в диалоговом режиме задач оптимизации при наличии
многих экстремумов (МИНИМУМ) ИЗ
3.1.1. Основные характеристики ППП ИЗ
стр.
Функциональное наполнение ППП 114
Диалоговое взаимодействие пользователя с ППП 121
Пример работы с ШШ 128
3.2. Синтез внешней цепи генератора импульсов
на ТРАПАТТ-диоде 130
Исследование функционирования технологического комплекса оборудования при травлении печатных плат в железо-меднохлоридных растворах 141
Расчет параметров электрохимической адсорбции по данным измерений частотной зависимости
модуля электродного импеданса 146
3.5. Выводы по главе III 151
ЗАКЛЮЧЕНИЕ 152
ЛИТЕРАТУРА 155
ПРИЛОЖЕНИЕ 169
Введение к работе
На настоящем этапе развития народного хозяйства электронные вычислительные машины (ЭВМ) находят все большее применение в научных исследованиях,в управлении предприятиями, в производстве и в других областях. Сложность решаемых задач быстро возрастает, что требует дальнейшего совершенствования вычислительной техники, ее математического обеспечения. В документе партии и правительства "Основные направления экономического и социального развития СССР на I98I-I985 годы и на период до 1990 года" указывается, что "совершенствование вычислительной техники, ее элементной базы и математического обеспечения, средств и систем сбора, передачи и обработки информации" является одним из важнейших направлений социально-экономического развития СССР.
В технике, экономике, естественных науках часто возникают оптимизационные задачи (03). Требуется минимизировать или максимизировать некоторую функцию, называемую целевой функцией, которая характеризует цену, вес, общую эффективность или нечто подобное при определенных ограничениях. Большинство практических задач имеют несколько решений, т.е. являются многоэкстремальными. В процессе оптимизации необходимо выбрать наилучшее решение среди многих возможных.
В LIJ замечено, что численные методы оптимизации — бурно развивающийся в настоящее время раздел вычислительной математики. Им посвящена обширная литература. Это вызвано тем, что, как показано в М, расширение приложений и совершенствование вычислительных средств приводят к резкому усложнению задач оптимизации.
Увеличение сложности 03 вызвало необходимость создания ме-
- б -
тодов анализа этих задач для их рационального изменения.
Анализ методов решения задач математического программирования СЗ-Il], особенно задач большой размерности, приведенный в С9], позволяет сделать вывод, что в последнее время все большее внимание уделяется методам, основанным на релаксации ограничений задачи и фиксации ее переменных. Это связано с тем, что математические модели выбора решения для различных производственных и технических задач включают и такие ограничения и переменные, которые не влияют или мало влияют на выбор решения. В СЗІ рассмотрены необходимые и достаточные условия, позволяющие определить существенные и несущественные ограничения для модели, которая описывается системой линейных неравенств и равенств. В ходе итерационного алгоритма поиска оптимума целевой функции часть ограничений и переменных может также не влиять на дальнейший ход итерационного процесса. Поэтому не только объединяются различные способы релаксации ограничений с методами оптимизации Ц4І, но и разрабатываются итерационные алгоритмы, в основу которых положены различные способы и схемы релаксации ограничений и фиксации переменных. Общий подход к релаксации ограничений в задачах выпуклого программирования изучен в Г5], а в Сб1 применен на квазивогнутые задачи математического программирования. Процедуры сокращения размерности задачи линейного программирования предложены в 7-11]. Их использование дает возможность значительно сократить размерность решаемых задач линейного программирования, после чего получить точное решение, применяя, например, симплекс метод [12].
В общем случае, когда имеется задача
mln (X) , Х~ (*i, .-..x^eAcR , А где А - замкнутое множество, и целевая функция, являясь не-
прерывной, обладает более сложной структурой, упрощение задачи затруднительно. Возможны следующие подходы к упрощению задачи:
аппроксимация целевой функции суммами функций меньшей размерности;
трансформирование целевой функции в сепарабельную форму с вводом дополнительных переменных и ограничений;
отображение точек п-мерного пространства в пространство меньшей размерности;
использование приближенных методов сведения многомерных задач к задачам меньшей размерности.
Вопросы аппроксимации функций суммами функций меньшей размерности исследованы в L13,14,15]. Для проведения аппроксимации необходимо знание аналитического выражения функции. Например, используя метод аппроксимации, предложенный в [14], проводя аппроксимацию целевой функции Uxit...jXn) , определенной на п -мерном единичном гиперкубе, сепарабельной функцией
п.
[с(х1}...,ха) = акГхк),
IS" '
где функция fL аппроксимирует функцию ^Х.,,...,Хп),а UK(xK)> К* (Я; - функции от одной переменной, получается:
^кґхк) =f (хк)-М- те) fo >
где +о - среднее значение целевой функции г С X ^,..., X (0 »а
f OCK)*J...Jf
о о
Это самый простой вариант аппроксимации, недостаточно хорошо отображающий характер целевой функции. Аппроксимация более сложной структуры затруднительна, что делает ее малоэффективной для уменьшения размерности задачи.
Многие функции (но не все) могут быть трансформированы в
сепарабельную форму с вводом дополнительных переменных и ограничений. В [1б] приведены две стратегии, многократное сочетание которых позволяет реализовать эту трансформацию:
1. Конструкция П^ ГХ-tVK^^2^ трансформируется ву^~7?
(Ч-/ >Чо ~ дополнительные переменные); к задаче добавляются
дополнительные ограничения:
h.z(Xz)*Ll4+ljz
2. Конструкция HfhfX)) трансформируется в Н(ц) (Ц -
дополнительная переменная); к задаче добавляется ограничение:
h(x) = у
Например, задача
гггсах,егх-' + Хг) ,
однократно применяя первую стратегию и двухкратно вторую, может быть трансформирована в следующую задачу:
г г
при ограничениях
Последняя задача - задача с сепарабельной целевой функцией, полностью эквивалентна первоначальной.
Такой подход к упрощению задачи можно применять в тех случаях, когда первоначальная задача не очень сложная, так как целевая функция упрощается, но возрастает число переменных и ограничений.
Третий способ упрощения задачи приводится в [17-21J. Используется нелинейное отображение выборочных точек в пространство меньшей размерности в некотором смысле наименее искажающее их геометрическую конфигурацию. Критерий степени искажен-ности геометрической конфигурации, используемый в ІІ7І, приводит к простому и эффективному вычислительному алгоритму [18, 19]. В [20,21] применяется незначительно видоизмененный критерий искаженности.
Пусть даны координаты т. точек в гг-мерном пространстве: а '(Х^.-.Дп, ), і.М,Г71. Пусть в результате некоторого однозначного отображения координаты точек. Л преобразованы в ко-
_^ „__, ... = * У^ ) -;Ур і ) L В4П7. *
в пространстве меньшей размерности р і р ^ я) . При этом
расстояния і— »
между исходными точками Л и Л преобразуются в расстояния
между точками Y и Y .В качестве меры искажения геометрической конфигурации исходных точек введена величина Zi , являющаяся функцией от переменных Y
т. 4 UJ у
Деление на cLij и 2Lk dy предпринято с целью нормирования, получения безразмерной величины погрешности. Выбор координат точек уменьшенной размерности сводится к решению следующей задачи поиска минимума погрешности:
min z^(Y,...,Y ),
где 6 - область изменения координат.
Полученная задача оптимизации является многоэкстремальной. В [18] приведена итерационная процедура поиска локального минимума. Использование такого способа сокращения размерности позволяет контролировать и наблюдать за "поведением" алгоритмов многомерного поиска. Такие наблюдения полезны при всестороннем исследовании и сравнении различных поисковых алгоритмов Кроме того, большая размерность не дает возможности использовать человека для принятия решений на некоторых этапах решения задачи.
Интерес представляет возможность однозначного отображения отрезка [0,11 вещественной оси на п.-мерный гиперкуб DсR. Отображения такого рода обычно называют кривыми Пеано [22І. Пусть X (Z),Z С 0,1] , есть кривая Пеано. Тогда из непрерывности f(X) . Xfz) и равенства
следует, что
f ОС)
XeD 2el0^
т.е. решение многомерной задачи минимизации целевой функции т (л) сводится к минимизации одномерной функции { (л (z)) [22, 23, 24].
Приближенные методы сведения многомерных задач к задачам меньшей размерности на основе некоторого конечного числа известных значений целевой функции и им соответствующих точек аргумента позволяют оценить степени влияния отдельных переменных и в некоторых случаях их групп на точность решения 03. Задачи упрощаются, фиксируя переменные или их группы с наименьшей степенью влияния.
- II -
Для грубой оценки степени влияния переменных или их групп на точность решения 03, в принципе можно использовать методы планирования эксперимента. Оптимизируемая функция в терминах планирования эксперимента представляется как функция отклика, а переменные Х^;...Ха - как входные и управляемые переменные, которыми исследователь может варьировать по своему усмотрению [25]. К числу методов, которые можно использовать для достижения вышеуказанных целей относятся:
Дисперсионный анализ [26] для выделения линейных эффектов и парных взаимодействий дискретно изменяющихся переменных.
Насыщенные дробные факторные планы [27] для выделения существенных переменных при условии, что доминирующими являются линейные эффекты.
Метод случайного баланса [28] для выделения существенных переменных из множества переменных и их парных взаимодействий.
Методы отбора переменных в регрессионном анализе:
метод всех возможных регрессий [29];
метод исключения [30];
метод включения [30];
метод шаговой регрессии [ЗІ].
Недостатком перечисленных методов является их привязанность к соответствующим фиксированным моделям. Например, методы выбора "наилучшего" уравнения регрессии — метод всех возможных регрессий, метод исключения, метод включения и метод шаговой регрессии - применяются для заранее принятой полиномиальной модели, в то время как в 03 часто встречаются более сложные многоэкстремальные функции.
Для анализа 03, целевые функции которых имеют сложную структуру, предложен метод выделения существенных переменных
[32]. Созданию этого метода предшествовали работы [33,34]. Результаты исследования метода выделения существенных переменных приведены в [35,36]. Метод предназначен для выявления переменных или их групп, оказывающих наибольшее влияние на точность решения оптимизационной задачи. Бго модификация применяется и в задачах планирования экстремальных экспериментов ГЗб]. Метод использует структурные характеристики экстремальных задач [34] и ряды фурье-Хаара [37]. На основе разложения целевой функции на конечное число членов ряда Фурье-Хаара в [32] показана возможность приведения задачи выделения существенных переменных к ряду задач типа случайного баланса [28].
Как показано в Г34] для функции а переменных \ (X,,,... ,ХП), определенной на гг-мерном единичном гиперкубе К - [0^ Х^^-> 0-6 Ха ^ А } , непрерывной во всех точках, координаты которых недвоично рациональны, существует единственное разложение на "разноразмерные" ортогональные слагаемые:
п.
+Z .. . Zf. . (xL ,...,xi5K..^ ftficfl..,xn)
со свойствами
J Ті і (х-і , XlJ dX; ... oiX; = 0
Jn ІЦ-'-l-s L1 Lb J-j JK
К для всех возможных непустых подмножеств
'U. }*) а[^.-Л] , (^*k«s)
Принимая за меру разброса для составляющих разложения
- ІЗ -
-f ^S J„ /4 LS 4' ' Cb L1 L5
к для 'f* ц <: l <.... < і ід f^Si а) и полагая, что они не равны
нулю, совокупность величин D; ; называют структурными ха-рактеристиками целевой функции ffx1,...)Xn). Характеристики О і ...[ являются оценкой степени влияния отдельных переменных и их групп на точность решения задачи. Здесь под оценкой степени влияния переменных и их групп на точность решения задачи понимается оценка погрешностей, возникающих при упрощении задачи, фиксируя отдельные переменные и их группы, а также при приближенном сведении задачи к ряду задач меньшей размерности.
Примером удачного использования метода выделения существенных переменных служит анализ структуры при оптимальном проектировании магнитной отклоняющей системы (МОС) [38]. Задача оптимального проектирования МОС состоит в минимизации целевой функции j(Xit..., х1ъ) , алгоритм определения значений которой сравнительно сложный, содержащий численное интегрирование системы дифференциальных уравнений движения электронов в магнитном поле МОС. Машинное время определения значения целевой функции в одной точке равно 21 секунде для БЭСМ-6, что усложняет решение задачи, выбор алгоритма оптимизации. Анализ структуры проводился по 150 результатам испытаний целевой функции. Установлено, что задача близка к сепарабельной - анализ показал, что взаимодействия переменных малы. При сравнении пяти известных алгоритмов оптимизации [39], наилучщим оказался покоординатный поиск, сконструированный на базе алгоритма одномерного поиска [40],т.е. учет специфики структуры оптимизационной задачи помог эффективно выбрать алгоритм оптимизации.
Недостатком метода выделения существенных переменных является большая зависимость времени работы на ЭВМ алгоритмической реализации метода от числа выделяемых структурных характеристик
и от числа испытаний целевой функции, предъявляемых для анализа. Это затрудняет проведение оптимального разбиения задачи на несколько задач меньшей размерности, т.е. нахождение такого разбиения переменных на m непересекающихся групп Ал,..., Am , чтобы минимизировать
I ... ZDt<...ts-r. ... . ZD-,..^,
где mL- число переменных в группе A\^,Vi і - структурные характеристики задачи, целевая функция которой f. (Хс e^L) получена из функции f fX1,. ., Хп) , фиксируя переменные, не принадлежащие группе А> .
Обзор методов оптимизации, эффективность которых зависит от структуры решаемой задачи.; Для решения 03 широкое применение нашли методы случайного поиска [4I,42j. Для определения "первого приближения", начиная с которого решение уточняется локальными методами, часто применяют глобальный поиск. Простейший
у min
глобальный поиск точки минимума Л состоит в выборе в Обладь 4 Vm
сти определения каких-то точек А;...,А , вычислении в каж
дой из них значений целевой функции {ІЮ и отборе точкиХ"
в которой L*4,m . Точка А служит приближе-
нием к точке минимума А При простейшем случайном поиске [43/ в качестве л выбираются независимые случайные точки, равномерно распределенные в области определения.
Чем более равномерно распределены точки, тем лучших результатов можно ожидать от поиска. Можно построить системы таких точек, которые расположены более равномерно, чем случайные как в п -мерном единичном гиперкубе, так и в проекциях меньшей размерности. Перечисленным требованиям удовлетворяют точки ЛП-пос-ледовательности ц , - , Ц; , построенной в [ 37].
- 15 -Если двоичное разложение номера
то расчет точки Ц e^,..., ^ Л) проводится следующим образом:
с = еД^...*ет\Ц- , j* ^а ,
где \/ заданы таблично, знак t означает поразрядное сложе-ниє по модулю 2 в двоичной системе.
В Г 37J приведена таблица Vs; для вычисления точек в единичном гиперкубе К размерностью а= ІЗ, а в [44] - размерностью п.- 51. В [44,45] приведены тексты программ на языке программирования ФОРТРАН для определения точек ЛП-последователь-ности.
ЛП-поиском называется простейший поиск, в котором пробными
А і
точками служат точки Ц,...,Ц,-- , образующие ЛП-последователь-ность, т.е. ЛП-поиск является детерминированным аналогом простейшего случайного поиска. Сравнение ЛП-поиска с простейшим случайным поиском проводилось на многих задачах [46,47,48] и неизменно ЛП-поиск оказывался более эффективным.
Эффективность ЛП-поиска зависит от структуры задачи, где под структурой понимается степень влияния отдельных переменных или их групп на точность решения. Как установлено в [49], ЛП-поиск без учета структуры задачи не всегда эффективен. Это относится особенно к задачам с выраженными взаимодействиями переменных. Основанием для исследования зависимости ЛП-поиска от структуры задачи служило следующее [49]:
I. ЛП-последовательности задаются на п-мерном единичном гиперкубе К П В 37J показано, что для размерности Я * 4 в принципе нельзя построить последовательности, различные проекции
которых на всех разноразмерных гранях К^ ... L , где KL ... ^
s-мерная грань гиперкуба К , 1й іл±... < isn,iSn , были бы расположены равномерно. Поэтому возникает вопрос, для каких проекций ЛП-последовательности наиболее равномерны.
"Качество" начальных участков ЛП-последовательностей, длина которых для д>5 достигает тысяч чисел, зависит от выбора таблицы так называемых направляющих чисел Vs: в генераторе ЛП-последовательностей.
В [37] указывается, что направляющие числа подобраны так, чтобы проекции ЛП-последовательности на двух- и трехмерные грани вида К,;д + <| и Кd ^ + J| ^ были хорошими при малых і .
С ростом а "качество" проекций для всевозможных граней в ЛП-последовательности трудно обеспечить, поэтому координаты точек с меньшими номерами распределены лучше.
В [49] доказано, что в случаях хорошего распределения проекций точек на грани существенных переменных ЛП-поиск бывает более эффективным. Выдвинуто два требования к рациональной нумерации переменных:
номера более существенных, т.е. обладающих более высокой степенью влияния на точность решения задачи переменных, должны быть связаны с более малыми номерами элементов точек ЛП-последовательности;
номера более сильно взаимодействующих между собой переменных должны быть связаны с более близкими номерами элементов точек ЛП-последовательности.
До настоящего времени эффективных методов определения нумерации переменных, отвечающей вышеуказанным требованиям, не было. Использование метода выделения существенных переменных позволяет найти нумерацию переменных, отвечающую только первому требованию. Нахождение нумерации, отвечающей второму требованию, используя
этот метод, затруднительно.
Другой метод оптимизации, эффективность которого зависит от структуры решаемой задачи - покоординатный поиск. В общем случае метод покоординатного поиска минимума оптимизируемой функции может быть записан как последовательность точек аргумента [50І:
где { }г {.,,..., 6 п } - стандартный базис в R [ 100]: ^ = = (1,0,...,0), 2= (0,1,...,0),..., а= (0,0,...,I);tnk+l
лк+L--/
te-.
выбирается так, чтобы минимизировать /(X) по прямой/
L- номер малой итерации метода; к - номер большой итерации метода.
Возможно два варианта покоординатного поиска в зависимости от тогоД^^ выбирается во всей области изменения переменной X1 или в окрестности точки аргумента л + : глобальный и локальный.
Метод покоординатного поиска не вызвал большого "интереса в связи с малой скоростью сходимости [51]. По сравнению с методом наискорейшего спуска [52], метод покоординатного поиска сходится в п. раз медленнее. Преимущество покоординатного поиска заключается в том, что он не требует вычисления градиента целевой функции и, что одномерный поиск, в многократное повторение которого сводится покоординатный поиск, является наиболее развитой частью методов оптимизации.
Малая скорость сходимости обусловлена тем, что не оптимально выбирается система координат для покоординатного поиска. Например, система координат для минимизации целевой функции-рх., ,Х2)-= 4Г><1-х2)2+('х1+х2)2 методом покоординатного поиска выбрана неудачно. Если сделать преобразование системы переменных X в
- 18 -новую систему У-(у1(... ,уа) следующего вида:
где X и У векторы-столбцы, составленные из элементов векторов-строк X и У , то минимум целевой функции можно найти за одну большую итерацию локального покоординатного поиска, начиная его из любой точки области определения. Как следствие, одним из направлений к развитию анализа структуры 03, является создание методов, позволяющих найти оптимальную систему координат. Используя метод выделения существенных переменных [32], этого сделать невозможно.
Преобразование системы координат нашло применение в локальной оптимизации. В [53] предложено семейство методов для решения задач выпуклого программирования, основанных на применении линейных преобразований пространства для симметризации областей локализации точек минимума, возникающих при использовании схем отсечений. Новая система координат вводится в зависимости от формы области, где локализован минимум и которая представляет собой выпуклую фигуру, высекаемую в шаре некоторой совокупностью плоскостей. В [54,55,56] развит подход, комбинирующий схемы отсечений и линейные преобразования в пространстве переменных для получения эффективных методов решения задач выпуклого программирования. В [57] предлагается процедура введения криволинейных координат для повышения эффективности некоторых методов минимизации выпуклых функций, использующих собственные векторы матрицы вторых производных, на случай невыпуклых функций. Минимизация осуществляется вдоль векторов, являющихся собственными по отношению к матрице вторых производных во вновь введенных координатах. В исходных же координатах спуск осуществляется вдоль некоторых кривых.
Обзор методов группировки параметров на основе корреляционной (или ковариационной) матрицы связи. При обработке результатов исследований в технике, экономике, социологии, психологии и в других областях часто приходится иметь дело с большим числом измеряемых величин, и возникает задача сокращения измеряемой информации с целью получения легко интерпретируемых результатов. Измеряемые параметры наиболее сильно коррелируют друг с другом в том случае, когда они наиболее сильно зависят от одного и того же фактора. Приняв это предположение как исходную гипотезу, можно строить разбиение всех измеряемых параметров на такие группы, что параметры, принадлежащие одной группе, в некотором смысле сильно коррелируют между собой, а параметры, принадлежащие разным группам, коррелирован^ относительно слабо. Задача такого рода называется задачей группировки параметров Г58].
Группировка параметров на основе корреляционной матрицы осуществима используя метод корреляционных плеяд [59-61] и селективный метод автоматической классификации Г 62,63]. Метод экстремальной группировки параметров 158,64] и эвристический алгоритм разбиения параметров на группы, предложенный в [65], позволяют проводить группировку параметров на основе как корреляционной, так и ковариационной матрицы. Метод корреляционных плеяд и метод экстремальной группировки параметров в [66] отнесены к эвристическим методам снижения размерности. Селективный метод автоматической классификации допускает возможность одновременного попадания классифицируемых параметров в разные группы.
Как показало экспериментальное исследование реализаций метода корреляционных плеяд, эвристического алгоритма разбиения параметров на группы и метода экстремальной группировки пара-
метров, приведенное в [65], последние дали результаты наиболее схожие с идеальными.
Реализация метода экстремальной группировки параметров приведена в [65]. Ее недостатками являются неоптимальное начальное разбиение параметров на группы, неспособность определения оптимального числа групп, а начальное вычисление некоторых параметров метода затруднительно. Авторы реализации пытались упростить вычисление этих параметров, но это понижает эффективность группировки. Целесообразно проведение исследования с целью разработки новой реализации метода экстремальной группировки параметров, не обладающей вышеуказанными недостатками.
Требования к программному обеспечению для решения 03. В настоящее время разработано большое количество численных методов оптимизации. Но, как замечено Ю.Г.Евтушенко в приложении к книге [67], сейчас не существует, да, по-видимому, и не будет существовать наилучшего во всех отношениях универсального метода оптимизации. Разумное сочетание разнообразных методов, а не поиск универсального метода, позволяет с наибольшей эффективностью решать поставленные задачи. Поэтому необходимо объединение в пакеты прикладных программ (ШШ) разнообразных программ оптимизации, что облегчает осуществление перехода от одного метода решения задачи к другому.
Так как 03 часто бывают очень сложными, в ПШ1 необходимо наличие программ, реализующих методы анализа структуры 03, позволяющие определить способы рационального упрощения и видоизменения исходной задачи или оптимального выбора стратегии решения задачи.
Многометодный режим расчетов поставил новую задачу об управлении процессом вычислений, привел к необходимости создания алгоритмов работы с алгоритмами [68]. Это сильно облегчает работу
пользователя с ШШ.
Решение действительно больших задач требует неформальных действий вычисляющего, возможности вмешиваться в процесс счета — так называемого диалогового режима. Эффективность диалогового режима решения задач оптимизации экспериментально доказана в [69].
Из вышесказанного вытекают следующие требования к программному обеспечению для решения 03:
Программы, реализующие методы решения и анализа структуры 03, должны быть объединены в ШШ.
В ШШ должны быть включены программы, позволяющие пользователю манипулировать программами, реализующими различные методы оптимизации, и результатами их работы.
Необходимо наличие в ШШ средств ведения диалога пользователя с ЭВМ.
Программы пункта І в [70] отнесены к функциональному наполнению (ФН) ШШ, а программы пунктов 2 и 3 - к системному наполнению (СН) ШШ.
В [71] приведены следующие общие требования к прикладному программному обеспечению, которые могут быть отнесены и к пакетам оптимизационных программ:
Полнота физической и математической моделей, охватываемых составом разработанных программ.
Эффективность реализованных алгоритмов.
Простота и удобство в эксплуатации.
Надежность алгоритмов и программ.
Расширяемость состава алгоритмов и программ.
Адаптируемость программного обеспечения к изменению конфигурации вычислительной техники.
Особенно важно последнее требование, так как постоянно усо-
вершенствуются операционные системы существующих ЭВМ, разрабатываются новые типы ЭВМ. Транспортабельности программного обеспечения посвящена обширная литература (см., напр., [72,73]).
Примером разработки, которая заранее предполагает распространение произведенной программной продукции на ряд заранее определенных вычислительных систем, может служить PORT -библиотека [74,753. Программы написаны на языке, являющемся общим подмножеством всех диалектов, включенных в проект системы (подмножество стандарта языка программирования ФОРТРАН). Учет машинной зависимости сводится к возможности замены вручную в теле трех функций-подпрограмм значений машинно- и операционно зависимых констант.
Таким образом можно обеспечить транспортабельность ФН ППП для решения 03, программы ФН составляя на стандартном языке программирования ФОРТРАН Г76].
Транспортабельность СН ППП обеспечить трудно, так как СН обладает большой привязанностью к конкретным ЭВМ и операционным системам. В случае транспортабельности ФН, при переходе к новому типу ЭВМ, СН приходится переделывать. Это не очень трудно, создавая СН с помощью инструментально-базовых систем, включающих наряду со средствами формирования СН и средства, используемые в ходе эксплуатации ППП. К таким системам относятся ПРИЗ [77 J, СПОРА [783, ЙСП [79], ПУПМ [803, ДШЛОГ [811. Используя последнюю систему, разработана известная диалоговая система оптимизации ДО СО для решения задач безусловной минимизации функций многих переменных, нелинейного программирования и оптимального управления (см.,напр.,[82,83]). Применение инструментальной системы (ИС) ДІАЛОГ облегчает изменение стандартных возможностей системы ДИСО и расширение их новыми диалоговыми возможностями.
Исследование современных средств для решения 03 показало, что целесообразна разработка ППП для решения и анализа структуры
в диалоговом режиме задач оптимизации при наличии многих экстремумов, отвечающего как требованиям к программному обеспечению для решения 03, так и общим требованиям к прикладному программному обеспечению.
Цель и задачи настоящей работы. Основной целью настоящей работы является разработка нового метода анализа структуры 03 и его применение для повышения эффективности оптимизации. Для достижения поставленной цели необходимо решение следующих задач:
Разработка и исследование метода анализа структуры 03, позволяющего определить для задачи оптимальную систему координат, найти оптимальное разбиение переменных задачи на группы и оценить степень влияния на точность решения задачи групп переменных и отдельных переменных как старой, так и новой систем координат.
Разработка и исследование модификаций методов оптимизации — ЛП-поиска и покоординатного поиска, учитывающих структуру решаемой задачи, и метода локальной оптимизации, основанного на анализе структуры решаемой задачи.
Разработка, исследование и применение ІЇЇШ для решения и анализа структуры в диалоговом режиме задач оптимизации при наличии многих экстремумов.
Для решения первой задачи необходимо решение следующих подзадач:
Ввод для 03 интегральных характеристик, описывающих их структуру.
Разработка методики оценки интегральных характеристик 03 по результатам испытаний целевой функции.
Исследование возможностей применения методов многомерного статистического анализа — метода главных компонент и метода экстремальной группировки параметров для анализа результатов оценки.
4. Разработка и исследование новой реализации метода экстремальной группировки параметров.
Краткое содержание отдельных глав. В первой главе приводится разработанный атором метод анализа структуры 03, включающий ввод интегральных характеристик для задачи, их оценку по результатам испытаний целевой функции и анализ результатов оценки, используя метод главных компонент и метод экстремальной группировки параметров. Новый метод позволяет:
ввести для задачи новую, в некотором смысле оптимальную, систему координат;
разбить переменные задачи на группы так, чтобы минимизировать погрешности, возникающие при упрощении задачи, разбивая ее на несколько независимых 03 меньшей размерности;
оценить степень влияния на точность решения задачи переменных старой и новой систем координат, а также их групп.
Приведен разработанный конкретный алгоритм оценки интегральных характеристик задачи на основе конечного числа результатов испытаний целевой функции.
Приведена разработанная новая реализация метода экстремальной группировки параметров, достоинства которой - оптимальное начальное разбиение параметров на группы и возможность определения оптимального числа групп.
Предложены модификации методов оптимизации, эффективность которых зависит от структуры решаемой задачи, - ЛП-поиск и покоординатный поиск, учитывающие структуру задачи, и метод локальной оптимизации, основанный на анализе структуры задачи.
Во второй главе приводятся результаты экспериментального исследования эффективности разработанного метода анализа структуры 03 и связанных с ним методов оптимизации.
Предложен список тестовых задач для исследования эффективно-
сти сравниваемых методов. Экспериментально обосновывается наличие для 03 оптимальной в некотором смысле системы координат. Приводятся результаты исследования:
качества оценки интегральных характеристик 03 по результатам испытаний целевой функции и определения оптимальной системы координат;
реализации метода экстремальной группировки параметров;
качества оценки степени влияния переменных и их групп на точность решения 03;
сравнительной эффективности методов анализа структуры 03;
эффективности ЛП-поиска, учитывающего структуру задачи;
эффективности покоординатного поиска, учитывающего структуру задачи;
эффективности реализаций метода локальной оптимизации, основанного на анализе структуры задачи.
В третьей главе приводится описание пакета прикладных программ для решения и анализа структуры в диалоговом режиме задач оптимизации при наличии многих экстремумов и его применение для решения ряда практических задач.
Особенностью функционального наполнения ПШІ является наличие большого числа программ, реализующих методы анализа структуры 03 и с ними связанные методы оптимизации, диалоговый режим работы, и транспортабельность основных программ функционального наполнения. Последнее свойство ППП позволяет использовать программы научного характера, включенные в функциональное наполнение пакета не только на ЭВМ БЭСМ-б, на которую ориентирован' ППП, но и на ДОС/ОС ЕС ЭВМ.
Приводятся результаты синтеза внешней цепи генератора импульсов на ТРАПАТТ-диоде, исследования функционирования технического комплекса оборудования при травлении печатных плат в железо-мед-
нохлоридных растворах с целью выбора оптимального состава раствора и режима работы комплекса, расчета параметров электрохимической адсорбции по данным измерений частотной зависимости модуля электродного импеданса.
Основные результаты диссертационной работы
Разработан новый метод анализа структуры 03, включающий ввод интегральных характеристик для задачи, их оценку по результатам испытаний целевой функции и анализ результатов оценки с использованием методов многомерного статистического анализа — метода главных компонент и метода экстремальной группировки параметров.
Предложена новая реализация метода экстремальной группировки параметров, достоинства которой по сравнению с реализацией, использовавшейся до настоящего времени, — оптимальное начальное разбиение параметров на группы и возможность определения оптимального числа групп. Выведены формулы, упрощающие определение факторов, соответствующих группам параметров, и вычисление связей параметров с факторами, соответствующими группам, в которых находятся данные параметры.
Предложены модификации ЛП-поиска и покоординатного поиска, учитывающие структуру задачи, и метод локальной оптимизации, основанный на анализе структуры задачи.
Проведено экспериментальное исследование, доказывающее целесообразность применения нового метода анализа структуры 03 и методов оптимизации, связанных с анализом структуры решаемой задачи, при решении сложных 03.
Разработан пакет прикладных программ для решения и анализа структуры в диалоговом режиме задач оптимизации при наличии многих экстремумов, особенностями которого являются большое число программ, реализующих методы анализа структуры 03 и с ними
связанные методы оптимизации, диалоговый режим работы, транспортабельность основных программ функционального наполнения.
6. Разработанные алгоритмы и программы применялись для решения ряда актуальных практических задач оптимального проектирования и выбора значений параметров модели. Решены задачи синтеза внешней цепи генератора импульсов на ТРАПАТТ-диоде, исследования функционирования технологического комплекса оборудования при травлении печатных плат в железо-меднохлоридных растворах с целью выбора оптимального состава раствора и режима работы комплекса, расчета параметров электрохимической адсорбции по данным измерений частотной зависимости модуля электродного импеданса и
др.
Связь с научной тематикой института. Настоящая работа выполнена в отделе теории оптимальных решений Института математики и кибернетики АН Литовской ССР в соответствии с научно-исследовательскими плановыми темами: "Исследование методов глобальной оптимизации и их применение для задач проектирования" (№ гос.регистрации 8I025I72), "Разработать и сдать в ШАЛ пакет прикладных программ многоэкстремальной оптимизации для решения задач автоматизированного проектирования" (№ гос. регистрации 0181.4013792).
Основные результаты диссертационной работы опубликованы в [84-97J и докладывались на:
республиканских семинарах "Теория оптимальных решений" (г.Вильнюс, 1980, 1981, 1982, 1983, 1984гг.);
республиканской конференции "Программное обеспечение ЭВМ" (г.Молетай, 1981 г.);
республиканской научно-технической конференции (г.Каунас, 1982 г.);
XXIII конференции Литовского математического общества (г.Каунас, 1982 г.);
республиканском координационном совещании "Программное обеспечение ЭВМ" (г.Молетай, 1983 г.);
ХХІУ конференции Литовского математического общества (г.Вильнюс, 1983 г.);
ХХУ конференции Литовского математического общества (г.Шяуляй, 1984 г.).
Внедрение работы. Программы автора настоящей работы включены в состав следующих пакетов прикладных программ, созданных по постановлениям Государственного комитета по науке и технике при Совете Министров СССР:
Пакет программ для решения и анализа оптимизационных задач (МИНФОР).
Пакет прикладных программ для решения многоэкстремальных задач проектирования на МВК ЭЛЬБРУС (ОПТИМУМ).
Пакет прикладных программ для решения в диалоговом режиме задач оптимизации при наличии многих экстремумов (МИНИМУМ).
Программа Г.Дземиды ЬРМШ, реализующая метод ЛП-поиска, учитывающего структуру оптимизационной задачи, включена в состав методоориентированного ППП для решения задач проектирования и управления. Пакет разрабатывается в Институте технической кибернетики АН БССР в соответствии с планом СП-І Совета по применению средств вычислительной техники в I98I-I985 гг. (тема I.I2).
Тульский политехнический институт использует разработанные Г.Дземидой алгоритмы и программы при создании диалоговой ситемы многокритериальной оптимизации параметров машин и конструкций (М0ПТІ), которая применяется при выполнении темы: "Исследовать и разработать методики расчета и выбора основных параметров струговых агрегатов для безлюдной выемки тонких и пологих пластов" (№ 0II3207000). Использование этих программ в пакете М0ПТІ позволяет сократить время поиска оптимальной совокупности параметров
на 20 %.
Разработанные алгоритмы и программы использованы в Горьков-ском политехническом институте им. А.А.Жданова при разработке технологии травления печатных плат в рецикле с электрохимической регенерацией — при решении проблемы "Разработка комплекса электрохимической регенерации железо-меднохлоридных растворов травления меди". В настоящее время комплексы внедрены на предприятиях министерств средств связи и приборостроения.
Результаты диссертационной работы использованы при исследовании и разработке макетов генераторов испульсов на ТРАДАТТ-дио-де. Разработанные на кафедре радиофизики Вильнюсского госуниверситета им. В.Капсукаса макеты применялись для проведения бюджетных научно-исследовательских работ по теме № 8I054I28.
Результаты диссертационной работы также использованы на кафедре физической химии Вильнюсского госуниверситета им. В.Капсукаса при расчете параметров электрохимической адсорбции по данным измерений частотной зависимости модуля электродного импеданса и определении доли экстенсивного компонента в равновесном эс-тансе.
Экономический эффект, полученный от внедрения результатов ра> боты, составляет 28,15 тысяч рублей в год.
- зо -
