Математическая морфология.
Электронный математический и
медико-биологический журнал. - Т. 8. -
Вып. 4. - 2009. - URL:
http://www.smolensk.ru/user/sgma/MMORPH/TITL.HTM
http://www.smolensk.ru/user/sgma/MMORPH/N-24-html/TITL-24.htm
http://www.smolensk.ru/user/sgma/MMORPH/N-24-html/cont.htm
УДК 519.816
ПРОБЛЕМА ФОРМИРОВАНИЯ НАЧАЛЬНОГО МНОЖЕСТВА
АЛЬТЕРНАТИВ
Ó 2009 г. Балашов О. В.
Рассмотрен
вопрос формирования начального множества альтернатив для решения задачи выбора.
Предлагается комбинированный подход, сочетающий в себе использование хранилищ
данных (знаний) по какой-либо конкретной предметной области и морфологический
анализ вариантов.
Ключевые
слова: начальное множество альтернатив, задачи выбора
Введение. Задача принятия решений (ПР) возникает, когда
присутствует несколько вариантов действий (альтернатив) для достижения заданного
или желаемого результата. При этом требуется выбрать наилучшую в определенном
смысле альтернативу.
Общую постановку задачи принятия решений, понимаемой
обычно как задачу выбора из некоторого множества, можно сформулировать следующим
образом [1]. Пусть X – множество альтернатив, Y – множество последствий
(исходов, результатов). Предполагается существование причинной связи между
выбором некоторой альтернативы xiÎX и наступлением соответствующего исхода yjÎY. Кроме того, предполагается наличие механизма оценки
качества такого выбора – обычно оценивается качество исхода. Требуется выбрать
наилучшую альтернативу, для которой соответствующий исход имеет наилучшую
оценку качества.
Нетрудно видеть, что в приведенной постановке задача
ПР складывается из двух частных задач: задачи формирования начального множества
X альтернатив и задачи выбора наилучшей альтернативы.
Следует указать, что вторая из этих задач может быть
решена различными методами, широко представленными в литературе (см., например,
[2-11]), в то время, как первую задачу можно рассматривать как проблему, не
имеющую до настоящего времени какого-либо полностью удовлетворительного
решения. Исследованию этой проблемы и посвящена представляемая статья.
1. Состояние
вопроса. Изучение литературы привело
к установлению только весьма ограниченного числа источников, в которых подчеркивалась
бы важность или предлагались какие-либо пути решения рассматриваемой проблемы.
Приведем основной материал из этих источников.
Так, в монографии [12] отмечается следующее:
"Лица, принимающее решение часто (к сожалению) не
осознают важности составления списка альтернатив. Совершенно очевидно, что, в
конечном счете, может быть выбрана не самая лучшая альтернатива из числа рассматриваемых.
В этом смысле качество выбора ограничено качеством альтернатив. Исчерпывающий
список имеющихся альтернатив оказывает большую помощь при принятии решений.
Принятие решений есть выбор одной из альтернатив, и составление их списка является
неотъемлемой частью этого процесса. В некотором смысле составление списка альтернатив совершенно
аналогично определению задачи при инженерном анализе. Когда альтернативы
неопределенны, список их неполон или даже непродуман, принять решение
невозможно. Однако если альтернативы четко перечислены, задача больше не
является неосязаемой. Теперь мы уже имеем совершенно конкретную задачу выбора
одной из перечисленных альтернатив. Составление списка альтернатив перед
принятием решений в основном является творческим этапом. Здесь с успехом можно
применять многое методы получения новых полезных идей… ."
В книге [9] указывается, что генерацию возможных
решений (альтернатив) можно реализовать посредством:
а) программной реализации аналитических моделей,
б) с использованием экспертных систем,
в) генерации сценариев путем комбинации различных
операций, заданных ЛПР (лицом, принимающим решение) или взятых из базы данных,
г) и, наконец, используя подход, получивший название
ситуационного управления.
В цитируемой работе отмечено, что генерации решений
можно подразделить на:
·
неожиданные,
принципиально новые, новаторские решения, которые пока компьютер делать не в
состоянии;
·
решения, основывающиеся
на типовых сценариях, по аналогии, на основе комбинации известных частных
решений; генерация таких решений доступна вычислительной машине.
Решение проблемы генерации альтернатив в [9]
предлагается делать, на основе разновидности экспертного подхода, известной как
техника когнитивных карт.
Напомним,
что когнитивная карта (карта познания) – это вид математической модели,
представленной в виде графа и позволяющей описывать субъективное восприятие
человеком или группой людей какого-либо сложного объекта, проблемы или
функционирования системы. Когнитивная карта предназначена для выявления
структуры причинных связей между элементами системы, сложного объекта,
составляющими проблемы и т.п. и оценки последствий, происходящих под влиянием
воздействия на эти элементы или изменения характера связей [8, 9].
Сама методика построения и анализа когнитивных карт в
[9] рассмотрена как будто бы подробно, но самый главный, как представляется
этап ее – выявление основных факторов, влияющих на решение проблемы – остается
"за кадром", предполагается, по умолчанию, что он реализуется ЛПР,
экспертом, или группой экспертов.
В этой связи более разработанным представляется
подход, изложенный в монографии [3] и представляющий собой следующую группу алгоритмов.
Алгоритм 1. Формирование начального множества
альтернатив с помощью экспертного
оценивания. В данном случае привлекаются N экспертов, действующих независимо
друг от друга. Каждому эксперту предлагается составить свой список альтернатив
Xj. Полученные множества альтернатив объединяются, образуя, таким
образом, начальное множество альтернатив:
. (1)
Алгоритм 2. Формирование начального множества
альтернатив с помощью модели. Здесь предполагается, что непосредственное
порождение множества X с помощью экспертов невозможно, но известен регулярный
способ (модель) порождения любой альтернативы xi. Например, пусть заданы
правила построения возможных расписаний авиарейсов, в то же время число всех
вариантов расписаний настолько велико, что их совместный анализ эксперту
провести не удается. Параметры модели заранее не известны, но могут быть найдены
экспертами.
Алгоритм 2 реализуется следующей последовательностью
шагов:
1) с помощью экспертизы определить числовые параметры
модели;
2) используя модель, найти множество возможных
альтернатив xi;
3) сформировать множество X = {xi}.
Алгоритм 3. Морфологический анализ. Морфологический
метод предполагает представление каждой альтернативы в виде составных частей
(компонент). Под компонентами понимаются части, на которые условно разделена
альтернатива. Компонентами могут быть как некоторые измеряемые параметры, так и
отдельные структурные части альтернативы. Например, в задаче выбора комплекса
технических средств для создания автоматизированной системы управления
альтернативу можно представить с помощью следующих компонент: тип ЭВМ, число
периферийных устройств, системное устройство ввода, системное устройство
вывода, математическое обеспечение.
Пусть множество возможных вариантов i-й компоненты обозначено через Хi
= {хi1, хi2, ..., хiki} (
). Тогда множество альтернатив представимо в виде
X = Х1 ´ X2 ´ ... ´ Хn. (2)
Такое представление задает конкретную модель
порождения возможных альтернатив.
Алгоритм 4. Формирование начального множества
альтернатив для иерархических систем. Путь альтернативы разбиты на части,
иерархически связанные межу собой. Например, допустимый план развития отрасли
основан на допустимых планах предприятий, а планы предприятий – на планах
цехов. Для формирования X предлагается использовать иерархическую экспертизу,
которая представляет собой последовательность экспертиз, где каждая экспертиза
использует результаты предыдущих.
Предлагается два способа проведения иерархической
экспертизы. Первый заключается в проведении экспертизы снизу вверх. Сначала проводят
экспертизы на самом низком уровне иерархии. Их результаты служат исходными
данными для проведения экспертиз на следующем уровне и т.д. Применительно к
планированию это означает, что сначала определяют допустимые планы цехов, на их
основе формируют допустимые планы предприятий и затем планы развития отрасли.
Второй способ заключается в проведении экспертизы
сверху вниз. Здесь результаты экспертизы более высокого уровня служат
ограничениями при определении допустимых альтернатив более низкого уровня.
Применительно к планированию сначала определяют допустимые планы развития отрасли,
затем допустимые планы предприятий и допустимые планы цехов. Допустимыми для
предприятия будут только такие планы, которые обеспечивают допустимость планов
отрасли.
Алгоритм 5. Формирование бесконечного начального
множества альтернатив. Пусть альтернативы являются точками из Еm.
Тогда множества возможных допустимых альтернатив образуют некоторые области в Еm.
Формирование начального множества альтернатив сводится к определению границ
этих областей. Отметим, что данный алгоритм применим, только в случае, если
альтернативы можно каким-то образом характеризовать количественно.
2. Анализ
возможных подходов к решению поставленной проблемы. Детальное изучение рассмотренных источников
позволяет установить следующее:
1) альтернативы могут быть как простыми (атомарными,
неразложимыми), предполагающие только один этап управляющего действия, так и
сложными, многоэтапными (или многоступенчатыми) – типа сценариев, состоящими из
последовательности элементарных (атомарных) действий или этапов;
2) из предыдущего пункта следует, что для формирования
начального множества альтернатив необходимо сформировать начальное множество
элементарных действий, которое может, как совпадать, так и не совпадать – в
случае альтернатив-сценариев – с множеством элементарных действий;
3) множество элементарных действий может быть
сформировано с помощью следующих подходов:
- экспертного с индивидуальной (независимой) работой
экспертов [3, 13],
- экспертного с коллективной работой экспертов
(мозговой штурм, "круглый стол") [13],
- с использованием имеющихся (электронных) хранилищ
данных или баз знаний,
- с использованием литературных источников.
4) при наличии полученного каким-либо способом
множества элементарных действий начальное множество альтернатив может быть
сформировано:
- экспертным путем с индивидуальной (независимой)
работой экспертов,
- с использованием морфологического подхода (см.
алгоритм 3, а также алгоритм в [14]).
Достоинства и недостатки приведенных вариантов:
1)
экспертные подходы,
особенно при коллективной работе экспертов, как представляется, могут быть
весьма продуктивными в смысле формирования максимально полного начального
множества альтернатив, и это – их достоинство, но, в то же время, ограничением
данных подходов может служить трудность в подборе компетентных экспертов и сложность
автоматизации в проведении экспертизы;
2)
использование
литературных источников – процесс, не являющийся автоматизированным и
достаточно медленный (продолжительный по времени); генерировать новые идеи
(альтернативы) этот подход вряд ли позволит, поэтому сфера его применения – сравнительно
несложные прикладные задачи;
3)
комбинация использования
электронных хранилищ данных и морфологического анализа, скорее всего, обеспечит
формирование достаточно полного начального множества альтернатив, и в то же
время поддается полной автоматизации.
Заключение. Изложенное позволяет сделать следующий общий вывод:
наиболее перспективным для формирования начального множества альтернатив является
комбинированный подход, сочетающий в себе использование хранилищ данных
(знаний) по какой-либо конкретной предметной области и морфологический анализ
вариантов. Для реализации такого подхода необходимо:
а) развернуть работы по созданию соответствующих
хранилищ данных (знаний);
б) разработать программное обеспечение для
автоматизации процесса генерации альтернатив (с использованием атомарных
действий из хранилищ данных и морфологического анализа и синтеза вариантов).
Литература
1. Черноруцкий И.Г. Методы принятия решений. Спб.:
БХВ-Петербург, 2005.
2. Кини Р.Л., Хайфа Х. Принятие решений при многих
критериях предпочтения и замещения. М.: Радио и связь, 1981.
3. Теория выбора и принятия решений / И.М. Макаров, Т.М.
Виноградская, А.А. Рубчинский, В.Б. Соколов. М.: Наука, 1982.
4. Науман Э. Принять решение – но как? М.: Мир, 1987.
5. Вентцель Е.С. Исследование операций. Задачи, принципы,
методология. М.: Наука, 1988.
6. Белкин А.Р., Левин М.Ш. Принятие решений:
комбинаторные модели аппроксимации информации. М.: Наука, 1990.
7. Саати Т. Принятие решений. Метод анализа иерархий. М.:
Радио и связь, 1993.
8. Силов В.Б. Приятие стратегических решений в нечеткой
обстановке. М.: ИНПРО-РЕС, 1995.
9. Трахтенгерц Э.А. Компьютерная поддержка принятия
решений. М.: СИНТЕГ, 1998.
10. Андрейчиков А.В., Андрейчикова О.Н. Анализ, синтез,
принятие решений в экономике. М.: Финансы и статистика, 2000.
11. Ларичев О.И. Теория и методы принятия решений, а также
Хроника событий в Волшебных странах: Учебник. М.: Логос, 2000.
12. Диксон Дж. Проектирование систем: изобретательство,
анализ и принятие решений. М.: Мир, 1969.
13. Дюк В., Самойленко А. Data Mining: учебный курс. Спб.:
Питер, 2001.
14. Половинкин А.И. Основы инженерного творчества. М.: Машиностроение, 1988.
PROBLEM OF FORMATION INITIAL SETS OF ALTERNATIVES
Balashov O. V.
The question of formation of initial set of alternatives of the decision
of a problem of a choice is considered. The combined approach combining use of
storehouses of given (knowledge) on any concrete data domain and the morphological
analysis of variants is offered.
Key words: initial set of alternatives, problem of a choice.
Сведенья об авторе
Балашов Олег
Валентинович, 1955 г.р., кандидат технических наук, старший научный сотрудник,
доцент кафедры прикладной информатики и математики Смоленского филиала
Российского университета кооперации.
Адрес:
- рабочий: 214018, г.
Смоленск, проспект Ю. Гагарина, д. 58;
- домашний: 214012, г.
Смоленск, ул. Толмачева, д. 5-а, кв. 72.
Телефон:
- раб. (4812) 65-84-49
- дом. (4812) 21-94-39
Область научных
интересов:
интеллектуальные информационные системы, системы поддержки принятия решений, нечеткая
логика, теория возможностей. Автор более 70 научных работ, в том числе двух
монографий.
Кафедра прикладной информатики и математики
Смоленский филиал Российского университета кооперации
Поступила в редакцию 23.12.2009.