学位论文 > 优秀研究生学位论文题录展示

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

作　者: 支东升
导　师: 张春慨
学　校: 哈尔滨工业大学
专　业: 计算机科学与技术
关键词: 粒子群算法组合拍卖竞胜标问题确定
分类号: TP18
类　型: 硕士论文
年　份: 2013年
下　载: 18次
引　用: 0次
阅　读: 论文下载

内容摘要

近年来随着计算机科学技术和电子商务的快速发展，组合拍卖的应用前景越来越广泛，而组合拍卖的求解效率是组合拍卖的核心问题，因此求解效率的高低直接影响到组合拍卖在现实生活中的应用。由于物品之间有很强的关联价值，以及竞标的不可分割性，所以组合拍卖能够很好地表达物品之间的关联价值，即能够更好地表达竞标者对物品的真实需求和喜好程度，因而能够提高拍卖的效率和灵活性、增加拍卖者的收入、降低拍卖的风险，所以它是一种有效的资源分配方法。由于组合拍卖问题的解空间是庞大的，比如n个物品就有2n1种组合，而且随着n的增大，组合标的数量是指数增长的。组合拍卖竞胜标问题的求解被证明是一个NP难问题，所以组合拍卖是一个比较难的求解问题，因此组合拍卖的研究有很好的现实意义和理论价值。本文提出了交叉迭代粒子群算法和多种群PSO算法并且使用了常用的四个标准测试函数来测试它的性能。在此基础上结合贪婪修补算子用离散粒子群算法对竞胜标问题进行确定。本文的具体工作如下：（1）本文提出了将粒子群算法的全局形式和局部形式交叉使用的交叉迭代PSO算法，并且通过四个基函数Sphere F1，Rosenbrock F3，Generalized Rastrigin F5，Generalized Griewank F7分别验证了它在30维、50维、100维的求解性能。实验证明交叉迭代粒子群算法在收敛速度方面明显的优于局部粒子群算法，在收敛精度方面明显的优于全局粒子群算法。其次本文的多种群PSO算法在函数优化中的效果较优。（2）在深入分析各种离散粒子群算法的基础上，本文采用映射粒子的位置而粒子群算法的基本模式不变的离散粒子群算法。实验证明这种思想的离散粒子群算法在求解组合拍卖时比离散二进制粒子群算法具有更好的导向性。其次本文提出的交叉迭代粒子群算法的离散化求解是综合性能最好的。（3）建立了单数量组合拍卖的数学模型，然后对它的解空间进行了化解，在此基础上设计了贪婪修补算子以此来修正离散粒子群算法的解，使其成为满足条件的解。（4）最后通过组合拍卖标准的CATS2.0来产生各种经济分布下的不同规模的数据来验证本文提出的算法的效率，证明本文算法的有效性。

全文目录

摘要  4-5
Abstract  5-9
第1章绪论  9-17
  1.1 课题背景及研究意义  9-11
    1.1.1 课题背景  9-11
    1.1.2 组合拍卖  11
  1.2 国内外研究现状  11-16
    1.2.1 组合拍卖的研究现状  11-13
    1.2.2 粒子群算法的研究现状  13-16
  1.3 主要研究内容及组织安排  16-17
    1.3.1 主要研究内容  16
    1.3.2 结构安排  16-17
第2章粒子群算法的相关研究及算法改进  17-40
  2.1 粒子群算法介绍  17-20
  2.2 粒子群算法的相关技术  20-25
    2.2.1 惯性权重因子ω和拓扑结构  20-23
    2.2.2 混合粒子群算法  23-24
    2.2.3 离散粒子群算法的研究  24-25
  2.3 交叉迭代粒子群算法的设计  25-34
    2.3.1 交叉迭代粒子群算法的提出  25-27
    2.3.2 算法性能验证  27-34
  2.4 多种群粒子群算法的设计  34-38
    2.4.1 多种群粒子群算法的提出  34-35
    2.4.2 算法性能验证  35-38
    2.4.3 交叉迭代PSO和多群PSO算法性能比较  38
  2.5 本章小结  38-40
第3章组合拍卖问题的数学模型及其求解  40-49
  3.1 组合拍卖问题  40
  3.2 组合拍卖问题的数学模型  40-43
    3.2.1 基于OR标集的组合拍卖问题  40-43
    3.2.2 基于XOR标集的组合拍卖问题  43
  3.3 组合拍卖中的DPSO算法和贪婪修补因子  43-45
  3.4 组合拍卖问题解空间的化解  45-46
  3.5 DPSO求解组合拍卖问题  46-48
    3.5.1 冲突矩阵的定义和竞胜标的评价方式  46-47
    3.5.2 DPSO求解基于OR标集的组合拍卖问题  47-48
    3.5.3 DPSO求解基于XOR标集的组合拍卖问题  48
  3.6 本章小结  48-49
第4章组合拍卖问题实验仿真  49-58
  4.1 实验环境  49
  4.2 实验方案与数据  49-50
  4.3 基于OR标集的组合拍卖问题实验比较  50-54
    4.3.1 L3 分布下的实验结果  50-52
    4.3.2 L4 分布下的实验结果  52-54
  4.4 基于XOR标集的组合拍卖问题的实验比较  54-57
  4.5 本章小结  57-58
结论  58-60
参考文献  60-65
致谢  65

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

内容摘要

全文目录

相似论文