Разлика между версии на „Многокритериална оптимизация“
| Ред 1: | Ред 1: | ||
| − | '''Многокритериалната оптимизация''' (на англ. [[Multi-objective optimization]]) или [[програмиране]], известна също като оптимизация с няколко [[критерий|критерия]] или няколко атрибута, е [[процес]] на [[оптимизиране]] едновременно на две или повече противоречиви [[цел]]и при спазване на определени [[ограничение|ограничения]]. | + | '''Многокритериалната оптимизация''' (на англ. [[Multi-objective optimization]]) или [[програмиране]], известна също като оптимизация с няколко [[критерий|критерия]] или няколко атрибута, е '''[[процес]] на [[оптимизиране]] едновременно на две или повече противоречиви [[цел]]и при спазване на определени [[ограничение|ограничения]]'''. |
| − | |||
| − | |||
[[Проблем]]и за многокритериалната оптимизация могат да се намерят в различни области: [[продукт]]и в процеса на проектиране, [[финансиране]], конструкция на въздухоплавателни средства, петролна и газова [[промишленост]], автомобилен дизайн или където трябва да се вземат оптимални [[решения]] в присъствието на компромиси между две или повече противоречиви цели. Повишаването на [[приходи]]те и намаляването на стойността на продукта; увеличаването на производителността и свеждането до минимум [[разход]]а на гориво на превозното средство; свеждане до минимум на теглото като същевременно се увеличава максималното съдържание на даден компонент са примери за многоцелеви проблеми на оптимизацията. | [[Проблем]]и за многокритериалната оптимизация могат да се намерят в различни области: [[продукт]]и в процеса на проектиране, [[финансиране]], конструкция на въздухоплавателни средства, петролна и газова [[промишленост]], автомобилен дизайн или където трябва да се вземат оптимални [[решения]] в присъствието на компромиси между две или повече противоречиви цели. Повишаването на [[приходи]]те и намаляването на стойността на продукта; увеличаването на производителността и свеждането до минимум [[разход]]а на гориво на превозното средство; свеждане до минимум на теглото като същевременно се увеличава максималното съдържание на даден компонент са примери за многоцелеви проблеми на оптимизацията. | ||
| − | |||
| − | |||
Ако многокритериалният проблем е добре оформен не трябва да има отделно решение, което едновременно намалява всяка цел, към своята най-голяма. Във всеки случай, една цел трябва да е достигнала връх така, че когато се опитва да оптимизира целта по-нататък, другите цели „страдат” като резултат. Намирането на такова решение и определяне с какво това решение е по-добро в сравнение с многото други такива решения е целта при създаването и решаването на един проблем, свързан с многокритериалната оптимизация. | Ако многокритериалният проблем е добре оформен не трябва да има отделно решение, което едновременно намалява всяка цел, към своята най-голяма. Във всеки случай, една цел трябва да е достигнала връх така, че когато се опитва да оптимизира целта по-нататък, другите цели „страдат” като резултат. Намирането на такова решение и определяне с какво това решение е по-добро в сравнение с многото други такива решения е целта при създаването и решаването на един проблем, свързан с многокритериалната оптимизация. | ||
| − | |||
| − | |||
==Въведение== | ==Въведение== | ||
| Ред 22: | Ред 16: | ||
където μ i е i-та целева [[функция]], g и h са неравенства и ограничени равенства, съответно, и х е векторът на оптимизиране, или променливо решение. Решението на по-горния проблем е множеството от точки на [[Парето]] (на англ. [[Set of Pareto points]]. По този начин, вместо да бъде уникално решението на проблема, решението на многокритериалния проблем е вероятно безкрайно множество от точки на Парето. | където μ i е i-та целева [[функция]], g и h са неравенства и ограничени равенства, съответно, и х е векторът на оптимизиране, или променливо решение. Решението на по-горния проблем е множеството от точки на [[Парето]] (на англ. [[Set of Pareto points]]. По този начин, вместо да бъде уникално решението на проблема, решението на многокритериалния проблем е вероятно безкрайно множество от точки на Парето. | ||
| − | |||
| − | |||
Дизайнът на точка в обективното пространство μ* се нарича оптималност на Парето (на англ. [[Pareto optimality]]) , ако не съществува друга възможна цел за проектиране на вектор μ такaва, че µi ≤ µi* за всяко i ={1,2,…,n} и µi < µi* , за най-малко един индекс на j, j = ={1,2,…,n} . | Дизайнът на точка в обективното пространство μ* се нарича оптималност на Парето (на англ. [[Pareto optimality]]) , ако не съществува друга възможна цел за проектиране на вектор μ такaва, че µi ≤ µi* за всяко i ={1,2,…,n} и µi < µi* , за най-малко един индекс на j, j = ={1,2,…,n} . | ||
==Методи за решение== | ==Методи за решение== | ||
| − | |||
| − | |||
| − | |||
| − | |||
Съществуват много методи за намиране на решение на проблема многокритериална оптимизация, някои от които са обяснени по-долу: | Съществуват много методи за намиране на решение на проблема многокритериална оптимизация, някои от които са обяснени по-долу: | ||
| − | |||
| − | |||
===Изграждане на обединена целевата функция (AOF) === | ===Изграждане на обединена целевата функция (AOF) === | ||
| − | |||
| − | |||
Това е интуитивен подход към решаването на многокритериалния проблем. Основната идея е да се обединят всички обективни функции в единна функционална форма, наречена AOF, също позната като претеглена линейна сума на целите. | Това е интуитивен подход към решаването на многокритериалния проблем. Основната идея е да се обединят всички обективни функции в единна функционална форма, наречена AOF, също позната като претеглена линейна сума на целите. | ||
| Ред 50: | Ред 34: | ||
===Методи NBI, SPO, DSD=== | ===Методи NBI, SPO, DSD=== | ||
| − | |||
| − | |||
Методите NBI (Normal Boundary Intersection или Нормални Гранични Пресечки), NC (Normal Contraint или Нормални Ограничения), SPO (Successive Pareto Optimization или Последователна Оптимизация на Парето) и DSD (Directed Search Domain или Пряко Търсене на Доминиране) се използват за решаване на многокритериални оптимизационни проблеми чрез изграждане на няколко AOF-а. Решението на всяка AOF „ражда” точка на Парето. | Методите NBI (Normal Boundary Intersection или Нормални Гранични Пресечки), NC (Normal Contraint или Нормални Ограничения), SPO (Successive Pareto Optimization или Последователна Оптимизация на Парето) и DSD (Directed Search Domain или Пряко Търсене на Доминиране) се използват за решаване на многокритериални оптимизационни проблеми чрез изграждане на няколко AOF-а. Решението на всяка AOF „ражда” точка на Парето. | ||
| Ред 62: | Ред 44: | ||
Еволюционните [[алгоритми]] са популярни подходи за решаване на многокритериална оптимизация. В днешно време, най-еволюционно оптимизиране използва Парето - базиран на [[рангови схеми]]. Генетичните алгоритми, като например за неразпространение на доминиращото сортиране на генетичен алгоритъм-II (NSGA-II) и силата на еволюционния подход на Парето 2 (SPEA-2) са станали стандартни подходи, въпреки че някои схеми, базирани на частиците „рояк” оптимизация и симулираното техническо закаляване са значителни. | Еволюционните [[алгоритми]] са популярни подходи за решаване на многокритериална оптимизация. В днешно време, най-еволюционно оптимизиране използва Парето - базиран на [[рангови схеми]]. Генетичните алгоритми, като например за неразпространение на доминиращото сортиране на генетичен алгоритъм-II (NSGA-II) и силата на еволюционния подход на Парето 2 (SPEA-2) са станали стандартни подходи, въпреки че някои схеми, базирани на частиците „рояк” оптимизация и симулираното техническо закаляване са значителни. | ||
| − | |||
| − | |||
| − | |||
| − | |||
===Други методи=== | ===Други методи=== | ||
| − | |||
| − | |||
* Многокритериална оптимизация използваща еволюционни алгоритми (MOEA - Multiobjective Optimization using Evolutionary Algorithms) | * Многокритериална оптимизация използваща еволюционни алгоритми (MOEA - Multiobjective Optimization using Evolutionary Algorithms) | ||
* Повърхностно размножаване на изпъкнали многокритериални случаи на Парето (PGEN - Pareto surface generation for convex multiobjective instances) | * Повърхностно размножаване на изпъкнали многокритериални случаи на Парето (PGEN - Pareto surface generation for convex multiobjective instances) | ||
* Непряка оптимизация на базата на самоорганизация (IOSO - Indirect Optimization on the basis of Self-Organization) | * Непряка оптимизация на базата на самоорганизация (IOSO - Indirect Optimization on the basis of Self-Organization) | ||
| + | |||
| + | ==Вижте още== | ||
| + | |||
| + | *[[Ефект]] | ||
| + | *[[Резултат]] | ||
| + | *[[План]] | ||
| + | *[[Прогноза]] | ||
| + | *[[Алгоритъм]] | ||
| + | *[[Критерий]] | ||
| + | *[[Решение]] | ||
| + | *[[Избор]] | ||
==Източници== | ==Източници== | ||
| Ред 84: | Ред 71: | ||
* 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. | * 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://www.calresco.org/lucas/pmo.htm Практическа многокритериална оптимизация] | ||
* [http://demonstrations.wolfram.com/EvolutionaryMultiobjectiveOptimization/ Еволюционна многокритериална оптимизация] | * [http://demonstrations.wolfram.com/EvolutionaryMultiobjectiveOptimization/ Еволюционна многокритериална оптимизация] | ||
[[category:Управленски решения и риск]] | [[category:Управленски решения и риск]] | ||
Версия от 16:11, 2 април 2012
Многокритериалната оптимизация (на англ. Multi-objective optimization) или програмиране, известна също като оптимизация с няколко критерия или няколко атрибута, е процес на оптимизиране едновременно на две или повече противоречиви цели при спазване на определени ограничения.
Проблеми за многокритериалната оптимизация могат да се намерят в различни области: продукти в процеса на проектиране, финансиране, конструкция на въздухоплавателни средства, петролна и газова промишленост, автомобилен дизайн или където трябва да се вземат оптимални решения в присъствието на компромиси между две или повече противоречиви цели. Повишаването на приходите и намаляването на стойността на продукта; увеличаването на производителността и свеждането до минимум разхода на гориво на превозното средство; свеждане до минимум на теглото като същевременно се увеличава максималното съдържание на даден компонент са примери за многоцелеви проблеми на оптимизацията.
Ако многокритериалният проблем е добре оформен не трябва да има отделно решение, което едновременно намалява всяка цел, към своята най-голяма. Във всеки случай, една цел трябва да е достигнала връх така, че когато се опитва да оптимизира целта по-нататък, другите цели „страдат” като резултат. Намирането на такова решение и определяне с какво това решение е по-добро в сравнение с многото други такива решения е целта при създаването и решаването на един проблем, свързан с многокритериалната оптимизация.
Въведение
От математическа гледна точка, многокритериалния проблем може да се запише като
min(x) [µ1(x), µ2(x), …, µn(x) ]' при следните ограничения g(x) ≤ 0 h(x) = 0 xi ≤ x ≤ xu
където μ i е i-та целева функция, g и h са неравенства и ограничени равенства, съответно, и х е векторът на оптимизиране, или променливо решение. Решението на по-горния проблем е множеството от точки на Парето (на англ. Set of Pareto points. По този начин, вместо да бъде уникално решението на проблема, решението на многокритериалния проблем е вероятно безкрайно множество от точки на Парето.
Дизайнът на точка в обективното пространство μ* се нарича оптималност на Парето (на англ. Pareto optimality) , ако не съществува друга възможна цел за проектиране на вектор μ такaва, че µi ≤ µi* за всяко i ={1,2,…,n} и µi < µi* , за най-малко един индекс на j, j = ={1,2,…,n} .
Методи за решение
Съществуват много методи за намиране на решение на проблема многокритериална оптимизация, някои от които са обяснени по-долу:
Изграждане на обединена целевата функция (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.