概念性 AI 神经网络 - 使用蚁群优化进行数据网络负载均衡

• 下载源代码 - 791.6 KB

引言

蚂蚁最早出现在大约1.2亿年前，演化出超过11,400个不同的物种，并因其高度有组织的群体（有时由数百万只蚂蚁组成）而被认为是其中最成功的昆虫之一。

蚂蚁的一个特别显著的特点是它们能够创造“蚂蚁街道”。长而双向的单行通道，它们通过这些通道在环境中导航，以最优时间到达目的地。这些不断变化的网络是通过使用信息素来实现的，信息素通过最短路径机制指引它们。这种技术允许一个自适应路由系统，如果找到更优的路径或现有路径上出现障碍物，该系统就会得到更新。

计算机科学家在20世纪90年代初开始研究蚂蚁的行为，以发现新的路由算法。这些研究的结果是蚁群优化（ACO），并且在实现良好的ACO技术的情况下，其性能与现有的顶尖路由算法相当。

本文详细介绍了ACO如何用于动态高效地路由流量。一种有效的路由算法将最小化完成呼叫所需的连接节点数量，从而最小化网络负载并提高可靠性。基于Marco Dorigo和Thomas Stützle设计的ANTNet实现，通过它进行了一系列带可视化辅助的测试，以比较遗传算法与非遗传算法。报告最后将总结算法的性能以及如何进一步优化它。

背景

电子通信网络可分为电路交换或分组交换。电路交换网络依赖于从源到目标的专用连接，该连接在启动时建立一次，并在连接拆除前保持不变。英国电信电话网络就是一个电路交换网络的例子。然而，分组交换网络的工作方式完全不同，所有要传输的数据被分成段并以数据包的形式发送。在分组交换网络中，数据包可能会乱序到达，通过不同的节点采取各种路径到达目的地。互联网和办公室局域网都是分组交换网络的良好示例。

可以使用多种技术来优化网络中的流量。这些技术包括流量和拥塞控制，其中节点从目标节点发送数据包确认，以增加或减少数据包传输速度。本报告关注的领域集中在网络路由和路由表的概念。这些表包含路由算法用于为数据包在下一个将访问的节点上做出局部转发决策的信息，以便到达最终目的地。

网络路由的一个问题（尤其是在互联网这样的大型网络中）是适应性。交通流量可能不可预测地高，而且网络的结构可能会随着旧节点的移除和新节点的添加而改变。这或许使得寻找一组恒定的参数来最优地路由网络几乎不可能。

路由算法

分组交换网络通过存储在链路状态中的路由表动态地引导数据包到其目的地，并通过链路状态算法进行选择。

链路状态算法通过为网络中的每个节点提供网络的连通性图来工作。该图显示了哪些节点是直接连接的。连接节点的值存储在一个图中，该图表示到其他节点的最短路径。一种用于网络路由的链路状态算法是Dijkstra算法。当找到两个节点之间的路径时，其权重将在表中更新。如果找到更短的路径，新的最优权重将被更新到表中，替换旧值。

该算法允许流量在网络中路由，同时连接到尽可能少的节点。该系统有效，但不考虑流量涌入和负载均衡。

介绍ANTNet

通过用通用算法替换Dijkstra算法，呼叫所走的路径可以根据其路径的长度进行评分；这样，如果它们在繁忙的网络中排队，它们的表现就会很差。因此，其他路径将获得相对分数并被选择。这将实时工作，并允许路由系统在传输数据包时进行调整。ANTNet使用虚拟信息素表，就像蚂蚁沿着一条路径行走，留下信息素来加强它一样。蚂蚁在一条路径上移动得越快，蚂蚁的吞吐量就越大，信息素浓度也就越高。同样，ANTNet中的信息素表允许快速路径有更高的被选中的几率，而不太优的路径则有较低的被选中的几率。

ANTNet的理念是，当放置一个呼叫时，一只蚂蚁将使用一种链路状态确定性算法穿越网络。每个节点都为网络中的所有其他节点维护一个信息素表。每个信息素表包含一个表条目列表，其中包含当前节点的所有连接节点。

算法

起初，每个可能的路径都有相同的被选择的可能性。一只蚂蚁被放置在一个由4个节点组成的网络上，源节点是1，目标节点是2。启动一个随机机制并选择一条路径。

图3.1 - 网络图

下一个节点 % 几率 2 33.33333% 3 33.33333% 4 33.33333% 表3.1 - 节点1的信息素表

在这种情况下，选择了节点2[图3.2]，蚂蚁到达了它的源目的地。

然后蚂蚁移动并更新访问过的节点的信息素表，赋予更高的（且在数学上更偏向的）值。对于图3.2和表3.2，这将按以下方式计算：

• 节点2是最终目的地
• 到达目的地需要1跳
• 将1（跳）除以100：100%
• 将100加到节点2的概率值（当前为33.3333）：133.3333
• 将其他节点的数值加到133.3333（133.3333 + 33.3333 + 33.3333）：200（约数）
• 计算比率：比率 = 100/200 = 0.5
• 将节点的概率设置为其当前值乘以比率
  • 节点2：133.3333 * 比率（0.5） = 66.6666%
  • 节点3：33.3333 * 比率（0.5） = 16.6666%
  • 节点4：33.3333 * 比率（0.5） = 16.6666%
• 节点2（66.6666%）+ 节点3（16.6666%）+ 节点4（16.6666%）= 99.9999%

系统并非100%准确，因为总和永远不会正好等于100%，但它足够接近，可以在所需级别内实现准确性。

下图描绘了更新发生后的路径和信息素表。

图3.2	下一个节点 % 几率 2 66.6666% 3 16.6666% 4 16.6666% 表3.2

程序

为了本程序的目的，创建了一个双向、无权重的拓扑网络，包含30个节点，与英国同步数字层次结构（SDH）网络非常相似。在设置了基本参数后，运行模拟。首先，所有信息素表都默认设置为相等的权重，然后生成呼叫并放置在网络上。最初，选择的路径是随机的。如果一个呼叫无法连接到节点，它将被迫等待，并且等待计数器将被枚举以反映量子（以计时器滴答为单位）。一旦一个节点到达其目标节点，它将向后移动，并在遍历时修改本地节点的信息素表。路径越短，其信息素表条目获得的概率增加就越大。这种情况会反复发生，直到最快节点的权重发生变化，以至于较慢路径被选择的概率非常低。

注意：要编译和运行程序，您需要从 dotnetcharting.com 下载dotnetcharting。

程序功能

• ANTNet 开/关 - 切换算法的开启和关闭
• 模拟速度 - 1 tick/秒 - 1,000 tick/秒（或系统能运行的接近速度）
• 总呼叫数 - 模拟终止前完成的呼叫数量
• 最大并发呼叫数 - 同时允许的呼叫数量
• 节点容量 - 一个节点一次可以路由的呼叫数量
• 呼叫持续时间 - 呼叫的长度（以滴答为单位）
• 减少 I/O - 绕过网络可视化以提高模拟速度
• 连接后返回 - 连接后立即将节点返回到源
• 实时网络负载可视化 - 查看节点ID、容量和路由状态（蓝色=关闭）
• 带标签和模拟叠加的图形功能
• 将信息素表渲染为HTML

类

• MainForm - 应用程序的GUI
• DrawPanel - 实时网络可视化自定义控件
• Global - 包含应用程序访问的静态变量
• Node - 表示一个节点，并持有一系列 PheromoneTable 对象用于路由
• Call - 表示网络上的一个呼叫，并持有源节点和目标节点
• Simulation - 表示已完成的模拟，用于创建图形
• PheromoneTable - Node 的路由表

网络包含30个 Node，每个 Node 包含一个 PheromoneTable 对象数组，对应网络中其他所有 Node（29个）。每个 PheromoneTable 包含一个 TableEntry 数组，对应于当前 Node 连接到的每个 Node。

下图表示程序中类之间的关系

更新信息素表

// returns the next Node of the path
        public int ProbablePath(ArrayList VisitedNodes)
{
    // create a random generator
    Random r = new Random(Global.Seed);

    double val=0;
    double count = 0;
    double Lastcount = -1;

    ArrayList tempTEVector=new ArrayList();

    // loop through all the connected nodes
    for(int i=0;i<tableEntry.Length;i++)
    {
        // has the node been visited?
        bool v=false;

        //loop through all the visited nodes
        for(int j=0;j<VisitedNodes.Count;j++)
        {
            // if the ID's match then this node has alrady been visited
            if(tableEntry[i].NodeID==(int)VisitedNodes[j])
                v=true;
        }
        
        // If v is false, then the node hasn't been visited.. so Add
        if(!v) 
        {
            // get the node
            Node n = Global.Nodes[tableEntry[i].NodeID];

            // if the node is accepting connections
            if(!n.FullCapacity)
            {
                // add the node as a possible candidate
                tempTEVector.Add(tableEntry[i]);
            }
        }
    }
    
    // if all connections have been visited
    if(tempTEVector.Count==0)
    {
        // loop through all the connected nodes
        for(int i=0;i<tableEntry.Length;i++)
            tempTEVector.Add(tableEntry[i]);
    }

    // get the ceiling amount for probabilities
    for(int i=0;i<tempTEVector.Count;i++)
        val+= ((TableEntry)tempTEVector[i]).Probablilty;

    //create random value
    val = r.NextDouble()*val;

    // loop through the temp Table Entries
    for(int i=0;i<tempTEVector.Count;i++)
    {
        // increment the count on each loop
        count += ((TableEntry)tempTEVector[i]).Probablilty;

        // if the random value falls into delegated range,
        // then select that path as the next node
        if(val>Lastcount && val < count)
            return ((TableEntry)tempTEVector[i]).NodeID;

        // get the value of the last count
        Lastcount=count;
    }

    // method should never return here
    return -1;
}

通过信息素表返回下一个节点

// updates the probabilities of the pheromone table by multiplying the selected 
// nodes probability by a radio of  newVal
public void UpdateProbabilities(double newVal, int EntryTableNodeID)
{
    TableEntry t;
    double total=0;

    // loop through all the table entries
    // get the total enumeration of probabilities and add the new value.
    // Since this total will be more than 100, a ratio multiplication is
    // applied. Although these values will not equate to exactly 100%, floating
    // point calculations will be accurate enough 
    // at least 99.99999% which is satisfactory
    for(int j=0;j<tableEntry.Length;j++)
    {
        t = tableEntry[j];

        // enumerate the total Probablilty
        total += t.Probablilty;
    
        // if the table entry matches the id of the chosen node path
        if(EntryTableNodeID==t.NodeID)
        {
            // add the new value to the total
            total += newVal;
            t = tableEntry[j];
            // add the new value the current value of the selected path
            t.Probablilty += newVal;
        }
    }

    // calculate the ratio for the multiplication
    double ratio = 100/total;

    // loop through each table entry and multiple the current probability
    // by the new ratio
    for(int j=0;j<tableEntry.Length;j++)
    {
        tableEntry[j].Probablilty *= ratio;
    }

    // this will enumerate all the values to 99.99999%
}

// Constructor takes a node to represent and a list of all connected nodes off the
// calling node
public PheromoneTable(Node n, int[] conns)
{
    this.NodeID = n.ID;

    // create a tableEntry array the same length as the number of connections
    this.tableEntry = new TableEntry[conns.Length];

    // create a new tableEntry for each connection
    for(int i=0;i<conns.Length;i++)
        tableEntry[i] = new TableEntry(conns[i]);

    // set default equal values
    for(int i=0;i<conns.Length;i++)
        tableEntry[i].Probablilty = (100 / (double)conns.Length);
}

模拟结果

以下测试将说明ANTNet算法如何影响流量的路由。这些测试将显示算法在没有ANTNet运行的系统上的有效性。由于可以开启和关闭节点，将进行一系列测试比较，以显示当路径不再有效且必须选择新路径时，ANTNet如何改进网络的路由。

这些测试使用以下参数运行：

• ANTNet 开
• 模拟速度 - 1,000 tick/秒
• 总呼叫数 - 5000
• 最大并发呼叫数 - 60
• 节点容量 - 35
• 呼叫持续时间 - 170（呼叫的长度，以滴答为单位）
• 减少 I/O - 绕过网络可视化以提高模拟速度
• 连接后返回 - 连接后立即将节点返回到源

ANTNet vs. 非ANTNet

第一个测试包含两个模拟：

• 模拟1（橙色）- ANTNet算法 OFF
• 模拟2（蓝色）- ANTNet ON

从这次模拟可以看出，即使在前500个呼叫完成时，ANTNet已经将平均跳数减少了约1.5个节点。这在模拟结束时更加明显，最佳路径选择变得更加偏向，并被强化为最优路线，从而使ANTNet的网络性能提高了近3.5跳。

为了从不同角度查看算法，下图描绘了在第2000个呼叫后关闭ANTNet算法然后激活它的系统运行情况。这可以通过一个标签来识别，然后平均跳数下降了近2跳。

循环消除

在蚂蚁返回其源节点之前，可以调用循环消除优化技术。循环的问题在于它们可能接收比应有的多得多的信息素，导致自强化循环的问题。

图5.3显示了两个模拟：

• 模拟1（橙色）- 循环消除 OFF
• 模拟2（蓝色）- 循环消除 ON

从这个测试来看，循环消除将平均跳数减少了1个节点，并且适应性更加稳定。这意味着当必须选择替代路径时，循环消除算法比常规实现响应速度更快。

注意：两条线都显示了实际遍历的节点数，而不是循环消除后的节点数。

适应性

模拟网络在节点被移除时如何适应非常重要。静态路由表可能包含最短路径，但它们不一定考虑网络流量和离线节点。程序中运行了三个模拟来显示系统与非自适应算法相比如何适应。

模拟1（橙色）

这是模拟器的正常运行，用于为接下来的两个模拟创建最优信息素表。

模拟2（蓝色）

自适应算法 OFF。

节点14、15和17被关闭，因为它们是伦敦的主要北部接入枢纽，所以流量需要分流到英格兰西部。由于网络是非自适应的，信息素表会偏向于已离线的节点，并因此导致持续重定向和每次都要走更长的路程。这种增加在图6.4的蓝色线上显示。

模拟3（绿色）

自适应算法 ON。

节点14、15和17仍然关闭，但由于网络现在设置为自适应，信息素表会被重新调整，系统会学习替代路线。这可以在图6.4的绿色线上看到。

建议

如果任何人有任何问题、bug或建议，请发表评论。

参考文献

1. Appleby, S., Steward, S. (1994). Mobile software agents for control in telecommunication networks. In BT Technology Journal, Vol. 12, No.2.
2. ANTNet: A Mobile Agents Approach to Adaptive Routing. Gianni Di Caro and Marco Dorigo.
3. Ant-based load balancing in telecommunication networks. Ruud Schoonderwoerd1,2, Owen Holland3, Janet Bruten1, and Leon Rothkrantz.
4. Data Networks. Bertsekas, D., Gallager, R. (1992).

历史

• 2006年5月4日：初始版本
• 2010年8月17日：更新
• 2023年1月10日：更新