The Fast and the Not-So-Frugal: Human Heuristics for Optimization Problem Solving
The Fast and the Not-So-Frugal: Human Heuristics for Optimization Problem Solving
复制标题
快速且不那么节俭：解决优化问题的人类启发法
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
T. Ormerod
中科院分区：
文献类型：
--
作者：
Genovefa Kefalidou;T. Ormerod
Genovefa Kefalidou@nottingham.ac.uk)Horizon数字经济研究/人为因素研究小组，诺丁汉大学，创新园区，凯旋路，诺丁汉，NG7 2TU，英国Thomas C.Ormerod(t.ormerod@surrey.ac.uk)萨里大学心理学系，吉尔福德，萨里，GU2 7XH，英国摘要在这篇论文中，人类启发式方法被确定为在解决有能力的车辆路径问题(CVRPs)时提供接近最优解决方案。以前的实验结果表明，人类可以相对较快地得出好的解决方案，与基于计算机的方法竞争，这进一步支持了以前对旅行商问题(TSP)的研究。进行了多元回归分析，以显示参与者采用的最佳启发式，并导致更好的CVRP解决方案。识别的启发式方法分为视觉空间启发式方法和算术启发式方法。视觉空间启发式(例如，集群、锚定)比算术(例如，平衡)执行得更好。策略切换似乎是CVRP解决方案中的关键一步，这表明采用的启发式方法既快速又不那么节俭，这是对快速而节俭的工具包的赞扬。根据问题解决理论和最佳人类启发式如何为当前用于优化问题解决的最先进的计算算法提供信息，对结果进行了讨论。关键词：最优化；问题求解；弱方法；快速节俭启发式；有能力的车辆路径问题。弱方法方法(即手段-目的分析和爬山)，人们根据朝着问题目标取得的进展来选择解决方案，并倾向于产生令人满意但次优的解决方案。吉格伦泽的“快速节俭”启发式建立在纽威尔和西蒙的理论基础上，认知努力程度较低(吉格伦泽和戈尔茨坦，1996)。快速而节俭的启发式算法旨在通过利用任务环境的特征来解释人类在一系列看似计算困难的任务中近乎完美的表现，但不需要确定这一类别下的任何特定启发式算法。虽然“令人满意”的启发式方法适用于对可用替代方案的顺序搜索，但“快速而节俭”的启发式方法只需要很少的信息和计算资源就可以做出不同的决定(Gigerenzer，Todd&ABC Research Group，1999)。本文报告的研究旨在洞察启发式算法在解决复杂而广泛应用的问题中的作用，并确定它们的性质和性质。图1：这是一个数字。引言发展问题解决理论的一个关键问题是确定在解决复杂问题时采用的人类启发式。这类问题的一个例子是有能力的车辆路径问题(CVRP)，这是一个困难的优化问题，其中必须从一组太大的候选解中找到最优解，而不允许进行穷举搜索。在CVRP中，人们必须发现一辆容量有限的车辆从一个或多个仓库向分布在欧几里得空间(图1)中的客户(表示为节点)交付的多条最短路线。每个站点(节点)只能访问一次，并且车辆不得超过每条路线的重量限制(在图1中为100)。存在求解CVRP的计算算法，每种算法都有局限性(即无法处理动态环境或局部最优-Michalewicz&Fogel(2002))。因此，CVRP具有相当大的现实意义(例如，在运输和物流中)和理论上的重要性，因为它们为研究问题的复杂性和启发式方法提供了一个很好的试验台。有关问题解决和有限理性的心理学理论包括Newell和Simon(1972)，图1：CVRP39-6问题的最优解。在解决优化问题时使用人类启发式方法有两个原因：一是通过了解人们如何获得好的解决方案来推动问题解决理论的进步；二是为计算算法提供信息。McGregor&Ormerod(1996)研究了旅行商问题(TSP)的图解-类似于没有重量限制和多条路线的CVRP-发现，对于多达100个节点的问题，人类的解决方案与启发式计算机方法相当。他们认为，解决方案是由凸壳边界的概念化指导的，这与人类视觉中对自然对象边界的检测(例如Marr，1980)一致，从全局边界移动到
The Fast and the Not-So-Frugal: Human Heuristics for Optimization Problem Solving Genovefa Kefalidou (Genovefa.Kefalidou@nottingham.ac.uk) Horizon Digital Economy Research / Human Factors Research Group, The University of Nottingham, Innovation Park, Triumph Road, Nottingham, NG7 2TU, UK Thomas C. Ormerod (t.ormerod@surrey.ac.uk) Department of Psychology, University of Surrey, Guildford, Surrey, GU2 7XH, UK Abstract In this paper, human heuristics have been identified that provide close to optimal solutions when solving Capacitated Vehicle Routing Problems (CVRPs). Results from previous experiments showed humans can produce good solutions relatively fast that compete with computer-based methods giving further support to previous research on Traveling Salesman Problems (TSPs). Multiple Regression analyses have been conducted to show the best heuristics adopted by participants and that lead to better CVRP solutions. Identified heuristics are categorized in visuospatial and arithmetic heuristics. Visuospatial heuristics (e.g. Clustering, Anchoring) performed better than the arithmetic (e.g. Balancing). Strategy switching appears to be a critical step within CVRP solutions suggesting that heuristics adopted are fast yet not- so-frugal, complimenting the fast and frugal toolkit. Results are discussed under the light of problem-solving theories and in terms of how best human heuristics can inform the current state-of-art computational algorithms used in optimization problem solving. Keywords: optimization; problem solving; weak methods; fast and frugal heuristics; capacitated vehicle routing problems. weak methods approach (i.e. means-ends analysis and hill- climbing) where people select solution attempts according to the progress made towards the problem goal, and which tend to produce satisfactory but sub-optimal solutions. Gigerenzer’s ‘fast and frugal’ heuristics, build upon Newell and Simon’s theories and are of low cognitive effort (Gigerenzer & Goldstein, 1996). Fast and frugal heuristics aim to explain near-perfect performance by humans on a range of seemingly computationally intractable tasks by capitalizing upon the characteristics of the task environment, without, however, determining any specific heuristics under this category. While ‘satisficing’ heuristics apply sequential searching for available alternatives, ‘fast and frugal’ heuristics necessitate little information and computational resources in order to make different decisions (Gigerenzer, Todd & ABC Research Group, 1999). The research reported in this paper aims to offer an insight as to what heuristics are involved in solving hard yet widely applied problems such as CVRPs and identify their nature and qualities. Figure 1: This is a figure. Introduction A key issue in developing problem-solving theories is to identify human heuristics adopted when solving complex problems. An example of such problems are the Capacitated Vehicle Routing Problems (CVRPs), which are hard optimization problems, where the best solution must be discovered from a set of candidate solutions too large to allow exhaustive search. In CVRPs, one has to discover a number of shortest routes taken by a capacity-limited vehicle from one or more depots to deliver to customers (represented as nodes) distributed in Euclidean space (Figure 1). Each station (node) must be visited once only and the vehicle must not exceed a weight limit (in Figure 1, it is 100) for each route. Computational algorithms exist for solving CVRPs each of which maintain limitations (i.e. unable to tackle with dynamic environments or local optimum - Michalewicz & Fogel (2002)). Consequently, CVRPs have considerable practical importance (e.g., in transportation and logistics) and theoretical importance as they provide an excellent testbed to investigate problem complexity and heuristics. Relevant psychological theories of problem-solving and bounded rationality include Newell and Simon’s (1972) Figure 1: The optimal solution of a CVRP 39-6 problem. Human heuristics employed when solving optimization problems are of interest for two reasons: for furthering the progress of problem-solving theories by understanding how people arrive at good solutions and for informing computational algorithms. McGregor & Ormerod (1996) examined drawn solutions to Traveling Salesman Problems (TSPs) – similar to CVRPs without weight constraints and multiple routes – and found that, with problems of up to 100 nodes, human solutions were comparable with heuristic computer methods. They suggested that solutions are guided by the conceptualization of a convex-hull boundary, which coincides with the detection of natural object boundaries in human vision (e.g., Marr, 1980), moving from a global to a