Содержание к диссертации
Введение
ГЛАВА 1. Анализ существующих модификаций генетического алгоритма и их применение в технических системах 21
1.1 Обзор и анализ генетических алгоритмов.. 21
1.2. Анализ основных направлений повышения эффективности генетических алгоритмов 27
1.3 Анализ применимости генетических алгоритмов и их модификаций в технических системах 35
1.4 Обзор существующих программных комплексов, реализующих оптимизацию с помощью генетических алгоритмов 42
Выводы к первой главе 50
ГЛАВА 2. Разработка способа увеличения вероятности нахождения глобального экстремума генетическим алгоритмом 51
2.1 Построение и анализ математической модели генетического алгоритма...51
2.2 Разработка способа регуляции генетических операторов 64
Выводы ко второй главе 82
ГЛАВА 3. Разработка генетического алгоритма с повышеной вероятностью нахождения глобального экстремума без увеличения времени сходимости 83
3.1 Разработка новых методов обновления генетического материала 83
3.2 Генетический алгоритм с регуляцией вероятностей генетических операторов и с равномерным распределением потомков 92
3.3 Применение разработанного алгоритма в технических системах ...ЮЗ
Выводы к третьей главе 115
ГЛАВА 4. Имитационное моделирование генетических алгоритмов с регуляцией вероятностей генетических операторов и мутацией с равномерным распределением потомков 116
4.1 Методика тестирования генетических алгоритмов 117
4.2 Описание программного комплекса тестирования генетических
алгоритмов. 130
Выводы к четвертной главе ...146
Заключение 147
Список используемых источников
- Анализ основных направлений повышения эффективности генетических алгоритмов
- Обзор существующих программных комплексов, реализующих оптимизацию с помощью генетических алгоритмов
- Разработка способа регуляции генетических операторов
- Генетический алгоритм с регуляцией вероятностей генетических операторов и с равномерным распределением потомков
Введение к работе
Одним из наиболее важных направлений научно-технического прогресса начала XXI века является развитие систем искусственного интеллекта, способных расширить круг решаемых человечеством задач.
Совместно с развитием вычислительно-информационных технологий стало возможным автоматизировать процесс решения технических и экономических вопросов, ранее решаемых вручную. При этом часть таких задач, практически не поддающихся решению классическими методами, решаются системами вычислительного интеллекта, состоящими из следующих направлений:
нечёткая логика и теория множеств;
нечеткие экспертные системы;
системы приближенных вычислений;
теория хаоса; фрактальный анализ;
нелинейные динамические системы;
гибридные системы (нейронечеткие, генетиконейронные, нечеткогенетические системы);
нейронные сети;
эволюционные вычисления.
Из них наиболее перспективным направлением являются эволюционные вычисления, которые подразделяются на эволюционные стратегии [117, 121], эволюционное программирование [88, 90, 91, 92], генетические алгоритмы [102, 103, 104] и генетическое программирование [109, 110]. В свою очередь, из эволюционных вычислений наибольшее распространение получили генетические алгоритмы, способные решать сложные оптимизационные задачи большой размерности.
7 Основные принципы, положенные в основе генетических алгоритмов, достаточно полно отражены в работах [77, 78, 93, 94, 100, 101, 102]. Среди них можно выделить следующие:
- проблемно-ориентированное кодирование решений в бинарную строку,
называемую хромосомой (особью);
работа алгоритма (эволюция) обеспечивается генетической наследственность приспособленных особей путем воздействия на них генетических операторов;
- простота схемы алгоритма, упрощающая адаптацию к конкретным
особенностям технических систем;
- возможность интеграции с неэволюционными алгоритмами.
При этом, генетический алгоритм, в его базовой конфигурации, предложенной в работе [100], обладает недостаточно высокой вероятностью нахождения глобального экстремума [83, 98, 119], вследствии известной проблемы «застревания» в локальных оптимумах. Эта проблема в совокупности с высокими временными затратами на решение задач ограничивают применимость генетических алгоритмов в технических системах.
Например, задача оптимального распределения электроэнергии в условиях повышенной нагрузки. В случае выхода из строя трансформаторных подстанций, вследствие износа оборудования, повышается нагрузка на другие подстанции. Требуется быстро найти такой способ подключения потребителей электроэнергии к трансформаторным подстанциям, при котором нагрузка на устаревшее оборудование будет минимальной и без отключения потребителей. В случае задержки с решением этой задачи, или если ответ будет не оптимальным, произойдёт авария. Устаревшие трансформаторы будут не выдерживать долго повышенной нагрузки, и последовательно будут выходить из строя. При этом, стандартный генетический алгоритм находит оптимальное решение только в 75% случаях [70], а в остальных случаях решение близко к оптимальному.
8 Таким образом, очевидно, что развитие вычислительной техники совместно с развитием систем искусственного интеллекта обусловило автоматизацию решения технических задач с помощью генетических алгоритмов, а с другой стороны отсутствие строгого математического аппарата с полным анализом зависимости эффективности генетических алгоритмов от параметров и различных генетических операторов ограничивает использование их в технических системах.
Для устранения основных недостатков ведутся исследования по созданию математических моделей модификаций генетического алгоритма в следующих направлениях:
- использование нестандартных архитектур генетического поиска;
- использование нестандартных или модифицированных генетических
операторов;
- использование нестандартных способов кодирования генотипа.
К нестандартным архитектурам относятся параллельные, многофазовые, многоуровневые, поколенческие архитектуры, а также макроэволюция, регуляция параметров алгоритма и интеграция с другими методами опимизации на уровне архитектуры генетического поиска. Нестандартные способы кодирования включают в себя использование в качестве хромосом вещественных чисел, символов, деревьев и графов, а также хромосом с переменной длиной, диплоидных хромосом.
Параллельные архитектуры являются адаптацией генетического алгоритма для параллельных вычислительных систем [4, 11, 28, 36, 37, 44, 97, 116]. Многофазовые архитектуры это использование различных вариаций генетического алгоритма на различных этапах эволюции и по сути является усложнением базового алгоритма, кратным числу используемых алгоритмов [59]. Многоуровневые [125] и поколенческие архитектуры [37], а так же макроэволюцию [36] целесообразно использовать совместно с параллельной архитектурой на высокопроизводительных параллельных вычислительных
9 системах, в виду многократно возросшей сложности и высоких временных требований таких алгоритмов по сравнению с базовым генетических алгоритмом. Однако эти алгоритмы имеют высокое преимущество перед базовым, в области специфических задач. Интеграция с классическими методами оптимизации сужает круг решаемых задач, из-за дополнительных требований классических методов к поверхности целевой функции, таких как дифференцируемость, непрерывность и т.д. [32]
Таким образом, перспективной архитектурой генетического поиска, является регуляция вероятностей параметров алгоритма, например вероятностей применения генетических операторов (кроссинговера, мутации, инверсии) [53, 54], а актуальной задачей, является повышение вероятности нахождения глобального экстремума генетическим алгоритмом с помощью регуляции вероятностей генетических операторов.
Исследования нестандартных и модифицированных генетических операторов в основном направлены на увеличение вероятности выхода из локальных экстремумов. При этом, разработанные генетические операторы в большинстве своём универсальны, и могут быть использованы и в других конфигурациях генетического алгоритма. Исключения составляют генетические операторы, адаптированные на использование нестандартных способов кодирования генетической информации, в основном, разрабатывающихся для описания фенотипа узкого круга специфических задач. Как правило, использование нестандартных способов кодирования увеличивает вероятность нахождения глобального экстремума только для тех типов задач, для которых они разрабатывались.
Большое разнообразие различных модификаций генетического алгоритма и отсутствие их сравнительных оценок эффективности затрудняет выбор алгоритма для применения в конкретной технической системе. Таким образом, возникает необходимость решения задачи получения сравнительных оценок эффективности модификаций генетических алгоритмов. Для решения этой
10 задачи в работе предлагается методика сравнения генетических алгоритмов и разработанный на основе её программный комплекс.
Объектом диссертационного исследования являются генетические алгоритмы, применяемые при решении задач глобальной оптимизации в технических и экономических системах.
Предметом диссертационных исследований являются математические модели генетических алгоритмов и генетических операторов.
Целью диссертационного исследования является повышение эффективности достижения оптимумов генетическими алгоритмами без увеличения времени, затрачиваемого на эволюцию.
Научная задача исследований состоит в разработке математических моделей генетических алгоритмов для повышения вероятности нахождения глобальных экстремумов.
Для решения поставленной общей научной задачи проведена её декомпозиция на ряд следующих частных задач.
Разработка и анализ математической модели процессов сходимости к глобальному экстремуму целевой функции и выхода из локальных экстремумов.
Разработка способа регуляции вероятностей генетических операторов для увеличения вероятности нахождения глобального экстремума.
Разработка математической модели оператора мутации с равномерным распределением потомков, для повышения вероятности выхода из локальш[ оптимумов.
4. Проведение экспериментальных исследований и получение
сравнительных оценок надежности разработанных и простого генетического
алгоритмов.
Методы исследований. Для решения поставленной в диссертационной работе научной задачи использованы методы теории вероятностей, основы
теории случайных процессов, теории выживания особей генетических алгоритмов, базирующейся на теореме Холланда.
Достоверность и обоснованность полученных в диссертационной работе результатов и формируемых на их основе выводов обеспечиваются строгостью и корректностью производимых математических выкладок, базирующихся на аппарате теории вероятностей и теории выживания особей в генетических алгоритмах, схожими результатами проводимых экспериментов в данной области, разработкой действующего программного комплекса, на который получено свидетельство о регистрации программы для ЭВМ №2006611765. Справедливость выводов относительно эффективности подтверждается строгостью методики оценки и практическими опытами. Работа состоит из четырех глав и приложений.
В первой главе проведен анализ существующих модификаций генетических алгоритмов. Показаны их достоинства и недостатки. Проведен анализ применимости генетических алгоритмов и их модификаций в технических системах, который показал недостаточную надежность нахождения глобального экстремума в задачах оптимизации в ситуации, когда необходимо получить максимально хорошее решение за ограниченное время, как, например, в задаче оптимального распределения электроэнергии в условиях повышенной нагрузки, в которой рассматривается ситуация выхода из строя трансформаторных подстанций повышения нагрузки на другие подстанции. Требуется быстро найти такой способ подключения потребителей электроэнергии к трансформаторным подстанциям, при котором нагрузка на устаревшее оборудование будет минимальной.
Проведенный анализ основных направлений повышения эффективности генетических алгоритмов показал, что наиболее перспективными являются:
1. Анализ зависимости эффективности генетических алгоритмов от генетических операторов, способов кодирования генотипа и других параметров алгоритма.
2. Анализ возможных схем интеграции генетических алгоритмов с другими методами оптимизации.
Первое направление анализа генетических алгоритмов выбрано в качестве приоритетного, т.к. второе направление — интеграция генетических алгоритмов с другими методами оптимизации - значительно усложняет его реализацию и полученный таким способом алгоритм будет обладать недостатками интегрированного в него метода оптимизации. Такие алгоритмы имеют высокую эффективность в ограниченном круге оптимизационных задач, т.к. повышаются требования к целевой функции.
Генетические операторы являются основной составляющей генетического алгоритма. Надёжность нахождения глобального экстремума полностью определяется эффективностью генетических операторов. Скорость алгоритма зависит от значений параметров генетических операторов. В простом генетическом алгоритме такие параметры, как вероятность кроссинговера, вероятность мутации и вероятность инверсии на протяжении всей эволюции остаются статичными. В настоящее время существует несколько способов регуляции этих параметров, например генетический алгоритм с элементами саморегуляции и двухуровневый генетический алгоритм. Эти алгоритмы имеют значительную сложность в реализации. Кроме того, двухуровневый генетических алгоритм имеет высокие требования к вычислительным ресурсам и выигрывает в скорости только при реализации на параллельных архитектурах.
В связи с вышеизложенным задача исследований формулируется следующим образом: требуется разработать математическую модель генетического алгоритма с регуляцией вероятностей генетических операторов и модифицированными генетическими операторами, имеющего надежность нахождения глобального экстремума целевой функцию выше надежности простого генетического алгоритма без потерь в скорости.
13 Во второй главе проводится анализ теоремы Холланда о выживаемости особей генетического алгоритма. В генетическом алгоритме после фазы первичной кластеризации одновременно протекают два процесса: спуск к лучшему из найденных в фазе кластеризации экстремуму целевой функции и поиск других, более выгодных экстремумов. Спуск к экстремуму обеспечивает оператор кроссинговера, а поиск новых экстремумов и обновление генетического материала обеспечивает оператор мутации. Скорость спуска к экстремуму определяет скорость алгоритма, а от качества поиска новых экстремумов зависит надежность нахождения глобального экстремума.
Для решения первой частной задачи введены следующие определения:
- доминирующий шаблон, это шаблон, у которого среднее значение
приспособленности особей, представленных в популяции в текущий момент
времени, максимально;
- экстремальный шаблон, это шаблон, множеству которого принадлежит
генотип экстремума целевой функции;
- глобально-экстремальный шаблон, это шаблон, множеству которого
принадлежит генотип глобального экстремума.
На основе теоремы Холланда [100], описывающей динамику численности особей шаблона, с учётов введенных определений, в главе описана математическая модель повышения порядка доминирующего шаблона, с учётом особей, перешедших в рассматриваемый шаблон из других шаблонов, более низкого порядка, число которых значительно при высоких значениях вероятности мутации. Так же в предложенной модели учтен факт ограниченности популяции, чего нет в классической теории. При анализе модели были сделаны выводы об оптимальных значениях вероятностей генетических операторов на различных этапах эволюции. На начальном этапе, когда идет обработка случайного генетического материала, сгенерированного при инициализации, и далее, когда доминирующие шаблоны уже выделены, но имеют низкий порядок, оптимальными являются вероятность кроссинговера,
14 равная 1, и вероятность мутации, равная 0. При достижении локального оптимума, когда доминирующий шаблон имеет высокий порядок, оптимальными являются максимальное значение вероятности мутации (для различных типов оператора лежит в пределах от 0,5 до 1) и вероятность кроссинговера в пределах от 0 до 0,5. Таким образом решена первая частная задача.
Для решения второй частной задачи в главе рассматривается процесс выхода генетического алгоритма из локального экстремума. При традиционно высоких значениях вероятности кроссинговера и низких значениях вероятности мутации численность особей доминирующего шаблона возрастает до максимума. Особи, фенотип которых соответствует найденному локальному экстремуму, начинают заполнять своими точными копиями всю популяцию. В результате имеется вырожденная популяция.
В такой ситуации, по выводам, сделанным при решении первой частной задачи, предлагается снизить вероятность кроссинговера, т.к. он уже не может разнообразить генетический материал, а вероятность мутации предлагается увеличить до максимума, чтобы обновить вырожденную популяцию новым генетическим материалом.
Определить степень вырожденности популяции возможно точным методом, вычислив по каждому локусу хромосомы среднеквадратичную разность битов особей по всей популяции. В работе был использован более простой, с точки зрения простоты реализации и требующий меньшего числа вычислений, способ определения степени вырожденности популяции заключается в анализе числа эпох, прошедший без изменения наилучшей приспособленности.
В работе предлагается способ регуляции вероятностей генетических операторов, в котором, вероятности генетических операторов на каждой эпохе вычисляется линейно по числу эпох, прошедших без изменения наилучшей
15 приспособленности, отнесенному к критерию останова алгоритма — максимальному числу эпох без изменения наилучшей приспособленности.
В ситуации, когда наилучшая приспособленность изменяется на каждой эпохе значения вероятностей будут близки к традиционным и обеспечивают максимальную скорость обработки генетического материала оператором кроссинговера. Вероятность мутации в этот момент равна 0. В случае, когда генетический алгоритм "застрянет" в локальном экстремуме, счетчик эпох без изменения наилучшей приспособленности начинает расти, понижая скорость вырождения популяции, и одновременно увеличивает приток нового генетического материала от оператора мутации, что увеличивает шансы выхода из локального экстремума. Таким образом, решена вторая частная задача.
В третьей главе проанализировано распределение потомков стандартного оператора мутации и делается вывод о степени его расхождения с равномерным распределением в зависимости от вероятности мутации. Наибольшая эффективность оператора достигается при вероятности 0,5, что объясняется тем, что при дальнейшем увеличении вероятности мутации наиболее вероятным потомком становится особь, являющаяся инвертированной копией особи на входе мутации, т.е. все биты которой противоположны битам исходной особи. Неравномерность распределения потомков приводит к тому, что вырожденная популяция не может выйти из локального экстремума, т.к. мутация выдает одни и те же особи.
Для решения третьей частной задачи, в работе предлагается использовать оператор мутации с равномерным распределением потомков, который позволяет выйти из локального экстремума при вырожденной популяции. Оператор реализует вероятностный алгоритм, который принимает на вход исходную особь и число эпох без изменения наилучшей приспособленности, и производит потомка. Процесс производства потомка состоит из двух этапов: выбор направления мутации и выбор расстояния мутации. Выбор направления мутации происходит путём выбора из пространства определения целевой
функции случайного вектора. За расстояние мутации принимается случайное
число, равномерно распределённое на интервале от 0 до значения расстояния
мутации. За функцию расстояния мутации принимается линейная зависимость
числа эпох без изменения наилучшей приспособленности, умноженная на
коэффициент, вычисляемый на этапе проектирования генетического алгоритма
в зависимости от параметров кодирования генотипа. После того, как
направление мутации и расстояние мутации получены, рассчитывается потомок как сумма исходной особи и вектора направления мутации, умноженного на расстояние мутации.
Оператор мутации с равномерным распределением потомков осуществляет равномерный поиск по всему пространству допустимых особей при росте счетчика эпох без изменения наилучшей приспособленности, что увеличивает вероятность выхода из локального экстремума. Таким образом решается третья частная задача.
Далее, в главе рассмотрены особенности применения генетических алгоритмов с регуляцией вероятностью генетических алгоритмов и мутацией с равномерным распределением потомков. Описана реализация предложенного в работе алгоритма применительно к оптимизации многомерных аналитических функций. Описаны реализации предложенных математических моделей и способа регуляции вероятностей в двух генетических алгоритмах с регуляцией вероятностей и мутацией с равномерным распределением потомков. Один с двухточечным кроссинговером, а второй со стандартным. По результатам тестирования, проведенном в четвертой главе, вариация алгоритма с двухточечным кроссинговером показала более лучшие результаты. Описана реализация эволюционного алгоритма с мутацией с равномерным распределением потомков применительно к задаче распределения ресурсов энергосистемы. Предложена реализация генетического алгоритма с регуляцией вероятностей генетических операторов применительно к задаче упаковки в контейнеры.
17 В четвертой главе решена четвертая частая задача, а именно разработана методика сравнения генетических алгоритмов, согласно которой выполняются следующие операции:
Определить множество тестируемых алгоритмов.
Определить множество тестовых задач.
Выбрать общие параметры тестируемых алгоритмов для каждой тестовой функции (Для генетических алгоритмов это вероятности генетических операторов, размер популяции, способ кодирования, длина хромосомы). Выбрать требуемую точность решений и объем испытаний К.
Из множества тестируемых алгоритмов выбрать базовый алгоритм, относительно которого будут вычисляться оценки эффективности тестируемых алгоритмов.
Для каждой тестовой функции последовательно К раз испытывается каждый тестируемый алгоритм путём нахождения глобального экстремума. При этом вычисляются следующие характеристики: количество испытаний, в которых у'-й алгоритм нашёл глобальный экстремум /-й тестовой функции и среднее число вычислений целевой функции в процессе поиска.
5. Для каждого тестируемого алгоритма вычисляется итоговая оценка
надежности суммирований произведений полученных оценок на коэффициент
сложности по всем тестовых функциям.
6. Строится таблица тестируемых алгоритмов и их полученных
характеристик.
В работе приводится описание разработанного программного комплекса для применения предлагаемой методики. Комплекс состоит из основной части и подключаемых модулей двух типов: первый тип - это модули, реализующие тестируемые алгоритмы, второй тип — модули, реализующие тестовые задачи различного типа.
Четвертая частная задача решена с помощью указанного программного комплекса. Получены сравнительные оценки надёжности нахождения
18 глобального экстремума для различных модификаций генетических алгоритмов, в том числе и разработанных в диссертационной работе. В качестве тестовых выбран набор сложных многомерных (2, 5 и 10 мерных) функций Де Йонга, Растригина, Гриенвонка. Так же в набор тестовых функции включены задача распределения ресурсов и задача одномерной упаковки.
Научная новизна исследований заключается в следующем:
Разработана математическая модель генетического алгоритма, описывающая процессы, происходящие на различных этапах генетического поиска, в том числе и процесс сходимости к экстремуму целевой функции и процесс выхода из локального экстремума.
Разработан новый способ регуляции вероятностей генетических операторов, эффективность которого подтверждена теоретически и экспериментально.
Разработан оператор мутации с равномерным распределением потомков и описаны варианты его реализации, как для генетического алгоритма, так и для эволюционного поиска. Эффективность разработанного оператора подтверждена теоретически и экспериментально.
Разработана методика тестирования генетических алгоритмов. Создан программный комплекс для статистического анализа результатов решения набора тестовых оптимизационных задач наиболее распространенными модификациями генетического алгоритма, включая предложенные в работе. Получены оценки эффективности для простого генетического алгоритма и ряда его модификаций.
Практическая значимость работы состоит в следующем: 1. Разработанная математическая модель генетического алгоритма может использоваться при исследовании поведения алгоритма в фазе инициализации, в фазе спуска к экстремуму и в фазе выхода из локального экстремума целевой функции.
2. Разработанный способ регуляции вероятностей генетических операторов
может применяться в технических и экономических системах, использующих
генетические алгоритмы.
Разработанный оператор мутации с равномерным распределением потомков может использоваться при решении оптимизационных задач с повышенными требованиями к вероятности нахождения глобального экстремума, в частности задачи распределения ресурсов и задачи упаковки.
Разработанная методика тестирования генетических алгоритмов и разработанный на её основе программный комплекс может применяться при проектировании вычислительных комплексов, использующих генетические алгоритмы.
На защиту выносятся следующие основные положения:
1. Разработанный способ регуляции вероятностей генетических операторов
позволяет увеличить вероятность нахождения глобального экстремума без
потерь в скорости.
Разработанный оператор мутации с равномерным распределением потомков позволяет увеличить вероятность выхода из локальных экстремумов.
Разработанные генетические алгоритмы с регуляцией вероятностей генетических операторов и мутацией с равномерным распределением потомков, а так же их варианты с различными способами кодирования генотипа, позволяют увеличить надежность нахождения глобального экстремума в задачах оптимального распределения ресурсов и упаковки в контейнеры.
Разработанная методика тестирования генетических алгоритмов и разработанный на её основе программный комплекс позволяют получить сравнительные оценки существующих вариантов генетических алгоритмов и сделать выбор наиболее эффективного алгоритма применительно к конкретной технической системе.
20 Личный вклад автора. Лично автору принадлежат разработка математической модели генетического алгоритма, описывающей процессы, происходящие на различных этапах генетического поиска, разработка способа регуляции вероятностей генетических операторов, разработка оператора мутации с равномерным распределением потомков, разработка методики тестирования генетических алгоритмов и разработка программного комплекса на основе этой методики.
Апробация работы. Основные результаты по теме диссертационного
исследования докладывались на VI Международной научно-практической
конференции «Информационная безопасность» (Таганрог, 2004), I
Международной научно-технической конференции
«Инфотелекоммуникационные технологии в науке, производстве и образовании» (Ставрополь, 2004), II Международной научно-технической конференции «Инфотелекоммуникационные технологии в науке, производстве и образовании» (Ставрополь, 2006), VII Международной научно-практической конференции «Информационная безопасность» (Таганрог, 2005), IX региональной научно-технической конференции «Вузовская наука — Северо-Кавказскому региону» (Ставрополь, 2005).
Публикации. По теме диссертации опубликовано 16 печатных трудов в том числе 6 статей в периодических научных изданиях; 10 публикаций в форме докладов на конференциях; 2 статьи опубликованы в журнале «Искусственный интеллект», входящем в перечень ВАК Украины; 1 статья опубликована в журнале «Системы управления и информационные технологии», входящем в перечень, рекомендованных ВАК РФ для публикации докторских диссертационных работ;
Анализ основных направлений повышения эффективности генетических алгоритмов
С 1975 годов основные утверждения [100] были представлены для генов фиксированной длины и соответствующих простых операторов выделяются детектор паттернов Кавичио, работа Франца по инверсии, игрок в покер Смита.
Исследование Кавичио, нацеленное на разработку детектора распознавания образов было одним из первых, использующих гены переменной длины, где использовались правила, оперирующие строками переменной длины, создавая модель машинного игрока в покер. Его разработанная система вычисления ПГА использовала модифицированный кроссинговер, который располагал точки кроссинговера, как на границах строк, кодирующих правила, так и внутри них, включала в алгоритм оператор инверсии, стремясь к более эффективному распределению правил внутри строки.
В [77] была рассмотрена возможность смещения отдельных подмножеств битов внутри строки, по нелинейной оптимизации. Из-за неудачного выбора вида функции оптимизации (которая легко оптимизировалась и простым генетическим алгоритмом без использования инверсии) не было показано реальных преимуществ нового алгоритма по сравнению с общепринятым.
В [78] были предложены различные модификации схем генетического переупорядочивания внутри строки, когда используется кроссинговер. Одновременно был проведен ряд исследований, развивавших теорию Холланда, и продемонстрированы новые генетические операторы.
Исследователи ГА предлагают много других операторов отбора, кроссинговера и мутации. Самый распространённый - турнирный отбор [79, 97]. Турнирный отбор реализует п турниров, чтобы выбрать п особей. Каждый турнир построен на выборке к элементов из популяции, и выбора лучшей особи среди них. Наиболее распространен турнирный отбор с к=2.
Элитные методы отбора [83] гарантируют, что при отборе обязательно будут выживать лучшие члены популяции совокупности. Наиболее распространена процедура обязательного сохранения только одной лучшей особи, если она не прошла как другие через процесс отбора, кроссинговера и мутации. Элитизм может быть внедрен практически в любой стандартный метод отбора.
Двухточечный [97] и равномерный кроссинговеры являются альтернативой одноточечному оператору. В двухточечном кроссинговере выбираются две точки разрыва, и родительские хромосомы обмениваются сегментом, который находится между двумя этими точками. В равномерном кроссинговере, каждый бит первого родителя наследуется первым потомком с заданной вероятностью; в противном случае этот бит передается второму потомку. В работе [42] предложен оператор нечёткого кроссинговера. Потом такого оператора получается в результате обмена между множеством родителей фрагментами хромосомы определенного порядка. ГА с таким оператором проигрывает ПГА при оптимизации унимодальных функций и даёт выигрыш в скорости при оптимизации многомодальных функций.
Среди нестандартных способов кодирования генотипа распространены диплоидные хромосомы [14]. При таком способе кодирования хромосома состоит из двух строк Х-хромосомы и Y-хромосомы. В работе [14] реализован принцип доминантности генов. Хромосома состоит из трех строк: двух строк Х-хромосомы и Y-хромосомы, в которых содержится полная генетическая информация о данной особи и одну опорную, с которой содержатся признаки доминантности генов либо Х-хромосомы, либо Y-хромосомы. Соответственно в данной модификации генетического алгоритма используется свой набор генетических операторов.
Одно из направлений модификации генетического алгоритма заключается в разделении популяции на отдельные участки (ниши), в каждой из которых осуществляется поиск альтернативных вариантов решений. Большинство известных ГА принимают размер популяции постоянным (ГА "стационарного состояния"). Существуют модификации ГА, допускающие варьирование размера популяции, как на различных итерациях алгоритма, так и на одной итерации после выполнения операций скрещивания и мутации ("поколенческие" ГА).
Также в литературе [11] используется принцип «многодетной семьи», который заключается в многократном применении ГО к выбранной паре родителей с целью получения потомства с большей приспособленностью (лучшем значением целевой функции) чем у его родителей.
Обзор существующих программных комплексов, реализующих оптимизацию с помощью генетических алгоритмов
Для достижения поставленной цели диссертационной работы необходимо исследовать и моделировать ГА и его модификации на ЭВМ. Программное обеспечение (ПО) для этих целей должно содержать следующие функциональные возможности: 1. моделирование оптимизации ГА аналитических функций; 2. возможность задать любую оптимизируемую функцию пользователем; 3. возможность моделирования не только ПГА, но и основанных на нём модификации; 4. мониторинг набора параметров в процессе эволюции, таких как вероятности ГО, генетического разнообразия, численности задаваемых пользователем шаблонов; 5. возможность вычисления следующих статистических оценок сходимости ГА: вероятность нахождения глобального экстремума, среднее число эпох, среднее число обращений к целевой функции; 6. возможность вычисления статистических оценок оптимальных значений вероятностей ГО; 7. Возможность моделирования решения технических задач, таких как задача упаковки и задача распределения ресурсов.
Для выбора подходящего ПО был выполнен обзор существующих программных продуктов и реализаций ГА. Программные реализации ГА делятся на обучающие системы, научные программы для исследований ГА, приложения для задач оптимизации и различные надстройки, библиотеки и компоненты для разработчиков ПО на разным языках программирования. Часто программные продукты снабжаются обучающими примерами. Все обучающие продукты не удовлетворяют предъявляемым требованиям, поэтому они не рассматриваются.
Большое число программных реализаций ГА относятся к научным программам. В основном это программы для исследования процессов сходимости ПГА и других модификаций ГА. Как правило, такие программы не предназначены для свободного распространения и используются только авторами или же являются приложениями к научным трудам. Основные известные научные программные продукты, разработанные для исследования ГА представлены в табл. 1.1.
В табл. 1.1 нет ПО, удовлетворяющего всем предъявляемым требованиям одновременно. Пункту 6 - «возможность вычисления статистических оценок оптимальных значений вероятностей ГО» не удовлетворяет ни один из перечисленных программных продуктов для исследования ГА.
Программные пакеты, предназначенные для использования в экономических и технических системах перечислены в табл. 1.2.
Среди программных продуктов, предназначенных для технических систем так же не нашлось полностью удовлетворяющего всем необходимым требованиям. Необходимо разработать новое ПО для исследований. Чтобы облегчить разработку ПО, предполагается использовать специальные программные реализации ГА, предназначенные для разработки программ. В основном это наборы библиотек, содержащие процедуры и функции, облегчающие программирование ГА и его модификаций. Для мощных систем визуального программирования, таких как Дельфи и Визуал Си++ разработаны специальные компоненты, облегчающих использование ГА в своих программах. Эти продукты перечислены в табл. 1.3. 1. Проведен обзор и анализ существующих модификаций ГА, показаны их основные достоинства и недостатки. Произведена классификация основных направлений модификации ГА. Указаны основные направления исследования ГА, направленные на увеличение вероятности нахождения глобальных экстремумов, среди которых выбраны приоритетные для исследования в диссертационной работе.
2. Выполнен анализ применимости модификаций ГА в технических системах. Показаны задачи, в которых применение ГА повысило эффективность технических систем. Из этих задач выделены задача распределения ресурсов и задача упаковки, использующиеся во множестве технических систем, для исследования особенностей решения их с помощью ГА в диссертационной работе.
3. Сформулированы требования к функциональным возможностям ПО для исследования ГА. Выполнен обзор существующего ПО исследования ГА на предмет соответствия сформулированным требованиям. Сделан вывод о необходимости создания многофункционального ПО для исследования ГА в диссертационной работе. Выполнен обзор существующих библиотек функций и компонент, реализующих ГА для использования в разрабатываемом ПО.
4. Для увеличения вероятности нахождения глобального экстремума предложено использовать регуляцию вероятностей генетических операторов и оператора мутации с равномерным распределением потомков.
Разработка способа регуляции генетических операторов
Генетические операторы включают в себя операторы отбора, кроссинговера, мутации и инверсии.
Простейшим вариантом оператора отбора является оператор случайного отбора [91]. Особи для кроссинговера выбираются независимо друг от друга. Их вероятности быть отобранными случайным отбором определяются выражением: Ро= - (2.33) В ПГА используется турнирный отбор [100]. Проводится серия из N «состязаний» между к случайно отобранными особями. Особь с лучшей приспособленностью побеждает особи с худшей приспособленностью. Таким образом, особи с низким значением приспособленности имеют меньшую вероятность быть отобранным, чем особи с высоким значением приспособленности. Наиболее распространен турнирный отбор с к = 2 вследствие простоты реализации и относительной эффективности. Вероятность для каждой особи быть отобранной пропорциональна приспособленности особи по отношению к средней приспособленностью по популяции [98, 100]: P0= =- (2.35)
Большое распространение имеет отбор по принципу рулетки. Реализуется отбор N особей, причем вероятность отбора каждой конкретной особи пропорциональна её приспособленности. Пусть каждой особи популяции соответствует свой сектор рулетки. Размер сектора пропорционален приспособленности особи (для определения размера сектора в отрезке 0-1 можно воспользоваться нормализацией приспособленностей особей популяции). Теперь, необходимо лишь N раз «раскрутить рулетку и посмотреть где остановится шарик». Вероятность отбора каждой особи определяется выражением [100]:
Р =-& В работе [75] предложен более строгий вариант «рулетки». В операторе отбора по принципу рулетки связь числа вхождений конкретной особи в множество отобранных для репродукции особей с приспособленностью этой особи реализуется через вероятность отбора. В пропорциональном отборе вероятностное звено исключается. Здесь число вхождений особи непосредственно пропорционально приспособленности особи.
Селекция с линейным ранжированием [123] предложена в качестве альтернативы пропорциональной селекции, имеющей серьезные недостатки. В процессе селекции с ранжированием все индивиды сортируются по значению функции пригодности и лучшему индивиду присваивается ранг N, а худшему -ранг 1. Тогда вероятность выбора для каждой особи в популяции назначается линейным образом согласно их рангу: Р0 = j\ /"max - (/"max " Мпіп )j [ J (23T
Селекция по принципу родства [48] делится на дальнее (аутбридинг) и ближнее (аутбридинг) родство. Распространены различные варианты по уровню селекции: фенотипичный и генотипичный. Для аутбридинга первая особь выбирается случайно, а вторая с большей вероятностью будет максимально отдаленная от первой в геометрическом смысле. В случае инбридинга вторая особь с большой вероятностью будет максимально близка к первой. Вероятность отбора первой особи определяется следующим выражением (2.33). k=l,N В работе [100] подробно проанализированы случайный и турнирный операторы отбора. Эффективность случайного оператора отбора вызывает сомнения. Из (2.34) можно сделать вывод, что в любом случае число представителей шаблона Н не зависит от эффективности шаблона и уменьшается пропорционально численности популяции. Таким образом, при проектировании ГА с регуляцией вероятностей генетических операторов целесообразно использовать турнирный оператор отбора.
Для дальнейшей разработки эффективного метода управления генетическими операторами необходимо провести анализ на предмет выживаемости шаблона основных генетических операторов.
Традиционный генетический алгоритм использует одноточечный кроссинговер, в котором две скрещивающиеся хромосомы разрезаются один раз в соответствующей точке и производится обмен полученными частями. Однако было изобретено много других различных алгоритмов с иными видами кроссинговера, часто включающих больше чем одну точку разреза. Де Ионг исследовал эффективность многоточечного кроссинговера [83] и пришел к выводу, что двухточечный кроссинговер дает улучшение, но что дальнейшее добавление точек кроссинговера редуцирует деятельность генетического алгоритма. Проблема с добавлением дополнительных точек кроссинговера состоит в том, что стандартные блоки, вероятно, будут прерваны. Однако преимущество большего количества точек кроссинговера состоит в том, что пространство состояний может быть исследовано более полно и подробно.
Число представителей шаблона Н для одноточечного кроссинговера будет определяться выражением (2.13).
В двухточечном кроссинговере [74] (и многоточечном кроссинговере вообще) хромосомы расцениваются как циклы, которые формируются соединением концов линейной хромосомы вместе. Для замены сегмента одного цикла сегментом другого цикла требуется выбор двух точек разреза. В этом представлении, одноточечный кроссинговер может быть рассмотрен как кроссинговер с двумя точками, но с одной точкой разреза, зафиксированной в начале строки. Следовательно, двухточечный кроссинговер решает ту же самую задачу, что и одноточечный кроссинговер, но более полно.
Генетический алгоритм с регуляцией вероятностей генетических операторов и с равномерным распределением потомков
Рассмотрим ГА с РВГО и с РРП применительно к задаче оптимизации: тахДх:). (3.13) Под решение будем понимать вектор х = (xb х2, ... , хм). Функция Дх) - скалярная, многопараметрическая, определённая в любой точке области D, где D является подмножеством RM, М— размерность задачи: VxeD:3f(x)eR, (3.14) D = {x = (xi, x2, ., л/) іЄ[a,, 6/], / = 1,M. Дополнительная информация о свойствах функции Дх), таких как дифференцируемость, липшицируемость, непрерывность, выпуклость, выполнение соотношения Беллмана и т.п., не учитывается. Требуется найти такое решение задачи (3.13) хц такое, что хц. \хц- тахДх) є; 0 є «1; є є R. (3.15) Кодирование генотипа аналитической функции
Генотип х кодируются бинарной строкой s с помощью функции кодирования s = g(x). Для обратного отображения SEX используется функция декодирования х = g_1( ). Переход из пространства параметров в хеммингово пространство бинарных строк осуществляется кодированием переменных Х\, х2, ... , хм в двоичные целочисленные строки достаточной длины, что бы обеспечить необходимую точность. Необходимая точность является тем условием, которое определяет длину бинарных строк. Пространство параметров дискретизируется таким образом, чтобы расстояние между двумя соседними узлами дискретизации было меньше значения необходимой точности решения. Например, для достижения точности є пространство параметров дикретизируется равномерной сеткой с количеством узлов, равным — Значения изменяемых параметров будут соответствовать узлам решетки, дискретизирующеи пространство D. Соответственно, если кодировки двух или более решений будут совпадать, то будут совпадать и сами решения. Каждый интервал \ах, Ь{\ разбивается на к отрезков равной длины. bi= LIrL i=h2,...,M. к
Этим самым покрывается г -й интервал [ah b,] сеткой st из к + 1 узлов с постоянным шагом hf. x\j)=ai+j-hj, j= 1,2, ...,к.
Используя двоичный алфавит {0, 1} каждому узлу сетки s{ присваивается уникальный код длины q. Длина кода q выбирается таким образом, чтобы к 2Ч. Наиболее целесообразно и экономично использовать сетку с к = 29 -1. Тогда символьная запись у-го узла по /-й координатной оси в двоичном коде может быть представлена в виде следующей бинарной конструкции: uU) ijU) UU)
После проведения дискретизации по всем М координатным осям получается пространственная решетка s с (к + Vf узлами в М мерном пространстве М, где каждый узел s представлен в виде:
Так как длина хромосомы s фиксирована и равна L = qM, то любая из 2 возможных бинарных строк представляет собой возможное решение. Узлы сетки st кодируются рефлексивным кодом Грея (табл. 3.1), поскольку код Грея обладает свойством непрерывности бинарной комбинации: изменение кодируемого числа на единицу соответствует изменению кодовой комбинации в одном разряде.
Алгоритм функции кодирования s = g(x) заключается в следующем: На этапе инициализации ГА создаётся массив к = {кг,к2,...,км}, где + 1, i = l,M. Операция _...J означает отбрасывание дробной к; = log: (Ь-аЛ \ є Л части числа.
На вход функции кодирования поступает фенотип х = (х1,х2,...,хм) 1. Инициализация цикла: присвоить і = 1; генотип s = 0. 2. Вычислить десятичный код: d; = Х -а - к, Л pi-eii 2 3. Кодирование параметра кодом Грея: по таблице соответствия десятичного кода и кода Грея выбирается бинарный код s , соответствующий десятичному коду dt. 4. Переход к следующей итерации: К генотипу s дописать справа двоичный код s]; присвоить і = і + 1; если і Мтогда перейти к шагу 2, иначе перейти к шагу 5. 5. Окончание: на выход функции подать генотип s. Алгоритм функции декодирования х = gr(s) заключается в следующем: 1. Инициализация цикла: присвоить і = 1; j = 1. 2. Вычислить десятичный код: из генотипа s взять, начиная с позиции у и до позиции/ + kj- 1, двоичную подстроку S;; по таблице соответствия десятичного кода и кода Грея выбирается, десятичный код dt соответствующий бинарному коду st; присвоить/ = j + k{. -.г, / ib:— a{ 3. Вычислить параметр xt фенотипа x: xt = a{ + dt — . 4. Переход к следующей итерации: присвоить і = і + 1; если і М тогда перейти к шагу 2, иначе перейти к шагу 5. 5. Окончание: на выход функции подать фенотип д: = (хь х2, ..., хм). На рис. 3.7 изображена структурная схема алгоритма кодирования. Таблица соответствия десятичного кода с кодом Грея обозначена как функция s, = Код Грея (d , а операция s shl s, означает сдвиг двоичной последовательности влево. На рис. 3.8 изображения структурная схема алгоритма декодирования генотипа в фенотип. Функцией dt = Код Грея 1 (s{) s = Код Грея {dt) обозначена операции декодирования кода Грея в десятичный код
Похожие диссертации на Разработка и исследование математической модели генетического алгоритма для применения в технических системах
