组合拍卖竞胜标确定问题的混沌搜索算法!
陈培友!，"，汪定伟!
（! # 东北大学信息科学与工程学院，沈阳 !!$$$%；" # 黑龙江科技学院经济贸易系，哈尔滨 !&$$"’）
摘要：组合拍卖能够提高拍卖的效率，还能降低竞标人的风险 #但竞胜标确定问题是一个 ()
难题 #在分析该问题特性的基础上，设计了一种嵌入优先适合启发式规则的混沌搜索算法 #与
传统算法相比，该算法具有实现方便，寻优效果好的优点 #实例计算结果表明了算法在解决该
问题的有效性和广阔的应用前景 #
关键词：组合拍卖；竞胜标确定问题；第一价格密封拍卖；混沌；电子商务
中图分类号：*)"+ 文献标识码：, 文章编号：!$$’ - +.$’（"$$/）$& - $$"% - $&
! 引 言
组合拍卖在电子商务中是一个十分重要的应
用领域，它可以使竞标人把多个项目看作一个标
的来竞标 #与其它拍卖机理比较，组合拍卖不仅能
够提高拍卖的效率，而且还能降低竞标人的风
险［!］，因而这种拍卖方式具有广阔的应用前景 #不
过，在组合拍卖的机理设计中，组合拍卖竞胜标确
定问题是一个 ()难题［"］，已经引起越来越多人
的研究 #文献［/ 0 ’］分别对这一问题及其传统的
精确算法和近似算法做了分析研究，表明：传统的
精确算法因求解问题的规模相对较小在实际应用
中受到限制，近似算法因求解问题的精度相对不
足或耗时相对过多在实际应用中受到限制 #文献
［.］综述了这一问题优化算法的最新发展，预见了
该问题未来的研究方向 #为了克服传统的精确算
法和近似算法求解该问题的不足，本文在研究该
问题的特性基础上，设计了一种嵌入优先适合启
发式规则的混沌搜索算法，并以实例计算验证了
算法解决该问题的有效性和广阔的应用前景 #
" 组合拍卖竞胜标确定问题描述
电子商务中，如果采用第一价格密封拍卖
（12345673289 49:;9<6=2< :>852?@）方式［+］，来实现多个
项目的拍卖，则非组合拍卖竞胜标确定是一件十
分容易的事情，只需将“标的”相同的最高价格的
标分别挑出即可 #如果有 ! 个标，" 个待拍项目，
则只需用 #（!"）这么长时间 $在同样条件下，组
合拍卖竞胜标确定要复杂得多，假设 % 为待拍项
目的集合，任意投标人 & 可以对% 中的单项或其
项目的组合 ’ !% 投标，标价为 (&（’）$为了问题
描述简洁和解决问题清晰，对上述标集先进行预
处理 $
预处理 " 对“标的”相同的单一标，只保留
其最高价格的标，即有
(（’）) ABC
&" (&**+,-
(&（’） （!）
预处理 # 对“标的”相同的组合标，只保留
其最高价格的组合标 $
这样，其它的标可视为因无“竞争力”而被遗
弃掉 $预处理 !先是淘汰掉“显性”的无竞争力的
标；预处理 "则是淘汰掉“隐性”的无竞争力的标，
这种标具有一定的欺骗性 $
本文所述的标均是经过上述处理后剩下的
“标的”不同的标，共 . 个 $这样就可以得到下面
的组合拍卖竞胜标确定问题的一般模型
第 D卷第 &期
"$$/年 !$月
管 理 科 学 学 报
EFGH(,I FJ K,(,LMKM(* NOPM(OMN P( OQP(,
R?;#D (?# &
F85 #，
###############################################################
"$$/
! 收稿日期："$$" - $D - !/；修订日期："$$/ - $& - ".#
基金项目：国家自然科学基金资助项目（D$$.%$$/；’$!’!$&D）#
作者简介：陈培友（!+D’—），男，黑龙江人，东北大学博士生，现为黑龙江科技学院副教授 #
!"#
!!""#!!$
（#） （$）
模型说明：
%）模型以极大化拍卖商收益为目标；
$）! 为一个可行解，即每个项目至多可以分
配给一个标；
&）"为可行解空间，令! %｛##&｝，因问题
特性，有定义如下
" %｛’ #! ( # $ #) % *，
%#，#) ! ’｝ （&）
这里，’ 是& 的族集（即 &
#!’
# % &）+
从上面的模型中，不难看出该问题是一个组
合优化问题 +不过，虽然看起来该问题模型较为简
单，但求解却是十分复杂的计算问题，是一个 ’(
难题 +
! 嵌入优先适合启发式的混沌搜索
算法
混沌是非线性动力学系统特有的一种运动形
式，混沌表现出的随机性是系统内在的随机性，它
的一个轨道可以在其吸引子中稠密 +根据混沌吸
引子的这种特性，当时间足够长，这种轨道就能以
任意精度逼近吸引子中的任意点，因此，近年来人
们开始尝试利用混沌吸引子的这种特性来求解最
优化问题［%)，%%］+然而，对于一个非线性动力学系
统，它是否会产生混沌，要取决于系统参数的选
择 +众所周知，对于一个非线性方程组，一组不同
的参数会产生一个性质不同的动力学系统 +一个
非线性动力系统何时产生混沌，产生混沌后如何
控制混沌的发展，是一件十分困难的事情 +在本文
中，混沌搜索路径序列采用人们熟悉的虫口模型，
即一维 *+,-./-0映射［%$］+动力学系统处在运动状
态时，实际上已经多次经历过最优解或近似最优
解了，只是系统处于混沌状态，系统在经历最优解
或近似最优解后又漂移到了其它地方 +显而易见，
只要把系统在混沌状态下经历过的最优解或近似
最优解记录下来，就可以不必等到系统稳定后再
输出最优解，基于上述想法和实际问题特性，本文
提出了嵌入优先适合启发式规则的混沌搜索
算法 +
算法拟采用一维 *+,-./-0映射来产生搜索路
径序列，一维 *+,-./-0映射的形式如下
, 1 -（ . / %）% 0 1 -（ .）1（% 2 -（ .））
参数 0 !（$，2］，, 1［)，%］’［)，%］
*+,-./-0映射有如下特性：
%）当 0!（$，&）时，映射 ,有稳定的不动点；
$）当 0!［&，& +34］时，映射 ,处于倍周期分
岔阶段；
&）当 0!（& +34，2）时，映射 ,失去稳定的周
期轨道，出现混沌，但难以确定在哪些点上其混沌
集的一维 *565.,75测度大于 )；
2）当 0 % 2时，系统处于混沌状态，［)，%］是
映射 , 的混沌不变集 +
在 *+,-./-0混沌不变集中，当时间足够长，,的
任一轨道在其中稠密，即对于%" 3 )，以及%- !
［)，%］，开球 4（-，"）中必包含 , 的一条轨道上的
点 +反之，, 的任一轨道能以任意精度逼近［)，%］
中的所有点 +
本文利用 0 % 2时的 *+,-./-0映射混沌不变集
的上述特性搜索问题的最优解 +求解 5 维最优化
问题，相当于在 5 维空间中确定一个使目标函数
值最大的点，为此需要用 5个独立的 *+,-./-0映射
来产生该空间中点的 5 个坐标分量 +因为每一个
坐标分量都能在［)，%］中稠密，所以这样产生的
点都能在 5 维单位超立方体中稠密，即这些点的
序列能够以任意精度逼近超立方体中所有点，当
然也能够以任意精度逼近超立方体中的全局最优
解 +根据这样分析，*+,-./-0 混沌模型可以用于求
解连续最优化问题 +
用 *+,-./-0混沌模型求解组合拍卖竞胜标确
定问题还需要作变换和嵌入优先适合启发式规
则［%&］，其搜索原理如下：
5维空间中的一个点有 5 个坐标分量，让点
的第 6个坐标对应第 6个标 $6（ 6 % %，$，⋯，5），对
点的 5 个坐标分量排序（升序或降序），相应地会
得到 5个标的一种排列，即一条搜索路径 +再按优
先适合启发式规则就可以得到组合拍卖竞胜标确
定问题的一条合法搜索路径（一个可行解）+对应
一条搜索路径也就对应组合拍卖竞胜标确定问题
的一条合法搜索路径 +
优先适合启发式规则是指一条搜索路径中排
在前面的标具有被选取的“优先权”，运用该规则
具体步骤如下：
—3$—第 3
(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((
期 陈培友等：组合拍卖竞胜标确定问题的混沌搜索算法
步骤 ! 保留排列中的第一个标 !（"#），令
$ % "#；
步骤 " 按照搜索路径顺序选取标 !（"&），若
$! "& % ’，保留 !（"&），且令 $ % $" "&；否则，
划去 !（"&）；
步骤 # 重复步!，当 $ % (时停止选取，并
划去其余的标 )
在标的排列中未被划去的标的子排列就是一
条合法搜索路径 )要想得到组合拍卖竞胜标确定
问题的一条合法搜索路径，首先要确定这 * 个标
的一种排列顺序，得到一条搜索路径，然后再运用
优先适合启发式规则就可以实现 )算法中的 * 个
标的排列顺序按如下方式产生：首先在（"，#）区
间中产生 * 个随机数 +（#，*）作为解空间中的一
个点的坐标，第 #个随机数对应第 #个标!#（ # % #，
!，⋯，*），将这 * 个随机数按升序（或降序）排列，
随机数对应的标也同时获得一个排列，这个排列
作为第一条路径，后面新的路径将通过 $%&’()’*映
射产生 )把上阶段的 * 个随机数 +（#，*）作为初
值，按式 +（ , - #）% ++（ ,）（# . +（ ,））得到新的
* 个值，再对这新的 * 个值排序，得到新的路径，
依此类推，除第一条路径随机产生外，后面的路径
全部由 $%&’()’*映射产生 )每得到一条搜索路径，
按优先适合启发式规则就得到一条合法搜索
路径 )
目标函数是使合法路径上的标价之和最大
化，算法的步骤如下：
#）对 +（ #）赋随机初值，# % #，!，⋯，*，最优
目标函数初值 /0, . 1 % "，对控制参数 2赋一个较
大的初值；
!）把 +（ #）的排序结果赋给 3（ #），对照
+（ #），3（ #）求得当前一个搜索路径，再按优先适
合启发式规则得到当前一个合法路径；
,）计算当前合法路径目标值 1；
+）记忆最大目标值 /0, . 1：如果 1 4 /0, . 1则
/0, . 1 % 1，5,60 % "，并记忆当前合法路径；
-）判断是否结束迭代：如果 5,60 % 2，则
停止；
.）用 $%&’()’*映射产生下一组 +（#，*）：
+（ , - #）% ++（ ,）（# . +（ ,））；5,60 % 5,60 - #；
/）返回第 !）步 )
# 计算实例
表 #给出一个简单的组合拍卖竞胜标确定问
题实例中需要的各项数据 )该问题总的投标数经
过预处理后剩下的标数为 ,"个，用标号 # 7 ,"分
别表示 )待拍卖的项目 #"个，分别用 8 7 9表示；
标书的“标的”中允许投标的最大项目的组合数
为 , )为了简洁，用“标数 : 项目数 : 允许投标的最
大项目组合数”描述该问题规模情况，即
," : #" : , )混沌搜索算法程序用 01 - - 语言编程，
程序运行在 233 : #.. 微机上 ) 表 ! 给出了程序
!" """次迭代运行的结果 )
从表 !中不难看出，标号为 4、#"、#-、#5、!4的
标书为竞胜标，对应的竞标人为买受人，买受人获
得的项目分别为（;，<）、（8，=，>）、（?，9）、（@，
A）、（B），拍卖商获得最大收益为 . !#.65, )
表 # ," :#" :,组合拍卖竞胜标确定问题实例
标号 标的 标价 标号 标的 标价 标号 标的 标价
# （?，=，;） ! +"/6#4 ## （B，@，9） # .+.64! !# （ <） 5+"6-.
! （@，;，<） ! ,"46"" #! （?，@，A） # .!" !! （=） 5!/65.
, （@，;，9） ! !!+6+, #, （>，<） # -#56// !, （ 9） //#64+
+ （?，=，>） ! #+-6". #+ （@，;） # +/565# !+ （>） .!.6-"
- （A，<，9） ! "./6"# #- （?，9） # +. !- （?） ."/6!,
. （?，=，@） ! "+"6+5 #. （@，9） # +#"6,. !. （8，A） -..65/
/ （?，@，<） # 44565" #/ （B，<） # #,-6+4 !/ （@） -,#654
5 （B，>，;） # 55#6!! #5 （@，A） # "!!6/, !5 （A） +#-6!.
4 （;，<） # /456!5 #4 （8，=） 4+,6/! !4 （B） !/,64/
#" （8，=，>） # .-!6#. !" （;） 4".6,. ," （8） #"#6#!
—.!— 管 理 科 学 学 报 !"",年 #"
###############################################################
月
表 ! "# !$# !"组合拍卖竞胜标确定问题求解结果
问题规模 最优解 ! 近似最优解 目标值
"# !$# !" （%，$#，$&，$’，!%） ( !$()’"
对本实例，表 "就算法的性能（求解精度和时
间复杂度）及算法实现的难易程度，给出了传统
精确算法与近似算法和混沌搜索算法的对比
分析 "
表 " 各种算法性能与算法实现的对比
算法名称 求解结果情况
时间复杂度
（所需计算步数 #$%&）
算法实现
穷举法 最优解 !（$#&）! #$%&! ’（$#$#） 很难
动态规划法 最优解 !（!$#）! #$%&! ’（"$#） 较难
最优任意时间算法 最优解 #$%&! ’（"#$#） 较难
混沌搜索算法 最优解 #$%&! ’（!$*） 较易
实例给出的问题规模较小，算法处理问题规
模为 $##或与其相近时，都有着很好的达优率 "由
于算法本身的特性，在时间足够长的条件下，能以
任意精度逼近最优解 "
! 结束语
对于组合拍卖竞胜标确定的一般问题，传统
的精确算法和近似算法存在不足，前者处理问题
的规模较小，后者得到的常是近似解或算法耗时
过多 "本文的嵌入优先适合启发式规则的混沌搜
索算法，能克服上述两点的不足 "利用混沌搜索产
生搜索路径，并根据组合拍卖竞胜标确定问题的
特性，嵌入优先适合启发式规则生成合法搜索路
径，算法具有实现方便、寻优效果好的优点 "实例
计算结果表明算法在解决该问题的有效性和广阔
的应用前景 "
参 考 文 献：
［$］+,--./01 2 3，24105 6 7，89:;1/ + 7< = >?4@1/,0?A1,: ,9>01?/ 4.>5,/1-4 ;?A ,1AB?A0 014. -:?0 ,::?>,01?/［3］< 8.:: 3?9A/,: ?; C>?D
/?41>-，$%’!，$"：*#!—*$E
［!］+?05F?B; G H，.> =，H,A-0,J + G< K?4B90,01?/,::L 4,/,M.,@:. >?4@1/,0?A1,: ,9>01?/-［3］< G,/,./0 2>1./>.，$%%&，**
（’）：$$"$—$$*E
［"］2,/J5?:4 N< =BBA?,>5.- 0? O1//.A 1/ >?4@1/,0?A1,: ,9>01?/-［3］< P.>1-1?/ 29BB?A0 -，!###，!’（$ Q !）：$(&—
$E(
［*］ R，25?5,4 S，N.//./5?:0T G< =/ =:M?A1054 ;?A G9:01D9/10 K?4@1/,0?A1,: =9>01?/-［+］< $E05 U,01?/,: K?/;.A./>. ?/
=A01;1>1,: V/0.::1M./>.，=9-01/，NW：!##$< &(—($
［&］=A/. =/--?/，G,001,- N./59/./， SMM.< V/ IA?MA,441/M ;?A K?4@1/,0?A1,: =9>01?/ Y1//.A
X?9A05 V/ K?/;.A./>. ?/ G9:01D,M./0 - IA?>..J1/M-，8?-0?/，G=：!###< "%—*(
［(］20,/ Z,/ H?.-.:，+9J?:; G1::.A < [B0141T,01?/ 1/ .:.>0A?/1> 4,-：C\,4B:.- 1/ >?4@1/,0?A1,: ,9>01?/-［3］<
（"）：!"—""
［E］2,/J?:4 N Y< =/ =:M?A1054 ;?A [B014,: Y1//.A 1/ K?4@1/,0?A1,: =9>01?/-［+］< IA?>..J1/M- ?; 21\0..05 V/
3?1/0 K?/;.A./>. ?/ =A01;1>1,: V/0.::1M./>.，20?>F5?:4，./，$%%%< &*!—&*E
［’］KHCU P1/ < =BBA?,>5.- 0? Y1//.A 1/ K?4@1/,0?A1,: =9>01?/-：= +.［+］< IA?>..J1/M- ?; V/D
K?/;.A./>. ?/ +.M1?/,: 7?M1-01>- ,/J 29BB:L K5,1/ G,/,M..4./0，25./L,/M：8,1-5,/ IA.--，!##!< !!—"#
—E!—第 &
"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
期 陈培友等：组合拍卖竞胜标确定问题的混沌搜索算法
［!］刘晓君，席酉民 " 拍卖理论与实务［#］" 北京：机械工业出版社，$%%&" ’&—’!
［&%］骆晨钟，邵惠鹤 " 采用混沌变异的进化算法［(］" 控制与决策，$%%%，（’）：’’)—’*%
［&&］张国平，王正欧，袁国林 " 求解一类组合优化问题的混沌搜索法［(］" 系统工程理论与实践，$%%&，（’）：&%$—&%’
［&$］刘秉正 " 非线性动力学与混沌基础［#］" 长春：东北师范大学出版社，&!!+" ,’—+$
［&,］玄光男，程润伟 " 遗传算法与工程设计［#］" 北京：科学出版社，$%%%" *-—)&
!"#$%&’ ()#*’" #+,$*&%"- .$* /&00)* 1)%)*-&0#%&$0 &0 ’$-2&0#%$*&#+ #3’%&$0(
!"#$ %&’()*+&，$，,-$. /’01(2&’&
& " ./0112 13 45316789:15 ./:;5/; 85< =5>:5;;6:5>，?1690;8@9;65 A5:B;6@:9C，.0;5C85> &&%%%+，D0:58；
$ " E;F8697;59 13 =/1517C 85< G68<;，H;:215>I:85> 45@9:9J9; 13 ./:;5/; 85< G;/05121>C，H86K:5 &’%%$)，D0:58
42(%*#’%：D17K:58916:82 8J/9:15@，’ 3 & 3 ，8J/9:15 L0;6; K:<<;6@ /85 K:< 15 /17K:589:15 13 :9;7@，:@ 8 B;6C :7F16M
9859 8FF2:/89:15 86;8 :5 90; ;2;/9615:/ /177;6/; 51L8<8C@ " 49 9;5<@ 91 2;8< 91 716; ;33:/:;59 8221/89:15@ 9085 968<:M
9:1582 8J/9:15@ :5 7J29:M:9;7 8J/9:15@，L0:2; N;;F:5> 6:@N@ 316 K:<<;6@ 21L" H1L;B;6，90; L:55;6 <;9;67:589:15 F61KM
2;7 :5 /17K:58916:82 8J/9:15@ :@ ?OM086<" PC 90; <;@/6:F9:15 13 90; F61K2;7 85< 8582C@:@ 13 :9@ /0868/9;6:@9:/@，90:@
F8F;6 F61F1@;@ 8 Q:99:5>MQ:6@9 0;J6:@9:/ ;7K;<<;< /0819:/ @;86/0 82>16:907" D17F86:5> 91 90; 968<:9:1582 82>16:907@，
:9 :@ ;8@C 91 1F;689; 85< /85 >;9 K;99;6 6;@J29@ " G0; 1J9/17; :5<:/89;@ 90; ;33:/:;5/C 85< 90; L:<; 8FF2:/89:15 F617:@;
13 90; 0;J6:@9:/ 82>16:907 316 @12B:5> 90:@ F61K2;7"
5)6 /$*1(：/17K:58916:82 8J/9:15；L:55;6 <;9;67:589:15 F61K2;7；3:6@9MF6:/; @;82;<MK:< 8J/9:15；/0819:/；;2;/9615M
:/ /177;6/;
—-$— 管 理 科 学 学 报 $%%,年 &%
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
月
