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.     

Decomposition-based classified ant colony optimization algorithm for scheduling semiconductor wafer fabrication system

Due to its typical features, such as large-scale, multiple re-entrant flows, and hybrid machine types, the semiconductor wafer fabrication system (SWFS) is extremely difficult to schedule. In order to cope with this difficulty, the decomposition-based classified ant colony optimization (D-CACO) method is proposed and analyzed in this paper. The D-CACO method comprises decomposition procedure and classified ant colony optimization algorithm. In the decomposition procedure, a large and complicate scheduling problem is decomposed into several subproblems and these subproblems are scheduled in sequence. The classified ACO algorithm then groups all of the operations of the subproblems and schedules them according to machine type. To test the effect of the method, a set of simulations are conducted on a virtual fab simulation platform. The test results show that the proposed D-CACO algorithm works efficiently in scheduling SWFS.     

一种改进的自适应蚁群算法

蚁群算法是一种新型的模拟进化算法,研究表明此算法具有一些优良性质,但是蚁群算法容易陷入局部最优。分析了蚁群算法陷入局部最优的主要原因,根据算法陷入最优的原因提出一种判断局部最优的方法;在蚁群算法中引入判断局部最优的策略,当算法陷入局部最优时对参数做相应的变化,来克服蚁群算法易陷入局部最优的缺陷。实验表明此方法行之有效。     

Ant colony optimization algorithm to solve for the transportation problem of cross-docking network

This paper addresses the transportation problem of cross-docking network where the loads are transferred from origins (suppliers) to destinations (retailers) through cross-docking facilities, without storing them in a distribution center (DC). We work on minimizing the transportation cost in a network by loading trucks in the supplier locations and then route them either directly to the customers or indirectly to cross-docking facilities so the loads can be consolidated. For generating a truck operating plan in this type of distribution network, the problem was formulated using an integer programming (IP) model and solved using a novel ant colony optimization (ACO) algorithm. We solved several numerical examples for verification and demonstrative purposes and found that our proposed approach finds solutions that significantly reduce the shipping cost in the network of cross-docks and considerably outperform Branch-and-Bound algorithm especially for large problems.     

First steps to the runtime complexity analysis of ant colony optimization

The paper presents results on the runtime complexity of two ant colony optimization (ACO) algorithms: ant system, the oldest ACO variant, and GBAS, the first ACO variant for which theoretical convergence results have been established. In both cases, as the class of test problems under consideration, a slight generalization of the well-known OneMax test function has been chosen. The techniques used for the runtime analysis of the two algorithms differ: in the case of GBAS, the expected runtime until the optimal solution is reached is studied by a direct bound estimation approach inspired by comparable results for the (1+1)$(1+1)$ evolutionary algorithm (EA). A runtime bound of order O(mlogm)$O(m\log m)$, where m   is the problem instance size, is obtained. In the case of ant system, the original discrete stochastic process is approximated by a suitable continuous deterministic process. The validity of the approximation is shown by means of a rigid convergence theorem exploiting a classical result from mathematical learning theory. Using this approximation, it is demonstrated that for the considered OneMax-type problems, a runtime of order O(mlog(1/ε))$O(m\log (1/\epsilon ))$ until reaching an expected relative   solution quality of 1-ε$1-\epsilon$, and a runtime of O(mlogm)$O(m\log m)$ until reaching the optimal   solution with high probability can be predicted. Our results are the first to show competitiveness in runtime complexity with (1+1$1+1$) EA on OneMax for a proper ACO algorithm.     

An ant colony optimization approach to a permutational flowshop scheduling problem with outsourcing allowed

This paper deals with the scheduling problem of minimizing the makespan in a permutational flowshop environment with the possibility of outsourcing certain jobs. It addresses this problem by means of the development of an ant colony optimization-based algorithm. This new algorithm, here named as flowshop ant colony optimization is composed of two combined ACO heuristics. The results show that this new approach can be used to solve the problem efficiently and in a short computational time.     

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.

Runtime analysis of the 1-ANT ant colony optimizer

The runtime analysis of randomized search heuristics is a growing field where, in the last two decades, many rigorous results have been obtained. First runtime analyses of ant colony optimization (ACO) have been conducted only recently. In these studies simple ACO algorithms such as the 1-ANT are investigated. The influence of the evaporation factor in the pheromone update mechanism and the robustness of this parameter w.r.t. the runtime behavior have been determined for the example function OneMax.This work puts forward the rigorous runtime analysis of the 1-ANT on the example functions LeadingOnes and BinVal. With respect to Evolutionary Algorithms (EAs), such analyses were essential to develop methods for the analysis on more complicated problems. The proof techniques required for the 1-ANT, unfortunately, differ significantly from those for EAs, which means that a new reservoir of methods has to be built up. Again, the influence of the evaporation factor is analyzed rigorously, and it is proved that its choice has a crucial impact on the runtime. Moreover, the analyses provide insight into the working principles of ACO algorithms. Our theoretical results are accompanied by experimental results that give us a more detailed impression of the 1-ANT’s performance. Furthermore, the experiments also deal with the question whether using many ant solutions in one iteration can decrease the total runtime.     

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

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

基于资源状态蚁群算法的云计算任务分配

针对云计算中的任务分配问题,分析任务资源之间的数学模型,提出一种基于资源状态蚁群算法,相对一般蚁群算法,加入虚拟机实时状态,更精确地表达云计算任务分配的问题.通过CloudSim工具设计仿真实验,实验结果表明,与最近Cristian Mateos提出的蚁群改进算法相比,该算法在任务完成时间、算法稳定收敛方面取得了较好表现,以RR算法为基准,该算法提高后的时间比例稳定在RR算法任务完成时间的60％～65％,稳定性提高4.7倍.     

Hybridization strategies for continuous ant colony optimization and particle swarm optimization applied to data clustering

Ant colony optimization (ACO) and particle swarm optimization (PSO) are two popular algorithms in swarm intelligence. Recently, a continuous ACO named ACOR was developed to solve the continuous optimization problems. This study incorporated ACOR with PSO to improve the search ability, investigating four types of hybridization as follows: (1) sequence approach, (2) parallel approach, (3) sequence approach with an enlarged pheromone-particle table, and (4) global best exchange. These hybrid systems were applied to data clustering. The experimental results utilizing public UCI datasets show that the performances of the proposed hybrid systems are superior compared to those of the K-mean, standalone PSO, and standalone ACOR. Among the four strategies of hybridization, the sequence approach with the enlarged pheromone table is superior to the other approaches because the enlarged pheromone table diversifies the generation of new solutions of ACOR and PSO, which prevents traps into the local optimum.     

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.     

An ant colony optimization approach to multi-objective optimal design of symmetric hybrid laminates for maximum fundamental frequency and minimum cost

An ant colony optimization algorithm for optimum design of symmetric hybrid laminates is described. The objective is simultaneous maximization of fundamental frequency and minimization of cost. Number of surface and core layers made of high-stiffness and low-stiffness materials, respectively, and fiber orientations are the design variables. Optimal stacking sequences are given for hybrid graphite/epoxy-glass/epoxy laminated plates with different aspect ratios and number of plies. The results obtained by ant colony optimization are compared to results obtained by a genetic algorithm and simulated annealing. The effectiveness of the hybridization concept for reducing the weight and keeping the fundamental frequency at a reasonable level is demonstrated. Furthermore, it is shown that the proposed ant colony algorithm outperforms the two other heuristics.     

Two-stage updating pheromone for invariant ant colony optimization algorithm

Ant colony optimization (ACO) is a metaheuristic approach for combinatorial optimization problems. With the introduction of hypercube framework, invariance property of ACO algorithms draws more attention. In this paper, we propose a novel two-stage updating pheromone for invariant ant colony optimization (TSIACO) algorithm. Compared with standard ACO algorithms, TSIACO algorithm uses solution order other than solution itself as independent variable for quality function. In addition, the pheromone trail is updated with two stages: in one stage, the first r iterative optimal solutions are employed to enhance search capability, and in another stage, only optimal solution is used to accelerate the speed of convergence. And besides, the pheromone value is limited to an interval. We prove that TSIACO not only has the property of linear transformational invariance but also has translational invariance. We also prove that the pheromone trail can limit to the interval (0, 1]. Computational results on the traveling salesman problem show the effectiveness of TSIACO 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.     

An ant colony optimization for single-machine tardiness scheduling with sequence-dependent setups

In many real-world production systems, it requires an explicit consideration of sequence-dependent setup times when scheduling jobs. As for the scheduling criterion, the weighted tardiness is always regarded as one of the most important criteria in practical systems. While the importance of the weighted tardiness problem with sequence-dependent setup times has been recognized, the problem has received little attention in the scheduling literature. In this paper, we present an ant colony optimization (ACO) algorithm for such a problem in a single-machine environment. The proposed ACO algorithm has several features, including introducing a new parameter for the initial pheromone trail and adjusting the timing of applying local search, among others. The proposed algorithm is experimented on the benchmark problem instances and shows its advantage over existing algorithms. As a further investigation, the algorithm is applied to the unweighted version of the problem. Experimental results show that it is very competitive with the existing best-performing algorithms.     

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.     

Nodal ant colony optimization for solving profit based unit commitment problem for GENCOs

This paper proposes a nodal ant colony optimization (NACO) technique to solve profit based unit commitment problem (PBUCP). Generation companies (GENCOs) in a competitive restructured power market, schedule their generators with an objective to maximize their own profit without any regard for system social benefit. Power and reserve prices become important factors in decision process. Ant colony optimization that mimics the behavior of ants foraging activities is suitably implemented to search the UCP search space. Here a search space consisting of optimal combination of binary nodes for unit ON/OFF status is represented for the movement of the ants to maintain good exploration and exploitation search capabilities. The proposed model help GENCOs to make decisions on the quantity of power and reserve that must be put up for sale in the markets and also to schedule generators in order to receive the maximum profit. The effectiveness of the proposed technique for PBUCP is validated on 10 and 36 generating unit systems available in the literature. NACO yields an increase of profit, greater than 1.5%, in comparison with the basic ACO, Muller method and hybrid LR-GA.     

基于蚁群算法优化SA的WMN路由设计与仿真

针对现有的无线网状网(WMN)路由协议在实际无线信道环境下性能降低的问题,提出了一种基于蚁群模拟退火(ASA)算法的WMN的路由算法.该算法吸收了蚁群算法的适应性、鲁棒性及本质上并行性的优点,并利用模拟退火(SA)算法调整路由的搜索方向,使蚁群算法的早熟现象和收敛速度得到了改善.对该算法进行仿真研究,结果表明:该算法在数据包的转发率、端到端延时数据丢失率和归一化路由开销等方面要比常规路由协议优秀很多,大大提高了系统的可靠性、鲁棒性,增强了通信网络的自适应能力.该算法用于WMN路由协议是可行的、有效的.