पैरेटो फ्रंट

बहुउद्देश्यीय अनुकूलन में, पैरेटो फ्रंट सभी पारेटो कुशल समाधानों का समुच्चय है। इसे व्यापक रूप से अभियांत्रिकी में उपयोग किया जाता है। यह प्रारूपो को प्रत्येक पैरामीटर की पूरी श्रृंखला पर विचार करने के अतिरक्त कुशल विकल्पों के समुच्चय पर ध्यान केंद्रित करने और इस समुच्चय के अंदर व्यापार-बंद करने की अनुमति देता है।

पैरेटो फ्रंटियर का उदाहरण। बॉक्सिंग बिंदु व्यवहार्य विकल्पों का प्रतिनिधित्व करते हैं, और छोटे मूल्यों को बड़े लोगों के लिए पसंद किया जाता है। बिंदु C पेरेटो सीमा पर नहीं है क्योंकि यह बिंदु A और बिंदु B दोनों का प्रभुत्व है। बिंदु A और B पर किसी अन्य का सख्ती से प्रभुत्व नहीं है, और इसलिए यह सीमा पर स्थित है।

उत्पादन-संभावना की सीमा। लाल रेखा पारेटो-कुशल फ्रंटियर का एक उदाहरण है, जहां सीमांत और उसके नीचे का क्षेत्र विकल्पों का एक सतत समुच्चय है। सीमांत पर लाल बिंदु उत्पादन के पारेटो-इष्टतम विकल्पों के उदाहरण हैं। सीमा से दूर के बिंदु, जैसे कि N और K, पारेतो-प्रभावी नहीं हैं, क्योंकि सीमांत पर ऐसे बिंदु मौजूद हैं जो उन पर पारेटो-प्रभुत्व रखते हैं।

परिभाषा

पेरेटो फ्रंटियर, पी (वाई), को अधिक औपचारिक रूप से निम्नानुसार वर्णित किया जा सकता है। कार्य के साथ एक प्रणाली पर विचार करें $f:X\rightarrow \mathbb {R} ^{m}$, जहाँ X मीट्रिक स्थान में व्यवहार्य निर्णयों का एक कॉम्पैक्ट जगह है $\mathbb {R} ^{n}$, और Y में कसौटी सदिश का व्यवहार्य समुच्चय है $\mathbb {R} ^{m}$, ऐसा है कि $Y=\{y\in \mathbb {R} ^{m}:\;y=f(x),x\in X\;\}$.

हम मानते हैं कि मापदंड मानों की पसंदीदा दिशाएँ ज्ञात हैं। एक बिंदु $y^{\prime \prime }\in \mathbb {R} ^{m}$ एक और बिंदु के लिए (सख्ती से हावी) पसंद किया जाता है $y^{\prime }\in \mathbb {R} ^{m}$, के रूप में लिखा गया है $y^{\prime \prime }\succ y^{\prime }$. पेरेटो सीमांत इस प्रकार लिखा गया है:

$P(Y)=\{y^{\prime }\in Y:\;\{y^{\prime \prime }\in Y:\;y^{\prime \prime }\succ y^{\prime },y^{\prime }\neq y^{\prime \prime }\;\}=\emptyset \}.$

प्रतिस्थापन की सीमांत दर

अर्थशास्त्र में पैरेटो फ्रंटियर का एक महत्वपूर्ण दृष्टीकोण यह है कि पारेतो-कुशल आवंटन पर, प्रतिस्थापन की सीमांत दर सभी उपभोक्ताओं के लिए समान होती है। एम उपभोक्ताओं और एन वस्तुओं के साथ एक प्रणाली और प्रत्येक उपभोक्ता के उपयोगिता समारोह के रूप में विचार करके एक औपचारिक बयान प्राप्त किया जा सकता है $z_{i}=f^{i}(x^{i})$ जहां $x^{i}=(x_{1}^{i},x_{2}^{i},\ldots ,x_{n}^{i})$, सभी के लिए मान सदिश है,जो सभी के लिए व्यवहार्यता बाधा है $\sum _{i=1}^{m}x_{j}^{i}=b_{j}$ के लिए $j=1,\ldots ,n$. पेरेटो इष्टतम आवंटन खोजने के लिए, हम लैग्रैंगियन यांत्रिकी को अधिकतम प्रयोग करते हैं:

$L_{i}((x_{j}^{k})_{k,j},(\lambda _{k})_{k},(\mu _{j})_{j})=f^{i}(x^{i})+\sum _{k=2}^{m}\lambda _{k}(z_{k}-f^{k}(x^{k}))+\sum _{j=1}^{n}\mu _{j}\left(b_{j}-\sum _{k=1}^{m}x_{j}^{k}\right)$

जहाँ $(\lambda _{k})_{k}$ और $(\mu _{j})_{j}$ गुणक के सदिश हैं। प्रत्येक अच्छे संबंध में लैग्रैंगियन का आंशिक व्युत्पन्न लेना $x_{j}^{k}$ के लिए $j=1,\ldots ,n$ और $k=1,\ldots ,m$ और प्रथम-क्रम स्थितियों की निम्नलिखित प्रणाली देता है:

${\frac {\partial L_{i}}{\partial x_{j}^{i}}}=f_{x_{j}^{i}}^{1}-\mu _{j}=0{\text{ for }}j=1,\ldots ,n,$

${\frac {\partial L_{i}}{\partial x_{j}^{k}}}=-\lambda _{k}f_{x_{j}^{k}}^{i}-\mu _{j}=0{\text{ for }}k=2,\ldots ,m{\text{ and }}j=1,\ldots ,n,$

जहाँ $f_{x_{j}^{i}}$ के आंशिक व्युत्पन्न को दर्शाता है $f$ इसके संबंध में $x_{j}^{i}$. अब, कोई भी ठीक करें $k\neq i$ और $j,s\in \{1,\ldots ,n\}$. उपरोक्त प्रथम-क्रम की स्थिति का अर्थ है

${\frac {f_{x_{j}^{i}}^{i}}{f_{x_{s}^{i}}^{i}}}={\frac {\mu _{j}}{\mu _{s}}}={\frac {f_{x_{j}^{k}}^{k}}{f_{x_{s}^{k}}^{k}}}.$

इस प्रकार, पारेतो-इष्टतम आवंटन में, प्रतिस्थापन की सीमांत दर सभी उपभोक्ताओं के लिए समान होनी चाहिए।

गणना

कंप्यूटर विज्ञान और पावर अभियांत्रिकी में विकल्पों के एक सीमित समुच्चय के पैरेटो फ्रंटियर की गणना के लिए कलन विधि का अध्ययन किया गया है।

• अधिकतम वेक्टर समस्या या स्काईलाइन ऑपरेटर।
• स्केलराइजेशन एल्गोरिदम या भारित रकम की विधि।
• $\epsilon$वें>-प्रतिबंध विधि।

अनुमान

चूंकि पूरे पारेटो फ्रंट को उत्पन्न करना अक्सर कम्प्यूटेशनल रूप से कठिन होता है, एक अनुमानित पारेटो-फ्रंट की गणना के लिए एल्गोरिदम होते हैं। उदाहरण के लिए, लेग्रियल एट अल। एक समुच्चय S को परेटो-फ्रंट P का 'ε-सन्निकटन' कहते हैं, यदि S और P के बीच हॉसडॉर्फ की निर्देशित दूरी अधिक से अधिक ε है। वे देखते हैं कि d आयामों में किसी भी पेरेटो फ्रंट P का ε-अनुमानन (1/ε) का उपयोग करके पाया जा सकता है।^d प्रश्न।

Zitzler, नोल्स और थिएले विभिन्न मानदंडों पर पारेटो- समुच्चय सन्निकटन के लिए कई एल्गोरिदम की तुलना करें, जैसे स्केलिंग, मोनोटोनिसिटी और कम्प्यूटेशनल जटिलता के लिए व्युत्क्रम।

बाहरी संबंध

• Code to compute the Pareto front of a finite set of points in Julia: https://github.com/cossio/ParetoEfficiency.jl.