Ant algorithms were first written about in 1991 and since then they have been applied to many problems with great success. During these years the algorithms themselves have been modified for improved performance and also been influenced by research in other fields. Since the earliest Ant algorithms, heuristics and local search have been the primary knowledge sources. This thesis asks the question "how is knowledge used in Ant algorithms?" To answer this question three Ant algorithms are implemented. The first is the Graph based Ant System (GBAS), a theoretical model not yet implemented, and the others are two influential algorithms, the Ant System and Max-Min Ant System. A comparison is undertaken to show that the theoretical model empirically models what happens in the other two algorithms. Therefore, this chapter explores whether different pheromone matrices (representing the internal knowledge) have a significant effect on the behaviour of the algorithm. It is shown that only under extreme parameter settings does the behaviour of Ant System and Max-Min Ant System differ from that of GBAS. The thesis continues by investigating how inaccurate knowledge is used when it is the heuristic that is at fault. This study reveals that Ant algorithms are not good at dealing with this information, and if they do use a heuristic they must rely on it relating valid guidance. An additional benefit of this study is that it shows heuristics may offer more control over the exploration-exploitation trade-off than is afforded by other parameters. The second point where knowledge enters the algorithm is through the local search. The thesis looks at what happens to the performance of the Ant algorithms when a local search is used and how this affects the parameters of the algorithm. It is shown that the addition of a local search method does change the behaviour of the algorithm and that the strength of the method has a strong influence on how the parameters are chosen. The final study focuses on whether Ant algorithms are effective for driving a local search method. The thesis demonstrates that these algorithms are not as effective as some simpler fixed and variable neighbourhood search methods.

Thesis (M.S.)--California Polytechnic State University, 2009. / Mode of access: Internet. Title from PDF title page; viewed on Jan. 7, 2010. Major professor: Helen Yu. "Presented to the faculty of California Polytechnic State University, San Luis Obispo." "In partial fulfillment of the requirements for the degree [of] Master of Science in Electrical Engineering." "2009." Includes bibliographical references (p. 82-83).

Thesis (Ph.D)--Aerospace Engineering, Georgia Institute of Technology, 2010. / Committee Chair: Mavris, Dimitri; Committee Member: Beeson, Don; Committee Member: Duncan, Scott; Committee Member: German, Brian; Committee Member: Kumar, Viren. Part of the SMARTech Electronic Thesis and Dissertation Collection.

In recent years, lots of research effort was spent on the integration of process planning and job-shop scheduling. Various integrated process planning and scheduling (IPPS) models and solution approaches have been proposed. The previous and existing research approaches are able to demonstrate the feasibility of implementing IPPS. However, most of them assumed that setup time is negligible or only part of the processing time. For machined parts, the setup for each operation includes workpiece loading and unloading, tool change, etc. For setup that depends only on the operation to be processed (sequence-independent), it is applicable to adopt the assumption of not considering setup in IPPS. For setup that depends on both the operation to be processed and the immediately preceding operation (sequence-dependent), it is an oversimplification to adopt such assumption. In such cases, the setup time varies with the sequence of the operations. The process plans and schedules constructed under such assumption are not realistic or not even feasible. In actual practice, therefore, the setup time should be separated from the process time in performing the IPPS functions. In this thesis, a new approach is proposed for IPPS problems with setup time consideration for machined parts. Inseparable and sequence-dependent setup requirements are added into the IPPS problems. The setup times are separated from the process times and they vary with the sequence of the operations. IPPS is regarded as NP-hard problem. With the separated consideration of setup times, it becomes even more complicated. An Ant Colony Optimization (ACO) approach is proposed to handle this complicated problem. The system is constructed under a multi-agent system (MAS). AND/OR graph is used to record the set of feasible production procedures and sequences. The ACO algorithm computes results by an autocatalytic process with the objective to minimize the makespan. Software agents called “artificial ants” traverse through the feasible routes in the graph and finally construct a schedule. A setup time parameter is added into the algorithm to influence the ants to select the process with less setup time. The approach is able to construct a feasible solution with less setup time. Experimental studies have been performed to evaluate the performance of MAS-ACO approach in solving IPPS problems with separated consideration of setup times. The experimental results show that the MAS-ACO approach can effectively handle the problem. / published_or_final_version / Industrial and Manufacturing Systems Engineering / Master / Master of Philosophy

D. Tech. Electrical Engineering. / Particle Swarm Optimisation (PSO) is based on a metaphor of social interaction such as birds flocking or fish schooling to search a space by adjusting the trajectories of individual vectors, called "particles" conceptualized as moving points in a multidimensional space. This thesis presents several algorithms/techniques to improve the PSO's global search ability. Simulation and analytical results confirm the efficiency of the proposed algorithms/techniques when compared to the other state of the art algorithms.

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

Process planning and scheduling are two important manufacturing planning functions which are traditionally performed separately and sequentially. Usually, the process plan has to be prepared first before scheduling can be performed. However, due to the complexity of manufacturing systems and the uncertainties and dynamical changes encountered in practical production, process plans and schedules may easily become inefficient or even infeasible. The concept of integrated process planning and scheduling (IPPS) has been proposed to improve the efficiency, effectiveness as well as flexibility of the respective process plan and schedule. By combining both functions together, the process plan for producing a part could be dynamically arranged in accordance with the availability of manufacturing resources and current status of the system, and its operations’ schedule could be determined concurrently. Therefore, IPPS could provide an essential solution to the dynamic process planning and scheduling problem in the practical manufacturing environment. Nevertheless, process planning and scheduling are both complex functions that depend on many factors and flexibilities in the manufacturing system, IPPS is therefore a highly complex NP-hard problem. Ant colony optimization (ACO) is a widely applied meta-heuristics, which has been proved capable of generating feasible solutions for IPPS problem in previous research. However, due to the nature of the ACO algorithm, the performance is not that favourable compared with other heuristics. This thesis presents an enhanced ACO approach for IPPS. The weaknesses and limitations of standard ACO algorithm are identified and corresponding modifications are proposed to deal with the drawbacks and improve the performance of the algorithm. The mechanism is implemented on a specifically designed multi-agent system (MAS) framework in which ants are assigned as software agents to generate solutions. First of all, the manufacturing processes of the parts are graphically formulated as a disjunctive AND/OR graph. In applying the ACO algorithm, ants are deployed to find a path on the disjunctive graph. Such an ant route indicates a corresponding solution with associated operations scheduled by the sequence of ant visit. The ACO in this thesis is enhanced with the novel node selection heuristic and pheromone update strategy. With the node selection heuristic, pheromone is deposited on the nodes as well as edges on the ant path. This is contrast to the conventional ACO algorithm that pheromone is only deposited on edges. In addition, a more reasonable strategy based on “earliest completion time” of operations are used to determine the heuristic desirability of ants, instead of the “greedy” strategy used in standard ACO, which is based on the “shortest processing time”. The approach is evaluated by a comprehensive set of problems with a full set of flexibilities, while multiple performance measurements are considered, including makespan, mean flow time, average machine utilization and CPU time, among which makespan is the major criterion. The results are compared with other approaches and encouraging improvements on solution quality could be observed. / published_or_final_version / Industrial and Manufacturing Systems Engineering / Master / Master of Philosophy

This thesis deals with robot path planning. It contains an overview of general approaches for path planning and describes methods of swarm intelligence and their application for robot path planning. This paper also contains proposals of adjustments for ant algorithms and it presents experimental results of algorithm implementation.

This dissertation presents the development of a new concept and technology exploration methodology for aerospace architectures. The methodology is based on modeling the design space by a graph, and optimizing the graph using Ant Colony Optimization. The results show that the proposed design methodology can explore more efficiently the concept and technology space of a launch vehicle architecture than traditional optimization approaches such as Genetic Algorithm and Simulated Annealing. The purpose of the method is to introduce quantitative and simultaneous exploration of concept and technology alternatives during the early phases of conceptual design. To achieve this goal, technical challenges such as expanding the size of the design space, exploring more efficiently the design options, and simultaneously considering technologies and concepts are overcome. The total number of design alternatives grows factorially with the number of concepts in the design space. Under these circumstances, the design space is difficult to explore in its totality. Considering more alternatives has been the focus of several researchers, using Genetic Algorithms and Simulated Annealing. The large number of incompatibilities between alternatives, however, limits these optimization algorithms and reduces the number of concepts or technologies that can be considered. To address these problems, a concept and technology selection methodology is developed. The methodology proposes a way to automatically generate aerospace architectures, and to model concept and technology incompatibilities by means of a graph. In conjunction with this new modeling approach, a graph-based stochastic optimization algorithm is used to efficiently explore the design space. This design methodology is applied to the simultaneous concept and technology exploration of an expendable launch vehicle architecture. This study demonstrates that the consideration of more design alternatives can help design engineers to make more informed decisions during the concept and technology selection process. Moreover, the simultaneous exploration of concepts and technologies has the potential to identify a different set of solutions than the standard approach where the technologies are explored after the concepts have initially been selected.

The purpose of this research is to develop a method for selecting the fidelity of contributing analyses in computer simulations. Model uncertainty is a significant component of result validity, yet it is neglected in most conceptual design studies. When it is considered, it is done so in only a limited fashion, and therefore brings the validity of selections made based on these results into question. Neglecting model uncertainty can potentially cause costly redesigns of concepts later in the design process or can even cause program cancellation. Rather than neglecting it, if one were to instead not only realize the model uncertainty in tools being used but also use this information to select the tools for a contributing analysis, studies could be conducted more efficiently and trust in results could be quantified. Methods for performing this are generally not rigorous or traceable, and in many cases the improvement and additional time spent performing enhanced calculations are washed out by less accurate calculations performed downstream. The intent of this research is to resolve this issue by providing a method that will minimize the amount of time spent conducting computer simulations while meeting accuracy and concept resolution requirements for results.