Двухфазная эволюция - Dual-phase evolution

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

Вступление

Двухфазная эволюция (DPE) - это процесс, который способствует возникновению крупномасштабного порядка в сложные системы. Это происходит, когда система многократно переключается между различными типами фаз, и на каждой фазе различные процессы воздействуют на компоненты или соединения в системе. DPE возникает из-за свойства графики и сети: лавина связности, которая возникает в графах по мере увеличения количества ребер.^[2]

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

Механизм DPE

Следующие функции необходимы для выполнения DPE.^[1]

Базовая сеть

DPE возникает там, где система имеет базовую сеть. То есть компоненты системы образуют набор узлов, и есть соединения (ребра), которые их соединяют. Например, генеалогическое древо - это сеть, узлами которой являются люди (с именами), а ребрами - отношения, такие как «мать» или «в браке». Узлы в сети могут принимать физическую форму, такую ​​как атомы, удерживаемые вместе атомными силами, или они могут быть динамическими состояниями или условиями, такими как позиции на шахматной доске с ходами игроков, определяющими края.

В математическом плане (теория графов ), граф ${\displaystyle \textstyle G=\langle N,E\rangle }$ это набор узлов ${\displaystyle \textstyle N}$ и набор ребер ${\displaystyle \textstyle E\subset \{(x,y)\mid x,y\in N\}}$. Каждый край ${\displaystyle \textstyle (x,y)}$ обеспечивает связь между парой узлов ${\displaystyle \textstyle x}$ и ${\displaystyle \textstyle y}$. Сеть - это граф, в котором значения присваиваются узлам и / или ребрам.

Фазовые сдвиги

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

В Модель Эрдеша – Реньи показывает, что случайные графы испытывают лавину связности по мере увеличения плотности ребер в графе.^[2] Эта лавина представляет собой внезапное изменение фазы в размере самого большого связного подграфа. Фактически, граф состоит из двух фаз: связной (большинство узлов связаны путями взаимодействия) и фрагментированной (узлы либо изолированы, либо образуют небольшие подграфы). Их часто называют Глобальный и местный фазы соответственно.

Фрагментированный граф.

Связанный граф.

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

Выбор и вариация

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

Системная память

Эффекты изменений в одной фазе переносятся на другую фазу. Это означает, что процессы, действующие на каждой фазе, могут изменять или уточнять шаблоны, сформированные на другой фазе. Например, в социальной сети, если человек заводит новые знакомства во время глобальной фазы, то некоторые из этих новых социальных связей могут выжить и в локальной фазе, чтобы стать постоянными друзьями. Таким образом, DPE может создавать эффекты, которые могут быть невозможны, если оба процесса действуют одновременно.

Примеры

Было обнаружено, что DPE встречается во многих естественных и искусственных системах.^[3]

Социальные сети

DPE может создавать социальные сети с известной топологией, в частности сети малого мира и безмасштабные сети.^[3]Сети малых миров, которые являются обычным явлением в традиционных обществах, являются естественным следствием чередования местный и Глобальный фазы: новые междугородные связи формируются на глобальной фазе, а существующие связи усиливаются (или удаляются) на локальной фазе. С появлением социальных сетей уменьшилось сдерживающее влияние, которое пространство, которое использовалось для создания социальных сетей, привело к тому, что время стало главным сдерживающим фактором для многих людей.

Чередование локальных и глобальных фаз в социальных сетях происходит в самых разных формах. Некоторые переходы между фазами происходят регулярно, например, ежедневный цикл людей, перемещающихся между домом и работой. Это изменение может повлиять на изменение общественного мнения.^[4] В отсутствие социального взаимодействия принятие мнения, продвигаемого СМИ, является Марковский процесс. Эффект социального взаимодействия при DPE заключается в том, чтобы замедлить начальное поглощение до тех пор, пока преобразованное число не достигнет критической точки, после чего потребление быстро ускоряется.

Социоэкономика

Модели DPE социально-экономической теории интерпретируют экономику как сети экономических агентов.^[5] В нескольких исследованиях изучается, как развивается социоэкономика, когда DPE действует в разных частях сети. Одна модель^[6] интерпретировал общество как сеть занятий с жителями, соответствующими этим занятиям. В этой модели социальная динамика становится процессом DPE внутри сети с регулярными переходами между фазой развития, во время которой сеть приходит в состояние равновесия, и фазой мутации, во время которой сеть трансформируется случайным образом путем создания новые занятия.

Другая модель^[7] интерпретировали рост и снижение социально-экономической активности как конфликт между кооператорами и перебежчиками. Кооператоры образуют сети, ведущие к процветанию. Однако сеть нестабильна, и вторжения перебежчиков периодически фрагментируют сеть, снижая благосостояние, до тех пор, пока вторжения новых кооператоров не восстанавливают сети снова. Таким образом, процветание рассматривается как двухэтапный процесс, в котором чередуются высокодоходные, взаимосвязанные фазы и неблагополучные, фрагментированные фазы.

Экология леса

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

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

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

Алгоритмы поиска

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

Такие проблемы, как оптимизация обычно можно интерпретировать как нахождение самого высокого пика (оптимума) в пространстве возможностей поиска. К задаче можно подойти двумя способами: местный поиск (например. скалолазание ) включает отслеживание пути от точки к точке и постоянное движение «в гору». Глобальный поиск включает в себя выборку из самых разных точек в пространстве поиска, чтобы найти высокие точки.

Многие алгоритмы поиска включают переход между фазами глобального поиска и локального поиска.^[3] Простой пример - Алгоритм Великого потопа в котором ищущий может перемещаться по ландшафту в произвольном порядке, но не может заходить в низменные области, которые затоплены. Поначалу ищущий может свободно бродить, но повышение уровня воды в конечном итоге ограничивает поиск определенной территории. Многие другие алгоритмы, вдохновленные природой, используют аналогичные подходы. Имитация отжига обеспечивает переход между фазами с помощью графика охлаждения. В клеточно-генетический алгоритм размещает решения в псевдопейзаже, в котором они размножаются только с местными соседями. Прерывистые катастрофы очищают участки, переводя систему в глобальную фазу до тех пор, пока пробелы не будут снова заполнены.

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

Связанные процессы

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

Рекомендации

1. Грин, Д.; Лю, Дж. & Аббасс, Х. (2014). Двухфазная эволюция: от теории к практике. Берлин: Springer. ISBN  978-1441984227.
2. Эрдеш, П. & Реньи, А. (1960). «Об эволюции случайных графов» (PDF). Публикации Математического института Венгерской академии наук. 5: 17–61.
3. Паперин, Г.; Грин, Д. & Садедин, С. (2011). «Двухфазная эволюция в сложных адаптивных системах» (PDF). Журнал интерфейса Королевского общества. 8 (58): 609–629. Дои:10.1098 / rsif.2010.0719. ЧВК  3061102. PMID  21247947.
4. Стокер, Р.; Корнфорт, Д. & Грин, Д. (2003). «Моделирование воздействия СМИ на социальную сплоченность». Достижения в сложных системах. 6 (3): 349–359. Дои:10.1142 / S0219525903000931.
5. Гудман, Дж. (2014). «Доказательства экологического обучения и специфики предметной области в рациональной оценке активов и рыночной эффективности» (PDF). Социально-экономический журнал. 48: 27–39. Дои:10.1016 / j.socec.2013.10.002.
6. Сюй, Г.; Ян, Дж. & Ли, Г. (2013). «Моделирование переходных процессов в обществе: застой, крах и рост в развивающейся сетевой модели». PLOS ONE. 8 (9): e75433. Bibcode:2013PLoSO ... 875433X. Дои:10.1371 / journal.pone.0075433. ЧВК  3783390. PMID  24086530.
7. Кавальер, М.; Седвардс, К.; Tarnita, C.E.; Новак, М.А. & Чикаш-Надь, А. (2012). «Процветание связано с нестабильностью в динамических сетях». Журнал теоретической биологии. 299: 126–138. arXiv:1102.4947. Дои:10.1016 / j.jtbi.2011.09.005. ЧВК  3298632. PMID  21983567.
8. Грин, Дэвид Г. (1994). «Связность и сложность экологических систем». Тихоокеанская биология сохранения. 1 (3): 194–200. Дои:10.1071 / PC940194.
9. Грин, Дэвид Дж. (1982). «Огонь и стабильность в послеледниковых лесах юго-запада Новой Шотландии». Журнал биогеографии. 9 (1): 29–40. Дои:10.2307/2844728. JSTOR  2844728.