MaxMinMin p-dispersion problem: A variable neighborhood search approach

In this work we have developed a Variable Neighborhood Search (VNS) method in order to solve the MaxMinMin p-dispersion problem, which adds a new type of plateau search mechanism to the classical VNS metaheuristic framework. Besides, several other contributions have been made to the basic VNS heuristic in terms of the ascent and perturbation functions. To the best of our knowledge this is the first application of the VNS to the MaxMinMin problem and our approach, compared to previous methods, finds or improves the results for all of the large-sized benchmarks with low computational efforts. Finding most of the proven optimal solutions in a fraction of a second, the robustness and quality of the solutions and the low complexity of the methods demonstrate the strength of the proposed heuristic solution procedures.     

Effective local search algorithms for high school timetabling problems

This paper addresses the high school timetabling problem. The problem consists in building weekly timetables for meetings between classes and teachers with the goal of minimizing violations of specific requirements. In the last decades, several mixed-integer programs have been proposed and tested for this family of problems. However, medium and large size instances are still not effectively solved by these programs using state-of-the-art solvers and the scientific community has given special attention to the devising of alternative soft computing algorithms. In this paper, we propose a soft computing approach based on Iterated Local Search and Variable Neighborhood Search metaheuristic frameworks. Our algorithms incorporate new neighborhood structures and local search routines to perform an effective search. We validated the proposed algorithms on variants of the problem using seven public instances and a new dataset with 34 real-world instances including large cases. The results demonstrate that the proposed algorithms outperform the state-of-the-art approaches in both cases, finding the best solutions in 38 out of the 41 tested instances.     

Reactive Search strategies using Reinforcement Learning,local search algorithms and Variable Neighborhood Search

Optimization techniques known as metaheuristics have been applied successfully to solve different problems, in which their development is characterized by the appropriate selection of parameters (values) for its execution. Where the adjustment of a parameter is required, this parameter will be tested until viable results are obtained. Normally, such adjustments are made by the developer deploying the metaheuristic. The quality of the results of a test instance [The term instance is used to refer to the assignment of values to the input variables of a problem.] will not be transferred to the instances that were not tested yet and its feedback may require a slow process of “trial and error” where the algorithm has to be adjusted for a specific application. Within this context of metaheuristics the Reactive Search emerged defending the integration of machine learning within heuristic searches for solving complex optimization problems. Based in the integration that the Reactive Search proposes between machine learning and metaheuristics, emerged the idea of putting Reinforcement Learning, more specifically the Q-learning algorithm with a reactive behavior, to select which local search is the most appropriate in a given time of a search, to succeed another local search that can not improve the current solution in the VNS metaheuristic. In this work we propose a reactive implementation using Reinforcement Learning for the self-tuning of the implemented algorithm, applied to the Symmetric Travelling Salesman Problem.     

Multi-neighborhood local search optimization for machine reassignment problem

As the topic of the Google ROADEF/EURO Challenge 2012, machine reassignment problem (denoted as MRP) is an important optimization problem in load balance of cloud computing. Given a set of machines and a set of processes running on machines, the MRP aims at finding a best process-machine reassignment to improve the usage of machines while satisfying various hard constraints. In this paper, we present a metaheuristic algorithm based on multi-neighborhood local search (denoted as MNLS) for solving the MRP. Our MNLS algorithm consists of three primary and one auxiliary neighborhood structures, an efficient neighborhood partition search mechanism with respect to the three primary neighborhoods and a dynamic perturbation operator. Computational results tested on 30 benchmark instances of the ROADEF/EURO Challenge 2012 and comparisons with the results in the challenge and the literature demonstrate the efficacy of the proposed MNLS algorithm in terms of both effectiveness and efficiency. Furthermore, several key components of our MNLS algorithm are analyzed to gain an insight into it.     

An effective local search for the maximum clique problem

We propose a variable depth search based algorithm, called k-opt local search (KLS), for the maximum clique problem. KLS efficiently explores the k-opt neighborhood defined as the set of neighbors that can be obtained by a sequence of several add and drop moves that are adaptively changed in the feasible search space. Computational results on DIMACS benchmark graphs indicate that KLS is capable of finding considerably satisfactory cliques with reasonable running times in comparison with those of state-of-the-art metaheuristics.     

On the two-dimensional cow search problem

We investigate the problem introduced by Baeza-Yates et al. [R.A. Baeza-Yates, J.C. Culberson, G.J.E. Rawlins, Searching with uncertainty, Research report, University of Waterloo, 1987]: given a plane and a horizontal or a vertical line in unknown location give a strategy to find this line. We use a competitive analysis to measure the performance of this strategy. This problem is one of the first generalisations of the cow search problem.     

Multi-objective genetic local search algorithm using Kohonen’s neural map

Genetic Algorithms (GAs) are population based global search methods that can escape from local optima traps and find the global optima regions. However, near the optimum set their intensification process is often inaccurate. This is because the search strategy of GAs is completely probabilistic. With a random search near the optimum sets, there is a small probability to improve current solution. Another drawback of the GAs is genetic drift. The GAs search process is a black box process and no one knows that which region is being searched by the algorithm and it is possible that GAs search only a small region in the feasible space. On the other hand, GAs usually do not use the existing information about the optimality regions in past iterations.In this paper, a new method called SOM-Based Multi-Objective GA (SBMOGA) is proposed to improve the genetic diversity. In SBMOGA, a grid of neurons use the concept of learning rule of Self-Organizing Map (SOM) supporting by Variable Neighborhood Search (VNS) learn from genetic algorithm improving both local and global search. SOM is a neural network which is capable of learning and can improve the efficiency of data processing algorithms. The VNS algorithm is developed to enhance the local search efficiency in the Evolutionary Algorithms (EAs). The SOM uses a multi-objective learning rule based-on Pareto dominance to train its neurons. The neurons gradually move toward better fitness areas in some trajectories in feasible space. The knowledge of optimum front in past generations is saved in form of trajectories. The final state of the neurons determines a set of new solutions that can be regarded as the probability density distribution function of the high fitness areas in the multi-objective space. The new set of solutions potentially can improve the GAs overall efficiency. In the last section of this paper, the applicability of the proposed algorithm is examined in developing optimal policies for a real world multi-objective multi-reservoir system which is a non-linear, non-convex, multi-objective optimization problem.     

无线传感器网络中局部最优的目标搜索研究

深入分析无线传感器网络中的目标搜索问题,比较了现有的几种搜索策略,重点关注最优搜索理论在无线传感器网络目标搜索中的应用。针对大规模传感器网络,提出了局部最优搜索改进模型,新模型在基本探测函数基础上,针对大规模传感器网络实际,对参数进行了重要补充与完善,使得改进后最优搜索模型在与改进前的最后搜索比较中显示出较明显的优势。     

Backtrack search algorithms and the maximal common subgraph problem

Backtrack algorithms are applicable to a wide variety of problems. An efficient but readable version of such an algorithm is presented and its use in the problem of finding the maximal common subgraph of two graphs is described. Techniques available in this application area for ordering and pruning the backtrack search are discussed. This algorithm has been used successfully as a component of a program for analysing chemical reactions and enumerating the bond changes which have taken place.     

DE-VNS: Self-adaptive Differential Evolution with crossover neighborhood search for continuous global optimization

In this paper, we suggest DE-VNS heuristic for solving continuous (unconstrained) nonlinear optimization problems. It combines two well-known metaheuristic approaches: Differential Evolution (DE) and Variable Neighborhood Search (VNS), which have, in the last decade, attracted considerable attention in both academic circles and among practitioners. The basic idea of our hybrid heuristic is the use of the neighborhood change mechanism in order to estimate the crossover parameter of DE. Moreover, we introduce a new family of adaptive distributions to control the distances among solutions in the search space as well as experimental evidence of finding the best probability distribution function for VNS parameter supported by its statistical estimation. This hybrid heuristic has shown excellent characteristics and it turns out that it is more favorable than the state-of-the-art DE approaches when tested on standard instances from the literature.     

改进的离散粒子群优化算法及其在竞胜标确定问题中的应用

通过拓展标准粒子群优化算法模型,提出了一种用于解决离散最优化问题的NDPSO算法,使其仍然具备标准PSO算法相对于其他智能算法的高效性和稳定性。在NDPSO算法的基础上引入依概率随机比较的概念,并构造了进行启发式搜索的随机修补算子,实现对组合拍卖中的竞胜标确定问题（WDP）的求解。实验结果表明,该求解方案与基于其他离散化PSO算法或遗传算法的求解方案相比在达优率和收敛速度上都具有明显的优势。     

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.     

Dynamic local search based immune automatic clustering algorithm and its applications

Based on clonal selection mechanism in immune system, a dynamic local search based immune automatic clustering algorithm (DLSIAC) is proposed to automatically evolve the number of clusters as well as a proper partition of datasets. The real based antibody encoding consists of the activation thresholds and the clustering centers. Then based on the special structures of chromosomes, a particular dynamic local search scheme is proposed to exploit the neighborhood of each antibody as much as possible so to realize automatic variation of the antibody length during evolution. The dynamic local search scheme includes four basic operations, namely, the external cluster swapping, the internal cluster swapping, the cluster addition and the cluster decrease. Moreover, a neighborhood structure based clonal mutation is adopted to further improve the performance of the algorithm. The proposed algorithm has been extensively compared with five state-of-the-art automatic clustering techniques over a suit of datasets. Experimental results indicate that the DLSIAC is superior to other five clustering algorithms on the optimum number of clusters found and the clustering accuracy. In addition, DLSIAC is applied to a real problem, namely image segmentation, with a good performance.     

求解k中间点问题的新局部搜索算法

为有效求解大规模k中间点问题,利用适应度距离相关性方法分析,发现该问题局部最优解的适应度与其到全局最优解的距离无太大关系,且多个局部最优解求交所得子集以极大概率包含全局最优解中的元素,进而提出一种基于求交操作的k中间点问题局部搜索算法。实验结果表明该算法在求解质量上与目前已知算法相比有较大改进。     

分散搜索算法求解多目标优化问题

最近涌现了各种进化方法来解决多目标优化问题,分散搜索也是一种可以解决多目标问题的算法。该算法的结构引用进化算法的杂交和变异算子来增强它的性能,但该算法与其他进化算法的不同在于一系列操作策略不再基于随机性原理,而是运用“分散-收敛集聚”的迭代机制。论文在多目标优化问题区域讨论分散搜索算法,寻找多目标的非支配集或Pareto最优解。实验表明,分散搜索算法具有很好的收敛性和分布性。     

Heuristic methods for the optimal statistic median problem

We consider the problem of finding the convex combination of vectors for which the median is maximum. The objective function of this problem is non-concave and non-differentiable, with many local optima that can trap any subgradient algorithm. So we analyzed and tested some heuristic procedures to find optimal or near-optimal solutions. First, we introduced a variant of Random Restart, in which starting solutions are the vertices of the simplex, and we proved that small size problems are solved by this procedure. Then, we analyzed two versions of Variable Neighborhood Search that are used to explore the whole space of the feasible solutions, and we show that the continuous version is more powerful than the discrete version.     

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

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

Evolutionary local search for the edge-biconnectivity augmentation problem

This paper considers the problem of augmenting a given graph by a cheapest possible set of additional edges in order to make the graph edge-biconnected. An application is the extension of an existing communication network to become robust against single link-failures. An evolutionary algorithm (EA) is presented which includes an effective preprocessing of the problem data and a local improvement procedure that is applied during initialization, recombination, and mutation. In this way, the EA searches the space of feasible, locally optimal solutions only. The variation operators were designed with particular emphasis on low computational effort and strong locality. Empirical results indicate the superiority of the new approach over two previous heuristic methods.