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

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

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

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

ในแบบจำลองเกาะ หรือที่เรียกว่าแบบจำลองการย้ายถิ่นฐานหรือแบบจำลองหยาบวิวัฒนาการเกิดขึ้นในประชากรย่อยที่แบ่งแยกอย่างเคร่งครัด ประชากรเหล่านี้อาจจัดระเบียบแบบผสมพันธุ์แบบสุ่ม แต่ไม่จำเป็นต้องเป็นเช่นนั้น บางครั้งจะมีการแลกเปลี่ยนบุคคลเกิดขึ้น ซึ่งเรียกว่าการย้ายถิ่นฐาน [ ^{2 ] [ 5 ] ช่วง}เวลาระหว่างการแลกเปลี่ยนเรียกว่ายุคและจุดสิ้นสุดของยุคสามารถถูกกระตุ้นได้ด้วยเกณฑ์ต่างๆ เช่น หลังจากเวลาที่กำหนดหรือจำนวนรุ่นที่เสร็จสมบูรณ์ที่กำหนด หรือหลังจากเกิดภาวะชะงักงัน ภาวะชะงักงันสามารถตรวจพบได้ เช่น จากข้อเท็จจริงที่ว่าไม่มีการปรับปรุงความเหมาะสมเกิดขึ้นในเกาะเป็นเวลาจำนวนรุ่นที่กำหนด แบบจำลองเกาะนำเสนอพารามิเตอร์กลยุทธ์ใหม่ๆ ที่หลากหลาย: ^{[ 11 ] [ 12 ] [ 13 ] [ 14 ]}

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

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

แบบจำลองเพื่อนบ้าน หรือที่เรียกว่าแบบจำลองการแพร่กระจายหรือแบบจำลองละเอียดกำหนดความสัมพันธ์เพื่อนบ้านเชิงโทโพโลยีระหว่างบุคคลในประชากรที่ไม่ขึ้นอยู่กับคุณสมบัติทางฟีโนไทป์แนวคิดพื้นฐานของแบบจำลองนี้คือการให้โครงสร้างพิเศษแก่ประชากร EA ซึ่งกำหนดเป็นกราฟที่เชื่อมต่อกัน โดยที่แต่ละจุดยอดเป็นบุคคลที่สื่อสารกับเพื่อนบ้านที่ใกล้ที่สุด^{[ 2 ] [ 6 ]}โดยเฉพาะอย่างยิ่ง บุคคลจะถูกจัดวางในเชิงแนวคิดในตาข่ายรูปวงแหวน และอนุญาตให้ผสมพันธุ์กับบุคคลที่อยู่ใกล้เคียงเท่านั้น ซึ่งนำไปสู่ความเป็นท้องถิ่นชนิดหนึ่งที่เรียกว่าการแยกตัวตามระยะทาง [ ^{6 ] [ 7 ] ชุด}ของคู่ผสมพันธุ์ที่เป็นไปได้ของบุคคลเรียกว่าเพื่อนบ้านหรือเดมรูปที่อยู่ติดกันแสดงให้เห็นโดยการแสดงเพื่อนบ้านที่ทับซ้อนกันเล็กน้อยของบุคคลสองคนซึ่งทำเครื่องหมายสีเหลือง ซึ่งข้อมูลทางพันธุกรรมสามารถแพร่กระจายระหว่างสองเดมได้ เป็นที่ทราบกันว่าในอัลกอริทึมประเภทนี้ บุคคลที่คล้ายคลึงกันมักจะรวมกลุ่มกันและสร้างนิชที่ไม่ขึ้นอยู่กับขอบเขตของเดม และโดยเฉพาะอย่างยิ่ง อาจมีขนาดใหญ่กว่าเดม^{[ 6 ] [ 7 ]}ไม่มีเส้นแบ่งที่ชัดเจนระหว่างกลุ่มที่อยู่ติดกัน และกลุ่มใกล้เคียงอาจถูกกลุ่มคู่แข่งเข้ายึดครองได้ง่าย และอาจรวมเนื้อหาของโซลูชันเข้าด้วยกันในระหว่างกระบวนการนี้ ในขณะเดียวกัน กลุ่มที่อยู่ไกลออกไปอาจได้รับผลกระทบช้าลง^{[ 6 ] [ 7 ]} EA ที่มีประชากรประเภทนี้เป็นที่รู้จักกันดีในชื่อEA แบบเซลล์ (cEA) ^{[ 8 ] [ 15 ]}หรืออัลกอริทึมทางพันธุกรรมแบบเซลล์ (cGA) ^{[ 7 ] [ 16 ]}

โครงสร้างที่ใช้กันทั่วไปสำหรับการจัดเรียงประชากรแต่ละตัวคือตารางทอรอยด์ 2 มิติ^{[ 17 ] [ 1 ] [ 2 ] [ 15 ]}แม้ว่าจำนวนมิติจะสามารถขยายได้ง่าย (เป็น 3 มิติ) หรือลดลง (เป็น 1 มิติ เช่น วงแหวน^{[ 6 ] [ 15 ]}ดูรูปทางด้านขวา) บริเวณใกล้เคียงของแต่ละตัวในตารางจะถูกกำหนดในแง่ของระยะทางแมนฮัตตันจากตัวนั้นไปยังตัวอื่นๆ ในประชากร ในอัลกอริทึมพื้นฐาน บริเวณใกล้เคียงทั้งหมดมีขนาดเท่ากันและมีรูปร่างเหมือนกัน บริเวณใกล้เคียงที่ใช้กันทั่วไปสองแบบสำหรับ cEA สองมิติคือ L5 และ C9 ดูรูปทางด้านซ้าย ในที่นี้Lหมายถึงเชิงเส้นในขณะที่Cหมายถึงกะทัดรัดแต่ละเดมแสดงถึงประชากรย่อยแบบแพนมิคติก ซึ่งการเลือกคู่ครองและการยอมรับลูกหลานเกิดขึ้นโดยการแทนที่พ่อแม่ กฎสำหรับการยอมรับลูกหลานมีลักษณะเฉพาะในระดับท้องถิ่นและขึ้นอยู่กับพื้นที่ใกล้เคียง ตัวอย่างเช่น อาจระบุได้ว่าลูกหลานที่ดีที่สุดจะต้องดีกว่าพ่อแม่ที่ถูกแทนที่ หรือหากไม่เคร่งครัดมากนัก ก็คือดีกว่าบุคคลที่แย่ที่สุดในกลุ่มประชากรเท่านั้น^{[ 2 ] [ 6 ]}กฎข้อแรกเป็นแบบชนชั้นสูงและสร้างแรงกดดันในการคัดเลือก ที่สูง กว่ากฎข้อที่สองที่ไม่ใช่แบบชนชั้นสูง ในEA แบบชนชั้นสูงบุคคลที่ดีที่สุดของประชากรจะรอดชีวิตเสมอ ในแง่นี้ พวกมันจึงเบี่ยงเบนจากแบบจำลองทางชีววิทยา

การทับซ้อนกันของย่านใกล้เคียงทำให้การแพร่กระจายของข้อมูลทางพันธุกรรมข้ามขอบเขตของย่านใกล้เคียงเป็นไปอย่างช้าๆ ดังนั้นจึงเรียกว่าแบบจำลองการแพร่กระจาย (diffusion model ) ลูกหลานที่ดีกว่าในปัจจุบันต้องการจำนวนรุ่นมากกว่าใน panmixy เพื่อแพร่กระจายในประชากร ซึ่งส่งเสริมการเกิดขึ้นของแหล่งเฉพาะถิ่นและการวิวัฒนาการในท้องถิ่น จึงรักษาความหลากหลายทางพันธุกรรมไว้ได้นานขึ้น^{[ 6 ] [ 17 ] [ 18 ]}ผลลัพธ์ที่ได้คือความสมดุลที่ดีขึ้นและมีพลวัตระหว่างการค้นหาแบบกว้างและ แบบลึก ที่ปรับให้เข้ากับพื้นที่การค้นหาในระหว่างการทำงาน^{[ 4 ]}การค้นหาแบบลึกเกิดขึ้นในแหล่งเฉพาะถิ่น และการค้นหาแบบกว้างเกิดขึ้นในขอบเขตของแหล่งเฉพาะถิ่นและผ่านวิวัฒนาการของแหล่งเฉพาะถิ่นต่างๆ ของประชากรทั้งหมด^{[ 19 ]}สำหรับขนาดย่านใกล้เคียงที่เท่ากัน การแพร่กระจายของข้อมูลทางพันธุกรรมจะมากกว่าสำหรับรูปทรงยาว เช่น L9 มากกว่าสำหรับบล็อก เช่น C9 และมากกว่าอย่างมีนัยสำคัญสำหรับวงแหวน^{[ 20 ]}ซึ่งหมายความว่าย่านใกล้เคียงแบบวงแหวนเหมาะสมอย่างยิ่งสำหรับการบรรลุผลลัพธ์ที่มีคุณภาพสูง แม้ว่าจะต้องใช้เวลาในการทำงานค่อนข้างนานก็ตาม ในทางกลับกัน หากเป้าหมายหลักคือความเร็วและผลลัพธ์ที่ดี แต่ผลลัพธ์อาจไม่สมบูรณ์แบบ โครงสร้างแบบ 2 มิติจะเหมาะสมกว่า

เมื่อนำแบบจำลองประชากรทั้งสองมาใช้กับอัลกอริทึมทางพันธุกรรม^{[ 5 ] [ 6 ]}กลยุทธ์วิวัฒนาการ^{[ 20 ] [ 17 ] [ 21 ]}และ EA อื่นๆ^{[ 22 ] [ 23 ]}การแบ่งประชากรทั้งหมดออกเป็นประชากรย่อยมักจะลดความเสี่ยงของการบรรจบกันก่อนกำหนดและนำไปสู่ผลลัพธ์ที่ดีขึ้นโดยรวมอย่างน่าเชื่อถือและรวดเร็วกว่าที่คาดหวังได้จาก EA แบบ panmictic ^{[ 2 ] [ 6 ]}

แบบจำลองเกาะมีข้อเสียเปรียบเมื่อเทียบกับแบบจำลองพื้นที่ใกล้เคียงตรงที่แบบจำลองเกาะมีการเพิ่มพารามิเตอร์กลยุทธ์ใหม่จำนวนมาก แม้ว่าจะมีงานวิจัยเกี่ยวกับหัวข้อนี้ในเอกสารอยู่แล้ว^{[ 11 ] [ 24 ] [ 25 ]}แต่ก็ยังคงมีความเสี่ยงที่จะเกิดการตั้งค่าที่ไม่เหมาะสมสำหรับผู้ใช้ ในทางกลับกัน แบบจำลองพื้นที่ใกล้เคียงนั้น ผู้ใช้จะต้องระบุเพียงขนาดของพื้นที่ใกล้เคียงเท่านั้น และในกรณีของแบบจำลองสองมิติ จะมีการเพิ่มตัวเลือกรูปร่างของพื้นที่ใกล้เคียงเข้าไปด้วย^{[ 26 ] [ 20 ] [ 27 ] [ 28 ]}

เนื่องจากแบบจำลองประชากรทั้งสองแบบบ่งชี้ถึงการแบ่งส่วนประชากร จึงเหมาะอย่างยิ่งที่จะใช้เป็นพื้นฐานสำหรับการประมวลผลแบบขนานของ EA ^{[ 5 ] [ 10 ] [ 29 ]}ยิ่งไปกว่านั้นยังใช้ได้กับ EA แบบเซลลูลาร์ เนื่องจากอาศัยเพียงข้อมูลที่มีอยู่เฉพาะที่เกี่ยวกับสมาชิกในกลุ่มประชากรของตนเท่านั้น ดังนั้น ในกรณีสุดขั้ว สามารถกำหนดเธรดการทำงานอิสระให้กับแต่ละบุคคลได้ เพื่อให้ cEA ทั้งหมดสามารถทำงานบนแพลตฟอร์มฮาร์ดแวร์แบบขนานได้^{[ 6 ] [ 30 ] [ 31 ] [ 32 ]}แบบจำลองเกาะยังสนับสนุนการประมวลผลแบบขนาน เช่น โดยการกำหนดโปรเซสเซอร์ให้กับแต่ละเกาะ หากประชากรย่อยของเกาะมีการจัดระเบียบแบบ panmictically การประเมินทั้งหมดของลูกหลานในแต่ละรุ่นสามารถประมวลผลแบบขนานได้เพิ่มเติม^{[ 9 ] [ 14 ] [ 33 ]}ในการใช้งานจริง การประเมินมักจะเป็นส่วนที่ใช้เวลานานที่สุด แน่นอนว่ายังสามารถออกแบบประชากรย่อยของเกาะเป็น cEA ได้เช่นกัน เพื่อให้ข้อความที่กล่าวมาก่อนหน้านี้เกี่ยวกับการประมวลผลแบบขนานของ cEA มีผลบังคับใช้ ด้วยวิธีนี้ โครงสร้างประชากรแบบลำดับชั้นที่มีการประมวลผลแบบขนานที่เหมาะสมจึงสามารถสร้างขึ้นได้^{[ 9 ]}ไม่เพียงแต่คลัสเตอร์คอมพิวเตอร์ที่มีราคาค่อนข้างสูงเท่านั้น แต่ยังสามารถใช้ การ์ดกราฟิกราคาไม่แพง ( GPU ) ^{[ 34 ] [ 35 ]}หรือคอมพิวเตอร์ของกริด^{[ 18 ] สำหรับการประมวลผลแบบขนานได้อีกด้วย}

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

• Erick Cantú-Paz (2001): อัลกอริทึมพันธุกรรมแบบขนานที่มีประสิทธิภาพและแม่นยำ (วิทยานิพนธ์ปริญญาเอก มหาวิทยาลัยอิลลินอยส์ เออร์บานา-แชมเปญ สหรัฐอเมริกา) สปริงเกอร์ นิวยอร์ก สหรัฐอเมริกาISBN 978-1-4613-6964-6doi : 10.1007/978-1-4615-4369-5
• Martina Gorges-Schleuter (1990): อัลกอริทึมทางพันธุกรรมและโครงสร้างประชากร - อัลกอริทึมแบบขนานจำนวนมากวิทยานิพนธ์ระดับปริญญาเอก Universität Dortmund, Fakultät für Informatik ประเทศเยอรมนี
• Enrique Alba, Bernabé Dorronsoro (2008): อัลกอริทึมทางพันธุกรรมของเซลล์ . สปริงเกอร์, นิวยอร์ก, นิวยอร์กไอเอสบีเอ็น 978-0-387-77609-5doi : 10.1007/978-0-387-77610-1
• Dirk Sudholt (2015): อัลกอริทึมวิวัฒนาการแบบขนานใน Janusz Kacprzyk, Witold Pedrycz (บรรณาธิการ): อัลกอริทึมวิวัฒนาการแบบขนาน Springer, Berlin, Heidelberg, หน้า 929–959 ISBN 978-3-662-43504-5doi : 10.1007/978-3-662-43505-2_46
• Gabriel Luque, Enrique Alba (2011): อัลกอริทึมทางพันธุกรรมแบบขนาน . สปริงเกอร์, เบอร์ลิน ไฮเดลเบิร์ก. ไอเอสบีเอ็น 978-3-642-22083-8doi : 10.1007/978-3-642-22084-5

• ออโตมาตาเซลลูลาร์
• วิวัฒนาการสองเฟส
• อัลกอริทึมวิวัฒนาการ
• เมตาฮิวริสติก