НАУКА и ОБРАЗОВАНИЕ

А. И. Дивеев, канд. техн. наук, "ВЦ РАН"

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

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

Введение

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

Задача дискретной оптимизации относится к классу труднорешаемых задач, т. е. допускает нахождение решения в общем случае только с помощью экспоненциальных алгоритмов, которые строятся на основе свойств целевой функции и ограничений. Наиболее эффективный метод поиска оптимального решения — это метод последовательного анализа и отсеивания вариантов [1—3], который является развитием метода "ветвей и границ" для задачи дискретной оптимизации с рекурсивно-монотонными функциями. Метод позволяет по анализу некоторого числа вариантов отсеивать большее число, последовательно уменьшая множество вариантов до размеров, удовлетворительных для использования прямого перебора.

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

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

Постановка задачи. Рассматривается следующая задача дискретной оптимизации:

                              (1)

                   (2)

где

Целевая функция f₀(x) является неубывающей, , если .

Введем определения и обозначения: X — множество вариантов;, — множества значений;  — допустимое множество, ,  — решение задачи (1), (2);

.

Метод последовательного анализа и отсеивания вариантов. Неубывающий характер целевой функции f₀(x) придает задаче (1), (2) свойство, позволяющее отсеивать бесперспективные варианты, не проверяя все множество X.

Если Допустим , но тогда  что невозможно.

Следовательно, .

На основании данного свойства построим алгоритм, позволяющий уменьшить мощность множества вариантов X.

Шаг 0. .

Шаг 1. .

Шаг 2. .

Шаг 3. Если , то .

Шаг 4. Если  то  и переходим на шаг 2.

Шаг 5. Если , то  и переходим на шаг 1, иначе находим  прямым перебором и завершаем вычисления.

В алгоритме на шаге 5 величина M определяет значение мощности множества вариантов, при котором вычислительные средства допускают применение прямого перебора. Для персональных компьютеров с тактовой частотой около 100 МГц величина М ≈ 10⁵.

На шаге 3 алгоритма выполняется проверка всех значений множеств , и отсеивание бесперспективных значений, не входящих в оптимальное решение. Всего за одну итерацию на шаге 3 выполняется не более  проверок, что значительно меньше мощности множества вариантов . Если удается отсеять одно значение из множества X_i, 1≤i≤n, то это приведет к уменьшению мощности множества вариантов X в m_i / (m_i-1) раз.

Для задач большой размерности алгоритм может привести к зацикливанию. Так как на шаге 3 проверяется не более, чем q вариантов, то имеем соответственно q значений функции f₀(x). Упорядочим все значения f₀(x). Вполне возможен случай, когда два соседних значения отличаются между собой настолько, что для параметра F*, находящегося между этими значениями, исключаются все допустимые варианты, а если параметр F* больше наибольшего из этих двух значений, то не исключается ни один вариант. Так как по конструкции алгоритм не позволяет получить промежуточное значение функции f₀(x), то наступает зацикливание вычислительного процесса.

Для исключения зацикливания необходимо увеличить число проверяемых вариантов на шаге 3. Такую возможность предоставляет метод трансформации.

Метод трансформации. Трансформацией множества называется любое его преобразование, не изменяющее его мощности.

Рассмотрим трансформацию множества вариантов X. Пусть  — базовое множество, элементами которого являются множества значений. Произведем разбиение базового множества .Построим новые множества значений , где , и новое множество вариантов .

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

Трансформация приводит задачу (1), (2) к следующему виду:

                      (3)

            (4)

К трансформированной задаче (3), (4) также может применяться алгоритм метода последовательного анализа и отсеивания вариантов, причем мощность множества вариантов при этом не изменяется, , а мощности некоторых множеств значений будут увеличены, так как h < n. Поэтому при проверках на отсеивание число проверяемых вариантов увеличивается, что позволяет исключить варианты, не отсеиваемые в исходной задаче.

В трансформированной задаче (3), (4) P(Y)  Y— допустимое множество, .

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

При получении повторного зацикливания в трансформированной задаче (3), (4) преобразование трансформации можно повторить. Каждый раз при выполнении трансформации мы будем получать взаимно однозначные отображения, по которым сможем восстановить оптимальное решение. Обозначим  композицию отображений после p трансформаций: . Тогда  — тождественное отображение . Обозначим также  композицию обратных отображений.

При неоднократном трансформировании множество вариантов в пределе будет одномерным (h=1) и полностью совпадать с множеством значений (Y= Y₁) В этом случае проверка метода последовательного анализа будет представлять собой поиск оптимального решения методом прямого перебора. Такой пошаговый переход в алгоритме к прямому перебору позволяет полностью исключить зацикливание.

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

Шаг 0. .

Шаг 1. .

Шаг 2. .

Шаг 3. .

Шаг 4. Если  то .

Шаг 5. Если  то  и переходим на шаг 3.

Шаг 6. Если , то k = k + 1, иначе переходим на шаг 8.

Шаг 7. Если k > K, то выполняем трансформацию , переходим на шаг 1.

Шаг 8. Если , то 7 = 7 и переходим на шаг 2, иначе находим оптимальное решение y⁰ прямым перебором вариантов в .

Первоначально в алгоритме на шаге 1 выполняется тождественная трансформация . Момент зацикливания определяется на шаге 7. Выполнение условия k > K указывает, что проверка на отсеивание на шаге 4 выполнялась более K раз и при этом не было отсеяно ни одного варианта. Практически при K = 10 выполнение условия на шаге 7 указывает на наступление зацикливания.

Алгоритм использовался при обработке базы данных элементов в задаче выбора оптимального варианта сложного электронного изделия по критерию стоимости с ограничением по надежности.

Список литературы

1. Волкович В. Л. Волошин А. Ф. Об одной схеме метода последовательного анализа и отсеивания вариантов // Кибернетика. 1978. № 4. С. 98-105.

2. Северцев Н. А. Дивеев А. И. Оптимальный выбор варианта технического изделия // Проблемы машиностроения и надежности машин / РАН. 1995. № 5. С. 3—8.

3. Дивеев А. И. К проблеме выбора варианта технической системы с монотонными параметрами // Проблемы машиностроения и надежности машин / РАН. 1996. № 4. С. 14—19.

4. Дивеев А. И., Северцев Н. А. Метод трансформации в схеме последовательного анализа и отсеивания вариантов // Труды международной конференции "Вопросы оптимизации вычислений (BOB-XXVII)". Киев, 6-8 окт., 1997 г. С. 94-97.

ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ, № 6, 1998

МЕТОДЫ ОПТИМИЗАЦИИ

Ключевые слова: Дискретная оптимизация, зацикливание, трансформация множества, разбиение множества.