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

В качестве транспортного уровня использовался Gigabit Ethernet. На узле №1 исполнялась управляющая программа которая реализовывала основные алгоритмы оптимизации. Ввиду относительно невысокого расхода вычислительных ресурсов управляющей программой, на всех узлах (№№1-6) исполнялись программы, реализующие вычисление целевых функций. Управляющий узел данной GRID-системы по мере исполнения оптимизационного алгоритма формировал очередь заданий (inputQueue) на исполнение узлами (scheduling). Исполнительные узлы получали задания у управляющего узла (выданное на исполнение задание перемещается в очередь исполняемых, pendingQueue), вычисляли значение целевой функции в заданной точке и пересылали результат управляющему узлу. Управляющий узел формировал очередь исполненных заданий, completedQueue, в которую перемещались задания из pendingQueue и к которой имела доступ функция, реализующая оп53 тимизационный алгоритм. После исполнения запланированных заданий алгоритм оптимизации в зависимости от полученных значений формировал новую очередь заданий и так до завершения алгоритма. Все исследуемые алгоритмы были модифицированы для возможности параллельного исполнения. Степень возможного параллелизма определялась размером данной очереди - чем больше размер очереди запланированных заданий, тем больше возможностей для исполнительных узлов получить задание.

3.2.2 Метод локального градиентного спуска

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

3.2.3 Градиентные методы

Исследовались эксплуатационные параметры трёх градиентных методов - метода координатного спуска, при котором движение пробной точки происходит строго по векторам, параллельным ортам; метод Пауэлла, при котором начальная группа из N итераций проводится по ортогональным векторам, затем производится корректировка базиса и следующие группы по N итераций проводится во новому базису; метод сопряжённых градиентов, при которых и первая и последующие группы итераций проводятся по базису, вычисляемому согласно значениям производных в пробной точке. Все методы требуют вычисления частных производных в пробных точках а так же поиска оптимального значения по направлению. После ряда экспериментов на тестовых функциях было обнаружено, что метод крайне охотно сходится ко всем локальным минимумам (выбор отрезка достаточной длины для методов поиска по направлению немного сглаживал эту проблему) и что для увеличения вероятности решения глобальной задачи требуется значительное количество пробных точек. 3.2.4. Метод роя частиц Реализован классический вариант метода. Для приведённых тестовых функций данный метод для нахождения глобального минимума требовал вычисления значения целевых функций большего на порядки (5-70 раз) по сравнению с градиентными методами. Лучшие результаты были получены при следующих параметрах: * коэффициент скорости затухания = 0.9 * степень локального притяжения = 0.1 * степень глобального притяжения = 0 * степень притяжения элитарных точек = 1.0 * количество заменяемых наихудших точек = 1 55 0 200 400 600 800 1000 0 10 20 30 40 50 60 70 % solved, f32 CG DE Рис. 3.1. Сравнение сходимости алгоритмов сопряжённых градиентов и дифференциальной эволюции для функции f32 0 5000 10000 15000 20000 25000 0 10 20 30 40 50 60 70 point computations, f32 CG DE Рис.

3.2 Сравнение количества вычислений целевой функции алгоритмов сопряжённых градиентов и дифференциальной эволюции для функции f32

В связи с большим количеством вычисления значения пробных функций для тестовых примеров данный метод не применялся для решения основной задачи. После того, как в соревновании алгоритмов остались два - метод сопряжённых градиентов и метод дифференциальной эволюции Из графиков видно, что при одинаковом количестве пробных точек для метода дифференциальной эволюции сходимость много выше а количество вычислений целевой функции много меньше. Например, при количестве пробных точек N = 30 метод ДЕ потребовал в среднем из 1000 испытаний 2308 вычислений целевой функции и сошёлся в 100.0% случаев, то метод СГ потре56 бовал в среднем 10240 вычислений целевой функции и сошёлся всего в 6.6% случаев. Если же за критерий взять одинаковую сходимость, то одинаковую сходимость в 71% дают метод ДЕ, который использует 11 пробных точек и требует 827 вычислений значения функции и метод СГ, который использует 500 точек и требует 221408 вычислений пробной функции. Заметим, что ты поставили методы в не совсем равные условия - функция f32 имеет 102489 локальных экстремумов на области [-600,600][-600,600] а градиентные методы склонны сходиться именно к локальным минимумам. Метод дифференциальной эволюции так же был модифицирован для дискретных параметров.

3.3. Решение обратной задачи сейсморазведки

В качестве тестового варианта обратной задачи сейсморазазведки была выбрана задача с пятью параметрами из раздела 1.1. при следующих значениях параметров: r = 250 n = 7 h = 660 б = 84.4 0 d = 100

3.3.1 Решение переборными методами

Для определения гладкости целевой функции по узлам сетки параметров m были построены графики значений целевой функции для двух постановок задач: * Зафиксированы значения параметров r = 200, n = 7, h = 1000. Два параметра изменяются в следующих границах: 80 6 б 6 90 и 100 6 l 6 300. В качестве d были взяты данные для б = 85 и d = 200. Полученные результаты показаны на рисунке 3.3 - в координатах б, d 57 150 200 250 80 82 84 86 88 90 150 200 250 80 82 84 86 88 90 Рис. 3.3. Целевая функция Px(~m) (слева) и Py(~m) (справа) 5 10 15 20 80 82 84 86 88 90 5 10 15 20 80 82 84 86 88 90 Рис. 3.4. Целевая функция Px(~m) (слева) и Py(~m) (справа) в случае постоянной ширины коридора * Зафиксированы значения параметров r = 200, h = 1000 при фиксированной длине коридора, равной 1800. Параметры б и n изменяются в следующих границах: 80 6 б 6 90, 3 6 n 6 22. В качестве d были взяты данные для б = 85, n = 12. Полученные результаты показаны на рисунке 3.4 - в координатах б, n. Если в двухмерном случае переборные алгоритмы требуют O(n 2 ), при шести параметрах сложность имеет порядок O(n 6 ), что приводит к практически неразрешимой задаче.

3.3.2 Решение градиентными методами

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

3.3.3 Решение методом дифференциальной эволюции

iter calc r б d h n f 4 120 212.7 85.2 100.0 530.3 6 0.000673546 8 240 248.6 85.7 116.4 656.4 7 0.000379036 12 360 248.6 85.7 116.4 656.4 7 0.000379036 16 480 253.0 84.9 100.0 660.0 7 0.000360932 20 600 253.0 84.9 100.0 660.0 7 0.000360932 24 720 250.8 85.3 100.0 678.1 7 0.000350787 28 840 252.6 84.8 100.0 671.3 7 0.000350245 32 960 252.6 84.8 100.0 671.3 7 0.000350245 36 1080 250.8 84.4 100.0 663.8 7 0.000309307 40 1200 250.8 84.4 100.0 663.8 7 0.000309307 44 1320 250.8 84.4 100.0 663.8 7 0.000309307 48 1440 250.8 84.4 100.0 663.8 7 0.000309307 139 4170 252.0 83.9 104.5 660.7 7 0.000308937 278 8340 250.6 84.1 100.9 659.0 7 0.000308730 В таблице представлен результат решения данного варианта задачи методом дифференциальной эволюции на 30 точках. Колонка iter обозначает количество проведённых итераций, calc - количество вычислений целевой функции, f - значение целевой функции. Остальные колонки содержат значения инвертированных параметров. Видно, что уже после 48 итераций достигну59 то достаточно близкое решение. Дальнейшее уточнение решения требует всё более увеличивающегося количества итераций. Одной из проблем данной реализации метода дифференциальной эволюции, которую предстоит разрешить, является выбор автоматического критерия останова.

Заключение

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

Список литературы

1. Чеверда В. А. Восстановление скоростного строения неоднородных сред методом полного обращения волновых сейсмических полей.

2. Аникиев Д.В., Каштан Б.М., Благовещенский А.С., Мулдер В.А. Точный динамический метод для решения обратной задачи сейсмики на основе интегральных уравнений Гельфанда-Левитана.

3. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации.

4. Петров И.Б., Лобанов А.И. Лекции по вычислительной математике.

5. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация.

6. Storn R. and Price K. Differential Evolution -- A Simple and Efficient Adaptive Scheme for Global Optimization over Continuous Spaces.

7. Жданов М.С. Геофизическая электромагнитная теория и методы.

8. Самарский А.А., Вабищевич П.Н. Численные методы решения обратных задач математической физики.

9. Федоренко Р.П. Введение в вычислительную физику.

10. Квасов И.Е. Численное моделирование волновых процессов в гетерогенных твёрдых деформируемых средах.

11. Кабанихин С.И. Обратные и некорректные задачи.

12. Васильев А.Н., Тархов Д.А. Нейросетевое моделирование. Принципы. Алгоритмы. Приложения./ СПб.:Изд-во Политехнического ун-та, 2009. 528 с.

13. Ландау Л.Д.,Лившиц Е.М. Теоретическая физика: Учеб. пособ.: для вузов. В 10 т. Т. VII. Теория упругости.М. ФИЗМАТЛИТ, 2007., 264 с.

14. Storn R. and Price K. Differential Evolution -- A Simple and Efficient Adaptive Scheme for Global Optimization over Continuous Spaces.

15. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация.

16. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации.

17. Васильев А.Н., Тархов Д.А. Нейросетевое моделирование. Принципы. Алгоритмы. Приложения./ СПб.:Изд-во Политехнического ун-та, 2009. 528 с.

18. Натан А.А., Горбачёв О.Г., Гуз С.А. Теория вероятностей.

19. Кормен.Т, Лейзерсон.Ч, Ривест.Р, Штайн.К Алгоритмы. Построение и анализ.

20. Карацуба А., Офман Ю. Умножение многозначных чисел на автоматах // Доклады Академии Наук СССР. 1962. Т. 145. № 2.

21. Полак Э. Численные методы оптимизации. Единый подход.// М. Мир, 1974, 376 с.

22. Деянов Р. Программа минимизации овражной функции многих переменных// Факультет ВМК МГУ им. Ломоносова/ http://www.mathlab.ru/deyanov/article/spiral-21.12.2009.pdf.

Размещено на Allbest.ru