Смешанные системы неравенств в обучаемых методах оптимизации тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Введение

Глава I. Комитетная дискриминация бесконечных множеств

§ I.I. Некоторые свойства комитетных конструкций

§ 1.2. Системы неравенств, связанные с задачами дискриминации

§ 1.3. Отделение квазиполиэдрального множества

Глава П. Синтез обучаемых методов оптимального планирования с использованием процедур дискримина-нтного анализа

§ 2.1. Смешанные системы неравенств и методы их решения

§ 2.2. Комитет несовместной смешанной системы неравенств

§ 2.3. Задача математического программирования, содержащая плохо формализуемые ограничения

§ 2.4. Модель динамики экономической системы при плохо формализуемых ограничениях

§ 2.5. Замечания о вычислительном аспекте предлагаемых алгоритмов

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

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

§ 3.2. Математическая модель

§ 3.3. Метод решения

Настоящая диссертационная работа посвящена вопросам использования методов распознавания образов для моделирования плохо определенных элементов оптимизационных задач.

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

В нашей стране развитие теории распознавания образов связано с именами Э.М.Бравермана, В.Н.Вапника, Ю.И .Журавлева, Н.Г.За-горуйко, М.М.Камилова, Вл.Д.Мазурова, Л.А.Расстригина, В.Н.Фомина, Я.З.Цыпкина и др. Из зарубежных ученых, работающих в этой области, следует отметить Р.Гонсалеса, У.Гренандера, Д.Кэйлора, М.Минского, Н.Нильсона, М.Осборна, Ф.Розенблатта, Р.Такияму, Дж. Ту, С.Эй,блоу.

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

На существование плохо формализуемых факторов и важность их учета в моделях прирожных, технологических, экономических и других процессов, указывается в работах Ю.И.Журавлева [l7j , Вл.Д. Мазурова [I, 32, 33], Н.Н.Моисеева [28, 39], Ю.М.Свирежева [23J и других авторов. В работах Ю.И.Журавлева [ 12, I7J с точки зрения плохой формализуемости рассматриваются задачи распознавания образов и изучается вопрос построения корректных алгоритмов для таких задач.

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

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

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

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

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

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

Таким образом, в связи с построением обучаемых методов оптимизации оказывается необходимым построение процедур дискриминант-ного анализа. В данной работе рассматривается постановка задачи дискриминантного анализа с использованием аппарата линейных неравенств. Систематическое и глубокое изложение теории линейных неравенств приведено в монографии С.НЛерникова [54]. В используемой постановке [3l] задача дискриминантного анализа есть по сути дела задача решения системы линейных неравенств, которая однозначно определяется разделяемыми множествами. Эта система может быть конечной или бесконечной в зависимости от того, конечны или бесконечны разделяемые множества. Совместность этой системы эквивалентна линейной разделимости множеств. В случае линейной не разделимости понятие комитета система неравенств позволяет говорить о комитетном разделении [28].

Понятие комитета системы неравенств было введено в [56, 57] Эйблоу и Кэйлором. Дальнейшее развитие комитетных методов в распознавании образов связано s нашей стране с работами Вл.Д.Мазурова [27] и В.Н.Фомина [53], за рубежом - с исследованиями Н.Ниль-сона (4lJ, М.Осборна [59], Р.Такиямы [60, 6lj . Вл.Д.Мазуровым были, в частности, получены условия существования комитета конечной системы линейных неравенств и сформулированы условия коми-тетной разделимости конечных множеств. Оказывается, всякие два непересекающиеся конечные множества векторов пространства R разделимы комитетом аффинных функций. Вопросы корректности комитетных алгоритмов подробно изучены в работах Ю.И.Журавлева [13-I6J.

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

Во-вторых, обычно в задачах дискриминантного анализа конечные разделяемые множества суть некоторые подмножества множества всех возможных ситуаций. Так, например, если вектор. X&R отражает состояние некоторой системы, X - R - множество всех возможных состояний, то X , как правило, бесконечно. Если все возможные состояния системы делятся на 2 типа, то есть Y-fl^B то множества Й и В обычно тоже бесконечны. Чаще всего эти множества неизвестны, известны лишь конечные их подмножества и комитетная конструкция, разделяющая hi и В1 выбирается в качестве некоторого приближения комитетной конструкции, разделяющей множества й и 6 . В связи с этим встает вопрос о существовании разделяющей комитетной конструкции для двух произвольных бесконечных множеств, то есть вопрос оценки широты класса комитетно разделимых бесконечных множеств.

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

Комитетная дискриминация бесконечных множеств рассматривалась А.И.Кривоноговым в [25]. Некоторым новым результатам в этой области посвящена глава I настоящей работы.

Дадим теперь краткий обзор результатов работы по главам.

ЗАКЛЮЧЕНИЕ

Отметим следующие основные результаты данной работы.

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

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

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

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

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

1. П.И.Балк. Алгоритмы идентификации в задачах регрессионного типа при нулевом медианном значении помехи. Автоматика и телемеханика, 1978, № 12, с.70-82.

2. Булавский В.А. Об одном типе проекционных методов математического программирования. Оптимизация (Новосибирск), 1972, № 5 (22), c.II-12.

3. Булавский В.А. Один специальный алгоритм квадратичного программирования. Оптимизация (Новосибирск), 1972, № 5 (22), с.23-26.

4. Булавский В.А. Методы релаксации для систем неравенств: Учебное пособие. Новосибирск: НГУ: 1981. - 82 с.

5. Вапник В.Н., Червоненкис А.Я. Теория распознавания образов. -М.:Наука, 1974, 416 с.

6. Глушков В.М. 0 диалоговом методе решения оптимизационных задач. Кибернетика, 1975, № 4, с.2-6.

7. Гренандер У. Лекции по теории образов. I. Синтез образов. -М.: Мир, 1979. 384 с.

8. Еремин И.И., Астафьев Н.Н. Введение в теорию линейного и выпуклого программирования. М.: Наука, 1976, 192 с.

9. Журавлев Ю.И. Непараметрические задачи распознавания образов. Кибернетика, 1976, № 6, с.93-103.

10. Журавлев Ю.И. Алгебры над множествами некорректных (эвристических) алгоритмов. Докл. АН СССР, 1977, т.235, й 4, с. 761-763.

11. Журавлев Ю.И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов I. Кибернетика, 1977, № 4, с. 14-21.

12. Журавлев Ю.И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов. 2. Кибернетика, 1977, № 6,с. 21-27.

13. Журавлев Ю.И. Экстремальные алгоритмы в алгебре над некорректными алгоритмами. Докл. АН СССР, 1977, т.237, to 3, с. 509-512.

14. Журавлев Ю.И. Об алгебраическом подходе к решению задач распознавания или классификации. В кн.: Проблемы кибернетики/ Под ред. С.В.Яблонского. М.: Наука, 1978, вып.33, с.5-68.

15. Загоруйко" Н.Г. Классификация задач распознавания образов. -В кн.: Вычислительные системы. Новосибирск: ИМ СО АН СССР, 1966, вып.22, с.3-19.

16. Загоруйко Н.Г. Методы распознавания и их применение. М.: Сов.радио, 1972. - 206 с.20.• Загоруйко Н.Г. Эмпирическое предсказание. Новосибирск: Наука, 1979, 120 с.

17. Казанцев B.C. О решении задач дискриминантного анализа в диалоговом режиме с использованием графического дисплея. В кн.: Классификация и оптимизация в задачах управления. Свердловск, УНЦ АН СССР, 1981, с.31-38.

18. Козинец В.Н. Рекуррентный алгоритм разделения выпуклых оболочек двух множеств. В кн.: Алгоритмы обучения распознаванию образов/Под ред. В.Н.Вапника. М.: Сов.радио, 1972, с.43-50.

19. Крапивин В.Ф., Свирежев Ю.М., Тарко A.M. Математическое моделирование глобальных биосферных процессов. М.: Наука, 1982, 272 с.

20. Кривоногов А.й. Некоторые модификации комитетных алгоритмовв распознавании образов. В кн.: Методы математического программирования и приложения. Свердловск: УНЦ АН СССР, 1979, с.49-55.

21. Кривоногов А.И. О некоторых комитетных конструкциях классификации. В кн.: Методы оптимизации и распознавания образов в задачах планирования. Свердловск, УНЦ АН СССР, 1980, с.92-98.

22. Кривоногов А.й. Некоторые вопросы обоснования комитетных алгоритмов. В кн.: Классификация и оптимизация в задачах управления. - Свердловск, УНЦ АН СССР, 1981, с.39-51.

23. Мазуров Вл.Д. О построении комитета системы выпуклых неравенств. Кибернетика, 1967, № 2, с.56-59.

24. Мазуров Вл.Д. Комитеты систем неравенств и задача распознавания. Кибернетика, 1971, № 3, с.140-146.

25. Мазуров Вл.Д. Применение методов теории распознавания образов в оптимальном планировании и управлении. Труды I Всесоюзной конференции по оптимальному планированию и управлению народным хозяйством. М., ЦЭМИ, 1971, с.49.

26. Мазуров Вл.Д. Об одном итерационном методе планирования, использующем, распознавание образов, для учета плохо формализуемых факторов. Изв. АН СССР (Техн.киберн.), 1973, Из 3, с. 105-107.

27. Мазуров Бл.Д. Теория линейных неравенств и распознавание образов. В кн.: Методы фейеровского типа в выпуклом программировании. Свердловск: ИММ УНЦ АН СССР, 1975, вып.18, с.9-39.

28. Мазуров Вл.Д. Методы математического программирования и распознавания образов в планировании производства. В кн.: Математические методы планирования промышленного производства Свердловск: ИММ УНЦ АН СССР, 1977, вып.22, с.3-27.

29. Мазуров Вл.Д. Плохо формализуемые задачи планирования технико-экономических систем. Свердловск: Средне-Уральское книжное издательство, 1983. - 35 с.

30. Мазуров Вл.Д., Тягунов Л.И. Метод комитетов в распознавании образов. В кн.: Метод комитетов в распознавании образов/ Труды Института математики и механики УНЦ АН СССР, вып.6, Свердловск, 1974, с.10-40.

31. Макаров В.Л. Модели оптимального роста экономики. Экономика и математические методы, 1969, т.5, fe 4, с.563-581.

32. Макаров В.Л., Рубинов A.M. Математическая теория динамики и равновесия. М.: Наука, 1973, 336 с.

33. Моисеев H.H. Элементы теории оптимальных систем. М.: Наука, 1975. 526 с.

34. Моисеев Н.Н. Кибернетическое описание эколого-экономических систем. Кибернетика, 1977, № 6, с.132-145.

35. Никайдо X. Выпуклые структуры и математическая экономика. -М.: Мир, 1972. 520 с.

36. Нильсон Н. Обучающиеся машины. М.: Мир, 1967. - 180 с.

37. Пакет КВАЗАР прикладных программ распознавания образов (версия 2): (Информационные материалы по математическому обеспечению) /Вл.Д.Мазуров, В.С.Казанцев, Н.Г.Белецкий, С.В.Мезенцев, Н.О.Сачков. Свердловск: ИММ УНЦ АН СССР, 1979, 121 с.

38. Плотников С.В. О некоторых вопросах полиэдральности. В кн.: Методы математического программирования и приложения. Свердловск: УНЦ АН СССР, 1979, с.40-48.

39. Плотников С.В. О методах проекции градиента в многоэкстремальных задачах. В кн.: Классификация и оптимизация в задачах управления. Свердловск: УНЦ АН СССР, 1981, с.ПЗ-Пб.

40. Пустыльник Е.И., Сксоев В.В., Чирко М.С. Об одном методе экстраполяции экспертных оценок. Экономика и математические методы, т.XIX, вып.4, 1983, с.716-717.

41. Б.Б.Розин. Статистическое моделирование экономических показателей. Новосибирск: Наука, Сиб.отд., 1976, 136 с.

42. Б.Б.Розин. Теория распознавания образов в экономических исследованиях. М.: Статистика, 1973, 224 с.

43. Сачков Н.О. Смешанные системы неравенств в комбинированных методах математического программирования. В кн.: Всесоюзная конференция. Динамическое управление, тезисы докладов, Свердловск: УНЦ АН СССР, 1979, с.229-230.

44. Сачков Н.О. Решение смешанных систем неравенств. В кн.: Методы оптимизации и распознавания образов в задачах планирования. Свердловск: УНЦ АН СССР, 1980, с.99-105.

45. Сачков Н.О. Учет плохо формализуемых ограничений в одной модели экономической динамики. В кн.: Классификация и оптимизация в задачах управления. Свердловск: УНЦ АН СССР, 1981,с.57-63.

46. Табак Д., Куо Б. Оптимальное управления и математическое программирование. М.: Наука, 1975. - 280 с.

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

48. Фомин В.Н. Математическая теория обучаемых опознающих систем. Л.: ЛГУ, 1976. - 236 с.

49. Черников С.Н. Линейные неравенства. М.: Наука, 1968, 476 с.

50. Черников С.Н. Свертывание конечных систем линейных неравенств. -Допов!д1 АН УрССР, 1969, № I, с.32-35.

51. Ablow С.М., Kaylor D.J. A committee solution of the pattern recognition problem.-IEEE Trans. Inform. Theory, 1965, vol. IT-11, N0.3, p.453-455

52. Ablow G.M., Kaylor D.J. Inconsistent homogenous linear inequalities.-Bull. Amer. Math. Soc., 1965, vol.71, No.5 p.724

53. Takiyama R. A general method for training the committee machine.-Pattern Recognition, 1978, vol.10, No.4, p.255-259

54. Takiyama R. A committee machine with a set of networks composed of two single-threshold elements as committee members.-Pattern Recognition, 1982, vol.15, No.5, p.405-412