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

Abstract

บทคัดย่อ         บทความนี้นําเสนอความรู้เบื้องต้นและการประยุกต์ใช้ขั้นตอนวิธีเชิงพันธุกรรมแบบกระชับ ซึ่งเป็นขั้นตอนวิธีที่อาศัยหลักการวิวัฒนาการคําตอบคล้ายกับขั้นตอนวิธีเชิงพันธุกรรมที่มีการใช้งานกันอย่างแพร่หลายในปัจจุบัน การนําขั้นตอนวิธีเชิงพันธุกรรมแบบเดิม ไปใช้ในฮาร์ดแวร์ขนาดเล็กเป็นเรื่องยาก เนื่องจากขั้นตอน วิธีเชิงพันธุกรรมต้องอาศัยประชากรจํานวนมากในการหาคําตอบ และต้องการฮาร์ดแวร์ที่มีความสามารถในการประมวลผลค่อนข้างสูง วิธีเชิงพันธุกรรมแบบกระชับที่นําเสนอนี้มีลักษณะเด่นในการใช้หน่วยความจําที่เกือบจะน้อยที่สุดในการเก็บตัวอย่างคําตอบที่ เป็นไปได้ เนื่องจากขั้นตอนวิธีนี้ใช้วิธีการแทนโครงสร้างของประชากรด้วยเวคเตอร์ความน่าจะเป็นที่แจกแจงความน่าจะเป็นของคําตอบงาน วิจัยที่ตีพิมพ์ก่อนหน้านี้ก็มีการพิสูจน์ว่าขั้นตอนวิธีเชิงพันธุกรรมแบบ กระชับมีพฤติกรรมการทํางานที่สามารถเทียบเคียงได้กับพฤติกรรมการทํา งานของขั้นตอนวิธีเชิงพันธุกรรมอย่างง่ายที่ใช้การไขว้เปลี่ยนแบบเอกรูป แต่ใช้หน่วยความจําน้อยกว่า ทั้งสองขั้นตอนวิธีให้คําตอบที่มีคุณภาพใกล้เคียงกันเมื่อใช้จํานวนครั้งที่เท่ากันในการประเมินค่าความเหมาะสม ทําให้ขั้นตอนวิธีนี้มีข้อได้เปรียบและเหมาะต่อการนําไปประยุกต์ใช้ในงานที่มีข้อจํากัดในเรื่องขนาดของหน่วยความจําและความสามารถในการประมวลผล ABSTRACT           This paper presents an introduction and applications of the Compact Genetic Algorithm (cGA), one ofevolutionary 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.