多项目采购中基于量子进化算法的打包优化方法

工业工程 ›› 2013, Vol. 16 ›› Issue (1): 45-49.

多项目采购中基于量子进化算法的打包优化方法

(1. 东北大学信息科学与工程学院，辽宁沈阳 110819; 2. 沈阳师范大学计算机与数学基础教学部，辽宁沈阳 110034) 

出版日期:2013-02-28 发布日期:2013-03-22
作者简介:汪定伟(1948-),男，江西省人，教授，博士生导师，主要研究方向为复杂系统建模与优化、智能优化方法、生产计划与调度、电子商务.〖ZK)〗
基金资助:
国家自然科学基金资助项目（70931001,61273203）

A Quantum Evolutionary Algorithm-Based Bundling Optimization for Multi-item Procurements

(1. Northeastern University, School of Information and Engineering, Shenyang 110819, China; 2. Shenyang Normal University, Department of Basic Computer and Mathematics, Shenyang 110034, China)

Online:2013-02-28 Published:2013-03-22

摘要/Abstract

摘要： 提出多项目集中采购或大型工程项目招标的逆向组合拍卖中的标的物打包优化的问题和数学模型。由于该优化问题实质上是一种自变量为集合的、非解析的多目标优化问题，提出一种基于量子进化算法的求解方法。方法中采用基于价格互补系数矩阵中非零变量的0-1编码，以及一种有利于好的量子位（Q-bit）胜出的β-旋转门。大量数值例子的对比计算的结果表明，β-旋转门明显优于现有的α-旋转门；而对比遗传算法这种新算法对于中小规模的打包优化问题有明显的计算优势。

关键词: 网上采购；组合拍卖, 标的物打包, 最优拍卖设计, 量子进化计算, 旋转门

Abstract: The object bundling optimization problem in reverse combinatorial auctions for online procurements and large project tenders is addressed. A mathematical model with multi-objectives is proposed to solve the problem. Because of its nonlinear and non-analytic properties with variable sets, it is very difficult to solve. Thus, a Quantum Evolutionary Algorithm (QEA) is developed for its solution. It adopts the 0-1 encoding scheme with nonzero elements in the cost complementarity matrix, and the β-based rotation gate to enlarge the probability of selecting the better Q-bits. Numerical results from a number of examples show that the β-based rotation gate is evidently better than the α-based one. Compared with a contrastive genetic algorithm, QEA can achieve better computational performances for small- and middle-sized problems.

Key words: online procurement, combinatorial auction, object bundling, optimal auction design, quantum evolutionary computation, rotation gate

汪定伟1，王娜2. 多项目采购中基于量子进化算法的打包优化方法[J]. 工业工程, 2013, 16(1): 45-49.

Wang Ding-wei1, Wang Na2. A Quantum Evolutionary Algorithm-Based Bundling Optimization for Multi-item Procurements[J]. Industrial Engineering Journal , 2013, 16(1): 45-49.

参考文献

［1］武刚, 冯玉强, 傅丽芳.面向政府采购的多属性电子拍卖机制设计［J］.系统管理学报, 2007, 16(3): 291-297. Wu Gang, Feng Yu-qiang, Fu Li-fang. Government procurement oriented multi-attribute E-auction mechanism design［J］. Journal of Systems & Management, 2007, 16(3): 291-297.  ［2］Vries S de， Vohra R V.Combinatorial auctions: a survey ［J］. INFORMS Journal on Computing, 2003, 15(3): 284-309. ［3］Wagner S M， Schwab A P. Setting the stage for successful electronic reverse auctions ［J］.Journal of Purchasing & Supply Management, 2004, 10(1): 11-26. ［4］Sandholm T. Approaches to winner determination in combinatorial auctions ［J］.Decision Support Systems, 2000, 28(1/2): 165-176.  ［5］Sandholm T. Algorithm for optimal winner determination in combinatorial auctions ［J］. Artificial Intelligence, 2002, 135(1/2):1-54. ［6］陈培友, 汪定伟. 组合拍卖竞胜标确定问题的混沌搜索方法［J］. 管理科学学报, 2003, 6(5): 24-28. Chen Pei-you,Wang Ding-wei. Chaotic search algorithm for winner determination in combinatorial auctions ［J］. Journal of Management Sciences in China, 2003, 6(5): 24-28. ［7］陈培友, 汪定伟. 多物品最优组合供应模式确定问题的模型研究［J］, 中国管理科学, 2006, 14(4): 35-39. Chen Pei-you,Wang Ding-wei. Research on the model of determination of multiple products optimal combinatorial supply patterns［J］. Chinese Journal of Management Science, 2006, 14(4): 35-39. ［8］Avery C, Hendershott T. Bundling and optimal auctions of multiple products［J］. Review of Economic Studies, 2000,67(3): 483-497. ［9］Schoenherr T,Mabert V A. The use of bundling in B2B online reverse auctions［J］.Journal of Operations Management,2008, 26(1): 81-95.〖ZK)〗 ［10］汪定伟. 网上集中采购的捆绑-组合拍卖机制设计［J］. 系统工程学报, 2011, 26(6): 809-815. Wang Ding-wei. Mechanism design of hybrid bundling and combination auction for centralized e-procurement［J］. Journal of Systems Engineering, to appear, 2011, 26(6): 809-815. ［11］Han K H，Kim J H. Quantum-inspired evolutionary algorithm for a class of combinatorial optimization［J］. IEEE Transactions on Evolutionary Computation, 2002, 6(6): 580-593.  ［12］Han K H，Kim J H. Quantum-inspired evolutionary algorithms with a new termination criterion, He Gate, and two-phase scheme［J］. IEEE Transactions on Evolutionary Computation, 2004, 8(2): 156-169. ［13］Vlachogiannis J G，Ostergaard J. Reactive power and voltage control based on general quantum genetic algorithms［J］. Expert Systems with Applications, 2009,36(3): 6118-6126. ［14］Chen J C. Application of quantum-inspired evolutionary algorithm to reduce PAPR of an OFDM signal using partial transmit sequences technique［J］. IEEE Transactions on Broadcasting, 2010, 56(1): 110-113. ［15］王凌. 量子进化算法研究进展［J］.控制与决策, 2008, 23(12): 1321-1326. Wang Ling. Advances in quantum-inspired evolutionary algorithms［J］. Control and Decision, 2008, 23(12): 1321-1326. ［16］任子武, 熊蓉, 储健. 混合量子差分进化算法及应用［J］. 控制理论与应用, 2011, 28(10): 1349-1355. Ren Zi-wu, Xiong Rong, Chu Jian. Hybrid quantum differential evolutionary algorithm and its applications［J］. Control Theory & Applications, 2011, 28(10):1349-1355. ［17］Gen M，Cheng R W. Genetic algorithms and engineering design［M］. New York：John Wiley and Sons, 1997.