基于领域知识的多目标路径规划算法研究

沙特国王大学学报基于领域知识的单目标和多目标Ritam Sarkara，Debaditya Barmanb，Nirmalya Chowdhurya，a印度加尔各答Jadavpur大学计算机科学工程系，邮编700032b计算机系统科学系，Visva-Bharati，Santiniketan 731235，印度阿提奇莱因福奥文章历史记录：收到2020年2020年9月12日修订2020年10月10日接受2020年10月17日网上发售保留字：遗传算法机器人路径规划基于领域知识的算子单目标路径规划多目标路径规划A B S T R A C T在移动机器人路径规划问题中，目标是找到一条从一个源到单个或多个目标的最优无碰撞路径。基于领域知识的遗传算法已经被提出来解决具有单个以及多个独立目标的路径规划问题。本文提出了四种新的基于领域知识的算子，即“电路去除算子”、“插入-删除算子”、“细化算子”和“目标对齐算子”。在这四个算子中，前三个算子用于具有单个目标的路径规划问题，而所有这四个算子都用于具有多个独立目标的路径规划问题。所提出的方法已部署在不同大小的几个模拟环境。从实验结果来看，基于领域知识的算子提高了传统遗传算法的性能。我们提出的方法移动机器人的路径规划问题有单一的目标优于一些以前提出的进化算法为基础的方法。©2020作者由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍移动机器人在MRPPP中，每个可能的路径都有一个起始节点，它可以包含单个或多个目标节点。还有一个机器人穿越的环境其目的是得到一个最佳或接近最佳的路径考虑的距离由机器人穿越的优化标准。机器人根据障碍物的性质，MRPPP分为两种类型：1。机器人二、障碍物不固定环境下的机器人例如，障碍物可以改变它们的位置和/或一些新的障碍物可以*通讯作者。电 子 邮 件 地 址 ： nirmalya63@gmail.com ， nirmalya.chowdhury@jadavpuruni-versity.in（N。Chowdhury）。沙特国王大学负责同行审查出现或消失的时间。这就是所谓的动态环境。机器人路径规划也可以大致分为两种类型（即，离线路径规划和在线路径规划）。离线路径规划是一种事先已知环境先验知识的路径规划，而在线路径规划是一种事先未知环境先验信息的路径规划，机器人在环境发生变化时通过一些传感器获取信息。具有单个目标的机器人的路径规划问题可通过若干技术来解决（Zhang等人，2018年）。其中一些是：C空间（Lozano-Perez，1983），势场（Chuang和Ahuja，1998），A* 算法（Warren，1993 ） ， 动 态 规 划 （ Willms 和 Yang ， 2006 ） ， Voronoi 图（Takahashi和Schilling，1989），由人工神经网络组成的软计算方法（ Gaudiano 等 人 ， 1996 ） 、 进 化 算 法 （ 粒 子 群 优 化 （ PSO ）Nasrollahy和Javadi，2009）、模糊逻辑（Meléndez等人，Liu等人（2017）使用蚁群优化（ACO）算法求解MRPPP。他们使用基于网格的环境。Ayari和Bouamama（2017）使用动态分布式PSO为多个机器人找到最佳无碰撞路径。Al-Jarrah等人提出了一种基于模糊逻辑和细菌算法的混合边缘检测算法。（2018年）。 Wang等人https://doi.org/10.1016/j.jksuci.2020.10.0101319-1578/©2020作者。由爱思唯尔公司出版代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。制作和主办：Elsevier可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comR. Sarkar，D.Barman和N.乔杜里沙特国王大学学报4270ð Þ ð Þ（2018）还将PSO用于具有多个目标的MRPPP。Zhang等人（2018）使用PSO和差分进化的组合来解决MRPPP。Saraswathi等人（2018）提出了一种使用Cuckoo搜索和Bat算法的混合算法，用于求解环境未知或部分已知的MRPPP。Tuba等人（2018）使用头脑风暴优化，提出了一种求解有静态障碍物MRPPP问题的群智能算法。Lamini et al.（2018）改进了交叉算子以生成可行路径。此外，它还防止了过早收敛，因为交叉操作后，由于染色体长度可变，可能会生成不可行路径。Orozco-Rosas et al.（2019）开发了一种基于膜计算的GA和人工势场方法的混合技术来生成无碰撞的最优路径。这种边缘检测算法已用于改进的GA中，以返回移动机器人的最优路径。Dai等人（2019）通过结合A* 技术和MAX-MIN Ant系统的特点，改进了MRPPP的ACO。Li等人（2019）将MRPPP公式化为基于识别传热路径的拓扑优化问题。Luan等人（2020）提出移动机器人的多智能体A启发式技术。Alam等人提出了一种基于粒子群优化算法的移动机器人路径规划最短无碰撞路径算法。（2020年）。这些方法的主要问题是它们的高计算量，复杂性和它们可能陷入局部最优的事实看起来，基于遗传算法（GA）的方法（Tuncer和Yildirim，2012; Li等人，2006; Hu和Yang，2004; Kang等人， 2014）将是非常有效的解决这些问题，因为它是一个多维搜索技术，它同时处理多个解决方案（Murthy和Chowdhury，1996）。遗传算法已被应用在许多其他领域也。他们中很少有人是（Deaven和Ho，1995; Reeves，1995; Hou等人，1994年;Murthy和Chowdhury，1996年）。机器人移动机器人的路径可能包含多个目标。这可以有三种类型。a）每个靶标依赖于其他靶标，b）靶标彼此独立，c）a型和b型的组合（Dong等人，2016年，一些目标是相互依赖的，其余的是独立的。首先提出了一种基于领域知识的单目标遗传算法来解决机器人路径规划问题。 然后将其扩展为一种基于领域知识的多目标遗传算法（DKBGAMT），该算法可以处理b型多目标问题。文件的其余部分组织如下。第2节和第3节分别对问题和提出的方法进行了详细的描述使用不同模拟环境的实验结果可以在第4节中找到，结论性评论在第5节中陈述。2. 问题描述本文研究了具有单一目标的单机器人路径规划问题，其中每一条可能的路径由一个起始节点、一个目标节点和介于它们之间的若干中间节点组成。为此，我们已经开发了一些遗传算法，并将其添加到我们提出的传统遗传算法。这些搜索引擎使用各种环境相关的信息，并作为本地搜索策略。这些局部搜索策略的目的是提高传统遗传算法在更短时间内找到更好解的能力。这些事实已通过实验得到证实。此外，我们还解决了另一个问题，即针对多个独立目标的单机器人路径规划，其中可能的路径包括起始节点、多个目标模式以及起始节点和第一目标之间的一些中间节点获取节点之间以及任意两个连续目标节点之间。此外，目标节点可以以任何顺序出现，因为它们彼此独立。我们考虑了机器人在一个模拟环境中的移动，该环境是一个有序编号的网格环境。其目标是得到一个最佳或接近最佳的路径考虑的距离作为优化标准的机器人穿越。在整个工作过程中考虑了某些假设，如下所述。(i) 所有模拟环境本质上都是静态(ii) 机器人的速度是固定的。(iii) 关于环境的完整信息已被假定为预先已知的。(iv) 由于障碍物边界由障碍物的实际边界和机器人所需的最小安全距离组成，因此移动机器人在整个研究中被视为一个点（Hu和Yang，2004）。3. 拟议的方法我们已经提出了基于遗传算法的方法来解决机器人第3.1节介绍了我们提出的单目标机器人路径规划方法3.1. 单一目标的拟议方法在这项工作中，我们提出了一种基于遗传算法的优化技术，以找到最优（即最短）的路径，机器人到达从起始节点S到目标节点T在静态环境中，而不与障碍物发生任何碰撞遗传算法是一种受自然遗传系统原理启发的随机搜索过程。在遗传算法中，每一个解决方案都被编码为染色体，一些预定义数量的染色体构成的人口。遗传算子（即选择，交叉和突变）在每次迭代或世代中应用于群体的个体，直到满足某些终止标准。在每一代结束时，采用精英策略将上一代的最佳染色体复制到当前一代中。适应度函数用于评估特定染色体相对于群体中其他染色体的良好程度该适应度函数可以是最小化的或最大化的，这取决于问题场景。3.1.1. 环境表现基于网格的分解已在这项工作中使用decomp- pose机器人的环境到 一 个 集 合 的 有 序 编 号 的 我 们 将 网 格 视 为 矩 形 （ Tuncer 和Yildirim，2012; Li等人，2006; Hu和Yang，2004; Kang等人，2014年，在形状。 如图 1（a）网格基本上有两种类型：彩色网格和空白网格。彩色网格代表障碍物，机器人可以自由移动的网格是空白网格。起始节点为S，预先知道目标节点T1和T23.1.2. 路径表示在机器人的路径规划问题中，每条路径都被看作是一个染色体。移动机器人的路径有不同类型的表示。例如十进制编码（Tuncer和Yildirim，2012; Li等人，2006; Hu和Yang，2004），二进制编码（Nagib和Gharieb，2004）等。在本文中，十进制编码的路径表示已被用于可能的路径是各种长度。在每条路径中，第一个节点是起点R. Sarkar，D.Barman和N.乔杜里沙特国王大学学报4271ð Þ- 你好-Fig. 1. (a)机器人最后一个节点是目标节点。如果一条路径的每一段都通过了空白网格，那么只有该路径可以被认为是可行路径，否则它就是不可行路径。 1（b）路径（1，10，14，36）是可行路径，而路径（1，6，36）是不可行路径。3.1.3. 初始种群初始种群中的个体或路径（也称为染色体）是随机生成的，没有一个个体是不可行的。不可行项的存在对于一个特定的问题，随着人口规模的增加，搜索过程变得更加多样化，但它引入了额外的计算成本。因此，选择种群规模以保持搜索过程中的多样性和计算成本之间的平衡是非常重要的此外，在文献中不存在为给定环境选择适当的种群大小值的标准指南也不存在任何可以通过仅检查环境的大小、源和目的地的位置、形状、大小以及环境中存在的障碍物的位置来测量环境的复杂性水平的标准除此之外，不存在这样的方法，其产生用于特定复杂性水平的环境的适当的群体大小。因此，唯一的解决方案是为环境使用不同的种群大小，并选择在可接受的计算时间限制内提供最佳结果同样，我们对每个环境使用了不同的种群大小，并报告了我们在计算时间方面获得可接受结果的种群大小。3.1.4. 健身适应度函数用于评价群体中染色体设P是从起始结点到目标结点的包含n个结点的路径由于距离已被视为优化标准，因此目标函数f（如等式（1）所示）（1）路径P需要最小化。Xn q22注意，由于惩罚分数增加了适应度值，因此选择不可行路径的概率降低。3.1.5. 遗传算子有三个遗传算子。它们是选择，交换和突变.这三个遗传算子在下文中进行了描述。3.1.5.1. 选择. 选择算子是基于“适者生存”的概念换句话说，特定染色体的选择概率与该染色体的适应度值成比例从群体中选择染色体以创建交配池，其大小与群体的大小相同3.1.5.2. 交叉。在交叉中，两个亲本染色体之间交换信息，并为下一代产生两个后代。在这项工作中，我们使用了单点交叉，其中单点是从除了起始节点和目标节点之外长度较短的父染色体中随机选择的。否则，在执行交叉之后，可能存在在子弹簧之一中具有多个开始节点或目标节点而在另一子弹簧中没有开始节点或目标节点的机会1/1.ð1 Þ¼惩罚;惩罚b.如果路径P不可行0;如果路径P可行由方程式（1），xi和xi≠1是第i个的x坐标，分别是路径P的第1个节点。类似地，yi和yi1是路径P的第i个和第i 1个节点的y坐标，penalty表示路径P的罚分。如果路径P被发现是不可行路径，则它等于环境中可能的最大路径段（即b），否则为零。由于该路径规划问题的目的是获得从起始节点到目标节点的最短可行路径，因此我们需要最小化等式中给出的目标函数f（一）. 可能如交叉的示例-1所示，父1和父2是父染色体，其中0是起始节点，150是目标节点。假设，第四个位置已经被随机选择用于交叉。结果，其余部分（即第四位置之后的部分）已经在亲本染色体之间交换，以产生后代。但是根据交叉的例子-2中所示的交叉f¼xiþ ðyiþ1-yiÞ罚金刑R. Sarkar，D.Barman和N.乔杜里沙特国王大学学报4272ðÞðÞ图二、（a）可见电路的示例，（b）电路移除之前的路径，（c）电路移除之后的路径如果选择第六个位置进行交叉，则后代1不包含目标节点（即，150），而后代2包含目标节点两次。因此，交叉点需要从具有较短长度的父染色体中选择，并且它不能是起始节点或目标节点。3.1.5.3.突变变异算子在种群中引入一定的遗传变异，以探索解空间而 不 陷 入 局 部 最 优 。 本 研 究 中 使 用 的 变 异 算 子 基 于 Tuncer 和Yildirim（2012）提出的变异算子。在这个方法中，变异算子已经被修改了一点，如算法1所示。例如，考虑图1（c）中的路径P（1，21，36），如果我们在路径上应用变异算子，则它可以选择除了起始节点和目标节点之外的任何节点。假设21号被选中进行变异。21的邻居是20、14、15、16、22、28、27和26。现在，21将被来自集合{21，20，14，15，16，22，28}的节点之一替换，该节点产生最佳拟合值。由于节点26和27是障碍物，所以它们不包括在所述集合中。预定义的突变概率。因此，在这种类型的突变中，对于每个染色体，如果满足上述条件，则至多一个节点可以参与突变操作。因此，需要更多的迭代次数或代来探索解空间，这可能会降低收敛速度。为了避免这个问题，在这项工作中，如果满足上述条件，则路径中的每个节点（除了起始节点和目标节点）都有机会参与变异操作，从而减少迭代次数。3.1.6. 领域知识算子有时，由于环境中障碍物的复杂排列和形状，用传统的遗传算法很难得到最优或接近最优的路径。在这些情况下，引入一些局部搜索策略，加强了传统的遗传算法，使其不会收敛到局部最优。这些局部搜索策略有助于搜索过程收敛到某些局部或全局最优解，另一方面，GA负责找到球最优点可能存在的最可能的区域。因此，传统遗传算法与局部搜索策略一起导致更好的优化算法1. 突变根据Tuncer和Yildirim（2012）中的突变，对于每个染色体，突变算子只随机选择一个节点，然后生成一个随机数（比如rand）。如果rand6Pmut，则执行变异操作，其中Pmut是（Kala，2012; Kala等人，2009年）。这些局部搜索策略也被称为基于领域知识的算子（DKBO），因为它们基于一些只适用于它们所应用的领域的知识。在这项工作中，三个领域知识为基础的操作（DKBOs）已被引入。它们是Circuit Removal操作符、Insertion-Deletion操作符和Refinement操作符。这些运算符有助于通过基于如下所述的一些算法在该路径3.1.6.1. 移除电路。Circuit Removal操作符检测并从路径中删除回路通常，如果在一条路径或染色体上有多个出现的节点，则出现回路。但在这种情况下，有时虽然染色体中没有电路有三种类型：可见电路、隐藏电路和可见和隐藏电路的组合。下文对此作了说明可见电路：-如果电路的出现仅仅是由于编码染色体中节点的重复，那么它可以被认为是一个可见的电路。‘‘例如，考虑路径1; 3; 9; 15; 8; 9; 23;36，如图1所示。 2（a）. 这里，电路仅由于节点9的多次出现而出现因此，在应用电路移除之后，它变为1; 3; 9; 23; 36。隐藏电路：-有时，路径或编码染色体可能包含一些回路，即使没有重复的节点。这些电路被认为是隐藏的电路。 这种类型的电路可以是两种类型。R. Sarkar，D.Barman和N.乔杜里沙特国王大学学报4273类型1：由于两个非相邻路径段之间的相交而形成的回路.类型2：路径段通过也是该路径的一部分的节点例如：考虑图中的路径（1，3，21，11，8，14，35，36）。第2段（b）分段。虽然没有任何节点的重复，但它包含两个上述类型的电路。它包含电路可能导致过早收敛的节点。为此，这里引入了插入操作符。插入操作符选择路径段，然后在所选路径段之间插入节点。插入后，在应用其他操作符后，将插入的节点拟合到适当的位置。算法3描述了用于插入-删除运算符的算法。类型1，由于两个非相邻路径段之间的相交（3）（21）（11）（8）由于路径段（14，35）通过作为路径的一部分的节点21，所以它也包含类型2的环路。在应用我们提出的电路去除算子之后，路径变成（1，3，9，8，14，21，35，36），如图所示。 2（c）.可见和隐藏电路的组合：-这种类型的回路是由于节点和隐藏回路的多次出现而出现的。算法2中说明了电路移除运算符的算法算法2. 电路拆除操作员算法3. 插入-删除运算符3.1.6.2. 插入-删除操作符。Tsai等人（2011）将Add and Deletion算子的概念应用于机器人路径修改。在Add算子中，基于称为B样条的平滑技术修改路径，该平滑技术在两个节点之间添加一个节点。根据他们提出的删除操作，删除随机选择的节点。我们提出的插入-删除算子由两个子算子组成：插入和删除算子。 在这里，删除运算符选择两个相邻的路径段，并检查第一段的起始节点和第二段的最后节点是否可以在它们之间没有任何障碍物的情况下连接。例如，令P i;P j和P j; P k是路径P的两个相邻路径段，则该算子将删除节点Pj，如果Pi和Pk可以连接而不与任何障碍物碰撞（即，彩色网格）。删除算子的作用但有时，删除操作符的应用导致路径具有很少数量的例如，考虑图1所示的环境。 3（a）和（b）。图3（a）中所示的路径是通过仅应用删除算子以及其它算子而生成的接近最优的路径，但是插入算子的应用在路径中引入了附加节点，并且使得路径如图3（a）中所示为最优的。 3（b）款。3.1.6.3. 精炼操作员。在这项工作中使用的细化算子是基于李等人（2006）中使用的细化算子，该算子背后的原则是直角三角形中的hypotenuse的长度必须小于其他两边的长度之和。算法4描述了细化运算符。我们还通过实验表明，所提出的细化算子比Li等人使用的算子更有效。 2006年，他找到了一条更短的路。R. Sarkar，D.Barman和N.乔杜里沙特国王大学学报4274算法4. 细化算子在路径段（20，24）和（24，36）之间的任何可行路径段（即，没有与任何障碍物碰撞的路径段）中的任何一个已经从与24相邻的中间节点（即，路径段（20，24）和（24，36）已经生成直角的节点）开始因此，它得到没有与任何障碍物碰撞的路径段（23，30），并最终生成路径（1，20，23，30，36），该路径的长度大于由本工作中使用的细化算子获得的路径。3.1.7. 精英策略精英策略的目的是将上一代的最佳染色体保留到当前一代中。因为，最好的染色体（即精英）可能会丢失，如果他们没有被选中，或者如果交叉或突变改变了他们。该方法已在算法5中描述算法5.精英策略3.1.8. 终止条件虽然没有这样的通用停止标准的GA（Murthy和Chowdhury，1996），该算法将终止时，以下三个条件之一将得到满足：例如，考虑图4（a）中的路径（1，20，24，36）。在该路径中，两个相邻的路径段（20，24）和（24，36）形成直角。现在，由于路径段（20，36）与障碍物碰撞，我们已经在上述两个路径段中插入了所有中间节点。结果，根据算法4的第8行和第9行，这两个路径段变成（21，22，23，24）和（30，24）现在，由于（21，30）不与任何障碍物碰撞，所以首先从路径中删除24，然后在20之后插入21，在36之前插入节点30，如算法4的第10行到第24行所述结果，路径变为（1，20，21，30，36），如图4（b）所示但是如果我们在图4（a）所示的路径上应用Li等人（2006）提出的细化算子，我们将得到图4（c）所示的路径，其中生成的路径是（1，20，23，30，36），因为在Li等人（2006）中， 2006年，《关于存在的检查》(i) 生成总数超过100。(ii) 该算法在100次迭代或代内收敛到最优解。(iii) 最佳染色体的适应度值在连续50代左右保持不变。3.1.9. 流程图所提出的方法的流程图已在图中描绘。 五、3.2. 多目标拟议方法包含多个目标的移动机器人路径规划问题有以下三种a）多个目标，其中每个目标依赖于其他目标，b）多个目标，其中目标彼此独立，以及c）类型a和类型b的组合（即，一些目标是依赖的，其余的是独立的）。如果所有的目标或其中的一部分R. Sarkar，D.Barman和N.乔杜里沙特国王大学学报4275ð Þ-图三. (a)插入之前的路径，（b）插入之后的路径。图四、（ a）细化操作符之前的路径，（b）细化操作符之后的路径，（c）Li等人中的细化操作符示例。（2006年）。因此，目标是以所需的顺序检索从源到第一目标，然后从第一目标到第二目标等等（一个接一个）的最短路径。例如，假设有一个机器人在位置说X和它的工作是携带一个对象说O1从X到另一个位置Y。之后，机器人必须从位置Y拾取另一个物体O2并将其带到另一个位置Z。在这个问题中，源位置是X，目标分别是Y和Z。因此，我们不必费心设置目标的顺序，我们只需要规划一条从X到Y，然后从Y到Z的路径。但是，如果没有保持任何特定顺序的这种要求，那么目标是以最小化路径的总长度的方式获得应该从X开始并且包含两个目标Y和Z的路径。因此，对于类型（a）和（c），我们可以顺序地规划路径（即，从X到Y，然后Y到Z），但是对于类型（b），我们需要同时考虑所有目标，因为我们不知道将产生具有最短长度的路径的目标的顺序。我们提出的DKBGAMT可以处理b型问题。对于类型a和类型c，我们提出的基于GA的单目标方法可以根据目标节点的某些指定顺序顺序依次应用（即，从起始节点到第一目标节点，然后第一目标节点到第二目标节点等）。但是，在这项工作中，我们已经解决了B型问题，据我们所知，我们提出的方法是第一次尝试解决上述问题。3.2.1. 环境表征这里，环境表示类似于针对第3.1.1节中描述的具有单个目标的路径所 考 虑 的 表 示 。 唯 一 的 区 别 在 于 ， 该 环 境 包 含 源 S 和 多 个 目 标{T1;T2;T3;. ;Tn}而不是单个目标。3.2.2. 路径表示每个路径包含一个源和一组n目标{T1;T2;T3;. ;T n}，其可以以任何顺序出现。 如第3.1.2节所述，如果任何路径段与障碍物碰撞，则该路径将被视为不可行路径，否则它将是可行路径。3.2.3. 初始种群如第3.1.3节所述，初始种群的每条路径都是随机生成的，所有生成的路径都满足可行性标准。3.2.4. 健身评估具有多个目标的路径的适应性的技术与第3.1.4节中提到的相同。3.2.5. 遗传算子如前所述，存在三种类型的遗传操作子。它们是选择、交叉和突变。在这三个操作符中，选择和突变操作符的实现方式与单个目标问题的实现方式相同（参见第3.1.5节）。3.2.5.1. 交叉。在本工作中，每个可能的路径都包含开始节点和所有预定义的目标节点，但不一定以任何特定的顺序。为此，在执行交叉操作之前，路径已经被划分为所有可能的路径段。 例如，如果有是一路径说P1S;. ;T11;. ;T21;. ;T i1;. ;T n1包含n个目标，其中T i1是路径P1的第i个目标和P1的第i个目标可能不与另一条路径的第i个目标相同，比如说P2（即，Ti2）。这里虚线表示中间节点。因此，路径P1将被... ;T11;T11.. . ;T21;. ;R. Sarkar，D.Barman和N.乔杜里沙特国王大学学报42763.2.6. 基于领域知识的算子类似于交叉算子，对于所有DKBO（例如，电路移除、插入-删除算子和细化算子），首先，具有n个目标的任何路径（比如P1）已经被划分成n个段，然后DKBO已经被应用于这些路径段中的每一个。之后，它们按照原来的顺序合并在一起。在本文中，我们引入了一种新的DKBO算法，即图五. 所提出的算法的流程图。T ; T i1;T i1;. ; T i11;.. . ，和Tn-11;.. . ; T n1。因此，如果有n个目标，则路径段的数量将等于n。现在，如果路径P1和P2属于Sarkar中提到的三种情况之一，则在路径 P1和 P2的路径段之间执行如第3.1.5.2等人（2020），随后根据新生成的路径段在路径中的原始顺序对它们进行重新排序和合并。3.2.6.1. 目标对准操作员。由于Mutation 、Insertion- Deletion和Refinement操作符，我们可能会得到一个目标可能出现多次的路径。我们提出了一个新的DKBO命名为目标对齐算子来处理这个问题。此操作符将这样的路径转换为新路径，其中每个目标仅出现一次。在应用这个操作符之前，我们需要找到每个目标节点第一次出现的位置，并将它们存储到一个名为initial_target_positions的数组中。这种机制可以是以下三种类型的情况。案例一：假设（0，5，8，10，14，8，23，18）是一条路径，其中0是起始节点，目标节点是：8和18，因此initial_target_positions=（3，8 ） 。 现 在 ， 由 于 目 标 节 点 8 的 出 现 次 数 是 两 次 ， 并 且 在initial_target_positions中的目标节点8的位置和节点8的第二次出现之间没有其他目标节点结果，我们得到了路径（0，5，8，23，18），其中每个目标节点的出现次数都是1，并且长度比前一个短。案例二：考虑路径（0，5，8，23，30，10，18，24，29，30），其中0是 起 始 节 点 ， 目 标 节 点 是 8 ， 30 和 18 。 因 此 ， initial_tar-get_position=（3，5，7）并且存在目标节点30的多次出现，并且这也是最后一个节点。在这些情况下，从第三个目标之后的节点中删除所有节点（即，倒数第二个目标节点18）到最后一个节点。因此，我们得到了路径（0，5，8，23，30，10，18），其中每个目标节点的出现次数正好是1，并且长度也比前一条路径短。案例三：假设有一条路径（0，5，8，23，18，9，12，15，10，8，24，29，30），其中0是起始节点，目标节点是8，18，15，30.因此，initial_target_position=（3，5，8，13）和目标节点8已经出现多次。此外，存在多个见图6。(a)环境1，（b）环境2。R. Sarkar，D.Barman和N.乔杜里沙特国王大学学报4277见图7。(a)（b）环境4。见图8。(a)（b）环境6。目标节点在第一次和第二次出现的8之间，并且它也不是最后一个节点。现在，考虑节点5（即，就在节点8的第一次出现之前定位的节点）和节点18（即，节点8的第一次出现之后的目标节点）作为段1（即，段1=（5，18）），然后节点15（即，节点8的第二次出现之前的目标节点）和24（即，节点8的第二次出现之后的节点）作为段2（即，段2=（15，24））。请注意，如果路径段（例如段1）不与任何障碍物相交，则它将是可行的根据路径段的可行性，可能存在以下情况。案例3a：如果段1和段2都是可行的，则计算两个段的拟合度值。之后，如果段1具有更高的适应度值，则删除节点8和23（即，删除从节点8的第一次出现直到下一个目标节点之前的节点的所有节点），否则，删除节点10和8（即，删除目标节点15之后直到目标节点8的第二次出现的所有节点如果段1和段2具有相同的适应度值，则随机删除（8，23）或（10，8）案例3b：如果段1或段2是可行的，则如果段1是不可行的，则删除节点8和23，或者如果段2是不可行的，则删除节点10和8。案例3c：假设线段1和线段2都是不可行的。在这种情况下，在节点8的第一次和第二次出现之间可以存在多个目标节点，并且它也可以不是最后一个节点。 在这些情况下，我们已经为目标节点8的每次出现采取了单独的路径。[001 pdf 1st-31 files]这些是：P1=（0，5，23，18，9，12，15，10，8，24，29，30）和P2=（0，5，8，23，18，9，12，15，10，24，29，30）。最后选择了具有最小适应值的路径3.2.7. 精英策略针对所提出的DKBGAMT的精英策略也以与针对单个目标的精英策略相同的方式被采用（参考第3.1.7节）。唯一的区别是，有一个名为Target alignment操作符的DKBO，它已应用于Mutation，Insertion-Deletion和Refinement操作的末尾。4. 实验结果以下部分描述了机器人的路径包含单个以及多个目标的实验结果。第4.1节叙述了单个靶的实验结果，多靶的实验结果已在4.2节中陈述。4.1. 机器人单目标路径的实验结果根据环境的大小，本节进一步分为两节（即第4.1.1节和第4.1.2节）。第4.1.1节和第4.1.2节分别给出了机器人在中等规模环境和大规模环境下包含单个目标的路径的实验结果。除此之外，还有另一个部分（即4.1.3），我们对单个机器人路径规划进行了全面讨论。4.1.1. 中等规模环境下机器人单目标路径实验结果所提出的方法已部署在几个环境。值得注意的是，这些环境中的一些也用于以前关于这个主题的一些工作（Tuncer和Yildirim，2012这有助于我们的实验比较R. Sarkar，D.Barman和N.乔杜里沙特国王大学学报4278结 果 与 GABAAMRPP （ Lamini 等 ， 2018 ） 、 IGA （ Tuncer 和Yildirim，2012）、ROBIL（Kang等人， 2014），并且所提出的方法不使用DKBO来解决相同的问题。在所有实验中使用的不同算子的值如下：突变概率-0.1，交叉概率-1.0，电路去除概率-1.0，插入-删除概率-1.0。0.30对于删除操作概率为0.20，对于插入和细化操作概率为-1.0。实验结果可参见下表1在这些表中，我们报告了方法收敛时间还包括生成初始种群所需的时间。环境1至6在图中表示。 6（a），（b）; Fig.7（a），（b）; Fig. 第8（a）段。(b)其实验结果分别列于表1-6中从表1-6中给出的实验结果这些事实证明了我们提出的方法比其他方法与传统的遗传算法（即，不使用DKBO的建议4.1.2. 大规模环境下机器人单目标路径实验结果在本节中，我们通过将其性能与GABAAMRPP（Lamini等人，2018）、IGA（Tuncer和Yildirim，2012）、ROBIL（Kang等人，2014），以及在大规模环境（即环境-7和环境-8）上不使用DKBO的所提出的方法。这些环境如图9和图10所示，相应的实验结果分别如表7和表8基于表7和表8中所示的实验结果，可以说，我们提出的方法成功地找到了环境7和环境8的最短长度路径。虽然environment - 7的收敛时间表1环境-1。方法人口规模最佳路径长度平均最佳路径长度平均世代数平均收敛时间（s）GABAAMRPP Lamini等. （2018年）2028.7328.7379.64ROBIL Kang等. （2014年）3027.7732.00297.8502 The Dog（2012）6027.2227.67152.46建议的方法不使用2027.2227.22231.78民主佛教建议使用DKBO1027.2227.22100.54表2环境-2。方法人口规模最佳路径长度平均最佳路径长度平均世代数平均收敛时间（s）GABAAMRPP Lamini等. （2018年）5031.6532.011123.90ROBIL Kang等. （2014年）7030.7532.183421.9302 The Dog（2012）6028.7129.64254.43建议的方法不使用5028.6429.02526.24民主佛教建议使用DKBO3028.5628.78223.05表3环境-3方法人口规模最佳路径长度平均最佳路径长度平均世代数平均收敛时间（s）GABAAMRPP Lamini等. （2018年）4024.8326.14816.98ROBIL Kang等. （2014年）5024.2425.652610.5302 The Dog（2012）8022.8624.20204.89建议的方法不使用4022.7623.75324.67民主佛教使用DKBO的建议方法2022.4222.43283.42表4环境-4。方法人口规模最佳路径长度平均最佳路径长度平均世代数平均收敛时间（s）GABAAMRPP Lamini等. （2018年）4026.2426.42818.48ROBIL Kang等. （2014年）6025.3726.373118.0102 The Dog（2012）10024.2025.08176.72建议的方法不使用6023.3024.52478.34民主佛教使用DKBO的建议方法3022.8324.05303.99R. Sarkar，D.Barman和N.乔杜里沙特国王大学学报表54279环境-5。方法人口规模最佳路径长度平均最佳路径长度平均世代数平均收敛时间（s）GABAAMRPP Lamini等. （2018年）4024.7425.141258.53ROBIL Kang等. （2014年）10026.6140.961923.6002 The Dog（2012）8021.8522.561928.90建议的方法不使用4021.8522.023817.00民主佛教使用DKBO的建议方法1021.8521.85236.51表6环境-6方法人口规模最佳路径长度平均最佳路径长度平均世代数平均收敛时间（s）GABAAMRPP Lamini等. （2018年）5022.9022.9059.25ROBIL Kang等. （2014年）5022.5823.04101.6302 The Dog（2012）10022.5822.80162.26建议的方法不使用6022.5222.55424.49民主佛教使用DKBO的建议方法5022.0522.31353.93见图9。环境7.见图10。 环境8.4.1.3. 单目标路径规划的总体探讨表1至表8中所示的所有实验结果表明，我们提出的方法优于其他方法。它已经设法找出所有环境的最佳路径，并且对于大多数环境，收敛时间也小于其他比较方法。最小平均最佳路径长度表明，我们提出的方法始终发现更好的路径，所有的环境。当多个方法同时收敛于同一解时，可以用平均路径长度例如，对于IGA、不使用DKBO的所提出的方法和使用DKBO的所提出的方法，环境-1和环境-5的最佳获得路径是相同的。但是，我们提出的方法的平均最佳路径长度和收敛时间的值小于其他方法，这表明了所提出的方法的优越性。下一节报告了一些内部观察结果。(i) 由于我们提出的方法需要一些额外的计算，由于DKBO，似乎它但是，方法需要显著更小的种群规模，因此，它在大多数环境中都能在更短的时间内收敛。一般来说，随着种群规模的增加，它会向种群中引入更多的变异，这有助于收敛到更好的解。但是，我们提出的DKBO即使在较小的种群规模下也引入了足够的变异，这导致了一个更好的路径与相当少的人口规