Содержание к диссертации
Введение
Глава 1. Генетический алгоритм: принципы организации и применения . 11
1.1. Генетический алгоритм: основные генетические операторы и схема 11
1.1.1. Общие принципы ГА 11
1.1.2. Кодировка хромосом 12
1.1.3. Вид генетических операторов 17
1.1.4- Структура и параметры алгоритма 22
1.1.5- Вид функции соответствия 25
1.2- Генетический алгоритм: история появления и развития 27
1.3. Применение генетического алгоритма 29
1.4. Выводы по главе 1 32
Глава 2. Система поддержки принятия решений на основе нечетких продукционных правил: объект параметрической настройки 33
2.1. Организации СППР и построение базы правил на основе лингвистических термов 33
2.2. Разработка схемы шкалирования входных показателей: сравнение с символьной моделью кодирования хромосом 39
2.3. Кодирование и оценка хромосом при параметрической настройке СППР 47
2.3.1. Кодирование хромосом 47
2.3.2, Обучающая выборка и оценивание хромосом 49
2.4. Пример реализации СППР: система автоматизации технического
анализа в области валютного дилинга 52
2.5. Выводы по главе 2 59
Глава 3. Разработка и исследование модифицированных генетических операторов 60
3.1. Теорема шим: принципы функционирования ГА и методы оценки эффективности 60
3.1.1. Шима 60
3.2. Модифицированный оператор мутации: разработка и исследование 68
3.2.1. Линейная генетическая мутация (ЛГМ+) 68
3.2.2. Нормальная генетическая мутация (НГМ+) 75
3.2.3. Показательная генетическая мутация 78
3.3. Модифицированный оператор скрещивания: разработка и исследование 80
3.4. Модифицированный оператор селекции: разработка и исследование 85
3.4.1. Использование промежуточных популяций для селекции хромосом 85
3.4.2. Разработка алгоритма формирования пар: инбридинг и аутбридинг по генотипу и фенотипу 90
3.5. Выводы по главе 3 101
Глава 4. Разработка многопопуляционного параллельного ГА, дополнительных генетических операторов и модели организации подчиненных популяций 103
4.1. Адаптационные механизмы: динамически изменяемые параметры, макромутации, 103
4.1.1. Виды адаптационных механизмов 103
4.1.2. Разработка модифицированного алгоритма с динамически изменяемыми параметрами 106
4.1.3. Макромутация 109
4.2. Многопопуляционныи параллельный генетический алгоритм (МПГА): разработка и исследование 114
4.2.1. Параллельный ГА: причины возникновения и использования 114
4.2.2. Схема многопопуляционного параллельного ГА 116
4.2.3. Алгоритм организации миграции хромосом между популяциями 121
4.3. Выводы по главе 4 124
Глава 5. Программная реализация 126
5.1. Программная реализация разработанных модификаций ГА: модуль «Генетический конструктор» 126
5.1,1- Основные функции модуля 126
5.1.2. Работа с модулем: интерфейс, основные формы 128
5.2. Программная реализация средства построения СППР с генетической параметрической настройкой: модуль «Генетическая СППР» 134
5.2.1. Основные функции модуля 134
5.2.2, Работа с модулем: интерфейс, основные формы 137
5.3. Пример построения и параметрической настройки СППР 140
5.4. БД: хранение сформированных моделей 144
5.5. Разработанные функции и программные модули 146
5.6- Выводы по главе 5 147
Результаты 148
Использующиеся сокращения 149
Список литературы 150
- Кодировка хромосом
- Организации СППР и построение базы правил на основе лингвистических термов
- Линейная генетическая мутация (ЛГМ+)
- Разработка модифицированного алгоритма с динамически изменяемыми параметрами
Введение к работе
Актуальность темы исследований
Исследование и применение эволюционных и генетических алгоритмов является важной частью современных информационных технологий. Использование этих алгоритмов позволяет решать различные классы задач оптимизации. Возможно их применение для решения комбинаторных задач или оптимизации различного вида функций, для настройки нейронных сетей или параметров систем поддержки принятия решений. При этом работа алгоритма является эффективной, она позволяет решать сложные оптимизационные задачи и, в тоже время, опирается на твердую теорию.
Особенностью генетических алгоритмов является то, что они опираются на естественную эволюцию в природе и исходят из принципов наследования и эволюционного отбора. Моделирование процесса естественной эволюции и его применение для решения задач оптимизации - это первостепенная задача для данного направления. В принципе, искусственная селекция животных для селекционеров и селекция виртуальных "животных" на компьютере являются сходными задачами. Поэтому проектировщики генетических алгоритмов могут выгодно использовать знания, полученные селекционерами. Именно с этим связано обилие в теории генетических алгоритмов «биологических» терминов, таких как: «скрещивание», «селекция», «мутация» и «макромутация» и т.п.
Несмотря на то, что базовые принципы эволюционных алгоритмов появились еще в середине 70-х годов прошлого века (в первую очередь благодаря работам Дж. Холланда) их исследование и совершенствование остаются актуальными и в настоящее время. По сути, реализация и отработка этих алгоритмов началась только в 90-х
годах - техническая база во времена Холланда не позволяла заниматься этими вопросами на практике.
Также можно отметить, что, несмотря на существование ряда программных продуктов, реализующих генетический алгоритмы, говорить о вопросе исследования различных форм ГА как о полностью отработанном явно преждевременно. Задача определения более значимых характеристик алгоритма, более эффективных сочетаний и конструкций генетических операторов, более оптимальных вероятностных параметров остается вполне актуальной. Это в первую очередь относится к таким вопросам, как построение параллельных ГА, адаптивных генетических операторов, применение эволюционной теории в стыковке с другими методами оптимизации и информационными технологиями.
В этой связи можно выделить такие направления развития теории генетических алгоритмов как взаимодействие с нейронными системами и теорией нечетких множеств. В случае с нейронными сетями речь может идти как о синтезе их структур при помощи ГА, так и об обучении построенной более традиционным методом структуры. Можно сказать, что использование ГА - это один из наиболее интересных и перспективных методов современной теории нейронных вычислений.
Отдельно остановимся на взаимодействии теории генетических алгоритмов с нечеткими вычислениями и схемами нечеткого логического вывода, являющимися основой для целого класса систем поддержки принятия решений. Построение СППР на основе нечетких логических правил, при помощи лингвистических термов, специальных функций принадлежности и иерархических моделей, позволяющих представить экспертные знания в наиболее точной и корректной форме - это один из наиболее логичных и вместе с тем эффективных методов. Но вместе с тем следует отметить, что добиться значительного повышения точности прогнозов (или рекомендованных стратегий - в зависимости от того, на
решение каких задач ориентирована СППР) можно лишь применив к построенной модели соответствующие методы параметрической идентификации, настройки базовых и вспомогательных параметров. Такими методами с большой степенью эффективности могут быть генетические алгоритмы. Разработка специализированных генетических алгоритмов настроенных на параметрическую идентификацию СППР, в частности, на определение значимости нечетких правил, параметров функций соответствий лингвистических термов и других характеристик системы, несомненно актуальна.
Цель работы
Целью работы является разработка и исследование генетических алгоритмов эффективных при параметрической настройке систем принятия решений. Цель достигается за счет:
разработки параллельных многопопуляционных адаптивных генетических алгоритмов,
разработки модифицированных генетических операторов,
практической реализации программного комплекса для работы с такого рода алгоритмами,
реализации программных средств для построения СППР на основе нечетких продукционных правил и их настройки при помощи ГА
Теоретические и практические результаты
1. Разработан многопопуляционный параллельный генетический алгоритм (МПГА), отличающийся от типового ГА разделением основного набора хромосом на несколько подпопуляций.
Предложены две методики обмена хромосомами между популяциями.
Предложены чряд модификаций генетических операторов: модифицированный механизм скрещивания и мутации; селекция на основе инбридинга и аутбридинга по фенотипу, генотипу и по значению функции соответствия.
Проведены исследования влияния вида генетических операторов и их параметров на эффективность последовательных и параллельных модификаций ГА.
4. В рамках разработки ГА для параметрической настройки СППР
. реализован ряд механизмов адаптации, в частности механизма
макромутаций, механизм циклических изменений параметров и ряд других.
5. Исследованные и разработанные алгоритмы реализованы в виде
программных модулей; проведено практическое тестирование
полученных программных средств при помощи специальных
тестовых функций.
Краткое содержание работы
Работа состоит из введения, 5 глав и заключения. Общий объем работы составляет 148 страниц. Список литературы составляет 21 наименование.
Во введении обосновывается актуальность проблемы, указывается цель проводимого исследования, а также приводятся полученные теоретические и практические результаты.
В главе 1 рассматривается структура типового генетического алгоритма, приводятся его достоинства и недостатки по сравнению с другими методами оптимизации. Приводится анализ различных видов генетических операторов и их параметров. Также в этой главе
приводятся различные сферы применения ГА. В конце главы приведен небольшой экскурс в историю появления эволюционных алгоритмов.
В главе 2 рассмотрены различные варианты построения систем поддержки принятия решений. Приведена классификация моделей СППР, указаны те из них, в которых применение ГА для параметрической идентификации способно привести к повышению эффективности. Разработана модель СППР на основе нечетких логических правил с генетической параметрической настройкой. Представлена схема СППР, рассмотрены ее основные достоинства и недостатки. Также в главе 2 приведен пример реализации СППР при помощи средств, разработанных в рамках данной работы.
В главе 3 рассматриваются варианты алгоритмов с точки зрения применения в них различных генетических операторов. Проанализировано влияние на эффективность алгоритма различных видов операторов скрещивания, мутации и селекции. Реализованы различные варианты алгоритма, с разными генетическими операторами и различной вероятностью их выполнения. Тестирование проводилось при помощи типовых тестовых функций (DeJong's function, Rastrigin's function и т.п.). Также в главе 3 рассмотрен вопрос эффективности функционирования генетических алгоритмов и рассмотрена теорема шим.
В главе 4 рассмотрены параллельные ГА, реализованы несколько моделей параллельного многопопуляционного алгоритма для параметрической настройки СППР, проведено сравнение их эффективности с эффективностью типового последовательного ГА и между собой. Отдельно указаны различные варианты адаптации в ГА, реализован и исследован ряд адаптационных механизмов (в частности механизм макромутаций при достижении популяциями определенной плотности; динамическое изменение вероятностных параметров ГО и т.д.).
В главе 5 представлена программная реализация разработанных и исследованных алгоритмов. Представлен модуль «Генетический конструктор», который позволяет пользователю строить различные варианты генетических алгоритмов, устанавливать различные параметры ГА, тестировать их при помощи специальных тестовых функций. В рамках модуля реализована возможность на каждой итерации просматривать изменение функции соответствия, параметров и кодировки каждой из популяций много по пуля ционно го параллельного алгоритма. Также есть возможность строить классические последовательные алгоритмы. Параметры разработанных алгоритмов сохраняются в специальную базу данных; структура БД также приведена в данной главе.
Также представлен модуль «Генетическая СППР», в рамках которого пользователь имеет возможность строить различные варианты иерархических схем логического вывода, определять лингвистические термы, описывать при помощи них нечеткие правила, проводить настройку параметров при помощи генетического алгоритма. Построенная и обученная система является функциональной, позволяет прогнозировать различные показатели, представляя прогнозы в виде лингвистических термов с той или иной степенью вероятности. В рамках главы 5 приведены экранные формы описанных выше модулей, формируемые в них графики, пользовательские инструкции, а-таюке перечень процедур и функций, которые могут использовать другие разработчики для работы с различными видами генетических алгоритмов и операторов.
Кодировка хромосом
Целью работы является разработка и исследование генетических алгоритмов эффективных при параметрической настройке систем принятия решений. Цель достигается за счет: - разработки параллельных многопопуляционных адаптивных генетических алгоритмов, - разработки модифицированных генетических операторов, - практической реализации программного комплекса для работы с такого рода алгоритмами, - реализации программных средств для построения СППР на основе нечетких продукционных правил и их настройки при помощи ГА Теоретические и практические результаты 1. Разработан многопопуляционный параллельный генетический алгоритм (МПГА), отличающийся от типового ГА разделением основного набора хромосом на несколько подпопуляций. Предложены две методики обмена хромосомами между популяциями. 2. Предложены чряд модификаций генетических операторов: модифицированный механизм скрещивания и мутации; селекция на основе инбридинга и аутбридинга по фенотипу, генотипу и по значению функции соответствия. 3. Проведены исследования влияния вида генетических операторов и их параметров на эффективность последовательных и параллельных модификаций ГА. 4. В рамках разработки ГА для параметрической настройки СППР . реализован ряд механизмов адаптации, в частности механизма макромутаций, механизм циклических изменений параметров и ряд других. 5. Исследованные и разработанные алгоритмы реализованы в виде программных модулей; проведено практическое тестирование полученных программных средств при помощи специальных тестовых функций. Краткое содержание работы Работа состоит из введения, 5 глав и заключения. Общий объем работы составляет 148 страниц. Список литературы составляет 21 наименование.
Во введении обосновывается актуальность проблемы, указывается цель проводимого исследования, а также приводятся полученные теоретические и практические результаты.
В главе 1 рассматривается структура типового генетического алгоритма, приводятся его достоинства и недостатки по сравнению с другими методами оптимизации. Приводится анализ различных видов генетических операторов и их параметров. Также в этой главе приводятся различные сферы применения ГА. В конце главы приведен небольшой экскурс в историю появления эволюционных алгоритмов.
В главе 2 рассмотрены различные варианты построения систем поддержки принятия решений. Приведена классификация моделей СППР, указаны те из них, в которых применение ГА для параметрической идентификации способно привести к повышению эффективности. Разработана модель СППР на основе нечетких логических правил с генетической параметрической настройкой. Представлена схема СППР, рассмотрены ее основные достоинства и недостатки. Также в главе 2 приведен пример реализации СППР при помощи средств, разработанных в рамках данной работы.
В главе 3 рассматриваются варианты алгоритмов с точки зрения применения в них различных генетических операторов. Проанализировано влияние на эффективность алгоритма различных видов операторов скрещивания, мутации и селекции. Реализованы различные варианты алгоритма, с разными генетическими операторами и различной вероятностью их выполнения. Тестирование проводилось при помощи типовых тестовых функций (DeJong s function, Rastrigin s function и т.п.). Также в главе 3 рассмотрен вопрос эффективности функционирования генетических алгоритмов и рассмотрена теорема шим.
В главе 4 рассмотрены параллельные ГА, реализованы несколько моделей параллельного многопопуляционного алгоритма для параметрической настройки СППР, проведено сравнение их эффективности с эффективностью типового последовательного ГА и между собой. Отдельно указаны различные варианты адаптации в ГА, реализован и исследован ряд адаптационных механизмов (в частности механизм макромутаций при достижении популяциями определенной плотности; динамическое изменение вероятностных параметров ГО и т.д.). В главе 5 представлена программная реализация разработанных и исследованных алгоритмов. Представлен модуль «Генетический конструктор», который позволяет пользователю строить различные варианты генетических алгоритмов, устанавливать различные параметры ГА, тестировать их при помощи специальных тестовых функций. В рамках модуля реализована возможность на каждой итерации просматривать изменение функции соответствия, параметров и кодировки каждой из популяций много по пуля ционно го параллельного алгоритма. Также есть возможность строить классические последовательные алгоритмы. Параметры разработанных алгоритмов сохраняются в специальную базу данных; структура БД также приведена в данной главе.
Также представлен модуль «Генетическая СППР», в рамках которого пользователь имеет возможность строить различные варианты иерархических схем логического вывода, определять лингвистические термы, описывать при помощи них нечеткие правила, проводить настройку параметров при помощи генетического алгоритма. Построенная и обученная система является функциональной, позволяет прогнозировать различные показатели, представляя прогнозы в виде лингвистических термов с той или иной степенью вероятности. В рамках главы 5 приведены экранные формы описанных выше модулей, формируемые в них графики, пользовательские инструкции, а-таюке перечень процедур и функций, которые могут использовать другие разработчики для работы с различными видами генетических алгоритмов и операторов.
Организации СППР и построение базы правил на основе лингвистических термов
Генетические алгоритмы разработанные в рамках данной работы предназначены в первую очередь для параметрической настройки систем поддержки принятия решений, организованных на основе нечетких продукционных правил. Алгоритм в данном случае используется для установки лучших значений параметров СППР (в первую очередь весов правил и характеристик функций принадлежности лингвистических термов), т.е. таких значений, при которых решения (прогнозы) системы наиболее точно соответствуют закономерностям, заданным обучающей выборкой. Построение системы, таким образом, можно рассматривать как совокупность двух основных этапов моделирования (см. рис. 2.1.). Структурная идентификация - это первый этап, на котором формируется грубая модель объекта, аппроксимирующая взаимосвязь входов (т.е. числовых или лингвистических характеристик, на основании которых формируется решение) и выходов (решений или прогнозов, получаемых системой) и содержащая настраиваемые параметры. Параметрическая идентификация - второй этап, на котором происходит «обучение» системы при помощи обучающей выборки - то есть подбираются такие значения параметров, при которых минимизируется разность между модельными и экспериментальными выходами объекта. Этот этап сводится к применению различных методов оптимизации, в данном случае - генетического алгоритма.
Модель объекта строится путем проектирования и настройки иерархической нечеткой базы знаний, представляющих собой совокупность лингвистических высказываний типа "Если «входы = ...» То «выход = ...» Вес правила «...»". На основе таких высказываний строится первоначальная модель, а затем производится настройка функций принадлежности нечетких термов и весов правил при помощи генетических алгоритмов.
Рассмотрим ряд принципов, которые должны быть использованы при построении систем поддержки принятия решений на основе нечетких продукционных правил. Во-первых, принцип лингвистичности входных и выходных переменных. Входы и выход объекта рассматриваются как лингвистические переменные, которые оцениваются качественными термами. Используя функции принадлежности того или иного вида, каждый из термов, оценивающий лингвистическую переменную, можно формализовать в виде нечеткого множества, заданного на соответствующем универсуме. Очевидно, что функционирование системы будет в значительной степени зависеть от параметров функций принадлежности и для наиболее эффективной работы необходимо подобрать оптимальные их значения. Таким образом, можно сказать, что параметры функций принадлежности составляют основной массив настраиваемых на этапе параметрической идентификации характеристик. Причем это верно вне зависимости от вида самих функций, т.е. и для треугольных и для а-уровневых и для колоколообразных ФП. Во-вторых, принцип формирования структуры зависимости "входы выход" в виде нечеткой базы знаний. Нечеткая база знаний представляет собой совокупность правил, которые отражают опыт эксперта и его понимание причинно-следственных связей в рассматриваемой задаче. Здесь к массиву настраиваемых параметров добавляется еще.аодна важная характеристика - значимость правила (вес). Параметрическая идентификаций, таким образом, направлена не только на уточнение нечеткой модели и получение более точного соответствия между лингвистическими термами и четкими значениями, но и на оптимизацию базы знаний, удаление недостоверных правил, увеличение значения определяющих закономерностей. В-третьих, принцип иерархичности баз знаний. Использование этого принципа позволяет преодолеть "проклятие размерности", что является актуальным в условиях большого количества входных параметров и правил. Кроме того, это способствует структурированию и более удобному представлению знаний. На рис.2.2 приведен пример дерева, отражающего иерархическую связь показателей.
Линейная генетическая мутация (ЛГМ+)
Одним из определяющих факторов в работе генетического алгоритма является вид и параметры оператора мутации. Мутация расширяет область генетического поиска в пространстве решений, способствует предотвращению преждевременной сходимости, вносит необходимое разнообразие в генотип популяции. Одно из основных достоинств ГА - нахождение глобального экстремума в многоэкстремальных функциях также основано на применении этого оператора так как именно он способен вывести популяцию из локального экстремума.
В главе 1 были рассмотрены традиционно использующиеся мутационные механизмы: равномерные генные и хромосомные мутации (РГМ и РХМ). Их характерной особенностью является равная вероятность изменения генов вне зависимости от их позиции в хромосоме и их значения в фенотипе. Для равномерной генной мутации вероятность изменения значения разряда бинарной строки равно заданному параметру «вероятность мутации». Для равномерной хромосомной мутации вероятность мутации гена определяется из вероятности мутации хромосомы и ее длины: t где Рт - вероятность мутации хромосомы, N - длина хромосомы, С -количество генов, изменяющихся в хромосоме. Но в ряде случаев такой подход не является вполне удовлетворительным- Речь в первую очередь идет об уточнении полученного решения в условии высокой плотности популяции. Рассмотрим пример (рис. 3.4). Предположим, что максимальное значение целевой функции достигается в точке (18,2,55), В результате выполнения генетического был получен результат, показанный на рис. 2,4. Плотность популяции достигла 1, то есть все хромосомы популяции сошлись к значению функции соответствия as и к виду хромосомы, показанному на рисунке. Таким образом суболтимальное решение найдено, но будет ли найден глобальный максимум эт7 С учетом высокой плотности популяции можно сказать, что возможности операторов селекции и скрещивания исчерпаны и улучшение решения может произойти только за счет оператора мутации. Но если в данном алгоритме применяется равномерный оператор мутации, то вероятность такого улучшения также чрезвычайно мала: где л - размер популяции - вероятность мутации гена длина хромосомы Для того, что бы достигнуть максимума необходимо чтобы хотя бы в одной хромосоме популяции произошла мутация двух генов («№13» и «№14») и не мутировали другие гены. При достаточно большом количестве закодированных переменных и длине хромосомы N такая мутация маловероятна.
Таким образом, для уточнения полученного решения в условиях высокой плотности популяции метод равномерной мутации не приемлем, и требуется разработка специализированного оператора мутации.
Рассмотрим разработанный модифицированный оператор мутации (ЛГМ+). Его основными особенностям являются, во-первых, зависимость вероятности изменения гена от его локуса, а во-вторых, использование при мутации не только информации о генотипе, но и о фенотипе. Вероятность изменения разряда при использовании модифицированного оператора может быть представлена в виде следующее зависимости:
Здесь Л/,-длина подстроки, кодирующей ї-ую переменную, d/- локус гена в подстроке Рты, Ртю- максимальное и минимальное значение вероятности мутации. f - вид функции по которой происходит изменение вероятности. Особо следует отметить параметры W/ и di. При использовании традиционных генетических операторов учитываются исключительно характеристики генотипа, такие как длина хромосомы, позиция гена в хромосоме и т.п. В данном же случае одним из факторов, влияющих на работу алгоритма, являются параметры решения - переменные, закодированные в хромосоме; при вычислении вероятности изменения разряда учитывается не длина хромосомы и позиция гена в ней, а длина подстроки, определяющей конкретную переменную и позиция в этой подстроке. Таким образом, вероятность изменения младших разрядов каждой переменной достаточно велика (и равна Pmsx)t а вероятность изменения старших разрядов - мала (вплоть до Ртіл).
Рассмотрим вид функции, в соответствии с которой происходит изменение вероятности мутации. Во-первых, в общем случае это может быть функция, линейно убывающая на интервале от Хгдо Хг (где /гиХ,-младший и старший разряд подстроки соответственно) и принимающая значения от Ртвх до Ртіп. (Линейная генная мутация - ЛГМ+)
Разработка модифицированного алгоритма с динамически изменяемыми параметрами
Перед началом выполнения алгоритма помимо базовой структуры операторов и параметров задается еще и периоды их циклического изменения, условия, при которых эти изменения могут произойти и собственно сама структура изменений. Например, задается следующий цикл: после 50 итерации каждые 10 итераций устанавливать вероятность мутации равной 0.02, при условии, что плотность популяции достигла значения Х- Длительность цикла - 3 итерации. В результате на последних итерациях, выполнения алгоритма будут наблюдаться вспышки мутации (предположим, базовым значением вероятности мутации было 0,005). Аналогично может изменяться любой другой параметр алгоритма, а также вид используемых генетических операторов, т.е. однородное скрещивание может при определенных условиях сменяться на двухточечное, равномерная мутация на линейную и т.д.
По-видимому, в качестве условий активизации цикла можно рассматривать целый ряд показателей, характеризующих работу алгоритма. Например, в [17] (для нечетких правил) используются фенотипный и генотипный разбросы, характеризующие расстояния между лучшими, худшими и средними значениями функций соответствия хромосом. 6 рамках данной работы для организации условий циклов использовались характеристики плотности популяции (в процентах), относительного прироста лучшего значения функции соответствия за период (в процентах) и длительности сохранения значения (в числе итераций). Лучшие показатели дали алгоритмы с циклами, настроенными по первому и третьему условиям. Это вызвано тем, что высокая плотность популяции, как и прекращение изменения значения функции соответствия может быть вызвано, как правило, только двумя причинами: или уже найдено оптимальное решение или же алгоритм сошелся к локальному экстремуму или субоптимальному решению. Как раз во втором случае и бывает целесообразно изменить схему применения генетических операторов и значения их параметров. Для тестирования модифицированного алгоритма использовались рассмотренные в предыдущих пунктах типовые тестовые функции, также адаптационный циклический механизм включен в многопопуляционный параллельный алгоритм (который подробнее рассмотрен в главе 3) и тестировался в его составе. Можно отметить, что использование циклов несколько увеличивает трудоемкость выполнения генетического алгоритма за счет проведения на каждой итерации дополнительных расчетов, но с учетом того, что данный алгоритм является популяционным (т,е. не работает с конкретными хромосомами, а настраивает характеристики популяции в целом), то эти расчеты проводятся один раз за итерацию и повышение трудоемкости нельзя назвать значительным.
В ряде случаев при выполнении ГА возникает ситуация когда базовые генетические операторы не способны вывести популяцию из локального экстремума. При достижении популяцией определенного уровня плотности (в особенности если популяция стала абсолютно однородной) вероятность нахождения глобального оптимума становится исчезающе малой. Скрещивание в такой ситуации становится абсолютно бесполезным, потому что у двух идентичных предков «рождаются» идентичные им потомки. Традиционный оператор мутации с определенной долей вероятности способен вывести популяцию из локального оптимума, но эта вероятность мала (и чем больше параметров кодировано в хромосоме тем она меньше) и, в любом случае, для нахождения нового решения, способного занять место в основной популяции, потребуется излишне много времени. Представленные в главе 2 модифицированные генетические операторы способны решить эту проблему, но только в условиях сходимости к субоптимальному решению, близкому к глобальному оптимуму по фенотипу. Если это условие не соблюдается, то модифицированные операторы также не решат проблему. Значительная часть исследований в области генетической теории посвящена именно вопросу препятствия преждевременной сходимости- И использование оператора селекции без промежуточной популяции кандидатов, с прямой заменой предков потомками, и использование удаленного скрещивания-аутбридинга, и повышение вероятности мутации, и еще целый ряд методов призваны решить эту проблему. Тем не менее, вероятность того, что алгоритм, снабженный всем арсеналом этих средств, все равно сойдется к локальному оптимуму нельзя полностью исключить.
Для предотвращения этого в рамках данной работы был предложен оператор макромутации- Как известно генетические алгоритмы представляют собой разновидность алгоритмов случайного поиска. С другой стороны поиск в ГА все же осуществляется целенаправленно и каждое состояние популяции S(t) определяется состоянием на предыдущей итерации (то есть в предыдущем поколении) S(M). Это свойство определяет эффективность генетического алгоритма по сравнению с обычным случайным поиском; генотип лучших хромосом наследуется потомками, поиск новых решений осуществляется с учетом уже найденных решений. Но в тоже время это свойство и является источником опасности преждевременной сходимости. Оператор макромутации представляет собой элемент случайного поиска, вводимый в генетический алгоритм в случае попадания его в локальный оптимум.
