A Graph-based Ant System and its convergence

A general framework for solving combinatorial optimization problems heuristically by the Ant System approach is developed. The framework is based on the concept of a construction graph, a graph assigned to an instance of the optimization problem under consideration, encoding feasible solutions by walks. It is shown that under certain conditions, the solutions generated in each iteration of this Graph-based Ant System converge with a probability that can be made arbitrarily close to 1 to the optimal solution of the given problem instance.     

THE COMBINATORIAL ANT SYSTEM

This paper presents a new distributed algorithm based on Ant System (AS) concepts called Combinatorial Ant System (CAS). It is oriented to solve static discrete-state combinatorial optimization problems. Our approach consists of mapping the solution space of the combinatorial optimization problem in the space where the ants will walk, and defining the transition probability and the pheromone update formula of the Ant System, according to the objective function of the Combinatorial Optimization Problem. We test our approach on the graph partitioning, graph coloring and traveling salesman problems.     

一种改进的蚁群算法在TSP问题中的应用研究

蚁群算法是近几年发展起来的一种新型的拟生态启发式算法,它已经被成功地应用在旅行商(TSP)问题上.由于基本蚁群算法存在过早陷入局部最优解和收敛性较差等缺点,文中对基本蚁群算法在基于蚁群系统的基础上进行了改进,在信息素的更新和解的搜索过程中更多地关注了局部最优解的信息,以使算法尽可能地跳出局部最优,并且改进后的算法对一些关键参数更容易控制.多次实验表明改进的蚁群算法在解决TSP问题上与基本蚁群算法相比有较好的寻优能力和收敛能力.这种算法可以应用在其它组合优化问题上,有一定的工程应用价值.     

– Ant System

Ant System, the first Ant Colony Optimization algorithm, showed to be a viable method for attacking hard combinatorial optimization problems. Yet, its performance, when compared to more fine-tuned algorithms, was rather poor for large instances of traditional benchmark problems like the Traveling Salesman Problem. To show that Ant Colony Optimization algorithms could be good alternatives to existing algorithms for hard combinatorial optimization problems, recent research in this area has mainly focused on the development of algorithmic variants which achieve better performance than Ant System.In this paper, we present – Ant System ( ), an Ant Colony Optimization algorithm derived from Ant System. differs from Ant System in several important aspects, whose usefulness we demonstrate by means of an experimental study. Additionally, we relate one of the characteristics specific to — that of using a greedier search than Ant System — to results from the search space analysis of the combinatorial optimization problems attacked in this paper. Our computational results on the Traveling Salesman Problem and the Quadratic Assignment Problem show that is currently among the best performing algorithms for these problems.     

A survey on metaheuristics for stochastic combinatorial optimization

Metaheuristics are general algorithmic frameworks, often nature-inspired, designed to solve complex optimization problems, and they are a growing research area since a few decades. In recent years, metaheuristics are emerging as successful alternatives to more classical approaches also for solving optimization problems that include in their mathematical formulation uncertain, stochastic, and dynamic information. In this paper metaheuristics such as Ant Colony Optimization, Evolutionary Computation, Simulated Annealing, Tabu Search and others are introduced, and their applications to the class of Stochastic Combinatorial Optimization Problems (SCOPs) is thoroughly reviewed. Issues common to all metaheuristics, open problems, and possible directions of research are proposed and discussed. In this survey, the reader familiar to metaheuristics finds also pointers to classical algorithmic approaches to optimization under uncertainty, and useful informations to start working on this problem domain, while the reader new to metaheuristics should find a good tutorial in those metaheuristics that are currently being applied to optimization under uncertainty, and motivations for interest in this field.

A new heuristic approach for non-convex optimization problems

In this work a new optimization method, called the heuristic Kalman algorithm (HKA), is presented. This new algorithm is proposed as an alternative approach for solving continuous, non-convex optimization problems. The principle of HKA is to explicitly consider the optimization problem as a measurement process designed to give an estimate of the optimum. A specific procedure, based on the Kalman estimator, was developed to improve the quality of the estimate obtained through the measurement process. The main advantage of HKA, compared to other metaheuristics, lies in the small number of parameters that need to be set by the user. Further, it is shown that HKA converges almost surely to a near-optimal solution. The efficiency of HKA was evaluated in detail using several non-convex test problems, both in the unconstrained and constrained cases. The results were then compared to those obtained via other metaheuristics. The numerical experiments show that HKA is a promising approach for solving non-convex optimization problems, particularly in terms of computation time and success ratio.     

约束法蚁群算法在多目标VRP中的研究

多目标车辆路径问题(MVRP)在物流研究领域具有重要的理论和现实意义,但由于各目标之间的相互联系和制约使得建模和求解具有很大的难度.在众多求解方法中,蚁群算法对解决类似组合优化问题具有明显的优势,蚁群算法已成功应用于一系列单目标优化问题,但对多目标问题的研究还处于起步阶段.侧重结合目标约束法与蚁群算法来研究多目标车辆路径问题,使各优化目标之间形成既彼此独立,又相互联系和制约的机制,最终求得多目标优化意义下的一种平衡解.仿真结果证明该算法具有良好的收敛性和运行效率,对于物流运输的实际运作具有重要的现实意义.     

Single and parallel machine capacitated lotsizing and scheduling: New iterative MIP-based neighborhood search heuristics

We propose a general-purpose heuristic approach combining metaheuristics and mixed integer programming to find high quality solutions to the challenging single- and parallel-machine capacitated lotsizing and scheduling problem with sequence-dependent setup times and costs. Commercial solvers fail to solve even medium-sized instances of this NP-hard problem; therefore, heuristics are required to find competitive solutions. We develop construction, improvement and search heuristics all based on MIP formulations. We then compare the performance of these heuristics with those of two metaheuristics and other MIP-based heuristics that have been proposed in the literature, and to a state-of-the-art commercial solver. A comprehensive set of computational experiments shows the effectiveness and efficiency of the main approach, a stochastic MIP-based local search heuristic, in solving medium to large size problems. Our solution procedures are quite flexible and may easily be adapted to cope with model extensions or to address different optimization problems that arise in practice.     

Optimum design of laminated composite plates containing a quasi-square cutout

In this paper, an attempt has been made to calculate the optimal values of effective parameters on the stress distribution around a quasi-square cutout using different optimization algorithms such as Particle Swarm Optimization (PSO), Genetic Algorithm (GA) and Ant Colony Optimization (ACO). To achieve this goal, the analytical results of symmetric laminated composite plates containing a square cutout have been used. The analytical solution can be achieved with the development of the Lekhnitskii solution method. This method is based on using complex variable method in the analysis of two-dimensional problems. In order to use the method in stress analysis of laminates containing a square cutout, by using conformal mapping, the area outside the square cutout is mapped to the area outside of a unit circle. Effective parameters on stress distribution around the square cutout in symmetric laminated plates considered as design variables include: load angle, cutout orientation, bluntness and the stacking sequence of the laminate. Cost function in this problem is the maximum stress created around the cutout calculated by the analytical solution method. Another goal of this paper is to investigate the performance of aforementioned optimization algorithms. The results show that the PSO algorithm converges earlier than the other two methods and have the better cost function.     

A general-purpose tunable landscape generator

The research literature on metaheuristic and evolutionary computation has proposed a large number of algorithms for the solution of challenging real-world optimization problems. It is often not possible to study theoretically the performance of these algorithms unless significant assumptions are made on either the algorithm itself or the problems to which it is applied, or both. As a consequence, metaheuristics are typically evaluated empirically using a set of test problems. Unfortunately, relatively little attention has been given to the development of methodologies and tools for the large-scale empirical evaluation and/or comparison of metaheuristics. In this paper, we propose a landscape (test-problem) generator that can be used to generate optimization problem instances for continuous, bound-constrained optimization problems. The landscape generator is parameterized by a small number of parameters, and the values of these parameters have a direct and intuitive interpretation in terms of the geometric features of the landscapes that they produce. An experimental space is defined over algorithms and problems, via a tuple of parameters for any specified algorithm and problem class (here determined by the landscape generator). An experiment is then clearly specified as a point in this space, in a way that is analogous to other areas of experimental algorithmics, and more generally in experimental design. Experimental results are presented, demonstrating the use of the landscape generator. In particular, we analyze some simple, continuous estimation of distribution algorithms, and gain new insights into the behavior of these algorithms using the landscape generator.     

Structural optimal design of systems with imprecise properties: a possibilistic approach

The optimization problem of structural systems with imprecise properties on the basis of a possibilistic approach is considered. System imprecisions are defined by fuzzy numbers and characterized by membership functions. A methodology for the efficient solution of the optimization process is presented. A two-step method is used to include the imprecision within the optimization, where high quality approximations are used for the evaluation of structural responses. The approximations are constructed using concepts of intermediate response quantities and intermediate variables. The approach is basically an algebraic process which can be implemented very efficiently for the optimal design of general structural systems with imprecise parameters. The method provides more information to the designer than is available using conventional design tools. The effectiveness of the methodology and the interpretation of the results are illustrated by the solution of two example problems.     

VERY STRONGLY CONSTRAINED PROBLEMS: AN ANT COLONY OPTIMIZATION APPROACH

Ant Colony Optimization (ACO) is a class of metaheuristic algorithms sharing the common approach of constructing a solution on the basis of information provided both by a standard constructive heuristic and by previously constructed solutions. This article is composed of three parts. The first one frames ACO in current trends of research on metaheuristics for combinatorial optimization. The second outlines some current research within the ACO community, reporting recent results obtained on different problems, while the third part focuses on a particular research line, named ANTS, providing some details on the algorithm and presenting results recently obtained on a prototypical strongly constrained problem: the set partitioning problem.     

Multi‐objective optimization using metaheuristics: non‐standard algorithms

In recent years, the application of metaheuristic techniques to solve multi‐objective optimization problems has become an active research area. Solving this kind of problems involves obtaining a set of Pareto‐optimal solutions in such a way that the corresponding Pareto front fulfils the requirements of convergence to the true Pareto front and uniform diversity. Most of the studies on metaheuristics for multi‐objective optimization are focused on Evolutionary Algorithms, and some of the state‐of‐the‐art techniques belong this class of algorithms. Our goal in this paper is to study open research lines related to metaheuristics but focusing on less explored areas to provide new perspectives to those researchers interested in multi‐objective optimization. In particular, we focus on non‐evolutionary metaheuristics, hybrid multi‐objective metaheuristics, parallel multi‐objective optimization and multi‐objective optimization under uncertainty. We analyze these issues and discuss open research lines.     

Transit network design by Bee Colony Optimization

The transit network design problem is one of the most significant problems faced by transit operators and city authorities in the world. This transportation planning problem belongs to the class of difficult combinatorial optimization problem, whose optimal solution is difficult to discover. The paper develops a Swarm Intelligence (SI) based model for the transit network design problem. When designing the transit network, we try to maximize the number of satisfied passengers, to minimize the total number of transfers, and to minimize the total travel time of all served passengers. Our approach to the transit network design problem is based on the Bee Colony Optimization (BCO) metaheuristics. The BCO algorithm is a stochastic, random-search technique that belongs to the class of population-based algorithms. This technique uses a similarity among the way in which bees in nature look for food, and the way in which optimization algorithms search for an optimum of a combinatorial optimization problem. The numerical experiments are performed on known benchmark problems. We clearly show that our approach, based on the BCO algorithm, is competitive with other approaches in the literature, and it can generate high-quality solutions.     

Reinforcement learning for optimum design of a plane frame under static loads

A new method is presented for optimum cross-sectional design of planar frame structures combining reinforcement learning (RL) and metaheuristics. The method starts from RL jointly using artificial neural network so that the action taker, or the agent, can choose a proper action on which members to be increased, reduced or kept their size. The size of the neural network is compressed into small numbers of inputs and outputs utilizing story-wise decomposition of the frame. The trained agent is used in the process of generating a neighborhood solution during optimization with simulated annealing (SA) and particle swarm optimization (PSO). Because the proposed method is able to explore the solution space efficiently, better optimal solutions can be found with less computational cost compared with those obtained solely by metaheuristics. Utilization of RL agent also leads to high-quality optimal solutions regardless of variation of parameters of SA and PSO or initial solution. Furthermore, once the agent is trained, it can be applied to optimization of other frames with different numbers of stories and spans.

     

求解置换流水车间调度问题的混合蚁群算法

针对最大—最小蚂蚁系统在解决置换流水车间调度问题时易陷入局部最优的问题,引入最好—最差蚂蚁系统中的信息素变异和重置规则,提出了一种混合蚁群算法。使信息素矩阵变异并在搜索过程停滞时重置信息素矩阵以在搜索过程中引入多样性。在基准问题集上的对比实验表明,该算法比传统的蚁群算法具有更好的搜索全局最优解的能力。     

A comprehensive survey on optimizing deep learning models by metaheuristics

Deep neural networks (DNNs), which are extensions of artificial neural networks, can learn higher levels of feature hierarchy established by lower level features by transforming the raw feature space to another complex feature space. Although deep networks are successful in a wide range of problems in different fields, there are some issues affecting their overall performance such as selecting appropriate values for model parameters, deciding the optimal architecture and feature representation and determining optimal weight and bias values. Recently, metaheuristic algorithms have been proposed to automate these tasks. This survey gives brief information about common basic DNN architectures including convolutional neural networks, unsupervised pre-trained models, recurrent neural networks and recursive neural networks. We formulate the optimization problems in DNN design such as architecture optimization, hyper-parameter optimization, training and feature representation level optimization. The encoding schemes used in metaheuristics to represent the network architectures are categorized. The evolutionary and selection operators, and also speed-up methods are summarized, and the main approaches to validate the results of networks designed by metaheuristics are provided. Moreover, we group the studies on the metaheuristics for deep neural networks based on the problem type considered and present the datasets mostly used in the studies for the readers. We discuss about the pros and cons of utilizing metaheuristics in deep learning field and give some future directions for connecting the metaheuristics and deep learning. To the best of our knowledge, this is the most comprehensive survey about metaheuristics used in deep learning field.

     

An agent based approach for the implementation of cooperative proactive S-Metaheuristics

This paper introduces several cooperative proactive S-Metaheuristics, i.e. single-solution based metaheuristics, which are implemented taking advantage of two singular characteristics of the agent paradigm: proactivity and cooperation. Proactivity is applied to improve traditional versions of Threshold Accepting and Great Deluge Algorithm metaheuristics. This approach follows previous work for the definition of proactive versions of the Record-to-Record Travel and Local Search metaheuristics. Proactive metaheuristics are implemented as agents that cooperate in the environment of the optimization process with the goal of avoiding stagnation in local optima by adjusting their parameters. Based on the environmental information about previous solutions, the proactive adjustment of the parameters is focused on keeping a minimal level of acceptance for the new solutions. In addition, simple forms of cooperation by competition are used to develop cooperative metaheuristics based on the combination of the four proactive metaheuristics. The proposed metaheuristics have been validated through experimentation with 28 benchmark functions on binary strings, and several instances of knapsack problems and travelling salesman problems.     

Energy efficient teaching-learning-based optimization for the discrete routing problem in wireless sensor networks

Wireless sensor networks (WSNs) are composed of sensor nodes, having limited energy resources and low processing capability. Accordingly, major challenges are involved in WSNs Routing. Thus, in many use cases, routing is considered as an NP-hard optimization problem. Many routing protocols are based on metaheuristics, such as Ant Colony Optimization (ACO) and Particle Swarm Optimization (PSO). Despite the fact that metaheuristics have provided elegant solutions, they still suffer from complexity concerns and difficulty of parameter tuning. In this paper, we propose a new routing approach based on Teaching Learning Based Optimization (TLBO) which is a recent and robust method, consisting on two essential phases: Teacher and Learner. As TLBO was proposed for continuous optimization problems, this work presents the first use of TLBO for the discrete problem of WSN routing. The approach is well founded theoretically as well as detailed algorithmically. Experimental results show that our approach allows obtaining lower energy consumption which leads to a better WSN lifetime. Our method is also compared to some typical routing methods; PSO approach, advanced ACO approach, Improved Harmony based approach (IHSBEER) and Ad-hoc On-demand Distance Vector (AODV) routing protocol, to illustrate TLBO’s routing efficiency.     

基于改进蚁群算法的数据仓库多连接查询优化

传统蚁群算法在解决数据仓库查询优化问题时存在过早收敛、收敛速度慢的缺点。为此,对传统蚁群算法进行改进,将伪随机状态转移规则引入最大最小蚁群系统,在每次迭代结束后进行迭代局部搜索。实验结果表明,改进算法在多表连接查询优化中具有较快的收敛速度,能提高最优解的质量。