การเขียนโปรแกรมทางพันธุกรรมเชิงเส้น

Q: ดูเพิ่มเติม

การเขียนโปรแกรมแบบหลายนิพจน์ การเขียนโปรแกรมทางพันธุกรรมแบบคาร์ทีเซียน วิวัฒนาการทางไวยากรณ์ การโปรแกรมทางพันธุกรรม

Q: หมายเหตุ

^ a b M. Brameier, W. Banzhaf, " การเขียนโปรแกรมเชิงพันธุกรรมเชิงเส้น ", Springer, นิวยอร์ก, 2007 ^ Brameier, M.: "เกี่ยวกับการเขียนโปรแกรมเชิงพันธุกรรมเชิงเส้นเก็บถาวรเมื่อ 2007-06-29 ที่ Wayback Machine ", ดอร์ทมุนด์, 2003 ^ W. Banzhaf, P. Nordin, R.

"การเขียนโปรแกรมเชิงพันธุกรรมเชิงเส้น" ไม่มีความเกี่ยวข้องกับ " การเขียนโปรแกรมเชิงเส้น "

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

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

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

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

ตัวอย่างของโปรแกรม LGP

เนื่องจากโปรแกรม LGP นั้นโดยพื้นฐานแล้วแสดงด้วยลำดับคำสั่งเชิงเส้น จึงอ่านและใช้งานได้ง่ายกว่าโปรแกรมที่ใช้โครงสร้างแบบต้นไม้ ตัวอย่างเช่น โปรแกรมง่ายๆ ที่เขียนขึ้นเพื่อแก้ปัญหาฟังก์ชันบูลีนที่มีอินพุต 3 ตัว (ใน R1, R2, R3) และเอาต์พุต 1 ตัว (ใน R0) สามารถเขียนได้ดังนี้:

R4 = R2 และR3 R0 = R1 หรือR4 R0 = R3 และR0 R4 = R2 และR4 # คำสั่งนี้ไม่มีผลR0 = R0 หรือR2

R1, R2, R3 ต้องถูกประกาศเป็นรีจิสเตอร์อินพุต (อ่านอย่างเดียว) ในขณะที่ R0 และ R4 ถูกประกาศเป็นรีจิสเตอร์คำนวณ (อ่านและเขียนได้) โปรแกรมนี้เรียบง่ายมาก มีเพียง 5 คำสั่ง แต่ตัวดำเนินการกลายพันธุ์และครอสโอเวอร์อาจช่วยเพิ่มความยาวของโปรแกรม รวมถึงเนื้อหาของแต่ละคำสั่งได้

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

โปรแกรมง่ายๆ อีกโปรแกรมหนึ่ง ซึ่งเขียนด้วยภาษา LGP คำสั่ง Slash/Aมีลักษณะเป็นชุดคำสั่งที่คั่นด้วยเครื่องหมายทับ:

input/ # รับข้อมูลจากผู้ใช้และบันทึกไว้ในรีจิสเตอร์ F 0 / # ตั้งค่ารีจิสเตอร์ I = 0 save/ # บันทึกเนื้อหาของ F ลงในเวกเตอร์ข้อมูล D[I] (เช่น D[0] := F) input/ # รับข้อมูลอีกค่าหนึ่งและบันทึกไว้ใน F add/ # เพิ่มข้อมูลปัจจุบันที่ชี้โดย I ลงใน F (เช่น F := F + D[0]) output/. # แสดงผลลัพธ์จาก F

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

ดูเพิ่มเติม

หมายเหตุ

^ ^a ^b M. Brameier, W. Banzhaf, " การเขียนโปรแกรมเชิงพันธุกรรมเชิงเส้น ", Springer, นิวยอร์ก, 2007
^ Brameier, M.: "เกี่ยวกับการเขียนโปรแกรมเชิงพันธุกรรมเชิงเส้นเก็บถาวรเมื่อ 2007-06-29 ที่ Wayback Machine ", ดอร์ทมุนด์, 2003
^ W. Banzhaf, P. Nordin, R. Keller, F. Francone,การเขียนโปรแกรมเชิงพันธุกรรม - บทนำ , Morgan Kaufmann, ไฮเดลเบิร์ก/ซานฟรานซิสโก, 1998
^ Poli, R.; Langdon, WB; McPhee, NF (2008). คู่มือภาคสนามสำหรับการเขียนโปรแกรมเชิงพันธุกรรม Lulu.com สามารถเข้าถึงได้ฟรีทางอินเทอร์เน็ตISBN 978-1-4092-0073-4.
^ M. Brameier, W. Banzhaf,การเปรียบเทียบการเขียนโปรแกรมเชิงพันธุกรรมเชิงเส้นและโครงข่ายประสาทเทียมในการทำเหมืองข้อมูลทางการแพทย์ ", IEEE Transactions on Evolutionary Computation , 5 (2001) 17-26
^ A. Guven,การเขียนโปรแกรมเชิงพันธุกรรมเชิงเส้นสำหรับการสร้างแบบจำลองอนุกรมเวลาของอัตราการไหลรายวัน , J. Earth Systems Science , 118 (2009) 137-146
^ R. Li, BR Noack, L. Cordier, J. Boree, F. Harambat,การลดแรงต้านของแบบจำลองรถยนต์โดยการควบคุมการเขียนโปรแกรมเชิงพันธุกรรมเชิงเส้น ,การทดลองในของไหล , 58 (2017) 103
^ P.-Y. Passagia, A. Quansah, N. Mazellier, GY Cornejo Maceda, A. Kourta,การควบคุมการหยุดนิ่งแบบป้อนกลับแบบเรียลไทม์ของปีกเครื่องบินที่เลขเรย์โนลด์สูงโดยใช้การเขียนโปรแกรมเชิงพันธุกรรมเชิงเส้น ,ฟิสิกส์ของของไหล , 34 (2022) 045108
^พื้นฐานของการเขียนโปรแกรมเชิงพันธุกรรม

ลิงก์ภายนอก

Slash/Aเป็นภาษาโปรแกรมและไลบรารี C++ ที่ออกแบบมาโดยเฉพาะสำหรับ GP เชิงเส้น
DigitalBiology.NETเป็นเครื่องมือค้นหาเฉพาะทางสำหรับแหล่งข้อมูลด้านชีววิทยาทั่วไปและพันธุศาสตร์
ซอฟต์แวร์การเขียนโปรแกรมเชิงพันธุกรรมDiscipulus
ซอฟต์แวร์การเขียนโปรแกรมเชิงพันธุกรรมMicroGP (โอเพนซอร์ส)
[1]โครงการ GP เชิงเส้นแบบโอเพนซอร์สที่ใช้ระบบวิจัยการคำนวณเชิงวิวัฒนาการ (ECJ) ที่ใช้ Java
[2]

[book-1] M. Brameier, W. Banzhaf, " การเขียนโปรแกรมเชิงพันธุกรรมเชิงเส้น ", Springer, นิวยอร์ก, 2007

[Brameier-2] Brameier, M.: "เกี่ยวกับการเขียนโปรแกรมเชิงพันธุกรรมเชิงเส้นเก็บถาวรเมื่อ 2007-06-29 ที่ Wayback Machine ", ดอร์ทมุนด์, 2003

[3] W. Banzhaf, P. Nordin, R. Keller, F. Francone,การเขียนโปรแกรมเชิงพันธุกรรม - บทนำ , Morgan Kaufmann, ไฮเดลเบิร์ก/ซานฟรานซิสโก, 1998

[4] Poli, R.; Langdon, WB; McPhee, NF (2008). คู่มือภาคสนามสำหรับการเขียนโปรแกรมเชิงพันธุกรรม Lulu.com สามารถเข้าถึงได้ฟรีทางอินเทอร์เน็ตISBN 978-1-4092-0073-4.

[5] M. Brameier, W. Banzhaf,การเปรียบเทียบการเขียนโปรแกรมเชิงพันธุกรรมเชิงเส้นและโครงข่ายประสาทเทียมในการทำเหมืองข้อมูลทางการแพทย์ ", IEEE Transactions on Evolutionary Computation , 5 (2001) 17-26

[6] A. Guven,การเขียนโปรแกรมเชิงพันธุกรรมเชิงเส้นสำหรับการสร้างแบบจำลองอนุกรมเวลาของอัตราการไหลรายวัน , J. Earth Systems Science , 118 (2009) 137-146

[7] R. Li, BR Noack, L. Cordier, J. Boree, F. Harambat,การลดแรงต้านของแบบจำลองรถยนต์โดยการควบคุมการเขียนโปรแกรมเชิงพันธุกรรมเชิงเส้น ,การทดลองในของไหล , 58 (2017) 103

[8] P.-Y. Passagia, A. Quansah, N. Mazellier, GY Cornejo Maceda, A. Kourta,การควบคุมการหยุดนิ่งแบบป้อนกลับแบบเรียลไทม์ของปีกเครื่องบินที่เลขเรย์โนลด์สูงโดยใช้การเขียนโปรแกรมเชิงพันธุกรรมเชิงเส้น ,ฟิสิกส์ของของไหล , 34 (2022) 045108

[9] พื้นฐานของการเขียนโปรแกรมเชิงพันธุกรรม

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

การเขียนโปรแกรมทางพันธุกรรมเชิงเส้น

ตัวอย่างของโปรแกรม LGP

ดูเพิ่มเติม

หมายเหตุ

ลิงก์ภายนอก

ข้อมูลสำคัญจากบทความ