Разработка и применение генетических алгоритмов для анализа поведения сложных динамических систем тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Малютина, Элина Эдуардовна

• Малютина, Элина Эдуардовна
• кандидат физико-математических наук
• 2001

Оглавление диссертации кандидат физико-математических наук Малютина, Элина Эдуардовна

ВВЕДЕНИЕ.

ГЛАВА 1. ВЫБОР НАИБОЛЕЕ ВАЖНЫХ ПАРАМЕТРОВ В ЗАДАЧЕ КЛАССИФИКАЦИИ ДАННЫХ НА ОСНОВЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА.

§1.1 Постановка задачи.

§1.2 Структура генетического алгоритма для задачи классификации данных

§1.3 Применение генетических алгоритмов для выбора признаков по методу проекций на подпространство.

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

§1.5 Результаты анализа экспериментальных данных. п. 1.5.1 Выбор наиболее важных параметров, характеризующих появление неустойчивости срыва плазменного разряда. п. 1.5.2 Оценка трудоемкости алгоритма. п. 1.5.3 Применение генетического алгоритма для аппроксимации границ областей неустойчивости в пространстве параметров плазмы.

Выводы.

ГЛАВА 2. ПРИМЕНЕНИЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА ДЛЯ КЛАСТЕРИЗАЦИИ ДАННЫХ.

§2.1 Структура генетического алгоритма, основанного на принципах самоорганизации.

§2.2 Сравнение алгоритма GA1 со стандартным генетическим алгоритмом и алгоритмом, основанным на принципе детерминированного сгущения.

§2.3 Анализ алгоритмов GA1 и GA2.

§2.4 Влияние управляющих параметров генетического алгоритма на формирование кластеров.

§2.5 сравнение генетического алгоритма и метода forel для задачи нахождения центроидов кластеров. выводы.

ГЛАВА 3. ПРИМЕНЕНИЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА ДЛЯ ПОИСКА ОПТИМАЛЬНОГО УПРАВЛЕНИЯ ДИНАМИЧЕСКОЙ СИСТЕМОЙ.

§3.1 Постановка задачи.

§3.2 Структура генетического алгоритма, используемого для поиска управления.

§3.3 Анализ степени разнообразия популяции.

§3.4 Результаты численного эксперимента.' п. 3.4.1 Численное исследование зависимости степени разнообразия популяции от параметров генетического алгоритма. п. 3.4.2 Численное исследование зависимости точности управления динамической системой от параметров генетического алгоритма. п. 3.4.3 Сравнение генетических алгоритмов для оптимизации нестационарных функционалов. п. 3.4.4 Сравнение времени счета для поиска локально-оптимального управления с помощью генетического алгоритма и метода квазилокальных вариаций. выводы.v.

ГЛАВА 4. ПОСТРОЕНИЕ АДАПТИВНЫХ СЕТОК С ИСПОЛЬЗОВАНИЕМ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ.

§4.1 Постановка задачи.

§4.2 Схема генетического алгоритма для построения расчетной сетки. п. 4.2.1 Процедура генерации сетки в одномерном пространстве. п. 4.2.2 Процедура генерации сетки в многомерном пространстве.

§4.3 Результаты численного эксперимента. п. 4.3. J Построение адаптивной сетки в одномерном пространстве. п. 4:3.2 Построение адаптивной сетки в многомерном пространстве.

Выводы.

Введение диссертации (часть автореферата) на тему «Разработка и применение генетических алгоритмов для анализа поведения сложных динамических систем»

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

В настоящее время для решения многих практических задач широко применяются методы эволюционных вычислений и генетические алгоритмы, являющиеся стохастическими методами оптимизации, основанными на принципах моделирования биологической эволюции [1-3]. Развитие генетических алгоритмов началось с работ Дж. Холланда [4] и ряда других авторов, обобщивших предшествовавшие подходы к созданию алгоритмов на эволюционной основе. В настоящее время разработка и применение генетических алгоритмов является интенсивно развивающимся направлением. Благодаря универсальности вычислительной схемы, возможностям параллельной реализации, устойчивости к шуму, генетические алгоритмы находят успешное практическое применение при решении многих сложных нелинейных многомерных задач оптимизации. В отличие от традиционных методов многопараметрической оптимизации, многие из которых часто характеризуются резким ростом вычислительных затрат при увеличении числа варьируемых параметров, генетические алгоритмы хорошо зарекомендовали себя на задачах большой размерности. В настоящее время они широко используются для решения большого круга практических задач [5], и область их применения постоянно расширяется. Генетические алгоритмы находят успешное применение при решении задач прогнозирования [6-8], управления [9-12], проектирования сложных систем [13] и др. 5

Генетический алгоритм является стохастическим методом оптимизации для задач вида fix) -» max, хеХ, (0.1) где f(x) - заданный функционал, XczR" - множество допустимых решений. Генетический алгоритм представляет собой итерационный процесс, который на каждой итерации определяет популяцию особей (g/, .g/Д t = ОД,. постоянного размера N. Особь представляет собой кодировку некоторого допустимого решения задачи из X. Решения задачи в генетическом алгоритме кодируются в виде строк фиксированной длины /, поэтому каждая особь g, = (go, gi2, ., gu), i = 1,.,jV является строкой, элементы которой принадлежат заданному конечному алфавиту (чаще всего используется алфавит {0,1}). Функция кодировки Г: {0,1 }1->Х переводит каждую строку g в элемент пространства X. На каждой итерации t, называемой поколением, оценивается мера "качества" каждой особи J[r(g/)) (так называемая функция качества). Таким образом, максимизируемая функция есть функция качества особи. Для простоты изложения суперпозицию функций/и Г в дальнейшем будем обозначать через /

Построение новых особей, которые станут членами следующей популяции, начинается с процедуры отбора. Оператор отбора выбирает пару родительских особей из Р\ при этом предпочтение отдается особям, имеющим наибольшее значение функции качества^). В стандартном генетическом алгоритме используется оператор пропорционального отбора, при котором вероятность отбора каждой особи пропорциональна ее функции качества и равна (0-2) Z/СЙ)

7=1

После процедуры отбора особи подвергаются преобразованиям с помощью операторов скрещивания и мутации. Скрещивание применяется к выбранным особям с фиксированной вероятностью рс. Его действие заключается в том, что часть элементов в двух отобранных строках меняется местами. Например, при действии оператора одноточечного скрещивания со входными строками gj- (gn,. ,gu), g2={g2i,-,g2i) сначала выбирается позиция строки q с равномерным распределением от 1 до /- 1, после которой элементы строк меняются местами. В результате образуются две новые строки gl и g2:

Si = (8l,l>--~> 8l,q> 82,q+l>" &2,l)

82 = (g2,1''''' 82,q' '""'' ) •

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

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

Справедлива следующая теорема о сходимости генетического алгоритма [14, 15]:

Теорема 0.1. Пусть /1Х = max{f(gj) | / = 1 ,.,N,t = 0,.,/} максимальное значение качества особей, достигаемое к шагу t, / -значение глобального оптимума функции Дх), ирт> 0.

Тогда: = ! limiU t 00 max

0.3) то есть вероятность нахождения генетическим алгоритмом глобального оптимума функции Дх) стремится к единице при t 00. 7

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

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

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

3. Генетические алгоритмы являются методами нулевого порядка, стратегия поиска в которых построена только на вычислении значений критерия оптимальности и не требует знания дополнительной информации о производных, константе Липшица, что характерно для градиентных и квази-ньютоновских методов. Обычно генетические алгоритмы применяются для приближенного решения задач оптимизации с большой размерностью, для которых не известно точных алгоритмов приемлемой трудоемкости. Большой интерес к генетическим алгоритмам объясняется тем что, как показывает практика, благодаря своим положительным свойствам, генетические алгоритмы часто превосходят другие стохастические и детерминированные эвристические методы и позволяют найти близкие к оптимальным решения трудных задач поиска за существенно меньшее время [1, 2, 9,16].

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

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

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

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

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

Выбор оптимального подмножества признаков для классификации данных является важной задачей, поскольку удачный выбор признаков во многом определяет успешность распознавания данных [17-19]. Необходимость выбора небольшого числа признаков обычно связана с требованием снижения времени и стоимости работы системы при сохранении приемлемой точности классификации данных. Известно, что процедура выбора признаков в ряде случаев позволяет не только уменьшать объемы обрабатываемых данных, но и приводит к повышению точности классификации [20, 21], так как весьма часто ряд признаков, общих для всех рассматриваемых классов объектов, не несет полезной информации с точки зрения распознавания данных [18]. Таким образом, разработка эффективных методов выбора признаков, обеспечивающих необходимое качество классификации, представляет одну из наиболее важных и наиболее трудных задач построения распознающих систем.

Традиционно для выбора признаков используются метод ветвей и границ (и его модификации) и различные разновидности методов последовательного поиска: прямой последовательный поиск (Sequential Forward Selection), обратный последовательный поиск {Sequential Backward Selection), (/, г)-поиск [22]. Применение метода ветвей и границ требует, чтобы рассматриваемая задача удовлетворяла свойству

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

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

В последнее время возникает большой интерес к возможности применения стохастических методов оптимизации и, в частности, генетических алгоритмов к задаче выбора признаков. Впервые применение генетических алгоритмов для выбора признаков было предложено в [24]. Задача состояла в уменьшении размерности пространства признаков при сохранении высокой точности классификации данных. Был предложен следующий способ представления решения задачи: каждая особь представляла собой битовую строку, в которой 'Г соответствовала наличию, а '0' -отсутствию признака в наборе. Функцией качества строки являлась точность классификации данных, полученная на наборе признаков, определяемых данной строкой. Впоследствии эта модель была принята и

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

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

Это способствовало увеличению интереса к использованию генетических алгоритмов для выбора признаков. Однако большинство исследований, проводимых в настоящее время по применению генетических алгоритмов для выбора признаков, основываются на небольшом числе обучающих наборов [25-27], что уменьшает надежность эксперимента. Часто рассматриваются упрощенные задачи, удовлетворяющие условию монотонности или имеющие попарно независимые признаки [24,28-30]. В диссертации на основе генетических алгоритмов проводится анализ реальной базы данных, полученной в результате экспериментов на токамаке.

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

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

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

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

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

В настоящее время при создании интеллектуальных систем управления сложными динамическими объектами начинают активно использоваться генетические алгоритмы [9,38,39]. В основном они применяются для решения оптимизационных задач, возникающих при

13 проектировании различных классов интеллектуальных систем. Так, например, генетические алгоритмы используются для определения формы функций принадлежности нечетких регуляторов, обеспечивающих заданное качество процессов управления [40, 41], для выбора топологий, архитектуры и оптимального алгоритма обучения нейронной сети [42,43], в задачах построения правил вывода в самонастраивающихся экспертных системах управления объектами [44] и т.д. Среди других практических применений генетических алгоритмов в задачах управления можно отметить такие задачи, как: синтез оптимальных алгоритмов управления многозвенными роботами манипуляторами [11], оптимальное управление стыковкой космических аппаратов [45], планирование маршрутов движения транспортных средств в условиях препятствий [10], построение бесконфликтных маршрутов самолетов [46], идентификация сложных динамических объектов с непрерывным и дискретным временем [47-49] и др.

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

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

Стандартный генетический алгоритм, использующийся для оптимизации стационарных функций, не может быть непосредственно применен к данному классу задач. Это связано с тем, что в генетическом алгоритме в течение начальных поколений может происходить быстрая потеря разнообразия популяции, которая необходима для адаптации алгоритма к изменениям целевой функции. Для решения этой проблемы применяются специальные приемы поддержания разнообразия популяции. Разработан ряд методов [50, 51], которые можно разделить на три основных класса: алгоритмы, постоянно поддерживающие разнообразие в популяции, алгоритмы, использующие процедуры адаптации, и алгоритмы, обладающие дополнительным "генетическим материалом".

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

1.1 алгоритмы, основанные на методе "случайных мигрантов" {random immigrants) [52,53]. В этом методе часть каждой популяции замещается новыми особями, сгенерированными случайным образом.

1.2 алгоритмы, использующие аналогии из термодинамики [54,55]. Основная идея, лежащая в основе "термодинамического" генетического алгоритма (ТДГА) [54], состоит в явном управлении разнообразием популяции путем управления так называемой "свободной энергией" F. Для задачи минимизации она вычисляется по формуле F = (Е)-ТН, где (Е) - средняя энергия" системы, Н - мера разнообразия популяции (энтропия),

Т - температура (проблема выбора параметра Т для динамических сред рассматривается в [55]). На первом шаге выполнения алгоритма к N особям популяции применяется оператор скрещивания. Затем к 2N "родителям" и "потомкам" применяется оператор мутации. При этом лучшая строка предыдущей популяции передается в новую популяцию без изменения. Далее из полученного множества последовательно выбираются особи для формирования новой популяции. При этом на каждом шаге вычисляется значение энергии F в предположении, что особь i (i = 0,.2N+1) станет членом новой популяции. Особь, минимизирующая F, становится членом новой популяции, и процесс выбора следующего члена популяции повторяется снова до тех пор, пока не будет сформирована популяция, состоящая из N членов.

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

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

2.1 метод "адаптивной мутации" (adaptive hypermutation) [57], позволяет резко увеличить уровень мутации в том случае, когда наблюдается ухудшение качества работы алгоритма.

2.2 метод "варьируемого локального поиска" {variable local search) [58], увеличивает уровень мутации после того, как зафиксировано уменьшение среднего значения функции качества.

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

2.3 методы адаптации уровня мутации и вероятности скрещивания, которые регулируются самим алгоритмом в процессе его выполнения [59, 60].

3. Алгоритмы третьего класса основаны на использовании дополнительных структур "памяти" (дополнительных "генов" или "хромосом"). Эти методы позволяют сохранять лучшие решения, полученные в прошлом, и при необходимости использовать их в будущем.

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

3.2 В [63] предложен метод сохранения лучших особей для использования их при создании новой популяции после того, как зафиксировано изменение среды. Предполагается, что изменения происходят через фиксированное число поколений, при этом лучшие особи популяции сохраняются через заданные интервалы времени. После изменения целевой функции новая популяция частично заполняется решениями, сохраненными на предыдущих итерациях (5-10%), а остальные особи инициализируются случайным образом. В [63] было отмечено существенное улучшение качества работы алгоритма при использовании данного подхода по сравнению со случайной инициализацией. Тем не менее, при передаче в новую популяцию большего числа сохраненных решений (50-100%) или при более значительных изменениях функцйи качества работа алгоритма ухудшалась.

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

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

В настоящее время в литературе уделяется недостаточно внимания сравнению различных вариантов генетических алгоритмов при

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

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

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

Практика решения задач гидродинамики и тепломассообмена разностными методами на сетках с фиксированным числом узлов

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

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

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

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

Наиболее распространенными подходами для создания адаптивных сеток при сохранении общего числа узлов являются подходы, основанные на применении вариационных методов [73, 74], и методы равнораспределения весовой функции [75-78].

20

Общей чертой вариационных методов является решение вариационной задачи определения экстремумов функционалов, характеризующих определенные свойства расчетной сетки. Метод равнораспределения основан на равномерном распределении в узлах сетки весовой функции, связанной с особенностями решения. Благодаря специальному выбору весовой функции [69], в ходе расчетов сетка автоматически сгущается в областях больших градиентов решения. В [79] было отмечено, что метод равнораспределения по сути эквивалентен решению уравнений Эйлера для вариационных задач. Следовательно, вариационные подходы и методы равнораспределения являются наиболее общими и изначально родственными способами адаптации расчетных сеток.

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

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

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

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

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Малютина, Элина Эдуардовна

Выводы

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

86

2. Исследованы свойства генетического алгоритма, приводящие к асимметрии распределения узлов сетки.

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

87

Заключение

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

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

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

3. Предложен и реализован генетический алгоритм для задачи поиска оптимального управления динамической системой. Исследована зависимость степени разнообразия популяции при поиске оптимального управления от параметров генетического алгоритма - размера популяции и вероятности мутации.

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

88

Список литературы диссертационного исследования кандидат физико-математических наук Малютина, Элина Эдуардовна, 2001 год

1. Goldberg D. Е. Genetic Algorithms in Search, Optimization and Machine Learning. Reading: Addison Wesley, New York, 1989 - 412p.

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

3. Курейчик В.М. Генетические алгоритмы. Состояние, проблемы, перспективы // Известия Академии наук. 1999. - №1. - С. 144-160.

4. Holland J.H. Adaptation in Natural and Artificial Systems // Univ.of Michigan Press, Ann Arbor. 1975.

5. Обозрение прикладной и промышленной математики. "Эволюционные вычисления и генетические алгоритмы." 1996. -т.З, №5.

6. Szpiro G.G. Forecasting Chaotic Time Series with Genetic Algorithms // Physical Review E. 1997. - V.55, N3. - P. 2557-2568.

7. Alvarez A. Forecasting the SST Space-Time Variability of the Alboran Sea with Genetic Algorithms // Geophysical Research Letters. 2000.

8. Загоруйко Н.Г. Самообучающийся генетический алгоритм для прогнозирования. // Искусственный интеллект и экспертные системы. Новосибирск, 1997. - Вып. 160, "Вычислительные системы". - С. 80-95.

9. Васильев В.И., Ильясов Б.Г. Интеллектуальные системы управления с использованием генетических алгоритмов // Учеб. пособие, Уфимск. гос. авиац. техн. ун-т. 1999. - 105 с.

10. Davidor Y. A. Genetic Algorithm Applied to Robot Trajectory Generation // Parallel Problem Solving from Nature 4. 1996.89

11. Zalzala A.M.S., Fleming P.S. Genetic Algorithms: Principles and Applications in Engineering Systems // Neural Network. 1996. - Vol. 6, N5. -P.803-820.

12. Ono O., Kobayashi В., Kato H. Optimal Dynamic Motion Planning of Autonomous Vehicles by a Structured Genetic Algorithm // Proc. of the 13th World Congress of IFAC, vol. Q. San-Francisco, USA,1996. -P.435-440.

13. Forrest S. Mayer-Kress G. Genetic Algorithms, Nonlinear Dynamical Systems and Models of International Security // Parallel Problem Solving from Nature 4. 1996.

14. Rudolph G. Convergence Analysis of Canonical Genetic Algorithm // IEEE Trans, on Neural Networks. 1994. - V.5, N.l. - P.96-101.

15. Eiben A.E., Aarts E.H.L., Van Нее K.M. Global Convergence of Genetic Algorithms: a Markov Chain Analysis // Parallel Problem Solving from Nature, 1st Workshop PPSN. Springe-Verlag, 1991. - P.4-12.

16. Еремеев A.B. Генетический алгоритм для задачи о покрытии. // Дискретный анализ и исследование операций. 2000. - Серия 2, т.7, №1.

17. Ту Дж., Гонсалес Р. Принципы распознавания образов. М.:"Мир", 1978.-320 с.

18. Болотов А.А., Фролов А.Б. Классификация и распознавание в дискретных системах / под ред. В.Н. Вагина. М., изд-во МЭИ,1997. -120 с.

19. Лбов Г.С. Методы обработки разнотипных экспериментальных данных. Новосибирск, "Наука", 1981.

20. Moser A. Distributed Genetic Algorithms for Feature Selection. Ph.D. theses, Univ. of Kaiserslantern. - Germany, 1999.

21. Moser A., Murty M.N. On the Scalability of Genetic Algorithms to Very Large-Scale Feature Selection // EvoIASP. 2000.90

22. Siedlecki W., Sklansky J. On Automatic Feature Selection // International Journal of Pattern Recognition and Artificial Intelligence. 1988. - Vol. 2, N2.-P. 197-220.

23. H. Vafaie K.DeJong Robust Feature Selection Algorithms // Proc. of the 5th IEEE Int. Conf. on Tools for Artificial Intelligence. Boston, MA: IEEE Press, 1993. - P.356-363.

24. Siedlecki W., Sklansky J. A Note on Genetic Algorithms for Large-Scale Feature Selection // Pattern Recognition Letters. 1989. -N10.-P. 335-347.

25. Guerra-Salcedo C., Whitley D. Genetic Search for Feature Selection: A Comparison Between CHC and GENESIS // Proc. of the Symposium on Genetic Algorithms. 1998.

26. Yang J., Honavar V. Feature Subset Selection Using a Genetic Algorithm. Feature Extraction, Construction and Selection A Data Mining Perspective, 1998.

27. Vafaie H. DeJong K, An Empirical Comparison Between Global and Greedy-Like Search for Feature Selection // Proc. of the Florida AI Research Symposium. 1994.

28. Flotzinger D. Feature Selection by Genetic Algorithms // IIG Report Series,- 1993.-P.369.

29. Prakash M., Murty M.N. Feature Selection to Improve Classification Accuracy Using A Genetic Algorithm // Journal of the Indian Institute of Science. -1997.

30. Jain A.K., Zongker D. Feature Selection: Evaluation, Application and Small Sample Performance // IEEE Transactions on Pattern Analysis and Machine Intelligence. 1997. - V. 19, N2.

31. Климонтович Ю.Л. Турбулентное движение и структура хаоса: новый подход к статистической теории открытых систем. М.: "Наука". Гл.ред. физ.-мат лит, 1990. - 320 с.91

32. Николис Г., Пригожин И. Самоорганизация в неравновесных системах. М.: "Мир", 1979. - 560 с.

33. Васильев С.Н. Жерлов А.К., Федосов Б.Е., Федунов Б.Е. Интеллектуальное управление динамическими системами. -М.: "Наука", 2000.

34. Васильев В.И., Ильясов Б.Г. Интеллектуальные системы управления с использованием нейронных сетей // Учеб. пособие, Уфимск. гос. авиац. техн. ун-т, 1998. 87 с.

35. Аверин А.В., Батыршин И.З., Блишун А.Ф. и др. Нечеткие множества в моделях управления и искусственного интеллекта. М.: "Наука", 1986.-312 с.

36. Борисов А.Н., Алексеев А.В. Обработка нечеткой информации в системах принятия решений. М: "Радио и Связь", 1989. - 304 с.

37. Handbook of Intelligent Control: Nueral,Fuzzy and Adaptive Approaches. / Ed. D.A. White, D. A. Sofge. N.Y.: Van Nostrand Reinhold, 1992. - 568 p.

38. Кусимов C.T., Ильясов Б.Г., Васильев В.И. и др. Управление динамическими системами в условиях неопределенности. -М.: "Наука", 1998.-452 с.

39. Chipperfield A., Fleming P. An Overview of Evolutionary Algorithms for Control Systems Engineering // Evolutionary Computation, 2000.

40. Liu Y., Kojima H. One Design Method of a Fuzzy Controller Using Genetic Algorithms // Proc. of the 1993 JSME Inter. Conf. on Advanced Mechanics. Tokyo, Japan, 1993. - P. 333-338.

41. Hoffman F. Pfister G. Automatic Design of Hierarchical Fuzzy Controller Using Genetic Algorithms // EUFIT 94, Aachen, Germany, 1994.

42. Brill F.Z., Brown D.E., Martin W.N. Fast Genetic Selection of Features for Neural Network Classifiers // IEEE Trans, on Neural Networks. -1992. V.3, N2. - P.324-32892

43. Guo Z., Uhrig R.E. Using Genetic Algorithms to Select Inputs for Neural Networks. // Inter. Workshop on Combinations of Genetic Algorithms and Neural Networks. -1992.

44. Grefenstette J. J. Learning Decision Strategies with Genetic Algorithms. -Navy Center for Applied Research in Artificial Intelligence, 1991.

45. Karr C.L., Freeman L.M. Genetic-algorithm Based Fuzzy Control of Spacecraft Autonomous Rendezvous // Engineering Application of Artificial Intelligence. 1997. - V.10, N3. - P.293-300.

46. Gerdes I. Construction of Conflict-Free Routes for Aircraft in Case of Free-Routing with Genetic Algorithms // Proc. 1st USA/Europe Air Traffic Management R&D Seminar, 1997.

47. Krishakumar K., Goldberg D.E. Control System Optimization Using Genetic Algorithms // Journal of Guidance, Control and Dynamics. 1992.- Vol.15, N3.-P.735-740.

48. Neubauer A. On-Line System Identification Using the Modified Genetic Algorithm//Proc. ofEUFIT'97, Germany. 1997. -P.764-768.

49. Kristinsson K, Dumont G.A. System Identification and Control Using Genetic Algorithms // IEEE Trans. Sys., Man and Cybern. 1992, V.22, N5. - P.1033-1046.

50. Trojanowski K., Michalewicz Z. Evolutionary Algorithms for Non-Stationary Environments // Proc. on the Workshop on Intelligent Information Systems VIII. Poland, 1999.

51. Branke J. Evolutionary Algorithms for Dynamic Optimization Problems, A Survey. -Technical Report 387, AIFB University Karlsruhe, 1999.

52. Grefenstette J.J. Genetic Algorithms for Changing Environments // PPSN.- 1992. P.137-144.

53. Cobb H.G., Grefenstette J.J. Genetic Algorithms for Tracking Changing Environments // Proc. of the 5th International Genetic Algorithms Conference. 1993.93

54. Mori N., Imanishi S., Kita H., Nishikawa Y. Adaptation to a Changing Environment by Means of the Memory Based Thermodynamical Genetic Algorithm // Proc. of the 7th IEEE Int. Conf. on Genetic Algorithms (VII ICGA'97). -1997. P.299-306.

55. Mori N., Kita H., Nishikawa Y. Adaptation to a Changing Environment by Means of the Feedback Thermodynamical Genetic Algorithm // 5PPSN: Parallel Problem Solving from Nature. 1998. - P.149-157

56. Ghosh A., Tsutsui S., Tanaka H. Function Optimization in Non-Stationary Environment using Steady-State Genetic Algorithms with Aging of Individuals // Proc. of the 5th IEEE Int. Conf. on Evolutionary Computation (ICEC'98). 1998. -P.666-671.

57. Cobb H.G. An Investigation into the Use of Hypermutation as an Adaptive Operator in the Genetic Algorithm Having Continuous Time-Dependent Nonsationary Environments. Naval Research Laboratory Memorandum Report 6760. - 1990.

58. Vavak F., Fogarty T.C., Jukes K. A Genetic Algorithm with Variable Range of Local Search for Tracking Changing Environments // Parallel Problem Solving from Nature 4. 1996.

59. Back Т., Schutz M. Intelligent Mutation Rate Control in Canonical Genetic Algorithm // Proc. of the 9th Int. Symposium ISMIS'96, 1996. -V.1079 inLNAI. -P.158-167 1997.

60. Srinivas M., Patnaik L.M. Adaptive Probabilities of Crossover and Mutation in Genetic Algorithms // IEEE Trans, on Systems, Man and Cybernetics. 1994. - V.24, № 4. - P. 656-667.

61. Goldberg D.E., Smith R. Nonstationary Function Optimization Using Genetic Dominance and Diploidy // Proc. of the Second Int. Conf. on Genetic Algorithms. 1987. - P.59-68.94

62. Dasgupta D., McGragor D.R. Nonstationary Function Optimization Using the Structured Genetic Algorithm // Parallel Problem Solving from Nature 2. 1992. -P.145-154.

63. Louis S.J., Xu Z. Genetic Algorithms for Open Shop Scheduling and ReScheduling // ISC A 11th Int. Conf. on Computers and their Applications. -1996. P.99-102.

64. Ramsey C.L., Grefenstette J.J. Case-based Initialization of Genetic Algorithms // 5th Int. Conf. on Genetic Algorithm. 1993. - P.84-91.

65. Дулан Э., Миллер Дж., Шилдерс У. Равномерные численные методы решения задач с пограничным слоем. М.: "Мир", 1983.

66. Ильина Е.В., Педоренко А.В., Попов A.M. Моделирование МГД-неустойчивости слабо диссипативной плазмы в токамаке. // Математическое моделирование. 1990. - т.2, №2. - С.86-94.

67. Лисейкин В.Д. Обзор методов построения структурных адаптивных сеток // ЖВМ и МФ. 1996. - т.36, №1. - С.3-41.

68. Baker T.J. Prospects and Inspections for Unstructured Methods // Proc. of Surface Modeling, Grid Generation and Related Issues in Computational Fluid Dynamics Workshop, NASA Conf. Publication 3281, 1995. P.273.

69. Thompson J.F. A Reflection on Grid Generation in the 90-s: Trends, Needs and Influences. // Numerical Grid Generation in Computational Fluid Simulations / eds. Soni B.K., Thompson J.F., Hauser J., Eiseman P.R. Mississippi, 1996. - P. 1029-1110.

70. Trepanier J. Y., Zhang H., Reggoi M., Camarero R. Adaptive and Moving Meshes for the Computation of Unsteady Uncompressible Flows // Numerical Grid Generation in Computational Fluid Dynamics and Related Fields. Amsterdam, 1991. - P. 43-54.

71. Lohner R., Baum J.D. Numerical Simulation of Shock Interaction with Complex Geometry Three-Dimensional Structures Using a New Adaptive H-Refinement Scheme on Unstructured Grids // AIAA Paper 0700. 1990.95

72. Maman N., Larrouturou B. Dynamical Mesh Adaptation for Two Dimensional Reactive Flow Simulations // Numerical Grid Generation in Computational Fluid Dynamics and Related Fields. Amsterdam, 1991. - P.13-26.

73. Saltsman J.S. Variational Methods for Generating Meshes on Surfaces in Three Dimensions // J. Сотр. Physics. 1986. - V.63, №1. -P.l-19.

74. Крейс Р.И., Тейтз Ф.К., Хасан Х.А. Построение адаптирующихся сеток с помощью вариационного метода Брекбилла-Зальцмана. // Аэрокосмическая техника. 1987. - №1. - С.83-90.

75. Похилко В.И., Тишкин В.Ф. Одномерный алгоритм расчета разрывных на адаптивных сетках. // Математическое моделирование.- 1994. Т.6, №11. - С.25-40.

76. Неледова А.В., Тишкин В.Ф., Филатов А.Ю. Нерегулярные адаптивные сетки для решения задач математической физики. // Математическое моделирование. 1997. - Т.9, №2.

77. Шокина Н.Ю. Численное моделирование на адаптивных сетках двумерных установившихся течений жидкости и газа // Вычислительные технологии. 1998. - Т.З, №3. - С. 85-93.

78. Хакимзянов Г.С., Шокина Н.Ю. Метод эквираспределения для построения адаптивных сеток // Вычислительные технологии. 1998.- Т.З, №6.

79. Thompson J.F. A Survey of Dynamically Adapted Grids in the Numerical Solution of Partial Differential Equations // Appl. Numer. Math. 1985. -V.l. -P.3-28.

80. Малютина Э.Э. Применение генетических алгоритмов для анализа активных баз данных // Вестник Московского Университета. 1997, Серия 15, "Вычислительная математика и кибернетика", №2. - С. 24-28.96

81. Malyutina E. The Selection of Optimal Subsets of Principal Components for Discrimination Using Genetic Algorithms // Proc. of the First International Conference on Evolutionary Computation and Its Applications. Moscow, 1996, - P. 278-284.

82. Малютина Э.Э. Применение генетического алгоритма для расчета управления сложной динамической системой // Численные методы и вычислительный эксперимент / Под ред. А.А. Самарского, В.И. Дмитриева. -М.: Диалог-МГУ, 1998. С. 82-96.

83. Malyutina Е. Using Genetic Algorithms for Dynamical System Control // Computational Mathematics and Modeling. 1999, Vol. 10, №4.

84. Малютина Э.Э. Применение стохастических методов для расчета управления динамической системой // Информационные технологии и вычислительные системы. 2000. №1. - С. 52-59.

85. Малютина Э.Э. Построение адаптивных сеток с помощью генетического алгоритма // Известия ТРТУ, Математическая международная научно-техническая конференция и молодежная научная конференция "Интеллектуальные САПР",- Таганрог, 2000. -№2. С. 344-345.

86. Малютина Э.Э. Построение адаптивных сеток с использованием генетических алгоритмов // Математическое моделирование. 2001. - Т. 13, №9.

87. Скурихин А.Н. Генетические алгоритмы // Новости искусственного интеллекта. 1995. - №4. -С.6-46.

88. Wright А.Н. Genetic Algorithms for Real Parameter Optimization // Foundations of Genetic Algorithms. 1991. - P.205-218.

89. Bethke A.D. Genetic Algorithms as Function Optimizers // Ph.D. thesis University of Michigan, No. 8106101. 1981.97

90. Grefenstette J. J. Optimization of Control Parameters for Genetic Algorithms // IEEE Transactions on Systems, Man and Cybernetics. -1986.-V. SMC-16, N.l. P. 122-128.

91. Oja E. Subspace Methods of Pattern Recognition. Research Studies Press, U.K., 1983.

92. Bandyopadhyay S., Murthy C.A., Pal S.K. Pattern Classification with Genetic Algorithms // Pattern Recognition Letters. 1995. -V.16. -P.801-808.

93. Goldberg D.E., Segrest P. Finite Markov Chain Analysis of Genetic Algorithms // Genetic Algorithms and Their Applications, Proc. 2nd Int. Conf. on Genetic Algorithms (ICGA'87). Cambridge, MA, 1987.

94. De Jong K. An Analysis of the Behavior of a Class of Genetic Adaptive Systems // Dissertation Abstracts International. 1975. - V.36, N.10, 5140B.

95. Кемени Д., Снелл Д. Конечные цепи Маркова. М: "Наука", 1970.-272 с.

96. Крамер Г. Математические методы статистики. -М: "Мир", 1975.

97. Загоруйко Н.Г. Прикладные методы анализа данных и знаний. -Новосибирск, 1999.

98. Leung Y., Gao Y., Xu Z. Degree of Population Diversity A Perspective on Premature Convergence in Genetic Algorithms and its Markov Chain Analysis. - Center for Environmental Studies, 1997.

99. Fogarty T.C., Vavak F., Cheng P. Application of the Genetic Algorithm for Load Balancing of Sugar Beet Presses // Proc. Of the 6th Int. Conf. On Genetic Algorithms. 1995. - P.617-624.

100. Vavak F., Fogarty T.C., Jukes K. Use of the Genetic Algorithm for Load Balancing in the Process Industry // 1st Inter. Mendelian Conf. on Genetic Algorithms, PC-DIR Publishing s.r.o. Brno, 1995. - P.159-164.98

101. Моисеев Н.Н., Иванилов Ю.П., Столярова Е.М. Методы оптимизации. М.: "Наука", 1978.

102. Львовский Е.Н. Статистические методы построения эмпирических формул. -Учебное пособие для ВТУЗов. М.: "Высшая школа", 1988.-239 с.

103. De Jong К., Potter М. Evolving Complex Structures via Cooperative Coevolution. // Fourth Annual Conference on Evolutionary Programming. -San Diego, CA, 1995.

104. Forrest S., Javornik В., Smith R., Perelson A. Using Genetic Algorithms to Explore Pattern Recornition in the Immune System // Evolutionary Computation. 1993. - V.l, N.3. - P. 191-211.

105. Daripa P. Iterative Schemes and Algorithms for Adaptive Grid Generation in One Dimension // J. Comput. Physics. 1992. -V.100.-P.284-293.

106. Coyle J.M., Flaherty J.E., Ludwig R. On the Stability of Mesh Equidistribution Strategies for Time-Dependent Partial-Differential Equations // J. Comput. Physics. 1986. - V.62, №1. - P.26-39.

107. Reeves C.R. Genetic algorithms for the Operations Researcher // INFORMS Journal on Computing. 1997. - V.9, N.3. - P.231-250.

108. Рис. 2.2 Применение алгоритма GA2 для выделения центроидов кластеров.

109. Рис.2.10 Группировка точек популяции генетического алгоритма вокруг центроидов кластеров (D=1.41, g=0.9)1. Рис 2.12

110. Сравнение генетического алгоритма и метода Forel

111. Рис. 3.3 Зависимость ошибки по функционалу от уровня мутации генетического алгоритма (а = О )

112. Зависимость ошибки по функционалу от уровня мутации генетического алгоритма, (а =0.1)

113. Зависимость ошибки по функционалу от уровня мутации генетического алгоритма. (а = 1.0)1. Рис 3.7

114. Зависимость ошибки по функционалу от времени. (а = 1.0)

115. Рис. 3.11 Зависимость ошибки по функционалу от времени. (а = 0.05 )

116. Рис 3.13 Зависимость времени счета от числа траекторий системы при использовании метода квазилокальных вариаций.

117. Рис 3.14 Зависимость времени счета от числа траекторий системы при использовании генетического алгоритма.х

118. Рис.4.3 Построение сетки с помощью метода равнораспределения весовой функции ( W = 0.5)1.I1. Рис.4.4

119. Зависимость ошибки аппроксимации на сетках, построенных с помощью генетического алгоритма (GA) и метода равнораспределения весовой функции (WF) от числа узлов сетки ( w = 0.3).118

120. Рис. 4.56 Построение сетки с помощью метода равнораспределения весовой функции (W = 0.1) (30 итерация)

121. Рис. 4.10 Изменение величины г при перемещении слоя.

122. Рис.4.126 Пример сетки, построенной с помощью ГА, при перемещении пика (х= 2.0) (код Грея)