Новости

На данной странице представлен каталог программ, включенных в Фонд алгоритмов и программ Сибирского отделения РАН. Полный каталог программ и БД, включенных в Фонд, а также любые выборки по научным центрам, объединенным ученым советам и др. вы можете найти на данной странице.

2019-12-30

Параллельная программа расчёта надёжности сети. Версия №2.

Назначение – программа предназначена для точного расчета надежности сети с использованием на суперЭВМ с распределённой памятью.

Область применения - анализ надёжности и живучести сетей различного назначения

Необходимость в расчёте и оценке показателей надёжности возникает, прежде всего, при структурной оптимизации сетей, как на этапе проектирования, так и при расширении существующих структур. При этом задача точного расчёта надёжности сети с NP-трудна, поэтому без использования суперЭВМ точно вычислить надёжность можно, как правило, только для сетей с количеством элементов около сотни.

Данная программа позволяет осуществлять параллельный точный расчёт надёжности сетей с ненадёжными каналами связи, под надёжностью понимается вероятность связности всех узлов сети. Распараллеливание расчёта основано на известном методе факторизации (ветвления, Мура-Шеннона), соответствующий алгоритм опубликован в [1]. По сравнению с первой версией программы оптимизированы параметры, повышающие масштабируемость программы. Рост производительности является линейным вплоть до 1000 вычислительных ядер. Однако, для структур разной плотности возможны разные оптимальные значения параметров [1].

Входные данные программы – структура сети в виде графа, значения надёжности каналов связи (т.е. вероятности их присутствия).

Выходные данные программы – значение надёжности сети, время расчёта.

Программа работает с представлением графов при помощи полного файла предшественников (списки KAO,FO). Информация в файле должна располагаться следующим образом: первая строка – количество вершин, вторая строка – количество рёбер, третья и четвёртая строка – списки представления графа (элементы списка разделяются запятыми).

[1] Denis A. Migov. Parallel Methods for Network Reliability Calculation and Cumulative Updating of Network Reliability Bounds // Proceedings of the IEEE 3rd Russian-Pacific Conference on Computer Technology and Applications. 2018. P. 1-5. (DOI: 10.1109/RPC.2018.8482197)

Функциональные возможности – расчёт надёжности сетей с количеством элементов в несколько сотен.

Инструментальные средства создания – C++, MPI .

Алгоритм разработан в рамках гранта РФФИ № 18-07-00460

2019-12-29

Метод расстановки стоков для повышения надёжности сбора информации в сети с ненадёжными элементами. Версия №2

Назначение - оптимизация сетей различного назначения с целью повышения надёжности.

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

Используемый алгоритм - генетический алгоритм. Программа позволяет для заданной структуры сети с ненадёжными вершинами определить оптимальное количество необходимых стоков (узлов, предназначенных для сбора информации с остальных) и их расстановку. Предполагается, что стоки могут быть размещены в узлах сети. Для каждого узла сети задаются значения надёжности и стоимости установки стока в этом узле. Под надёжностью сети понимается вероятность связности заданной доли (Т) узлов с каким-либо из стоков. Этот показатель подробно описан в статье [1], наряду с методом его расчёта. Алгоритм расстановки представлен в работе [2].

[1] D. Migov, V. Shakhov. Reliability of Ad Hoc Networks with Imperfect Nodes // Springer Lecture Notes in Computer Science (in MACOM 2014). Vol. 8715, 2014, p. 49-58. (http://link.springer.com/chapter/10.1007%2F978-3-319-10262-7_5)

[2] Волжанкина К.А., Мигов Д.А. Генетический алгоритм размещения стоков в беспроводной сенсорной сети с ненадёжными узлами для повышения вероятности успешного мониторинга // Материалы Межд. конференции "Актуальные проблемы вычислительной и прикладной математики", Новосибирск, 2019. Новосибирск: ИВМиМГ СО РАН, 2019, стр. 328-332.

Поиск ведётся в условиях наперёд заданных ограничений.

Входные данные программы: структура сети в виде графа, пример входных данных предоставлен в сопутствующих файлах (массивы KAO FO или полный файл предшественников), значения надёжности для всех узлов связи (числа от 0 до 1), параметры генетического алгоритма (размер популяции, кол-во поколений, размер турнира, вероятность мутации), количество устанавливаемых узлов, Т - доля узлов сети, которые должны быть связны с каким-либо из стоков, условия остановки алгоритма: количество поколений, ограничение на время работы алгоритма и стагнация (задаётся количество поколений, в которых вырождается решение).

Инструментальные средства создания - Delphi.

Алгоритм разработан в рамках гранта РФФИ № 18-07-00460.

2019-12-27

Оптимизация расписания работы светофорных объектов в условиях городского трафика

Назначение - установление оптимальных значений длин фаз на светофорных объектах в городской транспортной сети.
Область применения - оптимизация и увеличение эффективности транспортной сети мегаполисов.
Используемый алгоритм - в основе программы лежит эвристический алгоритм роя частиц, позволяющий осуществлять эффективный поиск решений с малой или нулевой относительной погрешностью. Для определения качества получаемых решений используется пакет микросимуляционного моделирования SUMO.
Функциональные возможности - расчет длин фаз и сдвигов фаз для заданного участка городской транспортной сети. Размерность решаемых задач - до 50 светофорных объектов (до 5 фаз на каждом СО).
Инструментальные средства создания - среда разработки VisualStudio 12.0, язык программирования C#, микросимуляционный пакет SUMO

2019-06-18

Программа для кластеризации конформационных состояний аминокислотных остатков и фрагментов полипептидной цепи (пептидов) по значениям торсионных углов (Condense)

Назначение - Программа Condense предназначена для кластеризации наборов конформационных состояний аминокислотных остатков и/или фрагментов полипептидной цепи (пептидов) по значениям торсионных углов. На вход программы подается специальным образом структурированная информация о величинах торсионных углов аминокислот/пептидов.

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

Дополнительно можно выводить все элементы, попавшие в данный кластер.

Область применения - молекулярная динамика белков и пептидов, структурная биология
Используемый алгоритм - метод невзвешенного попарного центроидного усреднения (невзвешенный центроидный метод, UPGMC ). В этом методе расстояние между двумя кластерами определяется как расстояние между их центрами тяжести (Sneath, P. H., & Sokal, R. R. (1973). Numerical taxonomy. The principles and practice of numerical classification).
Функциональные возможности - результатом кластеризации являются центральные структуры кластеров и, в зависимости от параметров, полный список элементов кластера. Программа была использована для анализа подвижности пентапептидов методом молекулярной динамики (Nekrasov, A.N., Alekseeva, L.G., Pogosyan, R.А., Dolgikh, D.A., Kirpichnikov, M.P., de Brevern, A.G. and Anashkina, A.A., 2019. A minimum set of stable blocks for rational design of polypeptide chains. Biochimie, 160, pp.88-92). Возможен анализ до 10000 пространственной структур пептидов и фрагментов полипептидных цепей.
Инструментальные средства создания - языкеС++

Алгоритм разработан в рамках выполнения работ по теме "Фундаментальные проблемы математического моделирования" Программы № 43 фундаментальных исследований Президиума РАН по стратегическим направлениям развития науки, грант «Математическая модель пространственной организации природных полипептидных цепей на основе информационного контента первичной структуры»

Программа запускается командой condense *.ang *.out

где ang-файл содержит блоки информации, содержащие значения торсионных углов, описывающие конформации, которые будут подвергнуты кластеризации.

out-файл содержит результаты кластеризации.

Параметры, определяющие режимы работы программы, задаются в файле condense.cfg

Во вложении - файл с инструкцией по использованию программы readme_condense.doc

2019-03-29

Гибридный алгоритм для задачи распределения бункерных накопителей

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

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

Dolgui A., Eremeev A.V., Sigaev V.S. HBBA: hybrid algorithm for buffer allocation in tandem production lines // Journal of Intelligent Manufacturing.–– 2007. –– Vol. 18, no. 3. –– P. 411––420.

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

Входные данные - файл с описанием линии

Выходные данные - файл с параметрами найденного решения.

Инструментальные средства создания - Lasarus