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.     

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.     

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.     

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.     

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.     

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.     

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.     

What users see - Structures in search engine results pages

This paper investigates the composition of search engine results pages. We define what elements the most popular web search engines use on their results pages (e.g., organic results, advertisements, shortcuts) and to which degree they are used for popular vs. rare queries. Therefore, we send 500 queries of both types to the major search engines Google, Yahoo, Live.com and Ask. We count how often the different elements are used by the individual engines. In total, our study is based on 42,758 elements. Findings include that search engines use quite different approaches to results pages composition and therefore, the user gets to see quite different results sets depending on the search engine and search query used. Organic results still play the major role in the results pages, but different shortcuts are of some importance, too. Regarding the frequency of certain host within the results sets, we find that all search engines show Wikipedia results quite often, while other hosts shown depend on the search engine used. Both Google and Yahoo prefer results from their own offerings (such as YouTube or Yahoo Answers). Since we used the .com interfaces of the search engines, results may not be valid for other country-specific interfaces.     

A new iterated fast local search heuristic for solving QAP formulation in facility layout design

In facility layout design, the problem of locating facilities with material flow between them was formulated as a quadratic assignment problem (QAP), so that the total cost to move the required material between the facilities is minimized, where the cost is defined by a quadratic function. In this paper, we propose a modification to iterated fast local search algorithm (IFLS) with a new recombination crossover operator and the modified IFLS is addressed as NIFLS. The ideas we incorporate in the NIFLS are iterated self-improvement with evolutionary based perturbation tool, which includes (i) recombination crossover as perturbation tool and (ii) self-improvement in mutation operation followed by a local search. Three schemes of NIFLS are proposed and the obtained solution qualities by the three schemes are compared. We test our algorithm on all the benchmark instances of QAPLIB, a well-known library of QAP instances. The performance of proposed recombination crossover with sliding mutation (RCSM) scheme of NIFLS is well superior to the other two schemes of NIFLS.     

Breakout local search for the multi-objective gate allocation problem

The problem of assigning gates to arriving and departing flights is one of the most important problems in airport operations. We take into account the real multi-criteria nature of the problem by optimizing a total of nine gate allocation objectives that are oriented both on convenience for airport/airline services and passenger comfort. As far as we are aware, this is the largest number of objectives jointly optimized in the GAP literature. Given the complexity of the considered problem, we propose a heuristic approach based on the Breakout Local Search (BLS) framework. BLS is a recent variant of the Iterated Local Search (ILS) with a particular focus on the perturbation strategy. Based on some relevant information on search history, it tries to introduce an appropriate degree of diversification by determining adaptively the number and type of moves for the next perturbation phase. Moreover, we use a new memory-based greedy constructive heuristic to generate a starting point for BLS. Benchmark instances used for our experiments and comparisons are based on information provided by Manchester Airport.     

A local search method for periodic inventory routing problem

Inventory routing problem considers inventory allocation and routing problems simultaneously, in which the replenishment policies and routing arrangement are determined by the supplier under the vendor managed inventory mode. What we consider here is a periodic inventory routing problem that once the delivery time, quantity and routing are determined, they will remain the same in the following periods. The problem is modeled concisely, and then it is decomposed into two subproblems, inventory problem and vehicle routing problem. The inventory problem is solved by proposing a local search method, which is achieved by four operators on delivery quantity and retailer’s demand. Insertion operator aims to insert a new replenishment point of a retailer while removal operator is to remove a replenishment point. Besides, addition operator is adopted as an assistant tool, and crossover operator is proposed for some special cases. We also propose a tabu search method to solve the routing problem. Finally, the computational results show that the method is efficient and stable.     

The effect of neighborhood structures on tabu search algorithm in solving course timetabling problem

The course timetabling problem must be solved by the departments of Universities at the beginning of every semester. It is a though problem which requires department to use humans and computers in order to find a proper course timetable. One of the most mentioned difficult nature of the problem is context dependent which changes even from departments to departments. Different heuristic approaches have been proposed in order to solve this kind of problem in the literature. One of the efficient solution methods for this problem is tabu search. Different neighborhood structures based on different types of move have been defined in studies using tabu search. In this paper, the effects of moves called simple and swap on the operation of tabu search are examined based on defined neighborhood structures. Also, two new neighborhood structures are proposed by using the moves called simple and swap. The fall semester of course timetabling problem of the Department of Statistics at Hacettepe University is solved utilizing four neighborhood structures and the comparison of the results obtained from these structures is given.     

Global search algorithms using a combinatorial unranking-based problem representation for the critical node detection problem

In this paper the problem of critical node detection (CNDP) is approached using population-based incremental learning (an estimation of distribution algorithm) and simulated annealing optimization algorithms using a combinatorial unranking-based problem representation. This representation is space-efficient and alleviates the need for any repair mechanisms. CNDP is a very recently proposed problem that aims to identify a vertex set V′⊆V$V\prime \subseteq V$ of k>0$k>0$ nodes from a given graph G=(V,E)$G=(V,E)$ such that G(V?V′)$G(V?V\prime )$ has minimum pairwise connectivity. Numerous practical applications for this problem exist, including pandemic disease mitigation, computer security and anti-terrorism. In order to test the proposed heuristics 16 benchmark random graph structures are additionally proposed that utilize Erdos–Renyi, Watts–Strogatz, Forest Fire and Barabasi–Albert models. Each of these models presents different network characteristics, yielding variations in problem difficulty. The relative merits of the two proposed approaches are compared and it is found that the population-based incremental learning approach, using a windowed perturbation operator is able to outperform the proposed simulated annealing method.     

A hybrid harmony search algorithm for the blocking permutation flow shop scheduling problem

This paper proposes a hybrid modified global-best harmony search (hmgHS) algorithm for solving the blocking permutation flow shop scheduling problem with the makespan criterion. First of all, the largest position value (LPV) rule is proposed to convert continuous harmony vectors into job permutations. Second, an efficient initialization scheme based on the Nawaz-Enscore-Ham (NEH) heuristic is presented to construct the initial harmony memory with a certain level of quality and diversity. Third, harmony search is employed to evolve harmony vectors in the harmony memory to perform exploration, whereas a local search algorithm based on the insert neighborhood is embedded to enhance the local exploitation ability. Moreover, a new pitch adjustment rule is developed to well inherit good structures from the global-best harmony vector. Computational simulations and comparisons demonstrated the superiority of the proposed hybrid harmony search algorithm in terms of solution quality.     

An integer programming-based local search for the covering salesman problem

We consider a generalized version of the well known Traveling Salesman Problem called Covering Salesman problem. In this problem, we are given a set of vertices while each vertex i can cover a subset of vertices within its predetermined covering distance r_i. The goal is to construct a minimum length Hamiltonian cycle over a subset of vertices in which those vertices not visited on the tour has to be within the covering distance of at least one vertex visited on the tour. The paper proposes an Integer Linear Programming based heuristic method which takes advantage of Integer Linear Programming techniques and heuristic search to improve the quality of the solutions. Extensive computational tests on the standard benchmark instances and on a new set of large sized datasets show the effectiveness of the proposed approach.     

Applying MOEAs to solve the static Routing and Wavelength Assignment problem in optical WDM networks

Wavelength-Division Multiplexing (WDM) in optical networks has revolutionized the Telecommunication field. This technology is able to exploit the enormous bandwidth capability of this kind of networks, allowing communication between end users via all-optical WDM channels (lightpath). Given a set of demands, the problem of setting up lightpaths by routing and assigning a wavelength to each connection is known as Routing and Wavelength Assignment (RWA) problem. There are two types of connection demands: static (demands are given in advance) and dynamic (demands are given in real-time). In this paper we present two different Multiobjective Evolutionary Algorithms (MOEA) with the aim of solving the static RWA problem. The first one is a population-based algorithm, the Differential Evolution (DE), but incorporating the Pareto Tournament concept (DEPT). The second one is a multiobjective version of the Variable Neighborhood Search (VNS), MO-VNS. In order to prove the goodness of our metaheuristics, we have compared them with the standard Fast Non-Dominated Sorting Genetic Algorithm (NSGA-II), typical heuristics in the Telecommunication field, and different varieties of Multiobjective Ant Colony Optimization Algorithms. On the whole, we conclude that our approaches have obtained very promising results.