遗传算法和蚁群算法及其在TSP问题和配电网重构问题中的应用研究

摘要

遗传算法是一种以达尔文自然进化论和孟德尔遗传变异理论为基础的基于种群的智能优化算法；蚁群算法则是对群体性昆虫蚂蚁觅食行为进行模拟而提出的一种新的基于种群的智能优化算法,它们可广泛应用于自然科学、工程技术和现代管理等领域中各种复杂问题的优化求解.本文对这两种算法进行了仔细的研究,针对它们收敛速度慢、容易早熟等不足,通过引入新的思想和方法,设计出新的遗传算法和蚁群算法使得这些问题得到改善或解决,并将其成功地应用到了TSP问题和配电网重构问题中.主要工作包括以下内容: 通过对TSP问题适应度地貌的分析,设计出了一种可变邻域搜索的变异算子(简称GIIM),该算子除了具有通常的变异作用外,还有很强的局部搜索功能.在该算子的基础之上,构造出了一种新的求解TSP的高效遗传算法(简称EGA).仿真测试表明,EGA不但具有很强的全局搜索能力,而且收敛速度很快；其测试结果与已知文献中类似算法和国际标准测试库TSPLIB中的最优路径相比,或相同或更优. 通过对TSP问题领域知识的深入研究,将(简称DT)引入到了蚁群系统(简称ACS)中,设计了一种基于DT三角网的候选集策略(简称CSDT),在此基础上结合GIIM,提出了一种新的基于候选集策略和可变邻域搜索变异的求解TSP的蚁群算法(简称DMACS).用典型的TSP标准测试集对该算法进行了验证并与文献中的同类算法进行了对比测试,仿真结果表明该算法优于已知文献中的同类算法. 将GTGA应用于以网损最小为目标的配电网重构问题.结合基于基本环路的染色体编码,设计了适用于配电网重构的基因库和治疗算子,从而将GTGA成功应用到了配电网重构之中. 在IEEE33和IEEE69节点的1000次仿真测试中,GTGA全部找到最优解,且最快收敛代数分别为第2和第3代、平均收敛代数分别为8.089和10.413代.仿真结果说明GTGA在配电网重构问题中的应用是成功的,该算法无论是收敛速度,还是全局寻优能力,以及鲁棒性与最新权威文献中求解配电网重构的其它算法相比,都具有优越的性能. 提出使用MCACS求解配电网重构问题.针对配电网重构问题的特点,结合基于基本回路的解的编码方式,设计了适合于配电网重构的解元件库、保健算子和治病算子,从而将MCACS成功应用到了配电网重构问题中.在IEEEE33和IEEE69节点的100次仿真测试中,MCACS全部找到最优解,且最快收敛代数分别为3和7、平均收敛代数分别为22.16和59.92. 仿真测试表明,MCACS不但优于己知文献中求解配电网重构的蚁群优化算法,而且同其它智能优化算法相比,也显示了具有竞争性的性能.

目录

文摘

英文文摘

独创性声明及学位论文使用授权声明

1绪论

1.1研究背景和意义

1.1.1遗传算法和蚁群算法

1.1.2 TSP问题和配电网重构问题

1.2遗传算法

1.2.1遗传算法概述

1.2.2遗传算法的理论基础

1.2.3遗传算法的研究与改进

1.3蚁群算法

1.3.1蚁群算法概述

1.3.2蚁群算法的基本流程

1.3.3蚁群算法的研究与改进

1.4 TSP问题

1.4.1 TSP问题的定义

1.4.2 TSP问题的标准测试库

1.4.3求解TSP问题的算法

1.5配电网重构问题

1.5.1配电网重构问题概述

1.5.2求解配电网重构问题的算法

1.6研究目的和思路

1.7全文的内容和组织

2一种新的求解TSP问题的高效遗传算法

2.2一种求解TSP的可变邻域搜索的变异算子

2.2.1 TSP问题的适应度地貌分析

2.2.2传统的反转、插入变异算子及特点分析

2.2.3一种求解TSP的可变邻域搜索的变异算子

2.3一种新的求解TSP问题的高效遗传算法及其机理分析

2.3.1编码与适应度函数

2.3.2交叉算子的选择

2.3.3选择算子

2.3.4新算法机理分析

2.4仿真测试

2.4.1与标准遗传算法的对比测试

2.4.2与最新文献关于中国旅行商问题的对比测试

2.4.3与TSPLIB中的实例的对比测试

2.4.4进化曲线分析

2.5结论

3一种新颖的基于基因疗法的遗传算法

3.1引言

3.2一种新颖的基于基因疗法的遗传算法

3.2.1基因疗法概述

3.2.2一种新颖的基于基因疗法的遗传算法

3.3基因库和治疗算子的构造

3.3.1基因库的建立

3.3.2基因库的更新

3.3.3治疗算子的构造

3.3.4算法的机理分析

3.4基因库和治疗算子的构造示例

3.4.1优质基因的提取及插入操作示例

3.4.2劣质基因的获取及清除操作示例

3.5关于TSP问题的仿真测试

3.5.1编码与适应度函数

3.5.2交叉与变异算子

3.5.3治疗算子

3.5.4选择算子

3.5.5仿真实验运行结果

3.6结论

4一种新的基于候选集策略和可变邻域搜索变异的求解TSP的蚁群算法

4.1引言

4.2一种新的基于候选集策略和可变邻域搜索变异的求解TSP问题的蚁群算法

4.2.1基于DT的候选集(CSDT)的构造

4.2.2可变邻域搜索的变异算子

4.3仿真结果及分析

4.3.1与ACS算法的比较

4.3.2与最新文献中的算法的比较

4.3.3进化曲线分析

4.4结论

5一种新颖的基于医疗理论的蚁群算法

5.1引言

5.2一种新颖的基于医疗理论的蚁群算法

5.3解元件库、保健算子和治病算子的构造示例

5.3.1优质解元件库的构造和保健算子

5.3.2劣质解元件的获取及治病算子的构造

5.4仿真测试

5.4.1 MCACS和ACS的比较

5.4.2 MCACS和DMACS的比较

5.5结论

6遗传算法和蚁群算法在配电网重构中的应用

6.1引言

6.2配电网的拓扑结构和配电网重构的数学模型

6.2.1配电网的拓扑结构

6.2.2配电网重构的数学模型

6.3配电网重构的潮流计算

6.3.1拓扑结构存储

6.3.2前推回代法

6.4基于基因疗法的遗传算法在配电网重构中的应用

6.4.1染色体编码、适应度函数、种群初始化、交叉及变异和选择算子

6.4.2基因库的构造及更新

6.4.3治疗算子的设计

6.4.4仿真对比测试

6.4.5结论

6.5基于医疗理论的蚁群算法在配电网重构中的应用

6.5.1解的编码、优质解元件的确定、优质解元件库的建立与更新

6.5.2蚂蚁构造解的过程、状态转换规则、信息素局部更新规则和保健算子

6.5.3劣质解元件的确定、治病算子、信息素全局更新规则

6.5.4仿真对比测试

6.5.5结论

7总结与展望

7.1总结

7.2进一步的设想

致谢

参考文献

附录

在校学习期间发表的论文、专利、获奖等评价情况