Численные методы оптимизации многоцелевых систем

6 

7  ЧИСЛЕННЫЕ МЕТОДЫ ОПТИМИЗАЦИИ МНОГОЦЕЛЕВЫХ СИСТЕМ

7.1  ОПТИМИЗАЦИЯ ОДНОМЕРНЫХ МНОГОЦЕЛЕВЫХ СИСТЕМ

Рассмотрим вначале случай, когда внешнее множество X одномерно представляет собой отрезок [a, b] , множество допустимых решений у есть замкнутая область n-мерного Евклидова простран­ства, а функция локальной эффективности _ƒ(x, y) неотрицательна, непрерывна и выпукла по X при любом yY. Тогда области Дирихле элементов m - элементной стратегии А связаны

, j=1,...,m, .

Рассмотрим функцию

представляющую собой оптимальное значение критерия оптимальности многоцелевой системы на отдельной области Дирихле. Ясно, что ее минимальное значение достигается при , причем для ИМС оно всегда равно нулю. Надлежащим преобразованием исходной задачи, не меняющим ее содержания, того же можно добиться и для ГМС. Тогда линия уровня F=0 есть биссектриса , и линии уровня с малыми значениями критерия оптимальности должны быть близки к ней. В частности, если они могут быть аппроксимированы семейством прямых

,

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

а оптимальное значение критерия равно для ГМС

,

для ИМС –

.

В общем же случае F( унимодальна, с минимумом при ,неотрицательна, непрерывна. Тогда

(6.1)

Найдем границы областей Дирихле, минимизи­рующие показатель эффективности F(X, A,E(x)). Легко показать, что для ГМС они удовлетворяют условию:

F(, j=1,...,m, . (6.2)

Если задаться значением C, то из этого условия, решая каждый раз уравнение относительно ξj, можно последовательно найти ξ (С),ξ(С),... и, наконец, (c). Приравнивая его правой гра­нице множества X, мы получаем уравнение относительно С:

(c)=b. (6.3)

Решив это уравнение, можно найти значение Copt, а сле­дом за ним, по (6.2), оптимальные значения границ областей Ди­рихле и компоненты элементов оптимальной стратегии yY, j=1,...,m. Геометрическая иллюстрация показана на рис. 6.1, на который нанесены линии уровня функции . Видно, что гра­фически оптимизация ГМС сводится к отысканию такой линии уровня, когда между этой линией и биссектрисой первого координатного угла можно впи­сать m-ступенчатую лестницу с началом на прямой ξ=a и кон­цом на прямой ξ=b.

Для опти­мальной ИМС можно показать, что

. (6.4)

Аналогично предыдущему, задавшись значением ξ, можно, после­довательно решая (6.4), вычислить ξ(ξ),ξ(ξ),...и, нако­нец, ξm(ξ)=b, т. е. прийти к уравнению относительно ξ, ре­шив которое, можно легко найти остальные границы оптимальных об­ластей Дирихле и саму оптимальную стратегию. Решению (6.4) мо­жет быть дана геометрическая интерпретация, аналогичная рис. 6.1.

6.2.  СВЕДЕНИЕ К ЗАДАЧЕ ЦЕЛОЧИСЛЕННОГО ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Если размерность внешнего множества превосходит единицу, оп­тимизация многоцелевой системы значительно усложняется, так как требуется не только найти оптимальную m - элементную стратегию, но и оптимально разбить на области Дирихле нестрого упорядоченное внешнее множество. Если на отрезке каждая область Дирихле могла быть задана двумя числами - ее границами, то в пространстве боль­шего числа измерений вообще нет унифицированного способа задания областей. Поэтому будем задавать многомерные множества X и Y конечным числом их элементов, т. е. использовать их точечную ап­проксимацию.

Пусть.Метрические свойства функции локальной эффективности в этом случае не так уж и важны, поэтому будем предполагать лишь ее липшицевость

для любых .

Введем m переменных u, i=1,...,m, целочисленных и удовлетворяющих условиям 0≤u≤1, таким образом, эти переменные могут принимать лишь значения 0 и 1. Установим, что если u=0, то точка Y€Y не входит в оптимальную стратегию, а если u=1, то входит. Тогда

( условие, что стратегия содержит ровно m элементов). Введем также nm целочисленных переменных , которые могут принимать значения 0 или1. Если, то будем считать, что точка не входит в область Дирихле элемента i, а если , то входит. Тогда

(условие наличия областей Дирихле лишь у элементов Y, входящих в оптимальную стратегию),

s=1,...,n

(условие покрытия всего множества X системой областей Дирихле).

Миноранта многоцелевой системы L(xs), очевидно, запишется

,s=1,...,n.

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

Для ГМС-

F, s=1,...,n;

, s=1,...,n, i=1,...,m

, s=1,...,n;

, u, i=1,...,m.

Для ИМС:

, s=1,..,n, i=1,...,m;

, s=1,...,n;

.

Эти задачи могут быть решены, например, алгоритмом Гомори, правда, количество переменных в описанных задачах равно m(n+1), что для реальных задач слишком велико.

6.3 ОПТИМИЗАЦИЯ ГАРАНТИРУЮЩЕЙ МНОГОЦЕЛЕВОЙ СИСТЕМЫ МЕТОДОМ ЦЛП

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

Пусть , . Обозначим

(6.5)

Введем булевы переменные - признаки того, включен ли элемент в стратегию A. Тогда число p элементов стратегии A определяется как

. (6.6)

Несколько расширим исходную постановку задачи оптимизации ГМС с учетом следующего обстоятельства. Критерий оптимальности ГМС весьма чувствителен к каждому элементу Y. Поэтому ошибка в определении эффективности хотя бы одного элемента может существенно исказить решение задачи. На практике же такие «выколотые точки» вполне возможны, именно поэтому, например, в математической статистике имеются специальные методы определения и исключения так называемых «грубых ошибок». Необходимо и при оптимизации ГМС предоставить возможность оптимального (по основному критерию) исключения из множества Y определенного числа элементов q. Для этого введем булевы переменные - признаки того, что элемент исключен из рассмотрения.

Тогда

. (6.7)

Введем

. (6.8)

Здесь - гарантированная точность представления множества Y оптимальной m-элементной стратегией в том смысле, что

. (6.9)

Рассмотрим -ю строку матрицы .Если

, (6.10)

это означает, что для данного существует хотя бы один номер такой, что .Соответственно, если

, (6.11)

это означает, что существует такой элемент стратегии A, что . Условие же

(6.12)

тогда означает, что либо элемент исключен из рассмотрения (тогда и (8) выполняется для любой стратегии A), либо в стратегии A существует элемент , «расстояние» от которого до элемента не превосходит .

Выполнение (8) для любых i=1,…,n означает, что для стратегии A

. (6.13)

Теперь можно поставить две взаимные оптимизационные задачи: минимизировать при фиксированном числе p элементов стратегии A и выполнении (6.12) для любых I=1,…,n, а также (6.6) и (6.7), либо минимизировать p при фиксированном и выполнении тех же условий. Предпочтительнее решать вторую задачу, поскольку она является стандартной задачей целочисленного линейного программирования (ЦЛП) всего лишь с n+m булевыми переменными uj, j=1,…,m, vi, I=1,…,n, критерием

(6.14)

и n+1 ограничениями

(6.15)

Перебирая значения единственного параметра и решая для каждого из них задачу ЦЛП, можно получить зависимость при фиксированном q. При этом, очевидно,

. (6.16)

Это позволяет решить первую из взаимных задач – заданному значению p сопоставить оптимальное значение .

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

Таблица 6.1

Номер студента	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
Рейтинг	24	31	23	35	12	25	27	19	27	29	29	26	29	30	23
Номер студента	16	17	18	19	20	21	22	23	24	25	26	27	28	29
Рейтинг	27	25	35	26	38	24	22	25	29	29	22	39	26	20

Расчеты по приведенному выше алгоритму показывают, что при отклонении рейтинга в подгруппе не более чем на единицу (=1) потребуется 7 подгрупп; не более чем на 2 единицы – 6; на 3 единицы – 4 и на 4 единицы – тоже 4 подгруппы. Между тем, если допустить возможность перевода из группы одного студента (q=1), необходимое число подгрупп уменьшается на единицу (переводится студент с наименьшим рейтингом 12), а если допускается возможность перевода трех человек (q=3), то потребное число подгрупп становится еще меньше. Оно приведено во второй строке табл.6.2, где указаны также переводимые студенты для различной величины допустимого отклонения рейтинга в подгруппах.

Таблица 6.2

	Q=3
	1	2	3	4
	5	4	3	2
Номер и рейтинг переводимого студента	Отметка о переводе из группы
4, 35	1		1
5, 12	1	1	1	1
18, 35	1		1
20, 38		1		1
27, 39		1		1

6.4 ОПТИМИЗАЦИИ ГАРАНТИРУЮЩЕЙ МНОГОЦЕЛЕВОЙ СИСТЕМЫ МЕТОДОМ СЕТЕЙ

Укажем вначале теорему общего характера.

Теорема (достаточное условие оптимальности ГМС). Пусть <X, Y,f(x, y)> и <X1,Y, f(x, y)>, где - гарантирующие многоцелевые системы, и

.

Тогда стратегия , оптимальная для ГМС <X1,Y, f(x, y)>, оптимальна и для <X, Y,f(x, y)>.

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

Доказательство. Пусть теорема неверна, т. е. существует допустимая стратегия такая, что . Ввиду того, что множество X1 уже, чем X,

,

что противоречит оптимальности стратегии для ГМС <X1,Y, f(x, y)>.

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

1.  Случайным образом выбирается некоторое подмножество внешнего множества стратегий X.

2.  Для выбранного подмножества алгоритмом ЦЛП находится оптимальная стратегия, которой соответствует некоторое значение критерия оптимальности.

3.  Для найденной стратегии вычисляется значение критерия оптимальности исходной ГМС для всего внешнего множества X. Если оно равно , это означает, что найденная стратегия является решением исходной задачи.

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

,

и процесс повторяется начиная со второго этапа.