Front-rear crossover: A new crossover technique for solving a trap problem

Abstract

Crossover methods are important keys to the success of genetic algorithms. However, traditional crossover methods fail to solve a trap problem, which is a difficult benchmark problem designed to deceive genetic algorithms to favor all-zero bits, while the actual solution is all-one bits. The Bayesian optimization algorithm (BOA) is the most famous algorithm that can solve the trap problem; however, it incurs a large computational cost. This paper, therefore, proposes a novel crossover technique, called a front-rear crossover (FRC), to enhance the simple genetic algorithm. We test the proposed technique with various benchmark problems and compare the results with four other crossover algorithms, including single point crossover (SPC), two point crossover (TPC), uniform crossover (UC) and ring crossover (RC). The FRC outperforms the four techniques in all test problems. It can also solve the trap problem by requiring the 40 times lesser number of fitness evaluations than BOA’s.

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