ОТРАСЛЕВОЙ СТАНДАРТ

Распоряжением Министерства от 20 июня 1980 г. № 087-16

срок введения установлен с 1 июля 1981 г.

 

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

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

1. ОБЩИЕ ПОЛОЖЕНИЯ

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

Поиск экстремальных значений вектора-аргумента , (n - число показателей) осуществляется в некоторой области D конечного n-мерного эвклидова пространства.

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

1.2. Применение метода случайного поиска рекомендуется:

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

- при решении оптимизационных задач, математические модели которых имеют сложную (нелинейную) структуру, большое число переменных (N ≥ 10) или малое число переменных (N < 10) (при условии, что время решения последних должно быть не менее 1,5 - 3 с).

1.3. Построение математической модели оптимизационной задачи, состоит в математическом описании критериальной функции , соответствующей выбранному критерию Q и области поиска D. Вопросы построения математической модели в настоящем стандарте не рассматриваются.

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

                                                                   (1)

и систему ограничений, определяющую область поиска D

                                               (2)

где m - число функциональных ограничений;

 - максимальное значение вектора-аргумента .

1.5. Пользователь при решении конкретной оптимизационной задачи должен:

- сформулировать задачу управления, построить математическую модель и записать ее на алгоритмическом языке;

- сформировать исходные данные с учетом значений соответствующих операторов FORMAT и DIMENSION;

- ввести укомплектованную программу в ЭВМ.

2. АЛГОРИТМ ПОИСКА ОПТИМАЛЬНЫХ ЗНАЧЕНИЙ ПОКАЗАТЕЛЕЙ

2.1. Исходные данные

2.1.1. При реализации алгоритма используется система следующих исходных данных в виде массивов, констант и переменных:

XO (J, I), XM (J, I), XN (J, I), W (J, I), D (J, I), VS (J, I), S₁ (J, I), KI, KM, L, IX, NN, N1, NT, NQ, NS, DN, S₂, S₃, S₄, D₁, D₂, D₃, D₄, D₅, D₆, D₇.

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

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

I - индекс вида переменной;

J - индекс функциональных частей системы, самостоятельно исследуемых в задаче оптимизации.

Если решается динамическая задача оптимизации, то индексы I и J имеют следующее содержание:

I - индекс вида переменной;

J - индекс интервала времени.

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

ХO (J, I) - массив значений координат исходной точки (любое значение вектора-аргумента , принадлежащее области допустимых значений, определяемой совокупностью простых и функциональных ограничений).

XM (J, I), XN (J, I) - массивы максимальных и минимальных значений переменных, определяющих область допустимых значений.

W (J, I) - массив признаков, определяющих тип переменной (непрерывной управляемой переменной соответствует признак 1, дискретной управляемой переменной соответствует признак 0).

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

Данное преобразование осуществляется путем присвоения соответствующему элементу массива W (J, I) значения, равного 0,5.

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

Массив шагов дискретности D (J, I) заполняется только для дискретных переменных, остальным переменным в массиве соответствуют пробелы, которые в ЭВМ реализуются в нули.

VS (J, I) - массив признаков, определяющих различие или единство значений I-й переменной по J (признак 0 соответствует переменной, имеющей различные значения по J, признак 10 соответствует переменной, имеющей единое значение по J).

S₁ (J, I) - массив коэффициентов масштаба (начальное значение коэффициентов масштаба для всех переменных равно 2).

2.1.3. Значения констант и переменных назначаются в пределах указанных диапазонов в зависимости от характера задачи оптимизации и требуемой точности решения:

NN - заданное число шагов поиска экстремума (NN ≈ 300 ÷ 2000);

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

КМ - общее число управляемых переменных (в частном случае КМ равняется КI);

L - предельное число функционально самостоятельных частей системы (при отсутствии этих частей L = 1;

IX - константа, используемая при генерации равномерно распределенных случайных чисел (IX = 71253);

S₂ - константа, характеризующая быстроту сходимости поиска (S₂ ≈ 0,05 ÷ 0,1);

S₃ - константа, определяющая максимальное значение коэффициентов масштаба по всем координатам (величина S₃ определяется требованием точности поиска и изменяется в диапазоне от 10 до 100);

S₄ - константа, определяющая меру близости экстремальных оценок (величина S₄ определяется требованием к быстроте сходимости и изменяется в диапазоне от 0,05 до 0,1);

NT - число случайных исходных точек поиска в области допустимых значений переменных (NT ≥ 1);

N₁ - число неэффективных шагов поиска, после которых осуществляется изменение коэффициентов масштаба (N₁ ≈ 50 ÷ 100);

NQ - число случайных пробных шагов при оценке статистического градиента критериальной функции;

D₁ - константа, определяющая величину пробных шагов при оценке статистического градиента критериальной функции (D₁ ≈ 0,005);

D₂ - константа, определяющая величину рабочих шагов по соответствующим координатам при градиентном поиске (D₂ ≈ 0,05 ÷ 0,1);

D₃ - коэффициент роста направленных шагов поиска (D₄ ≈ 1,1 ÷ 1,3);

NS - число направленных шагов поиска, после которых осуществляется увеличение коэффициента роста направленных шагов поиска D₃ (NS ≈ 2 ÷ 5);

DN - константа, определяющая меру увеличения коэффициента D₃ (DN ≈ 1,2 ÷ 2);

D₄ - коэффициент уменьшения направленных шагов поиска (1 < D₄ < D₃);

D₅ - константа, определяющая наличие или отсутствие функциональных ограничений (1 - наличие ограничений, 0 - отсутствие ограничений);

D₆ - константа, определяющая характер экстремальной задачи (0 - задача минимизации, 1 - задача максимизации);

D₇ - константа, определяющая величину уменьшения рабочих шагов при градиентном поиске (D₇ ≈ 0,005 ÷ 0,01).

2.2. Процесс случайного поиска

2.2.1. Поиск оптимальных значений показателей начинается с исходной точки поиска  с координатами ХО (J, I) и значением критериальной функции .

2.2.2. Величина случайного k-го шага поиска определяется выражением

                                                                 (3)

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

 - значение случайного k-го приращения вектора-аргумента.

2.2.3. Величина случайного k-го приращения вектора-аргумента определяется выражением

                                                                   (4)

где  - q мерный вектор длины шага поиска  = (α₁₁, α₁₂, ..., α_1kм; α₂₁, ..., α_ji, ..., α_lkm);

α_ji - длина шага поиска по j, i-й координате.

При этом α_ji определяется выражением

                                        (5)

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

 = (ξ₁₁, ξ₁₂, ..., ξ_1kм; ξ₂₁, ..., ξ_ji, ..., ξ_lkm),

где ξ_ji - случайное нормированное значение j, i координаты, равномерно распределенной в интервале [-1, 1]. При этом ξ_ji определяется выражением

                                                             (6)

где  - случайное число, равномерно распределенное в интервале [-1, 1], получаемое методом функциональных преобразований случайных чисел , случайно распределенных в интервале [0, 1] в соответствии с выражением

                                                                 (7)

2.2.4. Размерность векторов  и  определяется выражением

                                              (8)

при этом

                                             (9)

                                         (10)

2.3. Проверка случайного шага поиска на экстремальность

2.3.1. Проверка случайного шага поиска на экстремальность осуществляется путем проверки неравенств

 (при минимизации),

                                 (11)

 (при максимизации),

где  - текущее значение критериальной функции на k-ом шаге поиска;

 - оценка экстремального значения критериальной функции, найденной за (k - 1) шагов поиска.

2.3.2. Если соответствующее неравенство выполняется, то осуществляется операция присвоения

                                                 (12)

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

2.4. Процесс направленного поиска

2.4.1. Направленное приращение вектора-аргумента определяется выражением

                                                     (13)

где d_N - число направленных шагов.

Если d_N = 1, то

                                                        (14)

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

2.4.2. Если число удачных направленных шагов d_N > NS, то осуществляется увеличение коэффициента роста направленного приращения вектора-аргумента

D₃ = D₃ · DN.                                                              (15)

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

2.4.4. Если число d_N > 1, то после неудачного шага осуществляется обратный направленный шаг, значение которого определяется выражением

                                                      (18)

Если d_N = 1 обратный направленный шаг не осуществляется и начинается градиентный поиск.

2.5. Процесс градиентного поиска

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

2.5.2. Статистическая оценка градиента осуществляется двумя способами:

- если число оптимизируемых показателей невелико (q ≤ 10), то оценка градиента осуществляется методом центральной пробы по формуле

                                             (17)

где  - вектор значений пробных шагов;

 - вектор координатных орт;

- если число оптимизируемых показателей велико (q > 10), то оценка градиента осуществляется методом непарных проб относительно среднего

                                     (18)

при этом

                              (19)

где  - случайные значения вектора-аргумента, равномерно распределенные в пространстве оптимизируемых переменных, ограниченного по каждой координате интервалом [-g, g].

Величина g определяется выражением

                                           (20)

2.5.3. Величина градиентного шага по каждой координате определяется выражением

                                         (21)

Здесь

                      (22)

Величина константы α равна -1 при решении задачи минимизации критериальной функции и +1 при решении задачи максимизации критериальной функции.

2.5.4. После первого неудачного градиентного шага осуществляется процедура оценки положения экстремума в области  относительно точки пространства, определяемого координатами вектора .

Данная процедура основывается на принципах дихотомии и состоит из следующих операций:

- определения нового значения приращения путем деления пополам приращения Δd_r

                                                          (23)

где d_g - порядковый номер процедуры дихотомии;

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

                                                       (24)

Если ΔQ < 0 (для задачи минимизации), то  и повторяется операция деления  относительно нового значения .

Если ΔQ > 0 то значение вектора  пересчитывается и операция деления  осуществляется относительно исходного значения .

Данная процедура оценки положения экстремума прекращается после того, как выполнится условие

                                                 (25)

2.6. Итеративный пересчет коэффициентов масштаба зоны поиска

2.6.1. Изменение коэффициентов масштаба зоны поиска осуществляется после выполнения неравенства

K8 > N1,                                                              (26)

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

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

                                                    (27)

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

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

2.6.2. Остановка поиска осуществляется при выполнении одного из двух неравенств

K > NN, AMIN > S₃,                                                        (28)

где К - общее число случайных шагов поиска;

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

2.7. Выходные данные

2.7.1. Выходными данными алгоритма являются:

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

СХ (J, I) - массив оптимальных значений показателей (переменных), соответствующих конечному значению экстремальной оценки критериальной функции.

Кроме этого на печать выводятся все исходные данные.

2.8. Блок-схеме алгоритма поиска оптимальных значений показателей приведена в рекомендуемом приложении 1.

2.9. Примеры использования алгоритма поиска оптимальных значений показателей приведены в справочном приложении 2.

ПРИЛОЖЕНИЕ 1

Рекомендуемое

БЛОК-СХЕМА АЛГОРИТМА ПОИСКА ОПТИМАЛЬНЫХ ЗНАЧЕНИЙ ПОКАЗАТЕЛЕЙ

Примечание. На схеме применены следующие условные обозначения:

LS - индекс счетчика числа удачных шагов поиска;

LM - индекс счетчика числа неудачных шагов поиска;

КЗО - индекс счетчика числа исходных точек поиска;

Dr - индекс переменной, определяющей факт проведения расчета градиента (1 - проведение расчета градиента, 0 - непроведение расчета градиента).

 

ПРИЛОЖЕНИЕ 2

Справочное

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

Пример 1.

1. Определить значения управляющих воздействий u_j(К), (где К - число шагов оптимизации), оптимизирующих процесс изменения показателей П_i(К) (i - индекс типа показателей) производственного контура подсистемы управления качеством (УК).

2. Рассматривается упрощенный вариант модели управления, состоящий из двух подпроцессов:

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

- контроля поддержания качества изделия при гарантийной эксплуатации.

Предполагается, что приложение управляющих воздействий возможно лишь в первом подпроцессе (j = 1).

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

Требуется найти оптимальное управление {u₁(К), К = 2, 3, ..., N - 1} (N - число интервалов оптимизации) при ограничениях u₁(К) > 0; u₁(1) = 0;  и соответствующую ему траекторию вида

максимизирующее критерий качества управления J = П₂(N) и удовлетворяющее начальным условиям П₁(2) = 0,9; П₂(2) = 0,9 и ограничениям П₁(N) ≤ 0,999; П₂(N) ≤ 0,999, N = 7.

4. Данная задача относится к задачам динамического программирования с критерием качества регулирования, зависящим лишь от конечного состояния.

5. Результат поиска приведен в табл. 1.

Таблица 1

При этом  = 0,098.

6. Решение данной задачи методом, основанным на принципе максимума, имеет следующий вид

п₁(7) = 0,999; п₂(7) = 0,960 при

Пример 2.

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

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

2. Математически задача состоит в нахождении вектора , максимизирующего критериальную функцию вида

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

где N - число типов изделий;

SSW_i - эффект от реализации одного мероприятия по изделию i-го типа;

 - заданные значения нижних и верхних границ количества мероприятий по изделию i-го типа;

NR - количество лимитирующих ресурсов;

 - величина потребного годового фонда j-го ресурса;

q_ji - нормы расхода j-го ресурса при проведении мероприятий по i-му изделию;

QQ_j - величина наличного фонда ресурсов j-го вида.

3. В рассматриваемом примере N = 6, NR = 9.

Нормы расхода соответствующих ресурсов q_ji и величины QQ_j в условных единицах приведены в табл. 2.

Таблица 2

4. Значения эффекта от реализации одного мероприятия по изделию i-го типа в условных стоимостных единицах приведены в табл. 3.

Таблица 3

Оптимальный вариант мероприятий, обеспечивающих максимальный суммарный эффект от их реализации Q = 7725,212 условных стоимостных единиц, приведен в табл. 4.

Таблица 4

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

Пример 3.

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

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

0 ≤ х₁ ≤ 20; 0 ≤ х₂ ≤ 20.

2. Данная функция имеет 12 экстремумов.

Глобальный экстремум Q_гл = 6,990 при х₁ = 4,405 и х₂ = 0.

Найденная оценка глобального экстремума  = 6,992 при  = 4,399 и  = 0,002 (время поиска t ≈ 2 с).

Пример 4.

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

Q = 75,196 - 3,8112 · х₁ + 0,12694 · х₁² - 2,0567 · 10^-3 · х₁ + 1,0345 · 10^-5 · х₁⁴ - 6,8306 · х₂ + 0,030234 · х₁ · х₂ - 1,2813 · 10^-3 · х₂ · х₁² + 3,5256·10^-5 · х₂ · х₁³ - 2,266 · 10^-7 · х₂ · х₁⁴ + 0,25645 · х₂² - 3,4604 · 10^-3 · х₂³ + 1,3514 · 10^-5 · х₂⁴ -  - 5,2375 · 10^-6 · х₁ · х₂² - 6,3 · 10^-8 · х₁³ · х₂² + 7 · 10^-10 · х₁³ · х₂³ + 3,4054 · 10^-4 · х₁ · х₂² - 1,6638 · 10^-6 · х₁ · х₂³ - 2,8673·ехр(0,0005х₁х₂)

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

2. Найденная оценка глобального экстремума  = 6,728 при  = 45,631 и  = 51,638.

Время поиска t ≈ 14 с.

 

СОДЕРЖАНИЕ