§ 4.5. Адаптация в процессах восстановления числовых таблиц [294, 295]

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

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

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

Рассмотрим сначала простейший случай, когда Тогда в таблице (4.5.1) имеется один пропуск на месте элемента а. Для восстановления значения элемента матрица А разделяется на три части: где — матрица размерности полученная из матрицы (4.5.1) после вычеркивания строки и столбца:

вектор-столбец матрицы (4.5.1) без элемента

вектор-строка матрицы (4.5.1) без элемента

Значение тогда будет равно оценке неизвестного элемента

где — решающее правило такой оценки.

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

где — -мерный вектор вида

или в форме

где — -мерный вектор вида

Искомая оценка определяется как линейная экстраполяция опорной последовательности по Для этого образуем вектор

где , а множество состоит из номеров, подбираемых по признаку близости в соответствии с выбранной мерой — например, евклидовой:

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

В зависимости от величины возможны два режима работы алгоритма.

1. . В этом случае вектор параметров

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

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

2. . Здесь для определения параметров необходимо ввести дополнительную информацию в виде гипотезы о близости и (4.5.10), т. е. в виде той же меры минимум которой дает возможность определить искомые параметры Л.

Для этого следует решить задачу минимизации:

где

а Л есть решение задачи минимизации.

Теперь оценка искомого экстраполируемого значения очевидна:

где — решение системы (4.5.13) или задачи (4.5.15). В этом и состоит решающее правило в выражении (4.5.5). Далее рассмотрим общий случай: Построим функцию невязки таблицы А и ее поэлементной экстраполяции в виде суммы

где — оценка экстраполированного значения изложенным способом (4.5.16); — унимодальная неотрицательная функция, например а в местах соответствующих пропусков таблицы А стоят параметры вектора

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

где — решение этой задачи — оценки значений неизвестных элементов; — заданная ранее матрица интервалов изменения элементной таблицы А. Выбор метода оптимизации для решения задачи (4.5.18) зависит, очевидно, от характера функции (4.5.17)

Для анализа поведения невязки (4.5.17) решались следующие модельные задачи. Модель представляла собой матрицу (4.5.1) с заданной избыточностью. Избыточность моделировалась простейшей линейной зависимостью строк матрицы (4.5.1) следующим образом: первые строк матрицы были независимы, они заполнялись целыми случайными числами с равномерным распределением в интервале [0; 9], а остальные строк представляли собой линейные комбинации независимых строк, т. е.

где — целые случайные числа с равномерным распределением в интервале [0; 9]. Ранг такой матрицы, очевидно, равен числу линейно-независимых строк, т. е.

Пример Функция невязки (4.5.17) для данного примера представлена на рис. 4.5.1. Хорошо видно, что она имеет экстремальный характер, причем ее минимум соответствует истинному значению восстанавливаемого элемента. Любой локальный метод однопараметрической оптимизации этой функции обеспечит точное восстановление утраченного элемента таблицы.

Рис. 4.5.1. Функция невязки линейно-зависимой таблицы Минимум:

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

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

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

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

Таблица 4.5.1

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

Для решения задачи (4.5.8) в таких условиях необходимо применять глобальный поиск [116] — например, поиск со сглаживанием (см. § 3.6).

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

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

Рис. 4.5.2. (см. скан) Функция невязки линейно-зависимой таблицы со стохастическим возмущением: а — при малой стохастичности , б - при большой стохастичности в.

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

Таким образом, применение метода многомерной линейной экстраполяции в сочетании с процедурой параметрической

Рис. 4.5.3. (см. скан) Линии равного уровня функции невязки линейно-зависимой модельной таблицы при

оптимизации дает возможность достаточно точно восстанавливать элементы избыточной матрицы.

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

Рис. 4.5.4. (см. скан) Линии равного уровня функции невязки линейно-избыточной модельной таблицы с параметром стохастичности

(кликните для просмотра скана)

рис. 4.5.5, А, Б. Сглаживание вводилось на базе четырех случайных измерений:

где — величина области сглаживания; — реализация: единичного случайного вектора, равномерно распределенного а пространстве параметров . В качестве алгоритма поиска был использован адаптивный случайный поиск с «возвратом»:

где величина шага а уменьшалась в два раза после пяти неудачных шагов (и возвратов).

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

Рис. 4.5.6. (см. скан) Поведение сглаженного значения минимизируемой функции при восстановлении таблицы для двух начальных условий. Сплошная линия — процесс А, пунктир — процесс Б (см. рис. 4.5.5).

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

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