Моделирование и принятие решений в ГИС

Территория рекламы

Лекция 4. Моделирование и принятие решений в ГИС

1. Нечеткие множества

2. Методы оптимизации

1. Нечеткие множества

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

Значительное продвижение в этом направлении сделано 30 лет тому назад профессором Калифорнийского университета (Беркли) Лотфи А. Заде. Его работа «Fuzzy Sets», появившаяся в 1965 г. в журнале Information and Control, №8, заложила основы моделирования интеллектуальной деятельности человека и явилась начальным толчком к развитию новой математической теории.

Что же предложил Заде? Во-первых, он расширил классическое канторовское понятие множества, допустив, что характеристическая функция (функция принадлежности элемента множеству) может принимать любые значения в интервале (0,1) ), а не как в классической теории только значения 0 либо 1. Такие множества были названы нечеткими (fuzzy). 

Им были также определены операции над нечеткими множествами и предложены обобщения известных методов логического вывода.

Рассмотрим некоторые основные положения теории нечетких множеств.

Пусть Е - универсальное множество, х - элемент Е, а К - некоторое свойство. Обычное (четкое) подмножество А универсального множества Е, элементы которого удовлетворяют свойству R, определяется как множество упорядоченных пар , где  - характеристическая функция, принимающая значение 1, если х удовлетворяет свойству R, и 0 - в противном случае.

Нечеткое подмножество отличается от обычного тем, что для элементов х из Е нет однозначного ответа «да - нет» относительно свойства R. В связи с этим нечеткое подмножество А универсального множества Е определяется как множество упорядоченных пар , где  - характеристическая функция принадлежности (или просто функция принадлежности), принимающая значения в некотором вполне упорядоченном множестве М (например, М = [0,1] ). Функция принадлежности указывает степень (или уровень) принадлежности элемента х подмножеству А. Множество М называют множеством принадлежностей. Если М = {0,1}, то нечеткое подмножество А может рассматриваться как обычное или четкое множество.

Пусть М = [0, 1] и А - нечеткое множество с элементами из универсального множества Е и множеством принадлежностей М.

Величина называется высотой нечеткого множества А. Нечеткое множество А нормально, если его высота равна 1, т. е. верхняя граница его функции принадлежности равна 1 (=1). При < 1 нечеткое множество называется субнормальным.

Нечеткое множество пусто, если  Непустое субнормальное множество можно нормализовать по формуле

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

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

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

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

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

Нечеткая переменная характеризуется тройкой <, X, А>, где

- наименование переменной;

X - универсальное множество (область определения а);

А - нечеткое множество на X, описывающее ограничения (т. е, ) на значения нечеткой переменной .

Лингвистической переменной называется набор <, Т, X, G, М>,  где

- наименование лингвистической переменной;

Т - множество ее значений (терм-множество), представляющих собой наименования нечетких переменных, областью определения каждой из которых является множество X. Множество Т называется базовым терм-множеством лингвистической переменной;

G - синтаксическая процедура, позволяющая оперировать элементами терм- множества Т, в частности генерировать новые термы (значения). Множество ТС(Т), где С(Т) - множество сгенерированных термов, называется расширенным терм-множеством лингвистической переменной;

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

Введя понятие лингвистической переменной и допуская, что в качестве ее значений (термов) выступают нечеткие множества, фактически позволяет создать аппарат описания процессов интеллектуальной деятельности, включая нечеткость и неопределенность выражений.

2. Методы оптимизации

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

Таким образом, задачи поддержки принятия решений, относящиеся к одним из основных при моделировании в ГИС, в той или иной степени связаны с выбором целевых функций и математическим программированием.

2.1. Линейное программирование

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

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

Постановка задачи линейного программирования

Найти максимум функции

при ограничениях:

Такая форма задачи линейного программирования называется канонической формой.

Не ограничивая общности, можем считать, что все числа  Этого можно добиться, умножая ограничения, где  на -1.

Множество допустимых решений задачи

X = {}

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

Крайней точкой выпуклого множества X называется точка X, которая не может быть выражена в виде выпуклой комбинации других точек X, .

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

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

1. Определение начального базисного решения.

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

2.2. Задача безусловной оптимизации

Общая постановка задачи безусловной оптимизации представляется следующим образом.

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

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

Для определенности рассмотрим задачу поиска безусловного локального минимума:

Численное решение этой задачи, как правило, связано с построением последовательности {} точек, обладающих свойством убывания целевой функции:

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

Начальная точка поиска  задается исходя из физического содержания решаемой задачи и наличия априорной информации о положении точек экстремума.

Приемлемое направление спуска  должно удовлетворять условию  = 0, 1,...,

где - градиент непрерывно-дифференцируемой функции в точке, обеспечивающему убывание целевой функции. Примером приемлемого направления спуска является направление вектора антиградиента: .

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

Выбор шага  из последнего условия делает спуск в наискорейшем направлении.

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

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

2. Методы первого порядка, использующие информацию о первых производных функции ).

2.3. Задача условной оптимизации

Общая постановка задачи условной оптимизации представляются следующим образом.

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

целые числа.

При условии рассматриваемая задача является общей задачей, и она называется задачей со смешанными ограничениями.

При задача преобразуется в задачу с ограничениями типа равенств. В этом случае множество допустимых решений X имеет следующий вид. .

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

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

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

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

К описанной группе методов относятся метод проекции градиента и метод возможных направлений Зойтендейка. В методе Зойтендейка на каждой итерации строится возможное направление спуска и затем проводится оптимизация вдоль этого направления.

← Предыдущая
Страница 1
Следующая →

Скачать

лекция 4.doc

лекция 4.doc
Размер: 177.5 Кб

Бесплатно Скачать

Пожаловаться на материал

Нечеткие множества. Методы оптимизации. Линейное программирование. Задача безусловной оптимизации. Задача условной оптимизации

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

Искать ещё по теме...

Похожие материалы:

Биология

Генетика. Фундаментальные свойства и уровни организации жизни. Клеточная теория. Функциональная классификация генов. Химический состав и строение структуры хромосомы. Обмен веществ в клетке. ДНК. Генетическая информация в клетках. Онтогенез. Гены у человека. Медико-генетическое консультирование.

Дифференциалды психология

Темперамент. Әлеуметтік ортада тұлғаның даму детерминациясының мәселесі Іс-әрекеттің даралық стильдерінің теориясы

Дефектоскопия

Дефекты металлов, их виды и возможные последствия. Неразрушающий контроль качества методами дефектоскопии. Капиллярная дефектоскопия. Список использованных источников

Вечная Сонечка в романе Достоевского. Ее роль в судьбе Раскольникова

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

Оператор ООУ, ОТУ

Оборудование и обеспечение применяемые на нефтяных промыслах и местах объектов нефтедобычи. Установка подготовки нефти (УПН). Техника безопасности в нефтедобывающей промышленности.

Сохранить?

Пропустить...

Введите код

Ok