Содержание к диссертации
Введение
1. Основные тенденции развития эволюционного моделирования 9
1.1. Эволюционное моделирование 9
1.2. Типы генетических алгоритмов 13
1.3. Примеры программной реализации 24
1.4. Выводы 30
2. Математические модели эволюции и их использование для повышения эффективности эволюционного моделирования 33
2.1. Модели эволюции 33
2.1.1. Модель эволюции дульнева 34
2.1.2. Дискретные модели циклов жизни 35
2.1.3. Модель старения маккендрика — фон фёрстера 36
2.1.4. Оптимизация эволюционных процессов с помощью управления размером популяции 38
2.2. Использование моделей эволюции для решения задач оптимизации 40
2.3. Методы повышения эффективности эволюционного моделирования 44
2.4. Выводы 57
3. Эволюционное моделирование с динамическим изменением параметров 59
3.1. Эволюционные алгоритмы с динамическими параметрами 59
3.2. Оценка эффективности алгоритмов эволюционного моделирования с динамическими параметрами 72
3.3. Выводы 77
4. Разработка программной реализации алгоритмов и анализ экспериментальных исследований 79
4.1. Разработка инструментальной среды эволюционного моделирования 79
4.2. Экспериментальные исследования эволюционных алгоритмов с динамическими параметрами 85
4.3. Влияние динамических параметров эволюционных алгоритмов на нахождение оптимального решения 86
4.4. Оценка эффективности эволюционных алгоритмов с динамическими параметрами 104
4.5. Выводы 108
Заключение 110
Список литературы 112
- Использование моделей эволюции для решения задач оптимизации
- Методы повышения эффективности эволюционного моделирования
- Оценка эффективности алгоритмов эволюционного моделирования с динамическими параметрами
- Экспериментальные исследования эволюционных алгоритмов с динамическими параметрами
Введение к работе
Эволюционное моделирование является одной из фундаментальных областей научных исследований на стыке информатики, биологии и искусственного интеллекта [1]. Они находят применение при решении различных задач проектирования [11,12], оптимизации нейронных сетей [13], исследования графов [И], построения правил вывода в самонастраивающейся экспертной системе продукционного типа [3].
Алгоритмы эволюционного моделирования позволяют решать две задачи: изучение динамики процесса эволюции, исследование свойств и изменений популяции в зависимости от изменения среды; поиск множества решений, наилучшим образом удовлетворяющих заданной целевой функции.
Одним из новых подходов является использование моделирования эволюции и генетических алгоритмов по аналогии с процессами развития, изменения и приспособления живых организмов.
Генетика — наука о законах наследственности и изменчивости организмов. Основные задачи генетики — это разработка методов управления наследственностью и наследственной изменчивостью для получения "нужных" индивидууму форм, организмов или в целях управления их индивидуальным развитием.
Основные законы генетики утвердили принцип дискретности в явлениях наследования и организации генетического материала, сосредоточили главное внимание на изучении закономерностей наследования потомками признаков и свойств их родителей.
Сейчас генетические алгоритмы (ГА) — хорошо известная и эффективная оптимизационная методология, основанная на аналогии процессов натуральной селекции и генетических преобразований.
5 Биологические основы этой эффективной методологии для адаптационных процессов есть эволюция от одной генерации решений к другой. Причем, основой этого процесса является "выживание сильнейших", что выполняется путем исключения "слабых" элементов и оставление оптимальных или квазиоптимальных элементов [15].
В быстро прогрессирующей теории ГА содержится теоретический анализ классических адаптивных систем, в которых структурные модификации осуществляются последовательными и параллельными преобразованиями символов, выбранных из некоторого алфавита. Поиск оптимальных решений в поле таких представлений и выполняют ГА.
Эволюционные вычисления являются адаптивными алгоритмами, что позволяет применять их в нелинейных задачах высокой размерности при отсутствии требований к дифференцируемости оптимизируемой функции или полноты знаний о решаемой проблеме. Они отличаются устойчивостью при поиске решения, хотя в сложных задачах может быть низка скорость его определения.
При решении задач эволюционного моделирования обычно используются фиксированные размеры популяции и время жизни каждого индивида, что приводит к возникновению явления преждевременной сходимости. Оператор редукции особей и оператор селекции разнесены по времени, что приводит к несогласованности этих процедур. Поэтому актуально использование динамических параметров, введение операторов редукции, аналогичных процессам в живой природе, что позволит повысить эффективность алгоритма, обеспечить сохранение найденных лучших решений.
Для решения этой задачи могут быть использованы алгоритмы эволюционного моделирования с динамическими параметрами.
Объект исследования. Объектом исследования являются алгоритмы эволюционного моделирования с динамическими параметрами, программная реализация алгоритмов, зависимость критериев оптимизации от параметров алгоритма, разработка методики определения параметров генетических операторов в зависимости от качества решения.
Цели и задачи работы. Целью данной диссертационной работы являются исследование и разработка методов повышения эффективности алгоритмов эволюционного моделирования. Для достижения поставленной цели решаются следующие задачи:
Исследование и разработка алгоритмов эволюционного моделирования с динамическими параметрами;
Исследование и разработка критериев адаптивного выбора параметров эволюционных алгоритмов;
Построение прикладных систем эволюционного моделирования на основе предложенных подходов;
4) Оценки эффективности эволюционных алгоритмов с динамическими параметрами.
Методы исследования. Методы исследования базируются на теории алгоритмов, алгоритмах эволюционного моделирования и генетического поиска. Приведенные в работе положения подтверждаются экспериментальными результатами.
Научная новизна. Научная новизна заключается в получении следующих результатов:
Предложен подход к построению эволюционных систем с динамическими параметрами.
Разработаны алгоритмы эволюционного моделирования с динамическими параметрами.
Вычислены оценки эффективности алгоритмов на основе фундаментальной теоремы теории генетических алгоритмов.
Установлены эмпирические зависимости эффективности эволюционного поиска от параметров алгоритма, что позволило выработать рекомендации по их оптимальному выбору.
7 Предложена архитектура инструментальной среды эволюционного моделирования.
Практическая ценность. Разработанные в результате анализа существующих методов эволюционного поиска алгоритмы эволюционного моделирования с динамическими параметрами позволяют использовать новые возможности при оптимизации решений. Структурные схемы алгоритмов реализованы программно.
Реализация результатов работы. Основные теоретические и практические результаты диссертационной работы использованы в научно-исследовательских работах, выполненных по гранту Российского Фонда Фундаментальных Исследований № 01-01-0044, госбюджетной работе № 14890, выполненной по плану Министерства образования Российской Федерации, и госбюджетной работе № 12300, выполненной в рамках Федеральной программы "Перспективные информационные технологии" по плану Министерства науки, промышленности и технологии Российской Федерации.
Материалы диссертации использованы в учебном процессе на кафедре ТОЭ, САПР ТРТУ при проведении практических занятий в цикле лабораторных работ по курсу "Генетическое программирование", "Методы генетического поиска", "Информатика".
Апробация работы. Апробация научных и практических результатов работы проводилась на научных семинарах( 1999-2001, ТРТУ), международных научно-технических конференциях "Интеллектуальные САПР-99", "Интеллектуальные САПР-2000", V всероссийской научной конференции студентов и аспирантов " КРЭС-2000", научной конференции "Интегрированные модели и мягкие вычисления в искусственном интеллекте"(2001г.), международной научно-технической конференции "Интеллектуальные САПР-2001".
Публикации. По теме диссертации опубликовано 11 печатных работ.
Структура и объем диссертационной работы. Диссертационная работа состоит из введения, четырех глав, списка литературы и приложений. Работа содержит 122 страниц, включая 28 рисунка, 27 таблицы, список литературы из 105 наименований, 4 страницы приложений.
Использование моделей эволюции для решения задач оптимизации
Конкуренция и отбор - основные понятия самоорганизации и эволюции в сложных системах. Конкуренция с математической точки зрения означает оптимизацию параметров, функций или функционалов.
Конкуренция связана с селекцией, т.е. отбором лучшего решения в смысле заданного критерия цели. Отбором называется особая форма когерентного поведения подсистем сложной системы. Она встречается в том случае, когда в результате конкурентной ситуации между способными в принципе к существованию подсистемами возникает процесс, ведущий к исчезновению, по крайней мере, одной из подсистем или класса подсистем. Исходя из этого, можно выделить следующие виды отбора: 1. один объект возникает раньше другого, что не позволяет последнему принять участие в происходящих событиях; 2. выбор из эквивалентных вариантов.
Эти формы отбора рассматриваются с той точки зрения, что результат их действия зависит от начальных условий, и что существенную роль играет нелинейный закон роста (гиперболический рост). Такие формы отбора называются "гиперотбором". При "простом отборе" результат отбора зависит не от количества начальных условий, а лишь от некоторых совокупностей параметров, характеризующих подсистемы. Каждая подсистема имеет свою селективную ценность, и побеждает подсистема, имеющая наибольшую селективную ценность. Простой отбор играет важную роль, поскольку допускает неограниченную последовательность подсистем все более высокого качества, однако это не гарантирует существования селекционной ценности, стремления к оптимуму.
Простой отбор и гиперотбор являются основными принципами самоорганизации [100].
Рассмотрим экстремальные принцип в теории процессов отбора и эволюции. Экстремальный принцип может быть принципом сегрегации, принципом отбора, принципом эволюции. Эти принципы можно произвольным образом комбинировать, в результате чего различают девять типов - от динамического принципа сегрегации до полного принципа эволюции (рис. 2.3).
Таким образом, существование любого из этих принципов гарантирует существование всех подчиненных ему принципов. Например, доказательство несуществования одного из принципов влечет за собой вывод о несуществовании всех предшествующих ему общих принципов. Если установлен полный принцип эволюции, то тем самым известны качественные свойства всех возможных процессов отбора и эволюции рассматриваемой модели.
Конкуренция и отбор имеют фундаментальное значение для процессов эволюции, но сами по себе они еще не приводят к эволюции. Чтобы система могла эволюционировать, необходима мутация - случайное производство альтернативных возможностей.
Взаимодействие мутаций и отбора в процессах эволюции можно описать следующей схемой (рис. 2.4). Каждая мутация означает возмущение в установившемся на некоторое время равновесии. Мутант приводит к проверке системы на устойчивость относительно появления нового вида. Если мутация не дает никаких преимуществ по сравнению с существующими ранее видами, то новый вид исчезает в результате процесса отбора. Система оказывается устойчивой относительно возмущения. Отбор ведет к уничтожению нового вида, и система возвращается в исходное состояние. В другом случае, при преимуществе нового вида, система оказывается неустойчивой и переходит в новое селекционное состояние, соответствующее переходу на более высокий уровень эволюции.
Методы повышения эффективности эволюционного моделирования
Эффективность эволюционного моделирования зависит от множества факторов. Их оптимальный выбор приводит к повышению скорости и устойчивости поиска.
Скорость эволюционного поиска определяется временем, необходимым для выполнения заданного пользователем критерия останова (достижения заданного числа итераций, качества популяции или сходимость). Устойчивость поиска определяется способностью постоянно повышать среднюю целевую функцию и преодолевать локальные оптимумы.
Среди эволюционных алгоритмов генетические алгоритмы (ГА) используются наиболее часто для решения задач оптимизации, поскольку при построении конкретного ГА часто удается эффективно использовать различные предполагаемые свойства структуры пространства поиска, зависящие от решаемой задачи. Возможное объяснение принципа работы ГА представлено Голдбергом как гипотеза о строительных блоках [3], в которой предполагается, что ГА выполняет одновременно две задачи. Первая заключается в выращивании строительных блоков, а вторая состоит в смешивании этих блоков с целью получения оптимального решения. Чтобы получить достаточно уверенную сходимость к глобальному оптимуму, необходимо, чтобы оба этих процесса были сбалансированы надлежащим образом. Выращивание больших строительных блоков может быть ускорено увеличением селективного давления, однако это приведет к преждевременной сходимости алгоритма, не оставляя достаточного времени для рекомбинации блоков и исследования пространства поиска [11].
При конструировании адаптивных алгоритмов эволюционного моделирования исследуются следующие проблемы: 1) способы определения целевой функции; 2) генетическое представление решения, а именно способ, которым решению будет сопоставляться строка символов; 3) методы формирования начальной популяции. 4) операторы рекомбинации и мутации, позволяющие получить новую особь-решение из существующих родительских решений; 5) схемы отбора; 6) методы останова; 7) оператор редукции.
При этом выбор конкретных параметров должен соответствовать предполагаемым свойствам пространства поиска и определяется решаемой задачей.
Эффективность работы алгоритмов эволюционного моделирования во многом зависит от построения целевой функции [74].
С помощью эволюционных алгоритмов могут исследоваться системы, состоящие из объектов, обладающих сложной структурой и большим числом разнообразных характеристик. Часть этих характеристик влияет на величину ЦФ, а часть не влияет и может (должна) не рассматриваться при построении алгоритма. Поэтому для эффективного построения алгоритма встает вопрос о построении правильного отображения ЦФ множества М моделируемых реальных объектов О на рассмотренное множество используемых в алгоритме объектов А. Такое отображение может понадобиться, чтобы избежать обработки в генетическом алгоритме балласта из таких неважных свойств объектов. Таким образом в некоторых задачах для значительного уменьшения объема нужно или экспертно задать взаимно однозначное отображение пространства М в пространство А, или экспертно указать способ построения объектов множества Ми А друг из друга.
Традиционные оптимизационные задачи имеют целевую функцию с фиксированной областью значений, называемой также ландшафтом [13].
При разработке алгоритмов эволюционного моделирования с динамическими параметрами в качестве целевой функции были выбраны одномодальные и двумодальные математические функции с фиксированной областью значений. Задачей эволюционного алгоритма обычно ставится задача либо минимизации, либо максимизации значения целевой функции. Целевая функция должна вычисляться в зависимости от того, какие свойства индивидов должны улучшаться в процессе поиска.
Способ кодирования решения в значительной степени влияет на эффективность генетического поиска, поскольку кодирование вместе с оператором рекомбинации определяют эффективность обмена информацией между решениями, что в основном отличает ГА от других методов не эволюционной оптимизации. Для каждого класса задач должна строиться своя модель или способ представления, отражающие специфику и особенности решаемой задачи [6, 71-73]. Как правило, не все кодировки удобны для выполнения рекомбинации генетических строк. Обычно рассматривают два варианта: а) относительно простая кодировка и сложный оператор кроссинговера, требующий соблюдения валидности решений; б) кодировка, при которой любой оператор рекомбинации дает валидные решения.
Кроме того, некоторые альтернативные кодировки порождают дополнительный эпистасис, т.е. сильную взаимозависимость битов в формировании целевой функции [74], когда отдельный бит имеет смысл только в совокупности с некоторыми другими. Примером такой кодировки может служить кодирование текущего решения как перестановки относительно некоторого базового решения.
Оценка эффективности алгоритмов эволюционного моделирования с динамическими параметрами
Рассмотрим фундаментальную теорему генетических алгоритмов [3,11]. Эта теорема показывает асимптотическое число схем "выживающих" при реализации генетического алгоритма на каждой генерации. Влияние на число выживающих и умирающих схем оказывает значение целевой функции отдельной хромосомы и значение вероятностей генетических операторов (кроссинговера, мутации, селекции). Генетический поиск требует наличия популяции хромосом. Будем считать, что популяция хромосом Aj,j=l,2,...,n содержится в популяции A(t) во время (или генерацию) t. Пусть схема Н строится из алфавита V={0,1, }. Согласно сказанному, схема может быть определена на двоичной хромосоме длины L. Очевидно, что для алфавита мощности к существует (k+l)L схем. Более того, существует n-2L схем, содержащихся в популяции размера п, потому что каждый стринг представляется двумя схемами. Все созданные схемы не являются равными. Некоторые более специфичны, чем другие. Например, схема 011 1 имеет больше определенных состояний, чем схема о . Для количественной оценки схем введены две характеристики [11]: порядок схемы - О(Н); определенная длина схемы - L(H). Порядок схемы - число закрепленных позиций (в двоичном алфавите -число единиц и нулей), представленных в шаблоне.
Определенная длина - есть расстояние между первой и последней числовой стринговой позицией. Предположим, что заданы шаг (временной) t, т примеров схем Н, содержащихся в популяции A(t). Все это записывают как m=m(H,t) -возможное различное число различных схем Н при заданном t. В процессе репродукции хромосомы копируются согласно их ЦФ. После сбора непересекающихся популяций размера п с перемещением из популяции A(i) мы ожидаем получить m(H,t+l) представителей схемы Н в популяции за время t+І. Это вычисляется уравнением где f(H) - средняя ЦФ хромосом, представленных схемой Н за время t. Если обозначить среднюю ЦФ всей популяции как /=sum[f(j)]/n, то Другими словами, частные схемы «растут» как отношение средней ЦФ схемы к средней ЦФ популяции. Схема с ЦФ выше средней в популяции будет получать больше возможности для копирования и наоборот по правилу репродукции Холланда. Предположим, что схема Н остается с выше средней ЦФ с величиной с-/, где с-константа. Тогда выражение (3.6) можно модифицировать так: Начиная с t=0 и предполагая, что с - величина постоянная, получим Известно также, что вероятность «выживания» хромосомы At на шаге / после ОР определяется величиной Величина t изменяется от 1, 2,.. g, где g — число генераций генетического алгоритма.
Если мы только копируем старые хромосомы без обмена, поисковое пространство не увеличивается и процесс затухает. Потому используется оператор кроссинговера. Он создает новые хромосомы и увеличивает или уменьшает число схем в популяции. Нижняя граница вероятности выживания схемы после применения ОК может быть вычислена для любой схемы. Так как схема выживает, когда точка ОК попадает вне «определенной длины», вероятность выживания для простого ОК определяется по формуле 3.9: Если ОК выполняется посредством случайного выбора, например, с вероятностью Р(ОК), то вероятность выживания схемы определится выражением
Экспериментальные исследования эволюционных алгоритмов с динамическими параметрами
Цель экспериментального исследования - найти оптимальные параметры предложенных алгоритмов, при которых решение данной задачи (глобальный и близкие ему локальные максимумы функций) становится возможным или улучшается по сравнению с простым генетическим алгоритмом. Эффективность (оптимальность) алгоритмов может быть доказана в результате[102-105]: 1) Теоретического исследования, т.е. сравнения оценок временной сложности алгоритма (ВСА). 2) Экспериментальные исследования, т.е. путем проведения экспериментов и сравнения экспериментальных данных.
При выполнении данной работы на этапе исследований проведена серия экспериментов, собраны экспериментальные данные и проведено статистическое исследование этих данных. Объектами исследований в данной работе являются эволюционные алгоритмы с динамическими параметрами. 3) Цель работы - это исследование зависимости скорости сходимости эволюционных алгоритмов при использовании динамических параметров. В качестве критерия эффективности алгоритма используется нахождение максимального значения целевой функции за определенное количество итераций (число генерируемых поколений), выраженное в процентах. Исследование ЭА с динамическими параметрами должно быть объективным. Для обеспечения объективности необходимо провести серию экспериментов, используя различные тестовые функции. Таким образом, экспериментальные исследования состоят из следующих этапов: 1) Проведение серии экспериментов для фиксированных значений общих параметров и изменяемых дополнительных для каждого алгоритма; 2) Снятие экспериментальных данных - максимального и среднего значения целевой функции, полученных при использовании конкретного алгоритма; 3) Выполнение пунктов 1-2 для различных тестовых функций; 4)
Определение параметров алгоритмов, при которых решение задачи наиболее оптимально и возможно. После уточнения плана эксперимента приступим к исследованиям, при выполнении которых необходимо собрать экспериментальные данные. На основе статистических исследований подберем такие значения параметров переменных для каждой структуры ЭА, которые приводят к наиболее оптимальному решению тестовых задач. В качестве параметра эффективности будем считать процент нахождения оптимума целевой функции, который выражен из среднего максимального и среднего значения целевой функции по десяти прогонам алгоритма. Общие параметры для всех алгоритмов: - Начальный размер популяции -Р =10; - Вероятность оператора кроссинговера - Pcross =90%; - Вероятность мутации - Pmut=10%; - Критерий останова алгоритма (число генерируемых поколений)-N= 10; - Число прогонов алгоритма - NN=10; - Разрядность хромосомы - L=6; Результаты исследования эволюционного алгоритма с переменным временем жизни (ЭА1) приведены ниже. В этом алгоритме варьируемыми параметрами являются константа внешних воздействий S и минимальное время жизни хромосомы MinLT.
В таблицах 5-9 , в колонке "MinLT" дано минимальное время жизни хромосомы, при котором проводится тестирование, в строке "S" приведена величина константы внешних воздействий, в строках "fMaKc fcp" указаны усредненные максимальное и среднее значения целевой функции в процентах, полученные в результате тестирования. Анализируя табличные результаты тестирования (таблицы 4.1-4.5) и графики, показанные на рис. 4.6, можно сделать вывод, что оптимальные параметры исследуемого алгоритма лежат в следующих пределах: минимальное время жизни MinLT - [2-5], константа внешних воздействий s(n+l) - [0,7-1,5]. В эволюционном алгоритме с динамическим размером популяции (ЭА2) варьируемыми параметрами являются число удаляемых элементов D и уровень репродукции R. В таблицах 4.6-4.10 , в колонке "D" дано число удаляемых элементов, при котором проводится тестирование, в строке "R" приведен приведен диапазон изменения уровня репродукции, в строках "fMaKc, fcp" указаны усредненные максимальное и среднее значения целевой функции в процентах, полученные в результате тестирования. Оптимальные параметры исследуемого алгоритма лежат в следующих пределах (таблицы 4.6-4.10, рис. 4.7): число удаляемых элементов D - [1-3], уровень репродукции R - [0,3-0,8].
