Чем отличается сеть и гиперсеть
Перейти к содержимому

Чем отличается сеть и гиперсеть

  • автор:

КЛИЕНТАМ Выбрать населенный пункт
Г. ЧЕЛЯБИНСК (ОПТИКА, Р-Н ЧМЗ)

1.1. Где можно оставит заявку на подключение? Заявку на подключение вы можете оставить:
-Через сайт
-Обратившись в центр продаж по адресу: ул. Свободы, 32 офис 309, 310
-Позвонить по номеру (351) 778-88-88

1.2. Каков срок подключения после заключения договора? Подключение будет осуществлено в течение 5 дней. 1.3. Что делать при некачественном подключении? Не подписывать Акт сдачи-приемки услуг по предоставлению доступа до устранения замечаний, обратиться по телефону, указанному на сайте. 1.4. При подключении техники проведут кабель до моего оборудования или только заведут его в квартиру? Линия прокладывается до оборудования Абонента. В случае, если по квартире Абонента проложен подходящий кабель, линия может быть проложена до входной двери.

2.1. Как настроить VPN для подключения Интернет? Для подключения к Интернет Вам необходимо установить VPN соединение с нашим сервером. Для облегчения этой операции мы сделали подробные инструкции:

2.2. Есть ли порог скачивания? Нет, на всех тарифных планах для физических лиц порог входящего трафика отсутствует. 2.3. Как провести интернет в каждую комнату в квартире? Для того, чтобы провести интернет в каждую комнату в квартире, необходимо устройство под названием маршрутизатор (router). Маршрутизаторы бывают проводными, когда до каждого компьютера необходимо протягивать кабель, и беспроводными, когда можно осуществить подключение при помощи Wi-Fi, не используя лишних проводов. При использовании маршрутизатора для подключения нескольких компьютеров, нужно только одно подключение к сети «ГиперСеть», а это значит вы будете оплачивать только одну абонентскую плату. Нужно учесть, что при таком подключении, скорость вашего тарифного плана будет делиться на все подключенные компьютеры. 2.4. Почему страничка так медленно загружается? Мы обеспечиваем вам скоростное подключение к сети Интернет до нашего центрального узла. Дальнейшее прохождение Вашего запроса и ответа сервера, находящегося, например, в Москве и содержащего нужную Вам страничку, не поддается какому-либо контролю. Возможно, именно сейчас нужный Вам сервер просто не работает. 2.5. Что такое входящий трафик? Чем он отличается от исходящего? Входящий трафик — это информация, поступающая из сетей на Ваш компьютер. Исходящий трафик, соответственно, трансли- руется с Вашего компьютера в сети. Но нужно учитывать, что когда Вы отправляете кому-то письмо или закачиваете информацию на чей-то файловый архив, то определенный процент закаченного объема трафика возвращается на Ваш компьютер (5-10%) — такова особенность протокола ТСР/IP. Это так называемый обратный трафик. 2.6. Что такое Веб-страница? Веб-страница — это небольшой сайт с информацией о компании или частном лице, размещенный на Веб-сервере и доступный другим пользователям с помощью программ, работающих с Интернет (Internet Explorer, Netscape Navigator, Opera). 2.7. Что такое трафик? Трафик — это объём передаваемой по сети информации. Он измеряется в мегабайтах. 2.8. Не увеличивается ночная скорость. Для этого необходимо пере подключиться с Интернет (разорвать и подключить VPN подключение) после 12 часов ночи. Данное ограничение носит технический характер.

4.1. Можно ли перенести номер? Номер можно перенести, но перед этим обязательно уточните техническую возможность установки по новому адресу в контакт центре (351) 778-88-88 4.2. По какой технологии предоставляется услуга? В вашей квартире ставится самая обычная телефонная розетка для аналогового телефона с тоновым набором номера.
Внутри нашей сети для Домашнего телефона мы применяем технологию передачи голоса через IP-сети, как и везде в современной телефонии. 4.3. Как можно отключиться/расторгнуть договор? Для этого необходимо оплатить счёта, которые выставлены вам за услуги связи. Приехать в абонентский отдел, написать заявление на расторжение договора. Со следующего рабочего дня договор будет расторгнут.

ПАМЯТКА ПОЛЬЗОВАТЕЛЯ ПО ОПЛАТЕ УСЛУГ СВЯЗИ

Оплатить услуги связи (интернет или телефон) компании «ГиперСеть» можно с помощью: — платежной системы «Город» — платежной системы «КиберСити» (адреса всех пунктов приема платежей указаны ниже)

ПОМНИТЕ! При балансе 0 рублей пользование услугой интернет не возможно, необходимо пополнить счет

Оплата через систему «Город» производится через: терминалы и банкоматы Челябинска и Челябинской области, операторов в отдельных точках (например, в салонах сотовой связи), отделения «Челябинвестбанка» или в отделениях банков, входящих в систему «Город».

Для оплаты по системе «Город» с помощью терминала, необходимо: ввести адрес установки и выбрать из списка компаний, предоставляющих услуги компанию ГиперСеть.

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

Преимуществом системы «Город» является большое количество точек приема платежей, а также отсутствие дополнительной комиссии. Гарантировано платеж поступит на Ваш счет в течение суток.

Если вы производите оплату услуг в первый раз, то возможна ситуация, когда оператор по вашему адресу не видит компанию «ГиперСеть». Тогда следует попросить оператора добавить нового поставщика услуг, для этого оператору требуется зайти на вкладку «УСЛУГИ СВЯЗИ» и добавить «ГиперСеть» как нового поставщика услуг и далее выбрать услугу «Установка интернет».

Оплата через систему «КиберСити» производится через терминалы.

Для оплаты по системе «КиберСити» необходимо: на панели терминала выбрать раздел «Услуги Интернет», нажать «ГиперСеть» и ввести номер своего лицевого счета (номер ЛС можно узнать у оператора связи «ГиперСеть» по тел.778-88-88) минимальная сумма оплаты от 10 рублей, деньги поступают на Ваш счет в течение нескольких минут

Через терминалы «КиберСити» можно оплатить услуги по системе «Город»: в данном случае взымается дополнительная комиссия 3%, но не менее 10 руб.( если вы производите оплату в размере 10 руб., на счет Вам поступит сумма в размере 5 руб.). Не забывайте также и о том, что терминал не выдает сдачу.

Список адресов терминалов «КиберСити»

г.Челябинск, ул.Кирова, д.11, салон МТС
ул.Кирова,д.11,г.Челябинск,салон МТС
Свердловский пр-т,д.46,г.Челябинск,салон МТС
ул. Университетская набережная, 30А, школа №25
г. Челябинск, ул. Учебная, 5А, Лицей №142 (школа)
г. Челябинск, ул. Дзержинского, 83А, Гимназия №100 (школа)
г. Челябинск, ул. Чичерина, 27Б, Лицей №97 (школа)
г.Челябинск, ЧОУ ВПО ЮУрИУиЭ, ул.Комаровского, 9а,
г. Челябинск, ул.Кожзаводская, 1, ЧОУ ВПО ЮУрИУиЭ
г. Челябинск, ул. 250 летия Челябинску, 65, ДС Кенгуру
г. Челябинск, ул. Бажова (Мамина 1/1), Сибнефть, АЗС №10
г. Челябинск, ул. Кожзаводская (Шенкурская 9/1), Сибнефть, АЗС №4
г. Челябинск, ул. Героев Танкограда, дом № 15/1, АЗС №6 Сибнефть
п.Шершни, ул.Северная, д.40/1, АЗС №5 Сибнефть
( ремонт принтера )г. Челябинск, ул. Харлова , дом № 1/1, АЗС №2 Сибнефть
г. Челябинск, ул. Уральская, 2, школа №108 2
г. Челябинск, ул. Барбюса, 140Б, школа №76
г.Челябинск, ул. Мира, 46, Школа №96
г. Челябинск, ул. Коммунаров, 4, Лицей №37 (школа)
г. Челябинск, пр. Ленина, 54А, МТC
г. Копейск, пр. Победы, 11, МТС
г. Копейск, пр. Славы, 8, МТС
г.Челябинск, ул. Новороссийская 136, Школа №130
г. Челябинск, ул. Горького, 18/1, АЗС Сибнефть
г.Челябинск, ул. Красноармейская, д. 54, Башнефть, АЗС №402
г.Челябинск, ул. Володарского, 20, Школа №30
г. Челябинск, ул. Кирова, 13Б, Лицей №97
ул.Труда,д.62,офис КС,Тест терминал 01
г. Челябинск, ул. Сталеваров, 32,ост.к-с Сквер Победы
г.Челябинск ул.Каслинская, 34.,ост.к-с Островского
( ВС, ПН не раб. ) г. Челябинск, ул. Харлова, 10, п-н Дубликат
г. Челябинск, ул. Дзержинского, 6, м-н Всё для Вас
(без UPS) г. Челябинск, пр. Ленина, 85, Вечерний Челябинск
г. Челябинск, ул. Доватора, 1м, АЗС Башнефть
г. Челябинск, Свердловский пр., 23А, м-н Губернский
г. Челябинск, Троицкий тр., 7, Башнефть, АЗС №100, Экспрес-Маркет
г. Челябинск, пр. Ленина, 83, п-н Стрит-Гриль
с. Миасское, 38,3 км. АД М-51,«Башнефть», АЗС №194
г. Челябинск, М5,17км, АЗС Башнефть ИЗ Челябинска
г. Челябинск, М5,17км, АЗС Башнефть В Челябинск
м-н Продукты ул 250-летия Челябинска 25 г.Челябинск
м-н Продукты ул. Бр.Кашириных 134 А г.Челябинск
п-н Продукты 24 ул. Чичерина 2 г.Челябинск
п-н Продукты 24 ул.С.Юлаева 6 г.Челябинск
м-н Гурман ул. Салавата Юлаева, 23а, г.Челябинск
м-н Продукты ул. пр. Победы 113 г. Челябинск
м-н Хоккей ул. 250-летия Челябинска 25 г.Челябинск
м-н Продукты ул. Комсомольский проспект д. 41б г. Челябинск
м-н Продукты ул.Молодогвардейцев 70 г. Челябинск.
Столовая(авторынок Искра) ул. Шадринская 102 г. Челябинск
м-н Продукты ул.Румянцева 29 г.Челябинск
м-н Продукты ул.Островского 29 г.Челябинск
м-н Продукты ул.Кирова 9Г г.Челябинск
м-н Продукты ул. Шоссе Металлургов 39А г.Челябинск
г.Челябинск Краснопольский проспект 15
п-н Продукты г.Челябинск ул.Хлебозаводская ост.»Сад Строитель»
г.Челябинск ул.Лесопарковая 7
м-н Продукты ул.Захаренко 9а г Челябинск
г.Челябинск ул.Индивидуальная ост.»Сад Слава»
г.Челябинск ул.Академика Короева 4
г.Челябинск, пл. Мопра 2
г.Челябинск,пл.Мопра,2
г.Челябинск,ул.Аральская,д.38 Магазин
г. Челябинск, ул. Марченко, 37а, м-н «Продукты»
г. Челябинск, ул Северо-Крымская, 52, ост. павильон
Челябинск, ул. Молодогвардейцев, 39в, магазин
г.Челябинск, пр. Победы, 115, м-н Юрюзань
г. Челябинск, пересечение пр. Победы и ул. 40 лет победы, ост. павильон
Челябинская область, Красноармейский р-н, г. Копейск, п. Вахрушево
г.Челябинск, ул. Автоматики, 7, павильон
г. Челябинск, Сталеваров ул, д. 70, м-н «Продукты»
г.Челябинск, ул. Комаровского, д.10, м-н
г. Челябинск, ул. Сталеваров, 3а
г.Челябинск, ул. Чайковского, 54б, м-н
г.Челябинск, ул. Двинская, 11, м-н
г.Челябинск, ул. Аральская, 21
г.Челябинск, Троицкий тракт, 72б, ост.павильон Купеческий рынок
Челябинская область, трасса Уфа-Челябинск 1779 км., кафе Светлана
г.Челябинск, ул.Каслинская, 21в, м-н Продукты
г. Челябинск, п. Керамический, м-н
г.Челябинск, ул 40 лет Победы, 29, кафе «Перчик»
г. Челябинск, ул. 250-летия Челябинска, 67
г. Челябинск, ул. Плеханова, 14, м-н
г. Челябинск, пересечение Комсомольского проспекта и ул. Молодогвардейцев, ост. павильон «Продукты»
г.Челябинск, ул.Валдайская 1а, м-н Продукты
г. Челябинск, п. Новосинеглазово, ул. Лесная, 86, п-он Продукты
Челябинск, Троицкий тракт, д. 49, кафе Сигнал
г. Челябинск, ул. 250 лет Челябинску, 5В.
ул.Мехколонна 7,г.Челябинск,Терминал 5920001
ул. Зальцмана 34,г.Челябинск,м-н Продукты
г. Челябинск, Тракторосад №3
г.Челябинск,ул.Университетская набережная,д.90 детский сад №35
г.Челябинск,ул.Ереванская д.16.4.№77
г.Челябинск улВагнера д.70а. МБОУ СОШ 68
г.Челябинск, ул.Шенкурская д.13 №109 ,
г.Челябинск,ул.Академика Сахарова, д.24 №39
г. Челябинск, ул. Тимирязева, д. 6, Лицей №11
г. Челябинск, ул. Грибоедова, д. 2, школа №102
г. Челябинск, ул. Кузнецова, д. 33, школа №56
г. Челябинск, ул. Вагнера, 90, школа №128
г. Челябинск, ул. Агалакова, 19, №113
г. Челябинск, ул. Агалакова, 46, №51
г. Челябинск, ул. Омская, 13, м-н Продукты
г. Челябинск, ул. 2-ая Эльтонская, 16А, №116
г. Челябинск, ул. Бр. Кашириных 99а,ТК «Фрегат»
г. Челябинск, ул.Воровского, 17,м-н Мечта
г. Челябинск, Копейское шоссе, 1Г, ТК Светофор
г. Челябинск, ул. Гагарина, д. 4Б, ТК Андреевский
Кузнецова, 12, Проспект
Комсомольский пр-т, д. 74, Проспект
Новороссийская, 84, Пятерочка
ул. 250 лет Челябинска, 11, м-н Пятерочка
г. Челябинск, ул. Воровского д.40. магазин Продукты
г.Челябинск ул. Гагарина,д. 32 Магазин продукты

5.2. Какую технологию подключения вы используете? Сеть «ГиперСеть» построена по технологии «оптика до дома» — это означает, что кабель по которому подается сигнал доходит до каждого дома, это позволяет передавать сигнал без помех, независимо от того, какую услугу вы потребляете: интернет, телевидение или домашний телефон. В отличие, например, от спутникового интернета, данная технология позволяет не только предоставлять более качественные услуги, но также снизить их стоимость и избежать использования дополнительного оборудования. 5.3. Что значит выделенная линия? Выделенная линия или «оптика до дома» означает, что оптоволоконный кабель доходит до каждого дома, а выделенная линия до каждой квартиры. Это позволяет передавать сигнал без помех, независимо от того, какую услугу вы потребляете. Выделенная линия представляет собой пару проводов, проложенную от ближайшего узла доступа, который расположен в вашем доме, до вашей квартиры. 5.4. Где можно получить консультацию по услугам? Полную информацию можно получить на сайте или обратившись в контакт-центр по телефону, который указан на сайте. 5.5. Мегабайт — это сколько? Один мегабайт — это 10-12 средних веб-страниц или около 200 страниц печатного текста. 5.6. Как проверить компьютер на вирусы? Для этого необходимо:
— скачать бесплатную утилиту Dr. Web CureIt! c сайта разработчика программы;
— запустить скаченный файл, дождаться окончания быстрой проверки, ознакомиться с результатами;
— в случае необходимости запустить полную/выборочную проверку. Данная утилита содержит в себе все вирусы базы Dr. Web на день скачивания, но не умеет обновляться через интернет. Поэтому рекомендуется либо приобрести и установить полноценный антивирус с возможностью автоматического обновления, либо периодически скачивать свежую версию CureIt! для очередной проверки компьютера.
5.7. Не поступил платеж. Для этого необходимо:
1. Выслать сканированную квитанцию на info@hypernet.ru или отправить ее по факсу +7(351)2399365
2. Позвонить в службу Технической поддержки по телефону (351) 2399300 и объяснить суть проблемы 5.8. Зачем нужен Личный Кабинет? Личный Кабинет – это место, где вы можете производить различные операции со своим счетом: проверять баланс, активировать бонусы, брать обещанный платеж, менять пароль и логин доступа к своему счету. Ссылка на него находится в правой верхней части сайта.

Применение теории S-гиперсетей для моделирования систем сетевой структуры Текст научной статьи по специальности «Математика»

Аннотация научной статьи по математике, автор научной работы — Попков Владимир Константинович

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

i Надоели баннеры? Вы всегда можете отключить рекламу.

Похожие темы научных работ по математике , автор научной работы — Попков Владимир Константинович

Система распределённой обработки данных
Модели анализа устойчивости и живучести информационных сетей
Применение алгоритма муравьиной колонии для построения оптимальной гиперсети
Минимальная реализация и другие операции над гиперсетями
Гиперсетевая технология оптимизации инженерных сетей в горной или пересеченной местности
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
i Надоели баннеры? Вы всегда можете отключить рекламу.

Текст научной работы на тему «Применение теории S-гиперсетей для моделирования систем сетевой структуры»

ПРИМЕНЕНИЕ ТЕОРИИ S-ГИПЕРСЕТЕЙ ДЛЯ МОДЕЛИРОВАНИЯ СИСТЕМ СЕТЕВОЙ СТРУКТУРЫ

Институт вычислительной математики и математической геофизики СО РАН,

630090, Новосибирск, Россия

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

Ключевые слова: граф, гиперсеть, 5-гиперсеть, структурный анализ, синтез, математическое и имитационное моделирование.

Basic concepts of the theory of 5-hypernetworks are considered. It is shown that the concepts of this theory can be used to describe many network structure systems with an accuracy of an adequate solution to the formulated problem. In fact, analytical formulation of problems of analysis and synthesis of network structure systems is a nearly imitation model, which can be used to solve formulated problems.

Key words: graph, hypernetwork, 5-hypernetwork, structure analysis, synthesis, mathematical and imitation modeling.

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

1. Основные определения. Приведем определение простой гиперсети, в которой элементы типа узла однотипны, а линейные элементы (ветви, ребра) имеют различную природу [1].

Шестерка, состоящая из трех множеств и трех отображений S = (X, V, R; P, F, W), называется гиперсетью, если Vv £ V\P(v)\ = 2, Ут £ R\W(r)| = 2, Ут £ R множество F(r) С V составляет маршрут в графе PS = (X, V).

Таким образом, первичная PS и вторичная WS сети гиперсети S являются графами, а F отображает ребра WS=(X, R) в маршруты графа PS=(X ,V).

Так как множество F(т) является маршрутом, то отображение F единственным образом определяет отображение W. Действительно, концевые вершины маршрута F(т) одновременно являются концами ребра т, т. е. гиперсеть S можно задать пятеркой (X,V,R; P,F).

Работа выполнена в рамках Проекта Президиума РАН №14.2.

Приведем формальное определение 5-гиперсети. Пусть задано множество графов (гиперграфов) О0 = (X0,У), О1 = (X 1,и1). О0 = (Xк,ик) и корневое дерево Т0 = (X,Я), где X = . Хк, Я = Т\, . Гк — определяющее вложение графов О з в Ог (г < ]) аналогично

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

быть инцидентны несколько вершин Х3к

хк> из I графов [Озд>, 5 = 1. 1.

На множестве вершин Хк определяется ЬЗ = (Хк ,Е). Вершины хи х^ смежны в ЬЗ, если соответствующие графы О^ и в вершине хк имеют некоторую системообразующую связь ¡(хЗ1 ,хЗа). В противном случае эти вершины не связаны. Так же как и в гиперсетях, ребру иЗ Е О з в графе Ог сопоставляется цепь или некоторая связная часть между соответствующими вершинами из Ог. На рис. 1 приведен пример такой гиперсети. Следует отметить, что

Рис. 1. 5-гиперсеть и ее составляющие: а — отображение графа вторичной сети Ох в граф первичной сети О2 с образованием гиперсети 02(0х); б — отображение гиперсети 02(0\) и графа Оз в граф Оо с образованием ^-гиперсети Н = (О0(О3,О2(Ох))); в — гиперсеть Н = (О0(О3,О2(Ох))), в которой определены внутриузловые связи (графы Ь)

Рис. 2. Сумма графов сетей ^-гиперсети Н: а — объединение всех графов вторичных сетей ^-гиперсети Н; б — сумма графов всех сетей ^-гиперсети Н

системообразующие связи типа могут иметь различную природу и, как правило, существенно зависят от времени. В некоторых случаях, например в системе транспортных сетей различного типа (метро, автобус, трамвай), такими связями в транспортных муль-тиузлах являются тротуарные линии (пешеходные переходы). В этом случае имеет смысл рассматривать объединение всех вторичных сетей (рис. 2,а). Однако для некоторых задач целесообразно рассматривать сумму всех графов гиперсети Н включая первичную сеть РБ, т. е. О = О0 + +. + Оп + . На рис. 2,б приведен пример объединения всех графов, входящих в Б-гиперсеть Н. При этом структура вложений имеет вид, представленный на рис. 3.

С использованием приведенных ниже матриц определенную таким образом Б-гиперсеть можно задать с точностью до изоморфизма и даже с точностью до нумерации вершин и ребер.

Графы Ог, г = 1. к задаются матрицами инциденций . Вложения графов определяются системой матриц инциденций )>, таких что а\ = 1, если вершина XI Е Ог инцидентна вершине хг Е Оз (г < ]), и а\ = 0 в противном случае. Для матрицы инциденций ребра имеем Щ = 1, если ребро ир Е О3 вторичной сети инцидентно ветви и^ Е Ог первичной сети, и Ь>= 0 в противном случае. Представление Б-гиперсети заканчивается множеством матриц смежности М^ = (з^).

Пусть вершине хгх Е Ог инцидентны вершины . Тогда матрицы смежности М^в^) определяют смежность этих вершин в х\.. Таким образом, Б -гиперсеть Н — (Оо,О\, . Ок) однозначно задается следующей системой матриц:

1) Мг(с>) — матрица инциденций графов Ог (г = 0. к; 1г = 1. пг; рг = 1. тг, где к + 1 — число графов в БНМ; пг — число вершин в графе Ог; тг — число ребер в графе Ог);

2) <Мг(а1\),Щ(Ь>.)> — матрицы инциденций, определяющие вложение графов Оз в граф

Рис. 3. Структура вложений графов

матрицы смежностей вершин графов вторичных сетей в первичной сети н, ¡,й = 1, . п, т. е. вг? = 1, если вершины f и й графов

инцидентны вершине хг и смежны в этой вершине, иначе в

Рис. 4. Примеры топологических взаимосвязей ребер и вершин различных сетей Б-гиперсети Н = РБ)

Вероятно, наибольшее число приложений теории гиперсетей и Б-гиперсетей приходится на электросвязь и транспорт, поэтому большая часть задач, рассматриваемых в данной работе, связана с этими направлениями [1-4]. Тем не менее теория 5-гиперсетей применима для анализа и синтеза других систем сетевой структуры. Особый интерес вызывают задачи анализа межсетевых структурных взаимодействий сложных систем различной природы.

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

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

При отображении графа вторичной сети ШБ в первичную сеть РБ возникают четыре класса вложений ребер ШБ в ветви РБ (рис. 4,а).

Для гиперсети Н = (РБ, ШБ):

1. Ребра вторичной сети ШБ не отображаются в ребра первичной сети, имеет место только отображение вершин ШБ в вершины РБ. Таким образом, матрицы в представлении

гиперсети отсутствуют (рис. 4,6). В этом случае имеет место экс-отображение ШБ ^ РБ и соответственно экс-гиперсеть.

2. Если ребра вторичной сети ШБ = (X 1,Я) параллельны ветвям первичной сети РБ = (X°,У), то имеет место параотображение ШБ Р РБ (рис. 4,в), которое порождает парагиперсеть Н = (ШБ, РБ).

3. Если ребра вторичной сети ШБ располагаются на «плоских» ветвях первичной сети

РБ, то имеет место эктоотображение ШБ ^ РБ (рис. 4, г) и соответственно эктогиперсеть.

4. В последнем случае ребра вторичных сетей располагаются внутри ветвей первичной сети. На рис. 4,д приведен пример эндоотображения ШБ -н РБ, которое порождает эндоги-персеть.

Вершины могут отображаться друг в друга одним из четырех способов:

1. Вершина вторичной сети х абстрактно отображается в вершину у первичной сети, если их взаимное расположение безразлично, т. е. имеет место экс-отображение.

2. Если вершина х отображается рядом с узлом у, то имеет место параотображение (вершины 2.1 и 3.1 на рис. 1).

3. При эктоотображении вершин одна из них располагается на другой (на рис. 1 вершины 2.1 и 3.1 располагаются на узле 1).

4. При отображении одной вершины внутрь другой имеет место эндоотображение вершин (на рис. 1 вершина 1.2 располагается внутри вершины 2.1).

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

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

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

Пусть задана гиперсеть Н = (РБ,ШБ), которую будем называть РБ-планарной, если граф РБ первичной сети планарен, ШБ-планарной, если граф ШБ-планарен.

Данные характеристики хорошо изучены в теории графов. Более интересна следующая характеристика. Гиперсеть Н называется псевдопланарной, если граф ШБ может быть размещен в РБ без пересечения ребер. Гиперсеть Н квазипланарна, если граф ШБ может быть реализован в РБ без пересечения ребер, а РБ может быть реализован на плоскости без пересечения ветвей. Если такие реализации возможны, то гиперсеть Н планарная; если данные реализации выполнены, то гиперсеть Н плоская. На рис. 5 видно, что квазипланарная гиперсеть может быть неплоской.

Утверждение. Если гиперсеть Н = (РБ, ШБ) ШБ-планарна, то она планарна.

Доказательство. Если граф РБ первичной сети не планарен, то его можно сделать планарным путем удаления некоторых ветвей. В оставшейся части РБ’ можно выполнить плоскую реализацию ШБ. Для доказательства достаточно показать, что первичная плоская сеть РБ гомеоморфна плоскому кругу с отверстиями.

Уменьшим физический размер граней плоской первичной сети до точки (дырки). Тогда очевидно, что ШБ реализуем на поверхности, образованной первичной сетью, так как является ШБ-планарным.

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

На рис. 5,а видно, что РБ не плоский, а планарный, ШБ — плоский в РБ, т. е. внутри (на поверхности ветви) ребра не пересекаются. В то же время на рис. 5,б первичная сеть плоская, а вторичная — нет, и даже не планарная. Следовательно, из псевдопланарности гиперсети не следует планарность ШБ.

Рис. 5. Псевдопланарная гиперсеть: а — пятивершинная плоская реализация графа ШБ; б — неплоская реализация в плоском графе РБ

Применение понятия «планарный» к гиперсетям не всегда корректно. Действительно, РБ допускает изменение геометрии рисунка, т. е. из планарного можно сделать плоский граф РБ, при этом И и И’ остаются изоморфными.

i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

Следует отметить, что преобразование конфигурации РБ с целью сделать ее плоской приводит к изменению пространственной конфигурации ШБ, т. е. граф вторичной сети не может иметь двухклеточное вложение в плоскую реализацию первичной сети. Это видно на рис. 5,а: если перенести вершину Х5 (см. рис. 5,6), то граф РБ станет плоским, при этом граф ШБ будет иметь пересекающиеся ребра. Не существует перетрассировки ребер, позволяющей сделать его плоским, так как род графа ШБ равен 1.

Изменяя трассировки ребер ШБ в РБ, получаем другую гиперсеть И’, эквивалентную И [2]. Таким образом, изменяя трассировку ребер ШБ на ветвях РБ, получаем неизоморфное преобразование.

С практической точки зрения вместо эктогиперсети целесообразно рассмотреть эндоги-персеть. В этом случае представляет интерес пересечение ребер не внутри ветвей, а только на узлах первичной сети.

Эндогиперсеть БН = (РБ, ШБ) будем называть ШБ-квазиплоской, если в каждом узле РБ = (X, V) существует плоская реализация фрагментов вторичных гиперсетей Б-гиперсети, такая что БН = (РБ,ШБ\, . ШБк). Гиперсеть БН называется квазиплоской, если ШБ является квазиплоской в плоской сети РБ.

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

Нестационарная Б-гиперсеть называется квазипланарной, если она является квазипла-нарной в любой стационарный промежуток времени.

При исследовании проблем анализа и синтеза сетевой структуры возникают постановки следующих задач.

1. Пусть заданы граф первичной сети РБ, семейство графов вторичных сетей и отображения Xг — X0. Необходимо провести трассировку ребер в графе РБ, так чтобы Б-гиперсеть стала квазиплоской.

2. Найти критерий квазиплоскости Б-гиперсети И = (РБ, ШБ\. ШБк).

Классификация симбиотических связей

Вторичная сеть Б-гиперсети ШБ = (X, Я) Первичная сеть Б -гиперсети РБ=( Y ,V)

Полезная (П) Нейтральная (Н) Вредная (В)

П Мутуализм Комменсализм Паразитизм

(mutualism) (commensalism) (parasitism)

Н Комменсализм Нейтрализм Аменсализм

(commensalism) (neutralism) (amensalism)

В Паразитизм Аменсализм Конкуренция

(parasitism) (amensalism) (competition)

3. Пусть задана Б-гиперсеть Н. Требуется составить расписание работы внутризоновых ребер, так чтобы нестационарная Б-гиперсеть стала квазипланарной.

4. Решается предыдущая задача, но среднее число циклов в Н должно быть минимально возможным.

5. Добавить в Н минимальное число ветвей, так чтобы Б-гиперсеть стала квазипланарной с учетом перетрассировки ребер вторичных сетей ШБ^.

Очевидно, что понятие планарности в Б-гиперсетях порождает большое количество комбинаторных задач.

4. Классификация симбиотических связей в теории 5-гиперсетей. Для многих приложений теории Б-гиперсетей отношения между вторичной и первичной сетями, а также между вторичными сетями имеют характер симбиотических связей. Иными словами, они могут быть полезными, нейтральными или вредными. Исследование таких взаимоотношений позволяет анализировать устойчивость, развитие и другие характеристики систем различных взаимосвязанных сетей. В табл. 1 приведена классификация симбиотических связей.

Рассмотрим табл. 2-5, в которых приведены примеры различных симбиотических связей, с учетом следующих отображений ребер в ветви первичной сети (примеры таких отображений представлены на рис. 4):

— ребра вторичной сети ШБ не отображаются в ребра первичной сети (экс-отображение ШБ РБ);

Примеры экс-симбиоза WS и РБ в Б-гиперсети Н = (ШБ, РБ) для различных ССС

Вторичная сеть Первичная сеть S-гиперсети PS=(Y,V)

ШБ = (X, Я) Полезная (П) Нейтральная (Н) Вредная (В)

П Команды одного клуба Элита и общество Финансовая

(мутуализм — эс/пп) (комменсализм — пирамида

эс/пн) (паразитизм — эс/пв)

Н Социальное Независимые клубы Инфекционные

обслуживание по интересам больные и общество

(комменсализм — эс/нп) (нейтрализм — эс/нн) (аменсализм — эс/нв)

В Система жертва — Существа в Соперники

хищник агрессивной среде (конкуренция — эс/вв)

(паразитизм — эс/вп) (аменсализм — эс/вн)

Примеры парасимбиоза WS и РБ в Б-гиперсети И = (ШБ, РБ) для различных ССС

Вторичная сеть Первичная сеть Б -гиперсети РБ=(У V)

ШБ = (X, Я) Полезная (П) Нейтральная (Н) Вредная (В)

П Композиционные Линии электропередач Занятие телефонных

материалы (пс/пп) (ЛЭП) и шоссе пар в кабеле для пере-

(пс/пн) дачи данных (пс/пв)

Н Система освещения Кабельные линии и ЛЭП и низко-

дороги и шоссе инженерные сети в частотные каналы в

(пс/нп) одном коллекторе кабеле тональной

(пс/нн) частоты (пс/нв)

В Зимнее горячее и Тротуары и проезжая Трамвайные пути и

холодное водо- часть (пс/вн) дорога с проезжей

снабжение в одном частью (пс/вв)

— ребра вторичной сети ШБ = (X 1,Я) параллельны ветвям первичной сети (параотоб-ражение ШБ —— РБ);

— ребра ШБ располагаются на «плоских» ветвях первичной сети (эктоотображение

— ребра вторичных сетей располагаются внутри ветвей первичной сети (эндоотображение

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

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

Примеры эктосимбиоза WS и РБ в Б-гиперсетях И = (ШБ, РБ) для различных ССС

Вторичная сеть Первичная сеть Б-гиперсети РБ=(У V)

ШБ = (X, Я) Полезная (П) Нейтральная (Н) Вредная (В)

П Асфальтовое Маршруты общест- Потоки грузового

покрытие бетонных венного транспорта на транспорта на дорогах

дорог (эк.с/пп) дорогах (эк.с/пн) (эк.с/пв)

Н Спецтранспорт при Полосы движения на Гололедица на

ремонте дорог проезжей части дорогах (эк.с/нв)

В Защитные покрытия Потоки транспорта на Рельсовый транспорт

дорог, труб и т. д. разбитых дорогах на автодорогах

(эк.с/вп) (эк.с/вн) (эк.с/вв)

Примеры эндосимбиоза WS и РБ в Б-гиперсетях Н = (ШБ, РБ) для различных ССС

Вторичная сеть Первичная сеть Б-гиперсети РБ=(У,У)

ШБ = (X, Я) Полезная (П) Нейтральная (Н) Вредная (В)

П Сети электросвязи Поток пассажиров в Потоки минеральной

города (эн. с/пп) метро (эн. с/пн) воды в стальных

Н Поток агрессивной Кабели связи в Ливневый поток в

жидкости в трубах туннелях метро кабельной кана-

(эн. с/нп) (эн. с/нн) лизации (эн. с/нв)

В Система питания в ав- Обледенение ЛЭП Виртуальный компью-

тотранспорте (эн. с/вп) (эн. с/вн) тер (ПК в ПК) (эн. с/вв)

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

Примеры отношений, приведенные в табл. 4, 5, показывают типичность экто- и эндосим-биозов для инженерных сетей.

Из приведенных примеров систем сетевой структуры следует, что их взаимодействие может также описываться симбиотическими связями. Например, комменсализм является преимущественным отношением между сетями различных уровней гиперсети, соответствующей сети связи, обладающей высокой живучестью. Гиперсети с такими отношениями, как правило, находятся в устойчивом равновесии, а отношение аменсализма обусловливает неустойчивое равновесие. Понятно, что отношение паразитизма делает гиперсеть неустойчивой. Особый интерес представляют гиперсети, в которых отношения между сетями различного уровня являются «мутуализмом» или «конкуренцией». В первом случае имеет место взаимная польза и, следовательно, высокая устойчивость, во втором — жесткая конкуренция на грани развала. Ниже показано, что устойчивость гиперсетей связана также со структурными характеристиками, которые оказывают влияние на их связность и потоки.

Оценка симбиотических отношений является нетривиальной задачей, их качественная и численная меры определяются как наличием или отсутствием взаимоотношений между первичными РБ и вторичными WS сетями, так и их конкретным отображением Г(г) : ШБ — РБ. При г=0 отображение отсутствует. По аналогии с целеустремленными системами [5] в рассматриваемом случае отношения симбиоза можно доопределить такими понятиями, как сотрудничество, конфликт и независимость.

Обозначим через р(РБ)/Ш Б (Г (г)) ожидаемую оценку эффективности РБ, если ШБ реализовано в РБ с помощью отображения Г (г); соответствующие величины для ШБ обозначим р(ШБ)/РБ(Г-1(г)). Будем считать, что р принимает значения от 0 до 1. Как отмечено выше, при г = 0 отображение отсутствует.

Введем понятия сотрудничества, конфликта и независимости между сетями Б-гиперсети:

— если р(РБ)/ШБ(Г(г)) > р(РБ)/ШБ(Г(0)), то ШБ сотрудничает с РБ;

— если р(РБ)/ШБ(Г(г)) = р(РБ)/ШБ(Г(0)), то ШБ не зависит от РБ.

i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

Аналогичное неравенство можно построить для обратного отображения Г-1 : РБ ШБ.

Очевидно, что оценки р(РБ)/Ш Б (Г (г)) можно упорядочить таким образом, чтобы для г,г + 1 выполнялось неравенство р(РБ)/Ш Б (Г (г)) < р(РБ)/ШБ (Г (г + 1)).При этом = Q, т.е. множество отображений Г (г) задает пространство Q, которое определяет все многообразие гиперсетей с заданными сетями РБ и ШБ.

Теперь можно определить степень сотрудничества в зависимости от Г(г). Степень сотрудничества РБ с ШБ при заданном Г (г) определяется формулой АС (РБ, ШБ) = р(РБ)/ ШБ(Га))-р(РБ)/ШБ(Г(0)), а степень конфликта РБ с ШБ — выражением АК(РБ, ШБ) = -АС(РБ, ШБ).

Степень сотрудничества или конфликта сети РБ с сетью ШБ, вообще говоря, не равна степени сотрудничества или конфликта сети ШБ с сетью РБ. Обозначим через 8(РБ,ШБ) степень эксплуатации сети РБ сетью ШБ, т. е. 5(РБ,ШБ) = АС (РБ, ШБ) — АС (ШБ, РБ). Очевидно, что 5(ШБ,РБ) = АС(ШБ,РБ) — АС(РБ,ШБ). В зависимости от значений 5(РБ, ШБ) и 8(ШБ, РБ) можно определить различные типы эксплуатации.

Введенные выше понятия и параметры позволяют получить количественные характеристики Б-гиперсетей при моделировании реальных систем сетевой структуры.

5. Классификация 5-гиперсетей. Область применимости математической теории определяется не только свойствами математического объекта, но и его пластичностью. В частности, подробная классификация Б-гиперсетей позволяет адекватно описать различные системы для структурного анализа и оптимизации.

В табл. 6-13 приведена базовая классификация Б-гиперсетей, ориентированная на моделирование сложных систем сетевой структуры.

Системная типология гиперсетей

Классификационные Характеристики Б-гиперсетей

Типы вложений Экс-гиперсеть, парагиперсеть, эктогиперсеть, эндогиперсеть

Размерность Конечная, бесконечная

Потоковая функция Дискретная, непрерывная

Атрибуты Детерминированная, случайная

Стабильность Стационарная, нестационарная

Структура гиперсети Каскадная, смешанная, параллельная

Разнообразие вторичных Однотипная, ^-типная

Системная типология первичных и вторичных сетей

Классификационные Характеристики первичной и вторичных сетей

Тип математического Граф, гиперграф, гиперсеть

Ориентация Ориентированная, смешанная, неориентированная

Сложность Тривиальная, пустая, дерево, планарная, полная, произвольная

Однородность Однородная, неоднородная

Весовые характеристики Взвешенная, невзвешенная

Атрибуты Детерминированная, случайная

Стабильность Стационарная, нестационарная

Системная типология элементов

Классификационные признаки Характеристики элементов

Типы элементов Весовые характеристики Ориентация Время существования Представление Число полюсов Узлы (вершины), ветви (ребра), полюсы (полусвязь) Взвешенный(ая,ое), невзвешенный(ая,ое) Ориентированный, неориентированный Постоянно, по расписанию, случайное Абстрактное, геометрическое Все полюсы, свободные полюсы Таблица 9 Системная типология связей

Классификационные признаки Характеристики связей

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

Классификационные признаки Топологические характеристики Б-гиперсетей

Размерность пространства Род поверхности первичной сети Число уровней в иерархии Число сетей на к-м уровне Размерность Тип укладки элементов вторичных сетей в первичной Одномерное, двумерное, трехмерное Плоская, к-го рода Обычная гиперсеть (два слоя), к уровней (слоев) Уровень 0 — первичная сеть, N (к) —число сетей на уровне к Конечная, бесконечная Не укладываются, укладываются рядом с другими, укладываются на элементе, укладываются внутри элемента

28 Теоретическая информатика

Топологическая типология вторичных сетей

Классификационные признаки Топологические характеристики вторичных сетей

Тип математического объекта Наличие циклов Ориентация Род графа Связанность графов вторичных сетей Граф, гиперграф, ультраграф, гиперсеть Циклическая, ациклическая Ориентированная, неориентированная Плоский, к-го рода Связанная (связана с другими вторичными сетями), свободная (связана только с первичной сетью)

Топологическая типология элементов

Классификационные признаки Топологические характеристики элементов

Типы элементов Размерность Число полюсов Представление Узел (вершина), ветвь (ребро), полюс (полусвязь) Без размера, линейный, плоский, объемный Без полюсов, к-полюсный Абстрактное, геометрическое

Топологическая типология связей

Классификационные признаки Топологические характеристики связей

Ориентация полюсов Типы полюсов в элементах Разнообразие типов полюсов Занятость полюсов Тип связи полюсов Неориентированные, ориентированные Неоднородные, однородные Однотипные, разнотипные Занятые, свободные Слияние, инцидентность, полуинцидентность

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

6. Маршруты и метрика в 5-гиперсетях. Дана взвешенная гиперсеть ЛБ = (Х, V, Я); X = (х\. хп) — вершины, V(х¿) — вес вершины х^; V = (у\. ут) — ветви; ¡(у^) — вес ветви У3; Я = (т\. тд) — ребра гиперсети; ЛР = (X, V) — взвешенный граф первичной сети; ЛШ = (X, Я) — вторичная сеть; ЛР = (V, Я) — гиперграф, определяющий структуру вложения ЛШ в ЛР таким образом, что каждому ребру г = (х, в) £ Я будет сопоставлена (х, в)-цепь в первичной сети, следовательно, вес ребра г = (х, в) £ Я будет равен суммарному весу (х, в)-цепи в ЛР = (X, V).

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

Маршрутом в гиперсети Б = (X, У, Я) называется конечная последовательность ц = (х1,г1,х2, . хг-1,Гк-1, %к), составленная из элементов X, Я таким образом, что вершины и ребра чередуются, а два любых соседних элемента инцидентны.

Квазимаршрутом в гиперсети Б = (X, У, Я) называется конечная последовательность в которой пара соседних элементов (хг,гг) инцидентны, а (гг,хг+1) слабоинцидентны.

Если в определении маршрута заменить «инцидентность» на «слабую инцидентность», то получим определение слабого маршрута. Ориентированные маршруты определяются аналогично с учетом ориентации ребер (для сетей симплексной связи).

Длиной ребра (или его части) называется число ветвей, инцидентных этому ребру (части ребра). Длина рл маршрута ц (квазимаршрута, слабого маршрута) равна суммарной длине ребер (частей ребер), входящих в маршрут ¡.

Из определения маршрута в гиперсети Б = (X, У, Я) непосредственно следует, что каждому маршруту ц в Б между вершинами х и у соответствует маршрут ц в графе ШБ = (X, Я).

Расстояние р(хг,х^) между парой вершин хг и хз в гиперсети Б находится по взвешенному графу WS * = (X, Я). Каждому ребру г к графа WS * ставится в соответствие длина, равная ||, где = Г (г к). Таким образом, кратчайшие маршруты в гиперсетях могут быть найдены с помощью известных алгоритмов по графу WS*. Для ориентированной гиперсети граф WS* ориентируется.

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

Квазирасстояние р(х^,х^) между парой вершин хг и хз гиперсети Б можно найти по взвешенному орграфу ВБ* = (Б, и), в котором длина дуги пх равна числу ветвей в части ребра г к, входящего в квазимаршрут, соединяющий вершины хг и хз гиперсети Б.

Отношения слабой отдаленности и слабого расстояния играют большую роль при решении прикладных задач на гиперсетях.

В гиперсетях (ориентированных гиперсетях) слабое расстояние р(хг,хз) между вершинами хг и хз вычисляется с помощью взвешенного графа ПБ* = (X,и) (ПБ* = (X, и)), в котором ребру (дуге) пх ставится в соответствие длина, равная сумме весов ветвей в цепи, соединяющей вершины хг и хз в гиперсети Б.

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

Маршрут ¡ называется простой цепью, если каждая вершина встречается в ¡ не более одного раза.

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

7. Метрика £-гиперсети. В данном пункте приведен ряд метрик, определяющих расстояние между вершинами и ребрами гиперсети, а также между вторичными сетями в Б-гиперсети.

7.1. Расстояние в гиперсетях. Расстоянием (квазирасстоянием, слабым расстоянием) рня(х,у) между вершинами х и у гиперсети НБ = (РБ,ШБ) называется длина кратчайшего маршрута (квазимаршрута, слабого маршрута) между соответствующими вершинами

Рис. 6. Примеры сводимости гиперсети к соответствующим графам: а — гиперсеть; б — граф для вычисления кратчайших маршрутов; в — граф для вычисления кратчайших квазимаршрутов; г — граф для вычисления слабых маршрутов

х,у Е X. Очевидно, что рня(х,у) определена на множестве всех пар гиперсети ИБ и удовлетворяет аксиомам Фреше:

1) рефлексивность рня(х,у) = 0, если х = у;

2) симметричность рня(х,у) = рня(у,х);

Выполнение первой аксиомы очевидно.

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

Третья аксиома справедлива, поскольку для вычисления кратчайших маршрутов (квазимаршрутов, слабых маршрутов) нетрудно построить эквивалентные графы, в которых вычисляются кратчайшие (х, у)-маршруты в ИБ-гиперсети. Так как третья аксиома справедлива для графов и орграфов, то из сказанного выше следует справедливость аксиом Фреше для ИБ-гиперсети. Очевидно, что для квазирасстояния, как и для расстояния в орграфе, аксиома симметричности не выполняется. На рис. 6 приведены примеры сводимости гиперсети (рис. 6,а) к графам (рис. 6,б-г) для решения соответствующих задач поиска кратчайших маршрутов.

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

1) £n(x) = maxpAx,y) соответствует кратчайшему (x, у)-маршруту;

2) £ka(x) = maxpka(x,y) соответствует кратчайшему (x, у)-квазимаршруту;

3) £ps(x) = max pps(x, у) соответствует кратчайшему слабому маршруту в HS или марш-

Тогда R(HS) = min£(x) — радиус (квазирадиус, слабый радиус), а D(HS) = max£(x) — xex xex

диаметр (квазидиаметр, слабый диаметр).

Если отображение WS в PS не задано, то имеет место следующая задача: для заданных PS и WS найти такое отображение WS в PS, чтобы R(HS) ^ min / max и D(HS) ^ min / max.

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

При решении ряда задач необходимо вычислять расстояние между ребрами вторичной сети в некоторой гиперсети HS = (PS; WS) = (X,V,R; P,W,F). Пусть заданы два ребра ri и rj Е R. Расстояние между вершинами x Е W(ri) и у Е W(rj) обозначим prirj (x,y) (W(ri) и W(rj) — множества вершин, по которым проходят ребра ri и Tj соответственно). Вершину

у Е W(rj), ближайшую к вершине x Е W(ri) в графе PS, обозначим Lr. (у) = min p(x,y).

Пусть L(ri,Tj) = maxmin p(x,y). Ясно, что введенная таким образом величина

L(ri,Tj) не является расстоянием, так как не удовлетворяет аксиоме симметрии.

Аналогично определим L(Tj,Ti) = maxmin p(y,x). Следующее выражение опреде-

ляет расстояние pps(Ti,Tj) и является метрикой Хаусдорфа на гиперсети PS: pps(Ti,Tj) =

i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

yew (rj) xew (ri) xew (ri) yew (rj)

p(x,y) — расстояние между вершинами x и у в первичной сети PS.

На множестве ребер можно ввести так называемую равномерную метрику pps(Ti,Tj) =

max p(x, у). Данная метрика удовлетворяет трем аксиомам Фреше.

Назовем величину £(Ti) = max pps(Ti,Tj) эксцентриситетом ребра Ti Е R. Ребро t* Е R бу-

дем называть серединным,если£(r*) = min£(т^),иг**-периферийным, если £(r**) = max£(ri).

Величину £(т**) = n(HS) будем называть шириной гиперсети HS, а £(т*) = O(HS) — отклонением гиперсети HS. Сложность задачи вычисления введенных характеристик является полиномиальной.

При решении ряда практических задач необходимо найти трассировки ребер WS в PS, так чтобы n(HS) и O(HS) принимали экстремальные значения.

Представляет интерес задача проверки выполнения равенств реализаций WS в PS. 7.2. Расстояние в S-гиперсетях. В отличие от гиперсетей каждая вторичная сеть из имеет собственный набор вершин , такой что \Xi\ < \X0| У1,] = 1,n.

В отличие от гиперсетей расстояние в S-гиперсети SH = (PS, ) определяется не только для вершин и ребер, но и для вторичных сетей WS. Вершины вторичных сетей в общем случае являются независимыми элементами и могут быть несвязанными. В данном случае эти сети могут быть несвязанными и в евклидовом пространстве. Поэтому

Рис. 7. Иллюстрация к аксиоме транзитивности для расстояний между сетями: а — P(x, z) + P(z, v) > P(x, y); 6 — P(x, z) + P(z, v) = P(x, y)

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

Рассмотрим несколько метрик, связанных с разнообразием как элементов, так и способов

построения функции расстояния. Для вершин У ^ = X обычная метрика вычисляется

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

7.3. Расстояние между сетями. В зависимости от задач на Б-гиперсети БИ можно рассмотреть метрики, более адекватные поставленным задачам. В данном пункте не рассматриваются конкретные задачи, основное внимание уделено различным сетевым метрикам.

Рассмотрим метрику вложений. Пусть две сети Шг и Шз лежат на слоях хг,уз Е Я соответственно. Пусть у этих сетей имеется общий предок Шх, лежащий на слое Zк. Тогда рУ(Шг,Шз) = (г — к) + (] — к). Определенное таким образом расстояние является метрикой.

Представляет интерес еще одна метрика. Для сетей и Шз, применяя операции исключения промежуточных сетей, получим отображение и Шз на первичную сеть РБ. Тогда множествам ребер Шг и Шз будут соответствовать множества ветвей в РБ, N(Шг) и N(Шз) соответственно.

Определим между сетями Шг и Шз расстояние рР(Шг,Шз) = ^(Шг) и N(Шз)^(Шг)П N(Шз)||. Покажем, что введенное таким образом расстояние индуцирует псевдометрику МР: из определения и из равенства рР(Шг,Шз) = 0 не следует, что Шг = Шз.

Аксиома симметричности выполняется вследствие коммутативности операций П и и.

Покажем, что выполняется условие транзитивности. Так как на множества N(Шг) и N(Шз) не накладываются ограничения, то для произвольных подмножеств Z,X,Y Е N справедливо неравенство \(Х и Y)\(Х и Y)| < \(Х и Z)\(Z П X) и (^ и YП Y))|. Равенство имеет место, если Z С X и Y.

Очевидно, что в данной метрике максимальное расстояние между Ш г и Шз равно р(Шг,Шз) = \N(Шг) и N(Шз)\, т. е. не зависит от их расположения в РБ, если эти сети не пересекаются.

Для БН = (РБ,Шг, . Шп) можно предложить метрику Громова — Хаусдорфа. Пусть

Ь = р(Ш1,Шк) = штшахрнТ,т\), где р(т^,т1з) — метрика на пространстве всех ребер по Уз Мг з з

Рис. 8. Пример для доказательства справедливости метрического пространства

Г3 ^ • Как и для предыдущих метрИК, выполнены требованИЯ рефлексивности и симметричности.

Покажем, что для введенного расстояния выполнено условие транзитивности. Так как метрика Громова — Хаусдорфа справедлива на любых метрических пространствах, в которые отображены графы , условие транзитивности выполняется, вследствие того что граф первичной сети РБ является метрическим пространством.

Рассмотренные выше метрики не являются исчерпывающими для вторичных сетей Б-ги-персети БИ. Например, расстояние между графами вторичных сетей можно измерить сле-

дующим образом. Пусть задан граф объединенных вторичных сетей Ш =

(графы соединяют полюсы в каждом узле У1 (см. рис. 2,а)). Для определения расстояния между графами Шг и Шз достаточно в графе Ш вершины Шг и Шз склеить в Хщ1 и ущ.. Тогда рРвШгШз) = рщ (хщ> ).

Выполнение условий рефлексивности и симметричности следует из способа построения графа IV.

Рассмотрим ситуацию, приведенную на рис. 8. Здесь р(Ш\,Ш2) = а, р(Ш\,Ш3) = Ь, р(Ш2,Ш3) = с. Покажем, что Ь + т + с > а.

Очевидно, что Ь + с > а, так как к = 0 и I = 0. Справедливость неравенства следует из того, что Шк и Ш отображены в точки, а рщ(Шк) = а — длина кратчайшего маршрута. Таким образом, введенное выше расстояние является метрикой на метрическом пространстве НБ = (РБ,Шг. Шп).

8. Устойчивость. Б-гиперсеть называется устойчивой, если при заданном воздействии на ее структурные элементы численные характеристики сети остаются в определенных интервалах.

8.1. Операции над элементами сети или всей сетью. В данном пункте рассматриваются некоторые операции над элементами Б-гиперсети, которые приводят к ее изменению. 1. Удаление элементов (рис. 9):

— узлов (общее удаление, внутреннее, внешнее);

— вершин с инцидентными ребрами, т. е. вершин в графе вторичной сети;

— ветвей с инцидентными ребрами;

— ребер в графе вторичной сети;

— связей между сетями.

Рис. 9. Удаление элементов: а — элементы не удалены, б — внутреннее удаление, в — внешнее удаление

2. Изменение весовых характеристик элементов сетей:

— узла (с соответствующими весом, стоимостью, пропускной способностью);

— ветви (с соответствующими длиной, стоимостью, пропускной способностью);

— вершины (с соответствующими весом, стоимостью, пропускной способностью);

— ребра (с соответствующими длиной, стоимостью, пропускной способностью);

— связей (с соответствующими длиной, стоимостью, пропускной способностью).

3. Изменение структуры вложений (операций):

— малые изменения: перетрассировка ребра; перетрассировка к-ребер; смена отображений (вложений) двух вершин; циклическая перестановка вершин в узлы первичной сети; склеивание вершин;

— большие изменения: изменение структуры вложений вторичных сетей в первичную; перетрассировка всех ребер; переадресация всех вершин вторичной сети (т. е. новое отображение вторичной сети в первичную); исключение промежуточной вторичной сети а — Ь — с ^ а — с.

4. Изменение способа укладки: случайная укладка (отображение); специальная укладка (по заданному сценарию); оптимальная укладка.

8.2. Характеристики и атрибуты сети. В данном пункте рассматриваются основные структурные и численные характеристики, используемые в постановках различных задач теории Б-гиперсетей.

1. Структурные характеристики гиперсети:

1.1. Метрические (диаметр, радиус, матрица расстояний).

1.2. Потоковые (минимальный (в, ¿)-разрез, максимальный поток).

1.3. Связность (компактная связность, тотальная связность, К-связность, локальная (в, ¿)-связность (квазисвязность, слабая связность)).

1.4 Числа гиперсети (максимальная клика, минимальное покрытие, обхват, максимальная укладка и др.).

1.5. Свойства (гамильтонова, эйлерова, (к, -устойчивая, потокоустойчивая идр.)

2. Численные характеристики Б-гиперсети.

2.1. Характеристики вершин:

— aW(х) —степень х (число инцидентности) (число ребер в Ш, инцидентных вершинех);

— (х) — валентность (число полюсов).

2.2. Характеристики узлов:

— (у) — V-степень узла у Е Н (число ветвей);

— Б^(у) — г-степень узла у Е Н (число ребер);

— Vн (у) — валентность узла (число полюсов гиперсети Н);

— (у) — ранг узла (число вершин (отображений), вложенных в у Е Шг);

— Я(у) — абсолютный ранг узла у Е РБ С Н (число вершин всех сетей, отображенных в узел у).

2.3. Характеристики ребер:

— БХ[(г) — X-степень ребра г Е Ш (число вершин, инцидентных ребру у);

— Бщ (г) — У-степень ребра г Е Ш (число ветвей, инцидентных ребру г Е Шг).

2.4. Характеристики ветвей:

— Б^(у) — г-степень ветви V Е Н (число ребер, инцидентных у);

— Б^(у) — х-степень ветви V Е Н (число вершин, инцидентных у).

2.5. Характеристики сетей и конфигурации:

— глубина к(БИ) (число ярусов);

— ширина р(БН) (максимальное число сетей в ярусе);

— ранг слоя г(1) — число сетей в 1-м слое;

— Б(1) — степень слоя (число сетей в примыкающих слоях);

— Б(Шг) — степень сети (число сетей, непосредственно вложенных в сеть Шг);

— х(Шг) = (п, т,д,1, Ш) — структурная характеристика сети Шг (п — число вершин; т — число ребер; д — число вложенных сетей; I — номер слоя; Шз — сеть подложки (первичная сеть для Шг)).

На рис. 10 показан пример сети, имеющей следующие характеристики: глубина к(БН) = 7, ширина р(БН) = 4, спектр в(БН) = (1, 2, 3, 4, 3, 3, 2), число сетей п(БН) = 18; г(1) = I при I = 1 + 4.

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

Частично упорядоченная последовательность п = называется псев-догиперсетью, если не определены отображения ф(ШБ, РБ), ф(ШБз,ШБг) (] < I) для всех соседних пар вторичных сетей из п.

Псевдогиперсеть БИ =(РБ, ]¥Б, ф(WБ,PБ)) будем называть управляемой, если оператор ф( WБ, РБ) принимает значение из области П. Множество П задает множество эквивалентных гиперсетей П(БИ) =.

i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

Задача. Пусть заданы псевдогиперсеть БИ = (РБ, WБ) Е П и некоторая структурная характеристика /3(БИ) гиперсети БИ Е П(БИ). Требуется найти гиперсеть БИ0 Е П(БИ), так чтобы значение в (БИ0) было экстремальным или находилось в заданном интервале.

Так как |П| = 0(п\т\), то в общем случае данная задача решается методом перебора.

В дальнейшем псевдогиперсеть БИ будем называть управляемой гиперсетью и обозначать БЫп =(РБ,ШБ, ф(ШБ,РБ) е П).

Псевдогиперсеть, в которой не отображены только ребра, называется слабоуправляемой; если не отображены еще и вершины, то псевдогиперсеть называется сильноуправляемой. Если ф( ]¥Б,РБ) определено, то псевдогиперсеть не является управляемой. В том случае если в иерархической гиперсети БН = (РБ, ШБ\. ШБк) все пары (ШБШБг) управляемы, гиперсеть БИ абсолютно управляема, а если не все, то относительно неуправляема.

Псевдогиперсеть БИ = (РБ, ШБ) называется воспроизводимой (достижимой, доступной) относительно ф(ШБ,РБ) Е П, если значение в (БИ) принадлежит заданному интервалу при некотором отображении ф( ШБ,РБ).

10. Некоторые приложения теории 5-гиперсетей. В ранее опубликованных работах автора большая часть приложений теории гиперсетей была связана с областью телекоммуникаций и связи [1]. В работе [2] рассмотрены некоторые задачи оптимизации транспортных сетей мегаполиса. Ниже рассматриваются некоторые структурные модели городских сетей связи, а также транспортной системы, в которых математическим объектом является Б-ги-персеть.

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

По возможности математическая модель должна объединять все факторы, влияющие на облик и функционирование транспортной системы. Рассмотрим примеры взаимодействия раздичных городских пассажирских сетей. На рис. 11 представлена Б-гиперсеть с тремя видами транспортных систем: метро, автобус, трамвай.

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

— автомобильный транспорт: маршрутный пассажирский; индивидуальный пассажирский; грузовой; служебный; скоростной (с сиреной и мигалкой); специальный;

— электрический транспорт: троллейбусы, трамваи, скоростные электрички, электропоезда, метро, фуникулер, скоростной трамвай;

— узловая основа транспортных сетей: транспортные узлы; перекрестки дорог; стоянки, остановки общественного транспорта и других участников движения; парковки и другие места долговременных стоянок тредов; конечные остановки транспорта, вокзалы, автостанции, порты и другие места загрузки и разгрузки транспортных единиц;

— средства управления движением: светофоры; информационные щиты и электронные табло; дорожные знаки и указатели; дорожная разметка; полосы разгона и торможения на перекрестке; посты ГИБДД; правила дорожного движения; индивидуальные информационные и навигационные системы.

10.3. Уровни дорожно-транспортной сети. Уровни дорожно-транспортной сети (ДТС) задают структуру Б-гиперсети для формального описания.

Дорожная (первичная) сеть

Объединенная вторичная сеть

Рис. 11. Пример объединения (суммирования) всех вторичных сетей ^-гиперсети Н = (0о(01,02,Оз))

1. Основа ДТС: уличная сеть города, площади и перекрестки, туннели, внутридворовые проезды, стоянки и гаражи, различные препятствия и др.

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

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

4. Полоса движения — любая из продольных полос на проезжей части независимо от дорожной разметки, имеющая ширину, достаточную для движения в один ряд нерельсовых транспортных средств. Конечными узлами полос являются участки проезжих частей (аллели) между перекрестками, разветвлениями и другими узлами дорожной сети; рельсовые пути; полосы движения на дорогах; полосы движения с контактными проводами для троллейбусов; монорельсы.

5. Локусы — локальные участки сети на полосах движения, соответствующие местам, занимаемым транспортными единицами в течение определенного интервала времени.

6. Маршруты движения транспорта: утвержденные маршруты городского пассажирского транспорта; маршруты автотранспорта предприятий; маршруты индивидуальных и других транспортных единиц (тредов).

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

8. Граф локусов — наибольший граф по количеству вершин и ребер среди вторичных сетей Б-гиперсети транспортной системы города. Этот граф строится следующим образом. Аллели разбиваются на участки, в каждом из которых может находиться не более одного треда. В данном случае вершинами являются возможные остановки транспорта или границы между локусами. Две вершины считаются смежными, если тред может быть перемещен из одной вершины в другую за один такт процесса движения.

10.4. Задачи анализа и оптимизации для транспортных систем мегаполиса. В данном пункте приведены названия задач, которые рассматриваются и решаются учениками автора.

1. Моделирование транспортных потоков:

— математические модели потоков основных транспортных единиц внутри города;

— анализ транспортных потоков;

— распределение (проектирование) различных городских транспортных подсистем;

— классификация, моделирование и оптимизация транспортных развязок.

2. Модели передвижения пассажиров и товаров по городу:

— математические модели пассажиропотоков на городском транспорте;

— анализ и оптимизация маршрутов для пассажиров на городском и личном транспорте;

— математические модели грузопотоков и их оптимизация;

— организация транспортных потоков для обеспечения событийных переездов.

3. Управление транспортными системами:

— управление потоками транспортных средств путем расстановки разметок и развязок;

— управление потоками посредством светофоров и других сигнальных средств;

— оптимальное управление городскими транспортными системами и алгоритмы маршрутизации транспортных единиц;

— мониторинг движения транспорта и пешеходов.

4. Математические модели для задач оптимального размещения пунктов обслуживания транспортных средств и населения:

— бензозаправок и СТО;

— гаражей и других мест хранения транспортных единиц;

— остановок и временных стоянок транспортных единиц;

— мест обслуживания населения с использованием городского транспорта и др.

10.5. Задача управления светофорами на перекрестках любой конфигурации. Пусть задана Б-гиперсетевая модель любого транзитного перекрестка, т. е. на окружности диска геометрической модели узла уз располагаются полюсы, соответствующие входам на перекрестке. Пусть пара полюсов соединяется ребром и? = (хзк ,х31) и имеет место поток транспорта из полюса хк в полюс х\. В результате получаем граф Рг = (X, и), соответствующий потокам транспорта через перекресток уз. Вес V (из) характеризует величину потока машин за определенный промежуток времени. Если Б-гиперсеть нестационарная, то величина V(и3) зависит от времени ¿. Как правило, сутки можно разделить на несколько частей, в каждой из которых значение V(и3) изменяется незначительно. Для каждого выделенного промежутка можно составить расписание работы светофоров.

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

Сформулируем постановку задачи управления светофором. Множеству всех дуг , г = 1, . пз заданного перекрестка уз сопоставим пз — вершины некоторого графа

Рис. 12. Пример задачи управления перекрестками: а — модель перекрестка; б — граф зависимости потоков

G = (U, R). Две вершины u3k и uj смежны в G, если смежны соответствующие им дуги в орграфе Pj = (X, U) перекрестка yj.

Очевидно, что в графе Pj любому пустому подграфу Pk соответствует независимое множество потоков. В данном случае такое подмножество может быть максимальным. Семейство пустых подграфов, таких что (J Pk = Pi, определяет расписание работы све-iki тофоров, если наряду с открытием полос для движения определена длительность работы

каждого такта светофора.

Введем следующие обозначения: Xj = (x>l,xj2, ■ ■■,xk) — подмножество вершин в X, таких что подграф Pj = (XXj ,Uj) является пустым, т. е. uj = 0; V(Xj) — вес вершины xj;

bj = max V (Xj). Тогда целевая функция задачи имеет вид Ф = bj ^ min при условии

Таким образом, семейство подграфов P = покрывает все вершины графа G и не содержит ни одного ребра из b, т. е. P Р| G = X. Очевидно, что некоторое расписание работы светофора получается из решения Ф следующим образом. Для каждого подмножества независимых полос, соответствующих Pj, время работы на j-м такте определяется выражением

где Т — циклический период работы светофора.

На рис. 12 приведен пример узла гиперсети со всевозможными потоками между полюсами. Заключение. В работе рассмотрены некоторые основные понятия и определения теории Б-гиперсетей. Показано, что в рамках данной теории можно строить адекватные модели для решения различных задач для систем сетевой структуры.

1. Попков В. К. Математические модели живучести сетей связи. Новосибирск: ВЦ СО АН СССР, 1990. 233 с.

2. Попков В. К. Математические модели связности. Новосибирск: ИВМиМГ СО РАН, 2006. 490 с.

3. Попков В. К. Методы оптимизации структур зоновых сетей связи / В.К.Попков, С.Б.Кауль, М.И.Нечепуренко. Новосибирск: ВЦ СО АН СССР, 1983. 182 с.

4. Попков В. К. Математические модели и методы оптимизации городских транспортных систем // Материалы 2-й Всерос. конф. «Проблемы оптимизации и экономические приложения», Омск, 29 июня — 4 июля 2009 г. Омск: Б. и., 2009. С. 80-81.

Попков Владимир Константинович — д-р физ.-мат. наук, проф., гл. науч. сотр. Института вычислительной математики и математической геофизики; e-mail: popkov@sscc.ru

Дата поступления — 2.09.2010

Сверхэффективная нейронная сеть или гиперсеть

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

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

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

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

Причём во главу угла стоит ставить скорость обучения сети, а качество или точность сейчас второстепенны.
Только супер эффективная нейронная сеть (СНС) может быть фундаментом и основой для создания искусственного интеллекта.
Имея технологию СНС можно двигаться различными путями, как создавая когнитивные архитектуры на основе графов, гиперграфов и т.д. плюс СНС, так и двигаясь биологическим путём повторяя архитектуру биологического мозга. Я сторонник биологического подхода, хотя и не считаю этот путь единственным в достижении цели.

  1. Первый этап. Создание модели сенсорных анализаторов в первую очередь зрительных и слуховых. Вообще сенсорные анализаторы биологической нервной системы и должны стать прообразом сверхэффективных нейронных сетей (СНС).
  2. Второй этап. Получение знаний о механизмах мгновенной, временной и долговременной памяти в концепции СНС. Биологические сенсорные анализаторы легко работают с контекстом, только понимание концепции памяти в биологических нейронных сетях позволит перенять возможность работать с контекстом, что сильно расширит возможности СНС.
  3. Третий этап. Создание моделей моторных сетей. Не смотря на гомогенность коры головного мозга моторные сети в некотором смысле более сложно устроены, чем сенсорные анализаторы, хотя есть некоторое глубокое сходство. Поэтому этот этап не будет затянутым. В моторные сети будут входить модель мозжечка, как структура, запоминающая и воспроизводящая короткие временные интервалы для точности движений. А так же некий механизм поощрения, для обеспечения обучению правильных движений, аналогичный дофаминовыми механизмами поощрения в биологическом мозге.
  4. Четвертый этап. Одним из важных форм моторных действий является речь. Возможно, по этой причине этот и предыдущий этапы будут воплощены синхронно. На этом этапе речь не будет в полной мере осознанной. Подобно человеку должны быть пройдены этапы развития речи, такие как гуление, произношение отдельных звуков, затем слов. Максимальный уровень владения речью на этом этапе, это называние предъявленных предметов, описание сцен, ответы на простые вопросы, чтение или декларация текста. На этом этапе буде заложена основа для сети речевого круга (О речевом круге я подробно писал в статье «Что такое сознание»).
  5. Пятый этап. Создание модели базовых эмоций и потребностей. Этот этап не будет являться чётким этапом, многие его концепции будут проявляться и на более ранних этапах. Главной фундаментальной эмоцией, которую необходимо моделировать – это эмоция новизны. Достаточно создать оценочный механизм новизны информации на различных уровнях абстрактности и производить на его основе модуляцию параметров сети. Любопытство необходимо для эффективного обучения.
    Также нужно обеспечивать модели чувствами необходимыми для контроля их потребностей. К примеру, низкий заряд батареи робота мог бы создавать некие чувство голода для робота, и робот бы стремился удовлетворить его, то есть стал бы искать зарядное устройство или источник питания. Или создание некого чувства боли или дискомфорта, чтобы робот избегал травмирующих его ситуаций.
    Еще одна полезная эмоция, которую легко можно подвергнуть моделированию это различного рода привязанности. В основе привязанностей лежит механизм импринтинга. Это будет полезно для различного рода роботов-помощников или роботов-питомцев, от которых требуется следовать за хозяином или некоторая преданность.
    Человек более охотно будет взаимодействовать с интеллектом похожим на него, поэтому возможно появление более широкого спектра эмоциональных механизмов. К примеру, тревожности и страха, симпатии, радости и разочарования.
    Что касается внедрения на уровень базовых эмоций законов робототехники Айзека Азимова, то они имеют высокий абстрактный характер, что сильно усложняет их моделирование. Сначала модель должна быть обучена на столько, чтобы можно было выявить репрезентацию образов «Человек» и «причинение вреда», подобно тому, как у человека можно найти «бабушкины нейроны». Затем можно связать эмоциональный механизм со стремлением избегать сочетания этих образов. Сложно сказать, насколько такой метод будет эффективным.
  6. Шестой этап. Можно сказать, что этот этап такой же сложный, как и первый, если не сложнее. Условно его можно его можно назвать этапом префронтальной коры. Префронтальной коре головного мозга присваивают высшую когнитивную деятельность, здесь можно сказать, расположено суждение и долгосрочное целеполагание. Префронтальная кора контролирует работу эмоциональных центров и центров потребностей, она регулирует то, насколько сильно они влияют на поведение.
    Работа на этом этапе требует глубоких знаний о поведении человека. Только на этом этапе можно рассуждать и говорить о сознании и сознательном поведении. К этому этапу я отношу не только создание префронтальной коры, но и несколько важных биологических нейронных сетей и механизмов. К примеру, сеть «интерпретатор», которая стремиться дать обоснование любому нашему действию. Наличие таких сетей явно проявляется в экспериментах с участием людей с разделёнными полушариями мозга.
    Или сеть ответственная за иллюзию квалия, создающие ощущения централизованного восприятия мира. Также механизм восприятия границ своего тела и действий, нарушение этого механизма у людей может приводить к навязчивому стремлению избавиться от части своего тела или не способность различать свои действия от действий другого человека.
    Мы знаем, что нарушения в различных психических механизмах могут приводить к различным болезням аутистического спектра или различных форм шизофрении. На пути к искусственному интеллекту суждено встретится с примерами этих отклонений в искусственной психике, но у этого есть и полезное зерно. Работа над искусственным интеллектом позволит понять лучше природу психических болезней человека.

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

Далее я расскажу подробней, на каких принципах она основана и то, как я её реализую.

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

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

Индукция – это возникновение областей торможения на коре вокруг участка возбуждения. Это может быть связанно с тем, что отростки нейронов одной колонки на некотором расстоянии колонки могут образовывать связи с ингибирующими клетками других колонок. Характер ингибирующего (тормозящего) воздействия на соседние колонки можно представить следующим образом:

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

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

Пример работы шейдера, размер изображения 28х28 пикселей, радиус действия колонки 5 пикселей, шейдер применяется несколько раз:

Радиус действия колонки 7 пикселей:

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

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

Узлы – это вторая сигнальная система, это символьное представление образов в мозге, это коги.

Удивительно то, насколько простыми и элегантными решениями пользуется кора и мозг в целом.
Чтобы разобраться в том, как узлы могут хранить в себе образы или части образов, требуется изучить ещё один механизм, работающий в коре.

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

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

Карта таламического ядра, на которую мы будем проецировать некоторые образы, в данном случае примеры рукописных цифр из стандартного набора MNIST. Изображения в наборе MNIST имеют формат 28×28 пикселей, поэтому эту карту мы также установим 28×28 пикселей.
Карта коры будет составлять в данном варианте 21×21 пиксель.
Карта восходящих синаптических связей будет хранить в себе значения всех весов синапсов связывающих карту таламического ядра и карту коры. Условно каждый пиксель-гиперколонка коры будет иметь синапсы с 64-мя (ядро 8×8) пикселями карты таламического ядра. Если перемещать ядро 8×8 пикселей по карте таламического ядра шагом в один пиксель, то таким образом можно составить карту восходящих синаптических связей. Соответственно отсюда и получится размер карты коры 28 – 8 + 1 = 21, в свою очередь размер карты восходящих синаптических контактов будет составлять 168×168 пикселей (21 x 8 = 168).

Вес синапса будет определяться числом от 0 до 1 – это удобно для графического отображения на карте и позволяет хранить и обрабатывать эти параметры в форме изображений, что также удобно в работе с шейдерами, а также очень наглядно.
Еще один важный момент, в моделях, которые я буду описывать, присутствует всегда по две карты синаптических связей: одна карта побудительных синапсов, вторая карта тормозящих синапсов. Это всегда две одинаковые по размеру карты.
Известно, что тип синаптического контакта в биологической нервной системе в течение жизнедеятельности не меняется, то есть побудительный синапс не может стать тормозящим или наоборот. В компьютерных нейронных сетях знак веса синапса может легко изменяться в процессе обучения, что для модели претендующих на биологичность не является правильным.

В колонках коры помимо побудительных пирамидальных нейронов присутствуют множество тормозящих нейронов, и любой аксон от побудительной клетки направленный к колонке может создать синаптический контакт, как с побудительной, так и с тормозящей клеткой. Аналогично этому у нас имеется по две карты синаптических контактов, одна будет действовать со знаком «плюс», другая со знаком «минус». В обеих этих картах вес будет определяться числом от 0 до 1.
Значение весов восходящих синаптических контактов заполним случайными числами от 0 до 1.
Карта нисходящих синаптических связей будет иметь значительно больший размер. Как уже отмечалось нисходящих связей в биологическом мозге в несколько раз больше. В нашем случае мы выбираем такой размер карты, который позволит продемонстрировать концепцию хранения образов в узлах. Каждый пиксель-гиперколонка карты коры будет связан с каждым пикселем карты таламического ядра, то есть с каждым 784 пикселем (28 x 28 = 784), тогда размер карты составит 588×588 пикселей (21 x 28 = 588).
Изначально значение весов в карте нисходящих синаптических связей все будут равны 0, но данные веса мы изменим в процессе обучения.
Метод обучения, который мы в данном случае применим для нервной системы был экспериментально подтверждён. Он известен, как правило Хебба, самая простая его интерпретация: вместе срабатываем, значит укрепляем связь; а так же обратная сторона: не сработали вместе – связь ослабеваем.
Для начала предъявим нашей модели пример, проецируя его на карту таламического ядра. Затем через восходящие связи оказываем суммирующее воздействие на карту коры. Для каждого пикселя карты коры складываются все соответствующие ему значение весов из карты восходящих синаптических связей умноженное на значение уровня активности соответствующих пикселей карты таламического ядра. Значение весов из тормозящей карты восходящих синаптических связей будет складываться со знаком «минус». Полученная сумма умножается на подобранный коэффициент, именуемый коэффициент чувствительности. В данном случае он равен 0,5.
Если полученная сумма меньше или равна нулю, то активации пиксель-гиперколонки не происходит, его активность равна нулю. Если полученная сумма больше единицы, то значение пикселя карты коры будет равна единице, как максимальная степень активации гиперколонки. Если сумма имеет значение в интервале от 0 до 1, то пиксель-гиперколонка карты коры примет это значение.

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

Далее к карте коры мы применяем шейдер механизмов иррадиации и индукции. Этот шейдер мы можем применить несколько раз. Как результат получаем на карте коры несколько узлов.
Затем обращаемся к карте нисходящих синаптических связей и применяем к ней правило Хебба для обучения. Причём мы его применяем следующим образом: в случае совместного срабатывания мы в значительной степени усиливаем синаптическую связь. Если пресинапс срабатывает, а постсинапс нет, то ослабеваем синаптическую связь лишь на небольшое значение. В данном случае, при совместном срабатывании вес синапса увеличится на 0,8, при отсутствии совместного срабатывания вес уменьшится только на 0,1. Большее значение имеет именно совпадения, чем их отсутствие. Обратите внимание, что настраивается пресинапс, а не постсинапс, хотя сейчас это не имеет критического значения, так как весь синапс у нас регулируется одним весом, но это имеет важное идеологическое значение. Дело в том, что в классических нейронных сетях акцент даётся на настройку постсинапсов, и полностью игнорируется изменения в пресинапсах, хотя в биологических нейронных сетях изменения происходят в обеих частях синапса, и в пресинапсе они зачастую более ярко выражены (Сравнение мозга с нейронной сетью).

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

Можно увидеть, что в картах нисходящих синаптических связей отражаются образы целых цифр, причём ы тех местах, которые соответствуют узлам, которые активизируются на данные образы. Это возможно потому, что выбранное количество обратных связей для каждой микроколонки охватывает всю карту таламического ядра, в случае если обратные связи охватывали только часть карты, то и гиперколонка могла бы хранить в себе только часть образа. Так в узлах может быть записаны некоторые образы или некоторые составные части образов.
Узел при его активации как бы «смотрит» на ту активность, которая его активизирует и сохраняет её в себе. В узлах хранятся как бы некие эталонные примеры образов.

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

Моделирование действие LSD на кору больших полушарий
Это небольшое отступление продемонстрирует некоторое сходство нашей модели и работы биологического мозга. Дело в том, что для нас действие LSD на кору очень просто смоделировать. LSD своим действием мешает работе нейротрансмиттера ГАМК, который является главным ингибирующим нейромедиатором коры, он работает в механизме индукции. Поэтому чтобы это смоделировать, достаточно в настройках нашего пиксельного шейдера уменьшить степень действия индукции.

Как мы видим при этом привычные границы, и размеры узлов размываются и расширяются. Если еще уменьшить действие индукции то очаги активности могул сливаться, формируя некоторые узоры. Аналогичные явления могут происходить и в коре больших полушарий под действием LSD, о чём косвенно свидетельствует снимки МРТ сделанные у людей принявших LSD, активность коры в данном случае значительно большее и масштабнее, чем при обычной работе мозга. Учитывая, что практически каждая колонка хранит в себе образы или их части, то становиться понятным, почему происходит путаница и смешивание образов, понятны причины нарушения восприятия. Такие нарушения работы мозга не могут быть полезны для него.

Наркотики вредны для здоровья и здоровья мозга.

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

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

В нашем варианте на карту таламического ядра размером 28×28 пикселей мы применим карту связей нерва размером 512×512. Эта карта нерва будет связывать карту таламического ядра с картой коры размером 64×64 пикселя, то есть разбить всю карту связей нерва на квадраты 8×8 пикселей, то каждый такой квадрат включит в себя все связи пикселем-гиперколонкой (512 / 8 = 64).

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

Соответственно карты восходящих синаптических связей будут иметь размер 512×512 пикселей.
Карта нисходящих синаптических связей будет иметь размер 1024×1024, по причине, что количество рекуррентных связей должно быть больше для стабильных ревербераций. Здесь каждому пикселю карты коры будет соответствовать 16×16 пикселей карты таламического ядра (64 x 16 = 1024).

Следующий уровень обработки информации представлен картой выхода, которая имеет размер 1×10, по одному пикселю на цифру, так как наша сеть нацелена на распознавание рукописных цифр из стандартного набора MNIST. Карта выхода связана с картой коры аналогично, как и карта таламического ядра с картой коры. Соответственно также имеются карты восходящих синаптических связей и карты, нисходящих синаптических связей, которые имею размерность 64×640 пикселей. Таким образом каждый пиксель карты коры имеет синаптический контакт с каждым пикселем карты выхода, для того чтобы пиксели карты выхода имели максимальное рецептивное поле. Нисходящие синаптические связи как уже отмечалось, обычно имеют большее количество, чем восходящие, но в данном случае они будут одинаковы в количестве потому, что это будет максимальный размер обратных синаптических связей. Так каждый пиксель карты выхода «видит» каждый пиксель карты коры.

Обучение или настройку карты восходящих синаптических связей второго уровня можно провести по правилу Хебба, которое мы уже применяли. При этом во время обучения мы будем считать активным или равным 1 пиксель карты выхода, который соответствует цифре, пример которой предъявлен сети. Тем самым мы как бы связываем некоторую активность на карте коры с требуемым выходом и укрепляем эту связь. Это похоже на формирование рефлекторной дуги условного рефлекса, как представительство цифры связывается связями с комбинацией активных пикселей в карте таламического ядра. Таким образом, фактически не связанные элементы прямыми контактами за счет рекуррентных связей могут связываться и укреплять свои связи между собой. И это может работать через множество уровней.

Но если обучать или настраивать по правилу Хебба карту восходящих синаптических связей первого уровня, это правило приводит к тому, что слабоактивные пиксель-гиперколонки за счёт усиления с ними связей будут усиливать свою активность до максимума, и это создаст большое количество активных пиксель-гиперколонок, что приводит к взаимному подавлению при применении индукции. И это приводит к сильному снижению качества сети.
Поэтому мы применим другой способ обучения. Он будет состоять из двух этапов. Первый этап – это инициализация образов. На этом этапе мы сформируем некое базовое представление о каждом распознаваемом образе цифры, на малом количестве примеров. Для этого достаточно от 10 до 100 примеров, или от 1 до 10 примеров на одну цифру. На этом этапе будут настраиваться все карты синаптических связей кроме карт восходящих синаптических связей первого уровня, но они должны быть заполнены случайными значениями.

Сначала проецируем пример на карту таламического ядра, затем производим суммацию с применением случайных весов карты синаптических связей. Прежде чем применить шейдер иррадиации и индукции мы можем повлиять на карту коры, так чтобы итоговые узлы не совпадали для разных цифр. Для этого обратимся к карте нисходящих связей второго уровня, которая хранит в себе «отпечатки» паттернов узлов для каждой цифры сформированной на основе предыдущего опыта. Соответственно если такого опыта не было, то на карту коры не будет оказано никакого влияния. К примеру, если примером является цифра «5», то к карте коры мы прибавим значения побудительной карты нисходящих синаптических связей сектора соответствующих образу цифры «5». Это повысит шансы на образование узлов в том же месте, где эти узлы образовывались в прошлом акте обучения цифре «5». Так же мы вычтем из карты коры значения остальных секторов не связанных с цифрой «5». Это способствует тому, что узлы не будут образовываться в тех местах, которые соответствуют другим цифрам.
После такой коррекции значений карты коры применяем пиксельный шейдер ответственный за иррадиацию и индукцию.

Затем настраиваем карты восходящих синаптических связей второго уровня по правилу Хебба, с учётом того что на карте выхода будет активным пиксель соответствующий предъявляемому примеру.

Так же по правилу Хебба настраиваем карты нисходящих синаптических связей второго и первого уровня.

Так выглядят синаптических связей после такого обучения на 100 примерах(a и b карты восходящих побудительный и тормозящих синаптических связей второго уровня; c и d карты нисходящих побудительных и тормозящих синаптических связей второго уровня; f и g карты нисходящих побудительных и тормозящих синаптических связей первого уровня):

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

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

На видео обучение сети на 100 случайных примерах и тест на 10 000 тестовых примерах. В зависимости от выбранных обучающих примеров, возможно, от случайно выбранных весов для карты восходящих синаптических связей сеть в таком тесте выдает результат в диапазоне от 40 до 60%, увеличение количества примеров не даёт улучшения качества. Это очень скромный результат, но для данной задачи требуется более сложная архитектура сети. Числа и знаки распознаются нашим мозгом на достаточно высоком абстрактном уровне. Соответственно в модели требуется больше уровней. А также в биологическом зрительном анализаторе применяется некоторый дополнительный механизм, специальный фильтр из сетей нейронов, которые реагируют на определённой ориентации раздражители. Этот фильтр упрощает обработку зрительной информации. Добавление подобного фильтра, так же должно улучшить качество нашей сети. Все эти модификации требуют дальнейших исследований, над которыми работа будет продолжаться. Цель статьи и это примера рассказать о некоторых теоритических аспектах модели и подхода в целом.

Обычно художник не рисует картины подобно плоттеру, начиная с верхнего угла нанося сразу все детали бедующего произведения. Художник для начала наносит на холст эскиз из тонких еле заметных линий обозначающий общий план художественного замысла. Постепенно картина обрастает деталями, все более и более мелкими, в конце наносятся лишь самые точные и едва заметные мазки кистью. Подобно этому нужно подходить к вопросу моделирования мозга. Безнадёжно пытаться подробно моделировать, последовательно создавая кортикальные модули с множеством синаптических связей с большим разнообразием типов нейронов и нейромедиаторов. Лучшее решение это создавать изначально простые симуляции отдельных механизмов постепенно добавляя в модели необходимые детали.

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

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

  • искусственный интеллект
  • мозг
  • нейронные сети
  • гиперсеть
  • Искусственный интеллект
  • Мозг

Детальный гайд по тренировке гиперсетей для Stable Diffusion ⁠ ⁠

Детальный гайд по тренировке гиперсетей для Stable Diffusion Нейронные сети, Гайд, Stable Diffusion, NovelAI, Арты нейросетей, Искусственный интеллект, Нейроарт, Длиннопост

Я не уверен, в какое сообщество постить данный гайд, так как конкретно информационно-ориентированного сообщества на данный момент нет, то попробую запостить в арт. Я понимаю, что не совсем по теме, но вроде правилами не запрещено постить обучающие посты, ориентированные в большинстве своём на текстовую информацию.

Но картинки будут. В конце. Не бейте.

Данный гайд я ещё на ДТФ написал, и недавно на нём же мне и напомнили о существовании Пикабу. Проверил, как тут с постами по нейросеткам, а здесь даже меньше, чем там. Надо исправлять. Сейчас там творится полная уйня с обновлением сайта, так что возможно придётся переползти сюда, но собственно почему бы и нет.

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

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

Весь гайд будет базирован на AUTOMATIC1111, как вы могли понять.

Я ожидаю базовой нейро-грамотности, вы уже расставили базовые настройки, как выгрузка VAE и CLIP на время тренировки.

Сам гайд будет базирован в большой части на данном треде с гитхаба: https://github.com/AUTOMATIC1111/stable-diffusion-webui/disc. ?
И если вы спик инглиш, а так же не боитесь читать какие-то страшные технические тексты, то прошу так же заглянуть туда.

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

Дисклеймер: автор гайда любит маняме девочек

Предисловие

Я не буду разбирать основы, как запустить веб интерфейс и какие функции в настройках вам нужно включить. Я буду ожидать, что все вы уже выгрузили ваши VAE и CLIPы, и готовы к базовым процессам тренировки. Xformers можно не выключать, они и так не работают при тренировке гиперсетей(возможно сейчас работают, не проверял, старая информация), даже если включены в настройках.

Так же я ожидаю, что вы уже поставили флажок —deepdanbooru и знаете для чего оно нужно, а так же приготовили датасет для обучения.

И вы знаете, что нужно использовать модель с полными весами(но можно и не).

А теперь можно приступать к основному.

Кто такая эта ваша н***й функция активации

Детальный гайд по тренировке гиперсетей для Stable Diffusion Нейронные сети, Гайд, Stable Diffusion, NovelAI, Арты нейросетей, Искусственный интеллект, Нейроарт, Длиннопост

Вот встречает нас такая хрень, ничего не понятно, кроме имени.

Давайте по порядку.

Модули — хер знает, Автоматик писал, что 768 — это база. А остальные дополнительные. Пока нет детальных тестов, которые показали бы разницу между этими галочками, поэтому оставляем всё включенным.

Для тренировки гиперсетей на базе моделей SD 2.X был добавлен пятый модуль — 1024.

Структууууура — это нам надо знать.
Вкратце — это то, сколько нейронов и на каких слоях вы размещаете.
Первый и последний слой всегда 1, это входной и выходной уровень гиперсети. А вот в середине между ними вы может разместить какое угодно количество слоёв с какой угодно широтой.

Широта и глубина
Это понятия, которые мы отнесём к структуре слоёв.
Широкие нейросети хороши для запоминания объектов, по типу 1 4 1, а глубокие — для стиля, по типу 1 1.5 1.5 1
Одновременно широкие и глубокие сети работают плохо, по словам Heathen. Частично с этим соглашусь, но подозреваю, что долгая тренировка сможет утилизировать таковые.

ВНИМАНИЕ — Структура гиперсети влияет на то, сколько она занимает места, в том числе в памяти видеокарты во время тренировки. Если у вас как и у меня нищенская 3070ти на 8 гигов, то нам не светит тренировка широких гиперсетей, по крайней мере под виндой, и если хочется посмотреть видосиков пока она тренится. 1 3 1 уже вызовет ООМ ошибку после нескольких шагов, по крайней мере у меня. В основном сейчас я тренирую 2.4 0.8 тип сетей, и результаты меня вполне устраивают, но так как я любитель больших и длинных… Тренировок, то материала на сравнение особо не предоставлю, особенно под новую модель.

UPD: если не генерировать картинки, то возможно тренировать и ширину в 4, но трудно, ООМ будет мешаться всё-равно, но как-то через раз.

А кто такая эта ваша функция?
А тут на наш вопрос ответят питон-программисты, ведь это их функции активации. А я не питон. И не программист. Возможно к сожалению. Но скорее нет, чем да.
Всё, что вам нужно знать, это то, что Linear — работает и является базой модели SD, поэтому это стабильный вариант для стандартных гиперсеток.
Так же хороши rrelu, gelu, swish, softsign и т.д. и. т.п.
Мой любимец — Gelu. Heathen, автор основного гайда, от которого я отталкиваюсь(+ свой опыт), тоже оценил его высоко.
Любимцы Heathen:
Tanh/Softsign для фото/ирл при Normal активации. Xavier для арта с нуля.
Gelu/RRelu как альтернатива вышеназванной паре, но более мягкая.
Mish — Ещё мягче, чем Gelu. На Normal или Xavier активации.
Так же он называет активации для разных медиумов, типа арта и т. д., но, честно скажу, у меня не получилось это проверить и выдавало шум. Возможно нужна более долгая тренировка, ибо указано, что для обучения с нуля, то есть рандомный вес = изначальный шум. Но об этом мы поговорим в следующей части.

UPD: разные активации работают, но менее стабильны как по мне, поэтому в этой обновлённой версии я их указал.

Нормально? Или не нормально.
Инициализация весов. Это рандомизация, или распределение весов нейронов. Это так же математика, поэтому конкретно мне сказать нечего.

Используйте Normal, что бы работать на базе того, что уже знает модель, на которой тренируете, что бы она двигала стиль/знание объектов в сторону того, что вы тренируете. Ксавьер и Кайминг — изначально будет лишь шум на первую тысячу-две шагов, но постепенно перейдёт в арт.(Но пока всё-таки это не точно)

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

UPD: на monkeypatch при некоторых условиях артефакты могут проявляться и на правильной тренировке, например если включену cosine annealing warmup restart(или как-то так), так как оно ступенчато понижает и переинициализирует рейт тренировки, тем самым повышая шанс на то, что гиперсетка поджарится, если рейт окажется слишком высоким. Но в данном гайде мы не будет рассматривать Monkeypatch, это более продвинутая тренировка, пока оно вам не надо.

Dropout
Не выкидывайте свои нейроны, их иногда и так мало. На данный момент функция негативно влияет на тренировку.(Monkeypatch позволяет задать свои параметры дропаута)
Она отключает 30% ваших нейронов, то есть, условно поставили 1 3 1 — оно не будет использовать все 3, а будет только лишь чуть больше 2. По словам Heathen, данная функция бесполезна для небольших нейронных сетей, коей и является гиперсеть.
Не включать.

Пару слов о препроцессинге датасета

Если он маленький — пройдитесь ручками и расставьте теги самостоятельно в дополнение к deepdanbooru — упростите себе жизнь.

UPD: лушче используйте WD 1.4 Tagger, тогда не придётся ручками корректировать deepbooru по большей части.

Нейроны тоже тренируются

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

Детальный гайд по тренировке гиперсетей для Stable Diffusion Нейронные сети, Гайд, Stable Diffusion, NovelAI, Арты нейросетей, Искусственный интеллект, Нейроарт, Длиннопост

Ну вот оно нас встречает, а дальше что? Запускаем со стандартными настройками?
А вот х*р там.

Идём в \stable-diffusion-webui\textual_inversion_templates
и создаём файл, который в себе содержит только «[filewords]», если вы тренируете маняме. Если нет — оставляете стандартное(меняете subject или что-то там на hypernetworks).
Ну и соответственно вписываем путь на этот новый файл, или уже существующий, если тренируете обычную, не маняме модель.
Шаги — сколько хочется. Рекомендую для старта около 10000. Но тренировать, при правильном подходе, можно хоть до 100к.
Batch size — Если у вас 8 гигов, не трогайте, не хватит памяти на больше чем 1. Для остальных — больше лучше. Хотя буст скорости выше 2 уже не особо будет. Влияет на качество тренировки, но как именно — пока сказать трудно. Если учитывать наблюдения Dreambooth, которые я недавно читал, то больший размер позволит лучше работать с некторыми деталями, как например руки.
По умолчанию сетка будет сохраняться каждый 500 шагов, поэтому приготовьте пару десятков гигабайт места, либо увеличьте параметр сохранения. Уберите галочку с «save images with embedding in png chunks» — я вообще не понял, зачем оно надо, бесполезная штука, которая сохраняет картинки результатов, но с оверлеем названия сети и шагов, что она и так делает, но в названии самого файла.
Читать параметры — ставьте, если хочется контролированной генерации картинок при тренировке. Но не забудьте указать их во вкладке генерации.

А что по скорости обучения?
А вот тут мы остановимся. Нужно пояснить, что то, что у вас там написано — на самом деле не обязательно одно число.

5e-5:125, 5e-6:1500, 5e-7:8000, 5e-8:20000, 5e-9:-1

Такое — тоже работает, более того — вы обязаны использовать вариативную тренировку, если хотите тренировать долго и ради мощного результата.

Это один из небольших и общих примеров таких вариаций. Я использую другую, но вам оно не надо, ибо я использую более агрессивную стратегию и куда больше шагов.

Так же не забывайте на каждый слой вашей гиперсети поднимать рейт тренировки. Точно сказать не могу на сколько, но по моим экспериментам примерно на ступень. То есть не 0.00005, а уже 0.0005, если добавили ещё один слой. Но скорее всего это многовато и лучше обойтись повышением раз в 6-7 на каждый новый слой.

Апдейт по новым параметрам

Аккумуляция градиента

Важный новый параметр, который раньше был только через фиксы. Поставьте его на примерно 3-6, если уверены в качестве своего датасета. Он позволит аккумулировать градиенты картинок. Возможно сильно увеличить качество тренировки. Но, только если картинки хорошие, в одном стиле и т.д.

ВАЖНО: поменяйте рейт тренировки в соответствии с размером батча и градиента.

То есть, если у вас например батч 4 и градиент 4, то за один шаг у вас происходит тренировка на 16 картинках, ускоряйте рейт тренировки в 16 раз +-. Это работает для меня. То есть например 5е-5:160 превращается в 5е-5:10 и т.д.

Shuffle tags

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

Drop out tags

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

Latent Sampling

Once — стандартный параметр, генерирует латентное пространство один раз. Не хорошо.

Deterministic — процесс не опишу, но автор утверждает, что это приносит результаты лучше, чем полный рандом.

Random — как должно быть изначально, но не было.

Я тренирую на детерминистичном.

Ну, это всё, что нужно знать в базе для правильной тренировки

А что не в базе? А не в базе идите читать англоязычные статьи. Очень интересно. Посмотрите глазами, как выглядят функции активации, я таким методом и выбрал Gelu как основу ещё до появления гайда по ним от Heathen.

Заключение Я уже месяца два изучаю всю эту хрень(на момент написания на ДТФ). Очень интересно, затягивает, а ещё я аниме люблю, поэтому провожу много тренировок гиперсеток для стиля. Показать не смогу сейчас, ибо тренирую стили заново на новую Anything3 модель, покажу только один.

Решил написать этот гайд, ибо увидел, что есть много неправильных, даже негативных заключений в текущих кратких руководствах, хоть и называют их дебрями.(Это про ДТФ)

На пикабу так вообще, всё, что есть это сравнение гиперсетей NAI, что, обучающим контентом по гиперсетям, считать даже с натяжкой невозможно.

Детальный гайд по тренировке гиперсетей для Stable Diffusion Нейронные сети, Гайд, Stable Diffusion, NovelAI, Арты нейросетей, Искусственный интеллект, Нейроарт, Длиннопост

Так меняет картинку моя основная гиперсеть, тренированная на 60000 шагов. По сути, полностью новая генерация.
НО. Это не лучший пример, так как тренировано по ошибке на модели с неполными весами.

Да и вообще я щас занялся тренировкой LORA, поэтому не перетренировывал.

Ну, как и обещал, подборочка артов из моих последних генераций :3(Отличных от подборки на ДТФ), все они сгенерированы с помощью гиперсетей.

Детальный гайд по тренировке гиперсетей для Stable Diffusion Нейронные сети, Гайд, Stable Diffusion, NovelAI, Арты нейросетей, Искусственный интеллект, Нейроарт, Длиннопост

Детальный гайд по тренировке гиперсетей для Stable Diffusion Нейронные сети, Гайд, Stable Diffusion, NovelAI, Арты нейросетей, Искусственный интеллект, Нейроарт, Длиннопост

Детальный гайд по тренировке гиперсетей для Stable Diffusion Нейронные сети, Гайд, Stable Diffusion, NovelAI, Арты нейросетей, Искусственный интеллект, Нейроарт, Длиннопост

Детальный гайд по тренировке гиперсетей для Stable Diffusion Нейронные сети, Гайд, Stable Diffusion, NovelAI, Арты нейросетей, Искусственный интеллект, Нейроарт, Длиннопост

Больше не покажу, учитесь сами 😀
P. S. Пишите, спрашивайте, отвечу.

Я планирую перенести и остальные свои записи с ДТФ на Пикабу с дополнениями, фидбэк приветствуется.

На очереди такие гайды как:
От NAI-сойжака до кастом гигачада
Гайд по правильному промпт-крафтингу универсальных стилей для Stable Diffusion
LORA, почему кажется, что не работает, и как не потратить день в пустую

Если вам интересна какая-та конкретная тема — пишите, перенесу её в первую очередь, или напишу гайдец, если знаком с ней.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *