论文研究-序贯观察与选择问题截止阀策略的一个改进.pdf, 76系统工程理论与实践2008年2月当()=(.xgx)=0时即x=lim=时,电()取得最大值也就是说满是标准一的最优策略是截止阀t=(≈37%),能够保证选中最优选项的概率最大3.2标准二的最优策略在多次招聘的情境下,招聘者往往是保守型的决策,方面中国人的传统思维“不求有功,但求无过影响了决策的目标不是每一次都追求最好的选项,而是在尽可能完成招聘任务的前提下,追求更好的选项.也就是说,尽可能减少被迫选择最后一个应聘者的概率,使录用到应聘者的绝对名次的平均值最小.另方面,不追求单次决策的最优,而寻求多次决策的总名次均值最小也符合理性决策的要求在这一标准下,截止阀策略仍然适用,只不过截止阀的位置有了变化.可以讦明当截止阀t=[n]-1时,录用到应聘者的绝对名次的平均值最小.在证明这一结论前,先证明如下几个引理引理1当决策停止时,=1,T=s(t+1≤s≤n,1≤t≤n-1)的充要条件是:当s=n时,an=1且a1=2引理2当1≤t≤n-1,t+1≤≤n时,有=,mn{a,a2,…,a}2)当t+1≤s≤n-1时,a=1且mn{a1,证明由引理1知,当在序列未尾n取到最大值时,最大值排在未尾,次大值排在第1到第t位上,而其余n-2个可任意排列,因此在序列末尾取到最大值的排列有t(n-2)!种.当在位置s(t+1≤s≤n1)上取到最大值时,最大值排在第s位,前s-1中的最大数排在第1位到第t位上,先从n-1(大掉最大值)个数中选s-1个数排列在前s-1位置,并使最大的那个排列在第1到第t位置上,其余s-2个任意排列剩下的n-s个位置任意排列,共有Cn1(s-2)!(n-)!=(n-1)!,当S=n时1)!=t(n-2)!因此P(n-1)引理3当决策停止时,=r,T=s(1≤t≤n-1,r≠)的充要条件是1)当s=n时,an=r且a=1,1≤≤t;2)当t+1≤s≤n-1时,a=r且min{a1,a2,…,a-}=min{a,a2,…,a}≥r+1引理4当1≤t≤n-1,t+1≤s≤n,r时,有Lt,(n-2)n!(n+r+ t1证明由引理3知,当在序列末尾取到等级r时,最大值排到第1到第t位上而其余n-2个数可任意排列,因此在序列末尾取到等级r的排列共有t(n-2)!种.当在位置s(t-1≤s≤n-1)上取到等级r时,等级r排到第s位上,前s-1个数中不出现等级为1,2,…,r-1中的任何一个数,因此从n-r个数中选择s-1个数排在前s-1的位置上,将选中的s-1中最小者排在第1到第t的位置上,其余S-2个可仟意排列,最后剩下的n-s个也可任意排列,因此总共有Cnt(s-2)!(n-s)!n-r)!(n-s)!(n-s)(n+1-r-s)!种排列在这里当n-r≥s-1时,才能从n-r个数中选择s-1个数排在前s-1的位置上,而sx+1,因此n-r+1≥xt+1,即t≤n-r.故有①令V=从截止阀t后开始选择,录用到应聘者的绝对名次.T=录用应聘者时的步长②an代表第n个选项③Pn代表决策停止时选到的应聘者的绝对名次为r的概率C1994-2008ChinaAcademicjOurnalElectronicPublishingHouseAllrightsreservedhttp://www.cnki.net第2期序贯观察与选择问题截止阀策略旳一个改进77p=nn(=从Lt+1≤s≤n-r+1)①∴=0,(n-r+11n!(月-S+1其中G(s)s-1n!(n+1-r-s)!(n+1)∑1(n(s+1)s(代入(1)得E(O1(s+1)s(s-1)因为(+1)5(-1)=L31-+1-2(5-1)-5+2(5+1),所以(s+1)s(s-1)2t2(t+1)21)2t(t+1)2n(n+1)故有e(t22t(t+1)当且仅当4n=1即1=m:1时,R(达到最小也就是说截止阀:'=[Jm]-1时录月到应聘者的绝对名次的平均值最小从上述两种标准下的最优策賂求解我们发现,在不冏的冋题情境下,截止阀策略都能够适用,但是冋题情境和决策日标的不同导致截止阀值有所不同.其二,在标准二的问题情境下,决策者需要多次应用截止阀策略,其目标不是单次应用的收益最大,而是多次应用的平均吹益最大.为了达到这一目标,减少失败的概率(被迫选择最后一项的概率)较选择到最优选项的概率最大化更为重要.4截止阀策略的改进已有的截止阀策略记录截止阀前相对排序第一的选顶做为进一步选择的标竿(我们称作最大值标竿),从截上阀开始,采用超过标竿则录的原则进行决策.采用这种标竿,失败的概率它和截止阀的位置冇关.在标准二的冋题情境下,为了降低失败的慨率,是通过减少t,即提前截上阌的位置实现的.相对于标准一下的最优策略,这样的做法以减少观察的选项数量为代价换取了失败的概率地下降,进而达到多次应用的平均收益最大化然而,减少观察选项的数量就意味着减少对选项信息的了解,实际操作中,更加增加了次策的不确定性.比如,决策者面对100个应聘者时,仅仅观察了9个(t'=√100-1)就要做岀决策,心理上是难以接受的.为此,我们希望改多次应用情境下的截止阍策略,不大幅度的减少观察的①r;代表决策停上封选到的应聘者的绝对名次为,步长为s的概率01904-2008ChinaAcademicjOurnalelEctronicPublishingHouseAllrightsreservedhttp://www.cnki.net78系统工程理论与实践2008年2月选项数量,仍然能够保持较高的平均攻益.为此,换·种思路考虑问题,如图1和2所示,失败的风险主要和两个因素有关,方面和截止阀的位置有关另一方面,已和确定的标竿有关.标准二下的最优策略通过提前截上阂的位置减少失败的概率,而我们认为最大值枟竿才是失败概率高的主要因素.可以采用均值标杄的方法來改进最大值标杄的截止阀策略.只体而言,采用截止阀前部分选项打分的均值作为标杄.高失败的风险高失败的风险低后截什网亩低标杆图1截止阀对决策失败风险的影响图2标杆对决策失败风险的影响4.1收益函数按照 Bearden等的观点,我们定义更具一般性的收益函数φ(k)来度量决策结果q(k)=(1)n,其中p()=1,k是最终选项的绝对排名,n代表选项数量这样定义收益函数有三点原因,第一,假设(6)要求q(k)∈[0,1],并且q(1)=1;第二qp(1)(2)≥…(n)符合对假设(6)松弛的要求;第三,φ(n)=1/n符合现实情况,因为即便是被迫选择的选项也比没有选项的收益要高,同时n越大φ(n)越小,n→∞(n)-9采用这样的收益函数度量决策目标更加符合决策标准一情境下的决策要求.一方面,收益函数越大,代表收益越大,次策结果越伉.另一方面φ(k)分布的离散程度代表着决策收益的风险大小,离散程度越高,意味着可能出现最好(命中最优概率和最差结果(脱靶概率"的机会都大,即风险越大反之,离散程度小,意味着决策收袷有集中的趋势,即岀现最好结果和最差结果的机会都小,相应的风險乜小4.2均值标杆的截止阀策略从图1看出,已有的研究是采用提前截止阀的位置来降低决策的风险(被迫选择的概率).本研究的想法是通过降低标杄来减少次策的风险(图2).这样,可以避免提前载止阀的位置后牺牲观察选功的薮量来换取失败风险的降低.由于被选项值的离散程度不得而知,为了避免选项值的极化对标杄的影响,我们采用部分被选项的均值做为标杄.采用这样的标杄进行决策,很难确定标杄所处的相对位置,无法应用上述的古典概率方沄求得最优策略的精确位置.鉴于此,我们采用仿真实验的方法进行比较研究.我们先进行大胆的猜测,用截止阀前相对排名位于前20%的选项值的均值作为标杄,会取得更好的决策绩效.然后再采用仿真实验的方法证明这一结谂5实验本研究目的如下:在决策标准二的问题情境下,针对最大值标杄的截止阀策略,用均值标杄加以改进.鉴于均值标杄截止阀旿数理求解的困难,本硏究采用仿真实验的方法进行.一共进行两项实验,实验一证明从平玓收益和失败风险两方面看,均值祘竿的截止阀策略都优于最人值标杄的截上阀策略.实验二进步证明均值标杄中,相对排序前20%的选项的均值是最优的.采用自行开发的仿真实验平台进行实验和实验二5.1实验一实验过程如下:为了比较被选项的优劣,我们假设所有的被选项都可以按照统一的评价体系赋予一个综合的得分,这一得分代表被选项的优劣,得分越高被选项越优.这样决策的绩效度量变得简单,选中选项的分值越高,决策结果越优.这种做法见诸于人才豐选的相关研究中.我们将1,2,…,100共一百个序①命中最优概率定义为选中绝刈排序第一的选项的概率②脱靶概率定义为前n-1项均没有诜择而被迫诜择最后一项的概率.C1994-2008ChinaAcademicJournalElectronicPublishingHouse.alLrightsreservedhttp:/www.cnki.net第2期序贯观察与选择问题截止阀策略旳一个改进数随机地置乱作为测试集,其中每个整数代表个选项的综合得分,这里没有考虑得分相同,即并列的情况.策略一为最大值标杄的最优截止阅策略,即截止阀κ=9,标杄为截止阀前相对排序第一的选项值.策略弌为均值标杆的截止阀策略,即截止阀τ=3,标杄为截止阀前相对排序位于前20%的选项值的均值按照Sal& Rapoport的方法,用簧略一进行100次重复决策,记录截止阀前相对排序第一的选项做为标杄,从截上阀开始,见到优于标杄的选项则录用,如果没有优于枟杄旳选项,被迫选择第100项,记录实验的结果φ(k)φ(k2),…(k).同样,采用策略二进行100次重复决策,不同之处在于记录截止阀前相对排序位于前20%的选项值的均值做为标杆,记录实验结果φ(k1)φ3(k),…2(km)5.1.1实验结果由于没有先验的信息,为了比较两个策略的收益函数φ(k)和φ(k),只能从样本φ(k)(k),(k10)和φ(k1),φ(k2),…(k0)手.图3和图4显示φ(k)和q(k)的样本存在较大差异,因此提出偎设:H抑(k和φ(k)的分布无显著差异.1.001.000.800.800.600.600.400.200.20}000.00100图3最大值标竿策略的结果图4均值标竿策略的结果采用非参数检验 Manr whitney u方法检验假设,如表1所示,基于逼近法的显著性概率小于5%,所以拒绝原假设,即根据实验结果认为φ(k)和q3(k)的分布存在显著的差异5.1.2结果比较qp(k)和φ(k)行在显著差异,可以进一步比较两个分布的优劣,仍然通过样本的比较进行q(k)和φ(k)的描述统计量如表2所示表1分布差异假设检验表2两个样本的描述统计量统计量函数分布op(ki)p(k1)Manrr Whitney U均值0.89130.9515Wilcoxon w820.000标准差0.19670.0369616Asymp. Sig.(2-tailed)0.000方差0.03870.0014E(p(k))a{2(k)说明从函数分布的集中程度来看改进策略的收益函数分布更加集中,这意味着风险的减少,因此,函数φ2(k)对应的策略面临的风险小于函数qp(k)对应的策略即从风险规避以的角度来说,也是改进的策略更优5.2实验二实验一屮采用截止阀前相对排序位于前20%的选项值的均值做为标杄改进了最大值做为标忏的做法,从100次重复实验的平均收益和风险规避的角度看,改进后的均值截止阀策略均优于原最大值截止祤策略.前面已经提到,这种均值截上阀策略的最优解从数埋角度求解困难,因此,实验二仍然采用仿真实验C1994-2008ChinaAcademicournalElectronicPublishingHouseAllrightsreservedhttp://www.cnki.net80系统工程理论与实践2008年2月的方法证明20%是均值截止阀策咯的近似最优.现实世界中的序贯观察与选择问题均为离散事件,由于选项本身不连续,很难求得精确的最优解,同旼,精确的最优解乜不具有实际操作性.因此,本硏究采用10%的步长进行遍历求解,方面这样的步长对实际决策者而言,较为容易操作,另一方面,截止阀策略属于启发式策略,它最大的特点就在于牺牲精确性换取易用性門.因此,没有必要采用吏小的步长.在本研究中,以10%的步长进行离散事件的仿真,符合现实.由此,带来的问题是我们仅能将均值截止阀策略的最优解确定在20%拊近.基于满意决策的角度而言,这样的近似解是可以被接受的实验围绕均值标杆进行,计算均值的选项比例从最大的1个到50%,步长为10%.实验中没有考虑60%到100%的情况出于两点考虑.其一决策者有限的记忆能力不可能记下观察过的所有选项,高峰体验效应指出,决策者仅对观察过的较大的选顶留有印象.故仪考虑截止阀前柑对排序较大的一些选项.其二决策者不会将标杆定在低于平均水平的位置,那样的话,随便选择一个也有50%的机会优于平均水平,没有必要用任何策略了5.2.1实验结果根据上述的分析,实验分别采用六种均值截止阀策略进行100次重复决策,记录结果为P1(k1)P1(k2),…1(k00},{0%(k)仰1%(k2),…,AP1o%(k10)}φq2%(k1)0%(k2),…p20%(kmo)},{p30%(k1)甲o%(k2),…p%(ko)},{q%(k)卯n%(k2),…(po%(k0)},{(9s%(k1)qs%(k2),…9s%(k10)}表3六种均值戳止阀策略策略策略策略四策略二策略五策略六策略七截止阀37%37%37%37%标杆比例最大的1个1020%50%注:每种策咯都采用37%为截止阀,截止阀前一定比例桯对排序较优的选项值的均值为标杄表4六种均值截止阀策的平均收益100匚9(A)甲…()9-()(4)甲。()9(6平均收益0.80430.94850.95150.91990.89390.8726表4表明了六种均值标杆截止阀策略的平均收益.从0.960图4看出,釆用何种比例相对排序较优的选项值的均值做为标杆对决策的收益具冇显著影晌.整条收益曲线呈现倒0920U”形状.策略三(标准一情境下的最优策略)的平均收益为0.8043,是六种策略中最低的即决策标准一的最优策508略在决策标准二的情境下并非最优.主要原因是因为100次重复决策中,被迫选择最后一项的次数太多,较高的失0.8400败概率导致了平均收益的下降进一步证明了不同问题情0800境下,截止阀策略都能适用,只是策略参数需要改变.策略四的平均收益有了较大的提高,达到了0.9458.相比较策略三,策略四采用更多选项值的均值做为标杆,能够有效图5平均收益曲线减少脱靶的概率,即被迫选择的次数减◇,导致了平玓收益的提髙.策略二的平均收益是六种策略中最咼的,策略五、六、七的平均收益逐次的递减.从整条平均收益曲线看,曲线的顶点应该就在20%附近,即确定均值标杄的最优比例近似等于20%.这就证明了我们的结论,在均值标杄中,20%是确定均值标杄的近似最优比例另妒,在本硏究中,平均收益曲线在策略三到策略四阶段上升的非常快,说明用均侑标杄改进最大偵标杄(策略三是最大值标杄,策略四为均值标杆),对平均收益的贡献非常大.因此,釆用均值标杄改进截止C1994-2008ChinaAcademicJournalElectronicPublishingHouse.Allrightsreservedhttp://www.cnki.net第2期序贯观察与选择问题截止阀策略的一个改进81阀策略是有必要的.在策略四到策略二的曲线上丌缓慢,说明选项比例从10%到20%变动过程中,对平均收益提髙的贡献越来越小,即曲线即絲达到顶点,而当曲线越过策略二的位置后就开始较快的下降,也说明曲线的顶点就在20%附近6结束语截止阀策略是解决序贯观察与选择问题的有效方法.针对不同的决策标准,簑略的参数有所不同在多次应用的情境下,决策标准由单次应用中选中最优选项概率最大化变为平辶录用名次最小(平均收益最大化).目前的研究采用提前截止阀位置的方法降低失败的概率,进而提高平均益,而没有考虑到降低标杄也可以降低失败的概率.本研究从改进截止阀策略的标灯入ξ,采用均值标杄替代原有的最大值标杄.结果显示,改进后的截止阀策略具有更好的平均收益和更低的失败风险.同时,原先靠提前截止阀的位置降低失败风险会大幅减少观察选项的数量,减少了对选项信息的了解,而改进的截止阀策瑢避免了这一问题最后,采用均值标杄改进最大值标杄的截止阍策珞后,其多次应用的平均收益能够达到最大收益的95%还多符合启发式簧略牺牲一定精确性换取易用性旳原则当然,本研究还有很多不完善之处,均值标杄的截上阀策略的数理求解非常困难,研究中采用仿真实验的方法仅能求得满是条件的近似最优解.采用数理方法的精确解求解还有待进一步硏究.参考文献[1] Ferguson T S. Who solved the secretary problem? [J]. Statistical Science, 1989, 4(3): 282 -296[2] Lindley d v. dynamic programming and decision theory[J]. applied Statistics, 1961, 10: 39-513] Glbert J, Mosteller F. Recognizing the maximum of a sequence[J] Journal of the American Statistical Association, 1966, 61: 35-73.[4] Sakaguchi M. Dowry pmblems and oI a policies[r]. Reports of Stati stical Application Research, apan: Union of J apanesecientist and Engineer, 1978, 25: 124-128L 5 Lippman, Mccall. The economics of job search: A surveyLJ]. Economic Inquiry, 1976,14: 155-189[6 De Goot M H. Optimal Statistical Decisions [M]. New York: Mc Graw Hill, 1970[7] Albright S C. a bayesian approach to a generalized housing selling problem[J]. Management Science, 1977, 244): 432-440[8 Me Cardle K F. Information acquisition and the adoption of new techology[]. Management Science, 1985, 31(11): 1372[ 9] Steblay N M, Desert J, Fulero S, et al. Eyewitness accuracy rates in sequential and simultaneous lineup presentations: A metaanalytic comparison[J]. Law and Human Behavior, 2001, 25: 459-474[10] Seale DA. Rapoport A. Optimal stopping behavior with relative ranks The secretary pmblem with unknown population size[j IJournal of Behavioral Decision Making. 2000, 13(4): 391-411L11 Cowan R, Zabczyk J. An optimal selection problem associated with the poisson process [J]. Theory of Probability and ItsApplications, 1978, 23: 584-592[12 Stewart. The secretary problem with an unknown number of options[J]. Operations Research, 1981, 29: 130-145[13] Zwick R, Rapoport A. Consumer sequential search: Not enough or too much [J ]. Marketing Science, 2003, 224): 503-519[14] Bearden J N, Rapoport A, Murphy RO. Sequential observation and selection with rank dependent payoffs: An experimental study[J]. Management science,2006,9(52):1437-1449[15]李辉.一类经典“秘书问题”的推广[J].应用数学,2002,15(增):155-161.Li H. Generalization for a class of classical secretary problem[J]. Mathematica Applicata, 2002, 15(S1): 155-161[16] Seale D A, Rapoport A. Sequential decision making with relative ranks: An experimental investigation of the secretary problem[J. Organizational Behavior and Human Decision Processes, 1997, 69(3): 221-236[17 Kwan C Y, Yuan Y F. A Sequential Selection Problem[M]. Decision Sciences, 1988, 4(19): 762-771[18]KalinemanD, Sovic P, Tversky A. A judgment under uncertainty Heuristics and biases[J]. Science, 1974, 185: 1124-1131[191 Lee M D, O Conor T A, Welsh MB. Decisior making on the fullinformation secretary problem[C1/ProcecdingAnnualConferenceoftheCognitiveScienceSociety,2004,819-824.Mahwah,N:erLbaun.http://www.socsci.ucieduo1994-2008ChinaAcademicJournalElectronicPublishingHouseallrightsreservedhttp://www.cnki.net