Содержание к диссертации
Введение
ГЛАВА 1. Анализ эволюционных алгоритмов, нейронных сетей и алгоритмов кластеризации 16
1.1. Задача параметрического оценивания 16
1.2. Особенности параметрического оценивания ресурсоемких моделей 11
1.3. Генетические алгоритмы в задачах оптимиззаци 21
1.4. Нейронные сети в задачах аппроксимации 24
1.5. Алгоритмы кластеризации 30
1.6. Гибридные ГА, использующие нейронную сеть 34
1.7. Основные результаты и выводы по первой главв 38
ГЛАВА 2. Интеллектуальные алгоритмы идентификации параметров ресурсоемких моделей 33
2.1. Гибридная схема использования нейронной сети в составе ГА 39
2.2. Выбор архитектуры НС для использования в составе ГА+НС 43
2.3. Алгоритм обучения РБНС в нейросетевом контуре ГА+НС 52
2.4. Алгоритмы кластеризации входных данных на первом этапе обучения РБНС 55
2.5. Дополнительное обучение РБНС 76
2.6. Генетический алгоритм с вертикальными субпопуляциями 79
2.7. Основные результаты и выводы по второй главв 83
ГЛАВА 3. Исследование разработанных алгоритмов с помощью вычислительных экспериментто 88
3.1. Краткие сведения о разработанном комплексе программ 85
3.2. Тестирование алгоритмов кластеризации KM+GA и DA+GA з
3.3. Тестирование ГА+НС на задаче минимизации функций Растри-гина и Розенброка 94
3.4. Тестирование ГА+ВСП на задаче минимизации функций ПО
3.5. Основные результаты и выводы по третьей главе 118
ГЛАВА 4. Применение разработанных алгоритмов для идентификации параметров гидродинамических моделей нефтяных месторождений 120
4.1. Прямая задача теории гидродинамического моделирования 120
4.2. Обратная задача теории гидродинамического моделирования — адаптация модели нефтяного месторождения 123
4.3. Подбор множителей пористости околоскважинного пространства с использованием ГА+НС 128
4.4. Определение относительных фазовых проницаемостей модели резервуара с помощью ГА+НС и ГА+ВСП 135
4.5. Основные результаты и выводы по четвертой главе 142
Заключение 144
Список использованных источников 146
- Генетические алгоритмы в задачах оптимиззаци
- Выбор архитектуры НС для использования в составе ГА+НС
- Тестирование ГА+НС на задаче минимизации функций Растри-гина и Розенброка
- Подбор множителей пористости околоскважинного пространства с использованием ГА+НС
Введение к работе
Актуальность темы
Одним из важнеііших инструментов пропюзировагога поведешга сложных объектов исследования (ОИ) является математическое моделирование с использованием полномасштабных цифровых моделей этих объектов. Оно дает возможность заменить натурный эксперимент математическим (численным) и исследовать проявление того или иного воздействия на ОИ с помощью изучения влияния параметров на математическую модель. Такой эксперимент, дополняя натурный, позволяет глубже исследовать явление или процесс и принимать наиболее обоснованные решения, сокращающие возможность ошибки.
Теория идеіггификации систем появилась почти одновременно с теорией автоматического управления, о чем свидетельствуют рабогы Н. Nyquist (1932) и II. Bode (1945), в которых, по существу, описываются методы идентификации. В дальнейшем данным вопросом занималось множество известных ученых, таких как R. Lee (1964), G. Box, G. Jenkins (1970), A. Sage (1971), J. Mendel (1973), P. Eykhoff (1974) и др. Современное состояние данной теории представлено в монографиях таких авторов, как D. Grop (1979), Л. А. Растригин (1981), L. Ljung (1991), Я.З. Цыпкин (1995) и др. Идентификация ОИ с выходными сигналами у(к) = (yi(k),y2(k),. . .,Ут(&)), измеряемыми в дискретные моменты времени .'ь к = 1,2,..., осуществляется при помощи математической модели у = М(к | х). Выходные сигналы у(к | х) = = (yi(k | х),у2(к | х),... ,}'т(к I х)) модели зависят от вектора настраиваемых параметров х є Dm с R", значения которых подлежат определению. Для этого вводится целевая функция (ЦФ), отражающая качество идентификации. Часто она имеет квадратичную форму
/(x) = e(fc,x)r.W-(*,x), (1)
Є(,х) = уШ-у№|х),
где W — матрица весовых коэффициентов.
Далее задача идентификации параметров ОИ сводится, как правило, к задаче минимизации ЦФ (1). Обычно она имеет множество локальных минимумов, что ограничивает применимость методов локальной оптимизации (например, градиентных) только возможной стадией уточнения решения. Поэтому в таких задачах, как правило, применяются алгоритмы с возможностями глобальной оптимизации. Разработкой детерхминированных и эвристических методов глобальной оптимизации занимались С. А. Пиявский (1967), Н.П. Жидков (1968), Б.О. Шуберт (1972), Ю.Г. Евтушенко (1974), И. Федорова (1978), Р. Г. Стронгин (1978), А. V. Levy, S. Gomez (1980), А. О. Griewank (1981), Е. Гальперин (1985), J. S. Агога (1992) и другие ученые. Стохастические алгоритмы представлены в работах N. Metropolis (1953), J. Н. Conway (1982), A.II.G. Rinnooy Kan, C.G.E. Boender (1985), W.L. Price, M. Piccioni
2 (1987), S. Lucidi (1988), P. Jain (1989) и многих других исследователей. Созданием и совершенствованием эволюционных алгоритмов занимались, в частности, J.H. Holland (1962), I. Rechenberg (1965), Н. Schwefel (1965), К. DeJong (1975), D. Whitley (1989), К. Deb, D.E. Goldberg (1991), Z. Michalewicz(1992), F. Herrera, M. Lozano (1998), T. Back (2000) и др.
Развитие генетических алгоритмов (ГА) с целью ускорения эволюционного поиска в настоящее время идет по многим направлениям. К традиционным можно отнести усовершенствования основных операторов селекции, скрещивания и мутации, распараллеливание, разработку самонастраивающихся ГА. Одним из наиболее перспективных направлений является создание гибридных схем, когда ГА работает в паре с другим алгоритмом оптимизации, например с алгоритмом градиентного спуска (В. А. Тенев и Н. Б. Паклин, 2003).
Большим потенциалом обладает также использование гибридных схем с применением ГА и нейронных сетей (НС). Данному вопросу в последнее время посвящается много работ, например, A. A. Javadi, Z. Liu (2005), J.-Т. Kuo (2006), Т. Morimoto, К. С. Giannakoglou (2007) и др. Подобные гибридные алгоритмы основаны на технике суррогатного моделирования пая метамоде-лирования, предполагающей замену полномасштабной модели ОИ на значительно менее ресурсоемкую модель, приближенно воспроизводящую отклик исходной модели. Теория метамоделирования развивается, в частности, такими учеными, как А. П. Кулешов, А. В. Бершптейн, Е.В. Бурнаев, G. G. Wang (2007), A. Forrester, A. Sobester, А. Кеапе (2008).
Цель диссертационной работы
Целью диссертациогагого исследования является разработка эффективных алгоритмов решения задачи идентификации параметров ресурсоемких математических моделей на основе методов эволюционных вычислений, пей-росетевой аппроксимации и декомпозиции области поиска решения, а также реализация разработанных алгоритмов в виде комплекса программ.
Задачи исследования
-
Разработать гибридный генетический нейросетевой алгоритм идентификации параметров ресурсоемких математических моделей объекта исследования на основе данных натурного эксперимента.
-
Разработать алгоритм формирования обучающей выборки и обучения нейронной сети в составе гибридного алгоритма.
-
Разрабогать алгоритм идентификации параметров больших моделей, которые можно представить в виде конечного числа слабо связашшх частей, а критерий адекватности модели (целевую функцию) — в виде суперпозиции вложенных функций.
-
Реализовать предложенные алгоритмы в виде комплекса программ и проанализировать их эффективность с помощью вычислительных экспериментов.
-
Применить разработанные алгоритмы для идентификации параметров гидродинамических моделей нефтяных месторождений.
Методы нсследопапия
В работе использованы методы теории оптимизации, математической статистики, мягких вычислений, искусствегаюго интеллекта, базовые положеігая теории фильтрации многофазных систем.
Результаты, выносимые на защиту
-
Гибридный генетический нейросетевой алгоритм (ГА+НС) для идентификации параметров ресурсоемких моделей.
-
Алгоритм формирования обучающей выборки и обучения радиалыю-базисной нейронной сети в составе ГА+НС.
-
Генетический алгоритм с «вертикальными» субпопуляциями (ГА+ВСП) для идентификации параметров математических моделей ОИ с целевой функцией, представимой в виде суперпозиции вложенных функций, «существенно» зависящих от непересекающихся подмножеств множества всех аргументов ЦФ.
-
Реализация предложенных алгоритмов на языке C++ в виде комплекса программ.
-
Результаты анализа эффективности разработанных алгоритмов и рекомендации по их применению.
Научная новизна
-
Гибридная схема ГА+НС, разработанная для решения задач идентификации параметров ресурсоемких математических моделей. Отличается интеграцией в цикл ГА неиросетевого контура, предназначенного для получения прогноза оптимального решения. Обучающая выборка для НС формируется динамически в процессе рабогы алгоритма.
-
Алгоритм формирования обучающей выборки и обучения радиально-базисной нейронной сети в составе неиросетевого контура ГА+НС. Отличается предварительной кластеризацией множества приближений с автоматическим определением количества кластеров.
-
Генетический алгоритм с вертикальными субпопуляциями, предназначенный для оптимизации целевых функций, являющихся суперпозициями вложенных фушеций. Отличается оптимизацией вложенных функций от меньшего числа неизвестных одновременно с поиском оптимума в пространстве всех неизвестных ЦФ.
Практическая значимость и внедрение результатов работы
Разработанные алгоритмы ГА+НС и ГА+ВСП позволяют существенно сократить время, затрачиваемое на идентификацию параметров ресурсоемких математических моделей ОИ, по сравнению с обычным ГА.
Программная реализация предложенных алгоритмов на языке C++ в виде динамически подключаемых библиотек дает возможность применять их в составе различных программных комплексов. На разработанные библиотеки получено свидетельство об официальной регистрации программы для ЭВМ.
Алгоритмы ГА+НС и ГА+ВСП используются в пакетах прикладных программ, разработанных в ООО «РН-УфаНИПИнефть», таких как программный
4 комплекс для гидродинамического моделирования «NGT BOS» и система автоматической адаптации моделей на базе программного комплекса MATLAB, для работы с реальными проектами разработки нефтяных месторождений, а также в исследовательских целях.
Апробация работы
Основные результаты работы докладывались и обсуждались на следующих научно-технических конференциях.
Российский и Каспийский региональный конкурс студенческих и аспирантских работ SPE, Москва, 2006.
Вторая региональная зимняя школа аспирантов и молодых ученых, Уфа, 2007.
Научная сессия Государственного университета авиационного приборостроения, Санкт-Петербург, 2007.
Четвертая Международная научно-пракгическая конференция «Исследование, разработка и применение высоких технологий в промышленности», Санкт-Петербург, 2007.
Научно-практический семинар «Информационные технологии при разработке месторождений», Уфа, 2007.
36-я международная конференция «Современные информационные технологии в нефтяной и газовой промышленности», Коста дель Соль (Испания), 2007.
Международная научная конференция «Параллельные вычислительные технологии (ПаВТ)», Уфа, 2010.
Научно-практические семинары в ООО «РН-УфаНИПИнефть».
Публикации
По теме диссертации опубликовано 10 работ, в том числе 4 статьи в рецензируемых научных журналах из списка ВАК, 5 статей и материалов научно-практических конференций в других изданиях, 1 свидетельство об официальной регистрации программы для ЭВМ.
Структура и объем диссертации
Диссертационная работа изложена на 211 страницах машинописного текста и включает в себя введение, четыре главы основного материала, заключение и библиографический список из 145 наименований, изложенные на 157 страницах, а также два приложения. Работа содержит 50 рисунков и 35 таблиц.
Генетические алгоритмы в задачах оптимиззаци
Благодаря своим особенностям, генетические алгоритмы (ГА) зачастую обеспечивают преимущество перед многими традиционными эвристическими методами оптимизации, особенно когда пространство поиска имеет сложную форму, разрывно или сильно ограничено. Они не нуждаются в знании производных ЦФ и не предъявляют каких-либо требований к ее гладкости. Кроме того, ГА способны в процессе поиска выходить из локальных минимумов за счет использования целой популяции решений и не требуют знания априорной информации о предметной области (но могут использовать ее, если такая информация доступна). Все эти свойства делают ГА методами устойчивой оптимизации, популярными в настоящее время [12-14].
Описанию ГА посвящен раздел АЛ приложения А. Параграф А. 1.2 содержит описание канонической модели ГА, использовавшей двоичное представление хромосомы (приближения), описанное в параграфе А. 1.3. Генетические операторы скрещивания и мутации, характерные для канонической модели ГА, описаны в параграфе А. 1.4. Основополагающим теоретическим результатом, обосновывающим эффективность канонического ГА, является теорема шаблонов, приведенная в параграфе А. 1.5. В параграфе А. 1.6 приведены критические замечания в адрес теории шаблонов. Оператору селекции ГА посвя 22 щен параграф А. 1.7. Селекция фактичееки производится на основе значений функции приспособленности (ФП), некоторые способы вычисления которой представлены в А. 1.8. ФП, в свою очередь, обычно используется для расчета вероятностей отбора каждого приближения в популяции. Если вероятности вычисляются пропорционально значениям ФП, то селекция также называется пропорциональной (параграф А. 1.9). Альтернативой является ранговая селекция, описанная в АЛЛО. Турнирный оператор селекции, не требующий вероятностей отбора, рассмотрен в параграфе АЛЛ1.
Очевидно, что для многих задач наиболее естественным является представление параметров ЦФ в виде действительных чисел. Этап их преобразования в двоичный код создает для ГА ряд отрицательных эффектов, описанных в параграфах А.1.3 и АЛ.6. Принципиальным ограничением является дискретизация параметров, т. е. переход от непрерывного пространства поиска к дискретному. Преодолеть эти сложности позволяют генетические алгоритмы с вещественным кодированием Real-coded GA, RGA [15, 16].
При использовании RGA каждый ген хромосомы представляет собой действительное число, соответствующее одному параметру ЦФ. Таким образом, этап преобразования из фенотипа в генотип (и обратно) отсутствует, т. к. они совпадают. Помимо некоторого прироста скорости по сравнению с бинарным ГА, это позволяет генетическим операторам работать напрямую с фенотипом, что более предпочтительно [17]. Вещественное представление хромосом позволяет использовать большие (даже бесконечные) области определения параметров ЦФ. Кроме этого, такие часто встречающиеся в реальных задачах свойства ЦФ, как непрерывность и дифференцируемость, могут существенно помогать RGA при уточнении решения [15]. Вещественное представление изначально применялось в ЭА, называемых эволюционными стратегиями {Evolution Strategy) [18, 19].
Для RGA были разработаны специальные операторы кроссовера и мутации. Наиболее полный их обзор приведен в работе [15]. Кратко операторы скрещивания и мутации RGA, реализованные в библиотеке интеллектуальных алгоритмов оптимизации [20], описаны соответственно в параграфах А. 1.12 и АЛ. 13. По результатам экспериментов [15] КGA на большинстве экстремально сложных тестовых проблем (включая функции Растригина и Розенброка) показал значительно более высокую производительность, по сравнению с бинарным ГА. Необходимо отметить, что теоретический анализ бинарных ГА, включая теорему шаблонов и ее выводы, не применим к ГА е вещественным кодированием.
Исходя из специфики решаемой в данной работе задачи и преимуществ ГА с вещественным кодированием, он использовался во всех предлагаемых алгоритмах и проведенных экспериментах. Разработанная автором библиотека интеллектуальных алгоритмов оптимизации [20] позволяет использовать и бинарный ГА, предоставляя для этого все необходимые инструменты, включая функции автоматического кодирования/декодирования.
Развитие ГА с целью ускорения эволюционного поиска в настоящее время идет по многим направлениям. К классическим можно отнести усовершенствования и разработку новых операторов селекции, скрещивания и мутации [12, 14, 15, 21, 22], распараллеливание [23-26], разработку самонастраивающихся ГА [27-29]. Одним из наиболее эффективных направлений является создание гибридных схем, когда ГА работает в паре с другим алгоритмом оптимизации, например, градиентным [30, 31]. Такая комбинация позволяет использовать преимущества обоих методов одновременно. Популяционная природа ГА делает поиск устойчивым, в то время как дополнительный метод оптимизации может его существенно ускорить, давая наилучшее приближение оптимального решения.
Выбор архитектуры НС для использования в составе ГА+НС
На основе проведенного анализа существующих подходов, были сформулированы следующие этапы алгоритма обучения РБНС в нейросетевом контуре ГА+НС.
1. Определение количества радиально-базисных функций (нейронов скрытого слоя) и первого приближения позиций их центров с помощью кластеризации входных данных с автоматическим определением количества кластеров. Для гауссовских активационных функций параметры сг вычисляются по формуле (2.6).
2. Уточнение всех весов сети с помощью алгоритма обратного распространения ошибки (ОРО). Такой подход обеспечивает более точную настройку РБНС по сравнению с традиционным расчетом весов только выходного слоя по МНК, так как позволяет корректировать параметры РБФ нейронов скрытого слоя.
3. Возможное дополнительное обучение РБНС на основе алгоритма каскадной корреляции С. Фальмана [47].
Процедура выполнения первого этапа обучения РБНС описана в параграфе 2.4. Разработанные алгоритмы кластеризации с автоматическим определением количества кластеров и особенности первого этапа обучения РБНС рассматриваются в параграфе 2.4. Второй этап уточнения весов с помощью алгоритма ОРО тривиален и не требует отдельного рассмотрения. Краткое общее описание ОРО приведено в параграфе А.2.4 приложения А. В алгоритме ГА+НС для уточнения весов РБНС используется модификация ОРО, называемая RPROP [85]. Третий этап дополнительного обучения подробно описывается в разделе 2.5.
Детальная схема процедуры выполнения первого этапа обучения РБНС, в результате которой также формируется обучающая выборка для алгоритма ОРО и область поиска для вспомогательного ГА приведена на рисунке 2.6. Она выполняется на четвертом шаге алгоритма ГА+НС (рисунок 2.1) на каждой итерации У. ВходныМИ данными для нее является множество А = {(х,/(х))} из N приближений, сгенерированных главным ГА к началу итерации у, вместе с соответствующими значениями ЦФ. Процедура состоит из следующей последовательности действий.
1. Выделение из множества А подмножества из NB лучших приближений В с А, где NB задается пользователем. Целью данного шага является ограничение сверху размера обучающей выборки для РБНС, формируемой в дальнейшем из множества В (множество А растет неограниченно). Находится текущее лучшее приближение х (х є В).
2. Кластеризация В с помощью разработанного алгоритма с автоматическим определением количества кластеров. Найденное число кластеров Ny определяет количество РБФ (нейронов скрытого слоя), центры которых располагаются в центрах найденных кластеров Г = {у}.
3. Формирование обучающей выборки L с В для второго этапа обучения РБНС. В выборку L попадают приближения (и соответствующие им значения ЦФ) из NL ближайших к лучшему приближению хь кластеров, т. е. L = {(X///(xz)), X/ е иЙ Q. : d(xb,yh) /(х ,уД V; {/,-}}, где С, - множество точек, принадлежащих у-му кластеру с центром в точке уу : Су = {х е В : d(xh уу) d(xt, у ), V& Ф у}, а d(х, у) - расстояние между точками х и у. Значение NL задается пользователем (в экспериментах данной работы NL = 10).
4. Определение области поиска для вспомогательного ГА, задазаемой в виде двух векторов а = (пь... ,а„) и Ь = ф\,... ,Ьп), таких что at = тinz {xzJ}, hi = maxz {xzJ}, Vxz = (хгД, xza,..., хг,«) е Z. Здесь 2 — множество приближений из Nz (Nz NL) кластеров вокруг лучшего решения, определяемое аналогично множеству L. То есть область поиска содержится внутри области, покрываемой обучающей выборкой. Значение Nz выбирается пользователем (в экспериментах данной работы Nz = 4).
На рисунке 2.6 шаги 3 и 4 объединены в единый блок под названием «фильтр по кластерам». Он может отсутствовать в цепочке предобработки по желанию пользователя. В этом случае обучающая выборка совпадает с отфильтрованными лучшими приближениями, которые определяют и область поиска, то есть Z = L = В. Тем не менее, кластеризация проводится всегда, так как координаты центров кластеров необходимы для обучения РБНС.
Оптимальные значения эвристических параметров NB, NL и Nz зависят от минимизируемой ЦФ. Алгоритм ГА+НС будет устойчиво работать при варьировании этих параметров в широких пределах, однако некорректные значения приведут к ухудшению производительности алгоритма (недопустимые значения, такие как Nz NL, будут автоматически заменены на ближайшее допустимое). Оценка влияния конкретного параметра на поведение ГА+НС — трудоемкая задача, поэтому ниже даны общие рекомендации по выбору значений NB, NL и Nz.
Параметр NB, по сути, задает ограничение сверху на размер обучающей выборки для НС. В большинстве практических задач значения NB 1000 будет достаточно для корректной кластеризации и настройки весов НС. Точный размер обучающей выборки определяется множеством L, которое обычно увеличивается на каждой следующей итерации. Поэтому первый шаг описанной \
Параметр NL позволяет ограничить область значений ЦФ вокруг хь, которая будет восстанавливаться с помощью НС. Плотность покрытия пространства поиска приближениями падает с увеличением расстояния от лучшего решения. Поэтому меньшие значения NL позволяют построить более точную нейросетевую аппроксимацию ЦФ на меньшей области вокруг х . Большие значения Nz приведут к построению менее точной аппроксимации ЦФ на большей области.
Параметр Nz контролирует размер области поиска вспомогательным ГА. Корректные значения Nz NL позволяют ограничить область поиска независимо от области нейросетевой аппроксимации ЦФ. Например, при большом значении NL и глобальной аппроксимации ЦФ можно сосредоточить поиск прогноза оптимального решения на более узкой области вокруг х .
Тестирование ГА+НС на задаче минимизации функций Растри-гина и Розенброка
Скорее всего, данный эффект возникает из-за дискретности расписания отжига и неизбежных численных ошибок округления, к которым DA достаточно чувствителен. Эти факторы вызывают ошибку в прогнозе температуры деления. Избежать цепного деления можно сильным замедлением охлаждения вблизи момента деления кластера. В рамках данной работы проводился вычислительный эксперимент, когда при условии Г(у+1) Siv) значение Г(у+1) устанавливалось точно равным 5м. Цепного деления в этом случае не происходит, однако величина Г(у+1) - Г(у) по мере уточнения 5(у) быстро стремится к нулю и охлаждение неприемлемо замедляется. Поэтому такой способ на практике не применим.
Для преодоления последствий цепного деления, в алгоритме DA+GA применяется этап слияния близко расположенных центров кластеров на каждой итерации. Алгоритм детерминированного отжига обладает важным свойством, благодаря которому в случае деления кластера С7 раньше времени, центры дочерних кластеров на последующих итерациях будут сближаться друг с другом, стремясь к положению центра родительского кластера, пока выполняется условие Г(у) S\ где S — истинная температура деления кластера С/. Это свойство делает эффективным механизм слияния близко расположенных кластеров в один. В алгоритме DA+GA слияние происходит, если расстояние между ближайшими центрами кластеров меньше порога dm. Значение dm вычисляется на каждой итерации следующим образом: dm - кМпп, где Мпп — среднее расстояние между ближайшими центрами на данный момент, а коэффициент к задается пользователем (во всех экспериментах данной работы использовалось значение к = 0,1).
Важной компонентой алгоритма DA+GA является детектор момента начала «взрывного» деления кластеров. Если такой момент определен, система переходит в режим ускоренного охлаждения с фиксированным количеством кластеров, при этом Г(у+1) = Тма2. Момент взрыва определяется, если выполняется хотя бы одно из следующих условий; количество кластеров последовательно увеличивается в течение Е\ последних итераций алгоритма; количество кластеров возросло более, чем в ШЕ раз в течение последних Е2 итераций. Соответственно, параметры Еь Е2, тЕ задаются пользователем. В данной работе на основе экспериментов с ЦФ Растригина были заданы следующие значения: Ei = 4, Е2 = 3, тЕ = 1,7.
Далее приведено пошаговое описание алгоритма DA+GA. Схема алгоритма представлена на рисунке 2.9. 1. Задать пределы; максимальное количество кластеров Ктах» минимальную температуру Гтіп. 2. Инициализировать: К = 1,/?(Уі) = 1,Т 2Дтах(Сх[у1),текущая итерация у= 1. 3. Вычислить вероятности {р(хд}?=1 с помощью оператора селекции ГА. 4. Для j = 1, ..., К вычислить: У] Еі ХІР( Ї)Р(У№І) p(Jj) где р(уг)ехрЫ(хьу7)2/Л N J ы 5. Если сходимость значений у7} по правилу близости соседних приближений достигнута, сформировать множество центров F(v) = {уг} и перейти к следующему шагу, в противном случае вернуться на шаг 4. 6. Вычислить расстояния между всеми парами центров кластеров и для каждого центра найти ближайший к нему соседний центр. Сформировать множество уникальных пар ближайших центров кластеров. 7. Вычислить среднее расстояние между ближайшими центрами Мпп и порог слияния d = k-Mnn (коэффициент к задается пользователем). 8. Выбрать очередную пару кластеров сі и С2 из полученного множества. Если d(cuc2) d, то удалить центр с2. 9. Повторять шаг 8 до тех пор, пока не будут обработаны все уникальные пары ближайших центров. 10. Если количество кластеров непрерывно увеличивается в течение последних Еі итераций: 7(v) = у(v El+l) зафиксировать количество кластеров. 11. Если количество кластеров возросло более чем в ЖЕ раз в течение последних Е2 итераций: F(v) = Y{v El+x\ зафиксировать количество кластеров. 12. Произвести охлаждение; если количество кластеров зафиксировано, то у(у+\) у(у)а2. если 7 +1) s(v\ то у(у+1) min(S(v) - е, amaxT(v)); в противном случае T(v+1) = Т а. 13. Если Г(у+1) Гтіп, сделать последнюю итерацию для Г = О и выйти. 14. Если К Kmax И количсство кластсров не зафиксировано — проверить следующее условие деления для всех кластеров. Если Г(у+1;) Sj, добавить новый кодовый вектор у +1 = yj+ , р(ук+і) = р(yj)/2, p(yj) = р(Уу)/2 и увеличить К. 15. Увеличить V и перейти к шагу 3. Здесь шаги 1-5 соответствуют алгоритму DA+G , где вероятности предъявления входных векторов рассчитываются опреатором селекции ГА. Шаги 6-9 соответствуют этапу слияния ближайших центров. Шаги 10-11 представляют собой детектор «взрыва».
В среднем DA+GA более ресурсоемок, чем KM+GA, при этом он теоретически полностью детерминирован, т. е. должен всегда еходиться к одному решению. Однако, на практике выполнение этого свойства не гарантируется из-за дискретной природы вычислений. Помимо расписания отжига, на конечный результат оказывает влияние точность вычислений координат центров кластеров на каждой итерации. Т. к. эти координаты рассчитываются итеративно, увеличение точности приводит к значительному росту ресурсоемкости. Поэтому в данной работе сходимость значений координат центров определя
Подбор множителей пористости околоскважинного пространства с использованием ГА+НС
Скорее всего, такое поведение объясняется успешной аппроксимацией параболической формы функции Растригина в большом масштабе с помощью РБНС на первых итерациях, в результате чего ГА направляется в пологую область, содержащую глобальный минимум. В этой области адекватно восстановить поверхность данной ЦФ, содержащей очень большое количество локальных оптимумов (при большом числе параметров), становится сложно и прогнозы на основе РБНС теряют эффективность. В связи с этим динамика оптимизации постепенно становится похожей на таковую у стандартного ГА. Данный факт также объясняет относительно большие значения kt, поскольку они являются результатом усреднения по всем запускам для фиксированного количества параметров ЦФ.
Тем не менее, применение РБНС в экспериментах с 50 и 100 параметрами позволяет скачкообразно уменьшить значение ЦФ в начале оптимизации, за счет чего ее можно остановить гораздо раньше, чем с использованием стандартного ГА. При меньшей размерности входного пространства, ГА+НС и ГА+НС+ДО значительно превосходят стандартный ГА, поскольку нейросете-вой контур дает хорошие прогнозы на протяжении всего цикла оптимизации.
Необходимо также коснуться вопроса ресурсоемкости алгоритмов ГА+НС и ГА+НС+ДО. Как видно из таблиц 3.4 - 3.9 процессорное время, потраченное на гибридный генетический нейросетевой алгоритм, нелинейно изменяется с увеличением количества параметров ЦФ (рисунок 3.8). Максимальное время оптимизации (ГА+НС, 10 параметров функции Растригина) составило более 17 суток. Данный аномальный «выброс», вероятно, связан с изменением характера поведения ГА+НС — эксперимент с 10 параметрами оказался самым «трудным». Теоретически, алгоритм ГА+НС+ДО более ресурсоемок, по сравнению с ГА+НС, поскольку полностью включает в себя все стадии последнего. Однако, на практике, с ростом количества параметров ЦФ, наблюдается обратный эффект, обусловленный, вероятно, динамикой оптимизации и стохастической природой ГА. Кроме того, подобные результаты также косвен но свидетельствуют о том, что на дообучение РБНС тратится сравнительно небольшое время (на данной ЦФ) по отношению к другим стадиям гибридного ГА (кластеризация и обучение РБНС по алгоритму ОРО).
Эта функция была предложена Розенброком в 1960 г. и использовалась впоследствии Де Йонгом [84] для тестирования бинарного канонического ГА. Она представляет собой непрерывную, невыпуклую, унимодальную функцию с минимальным значением, равным нулю, в точке (1, 1, ..., 1). Минимизация функции Розенброка - очень сложная оптимизационная проблема, в том числе и для ГА, поскольку она содержит глубокую параболическую «впадину» вдоль кривой хі = х2і+х очень пологой формы [84]. Ее поверхность для двух параметров представлена на рисунке 3.9.
Результаты экспериментов по минимизации функции Розенброка с различным числом параметров алгоритмами ГА, ГА+НС и ГА+НС+ДО представлены в таблицах 3.4 - 3.9, а также на рисунке 3.7. Во всех экспериментах максимальное число итераций было равно 100, за исключением варианта с двумя параметрами, когда было просчитано 200 итераций.
На функции Розенброка алгоритмы демонстрируют существенно другую динамику (рисунок 3.10), по сравнению с задачей минимизации функции Рас-тригина. ГА+НС и ГА+НС+ДО оказались лучшими во всех случаях, начиная с первых итераций, за исключением варианта с пятью параметрами, когда стандартный ГА нашел незначительно лучшее значение ЦФ по сравнению с ГА+НС. ГА+НС+ДО продемонстрировал превосходство во всех случаях без исключения. Из рисунков видно, что преимущество гибридного алгоритма заключается прежде всего в высокой скорости минимизации ЦФ в начале оптимизации. Этот свойство хорошо проявляется при числе параметров больше трех. При этом эффект от дополнительного обучения РБНС проявилея в еще большей крутизне графика падения значения ЦФ по сравнению с ГА+НС. Характерное замедление скорости оптимизации, особенно заметное в экспериментах с 2, 3, 5 и 10 параметрами, обусловлено тем, что алгоритмы начинают длительный этап уточнения решения в очень пологой области на дне «впадины» функции Розенброка. При этом точность нейросетевых аппроксимаций становится недостаточной и на первый план выходят механизмы эволюционного поиска ГА.
Необходимо отметить эффективность нейросетевых прогнозов в сложных экспериментах с 50 и 100 параметрами ЦФ. Из рисунка 3.10 видно, что наибольшая скорость оптимизации достигается алгоритмами ГА+НС и ГА+НС+ДО в течение первых 10-20 итераций, когда они позволяют резко уменьшить значение ЦФ на 2-3 порядка и значительно опережают стандартный ГА. Кроме того, из таблиц 3.10 - 3.15 следует, что процент хороших нейросетевых прогнозов растет с увеличением размерности решаемой задачи, достигая пика при 50 параметрах для ГА+НС (12,25%) и 10 параметрах для ГА+НС+ДО (17,75%). Это означает, что гладкость нейросетевых аппроксимаций, обеспечиваемая описанными в данной главе методами, позволяет эффективно бороться с проклятием размерности и получать адекватные прогнозы лучшего решения.
