排序择优算法中的三个问题研究

论文摘要

排序择优算法是仿真与模拟领域中一种重要的随机运筹优化的求解方法。特别是在一些现实问题中,可能会遇到难以构建理论模型或无法求得解析解等情形,往往可以使用排序择优算法求解。一般而言,排序择优算法有两种最基本的思路,分别是频率法和贝叶斯法。虽然二者都以求得最优解为核心目的,但二者所追求的目标并不相同。频率法的目标是要确保选择最优解的概率达到要求,强调正确性;而贝叶斯法的目标是当总样本量给定时,通过有效的样本分配方式来最大化选择最优解的概率,强调效率。在大多数情况下,频率法的效率会比贝叶斯法稍低,即需要更多的样本量来达到相同的选择正确率。因此,提升频率法的效率一直是排序择优算法领域一个重要的研究问题。在本论文中,我们分别在第二章和第三章中提出了两种提升频率法算法效率的方法。此外,利用排序择优算法求解实际问题,将理论与现实有机结合,也是值得深入探索的研究方向之一。在第四章中,我们将排序择优算法运用在一个共享单车运营体系中,以求解最优的消费者激励计划,来帮助运营者提升共享单车系统的收益和消费者服务水平。在第二章中,我们提出了一种计算合理初始样本量的方法,从而提升频率法算法效率。在一些频率算法中,例如KN算法（Kim and Nelson（2001））和Rinott算法（Rinott（1978））,因为各个系统的方差是未知的,所以需要先获得一些样本来估计样本方差,这些样本就被称为初始样本。通过分析我们发现,因为通过初始样本估计的样本方差在算法运行过程中不会更新,所以初始样本的选取将会直接影响算法总样本数量。若初始样本量过少,样本方差估计的不准确性会增大,从而提升算法总样本量;若初始样本量过多,可能会造成初始样本量大于最终所需样本量的情况,同样也会造成样本浪费。为了选取合适的初始样本量,我们首先建立了初始样本量和总样本量之间的函数关系。通过求解使得总样本量最小的优化问题,我们提出了选择合适的初始样本量的算法。为了验证该算法的有效性,我们将该算法与KN算法相结合,提出了KN-ISS算法。通过大量数值实验分析表明,KN-ISS算法较KN算法效率提升明显,总样本量可减少30%-50%。同时,KN-ISS算法可以适用于多种不同的均值和方差的参数设置,并且均可以达到要求的选择正确率。讨论了初始样本量的选择方法之后,一个自然而然的延伸是考虑在算法运行过程中,应该如何设定合适的样本分配策略。在第三章中,我们提出了一种非均衡的样本分配策略,该策略不仅可以保证选择最优解的正确率,还可以有效提升算法效率。在频率法中,因为在算法运行过程中不会更新各个系统的样本方差,所以大多数频率法算法会使用均衡样本分配策略,即不同的系统所获得的样本分配数量是相同的,这种样本分配策略也便于证明算法的统计有效性。但是在大多数贝叶斯法算法中,因为会在算法运行过程中不断更新各个系统的样本均值和样本方差,所以会使用非均衡的样本分配策略。在贝叶斯法算法的分配策略中,往往会分配更多的样本给更有可能成为最优解的系统,以此加快选择的速度,提升算法效率。Jennison et al.（1980）和Jennison et al.（1982）认为可以将贝叶斯法中的样本分配思路运用在频率法算法中,并提出了一种非均衡的样本分配策略,但是该策略仅适用于所有系统的方差虽然未知但却相同的情形。Hong（2010）将Jennison et al.（1980）和Jennison et al.（1982）的结论推广到各个系统方差未知且不相同的情形,他提出可以构建一个使得任意两个系统样本量之和最小的优化模型,以求解非均衡的样本分配策略。受他们的启发,我们提出可以通过求解一个使所有系统总样本量最小化的优化问题,来求解非均衡的样本分配策略,并证明了我们提出的样本分配策略具有渐进统计有效性。在该样本分配策略中,首先会求解一个使得所有系统总样本量最小的优化模型,利用该求解结果构建一个基于样本均值、样本方差和样本量的参数指标。在算法运行过程中,会不断更新样本均值和样本方差,从而更新参数指标,再依据该参数指标的大小进行样本的分配。我们也通过数值实验发现,该样本分配策略可以有效提升频率法算法的效率并且能够保证选择最优解的正确率。我们提出的算法相较于KN算法、UVP算法（Hong（2010））等频率法算法,总样本量减少40%-60%。在相同样本量的情况下,较贝叶斯法的算法中具有代表性的OCBA算法（Chen et al.（2000））选择正确率提升10%-20%。除了提升频率法算法的效率外,我们也将排序择优算法运用在实际问题中,希望达到理论和实际相结合的目的。在第四章中,我们分析了一个随意停放式共享单车系统中的再分配问题。随意停放式共享单车是最近兴起的一种基于资源共享的交通方式。因为消费者归还车辆时没有停车点停放数量的限制,会放大不同停车点之间消费者需求的不稳定性和不对称性,使得不同停车点的资源分配高度不均衡。这样一方面会阻塞交通,侵占公共资源,另一方面也会使得某些点位无车,降低了消费者服务水平和共享单车系统的运营效率。我们提出了一种基于消费者激励计划的共享单车再分配策略:运营者通过给予消费者激励,引导消费者更换目的地,从而达到共享单车再分配的目标。我们的核心研究问题是如何设置最优的激励金额,一方面可以使得共享单车系统的消费者服务水平达到要求,另一方面也可以提升运营者的收益。在研究该问题时我们发现,共享单车运营者往往会缺乏消费者类型、目的地、骑行时间、到达速率等数据,特别是当进入一个新市场时数据会更加缺乏。虽然从理论角度而言,可以使用鲁棒优化模型来求解有限信息下的优化问题。但在本研究中,共享单车运营体系较为复杂,停车点位数量较多,各类信息高度匮乏,并且需要满足给定的服务水平,属于有约束的随机优化问题,无论是模型构建还是求解析解都存在挑战。因此,我们构建了基于排序择优算法的优化模型,提出了相应的求解算法,通过仿真和模拟的方式求解。该方法还可以用于其他产品进入新市场时的定价问题。通过大量数值试验表明,（1）通过该算法选择的激励方案一方面可以帮助运营者达到事先设定的服务水平,另一方面也可以提升共享单车系统运营效率,增加运营者收益;（2）该算法可以适用于多种不同的情形;（3）在大多数情形下,该算法都可以在一个合理的样本量范围内选择最优策略。

论文目录

• 摘要
• ABSTRACT
• Table of Abbreviations and Meanings
• Chapter 1 Introduction
•   1.1 Research Background
•   1.2 Thesis Organization
• Chapter 2 Algorithm for Initial Sample Size
•   2.1 Introduction
•   2.2 Problem Formulation
•   2.3 Algorithm for Calculating the Initial Sample Size
•     2.3.1 Analysis of Initial Sample Size
•     2.3.2 Theoretical Calculation of Total Sample Size
•     2.3.3 Discussion about All Alternatives Scenario
•     2.3.4 Algorithm for Calculating the Initial Sample Size
•     2.3.5 Comparison with Paulson and Hartmann’s Methods
•   2.4 KN-ISS Procedure
•   2.5 Numerical Experiments
•     2.5.1 Statistical Validity Check
•     2.5.2 Efficiency of KN-ISS
•     2.5.3 Initial Sample Size
•   2.6 Conclusion
• Chapter 3 Optimal Sampling Rule
•   3.1 Introduction
•   3.2 The Comparison Statistics
•   3.3 The Optimal Sampling Rule
•   3.4 The Asymptotic Statistical Validity
•     3.4.1 Construction of Brownian Motion Process
•   3.5 Numerical Results
•     3.5.1 Validity Check
•     3.5.2 The Efficiency of FSP
•     3.5.3 Comparison with OCBA
•   3.6 Application: Ambulance Dispatch Problem
•   3.7 Conclusion
• Chapter 4 Customer Incentive Rebalancing Plan
•   4.1 Introduction
•   4.2 Literature Review
•   4.3 Model Formulation
•     4.3.1 Network Model: Operational Process and Incentive Plan
•     4.3.2 The Stochastic Optimization Model
•   4.4 Procedures for Optimization Based on R&S
•   4.5 Numerical Investigations
•     4.5.1 Parameter Settings
•     4.5.2 Numerical Results
•     4.5.3 Discussions on the Numerical Results
•     4.5.4 Extensions
•   4.6 Conclusion
• Chapter 5 Conclusion
• Appendix A Benchmark Procedures in the Literature
•   A.1 KN Procedure
•   A.2 UVP Procedure
• Bibliography
• Acknowledgements
• Publications
• Projects

文章来源

类型: 博士论文

作者: 吴瑞璟

导师: 刘少轩

关键词: 排序择优算法,频率法,初始样本量,样本分配策略

来源: 上海交通大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 上海交通大学

分类号: O223

DOI: 10.27307/d.cnki.gsjtu.2019.000026

总页数: 125

文件大小: 2351K

下载量: 28