To see the other types of publications on this topic, follow the link: Ant colony sytem algorithm.
Dissertations / Theses on the topic 'Ant colony sytem algorithm'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Ant colony sytem algorithm.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Sabri, Dalia. "Performance analysis for network coding using ant colony routing." Thesis, Brunel University, 2011. http://bura.brunel.ac.uk/handle/2438/6435.
Full textAbstract:
The aim of this thesis is to conduct performance investigation of a combined system of Network Coding (NC) technique with Ant-Colony (ACO) routing protocol. This research analyses the impact of several workload characteristics, on system performance. Network coding is a significant key development of information transmission and processing. Network coding enhances the performance of multicast by employing encoding operations at intermediate nodes. Two steps should realize while using network coding in multicast communication: determining appropriate transmission paths from source to multi-receivers and using the suitable coding scheme. Intermediate nodes would combine several packets and relay them as a single packet. Although network coding can make a network achieve the maximum multicast rate, it always brings additional overheads. It is necessary to minimize unneeded overhead by using an optimization technique. On other hand, Ant Colony Optimization can be transformed into useful technique that seeks imitate the ant’s behaviour in finding the shortest path to its destination using quantities of pheromone that is left by former ants as guidance, so by using the same concept of the communication network environment, shorter paths can be formulated. The simulation results show that the resultant system considerably improves the performance of the network, by combining Ant Colony Optimization with network coding. 25% improvement in the bandwidth consumption can be achieved in comparison with conventional routing protocols. Additionally simulation results indicate that the proposed algorithm can decrease the computation time of system by a factor of 20%.
2
Bremang, Appah. "Using ant colonies for solve the multiprocessor task graph scheduling." Thesis, Högskolan Dalarna, Datateknik, 2006. http://urn.kb.se/resolve?urn=urn:nbn:se:du-2381.
Full textAbstract:
The problem of scheduling a parallel program presented by a weighted directed acyclic graph (DAG) to the set of homogeneous processors for minimizing the completion time of the program has been extensively studied as academic optimization problem which occurs in optimizing the execution time of parallel algorithm with parallel computer.In this paper, we propose an application of the Ant Colony Optimization (ACO) to a multiprocessor scheduling problem (MPSP). In the MPSP, no preemption is allowed and each operation demands a setup time on the machines. The problem seeks to compose a schedule that minimizes the total completion time.We therefore rely on heuristics to find solutions since solution methods are not feasible for most problems as such. This novel heuristic searching approach to the multiprocessor based on the ACO algorithm a collection of agents cooperate to effectively explore the search space.A computational experiment is conducted on a suit of benchmark application. By comparing our algorithm result obtained to that of previous heuristic algorithm, it is evince that the ACO algorithm exhibits competitive performance with small error ratio.
3
Björk, Carl Johan. "PID tuning with Ant Colony Optimization (ACO) : A framework for a step response based tuning algorithm." Thesis, Mittuniversitetet, Avdelningen för elektronikkonstruktion, 2018. http://urn.kb.se/resolve?urn=urn:nbn:se:miun:diva-33903.
Full textAbstract:
The building automation industry lacks an affordable, simple, solution for autonomous PID controller tuning when overhead variables fluctuate. In this project, requested by Jitea AB, a solution was developed, utilising step response process modelling, numerical integration of first order differential equations, and Ant Colony Optimization (ACO). The solution was applied to two control schemes; simulated outlet flow from a virtual water tank, and the physical air pressure in the ventilation system of a preschool in Sweden. An open-loop step response provided the transfer function in each case, which, after some manipulation, could be employed to predict the performance of any given set of PID parameters, based on a weighted cost function. This prediction model was used in ACO to find optimal settings. The program was constructed in both Structured Control Language and Structured Text and documented in an approachable way. The results showed that the program was, in both cases, able to eliminate overshoot and retain the settling time (with a slightly raised rise time) achieved with settings tuned per the current methods of Jitea AB. Noise and oscillations present in the physical system did not appear to have any major negative influence on the tuning process. The program performed above Jitea AB’s expectation, and will be tested in more scenarios, as it showed promise. Autonomous implementation could be of societal benefit through increased efficiency and sustainability in a range of processes. In future studies, focus should be on improving the prediction model, and further optimising the ACO variables.<br>Byggnadsautomationsbranschen saknar en kostnadseffektiv lösning för att autonomt trimma in PID-regulatorer när överordnade variabler fluktuerar. I detta (av Jitea AB beställda) arbete, utvecklades en lösning baserad på stegsvarsmodellering, numerisk integration av första gradens ordinära differentialekvationer och myrkolonisoptimering (ACO). Lösningen applicerades i två regleringsfall; en simulerad utloppsventil från en virtuell vattentank, och det fysiska lufttrycket i ventilationssystemet på en förskola i Sverige. Ett stegsvar med öppen slinga gav en överföringsfunktion i respektive fall, som efter viss manipulering kunde nyttjas för att förutspå prestandan för en uppsättning PID-parametrar baserat på en samlad, viktad kostnadsfunktion. Predikteringsmodellen implementerades i ACO för att finna optimala parametrar. Programmet konstruerades i Structured Control Language och Structured Text, och dokumenterades på ett pedagogiskt sätt. Resultaten visade att programmet (i båda fallen) klarade att eliminera översläng med bibehållen stabiliseringstid (och något förskjuten stigningstid) jämfört med Jitea AB:s existerande trimningsmetod. Signalbrus och oscillationer i det fysiska systemet verkade inte ha någon avsevärd negativ inverkan på trimningsprocessen. Programmet presterade över Jitea AB:s förväntan, och kommer (med tanke på de lovande resultaten) fortsatt att testas i fler scenarion. Implementation av en autonom version skulle kunna innebära flera samhälleliga förmåner i form av ökad verkningsgrad och hållbarhet i en rad processer. I framtida studier bör fokus läggas på att ytterligare förbättra prediktionsmodellen, samt att vidare utforska de optimala myrkolonisvariablerna.
4
Deilami, Sara. "Optimal dispatch of shunt capacitors and load tap changers in distorted distribution systems using ant colony algorithms." Thesis, Curtin University, 2010. http://hdl.handle.net/20.500.11937/92.
Full textAbstract:
This thesis investigates the performances of a class of intelligent system algorithms in solving the volt/VAr/THD control problem for large distribution systems. For this purpose, optimal dispatch of Load Tap Changers (LTCs) and Switched Shunt Capacitors in distribution networks with high penetration of nonlinear loads is studied. The optimization problem consists of determination of LTC positions, switched shunt capacitors statuses and proper coordination of these switched elements such that power loss is minimized, voltage profile is improved and total harmonic voltage distortion (THDv) is acceptable while network and operational constraints are satisfied. The Decoupled Harmonic Power Flow (DHPF) is employed for solving the optimization problem. In the next step, an Ant Colony algorithm (ACA) is developed and implemented as an effective and new technique to capture the near global solution of the dispatch problem. Simulation results based on ACA, Genetic Algorithm (GA) and Fuzzy-GA are presented and compared to show the accuracy of the proposed approach.Finally, the application of the developed dispatch ACA in smart grids with Plug-In Electric Vehicle (PEV) charging activities in the residential networks is considered. ACA is first applied on the distribution part of the smart grid to minimize losses, improve voltage profile and mitigate harmonic distortions. Then, a smart load management (SLM) algorithm is proposed and tested for the coordination of PEVs on the residential feeders. The developed algorithm is tested on smart grid configuration with 449 buses consisting of the IEEE 31-bus distribution system connected to a number of low voltage residential feeders populated with PEVs. Simulation results are presented and compared for uncoordinated (random) and SLM coordinated PEV charging considering consumer designated priorities and charging zones.
5
Korgo, Jakub. "Nové aplikace mravenčích algoritmů." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2018. http://www.nusl.cz/ntk/nusl-385942.
Full textAbstract:
Ant algorithms have been used for a variety of combinatorial optimization problems. One of these problems, where ant algorithms haven't been used, is the design of transition rules for cellular automata (CA). Which is a problem that this master's thesis is focused on. This work begins with an introduction into ant algorithms and a overview of its applications, followed by an introduction into CA. In the next part the author proposes a way how to encode rules of CA into a graph which is used in ant algorithms. The last part of this thesis contains an application of encoded graph on elitist ant system and MAX-MIN ant system. This is followed by experimental results of creating transition rules for CA problems by these algorithms.
6
Aidov, Alexandre. "Modified continuous ant colony algorithm for function optimization." FIU Digital Commons, 2008. http://digitalcommons.fiu.edu/etd/1166.
Full textAbstract:
Many classical as well as modern optimization techniques exist. One such modern method belonging to the field of swarm intelligence is termed ant colony optimization. This relatively new concept in optimization involves the use of artificial ants and is based on real ant behavior inspired by the way ants search for food. In this thesis, a novel ant colony optimization technique for continuous domains was developed. The goal was to provide improvements in computing time and robustness when compared to other optimization algorithms. Optimization function spaces can have extreme topologies and are therefore difficult to optimize. The proposed method effectively searched the domain and solved difficult single-objective optimization problems. The developed algorithm was run for numerous classic test cases for both single and multi-objective problems. The results demonstrate that the method is robust, stable, and that the number of objective function evaluations is comparable to other optimization algorithms.
7
Gambardella, Luca Maria. "Coupling ant colony system with local search." Doctoral thesis, Universite Libre de Bruxelles, 2015. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/209045.
Full textAbstract:
In the last decades there has been a lot of interest in computational models and metaheuristics algorithms capable to solve combinatorial optimization problems. The recent trend is to define these algorithms taking inspiration by the observation of natural systems. In this thesis the Ant Colony System (ACS) is presented which has been inspired by the observation of real ant colonies. ACS is initially proposed to solve the symmetric and asymmetric travelling salesman problems where it is shown to be competitive with other metaheuristics. Although this is an interesting and promising result, it was immediately clear that ACS, as well as other metaheuristics, in many cases cannot compete with specialized local search methods. An interesting trend is therefore to couple metaheuristics with a local optimizer, giving birth to so-called hybrid methods. Along this line, the thesis investigates MACS-VRPTW (Multiple ACS for the Vehicle Routing Problem with Time Windows) and HAS-SOP: Hybrid Ant System for the Sequential Ordering Problem (SOP). In the second part the thesis introduces some modifications of the original ACS algorithm. These modifications are able to speed up the method and to make it more competitive in case of large problem instances. The resulting framework, called Enhanced Ant Colony System is tested for the SOP. Finally the thesis presents the application of ACS to solve real-life vehicle routing problems where additional constraints and stochastic information are included.<br>Doctorat en Sciences de l'ingénieur<br>info:eu-repo/semantics/nonPublished
8
Natanasihamani, Hariharan. "Behavior integration for Prometheus using real world ant colony algorithm." Thesis, McGill University, 2014. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=121468.
Full textAbstract:
Prometheus aims to explore artificial intelligence in a controlled but flexible environment by mimicking the properties of the real world using a swarm intelligence implementation. Swarm Intelligence has been used for solving problems in the domain of self organization, complexity and collective intelligence for a group of agents. The collective behavior of the entity considered here - ants, are modeled as a decentralized and self-organized system in which the ants communicate indirectly and thrive by modifying the environment. This novel approach combines the widely established stigmergy theory with real-time fluid dynamics by using Pheromones and the Navier-Stokes equations respectively to subject the environment to natural conditions like wind, and spread and decay of smell thus making the environment more suitable to real time conditions. The chosen real-time fluid dynamics method proves to be computationally fast, robust and far more realistic than traditional approaches. Also, for evaporation, instead of choosing a random fixed value for every timestep, we take into consideration the effect of temperature, vapor pressure, wind and humidity on evaporation and consequences of that. It is hoped that this model will be a step closer to achieving results substantially closer to the real world and also, observing the changes that the aforementioned natural properties might impose on the experimental world.<br>Le projet d'intelligence artificielle Prometheus vise à explorer, dans un environnement contrôlé mais flexible, les propriétés du monde réel sur une intelligence en essaim. L'intelligence distribuée a été utilisée afin de résoudre les problèmes dans le domaine de l'auto-organisation, la complexité et l'intelligence collective d'un groupe d'agents. Le comportement collectif de l'entité considérée, ici la fourmi, est modélisé comme un système décentralisé et auto-organisé dans lequel les fourmis communiquent indirectement et prospèrent en modifiant l'environnement. Celle nouvelle approche combine la théorie de stigmergie avec la mécanique des fluides, utilisant respectivement les phéromones et les équations de Navier-Stokes, afin de soumettre à l'environnement des conditions naturelles comme le vent ou encore la propagation et la désintégration de l'odeur. Ainsi l'environnement correspond mieux à des conditions réelles. La méthode de mécanique des fluides en temps réel choisie, s'avère être rapidement calculable, robuste et beaucoup plus réaliste que les approches traditionnelles. De plus, pour modéliser l'évaporation, au lieu de choisir une valeur aléatoire fixée pour chaque itération, nous prenons en compte l'effet de la température, de la pression de la vapeur, du vent, de l'humidité de l'évaporation et leurs conséquences. Nous pensons que ce modèle contribuera à l'obtention de résultats nettement plus proches du monde réel et à l'observation des changements que les propriétés naturelles susmentionnées pourraient imposer à l'environnement expérimental.
9
Wang, Yuan. "Localized Ant Colony of Robots for Redeployment in Wireless Sensor Networks." Thèse, Université d'Ottawa / University of Ottawa, 2014. http://hdl.handle.net/10393/30706.
Full textAbstract:
Sensor failures or oversupply in wireless sensor networks (WSNs), especially initial
random deployment, create both spare sensors (whose area is fully covered by other
sensors) and sensing holes. We envision a team of robots to relocate sensors and
improve their area coverage. Existing algorithms, including centralized ones and the
only localized G-R3S2, move only spare sensors and have limited improvement because
non-spare sensors, with area coverage mostly overlapped by neighbour sensors,
are not moved, and additional sensors are deployed to fill existing holes. We propose
a localized algorithm, called Localized Ant-based Sensor Relocation Algorithm with
Greedy Walk (LASR-G), where each robot may carry at most one sensor and makes
decision that depends only on locally detected information. In LASR-G, each robot
calculates corresponding pickup or dropping probability, and relocates sensor with
currently low coverage contribution to another location where sensing hole would be
significantly reduced. The basic algorithm optimizes only area coverage, while modified algorithm includes also the cost of robot movement. We compare LASR-G with
G-R3S2, and examine both single robot and multi robots scenarios. The simulation
results show the advantages of LASR-G over G-R3S2.
10
Raya, Lilysuriazna Binti. "A metaheuristic ant colony optimization algorithm for symmetric and asymmetric traveling salesman problems." Thesis, Brunel University, 2018. http://bura.brunel.ac.uk/handle/2438/17617.
Full textAbstract:
This research addresses solving two types of Travelling Salesman Problems (TSP) which are the symmetric TSP (STSP) and the asymmetric TSP (ATSP). The TSP is a problem of finding a minimal length closed tour that visits each city once. If the distances between each pair of cities are the same in both directions, the problem is a STSP, otherwise, it is an ATSP. In this thesis, a new metaheuristic algorithm which is based on Ant Colony Optimization (ACO) is proposed to solve these problems. The key idea is to enhance the ability of exploration and exploitation by incorporating a metaheuristic approach with an exact method. A new strategy for creating 'Intelligent Ants' is introduced to construct the solution tours. This strategy aims at reducing the computational time by heuristically fixing part of the solution tour and improving the accuracy of the solutions through the usage of a solver, specifically for large size instances. Moreover, this proposed algorithm employs new ways of depositing and evaporating pheromone. A different approach of global updating of pheromone is proposed in which the pheromone is deposited only on the edges belonging to the colony-best ant and evaporated only on the edges belonging to the colony-worst ant that are not in the colony-best ant. Additionally, the parameters of the proposed algorithm which include the number of colonies, the number of ants in each colony, the relative influence of the pheromone trail α and the pheromone evaporation rate ρ are expressed as a function of the problem size. Comparisons with other sets of parameter values suggested in the literature have been investigated which illustrate the advantages of the choice of the proposed parameter settings. Further, in order to evaluate the performance of the proposed algorithm, a set of standard benchmark problems from the TSPLIB with up to 442 cities were solved and the results obtained were compared with other approaches from the literature. The proposed algorithm has proven to be competitive and shows better performance in 63% of the 16 algorithms in terms of solution quality and obtained the optimum solutions in 70% of the 33 instances, proving that it is a good alternative approach to solve these hard combinatorial optimisation problems.
11
Ståhlbom, Niclas. "A BINARY SPACE PARTITIONED ANT COLONY OPTIMIZATION ALGORITHM FOR THE TRAVELING SALESMAN PROBLEM." Thesis, Mälardalens högskola, Akademin för innovation, design och teknik, 2021. http://urn.kb.se/resolve?urn=urn:nbn:se:mdh:diva-55049.
Full textAbstract:
A common type of problems that exist in both industrial and scientific spaces are optimization problems. These problems can be found in among other things manufacturing, pathfinding, network routing and more. Because of the wide area of application, optimization is well a studied area. One solution to these types of problems is the Ant Colony Optimization algorithm that has been around since 1991 and has undergone a lot of developments over the years. This algorithm draws inspiration from real ant colonies and their procedure for foraging. However, a common criticism of this algorithm is its poor scalability. To tackle the scalability problem this thesis will combine the concept of binary space partitioning with the Ant Colony Optimization algorithm. The goal is to examine the algorithms convergence times and lengths of the paths produced. The results are measured in intervals by calculating the best possible path found at every interval. The findings showed that given an unlimited execution time the original Ant Colony Optimization algorithm produced shorter paths. But when a limit on execution time was introduced and the problem sizes grew the performance began to favor the partitioned versions. These findings could be useful in areas where complex optimization problems need to be solved within a limited timeframe.<br><p>The presentation took place via an online conference call using the software "Zoom"</p>
12
Li, Yibo. "Solving cardinality constrained portfolio optimisation problem using genetic algorithms and ant colony optimisation." Thesis, Brunel University, 2015. http://bura.brunel.ac.uk/handle/2438/10867.
Full textAbstract:
In this thesis we consider solution approaches for the index tacking problem, in which we aim to reproduces the performance of a market index without purchasing all of the stocks that constitute the index. We solve the problem using three different solution approaches: Mixed Integer Programming (MIP), Genetic Algorithms (GAs), and Ant-colony Optimization (ACO) Algorithm by limiting the number of stocks that can be held. Each index is also assigned with different cardinalities to examine the change to the solution values. All of the solution approaches are tested by considering eight market indices. The smallest data set only consists of 31 stocks whereas the largest data set includes over 2000 stocks. The computational results from the MIP are used as the benchmark to measure the performance of the other solution approaches. The Computational results are presented for different solution approaches and conclusions are given. Finally, we implement post analysis and investigate the best tracking portfolios achieved from the three solution approaches. We summarise the findings of the investigation, and in turn, we further improve some of the algorithms. As the formulations of these problems are mixed-integer linear programs, we use the solver ‘Cplex’ to solve the problems. All of the programming is coded in AMPL.
13
Mohi, El Din Hatem. "Comparative Analysis of Ant Colony Optimization and Genetic Algorithm in Solving the Traveling Salesman Problem." Thesis, Blekinge Tekniska Högskola, 2021. http://urn.kb.se/resolve?urn=urn:nbn:se:bth-21520.
Full textAbstract:
Metaheuristics is a term for optimization procedures/algorithms that can be applied to a wide range of problems. These problems for which metaheuristics are used usually fall in the NP-hard category, meaning that they cannot be solved in polynomial time. This means that as the input dataset gets larger the time to solve increases exponentially. One such problem is the traveling salesman problem (TSP) which is and has been widely used as a benchmark problem to test optimization algorithms. This study focused on two such algorithms called ant colony optimization (ACO) and genetic algorithm (GA) respectively. Development of such optimization algorithms can have huge implications in several areas of business and industry. They can for example be used by delivery companies to optimize routing of delivery vehicles as well as in material science/industry where they can be used to calculate the most optimal mix of ingredients to produce materials with the desired characteristics. The approach taken in this study was to compare the performance of the two algorithms in three different programming languages (python, javascript and C#). Previous studies comparing the two algorithms have reported conflicting results where some studies found that ACO yielded better results but was slower than GA, while others found that GA yielded better results than ACO. Results of this study suggested that both ACO and GA could find the benchmark solution, but ACO did so much more consistently. Furthermore javascript was found to be the most efficient language with which to run the algorithms in the setup used in this study.
14
ZHANG, YUAN-HAO, and 張原豪. "Ant Colony System Based Algorithm for Optimal VAR Sources Planning Problem." Thesis, 2017. http://ndltd.ncl.edu.tw/handle/prv4sc.
Full textAbstract:
碩士<br>高苑科技大學<br>電子工程研究所<br>105<br>Abstract
In power system research, the optimal reactive volt ampere (VAR) sources planning problem is a hard problem. Because it involves integer variables for determining the placement locations of capacitor, discrete variables for deciding the number of capacitor banks to be installed, and it is also a large-scale constrained optimization power problem. In this paper, we propose an ant colony system (ACS) based algorithm to solve this problem. We first employ the sensitivity analysis method, which performs reducing the search of the huge sample space formed by all integer and discrete control variables. The second part is to discover the near-globally optimal solution with the ACS algorithm. The algorithm also combines the successive quadratic programming method with the dual projected pseudo quasi-Newton method. Hence, the large-dimension OPF-like problems can be solved very fastest.
To demonstrate the computational efficiency of our algorithm, we have compared with the tabu search method and genetic algorithm on IEEE 118-bus system. The test results show that our algorithm is an excellent alternative for the optimal VAR sources planning problem.
15
Cheng, Ming-Jen, and 鄭明仁. "Optimal Feeder Routing for Distribution System Planning by Ant Colony System Algorithm." Thesis, 2004. http://ndltd.ncl.edu.tw/handle/82600358422594468512.
Full textAbstract:
碩士<br>國立臺灣科技大學<br>電機工程系<br>92<br>The purpose of distribution planning is usually to optimize the total costs of feeder configuration and substation location. Many optimum routings only consider the minimized maintenance costs and feeder resistive loss costs, but not consider reliability costs of the total cost optimization. Using the ant colony system (ACS) algorithm, this thesis successfully transforms the optimum routing into traveling salesman problem (TSP). Then, the total minimal cost of the routings planning will be obtained by the combinatorial optimization algorithm considering the summation of reliability costs, feeder resistive loss, and investment and maintenance costs. Finally, two cases of distribution systems are presented to show the feasibility and superiority of the ACS algorithm applied to optimal routing of distribution systems.
16
Lin, Zong-Han, and 林宗漢. "Applying Ant Colony System Algorithm for the Truck and Trailer Routing Problem." Thesis, 2008. http://ndltd.ncl.edu.tw/handle/8j6t8z.
Full textAbstract:
碩士<br>國立高雄第一科技大學<br>運籌管理所<br>96<br>This study aims at applying ant colony system (ACS) to solving the truck and trailer routing problem (TTRP), a variant of the well-known vehicle routing problem (VRP). In TTRP, a fleet of trucks and trailers are used to service customers. Due to some practical constraints, some customers, called truck customers, can only be serviced by a single truck. Other customers that may be serviced by a single truck or a complete vehicle (i.e., a truck pulling a trailer) are vehicle customers. As a result, there are three types of route in a TTRP solution, namely pure truck route, pure vehicle route, and complete vehicle route.
Ant colony system is a meta-heuristic inspired by the phenomenon that ants can find the shortest path between a food source and their net. Since ACS had been applied to many hard combinatorial optimization problems with success, including the vehicle routing problem, this research developed a two-stage solution algorithm based on ACS to solve the TTRP. The ACS approach is used in the first stage to construct a set of good routes. These routes are then improved by using a series of route improvement heuristics, including 2-opt, swap, and insertion, in the second stage. The proposed ACS-based algorithm is implemented and tested by using the benchmark TTRP problems presented in the literature. We compare the results obtained by the proposed ACS-based algorithm and those obtained by other heuristics (such as tabu search and simulated annealing) reported in the literature. The results demonstrate that the ACS-based algorithm is applicable and effective in solving the TTRP problem, in particular for problem instances with fewer than 150 customers.
17
Wu, Min-thai, and 吳明泰. "A Dynamic-Edge Ant-Colony-System Algorithm for Solving Continuous Domain Problems." Thesis, 2014. http://ndltd.ncl.edu.tw/handle/40480807768703303336.
Full textAbstract:
博士<br>國立中山大學<br>資訊工程學系研究所<br>102<br>Ant colony systems (ACS) have been successfully applied to solve optimization problems. Especially, they are effective in finding nearly optimal solutions to discrete search spaces. When the solution spaces of the problems to be solved are continuous, it is not so appropriate to use the original ACS. This dissertation thus proposes two extended ACS algorithm for solving continuous variables problems. The first approach based on binary coding provides a standard process for solving problems with continuous variables. It first encodes the solution space for a continuous domain into a discrete binary coding space (searching map), and then a modified ACS is applied to find the solution. Different from the previous ant-based algorithms for continuous domain, the proposed binary coding ACS (BCACS) could retain the original operators and keep the benefits and characteristics of the traditional ACS. Besides, it is easy to implement, and could be applied in different kinds of problems in addition to mathematical problems. The other proposed algorithm is dynamic-edge ACS (DEACS). Different from BCACS, it can dynamically generate edges between two nodes and give a pheromone measure through distribution functions. In addition, it maps the encoding representation and the operators of the original ACS into continuous spaces easily. The encoding of solution space in this algorithm is a real continuous space. Thus, the global best solution is assured to be in the solution space.
The proposed DEACS is also applied to fuzzy data mining for finding out interesting and meaningful linguistic patterns from large databases. Finally, this dissertation presented a Hadoop framework for DEACS in order to reduce the computation time. Experimental results on mathematical functions and fuzzy data miming show the good performance of the proposed approaches in the continuous solution space.
18
Malisia, Alice Ralickas. "Investigating the Application of Opposition-Based Ideas to Ant Algorithms." Thesis, 2007. http://hdl.handle.net/10012/3233.
Full textAbstract:
Opposition-based learning (OBL) was recently proposed to extend di erent machine learning
algorithms. The main idea of OBL is to consider opposite estimates, actions or states
as an attempt to increase the coverage of the solution space and to reduce exploration time.
OBL has already been applied to reinforcement learning, neural networks and genetic algorithms.
This thesis explores the application of OBL to ant algorithms. Ant algorithms
are based on the trail laying and following behaviour of ants. They have been successfully
applied to many complex optimization problems. However, like any other technique, they
can benefit from performance improvements. Thus, this work was motivated by the idea of
developing more complex pheromone and path selection behaviour for the algorithm using
the concept of opposition.
This work proposes opposition-based extensions to the construction and update phases
of the ant algorithm. The modifications that focus on the solution construction include
three direct and two indirect methods. The three direct methods work by pairing the ants
and synchronizing their path selection. The two other approaches modify the decisions of
the ants by using opposite-pheromone content. The extension of the update phase lead to
an approach that performs additional pheromone updates using opposite decisions.
Experimental validation was done using two versions of the ant algorithm: the Ant
System and the Ant Colony System. The di erent OBL extensions were applied to the
Travelling Salesman Problem (TSP) and to the Grid World Problem (GWP). Results
demonstrate that the concept of opposition is not easily applied to the ant algorithm.
One pheromone-based method showed performance improvements that were statistically
significant for the TSP. The quality of the solutions increased and more optimal solutions
were found. The extension to the update phase showed some improvements for the TSP
and led to accuracy improvements and a significant speed-up for the GWP. The other
extensions showed no clear improvement.
The proposed methods for applying opposition to the ant algorithm have potential, but
more investigations are required before ant colony optimization can fully benefit from opposition.
Most importantly, fundamental theoretical work with graphs, specifically, clearly
defining opposite paths or opposite path components, is needed. Overall, the results indicate
that OBL ideas can be beneficial for ant algorithms.
19
Wang, Cheng-Lan, and 王政嵐. "Analogous Ant Colony System Algorithm for Concave Cost Minimum Cost Network Flow Problems." Thesis, 2005. http://ndltd.ncl.edu.tw/handle/84561757893702971865.
Full textAbstract:
碩士<br>國立中央大學<br>土木工程研究所<br>93<br>Traditionally, the minimum cost transshipment problems are formulated as a linear cost problem, in order to reduce problem complexity. In reality, the unit cost decreases as the amount transported increases, resulting in a concave cost function. Recently, a research started to use advanced neighborhood search algorithms, such as threshold accepting (TA) and great deluge algorithm (GDA), to solve concave cost network problems in order to find better solutions than traditional heuristics. However, such neighborhood search algorithms easily encounter degeneracy problems, resulting in decreased solution efficiency. It is wondered if such algorithms can explore the whole domain area to find better solutions. In addition, most past research on solving concave cost network problems is confined to specific network problems. Therefore, a global search algorithm, based on genetic algorithm (GA), was recently developed to solve minimum concave cost transshipment problems.
Ant colony system algorithm (ACS) is a new popular heuristic which searches feasible solutions by using spread exploration. In some cases, its efficiency was found to be better than GA. Since there has not yet ACS developed to slove minimum cost transshipment problems with concave arc costs, in this research we developed an analogus ant colony system algorithm (AACS) to solve minimum cost transshipment problems with concave arc costs, based on ACS, incorporating the merits of GA, TA and concave cost network heuristics, that were applied for solving minimum cost transshipment problem with concave arc costs in literature. In order to evaluate this AACS, we referred to TA, GDA and GA to perform tests and comparison. The results can hopefully be useful reference for practitioners to solve their real problems.
The preliminary idea of our algorithm development was as follows: We first design several initial solution methods. In the feasible solution generation process, we developed several state transition rules to generate several paths, which did then be modified as feasible spanning trees by using a flow argumentation algorithm. For updating arc pheromones, we combined local and global pheromone updating rules, incorporating the TA search strategy, to develop several new pheromone updating rules. Besides, we referred to the elite strategy typically used in GA to speed up computations. In order to evaluate AACS for different problem scales and parameters, we designed a randomized network generator to produce many test problems. Finally, the tests were performed on personal computers with the assistance of C++ computer language for coding all necessary programs.
20
Lee, Lu-yao, and 李律瑤. "Using Ant Colony Algorithm for Maximizing Social Utility in Multi-user Communication System." Thesis, 2009. http://ndltd.ncl.edu.tw/handle/06481372218326781559.
Full textAbstract:
碩士<br>實踐大學<br>資訊科技與管理學系碩士班<br>97<br>With the rapid development of wireless networks and devices, the demand for spectrum resource is increasingly growing. Therefore, how to allocate spectrum dynamically to enhance system utility in a multi-user communication system has become an importance issue in recent years. In a multi-user communication system, the transmission quality of each user is affected by not only the channel background noise but also the crosstalk interference from other users, this thesis focuses on allocating the limited power on difference channels for each user to maximize social utility (i.e., the sum of all users’ utilities). Due to the non-convexity of this problem, the CPU time required to solve this problem by the conventional mathematical programming techniques increases greatly as the number of channel and user increases. This thesis proposes an efficient ant colony algorithm to allocate spectrum dynamically for users in order to maximize the social utility. The proposed algorithm integrates the cooling concept of simulated annealing to improve the solution efficiency by enhancing convergence during the local search of the ant colony optimization algorithm. In the computational experiments, the effect of each parameter on the performance of the proposed algorithm is analyzed. Besides, the results obtained by the proposed method are compared with that by the mathematical programming solver, LINGO. Computational results show that the differences in social utility between the proposed algorithm and LINGO are within 0.5% for all cases, and the proposed method outperforms the LINGO in solution time as the number of channel and user increases.
21
Wang, Y. D., and 王奕敦. "Design Fuzzy Sliding Mode Controller Based on the Fuzzy Ant Colony System Algorithm." Thesis, 2009. http://ndltd.ncl.edu.tw/handle/09628816964931785592.
Full textAbstract:
碩士<br>國立宜蘭大學<br>電機工程學系碩士班<br>97<br>In this paper, a novel fuzzy ant colony system (FACS) with a fuzzy mechanism and a fuzzy probable mechanism is presented for parameter determinations. Based on the fuzzy rules, the transition behavior of ants is simulated. The fuzzy probable mechanism is introduced with fuzzy probable rules to implement the diverse searching. The fuzzy probable rules are proposed to have the fuzziness in the antecedent parts and the probability in the consequent parts. To indicate the effectiveness, the fuzzy ant colony system is applied to find the proper parameters of the fuzzy sliding controllers for swinging and balancing the inverted pendulum and cart system. Also, the comparisons between the proposed fuzzy ant colony system and other ant colony optimization algorithms are provided in the simulations.
22
Alhaddad, Fawaz Masoud. "OPTIMAL FILTER PLACEMENT AND SIZING USING ANT COLONY OPTIMIZATION IN ELECTRICAL DISTRIBUTION SYSTEM." 2014. http://hdl.handle.net/10222/50515.
Full textAbstract:
This thesis presents an application of the Ant Colony algorithm for optimizing filter placement and sizing on a radial distribution system to reduce power losses and keep the effective harmonic voltage values and the total harmonic distortion (THD) within prescribed limits. First, a harmonic load flow (HLF) algorithm is performed to demonstrate the effect of harmonic sources on total power loss. Then the Ant Colony algorithm is used in conjunction with HLF to place a selection of filter sizes available at each possible location so that both power loss and THD are minimized. As a result the optimal adjustment of location and size of the filter are determined. Results of computational experiments on standard test systems are presented to demonstrate improvement and effectiveness of using the filters at the optimal location. The methodology used can be easily extended to different distribution network configurations.<br>Master Thesis
23
KAO, HONG-SHENG, and 高鴻聖. "Applying an Ant Colony System Algorithm on Solving the Multi-Temperature Vehicle Routing Problem." Thesis, 2011. http://ndltd.ncl.edu.tw/handle/21810326582273240294.
Full textAbstract:
碩士<br>育達商業科技大學<br>行銷與流通管理所<br>99<br>In the vehicle routing problem(VRP), three important issues consisting of multi-temperature, heterogeneous fleets, and time windows should be simultaneously considered to formulate a real-world vehicle routing plan, but it is more difficult to deal with. Although the study of the VRP has attracted many researchers, few papers in the literature simultaneously considered the three issues mentioned above, while most researchers discussed only the last two issues of the problem. It is hardly discovered that the exploration associated with the multi-temperature VRP has been published in the
literature. Therefore, the objective of this study is to explore the single-depot multi-temperature fixed size and mix VRP with time windows(MTFSMVRPTW). An efficient two-stages meta-heuristic ant colony system （KMACS） is developed, the first stage is to use the K-Means clustering method to cluster, the customer points in accordance with demand and distance, the second stage is to apply the ant colony system(ACS) to solve.
Finally, three experiments are designed and conducted in order to explore the impacts of changing the values of relevant parameters on the optimal solution. The first experimental result indicates that the best ant parameters as a1=0.1, a2=0.4, a3=0.5, a4=0.1, a5=0.4, a6=0.5, the best ACS parameters as α=0.1、ρ=0.1、β=10、P0=0.9. The second experiment shows the best number of generations as Mg=200. The third experimental results can be found that the KMACS method has high performance on solving the
MTFSMVRPTW, because the result of the delivery cost is a difference of 5% and distance is a difference of 3% compared with the optimal solution value. However, the time of solving the optimal solution requirs 135,988 seconds, but the KMACS method requires only 1 second to get the feasible solution values.
24
Tsai, Yu-Lun, and 蔡育倫. "A Ant Colony Optimization Algorithm for Setup Coordination in a Two-Stage Production System." Thesis, 2008. http://ndltd.ncl.edu.tw/handle/72484962114213303580.
Full textAbstract:
碩士<br>國立臺灣科技大學<br>工業管理系<br>96<br>This thesis is concerned with the coordination of setup times in a two-stage production system. The problem is derived from a furniture plant, where there are two consecutive departments including cutting and painting departments. In different departments, items are grouped according to different attributes. A sequence-dependent setup time is required in a stage when the new batch has a different level of attribute from the previous one. The objective is to minimize the total setup time. In this thesis, we first propose a simple dispatching rule called the Least Flexibility with Setups (LFS) rule. The LFS rule can yield a solution better than an existing genetic algorithm while using much less computation time. Using the LFS rule as both the initial solution method and the heuristic desirability, an ACO algorithm is developed to further improve the solution. Computational experiments show that the proposed ACO algorithm is quite effective in finding the near-optimal solution.
25
Huang, Yu-Chen, and 黃宇辰. "Optimization of the Series-Parallel System with the redundancy allocationproblem using a hybrid ant colony algorithm." Thesis, 2003. http://ndltd.ncl.edu.tw/handle/16172574649132672951.
Full textAbstract:
碩士<br>元智大學<br>工業工程與管理學系<br>91<br>The efficiency of production system has drawn more and more attention of system designers, as competitive pressures increase. Therefore, in this research, we propose a new hybrid ant colony algorithm to analyze redundancy allocation problem in series-parallel systems. The mechanism of Tabu lists is applied for local search in ant colony algorithm to increase quality of search results. We study the problem of selecting component and redundancy levels to optimize allocation cost, given system-level constraints on reliability and weight. Through experimental design and result analysis, it is shown that hybrid ant colony algorithm can search for optimal or near-optimal solutions in redundancy allocation problems with impressive efficiency.
Besides the above-mentioned achievements, this research also investigates the best selection of parameter values in the mixed ant colony algorithm. The parameters we analyzed include trail persistence, the relative importance of exploitation versus exploration, the relative importance of pheromone trail, relative importance of local heuristic and length of tabu list. Finally, we provide suggestions for setting the levels of parameters.
26
CHANG, HSIU-LING, and 張秀鈴. "A Study of Constructing Job Shop Scheduling Decision Support System with Limited Capacity Using Ant Colony Optimization Algorithm." Thesis, 2008. http://ndltd.ncl.edu.tw/handle/x5jtrg.
Full textAbstract:
碩士<br>世新大學<br>資訊管理學研究所(含碩專班)<br>96<br>In the past ten years, Job Shop Scheduling Problem (JSSP) had conducted many excellent studies. However, the studies are different from practical situation such as the most studies all in the particular problem scale and produce the type to descend the development before etc. It causes the result of studies cannot be used. Furthermore, Advanced Planning Scheduling (APS) does not fit all kind of industries because not all the enterprises have same conditions.
JSSP is considered as a particularly hard combinatorial optimization problem. The ant colony optimization algorithm (ACO) has been identified as an effective means of solving complex combinatorial optimization problems. This paper had constructed job shop scheduling model using ACO to get the rate of delivering and perform the sensitivity analysis. Finally, the conclusion is used as the reference of the individual cases scheduling.
27
Chen, Luke, and 陳與泳. "The Decision-Making of Fund Assignment for Combined Type Fund－the Application of Ant Colony System and Genetic Algorithm." Thesis, 2004. http://ndltd.ncl.edu.tw/handle/59675012471686566073.
Full textAbstract:
碩士<br>國立臺灣科技大學<br>資訊管理系<br>92<br>The idea today which we manage finances in the investment popularizes day after day, so each kind of investment tool was connected with the most of modern people’s life. In the future, professional management in investment and finance will become a trend, due to mature in stock markets, boom of the listed companies and complex correlation in global financial markets. The mutual fund has the superiority , since there are professional management, and contains many investments to enable it with the advantage of sharing risks and enjoying profit stably. In the past, the question which the investor faced is too many stocks, however the present is too many fund. In recent years, the combined type fund started to develop slowly in domestic, which take the fund as the investment sign and helps the investor by the professional angle to solve the problem to choose fund.
On the other hand, along with computer information and artificial wisdom developed, many questions unable to be solved by traditional method all have the unprecedented development. This research attempts to utilize genetic algorithm(GA) and ant colony system(ACS) to establish decision-making of fund assignment for combined type fund, and develops a policy-making pattern refered by the investor to construct the combined type fund.
The empirical results are as follows:
1. In respect of the convergence of Sharpe ratio, the convergent results from ACS and GA are almost identical.
2. The reward rates respectively from the decision-making constructed by ACS and GA differ not much. But they are both distinctly better then fund equal distribution and holding weighting index.
28
Chen, Jiun-Shiun, and 陳俊勳. "An Ant Colony Optimization Clustering Algorithm." Thesis, 2004. http://ndltd.ncl.edu.tw/handle/83304156993590898222.
Full textAbstract:
碩士<br>元智大學<br>工業工程與管理學系<br>92<br>Cluster analysis is a technique used to forecast and infer a great deal of data in the domain of data mining. Its major objective is to differentiate the data that have unknown categories. Decision manager can obtain the reference information through the result of cluster analysis. Therefore developing an efficient clustering algorithm is important for many applications. K-Means algorithm is commonly used to conduct clustering task since it can quickly cluster data. However, K-Means algorithm has many drawbacks when used to real world cluster problem.
This research combines the concept of traditional clustering algorithm and the technique of ant colony optimization to develop a clustering algorithm that can obtain the global optimization solution. The approach improves the drawback in which K-Means algorithm is easily fall into an awkward situation of the local optimization solution. To demonstrate the benefits of our method, this research experiments several sample data sets. These experiments show that the proposed cluster algorithm can improve the drawback of K-Means algorithm and obtain better cluster objective value and accurate rate. Furthermore, we use product specifications data and production defect data from a practical PCB manufacturer to forecast the defects for a new product. This can prevent and reduce the produce cost and raise the quality of the new product during production.
29
Zheng, Yu-Jie, and 鄭宇捷. "Some Aspects of Ant Colony Algorithm." Thesis, 2008. http://ndltd.ncl.edu.tw/handle/85269700296362976819.
Full textAbstract:
碩士<br>國立高雄海洋科技大學<br>輪機工程研究所<br>96<br>In this study, a new pheromone reset method for ant colony algorithm to avoid local minima property is investigated. For validation, the comparison between the presented technique and Dorigo’s ant colony optimization algorithm for traveling salesman problems are conduced.
Ant Colony System (ACS) is a recently proposed meta-heuristic approach for solving combinatorial optimization problems. In order to get the best optimal solution, the ants in the ACS not only select the route known, but also the route which never tracked. Exploitation and Exploration are the two mechanism for selecting the route.
The huge combinatorial optimization problems that the pheromone evaporation rapidly by using traditional ACS algorithm. This study is proposed to add the artificial reset pheromone to improvement solution effect. While the ants are convergence, the pheromone on the route reset and the ants search the solution again. This study provided experiment with some examples form TSPLIB. Adding the artificial reset pheromone can promote the accuracy to well
30
Yang, Min-Hao, and 楊閔皓. "SOPC Based Ant Colony Optimization Algorithm Design." Thesis, 2012. http://ndltd.ncl.edu.tw/handle/50255562295566376033.
Full textAbstract:
碩士<br>淡江大學<br>電機工程學系碩士班<br>100<br>In this thesis, proposed ant colony algorithm based on a SOPC (System on a Programmable Chip) technique on the FPGA chip. In the design and implementation of ant colony algorithm based on a SOPC (System on a Programmable Chip) technique is applied to design two processing method: (1) Selecting path, (2) Path analysis. Selecting path belongs to the pre-processing of the ant colony algorithm takes a longer computing processing time, so design into a hardware circuit, in order to speed up processing. (2) path analysis will be to the C language software in the NIOS II processor. Experimental results found in this paper to the processing time can be less accurate path information.
31
Chen, Ya-Ling, and 陳雅玲. "Classification Rule Discovery Based on Ant Colony AlgorithmClassification Rule Discovery Based on Ant Colony Algorithm." Thesis, 2007. http://ndltd.ncl.edu.tw/handle/17086737556265789520.
Full textAbstract:
碩士<br>華梵大學<br>資訊管理學系碩士班<br>95<br>In recent years , Ant Colony Algorithm has been a hot topic of Dataming. It was published by Dorigo et al. since 1996 and applied in many different type of problems, like Traveling Salesman, Scheduling Problem, Multiple Knapsack, and so on. But it was related to Classification Rule Mining until 2002 by Parepinelli et al., called Ant-Miner (ant-colony-based data miner).
This research is based on the Ant-Miner Algorithm. We put it into practice and improve it by changing station transition rule and adding the function of dealing with continuous attribute. Finally, the result of this study shows that, Ant-Miner after improving is not only be more convenient to use, but also the rate of correct is increasing.
32
Middendorf, Martin, Frank Reischle, and Hartmut Schmeck. "Multi Colony Ant Algorithms." 2002. https://ul.qucosa.de/id/qucosa%3A32027.
Full textAbstract:
In multi colony ant algorithms several colonies of ants cooperate in finding good solutions for an optimization problem. At certain time steps the colonies exchange information about good solutions. If the amount of exchanged information is not too large multi colony ant algorithms can be easily parallelized in a natural way by placing the colonies on different processors. In this paper we study the behaviour of multi colony ant algorithms with different kinds of information exchange between the colonies. Moreover we compare the behaviour of different numbers of colonies with a multi start single colony ant algorithm. As test problems we use the Traveling Salesperson problem and the Quadratic Assignment problem.
33
Chen, Jr-Ming, and 陳志明. "Applying Ant Colony Algorithm in Vehicle Routing Problem." Thesis, 2004. http://ndltd.ncl.edu.tw/handle/d43h2d.
Full text
34
Tu, Yi-Jung, and 杜宜蓉. "Evolving Ant Colony Optimization Using the Genetic Algorithm." Thesis, 2007. http://ndltd.ncl.edu.tw/handle/92480337140980150298.
Full textAbstract:
碩士<br>立德管理學院<br>應用資訊研究所<br>95<br>Genetic algorithm (GA) and ant colony optimization (ACO) are the two of heuristic algorithms. The ACO is inspired from the biological behavior of real ants. It was developed as a viable approach with high performance for achieving stochastic combinatorial optimizations. Although the ACO is effective in solving the global optimization problems, there are many parameters, both explicit and implicit, affect the performance of the algorithms since the search processes of the two algorithms are nonlinear and complex. Therefore, the ACO with well-selected parameter settings may result in good performance. This thesis proposes an evolving ant colony optimization, which employs a GA to find the best set of parameters employed in the ACO, and apply to the large traveling salesman problem (TSP) for the purpose of obtaining the optimal searching tour. In this thesis, there are ten designed parameters include the number of ant m, three weighting factors q0 , ?and β , local and global evaporation coefficients ρlocal and ρglobal , parameter of pheromone Q , number of table list l , number of iteration h , and repeated run number i . The benchmarking cases of traveling salesman problem (TSP) from 14 to 225 nodes are computed to generalize a set of optimal parameters through the evolving ACO for applying to large TSPs with over 300 nodes. The results demonstrated that the presented evolving ACO significantly enhances the solution accuracy and speed up the algorithmic convergence.
35
Peng, Kuang-Ping, and 彭光平. "PID CONTROLLER PARAMETER ESTIMATION USING ANT COLONY ALGORITHM." Thesis, 2012. http://ndltd.ncl.edu.tw/handle/90986380429125749428.
Full textAbstract:
碩士<br>大同大學<br>電機工程學系(所)<br>100<br>In this thesis, we propose an ant colony algorithm (ACA) estimator to obtain the parameters of (Proportional-Integral-Derivative) PID controller. Because the ACA is a cooperative agent algorithm, its characteristic is the positive feedback, distributed computation, and the use of a constructive greedy heuristic. Therefore, the structure of the ACA estimator is the three ACA sets in which are parallel structure. And, each ACA set is expressed as the parameters of the PID controller, KP, KI, and KD, respectively. The searching pattern of each ACA set is five layers in which each layer is ten nodes. These searching patterns are expressed as each PID parameter is five-bit decimal real number. In addition, integral of time and absolute error (ITAE) and the tracking error are cited into the cost function of ACA set to update the pheromones of ACA set. Finally, the effectiveness of the proposed controller has been verified by simulations using the inverted pendulum system. It can be improved the accuracy to estimate PID parameters.
36
Strite, Lisa. "A hybrid ant colony optimization algorithm for graph bisection /." 2001. http://emp3.hbg.psu.edu/theses/available/etd-12202001-102921/.
Full text
37
Iyengar, S., and S. Pattnaik. "Solving the MANET Routing Problem using Ant Colony Algorithm." Thesis, 2010. http://ethesis.nitrkl.ac.in/1682/1/BtechThesis.pdf.
Full textAbstract:
Mobile ad-hoc networks (MANETs) are a collection of mobile nodes communicating wirelessly without a centralized infrastructure. The biggest challenge in MANETs is to find a path between communicating nodes, that is, the MANET routing problem. The considerations of the MANET environment
and the nature of the mobile nodes create further complications which results in the need to develop special routing algorithms to meet these challenges. Swarm
Intelligence, a bio-inspired technique, which has proven to be very adaptable in other problem domains, has been applied to the MANET routing problem as it forms a good fit to the problem. In this thesis, a study of Ant Colony based routing algorithms is carried out taking into consideration two of the most popular algorithms Ant based algorithms, AntHocNet and the Ant Routing Algorithm (ARA). A thorough analyis of ARA is carried out based on the effect of its individual routing mechanisms on its routing efficacy. The original ARA algorithm, although finds the shortest path between source and destination, is observed to not be competitive against other MANET algorithms such as AODV in performance criteria. Based on the analysis performed, modifications are proposed to the ARA algorithm. Finally, a performance evaluation of the original ARA and the modified ARA is carried out with respect to each other, and with respect to AODV, a state of the art MANET routing algorithm vis-a-vis mobility criteria. The motivation behind the thesis is to realize application of MANETs in real world applications by solving the problem of routing.
38
Yang, Yu-Hsien, and 楊郁仙. "Shortest-Time Path Algorithm Based on Ant Colony Algorithm and Intersection Delay." Thesis, 2013. http://ndltd.ncl.edu.tw/handle/54985232823898838973.
Full textAbstract:
碩士<br>國立中興大學<br>資訊科學與工程學系所<br>101<br>Under real traffic condition, the drivers may not be able to reach the destination very soon even if the drivers choose the shortest distance path. For example, the drivers will spend more travel time while distance path has traffic jam.
There are many research papers regarding path planning in the literature. Some of them used the Ant Colony Optimization (ACO) Algorithm. Some of them considered intersection delay. However, none of them use ACO algorithm with intersection delay taken into consideration.
Intersection delay is an important factor of travelling time in real world traffic. Igonoring intersection delay will result in inpraticle path planning. In this thesis, we propose a shortest-time path algorithm based on ant colony algorithm and intersection delay.
For the experiments, we utilize the Highway Traffic Systems Simulation Model (HTSS model) of the Institute of Transportation for generating the traffic simulation data. The experimental results show that in a grid map, the proposed method could find the shortest-time path effectively from source to destination.
39
(13830946), Shanmuganatha Kasi. "Effective Sizing and Optimisation of Hybrid Renewable Energy Sources for Micro Distributed Generation System." Thesis, 2025. https://figshare.com/articles/thesis/Effective_Sizing_and_Optimisation_of_Hybrid_Renewable_Energy_Sources_for_Micro_Distributed_Generation_System/28656116.
Full textAbstract:
In the modern world, Renewable Energy Sources (RES) play a crucial role in resolving the fossil fuel issues. It supports maintaining the sustainability of the environment by reducing air pollution. Predominantly, Hybrid Renewable Energy System (HRES) is the ideal mechanism that integrates diverse RES for enhancing energy efficiency and reliability in Microgrids (MGs). Conversely, the integration of HRES with MGs faces challenging issues, such as energy management, load demand, efficiency, and reliability. Several research plans have been devised to attain enhanced HRES in MGs, but such schemes lack efficiency, reliability, and accuracy. To solve this problem, the proposed model implemented a specialized set of procedures to control load demand and decrease the cost of HRES in MGs. Accordingly, the respective model used the Ant Lion Colony Optimization with Particle Swarm Optimization (ALCO-PSO) for the Maximum Power Point Tracking (MPPT) mechanism for enhancing power efficiency. The Ant Colony Optimization (ACO) algorithm is utilized because it has the advantages of higher efficiency, better global search, and distributed nature. The classical research identified that it is limited due to computational complexity, premature convergence, etc. To resolve the issue, the Lion Optimization Algorithm (LOA) is combined with the ACO mechanism for ability to handle premature convergence, enhance complexity, sensitivity on parameter setting, etc. Conversely, ALCO is lacking certain factors such as limited scalability, global search capability, and other issues. To tackle the limitations, the PSO is incorporated with ALCO to improve accuracy through the ability to handle limited scalability and global search capability. Besides, direct current fault detection functions with the Artificial Neural Network (ANN) algorithm for improving the system’s performance with solar data. Finally, the performance of the projected system is calculated with specific performance metrics such as power, voltage, and power quality. The accuracy achieved by the model is 99.56%, the faster convergence (FC) obtained is 0.11 s, and the oscillation around (OA) gained by the model is 4.25 W. The tracking time is 0.2 s, the interruptible load is 0.009%, the cost of energy (COE) is 0.0413 $/kWh, and the penalty is 0.94 $/kWh.<p></p>
40
McDonald, Walter. "A Multi-Objective Ant Colony Optimization Algorithm for Infrastructure Routing." Thesis, 2012. http://hdl.handle.net/1969.1/ETD-TAMU-2012-05-11093.
Full textAbstract:
An algorithm is presented that is capable of producing Pareto-optimal solutions for multi-objective infrastructure routing problems: the Multi-Objective Ant Colony Optimization (MOACO). This algorithm offers a constructive search technique to develop solutions to different types of infrastructure routing problems on an open grid framework. The algorithm proposes unique functions such as graph pruning and path straightening to enhance both speed and performance. It also possesses features to solve issues unique to infrastructure routing not found in existing MOACO algorithms, such as problems with multiple end points or multiple possible start points. A literature review covering existing MOACO algorithms and the Ant Colony algorithms they are derived from is presented. Two case studies are developed to demonstrate the performance of the algorithm under different infrastructure routing scenarios. In the first case study the algorithm is implemented into the Ice Road Planning module within the North Slope Decision Support System (NSDSS). Using this ice road planning module a case study is developed of the White Hills Ice road to test the performance of the algorithm versus an as-built road. In the second case study, the algorithm is applied to a raw water transmission routing problem in the Region C planning zone of Texas. For both case studies the algorithm produces a set of results which are similar to the preliminary designs. By successfully applying the algorithm to two separate case studies the suitability of the algorithm to different types of infrastructure routing problems is demonstrated.
41
Chang, YunChien, and 章允建. "Ant Colony Algorithm Applied for Optimizing TFT-LCD Material Planning." Thesis, 2005. http://ndltd.ncl.edu.tw/handle/72088110095600003247.
Full textAbstract:
碩士<br>元智大學<br>資訊管理研究所<br>93<br>TFT-LCD is now on developing and it is one of the focal industries in Taiwan. Generation technology has advanced all the time. In order to reduce the unit cost, the TFT-LCD industries need to invest much money in inventing new technology, and expanding factory building, therefore it must take orders in mass production to fill up the cost, and then to earn profits. In the material planning process of module process, planning good or not will influence the quantity of finished products. For this reason, we need a decision model to make TFT-LCD material planning optimal which enables the quantity of production more under much restriction. Today, the decision model in the TFT-LCD industries is APS, but it still insufficient. Our research will be based on Ant Colony Optimization algorithm (ACO) to develop a optimal decision model in planning material, and use Taguchi Method in parameters design to make this model better. In the experiment, the computational results on test problems will be in comparison with Genetic Algorithm (GA) and greedy method, and then could solve the problem of material planning and allocation efficiently.
42
Hung, Kuo-Sheng, and 洪國勝. "An Entropy-Based Ant Colony Optimization Algorithm forTraveling Salesman Problems." Thesis, 2006. http://ndltd.ncl.edu.tw/handle/84525576238430302287.
Full textAbstract:
碩士<br>國立臺灣科技大學<br>電機工程系<br>94<br>In this thesis, we propose a dynamic updating rule for the heuristic parameters based on entropy to improve the efficiency of ant colony optimization (ACO) in solving the traveling salesman problem (TSP). Our algorithm also proposes to use a lower pheromone trail bound. TSP problems are known as NP-hard problems, which very hard find an optimal solution in a short time. ACO is a new metaheuristic algorithm that has been successfully applied to solve combinatorial optimization problems. ACO algorithm is biologically inspired by one aspect of the behavior of real ants, and it simulates the process of ants searching for food. When ants forage the food, they depend on the amount of pheromone deposited on the traverse path. Although ACO algorithm has very good search capability in optimization problems, it still has some drawbacks such as stagnation behavior, needing longer computing time, and premature convergence. These drawbacks will be more evident when the complexities of the considered problems increase. In our experimental results, the proposed method can avoid stagnation behavior and premature convergence. It can also be found that the proposed dynamic update of the heuristic parameters based on entropy will generate high quality tours and it can guide ants toward the effective solutions space in the initial search stages.
43
Liao, Yi-Cheng, and 廖益成. "Solving Multi-Floor Layout Problem by Ant Colony Optimization algorithm." Thesis, 2005. http://ndltd.ncl.edu.tw/handle/28408193484796960799.
Full textAbstract:
碩士<br>國立勤益技術學院<br>工業工程與管理系<br>93<br>The multi-floor layout problem is an extension of the single-floor layout problem. There has flow problem in the same floor or different floors. The analysis manner is more complex to NP-COMPLETE problem. If we have more equipment or departments that the best solving is timing going to exponential function or factorial function to increase progressively. Therefor when the departments number more bigger at the same time then this best solving way is not the best function we had. That is way the analytic manner is much more complex.
In 1991, (Ant Colony Optimization algorithm, ACO) from the scholar of Marco Dorigo who propose it. His improvement is using the ant which is looking for the food that has residues pheromone on the wayside. Also has many search ways and speed contractions peculiarity. Hereby this investigation is trying to solve multi-floor layout problem by Ant Colony Optimization algorithm.
This is not only build the evaluate sort but also using ACO for solving the problem. If evolves one has Multi-Floor Layout problem-ACO. The article MFLP-ACO control parameter and create lots of standard level. It had less cost and time to get the right factor to make up composition for the prevailing illume to solve and find the way.
44
Yeh, Cheng-Ting, and 葉建廷. "A Novel Fuzzy Modeling Method Based on Ant Colony Algorithm." Thesis, 2014. http://ndltd.ncl.edu.tw/handle/vj9z37.
Full textAbstract:
碩士<br>國立臺北科技大學<br>自動化科技研究所<br>102<br>In this thesis, a novel modeling method for Takagi-Sugeno (T-S) fuzzy model is proposed. At first, the sample data points are classified by alternative fuzzy c-means (AFCM) algorithm. Based on Xie-Beni index criterion, the optimal numbers of cluster can be obtained and then the numbers of cluster numbers are set as the rule numbers of fuzzy. In addition, by utilizing fuzzy c-regression model (FCRM) algorithm several linear subsystems can be divided from the unknown system. By examining the fuzzy relationship, ant colony optimization (ACO) algorithm and fuzzy c-regression model (FCRM) algorithm are adopted to find the fuzzy relationship between data points and linear subsystems, and construct the initial value of the fuzzy rule parameters. Moreover, the weight recursive least squares (WLRS) method is utilized to obtain the initial premise variables of each fuzzy rule for each linear subsystem and establish the T-S fuzzy model. Lastly, some examples are given to illustrate that our modeling method can provide the better approximation results than some studies.
45
Chi, Shih-Shih, and 紀詩詩. "Dynamic Path Planning Based on Adaptable Ant Colony Optimization Algorithm." Thesis, 2017. http://ndltd.ncl.edu.tw/handle/6xp5k2.
Full textAbstract:
碩士<br>中華大學<br>資訊工程學系<br>105<br>In recent years, many tourist attractions have suffered heavy traffic problems during vacations or holidays due to the convenience of transportation and the growing popularity of leisure activities. Traffic is overwhelming in attraction areas during almost every rush hour, as many cars converge from all directions to cause traffic jams.
However, according to common experience, different recreational attractions are not necessary located along a single route in a given tourist area. If all the recreational attractions in a given area are arranged in sequence based on the order visited, visitors may suffer schedule delays due to traffic problems occurring in early spots of this sequence, as tourists do not always visit attractions in the same order.
This thesis presents an Adaptable Ant Colony Optimization Algorithm(AACO) to solve the traffic jam problems. This algorithm can determine the priority of visitation to different attractions, using travel time and the distance between two attractions to determine the optimal path arrangement taken by each visitor. Every attraction may only be passed through once. The method is then implemented again to determine the next attraction, and so forth, until all attractions have been visited.
This thesis combines a consideration of leisure itineraries and the practical operation of the route planning model in order to establish a dynamic planning system that instantaneously provides optimal route information. The goal is to create a system that considers visitor preferences, and uses Google Maps API to assist in tailoring travel routes to the individual consumer.
The experimental results showed that this research can plan the route according to the desire degree of tourists to scenic spots in a short period. The sum of the desired values calculated by this algorithm is greater than that of the original ant optimization algorithm and the improved ant optimization algorithm. It is because the route selected is calculated based on the attraction desire priority. The results show that the mean total desired value of improved ant algorithm is 25.53% higher than that of the traditional ant optimization algorithm, the average travel time is reduced by 34.32%, and the average computing time is reduced by 25.53%. It can be seen from the data that the algorithm can effectively improve the travel route planning problem.
46
Liao, Cheng-Chi, and 廖錚圻. "An Ant Colony Optimization Algorithm for Scheduling in Agile Manufacturing." Thesis, 2006. http://ndltd.ncl.edu.tw/handle/u6j4qe.
Full textAbstract:
碩士<br>國立臺灣科技大學<br>工業管理系<br>94<br>Producing customized products in a short time at low cost is one of the goals of agile manufacturing. To achieve this goal, an assembly-driven differentiation strategy has been proposed in the agile manufacturing literature. In this thesis, we address a manufacturing system that applies the assembly-driven differentiation strategy. The system consists of machining and assembly stages, where there is a single machine at the machining stage and multiple identical assembly stations at the assembly stage. An ant colony optimization (ACO) algorithm is developed for solving the scheduling problem of determining the sequence of parts to be produced in the system so as to minimize the maximum completion time (or makespan). The ACO algorithm uses a new dispatching rule as the heuristic desirability and variable neighborhood search as the local search to make it more efficient and effective. To evaluate the performance of heuristic algorithms, a branch-and-bound procedure is proposed for deriving the optimal solution to the problem. Computational results show that the proposed ACO algorithm is superior to the existing algorithm, not only improving the performance but also decreasing the computation time.
47
Lee, Chain-Hau, and 李乾豪. "Incorporating Psychology Model of Emotion into Ant Colony Optimization Algorithm." Thesis, 2007. http://ndltd.ncl.edu.tw/handle/20296987220856216150.
Full textAbstract:
碩士<br>義守大學<br>資訊管理學系碩士班<br>95<br>This thesis presents a modification of the ant colony optimization algorithm (ACO) intended to introduce psychology factor of emotion into the algorithm. ACO is a combinational optimization computation inspired by the study of the ant colonies’ behavior. The combinational optimization process is based on the pheromone model and solution construction process. It remains a computational bottleneck in ACO algorithm. Here we define two emotions that ants could have, positive and negative, and correspond to two reaction to perception in path selection respectively. And we determine ant’s emotion at random in order to make the emotional system more unpredictable. For avoiding premature convergence, it allows Emotional Ant Colony Optimization (EACO) to continue search for global optimization in difficult optimization problems, reaching better solutions than ACO with a faster convergence speed. According to the experiment results of traveling salesman problem with various parameter settings and different iterations, the EACO can provide greater efficiency and satisfactory accuracy than ACO.
48
CHEN, Yu-Tsan, and 陳煜璨. "Pathfinding Using Ant Colony Algorithm in Game with 2D Topography." Thesis, 2012. http://ndltd.ncl.edu.tw/handle/18498830218260540681.
Full textAbstract:
碩士<br>育達商業科技大學<br>資訊管理所<br>100<br>Pathfinding is a basic artificial intelligence technique in role-playing game (RPG) and other types of games. The character on the screen will automatically cross the barrier and reach the destination when players click the point on the map. This is what Pathfinding doing. However, most design of Pathfinding in games is too simple. Some of Pathfinding just go straight forward from current position to the destination. This study is trying to use Ant Colony Algorithm in Pathfinding to improve the effectiveness of goal seeking in games.
This research topic is "how to find the destination in the build environment, and then quickly gather the characters dispersed in the environment". Therefore, we will use Ant Colony Algorithm to solving Pathfinding problem. It will send a message to all characters dispersed in the environment when someone fined the destination, and the characters will approach to the destination quickly according to the message. First, I’ll do the test of this pathfinding method on the map which I create. Then, add variously parameter and random changing topography. Finally, we’ll get the best route of the map.
49
Li, Shin-Hung, and 李欣鴻. "A Bidirectional Ant Colony Optimization Algorithm for Cloud Load Balancing." Thesis, 2013. http://ndltd.ncl.edu.tw/handle/92027290136220313256.
Full textAbstract:
碩士<br>輔仁大學<br>資訊工程學系碩士班<br>101<br>The cloud computing is a technology that provides convenient, on demand network access to share computing resources. Although the cloud computing has many advantages, there exist some issues to be resolved such as load balancing. Load balancing is a technique and provides the mechanism to allocate an appropriate workload for each server in the system, and to maintain the stability if a node in the system fails. The Cloud environment is dynamic where tasks can be started and finished anytime. A dynamic response to the dynamic environment is required to consider, for example: how to effectively deal with a sudden and massive influx of tasks. Thus, our main goal of this thesis is to propose an effective scheduling for task allocation in Cloud environment. In recent years, some researches have used the Ant Colony Optimization (ACO) to resolve the load balancing problem in Cloud environment. In this thesis, we modify Li’s and Nishant’s methods to improve the ACO algorithm. Experiment results show that the proposed method indeed provides an efficient ACO to solve the load balancing problem in the Cloud.
50
Jiang, Guan-Cing, and 江冠慶. "Ant Colony Optimization Algorithm for Polymorphic Job Shop Scheduling Problems." Thesis, 2013. http://ndltd.ncl.edu.tw/handle/49033478860086432729.
Full textAbstract:
碩士<br>國立臺灣大學<br>工業工程學研究所<br>101<br>This research defines a scheduling problem called “Polymorphic Job Shop Scheduling Problem” (PJSP). PJSP is a new problem originated from “Job Shop Scheduling Problem” (JSP). Different from JSP, many real world scheduling conditions are considered in PJSP. Though our literature survey shows none of the transformed JSP problems developed in recent studies are similar to PJSP, both JSP and PJSP are NP hard problems. In this research, a method based on “Ant Colony Optimization Algorithm” (ACO) to solve PJSP is developed and named as “Ant Colony Optimization Algorithm for Polymorphic Job Shop Scheduling Problem” (ACO4PJSP). In this study, two scheduling examples from software testing companies are tested by ACO4PJSP, proving that our developed ACO4PJSP is capable for solving two different scheduling examples based on different objectives and many scheduling conditions.