Содержание к диссертации
Введение
1. Проблемы современных систем мониторинга СНО 7
1.1. Средства навигационного оборудования как объект мониторинга 8
1.2. Классификация технологий передачи данных в системах мониторинга СНО 15
1.3. Технология беспроводных сенсорных сетей 22
2. Проектирование коммуникационной инфраструктуры системы мониторинга СНО на базе технологии сенсорных сетей 31
2.1. Структурная надежность коммуникационной инфраструктуры системы мониторинга СНО 32
2.2. Энергетическая эффективность коммуникационной инфраструктуры системы мониторинга СНО 35
2.3. Математическая модель задачи оптимального размещения шлюзов в сенсорной сети 39
2.4. Алгоритм определения пригодности схемы размещения шлюзов 47
2.5. Методика проектирования коммуникационной инфраструктуры системы мониторинга СНО на базе технологии сенсорных сетей 56
3. Обеспечение надежности сети системы мониторинга СНО 62
3.1. Методика обеспечения двусвязности сети 62
3.2. Влияние методики обеспечения двусвязности на размер множества вариантов размещения шлюзов 72
4. Обеспечение энергетической эффективности системы мониторинга СНО 75
4.1. Точный алгоритм 76
4.2. Генетический алгоритм 86
4.3. Алгоритм муравьиной колонии 97
4.4. Экспериментальная оценка алгоритмов оптимизации 107
Заключение 115
Список сокращений и условных обозначений 116
Список литературы
- Классификация технологий передачи данных в системах мониторинга СНО
- Энергетическая эффективность коммуникационной инфраструктуры системы мониторинга СНО
- Влияние методики обеспечения двусвязности на размер множества вариантов размещения шлюзов
- Алгоритм муравьиной колонии
Классификация технологий передачи данных в системах мониторинга СНО
На современном этапе развития систем навигационного обеспечения судоходства, в условиях повышенных требований безопасности, возникает задача отслеживания эксплуатационного состояния средств навигационного оборудования в режиме реального времени с помощью системы мониторинга и минимизации материальных затрат на ее установку и обслуживание. Бурное развитие технологий беспроводной передачи данных создает условия для совершенствования функциональных характеристик оборудования во многих отраслях производства. Технология сенсорных сетей нашла широкое применение в системах мониторинга в различных сферах человеческой деятельности, в том числе в области передачи эксплуатационной информации от средств навигационного оборудования. В настоящий момент существует ряд требований к системам мониторинга навигационных знаков [92], однако отсутствуют методики проектирования оптимальной коммуникационной инфраструктуры подобных систем, учитывающие современный уровень развития технологий беспроводной передачи данных. Применение эффективных методик проектирования, как правило, дает возможность существенно снизить финансовые и энергетические затраты в процессе эксплуатации системы мониторинга СНО. Тем не менее, на этапе проектирования системы могут возникнуть вопросы, требующие глубокого понимания принципов функционирования оптимизируемого объекта, а также ключевых особенностей взаимодействия его компонентов.
Повышение эффективности или оптимизация некоторого технического объекта требует системного подхода в изучении фундаментальных закономерностей его развития, а также анализа характерных достоинств и недостатков различных форм его реализации [54]. Таким образом, данный раздел будет посвящен описанию характеристик и проблем оптимизируемого объекта, т.е. коммуникационной инфраструктуры системы мониторинга СНО на базе технологии сенсорных сетей. В первом подразделе будет дано общее представление о средствах навигационного оборудования, приведена классификация навигационных знаков, а также требования к системам мониторинга СНО. Во втором подразделе будет проведен обзор различных технологий передачи данных в системах мониторинга СНО. В третьем подразделе будут отмечены основные технические характеристики и принципы действия технологии беспроводных сенсорных сетей.
Средства навигационного оборудования, являются важной частью навигационной системы морских портов и рек. Безопасность судовождения достигается за счет бесперебойного действия береговых и плавучих СНО, развития и совершенствования применяемых технологий в соответствии с современными требованиями морского флота. Подходы к портам и акватории портов, как правило, оборудованы маяками, светящими знаками, радиомаяками и звукосигнальными установками. Основным требованием к светящему морскому навигационному знаку является обеспечение необходимой дальности видимости огня в ночное и сооружения в дневное время суток. Дальность видимости и проблесковая характеристика светооптического аппарата СНО, как правило, указываются в описании «Огни и знаки» соответствующего бассейна.
Средства навигационного оборудования испытывают существенное воздействие внешней среды в процессе эксплуатации. Это обусловлено большими перепадами температур в течение года, действием шквалистого ветра, повышенной влажностью окружающей среды и соленостью воды. В замерзающих бассейнах, где навигация продолжается с помощью ледокольного флота, огни береговых навигационных знаков работают, как правило, круглый год, а плавучие знаки летней схемы ограждения заменяют ледовыми буями или светящими знаками, которые испытывают сильное механическое воздействие в период движения льдов. В виду того, что большинству навигационных знаков приходится работать в очень жестких климатических условиях, появляется необходимость организации наблюдения за их состоянием.
При планировании маршрута судоводитель рассчитывает, что СНО на его пути будет функционировать в соответствии с существующими регламентирующими документами и картами. В случае выхода автоматической аппаратуры СНО из строя или нарушения заданной проблесковой характеристики огня должны быть оповещены соответствующие власти. Не менее важна минимизация времени от момента выхода из строя навигационного знака до момента обнаружения поломки и оповещения мореплавателей. Выход из строя СНО может привести к навигационным происшествиям различной степени тяжести. Под навигационными происшествиями понимаются случаи, связанные с посадкой корабля на мель, касанием грунта, ударами о подводные препятствия или сооружения, обрывом подводного кабеля или трубопровода. Во всех случаях неизбежны значительные финансовые убытки.
В большинстве регионов России автоматизированный мониторинг средств навигационного оборудования развит крайне слабо. Сотрудникам морских портов или гидрографических предприятий приходится визуально отслеживать их состояние. В зависимости от количества береговых и плавучих знаков, интенсивности и характера судоходства устанавливаются соответствующие формы обслуживания СНО. Начальник укрупненного путевого поста со своим личным составом обеспечивает бесперебойную работу СНО в пределах обслуживаемого участка. Кроме того, к задачам наблюдения за состоянием и сохранностью СНО привлекаются капитаны судов, которые обязаны проверять правильность расстановки и действия плавучих предостерегательных знаков, а также соответствие их характеристик указанных в «Огнях и знаках» и на навигационных картах. В случае обнаружения неполадок они обязаны составить донесение соответствующим властям. Капитан судна, нанесший какое-либо повреждение плавучему знаку, обязан немедленно сообщить об этом с указанием координат, наименования знака и характера повреждения [25]. К сожалению, такой способ отслеживания эксплуатационного состояния навигационных знаков не всегда является эффективным, так как надежность и целостность информации низки. Высока зависимость от своевременности оповещения. Иначе выражаясь, на процесс обнаружения неисправности большое влияние оказывает человеческий фактор. Кроме того, визуальное наблюдение за функционированием навигационных знаков требует от гидрографических предприятий содержания крупного штата сотрудников, что не является эффективным подходом с финансовой точки зрения.
Для своевременного обнаружения неполадок используют устройства, регистрирующие состояние основных функциональных блоков наблюдаемого объекта и передающие эту информацию на пульт централизованного наблюдения. В центре мониторинга СНО выполняется обработка полученных данных и оповещение ответственных лиц. Таким образом, организация удаленного мониторинга является рациональным подходом в обеспечении бесперебойной работы навигационных знаков.
По месту и способу постановки навигационные знаки делятся на береговые и плавучие. Береговые навигационные знаки являются сооружениями, устанавливаемыми на жесткой грунтовой поверхности, например, на молах, пирсах и дамбах. К береговым СНО относятся различные навигационные створы, огни и маяки. Навигационным маяком называется капитальное сооружение башенного типа отличительной формы и окраски. В зависимости от назначения маяки оборудуются светооптическими аппаратами кругового или направленного действия. Навигационный огонь представляет собой световой прибор, устанавливаемый на естественных объектах или неспециальных сооружениях, например, на пирсах, зданиях или башнях. Навигационным створом называется сооружение башенного типа со щитом отличительной формы, над которым устанавливается топовая фигура. Створы позволяют строго придерживаться оси канала или фарватера, а также предназначены для указания безопасного прохода между мелями и рифами
Энергетическая эффективность коммуникационной инфраструктуры системы мониторинга СНО
В зависимости от конфигурации сети существует два типа доступа к каналу. В PAN-сетях без поддержки маячков используется CSMA-CA механизм доступа к каналу без применения слотов. Перед передачей данных устройство ждет в течение случайного периода времени и затем, если канал свободен, передает данные. Если канал занят, то попытка повторяется по истечению очередного случайного периода времени. В PAN-сетях с поддержкой маячков используется CSMA-CA механизм доступа к каналу с применения слотов. Выравнивание слотов ведется по сигналам маячков сети. Отличие от предыдущего алгоритма передачи данных заключается в том, что вместо случайного периода времени применяется случайное количество слотов.
В настоящий момент существует ряд сетевых технологий, основанных на стандарте IEEE 802.15.4, в которых реализованы протоколы верхнего уровня, необходимые для функционирования сенсорных сетей, например, ZigBee или WirelessHART. Особый интерес представляют технологии, в которых возможно создание децентрализованных многоячейковых сетей или mesh-сетей. В подобных сетях все узлы являются маршрутизаторами и отсутствует PAN-координатор, т.к. нет необходимости в централизованном управлении работы сети. Как правило, в подобных сетях каждый узел осуществляет поиск маршрута доставки сообщений самостоятельно с помощью реактивного протокола маршрутизации. Например, в реактивном протоколе Ad-hoc On-demand Distance Vector, в отличие от превентивных (проактивных) протоколов, отсутствует необходимость в постоянном поддержании таблиц маршрутизации в актуальном состоянии и поиске новых маршрутов, до тех пор, пока они не потребуются [26]. Протокол AODV основан на механизме широковещательного поиска маршрута, который используется для динамического создания записей в таблицах маршрутизации промежуточных узлов. Данный подход позволяет отказаться от ресурсоемкой задачи поиска для тех маршрутов, которые могут никогда не использоваться. Поиск маршрута осуществляется в случае, когда узлу-отправителю необходимо передать сообщение узлу-получателю, а в таблице маршрутизации узла-отправителя отсутствует запись с соответствующим маршрутом. Узел-отправитель инициирует процесс поиска маршрута путем широковещательной рассылки соседним узлам (узлам в пределах радиуса действия передатчика) запроса на установку маршрута (RREQ), содержащего следующие информационные поля:
Широковещательный идентификатор увеличивается на единицу, когда узел-отправитель формирует новый пакет RREQ. Поля с указанием порядкового номера узла-отправителя и широковещательным идентификатором делают запрос RREQ уникальным в сети. Если соседний узел, приняв запрос RREQ, не обнаруживает записи в собственной таблице маршрутизации с указанием узла-получателя, то он выполняет инкремент значения счетчика хопов и ретранслирует сообщение собственным соседним узлам. Стоит учитывать, что один узел может получить одинаковые запросы RREQ (с одинаковыми значениями порядкового номера узла-отправителя и широковещательного идентификатора) от нескольких соседних узлов. В подобных случаях дубликаты запроса не обрабатываются и не ретранслируются. В запросе RREQ предусмотрено два порядковых номера: порядковый номер узла-отправителя и последнее известное узлу-отправителю значение порядкового номера узла-получателя. Значение порядкового номера узла увеличивается при изменении соседних узлов. Информация о порядковом номере узла позволяет судить об актуальности маршрута до данного узла. При проходе запроса RREQ по сети каждый узел вписывает в информационное поле запроса собственный адрес. Узел-получатель, приняв запрос на собственный адрес, считывает адреса промежуточных узлов из RREQ и формирует маршрут между узлом-отправителем и узлом-получателем и отправляет ответ RREP узлу-отправителю по сформированному маршруту. Процесс поиска маршрута проиллюстрирован на рисунке 1.3. проход запроса RREQ от узла 1 для установки маршрута до узла 2; б — проход ответа RREP от узла 2 по кратчайшему маршруту.
Если промежуточный узел, приняв запрос RREQ, обнаруживает запись в собственной таблице маршрутизации с указанием узла-получателя, то он сравнивает значения порядкового номера узла-получателя в собственной таблице маршрутизации и в соответствующем поле запроса RREQ. Если значение порядкового номера узла-получателя в запросе RREQ больше чем в записи промежуточного узла, то это значит, что у узла-отправителя имеется более свежая информация о маршруте до узла-получателя, чем у промежуточного узла и, соответственно, промежуточный узел должен ретранслировать запрос. Если значение порядкового номера узла-получателя в запросе RREQ меньше или равно значению в записи промежуточного узла, то это значит, что промежуточный узел имеет актуальную информацию о маршруте до узла-получателя. В таком случае промежуточный узел формирует ответ RREP, в котором содержатся следующие информационные поля:
Ответ RREP отправляется промежуточным узлом соседнему узлу, от которого пришел запрос RREQ от узла-отправителя. По мере прохождения ответа RREP по маршруту в направлении узла-отправителя промежуточные узлы обновляют записи в собственных таблицах маршрутизации в соответствии с данными в ответе RREP. Если промежуточный узел продолжает получать ответы RREP в направлении узла-отправителя, то он, при необходимости, обновляет информацию в собственной таблице маршрутизации и ретранслирует сообщение дальше. Если значение порядкового номера узла-получателя больше, чем в предыдущих ответах RREP узлу-отправителю или значения порядковых номеров узлов-получателей равны, то ответ удаляется. Данный подход позволяет уменьшить количество ответов RREP в сети в направлении узла-отправителя и обеспечить его самым свежим и коротким маршрутом в направлении узла-получателя. Узел-отправитель может начинать передачу данных после приема первого ответа RREP. Если позже придет ответ RREP с более актуальной информацией о маршруте, то дальнейшую передачу данных узел-отправитель будет осуществлять по-новому более свежему маршруту. Если новизна маршрутов одинакова, дальнейшую передачу данных узел-отправитель будет осуществлять по кратчайшему маршруту. Недостаток подобного подхода заключается в том, что более свежий маршрут будет выбираться независимо от метрики (количества ретрансляций в маршруте), т.е. активный короткий маршрут может быть заменен на новый, но более длинный маршрут.
Помимо порядковых номеров узлов в таблице маршрутизации содержится другая полезная информация. Для каждой записи таблицы маршрутизации запускается таймер срока давности запроса маршрута. Задача данного таймера заключается в очищении таблицы от маршрутов к узлам, которые не используются при передаче данных. Значение срока давности запроса маршрута зависит от размера сети. Другим важным параметром является срок годности маршрута или время, после которого маршрут считается недействительным
Влияние методики обеспечения двусвязности на размер множества вариантов размещения шлюзов
Эффективность алгоритма является его ключевой характеристикой. В [18, с. 17], под «самым эффективным» алгоритмом понимается самый быстрый, т.к. именно ограничение по времени является основным фактором, по которому судят о пригодности алгоритма на практике. Время работы алгоритма выражается в виде функции от размера входных данных, требуемых для описания индивидуальной задачи. В случае задачи оптимального размещения шлюзов в сенсорной сети основным входным параметром, влияющим на время работы алгоритма, является количество узлов п. Также входными данными задачи являются:
В результате работы алгоритма по определению пригодности схемы размещения шлюзов х на выходе получаем ответ типа «да» или «нет». Для количественной оценки степени несоответствия схемы требованию энергетической эффективности следует использовать функцию пригодности
Работа алгоритма с элементами графа подразумевает наличие определенной схемы кодирования, которая будет отображать входные данные задачи в соответствующие цепочки символов, а именно способ записи топологии сети и схемы размещения шлюзов. В соответствии с утверждениями в работе [18] «разумная схема кодирования» должна отвечать следующим требованиям: 1) код задачи должен быть сжатым, т.е. не содержать избыточной информации или символов; 2) числа, входящие в условия задачи, должны быть представлены в двоичной системе счисления (или иметь любое другое основание, отличное от 1).
Существует несколько способов записи структуры графа: в виде списка вершин и ребер, в виде списка соседей, в виде матрицы смежности и в виде матрицы инцидентности [36]. Стоит отметить, что размерность входных данных задачи зависит не только от способа описания структуры графа, но и от степени его связности. Например, размерность матрицы смежности задается как ІИхІИ, а матрицы инцидентности как ІИхЕІ. Если в графе ребер меньше чем вершин, то целесообразно использовать матрицу инцидентности, но возникновение подобного случая на практике в сети навигационных знаков маловероятно, поэтому будем использовать матрицу смежности. Кроме того, представление графа в виде матрицы смежности понадобится нам в алгоритме при поиске кратчайших путей между всеми парами вершин. Однако это не означает, что другие формы записи не могут использоваться, т.к. длины входов для каждой из перечисленных схем кодирования отличаются друг от друга полиномиальным образом, поэтому способ представления структуры графа не окажет существенного влияния на работу алгоритма. Структуру сети навигационных знаков для вычислений будем представлять в виде матрицы смежности А размерности пхп, каждый элемент которой определяется в соответствии с (2.5). Для графа на рисунке 2.14 в результате обхода всех пар вершин получаем следующую форму записи структуры сети.
Значение максимально допустимого количества ретранслируемых сообщений txmax задается проектировщиком в зависимости от аппаратной платформы, используемой для передатчиков сенсорной сети, запаса электроэнергии навигационных знаков и требуемой длительности функционирования сети без замены элементов питания. Перед тем как приступить к описанию алгоритма, нужно принять ряд соглашений для представления переменных. Для удобства индексации элементов матрицы или параметров будем предполагать, что все вершины графа пронумерованы, т.е. V = {1,2,3...и}. Взятый в л(т) скобки верхний индекс для матрицы А будет указывать на длину кратчайшего пути между (т) вершинами, т.е. если элемент матрицы auv = 1, то между вершинами и и v существует путь длины т. Соответственно А(1) является матрицей смежности графа. Все элементы матрицы А( ) являются бинарными. Через W будем обозначать матрицу кратчайших путей между вершинами. Множество Nuv содержит все узлы всех кратчайших путей между и и v, включая сами узлы и и v. Параметр d представляет длину минимального пути от узла и до ближайшего шлюза. С учетом введенных обозначений алгоритм проверки схемы размещения шлюзов на соответствие заданному требованию энергоэффективности приведен на рисунках 2.16 и 2.17.
Рассмотрим данный алгоритм более подробно. В блоке 1 выполняется присваивание исходных значений всем переменным алгоритма. В блоках 2 — 6 выполняется вычисление вспомогательных данных, необходимых для проверки пригодности схемы размещения шлюзов. В блоках 2 и 4 решается задача поиска кратчайших путей между всеми парами вершин методом многократного умножения матриц [30, 37]. Помимо длины кратчайшего пути между парой вершин, нам необходимо выяснить номера узлов, из которых состоит этот путь. В блоке 2 поэтапно выполняется увеличение длины кратчайшего пути m между вершинами на единицу. Суть операции выполняемой в блоке 3 сводится к поиску кратчайших путей длины m +1 между всеми парами вершин путем умножения матрицы смежности графа A(1) и матрицы A(m) , отражающей наличие кратчайшего пути длины m между вершинами. Все элементы главной диагонали матриц A(m) при m ={1...n -1} равны 0, а также поскольку все элементы матриц A(m) являются булевыми, при «произведении» u-й строки матрицы A(1) и v-го столбца матрицы A(m) элемент au(vm+ 1) принимает значение 0 или 1. Единица в результате перемножения элементов au(1k) и ak(vm) сигнализирует о наличии кратчайшего пути длины m +1 от узла u до v. Тогда в блоке 4 соответствующее значение заносится в W — матрицу кратчайших путей между вершинами. Также в блоке 4 создается множество узлов Nuv, составляющих кратчайшие пути между данными вершинами. Если такое множество уже существует, то оно пополняется новыми элементами. Простой кратчайший путь в графе, который не содержит циклов с отрицательным весом и состоит из n узлов, может иметь не более n-1 ребер, поэтому блок 2 выполняется n-2 раз. На рисунке 2.18 изображены соответствующие матрицы наличия кратчайших путей и матрица кратчайших путей для графа на рисунке 2.14. Матрица A(2) получена путем умножения матрицы A(1) на саму себя. На матрице A(4) можно убедиться в наличии кратчайших путей длины 4 между узлами 1 и 9.
В блоке 6 на основе значения расстояния до ближайшего шлюза du для каждого узла сети u выясняются все ближайшие шлюзы, через которые узел u может передавать отчеты в центр мониторинга СНО. На основе этой информации определяется множество узлов Vu, которые могут быть задействованы для ретрансляции данных в случае передачи узлом u своему ближайшему шлюзу сообщения.
Алгоритм муравьиной колонии
Под воздействием окружающей среды выявляются признаки, способствующие выживанию организма. В генетических алгоритмах для сравнения альтернативных решения и выбора наиболее приспособленных хромосом используется целевая функция или функция пригодности (англ. fitness) — признак, по которому дается количественная оценка функционирования системы при некотором решении. Значение целевой функции или другой меры качества некоторого решения определяет его положение относительно других решений в пространстве всех альтернативных решений задачи. Иначе выражаясь, приспособленность особи в популяции измеряется значением целевой функции.
Генетический алгоритм начинает работу с формирования исходной популяции, состоящей из конечного набора допустимых решений задачи. Формирование «хорошей» начальной популяции может сократить время поиска глобального оптимума задачи. В общем виде работу ГА можно представить в виде многократного преобразования популяции хромосом последовательностью генетических операторов до тех пор, пока не будет выполнен некоторый критерий останова. Критерием останова алгоритма может быть выполнение заданного количества интераций (поколений) или получение алгоритмом некоторого решения, которое не удается улучшить (получение локального или глобального оптимума). Генетический оператор — это средство отображения одного множества хромосом на другое. Рассмотрим основные генетические операторы.
Оператор репродукции (селекции) — процесс, при котором происходит отбор родительских хромосом из текущей популяции для воспроизведения потомства, где более приспособленные особи имеют больше шансов быть выбранными. Выбор хромосом для репродукции может осуществляться на основе значений целевой функции или случайным образом. При случайном выборе хромосом вероятность выбора некоторой хромосомы обусловлена численностью популяции. В таком случае вероятность выбора pi i-й хромосомы определяется по формуле pi = , (4.2) общее количество хромосом в популяции. Однако более популярен метод выбора хромосомы в зависимости от ее приспособленности. Среди данных операторов самыми популярными являются операторы турнирной и пропорциональной селекции. При пропорциональной селекции вероятность выбора хромосомы пропорциональна значению ее целевой функции. В некоторых алгоритмах данный метод реализован в виде «колеса рулетки», где каждой хромосоме на рулетке выделяется сектор по размеру пропорциональный значению приспособленности хромосомы. При запуске рулетки наиболее приспособленные хромосомы имеют большую вероятность быть выбранными для производства потомства. Метод турнирного отбора был предложен Бринделом в 1981 г., а также Гольдбергом и Дебом в 1991 г. [15, 38]. В каждом турнире случайным образом выделяется подмножество k хромосом (участников турнира) и из них выбирается хромосома с наибольшим значением целевой функции. Кроме того, известны элитные методы отбора, которые гарантируют выживание только наиболее приспособленных особей. Важнейшей задачей селекции является закрепление удачных признаков организмов в последующих поколениях популяции, поэтому при выборе родительских хромосом целесообразно использовать две хромосомы с «хорошими» значениями целевой функции. В таком случае будут исследоваться наиболее перспективные участки пространства решений. В результате алгоритм будет сходиться в локальных, а иногда и в глобальных оптимумах. Однако стоит понимать, что использование похожих родительских хромосом со схожими значениями целевой функции не может обеспечить разнообразие генетического материала и расширить исследуемую область пространства решений, что понижает вероятность получения глобального оптимума задачи.
Оператор кроссинговера (скрещивания) выполняет формирование хромосом потомков путем объединения частей родительских хромосом. Выбор оператора кроссинговера определяет эффективность генетического алгоритма и зависит от структуры задачи. Одноточечный оператор кроссинговера ищет равные локусы для точки разреза двух родительских хромосом случайным образом и выполняет перестановку генов как показано на рисунке 4.8.
Одноточечный кроссинговер Например, при кодировке хромосом последовательностью бинарных чисел, для родительских хромосом вида {101111} и {000010} при точке разреза между третьим и четвертым генами получаем следующих потомков: {101010}, {000111}. Операторы одноточечного, двухточечного и многоточечного кроссинговера отличаются количеством точек разреза хромосом при обмене генами. Также в генетических алгоритмах существуют такие модификации оператора скрещивания как равномерный, упорядоченный, циклический, частично-соответствующий, универсальный и «жадный» кроссинговер. В генетическом алгоритме не обязательно копировать механизмы эволюционного развития, существующие в живой природе. Так в процессе кроссинговера возможно скрещивание трех, четырех и более хромосом между собой, т.е. в производстве потомства могут принимать участие более двух родителей. Операция скрещивания родительских хромосом также может выполняться в зависимости от степени их родства, определяемой с помощью Хэммингова расстояния, показывающего количество отличающихся генов. При равномерном кроссинговере каждый бит первого родителя передается потомку с некоторой вероятностью. Хромосома потомка с вероятностью 0,5 наследует ген родителя 1, в противном случае наследуется ген родителя 2. Одинаковые значения генов у обоих родителей наследуются потомством без изменений.
Оператор мутации выполняет частичное преобразование хромосомы случайным образом. Мутация — это скачкообразное изменение в структуре генотипа, приводящее к качественно новому проявлению свойств генетического материала. Одинаковая мутация не может возникнуть одновременно у нескольких особей, однако результаты мутации могут передаваться по наследству. Процесс мутационной изменчивости носит ненаправленный характер, поэтому мутационные изменения могут повышать, понижать или не оказывать влияния на жизнеспособность организма. Одноточечный оператор мутации случайным образом выбирает позицию гена в хромосоме и меняет его значение со значением соседнего гена. Также значение выбранного гена может изменяться путем присвоения некоторого значения, отличного от исходного. Так если хромосома представлена в виде бинарных элементов, то мутирующий ген принимает инверсное значение. Оператор мутации может применяться для нескольких генов. Как правило, применение оператора мутации к хромосоме носит вероятностный характер. Высокая вероятность мутации может не дать сильным хромосомам получать доминирующее положение в популяции, и алгоритм будет вырабатывать новые неоптимальные решения, даже в том случае, если алгоритм близок к получению глобального оптимума. Малая вероятность мутации наоборот может вызвать преждевременную сходимость алгоритма. Все отклонения в генотипе, полученные в результате мутации, описываются законом случайного распределения.
