p-Median and p-dispersion problems: A bi-criteria analysis

Given a collection of n locations and a symmetric measure of distance (difference) between each pair of locations, we seek to identify (select) a subset of p locations so as to achieve two distinct objectives. The first objective is to use the selected locations as centers (medians) of p groups that would partition the entire collection and minimize the total distance between the locations and their respective group medians. The second objective is to maximize the minimum distance (diversity) among the selected locations themselves. We study this problem as a multi-objective optimization problem and propose an iterative algorithm to obtain its non-dominated frontier. At each iteration we construct and solve a 0–1 integer programming problem. Through a computational experiment we show that this algorithm is computationally effective for small to medium size instances of the problem. We also propose a Lagrangian heuristic algorithm for solving larger instances of this problem.     

货郎担问题最优并行启发式算法

本文给出了满足三角不等式的货郎担问题的并行启发式算法，在ＳＩＭＤ ＣＲＥＶ ＰＲＡＭ并行机上该算法使用Ｏ（ｎ＾３／ｌｏｇ＾２ｎ）台处理器需Ｏ熄ｌｏｇ＾２ｎ）时间，这里ｎ是给定城市的个数，因而该并行算法是最优的。     

Capacitated Clustering Problems by Hybrid Simulated Annealing and Tabu Search

The capacitated clustering problem (CCP) is the problem in which a given set of weighted objects is to be partitioned into clusters so that the total weight of objects in each cluster is less than a given value (cluster ‘capacity’). The objective is to minimize the total scatter of objects from the ‘centre’ of the cluster to which they have been allocated. A simple constructive heuristic, a R-interchange generation mechanism, a hybrid simulated annealing (SA) and tabu search (TS) algorithm which has computationally desirable features using a new non-monotonic cooling schedule, are developed. A classification of the existing SA cooling schedules is presented. The effects on the final solution quality of the initial solutions, the cooling schedule parameters and the neighbourhood search strategies are investigated. Computational results on randomly generated problems with size ranging from 50 to 100 customers indicate that the hybrid SA/TS algorithm out-performs previous simulated annealing algorithms, a simple tabu search and local descent algorithms.     

广义AND／OR图的自底向上的启发式搜索算法BHAO

本文首先根据三角模概念，定义了一类新的更具普遍意义的广义ＡＮＤ／ＯＲ图．根据新定义的启发式函数ｈ（ｎ，ｘ）以及广义ＡＮＤ／ＯＲ图的最佳解树之所有子树亦是最佳子解树的原理，提出了广义ＡＮＤ／ＯＲ图的自底向上的启发式搜索算法ＢＨＡＯ．文中证明了算法ＢＨＡＯ的可采纳性．本文还提出了两类新的启发式函数的单调限制概念，并据此研究了算法ＢＨＡＯ的单调限制性质，研究了两个ＢＨＡＯ算法间的比较性质．     

On-Line Shape recognition with incremental training using binary synaptic weights algorithm

Recognition of hand drawn shapes is beneficial in drawing packages and automated sketch entry in handheld computers. In this paper, we propose a new approach to on-line geometric shape recognition with incremental training function, which utilizes a heuristic function to reduce noise and a neural network for classification and on-line training. Instead of recognizing segments of a drawing and then performing syntactical analysis to match with a predefined shape, which is weak in terms of generalization and dealing with noise, we examine the shape as a whole. The main concept of the recognition method is derived from the fact that internal angles are very important in the perceived shape of outlines. Our application's aim is to recognize elliptic, rectangular, and triangular shapes in a way similar to human cognition of these shapes. Human beings recognize such basic shapes regardless of the variations in size, noise on the shape border, rotation and in the case of triangles, regardless of the type of the triangle. The key concept is that the neural network learns the relationships between the internal angles of a shape and its classification, therefore only a few training samples which represent the class of the shape are sufficient. Fast meremental training, which is performed on-line, is accomplished by the use of the Binary Synaptic Weights algorithm, a one pass, feedforward neural network training algorithm. Incremental training offers the advantage of adjusting the recognition capability of the system to the user's drawings. the results are very successful, such that the neural network correctly classified shapes that did not have any resemblance to the shapes in the initial training set.     

基于启发式规则优化的网页元素提取方法

网页信息提取方法中的启发式规则,是识别网页标签信息、利用网页节点分析结果、针对网页不同内容、完成信息提取的重要手段。本研究在对现有启发式规则进行研究分析的基础上,提出了几种优化的启发式规则,实现对网页标题、发布时间、来源以及正文内容等元素信息的精准提取。本研究进一步提出了运用编辑距离算法实现正文内容提取准确率的判定,并提出阙值优化方法,克服了正文提取中噪声节点多、内容识别不完全的缺陷,大大提高了提取的准确度。     

一种改进的进化树构建算法

邻接法是最有效的距离建树法的一种,但邻接法的聚类过程总是选择距离最近的进行聚类,容易忽略一些更为合理的拓扑结构,这是邻接法准确性不够理想的一个重要原因。为了提高邻接法的准确性,本文结合最大似然法提出一种改进的进化树构建算法。该算法在邻接法基础上,结合最大似然法搜索最优的拓扑结构,通过模拟实验将改进算法与邻接法等进化树构建算法进行比较,实验结果表明,改进算法的准确性明显优于邻接法。     

Probabilistic heuristic estimates

Though they constitute the major knowledge source in problem-solving systems, no unified theory of heuristics has emerged. Pearl [15] defines heuristics as criteria, methods, or principles for deciding which among several alternative courses of action promises to be the most effective in order to achieve some goal. The absence of a more precise definition has impeded our efforts to understand, utilize, and discover heuristics. Another consequence is that problem-solving techniques which rely on heuristic knowledge cannot be relied upon to act rationally — in the sense of the normative theory of rationality.To provide a sound basis for BPS, the Bayesian Problem-Solver, we have developed a simple formal theory of heuristics, which is general enough to subsume traditional heuristic functions as well as other forms of problem-solving knowledge, and to straddle disparate problem domains. Probabilistic heuristic estimates represent a probabilistic association of sensations with prior experience — specifically, a mapping from observations directly to subjective probabilities which enables the use of theoretically principled mechanisms for coherent inference and decision making during problem-solving. This paper discusses some of the implications of this theory, and describes its successful application in BPS.This research was made possible by support from Heuristicrats, the National Aeronautics and Space Administration, and the Rand Corporation.     

Heuristic collision-free path planning for an autonomous platform

In this paper, a heuristic and learning, algorithmic scheme for collision-free navigation is presented. This scheme determines an optimum collision-free navigation path of an autonomous platform by using a trial and error process, past navigation knowledge and current information extracted from the generated surrounding environment.