автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Моделирование сложных систем коэволюционным алгоритмом генетического программирования

На правах рукописи

Р

ЖУКОВ ВАДИМ ГЕННАДЬЕВИЧ

МОДЕЛИРОВАНИЕ СЛОЖНЫХ СИСТЕМ КОЭВОЛЮЦИОННЫМ АЛГОРИТМОМ ГЕНЕТИЧЕСКОГО ПРОГРАММИРОВАНИЯ

05.13.01 - Системный анализ, управление и обработка

информации

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Красноярск - 2006

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования «Сибирский государственный аэрокосмический университет имени академика М.Ф. Решетнева»

Научный руководитель: доктор физико-математических наук, доцент

Попов Евгений Александрович

Официальные опнонмгты: доктор технических наук, профессор

Ловчиков Анатолий Николаевич

кандидат техзшческих наук, доцент Царев Роман Юрьевич

Ведущая организация: Томский государственный университет

систем управления и радиоэлектроники

Защита состоится 28 декабря 2006 г. в 11.00 на заседании диссертационного совета Д212.249.02 в Сибирском государственном аэрокосмическом университете имени академика М.Ф. Решетнева по адресу: 660014, г. Красноярск, пр. им. газ. "Красноярский рабочий", 31.

С диссертацией можно ознакомиться в научной библиотеке СнбГАУ.

Автореферат разослан 27 ноября 2006 г.

Ученый секретарь диссертациошгого совета

И.В. Ковалев

Общая характеристика работы

Исследование с помощью математических моделей зачастую является единственно возможным способом изучения сложных систем и решения важнейших практических задан управления. Высокие темпы информатизации различных видов деятельности в настоящее время привели к тому, что появилась возможность компьютерного моделирования и проектирования сложных систем, изучения их свойств и управления ими в условиях неполноты информации, ограниченности ресурсов, дефицита времени. При этом для исследования характеристик любой системы математическими методами должна быть выполнена формализация, то есть построена математическая модель.

Однако на практике сложно зафиксировать свойства функциональной зависимости выходных параметров от входных величин, еще сложнее привести аналитическое описание такой зависимости. Одним из способов решения данной проблемы является применение эволюционных алгоритмов путем решения задачи символьной регрессии методом генетического программирования. Символьная регрессия дает математическое выражение в символьной форме, которое можно подвергнуть содержательному анализу, упростить и далее использовать для моделирования или оптимизации. Эффективность применения алгоритмов генетического программирования определяется плательной настройкой их параметров, что препятствует их более широкому распространению, т.к. требует от конечных пользователей высокой квалификации и большого опыта в применении эволюционного моделирования, что редко наблюдается на практике. Поэтому необходимо разрабатывать адаптивные самонастраивающиеся алгоритмы генетического программирования для решения задач символьной регрессии. Кроме того, при решении задачи символьной регрессии с помощью метода генетического программирования часто возникает проблема подбора численных коэффициентов модели, что приводит к необходимости решения задачи минимизации функции ошибки аппроксимации, которая является, чаще всего, многоэкстремальной. Такие задачи успешно решаются эволюционными алгоритмами оптимизации." Все это приводит к необходимости разрабатывать и применять комбинации алгоритмов генетического программирования (для построения моделей) и генетических алгоритмов (для уточнения параметров модели).

Поэтому разработка методов, позволяющих в рамках единого подхода автоматизировать процесс построения и оптимизации математических моделей сложных систем и процессов, и выработка рекомендаций по правильному использованию алгоритмов в ходе автоматизированного моделирования является актуальной научно-технической задачей.

Целью диссертационной работы является совершенствование процесса моделирования сложных систем с помощью эволюционных алгоритмов, направленное на обеспечение возможности адаптивного выбора эффективного алгоритма моделирования в ходе решения задачи.

Поставленная цель предопределила следующую совокупность решаемых задач:

1. Исследовать эффективность метода генетического программирования на представительном множестве тестовых функций.

2. Разработать и реализовать адаптивную процедуру, позволяющую автоматизировать настройку параметров моделей, получаемых с помощью метода генетического программирования.

3. Разработать и программно реализовать модифицированный генетический алгоритм адаптивной настройки параметров модели и оценить его эффективность.

4. Провести сравнительный анализ обычного и модифицированного метода генетического программирования с целью выявления наиболее эффективного направления его совершенствования.

5. Разработать и реализовать алгоритм генетического программирования с адаптивным выбором настроек и оценить его эффективность на множестве тестовых задач.

6. Определить параметры, наиболее существенно влияющие на эффективность разработанного алгоритма генетического программирования, и выработать рекомендации по их настройке.

7. Программно реализовать разработанный самонастраивающийся алгоритм генетического программирования с оптимизацией параметров модели и решить с его помощью практические задачи автоматизированного моделирования сложных систем.

Методы исследования. При выполнении диссертационной работы использовались методы системного анализа, исследования операций, теории оптимизации, теории вероятностей и математической статистики, теории эволюционных алгоритмов, методика создания прикладных интеллектуальных систем.

Научная новизна результатов диссертационной работы состоит в следующем:

1. Разработан новый гибридный алгоритм символьной регрессии, сочетающий метод генетического программирования для выбора структуры модели и модифицированный генетический алгоритм для настройки ее параметров.

2. Впервые разработан коэволюционный алгоритм решения задач символьной регрессии, обладающий свойством адаптации стратегии поиска в ходе решения задачи.

3. Установлено сочетание значений параметров коэволюционного алгоритма генетического программирования, обеспечивающее высокую эффективность решения сложных задач моделирования.

Практическая значимость. На основе предложенного алгоритмического обеспечения разработаны современные программные системы, которые позволяют широкому кругу пользователей в рамках единого подхода решать задачи моделирования сложных систем. Полученные в диссертационной работе рекомендации по настройке параметров адаптивного коэво-

люционного алгоритма позволяют конечным пользователям, не владеющим аппаратом эволюционных алгоритмов, решать сложные задачи моделирования, возникающие в реальной практике.

Работа выполнена в рамках ФЦНТП «{Исследования и разработки по приоритетным направлениям развития науки и техники па 2002-2006 годы» по теме 2006-РИ-16.0/001/076 (государственный контракт № 02.438. 11,7043) и 2006-РИ-19.0/001/377 (государственный контракт № 02.442.11. 7337), в рамках НИР 4422 «Разработка и исследование эффективности гибридных методов оптимизации алгоритмически заданных функций дискретных переменных», выполняемой по ведомственной научной программе «Развитие научного потенциала высшей школы», а также по темппану СибГАУ «Бионические методы идентификации и оптимизации сложных систем» (№Б1.1.05).

Реализация результатов работы. В ходе работы над диссертацией реализованы три программные разработки, которые прошли экспертизу и зарегистрированы в Отраслевом фонде алгоритмов и программ Государственного координационного центра информационных технологий Федерального агентства образования.

Программные системы, разработанные в ходе выполнения работы, используются в качестве лабораторных установок для обучения студентов Сибирского государственного аэрокосмического университета по дисциплинам «Интеллектуальные технологии и принятие решений» и «Интеллектуальный анализ данных», студентов Красноярского государственного университета по дисциплинам «Эволюционные алгоритмы моделирования и оптимизации» н Интеллектуальные технологии анализа данных».

Разработанные программные системы использованы при решении практических задач аппроксимации рефрактометрических свойств прозрачных магнетиков и моделирования фазовых границ магнитного состояния кристаллов. Результаты решения и программные системы переданы Институту физики СО РАН, что подтверждено актом о передаче и использовании.

Основные защищаемые положения:

1. Разработанный гибридный алгоритм решения задачи символьной регрессии позволяет эффективно строить адекватные аналитические модели сложных систем с уже подобранными оптимальными параметрами и превосходит стандартный метод генетического программирования по быстродействию и надежности.

2. Коэволюционный алгоритм решения задач символьной регрессии обеспечивает автоматическую настройку стратегии поиска в ходе решения задачи и превосходит по эффективности стандартный и гибридный алгоритмы решения задач символьной регрессии по быстродействию и надежности.

3. Выработанные рекомендации по настройке параметров коэволю-ционного алгоритма генетического программирования позволяют широкому кругу пользователей, не владеющих аппаратом эволюционного моде-

лирования и оптимизации, успешно применять его при решении практических задач.

Публикации. По теме диссертации опубликовано шестнадцать печатных работ, список которых приведен в конце автореферата.

Апробация работы. Основные положения и отдельные результаты диссертации докладывались и обсуждались на Всероссийских конференциях "Решетневские чтения" (2004-2006 гг.), Всероссийской научно-практической конференции "Информационные технологии и математическое моделирование (ИТММ)" Томск (2004, 2006). Полученные результаты и диссертационная работа в целом обсуждалась на научных семинарах экспериментальной лаборатории тггеллектуальных технологий и адаптации и кафедры САИО в СибГАУ (2004-2006 гг.), на семинарах НИИ СУВГГГ (2005-2006 гг.), на научном семинаре кафедры механики и процессов управления Красноярского госуниверситета (2006 г.), на семинаре Сибирского государственного технологического университета (2006г.).

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, списка литературы и приложения.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность работы, сформулирована цель и поставлены задачи исследования, рассмотрены вопросы научной новизны и практической ценности проведенных исследований, изложены основные положения, выносимые на защиту.

Первая глава диссертации посвящена исследованию алгоритма решения задачи символьной регрессии с помощью метода генетического программирования.

Как правило, если экспертные знания об объекте в явном виде отсутствуют, то по имеющимся статистическим данным строится некоторая вычислительная модель (например, статистические методы, нейронные сети, непараметрический подход). Однако, при всем удобстве численной модели для принятия решений, ее недостаток заключается в том, что она, ло сути, является «черным ящиком», моделью, в которой перечисляются входные и выходные связи системы со средой, а информация о внутренней структуре «ящика» полностью отсутствует. Решение задачи символьной регрессии могло бы значительно улучшить ситуацию. Задача символьной регрессии заключается в нахождении математического выражения в символьной форме, аппроксимирующего зависимость между конечным набором значений независимых переменных и соответствующими значениями зависимых переменных. Генетическое программирование (ГП) - один из самых многообещающих подходов в данном направлении.

ГП является модификацией генетического алгоритма (ГА), основное различие - в представлении решений. Решения в ГП могут иметь различную форму и размер. Наиболее распространешгым является представление в виде деревьев, содержащих в узлах элементы одного из двух множеств:

■ б-

множества функций F и множества термов Т. Экспертные знания о природе задачи могут быть включены во множества F и Т в виде специальных функций или термов. В частности, термами могут быть специфические для предметной области константы (например, ускорение свободного падения, постоянная Планка и т.п.). Функции или комбинации функций, широко применяемые в исследуемой области, могут быть включены в функциональное множество, что избавляет от необходимости генерирования их в ходе работы алгоритма (например, факториалы, комбинаторные формулы и т.п.).

Функция пригодности вычисляется по заданной обучающей выборке. Для решения задачи символьной регрессии в работе предложена следующая функция пригодности:

fitness(A ) = ■————- • complexity^ ) J Z+Error(Aj) i

if min(y) > 0, then Z = maxfy) if min(y)< 0 & & max(y)> 0, then Z = (max(y)- min(y)) if min(y)<0&&max(y)s0,tben Z = min(jy|)

Eiror(Aj) = Z ^ -evaluateA., x.))

complexity(A () = 1— j i

с-М)*2

где Яй1ез5(А,) - пригодность решения А^, Еггог(А^) - квадратичная ошибка аппроксимации, вычисляемая по всем точкам обучающей выборки, N -объем обучающей выборки, суа!иа1е(А^, х() - значение полученного выражения А^ в точке x¡, сотр1ехЬу(Ар - штраф на сложность дерева, зависящий от общего количества вершин, С^(п)- количество вершин решения А , к - коэффициент штрафа, указанный пользователем.

Стандартная схема ГП представлена на рисунке 1.

Рисунок 1. Схема алгоршма генетического программирования

В связи с тем, что ГП является стохастической процедурой, оценка его эффективности осуществляется усреднением по многократным запускам (все исследования проводились при усреднении по 20-ти запускам алгоритмов). Для сравнения алгоритмов использовался показатель надежности, т.е отношение числа успешных запусков алгоритма к общему числу запусков.

В результате исследования работы метода ГП была определена наиболее эффективная комбинация настроек алгоритма ГП: метод роста - метод полного выращивания; селекция - пропорциональная или ранговая; рекомбинация - кратный узел; мутация - метод роста; вероятность мутации — 0,25 или 0,5; начальная глубина деревьев - 3-4; стратегии формирования нового поколения - элитизм.

При решении задачи символьной регрессии с помощью метода ГП часто возникает следующая проблема: в задачах, где решение имеет сложное выражение, деревья с более простой структурой (обычно линейные выражения) имеют пригодность выше, чем деревья со сложными структурами, которые обычно более перспективны. В результате, простые решения начинают преобладать в популяции, и поиск замедляется. Это связанно с тем, что набор констант во множестве термов фиксирован, и в удачно выращенных структурах численные коэффициенты часто оказываются плохо подобранными. То есть, решение с очень хорошей структурой может иметь ошибку аппроксимации намного больше, чем простая структура, в которой подбор коэффициентов точнее. Обычно метод ГП способен преодолеть данную проблему путем интенсивного применения оператора мутации и за счет появления поддеревьев, содержащих во внешних вершинах только константы. Тем не менее, зачастую алгоритм либо плохо справляется с подбором коэффициентов, либо коэффициенты настраиваются очень долго.

Для улучшения эффективности работы метода ГП предложено представлять вектор независимых входных переменных X = (Х|,Х2,...,ХП), в виде Х = (аи -х, +Ьм,а2>! -х2 +Ь2>1(...,аИ1, ■ хп +ЬП>;) где п - количество переменных, и настраивать коэффициенты 3| и Ь; через определенное количество поколений (К) метода ГП. Для решения получаемой задачи оптимизации коэффициентов модели предлагается использовать генетический алгоритм, т.к. известно, что он является подходящим инструментом поиска глобального оптимума. Данный подход был реализован программно и проверен на множестве тестовых задач. Было установлено, что наиболее эффективным по среднему времени работы алгоритма и количеству прогонов, в которых было получено решение с заданной точностью, является К = 5.

Таким образом, в первой главе разработана, реализована и протестирована эволюционная процедура, позволяющая автоматизировать настройку параметров моделей символьной регрессии.

Вторая глава посвящена обоснованию, разработке и исследованию коэволюционпого алгоритма ГП.

Для повышения эффективности использования ГА в процедуре настройки параметров моделей, получаемых алгоритмом ГП, были внесены следующие модификации:

1. Накопление и использование статистических данных в ходе работы

ГА;

2. Переход коэффициентов лучших решений алгоритма ГП в начальную популяцию ГА;

3. Адаптивный процесс увеличения ресурса ГА.

Показано, что при использовании предложенной модификации в случае появления в популяции удачных структур после подбора численных коэффициентов, алгоритм отдает предпочтение именно этим решениям. В результате при аппроксимации нелинейных зависимостей алгоритм гораздо быстрее переходит от линейных функций к более сложным и, соответственно, перспективным.

Эффективность модифицированного алгоритма проверена на множестве тестовых функций с усреднением по многим прогонам. Обобщенные результаты исследований разработанных алгоритмов представлены в таблице 1,

Таблица 1. Сравнение эффективности алгоритмов

№ Схема N,. % Nb % N3) %

1 ГП 20 40 40

2 ГП + ГА 5 45 50

3 ГП + ГА + Использование статистических данных 5 50 45

4 ГП + ГА + Использование статистических данных + Увеличение ресурса 5 50 45

5 ГП + ГА + Использование статистических данных + Увеличение ресурса + Переход коэффициентов лучших решений 0 45 55

В таблице Ni — количество прогонов, в которых было получено решение с Error > 5%, в процентах от общего количества прогонов; N2 - количество прогонов, в которых было получено решение с 1% < Еггог < 5%; N3 — количество прогонов, в которых было получено решение с Error < 1 %.

Таким образом, использование предложенных модификаций позволяет улучшить процедуру символьной регрессии на основе ГП.

Одним из наиболее существенных недостатков ГП, препятствующих его широкому распространению при решении практических задач, является зависимость его эффективности от выбора настроек. Результаты исследований, проведенных в первой главе, показали, что нельзя однозначно сказать о превосходстве определенного алгоритма ГП, и даже после многократных решений задачи (что само по себе плохо для практики) остается неопределенность выбора настроек ГП. Выбор конкретного алгоритма и настройка его параметров является сам по себе очень сложной задачей, для

решения которой нужна серьезная подготовка в области эволюционного моделирования, которой обычно нет у специалистов прикладных областей.

Для устранения подобной проблемы необходимо разрабатывать процедуры, автоматизирующие выбор настроек ГП в ходе однократного ре-.*шения задачи. В работе предлагается метод, использующий идеи коэволюции, то есть конкуренции частных алгоритмов ГП за ресурс в рамках однократного решения задачи моделирования.

Основная идея коэволюционного алгоритма состоит в следующем: одновременно эволюционируют несколько популяций, каждая из которых решает заданную задачу символьной регрессии и обладает своей стратегией поиска. При этом популяции борются за общий ресурс (количество индивидов, выделяемых для решения задачи), который в течение работы алгоритма перераспределяется в пользу более эффективной из них. Коэво-люционный алгоритм имеет следующую последовательность шагов:

1. Выбор индивидуальных алгоритмов.

2. Инициализация параметров коэволюционного алгоритма.

3. Работа индивидуальных алгоритмов в течение заданного интервала адаптации.

4. Оценка эффективности индивидуальных алгоритмов.

5. Проверка критерия остановки: если данный критерий срабатывает, то выводим лучшее найденное решение и алгоритм прекращает работу.

6. Перераспределение ресурса (на основе оценки, полученной на шаге 4).

7. Переход на шаг 3.

Так как коэволюцнонный алгоритм основывается на конкурирующих стратегиях алгоритмов, то для субпопуляций, реализующих эти стратегии, необходимо ввести функцию пригодности. С помощью этой функции определяется лучшая субпопуляция и ей дается больше возможностей для воспроизводства. Пусть Т — интервал адаптации, Ь1(к)=1, если ¡-я субпопуляция в момент к содержит наилучшего (по всем субпопуляциям) индивида, к=0 означает текущую ситуацию, к™1 - предыдущую и т. д. Тогда качество ¡-й субпопуляции можно вычислить по формуле:

т-1 т к

к„0 К + I

Изменение размеров ресурсов происходит путем сокращения каждой проигравшей популяции па некоторое число индивидов (определенный заранее размер штрафа) и увеличением победившей популяции на число, равное сумме потерь проигравших. Таким образом, общее число индивидов остается неизменным. Сокращение проигравших популяций осуществляется только до тех пор, пока они не достигнут минимального гарантированного размера — "социального минимума"

Исследование эффективности коэволюционного алгоритма ГП было проведено на множестве тестовых функций. Для создания наиболее слож-

них условий для коэволюционного алгоритма в его состав включались индивидуальные алгоритмы, выбранные из списка случайным образом.

В результате исследований показано, что коэволюциощшй алгоритм превосходит все индивидуальные алгоритмы, кроме, быть может, самого лучшего из них (рисунок 2).

Рисунок 2. Пример поведения лучшего Рисунок 3. Пример перераспределения индивида (коэволюциошшВ алгоритм ГП ■ в ходе работы коэволкщнонного

показан сплошной жирной лилией) алгоритма

Происходящий в ходе поиска процесс перераспределения ресурсов между алгоритмами представлен на рисунке 3.

На данном примере видна правильность предположения о том, что нельзя все отнимать у алгоритма (выгодность "социального минимума"), так как проигрывающие на начальных шагах алгоритмы могут в .дальнейшем помочь найти лучшее решение.

Из описания коэволюционного алгоритма вццпо, что на его эффективность могут оказать влияние следующие параметры: величина интервала адаптации, размер штрафа, размер "социального минимума" и количество индивидуальных алгоритмов.

В работе было проведено исследование влияния данных параметров и выработаны рекомендации по их настройке. В ходе исследований было установлено, что использование постоянной величины штрафа является неэффективным. Поэтому предложена следующая формула для расчета штрафа:

I 100 )

где Ъ — количество индивидов, на которое будут штрафоваться проигравшие индивидуальные алгоритмы, БрСА — общее число индивидов, — устанавливаемый пользователем размер штрафа в процентах, N — количество индивидуальных алгоритмов.

Для того чтобы установить характер зависимости эффективности коэволюционного алгоритма от значений его параметров и выработать рекомендации по их настройки были проведены следующие исследования:

а) Исследование эффективности коэволюционного алгоритма в зависимости от величины штрафа и социального минимума. В таблице 2 приведен пример получеш!ых результатов для одной из тестовых функций.

Таблица 2. Результаты исследования зависимости эффективности

Соц. минимум \штраф 2% 4% 6% 8% 10% 12% 14% 16%

2% 15 20 20 5 10 5 20 10

4% 10 15 10 20 10 25 10 5

6% 5 10 25 20 25 20 15 5

8% 15 5 15 15 15 20 5 15

10% 20 25 15 20 45 40 20 15

12% 10 5 20 25 30 25 15 5

14% 15 10 15 10 20 15 15 0

16% 0 5 5 10 15 10 5 30

б) Исследование зависимости эффективности коэволюционного алгоритма от величины интервала адаптации. В таблице 3 приведен пример полученных результатов для одной из тестовых функций.

Таблица 3. Результаты исследования зависимости эффективности

Интервал адаптации N3,% N2,% И,, %

2 15 75 10

3 10 60 30

4 35 55 10

5 45 50 5

6 25 65 10

7 10 85 5

8 15 75 10

9 5 80 15

10 10 75 15

в) Исследование зависимости эффективности коэволюционного алгоритма от количества индивидуальных алгоритмов. В таблице 4 приведен пример полученных результатов для одной из тестовых функций.

Таблица 4. Результаты исследования зависимости эффективности

Количество алгоритмов N3,% N2,% N,,<>/0

2 15 80 5

3 35 50 . 15

4 45 50 ' 5

5 40 50 10

6 35 50 15

7 30 50 20

8 20 60 20

Для остальных тестовых функций получены аналогичные результаты. В ходе исследований эффективности работы коэволюционного алгоритма ГП в зависимости от параметров, входящих в его настройку, было установлено, что:

- коэволюционный алгоритм ГП всегда лучше не только самого худшего из индивидуальных алгоритмов, но и лучше, чем средний алгоритм (по показателям надежности). В некоторых случаях он лучше лучшего из индивидуальных алгоритмов;

- коэволюционный алгоритм ГП позволяет автоматически выбирать лучшую стратегию из имеющихся и включать её в необходимый момент;

- не нужно сильно штрафовать проигравшие алгоритмы (размер штрафа 10-12%), но и давать им большие «социальные гарантии» тоже нельзя (оптимум - 10-12%);

- интервал адаптации необходимо выбирать равным 4-5;

- количество индивидуальных алгоритмов должно быть 4-5;

- при отсутствии уверенности в знаниях о свойствах эволюционных алгоритмов включение в коэволюцию случайно выбранных алгоритмов позволяет получать достаточно хорошие результаты (лучше средних);

- в случае практически полного отсутствия знаний о предпочтительности выбора индивидуальных алгоритмов даже комбинация из практически неработающих алгоритмов (худших по надежности в сравнении с другими алгоритмами) имеет большую надежность, чем надежность каждого из этих алгоритмов по отдельности;

- 75% решений имеют ошибку Error < 1,6%, т.е. коэволюционный алгоритм ГП позволяет получать достаточно хорошие аппроксимации;

- коэволюционный алгоритм ГП превосходит обычный алгоритм ГП по скорости нахождения решения (практически на порядок).

Фрагмент результатов работы коэволюциошюго алгоритма ГП с применением предложенных настроек представлен в таблице 5.

Таблица 5. Результаты работы коэволюционного алгоритма ГП

№ Тестовая функция Точное решение, % E<0,001, % Си N

1 f(x,y)»xJ +у2 100 100 7 10

2 f(x,y) = x2+y* ~cos(x)-cos(y) 75 100 13 Пб

3 FK.m^Rbl^ К 100 100 8 7

4 f(x,y,z) = xI+yI+21 100 100 9 33

5 f(x,y,z) = x3 + X • у+z2 100 100 11 76

б f.l 100 100 11 58

«Точное решение» означает, что алгоритм нашел точную структуру заданной тестовой функции; Е — ошибка аппроксимации; Сп - количество узлов в лучшем решении; N — номер поколения, на котором алгоритм нашел решение с заданной точностью.

Для улучшения эффективности работы коэволюциошюго алгоритма ГП предложено также выполнять настройку параметров получаемых моделей с помощью модифицированного ГА.

Сравнение эффективности коэволюционного алгоритма ГП с адаптивной настройкой параметров моделей с исходным коэволющгонным алгоритмом ГП показал, что показатель N1 снижается до 0 %, показатель N1 увеличивается на 25 %, а показатель N3 увеличивается на 30 %.

Итак, выработанные рекомендации по настройке параметров коэволюционного алгоритма ГП позволяют конечным пользователям, не владеющим аппаратом эволюционного моделирования и оптимизации, применять его при решении сложных задач моделирования, возникающих в реальной практике.

Третья глава посвящена практической реализации разработанных алгоритмов. Сначала приводится описание программных реализаций подходов, а затем апробация разработанного алгоритма моделирования сложных систем на реальной практической задаче.

В ходе диссертационного исследования было разработано четыре программных системы; программная реализация метода ГП; программная реализация метода ГП с настройкой коэффициентов модифицированным генетическим алгоритмом; программная реализация коэволюционного алгоритма ГП, предназначенная для решения сложных задач моделирования с помощью коэволюционного алгоритма, а также для исследования зависимости эффективности данного алгоритма от различных параметров, входящих в его настройку; программная реализация коэволюционного алгоритма ГП с настройкой коэффициентов с помощью МГА, предназначенная для решения сложных задач моделирования и оптимизации (концептуальная схема двух последних программных систем показана на рисунке 4).

Рисунок 4. Схема программной системы

Результатом работы программной системы является математическое выражение в символьной форме вида уг=^х1,х2,...,хп), аппроксими-

рующее зависимость между конечным набором значений независимых переменных и соответствующими значениями зависимых переменных.

Апробация козволюциошюго алгоритма ГП проведена на задачах моделирования:

1. Законов температурного изменения линейиого двупреломления света в кристаллах ИаМпСЬ и ЛЬ^МпСЦ отдельно для температур выше и ниже температуры фазового перехода Тц (рис. 5-8). Полученные результаты позволили выделить вклады в магнитное двупреломление от механизмов различной природы и определить константу обменного взаимодействия между магнитными ионами.

2. Границ магнитного фазового состояния легкоосного Ш^МпС!* и легкоплоскостного ИаМпСЬ аптиферромагнетиков (рис. 9,10). Результаты сравнивались с предсказанными в модели спин-волнового приближения. Получены аналитические уравнения для фазовых границ.

Для решения данных задач использовались следующие параметры ко-эволюционного алгоритма ГП:

- Размер ресурса - 400;

- Начальная глубина деревьев - 3;

- Интервал адаптации - 5;

- Размер штрафа -10%;

- Размер социального минимума - 10%;

Рис. 5. Температурная зависимость Рис. 6, Температурная зависимость про-линейного двупреломления света в иэводной линейного двупреломления Ш^МпСЦ (о и 0). Длина световой волны Ш^МпСЦ (0 и о). Результат работы А=0,63 мкм. алгоритма (-и - - -).

Результат работы алгоритма (—и —)

Аналитические зависимости, полученные с помощью коэволюционного алгоритма ГП:

- аппроксимация температурной зависимости линейного двупреломления Дп Шз2МпС14 выше Тм (рис, 5):

ИТ>-ех[Гт4__И<»<И>0, «ФС-.1636- Т) * 295.. схр(-.Шб- Т) • Т>_*]

" Ч. (10000,- Т + 990477.+ 3102267200: ехр(-.1бЗб-Т) + 164315.- ехр<4 1636- Т) • Т) _)

Значение ошибки: 0,523%.

- аппроксимация температурной зависимости двупреломления Дп Шэ^МпСЦ ниже Тк (рис. 5):

линейного

Р(Т) := сся

!пГ|*.41---я-!-" + (135.87- 20.91-Т)|Т|. . 64'*7.3.

. VI си(™С1п(|т|))) Т-0.822 _

■Значение ошибки: 0,682%.

- аппроксимация температурной производной линейного двупреломления <1Дп/(1Т Ш^МпСЦ ниже Тц (рис. б):

1<Г5}-<Ш5- КГ5- ехр(3.402- .1100-Т) -3.422- 1СГ4- екр<6.8СИ- люо. Т» 2,433- 10'3-Т + 3.422 !(Г4 Т2

Значение ошибки: 5,69%.

- аппроксимация температурной производной линейного двупреломления <1Дп/<1Т ШтгМпСЦ выше Тц (рис. б):

_92160000000.__

(-3904088600: Т + 191353761027+ 27870000,- Г2 27870000,- ехрИ,Э4- Ю'г ■ Т - ,22ш) _

Значение ошибки: 3,566%.

! .-Ка...I

1. I

т.к

Рис. 7. Температурная зависимость линейного двупреломления света в

Рис. 8. Температурная зависимость производной линейного двупреломления

ЫаМпС1з (о и 0). Длина световой волны №МпС1з (о и 0). Результат работы алго-

X *» 632,8 им. Результат работы алгоритма (— и —)

ритма {—и —)

Аналитические зависимости, полученные с коэволюционного алгоритма ГП:

- аппроксимация температурной зависимости двупреломления Дп ЫаМпСЬ выше Ты (рис. 7):

, ) .. . г 631000.Н

Р(Т>:=Ц -II.5129+ Ц -

Значение ошибки: 2,68%.

- аппроксимация температурной зависимости двупреломления Дп №МпС13 ниже Тм (рис. 7):

Р(Т) := 0.06998. Т2 - 0,178- Т - 1.58 Значение ошибки: 2,879%.

помощью

линейного

линейного

- аппроксимация температурной производной линейного двупреломления <ЗДп/с!Т ИаМпСЬ выше Ти (рис. 8):

ГСП :=-17.615+ 1п[(м0- Т3- 100 Т- (447000- 1п(Т> + 24350* Т + 211354^

Значение ошибки: 6,393%.

- аппроксимация температурной производной линейного двупреломления ¿Дп/<1Г КаМпС1з ниже Тн (рис, 8):

„„ 120.Ш- Т2 + 4104.917 ---

20 • "Г + Т

Значешю ошибки: 13,63%.

Рне. 9, Критическое поле Не КаМпОз, Рис. 10 Поле сшш-фяоо перехода, Нбр, полученное оптическими методами: КЬгМпС!«, полученное с помощью ли-

круговое (*), Ы у Сз оси и линейное дву- нейного (о) и кругового (• ) двупрелом-преломления (о), Н ± С}. Результат ра- ления. Результат работы алгоритма (-) боты алгоритма (-)

Зависимость, полученная с помощью коэволюционного алгоритма ГП для ЫаМпСЬ (рис. 9):

(ТО24.82+ !■[ |(1Н1М7№Т- ¡91517107* 1000000, Т3 - 2529000(1 Т3}' ■ 1

[_| (100,-Т-МЗГ

Значение ошибки: 3,546%.

Зависимость, полученная с помощью коэволюционного алгоритма

ГП для КЬзМпСЦ (рис. 10):

Р(а):=2.б- 10"*- а1 + 5,680' 10"1-а + 56_

Значение ошибки: 0,967%.

При моделировании для снижения влияния шума в функции пригодности использовались дополнительные слагаемые регуляризации, зависящие от величин первой и второй производных, оценки которых вычислялись по конечным разностям.

В заключение диссертации приведены основные результаты, полученные в ходе выполнения работы, и сформулированы выводы.

Основные результаты я выводы;

-исследована эффективность метода ГП на представительном множестве тестовых функций;

- разработан и программно реализован модифицированный генетиче--ский алгоритм адаптивной настройки параметров модели и произведена

оценка его эффективности;

-разработана и реализована адаптивная процедура, позволяющая автоматизировать настройку параметров моделей, полученных с помощью метода ГП;

-разработан, программно реализован адаптивный алгоритм, позволяющий автоматизировать выбор наиболее эффективного алгоритма ГП в ходе решения задачи моделирования;

- выработаны рекомендации по настройке параметров коэволюцион-ного алгоритма ГП;

-разработан и программно реализован модифицированный адаптивный поисковый алгоритм с автоматическим выбором наиболее эффективного алгоритма ГП с настройкой параметров модели. Показана его работоспособность;

- проведена апробация разработанного подхода на реальной практической задаче моделирования физических систем.

Таким образом, в диссертации решена задача разработки средств автоматизированного моделирования сложных систем методом генетического программирования, что имеет существенное значение для теории и практики системного анализа и управления сложными системами.

Публикации по теме диссертации:

1*. Жуков В.Г. Коэволюционный алгоритм решения нестационарных задач оптимизации / В.Г. Жуков, М.Н. Жукова // Вестник Сибирского государственного аэрокосмического университета им. ак. М.Ф. Решетнева. — № 1 (8). - 2006. - С. 27-30.

2. ЖуковВХ. Лабораторная установка для исследования работы стандартного генетического алгоритма / Жуков В.Г. // Инновации в науке и образовании. - № б (17). -2006. - С. 28-29.

3. Жуков В.Г. Программная система моделирования сложных систем с помощью коэволюционного алгоритма генетического программирования / В.Г. Жуков, Е.С. Семенкин // Инновации в науке и образовании. - № 7(18), -2006.-С. 29.

4. Жуков В.Г. Программная реализация метода генетического программирования с адаптивной настройкой коэффициентов для решения задачи символьной регрессии / В.Г, Жуков // Инновации в науке и образова-нии.-№ 7(18).-2006.-С. 30.

5. Попов Е.А., Жуков В.Г. База данных для обучения системы предсказания рефрактометрических свойств прозрачных магнетиков // Вестник НИИ СУВПТ (Вып. 13). - Красноярск: НИИ СУБГГГ, 2003,— С. 248-262.

6. Жуков В.Г. Аппроксимация рефрактометрических свойств прозрачных магнетиков коэволюционным алгоритмом генетического программирования / В.Г. Жуков, Е.А. Попов // Вестник университетского комплекса. - Вып. 7 (21). - 2006. -С. 47-56.

7. Жуков В.Г., Попов Е.А. Исследование коэволюционного алгоритма генетического программирования и его применение в задаче моделирования фазовых границ магнитного состояния кристалла / В.Г. Жуков, Е.А. Попов И Вестник университетского комплекса. — Вып. 8 (22). — 2006. — С. 121-130.

8. Жуков ВТ. Исследование эффективности коэволюционного алгоритма генетического программирования // В.Г. Жуков, С.Н. Ефимов, Е.С. Семенкин / "Информационные технологии и математическое моделирование (ИТММ)": Сб. тр. VI Всерос. науч.-практ. конф. — Томск: Изд-во ТГУ, 2006.-С. 71-75.

9. Жуков В.Г. О коэволюционном алгоритме генетического программирования для решения задачи символьной регрессии/ Жуков В.Г.// "Ре-шетневские чтения": Мат. VIII Всерос. науч. конф. с мсждунар. участ.. — Красноярск: СибГАУ, 2006. - С.23-25.

10. Жуков В.Г. О влиянии параметров па эффективность работы коэволюционном алгоритме генетического программирования / Жуков В.Г.// "Решетневские чтения": Мат. VIII Всерос. науч. конф. с междунар, участ.. -Красноярск: СибГАУ, 2005. - С.17-19.

11. Жуков В.Г. Разработка и применение адаптивного штрафа в работе коэволюционного алгоритма генетического программирования / Жуков В.Г. // Сборник трудов 43-й научно-практической конференции молодых ученых. — Красноярск: СибГАУ, 2005.

12. Жуков В.Г. О влиянии параметра рекомбинации на работу генетического алгоритма / Жуков В.ГУ/ "Информационные технологии и математическое моделирование (ИТММ)": Сб. тр. Ш Всерос. науч.-практ. конф. — Томск: Изд-во ТГУ, 2004. - С. 71-73.

13. Жуков В.Г. О влиянии параметра рекомбинации на работу генетического алгоритма / Жуков В.Г.// "Решетневские чтения": Мат. VII Всерос. науч. конф. с междунар. участ. — Красноярск: СибГАУ, 2004. — С. 176-177.

14. Жуков В.Г. LabGenAlg (лабораторная установка для исследования работы стандартного генетического алгоритма). - М.: ВНТИЦ, 2006. № гос. per. 50200601023.

15. Жуков В.Г., Семенкин Е.С. Программная система моделирования сложных систем с помощью коэволюционного алгоритма генетического программирования «Genetic Programming Coevolution v.2.1». -М.: ВНТИЦ, 2006. - № гос. per. 50200601391.

16. Жуков В.Г. Программная реализация метода генетического программирования с адаптивной настройкой коэффициентов для решения задачи символьной регрессии «Genetic Programming with adaptive setting of coefficients v.2.1». -M.: ВНТИЦ, 2006. - № гос. per. 50200601392.

Жуков Валим Геннадьевич

Моделирование сложных систем коэволюционным алгоритмом генетического программирования

Автореферат .

Подписано к печати 27.11.2006 Формат 60x84/16

Уч. изд. л. 1.0 Тираж 100 экз. Заказ №

Отпечатано в отделе копировальной и множительной техники СнбГАУ, 660014, г. Красноярск, пр. им. газ. «Красноярский рабочий», 31

Введение

Оглавление:

Глава I. Исследование эффективности алгоритма решения задачи символьной регрессии с помощью метода генетического программирования.

1.1. Методы решения задач аппроксимации в моделировании сложных систем.

1.2. Метод генетического программирования.

1.3. Исследование эффективности алгоритма генетического программирования.

1.4. Генетический алгоритм.

1.5. Исследование эффективности алгоритма генетического программирования с настройкой коэффициентов генетическим алгоритмом.

Выводы. у

Глава II. Обоснование, разработка и исследование эффективности коэволюционного алгоритма генетического программирования.

2.1. Разработка и исследование эффективности алгоритма генетического программирования с адаптивной настройкой коэффициентов модифицированным генетическим алгоритмом

2.2. Обоснование коэволюционного алгоритма.

2.3. Исследование зависимости свойств коэволюционного алгоритма от выбора его параметров.

2.4. Разработка и исследование эффективности коэволюционного алгоритма генетического программирования с адаптивной настройкой численных коэффициентов модифицированным генетическим алгоритмом.

Выводы.

Глава III. Практическая реализация коэволюционного алгоритма генетического программирования для решения сложных задач моделирования.

3.1. Описание программной реализации метода генетического программирования с адаптивной настройкой коэффициентов для решения задачи символьной регрессии «Genetic Programming with adaptive setting of coefficients v.2.1».

3.2. Описание программной системы моделирования сложных систем с помощью коэволюционного алгоритма генетического программирования «Genetic Programming Coevolution v.2.1». j q

3.3. Исследование некоторых магнитооптических и рефрактометрических свойств прозрачных магнитных кристаллов.

3.4. Построение фазовых границ магнитного состояния кристалла.

Выводы.

Исследование с помощью математических моделей зачастую является единственно возможным способом изучения сложных систем и решения важнейших практических задач управления. Высокие темпы информатизации различных видов деятельности в настоящее время привели к тому, что появилась возможность компьютерного моделирования тех или иных процессов, проектирования сложных систем, изучения их свойств и управления ими в условиях дефицита времени, ограниченности их ресурсов, неполноты информации [1]. При этом для исследования характеристик любой системы математическими методами должна быть выполнена формализация, то есть, построена математическая модель.

Однако на практике сложно зафиксировать свойства функциональной зависимости выходных параметров от входных величин, еще сложнее привести аналитическое описание такой зависимости. Одним из способов решения данной проблемы является применение эволюционных алгоритмов путем решения задачи символьной регрессии методом генетического программирования. Символьная регрессия дает математическое выражение в символьной форме, которое можно подвергнуть содержательному анализу, упростить и далее использовать для моделирования или оптимизации. Эффективность применения алгоритмов генетического программирования определяется тщательной настройкой их параметров, что препятствует их более широкому распространению, т.к. требует от конечных пользователей высокой квалификации и большого опыта в применении эволюционного моделирования, что редко наблюдается на практике. Поэтому необходимо разрабатывать адаптивные самонастраивающиеся алгоритмы генетического программирования для решения задач символьной регрессии. Кроме того, при решении задачи символьной регрессии с помощью метода генетического программирования часто возникает проблема подбора численных коэффициентов модели, что приводит к необходимости решения задачи минимизации функции ошибки аппроксимации, которая является, чаще всего, многоэкстремальной. Эти задачи очень трудно (или невозможно) решить с помощью обычных методов оптимизации, что приводит к необходимости разрабатывать и применять специализированные методы решения сложных оптимизационных задач [75]. К таким методам относятся, в частности, эволюционные и генетические алгоритмы [75, 90, 91]. Все это приводит к необходимости разработки и применения комбинаций алгоритмов генетического программирования (для построения моделей) и генетических алгоритмов (для уточнения параметров модели).

Поэтому разработка методов, позволяющих в рамках единого подхода автоматизировать процесс построения и оптимизации математических моделей сложных систем и процессов, и выработка рекомендаций по правильному использованию алгоритмов в ходе автоматизированного моделирования является актуальной научно-технической задачей [75, 76].

Целью диссертационной работы является совершенствование процесса моделирования сложных систем с помощью эволюционных алгоритмов, направленное на обеспечение возможности адаптивного выбора эффективного алгоритма моделирования в ходе решения задачи.

Поставленная цель предопределила следующую совокупность решаемых задач:

1. Исследовать эффективность метода генетического программирования на представительном множестве тестовых функций.

2. Разработать и реализовать адаптивную процедуру, позволяющую автоматизировать настройку параметров моделей, получаемых с помощью метода генетического программирования.

3. Разработать и программно реализовать модифицированный генетический алгоритм адаптивной настройки параметров модели и оценить его эффективность.

4. Провести сравнительный анализ обычного и модифицированного метода генетического программирования с целью выявления наиболее эффективного направления его совершенствования.

5. Разработать и реализовать алгоритм генетического программирования с адаптивным выбором настроек и оценить его эффективность на множестве тестовых задач.

6. Определить параметры, наиболее существенно влияющие на эффективность разработанного алгоритма генетического программирования, и выработать рекомендации по их настройке.

7. Программно реализовать разработанный самонастраивающийся алгоритм генетического программирования с оптимизацией параметров модели и решить с его помощью практические задачи автоматизированного моделирования сложных систем.

Методы исследования. При выполнении диссертационной работы использовались методы системного анализа, исследования операций, теории оптимизации, теории вероятностей и математической статистики, теории эволюционных алгоритмов, методика создания прикладных интеллектуальных систем.

Научная новизна результатов диссертационной работы состоит в следующем:

1. Разработан новый гибридный алгоритм символьной регрессии, сочетающий метод генетического программирования для выбора структуры модели и модифицированный генетический алгоритм для настройки ее параметров.

2. Впервые разработан коэволюционный алгоритм решения задач символьной регрессии, обладающий свойством адаптации стратегии поиска в ходе решения задачи.

3. Установлено сочетание значений параметров коэволюционного алгоритма генетического программирования, обеспечивающее высокую эффективность решения сложных задач моделирования.

Практическая значимость. На основе предложенного алгоритмического обеспечения разработаны современные программные системы, которые позволяют широкому кругу пользователей в рамках единого подхода решать задачи моделирования сложных систем. Полученные в диссертационной работе рекомендации по настройке параметров адаптивного коэволюционного алгоритма позволяют конечным пользователям, не владеющим аппаратом эволюционных алгоритмов, решать сложные задачи моделирования, возникающие в реальной практике.

Работа выполнена в рамках ФЦНТП «Исследования и разработки по приоритетным направлениям развития науки и техники на 2002-2006 годы» по теме 2006-РИ-16.0/001/076 (государственный контракт № 02.438. 11.7043) и 2006-РИ-19.0/001/377 (государственный контракт № 02.442.11.7337), в рамках НИР 4422 «Разработка и исследование эффективности гибридных методов оптимизации алгоритмически заданных функций дискретных переменных», выполняемой по ведомственной научной программе «Развитие научного потенциала высшей школы», а также по темплану СибГАУ «Бионические методы идентификации и оптимизации сложных систем» (№ Б 1.1.05).

Реализация результатов работы. В ходе работы над диссертацией реализованы три программные разработки, которые прошли экспертизу и зарегистрированы в Отраслевом фонде алгоритмов и программ Государственного координационного центра информационных технологий Федерального агентства образования.

Программные системы используются в качестве лабораторных установок для обучения студентов Сибирского государственного аэрокосмического университета по дисциплинам «Интеллектуальные технологии и принятие решений» и «Интеллектуальный анализ данных», студентов Красноярского государственного университета по дисциплинам «Эволюционные алгоритмы моделирования и оптимизации» и «Интеллектуальные технологии анализа данных».

Разработанные программные системы использованы при решении практических задач аппроксимации рефрактометрических свойств прозрачных магнетиков и моделирования фазовых границ магнитного состояния кристаллов. Результаты решения и программные системы переданы Институту физики СО РАН, что подтверждено актом о передаче и внедрении.

Основные защищаемые положения:

1. Разработанный гибридный алгоритм решения задачи символьной регрессии позволяет эффективно строить адекватные аналитические модели сложных систем с уже подобранными оптимальными параметрами и превосходит стандартный метод генетического программирования по быстродействию и надежности.

2. Коэволюционный алгоритм решения задач символьной регрессии обеспечивает автоматическую настройку стратегии поиска в ходе решения задачи и превосходит по эффективности стандартный и гибридный алгоритмы решения задач символьной регрессии по быстродействию и надежности.

3. Выработанные рекомендации по настройке параметров коэволюционного алгоритма генетического программирования позволяют широкому кругу пользователей, не владеющих аппаратом эволюционного моделирования и оптимизации, успешно применять его при решении практических задач.

Публикации. По теме диссертации опубликовано шестнадцать печатных работ, список которых приведен в конце диссертации [24-39].

Апробация работы. Основные положения и отдельные результаты диссертации докладывались и обсуждались на Всероссийских конференциях "Решетневские чтения" (2004-2006 гг.), Всероссийской научно-практической конференции "Информационные технологии и математическое моделирование (ИТММ)", Томск (2004, 2006). Полученные результаты и диссертационная работа в целом обсуждалась на научных семинарах экспериментальной лаборатории интеллектуальных технологий и адаптации и кафедры САИО в СибГАУ (2004-2006 гг.), на семинарах НИИ СУВПТ (2005-2006 гг.), на научном семинаре кафедры механики и процессов управления Красноярского госуниверситета (2006 г.), на семинаре Сибирского государственного технологического университета (2006г.).

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, списка литературы и приложения.

Выводы

В данной главе описана работа двух программных систем, приведены подробные структуры интерфейса, описаны основные правила действий для использования программ. Раскрыты особенности выбора индивидуальных алгоритмов, тестовых функций, описано каким образом осуществляется визуализация процесса поиска глобального оптимума.

С помощью программной системы были проведены все исследования коэволюционного алгоритма генетического программирования. Апробация коэволюционного алгоритма генетического программирования проведена на задачах моделирования:

1. Законов температурного изменения линейного двупреломления света в кристаллах NaMnCb и Ш^МпСЦ отдельно для температур выше и ниже температуры фазового перехода. Полученные результаты позволили выделить вклады в магнитное двупреломление от механизмов различной природы, определить константу обменного взаимодействия между магнитными ионами.

2. Границ магнитного фазового состояния легкоосного Ш^МпСЦ и легкоплоскостного NaMnCb антиферромагнетиков. Результаты сравнивались с предсказанными в модели спин-волнового приближения. Получены аналитические уравнения для фазовых границ.

Разработанная на основе коэволюционного алгоритма современная программная система позволяет решать как тестовые, так и практические задачи, связанные с моделированием (аппроксимацией) и параметрической оптимизацией сложных систем. Программная система позволяет повысить эффективность исследования реальных и проектируемых систем управления за счет возможности быстрой настройки их параметров, которая осуществляется путем оптимизации их значений.

Заключение

В ходе выполнения диссертационной работы получены следующие результаты:

Исследована эффективность алгоритма генетического программирования на представительном множестве тестовых функций.

Разработана и реализована адаптивная процедура, позволяющая автоматизировать настройку параметров моделей, полученных с помощью алгоритма генетического программирования.

Проведен сравнительный анализ алгоритма генетического программирования и алгоритма генетического программирования с адаптивной настройкой параметров модели с помощью генетического алгоритма.

Разработан и программно реализован модифицированный генетический алгоритм адаптивной настройки параметров модели и оценена его эффективность.

Разработан, программно реализован и оценена эффективность коэволюционного алгоритма генетического программирования, позволяющего автоматизировать выбор наиболее эффективного алгоритма генетического программирования в ходе решения задачи моделирования.

Установлены параметры, существенно влияющие на эффективность коэволюционного алгоритма генетического программирования, и выработаны рекомендации по их настройке.

Разработан и программно реализован коэволюционный алгоритм генетического программирования с адаптивной настройкой параметров модели.

Предложенные алгоритмы моделирования и оптимизации использовались при исследовании некоторых магнитооптических, рефрактометрических свойств прозрачных магнитных кристаллов.

Таким образом, в диссертации разработана эффективная процедура, позволяющая в значительной степени облегчить и упростить этапы моделирования и параметрической оптимизации сложных систем, что имеет существенное значение для теории и практики системного анализа.

1. Абдеев, Р.Ф. Философия информационной цивилизации / Р.Ф. Абдеев. М.: ВЛАДОС, 1994.

2. Айвазян, С.А. Прикладная статистика: Исследование зависимостей / С.А. Айвазян, И.С. Енюков, Л.Д. Мешалкин. М.: Финансы и статистика, 1985. - 487 с.

3. Бард, И. Нелинейное оценивание параметров / Д. Бард. М.: Финансы и статистика, 1979. - 349 с.

4. Батищев, Д.И. Генетические алгоритмы решения экстремальных задач / Д.И. Батищев; под ред. Я.Е. Львовича. Учеб. пособие. Воронеж, 1995.

5. Батищев, Д.И. Глобальная оптимизация с помощью эволюционно генетических алгоритмов / Д.И. Батищев, Л.Н. Скидкина, Н.В. Трапезникова. - Мужвуз. сборник, ВГТУ, Воронеж, 1994.

6. Батищев, Д.И. Оптимизация многоэкстремальных функций с помощью генетических алгоритмов / Д.И. Батищев, С.А. Исаев. -электронный ресурс. URL: http://saisa.chat.ru.

7. Березин, И.С. Методы вычислений. Т. 1 / И.С. Березин, Н.П. Жидков. М.: Наука, 1966. - 632 с.

8. Букатова, И.Л. Современные информационные технологии управления / И.Л. Букатова, В.В. Макрусев. М.: РИО РТА, 2003.

9. Букатова, И.Л. Эволюционное моделирование: идеи, основы теории, приложения / И.Л. Букатова. Издательство - Знание, 1981.

10. Вазан, М. Стохастическая аппроксимация / М. Вазан. М.: Мир, 1972.-295 с.

11. Валеев, С.Г. Регрессионное моделирование при обработке наблюдений / С.Г. Валеев. М.: Наука, 1991. - 269 с.

12. Варга, Р.С. Функциональный анализ и теория аппроксимации в численном анализе / Р.С. Варга. М.: Мир, 1974. - 126 с.

13. Вязовкин, B.C. Энциклопедия современной эзотерики / B.C. Вязовкин. http:// ariom.ru.

14. Гмурман, В.Е. Теория вероятностей и математическая статистика / В.Е. Гмурман. Учеб. пособие. - М.: Высш. шк., 2000, - 479 с.

15. Горбань, А.Н. Обучение нейронных сетей / А.Н. Горбань. М.: Параграф, 1990.-159 с.

16. Гребенников, А.И. Метод сплайнов и решение некорректных задач теории приближений / А.И. Гребенников. М.: МГУ, 1983. - 208 с.

17. Демиденко, Е.З. Линейная и нелинейная регрессии / Е.З. Демиденко. М.: Финансы и статистика, 1981. - 302 с.

18. Демиденко, Е.З. Оптимизация и регрессия / Е.З. Демиденко. М.: Наука, 1989.-292 с.

19. Демьянов, В.Ф. Введение в минимакс / В.Ф. Демьянов, В.Н. Малоземов. М.: Наука, 1972. - 368 с.

20. Дрейпер, Н. Прикладной регрессионный анализ / Н. Дрейпер, Г. Смит. -М.: Финансы и статистика, т. 1,1986; т. 2,1987.

21. Емельянова, М.Н. Коэволюционный алгоритм решения сложных задач оптимизации / М.Н. Емельянова // Сборник трудов VIII Международной научно-практической конференции "Системный анализ в проектировании и управлении". Санкт-Петербург: СПГПУ, 2004. - С. 4851.

22. Ерёменко, В.В. Магнитооптика и спектроскопия антиферромагнетиков / В.В. Ерёменко, Н.Ф. Харченко, Ю.Г. Литвиненко, В.М. Науменко. Киев: Наук, думка, 1989. - 256 с.

23. Жуков, В.Г. Аппроксимация рефрактометрических свойств прозрачных магнетиков коэволюционным алгоритмом генетического программирования / В.Г. Жуков, Е.А. Попов // Вестник университетского комплекса. Вып. 7 (21). - 2006. - С. 47-56.

24. Жуков, В.Г. База данных для обучения системы предсказания рефрактометрических свойств прозрачных магнетиков / В.Г. Жуков, Е.А. Попов // Вестник НИИ СУВПТ (Вып. 13). Красноярск: НИИ СУВПТ, 2003.—С. 248-262.

25. Жуков, В.Г. Коэволюционный алгоритм решения нестационарных задач оптимизации / В.Г. Жуков, М.Н. Жукова // Вестник Сибирского государственного аэрокосмического университета им. ак. М.Ф. Решетнева. № 1 (8). - 2006. - С. 27-30.

26. Жуков, В.Г. Лабораторная установка для исследования работы стандартного генетического алгоритма / В.Г. Жуков // Инновации в науке и образовании. № 6(17).- 2006. - С. 28-29.

27. Жуков, В.Г. О коэволюционном алгоритме генетического программирования для решения задачи символьной регрессии / В.Г. Жуков // "Решетневские чтения": Мат. VIII Всерос. науч. конф. с междунар. участ. -Красноярск: СибГАУ, 2006. С.23-25.

28. Жуков, В.Г. О влиянии параметров на эффективность работы коэволюционного алгоритма генетического программирования / В.Г. Жуков"Решетневские чтения": Мат. VIII Всерос. науч. конф. с междунар. участ. -Красноярск: СибГАУ, 2005. С.17-19.

29. Жуков, В.Г. О влиянии параметра рекомбинации на работу генетического алгоритма / В.Г. Жуков // "Информационные технологии и математическое моделирование (ИТММ)": Сб. тр. III Всерос. науч.-практ. конф. Томск: Изд-во ТГУ, 2004. - С. 71-73

30. Жуков, В.Г. О влиянии параметра селекции на работу генетического алгоритма / В.Г. Жуков // "Решетневские чтения": Мат. VII Всерос. науч. конф. с междунар. участ. Красноярск: СибГАУ, 2004. - С. 176-177.

31. Жуков, В.Г. Программная система моделирования сложных систем с помощью коэволюционного алгоритма генетического программирования / В.Г. Жуков, Е.С. Семенкин // Инновации в науке и образовании. № 7(18). - 2006. - С. 29.

32. Жуков, В.Г. Программная реализация метода генетического программирования с адаптивной настройкой коэффициентов для решения задачи символьной регрессии / В.Г. Жуков // Инновации в науке и образовании. № 7(18). - 2006. - С. 30.

33. Жуков, В.Г. Разработка и применение адаптивного штрафа в работе коэволюционного алгоритма генетического программирования / В.Г. Жуков // Сборник трудов 43-й научно-практической конференции молодых ученых. Красноярск: СибГАУ, 2005.

34. Жуков, В.Г. Программная система моделирования сложных систем с помощью коэволюционного алгоритма генетического программирования «Genetic Programming Coevolution v.2.1» / В.Г. Жуков, Е.С. Семенкин. -М.: ВНТИЦ, 2006. № гос. per. 50200601391.

35. Жуков, В.Г. LabGenAlg (лабораторная установка для исследования работы стандартного генетического алгоритма) / В.Г. Жуков. -М.: ВНТИЦ, 2006. № гос. per. 50200601023.

36. Жукова, М.Н. Коэволюционный алгоритм решения сложных задач оптимизации : дис. канд. тех. наук: 05.13.01: защищена 16.12.04 / Жукова Марина Николаевна. Красноярск, 2004. - Библиогр.: с. 106-114.

37. Завьялов, Ю.С. Методы сплайн-функций / Ю.С. Завьялов, Б.И. Квасов, B.JI. Мирошниченко. М.: Наука, 1980. - 352 с.

38. Заенцев, И.В. Нейронные сети: основные модели / И.В. Заенцев; Учеб. пособие к курсу «Нейронные сети». ВГУ, Воронеж, 1999.

39. Игнатов, Н.И. Натуральные сплайны многих переменных / Н.И. Игнатов, А.Б. Певный. Ленинград: Наука, 1991. - 127 с.

40. Кендалл, М.Дж. Статистические выводы и связи / М.Дж. Кендалл, А. Стюарт. М.: Наука, 1973. - 900 с.

41. Корнейчук, Н.П. Аппроксимация с ограничениями / Н.П. Корнейчук, А.А. Лигун, В.Т. Доронин. Киев:Наукова думка, 1982. - 250 с.

42. Крылов, В.И. Начала теории вычислительных методов. Интерполирование и интегрирование / В.И. Крылов, В.В. Бобков, П.И. Монастырный. Минск: Наука и техника, 1983. - 287 с.

43. Ландау, Л.Д. Электродинамика сплошных сред / Л.Д. Ландау, Е.М. Лифшиц. М.: Наука, - 1982. - 624 с.

44. Лебедев, В.А. Метод обобщенного адаптивного поиска для синтеза систем управления сложными объектами / Лебедев В.А., Е.С. Семенкин. М.: МАКС Пресс, 2002. - 320 с.

45. Линник, Ю.В. Метод наименьших квадратов и основы теории обработки наблюдений / Ю.В. Линник. М.: Физматгиз, 1962. - 349 с.

46. Липаев, В.В. Управление разработкой программных средств: Методы, стандарты, технология / В.В. Липаев. М.: Финансы и статистика, 1993.- 160 с.

47. Лоран, П.-Ж. Аппроксимация и оптимизация / П.-Ж. Лоран. М.: Мир, 1975.-496 с.

48. Лоусон, Ч. Численное решение задач метода наименьших квадратов / Ч. Лоусон, Р. Хентон. М.: Наука, 1986. - 230 с.

49. Малоземов, В.М. Полиномиальные сплайны / В.М. Малоземов, А.Б. Певный. Ленинград: ЛГУ, 1986. - 120 с.

50. Марчук, Г.И. Методы вычислительной математики / Г.И. Марчук. М.: Наука, 1989. - 608 с.

51. Математика и САПР: В 2-х кн. Кн. 1. М.: Мир, 1988. - 204 с.

52. Медведев, А.В. Непараметрические системы адаптации / А.В. Медведев. Новосибирск : Наука, 1983. - 174 с.

53. Мкртчян, С.О. Нейроны и нейронные сети (Введение в теорию формальных нейронов и нейронных сетей) / С.О. Мкртчян. М.: Энергия, 1971.-232 с.

54. Невельсон, М.Б. Стохастическая аппроксимация и рекуррентное оценивание / М.Б. Невельсон, Р.З. Хасьминский. М.: Наука, 1972. - 304 с.

55. Нейрокомпьютер как основа мыслящих ЭВМ. М.: Наука, 1993.-237 с.

56. Нейрокомпьютеры и интеллектуальные роботы / Под ред. Н.М. Амосова. Киев: Наукова думка, 1991. - 271 с.

57. Никифоров, А.Ф. Классические ортогональные полиномы дискретной переменной / А.Ф. Никифоров, С.К. Суслов, В.Б. Уваров. М.: Наука, 1985.-215 с.

58. Никольский, С.М. Приближение функций многих переменных и теоремы вложения / С.М. Никольский. М.: Наука, 1977. - 456 с.

59. Носач, В.В. Решение задач аппроксимации с помощью персональных компьютеров / В.В. Носач. М.: МИКАП, 1994. - 382 с.

60. Орлов, С.А. Технологии разработки программного обеспечения: Учебник / С.А. Орлов.- СПб.: Питер, 2002 464 с.

61. Оунэнс, А. Искусственный интеллект и эволюционное моделирование / JI. Фогель, А. Оунэнс, М. Уолш. Пер с англ. Зайченко Ю. П. - Под ред. Ивахненко А. Г. - М.:Мир, 1969.

62. Попов, Б.А. Вычисление функций на ЭВМ / Б.А. Попов, Г.С. Теслер. Киев: Наукова думка, 1984. - 600 с.

63. Попов, Б.А. Приближение функций для технических приложений ЭВМ / Б.А. Попов, Г.С. Теслер. Киев: Наукова думка, 1980. - 352 с.

64. Попов, Е.А. Котлярский М.М. Двупреломление антиферромагнитного Rb2MnCl4 / Е.А. Попов. ФТТ. - 1980. - Т.20. - С.241-244.

65. Попов, Е.А. Тонкая структура спектра поглощения света антиферромагнитного NaMnC13 / Е.А. Попов // Изв. вузов. Физика 2004. -№10.-С. 23-28.

66. Растригин, JT.A. Адаптация сложных систем / JI.A. Растригин. -М.: Наука, 1980.

67. Ремез, Е.Я. Основы численных методов чебышевского приближения / Е.Я. Ремез. Киев: Наукова думка, 1969. - 623 с.

68. Рубан, А.И. Методы анализа данных / А.И. Рубан; Учеб. пособие: В2 ч. Ч. 1; КГТУ. Красноярск, 1994. 220 с.

69. Стариков, А. Генетические алгоритмы математический аппарат электронный ресурс.: BaseGroup Labs. URL: http://www.basegroup.ru

70. Себер, Дж. Линейный регрессионный анализ / Дж. Себер. М.: Мир, 1980.-456 с.

71. Семенкин, Е.С. Адаптивные поисковые методы оптимизации сложных систем / С.П. Коробейников, Е.С. Семенкин, О.Э. Семенкина. -Красноярск: СИБУП, 1997.-355 с.

72. Семенкин, Е.С. Модели и методы оптимизации систем управления сложными объектами / Е.С. Семенкин, В.А. Терсков. -Красноярск: СЮИ МВД РФ, 2000. 211 с.

73. Сопов, Е.А. Эволюционные алгоритмы моделирования и оптимизации сложных систем : дис. канд. тех. наук: 05.13.01: защищена 16.12.04 / Сопов Евгений Александрович. Красноярск, 2004. - Библиогр.: с. 111-118.

74. Стечкин, С.Б. Сплайны в вычислительной математике / С.Б. Стечкин, Ю.Н. Субботин. М.: Наука, 1976. - 248 с.

75. Уоссермен, Ф. Нейрокомпьютерная техника: теория и практика / Ф. Уоссермен. М.:Мир, 1992.

76. Фокс, Дж. Программное обеспечение и его разработка: Пер. с англ. / Дж. Фокс. М.: Мир, 1985. - 368 с.

77. Форсайт, Дж. Машинные методы математических вычислений / Дж. Форсайт, М. Малькольм, К. Моулер. М.: Мир, 1980. - 280 с.

78. Хемминг, Р.В. Численные методы / Р. В. Хемминг. М.: Наука, 1972.-400 с.

79. Хэзфилд, Р. Искусство программирования на С. Фундаментальные алгоритмы, структуры данных и примеры приложений: Энциклопедия программиста: Пер. с англ. / Р. Хэзфилд, JI. Кирби, Д. Корбит и др. К.: Диасофт, 2001.

80. Цыпкин, Я.З. Информационная теория идентификации / Я.З. Цыпкин. М.: Наука. Физматлит, 1995. - 336 с.

81. Шилдт, Г. Полный справочник по С: 4-е издание: Пер. с англ. / Г. Шилдт. М.: Издательский дом "Вильяме", 2002. - 704 с.

82. Banzhaf, W. The Effect of Extensive Use of the Mutation Operator on Generalization in Genetic Programming / W. Banzhaf, F. D.Francone, P . Nordin. Department of Computer Science, Dortmund University, Germany.

83. Dahmen, W. Recent progress in multivariate splines, Approximations theory / W. Dahmen, C. A.Micchelli. New York, 1983.

84. Freeman, J. Neural Networks: Algorithms, Applications, and Programming Techniques / J. Freeman, D. Skapura. Houston. University of Houston at Clear Lake. Addison-Wesley Publishing Company. - 1991.

85. Goldberg, D.E. Genetic Algorithms in Search, Optimization, and Machine Learning / D.E. Goldberg. Reading, Massachusetts: Addison-Wesley, 1989.

86. Holland, J.H. Adaptation in Natural and Artificial Systems / J.H. Holland. Cambridge, MA: MIT Press, 1992 (2nd edition).

87. Holland, J.H. Adaptation in natural and artificial systems / J.H. Holland. Ann Arbor: University of Michigan Press, 1975.

88. Hornik, K. et al. Multilayer feedforward networks are universal approximators // IEEE Transactoins Neural Networks, 2(5), 1989. P. 359-366.

89. Hui, C.K. On spaces of piecewise polynomials with boundary conditions, Lect / C.K. Hui, U. Schumaker, J.D. Wang. Notes Maths., Springer Verlag, 1982.

90. Koza, John R. Genetic programming tutorial / John R. Koza. -электронный ресурс. URL: http://www.genetic-programming.com

91. Koza, John R. Hierarchical genetic algorithms operating on populations of computer programs / John R. Koza. Proceedings of the 11th International Joint Conference on Artificial Intelligence. San Mateo: Morgan Kaufman, 1989.

92. Koza, John R. Genetic Programming: On Programming Computer by Means of Natural Selection and Genetics / John R. Koza. Cambridge, MA: The MIT Press, 1992.

93. Koza, John R. Genetic Programming II: Automatic Discovery of Reusable Programs / John R. Koza. Cambridge, MA: The MIT Press, 1994.

94. Koza, John R. The Genetic Programming Paradigm: Genetically Breeding Populations of Computer Programs to Solve Problems Genetics / John R. Koza. Cambridge, MA: MIT Press, 1992.

95. Poggio, T. Networks for Approximation and Learning / T. Poggio, F. Girosi //Proc. IEEE, 1990, 78(9).-P. 1481-1497.

96. Poli Riccardo Exact Schema Theory for Genetic Programming and Variable-Length Genetic Algorithms with One-Point Crossover / Poli Riccardo. -Genetic Programming and Evolvable Machines, 2, 2001.

97. Popov E.A., Kotlyarskii M.M. Magnetic phase diagram of NaMnCb / E.A. Popov, M.M. Kotlyarskii //Phys. Stat. Sol.(b) 1982/ - V.l 11. -P.K13-K19.

98. Schwefel, H.-P. Parallel Problem Solving from Nature Proc / H.-P. Schwefel, R. Maenner (Eds.). - 1st Workshop PPSN, Berlin: Springer.

99. Spears, W.M. The Role of Mutation and Recombination in Evolutionary Algorithms / W.M. Spears. PhD dissertation, George Mason University, Virginia, USA, 1998.