Collaborative Research: Complex Networks Optimization

合作研究：复杂网络优化

• 批准号: 0217371
• 负责人: Alfredo Garcia
• 金额: $ 6.8万
• 依托单位: University of Virginia Main Campus
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2002
• 资助国家: 美国
• 起止时间: 2002-09-01 至 2005-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0217371&HistoricalAwards=false
• 关键词: Collaborative; Research; Complex; Networks; Optimization

This research project will study optimization algorithms rooted in the ideas of game theory in the context of complex network optimization, and particularly decentralized network optimization. Probably the central issue in managing such decentralized networks has been how to set prices so as to motivate the competing users to evolve to an overall system optimal configuration. The research will investigate the powerful paradigm of economic competition in the framework of artificial dynamic games that are played off-line, resulting in an algorithm that is potentially practical for large-scale systems optimization. The basic paradigm that will be investigated derives from Fictitious Play which is an adaptive procedure wherein each player assumes that other players will play according to the empirical distribution of their previous plays. The Fictitious Play method is a novel paradigm for optimization that draws from several distinct disciplines and application areas, including classical optimization, game theory, transportation science, and queueing network protocols. The robust nature of the algorithm allows for the ill-structured black box models of real systems which seldom exhibit the kind of smoothness properties that classical optimization methods demand. Its applicability in the context of two important real-world systems: a) internet traffic routing protocols and b) dynamic route guidance will be tested. Complex networks optimization is an important capability in a society increasingly dominated by ever more complex networks of people and machines. Examples include intelligent transportation systems, computer networks, and supply chains of customers and suppliers. The success of the research will lead to the development of a theoretical basis for the optimization of such complex-structured systems. The applicability of the proposed algorithmic paradigm of game theory through its application to realistic problems arising in the design and operation of the communications and transportation networks will be tested and refined. This research will not only lead to potential improvements in these application arenas but will also necessitate significant interactions with industry and government to insure realism for the models and data developed.

该研究项目将在复杂网络优化，特别是去中心化网络优化的背景下研究植根于博弈论思想的优化算法。管理这种去中心化网络的核心问题可能是如何设定价格，以激励竞争用户进化到整个系统的最佳配置。该研究将在离线进行的人工动态博弈框架内研究经济竞争的强大范式，从而产生一种对大规模系统优化具有潜在实用性的算法。将要研究的基本范式源自虚拟游戏，这是一种自适应过程，其中每个玩家假设其他玩家将根据他们之前的游戏的经验分布进行游戏。虚拟游戏方法是一种新颖的优化范例，它借鉴了几个不同的学科和应用领域，包括经典优化、博弈论、运输科学和排队网络协议。该算法的鲁棒性允许真实系统的结构不良的黑盒模型，这些模型很少表现出经典优化方法所需的平滑特性。它将测试其在两个重要的现实世界系统中的适用性：a）互联网流量路由协议和b）动态路线引导。在一个日益由更加复杂的人和机器网络主导的社会中，复杂网络优化是一项重要能力。例子包括智能交通系统、计算机网络以及客户和供应商的供应链。该研究的成功将为此类复杂结构系统的优化奠定理论基础。所提出的博弈论算法范式的适用性将通过其应用于通信和运输网络设计和运营中出现的实际问题来进行测试和完善。这项研究不仅会带来这些应用领域的潜在改进，而且还需要与行业和政府进行大量互动，以确保所开发的模型和数据的真实性。