Page 39 - 网络电信2024年6月刊
P. 39

当线路网络连通时，s=1，数学模型公式为：                                                               径被选择的概率。这样可以逐步优化选择路径，使蚁群算法更
                                                                                    好地找到较优解。
                       (2)
                                                                                          4. 信息素的更新
      其中，X为n维决策矢量，代表问题的解；n是待铺设线路的                                                         一旦“蚂蚁”K完成了一次旅程，就使用评估函数g(xk）来
数目，xi是矢量X的第i个元素，当第i条路线被选中时xi=1，否                                                    评估旅程，其中xk是“蚂蚁”K旅程所代表的解，并根据评估结
则xi=0;li为第i条线路的建设费用[3]。                                                             果评估每一侧的数量，以改变下一个周期的搜索方向。对m个
                                                                                    “蚂蚁”在m次游程中的最佳模式进行记录，并校正每侧的信息
      2. 优化方法                                                                       素量，以逐步优化搜索过程，校正公式如下：
      蚁群算法主要用来解决组合优化问题，是智能优化算法中
的一种。这种算法模拟了蚂蚁在寻找食物时的行为，并通过信                                                                                                                                        (3)
息素的相互引擎和正反馈机制来实现搜索和优化。
      本文采用蚁群算法来解决通信光缆网络线路优化问题，                                                      当“蚂蚁”k选中路线j时，  ；当“蚂蚁”k
在该算法中，蚂蚁通过一种随机策略完成此路程并形成一棵生
成树。与传统的辐射型检查过程不同，该算法只搜索可行解区                                                         未选中路线j时， 。
域。为了更好理解“蚂蚁”如何形成一棵生成树，引入3个集                                                               式中：r(0<r<1）为信息素量的挥发程度，由于“蚂蚁”以
合：
                                                                                    前留下的信息素会随着时间的流逝逐渐消失，因此用1-r来表示
          表示第k只“蚂蚁”t时刻已访问的节点集合，包含“蚂
蚁”已访问过的节点；                                                                          信息素的消失程度。 为“蚂蚁”k在第n次循环后，边j上
                                                                                    所遗留的信息素量，D表示常数参数。
          表示第k只“蚂蚁”t时刻未访问节点集合，包含了“蚂
蚁”尚未访问的节点；                                                                                Q、C0、D、a、b、r等参数可以通过实验方法确定其最优组
                                                                                    合。当上述过程完成后，代表蚂蚁完成了一次循环过程，对上
          表示t时刻的禁忌节点集合，包含了“蚂蚁”已访问                                                   述过程重复执行，尝试不同的参数组合，并记录评估结果，根
过，不允许再次访问的节点。                                                                       据评估结果，分析不同参数组合对算法性能的影响，并选择最
                                                                                    优的参数组合作为最终的配置。
      在采用的光缆线路模型中，所有站点统称为节点，一条边
表示一对节点间的路径连接。这些边分为两种类型：已存在边                                                              （二）基于遗传算法的通信光缆线路优化规划
和待建边。对于待建边j(其中j=1,2，…，n)具有两个权值，                                                           遗传算法是一种通过模拟生物进化过程中的遗传较差和变
一个权值costj表示线路投资费用，与线路长度成正比，因此可                                                      异等操作来进行问题优化的算法。该算法将问题的搜索空间表
以用站点间路径长度来表示。另一个权值tj，表示边j上的信息                                                       示为一组个体的群体，每个个体都代表一个可能的解，称为染
素数量。在每次游程中，蚂蚁k从t=0时刻开始。蚂蚁k在t时刻                                                      色体，通过不断地进行遗传操作，如选择、交叉和突变，使得
                                                                                    优秀的个体逐代繁衍，最终进化出更好的解。由于遗传算法的
先以概率 随机从集合 中选择边j。然后更新两节点集合，                                                         基本操作类似于生物的遗传和变异，其具有一定的可解释性，
令 式中，节点u是边j的一个端点，且                                                                  能够揭示问题的某些特征和改进方向。
                                                                                          1. 染色体编码
         。对集合 进行更新， = -{j}+ ，并且引入新的                                                       在遗传算法中，染色体编码是指将问题的解表示为一个
可选边，从而形成了集合 。重复以上步骤，确保所有的光缆                                                         染色体的形式，染色体可以看作是一个由基因组成的字符或向
线路节点都连入树[4]。                                                                        量。本文采用二进制编码，将解表示为一串由0和1组成的二进
                                                                                    制数字，每一位代表一个基因，可以使用固定长度的二进制串
      3. 搜索路径的确定                                                                    来表示一个染色体[5]。通过调整基因位的取值来实现对光缆线
      通过概率的形式能够给出每只“蚂蚁”在第i步选定哪条线                                                    路的选择与排列。基因位为1时，表示该条线路被选中，可以纳
路，“蚂蚁”在对搜索方向进行选择时，会考虑已发现的较好                                                         入最终方案；基因位为0时，表示该线路未被选中，将不纳入最
解域，同时也保持一定的探索性以避免陷入局部最优解，从而                                                         终方案。
                                                                                          2. 适应度函数
有效避免了算法过早收敛。“蚂蚁”k在t时刻从集合 中对边                                                              适应度函数用于评估一个个体（染色体）在问题领域中的
的选择取决于转移概率，其公式 表示如下：                                                                优劣程度，它根据个体的染色体编码所对应的解，计算出一个
                                                                                    适应度值，该值越高表示个体越好，即更接近问题的最优解。
                                                                               (3)  染色体sv的适应度函数如下：

                                                                               (4)                                                                                 (6)
      其中，hj表示从集合 中选择边j的期望程度，hjQ/                                                          其中，Z为一个大数，用于确保f(sv）的值为正；λ1和λ2
costj；参数a和b用来调节tj(n)和hj对转移概率的影响程度。                                                  是经济性和可靠性的权重系数，它们的和必须为1，用以调整
tj(n)为第n次循环边j上遗留的信息素的数量。tj(0)=C0中，表                                                 规划方案对经济性或可靠性的偏重程度，给二者设定一个初始
示常数。可以得出结论，该边遗留信息素的数量决定了该边被                                                         值，并通过逐渐调整和仿真试验来确定最佳取值；δ是调节因
选中的概率。通过这种方式，优秀路径上的信息素浓度会逐渐                                                         子，用于平衡经济性和可靠性对f(sv）的影响程度。由于Z、F
增加，从而吸引更多的“蚂蚁”选择该路径，进一步增加该路

                       网络电信 二零二四年六月                                                                59
   34   35   36   37   38   39   40   41   42   43   44