خوارزمية تقدير التوزيع

UMDA ^{[ 5 ]} هو برنامج EDA بسيط يستخدم عاملًا${\displaystyle \alpha _{UMDA}}$لتقدير الاحتمالات الهامشية من مجموعة سكانية مختارة${\displaystyle S(P(t))}$بافتراض${\displaystyle S(P(t))}$يحتوي${\displaystyle \lambda }$عناصر،${\displaystyle \alpha _{UMDA}}$ينتج الاحتمالات:

${\displaystyle p_{t+1}(X_{i})={\dfrac {1}{\lambda }}\sum _{x\in S(P(t))}x_{i},~\forall i\in 1,2,\dots ,N.}$

يمكن وصف كل خطوة من خطوات UMDA على النحو التالي

${\displaystyle D(t+1)=\alpha _{\text{UMDA}}\circ S\circ \beta _{\lambda }(D(t)).}$

يمثل نموذج PBIL ^{[ 6 ]} السكان ضمنيًا من خلال نموذجه، والذي يقوم من خلاله بأخذ عينات من الحلول الجديدة وتحديث النموذج. في كل جيل،${\displaystyle \mu }$يتم أخذ عينات من الأفراد و${\displaystyle \lambda \leq \mu }$يتم اختيارهم. ثم يتم استخدام هؤلاء الأفراد لتحديث النموذج على النحو التالي

${\displaystyle p_{t+1}(X_{i})=(1-\gamma )p_{t}(X_{i})+(\gamma /\lambda )\sum _{x\in S(P(t))}x_{i},~\forall i\in 1,2,\dots ,N,}$

أين${\displaystyle \gamma \in (0,1]}$هو مُعامل يُحدد معدل التعلم ، وقيمته الصغيرة تُحدد أن النموذج السابق${\displaystyle p_{t}(X_{i})}$ينبغي أن تتأثر بشكل طفيف فقط بالحلول الجديدة التي تم أخذ عينات منها. يمكن وصف PBIL على النحو التالي:

${\displaystyle D(t+1)=\alpha _{\text{PIBIL}}\circ S\circ \beta _{\mu }(D(t))}$

تعتمد طريقة CGA، ^{[ 7 ]} أيضًا على التجمعات السكانية الضمنية المحددة بواسطة التوزيعات أحادية المتغير. في كل جيل${\displaystyle t}$شخصان${\displaystyle x,y}$يتم أخذ عينات منها،${\displaystyle P(t)=\beta _{2}(D(t))}$السكان${\displaystyle P(t)}$ثم يتم ترتيبها تنازليًا حسب مستوى لياقتها،${\displaystyle S_{{\text{Sort}}(f)}(P(t))}$، مع${\displaystyle u}$أن تكون الأفضل و${\displaystyle v}$باعتبارها الحل الأسوأ. تُقدّر CGA احتمالات المتغيرات الأحادية على النحو التالي

${\displaystyle p_{t+1}(X_{i})=p_{t}(X_{i})+\gamma (u_{i}-v_{i}),\quad \forall i\in 1,2,\dots ,N,}$

أين،${\displaystyle \gamma \in (0,1]}$هو ثابت يحدد معدل التعلم ، وعادة ما يتم ضبطه على${\displaystyle \gamma =1/N}$يمكن تعريف CGA على النحو التالي:

${\displaystyle D(t+1)=\alpha _{\text{CGA}}\circ S_{{\text{Sort}}(f)}\circ \beta _{2}(D(t))}$

تقوم طريقة MIMIC ^{[ 8 ]} بتحليل التوزيع الاحتمالي المشترك في نموذج يشبه السلسلة يمثل التبعيات المتتالية بين المتغيرات. وتجد هذه الطريقة تبديلاً لمتغيرات القرار،${\displaystyle r:i\mapsto j}$بحيث${\displaystyle x_{r(1)}x_{r(2)},\dots ,x_{r(N)}}$يقلل من تباعد كولباك-لايبير بالنسبة لتوزيع الاحتمالية الحقيقي، أي${\displaystyle \pi _{r(i+1)}=\{X_{r(i)}\}}$. نماذج MIMIC هي توزيع

${\displaystyle p_{t+1}(X_{1},\dots ,X_{N})=p_{t}(X_{r(N)})\prod _{i=1}^{N-1}p_{t}(X_{r(i)}|X_{r(i+1)}).}$

تُختار الحلول الجديدة من المتغير الأيسر إلى المتغير الأيمن، حيث يُولّد الحل الأول بشكل مستقل، بينما تُولّد الحلول الأخرى وفقًا للاحتمالات الشرطية. ونظرًا لأنه يجب إعادة حساب التوزيع المُقدّر في كل جيل، فإنّ MIMIC تستخدم مجموعات سكانية محددة بالطريقة التالية.

${\displaystyle P(t+1)=\beta _{\mu }\circ \alpha _{\text{MIMIC}}\circ S(P(t)).}$

تقوم طريقة BMDA ^{[ 9 ]} بتحليل التوزيع الاحتمالي المشترك إلى توزيعات ثنائية المتغيرات. أولاً، تتم إضافة متغير مختار عشوائياً كعقدة في الرسم البياني، ثم يتم اختيار المتغير الأكثر اعتماداً على أحد المتغيرات الموجودة في الرسم البياني من بين المتغيرات غير الموجودة فيه، وتُكرر هذه العملية حتى لا يعتمد أي متغير متبقٍ على أي متغير في الرسم البياني (يتم التحقق من ذلك وفقاً لقيمة عتبة).

النموذج الناتج عبارة عن غابة ذات أشجار متعددة متجذرة عند العقد${\displaystyle \Upsilon _{t}}$بالنظر إلى${\displaystyle I_{t}}$بالنسبة للمتغيرات غير الجذرية، تُقدّر BMDA توزيعًا مُعاملًا يمكن فيه أخذ عينات من المتغيرات الجذرية بشكل مستقل، بينما يجب أن تكون جميع المتغيرات الأخرى مشروطة بالمتغير الأبوي.${\displaystyle \pi _{i}}$.

${\displaystyle p_{t+1}(X_{1},\dots ,X_{N})=\prod _{X_{i}\in \Upsilon _{t}}p_{t}(X_{i})\cdot \prod _{X_{i}\in I_{t}}p_{t}(X_{i}|\pi _{i}).}$

تُعرَّف كل خطوة من خطوات BMDA على النحو التالي:

${\displaystyle P(t+1)=\beta _{\mu }\circ \alpha _{\text{BMDA}}\circ S(P(t)).}$

كانت ECGA ^{[ 10 ]} من أوائل مناهج تحليل البيانات الاستكشافية التي استخدمت التحليل متعدد المتغيرات، والذي يسمح بنمذجة التبعيات عالية الرتبة بين متغيرات القرار. ويقوم منهجها بتحليل التوزيع الاحتمالي المشترك إلى حاصل ضرب التوزيعات الحدية متعددة المتغيرات.${\displaystyle T_{\text{eCGA}}=\{\tau _{1},\dots ,\tau _{\Psi }\}}$هي مجموعة من المجموعات الجزئية، حيث كل${\displaystyle \tau \in T_{\text{eCGA}}}$هي مجموعة روابط، تحتوي على${\displaystyle |\tau |\leq K}$المتغيرات. يتم تمثيل توزيع الاحتمال المشترك المُحلل على النحو التالي

${\displaystyle p(X_{1},\dots ,X_{N})=\prod _{\tau \in T_{\text{eCGA}}}p(\tau ).}$

شاع استخدام مصطلح "تعلم الارتباط" في خوارزمية ECGA للدلالة على الإجراءات التي تحدد مجموعات الارتباط. ويعتمد إجراء تعلم الارتباط الخاص بها على مقياسين: (1) تعقيد النموذج (MC) و(2) تعقيد المجموعة المضغوطة (CPC). يقيس تعقيد النموذج حجم تمثيل النموذج من حيث عدد البتات اللازمة لتخزين جميع الاحتمالات الهامشية.

${\displaystyle MC=\log _{2}(\lambda +1)\sum _{\tau \in T_{\text{eCGA}}}(2^{|\tau |-1}),}$

من ناحية أخرى، يقيس مؤشر ضغط البيانات (CPC) ضغط البيانات من حيث إنتروبيا التوزيع الهامشي على جميع الأقسام، حيث${\displaystyle \lambda }$حجم السكان المختار،${\displaystyle |\tau |}$يمثل عدد متغيرات القرار في مجموعة الارتباط${\displaystyle \tau }$و${\displaystyle H(\tau )}$يمثل الإنتروبيا المشتركة للمتغيرات في${\displaystyle \tau }$

${\displaystyle CPC=\lambda \sum _{\tau \in T_{\text{eCGA}}}H(\tau ).}$

تعمل عملية تعلم الربط في ECGA على النحو التالي: (1) إدخال كل متغير في مجموعة، (2) حساب معامل الارتباط CCC = MC + CPC لمجموعات الربط الحالية، (3) التحقق من الزيادة في معامل الارتباط CCC الناتجة عن ضم أزواج المجموعات، (4) ضم المجموعات التي حققت أعلى تحسن في معامل الارتباط CCC. تُكرر هذه العملية حتى يتعذر تحقيق أي تحسينات في معامل الارتباط CCC، مما ينتج عنه نموذج ربط.${\displaystyle T_{\text{eCGA}}}$يعمل نموذج ECGA مع مجموعات سكانية محددة، وبالتالي، باستخدام التوزيع المُعامل الذي يُنمذجه نموذج ECGA، يمكن وصفه على النحو التالي:

${\displaystyle P(t+1)=\beta _{\mu }\circ \alpha _{\text{eCGA}}\circ S(P(t))}$

تستخدم خوارزمية BOA ^{[ 11 ] [ 12 ] [ 13 ]} الشبكات البايزية لنمذجة الحلول الواعدة وأخذ عينات منها. الشبكات البايزية عبارة عن رسوم بيانية موجهة غير دورية، حيث تمثل العقد المتغيرات، وتمثل الحواف الاحتمالات الشرطية بين أزواج المتغيرات. قيمة المتغير${\displaystyle x_{i}}$يمكن اشتراط ذلك بحد أقصى لـ${\displaystyle K}$متغيرات أخرى، محددة في${\displaystyle \pi _{i}}$. يقوم BOA ببناء PGM الذي يرمز إلى توزيع مشترك عاملي، حيث يتم تقدير معلمات الشبكة، أي الاحتمالات الشرطية، من السكان المختارين باستخدام مقدر الاحتمال الأقصى.

${\displaystyle p(X_{1},X_{2},\dots ,X_{N})=\prod _{i=1}^{N}p(X_{i}|\pi _{i}).}$

من ناحية أخرى، يجب بناء بنية الشبكة البايزية بشكل تكراري (تعلم الارتباط). تبدأ بشبكة بدون حواف، وفي كل خطوة، تُضاف الحافة التي تُحسّن أحد مقاييس التقييم (مثل معيار معلومات بايز (BIC) أو مقياس بايز-ديريشليه مع تكافؤ الاحتمالية (BDe)). ^{[ 14 ]} يُقيّم مقياس التقييم بنية الشبكة وفقًا لدقتها في نمذجة المجموعة السكانية المختارة. من الشبكة المبنية، تُجري خوارزمية BOA عملية أخذ عينات من حلول واعدة جديدة على النحو التالي: (1) حساب الترتيب السلفي لكل متغير، حيث يسبق كل عقدة آباؤها؛ (2) أخذ عينة من كل متغير بشكل مشروط بآبائه. في ظل هذا السيناريو، يمكن تعريف كل خطوة من خطوات خوارزمية BOA على النحو التالي:

${\displaystyle P(t+1)=\beta _{\mu }\circ \alpha _{\text{BOA}}\circ S(P(t))}$

يختلف نموذج LTGA ^{[ 15 ]} عن معظم نماذج EDA في كونه لا يُنمذج توزيعًا احتماليًا بشكل صريح، بل نموذج ارتباط يُسمى شجرة الارتباط.${\displaystyle T}$هي مجموعة من مجموعات الارتباط بدون توزيع احتمالي مرتبط بها، وبالتالي، لا توجد طريقة لأخذ عينات من حلول جديدة مباشرة من${\displaystyle T}$. نموذج الارتباط هو شجرة ارتباط يتم إنتاجها وتخزينها كعائلة من المجموعات (FOS).

${\displaystyle T_{\text{LT}}=\{\{x_{1}\},\{x_{2}\},\{x_{3}\},\{x_{4}\},\{x_{1},x_{2}\},\{x_{3},x_{4}\}\}.}$

تُعدّ عملية تعلم شجرة الارتباط خوارزمية تجميع هرمية ، وتعمل على النحو التالي: في كل خطوة، يتم تحديد أقرب مجموعتين${\displaystyle i}$و${\displaystyle j}$بعد دمجها، تتكرر هذه العملية حتى تبقى مجموعة واحدة فقط، ويتم تخزين كل شجرة فرعية كمجموعة فرعية.${\displaystyle \tau \in T_{\text{LT}}}$.

تستخدم LTGA${\displaystyle T_{\text{LT}}}$لتوجيه إجراء "الخلط الأمثل" الذي يشبه عامل إعادة التركيب ولكنه لا يقبل إلا الحركات المُحسِّنة. نرمز إليه بـ${\displaystyle R_{\text{LTGA}}}$، حيث الترميز${\displaystyle x[\tau ]\gets y[\tau ]}$يشير إلى نقل المادة الوراثية المفهرسة بواسطة${\displaystyle \tau }$من${\displaystyle y}$ل${\displaystyle x}$.

خوارزمية المزج الأمثل لمجموعة الجينات المدخلات: مجموعة من المجموعات الجزئية${\displaystyle T_{\text{LT}}}$وعدد السكان${\displaystyle P(t)}$ الناتج: عدد السكان${\displaystyle P(t+1)}$لكل ​${\displaystyle x_{i}}$في${\displaystyle P(t)}$افعل ذلك لكل${\displaystyle \tau }$في${\displaystyle T_{\text{LT}}}$اختر عشوائيًا${\displaystyle x_{j}\in P(t):x_{i}\neq x_{j}}$${\displaystyle f_{x_{i}}}$:=${\displaystyle f(x_{i})}$${\displaystyle x_{i}[\tau ]}$:=${\displaystyle x_{j}[\tau ]}$لو${\displaystyle f(x_{i})\leq f_{x_{i}}}$ثم${\displaystyle x_{i}[\tau ]:=x_{j}[\tau ]}$يعود${\displaystyle P(t)}$

لا تُطبّق خوارزمية LTGA عوامل الاختيار التقليدية، بل يتم الاختيار أثناء عملية إعادة التركيب. وقد طُبّقت أفكار مماثلة عادةً في طرق البحث المحلي، ومن هذا المنطلق، يُمكن اعتبار خوارزمية LTGA طريقةً هجينة. باختصار، تُعرّف إحدى خطوات خوارزمية LTGA على النحو التالي:

${\displaystyle P(t+1)=R_{\text{LTGA}}(P(t))\circ \alpha _{\text{LTGA}}(P(t))}$