基于协方差矩阵调整的多目标多任务优化算法

多任务进化（EMT）是进化计算领域的一个新兴研究方向,区别于传统的单任务搜索算法,EMT通过在任务间传递有用知识,对多个任务同时实施进化搜索,以提升多个任务的收敛性能。目前,大多数进化算法只考虑了知识迁移而忽略了任务间的联系。提出一种多目标多任务优化算法,结合迁移学习的思想,采用任务间种群的协方差矩阵差异表示任务间种群分布特征差异,使用任务间种群均值的距离表示任务间种群的分布距离,并通过任务间种群的分布特征差异和分布距离表示任务间的相似度。对于某个目标任务,将其最相似任务中的解集实施K最近邻分类,以筛选出对目标任务有价值的解,并使其迁移到目标任务中。实验结果表明,与EMTSD、MaTEA、MO-MFEA-II等多目标多任务优化算法相比,所提算法具有较佳的收敛性能,平均运行效率约提高了66.62%。     

JAMES: An object‐oriented Java framework for discrete optimization using local search metaheuristics

This paper describes the Java Metaheuristics Search framework (JAMES, v1.1): an object‐oriented Java framework for discrete optimization using local search algorithms that exploits the generality of such metaheuristics by clearly separating search implementation and application from problem specification. A wide range of generic local searches are provided, including (stochastic) hill climbing, tabu search, variable neighbourhood search and parallel tempering. These can be applied to any user‐defined problem by plugging in a custom neighbourhood for the corresponding solution type. Using an automated analysis workflow, the performance of different search algorithms can be compared in order to select an appropriate optimization strategy. Implementations of specific components are included for subset selection, such as a predefined solution type, generic problem definition and several subset neighbourhoods used to modify the set of selected items. Additional components for other types of problems (e.g. permutation problems) are provided through an extensions module which also includes the analysis workflow. In comparison with existing Java metaheuristics frameworks that mainly focus on population‐based algorithms, JAMES has a much lower memory footprint and promotes efficient application of local searches by taking full advantage of move‐based evaluation. Releases of JAMES are deployed to the Maven Central Repository so that the framework can easily be included as a dependency in other Java applications. The project is fully open source and hosted on GitHub. More information can be found at http://www.jamesframework.org . Copyright © 2016 John Wiley & Sons, Ltd.     

Evolutionary squeaky wheel optimization: a new framework for analysis

Squeaky wheel optimization (SWO) is a relatively new metaheuristic that has been shown to be effective for many real-world problems. At each iteration SWO does a complete construction of a solution starting from the empty assignment. Although the construction uses information from previous iterations, the complete rebuilding does mean that SWO is generally effective at diversification but can suffer from a relatively weak intensification. Evolutionary SWO (ESWO) is a recent extension to SWO that is designed to improve the intensification by keeping the good components of solutions and only using SWO to reconstruct other poorer components of the solution. In such algorithms a standard challenge is to understand how the various parameters affect the search process. In order to support the future study of such issues, we propose a formal framework for the analysis of ESWO. The framework is based on Markov chains, and the main novelty arises because ESWO moves through the space of partial assignments. This makes it significantly different from the analyses used in local search (such as simulated annealing) which only move through complete assignments. Generally, the exact details of ESWO will depend on various heuristics; so we focus our approach on a case of ESWO that we call ESWO-II and that has probabilistic as opposed to heuristic selection and construction operators. For ESWO-II, we study a simple problem instance and explicitly compute the stationary distribution probability over the states of the search space. We find interesting properties of the distribution. In particular, we find that the probabilities of states generally, but not always, increase with their fitness. This nonmonotonocity is quite different from the monotonicity expected in algorithms such as simulated annealing.     

Learnable tabu search guided by estimation of distribution for maximum diversity problems

This paper presents a learnable tabu search (TS) guided by estimation of distribution algorithm (EDA), called LTS-EDA, for maximum diversity problem. The LTS-EDA introduces knowledge model and can extract knowledge during the search process of TS, and thus it adopts dual or cooperative evolution/search structure, consisting of probabilistic model space in clustered EDA and solution space searched by TS. The clustered EDA, as a learnable constructive method, is used to create a new starting solution, and the simple TS, as an improvement method, attempts to improve the solution created by the clustered EDA in the LTS-EDA. A distinguishing feature of the LTS-EDA is the usage of the clustered EDA with effective linkage learning to guide TS. In the clustered EDA, different clusters (models) focus on different substructures, and the combination of information from different clusters (models) effectively combines substructures. The LTS-EDA is tested on 50 large size benchmark problems with the size ranging from 2,000 to 5,000. Simulation results show that the LTS-EDA is better than the advanced algorithms proposed recently.     

GRASP with path relinking for commercial districting

The problem of grouping basic units into larger geographic territories subject to dispersion, connectivity, and balance requirements is addressed. The problem is motivated by a real-world application from the bottled beverage distribution industry. Typically, a dispersion function is minimized as compact territories are sought. Existing literature reveals that practically all the works on commercial districting use center-based dispersion functions. These center-based functions yield mixed-integer programming models with some nice properties; however, they have the disadvantage of being very costly to be properly evaluated when used within heuristic frameworks. This is due to the center updating operations frequently needed through the heuristic search. In this work, a more robust dispersion measure based on the diameter of the formed territories is studied. This allows a more efficient heuristic search computation. For solving this particular territory design problem, a greedy randomized adaptive search procedure (GRASP) that incorporates a novel construction procedure where territories are formed simultaneously in two main stages using different criteria is proposed. This also differs from previous literature where GRASP was used to build one territory at a time. The GRASP is further enhanced with two variants of forward-backward path relinking, namely static and dynamic. Path relinking is a sophisticated and very successful search mechanism. This idea is novel in any districting or territory design application to the best of our knowledge. The proposed algorithm and its components have been extensively evaluated over a wide set of data instances. Experimental results reveal that the construction mechanism produces feasible solutions of acceptable quality, which are improved by an effective local search procedure. In addition, empirical evidence indicate that the two path relinking strategies have a significant impact on solution quality when incorporated within the GRASP framework. The ideas and components of the developed method can be further extended to other districting problems under balancing and connectivity constraints.     

Evolutionary algorithm with a directional local search for multiobjective optimization in combinatorial problems

Evolutionary algorithms (EAs) are often employed to multiobjective optimization, because they process an entire population of solutions which can be used as an approximation of the Pareto front of the tackled problem. It is a common practice to couple local search with evolutionary algorithms, especially in the context of combinatorial optimization. In this paper a new local search method is proposed that utilizes the knowledge concerning promising search directions. The proposed method can be used as a general framework and combined with many methods of iterating over a neighbourhood of an initial solution as well as various decomposition approaches. In the experiments the proposed local search method was used with an EA and tested on 2-, 3- and 4-objective versions of two well-known combinatorial optimization problems: the travelling salesman problem (TSP) and the quadratic assignment problem (QAP). For comparison two well-known local search methods, one based on Pareto dominance and the other based on decomposition, were used with the same EA. The results show that the EA coupled with the directional local search yields better results than the same EA coupled with any of the two reference methods on both the TSP and QAP problems.     

Neural networks for learning in the real world: representation, reinforcement and dynamics

It is argued that the backpropagation learning algorithm is unsuited to tackling real world problems such as sensory-motor coordination learning or the encoding of large amounts of background knowledge in neural networks. One difficulty in the real world - the unavailability of ‘teachers’ who already know the solution to problems, may be overcome by the use of reinforcement learning algorithms in place of backpropagation. It is suggested that the complexity of search space in real world neural network learning problems may be reduced if learning is divided into two components. One component is concerned with abstracting structure from the environment and hence with developing representations of stimuli. The other component involves associating and refining these representations on the basis of feedback from the environment. Time-dependent learning problems are also considered in this hybrid framework. Finally, an ‘open systems’ approach in which subsets of a network may adapt independently on the basis of spatio-temporal patterns is briefly discussed.     

Heuristic, symbolic logic and knowledge-based approach to the design and construction of buildings

The emergence of knowledge-based expert systems provide means with which one can use the computer as an aid to the solution of an ill-structured problem. Expert systems are interactive computer programs based on heuristics, incorporating judgement, rules of thumb, intuition and expertise to provide knowledgeable advice about variety of tasks. Such specialized interactive computer programs can broadly be classified as (1) identifying the relevant design knowledge, (2) providing a formalism for representing and processing the knowledge and (3) implementing the formalism in a computer environment. While the first issue of identifying the relevant knowledge is through knowledge acquisition from various domain experts and verification of the same by other domain experts. The second issue is proper formalism for the varied knowledge requiring the use of logics (prepositional calculus) as a symbolic language; heuristics or rules of thumb wherever necessary and a suitable reasoning methodology, i.e. an inference technique. The third issue is the evaluation of a suitable strategy for successful computer implementation, i.e. the computer problem is subdivided into smaller tasks which have easy solutions; and the capability of interacting the solutions of the smaller tasks into a larger framework. Therefore, this will require theorem proving, search technique and a special purpose computer language such as PROLOG or readily available domain independent shells, i.e. expert system tools. The overall synthesis of all the above is termed as a knowledge-based expert system (KBES). In this paper a KBES is developed for a highly complex building element, ‘beam design’, as part of a larger model involving planning, analysis, design, optimization and cost forecasts along with other allied services such as plumbing and electrical services. In the development of KBES; the knowledge-base is purely heuristic and subjected to alteration by numerical calculations. For an effective search the modified depth technique is adopted. Heuristics are employed to further the search as and when required from the point of view of practical computer implementation. In the overall development, use is made of dependency diagrams, charts, tables and search trees. For computer implementation the necessary tool chosen was the M1 shell developed by Teknowledge Inc., U.S.A. This requires a PC-AT with 640 kB RAM and 40 MB hard disk. A brief overview of the expert system, followed by an example problem, is presented.     

How the Beast really moves: Cayley analysis of mechanism realization spaces using CayMos

For a common class of 2D mechanisms called 1-dof tree decomposable linkages, the following fundamental problems have remained open: (a) How to canonically represent (and visualize) the connected components in the Euclidean realization space. (b) How to efficiently find two realizations representing the shortest “distance” between two connected components. (c) How to classify and efficiently find all the connected components, and the path(s) of continuous motion between two realizations in the same connected component, with or without restricting the realization type (sometimes called orientation type).For a subclass of 1-dof tree-decomposable linkages that includes many commonly studied 1-dof linkages, we solve these problems by representing a connected component of the Euclidean realization space as a curve in a carefully chosen Cayley (non-edge distance) parameter space; and proving that the representation is bijective. We also show that the above set of Cayley parameters is canonical for all generic linkages with the same underlying graph, and can be found efficiently. We add an implementation of these theoretical and algorithmic results into the new software CayMos, and give (to the best of our knowledge) the first complete analysis, visualization and new observations about the realization spaces of many commonly studied 1-dof linkages such as the amusing and well-known Strandbeest, Cardioid, Limacon and other linkages.     

Competent information search in the World Wide Web: Development and evaluation of a web training for pupils

This paper describes the development and empirical evaluation of a web training for pupils (CIS-WEB, Competent Information Search in the World Wide WEB) which aims to convey prerequisite knowledge and skills that are necessary for a competent search for information on the web. The web training focuses on competent information handling and is based on two theoretical analyses. First, a conceptual analysis of information search from the perspective of media literacy research and information retrieval research was conducted and yielded a set of five pivotal content aspects that need to be covered by a web training. Each of these content aspects is characterized by declarative and procedural knowledge components which are necessary for the pursuit of a competent search for information on the web. Second, we conducted a task analysis which conceptualizes the search for information on the web as a problem-solving process and which allows to systematically distinguish between different types of information problems. In the empirical part of the paper two classroom studies are reported. In Study 1, the widespread training concept of a technically oriented Internet training for pupils was evaluated and it was shown that no substantial improvement of web searching skills can be expected from this type of treatment. In Study 2, it was shown that the web training CIS-WEB improves pupils’ declarative knowledge of the web as well as their search performance, thereby outperforming the conventional Internet training used in Study 1.     

Existence Test for Asynchronous Interval Iteration

In the search for regions that contain fixed points of a real function of several variables, tests based on interval calculations can be used to establish existence or non-existence of fixed points in regions that are examined in the course of the search. The search can e.g. be performed as a synchronous (sequential) interval iteration: In each iteration step all components of the iterate are calculated based on the previous iterate. In this case it is straight forward to base simple interval existence and non-existence tests on the calculations done in each step of the iteration. The search can also be performed as an asynchronous (parallel) iteration: Only a few components are changed in each step and this calculation is in general based on components from different previous iterates. For the asynchronous iteration it turns out that simple tests of existence and non-existence can be based on the component wise calculations done in the course of the iteration. These component wise tests are useful for parallel implementation of the search, since the tests can then be performed local to each processor and only when a test is successful does a processor communicate this result to other processors.     

An interactive example-driven approach to graphics recognition in engineering drawings

An interactive example-driven approach to graphics recognition in engineering drawings is proposed. The scenario is that the user first interactively provides an example of a graphic object; the system instantly learns its graphical knowledge and uses the acquired knowledge to recognize the same type of graphic objects. The proposed approach represents the graphical knowledge of an object in terms of its structural components and their syntactical relationships. We summarize four types of geometric constraints for knowledge representation, based on which we develop an algorithm for knowledge acquisition. Another algorithm for graphics recognition using the acquired graphical knowledge is also proposed, which is actually a sequential examination of these constraints. In the algorithm, we first guess the next component’s attributes (e.g., size, position and orientation) by reasoning from an earlier found component and the constraint between them, and then search for this hypothetical component in the drawing. If all of the hypothetical components are found, a graphic object of this type is recognized. For improving the system’s recognition accuracy, we develop a user feedback scheme, which can update the graphical knowledge from both positive (missing) and negative (mis-recognized) examples provided by the user for subsequent recognition. Experiments have shown that our proposed approach is both efficient and effective for recognizing various types of graphic objects in engineering drawings. This paper is an extension of our papers published in ICDAR2003 and GREC2003.     

基于广度优先搜索算法的故障隔离矩阵生成方法

相关性矩阵表示故障与测试之间的逻辑关系。隔离矩阵表示在给定的测试顺序下,故障隔离与测试之间的需求关系。测试顺序对诊断费用影响可以通过隔离矩阵进行计算。所以求解隔离矩阵是诊断费用优化的前提。针对相关性矩阵与隔离矩阵易于混淆的问题,以及传统分析方法求解隔离的不足,详述隔离矩阵的概念和生成原理,设计基于广度优先搜索的隔离矩阵生成算法。示例表明,生成算法是可行的和有效的。     

A bisection method for computing the H∞ norm of a transfer matrix and related problems

We establish a correspondence between the singular values of a transfer matrix evaluated along the imaginary axis and the imaginary eigenvalues of a related Hamiltonian matrix. We give a simple linear algebraic proof, and also a more intuitive explanation based on a certain indefinite quadratic optimal control problem. This result yields a simple bisection algorithm to compute the H_∞ norm of a transfer matrix. The bisection method is far more efficient than algorithms which involve a search over frequencies, and the usual problems associated with such methods (such as determining how fine the search should be) do not arise. The method is readily extended to compute other quantities of system-theoretic interest, for instance, the minimum dissipation of a transfer matrix. A variation of the method can be used to solve the H_∞ Armijo line-search problem with no more computation than is required to compute a single H_∞ norm. Research supported in part by NSF under Grant ECS-85-52465, ONR under Grant N00014-86-K-0112, an IBM faculty development award, and Bell Communications Research.     

COEVOLUTIONARY GENETIC ALGORITHMS FOR NONCONVEX NONLINEAR PROGRAMMING PROBLEMS: REVISED GENOCOP III

In this paper, we focus on general nonconvex nonlinear programming problems and consider an applicability of genetic algorithms. For such problems, Michalewicz et al. 1995 recently proposed the coevolutionary genetic algorithm, called GENOCOP III, by introducing the concepts of search points and reference points which, respectively, satisfy the linear constraints and all of the constraints. Unfortunately, however, in GENOCOP III, since an initial population is randomly generated, it is quite difficult to generate reference points. Furthermore, a new search point is randomly generated on the line segment between a search point and a reference point and effectiveness and speed of search may be quite low. Realizing such difficulties, in this paper we propose the revised GENOCOP III by introducing a method for generating a reference point by minimizing the sum of squares of violated nonlinear constraints and a bisection method for generating a new search point on the line segment between a search point and a reference point. Through a lot of numerical experiments, both feasibility and effectiveness of the proposed method are demonstrated.     

Computer based support of reasoning in the presence of fuzziness

Many important problems encountered in managerial decision making are unstructured, making them difficult to solve by preset algorithms. Much of the complexity of such problems is due to the reasoning that is needed to construct solution procedures for each problem instance. Thus, any Decision Support System (DSS) designed for such problems should support this reasoning activity, in addition to data access and computational activities. Yet, existing DSS generally do not provide much reasoning support. One of the difficulties faced in building automated systems to support such reasoning is that much of the knowledge typically available for unstructured problems is imprecise, where imprecision may be caused by either fuzziness, uncertainty, or both. In this paper, we address the problem of supporting problem solving with fuzzy knowledge. We develop a formal method for representing fuzzy knowledge, using a framework of mathematical logic. Using this method, fuzziness in all the major constructs needed to describe knowledge can be represented. Relationships can be constructed using fuzzy operators and terms, and components in relationships can be weighted by their relative significance. Also, computational procedures and data access procedures can be directly integrated into the reasoning process. Knowledge thus represented can be manipulated using suitable reasoning mechanisms. The fuzzy inference methods we present, enable the generation of acceptable solutions to problems even when some of the knowledge used is highly imprecise and/or incomplete. Other desirable features, such as explanation of solution procedures and user participation in problem solving, are also supported by our methodology. In addition, we develop bounding procedures, which convey the imprecision in the reasoning process, and also help to reduce the complexity of the search process by pruning poor solutions. Finally, we describe a prototype system which implements the methods developed in this paper. Using example problems processed by the system, we illustrate the versatility of these methods, and also highlight their major features and potential utility in practical applications.     

An improvement on the Migrating Birds Optimization with a problem-specific neighboring function for the multi-objective task allocation problem

Allocating tasks to processors is a well-known NP-Hard problem in distributed computing systems. Due to the lack of practicable exact solutions, it has been attracted by the researchers working on heuristic-based suboptimal search algorithms. With the recent inclusion of multiple objectives such as minimizing the cost, maximizing the throughput and maximizing the reliability, the problem gets even more complex and an efficient approximate method becomes more valuable. In this work, I propose a new solution for the multi-objective task allocation problem. My solution consists in designing a problem-specific neighboring function for an existing metaheuristic algorithm that is proven to be successful in quadratic assignment problems. The neighboring function, namely greedy reassignment with maximum release (GR-MR), provides a dynamic mechanism to switch the preference of the search between the exploration and exploitation. The experiments validate both that the quality of the solutions are close to the optimal and the proposed method performs significantly better comparing to three other metaheuristic algorithms. Neighboring functions being the common reusable components of metaheuristic algorithms, GR-MR can also be utilized by other metaheuristic-based solutions in the future.     

Solving Mixed and Conditional Constraint Satisfaction Problems

Constraints are a powerful general paradigm for representing knowledge in intelligent systems. The standard constraint satisfaction paradigm involves variables over a discrete value domain and constraints which restrict the solutions to allowed value combinations. This standard paradigm is inapplicable to problems which are either:(a) mixed, involving both numeric and discrete variables, or(b) conditional,¹ containing variables whose existence depends on the values chosen for other variables, or(c) both, conditional and mixed.We present a general formalism which handles both exceptions in an integral search framework. We solve conditional problems by analyzing dependencies between constraints that enable us to directly compute all possible configurations of the CSP rather than discovering them during search. For mixed problems, we present an enumeration scheme that integrates numeric variables with discrete ones in a single search process. Both techniques take advantage of enhanced propagation rule for numeric variables that results in tighter labelings than the algorithms commonly used. From real world examples in configuration and design, we identify several types of mixed constraints, i.e. constraints defined over numeric and discrete variables, and propose new propagation rules in order to take advantage of these constraints during problem solving.     

A framework for learning in search-based systems

We provide an overall framework for learning in search based systems that are used to find optimum solutions to problems. This framework assumes that prior knowledge is available in the form of one or more heuristic functions (or features) of the problem domain. An appropriate clustering strategy is used to partition the state space into a number of classes based on the available features. The number of classes formed will depend on the resource constraints of the system. In the training phase, example problems are run using a standard admissible search algorithm. In this phase, heuristic information corresponding to each class is learned. This new information can be used in the problem solving phase by appropriate search algorithms so that subsequent problem instances can be solved more efficiently. In this framework, we also show that heuristic information of forms other than the conventional single valued underestimate value can be used, since we maintain the heuristic of each class explicitly. We show some novel search algorithms that can work with some such forms. Experimental results have been provided for some domains