Search

The frequency assignment problem is a computationally hard problem with many applications including the mobile telephone industry and tactical communications. The problem may be modelled mathematically as a T-colouring problem for an undirected weighted graph; it is required to assign to each vertex a value from a given set such that for each edge the difference in absolute value between the values at the corresponding vertices is greater than or equal to the weight of the edge. This problem was solved using novel and existing metaheuristic algorithms and their relative successes were compared. Early work of this thesis used greedy, steepest descent and backtracking algorithms as a means of investigating the factors which influence the performance of an algorithm (selection of frequency, ordering of variables, provision of an incremental objective function). Later simulated annealing, tabu search and divide and conquer techniques were used and the results compared. A novel divide and conquer technique incorporating metaheuristics is described and results using test data based on real problems is presented. The divide and conquer technique (with either tabu search or simulated annealing) was found to improve significantly upon the corresponding metaheuristic when implemented alone and acting on non-trivial scenarios. The results were significant and consistent. The divide and conquer (with simulated annealing) algorithm in particular was shown to be robust and efficient in its solution of the frequency assignment problems presented. The results presented in this thesis consistently out-perform those obtained by the Defence, Evaluation and Research Agency, Malvern. In addition this method lends itself to parallelisation since the problem is broken into smaller independent parts. The divide and conquer algorithm does not exploit knowledge of the constraint network and should be applicable to a number of different problem domains. Algorithms capable of solving the frequency assignment problem most effectively will become valuable as demand for the electromagnetic spectrum continues to grow.

The ordering effect of sequential treatment addition is present in many problem areas ranging from online search ranking and job scheduling to election standardization and the design of clinical trials. The straightforward approach to studying this ordering effect on a response is to test each permutation of the treatment components. When the run size becomes too costly, a random sample of permutations can instead be used for estimation and inference. Noting the inefficiencies present in both of these approaches, well-designed order-of-addition experiments have been proposed to reduce the computational complexity of studying the ordering effect without sacrificing statistical power; however, this problem is under-studied in the statistical literature.In this work we make several state-of-the-art advancements to the order-of-addition literature. By leveraging the structure of order-of-addition data, we pose flexible, position-based models that work well in practice. These new models inspire and necessitate the creation of parsimonious designs that guarantee stable parameter estimates. We further adapt these designs for a component screening problem in which the pool of treatment components is larger than the number of available positions in the sequence.We test our methods against several prominent order-of-addition problems, including drug chemotherapy and job scheduling. Our models and model-based optimal designs outperform the accepted alternatives in most cases, and in other situations our methods act as valuable tools for encouraging robust experimentation. To encourage the use of quality order-of-addition designs in wider practice, we implement and compare popular, nature-inspired metaheuristic algorithms for solving difficult design problems without closed-form solutions. We find that certain variants and hybridized algorithms can produce quality designs for obtaining stable parameter estimates in order-of-addition models or for studying black-box deterministic functions on the space of permutations.

In engineering design, optimization is customary, and often indispensable. Typical cases include minimization of drag for vehicles, minimization of weight for structures like buildings and bridges, maximization of power and lift for aircraft and rockets, minimization of fuel consumption for engines, etc. Therefore it comes as no surprise that development of fast and efficient optimization algorithms for engineering design is an actively pursued research area. In recent decades, metaheuristic algorithms have proven to be efficient, robust and versatile methods for numerical optimization. However, they usually need to evaluate a large number of candidate designs to find the optimum. This becomes prohibitive for engineering optimization problems in which each design evaluation may require computationally expensive analysis and, consequently, the optimization process may take much longer time than affordable. Considering that the number of design evaluations is a critical factor in overall optimization time, it is imperative to develop techniques to search for the optimum design using fewest evaluations possible. With this singular goal, this thesis investigates a range of domains in which existing approaches can be improved. Engineering problems are often highly non-linear, discontinuous, and non-differentiable, which rules out (or restricts) the applicability of analytical techniques for solving them. However, they exhibit additional attributes that prove challenging even to the existing metaheuristic techniques, thus making the search difficult and, consequently, creating a necessity for carrying out large numbers of evaluations. These include: (a) Constraints - constraints render a fraction (possibly large fraction) of the search space infeasible, making it hard to find the optimum and at times even a feasible design; (b) Large number of objectives - Pareto-dominance sorting, a commonly used technique in multi-objective optimization algorithms, is inadequate to solve problems with large numbers of objectives, a fact well reported in literature; (c) Large number of variables - the search space grows exponentially with the number of variables, which results in a corresponding increase in computational effort; and (d) Multiple models - For certain problems, there may be multiple candidate models to choose a solution from, with none of them being an obviously preferred one. In such a case, one may need to explore each one of them to find the global best. In this thesis, studies are conducted on each of these domains individually. Shortcomings of the existing methods are analyzed, and novel techniques are developed for efficiently handling constraints, large number of objectives/variables and multiple models. For effective constraint handling, conventional evolutionary algorithm is enhanced using a novel infeasibility driven ranking technique, while conventional simulated annealing algorithm is enhanced using an approximate descent direction coupled with dominance-based acceptance criteria. For many-objective problems, improved secondary-ranking methods and a novel dimensionality reduction technique based on Pareto corner search are proposed. For many-variable problems, conventional cooperative coevolutionary algorithm is enhanced using a correlation based partitioning strategy which enables it to deliver competitive performances across a variety of separable and non-separable problems. Lastly, for trans-dimensional problems, a simulated annealing based algorithm which searches through model space and variable space simultaneously is presented. The proposed methods are able to achieve competitive results using markedly fewer numbers of design evaluations compared to conventional optimizers, which is demonstrated through rigorous numerical experiments on benchmark problems. Finally, the proposed algorithms are applied to a number of engineering design problems in order to accentuate their functionality and viability for solving real-life problems.