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

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

2014-03-29T15:55:47Z

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

2014-03-29T15:46:00Z

Detelina Staneva: Нова страница: '''Съществуват много методи за намиране на решение на проблема многокритериална оптимизаци...

2014-03-27T11:32:43Z

Нова страница: '''Съществуват много методи за намиране на решение на проблема многокритериална оптимизаци...

Нова страница

'''Съществуват много методи за намиране на решение на проблема многокритериална оптимизация''', някои от които са обяснени по-долу.

==Изграждане на обединена целевата функция (AOF)==

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

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

Важно е да се отбележи, че [[метод на претеглена сума |методът на претеглената сума]] е по същество субективен, поради това решителният мениджър (DM) трябва да достави теглата. Освен това този подход не може да установи решенията, които не са доминиращи, а само решенията, които са разположени на изпъкналата предна част на Парето могат да бъдат намерени.

Обективният начин за решаване на многокритериални проблеми изискващи Парето – отстъпчив [[класификационен метод]], отнасящ се до не-доминиращите решения, както се вижда в многокритериалните еволюционни подходи, като например NSGA-II и SPEA2.

==Методи NBI, SPO, DSD==

Методите NBI (Normal Boundary Intersection или Нормални Гранични Пресечки), NC (Normal Contraint или Нормални Ограничения), SPO (Successive Pareto Optimization или Последователна Оптимизация на Парето) и DSD (Directed Search Domain или Пряко Търсене на Доминиране) се използват за решаване на многокритериални оптимизационни проблеми чрез изграждане на няколко AOF-а. Решението на всяка AOF „ражда” точка на Парето.

Методите NC и DSD предполагат две различни процедури за [[филтриране]], за да се отстранят точките на Парето на местно ниво. AOF са изградени с цел получаване на равномерно разпределени точки на Парето, които дават добро впечатление (приближаване) на действителните групи до точките на Парето.

Методите DSD, NC и SPO генерират решения, които описват някои периферни райони от множеството от точки на Парето, за повече от 2 обекта, които се знае, че не са представени от решенията генерирани с метода NBI.

==Еволюционни алгоритми==

Еволюционните [[алгоритъм|алгоритми]] са популярни подходи за решаване на многокритериална оптимизация. В днешно време, най-еволюционно оптимизиране използва Парето - базиран на [[рангова схема|рангови схеми]]. Генетичните алгоритми, като например за неразпространение на доминиращото сортиране на генетичен алгоритъм-II (NSGA-II) и силата на еволюционния подход на Парето 2 (SPEA-2) са станали стандартни подходи, въпреки че някои схеми, базирани на частиците „рояк” оптимизация и симулираното техническо закаляване са значителни.

==Други методи==

* Многокритериална оптимизация използваща еволюционни алгоритми (MOEA - Multiobjective Optimization using Evolutionary Algorithms)
* Повърхностно размножаване на изпъкнали многокритериални случаи на Парето (PGEN - Pareto surface generation for convex multiobjective instances)
* Непряка оптимизация на базата на самоорганизация (IOSO - Indirect Optimization on the basis of Self-Organization)
==Вижте още==

*[[Ефект]]
*[[План]]
*[[Прогноза]]
*[[Алгоритъм]]
*[[Избор]]

==Източници==

* Steuer, R.E. (1986). ''Multiple Criteria Optimization: Theory, Computations, and Application''. New York: John Wiley & Sons
* Sawaragi, Y.; Nakayama, H. and Tanino, T. (1985). ''Theory of Multiobjective Optimization (vol. 176 of Mathematics in Science and Engineering)''. Orlando, FL: Academic Press Inc
* Deb, K.: Multi-Objective Optimization using Evolutionary Algorithms. Wiley, 2002
* Das and J. E. Dennis. Normal-Boundary Intersection: A New Method for Generating the Pareto Surface in Nonlinear Multicriteria Optimization Problems. SIAM Journal on Optimization
* A Messac and C. A. Mattson: Normal constraint method with guarantee of even representation of complete Pareto frontier
* Deb, K. Multi-Objective Optimization using Evolutionary Algorithms John Wiley & SonsCoello Coello, C. A.; Lamont, G. B. & Van Veldhuizen, D. A. Evolutionary Algorithms for Solving Multi-Objective Problems Springer, 2007.

==Външни препратки==

* [http://www.calresco.org/lucas/pmo.htm Практическа многокритериална оптимизация]
* [http://demonstrations.wolfram.com/EvolutionaryMultiobjectiveOptimization/ Еволюционна многокритериална оптимизация]

[[category:Управленски решения и риск]][[category:Количествени методи в управлението]][[category:Управление на операциите]][[category:Основи на управлението]]

← По-стара версия		Версия от 15:55, 29 март 2014
Ред 1:		Ред 1:
	'''Съществуват много методи за намиране на решение на проблема многокритериална оптимизация''', някои от които са обяснени по-долу.		'''Съществуват много методи за намиране на решение на проблема многокритериална оптимизация''', някои от които са обяснени по-долу.
−
−
−
−
−
−
−
−	~~Най-общо съществуващите методи за многокритериална оптимизация могат да бъдат разделени на две групи:~~
−
−	* Методи, основани на оптимизирането на обобщен критерий, определен в рамките на предварително избрана компромисна стратегия
−	* Методи, основани на определянето на приблизително Парето-оптимално множество Тегловен метод
−
−	Методът, предложен от ''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-метод предлага :~~
−
−	*информация за интервалите на изменение на отделните критерии;
−
−	*вариране на управляващите параметри в зависимост от наложените ограничения;
−
−	*възможност за обоснован избор на областни и критериални ограничения;
−
−	*възможност за интерпретиране на ограниченията като псевдокритерии;
−
−	*диалогов режим на вземане на решения от излъчено приблизително
−
−
−	~~Парето-оптимално множество;~~
−
−	*възможност за открояване на зависими критерии;
−
−	*таблично оформяне и лесно сортиране на резултатите по различни признаци.
−
−
−
−
−
−

	==Изграждане на обединена целевата функция (AOF)==		==Изграждане на обединена целевата функция (AOF)==

← По-стара версия		Версия от 15:46, 29 март 2014
Ред 1:		Ред 1:
	'''Съществуват много методи за намиране на решение на проблема многокритериална оптимизация''', някои от които са обяснени по-долу.		'''Съществуват много методи за намиране на решение на проблема многокритериална оптимизация''', някои от които са обяснени по-долу.
		+
		+
		+
		+
		+
		+
		+
		+	Най-общо съществуващите методи за многокритериална оптимизация могат да бъдат разделени на две групи:
		+
		+	* Методи, основани на оптимизирането на обобщен критерий, определен в рамките на предварително избрана компромисна стратегия
		+	* Методи, основани на определянето на приблизително Парето-оптимално множество Тегловен метод
		+
		+	Методът, предложен от ''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-метод предлага :
		+
		+	*информация за интервалите на изменение на отделните критерии;
		+
		+	*вариране на управляващите параметри в зависимост от наложените ограничения;
		+
		+	*възможност за обоснован избор на областни и критериални ограничения;
		+
		+	*възможност за интерпретиране на ограниченията като псевдокритерии;
		+
		+	*диалогов режим на вземане на решения от излъчено приблизително
		+
		+
		+	Парето-оптимално множество;
		+
		+	*възможност за открояване на зависими критерии;
		+
		+	*таблично оформяне и лесно сортиране на резултатите по различни признаци.
		+
		+
		+
		+
		+
		+

	==Изграждане на обединена целевата функция (AOF)==		==Изграждане на обединена целевата функция (AOF)==