交叉迭代粒子群算法及在组合拍卖问题中的应用

《交叉迭代粒子群算法及在组合拍卖问题中的应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、国内图书分类号：TP181学校代码：10213国际图书分类号：004.8密级：公开硕士学位论文交叉迭代粒子群算法的设计及在组合拍卖问题中的应用硕士研究生:支东升导师:张春慨副教授申请学位:工学硕士学科:计算机科学与技术所在单位:深圳研究生院答辩日期:2012年12月授予学位单位:哈尔滨工业大学ClassifiedIndex:TP181UDC:004.8DissertationfortheMasterDegreeofEngineeringDESIGNOFCROSS-ITERATIONPARTICLESWARMOPTIMIZATIONANDITSAPPLICATIONINCO

2、MBINATIONAUCTIONCandidate:DongshengZhiSupervisor:AssociateProf.ChunkaiZhangAcademicDegreeAppliedfor:MasterofEngineeringSpeciality:ComputerScience&TechnologyAffiliation:ShenzhenGraduateSchoolDateofDefence:December,2012Degree-Conferring-Institution:HarbinInstituteofTechnology哈尔滨工业大学工学硕士学位论文

3、摘要近年来随着计算机科学技术和电子商务的快速发展，组合拍卖的应用前景越来越广泛，而组合拍卖的求解效率是组合拍卖的核心问题，因此求解效率的高低直接影响到组合拍卖在现实生活中的应用。由于物品之间有很强的关联价值，以及竞标的不可分割性，所以组合拍卖能够很好地表达物品之间的关联价值，即能够更好地表达竞标者对物品的真实需求和喜好程度，因而能够提高拍卖的效率和灵活性、增加拍卖者的收入、降低拍卖的风险，所以它是一种有效的资源分配方n法。由于组合拍卖问题的解空间是庞大的，比如n个物品就有21−种组合，而且随着n的增大，组合标的数量是指数增长的。组合拍卖竞胜标问题的求解被证明是一个NP难问

4、题，所以组合拍卖是一个比较难的求解问题，因此组合拍卖的研究有很好的现实意义和理论价值。本文提出了交叉迭代粒子群算法和多种群PSO算法并且使用了常用的四个标准测试函数来测试它的性能。在此基础上结合贪婪修补算子用离散粒子群算法对竞胜标问题进行确定。本文的具体工作如下：（1）本文提出了将粒子群算法的全局形式和局部形式交叉使用的交叉迭代PSO算法，并且通过四个基函数SphereF1，RosenbrockF3，GeneralizedRastriginF5，GeneralizedGriewankF7分别验证了它在30维、50维、100维的求解性能。实验证明交叉迭代粒子群算法在收敛速度

5、方面明显的优于局部粒子群算法，在收敛精度方面明显的优于全局粒子群算法。其次本文的多种群PSO算法在函数优化中的效果较优。（2）在深入分析各种离散粒子群算法的基础上，本文采用映射粒子的位置而粒子群算法的基本模式不变的离散粒子群算法。实验证明这种思想的离散粒子群算法在求解组合拍卖时比离散二进制粒子群算法具有更好的导向性。其次本文提出的交叉迭代粒子群算法的离散化求解是综合性能最好的。（3）建立了单数量组合拍卖的数学模型，然后对它的解空间进行了化解，在此基础上设计了贪婪修补算子以此来修正离散粒子群算法的解，使其成为满足条件的解。（4）最后通过组合拍卖标准的CATS2.0来产生各种

6、经济分布下的不同规模的数据来验证本文提出的算法的效率，证明本文算法的有效性。关键词:粒子群算法；组合拍卖；竞胜标问题确定-I-哈尔滨工业大学工学硕士学位论文AbstractInrecentyears,withtherapiddevelopmentofcomputerscienceandtechnologyande-commerce,combinationauctionhavegreatpontentialinapplicationprospects.Howtogetmoreeffectivesolutionofcombinatorialauctionsisthecorei

7、ssueincombination,whichhavedirecteffectontheapplicatonprospectsandpracticality.Asthereisstrongcorrelationamonggoodsandbidcannotbedivisible,combinatorialauctioncanexpresscorrelationvalueamonggoodsbetter,thatistosayitcanhavemoreandmoreeffectivewaytoexpresstorealneedsa