Информационный сайт

 

Реклама
bulletinsite.net -> Книги на сайте -> Программисту -> Сигал И.Х. -> "Введение в прикладное дискретное программирование " -> 21

Введение в прикладное дискретное программирование - Сигал И.Х.

Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование — М.: ФИЗМАТЛИТ, 2003. — 240 c.
ISBN 5-9221-0377-6
Скачать (прямая ссылка): vvedenievprikladnoeprogrammirovanie2003.djvu
Предыдущая << 1 .. 15 16 17 18 19 20 < 21 > 22 23 24 25 26 27 .. 84 >> Следующая

сю = 3 Xio = 0 39 16 15 18
C5 =4 ж 5 = 0 35 14 13 16
С7 = 4 Ж 7 = 0 31 12 12 13
Ce = 5 Xq = 0 26 10 10 10
С2 = 5 X 2 = 0 21 8 7 9
Cl = 6 Xi = 0 15 6 6 5

Получено решение

Z0 = ( 0;0;0;0;0;0;0;1;1;0), f(z°) = 15,

что существенно хуже решения из табл. 2.8.

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

Общая схема алгоритма локальной оптимизации. Изложим эту схему применительно к общей задаче дискретного программирования на максимум:

/(ж0) = max/(ж),

X Є G, \G\ = Af < оо.

Пусть xk Є G — допустимое решение задачи, где к = 1,2,...
58 Разд. I. Предмет и модели дискретного программирования

Построим окрестность G(xk) С G и найдем

f(xk+1) = max/(ж), х Є G(xk);

затем построим G(xk+1) С G и т.д. Оптимизация в окрестности G(xk) выполняется до первого улучшения или с помощью полного перебора всех элементов окрестности. Оптимизация прекращается, если Xk = = xk+1 при некотором к, либо выполняется одно из условий

f(xk+1)-f(xk)<?, (f(xk+1)-f(xk))/f(xh)<e, где є > 0 — заданная точность. В дальнейшем можно ввести другое определение окрестности и продолжить оптимизацию заново. При этом получается последовательность алгоритмов локальной оптимизации и возникает нетривиальная задача определения наилучшей в заданном смысле последовательности их работы. Постановка задачи определения такой последовательности рассмотрена в гл. 7.

Алгоритмы локальной оптимизации для задачи о ранце. Приведем примеры определения окрестности для задачи о ранце. Пусть Z0 = (z®, Z2 , • • • , ^n) - допустимое булево решение.

1) Пусть z® = 0, zj = 1. Под окрестностью вектора Z0 будем понимать все допустимые векторы, получающиеся из Z0 следующим образом:

z\ — I, Zj= 0, к ф j, Ck — Cj > 0, 1 < к < n, I < j < п.

Алгоритмы, основанные на таком определении окрестности, не изменяют количество единиц в векторе Z0, поэтому «эффективными» не являются.

2) Выберем s > 1 компонент (^i, z®2,..., Z^a) вектора Z0 таких,

5

ЧТО ^2 zI <s- Под окрестностью вектора Z0 будем понимать все

к=1 к

допустимые векторы, получающиеся из Z0 фиксацией всех нулей и единиц на местах ii, г2,..., is’, число рассмотренных при этом булевых векторов равно 2s. Если рассмотреть все наборы по s компонент, то число рассмотренных булевых векторов будет равно 2s • C^1.

2.2.8. Алгоритмы «генетического» типа. Пусть в результате применения описанных выше алгоритмов отобрано t > 1 наилучших по значениям целевой функции различных допустимых векторов Z5 = 1 < S < t. Обозначим множество этих

векторов через Т. Найдем вектор w = (wi,w2,, wn) такой, что

t

Wj=Yz^ І = 1,2,..., п.

Значение Wj можно считать весом переменной Xj. Этот вес указывает
Гл. 2. Модели дискретного программирования

59

количество единиц В значениях переменной Xj в множестве наилучших решений Т.

Упорядочим компоненты вектора Wj по невозрастанию значений: Wj1 > Wj2 > ... > Wjn. Сформулируем третье правило последовательного назначения единиц.

Правило 3. Назначение единичных значений производится в соответствии с указанным выше упорядочением значений Wj.

Если полученный вектор z Є Т, то работа алгоритма на этом заканчивается. Если z ^ T, то вычислим min f(zs) = f(zs°) и рассмотрим два случая: s^t

а) / (Ю < / (^5о)5 в этом случае работа алгоритма окончена;

б) f (z) > f (zs°), в этом случае в множестве T вектор zs° заменяется вектором z, формируется новый вектор w и процесс продолжается.

Вектор z можно улучшить с помощью алгоритмов локальной оптимизации.

2.2.9. Комбинированные эвристические алгоритмы для задачи о ранце. Алгоритм этого типа состоит из двух основных этапов: построение начального решения и улучшение начального решения.

1) Построение начального решения предполагает выполнение всех алгоритмов, описанных в п. 2.2.5, и формирование множества T наилучших решений.

2) Улучшение начального решения состоит из двух основных элементов:

— применение алгоритмов локальной оптимизации;

— применение алгоритмов «генетического типа».

Применение алгоритмов локальной оптимизации предполагает,

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

Применение алгоритмов генетического типа направлено на улучшение множества наилучших решений Т. Если при этом удалось улучшить наилучшее решение из Т, то можно перейти к этапу 1), рассматривая наи лучшее решение в качестве начального.

2.2.10. Экспериментальные исследования системы комбинированных эвристических алгоритмов для приближенного решения задачи о ранце *). Параметры задачи Cj и ац — незави-

*) Вычислительный эксперимент по исследованию алгоритмов приближенного решения задачи о ранце проведен студентами под руководством и при участии авторов.
60 Разд. I. Предмет и модели дискретного программирования
Предыдущая << 1 .. 15 16 17 18 19 20 < 21 > 22 23 24 25 26 27 .. 84 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100