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

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

• 批准号: 0830092
• 负责人: Marina Epelman
• 金额: $ 11.66万
• 依托单位: Regents of the University of Michigan - Ann Arbor
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-08-01 至 2011-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0830092&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.

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