Search

Ant Colony Optimisation for classification has mostly been limited to rule based approaches where artificial ants walk on datasets in order to extract rules from the trends in the data, and hybrid approaches which attempt to boost the performance of existing classifiers through guided feature reductions or parameter optimisations. A recent notable example that is distinct from the mainstream approaches is PolyACO, which is a proof of concept polygon-based classifier that resorts to ant colony optimisation as a technique to create multi-edged polygons as class separators. Despite possessing some promise, PolyACO has some significant limitations, most notably, the fact of supporting classification of only two classes, including two features per class.This paper introduces PolyACO+, which is an extension of PolyACO in three significant ways: (1) PolyACO+ supports classifying multiple classes, (2) PolyACO+ supports polygons in multiple dimensions enabling classification with more than two features, and (3) PolyACO+ substantially reduces the training time compared to PolyACO by using the concept of multi-leveling. This paper empirically demonstrates that these updates improve the algorithm to such a degree that it becomes comparable to state-of-the-art techniques such as SVM, Neural Networks, and AntMiner+. nivå1

open access article Minimising the ongoing impact of train delays has benefits to both the users of the railway system and the railway stakeholders. However, the efficient rescheduling of trains after a perturbation is a complex real-world problem. The complexity is compounded by the fact that the problem may be both dynamic and multi-objective. The aim of this research is to investigate the ability of ant colony optimisation algorithms to solve a simulated dynamic multi-objective railway rescheduling problem and, in the process, to attempt to identify the features of the algorithms that enable them to cope with a multi-objective problem that is also dynamic. Results showed that, when the changes in the problem are large and frequent, retaining the archive of non-dominated solution between changes and updating the pheromones to reflect the new environment play an important role in enabling the algorithms to perform well on this dynamic multi-objective railway rescheduling problem.

This thesis was submitted for the award of Doctor of Philosophy and was awarded by Brunel University London In this thesis, a novel framework for dynamic congestion control has been proposed. The study is about the congestion control in broadband communication networks. Congestion results when demand temporarily exceeds capacity and leads to severe degradation of Quality of Service (QoS) and possibly loss of traffic. Since traffic is stochastic in nature, high demand may arise anywhere in a network and possibly causing congestion. There are different ways to mitigate the effects of congestion, by rerouting, by aggregation to take advantage of statistical multiplexing, and by discarding too demanding traffic, which is known as admission control. This thesis will try to accommodate as much traffic as possible, and study the effect of routing and aggregation on a rather general mix of traffic types. Software Defined Networking (SDN) and Network Function Virtualization (NFV) are concepts that allow for dynamic configuration of network resources by decoupling control from payload data and allocation of network functions to the most suitable physical node. This allows implementation of a centralised control that takes the state of the entire network into account and configures nodes dynamically to avoid congestion. Assumes that node controls can be expressed in commands supported by OpenFlow v1.3. Due to state dependencies in space and time, the network dynamics are very complex, and resort to a simulation approach. The load in the network depends on many factors, such as traffic characteristics and the traffic matrix, topology and node capacities. To be able to study the impact of control functions, some parts of the environment is fixed, such as the topology and the node capacities, and statistically average the traffic distribution in the network by randomly generated traffic matrices. The traffic consists of approximately equal intensity of smooth, bursty and long memory traffic. By designing an algorithm that route traffic and configure queue resources so that delay is minimised, this thesis chooses the delay to be the optimisation parameter because it is additive and real-time applications are delay sensitive. The optimisation being studied both with respect to total end-to-end delay and maximum end-to-end delay. The delay is used as link weights and paths are determined by Dijkstra’s algorithm. Furthermore, nodes are configured to serve the traffic optimally which in turn depends on the routing. The proposed algorithm is a fixed-point system of equations that iteratively evaluates routing – aggregation – delay until an equilibrium point is found. Three strategies are compared: static node configuration where each queue is allocated 1/3 of the node resources and no aggregation, aggregation of real-time (taken as smooth and bursty) traffic onto the same queue, and dynamic aggregation based on the entropy of the traffic streams and their aggregates. The results of the simulation study show good results, with gains of 10-40% in the QoS parameters. By simulation, the positive effects of the proposed routing and aggregation strategy and the usefulness of the algorithm. The proposed algorithm constitutes the central control logic, and the resulting control actions are realisable through the SDN/NFV architecture.

The real-life construction of examination timetabling problem is considered as a common problem that always encountered and experienced in educational institution whether in school, college, and university. This problem is usually experienced by the academic management department where they have trouble to handle complexity for assign examination into a suitable timeslot manually. In this paper, an algorithm approach of ant colony optimisation (ACO) is presented to find an effective solution for dealing with Universiti Sultan Zainal Abidin (UniSZA) examination timetabling problems. A combination of heuristic with ACO algorithm contributes the development solution in order to simplify and optimize the pheromone occurrence of matrix updates which include the constraints problem. The implementation of real dataset instances from academic management is applied to the approach for generating the result of examination timetable. The result and performance that obtained will be used for further use to evaluate the quality and observe the solution whether our examination timetabling system is reliable and efficient than the manual management that can deal the constraints problem.

International audience; The continuous evolution of manufacturing environments leads to a more efficient production process that controls an increasing number of parameters. Production resources usually represent an important constraint in a manufacturing activity, specially talking about the management of human resources and their skills. In order to study the impact of this subject, this paper considers an open shop scheduling problem based on a mechanical production workshop to minimise the total flow time including a multi-skill resource constraint. Then, we count with a number of workers that have a versatility to carry out different tasks, and according to their assignment a schedule is generated. In that way, we have formulated the problem as a linear as and a non-linear mathematical model which applies the classic scheduling constraints, adding some different resources constraints related to personnel staff competences and their availability to execute one task. In addition, we introduce a genetic algorithm and an ant colony optimisation (ACO) method to solve large size problems. Finally, the best method (ACO) has been used to solve a real industrial case that is presented at the end.

The idea of non-hierarchical production networks consisting of autonomous enterprises has been present in scientific community for more than 20 years. Although some global corporations are using their own production networks across continents, they are not similar to the original idea of non-hierarchical production networks in many aspects. It seems that this idea waited for production systems to acquire proper information and communications technology (ICT) or new industrial platforms, like Industry 4.0. The result is a new type of production network called Cyber-Physical Production Network (CPPN). The CPPN is, from ICT point of view, ready to act as non-hierarchical production networks consisting of autonomous production systems with many automated processes. One of the most important processes of the CPPN is a selection of optimal partners (enterprises) to be part of a new virtual enterprise, created inside production network. An optimisation problem emerges in this process, and it is called Partner Selection Problem (PSP). It is non-polynomial-hard combinatorial problem. Since metaheuristic algorithms are well-proven in solving that kind of problem, a specially designed metaheuristic algorithm derived from ant colony optimisation and named the HUMANT (HUManoid ANT) algorithm is used in this paper. It is multi-objective optimisation algorithm that successfully solves different instances of PSP with two, three, four or more objectives.

Differential evolution requires a prior setting of its parameters. Appropriate values are not always easy to determine, even more since they may change during the optimisation process. This is where parameter control comes in. Accordingly, a scheme inspired by ant colony optimisation for controlling the crossover-rate and mutation factor is proposed. Conceptually, artificial ants guided by a pheromone model select parameter value pairs for each individual. The pheromone model is steadily updated in order to reflect the current optimisation state. Promising results were achieved in the comprehensive experimental analysis. Nonetheless, much room for potential improvements is available.

In this article we propose a formalisation of the concept of exploration performed by metaheuristics. In particular, we define and test a method for studying this aspect regardless of the specific approach implemented. Understanding the behaviour of metaheuristics is important for being able to boost their results. Measuring the exploration performed may help increase this understanding. We propose an experimental analysis to show how the measure of exploration defined may be used to this aim. We quantify the different level of exploration implied by different parameter settings in an ant colony optimisation and in a genetic algorithm for the travelling salesman problem. The results suggest that it may be possible to establish a relation between exploration and performance of the algorithm.

Interest in biologically-inspired optimization techniques has increased due to its accurate results, fast performance and ease of use. In this paper, an ant colony optimization (ACO) technique is deployed and used for modelling a twin rotor system. The system is perceived as a challenging engineering problem due to its strong cross coupling between horizontal and vertical axes and inaccessibility of some of its states and outputs for measurements. Accurate modelling of the system is thus required so as to achieve satisfactory control objectives. It is demonstrated that ACO can be effectively used for modelling the system with highly accurate results. The accuracy of the modelling results is demonstrated through validation tests including training and test validation and correlation tests.

The focus of this paper is an ant colony optimisation heuristic for the graph colouring problem. We start by showing how a series of improvements enhance the performance of an existing ant colony approach to the problem and then go on to demonstrate that a further strengthening of the construction phase, combined with a tabu search improvement phase, raise the performance to the point where it is able to compete with some of the best-known approaches on a series of benchmark problems.

In Location-Based Services (LBSs), the service is provided based on the users' locations through location deter- mination and mobility anticipation. Most of the current location prediction research focuses on generalised location models, where the geographic extent is divided into regular shape cells. One such technique is the Mobility Prediction based on an Ant System (MPAS), which depends on the earlier Ant Colony Optimisation (ACO) that suffers from problems such as search stagnation and pheromone update. In this paper, a New Routing Area Displacement Prediction (NRADP) is introduced, which works on the routing-area level instead of the cell level. Experimental results show that the NRADP offers improved effectiveness, higher prediction rate, and a reduced search stagnation ratio in comparison with the MPAS. Index Terms—Ant Colony Optimisation, LBSs, Mobility Pre- diction, Cellular Network, UMTS, Routing Area.

The file attached to this record is the author's final peer reviewed version. The Publisher's final version can be found by following the DOI link. Efficient rescheduling after a perturbation is an important concern of the railway industry. Extreme delays can result in large fines for the train company as well as dissatisfied customers. The problem is exacerbated by the fact that it is a dynamic one; more timetabled trains may be arriving as the perturbed trains are waiting to be rescheduled. The new trains may have different priorities to the existing trains and thus the rescheduling problem is a dynamic one that changes over time. The aim of this research is to apply a population-based ant colony optimisation algorithm to address this dynamic railway junction rescheduling problem using a simulator modelled on a real-world junction in the UK railway network. The results are promising: the algorithm performs well, particularly when the dynamic changes are of a high magnitude and frequency.

In this paper, we consider a sequence-dependent disassembly line balancing problem (SDDLBP) with multiple objectives that requires the assignment of disassembly tasks to a set of ordered disassembly workstations while satisfying the disassembly precedence constraints and considering sequence-dependent part removal time increments. The four objectives to be achieved are as follows: (1) minimise the number of disassembly workstations, (2) minimise the total idle time by evenly distributing it among workstations, (3) maximise the priority of removing hazardous components as early as possible in the disassembly sequence and (4) maximise the priority of removing high demand components before low demand components. A new approach based on the tabu search (TS) algorithm is proposed to solve the SDDLBP. To the best of our knowledge, this paper investigates the first application of TS algorithm to solve the SDDLBP. Two case scenarios are considered and comparisons with ant colony optimisation and river formation dynamics approaches are provided to demonstrate the effectiveness of the algorithm. © 2013 Taylor & Francis.

In this thesis a solution for the problem of identifying the structure of news published by online newspapers is presented. This problem requires new approaches and algorithms that are capable of dealing with the massive number of online publications in existence (and that will grow in the future). The fact that news documents present a high degree of interconnection makes this an interesting and hard problem to solve. The identification of the structure of the news is accomplished both by descriptive methods that expose the dimensionality of the relations between different news, and by clustering the news into topic groups. To achieve this analysis this integrated whole was studied using different perspectives and approaches. In the identification of news clusters and structure, and after a preparatory data collection phase, where several online newspapers from different parts of the globe were collected, two newspapers were chosen in particular: the Portuguese daily newspaper Público and the British newspaper The Guardian. In the first case, it was shown how information theory (namely variation of information) combined with adaptive networks was able to identify topic clusters in the news published by the Portuguese online newspaper Público. In the second case, the structure of news published by the British newspaper The Guardian is revealed through the construction of time series of news clustered by a kmeans process. After this approach an unsupervised algorithm, that filters out irrelevant news published online by taking into consideration the connectivity of the news labels entered by the journalists, was developed. This novel hybrid technique is based on Qanalysis for the construction of the filtered network followed by a clustering technique to identify the topical clusters. Presently this work uses a modularity optimisation clustering technique but this step is general enough that other hybrid approaches can be used without losing generality. A novel second order swarm intelligence algorithm based on Ant Colony Systems was developed for the travelling salesman problem that is consistently better than the traditional benchmarks. This algorithm is used to construct Hamiltonian paths over the news published using the eccentricity of the different documents as a measure of distance. This approach allows for an easy navigation between published stories that is dependent on the connectivity of the underlying structure. The results presented in this work show the importance of taking topic detection in large corpora as a multitude of relations and connectivities that are not in a static state. They also influence the way of looking at multi-dimensional ensembles, by showing that the inclusion of the high dimension connectivities gives better results to solving a particular problem as was the case in the clustering problem of the news published online. Neste trabalho resolvemos o problema da identificação da estrutura das notícias publicadas em linha por jornais e agências noticiosas. Este problema requer novas abordagens e algoritmos que sejam capazes de lidar com o número crescente de publicações em linha (e que se espera continuam a crescer no futuro). Este facto, juntamente com o elevado grau de interconexão que as notícias apresentam tornam este problema num problema interessante e de difícil resolução. A identificação da estrutura do sistema de notícias foi conseguido quer através da utilização de métodos descritivos que expõem a dimensão das relações existentes entre as diferentes notícias, quer através de algoritmos de agrupamento das mesmas em tópicos. Para atingir este objetivo foi necessário proceder a ao estudo deste sistema complexo sob diferentes perspectivas e abordagens. Após uma fase preparatória do corpo de dados, onde foram recolhidos diversos jornais publicados online optou-se por dois jornais em particular: O Público e o The Guardian. A escolha de jornais em línguas diferentes deve-se à vontade de encontrar estratégias de análise que sejam independentes do conhecimento prévio que se tem sobre estes sistemas. Numa primeira análise é empregada uma abordagem baseada em redes adaptativas e teoria de informação (nomeadamente variação de informação) para identificar tópicos noticiosos que são publicados no jornal português Público. Numa segunda abordagem analisamos a estrutura das notícias publicadas pelo jornal Britânico The Guardian através da construção de séries temporais de notícias. Estas foram seguidamente agrupadas através de um processo de k-means. Para além disso desenvolveuse um algoritmo que permite filtrar de forma não supervisionada notícias irrelevantes que apresentam baixa conectividade às restantes notícias através da utilização de Q-analysis seguida de um processo de clustering. Presentemente este método utiliza otimização de modularidade, mas a técnica é suficientemente geral para que outras abordagens híbridas possam ser utilizadas sem perda de generalidade do método. Desenvolveu-se ainda um novo algoritmo baseado em sistemas de colónias de formigas para solução do problema do caixeiro viajante que consistentemente apresenta resultados melhores que os tradicionais bancos de testes. Este algoritmo foi aplicado na construção de caminhos Hamiltonianos das notícias publicadas utilizando a excentricidade obtida a partir da conectividade do sistema estudado como medida da distância entre notícias. Esta abordagem permitiu construir um sistema de navegação entre as notícias publicadas que é dependente da conectividade observada na estrutura de notícias encontrada. Os resultados apresentados neste trabalho mostram a importância de analisar sistemas complexos na sua multitude de relações e conectividades que não são estáticas e que influenciam a forma como tradicionalmente se olha para sistema multi-dimensionais. Mostra-se que a inclusão desta dimensões extra produzem melhores resultados na resolução do problema de identificar a estrutura subjacente a este problema da publicação de notícias em linha.

Assembly lines are one of the most frequently used flow oriented production systems in industry. Although only a few researchers have studied them, two-sided assembly lines are usually utilised to produce high-volume large-sized products such as trucks and buses. In this study, more than one two-sided assembly line constructed in parallel are balanced simultaneously using a newly developed ant colony optimisation algorithm. To the best knowledge of the authors, the proposed method is the first attempt to solve the parallel two-sided assembly line balancing problem using an ant colony optimisation based algorithm. The proposed approach is also illustrated with examples from the literature to show the procedures of the algorithm.

Küçükkoç, İbrahim (Balikesir Author), Recently, there is an increasing interest in applications of meta-heuristic approaches in solving various engineering problems. Meta-heuristics help both academics and practitioners to get not only feasible but also near optimal solutions where obtaining a solution for the relevant problem is not possible in a reasonable time using traditional optimisation techniques. Ant colony optimisation algorithm is inspired from the collective behaviour of ants and one of the most efficient meta-heuristics in solving combinatorial optimisation problems. One of the main application areas of ant colony optimisation algorithm is assembly line balancing problem. In this paper, we first give the running principle of ant colony optimisation algorithm and then review the applications of ant colony optimisation based algorithms on assembly line balancing problems in the literature. Strengths and weaknesses of proposed algorithms to solve various problem types in the literature have also been discussed in this research. The main aim is to lead new researches in this domain and spread the application areas of ant colony optimisation techniques in various aspects of line balancing problems. Existing researches in the literature indicate that ant colony optimisation methodology has a promising solution performance to solve line balancing problems especially when integrated with other heuristic and/or meta-heuristic methodologies.

The importance of achieving optimality or near optimality in supply routing is on the rise as globalization leads to scenarios in which multiple, heterogeneous and highly spatially distributed demands have to be satisfied under stringent constraints. However, there is no consensus concerning what constitutes an all-encompassing objective function for the supply planner, who faces what can easily constitute a problem requiring Non-deterministic Polynomial time for determining the solution even in its simplest formulations. The work presented in this article proposes a mathematically grounded approach that uses Ant Colony Optimisation to yield near optimal results across a large set of problem formulations and objective functions. The latter are designed to capture real-world goals such as cost reduction, optimal transportation management, flexibility and minimal lead-time. This study adds a new dimension to topics traditionally encountered in the literature, namely that of the cultural differences between partners engaged in international trade relations. Furthermore, the impact of the lag between determining and implementing the quasioptimal strategy is forecast for an array of objective functions tailored to represent approaches encountered in international companies dealing with supply challenges in fields such as Information Technology. Finally, the framework thus established is employed to analyse the indirect relationship between Asian “white box” suppliers and a Romanian firm operating in Mobile Integrated Device space.

In this paper we focus on the road network design problem in regional contexts. In this case a planner may have financial resources to invest for improving performance on existing roads. Against the background of an extensive literature of optimisation models and algorithms to solve this problem, the innovative aspects of this paper are as follows: the optimisation model refers to the daily operation of the network; the objective function also considers the environmental costs; the proposed meta-heuristic solution algorithm has never been used to solve this problem; and the assignment algorithm is based on Ant Colony Optimisation in order to reduce computing times. The model and algorithm were tested on a real-scale problem, showing their applicability to real dimension networks.

In this paper we focus on the road network design problem in regional contexts. In this case a planner may have financial resources to invest for improving performance on existing roads. Against the background of an extensive literature of optimisation models and algorithms to solve this problem, the innovative aspects of this paper are as follows: the optimisation model refers to the daily operation of the network; the objective function also considers the environmental costs; the proposed meta-heuristic solution algorithm has never been used to solve this problem; and the assignment algorithm is based on Ant Colony Optimisation in order to reduce computing times. The model and algorithm were tested on a real-scale problem, showing their applicability to real dimension networks.

In this work, the flowshop scheduling problem is considered with the objective of minimising the completion-time variance (CTV) of jobs, and an Ant Colony Optimisation (ACO) algorithm is presented. Two implementations of the Modified Ant Colony Optimisation algorithm (MACO-I and MACO-II) are proposed to solve the permutation flowshop scheduling problem. The proposed ant-colony-algorithm implementations have been tested on 90 benchmark flowshop scheduling problems. The solutions yielded by the proposed MACO implementations are compared with various algorithms and with the best CTV of jobs reported in the literature. The proposed MACO implementations are found to perform very well in minimising the chosen performance measure. � 2012 Copyright Taylor and Francis Group, LLC.

International audience; We present a model for the travelling salesman problem (TSP) solved using the ant colony optimisation (ACO), a bio-inspired mechanism that helps speed up the search for a solution and that can be applied to many other problems. The natural complexity of the TSP combined with the self-organisation and emergent behaviours that result from the application of the ACO make model-checking this system a hard task. We discuss our approach for modelling the ACO in a well-known probabilistic model checker and describe results of verifications carried out using our model and a couple of probabilistic temporal properties. These results demonstrate not only the effectiveness of the ACO applied to the TSP, but also that our modelling approach for the ACO produces the expected behaviour. It also indicates that the same modelling could be used in other scenarios.

This paper will propose an ant colony optimization (ACO)-based algorithm that can be used to simulate mass-transit networks; this algorithm imitates the behavior of public transport users. In particular, the authors show that the proposed algorithm, which is an extension of that proposed by D’Acierno et al. (A stochastic traffic assignment algorithm based on ACO, Lecture Notes in Computer Science 4150, pp. 25–36, 2006), allows mass-transit systems to be simulated in less time but with the same accuracy compared with traditional assignment algorithms. Finally, the authors state theoretically the perfect equivalence in terms of hyperpath choice behavior between artificial ants (simulated with the proposed algorithm) and mass-transit users (simulated with traditional assignment algorithms).

This thesis was submitted for the degree of Doctor of Philosophy and was awarded by Brunel University Traditional clustering algorithms have different criteria and biases, and there is no single algorithm that can be the best solution for a wide range of data sets. This problem often presents a significant obstacle to analysts in revealing meaningful information buried among the huge amount of data. Ensemble Clustering has been proposed as a way to avoid the biases and improve the accuracy of clustering. The difficulty in developing Ensemble Clustering methods is to combine external information (provided by input clusterings) with internal information (i.e. characteristics of given data) effectively to improve the accuracy of clustering. The work presented in this thesis focuses on enhancing the clustering accuracy of Ensemble Clustering by employing heuristic optimisation techniques to achieve a robust combination of relevant information during the consensus clustering stage. Two novel heuristic optimisation-based Ensemble Clustering methods, Multi-Optimisation Consensus Clustering (MOCC) and K-Ants Consensus Clustering (KACC), are developed and introduced in this thesis. These methods utilise two heuristic optimisation algorithms (Simulated Annealing and Ant Colony Optimisation) for their Ensemble Clustering frameworks, and have been proved to outperform other methods in the area. The extensive experimental results, together with a detailed analysis, will be presented in this thesis.

In this paper we propose an Ant Colony Optimisation (ACO) algorithm for optimising the signal settings on urban networks following a local approach. This problem, also known as LOSS (Local Optimisation of Signal Settings), has been widely studied in the literature and can be formulated as an asymmetric assignment problem (Cascetta, E., Gallo, M. and B. Montella, 2006. Models and algorithms for the optimization of signal setting on urban networks with stochastic assignment models. Ann. Oper. Res., 144, 301-328). The problem consists in optimising the signal settings of each intersection of an urban network as a function only of traffic flows at the accesses to the same intersection, taking account of the effects of signal settings on costs and on user route choices. The proposed ACO algorithm is based on two kinds of behaviour of artificial ants which allow the LOSS problem to be solved: traditional behaviour based on the response to pheromones for simulating user route choice, and innovative behaviour based on the pressure of an ant stream for solving the signal setting definition problem. Our results on a real-scale network show that the proposed approach allows the solution to be obtained in less time but with the same accuracy as in traditional MSA approaches.

There are two common types of operational research techniques, optimisation and metaheuristic methods. The latter may be defined as a sequential process that intelligently performs the exploration and exploitation adopted by natural intelligence and strong inspiration to form several iterative searches. An aim is to effectively determine near optimal solutions in a solution space. In this work, a type of metaheuristics called Ant Colonies Optimisation, ACO, inspired by a foraging behaviour of ants was adapted to find optimal solutions of eight non-linear continuous mathematical models. Under a consideration of a solution space in a specified region on each model, sub-solutions may contain global or multiple local optimum. Moreover, the algorithm has several common parameters; number of ants, moves, and iterations, which act as the algorithm-s driver. A series of computational experiments for initialising parameters were conducted through methods of Rigid Simplex, RS, and Modified Simplex, MSM. Experimental results were analysed in terms of the best so far solutions, mean and standard deviation. Finally, they stated a recommendation of proper level settings of ACO parameters for all eight functions. These parameter settings can be applied as a guideline for future uses of ACO. This is to promote an ease of use of ACO in real industrial processes. It was found that the results obtained from MSM were pretty similar to those gained from RS. However, if these results with noise standard deviations of 1 and 3 are compared, MSM will reach optimal solutions more efficiently than RS, in terms of speed of convergence., {"references":["C. Blum and A. Roli, \"Metaheuristics in Combinatorial Optimisation:\nOverview and Conceptual Comparison\". ACM Computing surveys,\nvol. 35, no. 3, pp. 268-308, 2003.","S. Kirkpatrick, C.D. Gelatt and M.P. Vecchi, \"Optimisation by\nSimulated Annealing\". Science, vol. 220, no. 4598, pp. 671-679,\n1983.","F. Glover, \"Tabu Search - part i\". ORSA Journal on Computing, vol.\n1, no. 3, pp. 190-206, 1986.","M. Dorigo and T. Stutzle, Ant Colony Ooptimisation. Massachusetts,\nBradford Book, 2004.","E.A. Hart and J. Timmis, \"Application Areas of AIS: The Past, the\nPresent and the Future\". Applied Soft Computing, vol. 8, no. 1, pp.\n191-201, 2008.","D.E. Goldberg, Genetic Algorithms in Search, Optimisation and\nmachine learning. Massachusetts, Addison-Wesley, 1989.","P. Merz and B. Freisleben, 1999. \"A Comparison of Memetic\nAlgorithms, Tabu Search, and Ant Colonies for the Quadratic\nAssignment Problem\", presented at the 1999 Congress on\nEvolutionary Computation.","S. Haykin, Neural Networks: A Comprehensive Foundation (2nd ed).\nNJ: Prentice Hall, 1999.","J. Kennedy and R.C. Eberhart, Swarm Intelligence. San Francisco,\nCA: Morgan Kaufmann Publishers, 2001.\n[10] M. Eusuff, K. Lansey and F. Pasha, \"Shuffled Frog-Leaping\nAlgorithm: A Memetic Metaheuristic for Discrete Optimisation\".\nEngineering Optimisation, vol. 38, no. 2, pp. 129-154, 2006.\n[11] H. Aytug, M. Knouja and F.E. Vergara, \"Use of Genetic Algorithms\nto Solve Production and Operations Management Problems: A\nReview\". International Journal of Production Research, vol.41, no. 17,\npp. 3955-4009, 2003.\n[12] S.S. Chaudhry and W. Luo, \"Application of Genetic Algorithms in\nProduction and Operations Management: A Review\". International\nJournal of Production Research, vol.43, no. 19, pp. 4083-4101, 2005.\n[13] D. Dasgupta, Artificial Immune Systems and their Applications.\nSpringer-Verlag, 1998.\n[14] M. Dorigo and C. Blum, \"Ant Colony Optimisation Theory: A\nsurvey\". Theoretical Computer Science, vol. 344, no.2-3, pp. 243-278,\n2005.\n[15] P. Ittipong, P. Luangpaiboon and P. Pongcharoen, 2008. \"Solving\nNon-Linear Continuous Mathematical Models Using Shuffled Frog\nLeaping and Memetic Algorithm\". Presented at the 2008 Operations\nResearch Network Conference, Bangkok, Thailand.\n[16] W.G.R. Spendley, G.R. Hext, and F.R. Himsworth, \"Sequential\nApplication of Simplex Designs in Optimisation and Evolutionary\nOperation\". Technometrics, vol. 4, no. 4, pp. 441-461, 1962.\n[17] J.A. Nelder and R. Mead, \"A Simplex Method for Function\nOptimisation\", Computer Journal, vol. 7, pp. 308-313, 1965.\n[18] J.A.M. Pulgarin, A.A. Molina and M.T. Alanon Pardo, \"The Use of\nModified Simplex Method to Optimise the Room Temperature\nPhosphorescence Variables in the Determination of Antihypertensive\nDrug\", Talanta, vol. 57, pp. 795-805, 2002.\n[19] F.H. Walters, L.R. Parker, S.L. Jr.,Morgan and S.M. Deming,.\nSequential Simplex Optimisation. CRC Press, Inc., Boca Raton, 1991."]}

In analyses of real dimension networks, it is important that simulation models allow solutions to be obtained swiftly such that it is possible to explore a large number of alternative projects or simulate beforehand consequences of a strategy in terms of future (minutes or hours) network conditions. Hence, in this paper we verify the possibility of developing a meta-heuristic algorithm that allows user flows on the transit system to be calculated more quickly than by using traditional algorithms. In particular, we steered our research into ant-based algorithms. Indeed, these algorithms based on the food source search of ant colonies, have in many cases shown their efficiency in terms of calculation time (an extended overview of ant-based algorithms can be found in Dorigo & Stützle, 2004). In the case of transportation systems, algorithms based on the Ant Colony Optimisation (ACO) approach were proposed by Poorzahedy & Abulghasemi (2005) in the case of network design, by de Oliveira & Bazzan (2006) for traffic control, and by D’Acierno et al. (2006) and Mussone et al. (2007) for traffic assignment. However, almost all ACO traffic assignment algorithms proposed in the literature are based on preventive choice user behaviour which is typical of models for simulating road systems. Instead, in the case of transit systems in an urban context, it is necessary to simulate preventive-adaptive choice behaviours because users are not able to set their itineraries preventively. Indeed, since the physical path depends on the arrival of vehicles at boarding stops, users choose the set of attractive lines beforehand (preventive stage) and the line used according to arrival events (adaptive stage). In this paper we propose an ACO algorithm that allows us to simulate preventive-adaptive user behaviour in the case of transit systems. In particular, we show that the proposed algorithm has an MSA framework and state the perfect equivalence in terms of (hyper-)path choice behaviours between artificial ants (with the proposed approach) and mass transit users (simulated with traditional algorithms). Finally, we show numerically that, in the case of real dimension networks, the proposed algorithm can be adopted to solve equilibrium assignment problems in less time but with the same accuracy compared with traditional algorithms.

Nella presente memoria è proposto un algoritmo di assegnazione basato sull'Ant Colony Optimisation che consente di risolvere il problema di assegnazione alle reti di trasporto privato in minor tempo ma con la stessa precisione degli algoritmi MSA tradizionali. In particolare, dopo aver mostrato la sua equivalenza ad un algoritmo di tipo MSA, gli autori dimostrano la convergenza teorica dell'algoritmo.

Centre for Intelligent Systems and their Applications This research identifies and investigates major issues in inducing accurate and comprehensible fuzzy rules from datasets. A review of the current literature on fuzzy rulebase induction uncovers two significant issues: A. There is a tradeoff between inducing accurate fuzzy rules and inducing comprehensible fuzzy rules; and, B. A common strategy for the induction of fuzzy rulebases, that of iterative rule learning where the rules are generated one by one and independently of each other, may not be an optimal one. FRANTIC, a system that provides a framework for exploring the claims above is developed. At the core lies a mechanism for creating individual fuzzy rules. This is based on a significantly modified social insect-inspired heuristic for combinatorial optimisation -- Ant Colony Optimisation. The rule discovery mechanism is utilised in two very different strategies for the induction of a complete fuzzy rulebase: 1. The first follows the common iterative rule learning approach for the induction of crisp and fuzzy rules; 2. The second has been designed during this research explicitly for the induction of a fuzzy rulebase, and generates all rules in parallel. Both strategies have been tested on a number of classification problems, including medical diagnosis and industrial plant fault detection, and compared against other crisp or fuzzy induction algorithms that use more well-established approaches. The results challenge statement A above, by presenting evidence to show that one criterion need not be met at the expense of the other. This research also uncovers the cost that is paid -- that of computational expenditure -- and makes concrete suggestions on how this may be resolved. With regards to statement B, until now little or no evidence has been put forward to support or disprove the claim. The results of this research indicate that definite advantages are offered by the second simultaneous strategy, that are not offered by the iterative one. These benefits include improved accuracy over a wide range of values for several key system parameters. However, both approaches also fare well when compared to other learning algorithms. This latter fact is due to the rule discovery mechanism itself -- the adapted Ant Colony Optimisation algorithm -- which affords several additional advantages. These include a simple mechanism within the rule construction process that enables it to cope with datasets that have an imbalanced distribution between the classes, and another for controlling the amount of fit to the training data. In addition, several system parameters have been designed to be semi-autonomous so as to avoid unnecessary user intervention, and in future work the social insect metaphor may be exploited and extended further to enable it to deal with industrial-strength data mining issues involving large volumes of data, and distributed and/or heterogeneous databases.

The task assignment problem commonly appears in distributed computing environments. It asks an assignment of tasks to processors is found such that it satisfies the imposed constraints and that the total execution and communication cost of the tasks is minimal. This paper presents an algorithm based on ant colony optimisation that incorporates ideas from the clonal selection algorithm. Namely, the ant colony optimisation algorithm includes the cloning of the iteration-best ant and mutation of its clones' solutions ; the goal being a better exploitation of promising parts of the search space. Besides that, the solution construction procedure is modified to take the memory constraints into account and the pheromone update mechanism is modified to enable the best clone to deposit pheromone. The experimental analysis, conducted on a large number of problem instances, showed that the proposed algorithm performs better compared to the MAX-MIN ant system, a differential evolution and a particle swarm optimisation algorithm.

An Ant Colony Optimisation technique has been implemented in order to help students visit pedagogical items proposed by Paraschool (a French leading e-learning company). The large number of students (more than 250 000) suggested to students as artificial ants, to leave stigmergic information on the web-site graph. This difference brought many changes in the original ACO process, but also a large improvement in the students' guiding system. The concept of Man-Hill has therefore been introduced.At this stage, it becomes necessary to rate the pedagogical items to refine the model and propose the students with items corresponding to their level. The Elo rating (used in Chess competitions) is used for his purpose. As a side effect, it revealed to be also a powerful audit system that can track semantic problem in exercises.; Ce travail de recherche se place dans le cadre de l'adaptation du paradigme de l'Optimisation par Colonie de Fourmis (OCF) à l'environnement du logiciel d'e-learning de la société Paraschool (leader français du soutien scolaire sur internet) pour le rendre intelligent et réactif à l'utilisateur. Le grand nombre d'utilisateurs a permis d'associer chaque élève à une fourmi, ce qui signifie que le mécanisme d'optimisation n'est plus basé sur une colonie de fourmis artificielles, mais sur une « colonie d'élèves » que nous appellerons Hommilière.Dans le but d'adapter la force des exercices aux élèves, la notation Elo des échecs a été appliquée afin d'évaluer le niveau des élèves et des items. En plus de cela, le système Elo s'avère être un très bon système d'audit, capable, entre autres, de mettre en évidence les erreurs sémantiques des exercices.

In this paper we propose a Stochastic User Equilibrium (SUE) algorithm that can be adopted as a simulation model when cost functions depend on the number of vehicles using network elements. Indeed, analyses of real dimension networks need simulation algorithms that allow network conditions and performances to be rapidly determined. Hence, we developed an MSA (Method of Successive Averages) algorithm based on the Ant Colony Optimisation paradigm that allows transportation systems to be simulated in less time but with the same accuracy compared with traditional MSA algorithms.

This paper presents an Ant Colony Optimisation (ACO) model for the Multiple Knapsack Problem (MKP). The ACO algorithms, as well as other evolutionary metaphors, are being applied successfully to diverse heavily constrained problems: Travelling Salesman Problem, Quadratic Assignment Problem and Bin Packing Problem. An Ant System, the first ACO algorithm that we presented in this paper, is also considered a class of multiagent distributed algorithm for combinatorial optimisation. The principle of an ACO Algorithm is adapted to the MKP. We present some results regardin its perfomance against known optimun for different instances of MKP. The obtained results show the potential power of this particular evolutionary approach for optimisation problems., Facultad de Informática

In this paper, the problem of scheduling in the permutation flowshop scheduling problem is considered with the objective of minimising the completion-time variance of jobs (CTV). Two particle swarm optimisation algorithms (PSOAs) are proposed and analysed. The first PSOA is inspired from the solution construction procedures that are used in ant colony optimisation algorithms. The second algorithm is a newly developed one. The proposed algorithms are applied to a set of benchmark flowshop scheduling problems, and performances of the algorithms are evaluated by comparing the obtained results with the results published in the literature. The performance analysis demonstrates the effectiveness of the proposed algorithms in solving the permutation flowshop sequencing problem with the CTV objective. � 2011 Inderscience Enterprises Ltd.

In this, an attempt has been made to analyse blood vessels in human retinal digital images using Ant Colony Optimisation (ACO) based edge detection algorithm and was then correlated with Otsu and Matched filter methods. Results show that the ACO method provides high visual quality output with better detection of blood vessels. It provides better delineation, distinctly differentiates central veins, extracts small blood vessels and detects abnormalities in the image. The ratio of vessel-to-vessel free area using ACO method is distinctly different for normal and abnormal images (p < 0.005). It appears that this study is useful for mass screening and avoids complications at later stages of diseases. Copyright � 2011 Inderscience Enterprises Ltd.

There are 11,619 community pharmacies in England which dispense over 1 billion prescriptions each year, providing essential primary care to NHS (National Health Service) patients. These pharmacies are facing pressure from a number of sources including funding cuts and high demands on services, while trying to deliver the highest standards of care. This paper presents an optimisation of a Coloured Petri Net (CPN) community pharmacy simulation model using an Ant Colony Optimisation (ACO) method. The CPN method was proposed by Naybour et al . Quantitative data from UK community pharmacies was collected by the authors and incorporated into the CPN simulation model. The optimisation is made up of a choice of how many staff to employ, which prescription checking strategy to use, and which staff work pattern to implement. This method aims to provide decision makers with a set of optimal pharmacy configurations at different cost levels. This can help to support pharmacy safety, efficiency, and improve decision making processes. It has been demonstrated how reliability modelling techniques traditionally used in safety-critical industries, can be used to carry out safety and efficiency analyses of healthcare systems, such as dispensing processes in community pharmacies, illustrated in this contribution.

In this paper we propose a Stochastic User Equilibrium (SUE) algorithm that can be adopted as a model, known as a simulation model, that imitates the behaviour of transportation systems. Indeed, analyses of real dimension networks need simulation algorithms that allow network conditions and performances to be rapidly determined. Hence, we developed an MSA (Method of Successive Averages) algorithm based on the Ant Colony Optimisation paradigm that allows transportation systems to be simulated in less time but with the same accuracy as traditional MSA algorithms. Finally, by means of Blum’s theorem, we stated theoretically the convergence of the proposed ACO-based algorithm.

Date of Conference: November 2007 In this paper, we give an overview of the four tasks submitted to TRECVID 2007 by COST292. In shot boundary (SB) detection task, four SB detectors have been developed and the results are merged using two merging algorithms. The framework developed for the high-level feature extraction task comprises four systems. The first system transforms a set of low-level descriptors into the semantic space using Latent Semantic Analysis and utilises neural networks for feature detection. The second system uses a Bayesian classifier trained with a "bag of subregions". The third system uses a multi-modal classifier based on SVMs and several descriptors. The fourth system uses two image classifiers based on ant colony optimisation and particle swarm optimisation respectively. The system submitted to the search task is an interactive retrieval application combining retrieval functionalities in various modalities with a user interface supporting automatic and interactive search over all queries submitted. Finally, the rushes task submission is based on a video summarisation and browsing system comprising two different interest curve algorithms and three features.

This paper generalises and strengthens the investigation of capturing intangible data for the benefit of organisations encouraging learning environments and self-organisation practices. It suggests current technological and algorithmic analysis may aid an organisation’s quest for sustained competitive advantage through the identification of previously unobservable data including cultural nuances. However, the implementation of such an approach presents challenges of which we summarise in our conclusion.