Mechanistic heuristic problem solving and heuristic search algorithms that exploit phase transitions and backbones

利用相变和主干的机械启发式问题解决和启发式搜索算法

• 批准号: 0535257
• 负责人: Weixiong Zhang
• 金额: --
• 依托单位: Washington University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-11-01 至 2009-10-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0535257&HistoricalAwards=false
• 关键词: Mechanistic; heuristic; problem; solving; search

This project studies general purpose heuristic problem solving through development of (1) efficient strategies and algorithms for solving combinatorial optimization problems, and (2) effective methods for exploiting intrinsic problem features of phase transitions and "backbones" -- that is, variables that need to be fixed among all optimal solutions -- to solve these problems. The general approach of this project is to mechanize problem solving using mathematical means. Each of the two research thrusts of the project involves several subtopics. The first thrust is to develop a general approach to heuristic problem solving that involves a new set of methods for automatically developing heuristic strategies and search algorithms. It employs a representation scheme using a constraint programming paradigm, a set of constraint manipulation methods for deriving heuristic functions, and a learning scheme to automatically determine the 'right' combination of heuristic functions and search methods for a given problem. The second thrust focuses on utilizing intrinsic problem features, particularly phase transitions and backbones. The project plans to consider a variety of problems, including combinatorial optimization problems (e.g., the Traveling Salesman Problem), constraint optimization problems (e.g., scheduling and resource allocation), and complex optimization problems in computational biology (e.g., sequence alignment and haplotype inferencing). The results of this research could have a very broad impact in computer science and beyond (e.g., operations research, computational molecular biology) due to the great variety of problems that can be approached through heuristic search and combinatorial optimization.

本项目通过开发(1)解决组合优化问题的有效策略和算法，以及(2)利用相变和“骨干”（即需要在所有最优解中固定的变量）的内在问题特征来解决这些问题的有效方法，研究通用启发式问题解决。这个项目的一般方法是用数学方法机械化地解决问题。该项目的两个研究重点中的每一个都涉及几个子主题。第一个重点是开发一种启发式问题解决的通用方法，该方法涉及一组用于自动开发启发式策略和搜索算法的新方法。它采用一种使用约束编程范例的表示方案，一套用于派生启发式函数的约束操作方法，以及一种用于自动确定启发式函数和给定问题搜索方法的“正确”组合的学习方案。第二个重点是利用问题的内在特征，特别是相变和主干。该项目计划考虑各种问题，包括组合优化问题（如旅行推销员问题），约束优化问题（如调度和资源分配），以及计算生物学中的复杂优化问题（如序列比对和单倍型推断）。这项研究的结果可能会对计算机科学和其他领域（例如运筹学，计算分子生物学）产生非常广泛的影响，因为可以通过启发式搜索和组合优化来解决各种各样的问题。