Dissertations / Theses on the topic 'Ant Colony Clustering'

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.

Submitted by (ana.araujo@ufrpe.br) on 2016-07-06T19:39:45Z No. of bitstreams: 1 Jose Domingos Albuquerque Aguiar.pdf: 818824 bytes, checksum: 7c15525f356ca47ab36ddd8ac61ebd31 (MD5)
Made available in DSpace on 2016-07-06T19:39:45Z (GMT). No. of bitstreams: 1 Jose Domingos Albuquerque Aguiar.pdf: 818824 bytes, checksum: 7c15525f356ca47ab36ddd8ac61ebd31 (MD5) Previous issue date: 2008-02-29
In this work we present a new data cluster algorithm based on social behavior of ants which applies Monte Carlo simulations in selecting the maximum path length of the ants. We compare the performance of the new method with the popular k-means and another algorithm also inspired by the social ant behavior. For the comparative study we employed three data sets from the real world, three deterministic artificial data sets and two random generated data sets, yielding a total of eight data sets. We find that the new algorithm outperforms the others in all studied cases but one. We also address the issue concerning about the right number of groups in a particular data set. Our results show that the proposed algorithm yields a good estimate for the right number of groups present in the data set.
Esta dissertação apresenta um algoritmo inédito de agrupamento de dados que têm como fundamentos o método de Monte Carlo e uma heurística que se baseia no comportamento social das formigas, conhecida como Otimização por Colônias de Formigas. Neste trabalho realizou-se um estudo comparativo do novo algoritmo com outros dois algoritmos de agrupamentos de dados. O primeiro algoritmo é o KMédias que é muito conhecido entre os pesquisadores. O segundo é um algoritmo que utiliza a Otimização por Colônias de Formigas juntamente com um híbrido de outros métodos de otimização. Para implementação desse estudo comparativo utilizaram-se oito conjuntos de dados sendo três conjuntos de dados reais, dois artificiais gerados deterministicamente e três artificiais gerados aleatoriamente. Os resultados do estudo comparativo demonstram que o novo algoritmo identifica padrões nas massas de dados, com desempenho igual ou superior aos outros dois algoritmos avaliados. Neste trabalho investigou-se também a capacidade do novo algoritmo em identificar o número de grupos existentes nos conjuntos dados. Os resultados dessa investigação mostram que o novo algoritmo é capaz de identificar o de número provável de grupos existentes dentro do conjunto de dados.

In this dissertation, we consider the clustering problem in data sets with unknown number of clusters having arbitrary shapes, intracluster and intercluster density variations. We introduce a clustering methodology which is composed of three methods that ensures extraction of local density and connectivity properties, data set reduction, and clustering. The first method constructs a unique neighborhood for each data point using the connectivity and density relations among the points based upon the graph theoretical concepts, mainly Gabriel Graphs. Neighborhoods subsequently connected form subclusters (closures) which constitute the skeleton of the clusters. In the second method, the external shape concept in computational geometry is adapted for data set reduction and cluster visualization. This method extracts the external shape of a non-convex n-dimensional data set using Delaunay triangulation. In the third method, we inquire the applicability of Swarm Intelligence to clustering using Ant Colony Optimization (ACO). Ants explore the data set so that the clusters are detected using density break-offs, connectivity and distance information. The proposed ACO-based algorithm uses the outputs of the neighborhood construction (NC) and the external shape formation. In addition, we propose a three-phase clustering algorithm that consists of NC, outlier detection and merging phases. We test the strengths and the weaknesses of the proposed approaches by extensive experimentation with data sets borrowed from literature and generated in a controlled manner. NC is found to be effective for arbitrary shaped clusters, intracluster and intercluster density variations. The external shape formation algorithm achieves significant reductions for convex clusters. The ACO-based and the three-phase clustering algorithms have promising results for the data sets having well-separated clusters.

Philosophiae Doctor - PhD
Wireless sensor networks (WSNs) have become a popular research area that is widely gaining the attraction from both the research and the practitioner communities due to their wide area of applications. These applications include real-time sensing for audio delivery, imaging, video streaming, and remote monitoring with positive impact in many fields such as precision agriculture, ubiquitous healthcare, environment protection, smart cities and many other fields. While WSNs are aimed to constantly handle more intricate functions such as intelligent computation, automatic transmissions, and in-network processing, such capabilities are constrained by their limited processing capability and memory footprint as well as the need for the sensor batteries to be cautiously consumed in order to extend their lifetime. This thesis revisits the issue of the energy efficiency in sensor networks by proposing a novel clustering approach for routing the sensor readings in wireless sensor networks. The main contribution of this dissertation is to 1) propose corrective measures to the traditional energy model adopted in current sensor networks simulations that erroneously discount both the role played by each node, the sensor node capability and fabric and 2) apply these measures to a novel hierarchical routing architecture aiming at maximizing sensor networks lifetime. We propose three energy models for sensor network: a) a service-aware model that account for the specific role played by each node in a sensor network b) a sensor-aware model and c) load-balancing energy model that accounts for the sensor node fabric and its energy footprint. These two models are complemented by a load balancing model structured to balance energy consumption on the network of cluster heads that forms the backbone for any cluster-based hierarchical sensor network. We present two novel approaches for clustering the nodes of a hierarchical sensor network: a) a distanceaware clustering where nodes are clustered based on their distance and the residual energy and b) a service-aware clustering where the nodes of a sensor network are clustered according to their service offered to the network and their residual energy. These approaches are implemented into a family of routing protocols referred to as EOCIT (Energy Optimization using Clustering Techniques) which combines sensor node energy location and service awareness to achieve good network performance. Finally, building upon the Ant Colony Optimization System (ACS), Multipath Routing protocol based on Ant Colony Optimization approach for Wireless Sensor Networks (MRACO) is proposed as a novel multipath routing protocol that finds energy efficient routing paths for sensor readings dissemination from the cluster heads to the sink/base station of a hierarchical sensor network. Our simulation results reveal the relative efficiency of the newly proposed approaches compared to selected related routing protocols in terms of sensor network lifetime maximization.

Many real-world optimisation problems are discrete in nature. Although recent rapid developments in computer technologies are steadily increasing the speed of computations, the size of an instance of a hard discrete optimisation problem solvable in prescribed time does not increase linearly with the computer speed. This calls for the development of new solution methodologies for solving larger instances in shorter time. Furthermore, large instances of discrete optimisation problems are normally impossible to solve to optimality within a reasonable computational time/space and can only be tackled with a heuristic approach. In this thesis the development of so called matheuristics, the heuristics which are based on the mathematical formulation of the problem, is studied and employed within the variable neighbourhood search framework. Some new variants of the variable neighbourhood searchmetaheuristic itself are suggested, which naturally emerge from exploiting the information from the mathematical programming formulation of the problem. However, those variants may also be applied to problems described by the combinatorial formulation. A unifying perspective on modern advances in local search-based metaheuristics, a so called hyper-reactive approach, is also proposed. Two NP-hard discrete optimisation problems are considered: 0-1 mixed integer programming and clustering with application to colour image quantisation. Several new heuristics for 0-1 mixed integer programming problem are developed, based on the principle of variable neighbourhood search. One set of proposed heuristics consists of improvement heuristics, which attempt to find high-quality near-optimal solutions starting from a given feasible solution. Another set consists of constructive heuristics, which attempt to find initial feasible solutions for 0-1 mixed integer programs. Finally, some variable neighbourhood search based clustering techniques are applied for solving the colour image quantisation problem. All new methods presented are compared to other algorithms recommended in literature and a comprehensive performance analysis is provided. Computational results show that the methods proposed either outperform the existing state-of-the-art methods for the problems observed, or provide comparable results. The theory and algorithms presented in this thesis indicate that hybridisation of the CPLEX MIP solver and the VNS metaheuristic can be very effective for solving large instances of the 0-1 mixed integer programming problem. More generally, the results presented in this thesis suggest that hybridisation of exact (commercial) integer programming solvers and some metaheuristic methods is of high interest and such combinations deserve further practical and theoretical investigation. Results also show that VNS can be successfully applied to solving a colour image quantisation problem.

In this Thesis we attempted to answer to some of the fundamental questions concerning galaxy evolution. In particular when and how galaxies got their present-day stellar content and how this process depends on their mass. In order to address this key issues, we developed a new semi-analytic model of galaxy formation (GECO, Galaxy Evolution COde), that couples a Monte Carlo representation of the hierarchical clustering of dark matter haloes with analytic recipes for the baryonic physics, such as the cooling of the gas, the star formation, the feedback from SN and AGN. We set the model on observations in the local universe and then we predict and compare results for the high redshift galaxies.

This thesis proposes a novel approach to extracting pose information from image sequences. Current state of the art techniques focus exclusively on the image space occupied by the body for pose and action recognition. The method proposed here, however, focuses on the negative spaces: the areas surrounding the individual. This has resulted in the colour-coded negative space approach, an image preprocessing step that circumvents the need for complicated model fitting or template matching methods. The approach can be described as follows: negative spaces surrounding the human silhouette are extracted using horizontal and vertical scanning processes. These negative space areas are more numerous, and undergo more radical changes in shape than the single area occupied by the figure of the person performing an action. The colour-coded negative space representation is formed using the four binary images produced by the scanning processes. Features are then extracted from the colour-coded images. These are based on the percentage of area occupied by distinct coloured regions as well as the bounding box proportions. Pose clusters are identified using feedback from an independent action set. Subsequent images are classified using a simple Euclidean distance measure. An image sequence is thus temporally segmented into its corresponding pose representations. Action recognition simply becomes the detection of a temporally ordered sequence of poses that characterises the action. The method is purely vision-based, utilising monocular images with no need for body markers or special clothing. Two datasets were constructed using several actors performing different poses and actions. Some of these actions included actors waving their arms, sitting down or kicking a leg. These actions were recorded against a monochrome background to simplify the segmentation of the actors from the background. The actions were then recorded on DV cam and digitised into a data base. The silhouette images from these actions were isolated and placed in a frame or bounding box. The next step was to highlight the negative spaces using a directional scanning method. This scanning method colour-codes the negative spaces of each action. What became immediately apparent is that very distinctive colour patterns formed for different actions. To emphasise the action, different colours were allocated to negative spaces surrounding the image. For example, the space between the legs of an actor standing in a T - pose with legs apart would be allocated yellow, while the space below the arms were allocated different shades of green. The space surrounding the head would be different shades of purple. During an action when the actor moves one leg up in a kicking fashion, the yellow colour would increase. Inversely, when the actor closes his legs and puts them together, the yellow colour filling the negative space would decrease substantially. What also became apparent is that these coloured negative spaces are interdependent and that they influence each other during the course of an action. For example, when an actor lifts one of his legs, increasing the yellow-coded negative space, the green space between that leg and the arm decreases. This interrelationship between colours hold true for all poses and actions as presented in this thesis. In terms of pose recognition, it is significant that these colour coded negative spaces and the way the change during an action or a movement are substantial and instantly recognisable. Compare for example, looking at someone lifting an arm as opposed to seeing a vast negative space changing shape. In a controlled research environment, several actors were instructed to perform a number of different actions. After colour coding the negative spaces, it became apparent that every action can be recognised by a unique colour coded pattern. The challenge is to ascribe a numerical presentation, a mathematical quotation, to extract the essence of what is so visually apparent. The essence of pose recognition and it's measurability lies in the relationship between the colours in these negative spaces and how they impact on each other during a pose or an action. The simplest way of measuring this relationship is by calculating the percentage of each colour present during an action. These calculated percentages become the basis of pose and action recognition. By plotting these percentages on a graph confirms that the essence of these different actions and poses can in fact been captured and recognised. Despite variations in these traces caused by time differences, personal appearance and mannerisms, what emerged is a clear recognisable pattern that can be married to an action or different parts of an action. 7 Actors might lift their left leg, some slightly higher than others, some slower than others and these variations in terms of colour percentages would be recorded as a trace, but there would be very specific stages during the action where the traces would correspond, making the action recognisable.In conclusion, using negative space as a tool in human pose and tracking recognition presents an exiting research avenue because it is influenced less by variations such as difference in personal appearance and changes in the angle of observation. This approach is also simplistic and does not rely on complicated models and templates

碩士
逢甲大學
交通工程與管理所
92
Cluster analysis is a traditional method of multivariate statistic classification. Cluster analysis is mainly to group all objects into several mutually exclusive clusters in order to make the degree of homogeneity within cluster and the degree of heterogeneity among clusters as high as possible. Cluster analysis is widely applied to many fields, such as pattern recognition, data analysis, image processing and market research. However, Cluster analysis is rapidly becoming computationally intractable as problem scale increases, because of the combinatorial character of the method. It has been proven that cluster analysis becomes an NP-hard problem when the number of clusters exceeds 3. Even the best algorithms developed for some specific objective functions, exhibit complexities of O(N3logN) or O(N3), leaving much room for improvement. Therefore, lots of heuristic algorithms have been proposed for cluster analysis. The performance of ant colony system developed by Dorigo et al. in 1996 based on the behaviors of nature ants out-searching for food has been proven in solving NP-hard and NP-complete combinatorial optimization problems, such as traveling salesman problem, vehicle routing problem, and quadratic assignment problem. This study attempts to propose and validate a clustering algorithm based on ant colony system, which is called ant-based clustering algorithm (ACA). For validating the performance of proposed algorithm in different scale of problems, three different scales of two-dimension data sets have been produced randomly, including small scale (10 samples), medium scale (50 samples) and large scale (100 samples). The comparison is also conducted by comparing its performance with that of agglomerative method, k-means method, and genetic clustering algorithm (GCA). In small scale problem, in addition to agglomerative method, all other three clustering algorithms can solve the optimum solution which is solved by the total enumeration method. In the medium and large scale problems with different number of clusters (3, 5, 7, 9 clusters), ACA statistically significantly outperforms than any other algorithms by 1.04%∼53.42%. GCA performs better than two statistic cluster analysis methods and agglomerative method have worst performance. However, no remarkable difference in the robustness, represented by standard error, has been observed for these four methods. In the case study, a total of 100 accident records data sets have been selected and 6 clustering variables which have significant influence on determining accident responsibility are selected by chi-square test. The results show that ACA still have the best performance in clustering this accidents data into 3 and 5 clusters.

碩士
元智大學
工業工程與管理學系
92
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.

碩士
大同大學
資訊經營學系(所)
93
Cellular manufacturing, which requires an effective parts clustering method to start up the manufacturing cell design, is the premier application of group technology. Cluster analysis, clustering similar parts to be part families by working with similarity coefficients specially designed, is one of the methods in common use. Cluster analysis is divided into hierarchical clustering method and nonhierarchical clustering method, but chaining effect often appeared in hierarchical clustering method and setting requirement of part family numbers for nonhierarchical clustering method have limited the applications of cluster analysis. Therefore, based on the recognition system of artificial ants, a new parts clustering algorithm is proposed in our study to solve the clustering problem. The proposed algorithm is using the ability of unsupervised learning of artificial ants to gradually build up the comprehensive recognition and naturally form the part clusters with high similarities. Furthermore, this algorithm also uses merging rules to decrease the part clusters and fit the designated cluster numbers. Due to the features like collective behaviour and randomization from ant clustering model, this algorithm allows re-clustering of the mis-clustered parts and accordingly eliminates the effect of exceptional parts. This algorithm has been developed to be a machine cell formation system; moreover, 17 reported cases have been tested and evaluated by clustering performance measures. The results coming from those 17 cases, which contain various complications and sizes, all revealed effective cell formulation that indicates the performance of this algorithm at parts clustering.

Woo Kwan Ho.
Thesis (M.Phil.)--Chinese University of Hong Kong, 2005.
Includes bibliographical references (leaves 148-155).
Abstracts in English and Chinese.
Contents --- p.ii
Abstract --- p.iv
Acknowledgements --- p.vii
List of Figures --- p.viii
List of Tables --- p.x
Chapter Chapter 1 --- Introduction --- p.1
Chapter Chapter 2 --- Literature Reviews --- p.7
Chapter 2.1 --- Block Clustering --- p.7
Chapter 2.2 --- Clustering XML by structure --- p.10
Chapter 2.2.1 --- Definition of XML schematic information --- p.10
Chapter 2.2.2 --- Identification of XML schematic information --- p.12
Chapter Chapter 3 --- Bi-Tour Ant Colony Optimization for diagonal clustering --- p.15
Chapter 3.1 --- Motivation --- p.15
Chapter 3.2 --- Framework of Bi-Tour Ant Colony Algorithm --- p.21
Chapter 3.3 --- Re-order of the data matrix in BTACO clustering method --- p.27
Chapter 3.3.1 --- Review of Ant Colony Optimization --- p.29
Chapter 3.3.2 --- Bi-Tour Ant Colony Optimization --- p.36
Chapter 3.4 --- Determination of partitioning scheme --- p.44
Chapter 3.4.1 --- Weighed Sum of Error (WSE) --- p.48
Chapter 3.4.2 --- Materialization of partitioning scheme via hypothetic matrix --- p.50
Chapter 3.4.3 --- Search of best-fit hypothetic matrix --- p.52
Chapter 3.4.4 --- Dynamic programming approach --- p.53
Chapter 3.4.5 --- Heuristic partitioning approach --- p.57
Chapter 3.5 --- Experimental Study --- p.62
Chapter 3.5.1 --- Data set --- p.63
Chapter 3.5.2 --- Study on DP Approach and HP Approach --- p.65
Chapter 3.5.3 --- Study on parameter settings --- p.69
Chapter 3.5.4 --- Comparison with GA-based & hierarchical clustering methods --- p.81
Chapter 3.6 --- Chapter conclusion --- p.90
Chapter Chapter 4 --- Application of BTACO-based clustering in XML database system --- p.93
Chapter 4.1 --- Introduction --- p.93
Chapter 4.2 --- Overview of normalization and vertical partitioning in relational DB design --- p.95
Chapter 4.2.1 --- Normalization of relational models in database design --- p.95
Chapter 4.2.2 --- Vertical partitioning in database design --- p.98
Chapter 4.3 --- Clustering XML documents --- p.100
Chapter 4.4 --- Proposed approach using BTACO-based clustering --- p.103
Chapter 4.4.1 --- Clustering XML documents by structure --- p.103
Chapter 4.4.2 --- Clustering XML documents by user transaction patterns --- p.109
Chapter 4.4.3 --- Implementation of Query Manager for our experimental study --- p.114
Chapter 4.5 --- Experimental Study --- p.118
Chapter 4.5.1 --- Experimental Study on the clustering by structure --- p.118
Chapter 4.5.2 --- Experimental Study on the clustering by user access patterns --- p.133
Chapter 4.6 --- Chapter conclusion --- p.141
Chapter Chapter 5 --- Conclusions --- p.143
Chapter 5.1 --- Contributions --- p.144
Chapter 5.2 --- Future works --- p.146
Bibliography --- p.148
Appendix I --- p.156
Appendix II --- p.168
Index tables for Profile A --- p.168
Index tables for Profile B --- p.171
Appendix III --- p.174

碩士
國立中山大學
資訊工程學系研究所
99
This thesis presents a novel algorithm called ant colony optimization with dual pheromone tables (ACODPT) for improving the quality of ant colony optimization (ACO). The proposed algorithm works by adding a so-called “negative” pheromone table to ACO to avoid the problem of ACO easily falling into local optima. By using the “negative” pheromone table to eliminate the most impossible path to search for the new solution, the probability of selecting the remaining paths is increased, and so is the quality. To evaluate the performance of the proposed algorithm, ACODPT is compared with several state-of-the-art algorithms in solving the clustering problem. The experimental results show that the proposed algorithm can eventually prevent ACO from falling into local optima in the early iterations, thus providing a better result than the other algorithms in many cases.

In this thesis, I introduce two new algorithms: Ant Brood Clustering-Intelligent Ants (ABC-INTE) and Ant Brood Clustering-Polymorphic Ants (ABC-POLY) for the graph clustering problem. ABC-INTE uses techniques such as hopping ants, relaxed drop function, ants with memories, stagnation control, and addition of k-means cluster retrieval process, as an improvement of the basic ABC-KLS algorithm. ABC-POLY uses two types of ants, inspired by the division of labour between the major and minor ants in Pheidole genus, as an improvement of ABC-INTE. For comparison purpose, I also implement MMAS, an ACO clustering algorithm. When tested on the benchmark networks, ABC-POLY outperforms or achieves the same modularity values as MMAS and ABC-INTE on 7 out of 10 networks and is robust against different graphs. In practice, the speed of ABC-POLY is at least 10 times faster than MMAS, making it a scalable algorithm compared to MMAS. ABC-POLY also outputs a direct visual representation of the natural clusters on the graph that is appealing to human observation. This thesis opens an interesting research topic to apply polymorphic ants for graph clustering in the ABC-POLY algorithm. The distributive and self-organization nature of ABC-POLY makes it a candidate for analyzing clusters in more complex and dynamic graphs.
May 2016

碩士
南華大學
資訊管理學系碩士班
97
Data mining is an important technique to extract useful knowledge from a set of raw data. The managers can exploit the mining knowledge to make right decisions. However, missing data significantly distort data mining results. Therefore, data preprocessing of missing values becomes extremely critical in successful data mining. Data clustering techniques is the partitioning of a dataset into clusters so that the data records in each cluster possess common characteristics. The shared characteristics can be utilized to predict the missing values. In this study, we propose an attribute values partitioning technique to preserve the relationships between attributes for estimating missing values. On the other hand, ant colony optimization (ACO) algorithm was recently proposed by few researchers to solve data clustering problems. In this study, we propose an improved ACO clustering approach, and employ the ant clustering as a basis to estimate the missing data. Furthermore, we integrate the attribute values partitioning with the ant clustering techniques to improve the estimation performance. Effectiveness of the proposed approaches is demonstrated on four datasets for four different rates of missing data. The empirical evaluation shows the improved ant clustering algorithm outperforms the previous methods in clustering quality, and the integrated missing data processing approach provides competitive results or performs well compared with the existing methods.

碩士
國立高雄第一科技大學
資訊管理所
98
Traditional Ant Colony Optimization (ACO) was proposed to solve discrete optimization problems. Recently continuous ACO represented as “ACOR” was developed to solve the continuous optimization problems. This study suggests a group-based ACOR (GACO) with communication strategy. The ant colony is divided into several subgroups and each subgroup communicates with each other. Additionally, each subgroup has different parameter settings with diversity to improve performance in searching optimal solution. We applied the GACO in the data clustering. Three types of communication strategies are tested in this study as follows：(I) each subgroup exchange its best 25% ants in sequence, (II) 7.5% best ants are collected from each subgroup, and they are sorted and assigned back to each subgroup uniformly, (III) combine strategy I and II in turn. Experimental results using the public UCI datasets show that (1) the performance of GACO with communication strategy III is better than that of the other two communication strategies, (2) the performance of GACO with diversity is better than that of the non-diversity GACO, and (3) the performance of GACO with communication strategy III is better than that of traditional ACOR and K-Mean.

碩士
國立屏東科技大學
資訊管理系
95
With the progress of information technology, business models change rapidly. The models shift from shopping in physical stores to shopping on the Internet and products are delivered to customers by logistic agencies. Logistic agencies put much emphasis on delivery cost because it relates significantly to their competitive advantage. Vehicle routing problem (VRP) focuses on distribution problems about designing vehicle routes to serve those customers, and it aims to reduce the delivery cost and deliver products to customers correctly and quickly. VRP is also a NP-Complete problem. In this thesis, we propose a new clustering concept for solving VRP and the algorithm is called Clustering-based Ant Colony Optimization (CACO). We construct preference paths by simulating ant’s ways of seeking for food to solve Vehicle Routing Problem under Capacity (CVRP). First, nodes which form smallest triangle will be combined as initial paths. Second, we implement ACO as a core approach for determine optimal routes and 2-opt exchange is used to search optimal route.

碩士
國立高雄第一科技大學
資訊管理所
98
Ant Colony Optimization (ACO) and Particle Swarm Optimization (PSO) are two popular algorithms in swarm intelligence. Traditional ACO was proposed to solve discrete optimization problems. Recently continuous ACO represented as “ACO_R” is developed to solve the continuous optimization problems. Although ACO_R is a new approach in solving continuous problems, it may trap into the local optimal. This study incorporates PSO with〖 ACO〗_R to overcome this drawback. Four types of hybridization are proposed as follows: (1) Sequence approach, (2) Parallel approach, (3) Sequence with double size of pheromone table, (4) Global best exchange. These hybrid systems are applied to data clustering. Experimental results using simulated and public UCI datasets show that the performances of the proposed hybrid systems are better than those of the K-mean, traditional PSO and ACO_R.

碩士
國立中興大學
電機工程學系所
94
This thesis proposes a novel design method of Fuzzy Controller by Ant Colony Optimization (ACO) algorithm with Fuzzy Clustering (FC-ACOFC). The objective of FC-ACOFC is to improve both the design efficiency of fuzzy controller and control performance. Structure of FC-ACOFC, including the number of rules and fuzzy sets in each input variable, is created on-line by a newly proposed fuzzy clustering method. In contrast to conventional grid-type partition, the antecedent part of FC-ACOFC is flexibly partitioned, and the phenomenon of highly overlapped fuzzy sets is avoided. Once a new rule is generated, the consequence is selected from a list of candidate control actions by ACO. In ACO, the tour of an ant is regarded as a combination of consequent actions selected from every rule. A pheromone matrix among all candidate consequent actions is constructed and an on-line learning algorithm for heuristic value update is proposed. Searching for the best one among all consequence combinations involves using the pheromone matrix and heuristic values. To verify the performance of FC-ACOFC, simulations on nonlinear system control, water bath temperature control and chaotic system control are performed. Simulations on these problems and comparisons with other algorithms have demonstrated the performance of FC-ACOFC. The ACO used here is hardware implemented on Field Programmable Gate Array (FPGA) chip. The use of Programmable Logic Device (PLD) is more and more general in recent years, and the procedure of circuit deign is fast and elastic. Application of the ACO chip to fuzzy control a simulated water bath temperature control problem has verified the effectiveness of the designed chip.

碩士
國立臺北科技大學
工業工程與管理研究所
92
Ant colony optimization is a meta-heuristic approach successfully applied to solve hard combinatorial optimization problems. It is also feasible for clustering analysis in data mining. Many researches use ant algorithms for clustering analysis and the result is better than other heuristic methods. In order to improve the performance of the algorithm, we use the concept of artificial immune system to strengthen the ant algorithm for clustering analysis. This study proposes a two-stage method for clustering problem, the immunity-based Ant Clustering Algorithm (IACA) and the Ant Colony System-Based K-means (ACSK). IACA using the immune system and ant algorithm is an auto-clustering method which can decide the number of the clusters and its centroids. According to the initial solution of IACA, we utilize ACSK which combines the K-means algorithm with the Ant Colony System algorithm to optimize its performance. The data sets generated using the Monte Carlo simulation and a real case data are used to evaluate the efficiency and validate the feasibility of the proposed algorithms and other clustering methods including Self-Organizing Map (SOM), SOM+GA-based clustering method, Ant System-based Clustering Algorithm (ASCA), and Ant System-based Clustering Algorithm +Ant K-means Algorithm(ASCA+AK). The proposed algorithm indeed has better clustering performances and smaller total within cluster variance according to the result of the experiment.

碩士
國立臺灣大學
資訊工程學研究所
102
With the rise of the fourth generation (4G) communication standards and the growing usage of mobile computing devices, mobile ad hoc network becomes a hot topic and getting more and more attention in recent years. In this thesis, we address the clustering problem in mobile ad hoc network (MANET). Due to the convenient deployment and the flexibility for variety terrains, MANET has been widely used in various fields. Routing protocols are the most important issue of MANETs, however, it has been proved that both proactive and reactive routing schemes cannot perform well or even didn’t work in a large scale size of MANET, and clustering is the most efficient method to deal with it. Clustering leads a hierarchical structure, for each cluster a cluster head will be chosen for intra- and inter- communication. However clustering in MANET is NP-hard and needs to consider multiple objectives. In this thesis, we propose a Pareto-based ant colony optimization (ACO) algorithm to deal with this multiobjective optimization problem. We proposed a clustering matrix encoding to reflect the cluster selection and cluster formation without any bias and redundant solutions. A repair function is proposed for upgrading the quality of solutions. Apart from this, we also propose a mechanism to maintain the cluster structure for dynamic situations. The experiment results confirm that it outperforms several state-of-the-art algorithms and indicates the potential to be applied to practical use.

碩士
國立屏東科技大學
資訊管理系所
96
With the change of social attitude the ideology of consumers changes as well. More and more companies put customization into production to improve the competitiveness. Logistics has become a critical role in distribution model. In order to lower the distribution cost, this thesis focuses on how to design an effective algorithm to shorten the routing path and make the routing more efficient. This research problem is called Vehicle Routing Problem (VRP). In recent years, there are many researchers proposing different approaches to solve relevant problems by finding the optima path and reducing the time cost. This thesis proposes an algorithm based on ant colony system for obtaining minimum cost in vehicle routing problem. Furthermore, the clustering approach is applied to help for generating optima results. The experiment results show that the proposed algorithm can provide acceptable time cost and can achieve better performance than traditional ant colony system in solving vehicle routing problem.

碩士
立德大學
資訊傳播研究所
96
Nowadays, global economy falls into not prosperous bog, Taiwan economy face significant challenge, many enterprises operate difficulty even close factory close a business, unemployment rate too therefore advance。Taiwan area construct industry at experience successively many year come public department quickness with plenty of infrastructures invest and commons excessive architecture invest develop behind, already as global whole economy environmental deterioration, faces run bottleneck's awkward situation, industry stagnate extent with range much wins in already for。At present inland constructs industry WTO posterior market open with advance continent market face international competitive power at government, much hads to promote production management efficacy come decrease manpower requirement, as reaches abbreviate project time, debases cost, enhances quality increase international competitive power's aim. Constructs engineering is all construct mother, construct homework flow many already artificial machines and tools melt at many, but dissemination homework all the time exists bottleneck, greater part in advances mix concrete plant, most lies on send give member subjectivity experience judgement, lacks of systematize dissemination style。Only as subjectivity style judgement, not only can not precisely calculation dissemination time, and towards needs with oil-fired in advance mix concrete cart, at faces international oil price continual rise under situation, it operator run cost much more large increase, so in advance mixes factory if can do a effective vehicle logistic despatch governance, then can promote in advance mix factory productivity, much can debase run cost, increases gain and international competitive power, therefore this research will direct to this problem exert ant algorithm, take advantage of Visual Basic (VB) is assembling a suit of systematization Ready-Mixed Concrete dissemination administration system, as supplies decision maker make known to lower levels policy's referrence, comes make best route and in advance mix concrete cart despatch choice, much can for green energy sources finish an energy.

碩士
國立雲林科技大學
資訊管理系碩士班
99
Forecast the company''s financial crisis has been an important academic issue, aimed at the prevention of listed companies unexpected bankruptcy caused significant loss of social costs. Traditional statistical methods of forecasting models constructed by the statistical assumptions of the request are limited, and therefore derivative new algorithms by imitation of biological behavior in recent years have been proposal. In this study, first apply gray prediction for historical data and generate predictive value, compared to only consider the traditional of the cross-sectional message financial data, more vertical-section of time trend of dynamic to join consider. Second, the use of a new artificial bee colony based clustering algorithm will replace with previous clustering method to group forecast value by homogeneous. Finally, use rough set theory dealing with data fuzzy regional and deriving decision rules, and then did the classification of the predicted value. In this study, integrated gray prediction, artificial bee colony based clustering algorithms and rough set theory based on past historical data construct an enterprise''s financial crisis early-warning model. Sample of listed companies in Taiwan to extract the period of 66 to 100 years, deduct of the bankruptcy crisis is not consistent out to 57 companies, and select the scale and assets corresponding to the normal company, the final capture of these two types of each company financial data for the time window before the crisis occurred date seven-year. The empirical results show that the proposed model of early warning crisis better than other accuracy of combination model, and the highest accuracy rate of predict on the previous year.