PGA Catagories

งานวิจัยที่เกี่ยวกับ PGA มีหลายตัว ในที่นี้มีเอกสารที่สรุปชนิดของ PGA[1] แบ่งออกเป็นกลุ่มใหญ่ ๆ 3 กลุ่ม คือ

1. Global population master-slave PGA(GPGA) มีกลุ่มประชากรเพียงกลุ่มเดียวซึ่งเก็บไว้ที่ master รวมถึงกระบวนการต่างๆ ของ GA ก็จะทำอยู่ที่ master ด้วย ส่วน slave ทำหน้าที่คำนวณหาค่า fitness ของแต่ละ individual ที่ได้รับมาเท่านั้น
   
2. Single population fine-grained PGA ลักษณะของ PGA แบบนี้จะมีการกระจาย individual ไปยัง processor แบบ 1-1 ซึ่งเหมาะกับ parallel machine ขนาดใหญ่ที่มีจำนวน processor มาก ๆ ข้อจำกัดของ PGA แบบนี้คือกระบวนการ selection และ mating จะจำกัดไว้ที่ processor ที่อยู่ใกล้เคียงเท่านั้น
   
3. Multiple population coarse-grained PGA มีชื่อเรียกหลายแบบเช่น multiple-deme GA หรือ distributed GA หรือ island GA เป็นต้น เป็นการทำ GA ของกลุ่มประชากรย่อยหลายกลุ่ม ( subpopulations ) และมีการแลกเปลี่ยน individual ซึ่งกันและกันในระหว่างกระบวนการ GA โดยการแลกเปลี่ยนนี้เรียกว่า migration

ใน 3 กลุ่มใหญ่ของ PGA ข้างต้น GPGA นั้นจะเป็นกระบวนการที่คล้ายกับ sequetial GA มากที่สุดเนื่องจากไม่ได้ไปเปลี่ยนแปลงพฤติกรรมใดๆของ alogrithm ส่วนอีก 2 แบบต่อมานั้นเปลี่ยนแปลงค่อนข้างมาก เช่นในกระบวนการ selection แบบแรกจะเลือกจากประชากรทั้งหมด ส่วนอีก 2 แบบต่อมาจะเป็นการเลือกจากกลุ่มประชากรย่อยเท่านั้น เช่นเดียวกับกระบวนการ mating

นอกจากนี้ยังมี PGA อีกแบบหนึ่งที่รวมกลุ่มใหญ่ด้านบนเข้าด้วยกัน เรียกว่า hierarchical PGA(HPGA) โดยอาศัย coarse-grained เป็นแกนหลักจับไขว้กับ GPGA และ fine-grained PGA ซึ่งผมจะไม่ขอกล่าวในรายละเอียดตอนนี้ครับ




จากรูป [2]
(a) คือ GPGA
(b) คือ coarse-grained PGA
(c) คือ fine-grained PGA
(d) คือ coarse-grained PGA และ fine-grained PGA
(e) คือ coarse-grained PGAและ GPGA

อ้างอิง
1. E. Cantú-Paz. “A Summary of Research on Parallel Genetic Algorithms” ,revised version, IlliGAL R. 97003. May 1997
2. E. Alba and J. M. Troya, “A survey of parallel distributed genetic algo-
rithms,” Complexity, vol. 4, no. 4, pp. 31–52, 1999