Collaborative Research : Approximate Fictitious Play for the Optimization of Complex Systems

协作研究:复杂系统优化的近似虚拟游戏

• 批准号: 0830380
• 负责人: Archis Ghate
• 金额: $ 8.34万
• 依托单位: University of Washington
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-08-01 至 2011-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0830380&HistoricalAwards=false
• 关键词: Collaborative; Research; Approximate; Fictitious; Play

The prevalence of advanced computing technology has resulted in increasingly complex simulation models of manufacturing, telecommunication, logistic, transportation, supply chain and other engineering systems. Such models often lack mathematical properties that have traditionally been essential to the development of efficient computational procedures for determining an optimal system design. Consequently, the need arises to develop new optimization algorithms that remain efficient even in the absence of simplifying mathematical structures. This research investigates the analytical and practical potential of computationally efficient variants of Fictitious Play (FP), an iterative technique from the mathematical theory of learning, as an optimization paradigm to achieve this goal. The key idea is to model the optimization problem as a game of common interest between artificial "players" that correspond to components of a carefully chosen partition of the design variables. The shared interest of these players is to optimize the metric of system performance. Theoretical justification for this approach is rooted in the well-known fact that for games of common interest, limit points of FP are Nash equilibria and thus may be viewed as a type of local optimum. The research builds on the investigators' earlier work on Sampled Fictitious Play (SFP), a modification that replaces the exceptionally demanding expected utility calculations in FP with their sampled approximations while still preserving FP's theoretical properties. The work will culminate in a powerful and rigorous suite of algorithms the investigators term Approximate Fictitious Play (AFP), where the "players" interact with one another by calculating a best response to a sample of strategies independently and adaptively chosen from a probability distribution over their history of past best responses. A major computational benefit of AFP is that the best response subproblems are embedded in and significantly smaller than the original optimization problem, leading to a dramatic increase in efficiency compared to finding jointly optimal strategies. Traditionally, simulation models of complex systems have been employed as descriptive tools to test "rule-of-thumb" alternatives suggested by a knowledgeable user. The AFP paradigm promises to make these models prescriptive as its convergence and optimality properties do not rely on regularity conditions that such systems and models are unlikely to exhibit.

先进计算技术的普及导致了制造业、电信、物流、运输、供应链等工程系统的仿真模型日益复杂。这类模型往往缺乏传统上对开发确定最佳系统设计的有效计算程序所必需的数学特性。因此，需要开发新的优化算法，即使在没有简化数学结构的情况下也保持高效。这项研究调查了虚拟游戏(FP)的计算效率变体作为实现这一目标的优化范式的分析和实践潜力。FP是一种来自数学学习理论的迭代技术。其关键思想是将优化问题建模为人造“玩家”之间共同感兴趣的博弈，这些博弈对应于精心选择的设计变量分区的组件。这些参与者的共同兴趣是优化系统性能的衡量标准。这种方法的理论证明植根于一个众所周知的事实，即对于共同利益的博弈，FP的极限点是纳什均衡，因此可以被视为一种局部最优。这项研究建立在研究人员早期对采样虚拟游戏(SFP)的工作基础上，SFP是一种修改，用采样近似取代FP中异常苛刻的预期效用计算，同时仍保留FP的理论性质。这项工作将最终形成一套强大而严格的算法，研究人员将其称为近似虚构游戏(AFP)，在该算法中，“玩家”通过独立地、自适应地从他们过去最佳响应历史的概率分布中选择一组策略样本，计算出最佳响应，从而相互作用。AFP的一个主要计算优势是，最佳响应子问题被嵌入到原始优化问题中，并且比原始优化问题小得多，导致与寻找联合最优策略相比，效率显著提高。传统上，复杂系统的仿真模型被用作描述性工具来测试由知识渊博的用户提出的“经验法则”备选方案。AFP范式承诺使这些模型具有规范性，因为它的收敛和最优化特性不依赖于这些系统和模型不太可能表现出的规律性条件。