Hybrid Adaptive Large Neighborhood Search for the Optimal Statistic Median Problem

In this paper, the problem of maximizing the median of a convex combination of vectors having important applications in finance is considered. The objective function is a highly nonlinear, nondifferentiable function with many local minima and the problem was shown to be APX hard. We present two hybrid Large Neighborhood Search algorithms that are based on mixed-integer programs and include a time limit for their running times. We have tested the algorithms on three testbeds and showed their superiority compared to other state-of-the-art heuristics for the considered problem. Furthermore, we achieved a significant reduction in running time for large instances compared to solving it exactly while retaining high quality of the solutions returned.     

基于MATLAB的非线性方程组遗传解法

将非线性方程组的求解问题转化为用遗传算法求解目标函数的最小值问题,利用MATLAB的遗传算法与直接搜索工具箱（GADs）对目标函数求取最小值。计算结果表明,用该方法求得的非线性方程组近似解精度较高。     

基于极大熵和声搜索算法的非线性方程组求解

提出一种基于极大熵和声搜索(HS)的非线性方程组求解算法。利用极大熵函数代替不可微的极大值函数,从而将非线性方程组问题转化为一个无约束极小化问题,并通过HS算法对其进行求解。数值实验结果表明,与牛顿算法相比,该算法简单直观,具有较高的求解准确性。     

HEURISTIC ALGORITHMS FOR SURVIVABLE P2P MULTICASTING

The growing volume of Internet traffic, increasing popularity of streaming services, and limited scalability of existing network techniques trigger the need to develop new delivery solutions based on a multicasting approach. Multicasting—defined as a one-to-many delivery technique—enables effective distribution of many kinds of content to end users. In this article we focus on peer-to-peer (P2P) multicasting, which combines concepts of P2P systems and multicasting solutions; in other words, the multicast tree is constructed using end hosts (peers). Because P2P multicasting can be applied to deliver content with high reliability requirements, we introduce to P2P multicasting additional survivability constraints that guarantee delivery of content in the case of network failures. We formulate a mixed-integer programming (MIP) optimization problem of survivable P2P multicasting. Because the problem is nondeterministic polynomial time (NP)-hard and exact methods such as branch-and-cut can be applied for only a relatively small problem instance, we propose two heuristic algorithms based on evolutionary approach and Tabu Search methods. Extensive computational experiments show that both heuristic algorithms provide results close to optimal—the average gap to optimal results is 0.26% and 5.15% in the case of evolutionary and Tabu Search methods, respectively.     

基于和声搜索算法求解组合优化问题

为了能够应用和声搜索算法（HSA）求解组合优化问题,基于HAS的三种操作的离散化实现提出了一种二进制和声搜索算法(BHSA),并将BHSA用于求解著名的k-可满足性(k-SAT)问题和0-1背包问题,通过与粒子群优化（BPSO）和遗传算法（GA）的实例计算对比验证了新算法的可行性与有效性。     

Solving cold-standby reliability redundancy allocation problems using a new swarm intelligence algorithm

A powerful new hybrid algorithm based on Simplified Swarm Optimization (SSO), Elite Selection and Boundary Search (BS), called the SEB, is proposed for solving the cold-standby reliability redundancy allocation problem (RRAP). The RRAP is a famous mixed-integer nonlinear programming problem in system design that requires that the reliability objective be set to satisfy the resource consumption constraint. In order to balance the exploration and exploitation abilities, the proposed SEB implements a new SSO to update the solutions, an elite selection is performed to select the solutions for subsequent iterations, and the new BS improves the best solution. The performance of the proposed SEB is evaluated by comparing the results with those obtained using existing algorithms and three RRAP benchmark problems taken from the literature.     

New metaheuristic approaches for the edge-weighted k-cardinality tree problem

In this paper we propose three metaheuristic approaches, namely a Tabu Search, an Evolutionary Computation and an Ant Colony Optimization approach, for the edge-weighted k-cardinality tree (KCT) problem. This problem is an NP-hard combinatorial optimization problem that generalizes the well-known minimum weight spanning tree problem. Given an edge-weighted graph G=(V,E), it consists of finding a tree in G with exactly k⩽|V|−1 edges, such that the sum of the weights is minimal. First, we show that our new metaheuristic approaches are competitive by applying them to a set of existing benchmark instances and comparing the results to two different Tabu Search methods from the literature. The results show that these benchmark instances are not challenging enough for our metaheuristics. Therefore, we propose a diverse set of benchmark instances that are characterized by different features such as density and variance in vertex degree. We show that the performance of our metaheuristics depends on the characteristics of the tackled instance, as well as on the cardinality. For example, for low cardinalities the Ant Colony Optimization approach is best, whereas for high cardinalities the Tabu Search approach has advantages.     

Community detection from biological and social networks: A comparative analysis of metaheuristic algorithms

In order to analyze complex networks to find significant communities, several methods have been proposed in the literature. Modularity optimization is an interesting and valuable approach for detection of network communities in complex networks. Due to characteristics of the problem dealt with in this study, the exact solution methods consume much more time. Therefore, we propose six metaheuristic optimization algorithms, which each contain a modularity optimization approach. These algorithms are the original Bat Algorithm (BA), Gravitational Search Algorithm (GSA), modified Big Bang–Big Crunch algorithm (BB-BC), improved Bat Algorithm based on the Differential Evolutionary algorithm (BADE), effective Hyperheuristic Differential Search Algorithm (HDSA) and Scatter Search algorithm based on the Genetic Algorithm (SSGA). Four of these algorithms (HDSA, BADE, SSGA, BB-BC) contain new methods, whereas the remaining two algorithms (BA and GSA) use original methods. To clearly demonstrate the performance of the proposed algorithms when solving the problems, experimental studies were conducted using nine real-world complex networks − five of which are social networks and the rest of which are biological networks. The algorithms were compared in terms of statistical significance. According to the obtained test results, the HDSA proposed in this study is more efficient and competitive than the other algorithms that were tested.     

基于谱分析的密度峰值快速聚类算法

针对密度峰值快速聚类（CFSFDP）算法对不同数据集聚类效果的差异，利用谱聚类对密度峰值快速聚类算法加以改进，提出了一种基于谱分析的密度峰值快速聚类算法CFSFDP-SA。首先，将高维非线性的数据集映射到低维子空间上实现降维处理，将聚类问题转化为图的最优划分问题以增强算法对数据全局结构的适应性；然后，利用CFSFDP算法对处理后的数据集进行聚类。结合这两种聚类算法各自的优势，能进一步提升聚类算法的性能。在5个人工合成数据集（2个线性数据集和3个非线性数据集）与4个UCI数据库中真实数据集上的聚类结果显示，相比CFSFDP算法，CFSFDP-SA算法的聚类精度有一定提升，在高维数据集的聚类精度上最多提高了14%，对原始数据集的适应性更强。     

改进和声搜索算法求解一般整数规划问题

设计了一种改进的和声搜索算法对一般的整数规划问题进行求解,在计算机上予以实现。经实验测试,相对遗传模拟退火算法和混合遗传算法,获得了同样甚至更好的解。由于改进和声搜索算法使用灵活,因此对于线性和非线性的整数规划问题都能进行求解。     

Pharmacy duty scheduling problem

In this study, we define the pharmacy duty scheduling problem, which requires a subset of pharmacies to be on duty on national holidays, at weekends, and at nights, in order to be able to satisfy the emergency medicine needs. We model the pharmacy duty scheduling problem as a multiperiod p‐median problem with special side constraints, and analyze the computational complexity. We propose a Tabu Search heuristic and develop lower bound (LB) algorithms. We test the performance of mathematical models, Tabu Search heuristic, and the LBs on randomly generated instances. We analyze the current system in ?zmir, the third largest city in Turkey, with a population of 3.5 million, and apply solution methods. Our results show that the proposed Tabu Search algorithm suggests improvements on the current system.     

Where genetic algorithms excel

We analyze the performance of a genetic algorithm (GA) we call Culling, and a variety of other algorithms, on a problem we refer to as the Additive Search Problem (ASP). We show that the problem of learning the Ising perceptron is reducible to a noisy version of ASP. Noisy ASP is the first problem we are aware of where a genetic-type algorithm bests all known competitors. We generalize ASP to k-ASP to study whether GAs will achieve "implicit parallelism" in a problem with many more schemata. GAs fail to achieve this implicit parallelism, but we describe an algorithm we call Explicitly Parallel Search that succeeds. We also compute the optimal culling point for selective breeding, which turns out to be independent of the fitness function or the population distribution. We also analyze a mean field theoretic algorithm performing similarly to Culling on many problems. These results provide insight into when and how GAs can beat competing methods.     

The strong network orientation problem

This study presents models and heuristics for solving the strong network orientation problem (SNOP), which can model several tactical optimization problems of setting directions in urban networks. The objective is to set an orientation for each edge in an undirected graph such that the resulting digraph is strongly connected and the total travel distance between any pair of nodes is minimized (or maximized). Investigating tactical optimization problems such as SNOP is motivated by several challenges in urban networks due to the growth of population in urban areas, large number of daily trips, increasing price of maintaining urban networks, and the need to reduce air pollution and passive noise. Thus, a new trend is to utilize the urban networks better. In this context, we first use a multicommodity flow formulation to model the minimization problem. The maximization version is modeled by using the dual formulation of the shortest path problem. Then, scalable heuristic strategies for solving SNOP are investigated. For such purpose, we first propose basic components such as constructive heuristics, perturbations and local searches. They are combined into several metaheuristics based on local searches, multi-start and evolutionary schemes, i.e. Multistart Local Search, Iterated Local Search (ILS), Relaxed ILS, Evolutionary Local Search (ELS), Relaxed ELS, and Variable Neighborhood Search. Computational experiments have been performed to analyze the proposed methods in terms of efficiency and quality of solutions, using grid instances and a graph from downtown Clermont-Ferrand in France.     

A Tabu search algorithm for the network pricing problem

In this paper, we propose an efficient Tabu Search procedure for solving the NP-hard network pricing problem. By exploiting the problem's features, the algorithm allows the near-optimal solution of problem instances that are out of reach of exact combinatorial methods.     

An optimization approach to nonlinear diagnostic filter synthesis

We consider the synthesis problem for diagnostic filters based on nonlinear models of the systems being diagnosed. To solve the problem, we propose a new approach that unites the methods of algebra of functions and differential geometry when performing a nonlinear transformation of the original mathematical model for the diagnosed system with linear optimization techniques. An advantage of the proposed approach is that it overcomes principled obstacles of existing diagnostic filter synthesis methods and gets a solution for systems with parametric uncertainties.     

Identification of nonlinear additive FIR systems

In this paper, we consider identification of a nonlinear additive system. An input signal is designed in such a way that the problem of identification of nonlinear additive systems is reduced to a problem of identification of static nonlinear functions. Then, three approaches are established to estimate the order of the system. The methods exploit the structure of the nonlinear additive model so that their implementations are easy.     

A comparative evaluation of nonlinear dynamics methods for time series prediction

A key problem in time series prediction using autoregressive models is to fix the model order, namely the number of past samples required to model the time series adequately. The estimation of the model order using cross-validation may be a long process. In this paper, we investigate alternative methods to cross-validation, based on nonlinear dynamics methods, namely Grassberger–Procaccia, Kégl, Levina–Bickel and False Nearest Neighbors algorithms. The experiments have been performed in two different ways. In the first case, the model order has been used to carry out the prediction, performed by a SVM for regression on three real data time series showing that nonlinear dynamics methods have performances very close to the cross-validation ones. In the second case, we have tested the accuracy of nonlinear dynamics methods in predicting the known model order of synthetic time series. In this case, most of the methods have yielded a correct estimate and when the estimate was not correct, the value was very close to the real one.     

分布式弹性搜索研究与实践

针对大数据量数据资源的简洁、快速搜索问题,深入研究了基于Lucene的分布式弹性搜索引擎ElasticSearch,简单分析了它的基本原理,详细描述了它的技术框架,并基于ElasticSearch搜索引擎,开发实现了公安信息资源整合与搜索系统,实现了大数据量信息资源的快速整合与一键式分布式准实时搜索,通过可视化监控界面,实时了解系统数据同步与搜索性能,为不断优化其性能奠定了坚实基础.     

COMPARATIVE ANALYSIS OF A HYBRID DE ALGORITHM WITH THE VNS ALGORITHM AND ITS VARIATION SVNS TO SOLVE A REAL-WORLD FREQUENCY ASSIGNMENT PROBLEM

The Frequency Assignment is a very important task in the planning of the GSM networks, and it still continues to be a critical task for current (and future) mobile communication operators. In this work, we compare a hybrid Differential Evolution algorithm with the Variable Neighbourhood Search algorithm and also its variant Skewed Variable Neighbourhood Search to solve a real-world Frequency Assignment problem (FAP) in GSM Networks. The results that are shown use accurate interference information. That information was also adopted by other researchers and it represents a real GSM network, granting, therefore, an really important applicability. Furthermore, we have analyzed and compared our approach with other algorithms proposed so far to this problem. Hence, our approach using the SVNS algorithm has proven to be efficient in solving this problem, and permitted us to obtain good results. In fact, with this work we have contributed to the FAP problem with an additional comparison between approaches using metaheuristics based on trajectory (VNS and SVNS) and others based on population (DE).     

Topic evolution based on the probabilistic topic model: a review

Accurately representing the quantity and characteristics of users’ interest in certain topics is an important problem facing topic evolution researchers, particularly as it applies to modern online environments. Search engines can provide information retrieval for a specified topic from archived data, but fail to reflect changes in interest toward the topic over time in a structured way. This paper reviews notable research on topic evolution based on the probabilistic topic model from multiple aspects over the past decade. First, we introduce notations, terminology, and the basic topic model explored in the survey, then we summarize three categories of topic evolution based on the probabilistic topic model: the discrete time topic evolution model, the continuous time topic evolutionmodel, and the online topic evolution model. Next, we describe applications of the topic evolution model and attempt to summarize model generalization performance evaluation and topic evolution evaluation methods, as well as providing comparative experimental results for different models. To conclude the review, we pose some open questions and discuss possible future research directions.