确定行驶路径的方法、装置、电子设备以及存储介质与流程

1.本公开涉及计算机技术领域，更具体地，涉及一种确定行驶路径的方法、装置、单子设备、存储介质和程序产品。


背景技术：

2.目前，用于求解车辆路径问题的智能优化算法包括：遗传算法、粒子群算法、模拟退火算法以及蚁群算法等。但是以上智能优化算法在优化过程中仅考虑了个体之间的竞争与协作，未能同时考虑种群之间的竞争与协作，造成求解精度低，收敛速度慢的问题。金字塔演化算法的分工与传递晋升机制，可以考虑种群间的竞争与协作，但忽视了每个个体之间的竞争与协作，也会造成求解精度低，收敛速度慢的问题。


技术实现要素：

3.鉴于上述问题，本公开提供了一种确定行驶路径的方法、装置、电子设备、存储介质和程序产品，能够在求解车辆路径路径问题的时候同时考虑种群间的竞争与协作和个体间的竞争与协作，从而达到求解精度高，收敛速度快的效果。
4.根据本公开的一个方面，提供了一种确定行驶路径的方法，包括：获取用户信息，对所述用户信息进行随机编码，形成初始种群集合，初始种群集合包括多个个体信息子集合，每个个体信息子集合包括多个用户当前信息和对应路径信息；针对每个个体信息子集合，根据所述用户当前信息和对应的路径信息，计算所述个体信息子集合的适应度，得到多个适应度；根据优化参数与适应度对所述多个个体信息子集合进行分层；根据多个个体信息子集合所处的层级，对所述个体信息子集合中的对应路径信息进行优化，得到优化的对应路径信息；以及根据所述优化的对应路径信息，确定行驶路径。
5.根据本公开的实施例，该方法还包括：设置优化参数，所述优化参数包括分层比例、传递比例和迭代次数。
6.根据本公开的实施例，对所述用户信息进行随机编码，形成初始种群集合包括：根据预定行驶条件，设置至少一个约束函数；基于所述约束函数和所述用户信息，得到满足所述约束函数的多个个体信息子集合。
7.根据本公开的实施例，针对每个个体信息子集合，根据所述用户当前信息和对应的路径信息，计算所述个体信息子集合的适应度，得到多个适应度包括：针对所述用户当前信息进行解码处理，得到第一用户信息，第一用户信息包括用户标识与用户位置坐标；基于行驶路径优化目标，设置适应度函数；基于每个个体信息子集合中的每个第一用户信息与适应度函数计算所述每一个体信息子集合的适应度，得到多个适应度。
8.根据本公开的实施例，根据优化参数与适应度对所述多个个体信息子集合进行分层包括：根据排序函数，对所述多个适应度进行排序；依据所述分层比例，将所述排序后的适应度划分为多个层；依据所述分层后的适应度，对所述适应度对应的所述多个个体信息子集合分为多个层。
9.根据本公开的实施例，多个层自下而上包括探索层、第一传递层、第二传递层和开采层，所述探索层包括第一分层比例的所述个体信息子集合，第一传递层包括第二分层比例的所述个体信息子集合，第二传递层包括第三分层比例的所述个体信息子集合和开采层包括第四分层比例的所述个体信息子集合。
10.根据本公开的实施例，根据多个个体信息子集合所处的层级，对所述个体信息子集合中的对应路径信息进行优化，得到优化的对应路径信息包括：根据针对所述多个层级分别确定的优化策略，对处于各个层级的个体信息子集合分别进行优化，得到经优化的多个个体信息子集合；根据适应度函数，计算所述经优化的多个个体信息子集合的适应度；根据所述适应度，计算所述经优化的个体信息子集合的传递概率，所述传递概率用于表示所述经优化的个体信息子集合传递至上一层级的概率；对所述传递概率进行排序；依据所述排序后的传递概率与传递比例，对多个层的所述多个经优化的个体信息子集合进行跨层级传递，得到优化的对应路径信息。
11.根据本公开的实施例，优化策略包括以下中的至少一个：第一优化策略，包括对所述探索层与第一传递层采用第一优化算子，对所述第二传递层与开采层采用第二优化算子，所述第一优化算子在优化过程中对所述对应的路径信息的优化幅度大于第二优化算子在优化过程中对所述对应的路径信息的优化幅度；第二优化策略，包括针对已经执行过第一优化策略的第二传递层与开采层中的多个个体信息子集合中的对应路径信息，利用第一适应度对应的个体信息子集合中的对应路径信息对优良的个体信息子集合中的对应路径信息进行加速，以及利用插入策略优化劣汰的个体信息子集合中的对应路径信息，所述第一适应度包括位于排序后首位的适应度。
12.根据本公开的实施例，利用第一适应度对应的个体信息子集合中的对应路径信息对优良的个体信息子集合中的对应路径信息进行加速包括：第二传递层使用当代第一适用度对应的个体信息子集合中的对应路径信息进行加速操作，开采层使用全局的第一适用度对应的个体信息子集合中的对应路径信息进行加速操作，其中所述加速操作包括：利用第一适用度对应的个体信息子集合中的对应路径信息，采用优化算子对所述待优化的对应路径信息进行优化的操作。
13.根据本公开的实施例，利用插入策略优化劣汰的个体信息子集合中的对应路径信息包括：去掉所述劣汰的第一优化个体信息子集合中的对应路径信息内部的至少一个元素，得到第一个体信息子集合中的对应路径信息；针对去掉的一个元素，分别插入所述第一个体信息子集合中的对应路径信息内的不同位置；依据所述适应度函数，分别计算所述插入不同位置后的第一个体信息子集合中的对应路径信息对应的适应度；确定与第一适应度对应的所述插入位置为所述元素的插入位置；直至全部所述去掉的元素都插入完毕，得到优化的个体信息子集合中的对应路径信息。
14.根据本公开的实施例，根据所述优化的对应路径信息，确定行驶路径包括：响应于确定满足结束条件，确定第一适应度对应的个体信息子集和中的对应路径信息为行驶路径，结束条件包括确定当前迭代次数等于所述迭代次数。
15.本公开的另一方面提供了一种确定行驶路径的装置，包括：获取模块，用于获取用户信息；编码模块，用于对所述用户信息进行随机编码，形成初始种群集合，初始种群集合包括多个个体信息子集合，每个个体信息子集合包括多个用户当前信息和对应路径信息；
计算模块，用于针对每个个体信息子集合，根据所述用户当前信息和对应的路径信息，计算所述个体信息子集合的适应度，得到多个适应度；分层模块，用于根据优化参数与适应度对所述多个个体信息子集合进行分层；优化模块，用于根据多个个体信息子集合所处的层级，对所述个体信息子集合中的对应路径信息进行优化，得到优化的对应路径信息；以及确定模块，用于根据所述优化的对应路径信息，确定行驶路径。
16.本公开的另一方面提供了一种电子设备，包括：一个或多个处理器；存储器，用于存储一个或多个程序，其中，当所述一个或多个程序被所述一个或多个处理器执行时，使得一个或多个处理器执行上述确定行驶路径的方法。
17.本公开的另一方面还提供了一种计算机可读存储介质，其上存储有可执行指令，该指令被处理器执行时使处理器执行上述确定行驶路径的方法。
18.本公开的另一方面还提供了一种计算机程序产品，包括计算机程序，该计算机程序被处理器执行时实现上述确定行驶路径的方法。
附图说明
19.通过以下参照附图对本公开实施例的描述，本公开的上述内容以及其他目的、特征和优点将更为清楚，在附图中：
20.图1示意性示出了根据本公开实施例的确定行驶路径的方法、装置、电子设备、存储介质和程序产品的应用场景图；
21.图2示意性示出了根据本公开实施例的行驶路径方法的流程图；
22.图3示意性示出了根据本公开实施例采用的分层方法示意图；
23.图4示意性示出了根据本公开另一实施例的行驶路径方法的流程图；
24.图5示意性示出了根据本公开实施例采用的加速操作示意图；
25.图6示意性示出了根据本公开实施例采用的插入策略示意图；
26.图7示意性示出了根据本公开实施例的确定行驶路径装置的结构框图；以及
27.图8示意性示出了根据本公开实施例的适于实现确定行驶路径方法的电子设备的方框图。
具体实施方式
28.以下，将参照附图来描述本公开的实施例。但是应该理解，这些描述只是示例性的，而并非要限制本公开的范围。在下面的详细描述中，为便于解释，阐述了许多具体的细节以提供对本公开实施例的全面理解。然而，明显地，一个或多个实施例在没有这些具体细节的情况下也可以被实施。此外，在以下说明中，省略了对公知结构和技术的描述，以避免不必要地混淆本公开的概念。
29.在此使用的术语仅仅是为了描述具体实施例，而并非意在限制本公开。在此使用的术语“包括”、“包含”等表明了所述特征、步骤、操作和/或部件的存在，但是并不排除存在或添加一个或多个其他特征、步骤、操作或部件。
30.在此使用的所有术语(包括技术和科学术语)具有本领域技术人员通常所理解的含义，除非另外定义。应注意，这里使用的术语应解释为具有与本说明书的上下文相一致的含义，而不应以理想化或过于刻板的方式来解释。
31.在使用类似于“a、b和c等中至少一个”这样的表述的情况下，一般来说应该按照本领域技术人员通常理解该表述的含义来予以解释(例如，“具有a、b和c中至少一个的系统”应包括但不限于单独具有a、单独具有b、单独具有c、具有a和b、具有a和c、具有b和c、和/或具有a、b、c的系统等)。
32.本公开的实施例提供了一种确定行驶路径方法，该方法包括对所述用户信息进行随机编码，形成初始种群集合，初始种群集合包括多个个体信息子集合，每个个体信息子集合包括多个用户当前信息和对应路径信息；针对每个个体信息子集合，根据所述用户当前信息和对应的路径信息，计算所述个体信息子集合的适应度，得到多个适应度；根据优化参数与适应度对所述多个个体信息子集合进行分层；根据多个个体信息子集合所处的层级，对所述个体信息子集合中的对应路径信息进行优化，得到优化的对应路径信息；以及根据所述优化的对应路径信息，确定行驶路径。
33.图1示意性示出了根据本公开实施例的确定行驶路径的应用场景图。
34.如图1所示，根据该实施例的应用场景100可以包括终端设备101、102、103，网络104和服务器105。网络104用以在终端设备101、102、103和服务器105之间提供通信链路的介质。网络104可以包括各种连接类型，例如有线、无线通信链路或者光纤电缆等等。
35.用户可以使用终端设备101、102、103通过网络104与服务器105交互，以接收或发送消息等。终端设备101、102、103上可以安装有各种通讯客户端应用，例如购物类应用、网页浏览器应用、搜索类应用、即时通信工具、邮箱客户端、社交平台软件等(仅为示例)。
36.终端设备101、102、103可以是具有显示屏并且支持网页浏览的各种电子设备，包括但不限于智能手机、平板电脑、膝上型便携计算机和台式计算机等等。
37.服务器105可以是提供各种服务的服务器，例如对用户利用终端设备101、102、103所浏览的网站提供支持的后台管理服务器(仅为示例)。后台管理服务器可以对接收到的用户请求等数据进行分析等处理，并将处理结果(例如根据用户请求获取或生成的网页、信息、或数据等)反馈给终端设备。
38.需要说明的是，本公开实施例所提供的确定行驶路径的方法一般可以由服务器105执行。相应地，本公开实施例所提供的确定行驶路径的装置一般可以设置于服务器105中。本公开实施例所提供的确定行驶路径的方法也可以由不同于服务器105且能够与终端设备101、102、103和/或服务器105通信的服务器或服务器集群执行。相应地，本公开实施例所提供的确定行驶路径的装置也可以设置于不同于服务器105且能够与终端设备101、102、103和/或服务器105通信的服务器或服务器集群中。
39.应该理解，图1中的终端设备、网络和服务器的数目仅仅是示意性的。根据实现需要，可以具有任意数目的终端设备、网络和服务器。
40.以下将基于图1描述的场景，通过图2～图6对公开实施例的确定行驶路径的方法进行详细描述。
41.图2示意性示出了根据本公开实施例的确定行驶路径方法的流程图。
42.如图2所示，该实施例的确定行驶路径方法包括操作s210～操作s260。
43.在操作s210，获取用户信息。
44.根据本公开实施例，根据业务类型来确定用户信息。例如，在应用于确定行驶路径的问题时，用户信息可以包括以下中的至少一个：用户当前位置、用户的服务时间窗、用户
的货物类型、用户的货物重量。
45.在操作s220，对用户信息进行随机编码，形成初始种群集合，初始种群集合包括多个个体信息子集合，每个个体信息子集合包括多个用户当前信息和对应路径信息。
46.根据本公开实施例，对所有用户进行随机编码，编码之后每个用户对应一个整数标识xi，xi∈(1，2，3，
…
，n)，用户与用户信息与该用户的整数标识相关联。针对用户的整数标识，随机生成多个个体信息子集合(xi，xi＝(x1，x2，x3，
…
，xn))，每个个体信息子集合包含多个用户与对应的路径信息。例如，个体信息子集合xi＝(x1，x2，x3)表示此路径包括三个用户(x1、x2和x3)和对应路径信息(x1→
x2→
x3)。所有随机生成的个体信息子集合形成初始种群集合(x，x＝(x1，x2，x3，
…
，xn))。例如，在5个用户的示例中，将用户随机编码为1、2、3、4和5。针对5个用户，可以随机生成多个个体信息子集合。例如可以为x1＝(1，2，3)、x2＝(5，2，3)和x3＝(1，4，3)等，所有随机生成的个体信息子集合形成初始种群集合x＝(x1，x2，x3，
…
，xn)。
47.在操作s230，针对每个个体信息子集合，根据用户当前信息和对应的路径信息，计算个体信息子集合的适应度，得到多个适应度。
48.根据本公开实施例，根据业务的优化目标确定适应度。适用度是评价每个个体信息子集合优劣程度的指标。例如，在求解最短行驶路径的问题中，可以选择路程作为适应度。依据每个个体信息子集合包含的用户的当前信息和对应的路径信息，计算每个个体信息子集合对应的路程，该路程称为该个体信息子集合的适应度。用户的当前信息可以是用户的当前位置。
49.在操作s240，根据优化参数与适应度对多个个体信息子集合进行分层。
50.根据本公开实施例，根据排序函数，对多个适应度进行排序；依据分层比例，将排序后的适应度划分为多个层；依据分层后的适应度，对适应度对应的多个个体信息子集合分为多个层。
51.根据排序函数，对每个个体信息子集合计算所得的适应度进行排序，其中，排序函数包括：升序和降序。根据分层比例将排序后的适应度分为多个层；再根据分层后每个适应度在的层，将每个适应度对应的个体信息子集合也分入该层。分层比例包含多个不同的百分数，每个百分数表示每个层包含个体信息子集合的个数占种群集合个体信息子集合个数的比例，多个百分数相加之和为1。分层比例包含百分数的个数就是将初始种群集合分的层数。例如，分层比例为(50％，25％，15％，10％)，因为其中包含了四个百分数，所以是将初始种群集合中的个体信息子集合分为四个层，每个层分别占比50％、25％、15％和10％。
52.在操作s250，根据多个个体信息子集合所处的层级，对个体信息子集合中的对应路径信息进行优化，得到优化的对应路径信息。
53.根据本公开实施例，针对初始种群集合分出的每个层，分别设置用于优化上述每个层包含的个体信息子集合的优化算子。依据对每层分别设置的优化算子，对每个层包含的个体信息子集合中的对应路径信息进行优化，得到经优化的对应路径信息。
54.计算上述经优化的对应路径信息的适应度，并将计算所得的适应度排序。依据传递比例和排序后的适应度，选择多个经优化的对应路径信息传递至上一层进行优化，经过优化得到优化的对应路径信息。传递比例是每个层中可以传递至上一层的个体信息子集合个数占该层个体信息子集合总数的比例。
55.优化算子是用于在业务中求最优解的方法，具体可以包括：逆转算子和随机两点换位算子等。以行驶路径问题为示例，逆转算子优化的步骤包括：在对应的路径信息中任意选择两个元素，对所选择的两个元素中间的元素进行倒序排列(优化前的原排列为正序排列)，再将所选择的两个元素的位置互换，最终得到优化后的对应的路径信息。随机两点换位算子优化的步骤包括：在对应的路径信息中任意选择两个元素，将所选择的两个元素的位置互换，得到优化后的对应的路径信息。
56.在操作s260，根据优化的对应路径信息，确定行驶路径。
57.根据本公开实施例，计算优化的对应路径信息的适应度，并对所计算的适应度排序。确定第一适应度对应的对应路径信息为行驶路径。第一适应度是位于排序后首位的适应度。例如，如果行驶路径的优化目标为路程最短，适应度按照自小至大排列，则第一适应度为所有适应度排序后位于首位的适应度(最小的适应度)。
58.图3示意性示出了根据本公开实施例分层方法示意图。
59.根据另一个实施例，如图3所示，在四个层的示例中，将初始种群集合内的个体信息子集合自下而上分为探索层340、第一传递层330、第二传递层320和开采层310。以分层比例为(50％，25％，15％，10％)为例，该分层比例表示探索层340包含初始种群集合50％的个体信息子集合，第一传递层330包含初始种群集合25％的个体信息子集合，第二传递层320包含初始种群集合15％的个体信息子集合；开采层310包含初始种群集合10％的个体信息子集合。
60.假设适应度值越小代表路径越优，可以对适应度进行自小至大排序。针对排序后的适应度，将位于后50％的适应度划分到探索层340中，进而将位于后50％适应度对应的个体信息子集合也划分为探索层340中；将位于前25％至前50％的适应度划分到第一传递层330中，进而将位于前25％至前50％适应度对应的个体信息子集合也划分为第一传递层330中；将位于前10％至前25％的适应度划分到第二传递层320中，进而将位于前10％至前25％适应度对应的个体信息子集合也划分为第二传递层320中；将位于前10％的适应度划分到开采层310中，进而将位于前10％适应度对应的个体信息子集合也划分为开采层310中。
61.本领域技术人员可以理解，以上实施例仅作为示例，本公开具体分层方法所分的层数并不局限于此。
62.根据另一实施例，前述对用户信息进行随机编码，形成初始种群集合可以包括如下操作。
63.根据预定行驶条件，设置至少一个约束函数；基于约束函数和用户信息，得到满足约束函数的多个个体信息子集合。
64.行驶条件包括车辆在行驶过程中受到的制约条件。例如，行驶条件中车辆在行驶过程中的约束条件可以包括车辆行驶的最长路程、车辆在行驶中的最大速度、用户的服务时间窗要求和车辆可以装配的最大重量等。根据行驶条件分别设置约束函数。利用约束函数，分别验证每个随机生成的个体信息子集合是否满足行驶条件，满足行驶条件的个体信息子集合形成初始种群集合。
65.根据另一实施例，前述针对每个个体信息子集合，根据用户当前信息和对应的路径信息，计算个体信息子集合的适应度，得到多个适应度可以包括如下操作。
66.针对用户当前信息进行解码处理，得到第一用户信息，第一用户信息包括用户标
识与用户位置坐标。基于行驶路径的优化目标，设置适应度函数；基于每个个体信息子集合中的每个第一用户信息与适应度函数计算每一个体信息子集合的适应度，得到多个适应度。例如，以行驶路径优化目标为行驶路径最短为示例，选择路程作为适应度。设置车辆出发位置为坐标原点，根据每一个用户信息中的实时位置与车辆出发位置的关系确定该用户的位置坐标，并将该坐标与该用户编码后形成的整数标识相关联，保证一个用户的整数标识对应一个坐标。依据用户坐标和对应的路径信息，确定计算路程的函数，该函数称为适应度函数。基于适应度函数，针对每个个体信息子集合计算其适应度。
67.通过结合金字塔演化算法与智能优化算法对由用户组成的个体信息子集合中对应的路径信息进行优化，克服了在求解行驶路径时不能同时考虑个体之间和种群之间的竞争与协作的问题，从而达到求解精度高，收敛速度快的效果。
68.图4示意性示出了根据本公开另一实施例的确定行驶路径的流程图。
69.如图4所示，该实施例的确定行驶路径方法包括操作s410～操作s480。
70.在操作s410，设置优化参数，优化参数包括分层比例、传递比例和迭代次数。
71.根据本公开实施例，在确定行驶路径之前，设置优化参数。优化参数可以包括初始种群集合的规模、分层比例、传递比例、车辆最大载重、车辆速度和迭代次数等。
72.在操作s420，对用户信息进行随机编码，形成初始种群集合，初始种群集合包括多个个体信息子集合，每个个体信息子集合包括多个用户当前信息和对应路径信息。
73.该操作s420可以通过与前文操作s220描述的方法类似的方法，来进行随机编码形成初始种群集合。在此不再赘述。
74.在操作s430，针对每个个体信息子集合，根据用户当前信息和对应的路径信息，计算个体信息子集合的适应度，得到多个适应度。
75.该操作s430可以通过与前文操作s230描述的方法类似的方法，来计算个体信息子集合的适应度。在此不再赘述。
76.在操作s440，根据优化参数与适应度对多个个体信息子集合进行分层。
77.该操作s440可以通过与前文操作s240描述的方法类似的方法，来对多个个体信息子集合进行分层。在此不再赘述。
78.在操作s450，根据针对多个层级分别确定的优化策略，对处于各个层级的个体信息子集合分别进行优化，得到经优化的多个个体信息子集合。
79.根据本公开实施例，在四个层的示例中，针对探索层、第一传递层、第二传递层和开采层分别制定优化策略。依据优化策略对以上四个层内的个体信息子集合中的对应路径信息进行优化，优化后得到经优化的对应路径信息。优化策略包括第一优化策略和第二优化策略的至少一种。
80.根据另一个实施例，第一优化策略包括对探索层与第一传递层采用第一优化算子进行优化，对第二传递层与开采层采用第二优化算子进行优化。需要说明的是，在设置第一优化策略时，第一扰动幅度大于第二扰动幅度。第一扰动幅度为第一优化算子在执行优化操作的过程中对对应的路径信息的优化幅度，第二扰动幅度为第二优化算子在执行优化操作的过程中对对应的路径信息的优化幅度。例如，针对探索层与第一传递层采用逆转算子优化，针对第二传递层与开采层采用随机两点换位算子优化。
81.第二优化策略包括使用当代第一适用度对应的个体信息子集合中的对应路径信
息，对已经执行过第一优化策略的第二传递层中对应的路径信息进行加速操作；使用全局第一适用度对应的个体信息子集合中的对应路径信息，对已经执行过第一优化策略的开采层中对应的路径信息进行加速操作；利用插入策略优化劣汰的个体信息子集合中的对应路径信息。第一适应度包括位于排序后首位的适应度。例如，如果行驶路径的优化目标为路程最短，适应度按照自小至大排列，则第一适应度为所有适应度排序后位于首位的适应度(最小的适应度)。
82.在操作s460，依据传递概率与传递比例，对多个层的多个经优化的个体信息子集合进行跨层级传递，得到优化的对应路径信息。
83.根据本公开实施例，计算步骤s450得到的经优化的多个个体信息子集合的适应度。根据计算所得的适应度，计算经优化的个体信息子集合的传递概率。传递概率表示经优化的个体信息子集合传递至上一层级的概率。例如，传递概率的计算公式为第一数值与第二数值的商，其中第一数值为当前个体信息子集合对应的适应度，第二数值为当前个体信息子集合所处的层级的适应度总和。依据该传递概率计算公式，求得多个经优化的个体信息子集合的传递概率。
84.对计算所得的多个传递概率进行排序。依据排序后的传递概率与传递比例，将多个层的多个个体信息子集合进行跨层级传递，得到优化的对应路径信息。例如，在四个层的示例中，传递比例为(50％，20％，10％)，前述传递比例表示将在探索层内选择50％的个体信息子集合传递至第一传递层，所选择的50％的个体信息子集合为传递概率排序位于前50％的对应的个体信息子集合；将在第一传递层内选择20％的个体信息子集合传递至第二传递层，所选择的20％的个体信息子集合为传递概率排序位于前50％的对应的个体信息子集合；将在第二传递层内选择10％的个体信息子集合传递至开采层，所选择的100％的个体信息子集合为传递概率排序位于前50％的对应的个体信息子集合。按照层级的优化策略，对跨层级传递后形成的新层级中的个体信息子集合再进行优化，经过优化得到优化的对应路径信息。
85.在操作s470，判断是否满足结束条件。
86.若不满足结束条件，返回至操作s430。
87.若满足结束条件，则执行操作s480，根据优化的对应路径信息，确定行驶路径。
88.根据本公开实施例，结束条件可以为以下中的至少一个，当前迭代次数等于优化参数中设置的迭代次数和此时的优化结果收敛。例如，以当前迭代次数等于优化参数中设置的迭代次数为例，优化参数中设置迭代次数为500，如果目前已执行的迭代次数小于500，则返回至操作s430步骤继续执行迭代过程，如果目前已执行的迭代次数为500次，则执行操作s480。
89.在满足结束条件时，将第一适应度对应的个体信息子集和中的对应的路径信息确定为行驶路径。第一适应度是位于排序后首位的适应度。例如，如果行驶路径的优化目标为路程最短，适应度按照自小至大排列，则第一适应度为所有适应度排序后位于首位的适应度(最小的适应度)。
90.图5示意性示出了根据本公开实施例采用的加速操作示意图。
91.根据另一个实施例，如图5所示，510表示待优化的个体信息子集合中的对应路径信息，520表示第一适应度对应的个体信息子集合中的对应路径信息。为了简便，下文中以
路径信息代表个体信息子集合中的对应路径信息。例如，优化的起始位为待优化的路径信息510的元素1所在的位置，也就是第一适应度对应的优化路径信息内元素2所在的位置。优化的结束位为待优化的路径信息510的元素3所在的位置，也就是第一适应度对应的路径信息内元素1所在的位置。
92.从起始位开始优化操作，将待优化的路径信息的起始位元素与第一适应度对应的路径信息的起始位元素交换。例如，将待优化的路径信息510的元素1与第一适应度对应的优化的路径信息520的元素2交换，元素交换之后待优化的路径信息变为(2，2，3，4，5)，第一适应度对应的路径信息变为(5，1，1，4，3)。确定路径信息中原存在的与换入元素相同的元素，将该元素换为该路径信息用于交换的元素。例如，将待优化的路径信息510中原来的元素2变为元素1，元素改变之后待优化的路径信息510变为第一优化路径信息530(1，2，3，4，5)，第一适应度对应的路径信息520变为第一优化的第一适应度对应的路径信息540(5，1，2，4，3)。
93.采用与以上起始位元素操作相同的操作，对待优化的路径信息510中剩余的元素进行优化。经过优化后，第一优化的路径信息530变为第二优化的路径信息550(1，3，2，4，5)，第一优化的第一适应度对应的路径信息540变为第二优化的第一适应度对应的路径信息560(5，1，3，4，2)。同理，经过再优化后，第二优化的路径信息550变为经优化的路径信息570(1，3，2，4，5)。
94.本领域技术人员可以理解，以上实施例仅作为示例，本公开加速的具体路径并不局限于此。
95.图6示意性示出了根据本公开实施例采用的插入策略示意图。
96.根据另一个实施例，插入策略包括：去掉劣汰的第一优化个体信息子集合中的对应路径信息内部的至少一个元素，得到第一个体信息子集合中的对应路径信息；针对去掉的一个元素，分别插入第一个体信息子集合中的对应路径信息内的不同位置；依据适应度函数，分别计算插入不同位置后的第一个体信息子集合中的对应路径信息对应的适应度；确定与第一适应度对应的插入位置为元素的插入位置；直至全部去掉的元素都插入完毕，得到优化的个体信息子集合中的对应路径信息。
97.如图6所示，610表示劣汰的路径信息，去掉路径信息610中的元素5和元素6，路径信息610变为路径信息620(3，2，1)。
98.首先，针对元素5，将元素5分别插入路径信息620(3，2，1)中不同位置，也就是元素5前后分别插入路径信息630中每一个虚框位置，并分别计算元素5插入每个位置后形成的路径信息的适应度，也就是插入路径信息630中的每个虚框位置都会形成一个新的路径信息，计算所形成的所有新的路径信息的适应度。如果在元素5在插入元素3和元素2之间(如路径信息640)时，所计算的适应度为第一适应度，那么此时确定640表示第一优化路径信息。同理，按照以上操作将元素6插入第一优化的路径信息640中，即可得到经优化的路径信息650(3，5，2，6，1)。
99.本领域技术人员可以理解，以上实施例仅作为示例，本公开使用插入策略的具体路径并不局限于此。
100.基于上述确定行驶路径方法，本公开还提供了一种确定行驶路径装置。以下将结合图7对该装置进行详细描述。
101.图7示意性示出了根据本公开实施例的确定行驶路径装置的结构框图。
102.如图7所示，该实施例的确定实行路径装置700包括获取模块710、编码模块720、计算模块730、分层模块740、优化模块750及确定模块760。
103.获取模块710用于获取用户信息。在一实施例中，获取模块710可以用于执行前文描述的操作s210，在此不再赘述。
104.根据本公开的实施例，确定行驶路径700还包括配置优化参数模块，优化参数包括分层比例、传递比例和迭代次数。
105.编码模块720用于对用户信息进行随机编码，形成初始种群集合，初始种群集合包括多个个体信息子集合，每个个体信息子集合包括多个用户当前信息和对应路径信息。在一实施例中，编码模块720可以用于执行前文描述的操作s220，在此不再赘述。
106.根据本公开的实施例，当前确定行驶路径编码模块720还用于：根据预定行驶条件，设置至少一个约束函数；基于约束函数和用户信息，得到满足约束函数的多个个体信息子集合。
107.计算模块730用于针对每个个体信息子集合，根据用户当前信息和对应的路径信息，计算个体信息子集合的适应度，得到多个适应度。在一实施例中，计算模块730可以用于执行前文描述的操作s230，在此不再赘述。
108.根据本公开的实施例，当前确定行驶路径计算模块730还用于：针对用户当前信息进行解码处理，得到第一用户信息，第一用户信息包括用户标识与用户位置坐标；基于行驶路径优化目标，设置适应度函数；基于每个个体信息子集合中的每个第一用户信息与适应度函数计算每一个体信息子集合的适应度，得到多个适应度。
109.分层模块740用于根据优化参数与适应度对多个个体信息子集合进行分层。在一实施例中，分层模块740可以用于执行前文描述的操作s240，在此不再赘述。
110.根据本公开的实施例，当前确定行驶路径分层模块740还用于：根据排序函数，对多个适应度进行排序；依据分层比例，将排序后的适应度划分为多个层；依据分层后的适应度，对适应度对应的多个个体信息子集合分为多个层。
111.优化模块750用于根据多个个体信息子集合所处的层级，对个体信息子集合中的对应路径信息进行优化，得到优化的对应路径信息，在一实施例中，优化模块750可以用于执行前文描述的操作s250，在此不再赘述。
112.根据本公开的实施例，当前确定行驶路径优化模块750还用于：根据针对多个层级分别确定的优化策略，对处于各个层级的个体信息子集合分别进行优化，得到经优化的多个个体信息子集合；根据适应度函数，计算经优化的多个个体信息子集合的适应度；根据适应度，计算经优化的个体信息子集合的传递概率，传递概率用于表示经优化的个体信息子集合传递至上一层级的概率；对传递概率进行排序；依据排序后的传递概率与传递比例，对多个层的多个经优化的个体信息子集合进行跨层级传递，得到优化的对应路径信息。
113.确定模块760用于根据对应的对应路径信息，确定行驶路径。在一实施例中，确定模块760可以用于执行前文描述的操作s260，在此不再赘述。
114.根据本公开的实施例，当前确定行驶路径确定模块760还用于：响应于确定满足结束条件，确定第一适应度对应的个体信息子集和中的对应路径信息为行驶路径，结束条件包括确定当前迭代次数等于迭代次数。
115.根据本公开的实施例，获取模块710、编码模块720、计算模块730、分层模块740、优化模块750和确定模块760中的任意多个模块可以合并在一个模块中实现，或者其中的任意一个模块可以被拆分成多个模块。或者，这些模块中的一个或多个模块的至少部分功能可以与其他模块的至少部分功能相结合，并在一个模块中实现。根据本公开的实施例，获取模块710、编码模块720、计算模块730、分层模块740、优化模块750和确定模块760中的至少一个可以至少被部分地实现为硬件电路，例如现场可编程门阵列(fpga)、可编程逻辑阵列(pla)、片上系统、基板上的系统、封装上的系统、专用集成电路(asic)，或可以通过对电路进行集成或封装的任何其他的合理方式等硬件或固件来实现，或以软件、硬件以及固件三种实现方式中任意一种或以其中任意几种的适当组合来实现。或者，获取模块710、编码模块720、计算模块730、分层模块740、优化模块750和确定模块760中的至少一个可以至少被部分地实现为计算机程序模块，当该计算机程序模块被运行时，可以执行相应的功能。
116.图8示意性示出了根据本公开实施例的适于实现确定行驶路径方法的电子设备的方框图。
117.如图8所示，根据本公开实施例的电子设备800包括处理器801，其可以根据存储在只读存储器(rom)802中的程序或者从存储部分808加载到随机访问存储器(ram)803中的程序而执行各种适当的动作和处理。处理器801例如可以包括通用微处理器(例如cpu)、指令集处理器和/或相关芯片组和/或专用微处理器(例如，专用集成电路(asic))等等。处理器801还可以包括用于缓存用途的板载存储器。处理器801可以包括用于执行根据本公开实施例的方法流程的不同动作的单一处理单元或者是多个处理单元。
118.在ram 803中，存储有电子设备800操作所需的各种程序和数据。处理器801、rom 802以及ram 803通过总线804彼此相连。处理器801通过执行rom 802和/或ram 803中的程序来执行根据本公开实施例的方法流程的各种操作。需要注意，所述程序也可以存储在除rom 802和ram 803以外的一个或多个存储器中。处理器801也可以通过执行存储在所述一个或多个存储器中的程序来执行根据本公开实施例的方法流程的各种操作。
119.根据本公开的实施例，电子设备800还可以包括输入/输出(i/o)接口805，输入/输出(i/o)接口805也连接至总线804。电子设备800还可以包括连接至i/o接口805的以下部件中的一项或多项：包括键盘、鼠标等的输入部分806；包括诸如阴极射线管(crt)、液晶显示器(lcd)等以及扬声器等的输出部分807；包括硬盘等的存储部分808；以及包括诸如lan卡、调制解调器等的网络接口卡的通信部分809。通信部分809经由诸如因特网的网络执行通信处理。驱动器810也根据需要连接至i/o接口805。可拆卸介质811，诸如磁盘、光盘、磁光盘、半导体存储器等等，根据需要安装在驱动器810上，以便于从其上读出的计算机程序根据需要被安装入存储部分808。
120.本公开还提供了一种计算机可读存储介质，该计算机可读存储介质可以是上述实施例中描述的设备/装置/系统中所包含的；也可以是单独存在，而未装配入该设备/装置/系统中。上述计算机可读存储介质承载有一个或者多个程序，当上述一个或者多个程序被执行时，实现根据本公开实施例的方法。
121.根据本公开的实施例，计算机可读存储介质可以是非易失性的计算机可读存储介质，例如可以包括但不限于：便携式计算机磁盘、硬盘、随机访问存储器(ram)、只读存储器(rom)、可擦式可编程只读存储器(eprom或闪存)、便携式紧凑磁盘只读存储器(cd-rom)、光
存储器件、磁存储器件、或者上述的任意合适的组合。在本公开中，计算机可读存储介质可以是任何包含或存储程序的有形介质，该程序可以被指令执行系统、装置或者器件使用或者与其结合使用。例如，根据本公开的实施例，计算机可读存储介质可以包括上文描述的rom 802和/或ram 803和/或rom 802和ram 803以外的一个或多个存储器。
122.本公开的实施例还包括一种计算机程序产品，其包括计算机程序，该计算机程序包含用于执行流程图所示的方法的程序代码。当计算机程序产品在计算机系统中运行时，该程序代码用于使计算机系统实现本公开实施例所提供的物品推荐方法。
123.在该计算机程序被处理器801执行时执行本公开实施例的系统/装置中限定的上述功能。根据本公开的实施例，上文描述的系统、装置、模块、单元等可以通过计算机程序模块来实现。
124.在一种实施例中，该计算机程序可以依托于光存储器件、磁存储器件等有形存储介质。在另一种实施例中，该计算机程序也可以在网络介质上以信号的形式进行传输、分发，并通过通信部分809被下载和安装，和/或从可拆卸介质811被安装。该计算机程序包含的程序代码可以用任何适当的网络介质传输，包括但不限于：无线、有线等等，或者上述的任意合适的组合。
125.在这样的实施例中，该计算机程序可以通过通信部分809从网络上被下载和安装，和/或从可拆卸介质811被安装。在该计算机程序被处理器801执行时，执行本公开实施例的系统中限定的上述功能。根据本公开的实施例，上文描述的系统、设备、装置、模块、单元等可以通过计算机程序模块来实现。
126.根据本公开的实施例，可以以一种或多种程序设计语言的任意组合来编写用于执行本公开实施例提供的计算机程序的程序代码，具体地，可以利用高级过程和/或面向对象的编程语言、和/或汇编/机器语言来实施这些计算程序。程序设计语言包括但不限于诸如java，c++，python，“c”语言或类似的程序设计语言。程序代码可以完全地在用户计算设备上执行、部分地在用户设备上执行、部分在远程计算设备上执行、或者完全在远程计算设备或服务器上执行。在涉及远程计算设备的情形中，远程计算设备可以通过任意种类的网络，包括局域网(lan)或广域网(wan)，连接到用户计算设备，或者，可以连接到外部计算设备(例如利用因特网服务提供商来通过因特网连接)。
127.附图中的流程图和框图，图示了按照本公开各种实施例的系统、方法和计算机程序产品的可能实现的体系架构、功能和操作。在这点上，流程图或框图中的每个方框可以代表一个模块、程序段、或代码的一部分，上述模块、程序段、或代码的一部分包含一个或多个用于实现规定的逻辑功能的可执行指令。也应当注意，在有些作为替换的实现中，方框中所标注的功能也可以以不同于附图中所标注的顺序发生。例如，两个接连地表示的方框实际上可以基本并行地执行，它们有时也可以按相反的顺序执行，这依所涉及的功能而定。也要注意的是，框图或流程图中的每个方框、以及框图或流程图中的方框的组合，可以用执行规定的功能或操作的专用的基于硬件的系统来实现，或者可以用专用硬件与计算机指令的组合来实现。
128.本领域技术人员可以理解，本公开的各个实施例和/或权利要求中记载的特征可以进行多种组合或/或结合，即使这样的组合或结合没有明确记载于本公开中。特别地，在不脱离本公开精神和教导的情况下，本公开的各个实施例和/或权利要求中记载的特征可
以进行多种组合和/或结合。所有这些组合和/或结合均落入本公开的范围。
129.以上对本公开的实施例进行了描述。但是，这些实施例仅仅是为了说明的目的，而并非为了限制本公开的范围。尽管在以上分别描述了各实施例，但是这并不意味着各个实施例中的措施不能有利地结合使用。本公开的范围由所附权利要求及其等同物限定。不脱离本公开的范围，本领域技术人员可以做出多种替代和修改，这些替代和修改都应落在本公开的范围之内。

技术特征：
1.一种确定行驶路径的方法，包括：获取用户信息；对所述用户信息进行随机编码，形成初始种群集合，初始种群集合包括多个个体信息子集合，每个个体信息子集合包括多个用户当前信息和对应路径信息；针对每个个体信息子集合，根据所述用户当前信息和对应的路径信息，计算所述个体信息子集合的适应度，得到多个适应度；根据优化参数与适应度对所述多个个体信息子集合进行分层；根据多个个体信息子集合所处的层级，对所述个体信息子集合中的对应路径信息进行优化，得到优化的对应路径信息；以及根据所述优化的对应路径信息，确定行驶路径。2.根据权利要求1所述的方法，还包括：设置优化参数，所述优化参数包括分层比例、传递比例和迭代次数。3.根据权利要求1所述的方法，其中，所述对所述用户信息进行随机编码，形成初始种群集合包括：根据预定行驶条件，设置至少一个约束函数；基于所述约束函数和所述用户信息，得到满足所述约束函数的多个个体信息子集合。4.根据权利要求1所述的方法，其中，所述针对每个个体信息子集合，根据所述用户当前信息和对应的路径信息，计算所述个体信息子集合的适应度，得到多个适应度包括：针对所述用户当前信息进行解码处理，得到第一用户信息，第一用户信息包括用户标识与用户位置坐标；基于行驶路径优化目标，设置适应度函数；基于每个个体信息子集合中的每个第一用户信息与适应度函数计算所述每一个体信息子集合的适应度，得到多个适应度。5.根据权利要求2所述的方法，其中，所述根据优化参数与适应度对所述多个个体信息子集合进行分层包括：根据排序函数，对所述多个适应度进行排序；依据所述分层比例，将所述排序后的适应度划分为多个层；依据所述分层后的适应度，对所述适应度对应的所述多个个体信息子集合分为多个层。6.根据权利要求5所述的方法，其中，所述多个层自下而上包括探索层、第一传递层、第二传递层和开采层，所述探索层包括第一分层比例的所述个体信息子集合，第一传递层包括第二分层比例的所述个体信息子集合，第二传递层包括第三分层比例的所述个体信息子集合和开采层包括第四分层比例的所述个体信息子集合。7.根据权利要求1-6之一所述的方法，其中，所述根据多个个体信息子集合所处的层级，对所述个体信息子集合中的对应路径信息进行优化，得到优化的对应路径信息包括：根据针对所述多个层级分别确定的优化策略，对处于各个层级的个体信息子集合分别进行优化，得到经优化的多个个体信息子集合；根据适应度函数，计算所述经优化的多个个体信息子集合的适应度；根据所述适应度，计算所述经优化的个体信息子集合的传递概率，所述传递概率用于表示所述经优化的个体信息子集合传递至上一层级的概率；
对所述传递概率进行排序；依据所述排序后的传递概率与传递比例，对多个层的所述多个经优化的个体信息子集合进行跨层级传递，得到优化的对应路径信息。8.根据权利要求7所述的方法，其中，所述优化策略包括以下中的至少一个：第一优化策略，包括对所述探索层与第一传递层采用第一优化算子，对所述第二传递层与开采层采用第二优化算子，所述第一优化算子在优化过程中对所述对应的路径信息的优化幅度大于第二优化算子在优化过程中对所述对应的路径信息的优化幅度；第二优化策略，包括针对已经执行过第一优化策略的第二传递层与开采层中的多个个体信息子集合中的对应路径信息，利用第一适应度对应的个体信息子集合中的对应路径信息对优良的个体信息子集合中的对应路径信息进行加速，以及利用插入策略优化劣汰的个体信息子集合中的对应路径信息，所述第一适应度包括位于排序后首位的适应度。9.根据权利要求8所述的方法，其中，所述利用第一适应度对应的个体信息子集合中的对应路径信息对优良的个体信息子集合中的对应路径信息进行加速包括：第二传递层使用当代第一适用度对应的个体信息子集合中的对应路径信息进行加速操作，开采层使用全局的第一适用度对应的个体信息子集合中的对应路径信息进行加速操作，其中所述加速操作包括：利用第一适用度对应的个体信息子集合中的对应路径信息，采用优化算子对所述待优化的对应路径信息进行优化的操作。10.根据权利要求8所述的方法，其中所述利用插入策略优化劣汰的个体信息子集合中的对应路径信息包括：去掉所述劣汰的第一优化个体信息子集合中的对应路径信息内部的至少一个元素，得到第一个体信息子集合中的对应路径信息；针对去掉的一个元素，分别插入所述第一个体信息子集合中的对应路径信息内的不同位置；依据所述适应度函数，分别计算所述插入不同位置后的第一个体信息子集合中的对应路径信息对应的适应度；确定与第一适应度对应的所述插入位置为所述元素的插入位置；直至全部所述去掉的元素都插入完毕，得到优化的个体信息子集合中的对应路径信息。11.根据权利要求2所述的方法，其中所述根据所述优化的对应路径信息，确定行驶路径包括：响应于确定满足结束条件，确定第一适应度对应的个体信息子集和中的对应路径信息为行驶路径，结束条件包括确定当前迭代次数等于所述迭代次数。12.一种确定行驶路径的装置，包括：获取模块，用于获取用户信息；编码模块，用于对所述用户信息进行随机编码，形成初始种群集合，初始种群集合包括多个个体信息子集合，每个个体信息子集合包括多个用户当前信息和对应路径信息；计算模块，用于针对每个个体信息子集合，根据所述用户当前信息和对应的路径信息，计算所述个体信息子集合的适应度，得到多个适应度；
分层模块，用于根据优化参数与适应度对所述多个个体信息子集合进行分层；优化模块，用于根据多个个体信息子集合所处的层级，对所述个体信息子集合中的对应路径信息进行优化，得到优化的对应路径信息；以及确定模块，用于根据所述优化的对应路径信息，确定行驶路径。13.一种电子设备，包括：一个或多个处理器；存储装置，用于存储一个或多个程序，其中，当所述一个或多个程序被所述一个或多个处理器执行时，使得所述一个或多个处理器执行根据权利要求1～11中任一项所述的方法。14.一种计算机可读存储介质，其上存储有可执行指令，该指令被处理器执行时使处理器执行根据权利要求1～11中任一项所述的方法。15.一种计算机程序产品，包括计算机程序，所述计算机程序被处理器执行时实现根据权利要求1～11中任一项所述的方法。

技术总结
本公开提供了一种确定行驶路径的方法，可以应用于计算机技术领域。该确定行驶路径的方法包括：对所述用户信息进行随机编码，形成初始种群集合，初始种群集合包括多个个体信息子集合，每个个体信息子集合包括多个用户当前信息和对应路径信息；针对每个个体信息子集合，根据所述用户当前信息和对应的路径信息，计算所述个体信息子集合的适应度，得到多个适应度；根据优化参数与适应度对所述多个个体信息子集合进行分层；根据多个个体信息子集合所处的层级，对所述个体信息子集合中的对应路径信息进行优化，得到优化的对应路径信息；以及根据所述优化的对应路径信息，确定行驶路径。本公开还提供了一种确定行驶路径的装置、设备、存储介质和程序产品。存储介质和程序产品。存储介质和程序产品。


技术研发人员：李华峰
受保护的技术使用者：中国建设银行股份有限公司
技术研发日：2021.12.07
技术公布日：2022/3/8