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.

The traditional mobile radio channel has always suffered from the detrimental effects of multipath fading. The use of multiple antennae at both ends of the wireless channel has proven to be very effective in combatting fading and enhancing the channel's spectral efficiency. To exploit the benefits offered by Multi-Input Multi-Output (MIMO) systems, both the transmitter and the receiver have to be optimally designed. In this thesis, we are concerned with the problem of receiver design for MIMO systems in a spatial multiplexing scheme. The MIMO detection problem is an NP-hard combinatorial optimization problem. Solving this problem to optimality requires an exponential search over the space of all possible transmitted symbols in order to find the closest point in a Euclidean sense to the received symbols; a procedure that is infeasible for large systems. We introduce a new heuristic algorithm for the detection of a MIMO wireless system based on the Ant Colony Optimization (ACO) metaheuristic. The new algorithm, AntMIMO, has a simple architecture and achieves near maximum likelihood performance in polynomial time.

The traffic signal optimization problem is to find a traffic signal setting in a traffic network such that vehicles could arrive at their destination with minimum waiting time. The design of traffic signal setting to decrease waiting time for vehicles moving on the roads in urban city is important but difficult. In this thesis, we use a graph model to represent a traffic network. We propose two signal setting algorithms, a fast heuristic approach and an evolutionary algorithm based on the ant colony optimization (ACO) method, to give a good traffic signal setting. The results show that we could find better solutions by ACO algorithms, and the heuristic algorithm is faster but gets more total waiting time for vehicles. Furthermore, we transform the traffic network data of Kaohsiung city in Taiwan into our traffic graph model and test our algorithm on this traffic graph.

In this thesis, the Hybrid Genetic Algorithm-Ant Colony Optimization (GACO) approach is presented to solve the unit commitment problem (UC), and comparison with the results obtained using literature methods. Then this thesis applied the ability of the Genetic Algorithm (GA) operated after Ant Colony Optimization (ACO) can promote the ACO efficiency. The objective of GA is to improve the searching quality of ants by optimizing themselves to generate a better result, because the ants produced randomly by pheromone process are not necessary better. This method can not only enhance the neighborhood search, but can also search the optimum solution quickly to advance convergence. The other objective of this thesis is to investigate an influence of emission constraints on generation scheduling. The motivation for this objective comes from the efforts to reduce negative trends in a climate change. In this market structure, the independent power producers have to deal with several complex issues arising from uncertainties in spot market prices, and technical constraints which need to be considered while scheduling generation and trading for the next day. In addition to finding dispatch and unit commitment decisions while maximizing its profit, their scheduling models should include trading decisions like spot-market buy and sell. The model proposed in this thesis build on the combined carbon finance and spot market formulation, and help generators in deciding on when these commitments could be beneficial.

Combinatorial optimization problems are of high academical as well as practical importance. Many instances of relevant combinatorial optimization problems are, due to their dimensions, intractable for complete methods such as branch and bound. Therefore, approximate algorithms such as metaheuristics received much attention in the past 20 years. Examples of metaheuristics are simulated annealing, tabu search, and evolutionary computation. One of the most recent metaheuristics is ant colony optimization (ACO), which was developed by Prof. M. Dorigo (who is the supervisor of this thesis) and colleagues. This thesis deals with theoretical as well as practical aspects of ant colony optimization. * A survey of metaheuristics. Chapter 1 gives an extensive overview on the nowadays most important metaheuristics. This overview points out the importance of two important concepts in metaheuristics: intensification and diversification. * The hyper-cube framework. Chapter 2 introduces a new framework for implementing ACO algorithms. This framework brings two main benefits to ACO researchers. First, from the point of view of the theoretician: we prove that Ant System (the first ACO algorithm to be proposed in the literature) in the hyper-cube framework generates solutions whose expected quality monotonically increases with the number of algorithm iterations when applied to unconstrained problems. Second, from the point of view of the experimental researcher, we show through examples that the implementation of ACO algorithms in the hyper-cube framework increases their robustness and makes the handling of the pheromone values easier. * Deception. In the first part of Chapter 3 we formally define the notions of first and second order deception in ant colony optimization. Hereby, first order deception corresponds to deception as defined in the field of evolutionary computation and is therefore a bias introduced by the problem (instance) to be solved. Second order deception is an ACO-specific phenomenon. It describes the observation that the quality of the solutions generated by ACO algorithms may decrease over time in certain settings. In the second part of Chapter 3 we propose different ways of avoiding second order deception. * ACO for the KCT problem. In Chapter 4 we outline an ACO algorithm for the edge-weighted k-cardinality tree (KCT) problem. This algorithm is implemented in the hyper-cube framework and uses a pheromone model that was determined to be well-working in Chapter 3. Together with the evolutionary computation and the tabu search approaches that we develop in Chapter 4, this ACO algorithm belongs to the current state-of-the-art algorithms for the KCT problem. * ACO for the GSS problem. Chapter 5 describes a new ACO algorithm for the group shop scheduling (GSS) problem, which is a general shop scheduling problem that includes among others the well-known job shop scheduling (JSS) and the open shop scheduling (OSS) problems. This ACO algorithm, which is implemented in the hyper-cube framework and which uses a new pheromone model that was experimentally tested in Chapter 3, is currently the best ACO algorithm for the JSS as well as the OSS problem. In particular when applied to OSS problem instances, this algorithm obtains excellent results, improving the best known solution for several OSS benchmark instances. A final contribution of this thesis is the development of a general method for the solution of combinatorial optimization problems which we refer to as Beam-ACO. This method is a hybrid between ACO and a tree search technique known as beam search. We show that Beam-ACO is currently a state-of-the-art method for the application to the existing open shop scheduling (OSS) problem instances.

In a multiuser system, several signals are transmitted simultaneously within the same frequency band. This can result in significant improvements both in spectral efficiency and system capacity. However, a detrimental effect of the shared transmissions (both in time and bandwidth), is that the signal received at the base station (BS) or access point (AP) suffers from cochannel interference (CCI) and inter-symbol interference (ISI). This situation presents challenges to receiver design. To combat the destructive nature of multipath fading, a receiver often employs multiple antennas to collect the faded superimposed versions of the transmitted signals. The multiple signals are combined and processed in such a way that the effects of CCI and ISI are minimized and the desired information is reliably recovered. The situation is even more challenging when the system is operating under overload, i.e. when there are fewer receive antennas than there are transmitted signals. Multiuser detection (MUD) is used to simultaneously estimate the information sent by the transmitters. To do this, the receiver exploits differences among the cochannel signals (through unique spatial signatures in this case). We consider a cochannel communication system where multiple transmitted signals arrive at a receiver (equipped with multiple receive antennas) after propagating through a Rayleigh fading channel. It is assumed that the receiver is operating in an overloaded scenario. For such systems, an optimum maximum a posterior probability (MAP) detector estimates the transmitted signal by maximizing the probability of correct decision. The MAP detector reduces to the maximum likelihood (ML) detector when all the transmitted signals are equiprobable. The computational complexity of both MAP and ML detectors increases exponentially with the number of transmitted signals and the channel memory. For large systems suffering severe CCI and ISI, this is clearly not a good choice for real-time implementation due to the associated computational expenses. The main factors that influence the complexity of MAP / ML detection are: (i) the number of transmitted signals (or equivalently the number of users sharing the system resources), (ii) modulation alphabet size, and (iii) length of the channel memory. On the other hand, linear detection approaches fail to offer acceptable performance while other nonlinear sub-optimum approaches incur high computational costs for reasonably improved system performance and exhibit an irreducible error-floor at medium to high signal to noise ratio (SNR) values. We develop receiver signal processing techniques for the frequency-flat fading channel (where all the multipaths of the transmitted signal arrive at the receiver within a symbol period). We develop an ant colony optimization (ACO) assisted soft iterative detection approach for binary phase-shift keying (BPSK) modulated signals which employs a simplified MAP criteria to extract the most probable signals from the search space. The structure of the receiver is such that it can continue operating under overloaded conditions. The technique achieves near maximum likelihood (ML) performance in critically loaded cases using much lower complexity. For the challenging case of overload it still offers performance close to ML at low to moderate SNR values. Second, an integrated framework comprising of ACO metaheuristic and a recursively defined ML search criteria is developed to handle multilevel modulations. The proposed receiver is capable of achieving near-ML performance for the considered system with significant savings in computational complexity. The receiver framework is independent of the system loading condition, and therefore it remains suitable for overloaded scenarios. Due to the branch and bound nature of the algorithm, an exact expression for the complexity cannot be determined. Instead, an upper bound on computational complexity is developed.

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.

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.

Previous research on DNA computing has shown that DNA algorithms are useful to solve some combinatorial problems, such as the Hamiltonian path problem and the traveling salesman problem. The basic concept implicit in previous DNA algorithms is the brute force method. That is, all possible solutions are created initially, then inappropriate solutions are eliminated, and finally the remaining solutions are correct or the best ones. However, correct solutions may be destroyed while the procedure is executed. In order to avoid such an error, we recommend combining the conventional concepts of DNA computing with a heuristic optimization method and apply the new approach to design strategies. In this thesis, we present a DNA algorithm based on ant colony optimization (ACO) for solving the traveling salesman problem (TSP). Our method manipulates DNA strands of candidate solutions initially. Even if the correct solutions are destroyed during the process of filtering out, the remaining solutions can be reconstructed and correct solutions can be reformed. After filtering out inappropriate solutions, we employ control of melting temperature to amplify the surviving DNA strings proportionally. The product is used as the input and the iteration is performed repeatedly. Accordingly, the concentration of correct solutions will be increased. Our results agree with that obtained by conventional ant colony optimization algorithms and are better than that obtained by genetic algorithms. The same idea can be applied to design methods for solving other combinatorial problems with DNA computing.

To realize efficient parallel processing, which is one of effective methods that deal with computing intensive applications, the technology of solving the problems of task matching and scheduling becomes extremely important. In this thesis, an Ant Colony Optimization (ACO) approach is employed for allocating task graphs onto a heterogeneous computing system. The approach uses a new state transition rule to reduce the time needed for finding a satisfactory solution. And a local search procedure is designed to improve the obtained solution. Furthermore, by applying the Taguchi Method in the technology of Quality Engineering, and further utilizing the Orthogonal Array (OA) to reduce the number of experiments and find the optimal combination of parameters, which allows the Ant Colony Algorithm to find solutions more efficient. The proposed algorithm is compared with the genetic-algorithm-based approach and the dynamic priority scheduling (DPS) heuristic. Experimental results show that the ACO approach outperforms two computing approaches in solving the task matching and scheduling problem.