Разработки СО РАН - каталог программ

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

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

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

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

- 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

Назначение - цифровое голографическое восстановление и цифровая голографическая интерферометрия по реальным цифровым голограммам.

Область применения - цифровая голография, цифровая голографическая микроскопия, оптическая физика.

Используемый алгоритм - метод преобразования Френеля, метод свёртки, метод фильтрации высоких частот для подавления нулевого порядка дифракции, метод цифровой голографической интерферометрии.

На вход программы подается файл изображения с голограммой, полученной цифровым путем. При помощи выбранного метода по голограмме восстанавливается изображение объекта, который был записан на этой голограмме. В основе методов восстановления лежит численное решение интеграла Френеля-Кирхгофа [1]. В методе преобразования Френеля используется разложение части подынтегрального выражения в ряд Тейлора и приведение интеграла к преобразованию Фурье. В методе свёртки интеграл Френеля-Кирхгофа рассматривается как интеграл Дюамеля и решается при помощи функционального и математического анализа. Перед голографическим восстановлением осуществляется дополнительная обработка голограммы с целью подавления нулевого порядка дифракции для улучшения качества результата [2]. Для этого используется адаптивный частотный фильтр. Для реализации цифровой голографической интерферометрии используются 2 голограммы. Разница между их численными восстановлениями по фазе позволяет восстановить трёхмерную деформационную модель по всей видимой поверхности измеряемого объекта [3].

1. Рябухо, В. П. Когерентно-оптические методы в измерительной технике и биофотонике: Учебное пособие / В. П. Рябухо, В. В. Тучин. – Саратов: Сателлит, 2009. – 127 с.
2. Kreis, T. Suppression of the dc term in digital holography / T. Kreis, W. Juptner // Optical Engineering. – 1997. – Vol. 36. – P. 2357-2360.
3. Schnars, U. Direct phase determination in hologram interferometry with use of digitally recorded holograms / U. Schnars // JOSA A. – 1994. – Vol. 11(7). – P. 661-665.

Функциональные возможности - цифровое голографическое восстановление реальных голограмм двумя методами с подавлением нулевого порядка дифракции при различных параметрах восстановления (длина волны, расстояние восстановления, угол отклонения опорного пучка, физический размер пикселя в голограмме и др.)

Инструментальные средства создания - Microsoft Visual Studio 2012, С++

Работа с программой - в приложенном архиве располагается программа для OC Windows в виде исполняемого файла (папка redist) и в виде исходного кода (папка src). Для запуска программы необходимо запустить файл Holo.exe или примеры (run_experiment1.bat и run_experiment2.bat). В папке redist также можно найти подробное руководство по работе с программой (Руководство.pdf).

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

Область применения: Программа может быть использована в курсе общей физики, при изучении курса оптики в старших классах. 

Используемый алгоритм:  В программе использован алгоритм расчета кардинальных элементов и постоянных Гаусса матричным методом [1].

[1] Матвеев А. Н. Оптика // М.: Высшая школа, 1985.- 351 с. 

Описание работы программы: 

1. После запуска программы пользователь указывает следующие входные параметры: фокусные расстояния и положение падающих лучей, а также толщину и радиусы кривизны линз, если осуществляется построение для сферической линзы .

2. Программа осуществляет построение линз по введенным параметрам.

3. Программа строит начальный луч.  

4. Учитывая толщину, радиусы кривизны и материал линзы, рассчитываются постоянные Гаусса и кардинальные элементы.

5. Программа находит точку фокуса и строит прошедший луч.

6. Построение производится в специальном окне программы.   

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

Инструментальные средства создания: Среда программирования Delphi 7.0