Pareto fram

I multi-objektiv optimering är Pareto-fronten ( även kallad Pareto-gräns eller Pareto-kurva ) uppsättningen av alla Pareto-effektiva lösningar. Konceptet används flitigt inom teknik . Det gör det möjligt för designern att begränsa uppmärksamheten till uppsättningen av effektiva val, och att göra avvägningar inom denna uppsättning, snarare än att överväga hela spektrumet av varje parameter.

Exempel på en Pareto-gräns. De inrutade punkterna representerar möjliga val, och mindre värden är att föredra framför större. Punkt C ligger inte på Pareto-gränsen eftersom den domineras av både punkt A och punkt B. Punkterna A och B domineras inte strikt av någon annan, och ligger därför på gränsen.

En produktionsmöjlighetsgräns . Den röda linjen är ett exempel på en Pareto-effektiv gräns, där gränsen och området till vänster och under den är en kontinuerlig uppsättning val. De röda punkterna på gränsen är exempel på Pareto-optimala val av produktion. Punkter utanför gränsen, såsom N och K, är inte Pareto-effektiva, eftersom det finns punkter på gränsen som Pareto-dominerar dem.

Definition

Pareto-gränsen, P ( Y ), kan mer formellt beskrivas enligt följande. Betrakta ett system med funktionen ${\displaystyle f:X\rightarrow \mathbb {R} ^{m}} ,$ där X är en kompakt uppsättning möjliga beslut i det metriska utrymmet $\mathbb {R} ^{n}$ , och Y är den möjliga uppsättningen av kriterievektorer i $\mathbb {R} ^{m}$ , så att $Y=\{y\in \mathbb {R} ^{m}:\;y=f(x),x\in X\;\}$ .

Vi antar att de föredragna riktningarna för kriterievärden är kända. En punkt $y^{\prime \prime }\in \mathbb {R} ^{m}$ föredras framför (strikt dominerar) en annan punkt $y^ {\prime }\in \mathbb {R} ^{m}$ , skrivet som $y^{\prime \prime }\succ y^{\prime }$ . Pareto-gränsen är alltså skriven som:

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

Marginal substitutionsgrad

En betydande aspekt av Pareto-gränsen inom ekonomi är att, vid en Pareto-effektiv allokering, är den marginala substitutionsgraden densamma för alla konsumenter. Ett formellt uttalande kan härledas genom att betrakta ett system med m konsumenter och n varor, och en nyttofunktion för varje konsument som $z_{i}=f^{i}(x^ {i})$ där $x^{i}=(x_{1}^{i},x_{2}^{i },\ldots ,x_{n}^{i})$ är vektorn av varor, både för alla i . Genomförbarhetsbegränsningen är $\sum _{i=1}^{m}x_{j}^{i}=b_{j}$ för $j=1,\ldots ,n$ . För att hitta den optimala Pareto-allokeringen maximerar vi Lagrangian :

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

där $(\lambda _{k})_{k}$ och $(\mu _{j})_{j}$ är vektorerna för multiplikatorer. Att ta den partiella derivatan av lagrangian med avseende på varje god $x_{j}^{k}$ för $j=1,\ldots ,n$ och $k=1,\ldots ,m$ och ger följande system av första ordningens villkor:

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

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

där $f_{x_{j}^{i}}$ betecknar den partiella derivatan av $f$ med avseende på $x_{j}^{i}$ . Fixa nu alla $k\neq i$ och $j,s\in \{1,\ldots ,n\}$ . Ovanstående första ordningens villkor innebär det

${\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}} }.$

I en Pareto-optimal allokering måste således den marginala substitutionsgraden vara densamma för alla konsumenter.

Beräkning

Algoritmer för att beräkna Pareto-gränsen för en ändlig uppsättning alternativ har studerats inom datavetenskap och kraftteknik. De inkluderar:

• "Det maximala vektorproblemet" eller skylinefrågan .
• "Skalariseringsalgoritmen" eller metoden för viktade summor.
• " Metoden $\epsilon$ -constraints".

Uppskattningar

Eftersom det ofta är beräkningssvårt att generera hela Pareto-fronten, finns det algoritmer för att beräkna en ungefärlig Pareto-front. Till exempel har Legriel et al. kalla en mängd S en ε -approximation av Pareto-fronten P , om det riktade Hausdorff-avståndet mellan S och P är som mest ε . De observerar att en ε -approximation av alla Pareto front P i d dimensioner kan hittas med hjälp av (1/ ε ) ^d frågor.

Zitzler, Knowles och Thiele jämför flera algoritmer för Pareto-uppsättningsapproximationer på olika kriterier, såsom invarians till skalning, monotoni och beräkningskomplexitet.

externa länkar

• Kod för att beräkna Pareto-fronten för en ändlig uppsättning punkter i Julia: https://github.com/cossio/ParetoEfficiency.jl .