物流数据中的云聚类调度算法研究

发布时间：2016-05-24 08:12

第一章 绪论

1.1 研究背景与意义
物流产业主要是为了经济的可持续发展[2]，在我国的经济综合发展中物流的发展有着举足轻重的影响，物流业的调整振兴应满足物流产业升级，增加其他经济部门的竞争能力，转型升级国家经济体系，从而全面加强综合国力，增强国际竞争力。我国制定了一系列振兴物流业发展的计划，并将其集成到宏观经济系统发展计划以实现低成本、高效益的目标。物流作为重要的“新经济”被广泛的称为第三利润源，在 21 世纪为中国的可持续发展做出自己的贡献。 物联网[3]作为一个信息技术发展的产物，它的应用已经渗透到我们日常生活的各个方面，并形成了一定规模的产业。物联网技术广泛运用于电力，运输，工业控制，零售，公共服务管理，健康，石油以及其他行业，可以实现许多功能，如车辆防盗，安全监控，自动售货机，机器的维护，公共交通管理等。将物联网技术运用到物流行业从而催生了智慧物流的发展。随着各种传感器的发展，智慧物流得到了前所未有的发展，从而催生了物流数据的处理的研究。 计算机技术的快速发展导致了数据呈现指数型增长，如何从大量的数据中找出隐含的，未知的有用的信息成为了人们越来越关心的问题，数据挖掘由此产生。聚类分析就是其中相当重要的一部分。它将目标的集合分成多个组，使得同一组中的样本尽量相似而不同组中的样本尽可能相异[4]。现今世界，国内外提出了层次型类聚、划分型类聚、密度型类聚、网络型类聚等类聚算法。 随着分布式、并行等技术的迅速发展，大量的数据需要处理，在此基础上云计算得到了发展，它允许用户根据自己的需要来付费并且可以取得强大的计算能力服务。它将分布式、并行、网格计算等技术和网络技术融合在一起，其中虚拟化最为重要，，我们能够虚拟化不少因素，比如它的软件、硬件等，用云平台来管理他们。云计算提供了基础设施即服务（IaaS），平台即服务（PaaS），软件即服务（SaaS）三种服务[5]。 
..........

1.2 论文的主要研究内容
本文主要对应用于物流数据的云聚类算法进行研究，本文的主要工作内容包含四个方面： (1)对云计算，聚类的相关内容进行分析，针对其中内容进行研究，对云计算的任务调度主要用到的算法进行了总结，对我国物流行业的现状以及未来的发展进行研究，最后研究了我国物流数据的主要应用。 (2)研究面向物流数据的 k 均值聚类算法，对 k 均值聚类中存在的一些问题进行理解，并针对 k 均值聚类结果受初始中心影响的问题，提出了一种基于普利姆的一种 k 均值聚类改进算法 IKACP(An Improved K-means clustering Algorithm Based on Prim)，并对其进行了实验评估。 (3)研究面向物流数据的基于随机梯度下降的支持向量机算法，针对大量数据的机器学习进行研究，使用随机梯度下降算法进行优化训练时间，提出了一种基于随机梯度下降的改进支持向量机分类算法 ISVMSGD(An  Improved  Support  Vector  Machine  Based  on  Stochastic Gradient Descent），并对其进行了实验评估。 (4)研究面向物流数据的云计算调度算法，对粒子群优化算法进行研究，加深对离散的粒子群算法的理解，研究云计算的调度模型，提出提出一种改进的二进制粒子群优化的任务调度算法 GCTA (A Green Cloud Task-scheduling algorithm) Based Improved Binary Particle Swarm Optimization，并对其进行了实验评估。 
.........

第二章 相关背景知识介绍

2.1 云聚类算法研究现状
(1)概念。云是从世界电信提供商开始使用虚拟专用网络中来的。云计算可以在不知道最终用户的物理位置和系统配置的情况下给用户提供计算、软件、数据访问以及存储服务。国际标准云计算的定义是“云计算是拥有能够通过网络进行按需配置一个包括网络，服务器，存储应用程序和服务等共享计算资源池的一个方便模式，服务提供商提供较小的管理工具就可以迅速配置和发布”。过连接世界各地的大型互联网，应用程序可以作为互联网上的一种服务，这样可以降低成本。云计算的主要目标是更好的利用分布式资源，以达到更高的吞吐量和能够解决大规模计算问题。 (2)架构。前端和后端两部分是云计算的重要组成部分。它们是通过网络彼此连接的，通常是因特网。前端我们认为主要就是到底是什么样的客户，后端就是该系统的云。前端有客户端的计算机和需要访问的云，后端就是云计算的服务器集群和数据存储等。图 2-1 是云计算的一个总观图，其包括五种必需具有的特征，三种服务形式和四种部署形式。 从图中我们可以看出云计算解决方案可分为四种类型。首先为私有云类型，它只能由一个单一的企业应用。在这种情况下资源及应用都是在公司的计算机中心或者计算机服务商提供的专用网络进行访问。其次，云计算资源可以设置为公开的即公有云，在这种情况下，务使用云供应商保管的数据。第三种可行的形式是拥有私有云和公有云的长处的混合云模式，对一些保密性要求较高的数据采用私有云，对其他一些数据使用公有云，可以有效降低云部署的成本。第四种是社区云，这可以由几个供应商，或者使用公有云的一个特定用户组提供，成为客户社区云。 
........

2.2 云调度算法研究现状
随着信息技术的快速发展，云计算由于可以迁移到许多网络环境中已经成为一个越来越重要的研究课题，其中最重要的问题是如何利用大量的计算资源，这就是云计算中的资源调度问题。任务调度的目标就是想办法将有限的资源优化分配给一个或者多个目标，人们普遍认为现在的调度算法研究可以追溯到 Johnson 的研究[13]。如今，调度被广泛的用于不同的领域，如制造印刷电路板，多媒体的功率系统控制以及万维网上的数据处理。从 20 世纪 80 年代到现在，这些系统经历了几次变化，早期的变化之一是随着集群的出现很多独立的计算机一起工作作为一个系统，这需要克服的一个问题就是集群系统只能使用本地资源。下一个变化就是网格，它的发展将所有地理上分散的可用异质性机构连接起来[14]。最近的一个变化就 是将集群和网格优势转移到云计算系统中。 在当前的计算机调度算法中，常用的两个为穷举算法和确定性算法。在实践中确定性算法比穷举性算法能更快的解决调度问题。然而这两个算法的主要缺点是他们并不适用于所有的分布式数据。不像确定性算法和穷举性算法，启发式算法（也叫近似算法）采用迭代方法在一个合理的时间内找到解决策略。很多研究成果[15]-[18]显示启发式调度算法可以提供比传统的调度算法更优的调度结果。 然而他们的重点都不在云计算，虽然很多调度算法已经被证明成果可用于不同的计算环境（如网格计算，集群计算等），其中的一些想法也许可以直接使用于基于云计算的任务调度。下面我们主要讨论使用于云计算的启发式任务调度算法。 
..........

第三章  基于普利姆的一种 K 均值聚类改进算法 ..... 16 
3.1  引言 .......... 16 
3.2  基于普利姆的 K 均值聚类改进算法 ............ 17
3.3  算法的实验结果及分析 ..... 20 
3.4  本章小结 ........... 24 
第四章  基于随机梯度下降的 SVM 分类算法 ........... 25 
4.1  引言 .......... 25 
4.2  基于随机梯度下降的 SVM 分类算法 .......... 26 
4.2.1  随机梯度下降算法 ........... 26 
4.2.2 SVM 分类算法 .......... 27 
4.2.3  基于随机梯度下降的 SVM 分类算法 ........ 27 
4.3  算法的实验结果及分析 ..... 28 
4.4  本章小结 ........... 31 
第五章  基于改进  BPSO 的绿色云计算调度算法..... 32 
5.1  引言 .......... 32 
5.2  基于改进 BPSO 的绿色云计算调度算法..... 33
5.3  算法的实验结果以及仿真分析 ........... 37 
5.4  本章小结 ........... 40 

第五章 基于改进BPSO 的绿色云计算调度算法

随着物流的快速发展，物流的数据量越来越大。此基础上面向物流数据的云计算得到了发展，如何在面向物流数据的云计算中进行合理的任务调度对云计算的效率提高有着举足轻重的影响。本文提出一种改进的二进制粒子群优化的任务调度算法 GCTA  (A  Green  Cloud Task-scheduling Algorithm)，该算法使用将虚拟机简化为采用流水线编号，并对速度和位置进行重新定义，从而有效的规避矩阵运算，提高资源利用率。仿真实验表明，本算法在面向物流数据的云调度算法中具有较低的任务执行时间相应的提高资源利用率。 

5.1 引言

如今随着信息产业数据呈现爆炸式的增加，云计算作为一个新的技术得到了在商业中取得了快速的发展，它允许用户根据自己的需要来付费并且可以取得强大的计算能力服务。作为云计算中的一个重要组成部分，任务调度数学化为 NP 完全问题[58]，无法在多项式的时间复杂度内寻找到最优解。遗传、模拟退火等智能优化算法被引入到云调度算法的研究中来[59]。遗传算法可以在寻找最优解的过程中对搜索空间得到的信息进行积累，并可以根据需要对搜索方向进行控制以得到最优解[60]，但参数较多，编程实现较复杂。粒子群算法是在生物学基础上提出，因而可以根据生物学进行理解、参数不多并且容易实现，用在对非线性、多峰问题上表现良好[61]。本文将对离散粒子群算法进行改进，来适应面向物流数据的云任务调度的情况，减小资源消耗。 近年来，由于大数据的快速发展，为了降低资源消耗提高资源利用率，云计算任务调度算法得到了人们的大量研究。文献[62]提出了一种以粒子群算法为基础的多处理器的任务调度和负载均衡方法，这种方法可以有效提高资源利用率。文献[63]提出了一种基于适应度函数值分类的简单的突变机制和自适应惯性权重方法来改进标准的粒子群算法来提供更好的资源服务。文献[64]提出一种基于代价的通过对可用资源做映射的云调度策略。文献[65]提出一种基于粒子群以及完成时间限制的采用分布式控制方式的调度算法。文献[66]提出一种粒子群优化和鸡尾酒解码对多处理器的混流车间调度问题算法。文献[67]提出了一种在 Iaas 资源提供商当它的资源不能满足需求时将任务分配到扩展云的资源分配框架。文献[68]提出了一种基于最小位置值的粒子群算法来解决任务调度问题。

........

总结

本文主要完成的主要工作内容总结为以下几个方面： 
(1)对面向物流数据的聚类算法进行研究，对 K 均值聚类中存在的一些问题进行理解，并针对 k 均值聚类结果受初始中心影响的问题，提出了一种基于普利姆的一种 K 均值聚类改进算法 IKACP(An Improved K-means clustering Algorithm Based on Prim)，在不改变 K 均值聚类算法的简单性的前提下将普利姆算法利用在初始聚类中心的选择上，可以有效的减小迭代次数，提高聚类正确率。 
(2)对面向物流数据的支持向量机分类算法进行研究，针对大量物流数据的机器学习进行研究，使用随机梯度下降算法优化物流数据训练时间，提高训练速度，提出了一种基于随机梯度下降的改进支持向量机分类算法 ISVMSGD(An  Improved Support Vector Machine Based on Stochastic Gradient Descent)，在大量数据中训练中在不影响正确率的情况下可以有效的提高训练速度。 
(3)对面向物流数据的云调度算法进行研究，对粒子群二进制的方法进行进一步学习，加深对离散的粒子群算法的理解，研究面向物流数据的云计算调度模型，利用离散粒子群算法对模型中的任务调度进行优化，提出了一种改进的二进制粒子群优化的任务调度算法 GCTA (A Green Cloud Task-scheduling algorithm)，主要将复杂矩阵运算简化为流水线，重新定义粒子的速度和位置。在随机产生的任务中可以减小系统总的执行时间，提高效率。在随机产生的任务中可以减小系统总的执行时间，调高效率。 
.........
参考文献(略)

本文编号：48970