公平席位分配问题在遗传选择操作中的应用

Application of fair cumulation method for apportioning seats on genetic selecting operation

选择是遗传算法的三大基本操作之一,适应度比例选择是遗传算法最常用的选择方法。首先比较其与公平席位分配问题的相同点,将其转换为公平席位分配问题;其次,为了克服经典适应度比例选择实现方法、即轮盘赌方法稳定性和可靠性差、随机性高的缺点,提出了改进轮盘赌、比例加惯例法、Q值法、d’Hondt法等,并将这些新方法与传统的轮盘赌方法在公平席位分配原则上进行理论上的比较评价。最后,在立方体、Schaffer、Powell奇异等标准数值测试函数上的实验结果表明,新引入的比例加惯例法和d’Hondt法选择操作比传统的轮盘赌方法稳定性高,有效提高了遗传算法收敛于全局最优解的概率,加快了收敛速度,能够用更低的计算代价获得更佳的优化效果,其中比例加惯例法和d’Hondt法最为突出。

Selection is one of the three operations in genetic algorithm and fitness-proportionate selection is one of the most com- mon used selections. Similarities compared with fair cumulation method for apportioning seats, fitness-proportionate selection ope ration was changed into fair cumulation method for apportioning seats. For shortcomings of classic fitness-proportionate selection method roulette wheel, such as poor stability, low reliability, high randomness, this paper compared some new selection methods including improved roulette wheel, ratio-tradition method, Q-method, d＇ Hondt on principles of fair cumulation method for appor- tioning seats by realizing fitness-proportionate selection method. Finally, the result of comparison of standard numerical functions, such as cube, Sehaffer, Powell singular function indicates that the ratio-tradition method and the d＇ Hondt method improve the probability of convergence to global optimal solution and quicken up the convergence and can find better optimum solutions with less computing cost than roulette wheel. Therefore, the ratio-tradition method and the d＇ Hondt method is the best method of oper- ation of the genetic algorithm, they can overcome the shortcomings of roulette wheel.