Please enable JavaScript.
Coggle requires JavaScript to display documents.
Стохатические модели - Coggle Diagram
Стохатические модели
-
Теория перколяции
Задача о протекании
Пусть есть прямоугольная решетка, состоящая из N*N свободных и занятых узлов.
Пусть вероятность того, что узел занят – p, и, соответственно, вероятность того, что узел свободен (1-p).
Будем называть кластером соседние занятые узлы и стягивающим кластером (перколяционным кластером) такой кластер, который начинается на одной границе и заканчивается на противоположной границе решетки.
-
Метод Монте-Карло
- Задать значение вероятности занятости узла p.
- Разыграть состояние каждого узла при заданном значении p, тем самым построив конкретную реализацию решетки.
- Определить, есть ли в этой реализации хотя бы один стягивающий кластер. Если есть, то увеличить счетчик числа стягивающих кластеров Mc на единицу.
- Повторить пункты 2-3 M раз.
- Получить оценку вероятности образования стягивающего кластера
- Повторить 1-5 для ряда значений вероятности p в интервале от 0 до 1.
Источники задач
Физика (исторически первый источник) – задачи просачивания жидкостей в пористой среде; некоторые задачи, связанные с проводимостью.
-
-
Другие области - для описания возникновения связных структур в случайных средах (кластеров), состоящих из отдельных элементов.
Порог перколяции
Порог pᶜ перколяции – доля занятых узлов, при которой возникает перколяционный кластер.
-
-
Модели дендритов
Кабельная теория Ролла - множество предположений и результатов, которые относятся к распространению и взаимодействия электрических сигналов в дендритных деревьях.
Основы кабельной теории - математический анализ затухания сигнала в трансатлантическом телефонном кабеле между Америкой и Англией
два морфологически идентичных дендритных дерева, но с различными электрическими свойствами, могут иметь совершенно разные вычислительные характеристики.
Теория клеточных автоматов
-
Основная особенность: возможность одновременного (параллельного) изменения состояния всей системы, в то время как каждый участок системы взаимодействует только со своими непосредственными соседями. Это свойство позволяет при моделировании связать события, происходящие на микроуровне, с изменениями макроуровневого моделируемого объекта.
Автоматы
Если состояние системы в произвольный момент времени характеризуется лишь ее предыдущим состоянием и набором правил, регламентирующих ее переход, то она называется автоматом.
Клеточные автоматы широко применяются для моделирования систем, в которых важную роль играет пространственное взаимодействие между элементами.
В физике, например, клеточные автоматы применяются для анализа явлений переноса (теплопроводности, диффузии и вязкости) и моделирования твердого тела.
-
-
Вероятностные правила
Такие клеточные автоматы называются стохастическими. В таких системах задается вероятность, что на следующем шаге клетка сменит свой цвет на другой.
Криптография
-
-
-
В этом случае односторонняя функция является результатом эволюции конечного клеточного автомата, первоначальное состояние которого сложно найти.
По заданному правилу легко найти результат эволюции клеточного автомата, но очень сложно вычислить его предыдущие состояния.
Тьюрмит - это машина Тьюринга, которая имеет ориентацию в пространстве, текущее состояние и «ленту», состоящую из бесконечного двухмерного массива ячеек.
В настоящее время для сборки устройств из отдельных молекул используют атомно-силовой микроскоп, но это ручная и очень непроизводительная работа. Если же удастся создать молекулярный аппарат типа тьюрмита, он сможет по командам своего "мозга" быстро строить нужные молекулярные структуры.
Модель изинга
Модель Изинга - математическая модель статистической физики, предназначенная для описания намагничивания материала.
Пусть рассматриваются N спинов σi, i=1, 2,... на решетке, каждый может быть направлен либо вверх, либо вниз:
Каждый спин взаимодействует с внешним полем H:
Спины, ближайшие друг к другу также взаимодействуют
Параллельно выстраиваться спинам "выгодно" - этому соответствует энергия -J, J>0(b)
Антипараллельные спины энергетически невыгодны - на образование каждой такой пары требуется положительная энергия +J
Энергия
-
Фазовый переход
Пусть H=0 (нет выделенного направления в пространстве - симметричный случай). Энтропия пытается разупорядочить спины, но параллельные состояния более энергетически выгодны.
-
При малых T перебарывает энергия:
В пограничной точке - точке Кюри Tc - имеет место фазовый переход.
Генетические алгоритмы
Законы живого мира
-
Естественный отбор
среди генетически различающихся особей одной и той же популяции выживают и оставляют потомство только наиболее приспособленные к окружающей среде.
-
-
Терминология
Ген (свойство, знак, детектор) – атомарный элемент генотипа (набор хромосом, характеризует особь)
-
-
Аллель – значение конкретного гена, определяющее свойство организма
Генотип - набор хромосом, характеризует особь
Фенотип – набор внешних свойств, соответствующих данному генотипу. В формализме ГА фенотип – декодированная из хромосом структура, описывающая реальные параметры задачи.
-
Базовые принципы
А. Имеется некоторая задача, ее решение – новое знание, которое является логическим следствием значений параметров, описывающих данную задачу.
Б. В ГА обрабатываются не сами параметры задачи, а их закодированная форма в виде хромосом.
В. На множестве хромосом определяется целевая функция приспособляемости, оценивающая уровень приспособленности д/каждой хромосомы.
Г. Решение задачи ищется в закодированном виде, обладающих наиболее высокими значениями целевой функции приспособляемости.
Д. При поиске решения используется только целевая функция без ее производных и какой-либо другой дополнительной информации.
Е. Поиск решения происходит не из одной точки (хромосомы), а из некого их множества.
Ё. Порождение нового поколения хромосом осуществляется на основе вероятностных механизмов выбора, а не детерминированности.
Стандартный ГА
Операторы
Селекция – метод рулетки
Оператор скрещивания – одноточечное
-
Сравнительная эффективность
-
локальные методы – метод Ньютона, градиентного спуска, алгоритм Гаусса
-
Применение
-
-
Разнообразные задачи на графах (задача коммивояжера, раскраска, нахождение паросочетаний)
-
-
-
-
-
-
-
-
-