อัลกอริทึมการประมาณการกระจาย ( EDA ) บางครั้งเรียกว่าอัลกอริทึมพันธุกรรมการสร้างแบบจำลองความน่าจะเป็น (PMBGA) ^{[ 1 ]}เป็น วิธี การเพิ่มประสิทธิภาพแบบสุ่มที่ชี้นำการค้นหาค่าที่เหมาะสมที่สุดโดยการสร้างและสุ่มตัวอย่างแบบจำลองความน่าจะเป็นที่ชัดเจนของโซลูชันที่เป็นไปได้ การเพิ่มประสิทธิภาพถูกมองว่าเป็นชุดของการอัปเดตแบบจำลองความน่าจะเป็นทีละน้อย โดยเริ่มจากแบบจำลองที่เข้ารหัสความน่าจะเป็นก่อนหน้าที่ไม่ให้ข้อมูลใดๆ เกี่ยวกับโซลูชันที่ยอมรับได้ และสิ้นสุดด้วยแบบจำลองที่สร้างเฉพาะค่าที่เหมาะสมที่สุดทั่วโลก ^{[ 2 ] [ 3 ] [ 4 ]}

EDA จัดอยู่ในกลุ่มของอัลกอริธึมเชิงวิวัฒนาการความแตกต่างหลักระหว่าง EDA กับอัลกอริธึมเชิงวิวัฒนาการทั่วไปส่วนใหญ่คือ อัลกอริธึมเชิงวิวัฒนาการสร้างโซลูชันที่เป็นไปได้ใหม่โดยใช้ การแจกแจง แบบแฝงที่กำหนดโดยตัวดำเนินการแปรผันหนึ่งตัวหรือมากกว่า ในขณะที่ EDA ใช้ การแจกแจงความน่าจะ เป็นแบบชัดเจนที่เข้ารหัสโดยเครือข่ายเบย์เซียนการแจกแจงปกติแบบหลายตัวแปรหรือคลาสโมเดลอื่น ๆ เช่นเดียวกับอัลกอริธึมเชิงวิวัฒนาการอื่น ๆ EDA สามารถใช้แก้ปัญหาการหาค่าเหมาะสมที่สุดที่กำหนดไว้บนรูปแบบต่างๆ ตั้งแต่เวกเตอร์ไปจนถึง นิพจน์ S แบบ LISPและคุณภาพของโซลูชันที่เป็นไปได้มักจะถูกประเมินโดยใช้ฟังก์ชันวัตถุประสงค์หนึ่งตัวหรือมากกว่า

ขั้นตอนทั่วไปของการวิเคราะห์ข้อมูลเชิงสำรวจ (EDA) มีรายละเอียดดังต่อไปนี้:

t  := 0 เริ่มต้นโมเดล M(0) เพื่อแสดงการกระจายแบบสม่ำเสมอเหนือโซลูชันที่ยอมรับได้ ในขณะที่ (ไม่ตรงตามเกณฑ์การยุติ) ให้ทำดังนี้P  := สร้างโซลูชันที่เป็นไปได้ N>0 รายการโดยการสุ่มตัวอย่าง M( t ) F  := ประเมินโซลูชันที่เป็นไปได้ทั้งหมดในP M(t + 1) := ปรับโมเดล ( P , F , M( t )) t  := t + 1 

การใช้แบบจำลองความน่าจะเป็นที่ชัดเจนในการหาค่าเหมาะสมที่สุด ทำให้ EDA สามารถแก้ปัญหาการหาค่าเหมาะสมที่สุดที่ยากอย่างยิ่งสำหรับอัลกอริธึมวิวัฒนาการทั่วไปและเทคนิคการหาค่าเหมาะสมที่สุดแบบดั้งเดิมได้ เช่น ปัญหาที่มีระดับepistasis สูง อย่างไรก็ตาม ข้อดีของ EDA คืออัลกอริธึมเหล่านี้ให้แบบจำลองความน่าจะเป็นแก่ผู้ปฏิบัติงานด้านการหาค่าเหมาะสมที่สุด ซึ่งเปิดเผยข้อมูลมากมายเกี่ยวกับปัญหาที่กำลังแก้ไข ข้อมูลนี้สามารถนำไปใช้ในการออกแบบตัวดำเนินการเพื่อนบ้านเฉพาะปัญหาสำหรับการค้นหาแบบโลคอล เพื่อกำหนดทิศทางการทำงานของ EDA ในอนาคตสำหรับปัญหาที่คล้ายกัน หรือเพื่อสร้างแบบจำลองการคำนวณที่มีประสิทธิภาพของปัญหาได้

ตัวอย่างเช่น หากประชากรถูกแทนด้วยสตริงบิตที่มีความยาว 4 บิต EDA สามารถแทนประชากรของโซลูชันที่มีแนวโน้มดีโดยใช้เวกเตอร์ความน่าจะเป็นสี่ค่า (p1, p2, p3, p4) เพียงเวกเตอร์เดียว โดยแต่ละองค์ประกอบของ p กำหนดความน่าจะเป็นที่ตำแหน่งนั้นจะเป็น 1 การใช้เวกเตอร์ความน่าจะเป็นนี้ทำให้สามารถสร้างโซลูชันที่เป็นไปได้จำนวนมากได้ตามต้องการ

ส่วนนี้อธิบายถึงแบบจำลองที่สร้างขึ้นโดย EDA ที่รู้จักกันดีบางรุ่น ซึ่งมีระดับความซับซ้อนแตกต่างกัน โดยจะถือว่ามีประชากรในแต่ละรุ่นตัวดำเนินการเลือกตัวดำเนินการสร้างแบบจำลองและตัวดำเนินการสุ่มตัวอย่างอยู่ เสมอ${\displaystyle P(t)}$${\displaystyle t}$${\displaystyle S}$${\displaystyle \alpha }$${\displaystyle \beta }$

วิธีการวิเคราะห์ข้อมูลเชิง สำรวจ (EDA) ที่ง่ายที่สุดนั้นสมมติว่าตัวแปรตัดสินใจเป็นอิสระต่อกัน กล่าวคือดังนั้น EDA แบบตัวแปรเดียวจึงอาศัยเพียงสถิติแบบตัวแปรเดียว และการแจกแจงแบบหลายตัวแปรจะต้องถูกแยกตัวประกอบเป็นผลคูณของการแจกแจงความน่าจะเป็นแบบตัวแปรเดียว ${\displaystyle p(X_{1},X_{2})=p(X_{1})\cdot p(X_{2})}$${\displaystyle N}$

${\displaystyle D_{\text{Univariate}}:=p(X_{1},\dots ,X_{N})=\prod _{i=1}^{N}p(X_{i}).}$

การแยกตัวประกอบในลักษณะนี้ถูกนำไปใช้ใน EDA หลายประเภท ต่อไปนี้เราจะอธิบายตัวอย่างบางส่วน

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,}$

โดยที่เป็นพารามิเตอร์ที่กำหนดอัตราการเรียนรู้ค่าที่น้อยจะกำหนดว่าแบบจำลองก่อนหน้าควรได้รับการปรับเปลี่ยนเพียงเล็กน้อยด้วยโซลูชันใหม่ที่สุ่มมา PBIL สามารถอธิบายได้ดังนี้ ${\displaystyle \gamma \in (0,1]}$${\displaystyle p_{t}(X_{i})}$

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

CGA ^{[ 7 ]}ยังอาศัยประชากรโดยปริยายที่กำหนดโดยการแจกแจงแบบเอกตัวแปร ในแต่ละรุ่นจะมีการสุ่มตัวอย่างบุคคลสองคน จากนั้น ประชากรจะถูกจัดเรียงตามลำดับความเหมาะสมที่ลดลงโดยที่เป็นโซลูชันที่ดีที่สุดและเป็นโซลูชันที่แย่ที่สุด CGA ประมาณความน่าจะเป็นแบบเอกตัวแปรดังต่อไปนี้ ${\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}$

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

โดยที่เป็นค่าคงที่ที่กำหนดอัตราการเรียนรู้ซึ่งโดยปกติจะตั้งไว้ที่CGA สามารถกำหนดได้ดังนี้ ${\displaystyle \gamma \in (0,1]}$${\displaystyle \gamma =1/N}$

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

แม้ว่าแบบจำลองตัวแปรเดียวจะคำนวณได้อย่างมีประสิทธิภาพ แต่ในหลายกรณีแบบจำลองเหล่านั้นไม่สามารถแสดงความสัมพันธ์ได้ดีพอที่จะให้ประสิทธิภาพที่ดีกว่าอัลกอริธึมพันธุกรรม (GA) เพื่อเอาชนะข้อเสียดังกล่าว จึงมีการเสนอให้ใช้การแยกตัวประกอบแบบสองตัวแปรในชุมชน EDA ซึ่งสามารถสร้างแบบจำลองความสัมพันธ์ระหว่างตัวแปรเป็นคู่ๆ ได้ การแยกตัวประกอบแบบสองตัวแปรสามารถกำหนดได้ดังนี้ โดยที่ประกอบด้วย ตัวแปรที่อาจขึ้นอยู่กับเช่น${\displaystyle \pi _{i}}$${\displaystyle X_{i}}$${\displaystyle |\pi _{i}|=1}$

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

การแจกแจงแบบสองตัวแปรและหลายตัวแปรมักแสดงด้วยแบบจำลองกราฟิกเชิง ความน่าจะเป็น (กราฟ) โดยที่ขอบแสดงถึงความสัมพันธ์ทางสถิติ (หรือความน่าจะเป็นแบบมีเงื่อนไข) และจุดยอดแสดงถึงตัวแปร การเรียนรู้โครงสร้างของแบบจำลองกราฟิกเชิงความน่าจะเป็นจากข้อมูลนั้นใช้วิธีการเรียนรู้แบบเชื่อมโยง (linkage learning)

MIMIC ^{[ 8 ]}แยกตัวประกอบการแจกแจงความน่าจะเป็นร่วมในแบบจำลองคล้ายลูกโซ่ที่แสดงถึงการพึ่งพาที่ต่อเนื่องกันระหว่างตัวแปรต่างๆ โดยจะค้นหาการเรียงสับเปลี่ยนของตัวแปรการตัดสินใจเช่นนั้น จะลด ความแตกต่างของ Kullback–Leiblerให้น้อยที่สุดเมื่อเทียบกับการแจกแจงความน่าจะเป็นที่แท้จริง นั่นคือMIMIC จำลองการแจกแจง ${\displaystyle r:i\mapsto j}$${\displaystyle x_{r(1)}x_{r(2)},\dots ,x_{r(N)}}$${\displaystyle \pi _{r(i+1)}=\{X_{r(i)}\}}$

${\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 ]}แยกตัวประกอบการแจกแจงความน่าจะเป็นร่วมในการแจกแจงแบบสองตัวแปร ขั้นแรก ตัวแปรที่เลือกแบบสุ่มจะถูกเพิ่มเป็นโหนดในกราฟ ตัวแปรที่ขึ้นอยู่มากที่สุดกับตัวแปรใดตัวหนึ่งในกราฟจะถูกเลือกจากตัวแปรที่ยังไม่ได้อยู่ในกราฟ ขั้นตอนนี้จะถูกทำซ้ำจนกว่าจะไม่มีตัวแปรใดที่ขึ้นอยู่ต่อตัวแปรใด ๆ ในกราฟ (ตรวจสอบตามค่าเกณฑ์)

แบบจำลองที่ได้จะเป็นเหมือนป่าที่มีต้นไม้หลายต้นซึ่งหยั่งรากอยู่ที่โหนดต่างๆเมื่อพิจารณาตัวแปรที่ไม่ใช่ราก BMDA จะประมาณการแจกแจงแบบแฟกทอรี ซึ่งตัวแปรรากสามารถสุ่มตัวอย่างได้อย่างอิสระ ในขณะที่ตัวแปรอื่นๆ ทั้งหมดจะต้องขึ้นอยู่กับตัวแปรแม่ ${\displaystyle \Upsilon _{t}}$${\displaystyle I_{t}}$${\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)).}$

ขั้นตอนต่อไปของการพัฒนา EDA คือการใช้การแยกตัวประกอบแบบหลายตัวแปร ในกรณีนี้ การกระจายความน่าจะเป็นร่วมมักจะถูกแยกตัวประกอบออกเป็นส่วนประกอบจำนวนหนึ่งที่มีขนาดจำกัด ${\displaystyle |\pi _{i}|\leq K,~\forall i\in 1,2,\dots ,N}$

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

การเรียนรู้ PGM ที่เข้ารหัสการแจกแจงแบบหลายตัวแปรเป็นงานที่ต้องใช้การคำนวณสูง ดังนั้น EDA จึงมักประมาณค่าสถิติแบบหลายตัวแปรจากสถิติแบบสองตัวแปร การผ่อนปรนเช่นนี้ทำให้สามารถสร้าง PGM ได้ในเวลาพหุนามแต่ก็จำกัดความทั่วไปของ EDA ดังกล่าวด้วย ${\displaystyle N}$

ECGA ^{[ 10 ]}เป็นหนึ่งใน EDA แรกๆ ที่ใช้การแยกตัวประกอบแบบหลายตัวแปร ซึ่งสามารถจำลองความสัมพันธ์ลำดับสูงระหว่างตัวแปรการตัดสินใจได้ วิธีการนี้จะแยกตัวประกอบการแจกแจงความน่าจะเป็นร่วมในผลคูณของการแจกแจงแบบมาร์จินัลหลายตัวแปร สมมติว่าเป็นเซตของเซตย่อย โดยที่แต่ละเซตย่อยเป็นเซตเชื่อมโยงที่มีตัวแปร การแจกแจงความน่าจะเป็นร่วมที่แยกตัวประกอบแล้วจะแสดงดังต่อไปนี้ ${\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 ทำให้คำว่า "การเรียนรู้การเชื่อมโยง" เป็นที่นิยมในฐานะที่หมายถึงขั้นตอนที่ระบุชุดการเชื่อมโยง ขั้นตอนการเรียนรู้การเชื่อมโยงของ ECGA อาศัยการวัดสองประการ ได้แก่ (1) ความซับซ้อนของแบบจำลอง (MC) และ (2) ความซับซ้อนของประชากรที่ถูกบีบอัด (CPC) MC จะวัดขนาดการแสดงแบบจำลองในแง่ของจำนวนบิตที่จำเป็นในการจัดเก็บความน่าจะเป็นแบบมาร์จินัลทั้งหมด

${\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 อีกต่อไปและสร้างแบบจำลองการเชื่อมโยงECGA ทำงานกับประชากรที่เฉพาะเจาะจง ดังนั้น การใช้การกระจายแบบแฟกทอรีที่จำลองโดย ECGA จึงสามารถอธิบายได้ดังนี้ ${\displaystyle T_{\text{eCGA}}}$

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

BOA ^{[ 11 ] [ 12 ] [ 13 ]}ใช้เครือข่ายเบย์เซียนเพื่อสร้างแบบจำลองและสุ่มตัวอย่างโซลูชันที่น่าสนใจ เครือข่ายเบย์เซียนเป็นกราฟแบบมีทิศทางที่ไม่มีวงจร โดยโหนดแทนตัวแปรและขอบแทนความน่าจะเป็นแบบมีเงื่อนไขระหว่างตัวแปรสองตัว ค่าของตัวแปรสามารถขึ้นอยู่กับค่าสูงสุดของตัวแปรอื่น ๆ ที่กำหนดไว้ในBOA สร้าง PGM ที่เข้ารหัสการแจกแจงร่วมแบบแยกส่วน ซึ่งพารามิเตอร์ของเครือข่าย กล่าวคือ ความน่าจะเป็นแบบมีเงื่อนไข จะถูกประมาณจากประชากรที่เลือกโดยใช้ตัวประมาณค่าความน่าจะเป็นสูงสุด ${\displaystyle x_{i}}$${\displaystyle K}$${\displaystyle \pi _{i}}$

${\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 ส่วนใหญ่ตรงที่ไม่ได้จำลองการกระจายความน่าจะเป็นอย่างชัดเจน แต่จำลองเฉพาะแบบจำลองการเชื่อมโยงที่เรียกว่าต้นไม้เชื่อมโยง การเชื่อมโยงคือชุดของชุดการเชื่อมโยงที่ไม่มีการกระจายความน่าจะเป็นที่เกี่ยวข้อง ดังนั้นจึงไม่มีวิธีที่จะสุ่มตัวอย่างโซลูชันใหม่โดยตรงจากแบบจำลองการเชื่อมโยงคือต้นไม้เชื่อมโยงที่สร้างขึ้นและจัดเก็บเป็นตระกูลของชุด (FOS) ${\displaystyle T}$${\displaystyle T}$

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

กระบวนการเรียนรู้แบบต้นไม้เชื่อมโยง (Linkage-tree learning) เป็น อัลกอริธึมการ จัดกลุ่มแบบลำดับชั้นซึ่งทำงานดังนี้ ในแต่ละขั้นตอน กลุ่ม ที่อยู่ใกล้กันที่สุด สอง กลุ่มจะถูกรวมเข้าด้วยกัน กระบวนการนี้จะทำซ้ำจนกว่าจะเหลือเพียงกลุ่มเดียว โดยแต่ละต้นไม้ย่อยจะถูกจัดเก็บเป็นเซตย่อย ${\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))}$

• กลุ่มความน่าจะเป็น (PC) ^{[ 16 ] [ 17 ]}
• การปีนเขาด้วยการเรียนรู้ (HCwL) ^{[ 18 ]}
• อัลกอริทึมการประมาณค่าปกติแบบหลายตัวแปร (EMNA)
• อัลกอริทึมการประมาณค่าเครือข่ายเบย์เซียน (EBNA)
• การปีนเขาแบบสุ่มด้วยการเรียนรู้โดยเวกเตอร์ของการกระจายปกติ (SHCLVND) ^{[ 19 ]}
• PBIL รหัสจริง
• อัลกอริทึมยีนเห็นแก่ตัว (SG) ^{[ 20 ]}
• วิวัฒนาการเชิงอนุพันธ์แบบกะทัดรัด (cDE) ^{[ 21 ]}และรูปแบบต่างๆ^{[ 22 ] [ 23 ] [ 24 ] [ 25 ] [ 26 ] [ 27 ]}
• การเพิ่มประสิทธิภาพฝูงอนุภาคขนาดกะทัดรัด (cPSO) ^{[ 28 ]}
• การเพิ่มประสิทธิภาพการค้นหาแบคทีเรียแบบกะทัดรัด (cBFO) ^{[ 29 ]}
• วิวัฒนาการโปรแกรมแบบเพิ่มขึ้นตามความน่าจะเป็น (PIPE) ^{[ 30 ]}
• อัลกอริทึมการประมาณค่าเครือข่ายเกาส์เซียน (EGNA)
• อัลกอริทึมการประมาณค่าปกติหลายตัวแปรที่มีการบรรจบกันตามเกณฑ์^{[ 31 ]}
• อัลกอริทึมทางพันธุกรรมเมทริกซ์โครงสร้างการพึ่งพา (DSMGA) ^{[ 32 ] [ 33 ]}

• ซีเอ็มเอ-เอส
• วิธีเอนโทรปีไขว้
• อัลกอริทึมการเพิ่มประสิทธิภาพอาณานิคมมด