In this study,we develop an elitist multiobjective evolutionary algorithm for approximating the Pareto-optimal frontiers of multiobjective optimization problems. The algorithm converges the true Pareto-optimal frontier while keeping the solutions in the population well-spread over the frontier. Diversity of the solutions is maintained by the territory de&amp / #64257 / ning property of the algorithm rather than using an explicit diversity preservation mechanism. This leads to substantial computational e&amp / #64259 / ciency. We test the algorithm on commonly used test problems and compare its performance against well-known benchmark algorithms. In addition to approximating the entire Pareto-optimal frontier,we develop a preference incorporation mechanism to guide the search towards the decision maker&amp / #8217 / s regions of interest. Based on this mechanism, we implement two variants of the algorithm. The &amp / #64257 / rst gathers all preference information before the optimization stage to &amp / #64257 / nd approximations of the desired regions. The second one is an interactive algorithm that focuses on the desired region by interacting with the decision maker during the solution process. Based on tests on 2- and 3-objective problems, we observe that both algorithms converge to the preferred regions.

Order-picking operations constitute the costliest activities in a warehouse. The order-picking problem (OPP) aims to determine the route of the picker(s) in such a way that the total order-picking time, hence the order-picking costs are minimized. In this study, a warehouse that consists of parallel pick aisles is assumed, and various versions of the OPP are considered. Although the single-picker version of the problem has been well studied in the literature, the multiple-picker version has not received much attention in terms of algorithmic approaches. The literature also does not take into account the time taken by the number of turns during the picking route. In this thesis, a detailed discussion is made regarding the computational complexity of the OPP with a single picker. A heuristic procedure, which makes use of the exact algorithm for the OPP with no middle aisles, is proposed for the single-picker OPP with middle aisles, and computational results on randomly generated problems are given. Additionally, an evolutionary algorithm that makes use of the cluster-first, route-second and route-first, cluster-second heuristics for the VRP is provided. The parameters of the algorithm are determined based on preliminary runs and the algorithm is also tested on randomly generated problems, with different weights given to the cluster-first, route-second and route-first, cluster-second approaches. Lastly, a polynomial time algorithm is proposed for the problem of minimizing the number of turns in a parallel-aisle warehouse.

In this thesis, we address the route selection problem for Unmanned Air Vehicles (UAV) under multiple objectives. We consider a general case for this problem where the UAV has to visit several targets and return to the base. For this case, there are multiple combinatorial problems to be considered. First, the paths to be followed between any pairs of targets should be determined. This part can be considered as a multi-objective shortest path problem. Additionally, we need to determine the order of the targets to be visited. This in turn, is a multi-objective traveling salesperson problem. The overall problem is a combination of these two combinatorial problems. The route selection for UAVs has been studied by several researchers, mainly in the military context. They considered a linear combination of the two objectives / minimizing distance traveled and minimizing radar detection threat / and proposed heuristics for the minimization of the composite single objective problem. We treat these two objectives separately. We develop an evolutionary algorithm to determine the efficient tours. We also consider an exact interactive approach to identify the best paths and tours of a decision maker. We tested the two solution approaches on both small-sized and large-sized problem instances.

In this study, we propose a two-phase solution approach for approximating the efficient frontier of a bicriteria hub location problem. We develop an evolutionary algorithm to locate the hubs on the network as the first phase. In the second phase, we develop a bounding procedure based on dominance relations and using the determined bounds, we solve the allocation subproblem for each located hub set. The two-phase approach is tested on the Australian Post data set and it is observed that our approach approximates the entire efficient frontier well. In addition, we suggest an interactive procedure to find the solutions that are in the decision maker&rsquo / s preferred region of the solution space. In this procedure, we progressively incorporate the preferences of the decision maker and direct the search towards the preferred regions. Based on some computational experiments, it is observed that the interactive procedure converges to the preferred regions.

We propose an interactive preference-based evolutionary algorithm for the clustering problem. The problem is highly combinatorial and referred to as NP-Hard in the literature. The goal of the problem is putting similar items in the same cluster and dissimilar items into different clusters according to a certain similarity measure, while maintaining some internal objectives such as compactness, connectivity or spatial separation. However, using one of these objectives is often not sufficient to detect different underlying structures in different data sets with clusters having arbitrary shapes and density variations. Thus, the current trend in the clustering literature is growing into the use of multiple objectives as the inadequacy of using a single objective is understood better. The problem is also difficult because the optimal solution is not well defined. To the best of our knowledge, all the multiobjective evolutionary algorithms for the clustering problem try to generate the whole Pareto optimal set. This may not be very useful since majority of the solutions in this set may be uninteresting when presented to the decision maker. In this study, we incorporate the preferences of the decision maker into a well known multiobjective evolutionary algorithm, namely SPEA-2, in the optimization process using reference points and achievement scalarizing functions to find the target clusters.

<p>Evolutionary algorithms (EAs) have been shown to be competent at solving complex, multimodal optimisation problems in applications where the search space is large and badly understood. EAs are therefore among the most promising classes of algorithms for solving the Protein Structure Prediction Problem (PSPP). The PSPP is how to derive the 3D-structure of a protein given only its sequence of amino acids. This dissertation defines, evaluates and shows limitations of simplified models for solving the PSPP. These simplified models are off-lattice extensions to the lattice HP model which has been proposed and is claimed to possess some of the properties of real protein folding such as the formation of a hydrophobic core. Lattice models usually model a protein at the amino acid level of detail, use simple energy calculations and are used mainly for search algorithm development. Off-lattice models usually model the protein at the atomic level of detail, use more complex energy calculations and may be used for comparison with real proteins. The idea is to combine the fast energy calculations of lattice models with the increased spatial possibilities of an off-lattice environment allowing for comparison with real protein structures. A hypothesis is presented which claims that a simplified off-lattice model which considers other amino acid properties apart from hydrophobicity will yield simulated structures with lower Root Mean Square Deviation (RMSD) to the native fold than a model only considering hydrophobicity. The hypothesis holds for four of five tested short proteins with a maximum of 46 residues. Best average RMSD for any model tested is above 6Å, i.e. too high for useful structure prediction and excludes significant resemblance between native and simulated structure. Hence, the tested models do not contain the necessary biological information to capture the complex interactions of real protein folding. It is also shown that the EA itself is competent and can produce near-native structures if given a suitable evaluation function. Hence, EAs are useful for eventually solving the PSPP.</p>

Scheduling of aperiodic and independent tasks in hard real-time symmetric multiprocessing systems is an NP-complete problem that is often solved using heuristics like particle swarm optimization (PSO). The performance of these class of heuristics, known as evolutionary algorithms, are often evaluated based on the number of iterations it takes to find a solution. Such metrics provide limited information on how the algorithm reaches a solution and how the process could be accelerated. This thesis presents a methodology to analyze the trajectory formed by candidate solutions in order to analyze them in both the time and frequency domains at a single scale. The analysis entails (i) the impact of different parameters for the PSO algorithm, and (ii) the evolutionary processes in the swarm. The work reveals that particles have a directed movement towards a solution during a transient phase, and then enter a steady state where they perform an unguided local search. The scheduling algorithm presented in this thesis uses a variation of the minimum total tardiness with cumulative penalties cost function, that can be extended to suit different system needs. The experimental results show that the scheduler is able to distribute tasks to meet the real-time deadlines over 1, 2, and 4 processors and up to 30 tasks with overall system loads of up to 50\% in fewer than 1,000 iterations. When scheduling greater loads, the scheduler reaches local solutions with 1 to 2 missed deadlines, while larger tasks sets take longer to converge. The trajectories of the particles during the scheduling algorithm are examined as a means to emphasize the impact of the behaviour on the application performance and give insight into ways to improve the algorithm for both space and terrestrial applications.

In the area of artificial intelligence, the development of Evolutionary Algorithms (EAs) has been very active, especially in the last decade. These algorithms started to evolve when scientists from various regions of the world applied the principles of evolution to algorithmic search and problem solving. EAs have been utilised successfully in diverse complex application areas. Their success in tackling hard problems has been the engine of the field of Evolutionary Computation (EC). Nowadays, EAs are considered to be the best solution to use when facing a hard search or optimisation problem. Various improvements are continually being made with the design of new operators, hybrid models, among others. A very important example of such improvements is the use of parallel models of GAs (PGAs). PGAs have received widespread attention from various researchers as they have proved to be more effective than panmictic GAs, especially in terms of efficacy and speedup. This thesis focuses on, and investigates, cellular Genetic Algorithms (cGAs)-a competitive variant of parallel GAs. In a cGA, the tentative solutions evolve in overlapped neighbourhoods, allowing smooth diffusion of the solutions. The benefits derived from using cGAs come not only from flexibility gains and their fitness to the objective target in combination with a robust behaviour but also from their high performance and amenability to implementation using advanced custom silicon chip technologies. Nowadays, cGAs are considered as adaptable concepts for solving problems, especially complex optimisation problems. Due to their structural characteristics, cGAs are able to promote an adequate exploration/exploitation trade-off and thus maintain genetic diversity. Moreover, cGAs are characterised as being massively parallel and easy to implement. The structural characteristics inherited in a cGA provide an active area for investigation. Because of the vital role grid structure plays in determining the effectiveness of the algorithm, cellular dimensionality is the main issue to be investigated here. The implementation of cGAs is commonly carried out on a one- or two-dimensional structure. Studies that investigate higher cellular dimensions are lacking. Accordingly, this research focuses on cGAs that are implemented on a three-dimensional structure. Having a structure with three dimensions, specifically a cubic structure, facilitates faster spreading of solutions due to the shorter radius and denser neighbourhood that result from the vertical expansion of cells. In this thesis, a comparative study of cellular dimensionality is conducted. Simulation results demonstrate higher performance achieved by 3D-cGAs over their 2D-cGAs counterparts. The direct implementation of 3D-cGAs on the new advanced 3D-IC technology will provide added benefits such as higher performance combined with a reduction in interconnection delays, routing length, and power consumption. The maintenance of system reliability and availability is a major concern that must be addressed. A system is likely to fail due to either hard or soft errors. Therefore, detecting a fault before it deteriorates system performance is a crucial issue. Single Event Upsets (SEUs), or soft errors, do not cause permanent damage to system functionality, and can be handled using fault-tolerant techniques. Existing fault-tolerant techniques include hardware or software fault tolerance, or a combination of both. In this thesis, fault-tolerant techniques that mitigate SEUs at the algorithmic level are explored and the inherent abilities of cGAs to deal with these errors are investigated. A fault-tolerant technique and several mitigation techniques are also proposed, and faulty critical data are evaluated critical fault scenarios (stuck at ‘1’ and stuck at ‘0’ faults) are taken into consideration. Chief among several test and real world problems is the problem of determining the attitude of a vehicle using a Global Positioning System (GPS), which is an example of hard real-time application. Results illustrate the ability of cGAs to maintain their functionality and give an adequate performance even with the existence of up to 40% errors in fitness score cells. The final aspect investigated in this thesis is the dynamic characteristic of cGAs. cGAs, and EAs in general, are known to be stochastic search techniques. Hence, adaptive systems are required to continue to perform effectively in a changing environment, particularly when tackling real-world problems. The adaptation in cellular engines is mainly achieved through dynamic balancing between exploration and exploitation. This area has received considerable attention from researchers who focus on improving the algorithmic performance without incurring additional computational effort. The structural properties and the genetic operations provide ways to control selection pressure and, as a result, the exploration/exploitation trade-off. In this thesis, the genetic operations of cGAs, particularly the selection aspect and their influence on the search process, are investigated in order to dynamically control the exploration/exploitation trade-off. Two adaptive-dynamic techniques that use genetic diversity and convergence speeds to guide the search are proposed. Results obtained by evaluating the proposed approaches on a test bench of diverse-characteristic real-world and test problems showed improvement in dynamic cGAs performance over their static counterparts and other dynamic cGAs. For example, the proposed Diversity-Guided 3D-cGA outperformed all the other dynamic cGAs evaluated by obtaining a higher search success rate that reached to 55%.

Scheduling of aperiodic and independent tasks in hard real-time symmetric multiprocessing systems is an NP-complete problem that is often solved using heuristics like particle swarm optimization (PSO). The performance of these class of heuristics, known as evolutionary algorithms, are often evaluated based on the number of iterations it takes to find a solution. Such metrics provide limited information on how the algorithm reaches a solution and how the process could be accelerated. This thesis presents a methodology to analyze the trajectory formed by candidate solutions in order to analyze them in both the time and frequency domains at a single scale. The analysis entails (i) the impact of different parameters for the PSO algorithm, and (ii) the evolutionary processes in the swarm. The work reveals that particles have a directed movement towards a solution during a transient phase, and then enter a steady state where they perform an unguided local search. The scheduling algorithm presented in this thesis uses a variation of the minimum total tardiness with cumulative penalties cost function, that can be extended to suit different system needs. The experimental results show that the scheduler is able to distribute tasks to meet the real-time deadlines over 1, 2, and 4 processors and up to 30 tasks with overall system loads of up to 50\% in fewer than 1,000 iterations. When scheduling greater loads, the scheduler reaches local solutions with 1 to 2 missed deadlines, while larger tasks sets take longer to converge. The trajectories of the particles during the scheduling algorithm are examined as a means to emphasize the impact of the behaviour on the application performance and give insight into ways to improve the algorithm for both space and terrestrial applications.

In this study, we consider the hub location problem of PTT, first realized by Cetiner (2003), and propose the evaluation of multiple decision criteria while locating hubs. Since the mathematical model for the problem is too large to be solved, we utilize heuristic methods in the solution procedure. While doing this, we first test two algorithms, NSGA-II and SPEA2, on different hub location problems and use the algorithm with better performance while solving the PTT problem.