Содержание к диссертации
Введение
ГЛАВА 1 Современные требования, предъявляемые к процессу проектирования систем физической защиты объектов информатизации 12
1.1 Понятие объекта информатизации. Анализ нормативной документации по вопросу защиты объектов информатизации 12
1.2 Анализ современного состояния процесса проектирования систем физической защиты объектов информатизации 19
1.3 Существующие подходы к информационной поддержке решения задачи проектирования систем физической защиты объектов информатизации 28
1.4 Метод определения требований к системе физической защиты объекта информатизации 35 Выводы 39
ГЛАВА 2 Метод создания концептуального проекта системы физической защиты объекта информатизации 42
2.1 Постановка задачи создания концептуального проекта системы физической защиты объекта информатизации 42
2.2 Вопрос защищенности критических элементов в зависимости от путей перемещения нарушителя 45
2.3 Алгоритм определения оптимального размещения точек
контроля 49
Выводы 68
ГЛАВА 3 Программное средство информационной поддержки решения задачи проектирования систем физической защиты объектов информатизации 70
3.1 Описание программного средства информационной поддержки 70
3.2 Проведение имитационного моделирования с использованием программного средства информационной поддержки
3.2.1 Оценка качества решения задачи с использованием программного средства 74
3.2.2 Оценка оптимальности результатов решения задачи 79
3.2.3 Сравнение методов поиска оптимального решения задачи 86 Выводы 89
ГЛАВА 4 Проектирование системы физической защиты с использованием адаптивного генетического алгоритма 91
4.1 Определение необходимости использования адаптивного генетического алгоритма 91
4.2 Разработка механизма адаптации генетического алгоритма 100
4.3 Анализ работоспособности механизма адаптации генетического алгоритма 110
4.4 Оценка эффективности разработанных метода и алгоритмов 121
Выводы 127
Заключение 129
Список сокращений и условных обозначений 133
Список литературы
- Анализ современного состояния процесса проектирования систем физической защиты объектов информатизации
- Вопрос защищенности критических элементов в зависимости от путей перемещения нарушителя
- Проведение имитационного моделирования с использованием программного средства информационной поддержки
- Анализ работоспособности механизма адаптации генетического алгоритма
Введение к работе
Актуальность работы. В современном мире объекты информатизации (ОИ) входят в состав большинства предприятий и организаций. Нарушение информационной безопасности ОИ может привести к разглашению конфиденциальной информации, банкротству организации, а также к нарушению функционирования предприятия. Наиболее серьезные последствия возможны, если объект информатизации является частью критически важного объекта (КВО). Такие объекты информатизации включают в себя автоматизированные системы управления производственными и технологическими процессами, выход из строя которых приводит к нарушению функционирования производства, что может повлечь за собой катастрофические последствия.
Среди всех угроз, направленных на ОИ можно выделить угрозы связанные с возможностью физического проникновения на объект с целью несанкционированного доступа к защищаемой информации и техническим средствам объекта информатизации. Средствами противодействия угрозам такого рода являются системы физической защиты (СФЗ). СФЗ представляют собой объединение сил охраны и технического оснащения – комплекса инженерно-технических средств охраны (ИТСО). Проектирование СФЗ – это сложный процесс. Если при проектировании допускаются ошибки, то полученная система, либо не сможет противодействовать угрозам, либо превысит необходимый уровень защищенности для объекта информатизации и затраты на ее создание и обслуживание будут необоснованно высоки. Поэтому физическая безопасность ОИ напрямую зависит от результатов решения задачи проектирования СФЗ.
В задаче проектирования СФЗ используется исходная информация, отражающая опыт и знания экспертов. Знания экспертов обычно являются результатами приблизительных оценок, прогнозов и предположений. Чтобы оперировать такой информацией, необходимо использовать методы обработки неточных данных.
Таким образом, актуальность проведения исследований заключается в необходимости информационной поддержки решения задачи проектирования систем физической защиты объектов информатизации с применением методов обработки неточной информации.
Степень разработанности темы исследования. В настоящее время идет постоянная работа по разработке нормативной документации в области обеспечения физической безопасности, в том числе по определению оптимальных структур систем физической защиты, создаются математические модели функционирования систем безопасности, математические модели объектов, математические модели нарушителей и т. п. Отечественные и зарубежные ученые, проводят многочисленные исследования, посвященные проблемам проектирования и оценки систем физической защиты: М. Гарсия, Джеймс Ф. Бродера, А.В. Бояринцев, А.Н. Бражник, А.Г. Зуев, В.В. Волхонский, В.С. Зарубин, И.М. Янников, Ю.А. Оленин, Г.Е. Шепитько, Р.Г. Магауенов, Я.Д. Вишняков, О.А. Панин, Н.Н. Радаев, В.В. Лесных, А.В. Бочков, В.А. Акимов, В.А. Герасименко, А.В. Архипов, С.Е. Сталенков, А.В. Измайлов, А.В. Ничиков, Г.Г.
Соломанидин, Н.Г. Топольский, К.И. Шестаков, Э.И. Абалмазов, А.М. Омельянчук. Описываются методы определения требований к СФЗ, способы оценки эффективности существующих и разрабатываемых систем. При этом среди исследований нет метода решения задачи проектирования СФЗ, позволяющего использовать средства информационной поддержки на этапе создания проекта СФЗ, определяющего размещение средств защиты на территории объекта. Существует отечественное и зарубежное программное обеспечение: СПРУТ, СПРУТ – ИМ, Вега – 2, ASSESS, EASI, FESEM, ISEM, SAFE, SAVI, SNAP, ALHPA, JTS и т. п., которое используется при проектировании СФЗ. Но все перечисленные программные средства применимы только на этапе тестирования готового проекта СФЗ для оценки его эффективности и не предоставляют помощи в процессе создания проекта.
Объектом исследования диссертационной работы является система физической защиты объекта информатизации.
Предметом исследования диссертационной работы является информационная поддержка решения задачи проектирования систем физической защиты объектов информатизации.
Цель диссертационной работы – разработка метода и алгоритмов для осуществления информационной поддержки решения задачи проектирования систем физической защиты объектов информатизации.
Для достижения поставленной цели необходимо решить следующие
задачи:
1. Разработать метод создания концептуального проекта системы
физической защиты объекта информатизации с определением размещения
средств защиты на территории объекта.
-
Разработать алгоритмы метода создания концептуального проекта СФЗ ОИ с применением обработки неточной информации.
-
Разработать программное средство для информационной поддержки решения задачи проектирования СФЗ ОИ.
4. Провести анализ работоспособности и оценить эффективность
реализованного метода и алгоритмов.
Методы исследования. Результаты исследований получены с помощью методов обработки неточной информации, таких как нечеткие переменные, генетические алгоритмы (ГА), метод ветвей и границ, многокритериальный анализ вариантов и теория графов.
Основные научные результаты, выносимые на защиту:
-
Метод создания концептуального проекта системы физической защиты объекта информатизации.
-
Алгоритмы метода создания концептуального проекта СФЗ ОИ на основе ГА с применением процедур обработки графов и нечетких чисел.
3. Алгоритм адаптивного генетического алгоритма, повышающий
работоспособность программного средства информационной поддержки решения
задачи проектирования СФЗ ОИ.
4. Алгоритм решения задачи проектирования СФЗ ОИ методом ветвей и
границ, применяемый для анализа работоспособности ГА.
Научная новизна результатов исследования:
-
Новизна метода создания концептуального проекта СФЗ ОИ заключается в том, что его использование позволяет получить концептуальный проект в виде структурно-логической модели СФЗ, согласно которой каждый участок объекта информатизации защищается набором точек контроля (логических понятий, соответствующих частям комплекса ИТСО объекта). При рабочем проектировании точкам контроля будут сопоставляться реальные средства защиты.
-
Новизна алгоритмов метода создания концептуального проекта СФЗ ОИ заключается в проведении многокритериальной оптимизации через взвешенную сумму трех целевых функций ГА, в использовании процедуры поиска всех возможных путей перемещения нарушителя по территории объекта и процедуры отсева нерациональных путей, основанных на обработке графов и нечетких чисел.
-
Новизна алгоритма адаптивного ГА заключается в проведении анализа свойств прошедших поколений хромосом для определения необходимых изменений параметров ГА, что позволяет не выбирать значения параметров вручную. Правильно подобранные значения параметров влияют на возможности ГА по поиску решения, например, уменьшается вероятность попадания в локальный оптимум, что повышает работоспособность программного средства информационной поддержки решения задачи проектирования СФЗ ОИ.
-
Новизна алгоритма решения задачи проектирования СФЗ ОИ методом ветвей и границ заключается в использовании целевой функции ГА и способа кодирования вариантов решений аналогичного хромосомам ГА. Алгоритм позволяет найти оптимальное решение задачи размещения точек контроля для простых модельных объектов, что используется в имитационном моделировании для анализа работоспособности ГА.
Практическая ценность научной работы заключается в повышении физической безопасности объектов информатизации путем информационной поддержки решения задачи проектирования систем физической защиты в условиях неточных исходных данных.
Внедрение результатов. Результаты работы были успешно применены в проектных работах, выполняемых в организациях ФГБУ «3 ЦНИИ» МО РФ ст. Донгузская, Оренбургской обл.; ЗАО «Центр безопасности информации «ЦИНТУР» г. Оренбург; ООО «Газпром энерго» Оренбургский филиал; в учебном процессе ФГБОУ ВО Оренбургский государственный аграрный университет Институт управления рисками и комплексной безопасности; ФГБОУ ВО Оренбургский государственный университет.
Соответствие диссертации паспорту научной специальности.
Представленная диссертация удовлетворяет п.6, п.9 и п.10 паспорта специальности 05.13.19 – «Методы, модели и средства защиты информации, информационная безопасность»:
п. 6. Модели и методы формирования комплексов средств противодействия угрозам хищения (разрушения, модификации) информации и нарушения информационной безопасности для различного вида объектов защиты вне зависимости от области их функционирования.
п. 9. Модели и методы оценки защищенности информации и информационной безопасности объекта.
п. 10. Модели и методы оценки эффективности систем (комплексов) обеспечения информационной безопасности объектов защиты.
Достоверность результатов подтверждена результатами апробации созданного программного средства и проведением имитационного моделирования с применением метода ветвей и границ.
Апробация работы. Результаты работы докладывались и обсуждались на следующих конференциях с публикацией в сборнике трудов: XII Международная конференция «Проблемы управления и моделирования в сложных системах» 21-23 июня 2010 г., г. Самара; IV Международная научно-техническая конференция «Информационные технологии в науке, образовании и производстве» 22-23 апреля 2010 г., г. Орел; XIII Международная конференция «Проблемы управления и моделирования в сложных системах» 15-17 июня 2011 г., г. Самара; VIII Международная научно-практическая конференция «Дни науки - 2012» 27 марта -5 апреля 2012 г. г. Прага; XV Международная конференция «Проблемы управления и моделирования в сложных системах» 25-28 июня 2013 г., г. Самара; V Международная научная конференция «Информационные Технологии и Системы» 24–28 февраля 2016 г., г. Челябинск; XIII Международная научно-техническая конференция «Новые Информационные Технологии и Системы» 23– 25 ноября 2016 г., г. Пенза. Результаты диссертации использовались в работе, занявшей первое место в открытом молодежном конкурсе «Приволжье – территория безопасности», проводимого в 2013 году.
Публикации. Результаты диссертационной работы опубликованы в 21 печатном издании, в том числе в 2 монографиях, 11 статьях в изданиях из перечня ВАК, включая 2 статьи без соавторства. Получены 8 свидетельств о государственной регистрации программы для ЭВМ и одно свидетельство о регистрации электронного ресурса.
Личный вклад автора. Основные результаты и положения, выносимые на защиту, получены лично автором. Метод для определения требований к системе физической защиты объекта информатизации разработан в соавторстве с научным руководителем.
Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав основного материала, заключения, списка сокращений и списка литературы. Работа изложена на 144 страницах машинописного текста, включает 30 рисунков и 21 таблицу. Список литературы содержит 102 наименования.
Анализ современного состояния процесса проектирования систем физической защиты объектов информатизации
В доктрине информационной безопасности Российской Федерации [1] сказано: «Настоящая Доктрина представляет собой систему официальных взглядов на обеспечение национальной безопасности Российской Федерации в информационной сфере … под информационной сферой понимается совокупность информации, объектов информатизации, …
Система обеспечения информационной безопасности является частью системы обеспечения национальной безопасности Российской Федерации … обеспечение информационной безопасности – осуществление … мер по прогнозированию, обнаружению, сдерживанию, предотвращению, отражению информационных угроз …»
Согласно ГОСТ Р 51275-2006 [2] под объектом информатизации (ОИ) понимают: «Совокупность информационных ресурсов, средств и систем обработки информации, используемых в соответствии с заданной информационной технологией, а также средств их обеспечения, помещений или объектов (зданий, сооружений, технических средств), в которых эти средства и системы установлены, или помещений и объектов, предназначенных для ведения конфиденциальных переговоров».
В основных положениях ГОСТ указано что: «Выявление и учет факторов, воздействующих или могущих воздействовать на защищаемую информацию в конкретных условиях, составляют основу для планирования и проведения эффективных мероприятий, направленных на защиту информации на объекте информатизации». Рассмотрим классификацию факторов, воздействующих на безопасность защищаемой информации.
Объективные факторы делятся на внутренние и внешние факторы: 1) Внутренние факторы - Передача сигналов. - Излучения сигналов, функционально присущие техническим средствам (ТС) объектов информатизации. - Побочные электромагнитные излучения. - Паразитное электромагнитное излучение. - Наводка. - Наличие акустоэлектрических преобразователей в элементах ТС ОИ. - Дефекты, сбои и отказы, аварии ТС и систем ОИ. - Дефекты, сбои и отказы программного обеспечения ОИ. 2) Внешние факторы - Явления техногенного характера. - Природные явления, стихийные бедствия. Субъективные факторы также подразделяются на внутренние и внешние: 1) Внутренние факторы - Разглашение защищаемой информации лицами, имеющими к ней право доступа. - Неправомерные действия со стороны лиц, имеющих право доступа к защищаемой информации. - Несанкционированный доступ к информации. - Недостатки организационного обеспечения защиты информации. - Ошибки обслуживающего персонала ОИ. 2) Внешние факторы - Доступ к защищаемой информации с применением технических средств. - Несанкционированный доступ к защищаемой информации путем: - Блокирование доступа к защищаемой информации путем перегрузки технических средств обработки информации ложными заявками на ее обработку. - Действия криминальных групп и отдельных преступных субъектов. - Искажение, уничтожение или блокирование информации с применением технических средств [2, 3]. Для противодействия факторам, воздействующим на безопасность ОИ, используются различные средства защиты информации [4, 5, 6].
Средства защиты информации, подразделяются на технические и программные и программно-технические. Техническими (или физическими) названы такие средства, которые реализуются в виде электрических, электромеханических, электронных устройств. Под программно-техническими средствами защиты понимают устройства, внедряемые непосредственно в аппаратуру обработки данных, или устройства, которые сопрягаются с ней по стандартному интерфейсу. Программные средства защиты образуют программы, специально предназначенные для выполнения функций, связанных с защитой информации [7, 8].
Различные средства в совокупности представляют собой системы защиты для поддержки информационной безопасности объекта. Например: системы обнаружения и предотвращения сетевых вторжений, системы предотвращения утечек конфиденциальной информации, антивирусные средства, межсетевые экраны, криптографические средства, системы резервного копирования, системы бесперебойного питания и т. п. [9, 10, 11].
Создание системы информационной безопасности, включающей в себя все виды средств (технические, программные и программно-технические), является чрезвычайно сложной проблемой. В частности требуется рассматривать сильно различающиеся по принципам воздействия на ОИ факторы, и соответственно анализировать множество способов защиты от всех видов факторов. Поэтому целесообразно разделить задачу создания системы защиты на несколько подзадач, например по видам средств защиты, и в дальнейшем объединять результаты решения в единую систему, защищающую ОИ от всех видов угроз информационной безопасности. Определим подробнее понятие физических средств защиты. К физическим средствам относят механические, электромеханические, оптические, акустические, лазерные, радиоволновые и другие устройства, системы и сооружения, предназначенные для создания препятствий на пути к защищаемой информации и способные выполнять функции физической защиты. Система физической защиты (СФЗ) по определению это объединение сил охраны и технического оснащения – комплекса инженерно-технических средств охраны. Состав СФЗ в виде структурной схемы отображен на рисунке 1.1 [12].
Вопрос защищенности критических элементов в зависимости от путей перемещения нарушителя
Чтобы защитить согласно требованиям критический элемент, к которому ведут несколько возможных путей нарушителя, нужно чтобы каждый путь содержал соответствующее количество ТК. В результате для защиты одного КЭ на объекте с большим количеством путей будет размещено намного больше ТК, чем требуется для соблюдения требуемого уровня защищенности данного КЭ. Однако множество путей на объекте включают в себя одинаковые участки, и ТК, расположенные на таких участках, будут влиять на защиту нескольких путей и даже нескольких КЭ. Таким образом, появляется необходимость увеличивать количество ТК (и увеличивать затраты на приобретение, установку и обслуживание элементов СФЗ) и одновременно имеется возможность уменьшать количество ТК (и уменьшать затраты) за счет размещения ТК на участках, где проходят большинство путей. Очевидно, что существует наилучший, оптимальный вариант расположения ТК на объекте, с соблюдением требуемой защищенности всех КЭ при минимальном количестве ТК.
Необходим анализ предполагаемых путей нарушителя. Так как невозможно угадать какой маршрут перемещения по территории объекта выберет нарушитель, рассматриваем все существующие пути.
Для перебора путей в графе используем метод поиска в глубину [62]. Метод позволяет найти все пути между двумя заданными вершинами. Задавая последовательно парами все точки проникновения и все критические элементы можно перебрать все существующие пути по территории объекта.
Общее количество путей в графе может быть очень большим, особенно при наличии нескольких точек проникновения и нескольких критических элементов. Поэтому после определения всех возможных путей, нужно провести отсев нерациональных или недопустимых для нарушителя маршрутов перемещения по территории объекта. Для этого представим найденные пути в виде графовой модели. Каждый путь это последовательность ребер, в которой каждые два соседних ребра имеют общую вершину, и никакое ребро не встречается более одного раза. Пути, ведущие из одной вершины (точки проникновения) до разных критических элементов можно представить в виде дерева [63, 64, 65]. Любую вершину ветвей дерева можно рассматривать как возможность смены направления движения нарушителя. Если вершина соединена ребрами с более чем двумя соседними вершинами, то существует ответвление с новой частью пути. Новые ветви также будут разветвляться, в результате получается дерево и на конце каждой ветви в висячей вершине будет критический элемент (рисунок 2.2). Тупики и пути, не заканчивающиеся КЭ, не рассматриваются по причине бесполезности для нарушителя.
На объекте с несколькими точками проникновения будет несколько деревьев путей. Таким образом, граф найденных путей представит собой лес, количество деревьев в котором равно числу точек проникновения, количество висячих вершин в каждом дереве зависит от числа критических элементов и количества возможных путей до каждого критического элемента.
У разных путей на одном объекте обычно есть совпадающие участки, значит, возможен переход от одного пути к другому. Из-за большого количества одинаковых участков на графе в виде леса сложно оценить взаимопересечение путей. Если объединить одинаковые вершины разных путей, то лес преобразуется обратно в граф объекта и различные пути невозможно будет выделить. Поэтому используем другую графовую модель. Представим все пути в виде векторов и обозначим переходы через совпадающие участки пунктирными линиями (рисунок 2.3). При частом переходе через совпадающие участки путь нарушителя будет проходить через большое количество вершин и ребер объекта. Некоторые пути могут полностью совпасть с частью более длинного пути. Так как пути всегда заканчиваются критическим элементом, то совпадающие пути заканчиваются одной и той же вершиной, а начало короткого пути совпадает с вершиной внутри длинного пути. Такой длинный путь содержит две точки проникновения или больше (пример выделен жирной линией на рисунке 2.3).
Отсев нерациональных маршрутов проведем следующим образом. Сначала исключаем из рассмотрения те пути, которые полностью содержат в себе другой путь до того же критического элемента. Так как меньший путь будет защищен достаточным количеством ТК (после решения задачи оптимального размещения точек контроля), то и больший путь также будет защищен достаточным количеством ТК.
Далее исключаем пути, проходящие через большое количество участков объекта. Чем длиннее путь, тем больше точек контроля будут встречаться нарушителю, тем больше шансов на его обнаружение и задержку. Нарушитель не будет использовать длинный маршрут, но необходимо четко обосновать какие пути «слишком длинны». Используем разработанное для метода определения требований к СФЗ понятие меры структурной защищенности (см. пункт 1.4). На достаточно длинном пути вероятность обнаружения и задержки нарушителя высока даже при отсутствии средств защиты на объекте. Прочность дверей, окон, время на их преодоление определяет структурную защищенность КЭ. Для расчета меры структурной защищенности в методе определения требований рассматривался самый незащищенный путь, который легко преодолевался нарушителем при отсутствии СФЗ [42]. Но при выборе длинных путей даже на незащищенном объекте нарушителю придется проходить слишком большое количество естественных препятствий. Значение вероятности обнаружения и задержки на таком пути может оказаться высоким и без средств защиты.
Для вычисления меры структурной защищенности всех путей, эксперты должны определить вероятность обнаружения и вероятность задержки на каждом участке объекта. Вероятности можно задавать в нечеткой форме, что упростит работу экспертов. Вычисление вероятностей для всего пути будет проводиться по формулам 1 и 2, приведенным в пункте 1.4.
Теперь можно определить пути со слишком высоким значением меры структурной защищенности и исключить их из рассмотрения. В качестве порогового значения можно выбрать вероятность обнаружения и задержки равную 0,95.
Проведение имитационного моделирования с использованием программного средства информационной поддержки
Для оценки работоспособности алгоритма оптимального размещения точек контроля проводились тестовые запуски программного средства. Целью тестирования было доказать возможность находить оптимальные решения с помощью генетического алгоритма.
Набор исходных данных для тестирования, включает граф модельного объекта, решение задачи с которым описано в пункте 2.3, рисунок 2.5. Точки проникновения и критические элементы выбраны аналогично: 1, 2, 13, 14, 15 – точки проникновения, 6, 7, 8, 9, 10, 11, 12 – КЭ (рисунок 2.6). Ограничения на количество ТК у всех вершин и ребер одинаковое: минимальное – ноль, максимальное – два ТК каждого типа. Требования для защиты критических элементов – по три ТК каждого типа.
В первых экспериментах проведена оценка сходимости генетического алгоритма. Сходимость ГА означает постепенное приближение свойств хромосом к значениям, близким к свойствам оптимального решения. Хромосома с оптимальным решением должна максимально возможно соответствовать правилам, описанным в целевых функциях. Следовательно, наличие сходимости выявляется постепенным снижением значений целевых функций для всех хромосом популяции.
У первой и второй функции правила, которым должны соответствовать хромосомы, взаимно исключают друг друга. Защищенность всех КЭ требует увеличения количества точек контроля, а сокращение затрат на СФЗ требует уменьшения этого же количества. Поэтому сходимость проверялась с учетом только одной целевой функции. Для этого веса остальных целевых функций задавались равными нулю, и проводился запуск ГА. Если оптимальное решение должно соответствовать только первой функции, то все КЭ объекта будут защищены, недостаток ТК равен нулю – значение функции стремится к нулю. Аналогично проводился запуск ГА с учетом только второй функции: общее количество ТК на объекте равно минимально возможному, т. е. нулю.
Эксперименты для первой и второй целевой функции проводились несколько раз с различным начальным набором хромосом. Обнаружилось постоянное снижение суммарного значения целевой функции для всех хромосом. Причем значение для первой функции достигало нуля очень быстро (менее пятидесяти поколений). Достижение нулевого значения для второй функции происходило в среднем за четыреста поколений.
На рисунках 3.5, 3.6 показаны графики суммарного несоответствия хромосом двум целевым функциям. По оси ординат откладывается сумма значений целевой функции для всех хромосом. Значения по оси абсцисс – это номера поколений хромосом. Чем правее точка, тем больше прошло итераций алгоритма.
Разница в скорости сходимости объясняется свойствами начального набора хромосом: случайное количество ТК всегда намного превышает требуемый по второй функции ноль. Снижение количества ТК до нуля возможно после большого количества операции кроссинговера и мутаций, поскольку одна мутация уменьшает количество ТК только на единицу. Получение оптимального результата по первой функции происходит за малое число поколений, т. к. среди начальных хромосом с большой вероятностью присутствует решение с полной защитой КЭ.
Таким образом, сходимость ГА экспериментально доказана. Это позволяет предположить, что оптимальное решение (или локальный оптимум) будет найдено при правильно заданных весах целевых функций и достаточном числе прошедших поколений. Рисунок 3.5 – График, показывающий сходимость генетического алгоритма по первой целевой функции
Далее проводились эксперименты для проверки близости получаемых программным средством решений к оптимальному решению. Потребовалось найти оптимальное решение для задачи размещения точек контроля.
Размерность задачи зависит от структурно-логической модели объекта и может составлять порядка сотни значений для описания набора точек контроля на всем объекте. Но количество точек контроля дискретно и множество допустимых решений в задаче конечно, так как существуют ограничения на количество точек контроля. Следовательно, оптимальное решение, как наилучшее из всех возможных, может быть найдено методом полного перебора. Количество вариантов размещения ТК очень велико даже для небольшого модельного объекта. Поэтому оптимальное решение было получено одной из схем неявного перебора – методом ветвей и границ [84, 85].
Методы неявного перебора дают возможность не рассматривать все множество допустимых решений. В методе ветвей и границ множество разбивается на части, и для подмножеств определяется возможность включать или не включать в себя оптимальное решение. Используется понятие рекорд – найденное в процессе перебора допустимое решение, с наибольшим соответствием целевым функциям. Если для какого-либо подмножества решений удалось определить, что все варианты решений в нем будут меньше соответствовать целевым функциям чем рекорд, то подмножество может не участвовать в переборе, т. е. все его решения отбрасываются. Когда при продолжающемся переборе решений будет найден новый рекорд, то может быть отброшено другое подмножество решений. Таким образом, множество решений постепенно сокращается, что позволяет, исключая отброшенные, просмотреть все варианты за приемлемое время [86].
В методе ветвей и границ также используются целевые функции, как и в генетическом алгоритме, что позволяет использовать имеющиеся процедуры программного средства, с помощью которых оценивается приспособляемость хромосомы для определения допустимости решения и выявления рекорда. Допустимые решения определялись по первой целевой функции генетического алгоритма – все критические элементы должны быть защищены. Из допустимых решений по второй целевой функции выбирался рекорд – решение с наименьшим количеством точек контроля. Общее количество ТК в текущем рекорде определяет, какие решения можно не рассматривать. Если проверяемое решение имеет больше ТК чем рекорд, то оно не может быть оптимальным и не должно участвовать в переборе.
Анализ работоспособности механизма адаптации генетического алгоритма
Генетические алгоритмы обладают множеством преимуществ по сравнению с другими методами оптимизации [66]. ГА также не лишены недостатков, один из которых сильная зависимость эффективности работы алгоритма от выбранных параметров ГА. Заранее заданные программистом (или пользователем) значения некоторых свойств алгоритма напрямую влияют на скорость сходимости алгоритма, на вероятность найти приемлемое решение за ограниченное число итераций алгоритма, возможность выхода из локального оптимума и другие показатели эффективности работы ГА.
Такими параметрами являются критерии отбора хромосом в родительский пул, вероятность мутации, число точек деления хромосом при многоточечном кроссинговере и т. п. Обычно поиск значений параметров для получения высокой эффективности ГА проводится интуитивно, методом проб и ошибок, что приводит к выбору не самых удачных вариантов. Проведение экспериментов с оценкой работоспособности алгоритма при различных значениях параметров может помочь выбрать лучшие значения, но требует многократного решения одной и той же задачи. Кроме того, один раз найденные значения параметров будут являться подходящими только для текущей задачи, и при смене исходных данных необходимо заново проводить эксперименты. Дополнительная сложность при определении значений параметров алгоритма вызывается следующей особенностью ГА: влияние многих параметров на эффективность ГА изменяется на протяжении всего времени работы ГА. Следовательно, нужно определять не постоянные значения, а правила изменения параметров в процессе поиска решения. Например, желательно уменьшать вероятность мутации в зависимости от времени работы генетического алгоритма [87]. Таким образом, поиск наилучших значений параметров ГА должен проводиться при каждом запуске ГА, что возможно при использовании адаптивных генетических алгоритмов [88–92].
Так как задача проектирования СФЗ ОИ требует использования высокоэффективных методов решения, то при использовании ГА необходимо обеспечить максимальную эффективность работы алгоритма. Выдвигаем предположение, что для решения задачи проектирования СФЗ ОИ требуется использование ГА с обязательной реализацией механизма адаптации.
Проанализируем, описанный в главе 2, процесс работы генетического алгоритма, чтобы выделить те параметры ГА, значения которых сильно влияют на эффективность его работы. В качестве показателя эффективности выберем скорость ГА, т. е. требуемое количество итераций алгоритма для получения оптимального решения. Проведем эксперименты, для определения, насколько сильно выбранные параметры влияют на скорость поиска решения.
Общая целевая функция задачи определения оптимального размещения точек контроля состоит из трех целевых функций и рассчитывается через взвешенную сумму. Значение общей целевой функции зависит от весов, и выбор весов будет влиять на свойства получаемых решений. Предполагаем, что веса целевых функций являются одними из параметров ГА, от которых сильно зависит эффективность работы ГА. Каждое значение должно определяться в совокупности с остальными: изменение веса одной функции влечет за собой обязательное изменение весов других т. к. сумма значений весов всегда равна единице. Поэтому будем рассматривать выбор значений весов как выбор одного параметра – соотношения весов между собой.
Вероятность мутации также является одним из значимых параметров ГА, выбор значения которого неочевиден, но влияет как на скорость работы, так и на саму возможность получения оптимального решения за ограниченное число поколений. Чем выше вероятность, тем быстрее среди хромосом появляются решения, более близкие к оптимальному. Если же мутации появляются часто, то происходит слишком быстрое изменение хромосом. В этом случае решения, близкие к оптимальному, не успевают пройти процедуру кроссинговера и закрепить свои свойства в будущих поколениях. Это замедляет или делает полностью невозможным поиск оптимального решения.
Таким образом, в процессе решения задачи оптимального размещения точек контроля с использованием стандартного ГА выделяем два параметра, значения которых, предположительно, оказывают наиболее сильное воздействие на эффективность работы алгоритма. Это веса целевых функций (соотношение весов) и вероятность мутации хромосом.
Были проведены эксперименты для выяснения зависимости скорости поиска решения от значений параметров. Эксперименты позволили определить наилучшие значения параметров (при которых скорость поиска решения наибольшая) только для исходных данных конкретной задачи. Но общий вид зависимости, очевидно, одинаков для любых исходных данных задачи (графа объекта, требуемой защищенности и т. п.).
В первой группе экспериментов проверялась скорость работы при различных соотношениях весов первой и второй целевой функции. При этом вес третьей функции задавался равным 0,1. Важность выполнения правила о близости средств обнаружения и видеонаблюдения к точкам проникновения ниже, чем у правил первой и второй целевой функции, т. к. более важно соблюдение условия защищенности всех КЭ и минимизация количества ТК.