Апостериорный анализ качества эвристических алгоритмов для приближенного решения двух задач минимизации энергозатрат в сетях сбора и передачи данных

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

Область применения: Моделирование работы сетей сбора и передачи данных, оценка качества функционирования.

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

Используемые алгоритмы: 

- 2 авторских эвристических алгоритма для приближенного решения задачи максимизации времени жизни беспроводной сенсорной сети в условиях заданного множества покрытий [1].

- жадный алгоритм для приближенного решения задачи максимизации времени жизни беспроводной сенсорной сети в условиях заданного множества покрытий [1].

- алгоритм Прима для построения остовного дерева минимального веса.

- авторский метод локальных улучшений для приближенного решения задачи построения оптимального коммуникационного дерева [2].

- генетический алгоритм для приближенного решения задачи построения оптимального коммуникационного дерева.

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

 В программе реализовано:

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

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

1. Файл Exp1.exe. Пользователь указывает любое число комбинаций параметров {n, m, d, r1, r2}, где n - число сенсоров, m - число покрытий, d - шаг регулярной решетки для построения покрытий, r1 и r2 - границы, в пределах которых для каждого сенсора случайно определяется ресурс. Кроме того, пользователь задает количество испытаний (случайных тестовых примеров) с одной комбинацией параметров. В ходе работы программы в файле Exp1_results.txt для каждой комбинации параметров записываются результаты численных экспериментоов: средняя по всем испытаниям относительная точность приближенных алгоритмов (AR(CPLEXR), AR(GREED), AR(H1), AR(H2)), среднеквадратичное отклонение относительной точности (S(CPLEXR), S(GREED), S(H1), S(H2)), а также средняя доля покрытых узлов (Covered), среднее количество сенсоров в одном покрытии (NbSensInCov) и среднее количество покрытий, содержащих один и тот же сенсор (NbCovInSens). В текстовый файл Exp1_time.txt записывается среднее время работы каждого алгоритма и время, затрачиваемое на создание модели для каждой комбинации параметров.
2. Файл Exp2.exe. Пользователь сначала выбирает режим работы программы: запуск серии испытаний с заданной размерностью, либо запуск CPLEX и генетического алгоритма с принудительной остановкой через указанное время. Затем пользовтель может задать произвольное число вариантов размерностей задачи, количество испытаний с одной размерностью, а также, в случае, если выбран второй режим работы программы, произвольное число вариантов времени принудительной остановки алгоритмов. Общие результаты вычислений - относительная точность или оценка относительной точности, и время работы алгоритмов GA_LI (гибридный генетический алгоритм с локальными улучшениями), GA_R (генетический алгоритм со случайной мутацией), T1 (остовное дерево минимального веса), T2 (остовное дерево минимального веса для специальных весов), LI (применение процедуры локальных улучшений к лучшему из деревьев T1 и T2) - записываются в виде текстового файла Exp2_results.txt:, результаты решения каждого тестового примера записываются в виде одной строки в файле Exp2_log.txt.

Функциональные возможности:

• Первая программа (файл Exp1.exe) работает с любой комбинацией входных параметров в пределах: 25 < n < 1000, 5 < m < 100, 0 < d < 100, 1 <= r1 <= r2 <= 100.
• Вторая программа (файл Exp2.exe) работает с размерностью n от 10 до 500. При этом точное решение задачи строится пакетом CPLEX только при n < 40.

Используемые в работе алгоритмы опубликованы в статьях:

[1] Ерзин А.И., Плотников Р.В. О максимизации времени функционирования сенсорных сетей при ресурсных ограничениях // Дискретный анализ и исследование операций, Т. 18, №6, 2011, 17-32.

[2] Ерзин А.И., Плотников Р.В., Шамардин Ю.В. О некоторых полиномиально разрешимых случаях и приближенных алгоритмах для задачи построения оптимального коммуникационного дерева. Дискретный анализ и исследование операций, Т. 20, № 1, 2013, с.12-27.

Инструментальные средства создания - Microsoft Visual Studio 2008 (язык C++), IBM ILOG CPLEX