WebSail: From On-line Learning to Web Search

In this paper we report our research on building WebSail, an intelligent web search engine that is able to perform real-time adaptive learning. WebSail learns from the user's relevance feedback, so that it is able to speed up its search process and to enhance its search performance. We design an efficient adaptive learning algorithm TW2 to search for web documents. WebSail employs TW2 together with an internal index database and a real-time meta-searcher to perform real-time adaptive learning to find desired documents with as little relevance feedback from the user as possible. The architecture and performance of WebSail are also discussed. Received 3 November 2000 / Revised 13 March 2001 / Accepted in revised form 17 April 2001     

基于演化算法实现多目标优化的岛屿迁徙模型

多目标演化算法(MOEA)利用种群策略，尽可能地找出多目标问题的Pareto最优集供决策者选择，为决策者提供了更大的选择余地，与其它传统的方法相比有了很大的改进．但提供大量选择的同时，存在着不能为决策者提供一定的指导性信息，不能反映决策者的偏好，可扩展性差等问题．本文提出了一个新的多目标演化算法(MOEA)计算模型…岛屿迁徙模型，该模型体现了一种全新的多目标演化优化的求解思想，对多目标优化问题的最优解集作了新的定义．数值试验结果表明，岛屿迁徙模型在求解MOP时有效地解决了以上问题，并且存在进一步改进的潜力．     

A comparative study of different approaches using an outranking relation in a multi-objective evolutionary algorithm

This paper presents a comparative analysis of three versions of an evolutionary algorithm in which the decision maker's preferences are incorporated using an outranking relation and preference parameters associated with the ELECTRE TRI method. The aim is using the preference information supplied by the decision maker to guide the search process to the regions where solutions more in accordance with his/her preferences are located, thus narrowing the scope of the search and reducing the computational effort. An example dealing with a pertinent problem in electrical distribution network is used to compare the different versions of the algorithm and illustrate how meaningful information can be elicited from a decision maker and used in the operational framework of an evolutionary algorithm to provide decision support in real-world problems.     

基于双群体进化规划的动态优化算法

动态优化问题的优化环境随时间变化导致了最优解随时间移动.为了有效地跟踪最优解,提出了一个基于双群体进化规划的动态优化算法.局部搜索群体运用高斯变异算子,并接受已有信息;全局搜索群体运用柯西变异算子,与已有信息隔离并传送较优个体至局部搜索群体.在进化过程中,它们的群体规模动态地变化.算法有效地利用了已有信息,实现了全局搜索与局部搜索的分离,适合于求解环境变化方式未知的动态优化问题.对三个动态优化模型进行了测试,并与随机初始化群体法进行了比较,仿真结果表明r提出的算法是有效的.     

Heuristic and randomized optimization for the join ordering problem

Recent developments in database technology, such as deductive database systems, have given rise to the demand for new, cost-effective optimization techniques for join expressions. In this paper many different algorithms that compute approximate solutions for optimizing join orders are studied since traditional dynamic programming techniques are not appropriate for complex problems. Two possible solution spaces, the space of left-deep and bushy processing trees, are evaluated from a statistical point of view. The result is that the common limitation to left-deep processing trees is only advisable for certain join graph types. Basically, optimizers from three classes are analysed: heuristic, randomized and genetic algorithms. Each one is extensively scrutinized with respect to its working principle and its fitness for the desired application. It turns out that randomized and genetic algorithms are well suited for optimizing join expressions. They generate solutions of high quality within a reasonable running time. The benefits of heuristic optimizers, namely the short running time, are often outweighed by merely moderate optimization performance.     

Plateaus can be harder in multi-objective optimization

In recent years a lot of progress has been made in understanding the behavior of evolutionary computation methods for single- and multi-objective problems. Our aim is to analyze the diversity mechanisms that are implicitly used in evolutionary algorithms for multi-objective problems by rigorous runtime analyses. We show that, even if the population size is small, the runtime can be exponential where corresponding single-objective problems are optimized within polynomial time. To illustrate this behavior we analyze a simple plateau function in a first step and extend our result to a class of instances of the well-known SetCover problem.     

Evolutionary Algorithms: A Tool for Addressing Problems which Humans Cannot Solve

Although computers have been applied in many areas, there are some applications which seem to be more difficult than others to computerise. Typically these are problems for which we do not have a complete understanding, such as computer vision or robot path planning. Traditional development methods cannot account for a poor analysis of a problem and therefore fail to deliver successful systems for ill-defined problems. Three case studies are presented to demonstrate the application of genetic algorithms and genetic programming to demonstrate how these evolutionary techniques can be applied to ill-defined problems, thus diminishing the need for humans to apply themselves to dangerous or mundane tasks.     

An improved multi-objective evolutionary algorithm for the vehicle routing problem with time windows

The vehicle routing problem with time windows is a complex combinatorial problem with many real-world applications in transportation and distribution logistics. Its main objective is to find the lowest distance set of routes to deliver goods, using a fleet of identical vehicles with restricted capacity, to customers with service time windows. However, there are other objectives, and having a range of solutions representing the trade-offs between objectives is crucial for many applications. Although previous research has used evolutionary methods for solving this problem, it has rarely concentrated on the optimization of more than one objective, and hardly ever explicitly considered the diversity of solutions. This paper proposes and analyzes a novel multi-objective evolutionary algorithm, which incorporates methods for measuring the similarity of solutions, to solve the multi-objective problem. The algorithm is applied to a standard benchmark problem set, showing that when the similarity measure is used appropriately, the diversity and quality of solutions is higher than when it is not used, and the algorithm achieves highly competitive results compared with previously published studies and those from a popular evolutionary multi-objective optimizer.     

动态多目标优化进化算法及性能分析

针对动态多目标优化问题提出了一种求解的新进化算法。首先,构建了一种近似估计新环境下动态多目标优化问题的Pareto核迁移估计模型。其次,当探测到问题环境发生改变时,算法利用以前环境搜索到的Pareto核的有效信息通过Pareto核迁移估计模型对新环境下的进化种群进行近似估计;当问题的环境未发生变化时,引入了带区间分割的变异算子和非劣解存档保优策略,以提高算法的搜索效率。最后计算机仿真表明新算法对动态多目标优化问题十分有效。     

User Environments and Individuals: Experience with Adaptive Interface Agents

The traditional style of working with computers generally revolves around the computer being used as a tool, with individual users directly initiating operations and waiting for the results of them. A more recent paradigm of human-computer interaction, based on the indirect management of computing resources, is agent-based interaction. The idea of delegation plays a key part in this approach to computer-based work, which allows individuals to relinquish the routine, mechanistic parts of their everyday tasks, having them performed automatically instead. Adaptive interfaces combine elements of both these approaches, where the goal is to have the interface adapt to its users rather than the reverse. This paper addresses some of the issues arising from a practical software development process which aimed to support individuals using this style of interaction. This paper documents the development of a set of classes which implement an architecture for adaptive interfaces. These classes are intended to be used as part of larger user interface systems which are to exhibit adaptive behaviour. One approach to the implementation of an adaptive interface is to use a set of software “agents”– simple processes which effectively run “in the background”– to decompose the task of implementing the interface. These agents form part of a larger adaptive interface architecture, which in turn forms a component of the adaptive system.     

Location Models for Augmented Environments

In this paper we describe two projects on contextualized computer systems and audio augmented environments we are currently working on at the Fraunhofer Institutes FIT and IMK. In this paper we will only focus on the world models and the augmentation layer. Both projects are based on completely different technologies, and use different representation methods and interaction facilities. While in hippie users are moving with small laptop computers or wearable computers with a small visual display, in LISTEN users will have only a wireless headphone displaying spatially rendered sound-scenes. Correspondence to: J. Goβmann, Fraunhofer-IMK, Schloss Birlinghoven, D-53754 St Augustin, Germany.     

Learning algorithm for multimodal optimization

We present a new evolutionary algorithm—“learning algorithm” for multimodal optimization. The scheme for reproducing a new generation is very simple. Control parameters, of the length of the list of historical best solutions and the “learning probability” of the current solutions being moved towards the current best solutions and towards the historical ones, are used to assign different search intensities to different parts of the feasible area and to direct the updating of the current solutions. Results of numerical tests on minimization of the 2D Schaffer function, the 2D Shubert function and the 10D Ackley function show that this algorithm is effective and efficient in finding multiple global solutions of multimodal optimization problems.     

Hybrid algorithms for the twin–screw extrusion configuration problem

The twin-screw configuration problem (TSCP) arises in the context of polymer processing, where twin-screw extruders are used to prepare polymer blends, compounds or composites. The goal of the TSCP is to define the configuration of a screw from a given set of screw elements. The TSCP can be seen as a sequencing problem as the order of the screw elements on the screw axis has to be defined. It is also inherently a multi-objective problem since processing has to optimize various conflicting parameters related to the degree of mixing, shear rate, or mechanical energy input among others. In this article, we develop hybrid algorithms to tackle the bi-objective TSCP. The hybrid algorithms combine different local search procedures, including Pareto local search and two phase local search algorithms, with two different population-based algorithms, namely a multi-objective evolutionary algorithm and a multi-objective ant colony optimization algorithm. The experimental evaluation of these approaches shows that the best hybrid designs, combining Pareto local search with a multi-objective ant colony optimization approach, outperform the best algorithms that have been previously proposed for the TSCP.     

On-Line Learning from Search Failures

Learning by explaining failures and avoiding similar ones thereafter is an attractive way to speed up problem solving. However, previous methods for explanation-based learning from failure can take too long to detect failures, explain them, or test the learned rules. This expense is especially critical for adaptive search, in which control knowledge acquired while solving an individual problem instance must be learned quickly enough to speed up its solution.We present an adaptive search technique that speeds up state-space search by learning heuristic censors while searching. The censors speed up search by pruning away more and more of the space until a solution is found in the pruned space. Censors are learned by explaining dead ends and other search failures. To learn quickly, the technique overgeneralizes by assuming that certain constraints are preservable, i.e., remain true along at least one solution path. A recovery mechanism detects violations of this assumption and selectively relaxes learned censors. The technique, implemented in an adaptive problem solver named FAILSAFE-2, learns useful heuristics that cannot be learned by other reported methods.We present experimental evidence that FAILSAFE-2 is effective (learns useful rules, even in recursive domains where PRODIGY and STATIC do not), adaptive (learns fast enough to pay off even within a single problem), and general (speeds up diverse problem solvers, even initially strong ones).     

A robust real-coded evolutionary algorithm with toroidal search space conversion

This paper presents a robust Real-coded evolutionary algorithm. Real-coded evolutionary algorithms (RCEAs), such as real-coded genetic algorithms and evolution strategies, are known as effective methods for function optimization. However, they often fail to find the optimum in case the objective function is multimodal, discrete or high-dimensional. It is also reported that most crossover (or recombination) operators for RCEAs has sampling bias that prevents to find the optimum near the boundary of search space. They like to search the center of search space much more than the other. Therefore, they will not work on functions that have their optima near the boundary of search space. In this paper, we apply two methods, genetic algorithm with search area adaptation (GSA) and toroidal search space conversion (TSC), to the function optimization for improving the robustness of RCEAs. The former method searches adaptively and the latter one removes the sampling bias. Through several experiments, we have confirmed that GSA works adaptively and it shows higher performance, and RCEAs with TSC show effectiveness to find the optima near the boundary of search space.     

Dynamic vp-tree indexing for n-nearest neighbor search given pair-wise distances

Abstract. For some multimedia applications, it has been found that domain objects cannot be represented as feature vectors in a multidimensional space. Instead, pair-wise distances between data objects are the only input. To support content-based retrieval, one approach maps each object to a k-dimensional (k-d) point and tries to preserve the distances among the points. Then, existing spatial access index methods such as the R-trees and KD-trees can support fast searching on the resulting k-d points. However, information loss is inevitable with such an approach since the distances between data objects can only be preserved to a certain extent. Here we investigate the use of a distance-based indexing method. In particular, we apply the vantage point tree (vp-tree) method. There are two important problems for the vp-tree method that warrant further investigation, the n-nearest neighbors search and the updating mechanisms. We study an n-nearest neighbors search algorithm for the vp-tree, which is shown by experiments to scale up well with the size of the dataset and the desired number of nearest neighbors, n. Experiments also show that the searching in the vp-tree is more efficient than that for the -tree and the M-tree. Next, we propose solutions for the update problem for the vp-tree, and show by experiments that the algorithms are efficient and effective. Finally, we investigate the problem of selecting vantage-point, propose a few alternative methods, and study their impact on the number of distance computation. Received June 9, 1998 / Accepted January 31, 2000     

Multi-objective PSO algorithm for mining numerical association rules without a priori discretization

In the domain of association rules mining (ARM) discovering the rules for numerical attributes is still a challenging issue. Most of the popular approaches for numerical ARM require a priori data discretization to handle the numerical attributes. Moreover, in the process of discovering relations among data, often more than one objective (quality measure) is required, and in most cases, such objectives include conflicting measures. In such a situation, it is recommended to obtain the optimal trade-off between objectives. This paper deals with the numerical ARM problem using a multi-objective perspective by proposing a multi-objective particle swarm optimization algorithm (i.e., MOPAR) for numerical ARM that discovers numerical association rules (ARs) in only one single step. To identify more efficient ARs, several objectives are defined in the proposed multi-objective optimization approach, including confidence, comprehensibility, and interestingness. Finally, by using the Pareto optimality the best ARs are extracted. To deal with numerical attributes, we use rough values containing lower and upper bounds to show the intervals of attributes. In the experimental section of the paper, we analyze the effect of operators used in this study, compare our method to the most popular evolutionary-based proposals for ARM and present an analysis of the mined ARs. The results show that MOPAR extracts reliable (with confidence values close to 95%), comprehensible, and interesting numerical ARs when attaining the optimal trade-off between confidence, comprehensibility and interestingness.     

一种改进的禁忌搜索法在函数优化问题中的应用

禁忌搜索法对初始解、邻域个数及禁忌列表的大小等参数有比较严格的要求,这些参数直接影响着算法的优化能力。文章提出了一种改进的禁忌搜索法,它用有效空间来压缩搜索范围,这样可以提高搜索效率和全局搜索能力。用短期和长期禁忌列表存储器来保证算法能搜索到全局空间的每一点,并且不重复搜索。经过验算和分析,证明它是一种较好的全局启发式搜索法。     

一种非参数惩罚函数的优化演化算法

对约束优化问题的处理通常使用惩罚函数法,使用普通惩罚函数法的困难存在于参数的选取。该文提出一种基于演化算法的非参数罚函数算法,对违反约束条件动态地进行惩罚,由适应值的设定来平衡群体中可行解和不可行解的比例,使群体较好地向最优解逼近,使用实数编码的多父体单形杂交演化策略来实现新算法,通过对测试函数的检验,该算法具有稳健、高效、简洁易于实现等特点。     

A multi-objective evolutionary algorithm for examination timetabling

This paper considers the scheduling of exams for a set of university courses. The solution to this exam timetabling problem involves the optimization of complete timetables such that there are as few occurrences of students having to take exams in consecutive periods as possible but at the same time minimizing the timetable length and satisfying hard constraints such as seating capacity and no overlapping exams. To solve such a multi-objective combinatorial optimization problem, this paper presents a multi-objective evolutionary algorithm that uses a variable-length chromosome representation and incorporates a micro-genetic algorithm and a hill-climber for local exploitation and a goal-based Pareto ranking scheme for assigning the relative strength of solutions. It also imports several features from the research on the graph coloring problem. The proposed algorithm is shown to be a more general exam timetabling problem solver in that it does not require any prior information of the timetable length to be effective. It is also tested against a few influential and recent optimization techniques and is found to be superior on four out of seven publicly available datasets.