Содержание к диссертации
Введение
1. Постановка задачи формирования оптимального набора комплекса средств защиты при проектировании защищенного объекта информатизации 12
1.1. Анализ состава и структуры комплексной системы защиты информации 12
1.2. Анализ методической обеспеченности процесса проектирования комплексных систем защиты информации 20
1.3. Формальная постановка задачи выбора оптимального варианта комплекса средств защиты информации при проектировании защищенного объекта информатизации 40
Выводы по I главе 48
2. Разработка модели реализации деструктивных воздействий для априорной оценки эффективности вариантов комплекса средств защиты информации ... 50
2.1. Структура показателей эффективности функционирования комплекса средств защиты информации 50
2.2. Обобщенная структура процесса оценки эффективности функционирования варианта комплекса средств защиты информации .. 66
2.3. Априорная оценка эффективности функционирования комплекса средств защиты на основе моделирования процесса реализации информационных угроз 69
Выводы по II главе 89
3. Разработка методики формирования оптимального состава комплекса средств защиты информации 91
3.1. Анализ методов решения оптимизационных задач 91
3.2. Особенности генетического алгоритма отбора как метода решения оптимизационных задач 97
3.3. Методика формирования оптимального набора комплекса средств защиты в процессе проектирования комплексной системы защиты информации 103
3.4. Научно-технические предложения по технической реализации разработанной методики и оценка её эффективности 119
Выводы по III главе 126
Заключение 128
Список литературы 131
- Анализ методической обеспеченности процесса проектирования комплексных систем защиты информации
- Обобщенная структура процесса оценки эффективности функционирования варианта комплекса средств защиты информации
- Априорная оценка эффективности функционирования комплекса средств защиты на основе моделирования процесса реализации информационных угроз
- Особенности генетического алгоритма отбора как метода решения оптимизационных задач
Введение к работе
В современных условиях информатизации общества не вызывает сомнения необходимость защиты информационных ресурсов. Одной из наиболее важных особенностей информации является возможность её существования в разнообразных формах и её способность распространяться по различным каналам. Кроме того, негативные последствия может повлечь не только факт утраты защищаемой информацией конфиденциальности, но и нарушение её целостности и доступности. В этой связи наиболее целесообразной представляется комплексная защита информации на объекте информатизации в целом.
На сегодняшний день разработано достаточно большое количество ГОСТов и руководящих документов, определяющих требования к защищенным системам и порядок их создания. Вместе с тем, подавляющее большинство из них предлагают реализацию индивидуального проектирования систем защиты информации, выражающегося в построении инфокоммуникационных систем в защищенном исполнении с использованием концепции нисходящего проектирования. Несмотря на очевидные достоинства, такой подход требует значительных временных и материальных затрат, и, зачастую, недоступен ряду организаций с небольшим бюджетом.
Вместе с тем, в настоящее время наблюдается рост объема рынка средств защиты информации, что предопределило возможность реализации концепции восходящего проектирования с использованием типовых решений по средствам защиты,, которая является более доступной для большинства негосударственных учреждений, не оперирующих информацией содержащей государственные секреты и обладающих невысоким бюджетом.
При этом одной из важнейших задач оптимального построения комплексной системы защиты информации (СЗИ) является выбор из множества имеющихся средств такого их набора, который позволит обеспечить нейтрализацию всех потенциально возможных информационных угроз с наилучшим качеством и минимально возможными затраченными на это ресурсами.
Известно, что наиболее эффективно задачи защиты информации решаются в рамках упреждающей стратегии защиты, когда на этапе проектирования оцениваются потенциально возможные угрозы и реализуются механизмы защиты от них. При этом, на этапе проектирования системы защиты информации разработчик, не имея статистических данных о результатах функционирования создаваемой системы, вынужден принимать решение о составе комплекса средств защиты информации, находясь в условиях значительной неопределенности. Тем не менее, методология проектирования систем защиты информации должна предоставлять возможность реализации упреждающей стратегии защиты.
На сегодняшний день методическое обеспечение формирования системы защиты информации для объектов информатизации сформировано недостаточно полно. Выбор необходимого комплекса средств защиты (КСЗ) для обеспечения функционирования данной системы возложен на пользователя и отличается значительной долей субъективизма. А предложения по обеспечению информационной безопасности ограничены общими рекомендациями и не носят комплексного характера.
Таким образом, построение системы защиты на основе использования нормативного подхода и практического опыта построения систем защиты не позволяют говорить об оптимальности предложенного варианта КСЗ.
Таким образом, задача развития и разработки методического обеспечения оптимального выбора состава КСЗ на этапе проектирования объекта информатизации при реализации упреждающей стратегии защиты информации является весьма актуальной.
Данная работа выполнена в соответствии с одним из основных научных направлений Академии Федеральной службы охраны Российской Федерации. Целью работы является совершенствование методического обеспечения формирования рациональной структуры и оптимального состава комплекса средств защиты информации и оценки его показателей эффективности при построении комплексной системы защиты информации. При этом в качестве объекта исследования в работе рассматривается процесс проектирования комплексных систем защиты информации в организации, а предметом исследования является методическое обеспечение формирования оптимального состава комплекса средств защиты информации.
Для достижения указанной цели были решены следующие задачи:
• проведён анализ подходов к проектированию комплексных систем защиты информации, и методов оценки их эффективности;
• разработан подход к формированию множества потенциально возможных угроз информации циркулирующей в организации в рамках упреждающей стратегии защиты информации;
• разработана математическая модель процесса реализации информационных угроз, позволяющая получить априорную оценку эффективности функционирования комплексной системы защиты информации в условиях реализации упреждающей стратегии защиты информации;
• разработана методика формирования рационального состава комплекса средств защиты информации;
• разработаны научно-практические предложения по использованию разработанной методики для построения комплексных систем защиты информации.
Методы исследования. Для получения результатов использовались положения теории защиты информации, теории информационной войны, системного анализа, а также математические методы теории вероятностей, случайных процессов, эволюционных вычислений. Обоснованность и достоверность теоретических исследований, результатов математического моделирования и экспериментальной проверки предлагаемых решений подтверждается строгой постановкой общей и частных задач исследований и корректным применением апробированного математического аппарата.
Научная новизна диссертационной работы заключается в разработке процедуры оценки эффективности комплекса средств защиты информации на основе вычисления прогнозного значения рисков с учетом возможностей злоумышленника по преодолению системы защиты информации, параметров комплекса средств защиты и информационных угроз, а также в применении известного метода эволюционных вычислений в новой предметной области выбора оптимального варианта средств защиты информации.
Практическая значимость полученных результатов заключается в разработке конструктивной методики формирования комплекса средств защиты при проектировании комплексной системы защиты информации и возможности её внедрения в практику деятельности системных интеграторов и служб защиты информации. Совокупность полученных результатов исследования является решением актуальной научной задачи, направленной на обеспечение качества проектирования комплексных систем защиты в условиях упреждающей стратегии, что обеспечивает возможность практического применения разработанной методики в ОАО "МегаФон", ЗАО "Навигатор-технолоджи".
Научные результаты работы используются в Академии Федеральной службы охраны Российской Федерации в ходе учебного процесса на кафедре «Систем документальной связи» курсантами специальности 090106 «Информационная безопасность телекоммуникационных систем» по дисциплинам «Организационно-правовое обеспечение информационной безопасности», «Основы проектирования защищенных телекоммуникационных систем», что подтверждено актом внедрения в учебный процесс. Основные положения, выносимые на защиту:
1. Математическая модель процесса реализации информационных угроз потенциальным злоумышленником, позволяющая получить априорную оценку рисков информационной безопасности организации в условиях реализации упреждающей стратегии защиты информации, учитывающая количественные показатели модели злоумышленника и логику его деятельности.
2. Методика формирования рационального комплекса средств защиты информации, позволяющая найти решение при наличии непереборного числа проектных вариантов в условиях дискретной, многоэкстремальной, неявно заданной целевой функции.
3. Предложения по практической реализации методики формирования рационального состава комплекса средств защиты информации, заключающиеся в формализации и алгоритмизации процесса формирования комплекса средств защиты информации.
Апробация работы. Результаты исследований апробировались и обсуждались на научно-технических конференциях различного уровня:
- II межвузовской научно-практической конференции "Перспективы развития средств связи в силовых структурах, обеспечение информационной безопасности в системах связи" (Голицино, 2006);
- III межвузовской научно-практической конференции "Перспективы развития средств связи в силовых структурах, обеспечение информационной безопасности в системах связи" (Голицино, 2007);
- XVI Международной научной конференции "Информатизация и информационная безопасность правоохранительных органов" (Москва, 2007);
- 33 Всероссийской научно-технической конференции "Сети, системы связи и телекоммуникации. Деятельность ВУЗа при переходе на ФГОС 3-го поколения" (Рязань, 2008).
Публикации. По теме диссертации опубликовано 12 научных работ, в том числе 2 - в изданиях, рекомендованных ВАК Минобрнауки РФ.
Структура и объем работы. Диссертационная работа состоит из введения, трёх глав, заключения и списка литературы из 104 наименований. Основная часть работы изложена на 140 страницах, содержит 37 рисунков, 5 таблиц.
В первой главе проведён анализ процесса проектирования комплексных систем защиты информации, а также методов оценки защищенности информации и оптимизации состава комплекса средств защиты, как основы построения системы защиты информации в целом. Рассмотрена и проанализирована структура комплексной системы защиты информации. Сделан вывод о том, что просчеты в выборе комплекса средств защиты информации на этапе проектирования ведут к неоправданному увеличению ущерба от реализации деструктивных воздействий. В процессе проектирования системы защиты информации на объекте информатизации наиболее трудоемкими и наименее обеспеченными в методическом плане являются этапы оценки эффективности и выбора оптимального проектного варианта. Анализ методов оценки рисков показал, что наиболее точные и адекватные результаты дают аналитические методы, они также позволяют учесть изменение уровня защищенности информационных ресурсов с течением времени, а также особенности процесса реализации различных типов угроз. Сформулирована задача исследования на вербальном уровне и формализована в математическом виде.
Во второй главе разработана модель процесса реализации информационных угроз, позволяющая произвести априорную оценку риска информационной безопасности с учетом особенностей различных типов информационных угроз. Предложена обобщенная модель позволяющая оценить априорную эффективность функционирования варианта комплекса средств защиты информации. В третьей главе предложена процедура оптимизации состава комплекса средств защиты, которая в совокупности с предложенной моделью составила основу методики формирования рационального состава комплекса средств защиты информации. Разработано программное обеспечение, позволяющее реализовать алгоритм методики. Оценена эффективность применения в процессе проектирования комплексной системы защиты информации предложенной методики по сравнению с используемыми в настоящее время. Полученные данные позволили сделать вывод о том, что использование методики позволяет сократить время проектирования, получить обоснованный вариант КСЗ, уменьшить вероятность ошибки проектирования.
В заключении сделаны общие выводы и приведены основные результаты диссертационной работы. А также приведены сведения о внедрении полученных результатов и о публикациях по теме диссертации.
Анализ методической обеспеченности процесса проектирования комплексных систем защиты информации
В настоящее время вопросу построения комплексных систем защиты информации для различных объектов информатизации решается на международном, государственном и ведомственных уровнях. Так в последнее время создано множество стандартов [37-46] регламентирующих требования к системам защиты информации и описывающие лучшие практики в области построения защищенных информационных систем.
Структура нормативно-методического обеспечения защиты информации представлена на рисунке 1.5.
Тем не менее, нормативный подход к построению комплексных СЗИ не позволяет в условиях наличия достаточно большого количества разнородных средств защиты информации определить достаточность того или иного набора этих средств, превосходство одного варианта КСЗ над другим, а тем более обосновать оптимальность выбранного комплекса средств защиты.
Общая схема построения комплексных систем защиты информации включает в себя пять этапов [58, 98]: подготовительный; аналитический; исследовательский; рекомендательный; внедрение.
Более подробная схема формирования защищенного объекта информатизации представлена на рисунке 1.6.
В ходе подготовительного этапа создаются и применяются различные базы данных информационных ресурсов ОИ и связей между ними. Интегрированные средства автоматизированного проектирования с алгоритмическими функциями анализа информационных рисков, представляющих информацию в наглядном виде отсутствуют. Существующие системы [17, 20, 26, 29, 48, 58, 64, 86, 102], такие как CRAMM, RiskWatch, Авангард, Гриф и другие, формируют логическую структуру информационной системы ОИ на основе ответов экспертов на вопросы о ней, либо позволяют отобразить ресурсы, группы пользователей, виды информации в древовидном виде.
При проектировании систем защиты информации обычно приходится использовать CASE-средства общего назначения для разработки, отображения и анализа различных схем, такие как Microsoft Visio, ERWin и другие [20]. Однако они не дают возможности в автоматическом режиме связать полученные модели информационной системы ОИ и протекающих в ней процессов с различными системами анализа рисков ИБ ОИ.
На аналитическом этапе определяют совокупность угроз, характерных для рассматриваемого ОИ, выделяют категории объектов, подлежащих защите.
На данном этапе проектирования определяются показатели качества системы защиты информации, в их числе выделяют: целевые, технические, эффективности жизненного цикла, экономические, эффективности управления, социальные и др. Определяются допустимые ограничения, накладываемые системой защиты информации на информационную систему (например, уменьшение производительности аппаратной и программной составляющих ограничения административно-органнизационного плана и др.).
Проводится анализ возможных к применению средств зашиты информации и их характеристик, определяется совместимость средств защиты с функционирующей системой (в т.ч. аппаратная часть, операционная система, прикладные программы).
Вышеописанные мероприятия наиболее полным и эффективным образом производятся с использованием программных средств, упрощающих и улучшающих создание и обработку базы данных средств защиты информации, их технических характеристик и возможностей по применению в системе защиты во взаимосвязи с другими средствами защиты и информационными активами организации [58].
Следовательно, подготовительный и аналитический этапы целесообразно объединить в одном программном средстве, в рамках реализации единой методики.
В процессе реализации исследовательского этапа проводится анализ состояния системы и оценка видов угроз, а также ценности информации, на которые воздействуют угрозы. Разрабатываются специальные шкалы оценок допустимых потерь в натуральном и денежном эквивалентах.
Обобщенная структура процесса оценки эффективности функционирования варианта комплекса средств защиты информации
Однако в реализации системы отсутствуют конкретные методики расчета составляющих элементов рисков. Исходные данные для расчета рисков - ущерб и вероятность вводятся в модель. Существует справочная база данных, помогающая проектировщику в выборе этих значений, но процедура остаётся неформализованной. Недостатком является методологически сложный этап выбора значений показателей, измеряемых в количественных шкалах, который полностью перекладывается на аналитика. Какой либо верификации значений не предполагается. Другой особенностью является отсутствие базы данных по вероятностям появления угроз. Она заполняется данными под конкретный заказ.
Таким образом, данную систему сложно рассматривать как универсальный инструмент проектировщика.
В систему встроен модуль по оценке спроектированных моделей комплексов мер и мероприятий защиты информации по критерию «эффективность - стоимость». Однако, отсутствует как БД по средствам защиты информации, так и алгоритмическое обеспечение анализа моделей систем технической защиты информации.
Другой отечественной системой анализа и управления рисками является Digital Security Office 2006, которая состоит из двух программных модулей ГРИФ и КОНДОР. Данная система позволяет производить анализ рисков на основе собственной классификации угроз DSECCT отдельно по угрозам доступности, целостности и конфиденциальности. При этом эффективность средств защиты и коэффициенты защищенности отдельных информационных активов задаются экспертным путем, а в качестве основного показателя для оценки рисков используется произведение вероятности реализации угрозы на ущерб от её реализации для угроз конфиденциальности и целостности, и произведение времени простоя системы на ущерб для угроз доступности.
Основными недостатками представленных систем являются: использование в качестве показателей для оценки и управления рисками предсказания годовых потерь и оценки возврата от инвестиций, что существенно затрудняет применение данных средств для оценки безопасности ведомственных объектов информатизации; не учитывается российское законодательство и руководящие документы ФСТЭК по защите информации; методологическая сложность решения задачи выбора значений показателей, измеряемых в количественных шкалах, которая полностыо перекладывается на аналитика; используются в основном эмпирические методы расчета результирующих показателей качества СЗИ.
Эти недостатки в сочетании с зависимостью стоимости защиты от уровня защищенности информационных ресурсов позволяют сформулировать требования к средствам анализа и управления защитой информации на объекте информатизации, с учетом российской специфики: учет требований российского законодательства и руководящих документов ФСТЭК; использование научно обоснованной методики расчета и оценки зависимости эффективности защитных механизмов от времени; сокращение субъективизма, вызванного наличием экспертной информации при формировании исходных данных; выбор более пригодных критериев для оценки эффективности вариантов КСЗ; возможность учета количественных параметров модели злоумышленника, а также логики его деятельности по преодолению защитных механизмов; использование алгоритма оптимального выбора механизмов безопасности, позволяющего осуществить построение СЗИ при ограниченных затратах на реализацию защиты.
Как показывает анализ литературы, в настоящее время еще не окончательно сформирована методология построения подсистем защиты для сложных организационно-технических систем, к которым можно отнести большинство ОИ. Задачи защиты решаются фрагментарно, выделением разнородных сил и средств. Сложившаяся практика защиты информации строится в основном на эвристических подходах и ориентирована, прежде всего, на решение задач защиты организационными мерами, рассматривается с позиций защиты информации от несанкционированного доступа и решается, прежде всего, за счет внедрения межсетевых экранов, частных виртуальных сетей, а также использования криптографических средств, контролирующих доступ и защиту от воздействий извне. При этом нельзя говорить о комплексном подходе к защите информационных ресурсов от всего комплекса информационных угроз направленных на нарушение их конфиденциальности, целостности и доступности.
Решение задачи синтеза системы защиты информации невозможно без развития количественных методов оценки её эффективности. Обобщенная классификация таких методов приведена на рис. 1.7.
Западные организации широко используют для оценки эффективности систем защиты экономические показатели такие как ROI (Return on investment, доход от инвестиции), NPV (Net percent value, чистый дисконтированный доход), IRR (Internal Rate of Return, внутренняя норма доходности) [103] (см. рис. 1.8.) Величина NPV дает ответ на вопрос является ли проект эффективным при заданной норме дисконта, a IRR определяется в процессе расчета и затем сравнивается с требуемой инвестором нормой дохода на вкладываемый капитал [49].
Априорная оценка эффективности функционирования комплекса средств защиты на основе моделирования процесса реализации информационных угроз
Оценка эффективности функционирования КСЗИ представляет собой сложную научно-техническую задачу. Комплексная СЗИ оценивается в процессе проектирования ОИ, в период эксплуатации и при создании (модернизации) СЗИ для уже существующих ОИ.
При разработке сложных систем распространенным методом проектирования является синтез с последующим анализом. Система синтезируется путем согласованного объединения блоков, устройств, подсистем и анализируется (оценивается) эффективность полученного решения. Из множества синтезированных систем выбирается лучшая по результатам анализа, который осуществляется с помощью моделирования.
Моделирование КСЗИ заключается в построении образа (модели) системы, с определенной точностью воспроизводящего процессы, происходящие в реальной системе. Реализация модели позволяет получать и исследовать характеристики реальной системы.
Для оценки систем используются аналитические и имитационные модели. В аналитических моделях функционирование исследуемой системы записывается в виде математических или логических соотношений. Для этих целей используется мощный математический аппарат: алгебра, функциональный анализ, разностные уравнения, теория вероятностей, математическая статистика, теория множеств, теория массового обслуживания и т. д.
При имитационном моделировании моделируемая система представляется в виде некоторого аналога реальной системы. В процессе имитационного моделирования на ЭВМ реализуются алгоритмы изменения основных характеристик реальной системы в соответствии с эквивалентными реальным процессам математическими и логическими зависимостями.
Модели делятся также на детерминированные и стохастические. Модели, которые оперируют со случайными величинами, называются стохастическими. Так как на процессы защиты информации основное влияние оказывают случайные факторы, то модели систем защиты являются стохастическими.
Моделирование КСЗИ является сложной задачей, потому что такие системы относятся к классу сложных организационно-технических систем, которым присущи следующие особенности: сложность формального представления процессов функционирования таких систем, главным образом, из-за сложности формализации действий человека; многообразие архитектур сложной системы, которое обуславливается многообразием структур ее подсистем и множественностью путей объединения подсистем в единую систему; большое число взаимосвязанных между собой элементов и подсистем; сложность функций, выполняемых системой; функционирование систем в условиях неполной определенности и случайности процессов, оказывающих воздействие на систему; наличие множества критериев оценки эффективности функционирования сложной системы; существование интегрированных признаков, присущих системе в целом, но не свойственных каждому элементу в отдельности (например, система с резервированием является надежной, при ненадежных элементах); наличие управления, часто имеющего сложную иерархическую структуру; разветвленность и высокая интенсивность информационных потоков.
Для преодоления этих сложностей применяются: 1) специальные методы неформального моделирования; 2) декомпозиция общей задачи на ряд частных задач; 3) макромоделирование.
Для решения задачи проектирования СЗИ предлагается методика основанная на использовании моделей функционирования КСЗ, учитывающих характеристики потенциального злоумышленника и средств защиты. Обобщенная схема процесса оценки эффективности функционирования комплекса средств защиты информации в ходе реализации упреждающей стратегии защиты информации представлена на рис. 2.3.
На основании руководящих документов [41-46], требований заказчика, структуры и состава ОИ из всей совокупности средств защиты информации и возможных угроз выбираются такие их подмножества, которые соответствуют рассматриваемому ОИ и сложившимся условиям. На этом этапе необходимо проанализировать возможности проявления угроз различного вида, вопросы совместного функционирования различных СрЗИ друг с другом и с элементами ОИ.
Для решения задачи определения наилучшего варианта из множества синтезированных на первом этапе необходима методика оценки эффективности функционирования КСЗИ, которая основывается на результатах полученных в ходе использования моделей воздействия информационных угроз, функционирования КСЗИ и использования ресурсов объекта информатизации.
Результаты оценки эффективности функционирования комплекса средств защиты информации лежат в основе методики оптимизации его состава.
Множество угроз, которым подвергается защищаемая информация можно условно разделить на различные классы. Вопросы классификации угроз рассмотрены в большом количестве работ [1, 13, 22, 52, 54, 67, 71, 74].
Особенности генетического алгоритма отбора как метода решения оптимизационных задач
Согласованность и эффективность работы элементов биологических организмов наводит на мысль о возможности использования принципов биологической эволюции для оптимизации практически важных для человека систем. Возможность применения методов эволюционных вычислений для решения разнообразных оптимизационных задач исследовалась в целом ряде работ [9, 30,31,33, 100, 102] В общем виде эволюционный алгоритм - это оптимизационный метод, базирующийся на эволюции популяции "особей". Каждая особь характеризуется приспособленностью - многомерной функцией ее генов. Задача оптимизации состоит в максимизации функции приспособленности. В процессе эволюции в результате отбора, рекомбинаций и мутаций геномов особей происходит поиск особей с высокими приспособленностями. Основные эволюционные алгоритмы: - генетический алгоритм, предназначенный для оптимизации функций дискретных переменных и акцентирующий внимание на рекомбинациях геномов; - эволюционное программирование, ориентированное на оптимизацию непрерывных функций без использования рекомбинаций; - эволюционная стратегия, ориентированная на оптимизацию непрерывных функций с использованием рекомбинаций; - генетическое программирование, использующее эволюционный метод для оптимизации компьютерных программ.
По сравнению с обычными оптимизационными методами эволюционные алгоритмы имеют следующие особенности: параллельный поиск, случайные мутации и рекомбинации уже найденных хороших решений. Они хорошо подходят как простой эвристический метод оптимизации многомерных, плохо определенных функций, что определяет возможность их использования для решения задачи диссертационного исследования. Наибольшее распространение получил генетический алгоритм [100] обобщенный вид которого представлен на рисунке 3.3. Генетический алгоритм (ГА) [100] - это модель эволюции популяции искусственных "особей". Каждый особь характеризуется своей хромосомой Хк, хромосома есть "геном" особи. Хромосома определяет приспособленность особи f[Xk); к = 1,..., п\ п — численность популяции. Хромосома есть цепочка символов Хк = {Хк1, Хк2,...Лш), N - длина цепочки. Символы интерпретируются как "гены" особи, расположенные в хромосоме Хк . Задача алгоритма состоит в максимизации функции приспособленности В решаемой задаче в качестве функции приспособленности выступает модель априорной оценки эффективности функционирования варианта КСЗ в условиях информационных угроз. Эволюция состоит из последовательности поколений. Для каждого поколения отбираются особи с большими значениями приспособленностями. Хромосомы отобранных особей рекомбинируются и подвергаются малым мутациям. Формально, схема ГА может быть представлена следующим образом (популяция t-то поколения обозначается как {Xk(t)}): Шаг 0 . Создать случайную начальную популяцию {Хк{0)}. Шаг 1. Вычислить приспособленность j[Xk) каждой особи Хк популяции {Xk(t)}. Шаг 2. Производя отбор особей Хк в соответствии с их приспособленностями f[Xk) и применяя генетические операторы (рекомбинации и точечные мутации) к отобранным особям, сформировать популяцию следующего поколения {Xk(t+l)}. Шаг 3. Повторить шаги 1,2 для t = 0, 1, 2, ... , до тех пор, пока не выполнится некоторое условие окончания эволюционного поиска (прекращается рост максимальной приспособленности в популяции, число поколений t достигает заданного предела и т.п.). Имеется ряд конкретных вариантов генетического алгоритма, которые отличаются по схемам отбора, рекомбинаций, по форме представления хромосом и т.д.
Наиболее традиционный вариант генетического алгоритма базируется на следующей схеме: 1) цепочки символов в хромосомах бинарны (символы Хк1 принимают значения 0 либо 1), длина цепочек постоянна (N — const), 2) метод отбора пропорционально-вероятностный, 3) рекомбинации производятся по схеме однократного кроссинговера. Пропорционально-вероятностный отбор означает, что на шаге 2 отбор производится с вероятностями, пропорциональными приспособленностям fk особей (fk=f(Xk) ) . Схему можно представить, как выбор особи с помощью рулетки, относительные площади секторов которой равны qk =fk [X ift ]" . Возможны и другие методы отбора. Например, отбор может быть ранжированным: все особи ранжируются по приспособленностям и заданная часть (скажем, лучшая половина) лучших особей отбирается для формирования следующего поколения. Одноточечный кроссинговер организуется по аналогии с биологической рекомбинацией. А именно, если есть два родителя Xj = (Хц, Х12,...Лш) кХ2= (Х2], Х22,..., X2N), то их потомки есть (Хц,..., Х]т, X2tm+1,...X2N) и (X2i,..., Х2т, Xitt„+],...X1N); т.е. "голова" и "хвост" хромосомы потомка берутся от разных родителей. Точка кроссинговера выбирается случайным 101 образом между т-м и га+1-м "генами". Аналогичным образом может быть организован двухточечный и "несколько-точечный" кроссинговер. Тип рекомбинации по схеме кроссинговера часто дополняется инверсиями, т.е. изменением порядка следования символов в участках хромосом; это аргументируется, как необходимость подобрать существенные для приспособленности комбинации символов в хромосоме. Некоторые схемы ГА используют равномерные рекомбинации. Это означает, что два родителя имеют двух потомков, символы хромосомы одного из потомков выбираются случайно от любого (но сохранением порядка следования символов), а второму потомку достаются оставшиеся символы. Например, два потомка родителей Xi = (XJJ, Х12,..., X1N) иХ2= (X2i, Х22,..; X2N), могут иметь следующие хромосомы (Xj], Х22, Х13, Х]4,..., X2N) и (X2j, Х]2, Х23, Х24,..., XJN). Использование для решения задачи исследования классического генетического алгоритма с пропорциональным отбором и одноточечным кроссинговером позволяет добиться приемлемого времени решения, поэтому предлагается в рамках разрабатываемой методики применить именно этот оптимизационный алгоритм. Как метод оптимизации, ГА обладает внутренним параллелизмом, поскольку разные частные существенные комбинации генов - их часто называют "схематами" ("schemata") - отыскиваются параллельным образом, одновременно для всех комбинаций. Данный механизм проиллюстрирован на рисунке 3.5. Доказана высокая эффективность применения генетических алгоритмов в следующих случаях [62, 100]:
