Combinatorial optimization of distributed queries

In relational distributed databases a query cost consists of a local cost and a transmission cost. Query optimization is a combinatorial optimization problem. As the query size grows, the optimization methods based on exhaustive search become too expensive. We propose the following strategy for solving large distributed query optimization problems in relational database systems: (1) represent each query-processing schedule by a labeled directed graph; (2) reduce the number of different schedules by pruning away invalid or high-cost solutions; and (3) find a suboptimal schedule by combinatorial optimization. We investigate several combinatorial optimization techniques: random search, single start, multistart, simulated annealing, and a combination of random search and local simulated annealing. The utility of combinatorial optimization is demonstrated in the problem of finding the (sub)optimal semijoin schedule that fully reduces all relations of a tree query. The combination of random search and local simulated annealing was superior to other tested methods     

A great deluge and tabu search hybrid with two-stage memory support for quadratic assignment problem

A two-stage memory architecture is maintained within the framework of great deluge algorithm for the solution of single-objective quadratic assignment problem. Search operators exploiting the accumulated experience in memory are also implemented to direct the search towards more promising regions of the solution space. The level-based acceptance criterion of the great deluge algorithm is applied for each best solution extracted in a particular iteration. The use of short- and long-term memory-based search supported by effective move operators resulted in a powerful combinatorial optimization algorithm. A successful variant of tabu search is employed as the local search method that is only applied over a few randomly selected memory elements when the second stage memory is updated. The success of the presented approach is illustrated using sets of well-known benchmark problems and evaluated in comparison to well-known combinatorial optimization algorithms. Experimental evaluations clearly demonstrate that the presented approach is a competitive and powerful alternative for solving quadratic assignment problems.     

An interactive simulation and analysis software for solving TSP using Ant Colony Optimization algorithms

Traveling salesman problem (TSP) is one of the extensively studied combinatorial optimization problems and tries to find the shortest route for salesperson which visits each given city precisely once. Ant colony optimization (ACO) algorithms have been used to solve many optimization problems in various fields of engineering. In this paper, a web-based simulation and analysis software (TSPAntSim) is developed for solving TSP using ACO algorithms with local search heuristics. Algorithms are tested on benchmark problems from TSPLIB and test results are presented. Importance of TSPAntSim providing also interactive visualization with real-time analysis support for researchers studying on optimization and people who have problems in form of TSP is discussed.     

A local search based approach for solving the Travelling Thief Problem: The pros and cons

The Travelling Thief Problem (TTP) is a novel problem that aims to provide a benchmark model of combinatorial optimization problems with multiple interdependent components. The TTP combines two other well known benchmark problems: the Travelling Salesman Problem (TSP) and the Knapsack Problem (KP). The aim of this paper is to study the interdependence between the TTP's components, and how it makes solving each sub-problem independently from the other useless for solving the overall problem. A local search approach is proposed to solve the TTP. Two simple iterative neighborhood algorithms based on our approach are presented, analyzed, and compared to other algorithms. Initialization strategies are empirically investigated. The experimental results confirm that our approach was able to find new better solutions for many TTP instances.     

Combinatorial optimization with use of guided evolutionarysimulated annealing

Feasible approaches to the task of solving NP-complete problems usually entails the incorporation of heuristic procedures so as to increase the efficiency of the methods used. We propose a new technique, which incorporates the idea of simulated annealing into the practice of simulated evolution, in place of arbitrary heuristics. The proposed technique is called guided evolutionary simulated annealing (GESA). We report on the use of GESA approach primarily for combinatorial optimization. In addition, we report the case of function optimization, treating the task as a search problem. The traveling salesman problem is taken as a benchmark problem in the first case. Simulation results are reported. The results show that the GESA approach can discover a very good near optimum solution after examining an extremely small fraction of possible solutions. A very complicated function with many local minima is used in the second case. The results in both cases indicate that the GESA technique is a practicable method which yields consistent and good near optimal solutions, superior to simulated evolution.     

An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem

Flexible job-shop scheduling problem (FJSP) is an extension of the classical job-shop scheduling problem. Although the traditional optimization algorithms could obtain preferable results in solving the mono-objective FJSP. However, they are very difficult to solve multi-objective FJSP very well. In this paper, a particle swarm optimization (PSO) algorithm and a tabu search (TS) algorithm are combined to solve the multi-objective FJSP with several conflicting and incommensurable objectives. PSO which integrates local search and global search scheme possesses high search efficiency. And, TS is a meta-heuristic which is designed for finding a near optimal solution of combinatorial optimization problems. Through reasonably hybridizing the two optimization algorithms, an effective hybrid approach for the multi-objective FJSP has been proposed. The computational results have proved that the proposed hybrid algorithm is an efficient and effective approach to solve the multi-objective FJSP, especially for the problems on a large scale.     

优化建模软件LocalSolver简介

优化建模工具LocalSolver是近年出现的一个基于局部搜索的商业软件，依赖其特有的局部搜索技术，对于组合优化问题表现出强大的求解能力。介绍该软件的主要特点、基本的工作流程和同C语言语法的不同之处，并用经典的背包问题和指派问题两个实例来说明LocalSolver的用法和求解能力。     

集装箱装入问题的研究

集装箱装载问题是一种有广泛应用背景的组合优化问题,它属于NP-hard问题。禁忌搜索算法(TS)是求解组合问题的一种主要方法,有很强的全局搜索能力。集装箱装入属于有多种约束的空间资源优化问题。约束条件多,求解困难。根据同类型货物一次性装载的思想,提出了一种新的基于空间划分的启发式算法。     

Effective Memetic Algorithms for VLSI design = Genetic Algorithms + local search + multi-level clustering

Combining global and local search is a strategy used by many successful hybrid optimization approaches. Memetic Algorithms (MAs) are Evolutionary Algorithms (EAs) that apply some sort of local search to further improve the fitness of individuals in the population. Memetic Algorithms have been shown to be very effective in solving many hard combinatorial optimization problems. This paper provides a forum for identifying and exploring the key issues that affect the design and application of Memetic Algorithms. The approach combines a hierarchical design technique, Genetic Algorithms, constructive techniques and advanced local search to solve VLSI circuit layout in the form of circuit partitioning and placement. Results obtained indicate that Memetic Algorithms based on local search, clustering and good initial solutions improve solution quality on average by 35% for the VLSI circuit partitioning problem and 54% for the VLSI standard cell placement problem.     

A filter-and-fan algorithm for the capacitated minimum spanning tree problem

The capacitated minimum spanning tree (CMST) is a notoriously difficult problem in combinatorial optimization. Extensive investigation has been devoted to developing efficient algorithms to find optimal or near-optimal solutions. This paper proposes a new CMST heuristic algorithm that effectively combines the classical node-based and tree-based neighborhoods embodied in a filter-and-fan (F&F) approach, a local search procedure that generates compound moves in a tree search fashion. The overall algorithm is guided by a multi-level oscillation strategy used to trigger each type of neighborhood while allowing the search to cross feasibility boundaries. Computational results carried out on a standard set of 135 benchmark problems show that a simple F&F design competes effectively with prior CMST metaheuristics, rivaling the best methods, which are significantly more complex.     

Combinations of Estimation of Distribution Algorithms and Other Techniques

This paper summaries our recent work on combining estimation of distribution algorithms (EDA) and other techniques for solving hard search and optimization problems:a) guided mutation,an offspring generator in which the ideas from EDAs and genetic algorithms are combined together,we have shown that an evolutionary algorithm with guided mutation outperforms the best GA for the maximum clique problem,b)evolutionary algorithms refining a heuristic,we advocate a strategy for solving a hard optimization problem with complicated data structure,and c) combination of two different local search techniques and EDA for numerical global optimization problems,its basic idea is that not all the new generated points are needed to be improved by an expensive local search.     

求解TSP的改进模拟退火算法

利用模拟退火算法给出了求解旅行商问题的一种新方法.在模拟退火算法的基本原理基础上,针对解变换只交换两个城市而容易落入局部最优解的缺点,提出了在解变换产生新解的过程中,采用逆转操作的改进方法.这使得迭代过程突破局部最优圈,然后跳到另一个搜索空间.这样能够使其更具多样性,改善了模拟退火算法的局部搜索能力.并将其应用于求解旅行商问题,显著改善了它局部寻优的能力.在几个公共测试数据集上的结果表明,算法稳定可行,在求解组合优化问题方面,具有良好的性能.     

Four-layer framework for combinatorial optimization problems domain

Four-layer framework for combinatorial optimization problems/models domain is suggested for applied problems structuring and solving: (1) basic combinatorial models and multicriteria decision making problems (e.g., clustering, knapsack problem, multiple choice problem, multicriteria ranking, assignment/allocation); (2) composite models/procedures (e.g., multicriteria combinatorial problems, morphological clique problem); (3) basic (standard) solving frameworks, e.g.: (i) Hierarchical Morphological Multicriteria Design (HMMD) (ranking, combinatorial synthesis based on morphological clique problem), (ii) multi-stage design (two-level HMMD), (iii) special multi-stage composite framework (clustering, assignment/location, multiple choice problem); and (4) domain-oriented solving frameworks, e.g.: (a) design of modular software, (b) design of test inputs for multi-function system testing, (c) combinatorial planning of medical treatment, (d) design and improvement of communication network topology, (e) multi-stage framework for information retrieval, (f) combinatorial evolution and forecasting of software, devices. The multi-layer approach covers ‘decision cycle’, i.e., problem statement, models, algorithms/procedures, solving schemes, decisions, decision analysis and improvement.     

基于混合蚁群优化的卫星地面站系统任务调度方法

卫星地面站系统任务调度是一个典型的组合优化问题, 优化过程极其复杂. 鉴于此, 提出了一种有效求解该问题的基于蚁群优化算法和导向局部搜索方法的混合优化方法. 该方法将蚁群优化和导向局部搜索有效地结合在一起, 极大地提高了优化绩效. 实例计算结果表明, 该混合方法能有效地求解卫星地面站系统任务调度问题.     

基于二次分配问题的混合蚁群算法

二次分配问题是组合优化领域中经典的NP-hard问题之一,应用广泛。在对二次分配问题进行分析的基础上,提出了一种求解该问题的混合蚁群算法。该算法通过在蚁群算法中引入遗传算法的2-交换变异算子,增强了算法的局部搜索能力,提高了解的质量。实验结果表明,该算法在求解二次分配问题时优于蚁群算法和遗传算法。     

A hybrid genetic algorithm and tabu search approach for post enrolment course timetabling

The post enrolment course timetabling problem (PECTP) is one type of university course timetabling problems, in which a set of events has to be scheduled in time slots and located in suitable rooms according to the student enrolment data. The PECTP is an NP-hard combinatorial optimisation problem and hence is very difficult to solve to optimality. This paper proposes a hybrid approach to solve the PECTP in two phases. In the first phase, a guided search genetic algorithm is applied to solve the PECTP. This guided search genetic algorithm, integrates a guided search strategy and some local search techniques, where the guided search strategy uses a data structure that stores useful information extracted from previous good individuals to guide the generation of offspring into the population and the local search techniques are used to improve the quality of individuals. In the second phase, a tabu search heuristic is further used on the best solution obtained by the first phase to improve the optimality of the solution if possible. The proposed hybrid approach is tested on a set of benchmark PECTPs taken from the international timetabling competition in comparison with a set of state-of-the-art methods from the literature. The experimental results show that the proposed hybrid approach is able to produce promising results for the test PECTPs.     

钢铁生产中的加热炉优化调度算法研究

钢铁生产中的加热炉调度问题属于组合优化中的NP—hard问题．对此．建立了加热炉调度问题的数学规划模型，并提出一种用于求解该问题的超启发式算法——遗传局部搜索算法．基于生产实际数据的仿真实验表明.所提出的方法适用于生产实际．效果优于目前现场使用的人工调度方法．     

A noisy chaotic neural network for solving combinatorial optimization problems: stochastic chaotic simulated annealing

Recently Chen and Aihara have demonstrated both experimentally and mathematically that their chaotic simulated annealing (CSA) has better search ability for solving combinatorial optimization problems compared to both the Hopfield-Tank approach and stochastic simulated annealing (SSA). However, CSA may not find a globally optimal solution no matter how slowly annealing is carried out, because the chaotic dynamics are completely deterministic. In contrast, SSA tends to settle down to a global optimum if the temperature is reduced sufficiently slowly. Here we combine the best features of both SSA and CSA, thereby proposing a new approach for solving optimization problems, i.e., stochastic chaotic simulated annealing, by using a noisy chaotic neural network. We show the effectiveness of this new approach with two difficult combinatorial optimization problems, i.e., a traveling salesman problem and a channel assignment problem for cellular mobile communications.     

物流配送车辆路径问题的优化研究

物流中的车辆路径问题(VRP)是目前组合优化领域的研究热点问题,VRP为NP-hard问题。本文在对VRP分析的基础上,建立数学模型,提出了一种适合求解该问题的蚁群遗传融合优化算法。提出的优化算法首先采用蚁群算法在局部阶段产生最好解,然后利用遗传算法的优良基因在全局阶段对优化解进一步优化,以获取最好路径解。实验结果表明,提出的融合算法能高效解决VRP问题,且优化效果比单算法好。     

A novel feature-based approach to characterize algorithm performance for the traveling salesperson problem

Meta-heuristics are frequently used to tackle NP-hard combinatorial optimization problems. With this paper we contribute to the understanding of the success of 2-opt based local search algorithms for solving the traveling salesperson problem (TSP). Although 2-opt is widely used in practice, it is hard to understand its success from a theoretical perspective. We take a statistical approach and examine the features of TSP instances that make the problem either hard or easy to solve. As a measure of problem difficulty for 2-opt we use the approximation ratio that it achieves on a given instance. Our investigations point out important features that make TSP instances hard or easy to be approximated by 2-opt.