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

ВВЕДЕНИЕ

1. АНАЛИЗ ПРОБЛЕМЫ МНОГОКРИТЕРИАЛЬНОГО 10 ВЫБОРА

1.1 Особенности задач многокритериального выбора

1.2 Анализ способов представления исходной информации 12 для выбора

1.3 Анализ методов принятия решений

2. МОДЕЛЬ ВЫБОРА И АЛГОРИТМЫ ОПТИМИЗАЦИИ АЛЬТЕРНАТИВ НА ОСНОВЕ ОБОБЩЁННЫХ РАНЖИРОВОК

2.1. Формализация описания выбора

2.2. Алгоритм ранжирования альтернатив на основе попарного сравнения

2.3. Алгоритмы поиска множества парето-оптимальных и слабоэффективных решений

2.4. Тестовый пример получения ранжировок альтернатив и поиска парето-оптимальных и слабоэффективных решений

3. АЛГОРИТМЫ СУЖЕНИЯ МНОЖЕСТВА ПАРЕТО-ОПТИМАЛЬНЫХ РЕШЕНИЙ

3.1. Алгоритм выделения из множества Парето решений близких" к идеальной точке (алгоритм ИТ)

3.2 Алгоритм сужения множества Парето на основе последовательного усиления отношения предпочтения алгоритм АС)

Актуальность темы. Многокритериальные задачи принятия решений обычно относят [1, 2] к классу слабоструктурированных, так как часть информации, необходимой для полного и однозначного решения задачи, здесь отсутствует в принципе. При этом многокритериальный характер задач осложняется тем, что количество альтернативных решений зачастую является большим, и поэтому решение задачи затруднительно без применения ЭВМ [2]. Кроме того, часто критерии оценки альтернатив являются не количественными, а качественными, причём последние обычно доминируют.

Сведение указанных задач к «жёстким» оптимизационным (только с количественными критериями и с заданными весовыми коэффициентами значимости), обеспечивая возможность использования хорошо развитого математического аппарата скалярной оптимизации и некоторые другие достоинства, тем не менее, может привносить в постановку задачи заведомо ложную информацию с непредсказуемыми и, может быть, негативными последствиями. При этом используемые методы, как правило, подразумевают введение единой количественной меры и максимизацию соответствующего обобщённого (глобального, скалярного) критерия оптимальности, который часто отождествляется с целью, что может быть неверным, так как критерии характеризуют цель лишь косвенно, иногда лучше, иногда хуже, но всегда приближённо. Не задав всех необходимых ограничений, можно одновременно с максимизацией указанного обобщённого критерия (как единой функции полезности) получить также непредвиденные и нежелательные сопутствующие эффекты. Кроме того, ряд авторов, например [3], отмечают, что, если даже удаётся получить единственное оптимальное решение, то оно может оказаться очень «хрупким», т.е. незначительные изменения в условиях задачи могут привести к выбору существенно отличающихся альтернатив.

Избежать возможных ошибок, связанных с особенностями рассматриваемых задач, позволяет методология системного анализа, отличительной чертой которой является учёт факторов неопределённости и качественных суждений при выборе цели, разработке и обсуждении альтернатив. Поэтому теория и практика принятия решений опираются на системный подход и, в частности, на его принцип «первого лица», в соответствии с которым предпочтения руководителя, или лица принимающего решение (ЛПР), стали провозглашаться основой окончательного выбора [2-11]. Как указывается в [4], тем самым был сделан принципиально важный шаг, который в разрез с известной методологией исследования операций, состоял в отказе от навязывания руководителю единственно возможного решения многокритериальной задачи выбора. Системный анализ является, по существу, объедине нием общей схемы системного подхода и методов оценки и сравнения многокритериальных альтернатив на основе субъективных суждений и включает следующие процедуры [2]:

- определить цели и ресурсы;

- определить альтернативные решения задачи;

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

- выбрать предпочтительные альтернативы.

Анализ работ, в которых задача выбора ставится в каком-либо виде [3,6,8,12-15], показывает, что вышеприведенные процедуры системного анализа характерны для самых разных многокритериальных задач принятия решений и требуют своей технологической (математической и компьютерной) поддержки. В направлении их конкретизации можно выделить следующие этапы:

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

2. Формирование частных критериев, существенных для оценки альтернатив.

3. Формализация исходных предпочтений экспертов, или оценивание альтернатив (в количественной форме или в форме отношений предпочтения).

4. Оптимизация альтернатив.

5. Прогнозирование последствий выбранного решения и собственно принятие решения.

В диссертации будут рассматриваться только этапы 3, 4 с учётом при этом характерных особенностей и возможностей методов, используемых б настоящее время для реализации других этапов. Большое количество публикаций, посвященных научно-технологической поддержке этапов 3, 4 [510, 16], свидетельствует о том, что эти этапы являются в проблематике многокритериального выбора наиважнейшими и базовыми, а также о высокой практической значимости и актуальности выбранной темы диссертации.

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

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

Анализ проблем, возникающих при оценке и оптимизации альтернатив, показывает, что многие из них обусловлены ограниченными возможностями человека в обработке информации при принятии решения [2,5,17-19]. Следовательно, необходима такая структуризация процесса целенаправленного выбора компромиссного варианта, чтобы человек мог проникаться промежуточными результатами решения и проявлять своё «я» на основе должной (учитывающей возможности человека) организации человеко-машинной технологии принятия решений.

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

Для достижения данной цели решаются следующие задачи:

1. Формализация исходных предпочтений экспертов.

2. Разработка алгоритмов и программ многокритериальной оптимизации альтернатив (на основе обобщённых ранжировок).

3. Применение разработанного программного комплекса "МАТОП" в многокритериальных задачах выбора.

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

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

Практическая значимость работы состоит в том, что разработанные в диссертации алгоритмы и комплекс программ "МАТОП" могут быть использованы в разнообразных многокритериальных задачах, встречающихся на практике (проектирование технических систем, оптимизация автотранспортных маршрутов, системы поддержки принятия решений и др.)

Результаты работы использованы при решении следующих задач: проектирование управляемого трансформатора; обоснование структуры авиационного противолодочного комплекса; разработка методики функционального диагностирования системы электроснабжения Ан-124; анализ и составление учебных программ.

Реализация. В рамках данной работы были выполнены заказные (заказчик НТК ВВС) научно - исследовательские работы: «Аттракцион», «Ап-проксимация-96», «Технология-2000», «Классификация».

Доклады и публикации. Материалы работы докладывались на: семинарах адъюнктов и соискателей при Иркутском ВАИИ (1995-1999 г.г.); научно-технических конференциях «Проблемы повышения боевой готовности, боевого применения, технической эксплуатации и обеспечения безопасности полётов летательных аппаратов с учётом климатогеографических условий Сибири, Забайкалья и Дальнего Востока», ИВВАИУ, г. Иркутск, (1995-1999 г.г.); Всероссийской научно-практической конференции «Проблемы оптимизации в человеко-машинных системах», г. Иркутск, 1998 г научно-технической конференции ВАТУ «Проблемы разработки комплексов авиационного оборудования нового поколения», ВАТУ, г. Москва, 1998 г; семинарах «Методы оптимизации и их приложения» при ИДСТУ СО РАН, г. Иркутск (1998 г., 1999 г.), конференции «Ляпуновские чтения», ИДСТУ СО РАН, г. Иркутск, 2001 г.

Основные результаты диссертации опубликованы в 7 печатных работах.

Структура и объем диссертации. Диссертация состоит из 4 разделов, общим объёмом 124 страницы, из них приложение - 20 страниц. В работе содержится 8 таблиц, 25 рисунков, 1 приложение. Список литературы содержит 50 наименований.

ЗАКЛЮЧЕНИЕ

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

Разработанные алгоритмы и комплекс программ "МАТОП" позволяют сформировать в форме обобщённых ранжировок непротиворечивую информацию, исходную для выбора, наиболее простым для ЛПР способом и осуществлять многокритериальную оптимизацию альтернатив как автоматически, так и с участием ЛПР. При этом исключается обязательность использования количественной формы оценивания альтернатив.

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

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

Разработанный комплекс программ "МАТОП" оттестирован на ряде многомерных задач выбора и предназначен для обработки информации на ПЭВМ без повышенных требований к характеристикам машины. Наиболее эффективной областью применения ПК "МАТОП" являются слабоструктурированные многокритериальные задачи выбора, в которых критериальные оценки заданы качественно.

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

1. Алгоритм ранжирования альтернатив на основе попарного сравнения.

2. Алгоритмы поиска множества парето-оптимальных и слабоэффективных решений.

3. Алгоритм выделения парето-оптимальных решений "близких" к идеальной точке (алгоритм ИТ).

4. Алгоритм сужения множества парето-оптимальных альтернатив на основе последовательного усиления отношения предпочтения (алгоритм АС).

5. Программный комплекс многокритериальной оптимизации "МАТОП", реализующий алгоритмы из п.п. 1-4.

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

IUI

1. Simon Н., Newell A. Heuristic problem solving: the next advance in operations research // Operations Research. 1958. - V.6.

2. Ларичев О.И. Наука и искусство принятия решений. М.: Наука, 1979.

3. Перегудов Ф.И., Тарасенко Ф.П. Введение в системный анализ. -М.: Высшая школа, 1989.

4. Ларичев О.И. Объективные модели и субъективные решения. -М.: Наука, 1987.

5. Ларичев О.И., Мошкович Е.М. Качественные методы принятия решений. -М.: Наука. Физматлит, 1996.

6. Ларичев О.И. Теория и методы принятия решений. -М.: Логос, 2000.

7. Березовский Б. А. и др. Многокритериальная оптимизация: математические аспекты. АН СССР, Ин-т проблем управления. М.: Наука, 1989.

8. Трахтенгерц Э.А. Методы генерации, оценки и согласование решений в распределенных системах поддержки принятия решений. // А и Т. 1995. № 4, с. 3-52.

9. Саати Т. Принятие решений. Метод анализа иерархий. -М.: Радио и связь, 1993.

10. Roy В. Methodologie Multicritere d'Aide a la Decision. Paris: Economica, 1985.

11. Монтгомери Г., Свенсон О. Анализ доминантного структурирования проблемы принятия решений с использованием метода мышления вслух// Системы и методы поддержки принятия решений. М.: ВНИИСИ, 1986.-С.16-28.

12. Оптнер СЛ. Системный анали ¡пения деловых и промышленных проблем. -М.: Сов. Радио, 1969

13. Федоренко Н.П. О методах со ю экономического прогнозирования. - В кн.: Методология прогнозирования экономического развития СССР. -М. : Экономика, 1971.

14. Черняк Ю.Н. Системный анализ в управлении экономикой. -М.: Экономика, 1975.

15. Янг С. Системное управление организацией. -М.: Сов. Радио, 1972.

16. Farquhar P., Pratkanis A. Decision Structuring with Phantiom Alternatives. -Carnegie Mellon Univ., 1991.

17. Winterfeldt D. Von, Fisher G. Multi-attribute utility theory: models and assessement procedures. In: Utility probability and human decision making / Ed. D. Wendt, C.A. Vlec. Reidel Publ. Co., 1975.

18. Keeney R. L. Value-Focused Thinking. Harvard University, 1992.

19. Borcherding K., Schmeer S., Weber M. Biases in multiattribute weigth elici-tation // Contributions to Decision Research/Eds. J.P. Caverni, M. Bar-Hillel, F.N. Barron, H. Jungermann.-North-Holland, 1993.

20. Подиновский В. В., Ногин В. Д. Парето оптимальные решения многокритериальных задач. -М.: Наука, 1982.

21. Кемени Д., Снелл Д. Кибернетическое моделирование. М.: Сов. Радио, 1972, с. 192.

22. Теория выбора и принятия решений. Под ред. И.М. Макарова, М.: Наука, 1982.

23. Фишберн П. Теория полезности для принятия решений.-М.: Наука, 1978.

24. Айзерман М. А., Завалишин Н.В., Пятницкий Е.С. Глобальные функции множеств в теории выбора альтернатив. // А и Т, 1997, № 3, с. 111-125.

25. Айзерман М.А., Вольский В.И., Литваков Б.М. Элементы теории выбора. Псевдокритерии и псевдокритериальный выбор. М.: 1994.

26. Zadeh L.A. Fuzzy Setz. Inform, and Control. Vol. 8, June 1965.

27. Борисов В.И. Векторная оптимизация систем. В кн.: Исследование систем. М.: ВИНИТИ, 1971.

28. Салуквадзе М.Е. Задачи векторной оптимизации в теории управления. Тбилиси: Мецниереба, 1975.

29. Нейман Дж. Фон, Моргенштерн О. Теория игр и экономическое поведение. -М.: Наука, 1970.iUj

30. McCrimman К. R. ,Wehrung D. A. Trade -off analysis: indifference and preferred proportion. Workshop on Decision Making with Multiple Conflicting Objectives, NASA. Laxenburg, 1975.

31. Tversky A. Intransitivity of preferences. Psychol. Rev., 1969, vol. 76, N 1.

32. Шапот Д. В. О построении критериев качества технических объектов. -Известия АН СССР. Техническая кибернетика, 1971, № 6.

33. Райфа Г. Анализ решений. М.: Наука, 1977.

34. Интема Д., Клем JI. Оценка многомерных ситуаций с помощью ЦВМ. -Зарубежная электроника, 1967, № 2.

35. Васильев С.Н., Селёдкин А.П. Синтез функции эффективности в многокритериальных задачах принятия решений. // Техническая кибернетика №3, 1980, с. 187.

36. Edwards W. How to use multi attribute utility measurement for social decisionmaking. IEEE Trans. Syst., Man, and Cybern., May 1977, vol. SMC -7, N5.

37. Terry H. Comparative evaluation of performance using multiple criteria. Manag. Sci., 1963, vol. 9, N3.

38. Irving R.H., Love S.F. Evaluation and choice an engineering approach. -Eng. Digest, 1975, N6.

39. Мушик Э., Мюллер П. Методы принятия технических решений. М.: Мир, 1990.

40. Подиновский В.В. Многокритериальные задачи с однородными равноценными критериями. // Журнал вычисл. матем. и мат. физики, 1975, Т. 15, №2, с. 130-141.

41. Подиновский В.В. Многокритериальные задачи с упорядоченными по важности критериями. // А и Т, 1976, №11, с. 118 127.

42. Авен П.О., Мучник И.Б. Ослон А.А. Функциональное шкалирование, агрегирующие интегральные показатели. -М.: Препринт ВНИИ системных исследований, 1986, с. 27.1ич

43. Гуляницкий Л.Ф., Волкович О.В., Малышко С.А. Один подход к формализации и исследованию задач группового выбора. // Кибернетика и системный анализ, 1994. №3 с. 120 - 127.

44. Свами М., Тхуласираман К., Графы, сети и алгоритмы. -М.: Мир, 1984, с.95, с.318-320.

45. Нефедов В.Н. Алгоритмический подход к решению задач теории графов и сетей. М.: МАИ, 1990, с. 4-21.

46. Тихонов В.И., Харисов В.Н. Статистический анализ и синтез радиотехнических устройств и систем. М.: Радио и связь, 1991, с. 25 - 26.

47. Зайчик В.М. Проектирование синхронных машин по заданным электромагнитным нагрузкам //Известия вузов. Электромеханника, 1979, №1, с.40-44.

48. Зайчик В.М. Расчет асинхронных двигателей при заданных значениях ■ электромагнитных нагрузок //Электричество, 1977, №1, с.77-81.

49. Построение множества Парето (пример 1) Множество лидирующих решений х1131. Первоначальный отбор с помощью лидирующего решения: кол-во альтернатив = 2993. Множество Парето: кол-во альтернатив = 2970.

50. Не вошли в множество Парето: х135 х160 х314 х328 х388 х676 х900 х1104 х1283 х1335 х1463 х1558 х1630 х1642 х1809 х1854 х1915 х1952 х2018 х2297 х2311 х2364 х2569 х2572 х2608 х2660 х2677 х2701 х2963 х2984 кол-во альтернатив = 30

51. Кол-во шагов = 30.813.946,1. П.З

52. Алгоритм ИТ (пример 1, на исходном множестве альтернатив)1. Наилучшие решениях1361 х2688 х119 х1444 х1799 х114 х401 х398 х2777 х1099 х1453 х732 х983х252 х2905 х2555 х2897 х770хг\еп) Множество компромиссных решенийх252:1851 х2368

53. Кол-во альтернатив = 1 Кол-во шагов = 3.727.499

54. Алгоритм ИТ (ЛПР) (пример1, на множестве Парето, кол-во альтернатив 2970)

55. Первоначальный отбор: кол-во альтернатив = 200 Множество лидирующих решений: х 1131

56. Компромиссные решения: х1131

57. Конец Кол-во шагов = 8.881.512

58. Алгоритм АС на множестве Парето (пример 1)1 проход

59. Первоначальный отбор: кол-во альтернатив = 200 Множество лидирующих решений: х1131

60. Эквивалентные решения: х1131, х2368

61. Первоначальный отбор: х1131, х2368

62. Множество лидирующих решений: х1131, х2368

63. Компромиссные решения: х1131, х2368