22 февраля 2016г.
Разработка новых методов решения оптимизационных задач приводит к необходимости пересмотра результатов сравнительного анализа методов по быстродействию. В работе [2] представлен генетический алгоритм решения частично целочисленной задачи линейного программирования (ЧЦЗЛП). Кроме того приведены результаты статистического эксперимента, который заключался в сравнительном анализе генетического алгоритма с методом ветвей и границ. Но следует заметить, что в настоящее время ведутся исследования метода декомпозиции Бендерса, который принадлежит к тому же классу методов, что и рассматриваемые в [2]. Проведем эксперимент и сравним по скорости решения метод декомпозиции Бендерса [1], генетический алгоритм, метод ветвей и границ. Целью сравнительного анализа является ранжирование указанных методов по быстродействию. Для сравнения трех методов используются результаты работы программных реализаций генетического алгоритма, метода ветвей и границ из [2]. Для проведения сравнительного анализа трех методов необходимо было разработать программу на основании метода декомпозиции Бендерса. Программные реализации разрабатывались применительно к ЧЦЗЛП. Рассмотрим постановку этой массовой задачи (1):
10.
Конец
Сравнительный анализ методов проводился
на множестве из трех задач, описанных в электронном каталоге Miplib. Рассматривались задачи "Bell 3a", "lseu" и "p0033", постановка которых в формате
mps дана в каталоге Miplib [3]. Указанное множество
характеризуется диапазоном
размерностей задач от 33 до 133 переменных, диапазоном количества
ограничений от 49 до 256 и диапазоном количества
целочисленных переменных от 33
до 89.
Результаты
работы методов приведены в Табл. 1.
Снимались показания времени решения методами
каждой задачи, а также фиксировалось найденное
значение целевой
функции.
Таблица 1
|
Наименование задачи
|
|
Метод ветвей и границ
|
Генетический алгоритм
|
Метод декомпозиции Бендерса
|
Оптимальное значение целевой функции
|
|
Bell 3a
|
Время решения, мин.
|
60,356
|
36,03
|
11,33
|
878430,32
|
|
Найденное значение целевой функции
|
1458726,68
|
945512,438
|
1770182,476
|
|
lseu
|
Время решения, мин.
|
120
|
37
|
2,79
|
1120
|
|
Найденное значение целевой функции
|
1441
|
1120
|
1017
|
|
p0033
|
Время решения, мин.
|
0,532
|
0,853
|
0,014
|
3089
|
|
Найденное значение целевой функции
|
3089
|
3164
|
3107
|
Примечание. В работе Хоролич производилось 10 запусков
метода ветвей и границ для задачи
"Bell 3a", что потребовало 36214 секунд.
На решение одной задачи в среднем
затрачено 
Список литературы
1. Схрейвер А. Теория линейного и целочисленного программирования / А. Схрейвер, Москва, 1991, Т.2. – С. 602-604.
2. Хоролич Г.Б. Эволюционные алгоритмы решения задач
смешанной целочисленной оптимизации / Г.Б. Хоролич, Красноярск, 2002. – 164 с.
3.
http://miplib.zib.de/miplib3/miplib3/bell3a.mps.gz
