求解TSP的交配算子设计策略

旅行商问题(TSP)是一类典型的NP完全问题,遗传算法(GA)是求解这类问题的常用方法之一。由于该问题的解是一种特殊的序列,一些典型的GA交配方法在求解该问题时的性能并不理想。通过多次对比两种常用的GA交配方法与3种专门为TSP作优化的交配方法,总结了一种对旅行商问题的交配算子的设计策略,即注重对双亲的边继承以及加入适当的贪心控制策略。通过对Gr17、Oliver30、Eil51、Eil76和Krob100等测试数据进行实验,证明了在该策略的指导下改进的两种交配算子具有更好的表现。

一种改进的遗传算法求解TSP问题

提出一种基于顶点的候选表进行交配的遗传算法(Candidate Crossover Genetic Algorithm,CCGA)求解旅行商问题(TSP)。遗传算法(GAs)是一种广泛使用的全局优化算法,并且已经成功地用于求解TSP。但是传统的遗传算法的交配算子缺乏指导性和启发性,交配算子随机的选择父体基因进行交配,导致GAs求解速度慢、解的精度不高等不足。通过分析TSP问题本身的特征,给出了一个使用已有的邻接边的信息和路径信息生成顶点的候选表,然后基于顶点的候选表进行交配的交配算子,使用该交配算子的遗传算法在求解TSP问题时性能上得到了很大的提高,通过TSP Lib上的测试样例将该CCGA和传统的遗传算法进行比较。比较结果表明CCGA具有更大的优势,它能使算法求解到近似最优解和最优解只存在很小的偏差。

基于家族优生学进化算法的电力系统动态无功优化

针对大规模电网无功优化收敛速度慢的问题,提出了基于家族优生学的无功优化算法,该方法将正交设计技术引入家庭子代培植过程中,以加强个体行为改善,避免早熟,加快了进化后期的收敛速度。采用改进的动态无功优化数学模型和相适应的编码方法,并根据控制变量的可调档位数动态分配码串长度,由控制变量确定基因组,以基因组中控制变量的可调档位数为约束条件,修正不可行解,提高了计算效率。算例表明将家族优生学进化算法应用于无功优化,取得了良好的效果。