基于文化的连续蚂蚁优化算法的研究*

针对蚂蚁优化算法在求解连续空间问题方面的缺陷,提出一种基于文化的连续蚂蚁优化算法。该算法将蚂蚁优化算法纳入文化算法的框架,组成基于蚂蚁优化算法的主群体和信念的两大空间。在知识和群体层面使用双重进化机制支持问题的求解和知识的提取,从而充分利用精英蚂蚁所携带的特征信息,在很大程度上提高了收敛速度,增强了搜索的多样性。实验结果表明,该算法求解速度快、寻优成功率高,是一种提高蚂蚁优化算法性能的有效算法。     

基于聚类分析的增强型蚁群算法

针对蚁群算法存在的早熟收敛、搜索时间长等不足,提出一种增强型蚁群算法.该算法构建了一优解池,保存到当前迭代为止获得的若干优解,并提出一种基于邻域的聚类算法,通过对优解池中的元素聚类,捕获不同的优解分布区域.该算法交替使用不同簇中的优解更新信息素,兼顾考虑了搜索的强化性和分散性.针对典型的旅行商问题进行仿真实验,结果表明该算法获得的解质量高于已有的蚁群算法.     

An ant colony optimization algorithm for DNA sequencing by hybridization

The reconstruction of DNA sequences from DNA fragments is one of the most challenging problems in computational biology. In recent years the specific problem of DNA sequencing by hybridization has attracted quite a lot of interest in the optimization community. Several metaheuristics such as tabu search and evolutionary algorithms have been applied to this problem. However, the performance of existing metaheuristics is often inferior to the performance of recently proposed constructive heuristics. On the basis of these new heuristics we develop an ant colony optimization algorithm for DNA sequencing by hybridization. An important feature of this algorithm is the implementation in a so-called multi-level framework. The computational results show that our algorithm is currently a state-of-the-art method for the tackled problem.     

Structural topology optimization using ant colony optimization algorithm

The ant colony optimization (ACO) algorithm, a relatively recent bio-inspired approach to solve combinatorial optimization problems mimicking the behavior of real ant colonies, is applied to problems of continuum structural topology design. An overview of the ACO algorithm is first described. A discretized topology design representation and the method for mapping ant's trail into this representation are then detailed. Subsequently, a modified ACO algorithm with elitist ants, niche strategy and memory of multiple colonies is illustrated. Several well-studied examples from structural topology optimization problems of minimum weight and minimum compliance are used to demonstrate its efficiency and versatility. The results indicate the effectiveness of the proposed algorithm and its ability to find families of multi-modal optimal design.     

An ant colony optimization algorithm for continuous optimization: application to feed-forward neural network training

Ant colony optimization (ACO) is an optimization technique that was inspired by the foraging behaviour of real ant colonies. Originally, the method was introduced for the application to discrete optimization problems. Recently we proposed a first ACO variant for continuous optimization. In this work we choose the training of feed-forward neural networks for pattern classification as a test case for this algorithm. In addition, we propose hybrid algorithm variants that incorporate short runs of classical gradient techniques such as backpropagation. For evaluating our algorithms we apply them to classification problems from the medical field, and compare the results to some basic algorithms from the literature. The results show, first, that the best of our algorithms are comparable to gradient-based algorithms for neural network training, and second, that our algorithms compare favorably with a basic genetic algorithm.

Inducing decision trees with an ant colony optimization algorithm

Decision trees have been widely used in data mining and machine learning as a comprehensible knowledge representation. While ant colony optimization (ACO) algorithms have been successfully applied to extract classification rules, decision tree induction with ACO algorithms remains an almost unexplored research area. In this paper we propose a novel ACO algorithm to induce decision trees, combining commonly used strategies from both traditional decision tree induction algorithms and ACO. The proposed algorithm is compared against three decision tree induction algorithms, namely C4.5, CART and cACDT, in 22 publicly available data sets. The results show that the predictive accuracy of the proposed algorithm is statistically significantly higher than the accuracy of both C4.5 and CART, which are well-known conventional algorithms for decision tree induction, and the accuracy of the ACO-based cACDT decision tree algorithm.     

基于免疫修复的快速蚁群优化算法

蚁群优化算法通过信息素记录搜索过程中获取的知识,并基于信息素搜索新的解．影响信息素质量的因素主要是信息素更新策略和蚂蚁已找到的候选解的质量．为了提高已有候选解的质量,提出基于免疫原理识别候选解中的“病变”成分,并对其“病变”成分进行修复．经免疫修复后,候选解的质量大大提高,由它更新的信息素更好地反映了优质解的特点,从而加快了信息的正反馈过程．实验结果验证了该算法的有效性．     

A hybrid ant colony optimization algorithm for optimal multiuser detection in DS-UWB system

A hybrid ant colony optimization algorithm is proposed by introducing extremal optimization local-search algorithm to the ant colony optimization (ACO) algorithm, and is applied to multiuser detection in direct sequence ultra wideband (DS-UWB) communication system in this paper. ACO algorithms have already successfully been applied to combinatorial optimization; however, as the pheromone accumulates, we may not get a global optimum because it can get stuck in a local minimum resulting in a bad steady state. Extremal optimization (EO) is a recently developed local-search heuristic method and has been successfully applied to a wide variety of optimization problems. Hence in this paper, a hybrid ACO algorithm, named ACO-EO algorithm, is proposed by introducing EO to ACO to improve the local-search ability of the algorithm. The ACO-EO algorithm is applied to multiuser detection in DS-UWB communication system, and via computer simulations it is shown that the proposed hybrid ACO algorithm has much better performance than other ACO algorithms and even equal to the optimal multiuser detector.     

A new ant colony optimization algorithm for the multidimensional Knapsack problem

The paper proposes a new ant colony optimization (ACO) approach, called binary ant system (BAS), to multidimensional Knapsack problem (MKP). Different from other ACO-based algorithms applied to MKP, BAS uses a pheromone laying method specially designed for the binary solution structure, and allows the generation of infeasible solutions in the solution construction procedure. A problem specific repair operator is incorporated to repair the infeasible solutions generated in every iteration. Pheromone update rule is designed in such a way that pheromone on the paths can be directly regarded as selecting probability. To avoid premature convergence, the pheromone re-initialization and different pheromone intensification strategy depending on the convergence status of the algorithm are incorporated. Experimental results show the advantages of BAS over other ACO-based approaches for the benchmark problems selected from OR library.     

一种求解函数优化的自适应蚁群算法

针对多极值连续函数优化问题,提出了一种自适应蚁群算法。该方法将解空间划分成若干子域,根据蚂蚁在搜索过程中所得解的分布状况动态的调节蚂蚁的路径选择策略和信息量更新策略,求出解所在的子域,然后在该子城内确定解的具体值。仿真结果表明谊算法具有不易陷入局部最优、解的精度高、收敛速度快、稳定性好等优点,其性能优于基本遗传算法以及克隆选择算法。     

Scalable platforms using ant colony optimization

Mass customization necessitates increased product variety at the customers’ end but comparatively lesser part variety at the manufacturer’s end. Product platform concepts have been successful to achieve this goal at large. One of the popular methods for product platform formation is to scale one or more design variables called the scaling variables. Effective optimization methods are needed to identify proper values of the scaling variables. This paper presents a graph-based optimization method called the scalable platforms using ant colony optimization (SPACO) method for identifying appropriate values of the scaling variables. In the graph-based representation, each node signifies a sub-range of values for a design variable. This application includes the concept of multiplicity in node selection because there are multiple nodes corresponding to the discretized values of a given design variable. In the SPACO method, the overall decision is a result of the cumulative decisions, made by simple computing agents called the ants, over a number of iterations. The space search technique initially starts as a random search technique over the entire search space and progressively turns into an autocatalytic (positive feedback) probabilistic search technique as the solution matures. We use a family of universal electric motors, widely cited in the literature, to test the effectiveness of the proposed method. Our simulation results, when compared to the results reported in the literature, prove that SPACO method is a viable optimization method for determining the values of design variables for scalable platforms.     

Solution bias in ant colony optimisation: Lessons for selecting pheromone models

Ant colony optimisation is a constructive metaheuristic in which solutions are built probabilistically influenced by the parameters of a pheromone model—an analogue of the trail pheromones used by real ants when foraging for food. Recent studies have uncovered the presence of biases in the solution construction process, the existence and nature of which depend on the characteristics of the problem being solved. The presence of these solution construction biases induces biases in the pheromone model used, so selecting an appropriate model is highly important. The first part of this paper presents new findings bridging biases due to construction with biases in pheromone models. Novel approaches to the prediction of this bias are developed and used with the knapsack and generalised assignment problems. The second part of the paper deals with the selection of appropriate pheromone models when detailed knowledge of their biases is not available. Pheromone models may be derived either from characteristics of the way solutions are represented by the algorithm or characteristics of the solutions represented, which are often quite different. Recently it has been suggested that the latter is more appropriate. The relative performance of a number of alternative pheromone models for six well-known combinatorial optimisation problems is examined to test this hypothesis. Results suggest that, in general, modelling characteristics of solutions (rather than their representations) does lead to the best performance in ACO algorithms. Consequently, this principle may be used to guide the selection of appropriate pheromone models in problems to which ACO has not yet been applied.     

An adaptive ant colony optimization algorithm for constructing cognitive diagnosis tests

A critical issue in the applications of cognitive diagnosis models (CDMs) is how to construct a feasible test that achieves the optimal statistical performance for a given purpose. As it is hard to mathematically formulate the statistical performance of a CDM test based on the items used, exact algorithms are inapplicable to the problem. Existing test construction heuristics, however, suffer from either limited applicability or slow convergence. In order to efficiently approximate the optimal CDM test for different construction purposes, this paper proposes a novel test construction method based on ant colony optimization (ACO-TC). This method guides the test construction procedure with pheromone that represents previous construction experience and heuristic information that combines different item discrimination indices. Each test constructed is evaluated through simulation to ensure convergence towards the actual optimum. To further improve the search efficiency, an adaptation strategy is developed, which adjusts the design of heuristic information automatically according to the problem instance and the search stage. The effectiveness and efficiency of the proposed method is validated through a series of experiments with different conditions. Results show that compared with traditional test construction methods of CDMs, the proposed ACO-TC method can find a test with better statistical performance at a faster speed.     

Applying multi-objective ant colony optimization algorithm for solving the unequal area facility layout problems

The unequal area facility layout problem (UA-FLP) which deals with the layout of departments in a facility comprises of a class of extremely difficult and widely applicable multi-objective optimization problems with constraints arising in diverse areas and meeting the requirements for real-world applications. Based on the heuristic strategy, the problem is first converted into an unconstrained optimization problem. Then, we use a modified version of the multi-objective ant colony optimization (MOACO) algorithm which is a heuristic global optimization algorithm and has shown promising performances in solving many optimization problems to solve the multi-objective UA-FLP. In the modified MOACO algorithm, the ACO with heuristic layout updating strategy which is proposed to update the layouts and add the diversity of solutions is a discrete ACO algorithm, with a difference from general ACO algorithms for discrete domains which perform an incremental construction of solutions but the ACO in this paper does not. We propose a novel pheromone update method and combine the Pareto optimization based on the local pheromone communication and the global search based on the niche technology to obtain Pareto-optimal solutions of the problem. In addition, the combination of the local search based on the adaptive gradient method and the heuristic department deformation strategy is applied to deal with the non-overlapping constraint between departments so as to obtain feasible solutions. Ten benchmark instances from the literature are tested. The experimental results show that the proposed MOACO algorithm is an effective method for solving the UA-FLP.     

用蚁群算法求解带平衡约束的圆形布局问题

采用启发式方法结合演化算法的思路求解带平衡约束的圆形布局问题.首先对传统优化模型进行调整,并探讨了调整的合理性;然后设计一种分步定位的布局方法,在此基础上利用蚁群算法寻优;最后利用局部搜索技术,在传统模型意义下对布局进行了改进.数值实验表明,算法的性能比目前已有的结果有较大的提高.     

Diversity control in ant colony optimization

Optimization inspired by cooperative food retrieval in ants has been unexpectedly successful and has been known as ant colony optimization (ACO) in recent years. One of the most important factors to improve the performance of the ACO algorithms is the complex trade-off between intensification and diversification. This article investigates the effects of controlling the diversity by adopting a simple mechanism for random selection in ACO. The results of computer experiments have shown that it can generate better solutions stably for the traveling salesmen problem than AS_rank which is known as one of the newest and best ACO algorithms by utilizing two types of diversity.     

An ant colony optimization routing algorithm for two order pickers with congestion consideration

This paper develops a routing method to control the picker congestion that challenges the traditional assumption regarding the narrow-aisle order picking system. We proposes a new routing algorithm based on Ant Colony Optimization (ACO) for two order pickers (A-TOP) with congestion consideration. Using two extended dedicated heuristics with congestion consideration as reference group, a comprehensive simulation study is conducted to evaluate the effectiveness of A-TOP. The simulation proves that A-TOP achieves the shortest total picking time in most instances and performs well in dealing with the congestion. The impacts of warehouse layout, order size, and pick:walk-time ratio on A-TOP and system performance are analyzed as well. A-TOP can adapt to different warehouse configurations, meanwhile, it can be easily extended to the situation with more than two order pickers.     

MSDP with ACO: A maximal SRLG disjoint routing algorithm based on ant colony optimization

Failure resilience is a desired feature in communication networks, and different methods can be considered in order to achieve this feature. One of these methods is diverse Routing. In this paper, we are going to suggest a sort of diverse routing algorithm, which can find two maximal shared risk link group (SRLG) disjoint paths between a source and a destination node. This algorithm is based on ant colony optimization algorithm, which consists of three parts. These parts are graph transformation technique, finding two maximal edge-disjoint routes and reverse transformation. The final routes are always maximal SRLG disjoint. Simulation results show the efficiency of the proposed method.     

基于信息素适量更新与变异的高效蚁群算法

为了克服基本蚁群算法求解速度慢、易于出现早熟和停滞现象的缺陷,提出了一种高效的蚁群算法（EACA）。它修改了基本蚁群算法中信息素的更新规则,使得每轮搜索后信息素的增量能更好地反映解的质量,以加快收敛;另外,它采用了一种启发式变异方法对路径进行优化,以产生搅动效应,避免早熟。以TSP问题为例进行的实验结果表明：提出的算法优于ACA和ACAGA。