改进图聚类算法及其应用

《改进图聚类算法及其应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、JournalofComputerApplicationsISSN1001-90812012-12-01计算机应用，2012，32(12):3278－3282CODENJYIIDUhttp://www．joca．cn文章编号:1001－9081(2012)12－3278－05doi:10．3724/SP．J．1087．2012．03278改进图聚类算法及其应用*丁利，向来生，刘希玉，宋超超(山东师范大学管理科学与工程学院，济南250014)(*通信作者电子邮箱lizi321321@126．com)摘要:第四方物流企业联盟建立问题是研究如何将区域内物流企

2、业以一种高效、低联系代价的方式建立合作联盟的问题。针对该问题提出一种基于离散粒子群优化算法的改进图聚类算法，有助于降低合作联盟之间的联系代价。通过离散粒子群算法优化基本图聚类算法得到的初期聚类结果，利用扰动策略对优化结果进行再拓展。对于实验中的100家虚拟企业进行了聚类，使得联盟企业内部总联系代价从初始时的39991降低到最后的24800。实验结果表明，基于离散粒子群算法的改进图聚类算法能以较低的花费解决物流企业联盟建立问题。关键词:第四方物流;企业联盟;图聚类;粒子群优化;离散化;扰动策略中图分类号:TP18文献标志码:AImprovedgraphc

3、lusteringalgorithmanditsapplication*DINGLi，XIANGLai-sheng，LIUXi-yu，SONGChao-chao(InstituteofManagementScienceandEngineering，ShandongNormalUniversity，JinanShandong250014，China)Abstract:Thefourth-partylogisticscompanyalliancebuildingproblemistostudyhowtobuildalliancewithamethodofh

4、ighefficiencyandlowcost．AnimprovedalgorithmaboutgraphclusteringbasedonParticleSwarmOptimization(PSO)wasproposedtosolvetheproblem，anditcontributedtoreducetheconnectioncostbetweencompaniesinthegroup．DiscretizationPSOwasusedtooptimizetheclusteringresultofgraphclusteringalgorithm，an

5、dtheresultwithdisturbancestrategiesgotenhanced．Clusteringthe100virtualcompanies，thecostwasreducedfrom39991to24800．Theexperimentalresultshowsthat，theimprovedgraphclusteringalgorithmbasedondiscretizationPSOcansolvetheprobleminawaywithhighefficiencyandlowcost．Keywords:thefourth-par

6、tylogistics;companyalliance;graphclustering;ParticleSwarmOptimization(PSO);discretization;disturbancestrategy0引言1联盟建立问题数学模型［1］1．1问题描述第四方物流是为整合物流资源，一般由政府或者非营某区域内有若干物流企业为响应第四方物流建设方案，利性机构组织，来为第三方物流企业建立统一的信息供求平为第四方物流系统的到来做好前期准备工作，企业之间纷纷台，从而使得区域内的物流行业高效、快速发展。随着第四方选择进行合作，互补有无，来共同开发物流市

7、场，满足市场需物流的提出，物流企业之间纷纷合作来为第四方物流做好准求。企业之间考虑以一种高效、总花费少的方式进行互相联备，物流企业联盟建立问题越来越引起物流行业专家的兴趣，系，如何能保证该区域内物流企业之间通过这种高效、低花费纷纷对物流企业联盟建立问题以及第四方物流问题进行研的方式建立联系是该问题的关键。究。1．2问题形式化目前国内外的研究多从企业自身属性［2－5］出发，通过研该部分主要是对本文所研究问题的形式化描述，包括变量符号、目标函数以及约束条件的数学化描述。究企业的内部属性如企业秉性、信任机制等，对个体与个体之1．2．1变量符号定义间的合作展开

8、研究，而从整个物流区域的总体发展角度、考虑1)设企业集合为N={1，2，…，n}，企业与企业之