VII Международная студенческая научная конференция Студенческий научный форум - 2015

В рамах курсовой работы авторами поставлена задача разработки программы для моделирования эффекта перколяции с различными дополнительными возможностями (возможность выбора исходных опций, поиск протекающего кластера, расчет порога перколяции и т.д.) в соответствии с основными этапами разработки жизненного цикла программного обеспечения[1].

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

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

Рис.1. Пример перколяции в электрической цепи [2].

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

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

На этапе анализа предметной областибыло изучено несколько алгоритмовкластеризции: «k-средних», «с-средних», алгоритм «выделения связных компонент»[3]. Эти алгоритмы реализуются довольно просто и часто используются при кластеризации небольших данных, но если применить их к большой перколяционной решетке, то будет затрачиваться значительное время.

Полжив время исполнения ключевым критерием реализации проекта, выбор пол на алгоритм Хошена-Копельмана, использующий многократную маркировку кластеров. При представлении перколяционной решетки в виде массива требуется пройти по ней лишь дважды: первый раз происходит расстановка первичных меток, проверка их на ложность, и, соответственно, запись истинного значения для каждой ложной клетки(рис.2а), второй раз ложные метки заменяются на соответствующие им истинные(рис.2б)[4].

Рис.2. Перколяционная конфигурация на квадратной решетке 7x7 с применением алгоритма  Хошена-Копельмана[4].

Для моделирования была выбрана ячеечная перколяция в квадратной решетке 12х12 по одной из сторон по двум причинам:

1)                    Рациональное соотношение «удобность-эффективность-наглядность». Квадратную решетку в программе очень удобно представить в виде двумерного массива, с которым можно эффективно работать. Так же ее можно наглядно изобразить с помощью таблицы.

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

Одним из требований к выполнению курсовой работы являлось использование объектно-ориентированного языка С#: с его помощью реализовывается программа, а так же библиотека, которую при желании пользователь может расширять.

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

Основой продукта является библиотека классов, в которой с помощью нескольких методов реализуется алгоритм и генерируются входные данные. Визуальное представление было возложено на WindowsForm, где происходит вывод данных через DataGridView, а так же осуществляется связь с пользователем.

На рис.3 приведена исходная решетка, в которой «0» соответствует пустой клетке, «1» - заполненной. Задача программы: поиск и маркировка кластеров - совокупностей соседних хотя бы по одной стороне заполненных клеток.

Рис.3. Создание исходной решетки.

Генерирование исходных данных осуществляется при нажатии кнопки ‘createtablet', а также элемента trackbar, который отвечает за заполняемость таблицы. По умолчанию значение зафиксировано на 50% (это значит, что вероятность заполнения каждой из клеток ровно 50%). Пользователь может установить нужный ему уровень, чтобы получить требуемый результат.

Создание исходной таблицы было реализовано следующим способом: значение элемента trackBar(от 0.00 до 1.00) соответствует вещественной переменной ProbValue; при заполнении каждой следующей клетки таблицы генерируется случайное вещественное число, принадлежащее полуинтервалу [0, 1) и сравнивается со значением ProbValue. Если ProbValue больше, то в клетке ставится 1, в противном случае 0. Таким образом достигается случайное расположение заполненных клеток, а заполняемость можно регулировать.

Результат отображается в левом элементе DataGridView с подписью ‘soursetablet' (рис.3), а также дублируется в правый элемент для удобства динамческого просмотра - сравнения таблиц до и после применения алгоритма.

Реализация алгоритма Хошена-Копельмана выполняется при нажатии кнопки ‘markclusters' - происходит обработка исходной таблицы, полученной в шаге 1. В соответствии с алгоритмом, маркировку кластеров можно условно поделить на 2 этапа:

1)                     Первичная маркировка. Сохранение ложных значений и соответствующих им истинных.

Изначально создается массив из Nэлементов, где N - максимальное кол-во кластеров в исходной решетке (N = LxL/2, где L - кол-во элементов на 1 стороне). В этом массиве индекс соответствует номеру кластера, и значение элемента по индексу - его метке: если значение 0, то истинная метка равна индексу(так как нулем помечаются только пустые клетки), если значение отлично от 0, это говорит о том, что в это метка ложная, а истинное значение - это значение элемента массива по этому индексу.

Последовательно пробегая по каждой клетке таблицы, проверяется значение клетки (повторю, считаем, что 0 - пустая клетка, 1 - заполнена) - пропускаем пустые клетки, так как они не являются объектом кластеризации, а заполненные маркируем следующим образом:

• если соседние клетки (считаем те, у которых индекс стоки или ряда на 1 меньше, чем у текущей) пустые, то присваиваем текущей клетке номер счетчика, счетчик инкрементируем.
• если одна из соседних клеток не пустая, то, проверив массив ложных меток присваиваем текущей клетке значение соседа, если эта метка отсутствует в массиве, и верную метку-значение, которое хранится в этом же массиве, если сосед обнаружен в ложном массиве.
• если обе соседних клетки заполнены, то текущей клетке присваивается значение наименьшей метки из соседей, наибольшая при этом отправляется в массив ложных меток, где помечается, что верное значение данной метки равно значению метки наименьшего из соседей. Стоит отметить, что наименьший из соседей так же подвергается проверке на нахождение в массиве ложных меток (если он там обнаруживается, то текущей клетке присваивается верное значение, которое находится в этом же массиве).

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

2)                     Вторичная маркировка. Исправление ложных меток на истинные.

Последний шаг (последняя маркировка) заключается в том, что вновь пробегая по каждой клетке уже маркированной единожды мы проверяем, является ли эта метка ложной. Проверяем массив истинных/ложных меток: по индексу, соответствующему текущей метке ячейки вызываем элемент массива. Если значение элемента по данному индексу равно нулю, тогда метка истинная. Если отлично от нуля, то присваиваем ячейке это значение элемента массива по индексу. На выходе получаем правильно маркированную таблицу(рис.4).  

Рис.4 - Маркированная таблица.

Разработанное приложение имеет простой интерфейс (рис.5), пока лишь базовую реализацию, которая в рамках курсовой работы будет расширена дополнительным функционалом.

Рис.5. Интерфейс разработанного приложения.

Созданная пользовательская библиотека будет расширятся, в ближайших планах добавить методы нахождения и выделения протекающего(-их) кластера(-ов), возможности устанавливать пользовательские исходные конфигурации (перколяцонные решетки различных форм,  выбор количества элементов, и т.п.). В дальнейшем планируется попробовать перенести алгоритм Хошена-Копельмана из плоскости в пространство, а так же добавить удобную графическую реализацию (не в таблице).

Список источников и литературы

1.      https://ru.wikipedia.org/wiki/Перколяция - статья, посвященная физическому явлению перколяции, дата обращения 12.02.15

2.      http://thesaurus.rusnano.com/wiki/article1473 - словарная статья, дающая определение и кратко описывающее перколяцию в электрической цепи, дата обращения 2.02.15

3.      http://habrahabr.ru/post/101338/ - статья о алгоритмах кластеризации данных.

4.      Х.Гулд, Я.Тобочник «Компьютерное моделирование в физике: часть 2» - учебное издание, посвященное компьютерному моделированию, где кратко изложен алгоритм Хошена-Копельмана, дата обращения 15.01.15