在约束编程解决器中学习和微调通用值选择启发式
Tom Marty1,2,3, Léo Boisvert1, Tristan François2
1Polytechnique Montréal, Montreal, Canada.
概括
本研究引入了一种机器学习方法,用于自动学习约束编程解决者的值选择启发式,减少对专家知识的需求,提高解决复杂组合问题的效率.
科学领域:
- 人工智能的人工智能
- 运营研究 运营研究
- 计算机科学 计算机科学
背景情况:
- 约束编程 (CP) 对于组合式问题是有效的,分支启发式对解决器效率至关重要.
- 开发专门的启发式需要大量的时间和特定问题的专业知识.
- 现有的通用变量选择启发式比值选择启发式多得多.
研究的目的:
- 开发一种通用的机器学习程序,用于在CP解决器中自动学习值选择启发式.
- 为了解决价值选择启发式生成的自动化方法的稀缺性.
主要方法:
- 采用深度Q学习算法与量身定制的奖励信号相结合.
- 使用异质图形神经网络来学习启发式.
- 在图形着色,最大独立集合,最大切割和最小顶点覆盖问题上测试了框架.
主要成果:
- 学习值选择启发式证明了与已建立的基于影响和基于活动的启发式相比的竞争性表现.
- 该框架成功地找到了近乎最佳的解决方案,并且回溯时间最小.
- 在不同问题类上微调模型可以加速学习过程.
结论:
- 拟议的深度Q学习框架提供了一种有效的,自动化的方法来生成CP的值选择启发式.
- 这种方法减少了对专家知识的依赖,并提高了在各种组合问题的解决者性能.
- 通过微调转移学习显示出更快地适应新问题领域的希望.
更多相关视频
07:05Operant Protocols for Assessing the Cost-benefit Analysis During Reinforced Decision Making by Rodents
Published on: September 10, 2018
5.9K
11:53Spatial Multiobjective Optimization of Agricultural Conservation Practices using a SWAT Model and an Evolutionary Algorithm
Published on: December 9, 2012
12.9K
相关概念视频
Decision Making: P-value Method
5.3K
The process of hypothesis testing based on the P-value method includes calculating the P- value using the sample data and interpreting it.
First, a specific claim about the population parameter is proposed. The claim is based on the research question and is stated in a simple form. Further, an opposing statement to the claim is also stated. These statements can act as null and alternative hypotheses: a null hypothesis would be a neutral statement while the alternative hypothesis can...
First, a specific claim about the population parameter is proposed. The claim is based on the research question and is stated in a simple form. Further, an opposing statement to the claim is also stated. These statements can act as null and alternative hypotheses: a null hypothesis would be a neutral statement while the alternative hypothesis can...
5.3K
Constraints and Statical Determinacy
572
In structural engineering, the equilibrium of a system is not only determined by its equations of equilibrium but also with the help of constraints. Constraints refer to restrictions on the motion of a system. The proper combinations of constraints can minimize the total number of constraints needed to maintain a system in mechanical equilibrium. When this happens, the system is said to be statically determinate. For such systems, the unknown reaction supports can be estimated using equilibrium...
572
Statically Indeterminate Problem Solving
358
Statically indeterminate problems are those where statics alone can not determine the internal forces or reactions. Consider a structure comprising two cylindrical rods made of steel and brass. These rods are joined at point B and restrained by rigid supports at points A and C. Now, the reactions at points A and C and the deflection at point B are to be determined. This rod structure is classified as statically indeterminate as the structure has more supports than are necessary for maintaining...
358
Heuristics
70
Heuristics are problem-solving strategies that use mental shortcuts to simplify decision-making. Unlike algorithms, which must be followed precisely to achieve a correct result, heuristics offer a general problem-solving framework. They save time and energy but can sometimes lead to less rational decisions.
People often rely on heuristics when faced with an overload of information, limited time, low importance of the decision, limited information, or when a heuristic readily comes to mind. For...
People often rely on heuristics when faced with an overload of information, limited time, low importance of the decision, limited information, or when a heuristic readily comes to mind. For...
70
The Anchoring-and-Adjustment Heuristic
7.2K
In order to make good decisions, we use our knowledge and our reasoning. Often, this knowledge and reasoning is sound and solid. However, sometimes, we are swayed by biases or by others manipulating a situation. For example, let’s say you and three friends wanted to rent a house and had a combined target budget of $1,600. The realtor shows you only very run-down houses for $1,600 and then shows you a very nice house for $2,000. Might you ask each person to pay more in rent to get the...
7.2K
Stability of Equilibrium Configuration: Problem Solving
573
The stability of equilibrium configurations is an important concept in physics, engineering, and other related fields. In simple terms, it refers to the tendency of an object or system to return to its equilibrium position after being disturbed. The stability of an equilibrium configuration can be analyzed by considering the potential energy function of the system and examining its behavior near the equilibrium point.
Problem-solving in the context of the stability of equilibrium configuration...
Problem-solving in the context of the stability of equilibrium configuration...
573
