Subdomain generation using emergent ant colony optimization

Finite elements mesh decomposition is a well known optimization problem and is used to split a computationally expensive finite elements mesh into smaller subdomains for parallel finite elements analysis.The ant colony optimization is a type of algorithm that seeks to model the emergent behaviour observed in ant colonies and utilize this behaviour to solve combinatorial problems. This technique has been applied to several problems, most of which are graph related because the ant colony metaphor can be most easily applied to such types of problems. This paper examines the application of ant colony optimization algorithm to the partitioning of unstructured adaptive meshes for parallel explicit time-stepping finite elements analysis.The concept of ant colony optimization technique in addition to the notion of swarm intelligence for finding approximate solutions to combinatorial optimization problems is described. This algorithm combines the features of the classical ant colony optimization technique with swarm intelligence to form a model which is an artificial system designed to perform a certain task.The application of the ant colony optimization for partitioning finite elements meshes based on triangular elements using the swarm intelligence concept is described. A recursive greedy algorithm optimization method is also presented as a local optimization technique to improve the quality of the solutions given by the ant colony optimization algorithm. The partitioning is based on the recursive bisection approach.The mesh partitioning is carried out using normal and predictive modes for which the predictive mode uses a trained multi-layered feedforward neural network that estimates the number of triangular elements that will be generated after finite elements mesh generation is carried out.The performance of the proposed hybrid approach for the recursive bisection of finite elements meshes is examined by decomposing two mesh examples and comparing them with a well known finite elements domain decomposer.     

Ant colony optimization for dynamic routing and wavelength assignment in WDM networks with sparse wavelength conversion

Since optical WDM networks are becoming one of the alternatives for building up backbones, dynamic routing, and wavelength assignment with delay constraints (DRWA-DC) in WDM networks with sparse wavelength conversions is important for a communication model to route requests subject to delay bounds. Since the NP-hard minimum Steiner tree problem can be reduced to the DRWA-DC problem, it is very unlikely to derive optimal solutions in a reasonable time for the DRWA-DC problem. In this paper, we circumvent to apply a meta-heuristic based upon the ant colony optimization (ACO) approach to produce approximate solutions in a timely manner. In the literature, the ACO approach has been successfully applied to several well-known combinatorial optimization problems whose solutions might be in the form of paths on the associated graphs. The ACO algorithm proposed in this paper incorporates several new features so as to select wavelength links for which the communication cost and the transmission delay of routing the request can be minimized as much as possible subject to the specified delay bound. Computational experiments are designed and conducted to study the performance of the proposed algorithm. Comparing with the optimal solutions found by an ILP formulation, numerical results evince that the ACO algorithm is effective and robust in providing quality approximate solutions to the DRWA-DC problem.     

An artificial bee colony algorithm for the minimum routing cost spanning tree problem

Given a connected, weighted, and undirected graph, the minimum routing cost spanning tree problem seeks a spanning tree of minimum routing cost on this graph, where routing cost of a spanning tree is defined as the sum of the costs of the paths connecting all possible pairs of distinct vertices in that spanning tree. This problem has several important applications in networks design and computational biology. In this paper, we have proposed an artificial bee colony (ABC) algorithm-based approach for this problem. We have compared our approach against four best methods reported in the literature—two genetic algorithms, a stochastic hill climber and a perturbation-based local search. Computational results show the superiority of our ABC approach over other approaches.     

一种进化型蚁群算法及其在TSP问题中的检验

蚁群算法是通过模拟蚂蚁觅食而发展出的一种新的启发算法,其收敛速度一直是人们关心的问题。针对蚁群算法的一些不足,提出基于最小生成树的进化型蚁群算法。它利用了最小生成树与最优路径之间的关系限制了蚂蚁在每一个城市的搜寻范围,进化了寻优策略,节省了在不可能构成最优路径的路段上的计算时间,提高了运算速度,克服了以往蚁群算法的计算时间长、精度低的缺点,使得蚁群算法有了显著的提高。计算机仿真结果表明,该文算法改进了标准蚂蚁群算法的效率和计算结果的质量。     

一个蚁群优化模型的期望性能分析

用蚁群优化求解组合优化问题时, 信息素模型及其规则可能使问题的各组件之间的竞争失衡, 从而有可能使蚁群搜索停滞在最差解。 研究了蚁群优化求解k-最小生成树问题时的信息素模型及其更新规则对性能的影响,对原有的信息素模型作出了新的解释:直接表示k-最小生成树问题的边被选择的概率。基于新的信息素模型设计了一种新的解的构造过程,这种过程不仅产生可行解, 也产生不可行解;同时研究了使用可行解和全部解更新信息素模型时算法的迭代期望质量随时间的增减情况,其结果表明, 只使用可行解时迭代期望质量随时间连续降低, 而使用全     

Savings based ant colony optimization for the capacitated minimum spanning tree problem

The problem of connecting a set of client nodes with known demands to a root node through a minimum cost tree network, subject to capacity constraints on all links is known as the capacitated minimum spanning tree (CMST) problem. As the problem is NP-hard, we propose a hybrid ant colony optimization (ACO) algorithm to tackle it heuristically. The algorithm exploits two important problem characteristics: (i) the CMST problem is closely related to the capacitated vehicle routing problem (CVRP), and (ii) given a clustering of client nodes that satisfies capacity constraints, the solution is to find a MST for each cluster, which can be done exactly in polynomial time. Our ACO exploits these two characteristics of the CMST by a solution construction originally developed for the CVRP. Given the CVRP solution, we then apply an implementation of Prim's algorithm to each cluster to obtain a feasible CMST solution. Results from a comprehensive computational study indicate the efficiency and effectiveness of the proposed approach.     

An algorithm based on ant colony optimization for the minimum connected dominating set problem

Ant colony optimization is a well established metaheuristic from the swarm intelligence field for solving difficult optimization problems. In this work we present an application of ant colony optimization to the minimum connected dominating set problem, which is an NP-hard combinatorial optimization problem. Given an input graph, valid solutions are connected subgraphs of the given input graph. Due to the involved connectivity constraints, out-of-the-box integer linear programming solvers do not perform well for this problem. The developed ant colony optimization algorithm uses reduced variable neighborhood search as a sub-routine. Moreover, it can be applied to the weighted and to the non-weighted problem variants. An extensive experimental evaluation presents the comparison of our algorithm with the respective state-of-the-art techniques from the literature. It is shown that the proposed algorithm outperforms the current state of the art for both problem variants. For comparison purposes we also develop a constraint programming approach based on graph variables. Even though its performance deteriorates with growing instance size, it performs surprisingly well, solving 315 out of 481 considered problem instances to optimality.     

A swarm intelligence approach to the quadratic minimum spanning tree problem

The quadratic minimum spanning tree problem (Q-MST) is an extension of the minimum spanning tree problem (MST). In Q-MST, in addition to edge costs, costs are also associated with ordered pairs of distinct edges and one has to find a spanning tree that minimizes the sumtotal of the costs of individual edges present in the spanning tree and the costs of the ordered pairs containing only edges present in the spanning tree. Though MST can be solved in polynomial time, Q-MST is NP-Hard. In this paper we present an artificial bee colony (ABC) algorithm to solve Q-MST. The ABC algorithm is a new swarm intelligence approach inspired by intelligent foraging behavior of honey bees. Computational results show the effectiveness of our approach.     

A hybrid ant colony optimization approach for finite element mesh decomposition

This paper examines the application of the ant colony optimization algorithm to the partitioning of unstructured adaptive meshes for parallel explicit time-stepping finite element analysis. The concept of the ant colony optimization technique for finding approximate solutions to combinatorial optimization problems is described.The application of ant colony optimization for partitioning finite element meshes based on triangular elements is described.A recursive greedy algorithm optimization method is also presented as a local optimization technique to improve the quality of the solutions given by the ant colony optimization algorithm. The partitioning is based on the recursive bisection approach.The mesh decomposition is carried out using normal and predictive modes for which the predictive mode uses a trained multilayered feed-forward neural network which estimates the number of triangular elements that will be generated after finite elements mesh generation is carried out.The performance of the proposed hybrid approach for the recursive bisection of finite element meshes is examined by decomposing two mesh examples.     

Ant colony optimization

Swarm intelligence is a relatively new approach to problem solving that takes inspiration from the social behaviors of insects and of other animals. In particular, ants have inspired a number of methods and techniques among which the most studied and the most successful is the general purpose optimization technique known as ant colony optimization. Ant colony optimization (ACO) takes inspiration from the foraging behavior of some ant species. These ants deposit pheromone on the ground in order to mark some favorable path that should be followed by other members of the colony. Ant colony optimization exploits a similar mechanism for solving optimization problems. From the early nineties, when the first ant colony optimization algorithm was proposed, ACO attracted the attention of increasing numbers of researchers and many successful applications are now available. Moreover, a substantial corpus of theoretical results is becoming available that provides useful guidelines to researchers and practitioners in further applications of ACO. The goal of this article is to introduce ant colony optimization and to survey its most notable applications     

The hyper-cube framework for ant colony optimization.

Ant colony optimization is a metaheuristic approach belonging to the class of model-based search algorithms. In this paper, we propose a new framework for implementing ant colony optimization algorithms called the hyper-cube framework for ant colony optimization. In contrast to the usual way of implementing ant colony optimization algorithms, this framework limits the pheromone values to the interval [0,1]. This is obtained by introducing changes in the pheromone value update rule. These changes can in general be applied to any pheromone value update rule used in ant colony optimization. We discuss the benefits coming with this new framework. The benefits are twofold. On the theoretical side, the new framework allows us to prove that in Ant System, the ancestor of all ant colony optimization algorithms, the average quality of the solutions produced increases in expectation over time when applied to unconstrained problems. On the practical side, the new framework automatically handles the scaling of the objective function values. We experimentally show that this leads on average to a more robust behavior of ant colony optimization algorithms.     

Choquet optimal set in biobjective combinatorial optimization

We study in this paper the generation of the Choquet optimal solutions of biobjective combinatorial optimization problems. Choquet optimal solutions are solutions that optimize a Choquet integral. The Choquet integral is used as an aggregation function, presenting different parameters, and allowing to take into account the interactions between the objectives. We develop a new property that characterizes the Choquet optimal solutions. From this property, a general method to easily generate these solutions in the case of two objectives is defined. We apply the method to two classical biobjective optimization combinatorial optimization problems: the biobjective knapsack problem and the biobjective minimum spanning tree problem. We show that Choquet optimal solutions that are not weighted sum optimal solutions represent only a small proportion of the Choquet optimal solutions and are located in a specific area of the objective space, but are much harder to compute than weighted sum optimal solutions.     

A computationally efficient approach for watershed scale spatial optimization

A multi-level spatial optimization (MLSOPT) approach is developed for solving complex watershed scale optimization problems. The method works at two levels: a watershed is divided into small sub-watersheds and optimum solutions for each sub-watershed are identified individually. Subsequently sub-watershed optimum solutions are used for watershed scale optimization. The approach is tested with complex spatial optimization case studies designed to maximize crop residue (corn stover) harvest with minimum environmental impacts in a 2000 km² watershed. Results from case studies indicated that the MLSOPT approach is robust in convergence and computationally efficient compared to the traditional single-level optimization frameworks. The MLSOPT was 20 times computationally efficient in solving source area based optimization problem while it was 3 times computationally efficient for watershed outlet based optimization problem compared to a corresponding single-level optimizations. The MLSOPT optimization approach can be used in solving complex watershed scale spatial optimization problems effectively.     

Solving minimum constraint removal (MCR) problem using a social-force-model-based ant colony algorithm

The minimum constraint removal (MCR) motion planning problem aims to remove the minimum geometric constraints necessary for removing a free path that connects the starting point and the target point. In essence, discrete MCR problems are non-deterministic polynomial-time (NP)-hard problems; there is a “combinatorial explosion” phenomenon in solving such problems on a large scale. Therefore, we are searching for highly efficient approximate solutions. In the present study, an ant colony algorithm was used to solve these problems. The ant colony algorithm was improved based on the social force model during the solving process, such that it was no longer easy for the algorithm to fall into local extreme, and the algorithm was therefore suitable for solving the MCR problem. The results of the simulation experiments demonstrated that the algorithm used in the present study was superior to the exact algorithm and the greedy algorithm in terms of solution quality and running time.     

Leaf constrained minimal spanning trees solved by modified quantum-behaved particle swarm optimization

Given an undirected, connected, weighted graph, the leaf-constrained minimum spanning tree (LCMST) problem seeks a spanning tree of minimum weight among all the spanning trees of the graph with at least l leaves. In this paper, we have proposed an approach based on Quantum-Behaved Particle Swarm Optimization (QPSO) for the LCMST problem. Particle swarm optimization (PSO) is a well-known population-based swarm intelligence algorithm. Quantum-behaved particle swarm optimization (QPSO) is also proposed by combining the classical PSO philosophy and quantum mechanics to improve performance of PSO. In this paper QPSO has been modified by adding a leaping behavior. When the modified QPSO (MQPSO), falls in to the local optimum, MPSO runs a leaping behavior to leap out the local optimum. We have compared the performance of the proposed method with ML, SCGA, ACO-LCMST, TS-LCMST and ABC-LCMST, which are reported in the literature. Computational results demonstrate the superiority of the MQPSO approach over all the other approaches. The MQPSO approach obtained better quality solutions in shorter time.     

A 2-phase algorithm for solving the single allocation p-hub center problem

The single allocation p-hub center problem is an NP-hard location–allocation problem which consists of locating hub facilities in a network and allocating non-hub nodes to hub nodes such that the maximum distance/cost between origin–destination pairs is minimized. In this paper we present an exact 2-phase algorithm where in the first phase we compute a set of potential optimal hub combinations using a shortest path based branch and bound. This is followed by an allocation phase using a reduced sized formulation which returns the optimal solution. In order to get a good upper bound for the branch and bound we developed a heuristic for the single allocation p-hub center problem based on an ant colony optimization approach. Numerical results on benchmark instances show that the new solution approach is superior over traditional MIP-solver like CPLEX. As a result we are able to provide new optimal solutions for larger problems than those reported previously in literature. We are able to solve problems consisting of up to 400 nodes in reasonable time. To the best of our knowledge these are the largest problems solved in the literature to date.     

Hybrid Nested Partitions and Mathematical Programming Approach and Its Applications

Large-scale discrete optimization problems are difficult to solve, especially when different kinds of real constraints are considered. Conventionally, standard mathematical programming is a general approach for discrete optimization, but may suffer from the unacceptable long solution time in applications. On the other hand, some heuristics/metaheuristics methods are more powerful in finding approximate solutions efficiently, but mostly are problem and constraint dependent. In this paper, we develop a new hybrid nested partitions and mathematical programming approach, which creates compliance between mathematical programming and the heuristics/metaheuristics methods. Potentially applicable to many different types of problems, the hybrid approach can provide approximate solutions efficiently, and in the meantime can easily handle different kinds of constraints. The applications of the hybrid approach to the local pickup and delivery problem (LPDP) and the discrete facility location problem (DFLP) are presented in this paper.     

一类用于连续域寻优的蚁群算法

由真实蚁群觅食行为启发而来的经典蚁群算法,非常适合解决组合优化问题,但经典蚁群算法的离散性本质也限制了其在连续空间问题求解中的应用。为此,提出了一种用于连续域寻优的改进蚁群算法。局部搜索上基于解决离散域问题的经典蚁群优化思想,全局搜索利用类似于遗传算法的交叉、变异操作-称为Ant Diffusion和Ant Walk方法,每代寻优结束后均采用"精英策略"把本代最优个体保留到下一代中。最后,采用改进算法对几个基准函数做了寻优测试,都取得了良好的效果,证明了算法的有效性。     

求解多目标最小生成树的改进多目标蚁群算法

多目标最小生成树问题是典型的NP问题。针对此问题,提出一种改进的多目标蚁群算法。为获得更好的非劣前端,通过合理选取多个信息素扩散源与扩散策略来避免其早熟收敛,并引入非支配排序算子,提高种群多样性并避免算法过早陷入局部最优解。对比实验结果表明：对于多目标最小生成树问题,该算法是有效的,不但在求解效率和解的质量方面优于相关算法,而且随着问题规模的扩大,算法仍保持较好的性能。     

Generalized submodular cover problems and applications

The greedy approach has been successfully applied in the past to produce logarithmic ratio approximations to NP-hard problems under certain conditions. The problems for which these conditions hold are known as submodular cover problems. The current paper³extends the applicability of the greedy approach to wider classes of problems. The usefulness of our extensions is illustrated by giving new approximate solutions for two different types of problems. The first problem is that of finding the spanning tree of minimum weight among those whose diameter is bounded by D. A logarithmic ratio approximation algorithm is given for the cases of D=4 and 5. This approximation ratio is also proved to be the best possible, unless P=NP. The second type involves some (known and new) center selection problems, for which new logarithmic ratio approximation algorithms are given. Again, it is shown that the ratio must be at least logarithmic unless P=NP.