A stochastic Kaczmarz algorithm for network tomography

We develop a stochastic approximation version of the classical Kaczmarz algorithm that is incremental in nature and takes as input noisy real time data. Our analysis shows that with probability one it mimics the behavior of the original scheme: starting from the same initial point, our algorithm and the corresponding deterministic Kaczmarz algorithm converge to precisely the same point. The motivation for this work comes from network tomography where network parameters are to be estimated based upon end-to-end measurements. Numerical examples via Matlab based simulations demonstrate the efficacy of the algorithm.     

On a generalization of Bernstein polynomials and Bézier curves based on umbral calculus

In Winkel (2001) a generalization of Bernstein polynomials and Bézier curves based on umbral calculus has been introduced. In the present paper we describe new geometric and algorithmic properties of this generalization including: (1) families of polynomials introduced by Stancu (1968) and Goldman (1985), i.e., families that include both Bernstein and Lagrange polynomial, are generalized in a new way, (2) a generalized de Casteljau algorithm is discussed, (3) an efficient evaluation of generalized Bézier curves through a linear transformation of the control polygon is described, (4) a simple criterion for endpoint tangentiality is established.     

Solving a multi-floor layout design model of a dynamic cellular manufacturing system by an efficient genetic algorithm

This paper presents a mixed-integer programming model for a multi-floor layout design of cellular manufacturing systems (CMSs) in a dynamic environment. A novel aspect of this model is to concurrently determine the cell formation (CF) and group layout (GL) as the interrelated decisions involved in the design of a CMS in order to achieve an optimal (or near-optimal) design solution for a multi-floor factory in a multi-period planning horizon. Other design aspects are to design a multi-floor layout to form cells in different floors, a multi-rows layout of equal area facilities in each cell, flexible reconfigurations of cells during successive periods, distance-based material handling cost, and machine depot keeping idle machines. This model incorporates with an extensive coverage of important manufacturing features used in the design of CMSs. The objective is to minimize the total costs of intra-cell, inter-cell, and inter-floor material handling, purchasing machines, machine processing, machine overhead, and machine relocation. Two numerical examples are solved by the CPLEX software to verify the performance of the presented model and illustrate the model features. Since this model belongs to NP-hard class, an efficient genetic algorithm (GA) with a matrix-based chromosome structure is proposed to derive near-optimal solutions. To verify its computational efficiency in comparison to the CPLEX software, several test problems with different sizes and settings are implemented. The efficiency of the proposed GA in terms of the objective function value and computational time is proved by the obtained results.     

Hybrid shuffled frog leaping algorithm for energy-efficient dynamic consolidation of virtual machines in cloud data centers

Cloud computing aims to provide dynamic leasing of server capabilities as scalable virtualized services to end users. However, data centers hosting cloud applications consume vast amounts of electrical energy, thereby contributing to high operational costs and carbon footprints. Green cloud computing solutions that can not only minimize the operational costs but also reduce the environmental impact are necessary. This study focuses on the Infrastructure as a Service model, where custom virtual machines (VMs) are launched in appropriate servers available in a data center. A complete data center resource management scheme is presented in this paper. The scheme can not only ensure user quality of service (through service level agreements) but can also achieve maximum energy saving and green computing goals. Considering that the data center host is usually tens of thousands in size and that using an exact algorithm to solve the resource allocation problem is difficult, the modified shuffled frog leaping algorithm and improved extremal optimization are employed in this study to solve the dynamic allocation problem of VMs. Experimental results demonstrate that the proposed resource management scheme exhibits excellent performance in green cloud computing.     

Text classification using genetic algorithm oriented latent semantic features

In this paper, genetic algorithm oriented latent semantic features (GALSF) are proposed to obtain better representation of documents in text classification. The proposed approach consists of feature selection and feature transformation stages. The first stage is carried out using the state-of-the-art filter-based methods. The second stage employs latent semantic indexing (LSI) empowered by genetic algorithm such that a better projection is attained using appropriate singular vectors, which are not limited to the ones corresponding to the largest singular values, unlike standard LSI approach. In this way, the singular vectors with small singular values may also be used for projection whereas the vectors with large singular values may be eliminated as well to obtain better discrimination. Experimental results demonstrate that GALSF outperforms both LSI and filter-based feature selection methods on benchmark datasets for various feature dimensions.     

An analytical framework for integrated maritime terminal scheduling problems with time windows

Container transport, an integral part of intercontinental trade, has steadily increased over the past few decades. The productivity of such a system, in part, hinges on the efficient allocation of terminal resources such that the container transit time is minimized. This study provides an analytical framework, which entails efficient scheduling of quay and yard cranes, to minimize the time spent by containers at a terminal. A mixed-integer programming model is developed to capture the two-stage multi-processor characteristic of the problem, where each crane has specific time window availability. A genetic algorithm equipped with a novel decoding procedure is developed. The mixed-integer model is tested on a number of problem instances of varying sizes to gain managerial insights.     

动态格点搜索的改进算法用于团簇结构快速优化

结合高效的动态格点搜索(DLS)算法与扰动操作(Perturbation Operation)提出一种新的改进方法(DLS-PO),用于确定团簇的最低能量结构。针对一个特定构型,DLS算法总能给出其对应搜索空间的最规则结构。然而,一次失败的DLS优化将消耗大量的运算资源。为此,采取原子移动和结构旋转的扰动操作成功地改变了构型,再结合后续的DLS操作,提高了优化效率。将该算法用于原子数高达309的Lennard-Jones团簇及100原子NP-B函数铝团簇的结构优化。优化结果显示相比于DLS算法,DLS-PO算法更为高效。     

一种混合的离散细菌菌落优化算法

为了利用细菌算法解决组合优化问题, 提出了一种混合的离散细菌菌落优化算法。根据现有细菌优化算法, 设计一种新的个体编码方式及进化模式, 通过设计种群的自适应调整因子增强个体活力, 并融合禁忌搜索算法, 克服算法易于陷入过早收敛的不足, 并与其他算法在Taillard标准调度测试问题集上比较实验, 验证了算法的有效性。仿真结果表明, 该算法可以搜索到问题的最优组合, 能够有效避免算法陷入局部最优, 取得了满意的结果。     

基于局部自适应先验MRF模型的快速BP图像分割算法

针对常规MRF分割模型不能有效描述图像的局部特征、常导致图像的过分割现象,提出了一种局部自适应先验的MRF模型。该模型利用图像的邻接区域信息建立了一种局部自适应特征MRF模型。基于提出的模型,建立了一种具有快速收敛策略的区域BP算法对MRF模型的区域消息进行传递,有效解决了区域BP算法的计算量大的问题。实验结果表明,与常规区域BP算法相比,提出的分割方法具有更快的分割速度和精度。     

空间资源索引与top-k查询研究

以空间资源索引结构R-tree为基础, 考虑人们对空间资源能力指标的要求, 利用道路网络模型进行空间距离的计算, 提出了一种包含能力维度信息的空间资源索引结构和top-k查询算法, 并与传统遍历算法进行对比实验, 验证了查询算法的有效性。