close

Вход

Забыли?

вход по аккаунту

?

Сравнительный анализ двухэтапного алгоритма с методом последовательных уступок.

код для вставкиСкачать
Известия ТРТУ
Тематический выпуск
Л.И. Замкова
СРАВНИТЕЛЬНЫЙ АНАЛИЗ ДВУХЭТАПНОГО АЛГОРИТМА
С МЕТОДОМ ПОСЛЕДОВАТЕЛЬНЫХ УСТУПОК
Рассмотрим методы решения двухкритериальной задачи о рюкзаке (рис. 1).
n
∑ l i ⋅ y i → max;
i =1
n
∑ ri ⋅ y i → min ;
i =1
n
∑ ri ⋅ y i ≤ D ;
i =1
y ∈ {0 ,1} i = 1, 2 ,..., n .
i
Рис. 1. Задача о рюкзаке
n
∑ l i ⋅ y i → max ;
i =1
n
∑ ri ⋅ y i ≤ D ;
i =1
y i ∈ {0 ,1} i = 1, 2 ,..., n ,
Рис. 2. Однокритериальная
задача о рюкзаке
Автором разработан двухэтапный алгоритм (ДЭА) решения двухкритериальной задачи о рюкзаке. Этот метод решения предполагает последовательную оптимизацию. Сначала определяется множество оптимальных решений по первому
критерию. Причем векторы этого множества могут различаться по значению второго
критерия. Среди решений, оптимальных по первому критерию, выбирается наименьшее по значению второго критерия. Оно является решением двухкритериальной
задачи о рюкзаке. Таким образом, двухкритериальная постановка сводится к нахождению множества оптимальных решений однокритериальной задачи о рюкзаке
(рис. 2), а затем выбору элемента этого множества, минимального по ограничению. ДЭА подробно представлен в работе [1].
В литературе [2] рассматривается метод последовательных уступок (МПУ).
Суть этого метода применительно к двухкритериальной задаче о рюкзаке заключается в максимизации главного первого критерия, а затем при заданной уступке от
оптимального значения главного критерия производится минимизация второго
критерия. Таким образом, двухкритериальная задача о рюкзаке разбивается на две
последовательно решаемые однокритериальные задачи.
n
L( y ) = ∑ l i ⋅ y → max
i
i =1
R ( y )≤ D
y ∈ {0,1} i = 1, 2,..., n
i
где
30
n
R ( y ) = ∑ r ⋅ y → min
i i
i =1
⎛ *⎞−∆
⎟
⎝ ⎠
L ( y ) ≥ L⎜ y
R( y ) ≤ D
y ∈ {0,1} i = 1, 2,..., n
i
y* – оптимальное решение первой задачи, L(y*) – оптимальное значение целевой функции в точке y* при решении первой задачи, ∆ – уступка (возможное отклонение от оптимального значения L(y*) первого критерия при
решении второй задачи).
Раздел I. Информационные системы в управлении
Обозначим через y** оптимальное решение второй задачи. Оно же будет
являться решением исходной двухкритериальной задачи о рюкзаке. Заметим, что
первая задача решается методом функциональных уравнений динамического программирования [3]. Этот метод определяет L(y*). Вторая этапная задача решается
методом отсечений Гомори [4]. Ее решением является вектор y**.
На основе методов созданы программы на языке C++ в среде Builder 4.
Сравнивалось быстродействие в секундах программных реализаций на процессоре
Celeron 2,6 ГГц. В методе последовательных уступок задавалась нулевая уступка
∆=0. При этом программы выдавали оптимальное решение индивидуальной двухкритериальной задачи о рюкзаке. Рассматривалась выборка из 50 задач размерности n=50. Программы тестировались на следующем контрольном примере:
3000 ⋅ y1 + 1000 ⋅ y 2 + 10000 ⋅ y 3 + 6000 ⋅ y 4 + 4000 ⋅ y 5 + 500 ⋅ y 6 +
+ 800 ⋅ y 7 + 300 ⋅ y8 + 900 ⋅ y 9 + 1000 ⋅ y10 → max
2300 ⋅ y1 + 2500 ⋅ y 2 + 1900 ⋅ y 3 + 1600 ⋅ y 4 + 200 ⋅ y 5 + 3050 ⋅ y 6 +
+ 2555 ⋅ y 7 + 2405 ⋅ y8 + 2055 ⋅ y 9 + 4000 ⋅ y10 → min
2300 ⋅ y1 + 2500 ⋅ y 2 + 1900 ⋅ y 3 + 1600 ⋅ y 4 + 200 ⋅ y 5 + 3050 ⋅ y 6 +
+ 2555 ⋅ y 7 + 2405 ⋅ y8 + 2055 ⋅ y 9 + 4000 ⋅ y10 <= 2000
y i ∈ {0,1} i = 1, 2,...,10.
Для этой задачи множество допустимых решений очевидно:
(0010000000)
(0001000000)
.
(0000100000)
(0001100000)
Оптимальное решение данной индивидуальной задачи выбирается среди
допустимых: (0001100000). Это решение МПУ выдал за 0,047 секунд, а ДЭА – за
0,031 секунду. Оптимальное значение первого критерия – 10000, а второго – 1800.
Результаты эксперимента приведены в табл. 1.
В среднем для 50 запусков время работы МПУ обозначим SМПУ, а время работы ДЭУ – SДЭУ. Рассчитанные по таблице значения SМПУ ≈0,2493 и SДЭУ ≈0,2355.
Тогда вычисления по формуле
S
⋅ 100% S ДЭУ ⋅ 100%
МПУ
−
≈ 5,54%
S
S
МПУ
МПУ
показывают, что МПУ в среднем работает на 5,54 % медленнее, чем ДЭУ. Исходные данные для опытных задач выбирались случайным образом. На основании
вышеизложенного можно сделать вывод, что ДЭУ несколько эффективнее МПУ.
31
Известия ТРТУ
Тематический выпуск
Таблица 1
№ МПУ, ДЭА,
№ МПУ, ДЭА,
№ МПУ, ДЭА,
опыта сек.
сек. опыта сек.
сек. опыта сек.
сек.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
0,282
0,297
0,234
0,235
0,250
0,234
0,233
0,235
0,266
0,233
0,234
0,218
0,219
0,250
0,235
0,298
0,219
0,250
0,297
0,219
0,234
0,250
0,219
0,219
0,219
0,234
0,219
0,219
0,203
0,203
0,218
0,219
0,297
0,203
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
0,219
0,218
0,235
0,235
0,219
0,219
0,235
0,268
0,250
0,235
0,328
0,234
0,281
0,312
0,250
0,235
0,264
0,203
0,204
0,219
0,218
0,203
0,203
0,218
0,234
0,219
0,219
0,359
0,265
0,281
0,312
0,203
0,234
0,250
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
0,260
0,219
0,251
0,312
0,251
0,297
0,266
0,250
0,219
0,251
0,235
0,251
0,250
0,233
0,265
0,249
0,203
0,203
0,219
0,312
0,218
0,297
0,250
0,250
0,218
0,219
0,234
0,219
0,250
0,250
0,235
0,234
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Замкова Л.И. Разработка программной системы эффективной оплаты счетов / Известия
ТРТУ. № 6. 2005.
2. Подиновский В.В., Гаврилов В.М. Оптимизация по последовательно применяемым критериям. 1975.
3. Данциг Дж. Линейное программирование его обобщения и приложения. 1966.
4. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. 1985.
Э.М. Котов, Ю.А. Целых
РЕАЛИЗАЦИЯ ЗАДАЧИ СЕМАНТИЧЕСКОГО АНАЛИЗА
В ИНФОРМАЦИОННО-ПОИСКОВЫХ СИСТЕМАХ
Существующие на сегодняшний день технологии информационного поиска
не обеспечивают эффективной реализации поисковых систем в связи с отсутствием сложившихся подходов к реализации задачи семантического анализа текстовой
информации [1]. И в существующих поисковых системах традиционно реализуются три задачи лингвистического анализа текстовой информации. А именно:
1. Лексический анализ – задача восприятия текста.
2. Морфологический анализ – задача выявления значения слов.
3. Синтаксический анализ – задача выявления значения членов предложения.
Все это, в свою очередь, обуславливает низкую адекватность выдаваемой в
результате поиска информации, причем в больших объемах. Т.е. информационнопоисковые системы (ИПС) реализуют автоматическую индексацию большого количества документов, но им не присуще наличие развитых средств искусственного
интеллекта для экспертной оценки смыслового содержания информации. И представляется целесообразным применение аппарата «интеллектуального поиска»,
что позволит осуществить автоматизацию всех этапов лингвистического анализа.
32
Документ
Категория
Без категории
Просмотров
5
Размер файла
257 Кб
Теги
анализа, последовательного, уступом, методов, алгоритм, двухэтапного, сравнительный
1/--страниц
Пожаловаться на содержимое документа