遗传算法与蚂蚁算法的融合（Genetic AlgorithmAnt Algorithm 简称GAAA）,其基本思想是汲取两种算法的优点 ，克服各自的缺陷 ， 优势互补 。
在时间效率上优于蚂蚁算法 ，在求精解效率上优于遗传算法 ， 是时间效率和求解效率都比 较好的一种新的启发式方法 。
其基本思路是算法前过程采用 遗传算法 ， 充分利用遗传算法的快速性、随机性、全局收敛 性 ， 其结果是产生有关问题的初始信息素分布 。
算法后过程 采 。

24、用蚂蚁算法 ， 在有一定初始信息素分布的情况下 ， 充分利 用蚂蚁算法并行性、正反馈性、求精解效率高等特点 。
图3-2 GAAA算法总体框架 定义目标函数定义目标函数 生成若干组优化解生成若干组优化解 定义适应值函数定义适应值函数 转化为初始信息素分布转化为初始信息素分布 问题问题 遗传遗传 算法算法 蚂蚁蚂蚁 算法算法 最好最好 解解 图3-3 GAAA算法详细流图 lGAAA中的遗传算法中的遗传算法是基于优胜选择遗传算法的原理与定义 。
l编码与适应值函数：编码与适应值函数：如TSP问题 ， 以城市的遍历次序作为遗传 算法的编码 ， 适应度函数取为哈密顿圈的长度的倒数 。
l种群生成与染色体选择：种群生成与染 。

25、色体选择：利用随机函数生成一定数量的十进 制实数编码种群 ， 根据适应值函数选择准备进行交配的一对 染色体父串 。
l交叉算子：交叉算子：采用Davis提出的顺序交叉方法 。
l变异算子变异算子：采用逆转变异方法 。
l交叉算子：交叉算子：采用Davis提出的顺序交叉方法 ， 先进行常规的双点交叉 ，在进行维持原有相对访问顺序的巡回路线修改 。
具体交叉如下： l（1）随机在父串上选择一个交配区域 ， 如两父串选定为： lold1= 1 2 | 3 4 5 6 | 7 8 9, old2= 9 8 | 7 6 5 4 | 3 2 1 l（2）将old2的交配区域加到old1前面 ， 将old1的交配区域加到old2 的 。

26、前面： l old1= 7 6 5 4 | 1 2 3 4 5 6 7 8 9, old2= 3 4 5 6 | 9 8 7 6 5 4 3 2 1 l（3）依次删除old1 ， old2中与交配区相同的数码 ， 得到最终的两 子串： l new1= 7 6 5 4 1 2 3 8 9, new2= 3 4 5 6 9 8 7 2 1 l l变异算子变异算子：采用逆转变异方法 ， 所谓“逆转” ， 如染色体 (12 3456) 在区间23和区间56处发生断裂 ， 断裂片段又以反 向顺序插入 ， 于是逆转后的染色体变为(125436) 。
这里 的“进化” ， 是指逆转算子的单方向性 ， 只有经逆转后 ， 适应值有 提高的才接受下来 ，。

27、否则逆转无效 。
lGAAA中蚂蚁算法选择基于蚂蚁圈模型（Ant-Cycle）和 MMAS(MAX-MIN Ant System)算法 ， 在吸取其各自优点的 基础上并进行改进 ， 具体来说： l信息素更新方程： l选择概率： l每一蚂蚁圈信息素增加： l各路径设置信息素初值 。
)()() 1(ttt k ijijij other Nj t t tp k i Nl ilil ijij k ij k i 0 )( )( )( k k ij L Q l两种算法对接的关键是如何把遗传算法的结果转化为蚂蚁算 法的信息素 。
l信息素的初值设置：信息素的初值设置：MMAS是把各路径信息素初值设为最大 值max ， 这里 。

28、我们通过遗传算法得到了一定的路径信息素 ， 所 以把信息素的初值设置为: S = C+G 这里 ， C是一个根据具体求解问题规模给定的一个信息素常 数 ， 相当于MMAS算法中的min ， G是遗传算法求解结果转换 的信息素值 。
l信息素更新模型：信息素更新模型：采用蚂蚁圈模型进行信息素更新 ， 即一圈 中只有最短路径的蚂蚁才进行信息素修改增加 。
l我们采用GAAA算法分别对典型的NP-hard问题30城市 TSP问题和中国CHN144城市问题进行了实验, GAAA中 遗传算法迭代次数分别选定为30代和144代 ， 蚂蚁算法 中各路径信息素初值C分别设为60和600, 遗传算法求 解结果转换的信息素值是经过路径加2和 。

29、20,轨迹更新分 别取=0.8 ， Q=1000和=0.9 ， Q=100000 。
表3-1、表3- 2、表3-3、表3-4、图3-4、图3-5、图3-6、图3-7、图3- 8、图3-9、图3-10、图3-11、图3-12、图3-13是仿真实 验结果 。
表表3-1 GAAA算法优化解数据逼近过程算法优化解数据逼近过程 GAAA过程 TSP30优化解值CHN144优化解值 最大值 最小值 平均值最大值 最小值 平均值 初始随机生成优化解值 1500 1209 1318.888763 65739 76316 选择算子作用优化解值 1198 1101 1139.165564 61278 63211 杂交算子作 。

30、用优化解值 1095 1005 1050.356405 54329 55323 变异算子作用优化解值 987 817 912.351994 51344 51508 蚂蚁算法作用优化解值 452 424 433.731153 30351 30612 表表3-2 GAAA算法随机求解的算法随机求解的30个个 优化解值分布优化解值分布 )1000, 8 . 0, 2, 1(Q)100000, 9 . 0, 2, 2(Q TSP30优化解值分布CHN144优化解值分布 436 430 431 439 426 437 433 429 434 439 426 438 424 426 425 446 449 。

稿源：(未知)

【傻大方】网址：/a/2021/0819/0023818768.html

标题：蚂蚁|蚂蚁算法2010( 四 )