Оптимизацията е целенасочена дейност за намиране на алтернатива, която да е с най-голям ефект или с най-голяма възможна производителност, осъществена при дадени ограничения чрез увеличаване на желан фактор или намаляване на нежелан такъв. Оптимизация е термин, свързан с подобряването на изпълнението, който най-често намира приложение в сферата на : математиката - намиране на максимум или минимум на дадена функция за решаване на проблеми; компютърните науки- подобряване на една система, така че да се намали натоварването ѝ, пропускателната способност, изискванията по отношение на паметта или друга характеристика; програмирането - подобряване на системата за намаляване на времето за изпълнение, трафик, изисквания за памет или друго имущество на системата, наречено СЕО (SEO - Search Engine Optimization)

Обект на може да бъде както производствен процес или част от него, намирайки се в стадий на или , така и човешката дейност, разглеждана в определен период от време. За осъщесвяване на ефективна оптимизация трябва да се спазят следните :

Избор т.е. реалните възможности за постигане на главната цел;
за постигане на целта при удоволетворяване на ограниченията.

За намирането на се използват които могат да бъдат наречени още и екстремни задачи. За решаването на този тип задачи се използват точно определени , които се наричат оптимизационни методи . Различните методи за оптимизация са ориентирани към решаване на определени класове от задачи, сложността на които се определя от размите на параметрите, структурата на ограниченията и свойствата на целевата функция.

Локална оптимизация

Оптимизационен модел.

В най-общ смисъл изследователските модели се делят на две групи – експериментални (натурни) и теоритични (умозрителни). Теоритичните модели са изестни и като математичен. Математичният модел на конкретен обект е неговото описание със средствата на математиката и използване на закономерностите от една или няколко науки в съответствие с избрания аспект на разглеждане. Възможно е моделът да бъде коригиран и допълван до тогава, докато получените чрез него резултати съответстват в желана степен на реалния обект. Теоритичните модели се делят на два вида – детерминирани (класически) и стахостически ( експериментално- статистически).

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

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

Едномерните методи от своя страна се делят на преки и непреки такива.

Особеност на преките методи е това, че при тях се взима само стойностите на целевата функция намиращи се в интервала [a,b], без да се взимат нейните производни.

Към преките едномерни методи за оптимизация спадат следните методи:

Сканиране с постоянна стъпка-при този метод интервалът се разделя на равни части, а постоянната стъпка е δ = (b-a)/n;
Метод на дихотомията- последователно търсене, при което при всяко повторение на процеса областта на търсене се намалява два пъти;
Метод на “златното сечение”-минимумът на целевата функция може да се намери с по-малко изчисления, ако интервалъ [a,b] е разделен на части, които спазват правилото за „златното сечение”, (отношението на първата част на дадена отсечка към втората част, трябва да е както отношението на цялата отсечка към първата част )
Полиномна апроксимация- изпозлва се, когато целевата функция може да се прогнозира достатъчно точно чрез полином, в близост до минимума.

Непреките едномерни методи се използват, когато целевата функция е неопределена или два пъти диференцируема, при намирането на минимума й и се използват нейните производни. Непреките методи включват:

Метод на средната точка- използва се връзката между знака на първата производна на целевата функция и характера на изменението на самата функция;
Метод на Нютон- изпозва се за намирането на корените на реални функции;
Метод на кубичната апроксимация- за определянето на апроксимиращия полином се изпозлват както стойностите на целевата функция, така и на нейните производни

Намирането на локален минимум на функция на една променлива в зададен интервал с помощта на Matlab се извършва с програмата fmin. Алгоритъмът, използван в тази програма, съчетава методите на златното сечение и на квадратичната интерполация. Целевата функция трябва да бъде непрекъсната.

Повикващият израз на програмата е

[x,opt]=fmin(‘fun’,x1,x2,options,p1,p2,…)

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

(x k = x k-1 + skd k, k = 1, 2, … ,)

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

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

Голяма част от преките безусловни методи не се обосновават на теоритична обосновка, а на евристични съображения. Този вид методи използват информация само за целевата функция, стойностите на която се изчисляват в следствие на ясно дефинирана стратегия. Методите, които спадат към групата на преките безусловни такива са:

Метод на покоординатното спускане- последователна едномерна минимизация на целевата функция по всяка от координатите на n- мерното пространство
Методи на случайното търсене- това е голяма група от методи, в която стойностите на целевата функция се изчисляват в точки, генерирани по някакъв случаен закон
Симплекс метод- едновременно изследва и премества към минимума чрез точки, които образуват симплекс в управляващо параметрите пространство Непреките безусловни методи се отличават от преките по това, че при тях освен стойностите на целевата функция се използват и нейните първа и втора производни. Съществуват четири метода, които спадат към тази група:
Метод на най-стръмното спускане- при този метод се изчислява антиградиентът на целевата функция в една точка, което превръша задачата в едномерна минимизационна такава, а посоката на търсене се задава от антиградиентът (нейното най-голямо намаляване)
Метод на спрегнатите градиенти- стъпката от всяко повторение не е в посоката на антиградиентите, а се изчислява от антиградиентите от предходното и текущо повторение
Метод на Нютон- намирането на минимума на целева функция с непрекъснати първа и втора производни, чрез използването на градиент ∇f (x) и Хесиан H(x).
Квазинютонови методи- група методи, съчетаващи предимствата на метода на най-стръмното спускане и метода на Нютон

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

Определянето на най-малката (или най-голямата) стойност на многоекстремална функция се осъществява със специализирани методи за глобална (многоекстремална) оптимизация. Несъществуването на универсален ефективен метод за решаване на задачите за глобална оптимизация е причина за създаването на множество методи, ориентирани към определени типове задачи. Като правило никой метод не може да гарантира успешно решаване на многоесктремани задачи със сложна структура. Глобалната оптимизация също както и локалната се дели едномерна и многомерна.

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

Характерна особеност на ефективните методи за глобална оптимизация е, че в околностите на глобалния минимум и на локалните минимуми с близки стойности до търсения оптимум, плътността на точките от минимизиращите редици {x k} и {y k} е по-висока.

Обобщен алгоритъм
Метод на случайното търсене
Метод на глобалното търсене

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

Методи на случайното търсене- различава се от другите методи с това, че при него се въвежда елемент на случайност в процедурата на търсене;
Метод Монте Карло- основава се на предположението, че локалните екстремуми на целевата функция са разпределени равномерно в допустимото пространство П. Чрез този метод се осъществява сондиране и изследване на цялото допустимо множество;
Метод на детерминираното сондиране

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

По- голямата част от съвременните изследователски и приложни оптимизациони задачи са многокритериални и принципно конфликтни. Изборът на система от критерии за оценка и ранжирането им по степен на важност няма еднозначно тълкуване и поражда субективни решения. Друга важна особеност на многокритериалните задачи е, че те нямат само едно единствено решение. Обикновено резултатът от решаването им е множество от т. нар. Парето- оптимални решения, получени в следствие на предложения от Вилфред Парето принцип за съгласувана оптималност. Тъй като никое от получените Парето-оптимални решения не е по-добро от другото е необходимо да се намери еднозначно решение, за което е нужна допълнителна информация и нечие субективно виждане за компромис.

Две са главните цели при многокритериалната оптимизация:

• да се намерят решения, близки до действителните Парето-оптимални решения;

• определените решения да се различават съществено едно от друго.

Постигането на първата цел означава, че се удовлетворяват условията за съгласувана оптималност, а на втората – че няма смесване на различните критерии.

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

Най-общо съществуващите методи за многокритериална оптимизация могат да бъдат разделени на две групи:

Методи, основани на оптимизирането на обобщен критерий, определен в рамките на предварително избрана компромисна стратегия

'Методи, основани на определянето на приблизително Парето-оптимално множество Тегловен метод

Методът, предложен от L. Zadeh през 1963 година, реализира линейна компромисна схема . Многокритериалната задача се трансформира в еднокритериална с помощта на линейна комбинация от отделните критерии с предварително избрани коефициенти w (тегловни коефициенти):

minx∈X F(x),

Метод на ε-ограниченията

Това е процедура предложена от Haimes, Lasdon, Wismer през 1971 година с цел да преодолява недостатъците на тегловните методи, които се дължат на неизпъкналост на Парето-множеството. При тази компромисна схема един от критериите се избира за основен и се минимизира, а останалите критерии се приемат за ограничения от вида

fν (x) ≤ εν , ν = 1, 2, ..., r, ν ≠ μ.

Методът позволява да бъдат определени Парето-оптимални решения и по неизпъкнал участък от границата

Метод на достигане на целта

Този метод включва задаване на цел z° = [z1°, …, zr°]T, която съответства на критерия f(x) = [f1(x), …, fr(x)]T. Доближаването до целта да бъде двупосочно – отдолу или отгоре. Процесът се управлява от тегловен вектор w = [w1,w2, …, wr]T.

Тегловният вектор w позволява въвеждането на мярка за относителния компромис между целите. Задачата за векторна оптимизация се преобразува в еднокритериална задача от вида

minγ, x∈D γ,

Минимаксен метод

За да се избегнат случаи с недопустимо лоши стойности на някои критерии е препоръчително в структурата на задачата за векторна оптимизация да се въведат и критериални ограничения

Метод на глобалния критерий

При метода на глобалния критерий се минимизира разстоянието между някаква зададена точка в критериалното пространство и точките от достижимото множество. Обикновено за точка zосе избира утопичната точка U. Ако всички критерии са еднакво важни, тегловните коефициенти се приемат еднакви wv= 1.

Метод с нелинейна компромисна схема

Компромисната схема, предложена от А. Н. Воронин през 1984 година, свежда задача за векторна оптимизация до еднокритериална задача

Обобщеният критерий на Воронин

F(x) = Σ rv=1 (1 /ρν)

има адаптивни свойства при различна “напрегнатост” на компромисните ситуации в зависимост от стойностите на събираемите 1/ρν . Когато стойността на някой от частните критерии започне да се доближава до своята граница (напрегнат компромисен режим), критерият F рязко нараства и минимизирането на цялата сума се свежда до минимизиране на най-лошото събираемо. Ако частните критерии са далече от пределно допустимите им стойности (спокоен компромисен режим) схемата реализира принципа на интегрална оптималност.

PSI-метод

PSI-методът (съкратено от Parametric Space Investigation) е в основата на универсална изчислителна технология за решаване на приложни многокритериални задачи, които намират приложение в оптималното проектиране на технически обекти и процеси.

За прилагането на PSI-метода е необходимо наличието на математичен модел симулатор на оптимизируемия обект, в който освен обичайните за нелинейното оптимиране ограничения могат да се въвеждат и вариращи ограничения върху изменението на критериите. Решената по този начин оптимизационна задача изисква формирането на допустимото параметрично множество да става в процеса на

решаване на оптимизационната задача.

Програмно реализирания PSI-метод предлага :

• информация за интервалите на изменение на отделните критерии;

• вариране на управляващите параметри в зависимост от наложените ограничения;

• възможност за обоснован избор на областни и критериални ограничения;

• възможност за интерпретиране на ограниченията като псевдокритерии;

• диалогов режим на вземане на решения от излъчено приблизително

Парето-оптимално множество;

• възможност за открояване на зависими критерии;

• таблично оформяне и лесно сортиране на резултатите по различни

признаци.

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

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

Обект за оптимизация
Критерий за оптималност- Числен показател, по който се оценява ефективността от функционирането на обекта за оптимизация

Управляемост на обекта- Наличие на управляващи параметри (температура, налягане, концентрация), които се изменят независимо един от друг, вследствие на което се получават множество варианти на състоянието на обекта, от които се избира най-добрият.

'Метод за оптимизация- Методът за оптимизация е най-важната предпоставка за решение на оптимизационните задачи, тъй като той осъществява процеса на търсене на най-добрия резултат, независимо от характера на обекта за оптимизация.

Обща формулировка на оптимизационните задачи

В най-общ вид една оптимизационна задача се дефинира по следния начин. Търси се максимум на целевата функция 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*), за които се изпълнява условието:

Q(x*) = Q(x1*, x2*,…, xn*) = Qmax > Q(x1, x2,…, xn)

при спазване на ограниченията

x* ∈ Гx

φ i (x1*, x2*,…,xn*) = 0i , i = 1,2,…,ml < n

ψ j (x1*, x2*, …,xn*) = 0j , j = 1,2,…,m2 ,

т.е. x* ∈Гx, φ, ψ

Множеството от точки, които удовлетворяват наложените ограничения, се нарича множество на допустимите решения за целевата функция Q(x) или за

краткост допустима област - x* ∈ Гx, φ, ψ

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

Поради голямото разнообразие от обекти, с които са свързани оптимизационните задачи, последните могат да се класифицират по много признаци. Някои от тях са:

1) Според характера на решавания проблем:

• задача за структурна оптимизация на разглеждания обект – се иска да се проектира съд с минимална повърхнина при зададен обем и няколко за дадени възможни геометрични форми.

• задача за параметрична оптимизация – Търсят се параметрите на обекта така, че критерият да получи оптимална стойност

2) Според типа на математичния модел:

• статична оптимизационна задача – възниква, когато обектът се разглежда в стационарно (равновесно) състояние. Изменението на управляващите параметри води до мигновена промяна в стойността на критерия. Ограниченията в нея се описват с алгебрични уравнения и неравенства. Целевата функция е възможно да се формира като интегрална оценка или въз основа на избрана стойност на някоя характеристика на обекта.

• динамична оптимизационна задача – възниква, когато състоянието на обектa, който се оптимизира, се моделира с помощта на диференциални уравнения, (освен пространствено се изменя и времево). Обектът, подлежащ на оптимизация, притежава способността да натрупва енергия или вещество, в резултат на което той не реагира мигновено на изменението на управляващите параметри. В тези случаи диференциалните уравнения представляват ограничения от тип равенство, а целевата функция обикновено е интегрална оценка.

3) Според броя на управляващите параметри:

• едномерна (еднопараметрична) оптимизационна задача – тя има само един управляващ параметър, т.е. x∈Ε 1.

• многомерна (многопараметрична) оптимизационна задача – броят на управляващите параметри е ξ >1, т.е. x∈Ε ξ.

4) Според характера на зависимостта на критерия или/и на ограниченията от параметрите:

• нелинейни оптимизационни задачи – целевата функция или поне едно от наложените функционални ограничения е нелинейна функция на управляващите параметри.

• линейни оптимизационни задачи – критерият и всички ограничения в задачата са линейни функции на управляващите параметри.

• квадратични оптимизационни задачи – критерият е квадратична функция на управляващите параметри, а ограниченията са линейни.

5) Според наличието на ограничения:

• задача за условна оптимизация. Тази задача съдържа освен интервални и други

ограничения.

• задача за безусловна оптимизация. Тази задача не съдържа никакви ограничения или съдържа само интервални ограничения. От гледна точка на математиката задачата за безусловна оптимизация без интервални ограничения се характеризира с неограничено изме нение на управляващите параметри, т.е. u − → −∞ и u + → +∞. В практическите задачи обаче, винаги се задават някакви интервални ограничения.

Задачите за условна оптимизация е възможно да се преобразуват в задачи за безусловна оптимизация. Това става чрез подхода на “наказателните” функции. Той се състои в изграждане на обобщена целева функция, която съдържа както целевата функция, така и всички ограничения.

Честа практика е пренебрегването на някои ограничения с цел оптимизиране на задачата.За да има решение една оптимизационна задача трябва всички ограничения да са съвместими, т.е. да съществува непусто допустимо параметрично множество Du и целевата функция да е дефинирана в него.

6) Според вида на търсения минимум:

• задача за локална оптимизация – свързана е с определяне на локален минимум на целевата функция.

• задача за глобална оптимизация – изисква се определяне на глобален минимум на целевата функция.

7) Според броя на критериите:

• еднокритериална задача – притежава само един критерий, подлежащ на оптимизиране.

• многокритериална задача – съдържа няколко критерия.

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

Онагледяването на една оптимизационна задача (когато това е възможно) изисква изображението на нейната целева функция да се допълни с графично представяне на наложените ограничения.

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

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

1. Задачи за едномерно търсене (n = 1);

2. Задачи за многомерно търсене (с малка n = 4 ÷ 5, средна 5<n<20 и голяма размерност n > 20);

3. Задачи с пълна и непълна информация за параметрите в математичния модел;

4. Задачи в барицентрично, Декартово или смесено пространство на управляващите параметри;

5. Задачи с непрекъснати, дискретни и смесени управляващи параметри;

6. Задачи със зададена или незададена начална точка при търсене на оптимума;

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

В зависимост от целевата функция

1. Методи за едноцелева оптимизация;

2. Методи за многоцелева оптимизация;

3. Със зададени и незададени производни на целевата функция;

4. Зададена или незададена точност на локализация на екстремума по целева функция;

5. Оптимизация при едноекстремални или многоекстремални целеви функции;

6. Оптимизация при експериментално определена или аналитично зададена целева функция.

В зависимост от ограниченията

1. Без ограничения;

2. С факторни ограничения;

3. С функционални и смесени ограничения;

4. Оптимизация в изпъкнали, неизпъкнали и несвързани допустими области

Основни изисквания към оптимизационните алгоритми

1. Сходимост.

2. Бърза сходимост - получаване на решение за кратко време с малък брой изчисления на целевата функция.

3. Малка заемана памет от програмата на ИМ.

4. Лесна подготовка на условията на задачата за алгоритъма и минимална входна информация за работата на програмата.

5. Сигурно изпълнение на критерия за спиране на търсенето съобразно зададената точност.

6. Изпълнение на всички ограничения, наложени от задачата.

7. Универсалност.

Вижте още:

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

Оптимизация

Съдържание