Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Компекс-метод решения задач НЛП.

Читайте также:
  1. Cельскохозяйственное картографирование, его особенности и задачи.
  2. I группа: задачи на решение проблем в обучении
  3. I Цели и задачи изучения дисциплины
  4. I. Семинар. Тема 1. Предмет, система, задачи судебной медицины. Правовые и организационные основы судебно-медицинской экспертизы, Понятие, объекты, виды, экспертизы
  5. I. Цель и задачи дисциплины
  6. II Всероссийский съезд Советов рабочих и солдатских депутатов и его важнейшие решения.
  7. II. Рассмотрение заявления объекта туристской индустрии и представленных документов и принятие решения о проведении классификации
  8. II. Типовые задачи.
  9. II. Цели и задачи выпускной квалификационной работы
  10. PR — деятельность в органах власти: задачи и специфика.

Этот метод являетя развитием метода Нелдера-Мида, который позволяет учитывать наложенные на задачу ограничения.

Задача такова: дана функция f(x) от вектора x, надо найти минимум функции и на x наложены ограничения lj<=xj<=uj, j=1,n – явные ограничения. И еще неявные ограничения gi(x)<=bi, i=1,m.

 

1. Если целевая функция, также все функции gi, являются выпуклыми, то данная задача имеет единственное решение.

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

3. Также предполагается существование некой начальной точки х1, которая при этом удовлетворяет всем ограничениям.

 

Для начала решения выбираются k точек в пространстве, удовлетворяющие ограничениям и в каждой точке вычисляют значение целевой функции. Бокс предложил назвать этот набор точек комплексом. Значение k должно быть четным и равным 2n, n – размерность пространства. Один из способов задания координат:

 

xij = lj + r(uj-lj), j = 1…n, i = 1…k, r -случайная величина, равномерно распределенная на отрезке (0,1).

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

 

X'i = (xi+xc)/2 – новая точка,

xc=1/(i-1)*sum(e=1…i-1)(xe) – центр тяжести комплекса.

 

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

 

Алгоритм Бокса:

 

1. Точки комплекса найдены. Находится точка Xh среди всех выбранных точек, которая имеет наибольшее значение функции, также находится центр Xk+1 остальных точек комплекса и значения во всех точках комплекса и в точке Xk+1.

2. Попытаемся получить новую точку Xk+2, как отражение точки Xh относительно точки Xk+1, используя формулу xk+2 = Xk+1 + a(Xk+1 – Xh) a – коэффициент отражения.

3. Проверяем будет ли новая точка удовлетворять всем неравенствам. Является ли точка Xk+2 допустимой точкой другими словами. Если да, то к пункту 4.

1.1 Если для Xk+2 не выполнено ограничение по lj, то можем положить Xk+2,j = lj + 10^(-6). Если не выполняется ограничение по uj, то xk+2 = uj – 10^(-6) и к пункту 3.2.

1.2 Если и в этом случае ограничение не выполняется, то точка Xk+2=(xk+2+xk+1)/2 смещается к центру тяжести на половину своего расстояния. … И пункт 3.2 выполняется, пока не найдется допустимая точка. Она будет найдена, так как функции выпуклые.

2. Выполняется если Xk+2 допустимая точка. Fk+2=f(xk+2) и сравнивается со значением функции f(h), в том случае если значение в fXk+2 больше в fh – ее еще больше смещают к центру, а если f(Xk+2)<f(h), то заменяем Xh на Xk+2.

3. Вычисление двух величин для проверки сходимости процесса.

3.1 Вычисляем среднеквадратическое отклонение сигма для k значений функции.

Сигма=(1/k∑(e=1,k)(f(Xe)-f)2)1/2-сумма квадратов отклонений

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

4. Сравниваем значения сигмы и d со значениями точности эпсилон и дельта и если точность соблюдена, считаем, что нашли минимум функции и за минимум берем центр тяжести комплекса. A обычно равна 1,3.

 

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

 




Дата добавления: 2015-02-16; просмотров: 19 | Поможем написать вашу работу | Нарушение авторских прав




lektsii.net - Лекции.Нет - 2014-2024 год. (0.007 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав