ITR: Large-Scale Applications and Theory of Extremal Optimization

ITR：大规模应用和极值优化理论

• 批准号: 0312510
• 负责人: Stefan Boettcher
• 金额: $ 28.4万
• 依托单位: Emory University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-09-01 至 2007-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0312510&HistoricalAwards=false
• 关键词: ITR; Large; Scale; Applications; Theory

This award was made on a 'small' category proposal submitted in response to the ITR solicitation, NSF-02-168. The Divisions of Materials Research and Mathematics jointly fund this grant. It supports the application of the extremal optimization heuristic, developed by the PI, to hard optimization problems, ranging from the physics of disordered materials to combinatorial problems in computer science and artificial intelligence. The PI aims to (1) measure ground-state energies, entropies, and overlaps for spin glasses on networks and lattices, and (2) elucidate the order parameter at the SAT/UNSAT transition in combinatorial optimization problems. Extremal optimization has produced many results for lattice spin-glasses, and agrees with recent theoretical predictions on finite-connectivity Bethe-lattices to within 0.1%. A short-term objective is to produce numerical results for spin-glass systems to test the cutting-edge predictions of replica symmetry breaking on low-connectivity systems. Central to the research is the investigation of hybrid methods, derived from experimental and theoretical advances, which enable the study of much larger and more realistic systems. Comparative studies will educate practitioners about the potential of this approach to optimization with the hope of inspiring further applications. This project will introduce students to computational techniques and a spectrum of simulation methods in the process of experimenting with optimization problems on networks relevant for many physical and cross-disciplinary problems. Students will interact at the interface between computer science and physics, and as part of their education will conduct student research at Los Alamos National Laboratory's Computer and Computational Sciences division under an existing collaboration. Assessing the potential of this novel method in comparison with other optimization methods will afford undergraduate students in particular with a comprehensive learning experience. %%%This award was made on a 'small' category proposal submitted in response to the ITR solicitation, NSF-02-168. The Divisions of Materials Research and Mathematics jointly fund this grant. It supports research and education in the statistical mechanics of disordered systems. The PI will continue work on an optimization algorithm he developed and apply it to problems ranging from the physics of disordered materials to combinatorial problems in computer science and artificial intelligence. Successful algorithmic strategies will be applied to realistic systems, for instance, to help settle long-standing questions about three dimensional spin glasses.This project will introduce students to computational techniques and a spectrum of simulation methods in the process of experimenting with optimization problems on networks relevant for many physical and cross-disciplinary problems. Students will interact at the interface between computer science and physics, and as part of their education will conduct student research at Los Alamos National Laboratory's Computer and Computational Sciences division under an existing collaboration. Assessing the potential of this novel method in comparison with other optimization methods will afford undergraduate students in particular with a comprehensive learning experience. ***

该奖项是根据ITR招标NSF-02-168提交的“小型”类别提案而颁发的。材料研究和数学部门共同资助这项赠款。它支持由PI开发的极值优化启发式应用于硬优化问题，从无序材料的物理学到计算机科学和人工智能中的组合问题。PI的目的是（1）测量网络和晶格上自旋玻璃的基态能量，熵和重叠，（2）阐明组合优化问题中SAT/UNSAT转变的序参数。极值优化产生了许多结果的晶格自旋玻璃，并同意最近的理论预测有限连接贝特晶格在0.1%。短期目标是产生自旋玻璃系统的数值结果，以测试低连接系统上副本对称性破缺的前沿预测。研究的核心是混合方法的研究，来自实验和理论的进步，使更大和更现实的系统的研究。比较研究将教育从业者这种方法的潜力，以优化，希望能激发进一步的应用。该项目将向学生介绍计算技术和模拟方法的频谱在实验过程中与许多物理和跨学科问题相关的网络优化问题。学生将在计算机科学和物理学之间的接口进行互动，作为他们教育的一部分，他们将在洛斯阿拉莫斯国家实验室的计算机和计算科学部门进行学生研究。与其他优化方法相比，评估这种新方法的潜力将为本科生提供全面的学习经验。%此奖项是根据ITR招标NSF-02-168提交的“小型”类别提案授予的。材料研究和数学部门共同资助这项赠款。它支持无序系统统计力学的研究和教育。PI将继续研究他开发的优化算法，并将其应用于从无序材料物理到计算机科学和人工智能中的组合问题。 成功的算法策略将应用于现实系统，例如，帮助解决长期存在的关于三维自旋玻璃的问题。该项目将向学生介绍计算技术和一系列模拟方法，并在与许多物理和跨学科问题相关的网络上进行优化问题的实验。学生将在计算机科学和物理学之间的接口进行互动，作为他们教育的一部分，他们将在洛斯阿拉莫斯国家实验室的计算机和计算科学部门进行学生研究。与其他优化方法相比，评估这种新方法的潜力将为本科生提供全面的学习经验。***