This thesis introduces Intelligent Fitness Functions and Partial Fitness Functions both of which can improve the performance of a genetic algorithm which is limited to a fixed run time. An Intelligent Fitness Function is defined as a fitness function with a memory. The memory is used to store information about individuals so that duplicate individuals do not need to have their fitness tested. Different types of memory (long and short term) and different storage strategies (fitness based, time base and frequency based) have been tested. The results show that an intelligent fitness function, with a time based long term memory improves the efficiency of a genetic algorithm the most. A Partial Fitness Function is defined as a fitness function that only partially tests the fitness of an individual at each generation. Thus only promising individuals get fully tested. Using a partial fitness function gives the genetic algorithm more evolutionary steps in the same length of time as a genetic algorithm using a normal fitness function. The results show that a genetic algorithm using a partial fitness function can achieve higher fitness levels than a genetic algorithm using a normal fitness function. Finally a genetic algorithm designed to solve a substitution cipher is compared to one equipped with an intelligent fitness function and another equipped with a partial fitness function. The genetic algorithm with the intelligent fitness function and the genetic algorithm with the partial fitness function both show a significant improvement over the genetic algorithm with a conventional fitness function.

Scheduling large real world problems is a complex process and finding high quality solutions is not a trivial task. In cooperation with Trimble MRM Ltd., who provide scheduling solutions for many large companies, a problem is identified and modelled. It is a general model which encapsulates several important scheduling, routing and resource allocation problems in literature. Many of the state-of-the-art heuristics for solve scheduling problems and indeed other problems require specialised heuristics tailored for the problem they are to solve. While these provide good solutions a lot of expert time is needed to study the problem, and implement solutions. This research investigates methods to enhance existing search based methods. We study hyperheuristic techniques as a general search based heuristic. Hyperheuristics raise the generality of the solution method by using a set of tools (low level heuristics) to work on the solution. These tools are problem specific and usually make small changes to the problem. It is the task of the hyperheuristic to determine which tool to use and when. Low level heuristics using exact/heuristic hybrid method are used in this thesis along with a new Tabu based hyperheuristic which decreases the amount of CPU time required to produce good quality solutions. We also develop and investigate the Variable Fitness Function approach, which provides a new way of enhancing most search-based heuristics in terms of solution quality. If a fitness function is pushing hard in a certain direction, a heuristic may ultimately fail because it cannot escape local minima. The Variable Fitness Function allows the fitness function to change over the search and use objective measures not used in the fitness calculation. The Variable Fitness Function and its ability to generalise are extensively tested in this thesis. The two aims of the thesis are achieved and the methods are analysed in depth. General conclusions and areas of future work are also identified.

Scheduling large real world problems is a complex process and finding high quality solutions is not a trivial task. In cooperation with Trimble MRM Ltd., who provide scheduling solutions for many large companies, a problem is identified and modelled. It is a general model which encapsulates several important scheduling, routing and resource allocation problems in literature. Many of the state-of-the-art heuristics for solve scheduling problems and indeed other problems require specialised heuristics tailored for the problem they are to solve. While these provide good solutions a lot of expert time is needed to study the problem, and implement solutions. This research investigates methods to enhance existing search based methods. We study hyperheuristic techniques as a general search based heuristic. Hyperheuristics raise the generality of the solution method by using a set of tools (low level heuristics) to work on the solution. These tools are problem specific and usually make small changes to the problem. It is the task of the hyperheuristic to determine which tool to use and when. Low level heuristics using exact/heuristic hybrid method are used in this thesis along with a new Tabu based hyperheuristic which decreases the amount of CPU time required to produce good quality solutions. We also develop and investigate the Variable Fitness Function approach, which provides a new way of enhancing most search-based heuristics in terms of solution quality. If a fitness function is pushing hard in a certain direction, a heuristic may ultimately fail because it cannot escape local minima. The Variable Fitness Function allows the fitness function to change over the search and use objective measures not used in the fitness calculation. The Variable Fitness Function and its ability to generalise are extensively tested in this thesis. The two aims of the thesis are achieved and the methods are analysed in depth. General conclusions and areas of future work are also identified.

Affordability of products and services is an economic benefit that should accrue to consumers, whether they are corporations, government agencies or individuals. This concept of affordability goes beyond conventional wisdom that considers affordability as the ability to pay the price of a product or service. This dissertation defines and explores a broader concept of affordability – one of fitness to perform at the level of quality required by the consumer, to perform at that level whenever the product or service is used, and to do so with minimum consumption of resources. This concept of affordability is applied to technological systems by using the complexity sciences concept of fitness as the metaphor for technological systems' fitness. During a system design evolution, the specific design outcome is determined by that set of design search paths followed – it is path dependent. Dynamic mechanisms create, dictate and maintain path dependence. Initial conditions define the start and direction of a path. During subsequent design steps, positive feedback influences the designer to continue on that path. This dissertation describes underlying mechanisms that create, dictate and maintain path dependence; discusses the effects of path dependence on system design and system affordability; models these effects using system dynamics modeling; and suggests actions to address its effects. This dissertation also addresses several types of fitness landscapes, and suggests that the Data Envelopment Analysis (DEA) solution space is a form of fitness landscape suitable for evaluating the efficiency, and thus the fitness, of research and development (R&D) projects. It describes the use of DEA to evaluate and select Department of Defense (D0D) R&D projects as a new application of DEA. / Ph. D.

The fitness function developed in this thesis directly links the physicochemical properties of an enzyme to evolutionary fates in a quantitative and predictive manner through a comparative study of empirical and simulated data. The success or failure of organisms during evolution is dictated by changes in molecular structure that give rise to changes in fitness revealed by evolutionary dynamics within a population. While the conceptual link between genotype, phenotype and fitness is clear, the ability to relate these in a quantitative manner remains difficult. I show here that predicting success during adaptation can depend critically upon enzyme kinetic and folding models. We used a 'weak link' method to favor mutations to an essential, but maladapted adenylate kinase gene within a microbial population that resulted in the identification of five mutants that arose nearly simultaneously and competed for success. The unique catalytic role of adenylate kinase in vivo is to maintain adenylate homeostasis by catalyzing the reaction: ATP + AMP [imaginary] ADP. The stabilizing substitutions retained this essential function and were shown to be necessary for viability at higher temperatures. Physicochemical characterization of these mutants demonstrated that, although steady-state enzyme activity is important, success within the population is critically dependent on resistance to denaturation and aggregation thus emphasizing the importance of proper folding in adaptation. In vitro activity is a product of critical catalytic and folding pathways, and hence is a valuable proxy for fitness. A fitness function relating in vitro measurements of enzyme activity and reversible and irreversible unfolding to growth rate must impose an activity threshold above which there is no added fitness benefit in order to reproduce in vivo evolutionary fates in an in silico population. The fitness function thereby links organismal adaptation to the properties of a single gene. Understanding the physical basis for adaptation of an organism is the first step in the development of approaches that can accurately model, and someday predict, the manner in which organisms would respond to new antibiotics and improve upon the current clinical regimens.

The modern view of optimization is that optimization algorithms are not designed in a vacuum, but can make use of information regarding the broad class of objective functions from which a problem instance is drawn. Using this knowledge, we want to design optimization algorithms that execute quickly (efficiency), solve the objective function with minimal samples (performance), and are applicable over a wide range of problems (abstraction). However, we present a new theory for blackbox optimization from which, we conclude that of these three desired characteristics, only two can be maximized by any algorithm. We put forward an alternate view of optimization where we use knowledge about the problem class and samples from the problem instance to identify which problem instances from the class are being solved. From this Elimination of Fitness Functions approach, an idealized optimization algorithm that minimizes sample counts over any problem class, given complete knowledge about the class, is designed. This theory allows us to learn more about the difficulty of various problems, and we are able to use it to develop problem complexity bounds. We present general methods to model this algorithm over a particular problem class and gain efficiency at the cost of specifically targeting that class. This is demonstrated over the Generalized Leading-Ones problem and a generalization called LO∗∗ , and efficient algorithms with optimal performance are derived and analyzed. We also iii tighten existing bounds for LO∗∗∗. Additionally, we present a probabilistic framework based on our Elimination of Fitness Functions approach that clarifies how one can ideally learn about the problem class we face from the objective functions. This problem learning increases the performance of an optimization algorithm at the cost of abstraction. In the context of this theory, we re-examine the blackbox framework as an algorithm design framework and suggest several improvements to existing methods, including incorporating problem learning, not being restricted to blackbox framework and building parametrized algorithms. We feel that this theory and our recommendations will help a practitioner make substantially better use of all that is available in typical practical optimization algorithm design scenarios.