جبهة باريتو

في التحسين متعدد الأهداف ، تُعرف جبهة باريتو (وتُسمى أيضًا منحنى باريتو ) بأنها مجموعة جميع الحلول الكفؤة وفقًا لمبدأ باريتو . ^{[ 1 ]} وبعبارة أخرى، عندما يكون هناك العديد من الأهداف المختلفة التي يجب مراعاتها في مسألة تحسين ، فإن جبهة باريتو تمثل مجموعة الحلول التي لا يتفوق فيها أي حل على أي حل آخر في المجموعة عند كل هدف، ويتفوق فيها حل واحد على الأقل من حلول جبهة باريتو على أي حل خارج المجموعة عند كل هدف. ^{[ 2 ]} يُستخدم هذا المفهوم على نطاق واسع في الهندسة . ^{[ 3 ] : 111-148} فهو يسمح للمصمم بالتركيز على مجموعة الخيارات الكفؤة، وإجراء المفاضلات ضمن هذه المجموعة، بدلًا من النظر في النطاق الكامل لكل مُعامل. ^{[ 4 ] : ​​63-65 [ 5 ] : 399-412}

يمكن وصف حدود باريتو، P ( Y )، بشكل أكثر رسمية على النحو التالي. لنفترض نظامًا بدالة${\displaystyle f:X\rightarrow \mathbb {R} ^{m}}$حيث X هي مجموعة مضغوطة من القرارات الممكنة في الفضاء المتري${\displaystyle \mathbb {R} ^{n}}$و Y هي مجموعة متجهات المعيار الممكنة في${\displaystyle \mathbb {R} ^{m}}$بحيث${\displaystyle Y=\{y\in \mathbb {R} ^{m}:\;y=f(x),x\in X\;\}}$.

نفترض أن الاتجاهات المفضلة لقيم المعايير معروفة. نقطة${\displaystyle y^{\prime \prime }\in \mathbb {R} ^{m}}$يُفضَّل على (يُهيمن تمامًا على) نقطة أخرى${\displaystyle y^{\prime }\in \mathbb {R} ^{m}}$، مكتوبة على النحو التالي${\displaystyle y^{\prime \prime }\succ y^{\prime }}$وبالتالي، تُكتب حدود باريتو على النحو التالي:

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

من الجوانب المهمة لحدود باريتو في علم الاقتصاد أنه عند تخصيص الموارد بكفاءة باريتو، يكون معدل الإحلال الحدي متساوياً لجميع المستهلكين. ^{[ 6 ]} ويمكن اشتقاق بيان رسمي من خلال النظر في نظام يتكون من m مستهلكين و n سلعة، ودالة منفعة لكل مستهلك على النحو التالي:${\displaystyle z_{i}=f^{i}(x^{i})}$أين${\displaystyle x^{i}=(x_{1}^{i},x_{2}^{i},\ldots ,x_{n}^{i})}$يمثل متجه البضائع، وذلك لجميع قيم i . ويُعد قيد الجدوى هو${\displaystyle \sum _{i=1}^{m}x_{j}^{i}=b_{j}}$ل${\displaystyle j=1,\ldots ,n}$لإيجاد التخصيص الأمثل وفقًا لمبدأ باريتو، نقوم بتعظيم دالة لاغرانج :

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

أين${\displaystyle (\lambda _{k})_{k}}$و${\displaystyle (\mu _{j})_{j}}$هي متجهات المضاعفات. بأخذ المشتقة الجزئية للدالة لاغرانج بالنسبة لكل سلعة${\displaystyle x_{j}^{k}}$ل${\displaystyle j=1,\ldots ,n}$و${\displaystyle k=1,\ldots ,m}$يُعطي النظام التالي من الشروط من الدرجة الأولى:

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

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

أين${\displaystyle f_{x_{j}^{i}}}$يرمز إلى المشتق الجزئي لـ${\displaystyle f}$بالنسبة إلى${\displaystyle x_{j}^{i}}$والآن، قم بإصلاح أي${\displaystyle k\neq i}$و${\displaystyle j,s\in \{1,\ldots ,n\}}$الشرط من الدرجة الأولى المذكور أعلاه يعني أن

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

وبالتالي، في التخصيص الأمثل وفقًا لمبدأ باريتو، يجب أن يكون معدل الإحلال الحدي متساويًا لجميع المستهلكين. ^{[ 7 ]}

تمت دراسة خوارزميات حساب حدود باريتو لمجموعة محدودة من البدائل في علوم الحاسوب وهندسة الطاقة. ^{[ 8 ]} وتشمل هذه الخوارزميات ما يلي:

• " القيم العظمى لمجموعة نقاط "
• "مشكلة المتجه الأقصى" أو استعلام الأفق ^{[ 9 ] [ 10 ] [ 11 ]}
• "خوارزمية التحويل إلى عدد قياسي" أو طريقة المجاميع المرجحة ^{[ 12 ] [ 13 ]}
• "ال${\displaystyle \epsilon }$طريقة القيود ^{[ 14 ] [ 15 ] [ 16 ]}
• الخوارزميات التطورية متعددة الأهداف ^{[ 17 ] [ 18 ]}

نظرًا لأن توليد جبهة باريتو الكاملة غالبًا ما يكون عملية معقدة حسابيًا، توجد خوارزميات لحساب جبهة باريتو تقريبية. على سبيل المثال، يُطلق ليغريل وآخرون ^{[ 19 ]} على المجموعة S اسم تقريب ε لجبهة باريتو P ، إذا كانت مسافة هاوسدورف الموجهة بين S و P لا تتجاوز ε . وقد لاحظوا أنه يمكن إيجاد تقريب ε لأي جبهة باريتو P في d بُعد باستخدام (1/ ε ) ^d استعلامًا.

قام زيتزلر ونولز وثيل ^{[ 20 ]} بمقارنة العديد من الخوارزميات لتقريب مجموعة باريتو على معايير مختلفة، مثل عدم التأثر بالقياس، والرتابة، والتعقيد الحسابي.