The Distance - Based Selection Technique for Crossover in Genetic Algorithm

Abstract

The aim of this research is to study and develop the natural inspired parent selections for the crossover operator in genetic algorithms. There are three distance-based methods of mating selection: the hamming distance-based selection (HS), the cosine coefficient distance-based selection (CS), and the Pearson coefficient distance-based selection (PS). The experiment conducts the comparison of the distance-based selection methods with two traditional selections: the roulette wheel selection (RWS) and the tournament selection (TS). In the experiment, all selection methods are evaluated based on four binary testing problems: one-max, zero-max, random-max, and two trap problems. The measurement criterion is the number of generations when the answer is found and the fitness values when the correct answer is not found. From the experimental results, the suitable approaches are divided into two groups according to the characteristics of the benchmark problems. For the trap problem with many local optima, the distance-based selection methods outperformed the traditional selection. However, for the other benchmark problems, the tournament selection is the better method than others.

งานวิจัยนี้มีจุดมุ่งหมายเพื่อศึกษาและพัฒนาเทคนิคการเลือกตามระยะทางสำหรับการไขว้เปลี่ยนในขั้นตอนเชิงพันธุกรรม ด้วยเทคนิคการคัดเลือก 3 เทคนิค ได้แก่ เทคนิคการเลือกตามด้วยระยะทางแฮมมิ่ง (HS) เทคนิคการเลือกตามด้วยสหสัมพันธ์โคไซน์ (CS) และเทคนิคการเลือกตามด้วยสหสัมพันธ์เพียร์สัน (PS) ซึ่งจะนำไปทดลองเปรียบเทียบกับเทคนิคการเลือกคัดแบบดั้งเดิม 2 เทคนิค ได้แก่ การคัดเลือกแบบวงล้อรูเล็ต (Roulette Wheel Selection) การคัดเลือกแบบการแข่งขัน (Tournament Selection) ในการทำการทดลองครั้งนี้ เทคนิคการคัดเลือกทั้งหมด จะได้รับการประเมินด้วย 4 ปัญหา ได้แก่ ปัญหาบิตหนึ่งมากสุด (One max problem) ปัญหาบิตศูนย์มากสุด (Zero max problem) ปัญหาบิตสูงสุดที่เกิดจากการสุ่ม (Random max problem) และปัญหากับดัก (Trap problem) โดยมีเกณฑ์การวัดผลคือจำนวนรุ่นที่พบคำตอบ และค่าความเหมาะสม เมื่อไม่พบคำตอบที่ถูกต้อง จากการทดลองได้แบ่งแนวทางออกเป็น 2 กลุ่มตามลักษณะของปัญหา สำหรับปัญหากับดักเทคนิคการเลือกตามระยะทาง สามารถช่วยให้หลุดจากจุดเหมาะสมวงแคบ (local optima) ซึ่งสามารถช่วยเพิ่มประสิทธิภาพในการหาคำตอบได้ และสำหรับปัญหาอื่นๆ เทคนิคการคัดเลือกแบบประลองเป็นเทคนิคที่เหมาะสมกว่าเทคนิคอื่นๆ