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

ВВЕДЕНИЕ стр.

ГЛАВА I. ОПТИМИЗАЦИЯ ФУНКЦИЙ ПОИСКОВЫМИ МЕТОДАМИ ПО ЮМЕРЕНШМ С КОРРЕЛИРОВАННОЙ ПОМЕХОЙ

§ I.I. О поисковых процедурах оптимизации

§ 1.2. Примеры задач поисковой оптимизации

§ 1.3. Поисковые методы оптимизации (обзор)

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

Выводы

ГЛАВА 2. РОБАСТБЫЙ ПОИСКОВЫЙ АЛГОРИТМ В УСЛОВИЯХ паж С ИЗВЕСТНЫМИ КОРРЕЛЯЦИОННЫЕ СВОЙСТВАМИ

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

§ 2.2. Структура поискового алгоритма. Состоятельность последовательности оценок

§ 2.3. Оптимальный на классе алгоритм случайного поиска

§ 2.4. Реализуемый оптимальный на классе поисковый алгоритм при помехе с известной функцией корреляции

§ 2.5. О "критериальном" алгоритме случайного поиска

§ 2.6. Моделирование работы поискового алгоритма при 68 помехе с известной корреляцией Выводы

ГЛАВА 3. РОБАСТНАЯ ПОИСКОВАЯ ПРОЦЕДУРА ОПТИМИЗАЦИИ ПРИ ПОМЕХЕ С НЕИЗВЕСТНЫ!,Ж КОРРЕЛЯЦИОННЫМ СВОЙСТВАМИ

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

§ 3.2. Состоятельность последовательности оценок, построенных поисковыми процедурами

§ 3.3. Оптимальный на классе поисковый алгоритм.

Предельные возможности процедур оптимизации

§ 3.4. Робастный поисковый алгоритм

§ 3.5. Реализуемый, оптимальный на классе поисковый 92 алгоритм

§ 3.6. Моделирование работы робастного поискового алгоритма при помехе с неизвестной функцией корреляции 100 Выводы

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

§ 4.1. Оценивание максимумов спектров стационарных Ю? случайных процессов

§ 4.2. Оптимизация модели производительности труда 109 Выводы

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

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

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

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

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

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

- построен робастный поисковый алгоритм оптимизации функции по её измерениям с помехой неизвестной корреляции;

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

Практическая ценность работы заключается в том, что:

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

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

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

Реализация результатов работы осуществлялась в виде программ для ЭВМ на алгоритмическом языке Фортран-1У, разработанных для решения конкретных практических задач.

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

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

Результаты применения подтверждаются соответствующими актами о внедрении.

Апробация результатов. Основные результаты были доложены:

- на Всесоюзной конференции "Теория адаптивных систем и ее применения", г. Ленинград, май, 1983 г.;

- на ХХУШ конференции молодых ученых Института проблем управления, г. Москва, май, 1982 г.;

- на XXIX конференции молодых ученых Института проблем управления, г. Москва, май, 1983 г.;

- на семинарах под руководством чл.-корр. АН СССР Я.З.Цыпки-на в лаб. 7 Института проблем управления.

Автором опубликовано 9 научных работ, из них 5 по теме диссертации.

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

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка цитируемой литературы ( 55" названии), приложения и содержит (без приложения) ^29 страниц печатного текста, 5" таблиц, 50 рисунков.

- 121 -ВЫВОДЫ К ГЛАВЕ 4

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

- в экономико - математических исследованиях;

- в химической, лёгкой и др. промышленностях.

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

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

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

- 122 -ЗАМКЯЕНИЕ

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

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

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

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

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

6. Разработанными поисковыми методами решены две прикладные задачи: определения положений и значений максимумов спектров случайных процессов и оптимизации модели производительности

- 123 труда для треста "Металлургпрокатмонтаж". Установлено, что полученные в работе поисковые алгоритмы оптимизации, эффективны для решения практических задач различного характера.

1. Айзерман М.А., Браверман Э.М., Розоноэр Л.И. Метод потенциальных функций в теории обучения машин. - М.: Наука, 1970. - 384 с.

2. Андерсон Т. Статистический анализ временных рядов. М*: Мир, 1976. - 755 с.

3. Бородин А.Н. Процедура стохастической аппроксимации при наблюдениях, удовлетворяющих условию слабой зависимости. Теория вероятностей и ее применение, т. ХХ1У, вып. I, 1979. с. 34-51.

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

5. Ибрагимов И.А., Линник Ю.В. Независимые и стационарно связанные величины. М.: Наука, 1965. - 524 с.

6. Каплинский А.И., Песин A.M. Об одном способе построения рандомизированных алгоритмов. Автоматика и телемеханика. 1982, № 12, с. 65-75.

7. Каплинский А.И., Лимарев А.В. 0 структуре рандомизированных алгоритмов решения экстремальных задач. В кн.: Адаптация в сложных системах управления. Воронеж: Воронежский политехнический институт, 1978, с. 3-12.

8. Козленко Н.И., Песин A.M., Панова Л.В. Вероятностные характеристики оценки сообщения дифференциальной импульсно-кодо-вой модуляции. М. Радиотехника и электроника, том ХХУ,1. JS 9, 1980, с. 1873-1880.

9. Ланкастер П. Теория матриц. М.: Наука, 1978. - 280 с.

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

11. Лоэв М. Теория вероятностей. М.: Иностранная литература, 1962. - 719 с.

12. Немировский А.С. О процедуре стохастической аппроксимации при зависимых шумах. Техническая кибернетика. Известия АН СССР, 1981, В I, с. 14-25.

13. Песин A.M. О поисковых алгоритмах оптимизации при наличии коррелированных помех. В сб.: Моделирование и оптимизация сложных систем. Воронеж: Воронежский политехнический институт, 1982, с. 52-57.

14. Песин A.M. Робастный поисковый алгоритм оптимизации в коррелированных шумах. В кн.: Тезисы докладов Всесоюзной конференции "Теория адаптивных систем и ее применения", сост. в апреле 1983г., Ленинград. - 118 с.

15. Позняк А.С., Цыпкин Я.З. Оптимальные и робастные алгоритмы случайного поиска. В сб.: Приборостроение и автоматический контроль, вып. 2. - М.: Машиностроение, 1982, с. 9-38.

16. Поляк Б.Т., Цыпкин Я.З. Робастные алгоритмы адаптации. -Автоматика и телемеханика. 1980, В 10, с. 91-97.

17. Поляк Б.Т., Цыпкин Я.З. Оптимальные алгоритмы критериальной оптимизации в условиях неопределенности. Докл. АН СССР. т.273, №2, с.315 - 318, 1983 г.

18. Поляк Б.Т., Цыпкин Я.З. Псевдоградиентные алгоритмы адаптации и обучения. Автоматика и телемеханика. 1973, № 3,с. 45-68.

19. Поляк Б.Т., Цыпкин Я.З. Оптимальные псевдоградиентные алгоритмы адаптации. Автоматика и телемеханика. 1980, № 8,с. 74-84.

20. Поляк Б.Т., Цыпкин Я.З. Огрубленный метод максимального правдоподобия. В сб.: Динамика систем, вып. 12, Изд-во Горьковского Гос. университета, 1977, с. 22-46.

21. Растригин Л.А. Случайный поиск в процессах адаптации. М.: Зинатне, Рига, 1973. - 129 с.

22. Растригин Л.А. Случайный поиск. Рига: Зинатне, 1965.

23. Ройтенберг Я.Н. Автоматическое управление. М.: Наука, 1981. - 447 с.

24. Розанов Ю.А. Стационарные случайные процессы. М.: Физмат-гиз, 1963. - 284 с.

25. Рытов С.М. Введение в статистическую радиофизику. М.: . Наука, 1966. - 404 с.

26. Сейдж Э., Меле Дж. Теория оценивания и ее применение в связи и управлении. М.: Связь, 1976. 494 с.

27. Справочник по теории вероятностей и математической статистике. Под ред. академика АН УССР Королюка B.C. Киев: Наукова думка, 1978. - 581 с.

28. Тиман А.Ф. Теория приближения функций действительного пфе-. менного. М., Физматгиз, I960. 624 с.

29. Тихонов А.Н., Арсенин В.Я. Методы решения некорректных задач. М.: Наука, 1974.

30. Фомин В.Н., Фрадков А.Л., Якубович В.А. Адаптивные управление динамическими объектами. М., Наука, 1981. 447 с.

31. Фурунжиев Р.И. Автоматизированное проектирование колебательных систем.Минск: Высшая школа, 1977. 451 с.

32. АН СССР.1981, т. 258, В 6, с. I33Q-I333.

33. Цыпкин Я.З., Позняк А.С. Оптимальные поисковые алгоритмы стохастической оптимизации. Докл. АН СССР. 1981, т. 260,1. Л 3, с. 550-553.

34. Цыпкин Я.З., Позняк А.С., Песин A.M. Поисковые алгоритмы критериальной оптимизации в условиях неоврэдедеанрсти . Докл. АН СССР, т. 270,№ 3, с. 565-568.

35. Цыпкин Я.З., Позняк А.С. Рекуррентные алгоритмы оптимизации в условиях неопределенности. В кн.: Итоги науки и техники, серия "Техническая кибернетика", 1983, т. 16, с. 3-70.

36. Цыпкин Я.З. Адаптация и обучение в автоматических системах. М.: Наука, 1968.

37. Шкхофф П. Основы идентификации систем управления. Оценивание параметров и состояния. М.: Мир, 1975. - 683 с.

38. Балан В. А. Экономико математические модели производительности труда. - М.; Наука, 1979. - 126 с.

39. Климов Н.А. Производительность и интенсивность труда при социализме. М.: Изд - во МГУ, 1971. - НО с.

40. Сущинский М.М. Спектры комбинационного рассеяния молекул и кристаллов. М.: Наука, 1969.

41. Ahdelhamid S.N. Transformation of observations in stohastic approximation. The Annals of Statistics, v.1, H6, pp. 1158 1174» 1979.

42. Blum J.R. Multidimensional stochastic approximation method. Ann. Math. Stat., v.25, ИЗ» pp. 737 744, 1954.47 ^ Burkholder D.L. On a class of stochastic approximation procedures. Ann. Math. Stut., v.27» pp. Ю44 -1059, 1956.

43. Chung K.L. On stochastic approximation methods, Ann. Math. Stat., v.25, pp. 463 483, 1954.49# I'arden D.C. Stochastic approximation with correlated data. IEEE Trans, on Inform, theory, v.IT 27, N1, pp. 105 - 113, Jan. 1981.

44. Kiefer J., Wolfowitz J. Stochastic estimation of the maximum of a regression function. Ann. Math. Stat., v.23, pp. 462 466, 1952.

45. Kushner H.J., Clark D.S. Stochastic approximation for constrained and unconstrained systems. Math. Sciences, v.26, New York, Springer, 1978.

46. Ljung L. Analysis of recursive stochastic algorithms, IEEE Trans. Automat. Gontr., v. AC 22, pp. 551 - 575, Aug. 1977.

47. Robbins H., Siegmund D., A convergence theorem for non negative almost supermartingales and some applications. Optimal methods in statistics, Academic Press., New York and London, pp. 233 258, 1971.

48. Sacks J. Asymptotic distribution of stochastic approximation procedures, Ann. Math. Stat., v.29» pp. 373 -405, 1958.

49. Solo V. Stochastic approximation with depend noise.

50. Stochastic processes and their application ( Holland ), v.13, pp. 157 170, 1982.