An analysis of the interface between evolutionary algorithm operators and problem features for water resources problems. A case study in water distribution network design

Evolutionary Algorithms (EAs) have been widely employed to solve water resources problems for nearly two decades with much success. However, recent research in hyperheuristics has raised the possibility of developing optimisers that adapt to the characteristics of the problem being solved. In order to select appropriate operators for such optimisers it is necessary to first understand the interaction between operator and problem. This paper explores the concept of EA operator behaviour in real world applications through the empirical study of performance using water distribution networks (WDN) as a case study. Artificial networks are created to embody specific WDN features which are then used to evaluate the impact of network features on operator performance. The method extracts key attributes of the problem which are encapsulated in the natural features of a WDN, such as topologies and assets, on which different EA operators can be tested. The method is demonstrated using small exemplar networks designed specifically so that they isolate individual features. A set of operators are tested on these artificial networks and their behaviour characterised. This process provides a systematic and quantitative approach to establishing detailed information about an algorithm's suitability to optimise certain types of problem. The experiment is then repeated on real-world inspired networks and the results are shown to fit with the expected results.     

Optimal control of a water distribution network by two multilevel methods

The problem of daily controlling a water distribution network, including pumping devices and storage capacities, in order to supply the consumers at the lowest cost is formulated as a constrained optimal control problem. Discrete Dynamic Programming seems the only way to overcome the particular difficulties of this problem but the dimensionality prevents one using it on the global problem. Two approaches are considered. The first one consists in tearing up the network into several subnetworks and to use an algorithm of coordination. It succeeds in case of weak coupling between subnetworks. The second one uses an original approach of aggregation and disaggregation iteratively. Presently available experiments with the latter method showed its satisfactory behaviour.     

高校科研能力的协同IWD粗糙集-块神经网络评估模型

针对高校科研能力评估过程中存在的多因素、高非线性特点,经典评估模型主观性较强,导致模型评估准确性不高的问题,提出基于协同智能水滴算法IWD和粗糙集块神经网络RBNN的高校科研能力评估模型。首先,引入智能水滴算法,并针对传统智能水滴算法固定旁域搜索范围不利于提升算法搜索效率的问题,提出一种局部空间自动缩放算法LSAS,该算法根据当前种群最优个体,自动调整下一步搜索空间大小,对进化过程进行指导,提高算法的进化效率;其次,基于粗糙集理论对高校科研能力数据进行特征预处理,简化数据计算量;最后,对块神经网络和粗糙集参数进行编码,并对高校科研能力模型进行评估。仿真结果表明,此评估模型具有较高的准确性和较快的计算效率。     

The state of the art on buffer allocation problem: a comprehensive survey

The buffer allocation problem is an NP-hard combinatorial optimization problem and it is an important research issue in designing manufacturing systems. The problem deals with finding optimal buffer sizes to be allocated into buffer areas in a production system to achieve a specific objective. This paper presents a comprehensive survey on buffer allocation problem in production systems. To provide a systematic review of current relevant research, first studies are grouped in two categories: 1. Reliable production lines, 2. Unreliable production lines. Next, the studies in each group are reviewed based on topology of the production line, the solution methodologies suggested and the objective function employed. The aim of this review is twofold. First, it provides an overview of recent advances in the field in order to highlight the new trends in solution methodology. Second, it presents ideas for future research by identifying gaps in the current literature.     

动态水面数据采集与重建方法

自然现象模拟是计算机图形学中的一个重要研究热点.如何快速逼真地模拟自然现象是此类研究的主要目的.传统的解决思路大多采用基于物理的建模方法,而随着采集设备的快速发展,基于采集图像的重建方法得到了广泛关注与研究.本文以液体为研究对象,总结了近年来基于采集图像的重建方法的部分研究成果.针对动态水面,提出了一种动态水面数据采集与重建方法.首先,设计并搭建一套基于多相机的动态水面数据采集系统,采集得到多视图下不同水面运动现象的连续帧图像.其次,通过提取采集图像序列中每幅图像的亚像素级特征点,进行特征点匹配并建立特征点与物理空间中三维点的映射关系.然后,结合水介质的光学折射特性迭代求解水面上三维点阵的高度场和法向量.最终获得动态水面的重建结果.实验结果表明该方法能快速生成与采集水面可视效果相近的三维重建结果,可在计算机游戏、医学、科学研究可视化等领域具有应用前景.     

刚柔耦合系统动力学研究进展

首先简要回顾了柔性多体系统动力学前期研究的3个阶段．针对传统零次近似模型的缺陷提出了新的建模理论,并在新的一次近似耦合模型的基础上,就“动力刚化”问题和刚柔耦合动力学问题中的离散化方法与实验等方面进行研究;研制了供理论研究和动力学现象揭示的实验平台．文中对所取得的研究成果进行介绍．文末对今后的研究方向进行了展望．     

Identification of resonance waves in open water channels

This article describes a way to determine the properties of resonance (reflecting) waves in open water channels. For channels that are sensitive to resonances, information about the first resonance mode is required for controller and filter design. This research applies standard system identification techniques and is tested on an actual channel at the Central Arizona Irrigation and Drainage District, Eloy, AZ. The identification experiment results in good estimations of the frequency and magnitude of the first resonance peak of the open water channel.     

The problem of implicit knowledge

Abstract: Recognising the existence of different forms of knowledge is a first step towards effective knowledge elicitation. This article takes a brief look at some of the different types of knowledge which human experts possess and then focusses on the problem of implicit knowledge.
The fact that much of an expert's knowledge is implicit or tacit in nature is a major problem for those working in the area of knowledge elicitation. Despite this, the topic has attracted little discussion or research. The present article reviews some of the limited literature on the topic and attempts to settle some of the confusion over what implicit knowledge is, or might be. Relevant experiments from the psychological literature are discussed. The paper also looks at possible ways of assessing implicit knowledge and makes recommendations for future research in this area.     

Movement Planning in the Presence of Flows

This paper investigates the problem of time-optimum movement planning in two and three dimensions for a point robot which has bounded control velocity through a set of n polygonal regions of given translational flow velocities. This intriguing geometric problem has immediate applications to macro-scale motion planning for ships, submarines, and airplanes in the presence of significant flows of water or air. Also, it is a central motion planning problem for many of the meso-scale and micro-scale robots that have been constructed recently, that have environments with significant flows that affect their movement. In spite of these applications, there is very little literature on this problem, and prior work provided neither an upper bound on its computational complexity nor even a decision algorithm. It can easily be seen that an optimum path for the 2D version of this problem can consist of at least an exponential number of distinct segments through flow regions. We provide the first known computational complexity hardness result for the 3D version of this problem; we show the problem is PSPACE hard. We give the first known decision algorithm for the 2D flow path problem, but this decision algorithm has very high computational complexity. We also give the first known efficient approximation algorithms with bounded error.     

Agent-based modeling and evolutionary computation for disseminating public advisories about hazardous material emergencies

In the event of a large-scale disaster, an important aspect of humanitarian logistics is the distribution of information or warnings to the affected population. This research develops the problem formulation and solution approach for a specific routing for relief problem, in which warnings should be disseminated to an affected community, using public announcement systems mounted on emergency vehicles. The problem statement is formulated to maximize the number of individuals of a community who are protected. An evolutionary algorithm framework is developed by coupling an agent-based model with a variable-length genetic algorithm to route emergency vehicles. The dynamics of interactions among consumers, emergency vehicles, and the spatiotemporal trajectory of the hazard are simulated using an agent-based modeling approach, and a variable-length genetic algorithm approach selects routes to warn a maximum number of consumers before they are affected by the emergency. The example that is explored in this research is contamination of a water distribution network. A fleet of emergency vehicles is equipped with public address systems and is deployed to warn consumers to stop using contaminated water. The framework is demonstrated for an illustrative virtual city, Mesopolis. The results of the evolutionary algorithm framework are compared with two conventional routing optimization approaches, including a covering tour problem approach and a manual routing approach, for four contamination scenarios. The evolutionary algorithm can be applied to route emergency service vehicles to broadcast information for other emergencies, such as flash flooding, hazardous materials incidents, and severe weather.     

On computing minimal models

This paper addresses the problem of computing the minimal models of a given CNF propositional theory. We present two groups of algorithms. Algorithms in the first group are efficient when the theory is almost Horn, that is, when there are few non-Horn clauses and/or when the set of all literals that appear positive in any non-Horn clause is small. Algorithms in the other group are efficient when the theory can be represented as an acyclic network of low-arity relations. Our algorithms suggest several characterizations of tractable subsets for the problem of finding minimal models.This work was partially supported by an IBM graduate fellowship to the first author, by NSF grants IRI-9157636 and IRI-9200918, by Air Force Office of Scientific Research grant AFOSR 900136, by a grant from Xerox Palo Alto research center, and by Toshiba of America. Part of this work was done while the first author was a graduate student at the Cognitive Systems Laboratory, Computer Science Department, University of California, Los Angeles, California, USA.     

推荐系统中的冷启动问题研究综述

推荐系统能够快捷、准确地定位用户真正需要的信息,解决网络信息过载问题。其中协同过滤推荐技术是推荐系统应用最广泛和成功的技术,但该技术面临冷启动问题的挑战。本文分析冷启动问题的产生原因,阐述研究冷启动问题的意义,重点总结解决冷启动问题的算法现状,分析比较它们的性能差异和各自存在的优缺点,从而便于使用者在解决冷启动问题时对算法的选择和使用。     

遗传算法解柔性作业车间调度问题应用综述

柔性作业车间调度问题是典型的NP难问题,对实际生产应用具有指导作用。近年来,随着遗传算法的发展,利用遗传算法来解决柔性作业车间调度问题的思想和方法层出不穷。为了促进遗传算法求解柔性作业车间调度问题的进一步发展,阐述了柔性作业车间调度问题的研究理论,对已有改进方法进行了分类,通过对现存问题的分析,探讨了未来的发展方向。     

A multi-objective genetic algorithm applied to autonomous underwater vehicles for sewage outfall plume dispersion observations

This work presents a multi-objective genetic algorithm to solve route planning problem for multiple autonomous underwater vehicles (AUVs) for interdisciplinary coastal research. AUVs are mobile unmanned platforms that carry their own energy and are able to move themselves in the water without intervention from an external operator. Using AUVs one can provide high-quality measurements of physical properties of effluent plumes in a very effective manner under real oceanic conditions. The AUV's route planning problem is a combinatorial optimization problem, where the vehicles must travel through a three-dimensional irregular space with all dimensions known. Therefore, minimization of the total travel distance while considering the maximum number of water samples is the main objective. Besides the AUV kinematics restrictions other considerations must be taken into account to the problem, like the ocean currents. The practical applications of this approach are the environmental monitoring missions which typically require the sampling of a volume of water with non-trivial geometry for which parallel line sweeping might be a costly solution. Some real-life test problems and related solutions are presented.     

基于价格的拥塞控制模型扩展

基于价格的拥塞控制模型将网络拥塞控制问题抽象为聚合效用最大化的优化问题,已经成为拥塞控制机制设计和分析的一般框架。然而简化的线性模型与现实网络环境有一定差距,不能准确有效地指导新协议的设计与分析。因此,近年来研究人员正试图结合新的技术和应用,扩展完善基于价格的模型,建立更为准确有效的模型来反映现实的网络环境。为了系统地了解该领域研究工作的进展,本文首先简要回顾了基于价格的模型,分析其不足,介绍近年来在模型扩展方面的研究工作,最后指出几个有意义的研究方向。     

基于最小二乘支持向量回归的水质预测

水质系统是一个开放的、复杂的、非线性动力学系统,具有时变复杂性,针对水质预测方法的研究虽然已经取得了一些成果,但也存在预测精度与计算复杂度等难题。为此,本文提出一种基于最小二乘支持向量回归的水质预测算法。支持向量机是机器学习中一种常用的分类模型,通过核函数将非线性数据从低维映射到高维空间,在高维空间实现线性分类和回归,最小二乘支持向量回归（LS-SVR）利用所有的样本参与回归拟合,使得回归的损失函数不再只与小部分支持向量样本有关,而是由所有样本参与学习修正误差,提高预测精度;同时该算法将标准SVR求解问题由不等式的约束条件及凸二次规划问题转化成线性方程组来求解,提高了运算速度,解决了非线性复杂特性的水质预测问题。     

Design as intelligent behaviour: An AI in design research programme

Design is a kind of intelligent behaviour: a kind which makes much use of explicit knowledge. This paper presents the philosophy, aims, background, experimental approach, of the AI in Design research programme being conducted in the Department of Artificial Intelligence, Edinburgh University. It structures this presentation in terms of the three levels, or kinds, of understanding that Artificial Intelligence research should generate; Knowledge Level, Symbol Level, and System Engineering Level understanding. The development of an exploration-based model of design is presented at the Knowledge Level, an AI-based design support system architecture is presented at the Symbol Level, and the engineering of a series of experimental design support systems is presented at the System Engineering Level. To illustrate the use of the current version of the design support system a water turbine design problem is considered. A final section discusses the current status and future of the research programme.     

A first multilevel cooperative algorithm for capacitated multicommodity network design

We describe the first multilevel cooperative tabu search for the capacitated multicommodity network design problem. Main design challenges are associated to the specification of the problem instance addressed at each level in cooperation, as well as to the definition of the cooperation operators. The paper proposes a first approach to address these challenges and tests it on a set of well-known benchmark problems. The proposed method appears competitive, particularly when difficult problems with many commodities are considered. Directions and challenges for future research are identified and discussed.     

步态识别问题的特点及研究现状

步态识别作为一种较新的生物认证技术有其独特优势,在计算机视觉研究领域又是一个难题.本文首先分析了步态识别问题的这两个特点.其次,按一个模式识别系统所涉及的4个问题域：传感器的选择、预处理技术、表达方法、决策模型为索引去分析步态识别问题.在表达方法一节中将文献中所反映的研究方法从计算机视觉的角度分为基于模型和基于整体的两大类,并对每类方法进行了举例说明,指出了所举出的方法的优缺点和其提取步态模式中的结构成分信息和运动特征信息时所采用的方法.再次,对步态识别算法性能评价标准和可得到的数据库进行了分析说明.最后得出了目前步态识别问题研究中的几个薄弱点,指出进一步研究此问题的发展空间.     

基于区分能力大小的启发式约简算法及其应用

提出了一种能处理噪音的有效约简算法，该算法基于粗集理论认为知识是区分事物的能力的观点，对知识进行量化，证明了量化的合理性，并以量化后的区分能力作为启发式信息，指导约简，提高了约简效率。另外，利用这种启发式信息，提出了一种解决噪音问题的方法。最后，将该算法应用到人机接口中，用于手关节自由度的约简，这对手势识别与合成是很有意义的工作。