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

Пусть минимизируемая функция Q (х) зависит от небольшого числа переменных (n ≤ 3). В этом случае для решения задачи поиска глобального минимума x* непрерывной функции Q (х), определенной в n-мерном гиперпараллелепипеде Dx = {x|ai ≤ xi ≤ bi , i = 1, 2,…, n}

min Q(x1, x2, …, xn), (6.1)

можно использовать алгоритм F34, реализующий метод многошаговой редукции размерности. Основная идея этого метода состоит в том, что исходная задача (6.1) сводится к последовательности «вложенных одна в другую» одномерных задач глобальной минимизации:

min Q(x) = min min … min Q(x1, …, xn). (6.2)

Например, для функции трех переменных (n=3) можно записать следующим образом:

min Q(x1, x2, x3) = min Q1(x1), (6.3)

Из (6.3) следует, что решение исходной задачи эквивалентно решению задачи минимизации функции одного переменного Q11). Вычисление значения функции Q11) для фиксированного значения x1 сводится к решению задачи одномерной минимизации функции Q2(x1, х2) по переменной х2, а вычисление значения функции Q2(x1, x2) для фиксированных значений переменных х1 и х2 — к решению задачи одномерной минимизации исходной функции по переменной x3.

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

Если через Nk обозначить число испытаний, необходимое для отыскания на интервале [аk, bk] точки глобального минимума одномерной
функции Qk(x1, …, xk) с заданной точностью εk (при фиксированных
значениях переменных x1, …, xk-1), то общие затраты на решение задачи (6.1) будут равны

N = ∏Nk

При одинаковом числе испытаний при одномерном поиске Nk = A, k = — 1, …, n, при увеличении размерности исходной задачи общие затраты на поиск будут расти экспоненциально

N = Аn.

Поэтому многошаговая схема редукции (6.2) становится малоэффективной при большом числе переменных.

Другим недостатком алгоритма является то, что точность εi решения каждой «вложенной» одномерной задачи минимизации должна быть задана заранее. Если значения этих точностей (ε1, …, εn) окажутся недостаточными при оценке конечного результата, то решение исходной задачи по схеме (6.2) придется повторить заново с меньшими значениями εi, i = 1, 2, …, n. Если значения точностей заданы слишком! высокими, то решение исходной задачи (6.1) может прерваться в связи с тем, что исчерпано допустимое число испытаний N. В этом случае полученное приближение

Q(xk) = min Q(xi)

будет соответствовать оценке минимума функции Q(х) в некоторой подобласти множества Dx. Причем может оказаться, что в значительной части области испытания не проводились, хотя в другой ее части определены минимальные значения некоторых из функций Qk(x1,…, xk-1) с заданными точностями εk.

Размерность задачи многомерной минимизации (6.1) может быть повышена до 5—7 переменных за счет использования алгоритма F35, основанного на повторении развертки (кривой Пеано), которая отображает отрезок [0, 1] вещественной оси в гиперпараллелепипед Dx. При этом осуществляется построение однозначного и непрерывного отображения х(v), которое для любой точки v∈[0,1] позволяет получить точку х(v) = (x1(v), …, xn(v))∈Dx:

min Q(x1, …, xn) = min g(v). (6.4)

Таким образом, решение исходной задачи (6.1) эквивалентно поиску точки минимума v* одномерной функции g(v) = Q(x1(v), …, xn(v)) с помощью одного из методов одномерного глобального поиска.

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

Пусть область Dx при помощи линейного преобразования

yi = [2xi — bi — аi]/2 (bi — aii), i =1, 2, …, n,

приведена к n-мерному гиперкубу с единичными ребрами:

Dy= {у| — 0,5 ≤ yi ≤ 0,5, i = 1,2, …, n}. (6.5)

Гиперкуб (6.5) разбивается координатными плоскостями на 22 гиперкубов первого разбиения (m = 1) с длиной ребра, равной 1/2. Полученные гиперкубы нумеруются числами z1 от 0 до (2n — 1) таким образом, чтобы гиперкубы с номерами, различающимися на единицу, имели общую грань. Условимся обозначать гиперкубы первого разбиения через D(z1), где z1 = 2k — 1, k = 0, 1, …, n. Тогда смежные гиперкубы D(z1) и D(z1 + 1) имеют общую грань, если их центры различаются только одной координатой. Первое разбиение гиперкуба Dy для двумерного случая показано на рис. 6.1, а.



Рис. 6.1. Первое разбиение гиперкуба Dy(a) и отрезка [0, 1] (б)

Далее каждый гиперкуб первого разбиения D(z1), в свою очередь, также разбивается плоскостями, параллельными координатным осям и проходящими через его центр, на 2n гиперкубов второго разбиения (m = 2) с длиной ребра равной 1/4. Нумерация полученных гиперкубов проводится по тому же принципу, что и нумерация гиперкубов первого разбиения, с тем отличием, что нулевой гиперкуб второго разбиения, входящий в D(z1), должен иметь общую грань с (2n — 1)-м гиперкубом второго разбиения, входящим в D(z1 — 1). Гиперкубы второго разбиения условимся обозначать D(z1, z2), где z2 = 2k, k = 0,1,…, n, являются номерами гиперкубов второго разбиения, входящих в D(z1). Продолжая указанный процесс, можно получить гиперкубы любого s-ro разбиения (m = s) с длиной ребра (1/2)s которые условимся обозначать D(z1, …, zs). Для обеспечения непрерывности строящегося отображения у(v) необходимо, чтобы при нумерации гиперкубов (j + 1)-го разбиения смежные гиперкубы имели общую грань, а нулевой гиперкуб (j + 1)-го разбиения, входящий D(z1, …, zj-1, zj), должен иметь общую грань с (2n — 1)-м гиперкубом, входящим в D(z1, …, zj-2, zj-1).



Рис. 6.2. Второе разбиение (m = 2) гиперкуба Dy(а) и отрезка [0,1] (б)

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

Теперь рассмотрим процесс деления отрезка [0,1] на 2n равных частей, каждая из которых, в свою очередь, также делится на 2n равных частей и т. д. При этом интервалы каждого j-го разбиения, длина которых равна (1/2)jn, нумеруются слева направо числами zj = 2k — 1, k = 0, 1, …, n, и обозначаются через Δ(z1, …, zj). Например, Δ(z1, z2, z3) означает интервал третьего разбиения с номером z3, входящий в интервал второго разбиения с номером z2, который, в свою очередь, входит в интервал первого разбиения с номером z1. После проведения
s-ro разбиения длина интервала Δ(z1, …, zj) равна (1/2n)s.

При этом интервал Δ(0,0, …, 0) содержит левый конец единичного отрезка, а интервал Δ(2n — 1, …, 2n) — правый конец.

На рис. 6.1, рис. 6.2 и рис. 6.3. приведены соответственно первое, второе и третье разбиения единичного отрезка.



Рие. 6.З. Третье разбиение (m = 3) гиперкуба Dy(а) и отрезка [0.1] (б)

Будем считать, что точка у (v), соответствующая точке v, содержится в гиперкубе D(z1, …, zs), если v принадлежит интервалу Δ(z1, …, zs). Построенное таким образом отображение у (v) является однозначным и непрерывным.


Оставить комментарий





Статистика

Рейтинг@Mail.ru