Incremental acquisition of search knowledge

The development of highly effective heuristics for search problems is a difficult and time-consuming task. We present a knowledge acquisition approach to incrementally model expert search processes. Though, experts do not normally have complete introspective access to that knowledge, their explanations of actual search considerations seem very valuable in constructing a knowledge-level model of their search processes.Furthermore, for the basis of our knowledge acquisition approach, we substantially extend the work done on Ripple-down rules which allows knowledge acquisition and maintenance without analysis or a knowledge engineer. This extension allows the expert to enter his domain terms during the KA process; thus the expert provides a knowledge-level model of his search process. We call this framework nested ripple-down rules.Our approach targets the implicit representation of the less clearly definable quality criteria by allowing the expert to limit his input to the system to explanations of the steps in the expert search process. These explanations are expressed in our search knowledge interactive language. These explanations are used to construct a knowledge base representing search control knowledge. We are acquiring the knowledge in the context of its use, which substantially supports the knowledge acquisition process. Thus, in this paper, we will show that it is possible to build effective search heuristics efficiently at the knowledge level. We will discuss how our system SmS1.3 (SmS for Smart Searcher) operates at the knowledge level as originally described by Newell. We complement our discussion by employing SmS for the acquisition of expert chess knowledge for performing a highly pruned tree search. These experimental results in the chess domain are evidence for the practicality of our approach.     

Expert system for scheduling in an airline gate allocation

Scheduling is an important technique encompassing a wide application area. Because of the complex interrelations among the resources, knowledge, and various other constraints, scheduling has many difficulties. Artificial Intelligence technology has been applied to solve the scheduling problem. As AI techniques are efficient in representing knowledge and dealing with heuristics, it is an adequate approach to model and to solve scheduling problems. We have implemented the ramp scheduling system, called RACES (Ramp Activity Coordination Expert System), to solve complex and dynamic aircraft parking problems. RACES was developed from the domain knowledge and experience which were acquired from the domain experts. Domain knowledge and experience are important factors in controlling the scheduling procedure. RACES divides the problem into sub-problems and experimental heuristics in the knowledge acquisition process. The system independently processes scheduling for the divided sub-problems and shares variables and domains. During the scheduling, the system selects or confines the search space with domain filtering techniques by exploiting the characteristics of various constraints and knowledge. RACES produces a user-driven near-optimal solution by means of a trade-off scheduling method using heuristics between the size of aircraft and the best-fit time. For 400 daily flights, RACES made parking schedules for aircraft in about 20 s compared with 4–5 h by human experts.     

云化SFT下的径集域与割集域的重构与研究

为了克服原有SFT体系中径集域和割集域处理具有模糊性、随机性和离散性故障数据能力不足的问题,使用云模型和SFT相结合的方法来解决该问题。首先使用云模型云化SFT特征函数,得到云化特征函数,进而云化径集域和割集域,最终得到云化径集域和云化割集域。云化径集域和云化割集域没有严格的分界线,分布区域是通过云滴表示的。若云滴表示的元件/系统故障概率小于P_b,这些云滴存在的区域即为云化径集域;反之大于P_b的云滴存在的区域为云化割集域。通过实例分析了元件X₁和系统的云化径集域和云化割集域,得到了他们适合工作的环境因素变化范围组合。分析过程和结果表明云化径集域和云化割集域能克服原始故障数据的不确定性。     

Grammar-based generation of variable-selection heuristics for constraint satisfaction problems

We propose a grammar-based genetic programming framework that generates variable-selection heuristics for solving constraint satisfaction problems. This approach can be considered as a generation hyper-heuristic. A grammar to express heuristics is extracted from successful human-designed variable-selection heuristics. The search is performed on the derivation sequences of this grammar using a strongly typed genetic programming framework. The approach brings two innovations to grammar-based hyper-heuristics in this domain: the incorporation of if-then-else rules to the function set, and the implementation of overloaded functions capable of handling different input dimensionality. Moreover, the heuristic search space is explored using not only evolutionary search, but also two alternative simpler strategies, namely, iterated local search and parallel hill climbing. We tested our approach on synthetic and real-world instances. The newly generated heuristics have an improved performance when compared against human-designed heuristics. Our results suggest that the constrained search space imposed by the proposed grammar is the main factor in the generation of good heuristics. However, to generate more general heuristics, the composition of the training set and the search methodology played an important role. We found that increasing the variability of the training set improved the generality of the evolved heuristics, and the evolutionary search strategy produced slightly better results.     

基于非参数信念传播的可行C-空间关节人手跟踪方法

采用三维人手图模型描述了人手结构、运动学、动力学及自遮挡特性,将人手高维（27维）跟踪问题转为并行跟踪16个6维变量的问题,降低了计算复杂度．在非参数信念传播过程中嵌入连续自适应均值漂移方法得到可行C空间,在该空间中传递消息以提高跟踪效率．实验结果表明,该方法在人手发生自遮挡的情况下,能快速、鲁棒地跟踪关节人手．     

EDA: AN EVOLUTIONARY DECODING ALGORITHM FOR STATISTICAL MACHINE TRANSLATION

In a statistical machine translation system (SMTS), decoding is the process of finding the most likely translation based on a statistical model, according to previously learned parameters. The success of an SMTS is strongly dependent on the quality of its decoder. Most of the SMTS's published in current literature use approaches based on traditional optimization methods and heuristics. On the other hand, over the last few years there has been a rapid increase in the use of metaheuristics. These kinds of techniques have shown to be able to solve difficult search problems in an efficient way for a wide number of applications.

This paper proposes a new approach based on evolutionary hybrid algorithms to translate sentences in a specific technical context. The algorithm has been enhanced by adaptive parameter control. The tests are carried out in the context of Spanish and then translated to English.

The experimental results validate the superior performance of our method in contrast to a statistical greedy decoder. We also compare our new approach to the existing public domain general translators.     

Simultaneous design of components layout and supporting structures using coupled shape and topology optimization technique

The purpose of this paper was to study the layout design of the components and their supporting structures in a finite packing space. A coupled shape and topology optimization (CSTO) technique is proposed. On one hand, by defining the location and orientation of each component as geometric design variables, shape optimization is carried out to find the optimal layout of these components and a finite-circle method (FCM) is used to avoid the overlap between the components. On the other hand, the material configuration of the supporting structures that interconnect components is optimized simultaneously based on topology optimization method. As the FE mesh discretizing the packing space, i.e., design domain, has to be updated itertively to accommodate the layout variation of involved components, topology design variables, i.e., density variables assigned to density points that are distributed regularly in the entire design domain will be introduced in this paper instead of using traditional pseudo-density variables associated with finite elements as in standard topology optimization procedures. These points will thus dominate the pseudo-densities of the surrounding elements. Besides, in the CSTO, the technique of embedded mesh is used to save the computing time of the remeshing procedure, and design sensitivities are calculated w.r.t both geometric variables and density variables. In this paper, several design problems maximizing structural stiffness are considered subject to the material volume constraint. Reasonable designs of components layout and supporting structures are obtained numerically.     

基于青鸟接口规约的全领域模型系统

现有的构件模型难以对领域的共性和变化性进行定义与描述,致使构件的粒度大小难以控制。基于常用的树形程序的特点,提出一种基于青鸟接口规约的全领域构件模型系统,整个系统由全领域构件模型及相应的二次加工工具系统组成。全领域构件模型能对领域中一族具有共性和变化性的描述进行代码实现;二次加工工具系统能对全领域构件进行二次加工,剔除构件中的冗余子模块。此全领域构件模型系统能够有效解决代码构件开发中经常遇到的构件的粒度大小问题。     

Knowledge-based radiologic image retrieval using axes of clinical relevance

This paper describes an approach to computer-based intelligent retrieval of feature-coded radiographic images relevant to a specific case being evaluated. The approach involves partitioning the search space along clinically natural groups of attributes which we call "axes of clinical relevance." By embedding knowledge about the domain to help direct the search process, a clinician's needs may be met more comprehensively. Domain knowledge, supplied to the system as "axis heuristics," may make search more robust. These heuristics provide a graded, progressive relaxation of the search constraints. This approach helps show the user groups of images in order of probable relevance to a current case. AXON is a prototype knowledge-based system constructed to illustrate this approach in the domain of chest imaging. This paper describes the AXON system, demonstrates some searches which illustrate the potential utility of this approach, and discusses preliminary tests of the search strategies used by AXON.     

On the empirical justification of theoretical heuristic transference and learning

The solution of intractable problems implies the use of heuristics. Quantum computers may find use for optimization problems, but have yet to solve any NP-hard problems. This paper demonstrates results in game theory for domain transference and the reuse of problem-solving knowledge through the application of learned heuristics. It goes on to explore the possibilities for the acquisition of heuristics for the solution of the NP-hard TSP problem. Here, it is found that simple heuristics (e.g., pairwise exchange) often work best in the context of more or less sophisticated experimental designs. Often, these problems are not amenable to exclusive logic solutions; but rather, require the application of hybrid approaches predicated on search. In general, such approaches are based on randomization and supported by parallel processing. This means that heuristic solutions emerge from attempts to randomize the search space. The paper goes on to present a constructive proof of the unbounded density of knowledge in support of the Semantic Randomization Theorem (SRT). It highlights this result and its potential impact upon the community of machine learning researchers.     

基于领域本体的网络搜索模型

本文提出了一个以领域本体为驱动的网络搜索模型。以Internet上海量、多变的资源为背景,一方面通过语义推理,优化了网络搜索中存在的如查准率低等问题,另一方面利用本体库资源,在网络搜索过程中做问题激发,不仅增强了搜索的人性化,更提高了语义分析的效率。本文以股票领域本体为案例进行了验证,表明该模型对于资源类型丰富、结构复杂多变的大规模资源库,具有更灵活有效的语义搜索特征。     

Upgrading automation for nuclear fuel in-core management: From the symbolic generation of configurations, to the neural adaptation of heuristics

FUELCON is an expert system in nuclear engineering. Its task is optimized refueling-design, which is crucial to keep down operation costs at a plant. FUELCON proposes sets of alternative configurations of fuel-allocation; the fuel is positioned in a grid representing the core of a reactor. The practitioner of in-core fuel management uses FUELCON to generate a reasonably good configuration for the situation at hand. The domain expert, on the other hand, resorts to the system to test heuristics and discover new ones, for the task described above. Expert use involves a manual phase of revising the ruleset, based on performance during previous iterations in the same session. This paper is concerned with a new phase: the design of a neural component to carry out the revision automatically. Such an automated revision considers previous performance of the system and uses it for adaptation and learning better rules. The neural component is based on a particular schema for a symbolic to recurrent-analogue bridge, called NIPPL, and on the reinforcement learning of neural networks for the adaptation.     

An informed genetic algorithm for the examination timetabling problem

This paper presents the results of a study conducted to investigate the use of genetic algorithms (GAs) as a means of inducing solutions to the examination timetabling problem (ETP). This study differs from previous efforts applying genetic algorithms to this domain in that firstly it takes a two-phased approach to the problem which focuses on producing timetables that meet the hard constraints during the first phase, while improvements are made to these timetables in the second phase so as to reduce the soft constraint costs. Secondly, domain specific knowledge in the form of heuristics is used to guide the evolutionary process. The system was tested on a set of 13 real-world problems, namely, the Carter benchmarks. The performance of the system on the benchmarks is comparable to that of other evolutionary techniques and in some cases the system was found to outperform these techniques. Furthermore, the quality of the examination timetables evolved is within range of the best results produced in the field.     

Heuristics-based mediation for building smart architectures at run-time

Smart architectures are increasingly being used in current software development. Smart user interfaces, smart homes, or smart buildings are becoming common examples in the new era of smart cities. Software architectures usually related to these domains need to be adapted and reconfigured at run-time, for example, to provide new services, react to user interaction, or due to changes decided from the business logic of the application. Component-based techniques are a suitable way to carry out this kind of adaptation, as dynamic reconfiguration operations can be applied to the architecture. In this paper, we address run-time generation of component-based applications, taking the abstract definitions of their architecture as a reference, in addition to a set of available components. The process calculates the best configuration of components from the abstract definition by applying a trading approach based on an adapted A* algorithm. This algorithm uses heuristics based on syntactic and semantic information obtained from the component definitions. A case study related to mashup user interfaces formed by coarse-grained components is also explained. In short, the results show the usefulness of heuristics and suitable execution times for building the best configurations.     

Heuristics for automated knowledge source integration and service composition

The NP-hard component set identification problem is a combinatorial problem arising in the context of knowledge discovery, information integration, and knowledge source/service composition. Considering a granular knowledge domain consisting of a large number of individual bits and pieces of domain knowledge (properties) and a large number of knowledge sources and services that provide mappings between sets of properties, the objective of the component set identification problem is to select a minimum cost combination of knowledge sources that can provide a joint mapping from a given set of initially available properties (initial knowledge) to a set of initially unknown properties (target knowledge). We provide a general framework for heuristics and consider construction heuristics that are followed by local improvement heuristics. Computational results are reported on randomly generated problem instances.     

Improved Tabu search heuristics for the dynamic space allocation problem

The dynamic space allocation problem (DSAP) presented in this paper considers the task of assigning items (resources) to locations during a multi-period planning horizon such that the cost of rearranging the items is minimized. Three tabu search heuristics are presented for this problem. The first heuristic is a simple basic tabu search heuristic. The second heuristic adds diversification and intensification strategies to the first, and the third heuristic is a probabilistic tabu search heuristic. To test the performances of the heuristics, a set of test problems from the literature is used in the analysis. The results show that the tabu search heuristics are efficient techniques for solving the DSAP. More importantly, the proposed tabu search heuristic with diversification/intensification strategies found new best solutions using less computation time for one-half of all the test problems.     

A two-stage hybrid manufacturing model with controllable make-to-order production rates

As an effective strategy to facilitate delivering customized products within short lead time, hybrid manufacturing via a two-stage process has received attention from academia and industry. In this paper, we study a two-stage hybrid manufacturing system in which semifinished products are manufactured in a make-to-stock fashion in the first stage and end-products are produced from semifinished goods in a make-to-order (MTO) mode in the second stage. The rate of MTO production can be controlled within given limits, depending on the status of the system. The primary goal of this paper is to study a policy for coordinating order admission, MTO production rate, and inventory replenishment controls. Formulating the problem as a Markov decision process model, we characterize the structure of optimal control policies to maximize the long-run average profit. Using a numerical experiment, we study how the flexibility in MTO production rate affects the optimal policy and the optimal profit. We also examine the effect of the number of alternative MTO production rates on the optimal profit. We propose three heuristic policies implementable for general cases. The first heuristic describes two linear switching functions for admission and production controls and a selection rule for MTO production rate control. The second heuristic specifies fixed thresholds for the control decisions using the local information. The third heuristic presents linear switching functions that approximate the optimal threshold curves. Unlike second and third heuristics, the first heuristic does not require a grid search to determine the control parameters. We implement numerical studies to examine the marginal impact of system parameters and the effect of the number of alternative MTO production rates on the performance of the heuristics. Compared to the optimal policy, the average percentage performance of the first and third heuristics is less than 1% for both numerical studies. On the other hand, the average percentage performance of the second heuristic is larger than 3%, and it exceeds 10% for a set of particular problem examples.     

Choice function based hyper-heuristics for multi-objective optimization

A selection hyper-heuristic is a high level search methodology which operates over a fixed set of low level heuristics. During the iterative search process, a heuristic is selected and applied to a candidate solution in hand, producing a new solution which is then accepted or rejected at each step. Selection hyper-heuristics have been increasingly, and successfully, applied to single-objective optimization problems, while work on multi-objective selection hyper-heuristics is limited. This work presents one of the initial studies on selection hyper-heuristics combining a choice function heuristic selection methodology with great deluge and late acceptance as non-deterministic move acceptance methods for multi-objective optimization. A well-known hypervolume metric is integrated into the move acceptance methods to enable the approaches to deal with multi-objective problems. The performance of the proposed hyper-heuristics is investigated on the Walking Fish Group test suite which is a common benchmark for multi-objective optimization. Additionally, they are applied to the vehicle crashworthiness design problem as a real-world multi-objective problem. The experimental results demonstrate the effectiveness of the non-deterministic move acceptance, particularly great deluge when used as a component of a choice function based selection hyper-heuristic.     

Perturbation heuristics for the pickup and delivery traveling salesman problem

This article describes and compares seven perturbation heuristics for the Pickup and Delivery Traveling Salesman Problem (PDTSP). In this problem, a shortest Hamiltonian cycle is sought through a depot and several pickup and delivery pairs. Perturbation heuristics are diversification schemes which help a local search process move away from a local optimum. Three such schemes have been implemented and compared: Instance Perturbation, Algorithmic Perturbation, and Solution Perturbation. Computational results on PDTSP instances indicate that the latter scheme yields the best results. On instances for which the optimum is known, it consistently produces optimal or near-optimal solutions.Scope and purposeIn several distribution management contexts, it is necessary to construct a shortest tour starting at a depot and making several pickup and deliveries. In the Traveling Salesman Problem with Pickup and Delivery, to each pickup point is associated a delivery point later in the tour. Like several routing problems, the PDTSP is very hard to solve to optimality and local search heuristics often get trapped in local optima. Perturbation heuristics provide a means of escaping from local optima. This paper describes and compares three types of perturbation heuristic. It shows that the best scheme consistently yields high-quality solutions.     

A software framework for fast prototyping of meta-heuristics hybridization

Hybrids of meta‐heuristics have been shown to be more effective and adaptable than their parents in solving combinatorial optimization problems. However, hybridized schemes are also more tedious to implement due to their increased complexity. We address this problem by proposing the meta‐heuristics development framework (MDF). In addition to being a framework that promotes software reuse to reduce developmental effort, the key strength of MDF lies in its ability to model meta‐heuristics using a “request, sense and response” schema, which decomposes algorithms into a set of well‐defined modules that can be flexibly assembled through a centralized controller. Under this scheme, hybrid schemes become an event‐based search that can adaptively trigger a desired parent's behavior in response to search events. MDF can hence be used to design and implement a wide spectrum of hybrids with varying degrees of collaboration, thereby offering algorithm designers quick turnaround in designing and testing their meta‐heuristics. Such technicality is illustrated in the paper through the construction of hybrid schemes using ant colony optimization and tabu search.