基于K-Means聚类和遗传算法对运输问题的优化解决方法

摘要

本发明提供了基于K‑Means聚类和遗传算法对运输问题的优化解决方法，该基于K‑Means聚类和遗传算法对运输问题的优化解决方法包括如下步骤:S1:设置参数:聚类中心种群规模N、迭代次数T、生产地数量m、销售地数量n；S2:首先通过ArcGIS Pro平台获得的地图设置m个生产地及n个销售地，利用K‑Means对销售地进行聚类；S3:初始化种群，通过智能混合算法计算费用成本矩阵C；S4:设迭代次数；S5:对种群中的个体随机成双配对，组成N/2个父本对；S6:交叉操作。本发明不同于传统的线性规划的解法，采用了K‑Means算法对数据进行聚类，K‑Means算法能够处理图像和文本特征，具有较高的稳定性和伸缩性，能够处理数值形式的数据集，聚类效果好。

说明书

技术领域

本发明涉及涉及计算机数据信息处理、地理信息系统、网络数据分析和图论技术领域，尤其是涉及基于K-Means聚类和遗传算法对运输问题的优化解决方法装置。

背景技术

近年来互联网的快速发展也逐渐带动了物流运输产业的繁荣发展，如何调配运输线路，使得完成运输任务的同时，运输成本达到最低，时间效率达到最高，运输寻优问题是人们在生产生活中不免会遇到的问题。因此，如何优化物流的运输系统和运输模式，使运输过程更加科学高效，求得使运输最优的解决方案，能够使得运输双方达到合作共赢的效果，显然对节约成本、提高效率、实现效益、促进运输业发展，同时对我国的国民和经济发展具有重要的现实意义。

运输问题作为一类特殊的线性规划问题，运用范围也极其广泛，然而传统的运输寻优方法冗杂、繁琐，并且会随着维数的增加，用传统的算法的时间复杂度和空间复杂度都会呈指数增长。例如传统上的表上作业法，求解过程比较繁琐，并且是建立在以产销平衡运输问题为前提的。但是现实生活中运输问题往往会受到诸多因素影响。运输寻优问题不仅仅与成本路线有关，同时和工作生产的时间、天气原因、气候变化、道路好坏等人为客观因素有关。而如何将各种复杂多变的现实运输场景转化为抽象的数学模型，并寻找最优的解决方案，是人们迫切需要解决的问题。

本发明通过分析常见的现实运输问题，运用K-Means算法，并结合改进后的动态遗传算法对运输问题进行两阶段处理。采用聚类、种群初始化、交叉、变异等一系列步骤来寻找运输优化方案。将从ArcGISPro平台获取费用矩阵采用遗传算法进行求解，遗传算法中的变异运用动态变异率，以加速算法收敛性。对于变异产生的染色体采用MC接受的形式，避免使算法陷入局部最优。经过K-Means聚类算法进行若干次迭代，从而计算出运输问题的优化解决方法。

为此，提出基于K-Means聚类和遗传算法对运输问题的优化解决方法。

发明内容

本发明的第一目的在于提供基于K-Means聚类和遗传算法对运输问题的优化解决方法，通过分析常见的现实运输问题，运用K-Means算法，并结合改进后的动态遗传算法对运输问题进行两阶段处理，采用聚类、种群初始化、交叉、变异等一系列步骤来寻找运输优化方案，将从ArcGISPro平台获取费用矩阵采用遗传算法进行求解，遗传算法中的变异运用动态变异率，以加速算法收敛性，对于变异产生的染色体采用MC接受的形式，避免使算法陷入局部最优，经过K-Means聚类算法进行若干次迭代，从而计算出运输问题的优化解决方法，以解决上述背景技术中提出的问题。

本发明提供基于K-Means聚类和遗传算法对运输问题的优化解决方法，该基于K-Means聚类和遗传算法对运输问题的优化解决方法包括如下步骤:

S1:设置参数:聚类中心种群规模N、迭代次数T、生产地数量m、销售地数量n；

S2:首先通过ArcGISPro平台获得的地图设置m个生产地及n个销售地，利用K-Means对销售地进行聚类；

K-Means聚类算法描述如下：

2.1)选择一些类或组，初始化各自的中心点，即随机选择K个聚类中心；

2.2)计算各销售地到各聚类中心的距离dis,其中：

S表示聚类中心的集合，表示数据集中第j个数据，表示当前聚类数；并根据计算结果将销售地归属到最近距离的聚类中心范围内；

2.3)求聚类中心的平均值，得到的结果视为新的聚类中心；

其中：

2.4)重复以上操作步骤，直到每一类的聚类中心在每次迭代后变化都不大为止，也可以多次随机初始化中心点，然后选择运行结果最好的一个所得结果最终呈现收敛特征；

S3:初始化种群；通过智能混合算法计算费用成本矩阵C，

迭代如下过程生成初始种群：

X＝{X

其中：

x

初始化过程即分配，其基本思想如下：

3.1)初始化前提需要满足非负条件和平衡条件，产生满足所有约束的种群；

3.2)首先从分配矩阵中任选一个x

随机选取一个x

其中：

x

k代表第k个数(1,2,3…k)，n代表第n列；

3.3)修改a

为止，修改后的a

b

S4:设迭代次数t＝1，其中t∈{1,2,...,T}；

S5:对种群中的个体随机成双配对，组成N/2个父本对，对每对父本执行步骤S6至S8；

S6:交叉操作，过程如下：

6.1)假设

两矩阵之间的关系为：

6.2)将生成的R矩阵分解为

其中：

R＝R

6.3)生成交叉个体

S7:对交叉个体

7.1)从双亲矩阵中随机选择交叉个体的p行和q列，建立子矩阵Y＝(y

7.2)生成新的子矩阵Y′＝(y′

供给

7.3)将子矩阵Y′＝(y′

S8:选择操作，过程如下：

8.1)设计适应度函数：

8.2)分别计算父代个体X

8.3)若

8.4)若

S9:t＝t+1，若t≤T，转至步骤S5；否则结束程序，输出最优解。

与现有技术相比，本发明的有益效果是：

1、不同于传统的线性规划的解法，采用了K-Means算法对数据进行聚类，K-Means算法能够处理图像和文本特征，具有较高的稳定性和伸缩性，能够处理数值形式的数据集，聚类效果好；

2、聚类方法使得销售地种群当中产生中心点，具体思想是通过将货物运输到中心点再向中心点附近其他销售地运送货物，该方法大大缩短了运输距离，节约成本，提高效率；

3、K-Means算法可以通过若干次迭代，计算出运输问题的优化解决方法；

4、采用遗传算法来解决并优化运输问题解决方法；

5、采用了动态交叉变异加上MC接收形式提升了算法的收敛性。

其中，变异运用动态变异率，同时随机分配，使得产生的种群优良性增大。

附图说明

为了更清楚地说明本发明具体实施方式或现有技术中的技术方案，下面将对具体实施方式或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图是本发明的一些实施方式，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1为本发明基于K-Means聚类和遗传算法对运输问题的优化解决方法过程流程图。

图2为本发明一种基于K-Means算法的运输问题过程流程图。

图3为本发明一种基于动态遗传算法的运输问题解决方法的交叉过程流程图。

图4为本发明一种基于动态遗传算法的运输问题解决方法的变异过程流程图。

具体实施方式

下面将结合实施例对本发明的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

在本发明的描述中，需要理解的是，术语"中心"、"纵向"、"横向"、"长度"、"宽度"、"厚度"、"上"、"下"、"前"、"后"、"左"、"右"、"竖直"、"水平"、"顶"、"底"、"内"、"外"、"顺时针"、"逆时针"等指示的方位或位置关系为基于附图所示的方位或位置关系，仅是为了便于描述本发明和简化描述，而不是指示或暗示所指的装置或元件必须具有特定的方位、以特定的方位构造和操作，因此不能理解为对本发明的限制。

此外，术语"第一"、"第二"仅用于描述目的，而不能理解为指示或暗示相对重要性或者隐含指明所指示的技术特征的数量。由此，限定有"第一"、"第二"的特征可以明示或者隐含地包括一个或者更多个所述特征。在本发明的描述中，"多个"的含义是两个或两个以上，除非另有明确具体的限定。此外，术语“安装”、“相连”、“连接”应做广义理解，例如，可以是固定连接，也可以是可拆卸连接，或一体地连接；可以是机械连接，也可以是电连接；可以是直接相连，也可以通过中间媒介间接相连，可以是两个元件内部的连通。对于本领域的普通技术人员而言，可以具体情况理解上述术语在本发明中的具体含义。

请参阅图1至图4，本发明提供一种技术方案：

基于K-Means聚类和遗传算法对运输问题的优化解决方法，该基于K-Means聚类和遗传算法对运输问题的优化解决方法包括如下步骤:

S1:设置参数:聚类中心种群规模N、迭代次数T、生产地数量m、销售地数量n；

S2:首先通过ArcGISPro平台获得的地图设置m个生产地及n个销售地，利用K-Means对销售地进行聚类；

K-Means聚类算法描述如下：

2.1)选择一些类或组，初始化各自的中心点，即随机选择K个聚类中心；

2.2)计算各销售地到各聚类中心的距离dis,其中：

S表示聚类中心的集合，表示数据集中第j个数据，表示当前聚类数；并根据计算结果将销售地归属到最近距离的聚类中心范围内；

2.3)求聚类中心的平均值，得到的结果视为新的聚类中心；

其中：

2.4)重复以上操作步骤，直到每一类的聚类中心在每次迭代后变化都不大为止，也可以多次随机初始化中心点，然后选择运行结果最好的一个所得结果最终呈现收敛特征；

S3:初始化种群；通过智能混合算法计算费用成本矩阵C，

迭代如下过程生成初始种群：

X＝{X

其中：

x

初始化过程即分配，其基本思想如下：

3.1)初始化前提需要满足非负条件和平衡条件，产生满足所有约束的种群；

3.2)首先从分配矩阵中任选一个x

随机选取一个x

其中：

x

k代表第k个数(1,2,3…k)，n代表第n列；

3.3)修改a

为止。修改后的a

b

S4:设迭代次数t＝1，其中t∈{1,2,...,T}；

S5:对种群中的个体随机成双配对，组成N/2个父本对，对每对父本执行步骤S6至S8；

S6:交叉操作，过程如下：

6.1)假设

两矩阵之间的关系为：

6.2)将生成的R矩阵分解为

其中：

R＝R

6.3)生成交叉个体

S7:对交叉个体

7.1)从双亲矩阵中随机选择交叉个体的p行和q列，建立子矩阵Y＝(y

7.2)生成新的子矩阵Y′＝(y′

供给

7.3)将子矩阵Y′＝(y′

S8:选择操作，过程如下：

8.1)设计适应度函数：

8.2)分别计算父代个体X

8.3)若

8.4)若

S9:t＝t+1，若t≤T，转至步骤S5；否则结束程序，输出最优解。

有益效果：

1、不同于传统的线性规划的解法，采用了K-Means算法对数据进行聚类，K-Means算法能够处理图像和文本特征，具有较高的稳定性和伸缩性，能够处理数值形式的数据集，聚类效果好；

2、聚类方法使得销售地种群当中产生中心点，具体思想是通过将货物运输到中心点再向中心点附近其他销售地运送货物，该方法大大缩短了运输距离，节约成本，提高效率；

3、K-Means算法可以通过若干次迭代，计算出运输问题的优化解决方法；

4、采用遗传算法来解决并优化运输问题解决方法；

5、采用了动态交叉变异加上MC接收形式提升了算法的收敛性。其中，变异运用动态变异率，同时随机分配，使得产生的种群优良性增大。

最后应说明的是：以上各实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述各实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分或者全部技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的范围。