การคัดเลือก (Selection ) คือตัวดำเนินการทางพันธุกรรมในอัลกอริธึมวิวัฒนาการ (Evolutionary Algorithm: EA) EA เป็นเมตาฮิวริสติกที่ได้รับแรงบันดาลใจจากวิวัฒนาการทางชีววิทยาและมีเป้าหมายเพื่อแก้ปัญหาที่ท้าทายอย่างน้อยในระดับประมาณการคัดเลือกมีวัตถุประสงค์สองประการ: ประการแรก สามารถเลือกจีโนมแต่ละตัวจากประชากรเพื่อการผสมพันธุ์ในรุ่นต่อไป (เช่น การใช้ตัวดำเนินการครอสโอเวอร์ ) ประการที่สอง กลไกการคัดเลือกยังใช้เพื่อเลือกโซลูชันที่เป็นไปได้ (แต่ละตัว) สำหรับรุ่นต่อไป แบบจำลองทางชีววิทยาคือการคัดเลือกโดยธรรมชาติ

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

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

ขั้นตอนการคัดเลือกเพื่อการผสมพันธุ์ที่ใช้ในช่วงแรก^{[ 1 ]}อาจดำเนินการได้ดังนี้:

1. ค่าความเหมาะสมที่คำนวณได้ ( ฟังก์ชันความเหมาะสม ) จะถูกปรับให้เป็นค่ามาตรฐาน โดยที่ผลรวมของค่าความเหมาะสมที่ได้ทั้งหมดจะเท่ากับ 1
2. ค่าความเหมาะสมที่สะสมและปรับให้เป็นมาตรฐานจะถูกคำนวณ: ค่าความเหมาะสมที่สะสมของแต่ละบุคคลคือผลรวมของค่าความเหมาะสมของตัวบุคคลนั้นเองบวกกับค่าความเหมาะสมของบุคคลก่อนหน้าทั้งหมด ค่าความเหมาะสมที่สะสมของบุคคลสุดท้ายควรเป็น 1 มิฉะนั้นจะเกิดข้อผิดพลาดในขั้นตอนการปรับให้เป็นมาตรฐาน
3. เลือกหมายเลขสุ่มR ระหว่าง 0 ถึง 1
4. บุคคล ที่ได้รับการคัดเลือกคือบุคคลแรกที่มีค่ามาตรฐานสะสมมากกว่าหรือเท่ากับR

สำหรับปัญหาหลายๆ อย่าง อัลกอริทึมข้างต้นอาจใช้ทรัพยากรการคำนวณมาก ทางเลือกที่ง่ายกว่าและเร็วกว่าคือการใช้สิ่งที่เรียกว่าการยอมรับแบบสุ่ม (stochastic acceptance)

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

มีอัลกอริธึมการคัดเลือกอื่นๆ ที่ไม่ได้พิจารณาบุคคลทั้งหมดสำหรับการคัดเลือก แต่จะเลือกเฉพาะบุคคลที่มีค่าความเหมาะสมสูงกว่าค่าคงที่ที่กำหนด (โดยพลการ) เท่านั้น อัลกอริธึมอื่นๆ เลือกจากกลุ่มที่จำกัด โดยอนุญาตให้เลือกได้เพียงเปอร์เซ็นต์ที่กำหนดเท่านั้น โดยพิจารณาจากค่าความเหมาะสม

วิธีการที่ระบุไว้แตกต่างกันหลักๆ ในแรงกดดันการเลือก^{[ 2 ] [ 3 ]}ซึ่งสามารถตั้งค่าได้ด้วยพารามิเตอร์กลยุทธ์ในการเลือกอันดับตามที่อธิบายไว้ด้านล่าง ยิ่งแรงกดดันการเลือกสูงเท่าไร ประชากรก็จะยิ่งลู่เข้าสู่โซลูชันที่แน่นอนได้เร็วขึ้นเท่านั้น และพื้นที่การค้นหาอาจไม่ได้รับการสำรวจอย่างเพียงพอการลู่เข้าก่อนกำหนด นี้ ^{[ 4 ]}สามารถแก้ไขได้โดยการจัดโครงสร้างประชากรให้เหมาะสม^{[ 5 ] [ 6 ]}มีความสัมพันธ์อย่างใกล้ชิดระหว่างแบบจำลองประชากรที่ใช้และแรงกดดันการเลือกที่เหมาะสม^{[ 5 ]}หากแรงกดดันต่ำเกินไป คาดว่าประชากรจะไม่ลู่เข้าแม้หลังจากเวลาการคำนวณที่ยาวนาน สำหรับวิธีการเลือกเพิ่มเติมและรายละเอียดเพิ่มเติม โปรดดูที่^{[ 7 ] [ 8 ]}

ในการเลือกโดยใช้วงล้อรูเล็ตความน่าจะเป็นในการเลือกบุคคลเพื่อผสมพันธุ์ในรุ่นต่อไปนั้นเป็นสัดส่วนกับค่าความเหมาะสมของบุคคลนั้น ยิ่งค่าความเหมาะสมดีเท่าไร โอกาสที่บุคคลนั้นจะถูกเลือกก็ยิ่งสูงขึ้นเท่านั้น การเลือกบุคคลสามารถแสดงได้เหมือนกับการหมุนวงล้อรูเล็ตที่มีช่องเท่ากับจำนวนบุคคลในรุ่นปัจจุบัน โดยขนาดของช่องขึ้นอยู่กับความน่าจะเป็น ความน่าจะเป็นในการเลือกบุคคลเท่ากับโดยที่คือค่าความเหมาะสมของ บุคคล และคือขนาดของรุ่นปัจจุบัน (โปรดทราบว่าในวิธีนี้ บุคคลหนึ่งอาจถูกเลือกได้หลายครั้ง) ${\displaystyle i}$${\displaystyle p_{i}={\frac {f_{i}}{\Sigma _{j=1}^{N}f_{j}}}}$${\displaystyle f_{i}}$${\displaystyle i}$${\displaystyle N}$

การสุ่มตัวอย่างแบบสากลเชิงสุ่ม (Stochastic universal sampling)เป็นการพัฒนาต่อยอดจากการเลือกแบบวงล้อรูเล็ต (roulette wheel selection) โดยมีค่าความคลาดเคลื่อนน้อยที่สุดและไม่มีอคติ

ในการคัดเลือกตามลำดับ ความน่าจะเป็นในการคัดเลือกไม่ได้ขึ้นอยู่กับความเหมาะสมโดยตรง แต่ขึ้นอยู่กับลำดับความเหมาะสมของแต่ละบุคคลภายในประชากร^{[ 9 ]}ไม่จำเป็นต้องทราบค่าความเหมาะสมที่แน่นอน แต่สามารถเรียงลำดับบุคคลตามคุณภาพได้เท่านั้น

นอกจากแรงกดดันในการคัดเลือกที่ปรับได้แล้ว ข้อดีของการคัดเลือกตามลำดับยังเห็นได้จากข้อเท็จจริงที่ว่ามันยังเปิดโอกาสให้บุคคลที่ด้อยกว่าได้สืบพันธุ์และปรับปรุงให้ดีขึ้นอีกด้วย^{[ 10 ]}สิ่งนี้มีประโยชน์อย่างยิ่งในการใช้งานที่มีข้อจำกัด เนื่องจากช่วยอำนวยความสะดวกในการเอาชนะข้อจำกัดในหลายขั้นตอนกลาง กล่าวคือ ผ่านลำดับของบุคคลหลายคนที่ได้รับการจัดอันดับไม่ดีเนื่องจากการละเมิดข้อจำกัด

การจัดอันดับเชิงเส้น ซึ่งย้อนกลับไปถึง Baker ^{[ 11 ] [ 12 ]}มักถูกนำมาใช้^{[ 5 ] [ 10 ] [ 13 ]}วิธีนี้อนุญาตให้กำหนดแรงกดดันในการคัดเลือกโดยใช้พารามิเตอร์ซึ่งสามารถมีค่าได้ระหว่าง 1.0 (ไม่มีแรงกดดันในการคัดเลือก) และ 2.0 (แรงกดดันในการคัดเลือกสูง) ความน่าจะเป็นสำหรับตำแหน่งอันดับจะได้รับดังนี้: ${\displaystyle sp}$${\displaystyle P}$${\displaystyle n}$${\displaystyle R_{i}}$

${\displaystyle P(R_{i})={\frac {1}{n}}{\Bigl (}sp-(2sp-2){\frac {i-1}{n-1}}{\Bigr )}\quad \quad 1\leq i\leq n,\quad 1\leq sp\leq 2\quad {\mathsf {with}}\quad P(R_{i})\geq 0,\quad \sum _{i=1}^{n}P(R_{i})=1}$

นิยามอีกประการหนึ่งสำหรับความน่าจะเป็นของตำแหน่งอันดับคือ: ^{[ 9 ]}${\displaystyle P}$${\displaystyle i}$

${\displaystyle P(i)={\frac {2*(n-i+1)}{n*(n+1)}}}$

การเลือกอันดับเลขชี้กำลังถูกกำหนดดังนี้: ^{[ 9 ]}

${\displaystyle P(i)={\frac {w^{ni}}{\sum _{k=1}^{n}{w^{nk}}}},0\leq w\leq 1}$

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

การคัดเลือกจากทัวร์นาเมนต์เป็นวิธีการเลือกบุคคลจากกลุ่มบุคคลทั้งหมด ผู้ชนะจากแต่ละทัวร์นาเมนต์จะถูกเลือกให้เข้าร่วมการแข่งขันรอบต่อไป

สำหรับการคัดเลือกแบบตัดทอนบุคคลจะถูกจัดเรียงตามความเหมาะสม และส่วนหนึ่ง (10% ถึง 50%) ของบุคคลชั้นนำจะถูกเลือกสำหรับรุ่นถัดไป^{[ 9 ]}

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

ในการเลือกแบบ Boltzmann อุณหภูมิที่เปลี่ยนแปลงอย่างต่อเนื่องจะควบคุมอัตราการเลือกตามตารางเวลาที่กำหนดไว้ล่วงหน้า อุณหภูมิเริ่มต้นสูง ซึ่งหมายความว่าแรงกดดันในการเลือกต่ำ อุณหภูมิจะค่อยๆ ลดลง ซึ่งจะค่อยๆ เพิ่มแรงกดดันในการเลือก ทำให้ GA สามารถจำกัดขอบเขตให้แคบลงไปยังส่วนที่ดีที่สุดของพื้นที่การค้นหาในขณะที่ยังคงรักษาความหลากหลายในระดับที่เหมาะสม^{[ 14 ]}

อัลกอริทึมการคัดเลือกส่วนใหญ่จะเลือกจีโนมแต่ละตัวโดยพิจารณาจากค่าความเหมาะสมแบบสเกลาร์ ซึ่งในหลายกรณีจะได้รับมาจากกรณีฝึกฝนหลายกรณี ในทางตรงกันข้ามการคัดเลือกแบบ Lexicaseจะพิจารณาประสิทธิภาพในแต่ละกรณีฝึกฝนแยกกัน แทนที่จะรวมการวัดประสิทธิภาพจากหลายกรณี โดยจะพิจารณากรณีต่างๆ ในลำดับแบบสุ่มที่แตกต่างกัน และด้วยเหตุนี้จึงมีลำดับความสำคัญที่แตกต่างกันสำหรับแต่ละเหตุการณ์การคัดเลือก^{[ 15 ] [ 16 ] [ 17 ]}

• การคัดเลือกโดยธรรมชาติ
• การคัดเลือกทางเพศ

• บทนำเกี่ยวกับอัลกอริธึมทางพันธุกรรม
• โครงร่างการดำเนินการของเวอร์ชันการยอมรับแบบสุ่ม