Оптимизация - Редакционна история

Detelina Staneva в 15:46, 29 март 2014

2014-03-29T15:46:55Z

Detelina Staneva: /* Вижте още */

2014-03-29T15:46:13Z

Вижте още

Detelina Staneva: /* Вижте още */

2014-03-29T15:43:52Z

Вижте още

Detelina Staneva: /* Методи за многокритериална оптимизация */

2014-03-29T15:43:00Z

Методи за многокритериална оптимизация

Detelina Staneva: /* Вижте още */

2014-03-29T15:42:33Z

Вижте още

Detelina Staneva: /* Необходими предпоставки за оптимизационните задачи */

2014-03-29T15:41:55Z

Необходими предпоставки за оптимизационните задачи

Detelina Staneva: /* Избор на алгоритъм за нелинейна оптимизация */

2014-03-29T15:41:37Z

Избор на алгоритъм за нелинейна оптимизация

Detelina Staneva: /* Видове оптимизационни задачи */

2014-03-29T15:41:10Z

Видове оптимизационни задачи

Detelina Staneva: /* Многомерна оптимизация */

2014-03-29T15:39:57Z

Многомерна оптимизация

Detelina Staneva: /* Едномерна оптимизация */

2014-03-29T15:39:35Z

Едномерна оптимизация

← По-стара версия		Версия от 15:46, 29 март 2014
Ред 10:		Ред 10:

	За намирането на се използват които могат да бъдат наречени още и екстремни задачи. За решаването на този тип задачи се използват точно определени , които се наричат оптимизационни методи . Различните методи за оптимизация са ориентирани към решаване на определени класове от задачи, сложността на които се определя от размите на параметрите, структурата на ограниченията и свойствата на целевата функция.		За намирането на се използват които могат да бъдат наречени още и екстремни задачи. За решаването на този тип задачи се използват точно определени , които се наричат оптимизационни методи . Различните методи за оптимизация са ориентирани към решаване на определени класове от задачи, сложността на които се определя от размите на параметрите, структурата на ограниченията и свойствата на целевата функция.
−
−	~~==Локална оптимизация==~~
−
−	~~===Оптимизационен модел===~~
−
−	В най-общ смисъл изследователските модели се делят на две групи – експериментални (натурни) и теоритични (умозрителни). Теоритичните модели са изестни и като математичен. Математичният модел на конкретен обект е неговото описание със средствата на математиката и използване на закономерностите от една или няколко науки в съответствие с избрания аспект на разглеждане. Възможно е моделът да бъде коригиран и допълван до тогава, докато получените чрез него резултати съответстват в желана степен на реалния обект. Теоритичните модели се делят на два вида – детерминирани (класически) и стахостически ( експериментално - статистически).
−
−	~~===Едномерна оптимизация===~~
−
−	~~===Многомерна оптимизация===~~
−
−	~~==Глобална оптимизация==~~
−
−	Определянето на най-малката (или най-голямата) стойност на многоекстремална функция се осъществява със специализирани методи за глобална(многоекстремална) оптимизация. Несъществуването на универсален ефективен метод за решаване на задачите за глобална оптимизация е причина за създаването на множество методи, ориентирани към определени [[тип]]ове задачи. Като правило никой метод не може да гарантира успешно решаване на многоесктремани задачи със сложна [[структура]]. Глобалната оптимизация също както и локалната се дели едномерна и многомерна.
−
−	~~===Методи за едномерна глобална оптимизация===~~
−
−	Характерна особеност на ефективните методи за [[глобална оптимизация]] е, че в околностите на глобалния минимум и на локалните минимуми с близки стойности до търсения оптимум, плътността на точките от минимизиращите редици {''x k''} и {''y k''} е по-висока.
−	* Обобщен алгоритъм
−	* Метод на случайното търсене
−	* Метод на глобалното търсене
−
−	~~===Методи за многомерна глобална оптимизация===~~
−
−	* Методи на случайното търсене- различава се от другите методи с това, че при него се въвежда [[елемент]] на случайност в [[процедура]]та на търсене;
−	* [[Метод Монте Карло]] - основава се на предположението, че локалните екстремуми на целевата функция са разпределени равномерно в допустимото пространство П. Чрез този метод се осъществява сондиране и изследване на цялото допустимо множество;
−	* Метод на детерминираното сондиране
−
−	~~===Многокритериална оптимизация===~~
−
−	По - голямата част от съвременните изследователски и приложни оптимизациони задачи са многокритериални и принципно конфликтни. Изборът на система от критерии за оценка и ранжирането им по степен на важност няма еднозначно тълкуване и поражда субективни решения. Друга важна особеност на многокритериалните задачи е, че те нямат само едно единствено решение. Обикновено резултатът от решаването им е множество от т. нар. Парето- оптимални решения, получени в следствие на предложения от Вилфред Парето принцип за съгласувана оптималност. Тъй като никое от получените Парето-оптимални решения не е по-добро от другото е необходимо да се намери еднозначно решение, за което е нужна допълнителна информация и нечие субективно виждане за компромис.
−
−	~~Две са главните цели при многокритериалната оптимизация:~~
−
−	*да се намерят решения, близки до действителните Парето-оптимални решения;
−	*определените решения да се различават съществено едно от друго.
−
−	Постигането на първата цел означава, че се удовлетворяват условията за съгласувана оптималност, а на втората – че няма смесване на различните критерии.
−
−	~~===Методи за многокритериална оптимизация===~~
−
−	~~==Оптимизационни задачи==~~
−
−	~~===Необходими предпоставки за оптимизационните задачи===~~
−
−	~~===Видове оптимизационни задачи===~~
−
−	~~===Графично онагледяване на оптимизационни задачи===~~
−
−	Онагледяването на една оптимизационна задача (когато това е възможно) изисква изображението на нейната целева функция да се допълни с графично представяне на наложените ограничения.

	==Вижте още==		==Вижте още==

@@ Ред 69: / Ред 69: @@
 *[[Избор на алгоритъм за нелинейна оптимизация]]
 *[[Предпоставки за оптимизационна задача]]
-*[[Методи за многокритериална оптимизация]]
+*[[Методи за решение при многокритериална оптимизация]]
 *[[Многокритериална оптимизация]]
 *[[Производство]]

@@ Ред 70: / Ред 70: @@
 *[[Предпоставки за оптимизационна задача]]
 *[[Методи за многокритериална оптимизация]]
 *[[Производство]]
 *[[Продукция]]

← По-стара версия		Версия от 15:43, 29 март 2014
Ред 50:		Ред 50:

	===Методи за многокритериална оптимизация===		===Методи за многокритериална оптимизация===
−
−	~~Най-общо съществуващите методи за многокритериална оптимизация могат да бъдат разделени на две групи:~~
−
−	* Методи, основани на оптимизирането на обобщен критерий, определен в рамките на предварително избрана компромисна стратегия
−	* Методи, основани на определянето на приблизително Парето-оптимално множество Тегловен метод
−
−	Методът, предложен от ''L. Zadeh'' през 1963 година, реализира линейна компромисна схема . Многокритериалната задача се трансформира в еднокритериална с помощта на линейна комбинация от отделните критерии с предварително избрани коефициенти w (тегловни коефициенти):
−
−	~~minx∈X F(x),~~
−
−	* Метод на ε-ограниченията
−
−	Това е процедура предложена от Haimes'', Lasdon, Wismer'' през 1971 година с цел да преодолява недостатъците на тегловните методи, които се дължат на неизпъкналост на Парето-множеството. При тази компромисна схема един от критериите се избира за основен и се минимизира, а останалите критерии се приемат за ограничения от вида
−
−	~~<center>fν (x) ≤ εν , ν = 1, 2, ..., r, ν ≠ μ.</center>~~
−
−	~~<center></center>~~
−
−	Методът позволява да бъдат определени [[Вилфредо Парето\|Парето]] - оптимални решения и по неизпъкнал участък от границата
−
−	* Метод на достигане на [[цел]]та
−
−	Този метод включва задаване на цел z° = [z1°, …, zr°]T, която съответства на критерия f(x) = [f1(x), …, fr(x)]T. Доближаването до целта да бъде двупосочно – отдолу или отгоре. Процесът се управлява от тегловен вектор w = [w1,w2, …, wr]T.
−
−	Тегловният вектор w позволява въвеждането на мярка за относителния компромис между целите. Задачата за векторна оптимизация се преобразува в еднокритериална задача от вида
−
−	~~<center>minγ, ''x''∈''D ''γ,</center>~~
−
−	* Минимаксен метод
−
−	За да се избегнат случаи с недопустимо лоши стойности на някои критерии е препоръчително в структурата на задачата за векторна оптимизация да се въведат и критериални ограничения
−
−	* Метод на глобалния критерий
−
−	При метода на глобалния критерий се минимизира разстоянието между някаква зададена точка в критериалното пространство и точките от достижимото множество. Обикновено за точка ''z''осе избира утопичната точка ''U''. Ако всички критерии са еднакво важни, тегловните коефициенти се приемат еднакви ''w''v= 1.
−
−	* Метод с нелинейна компромисна схема
−
−	Компромисната схема, предложена от [[А. Н. Воронин]] през 1984 година, свежда задача за векторна оптимизация до еднокритериална задача
−
−	~~Обобщеният [[критерий на Воронин]]~~
−
−	~~<center>F(x) = Σ rv=1 (1 /ρν)</center>~~
−
−	~~<center></center>~~
−
−	има адаптивни свойства при различна “напрегнатост” на компромисните ситуации в зависимост от стойностите на събираемите 1/ρν . Когато стойността на някой от частните критерии започне да се доближава до своята граница (напрегнат компромисен режим), критерият F рязко нараства и минимизирането на цялата сума се свежда до минимизиране на най-лошото събираемо. Ако частните критерии са далече от пределно допустимите им стойности (спокоен компромисен режим) схемата реализира принципа на интегрална оптималност.
−
−	* PSI-метод
−
−	PSI-методът (съкратено от ''Parametric Space Investigation'') е в основата на универсална изчислителна технология за решаване на приложни многокритериални задачи, които намират приложение в оптималното проектиране на технически обекти и процеси.
−
−	За прилагането на PSI-метода е необходимо наличието на математичен модел симулатор на оптимизируемия обект, в който освен обичайните за нелинейното оптимиране ограничения могат да се въвеждат и вариращи ограничения върху изменението на критериите. Решената по този начин оптимизационна задача изисква формирането на допустимото параметрично множество да става в процеса на решаване на оптимизационната задача.
−
−	~~Програмно реализирания PSI-метод предлага :~~
−
−	*информация за интервалите на изменение на отделните критерии;
−
−	*вариране на управляващите параметри в зависимост от наложените ограничения;
−
−	*възможност за обоснован избор на областни и критериални ограничения;
−
−	*възможност за интерпретиране на ограниченията като псевдокритерии;
−
−	*диалогов режим на вземане на решения от излъчено приблизително
−
−
−	~~Парето-оптимално множество;~~
−
−	*възможност за открояване на зависими критерии;
−
−	*таблично оформяне и лесно сортиране на резултатите по различни признаци.

	==Оптимизационни задачи==		==Оптимизационни задачи==

@@ Ред 141: / Ред 141: @@
 *[[Избор на алгоритъм за нелинейна оптимизация]]
 *[[Предпоставки за оптимизационна задача]]
 *[[Производство]]
 *[[Продукция]]

← По-стара версия		Версия от 15:41, 29 март 2014
Ред 126:		Ред 126:

	===Необходими предпоставки за оптимизационните задачи===		===Необходими предпоставки за оптимизационните задачи===
−
−	~~# Обект за оптимизация~~
−	# Критерий за оптималност - Числен показател, по който се оценява [[ефективност]]та от функционирането на обекта за оптимизация
−	# Управляемост на обекта'' - ''Наличие на управляващи параметри (температура, [[налягане]], [[концентрация]]), които се изменят независимо един от друг, вследствие на което се получават множество варианти на състоянието на [[обект]]а, от които се избира най-добрият.
−	# Метод за оптимизация - Методът за оптимизация е най-важната предпоставка за решение на оптимизационните задачи, тъй като той осъществява процеса на търсене на най-добрия резултат, независимо от характера на обекта за оптимизация.
−
−	В най-общ вид една оптимизационна [[задача]] се дефинира по следния начин. Търси се максимум на целевата функция maxQ(x) = maxQ(x1, x2,…,xn) в пространството определено от управляващите параметри x ∈ Гx и наложените ограничения от други функции:
−
−	~~φ i (x1, x2,…,xn) = φ 0il , i = 1,2,…,ml < n~~
−
−	~~ψ j (x1, x2, …,xn) ≥ ψ 0j , j = 1,2,…,m2~~
−
−	Целта на задачата за оптимизация е да се намерят такива [[стойност]]и на управляващите параметри x* ''= ''(''x1, x2,…, xn*'')'', ''за които се изпълнява условието:
−
−	~~<center>Q(x) = Q(''x1, x2,…, xn'') = Qmax > Q(''x1, x2,…, xn'')</center>~~
−
−	~~при спазване на ограниченията~~
−
−	~~x* ∈ Гx~~
−
−	~~φ ''i ''(''x1, x2,…,xn''*) = 0''i '', ''i ''= 1,2,…,''m''l < ''n''~~
−
−	~~ψ ''j ''(''x1, x2, …,xn''*) = 0''j '', ''j ''= 1,2,…,''m''2 ,~~
−
−	~~т.е. x* ∈Г''x, φ, ψ''~~
−
−	Множеството от точки, които удовлетворяват наложените ограничения, се нарича множество на допустимите решения за целевата функция Q(x) или за
−
−	~~краткост [[допустима област]] - x* ∈ Г''x, φ, ψ''~~

	===Видове оптимизационни задачи===		===Видове оптимизационни задачи===

← По-стара версия		Версия от 15:41, 29 март 2014
Ред 161:		Ред 161:

	Онагледяването на една оптимизационна задача (когато това е възможно) изисква изображението на нейната целева функция да се допълни с графично представяне на наложените ограничения.		Онагледяването на една оптимизационна задача (когато това е възможно) изисква изображението на нейната целева функция да се допълни с графично представяне на наложените ограничения.
−
−	~~==Избор на алгоритъм за нелинейна оптимизация ==~~
−
−	~~Избор на алгоритъм за оптимизация~~
−
−	~~#Задачи за едномерно търсене (n = 1);~~
−	~~#Задачи за многомерно търсене (с малка n = 4 ÷ 5, средна 5<n<20 и голяма размерност n > 20);~~
−	~~#Задачи с пълна и непълна информация за параметрите в математичния модел;~~
−	~~#Задачи в барицентрично, Декартово или смесено пространство на управляващите параметри;~~
−	~~#Задачи с непрекъснати, дискретни и смесени управляващи параметри;~~
−	~~#Задачи със зададена или незададена начална точка при търсене на оптимума;~~
−	#Задачи със зададена абсолютна или относителна точност на локализация на екстремума по всеки управляващ параметър.
−
−
−	~~В зависимост от целевата функция~~
−
−	~~#Методи за едноцелева оптимизация;~~
−	~~#Методи за многоцелева оптимизация;~~
−	~~#Със зададени и незададени производни на целевата функция;~~
−	~~#Зададена или незададена точност на локализация на екстремума по целева функция;~~
−	~~#Оптимизация при едноекстремални или многоекстремални целеви функции;~~
−	~~#Оптимизация при експериментално определена или аналитично зададена целева функция.~~
−
−
−	~~В зависимост от ограниченията~~
−
−	~~#Без ограничения;~~
−	~~#С факторни ограничения;~~
−	~~#С функционални и смесени ограничения;~~
−	~~#Оптимизация в изпъкнали, неизпъкнали и несвързани допустими области~~
−
−
−	~~Основни изисквания към оптимизационните алгоритми~~
−
−	~~#Сходимост.~~
−	~~#Бърза сходимост - получаване на решение за кратко време с малък брой изчисления на целевата функция.~~
−	~~#Малка заемана памет от програмата на ИМ.~~
−	#Лесна подготовка на условията на задачата за алгоритъма и минимална входна информация за работата на програмата.
−	~~#Сигурно изпълнение на критерия за спиране на търсенето съобразно зададената точност.~~
−	~~#Изпълнение на всички ограничения, наложени от задачата.~~
−	~~#Универсалност.~~

	==Вижте още==		==Вижте още==

← По-стара версия		Версия от 15:41, 29 март 2014
Ред 157:		Ред 157:

	===Видове оптимизационни задачи===		===Видове оптимизационни задачи===
−
−	Поради голямото разнообразие от обекти, с които са свързани оптимизационните задачи, последните могат да се класифицират по много признаци. Някои от тях са:
−
−
−	*Според характера на решавания проблем:
−
−	:*задача за структурна оптимизация на разглеждания обект – се иска да се проектира съд с минимална повърхнина при зададен обем и няколко за дадени възможни геометрични форми.
−
−	:*задача за параметрична оптимизация – Търсят се параметрите на обекта така, че критерият да получи оптимална стойност
−
−
−	*Според типа на математичния модел:
−
−	:*статична оптимизационна задача – възниква, когато обектът се разглежда в стационарно (равновесно) състояние. Изменението на управляващите параметри води до мигновена промяна в стойността на критерия. Ограниченията в нея се описват с алгебрични уравнения и неравенства. Целевата функция е възможно да се формира като интегрална оценка или въз основа на избрана стойност на някоя характеристика на обекта.
−
−	:*динамична оптимизационна задача – възниква, когато състоянието на обектa, който се оптимизира, се моделира с помощта на диференциални уравнения, (освен пространствено се изменя и времево). Обектът, подлежащ на оптимизация, притежава способността да натрупва енергия или вещество, в резултат на което той не реагира мигновено на изменението на управляващите параметри. В тези случаи диференциалните уравнения представляват ограничения от тип равенство, а целевата функция обикновено е интегрална оценка.
−
−
−	*Според броя на управляващите параметри:
−
−	~~:*едномерна (еднопараметрична) оптимизационна задача – тя има само един управляващ параметър, т.е. x∈Ε 1.~~
−
−	~~:*многомерна (многопараметрична) оптимизационна задача – броят на управляващите параметри е ξ >1, т.е. x∈Ε ξ.~~
−
−
−	*Според характера на зависимостта на критерия или/и на ограниченията от параметрите:
−
−	:*нелинейни оптимизационни задачи – целевата функция или поне едно от наложените функционални ограничения е нелинейна функция на управляващите параметри.
−
−	:*линейни оптимизационни задачи – критерият и всички ограничения в задачата са линейни функции на управляващите параметри.
−
−	:*квадратични оптимизационни задачи – критерият е квадратична функция на управляващите параметри, а ограниченията са линейни.
−
−
−	*Според наличието на ограничения:
−
−	~~:*задача за условна оптимизация. Тази задача съдържа освен интервални и други~~
−
−	~~ограничения.~~
−
−	:*задача за безусловна оптимизация. Тази задача не съдържа никакви ограничения или съдържа само интервални ограничения. От гледна точка на математиката задачата за безусловна оптимизация без интервални ограничения се характеризира с неограничено изме нение на управляващите параметри, т.е. u − → −∞ и u + → +∞. В практическите задачи обаче, винаги се задават някакви интервални ограничения.
−
−	Задачите за условна оптимизация е възможно да се преобразуват в задачи за безусловна оптимизация. Това става чрез подхода на “наказателните” функции. Той се състои в изграждане на обобщена целева функция, която съдържа както целевата функция, така и всички ограничения.
−
−	Честа практика е пренебрегването на някои ограничения с цел оптимизиране на задачата.За да има решение една оптимизационна задача трябва всички ограничения да са съвместими, т.е. да съществува непусто допустимо параметрично множество Du и целевата функция да е дефинирана в него.
−
−
−	*Според вида на търсения минимум:
−
−	~~:*задача за локална оптимизация – свързана е с определяне на локален минимум на целевата функция.~~
−
−	~~:*задача за глобална оптимизация – изисква се определяне на глобален минимум на целевата функция.~~
−
−
−	*Според броя на критериите:
−
−	~~:*еднокритериална задача – притежава само един критерий, подлежащ на оптимизиране.~~
−
−	~~:*многокритериална задача – съдържа няколко критерия.~~

	===Графично онагледяване на оптимизационни задачи===		===Графично онагледяване на оптимизационни задачи===

← По-стара версия		Версия от 15:39, 29 март 2014
Ред 20:		Ред 20:

	===Многомерна оптимизация===		===Многомерна оптимизация===
−
−	~~(''x k ''= ''x k-1 ''+ ''skd k'', ''k ''= 1, 2, … ,)~~
−
−	Многомерната оптимизация представлява задача, за минимизация на целевата функция, зависеща от много променливи. Към големият брой управляващи параметри и сложността на целевата функция, се добавяр многобройни ограничения.
−
−	~~Методите за многомерна оптимизация се делят на преки и непреки.~~
−
−	Голяма част от преките безусловни методи не се обосновават на теоритична обосновка, а на евристични съображения. Този вид методи използват информация само за целевата функция, стойностите на която се изчисляват в следствие на ясно дефинирана стратегия. Методите, които спадат към групата на преките безусловни такива са:
−
−	* Метод на покоординатното спускане - последователна едномерна минимизация на целевата функция по всяка от координатите на n- мерното пространство
−	* Методи на случайното търсене - това е голяма група от методи, в която стойностите на целевата функция се изчисляват в точки, генерирани по някакъв случаен закон
−	* Симплекс метод - едновременно изследва и премества към минимума чрез точки, които образуват симплекс в управляващо параметрите пространство Непреките безусловни методи се отличават от преките по това, че при тях освен стойностите на целевата функция се използват и нейните първа и втора производни. Съществуват четири метода, които спадат към тази група:
−	* Метод на най-стръмното спускане - при този метод се изчислява антиградиентът на целевата функция в една точка, което превръша задачата в едномерна минимизационна такава, а посоката на търсене се задава от антиградиентът (нейното най-голямо намаляване)
−	* Метод на спрегнатите градиенти - стъпката от всяко повторение не е в посоката на антиградиентите, а се изчислява от антиградиентите от предходното и текущо повторение
−	* Метод на Нютон - намирането на минимума на целева функция с непрекъснати първа и втора производни, чрез използването на градиент ∇f (x) и Хесиан H(x).
−	* Квазинютонови методи- група методи, съчетаващи предимствата на [[метод]]а на най-стръмното спускане и метода на Нютон

	==Глобална оптимизация==		==Глобална оптимизация==

← По-стара версия		Версия от 15:39, 29 март 2014
Ред 18:		Ред 18:

	===Едномерна оптимизация===		===Едномерна оптимизация===
−
−	Оптимизационните задачи, при които трябва да се определи минимума на целевата функция, която зависи само от една променлива, се наричат едномерни. Това са най-простият тип оптимизационни задачи, но в практиката те се срещат много рядко.
−
−	~~Едномерните методи от своя страна се делят на преки и непреки такива.~~
−
−	Особеност на преките методи е това, че при тях се взима само стойностите на целевата функция намиращи се в интервала [a,b], без да се взимат нейните производни.
−
−	~~Към преките едномерни методи за оптимизация спадат следните методи:~~
−
−	# Сканиране с постоянна стъпка-при този метод интервалът се разделя на равни части, а постоянната стъпка е δ = (b-a)/n;
−	# Метод на дихотомията - последователно търсене, при което при всяко повторение на процеса областта на търсене се намалява два пъти;
−	# Метод на “златното сечение”-минимумът на целевата функция може да се намери с по-малко изчисления, ако интервалъ [a,b] е разделен на части, които спазват правилото за „златното сечение”, (отношението на първата част на дадена отсечка към втората част, трябва да е както отношението на цялата отсечка към първата част )
−	# Полиномна апроксимация- изпозлва се, когато целевата функция може да се прогнозира достатъчно точно чрез [[полином]], в близост до [[минимум]]а.
−
−
−	Непреките едномерни методи се използват, когато целевата функция е неопределена или два пъти диференцируема, при намирането на минимума й и се използват нейните производни. Непреките методи включват:
−
−	# Метод на средната точка - използва се връзката между знака на първата производна на целевата функция и характера на изменението на самата функция;
−	~~# Метод на [[Нютон]] - изпозва се за намирането на корените на реални функции;~~
−	# Метод на [[кубична апроксимация\|кубичната апроксимация]] - за определянето на апроксимиращия полином се изпозлват както стойностите на целевата функция, така и на нейните производни
−
−
−	Намирането на локален минимум на функция на една променлива в зададен интервал с помощта на ''Matlab ''се извършва с програмата ''fmin''. [[Алгоритъм]]ът, използван в тази програма, съчетава методите на златното сечение и на квадратичната интерполация. Целевата функция трябва да бъде непрекъсната.
−
−	~~Повикващият израз на програмата е~~
−
−	~~[x,opt]=fmin(‘fun’,x1,x2,options,p1,p2,…)~~

	===Многомерна оптимизация===		===Многомерна оптимизация===