基于分布式约束优化的武器目标分配问题研究

为解决舰艇编队协同防空中的武器目标分配(WTA)问题,提出一种将WTA问题建模为分布式约束优化问题的方法。介绍求解分布式约束优化问题的2个典型算法ADOPT和DPOP。通过Frodo软件平台对舰艇拦截多批反舰导弹过程进行仿真,比较2个算法在仿真时间、通信量等方面的性能,结果证明了该方法求解WTA问题的可行性。     

ADOPT-ing: unifying asynchronous distributed optimization with asynchronous backtracking

This article presents an asynchronous algorithm for solving distributed constraint optimization problems (DCOPs). The proposed technique unifies asynchronous backtracking (ABT) and asynchronous distributed optimization (ADOPT) where valued nogoods enable more flexible reasoning and more opportunities for communication, leading to an important speed-up. While feedback can be sent in ADOPT by COST messages only to one predefined predecessor, our extension allows for sending such information to any relevant agent. The concept of valued nogood is an extension by Dago and Verfaille of the concept of classic nogood that associates the list of conflicting assignments with a cost and, optionally, with a set of references to culprit constraints. DCOPs have been shown to have very elegant distributed solutions, such as ADOPT, distributed asynchronous overlay (DisAO), or DPOP. These algorithms are typically tuned to minimize the longest causal chain of messages as a measure of how the algorithms will scale for systems with remote agents (with large latency in communication). ADOPT has the property of maintaining the initial distribution of the problem. To be efficient, ADOPT needs a preprocessing step consisting of computing a Depth-First Search (DFS) tree on the constraint graph. Valued nogoods allow for automatically detecting and exploiting the best DFS tree compatible with the current ordering. To exploit such DFS trees it is now sufficient to ensure that they exist. Also, the inference rules available for valued nogoods help to exploit schemes of communication where more feedback is sent to higher priority agents. Together they result in an order of magnitude improvement.     

A novel end‐to‐end deep learning scheme for classifying multi‐class motor imagery electroencephalography signals

An important subfield of brain–computer interface is the classification of motor imagery (MI) signals where a presumed action, for example, imagining the hands' motions, is mentally simulated. The brain dynamics of MI is usually measured by electroencephalography (EEG) due to its noninvasiveness. The next generation of brain–computer interface systems can benefit from the generative deep learning (GDL) models by providing end‐to‐end (e2e) machine learning and increasing their accuracy. In this study, to exploit the e2e‐property of deep learning models, a novel GDL methodology is proposed where only minimal objective‐free preprocessing steps are needed. Furthermore, to deal with the complicated multi‐class MI–EEG signals, an innovative multilevel GDL‐based classifying scheme is proposed. The effectiveness of the proposed model and its robustness against noisy MI–EEG signals is evaluated using two different GDL models, that is, deep belief network and stacked sparse autoencoder in e2e manner. Experimental results demonstrate the effectiveness of the proposed methodology with improved accuracy compared with the widely used filter bank common spatial patterns algorithm.     

Optimal Sorting Algorithms for a Simplified 2D Array with Reconfigurable Pipelined Bus System

In recent years, many researchers have investigated optical interconnections as parallel computing. Optical interconnections are attractive due to their high bandwidth and concurrent access to the bus in a pipelined fashion. The Linear Array with Reconfigurable Pipelined Bus System (LARPBS) model is a powerful optical bus system that combines both the advantages of optical buses and reconfiguration. To increase the scalability of the LARPBS model, we propose a two-dimensional extension: a simplified two-dimensional Array with Reconfigurable Pipelined Bus System (2D ARPBS). While achieving better scalability, we show the effectiveness of this newly proposed model by designing two novel optimal sorting algorithms on this model. The first sorting algorithm is an extension of Leighton's seven-phase columnsort algorithm that eliminates the restriction of sorting only an r times s array, where r ge s^2 , and sorts an n times n array in O(log n) time. The second one is an optimal multiway mergesort algorithm that uses a novel processor efficient two-way mergesort algorithm and a novel multiway merge scheme to sort n^2 items in O(log n) time. Using an optimal sorting algorithm Pipelined Mergesort designed for the LARPBS model as a building block, we extend our research on parallel sorting on the LARPBS to a more scalable 2D ARPBS model and achieve optimality in both sorting algorithms.     

State inverse and decorrelated state stochastic approximation

Stochastic approximation algorithms for parameter identification are derived by a sequential optimization and weighted averaging procedure with an instructive geometric interpretation. Known algorithms including standard least squares and suboptimal versions requiring less computational effort are thereby derived. More significantly, novel schemes emerge from the theory which, in the cases studied to date and reported here, converge much more rapidly than their nearest rivals amongst the class of known simple schemes. The novel algorithms are distinguished from the known ones by either a different step size selection, and/or by working with a transformed state variable with components relatively less correlated, and/or by replacing the state vector in a crucial part of the calculations by its componentwise pseudoinverse.The convergence rate of the novel schemes in our simulations is significantly closer to that of the more sophisticated optimal least square recursions than other stochastic approximations schemes in the literature. For the case of extended least squares and recursive maximum likelihood schemes, the novel stochastic recursion performs, in loose terms within a factor of 10 (rms error), of the more sophisticated schemes in the literature. An asymptotic convergence analysis for the algorithms is a minor extension of known theory.     

A constrained optimization perspective on actor–critic algorithms and application to network routing

We propose a novel actor–critic algorithm with guaranteed convergence to an optimal policy for a discounted reward Markov decision process. The actor incorporates a descent direction that is motivated by the solution of a certain non-linear optimization problem. We also discuss an extension to incorporate function approximation and demonstrate the practicality of our algorithms on a network routing application.     

Classification of gene-expression data: The manifold-based metric learning way

Classification of microarray gene-expression data can potentially help medical diagnosis, and becomes an important topic in bioinformatics. However, microarray data sets are usually of small sample size relative to an overwhelming number of genes. This makes the classification problem fairly challenging. Instance-based learning (IBL) algorithms, such as nearest neighbor (k-NN), are usually the baseline algorithm due to their simplicity. However, practices show that k-NN performs not very well in this field. This paper introduces manifold-based metric learning to improve the performance of IBL methods. A novel metric learning algorithm is proposed by utilizing both local manifold structural information and local discriminant information. In addition, a random subspace extension is also presented. We apply the proposed algorithm to the gene-classification problem in three ways: one in the original feature space, another in the reduced feature space, and the third via the random subspace extension. Statistical evaluation shows that the proposed algorithm can achieve promising results, and gain significant performance improvement over traditional IBL algorithms.     

一种蓝牙分散网拓扑形成算法的设计与实现

针对现有的蓝牙分散网拓扑形成算法的动态性和自愈性较差的问题，提出了一种新算法.该算法综合考虑了对分散网互连有显著影响的微微网的个数、负载均衡和结点移动性等因素，使最终得到的分散网拓扑是一个异构的、局部互连网状的结构，该结构具有较强自愈和容错能力.利用BlueHoc蓝牙扩展模块在NS-2仿真器上对算法进行了模拟.结果显示，提出的算法可以有效地用于蓝牙分散网拓扑结构的创建.     

Path Planning for Autonomous Underwater Vehicles

Efficient path-planning algorithms are a crucial issue for modern autonomous underwater vehicles. Classical path-planning algorithms in artificial intelligence are not designed to deal with wide continuous environments prone to currents. We present a novel Fast Marching (FM)-based approach to address the following issues. First, we develop an algorithm we call FM* to efficiently extract a 2-D continuous path from a discrete representation of the environment. Second, we take underwater currents into account thanks to an anisotropic extension of the original FM algorithm. Third, the vehicle turning radius is introduced as a constraint on the optimal path curvature for both isotropic and anisotropic media. Finally, a multiresolution method is introduced to speed up the overall path-planning process     

Morphable Surface Models

We describe a novel automatic technique for finding a dense correspondence between a pair of n-dimensional surfaces with arbitrary topologies. This method employs a different formulation than previous correspondence algorithms (such as optical flow) and includes images as a special case. We use this correspondence algorithm to build Morphable Surface Models (an extension of Morphable Models) from examples. We present a method for matching the model to new surfaces and demonstrate their use for analysis, synthesis, and clustering.     

Multiobjective optimization using population-based extremal optimization

In recent years, a general-purpose local-search heuristic method called Extremal Optimization (EO) has been successfully applied in some NP-hard combinatorial optimization problems. In this paper, we present a novel Pareto-based algorithm, which can be regarded as an extension of EO, to solve multiobjective optimization problems. The proposed method, called Multiobjective Population-based Extremal Optimization (MOPEO), is validated by using five benchmark functions and metrics taken from the standard literature on multiobjective evolutionary optimization. The experimental results demonstrate that MOPEO is competitive with the state-of-the-art multiobjective evolutionary algorithms. Thus MOPEO can be considered as a viable alternative to solve multiobjective optimization problems.     

A theoretical and empirical study on unbiased boundary-extended crossover for real-valued representation

We present a new crossover operator for real-coded genetic algorithms employing a novel methodology to remove the inherent bias of pre-existing crossover operators. This is done by transforming the topology of the hyper-rectangular real space by gluing opposite boundaries and designing a boundary extension method for making the fitness function smooth at the glued boundary. We show the advantages of the proposed crossover by comparing its performance with those of existing ones on test functions that are commonly used in the literature, and a nonlinear regression on a real-world dataset.     

Cognitive outcomes from the Game-Design and Learning (GDL) after-school program

The Game-Design and Learning (GDL) initiative engages middle school students in the process of game-design in a variety of in-school, after-school, and summer camp settings. The goal of the GDL initiative is to leverage students' interests in games and design to foster their problem-solving and critical reasoning skills. The present study examines the effectiveness of an after-school version of the GDL program using a quasi-experimental design. Students enrolled in the GDL program were guided in the process of designing games aimed at solving problems. Compared to students in a control group who did not attend the program (n = 24), the children who attended the GDL program (n = 20) showed a significant increase in their problem-solving skills. The results provide empirical support for the hypothesis that participation in the GDL program leads to measurable cognitive changes in children's problem-solving skills. This study bears important implications for educators and theory.     

An effective approximation algorithm for the Malleable Parallel Task Scheduling problem

The Malleable Parallel Task Scheduling problem (MPTS) is an extension of one of the most classic scheduling problems (P∥C_max). The only difference is that for MPTS, each task can be processed simultaneously by more than one processor. Such flexibility could dramatically reduce the makespan, but greatly increase the difficulty for solving the problem. By carefully analyzing some existing algorithms for MPTS, we find each of them suitable for some specific cases, but none is effective enough for all cases. Based on such observations, we introduce some optimization algorithms and improving techniques for MPTS, with their performance analyzed in theory. Combining these optimization algorithms and improving techniques gives rise to our novel scheduling algorithm OCM (Optimizations Combined for MPTS), a 2-approximation algorithm for MPTS. Extensive simulations on random datasets and SPLASH-2 benchmark reveal that for all cases, schedules produced by OCM have smaller makespans, compared with other existing algorithms.     

A formally based parallelization of data mining algorithms for multi-core systems

We describe a novel, systematic approach to efficiently parallelizing data mining algorithms: starting with the representation of an algorithm as a sequential composition of functions, we formally transform it into a parallel form using higher-order functions for specifying parallelism. We implement the approach as an extension of the industrial-strength Java-based library Xelopes, and we illustrate its use by developing a multi-threaded Java program for the popular naive Bayes classification algorithm. In comparison with the popular MapReduce programming model, our resulting programs enable not only data-parallel, but also task-parallel implementation and a combination of both. Our experiments demonstrate an efficient parallelization and good scalability on multi-core processors.

     

Skyblocking for entity resolution

In this paper, we introduce a novel framework for entity resolution blocking, called skyblocking, which aims to learn scheme skylines. In this skyblocking framework, each blocking scheme is mapped as a point to a multi-dimensional scheme space where each blocking measure represents one dimension. A scheme skyline contains blocking schemes that are not dominated by any other blocking schemes in the scheme space. To efficiently learn scheme skylines, two challenges exist: one is the class imbalance problem and the other is the search space problem. We tackle these two challenges by developing an active sampling strategy and a scheme extension strategy. Based on these two strategies, we develop three scheme skyline learning algorithms for efficiently learning scheme skylines under a given number of blocking measures and within a label budget limit. We experimentally verify that our algorithms outperform the baseline approaches in all of the following aspects: label efficiency, blocking quality and learning efficiency, over five real-world datasets.     

Join-Idle-Queue: A novel load balancing algorithm for dynamically scalable web services

The prevalence of dynamic-content web services, exemplified by search and online social networking, has motivated an increasingly wide web-facing front end. Horizontal scaling in the Cloud is favored for its elasticity, and distributed design of load balancers is highly desirable. Existing algorithms with a centralized design, such as Join-the-Shortest-Queue (JSQ), incur high communication overhead for distributed dispatchers.We propose a novel class of algorithms called Join-Idle-Queue (JIQ) for distributed load balancing in large systems. Unlike algorithms such as Power-of-Two, the JIQ algorithm incurs no communication overhead between the dispatchers and processors at job arrivals. We analyze the JIQ algorithm in the large system limit and find that it effectively results in a reduced system load, which produces 30-fold reduction in queueing overhead compared to Power-of-Two at medium to high load. An extension of the basic JIQ algorithm deals with very high loads using only local information of server load.     

动态搜索算法求解时间依赖型旅行商问题研究

时间依赖型旅行商问题(TDTSP)是旅行商问题(TSP)的延伸.在该问题中,任意两节点间的旅行时间(成本)不仅取决于节点间的距离,还依赖于一天中具体时段或节点在哈密顿圈中所处的具体位置.对基于节点所处哈密顿圈中具体位置的TDTSP问题建立相应的数学模型,并提出求解该问题的动态搜索算法.通过实验仿真,验证了动态搜索算法优于目前在邻域搜索领域求解该问题最有效的动态规划启发式算法.     

Binary particle swarm optimization with multiple evolutionary strategies

This paper introduces a novel variation of binary particle swarm optimization(BPSO) algorithm and a further extension to improve its performance.Firstly,mimicking the behaviors of some creatures group,multiple evolutionary strategies BPSO(MBPSO) is introduced which takes different evolutionary strategies for various particles according to their performances.Then,on the basis of MBPSO,a new strategy is discussed to improve the performance of the MBPSO(M2BPSO) which adopts the concept of the mutation operator aiming to overcome the premature convergence and slow convergent speed during the later stages of the optimization.The proposed two algorithms are tested on seven benchmark functions and their results are compared with those obtained by other methods.Experimental results show that our methods outperform the other algorithms.