Algorithm portfolio selection as a bandit problem with unbounded losses

We propose a method that learns to allocate computation time to a given set of algorithms, of unknown performance, with the aim of solving a given sequence of problem instances in a minimum time. Analogous meta-learning techniques are typically based on models of algorithm performance, learned during a separate offline training sequence, which can be prohibitively expensive. We adopt instead an online approach, named GAMBLETA, in which algorithm performance models are iteratively updated, and used to guide allocation on a sequence of problem instances. GAMBLETA is a general method for selecting among two or more alternative algorithm portfolios. Each portfolio has its own way of allocating computation time to the available algorithms, possibly based on performance models, in which case its performance is expected to improve over time, as more runtime data becomes available. The resulting exploration-exploitation trade-off is represented as a bandit problem. In our previous work, the algorithms corresponded to the arms of the bandit, and allocations evaluated by the different portfolios were mixed, using a solver for the bandit problem with expert advice, but this required the setting of an arbitrary bound on algorithm runtimes, invalidating the optimal regret of the solver. In this paper, we propose a simpler version of GAMBLETA, in which the allocators correspond to the arms, such that a single portfolio is selected for each instance. The selection is represented as a bandit problem with partial information, and an unknown bound on losses. We devise a solver for this game, proving a bound on its expected regret. We present experiments based on results from several solver competitions, in various domains, comparing GAMBLETA with another online method.     

Portfolio selection with the effect of systematic risk diversification: formulation and accelerated gradient algorithm

In this paper, we propose an optimal trade-off model for portfolio selection with the effect of systematic risk diversification, measured by the maximum marginal systematic risk of all the risk contributors. First, the classical portfolio selection model with constraints on allocation of systematic risk is shown to be equivalent to our trade-off model under certain conditions. Then, we transform the trade-off model into a special non-convex and non-smooth composite problem equivalently. Thus a modified accelerated gradient (AG) algorithm can be introduced to solve the composite problem. The efficiency of the algorithm for solving the composite problem is demonstrated by theoretical results on both the convergence rate and the iteration complexity bound. Finally, empirical analysis demonstrates that the proposed model is a preferred tool for active portfolio risk management when compared with the existing models. We also carry out a series of numerical experiments to compare the performance of the modified AG algorithm with the other three first-order algorithms.     

A genetic algorithm-based approach for solving the resource-sharing and scheduling problem

We introduce a heuristic that is based on a unique genetic algorithm (GA) to solve the resource-sharing and scheduling problem (RSSP). This problem was previously formulated as a continuous-time mixed integer linear programming model and was solved optimally using a branch-and-bound (B&B) algorithm. The RSSP considers the use of a set of resources for the production of several products. Producing each product requires a set of operations with precedence relationships among them. Each operation can be performed using alternative modes which define the subset of the resources needed, and an operation may share different resources simultaneously. The problem is to select a single mode for each operation and accordingly to schedule the resources, while minimizing the makespan time. The GA we propose is based on a new encoding schema that adopts the structure of a DNA in nature. In our experiments we compared the effectiveness and runtime of our GA versus a B&B algorithm and two truncated B&B algorithms that we developed on a set of 118 problem instances. The results demonstrate that the GA solved all the problems (10 runs each), and reaches optimality in 75% of the runs, had an average deviation of less than 1% from the optimal makespan, and a runtime that was much less sensitive to the size of the problem instance.     

Effective synchronizing algorithms

The notion of a synchronizing sequence plays an important role in the model-based testing of reactive systems, such as sequential circuits or communication protocols. The main problem in this approach is to find the shortest possible sequence which synchronizes the automaton being a model of the system under test. This can be done with a synchronizing algorithm. In this paper we analyze the synchronizing algorithms described in the literature, both exact (with exponential runtime) and greedy (polynomial). We investigate the implementation of the exact algorithm and show how this implementation can be optimized by use of some efficient data structures. We also propose a new greedy algorithm, which relies on some new heuristics. We compare our algorithms with the existing ones, with respect to both runtime and quality aspect.     

A multi-objective perspective on performance assessment and automated selection of single-objective optimization algorithms

We build upon a recently proposed multi-objective view onto performance measurement of single-objective stochastic solvers. The trade-off between the fraction of failed runs and the mean runtime of successful runs – both to be minimized – is directly analyzed based on a study on algorithm selection of inexact state-of-the-art solvers for the famous Traveling Salesperson Problem (TSP). Moreover, we adopt the hypervolume indicator (HV) commonly used in multi-objective optimization for simultaneously assessing both conflicting objectives and investigate relations to commonly used performance indicators, both theoretically and empirically. Next to Penalized Average Runtime (PAR) and Penalized Quantile Runtime (PQR), the HV measure is used as a core concept within the construction of per-instance algorithm selection models offering interesting insights into complementary behavior of inexact TSP solvers.     

动态抢占阈值调度中的快速任务选择算法

基于动态抢占阈值的实时调度算法集非抢占调度和纯抢占调度的特点,既减少了由于过多的随意抢占造成的CPU资源浪费,又保证了较高的CPU资源利用率。然而,现有的任务选择算法运行时的额外代价严重影响了系统的整体性能。针对这个问题,本文提出一种使用“选择树”作为任务队列结构的、时间复杂度为O（｜log2n｜）的快速任务选择算法。本文从理论上证明该算法正确性的同时,在使用ARM9芯片的Nokia智能手机上验证了该算法在嵌入式实时系统中的有效性。实验表明,该算法在充分利用处理器的同时能够有效降低动态阈值调度算法的额外代价。     

A divide-and-conquer recursive approach for scaling up instance selection algorithms

Instance selection is becoming more and more relevant due to the huge amount of data that is being constantly produced. However, although current algorithms are useful for fairly large datasets, scaling problems are found when the number of instances is of hundreds of thousands or millions. In the best case, these algorithms are of efficiency O(n ²), n being the number of instances. When we face huge problems, scalability is an issue, and most algorithms are not applicable. This paper presents a divide-and-conquer recursive approach to the problem of instance selection for instance based learning for very large problems. Our method divides the original training set into small subsets where the instance selection algorithm is applied. Then the selected instances are rejoined in a new training set and the same procedure, partitioning and application of an instance selection algorithm, is repeated. In this way, our approach is based on the philosophy of divide-and-conquer applied in a recursive manner. The proposed method is able to match, and even improve, for the case of storage reduction, the results of well-known standard algorithms with a very significant reduction of execution time. An extensive comparison in 30 datasets form the UCI Machine Learning Repository shows the usefulness of our method. Additionally, the method is applied to 5 huge datasets with from 300,000 to more than a million instances, with very good results and fast execution time.     

基于多摇臂赌博机的产品定价算法

针对在线零售商在不完全需求信息下的单产品定价问题,提出了一种基于多摇臂赌博机的产品定价算法。为了提升多摇臂赌博机算法在定价问题中的效果,该算法利用了需求曲线的单调性,并加入了消费者偏好识别。对消费者的保留价格进行分析得到消费者购买概率,将在线零售商的定价问题建模为多摇臂赌博机模型,给出了相应的定价算法并进行了理论分析,最后通过仿真实验比较了相关算法的定价效果。仿真结果表明该算法提高了在线零售商的收益。     

Multi-armed bandit heterogeneous ensemble learning for imbalanced data

One of the most widely used approaches to the class-imbalanced issue is ensemble learning. The base classifier is trained using an unbalanced training set in the conventional ensemble learning approach. We are unable to select the best suitable resampling method or base classifier for the training set, despite the fact that researchers have examined employing resampling strategies to balance the training set. A multi-armed bandit heterogeneous ensemble framework was developed as a solution to these issues. This framework employs the multi-armed bandit technique to pick the best base classifier and resampling techniques to build a heterogeneous ensemble model. To obtain training sets, we first employ the bagging technique. Then, we use the instances from the out-of-bag set as the validation set. In general, we consider the basic classifier combination with the highest validation set score to be the best model on the bagging subset and add it to the pool of model. The classification performance of the multi-armed bandit heterogeneous ensemble model is then assessed using 30 real-world imbalanced data sets that were gathered from UCI, KEEL, and HDDT. The experimental results demonstrate that, under the two assessment metrics of AUC and Kappa, the proposed heterogeneous ensemble model performs competitively with other nine state-of-the-art ensemble learning methods. At the same time, the findings of the experiment are confirmed by the statistical findings of the Friedman test and Holm's post-hoc test.     

Parameter tuning evolutionary algorithms for runtime versus cost trade-off in a cloud computing environment

The runtime of an evolutionary algorithm can be reduced by increasing the number of parallel evaluations. However, increasing the number of parallel evaluations can also result in wasted computational effort since there is a greater probability of creating solutions that do not contribute to convergence towards the global optimum. A trade-off, therefore, arises between the runtime and computational effort for different levels of parallelization of an evolutionary algorithm. When the computational effort is translated into cost, the trade-off can be restated as runtime versus cost. This trade-off is particularly relevant for cloud computing environments where the computing resources can be exactly matched to the level of parallelization of the algorithm, and the cost is proportional to the runtime and how many instances that are used. This paper empirically investigates this trade-off for two different evolutionary algorithms, NSGA-II and differential evolution (DE) when applied to a multi-objective discrete-event simulation (DES) problem. Both generational and steady-state asynchronous versions of both algorithms are included. The approach is to perform parameter tuning on a simplified version of the DES model. A subset of the best configurations from each tuning experiment is then evaluated on a cloud computing platform. The results indicate that, for the included DES problem, the steady-state asynchronous version of each algorithm provides a better runtime versus cost trade-off than the generational versions and that DE outperforms NSGA-II.     

局部时空域模型的核密度估计目标检测方法

针对非参数核密度估计在前期学习阶段信息冗余和计算量大,在后期背景更新阶段自适应性差需手动调整阈值和检测结果出现阴影等问题,提出一种基于局部时空域模型的核密度估计目标检测方法。在前期训练学习阶段采用K均值聚类选择关键帧,从而避免信息冗余和计算量大问题;在后期背景更新阶段,构建一种局部时空域模型,在时间域通过历史帧信息自适应调整时间域窗口大小,在空间域利用颜色和LBP描述的纹理特征消除部分阴影问题。在复杂场景下的实验结果表明,该算法在实时性和检测准确率方面有效得到提高。     

Allocating training instances to learning agents for team formation

Agents can learn to improve their coordination with their teammates and increase team performance. There are finite training instances, where each training instance is an opportunity for the learning agents to improve their coordination. In this article, we focus on allocating training instances to learning agent pairs, i.e., pairs that improve coordination with each other, with the goal of team formation. Agents learn at different rates, and hence, the allocation of training instances affects the performance of the team formed. We build upon previous work on the Synergy Graph model, that is learned completely from data and represents agents’ capabilities and compatibility in a multi-agent team. We formally define the learning agents team formation problem, and compare it with the multi-armed bandit problem. We consider learning agent pairs that improve linearly and geometrically, i.e., the marginal improvement decreases by a constant factor. We contribute algorithms that allocate the training instances, and compare against algorithms from the multi-armed bandit problem. In our simulations, we demonstrate that our algorithms perform similarly to the bandit algorithms in the linear case, and outperform them in the geometric case. Further, we apply our model and algorithms to a multi-agent foraging problem, thus demonstrating the efficacy of our algorithms in general multi-agent problems.     

Algorithms for unconstrained global optimization of nonlinear (polynomial) programming problems: The single and multi-segment polynomial B-spline approach

We investigate the use of the polynomial B-spline form for unconstrained global optimization of multivariate polynomial nonlinear programming problems. We use the B-spline form for higher order approximation of multivariate polynomials. We first propose a basic algorithm for global optimization that uses several accelerating algorithms such as cut-off test and monotonicity test. We then propose an improved algorithm consisting of several additional ingredients, such as a new subdivision point selection rule and a modified subdivision direction selection rule. The performances of the proposed basic and improved algorithms are tested and compared on a set of 14 test problems under two test conditions. The results of the tests show the superiority of the improved algorithm with multi-segment B-spline over that of the single segment B-spline, in terms of the chosen performance metrics. We also compare the quality of the set of all global minimizers found using the proposed algorithms (basic & improved) with those using well-known solvers BARON and Gloptipoly, on a smaller set of four test problems. The problems in the latter set have multiple global minimizers. The results show the superiority of the proposed algorithms, in that they are able to capture all the global minimizers, whereas Gloptipoly and BARON fail to do so in some of the test problems.     

When architecture meets AI: A deep reinforcement learning approach for system of systems design

How to design System of Systems has been widely concerned in recent years, especially in military applications. This problem is also known as SoS architecting, which can be boiled down to two subproblems: selecting a number of systems from a set of candidates and specifying the tasks to be completed for each selected system. Essentially, such a problem can be reduced to a combinatorial optimization problem. Traditional exact solvers such as branch-bound algorithm are not efficient enough to deal with large scale cases. Heuristic algorithms are more scalable, but if input changes, these algorithms have to restart the searching process. Re-searching process may take a long time and interfere with the mission achievement of SoS in highly dynamic scenarios, e.g., in the Mosaic Warfare. In this paper, we combine artificial intelligence with SoS architecting and propose a deep reinforcement learning approach DRL-SoSDP for SoS design. Deep neural networks and actor–critic algorithms are used to find the optimal solution with constraints. Evaluation results show that the proposed approach is superior to heuristic algorithms in both solution quality and computation time, especially in large scale cases. DRL-SoSDP can find great solutions in a near real-time manner, showing great potential for cases that require an instant reply. DRL-SoSDP also shows good generalization ability and can find better results than heuristic algorithms even when the scale of SoS is much larger than that in training data.     

Bandit problems and the exploration/exploitation tradeoff

We explore the two-armed bandit with Gaussian payoffs as a theoretical model for optimization. The problem is formulated from a Bayesian perspective, and the optimal strategy for both one and two pulls is provided. We present regions of parameter space where a greedy strategy is provably optimal. We also compare the greedy and optimal strategies to one based on a genetic algorithm. In doing so, we correct a previous error in the literature concerning the Gaussian bandit problem and the supposed optimality of genetic algorithms for this problem. Finally, we provide an analytically simple bandit model that is more directly applicable to optimization theory than the traditional bandit problem and determine a near-optimal strategy for that model     

Corruption-tolerant bandit learning

We present algorithms for solving multi-armed and linear-contextual bandit tasks in the face of adversarial corruptions in the arm responses. Traditional algorithms for solving these problems assume that nothing but mild, e.g., i.i.d. sub-Gaussian, noise disrupts an otherwise clean estimate of the utility of the arm. This assumption and the resulting approaches can fail catastrophically if there is an observant adversary that corrupts even a small fraction of the responses generated when arms are pulled. To rectify this, we propose algorithms that use recent advances in robust statistical estimation to perform arm selection in polynomial time. Our algorithms are easy to implement and vastly outperform several existing UCB and EXP-style algorithms for stochastic and adversarial multi-armed and linear-contextual bandit problems in wide variety of experimental settings. Our algorithms enjoy minimax-optimal regret bounds, as well as can tolerate an adversary that is allowed to corrupt upto a universally constant fraction of the arms pulled by the algorithm.

     

Reformulations and algorithms for the optimization of switching decisions in nonlinear optimal control

In model-based nonlinear optimal control switching decisions that can be optimized often play an important role. Prominent examples of such hybrid systems are gear switches for transport vehicles or on/off valves in chemical engineering. Optimization algorithms need to take the discrete nature of the variables that model these switching decisions into account. Unnecessarily, for many applications still an equidistant time discretization and either rounding or standard mixed-integer solvers are used. In this article we survey recent progress in theoretical bounds, reformulations, and algorithms for this problem class and show how process control can benefit from them. We propose a comprehensive algorithm based on the solution of a sequence of purely continuous problems and simulations, and provide a new and more compact proof for its well-posedness. Instead of focusing on a particular application, we classify different solution behaviors in the applications section. We provide references to respective case studies with prototype character and cite newly emerging benchmark libraries. We conclude by pointing out future challenges for process control with switching decisions.     

Improved Parameterized Set Splitting Algorithms: A Probabilistic Approach

In this paper, we study parameterized algorithms for the set splitting problem, for both weighted and unweighted versions. First, we develop a new and effective technique based on a probabilistic method that allows us to develop a simpler and more efficient deterministic kernelization algorithm for the unweighted set splitting problem. We then propose a randomized algorithm for the weighted set splitting problem that is based on a new subset partition technique and has its running time bounded by O ^*(2 ^k ), which is significantly better than that of the previous best deterministic algorithm (which only works for the simpler unweighted set splitting problem) of running time O ^*(2.65 ^k ). We also show that our algorithm can be de-randomized, which leads to a deterministic parameterized algorithm of running time O ^*(4 ^k ) for the weighted set splitting problem and gives the first proof that the problem is fixed-parameter tractable. A preliminary version of this paper was presented at The 13th Annual International Computing and Combinatorics Conference (COCOON 2007), Banff, Canada, July 2007, LNCS vol. 4598, pp. 537–547. This work was supported in part by the National Science Foundation under the Grant CCF-0430683.     

Normal-Based Bas-Relief Modelling via Near-Lighting Photometric Stereo

We present a n ear- l ighting p hotometric s tereo (NL-PS) system to produce digital bas-reliefs from a physical object (set) directly. Unlike both the 2D image and 3D model-based modelling methods that require complicated interactions and transformations, the technique using NL-PS is easy to use with cost-effective hardware, providing users with a trade-off between abstract and representation when creating bas-reliefs. Our algorithm consists of two steps: normal map acquisition and constrained 3D reconstruction. First, we introduce a lighting model, named the q uasi- p oint l ighting m odel (QPLM), and provide a two-step calibration solution in our NL-PS system to generate a dense normal map. Second, we filter the normal map into a detail layer and a structure layer, and formulate detail- or structure-preserving bas-relief modelling as a constrained surface reconstruction problem of solving a sparse linear system. The main contribution is a WYSIWYG (i.e. what you see is what you get) way of building new solvers that produces multi-style bas-reliefs with their geometric structures and/or details preserved. The performance of our approach is experimentally validated via comparisons with the state-of-the-art methods.     

Prioritizing Point-Based POMDP Solvers

Recent scaling up of partially observable Markov decision process (POMDP) solvers toward realistic applications is largely due to point-based methods that quickly converge to an approximate solution for medium-sized domains. These algorithms compute a value function for a finite reachable set of belief points, using backup operations. Point-based algorithms differ on the selection of the set of belief points and on the order by which backup operations are executed on the selected belief points. We first show how current algorithms execute a large number of backups that can be removed without reducing the quality of the value function. We demonstrate that the ordering of backup operations on a predefined set of belief points is important. In the simpler domain of MDP solvers, prioritizing the order of equivalent backup operations on states is known to speed up convergence. We generalize the notion of prioritized backups to the POMDP framework, showing how existing algorithms can be improved by prioritizing backups. We also present a new algorithm, which is the prioritized value iteration, and show empirically that it outperforms current point-based algorithms. Finally, a new empirical evaluation measure (in addition to the standard runtime comparison), which is based on the number of atomic operations and the number of belief points, is proposed in order to provide more accurate benchmark comparisons.