ขั้นตอนวิธีเชิงพันธุกรรมแบบกระชับและการประยุกต์

Abstract

บทความนี้นำเสนอความรู้เบื้องต้นและการประยุกต์ใช้ขั้นตอนวิธีเชิงพันธุกรรมแบบกระชับ ซึ่งเป็นขั้นตอนวิธีที่อาศัยหลักการ วิวัฒนาการคำตอบคล้ายกับขั้นตอนวิธีเชิงพันธุกรรมที่มีการใช้งานกันอย่างแพร่หลายในปัจจุบัน การนำขั้นตอนวิธีเชิงพันธุกรรมแบบเดิม ไปใช้ในฮาร์ดแวร์ขนาดเล็กเป็นเรื่องยาก เนื่องจากขั้นตอนวิธีเชิงพันธุกรรมต้องอาศัยประชากรจำนวนมากในการหาคำตอบ และต้องการ ฮาร์ดแวร์ที่มีความสามารถในการประมวลผลค่อนข้างสูง วิธีเชิงพันธุกรรมแบบกระชับที่นำเสนอนี้มีลักษณะเด่นในการใช้หน่วยความจำที่เกือบจะน้อยที่สุดในการเก็บตัวอย่างคำตอบที่ เป็นไปได้ เนื่องจากขั้นตอนวิธีนี้ใช้วิธีการแทนโครงสร้างของประชากรด้วยเวคเตอร์ความน่าจะเป็นที่แจกแจงความน่าจะเป็นของคำตอบ งานวิจัยที่ตีพิมพ์ก่อนหน้านี้ก็มีการพิสูจน์ว่าขั้นตอนวิธีเชิงพันธุกรรมแบบกระชับมีพฤติกรรมการทำงานที่สามารถเทียบเคียงได้กับพฤติกรรม การทำงานของขั้นตอนวิธีเชิงพันธุกรรมอย่างง่ายที่ใช้การไขว้เปลี่ยนแบบเอกรูป แต่ใช้หน่วยความจำน้อยกว่า ทั้งสองขั้นตอนวิธีให้คำตอบ ที่มีคุณภาพใกล้เคียงกันเมื่อใช้จำนวนครั้งที่เท่ากันในการประเมินค่าความเหมาะสม ทำให้ขั้นตอนวิธีนี้มีข้อได้เปรียบและเหมาะต่อการ นำไปประยุกต์ใช้ในงานที่มีข้อจำกัดในเรื่องขนาดของหน่วยความจำและความสามารถในการประมวลผล This paper presents an introduction and applications of the Compact Genetic Algorithm (cGA), one of evolutionary algorithms similar to genetic algorithms widely used to solve current real-world problems. Executing traditional genetic algorithms on a small-sized hardware is ineffective due to large number of population and high processing power requirement. The cGA has a distinct characteristic that it requires almost minimal memory to store candidate solutions. It represents a population structure as a probability distribution over the set of solutions. There are proofs in the literature that the cGA mimics the behavior of Simple Genetic Algorithm (sGA) with uniform crossover using a small amount of memory, and achieves comparable quality with approximately the same number of fitness evaluations. Thus, these advantages contribute to a flexible implementation for the problems that have limitations on memory usage and computational resources.