【贪心K-均值自组织神经网络路径规划的算法实现概述4900字】

贪心K-均值自组织神经网络路径规划的算法实现概述目录TOC\o"1-3"\h\u24551贪心K-均值自组织神经网络路径规划的算法实现概述 1215011.1K-均值算法自组织神经网络算法 1140261.2引入贪心策略 1164231.3贪心K-均值自组织神经网络算法整体流程 1本章研究的单目标位置的多机器人系统路径规划问题，其特点是系统的所有目标任务先验且每个任务仅一个目标位置，该类问题通常被抽象为多旅行商问题模型。在1.3.2节中我们分析了基本的SOM不能直接用来求解多旅行商问题，本文首先把SOM网络和K-均值算法融合，将MTSP问题退化为多个标准的TSP，再使用多SOM网络并行求解标准的TSP问题。在K-均值的迭代过程中，由于传统的K-均值算法是聚类算法，在聚类过程中未考虑聚类结果的均衡性，当城市分布稀疏不一的情况时，会导致各旅行商的旅行路径不均衡，从而影响整体的旅行效率。因此我们引入贪心策略在K-均值的迭代过程中调节聚类结果。1.1K-均值算法自组织神经网络算法K-均值聚类算法是一种常用的无监督学习方法，可以实现对未标记数据进行分类。K-均值聚类算法的目标是将输入数据经过迭代后，将每个输入数据点分配给k组中的一组，这个特点使得该算法能够实现将MTSP退化为多个标准的TSP问题。假设系统中有k个机器人（即k个旅行商），则K-均值聚类的目标是将多个目标任务点聚类为k组，并把每组目标任务点分配给一个机器人去执行。K-均值自组织神经网络多机器人路径规划算法流程如算法1所示：算法1K-均值自组织神经网络多机器人路径规划算法1确定机器人数量k，K-均值最大迭代次数kmeans_iter，初始化聚类中心2whileK-均值算法未达到最大迭代次数do3计算所有任务点到k个聚类质心的欧式距离4将任务点分配到距离其最近的类别5对每个类别，计算新的聚类中心C6return各机器人所需执行的任务7for每个机器人do8初始化输出神经元9while未达到终止条件do10根据K-均值聚类结果输入目标任务位置g11计算输出神经元与输入目标位置距离确定获胜神经元12更新获胜神经元领域大小13更新学习率后计算获胜邻域权值向量14endwhile15return各机器人路径我们使用K-均值自组织神经网络算法在TSPLIB数据集krA100进行了分析，图1.3中的散点代表了krA100数据集中原始需要访问的100个城市位置，我们假设需要5个旅行商访问完这些城市，即5个机器人去完成这100个任务。K-均值自组织神经网络路径规划算法规划的路径结果如图1.4所示，每种颜色分别为每个机器人的执行路径，可以发现虽然K-均值自组织神经网络算法可以解决MSTP问题，同时由于K-均值的聚类性质可以较好的避免机器人之间发生冲突。但是也存在一些缺陷，如图1.5是各机器人的路径代价对比，可以发现3号机器人的负载明显高于其他机器人，这样的负载不均衡会导致其他机器人虽然完成了任务但必须等待3号机器人，从而造成多机器人系统整体运行效率降低。图1.3kroA100数据集原始数据图1.3kroA100数据集原始数据图1.SEQ图2.\*ARABIC4kroA100数据集原始数据图1.5各机器人路径代价图1.3kroA100数据集原始数据图1.SEQ图2.\*ARABIC5kroA100数据集原始数据图1.5各机器人路径代价图1.6贪心K-均值自组织神经网络算法流程图图1.5各机器人路径代价图1.3kroA100数据集原始数据图1.SEQ图2.\*ARABIC6kroA100数据集原始数据图1.5各机器人路径代价图1.3kroA100数据集原始数据图1.SEQ图2.\*ARABIC7kroA100数据集原始数据图1.4kroA100基本K-均值聚类结果图1.SEQ图2.\*ARABIC8kroA100基本K-均值聚类结据图1.4kroA100基本K-均值聚类结果图1.SEQ图2.\*ARABIC9kroA100基本K-均值聚类结据图1.4kroA100基本K-均值聚类结果图1.SEQ图2.\*ARABIC10kroA100基本K-均值聚类结据图1.4kroA100基本K-均值聚类结果图1.SEQ图2.\*ARABIC11kroA100基本K-均值聚类结据图1.5各机器人路径代价图1.5各机器人路径代价由于K-均值算法是一种聚类算法，它的目标是使得聚类完成后的类内相似度小，类间相似度尽可能的大。虽然该方法可以实现将MSTP退化为多个标准的TSP问题，通过实验分析可知，它在聚类过程中并未考虑各机器人的负载均衡问题。因此通常会出现任务密集区的机器人不断地在工作，而任务稀疏区域的机器人由于任务数量少，在完成任务后会空闲的问题。该问题会导致多机器人系统执行总任务所需的时间过长，从而导致系统的整体运行效率低，为了解决这种不均衡问题，本文进一步引进了贪心策略。1.2引入贪心策略通常解决在多机器人负载不均衡的问题上，最直观的解决方案是将负载大的机器人多出的任务分配给负载较小的机器人，从而平衡各机器人之间的负载。由于本文的优化目标为最小化多机器人中最大的路径代价maxspan，因此各机器人的负载由各自的路径代价来评估。本文提出的贪心K-均值算法自组织神经网络算法，通过在K-均值算法迭代过程中，引入贪心算法来计算当前迭代结果中各聚类结果的路径代价，根据路径代价来评估各机器人的负载情况，同时引入调节因子来调整每次迭代的分配结果，调节因子将负载较大的类别负载减小，将负载较小的类别负载类别扩大，从而解决K-均值自组织神经网络中存在的负载不均衡问题。贪心算法是指在求解某些问题时，暂不考虑全局情况，在当前状态下，总是做出在当前来看最好的选择。贪心算法由于仅考虑当前的最优值，通常求解的结果并非是最优值，但具备求解速度快的优点。我们在贪心K-均值迭代过程中，对路径代价的预估仅是用来指导调节因子调整大小，对路径代价的精度要求并不高，同时贪心算法的运算复杂度远低于其他路径求解算法。因此，使用贪心算法来指导K-均值的迭代变得十分有效。贪心K-均值算法主要过程如下：（1）开始迭代，确定聚类数量k，最大迭代次数Greedykmeans_max⁡_iter，偏置倍数δ，初始化k个聚类中心（2）计算所有任务点G=g1,dij=其中，dij表示任务点gi到聚类中心cj的欧式距离，xi,yi表示任务点gi（3）将任务点G=g1,g2,⋯,gn（4）对每个类别，计算其所有点Cj=gxk=i=1l−1其中，xk,y对每个类别，使用贪心算法计算其路径代价D=（6）在每次迭代过程中，使用放大和缩小调节因子分别调整最大和最小聚类空间，缩小调节因子narrowiter和放大调节因子enlargenarrowiter=Denlargeiter=Dave−其中，iter是指当前迭代次数，Dmax是指当前迭代轮数中最大的路径代价值，Dmin是指当前迭代轮数中最大的路径代价值，Dave（7）在每次迭代过程中，使用调节因子将最大和最小聚类空间的任务目标生成虚拟任务位置，将路径代价最大的聚类空间Cmax=g1xi=xi同样地，对路径代价最小聚类空间minDxi=xi（8）最后判断iter是否达到最大迭代次数，未达到则根据生成的虚拟任务目标位置回到第二步进行下一轮迭代，否则结束迭代，根据最终的聚类结果索引到真实任务目标位置，输出最终任务分配结果。算法2是贪心K-均值算法的详细过程，首先确定机器人数量k，即聚类数量，最大迭代次数Greedykmeans_max⁡_iter，以及缩放倍数δ。接下来使用贪心算法计算每轮迭代的分类结果中各机器人所需执行任务的路径代价，然后在最大聚类空间中，通过各机器人的平均路径代价与其路径代价差值来确定缩小调节因子narrowiter大小，同样地，扩大调节因子enlargeiter算法2贪心K-均值算法1确定聚类数量k，最大迭代次数Gkmeans_iter，偏置倍数δ，初始化k个聚类中心2while未达到最大迭代次数do3计算所有点到k个聚类质心的欧式距离4将数据点分配到距离其最近的类别5对每个类别计算新的聚类中心Ci6使用贪心算法计算各类别路径代价D7计算当轮迭代缩小调节因子narrowiter和扩大调节因子narrowenlarge8使用缩小调节因子narrowiter将聚类空间maxXY9使用扩大调节因子enlargeiter聚类空间minXY10endwhile1.3贪心K-均值自组织神经网络算法整体流程贪心K-均值自组织神经网络算法整体流程如图1.6所示，首先我们使用贪心K-均值算法各机器人分配任务，在此阶段将MSTP问题简化为TSP问题，然后在第二层使用多SOM并行为各机器人规划路径，即进行标准TSP的求解。图1.图1.6贪心K-均值自组织神经网络算法流程图算法3详细描述了贪心K-均值自组织神经网络的具体实现过程，在第一层中调节因子能够解决基本K-均值任务不均衡的问题，其原理在于调节因子在每次迭代时，会对当前迭代轮次的最大和最小聚类空间中的任务目标生成虚拟任务目标，虚拟任务目标呈现出最大聚类空间内的任务目标变得稀疏，最小聚类空间的任务目标紧密的效果。在每次贪心K-均值迭代时，narrowiter和enlargeiter分别对当前迭代轮次的聚类空间集合中的任务坐标进行调整，最大聚类空间的虚拟任务坐标位置由narrowiter生成，生成的虚拟任务坐标位置呈现出远离其聚类中心，靠近其他聚类中心的效果。在下次迭代聚类时，由于距离聚类中心的距离变化，最大聚类空间内的任务可能会被给其他类别。同样地，对当前轮次迭代的最小聚类空间，使用enlargeiter生成最小空间的虚拟任务目标，这些虚拟任务目标呈现出靠近其聚类中心，远离其他聚类中心的效果，在下次迭代聚类时，其他类别的任务目标可能会被新加入到该类别中。narrow算法3贪心K-均值自组织神经网络路径规划算法1确定机器人数量k，贪心K-均值最大迭代次数Gkmeans_iter，偏置倍数δ，并初始化k个聚类中心2while贪心K-均值算法未达到最大迭代次数do3计算所有任务点到k个聚类质心的欧式距离4将任务点分配到距离其最近的类别5对每个类别计算其所有点的均值并将均值作为新的聚类中心6使用贪心算法计算各类别路径长度D7计算当轮迭代缩小调节因子narrowiter和放大调节因子narrowenlarge8缩小调节因子narrowiter将聚类空间maxXY9使用放大调节因子enlargeiter聚类空间minXY10endwhile11for每个机器人do12初始化输出神经元13while未达到终止条件do14根据贪心K-均值聚类结果顺序输入目标任务位置g15计算输出神经元与输入目标位置距离确定获胜神经元16更新获胜神经元领域大小17更新学习率后计算获胜邻域权值向量18end我们使用贪心K-均值自组织神经网络算法在TSPLIB数据集krA100进行了测试，假设机器人数量为5台，如图1.7展示了TSPLIB数据集krA100虚拟城市的生成结果，深色散点代表真实的城市位置（即任务位置），浅色散点代表生成的虚拟城市位置。图1.8是基本的K-均值算法的分类结果，图1.9是贪心K-均值的分类结果，可以观察到，经过优化后，任务17,78,89,48,5被由负载较重的4号机器人转移到负载较轻的1号机器人，任务44,90,97由1号转到2号机器人，任务38,4,36由3号转移到5号机器人。图1.图1.7kroA100虚拟城市生成结果图1.SEQ图2.\*ARABIC12kroA100虚拟城市生成结果图1.图1.8kroA100基本K-均值分配结果图1.图1.9kroA100贪心K-均值