Multi-objectives Tabu Search based algorithm for progressive resource allocation

Military course of action planning involves time and space synchronization as well as resource and asset allocation. A mission could be seen as a defined set of logical ordered tasks with time and space constraints. The resources to task rules require that available assets should be allocated to each task. A combination of assets might be required to execute a given task. The couple (task, resources) constitutes an action. This problem is formulated as a multi-objectives scheduling and resource allocation problem. Any solution is assessed based on a number of conflicting and heterogeneous objectives. In fact, military planning officers should keep perfecting the plan based on the Commander’s criteria for success. The scheduling problem and resource allocation problem are considered as NP-Hard Problems [A. Guitouni, B. Urli, J.-M. Martel, Course of action planning: A project based modelling, Working Paper, Faculté des sciences de l’ administration, Université Laval, Québec, 2005]. This paper is concerned with the multi-objectives resource allocation problem. Our objective is to find adequate resource allocation for given courses of action schedule. To optimize this problem, this paper investigates non-exact solution methods, like meta-heuristic methods for finding potential efficient solutions. A progressive resource allocation methodology is proposed based on Tabu Search and multi-objectives concepts. This technique explores the search space so as to find a set of potential efficient solutions without aggregating the objectives into a single objective function. It is guided by the principle of maximizing the usage of any resource before considering a replacement resource. Thus, a given resource is allocated to the maximum number of tasks for a given courses of action schedule. A good allocation is a potential efficient solution. These solutions are retained by applying a combination of a dominance rule and a multi-criteria filtering method. The performance of the proposed Pareto-based approach is compared to two aggregation approaches: weighted-sum and the lexicographic techniques. The result shows that a Pareto-based approach is providing better solutions and allowing more flexibility to the decision-maker.     

Comparison of Krylov subspace methods on the PageRank problem

PageRank algorithm plays a very important role in search engine technology and consists in the computation of the eigenvector corresponding to the eigenvalue one of a matrix whose size is now in the billions. The problem incorporates a parameter that determines the difficulty of the problem. In this paper, the effectiveness of stationary and nonstationary methods are compared on some portion of real web matrices for different choices of . We see that stationary methods are very reliable and more competitive when the problem is well conditioned, that is for small values of . However, for large values of the parameter the problem becomes more difficult and methods such as preconditioned BiCGStab or restarted preconditioned GMRES become competitive with stationary methods in terms of Mflops count as well as in number of iterations necessary to reach convergence.     

Designing delivery districts for the vehicle routing problem with stochastic demands

This paper considers the problem of designing districts for vehicle routing problems with stochastic demands. In particular, demands are assumed to be uncertain at the time when the districts are made, and these are revealed only after the districting decisions are determined. Tabu search and multistart heuristics for this stochastic districting problem are developed and compared. Computational results show that tabu search is superior over multistart.     

A hybrid tabu search/branch & bound approach to solving the generalized assignment problem

A new approach for solving the generalized assignment problem (GAP) is proposed that combines the exact branch & bound approach with the heuristic strategy of tabu search (TS) to produce a hybrid algorithm for solving GAP. The algorithm described uses commercial software to solve sub-problems generated by the TS guiding strategy. The TS approach makes use of the concept of referent domain optimisation and introduces novel add/drop strategies. In addition, the linear programming relaxation of GAP that forms part of the branch & bound approach is itself helpful in suggesting which variables might take binary values. Computational results on benchmark test instances are presented and compared with results obtained by the standard branch & bound approach and also several other heuristic approaches from the literature. The results show the new algorithm performs competitively against the alternatives and is able to find some new best solutions for several benchmark instances.     

Precise and global identification of phospholipid molecular species by an Orbitrap mass spectrometer and automated search engine Lipid Search

In the present research, we have established a new lipidomics approach for the comprehensive and precise identification of molecular species in a crude lipid mixture using a LTQ Orbitrap mass spectrometer (MS) and reverse-phase liquid chromatography (RPLC) combination with our newly developed lipid search engine “Lipid Search”. LTQ Orbitrap provides high mass accuracy MS spectra by Fourier-transform (FT) mass spectrometer mode and can perform rapid MSⁿ by ion trap (IT) mass spectrometer mode. In this study, the negative ion mode was selected to detect fragment ions from phospholipids, such as fatty acid anions, by MS2 or MS3. We selected the specific detection approach by neutral loss survey-dependent MS3, for the identification of molecular species of phosphatidylcholine, sphingomyelin and phosphatidylserine. Identification of molecular species was performed by using both the high mass accuracy of the mass spectrometric data obtained from FT mode and structural data obtained from fragments in IT mode. Some alkylacyl and alkenylacyl species have the same m/z value as molecular-related ions and fragment ions, thus, direct acid hydrolysis analysis was performed to identify alkylacyl and alkenylacyl species, and then the RPLC–LTQ Orbitrap method was applied. As a result, 290 species from mouse liver and 248 species from mouse brain were identified within six different classes of phospholipid, only those in manually detected and confirmed. Most of all manually detected mass peaks were also automatically detected by “Lipid Search”. Adding to differences in molecular species in different classes of phospholipids, many characteristic differences in molecular species were detected in mouse liver and brain. More variable number of saturated and monounsaturated fatty acid-containing molecular species were detected in mouse brain than liver.     

Hybrid genetic algorithm–tabu search approach for optimising multilayer optical coatings

Constructing multilayer optical coatings (MOCs) is a difficult large-scale optimisation problem due to the enormous size of the search space. In the present paper, a new approach for designing MOCs is presented using genetic algorithms (GAs) and tabu search (TS). In this approach, it is not necessary to specify how many layers will be present in a design, only a maximum needs to be defined. As it is generally recognised that the existence of specific repeating blocks is beneficial for a design, a specific GA representation of a design is used which promotes the occurrence of repeating blocks. Solutions found by GAs are improved by a new refinement method, based on TS, a global optimisation method which is loosely based on artificial intelligence. The improvements are demonstrated by creating a visible transmitting/infrared reflecting filter with a wide variety of materials.     

一种有机质谱谱图的库检索新算法

一种有机质谱谱图的库检索新算法律祥俊，林少凡，张金碚，张法义（南开大学中心实验室，天津，３０００７１）关键词检索，算法，质谱，数据库利用计算机匹配技术识别有机质谱谱图中的库检索方法仅需用低分辨质谱图即可识别未知化合物，似为最成功的方法［１～３］．质谱...     

R基团搜索技术用于HIV-1逆转录酶抑制剂的分子设计

本文采用基于R基团搜索技术的Topomer CoMFA方法对41个人类免疫缺陷病毒(HIV-1)逆转录酶抑制剂进行了三维定量构效关系(3D-QSAR)分析。所得优化模型的拟合、交互验证及外部验证的复相关系数分别为0.995、0.859和0.945。采用Topomer Search技术对ZINC数据库进行R基团的虚拟筛选,得到R贡献高的基团,以活性最高的13号分子为模板进行过滤得到1个Ra基团和20个Rb基团。并以此设计得到20个新化合物分子,其中有19个化合物的预测活性值高于13号分子。研究结果表明,所建立的Topomer CoMFA模型具有良好的稳定性和预测能力,基于R基团的Topomer Search技术可以有效筛选并设计出新的HIV-1逆转录酶抑制剂,为抗艾滋病新药设计提供了理论依据。     

An adaptive memory algorithm for the k-coloring problem

Let G=(V,E) be a graph with vertex set V and edge set E. The k-coloring problem is to assign a color (a number chosen in {1,…,k}) to each vertex of G so that no edge has both endpoints with the same color. The adaptive memory algorithm is a hybrid evolutionary heuristic that uses a central memory. At each iteration, the information contained in the central memory is used for producing an offspring solution which is then possibly improved using a local search algorithm. The so obtained solution is finally used to update the central memory. We describe in this paper an adaptive memory algorithm for the k-coloring problem. Computational experiments give evidence that this new algorithm is competitive with, and simpler and more flexible than, the best known graph coloring algorithms.     

A General Vehicle Routing Problem

In this paper, we study a rich vehicle routing problem incorporating various complexities found in real-life applications. The General Vehicle Routing Problem (GVRP) is a combined load acceptance and generalised vehicle routing problem. Among the real-life requirements are time window restrictions, a heterogeneous vehicle fleet with different travel times, travel costs and capacity, multi-dimensional capacity constraints, order/vehicle compatibility constraints, orders with multiple pickup, delivery and service locations, different start and end locations for vehicles, and route restrictions for vehicles. The GVRP is highly constrained and the search space is likely to contain many solutions such that it is impossible to go from one solution to another using a single neighbourhood structure. Therefore, we propose iterative improvement approaches based on the idea of changing the neighbourhood structure during the search.