论文部分内容阅读
组合拍卖是解决各种资源分配问题的有效机制，随着电子商务的发展，组合拍卖机制发展成为一种新的多方交互与决策的电子谈判模式，是当前电子商务的一个重要应用领域。组合拍卖问题是组合拍卖理论的研究核心之一，是NP难题。该问题的优化与求解直接影响到整个组合拍卖机制的有效性与实用性，有着极高的理论研究价值和广泛的应用前景。
本文主要研究基于组合标集的单数量组合拍卖问题和多数量组合拍卖问题，目前，国内外文献对整合了组合标集的组合拍卖问题尚未见有较深入的优化求解。为此，本文对这两种基于组合标集的组合拍卖问题进行研究，对问题的优化求解开展了以下工作：
1、对组合拍卖问题原型进行了研究，分析了组合拍卖问题与多维背包问题的关系，揭示了两种基于组合标集的组合拍卖问题模型均派生于多维背包问题模型。
2、对基于组合标集的单数量组合拍卖问题建立了0-1整数规划模型。分析了单数量组合拍卖下的组合标集特性，提出多项启发式规则并设计相应的预处理方法对问题进行优化，有效地缩减求解空间。
3、针对单数量组合拍卖的特性，设计新的评价策略和评价函数，更准确评估标进入最优解的可能性。提出单亲算子与免疫算子相结合的启发式算法对问题进行求解，免疫算子利用评价函数将问题的特征知识引入到算法求解中，减少了冗余搜索，提高算法搜索效率。仿真测试表明该算法能够有效地解决大规模问题，而且表现出良好的求解性能。
4、对基于组合标集的多数量组合拍卖问题建立了0-1整数规划模型。分析了多数量组合拍卖下的组合标集特性，提出多项启发式规则并设计相应的预处理方法优化求解，
5、针对多数量组合拍卖的特性，提出启发函数评价标的综合效益。提出了加入优化算子的单亲遗传算法进行求解。优化算子利用启发函数分析并改善染色体的基因组成，提高种群平均适值，引导搜索往好的方向进行。计算结果验证了算法的有效性，算法能够适用于不同规模不同情况的多数量拍卖，有着良好的性能。