Hard combinatorial optimization (CO) problems pose challenges to traditional algorithmic solutions. The search space usually contains a large number of local optimal points and the computational cost to reach a global optimum may be too high for practical use. In this work, we conduct a comparative study of several state-of-the-art metaheuristic algorithms for hard CO problems solving. Our study is motivated by an industrial application called the Fertilizer Blends Optimization. We focus our study on a number of local search metaheuristics and analyze their performance in terms of both runtime efficiency and solution quality. We show that local search granularity (move step size) and the downhill move probability are two major factors that affect algorithm performance, and we demonstrate how experimental tuning work can be applied to obtain good performance of the algorithms. <p>Our empirical result suggests that the well-known Simulated Annealing (SA) algorithm showed the best performance on the fertilizer problem. The simple Iterated Improvement Algorithm (IIA) also performed surprisingly well by combining strict uphill move and random neighborhood selection. A novel approach, called Delivery Network Model (DNM) algorithm, was also shown to be competitive, but it has the disadvantage of being very sensitive to local search granularity. The constructive local search method (GRASP), which combines heuristic space sampling and local search, outperformed IIA without a construction phase; however, the improvement in performance is limited and generally speaking, local search performance is not sensitive to initial search positions in our studied fertilizer problem.

Sound source localization with microphone arrays has received considerable attention as a means for the automated tracking of individuals in an enclosed space and as a necessary component of any general-purpose speech capture and automated camera pointing system. A novel computationally efficient method compared to traditional source localization techniques is proposed and is both theoretically and experimentally investigated in this research. This thesis first reviews the previous work in this area. The evolution of a new localization algorithm accompanied by an array structure for audio signal localization in three dimensional space is then presented. This method, which has similarities to the structure of the eye, consists of a novel hemispherical microphone array with microphones on the shell and one microphone in the center of the sphere. The hemispherical array provides such benefits as 3D coverage, simple signal processing and low computational complexity. The signal processing scheme utilizes parallel computation of a special and novel closeness function for each microphone direction on the shell. The closeness functions have output values that are linearly proportional to the spatial angular difference between the sound source direction and each of the shell microphone directions. Finally by choosing directions corresponding to the highest closeness function values and implementing linear weighted spatial averaging in those directions we estimate the sound source direction. The experimental tests validate the method with less than 3.10 of error in a small office room. Contrary to traditional algorithmic sound source localization techniques, the proposed method is based on parallel mathematical calculations in the time domain. Consequently, it can be easily implemented on a custom designed integrated circuit.

The automated timetabling and scheduling is one of the hardest problem areas. This isbecause of constraints and satisfying those constraints to get the feasible and optimizedschedule, and it is already proved as an NP Complete (1) [1]. The basic idea behind this studyis to investigate the performance of Genetic Algorithm on general scheduling problem underpredefined constraints and check the validity of results, and then having comparative analysiswith other available approaches like Tabu search, simulated annealing, direct and indirectheuristics [2] and expert system. It is observed that Genetic Algorithm is good solutiontechnique for solving such problems and later analysis will prove this argument. The programis written in C++ and analysis is done by using variation in various parameters.

This thesis investigates extending the dynamically-typed, functional programming language Scheme, with simulated overloading in order to permit the binding of multiple, distributed defnitions to function names. Overloading facilitates the use of an incremental style of programming in which functions can be defined with a base behaviour and then extended with additional behaviour as it becomes necessary to support new data types. A technique is demonstrated that allows existing functions to be extended, without modifcation, therefore improving code reuse. Using the primitives provided by Scheme, it is possible to write functions that perform like the generic routines (functions) of the programming language EL1. These functions use the type of their arguments to determine, at run-time, the computation to perform. It is shown that by gathering the definitions for an overloaded function and building a generic routine, the language appears to provide overloading. A language extension that adds the syntax necessary to instruct the system to gather the distributed set of definitions for an overloaded function and incrementally build an equivalently applicable generic function is described. A simple type inference algorithm, necessary to support the construction of generic functions, is presented and detailed. Type inference is required to determine the domain of an overloaded function in order to generate the code needed to perform run-time overload resolution. Some limitations and possible extensions of the algorithm are discussed.

Hard combinatorial optimization (CO) problems pose challenges to traditional algorithmic solutions. The search space usually contains a large number of local optimal points and the computational cost to reach a global optimum may be too high for practical use. In this work, we conduct a comparative study of several state-of-the-art metaheuristic algorithms for hard CO problems solving. Our study is motivated by an industrial application called the Fertilizer Blends Optimization. We focus our study on a number of local search metaheuristics and analyze their performance in terms of both runtime efficiency and solution quality. We show that local search granularity (move step size) and the downhill move probability are two major factors that affect algorithm performance, and we demonstrate how experimental tuning work can be applied to obtain good performance of the algorithms. <p>Our empirical result suggests that the well-known Simulated Annealing (SA) algorithm showed the best performance on the fertilizer problem. The simple Iterated Improvement Algorithm (IIA) also performed surprisingly well by combining strict uphill move and random neighborhood selection. A novel approach, called Delivery Network Model (DNM) algorithm, was also shown to be competitive, but it has the disadvantage of being very sensitive to local search granularity. The constructive local search method (GRASP), which combines heuristic space sampling and local search, outperformed IIA without a construction phase; however, the improvement in performance is limited and generally speaking, local search performance is not sensitive to initial search positions in our studied fertilizer problem.

GPRS is one of popular topics for mobile communication. To satisfy the Quality of Service (QoS) requirement for multimedia transmission, the QoS is divided into four classes, which are conversational, interactive, streaming and background class. When mobile communication network transmits the multimedia data, it needs a proper scheduling algorithm to assign the radio resource and make every data meet the requirement of the QoS in GPRS system. In this thesis, we discuss the properties of every traffic class. For each traffic class, we propose a transmission method. The proposed methods are integrated with the link adaptation to develop a scheduling algorithm to suit the QoS requirement in the GPRS system. In addition, we introduce the FIFO scheduling algorithm and the scheduling algorithm that has priority. Our methods are then compared with those existing algorithms. We use OPNET simulation system to study the FIFO scheduling algorithm, the priority-scheduling algorithm and our new scheduling algorithms. The effects on the delay time, packet loss ratio and throughput for every scheduling algorithm are analyzed and compared. The simulations show that the new scheduling algorithm can satisfy all QoS requirements, and the performance of the new scheduling algorithm is better than that of the other scheduling algorithms in the interactive class.

Researchers have applied genetic algorithms (GAs) and other heuristic optimization methods to perform truss optimization in recent years. Although a substantial amount of research has been performed on the optimization of truss member sizes, nodal coordinates, and member connections, research that seeks to simultaneously optimize the topology, geometry, and member sizes of trusses is still uncommon. In addition, most of the previous research is focused on the problem domains that are limited to a structured domain, which is defined by a fixed number of nodes, members, load locations, and load magnitudes. The objective of this research is to develop a computational method that can design efficient roof truss systems. This method provides an engineer with a set of near-optimal trusses for a specific unstructured problem domain. The unstructured domain only prescribes the magnitude of loading and the support locations. No other structural information concerning the number or locations of nodes and the connectivity of members is defined. An implicit redundant representation (IRR) GA (Raich 1999) is used in this research to evolve a diverse set of near-optimal truss designs within the specified domain that have varying topology, geometry, and sizes. IRR GA allows a Pareto-optimal set to be identified within a single trial. These truss designs reflect the tradeoffs that occur between the multiple objectives optimized. Finally, the obtained Pareto-optimal curve will be used to provide design engineers with a range of highly fit conceptual designs from which they can select their final design. The quality of the designs obtained by the proposed multi-objective IRR GA method will be evaluated by comparing the trusses evolved with trusses that were optimized using local perturbation methods and by trusses designed by engineers using a trial and error approach. The results presented show that the method developed is very effective in simultaneously optimizing the topology, geometry, and size of trusses for multiple objectives.

Along the history of Very Large Scale Integration (VLSI), we have successfully scaled down the size of transistors, scaled up the speed of integrated circuits (IC) and the number of transistors in a chip - these are just a few examples of our achievement in VLSI scaling. It is projected to enter the nanometer (timing estimation and buffer planning for global routing and other early stages such as floorplanning. A novel path based buffer insertion scheme is also included, which can overcome the weakness of the net based approaches. Part-2 Circuit clustering techniques with the application in Field-Programmable Gate Array (FPGA) technology mapping The problem of timing driven n-way circuit partitioning with application to FPGA technology mapping is studied and a hierarchical clustering approach is presented for the latest multi-level FPGA architectures. Moreover, a more general delay model is included in order to accurately characterize the delay behavior of the clusters and circuit elements.

A 3D graphics system usually consists of two major subsystems: geometry subsystem and rendering subsystem. The geometry subsystem performs transformation, lighting, backface culling, and clipping. The clipping is to remove the part of a triangle that is outside of the view volume by calculating the intersections of the triangle edges with view planes. The clipping operation turns out to be a time-consuming procedure in the geometry subsystem. In this thesis, we present several clipping algorithms and their hardware implementations, and compare the performance in the geometry subsystem. Furthermore, a new pre-clipping algorithm is also proposed to reduce the number of triangles that need to go through the clipping operations in order to reduce the burden of clipping operations in the whole geometry subsystem. The whole geometry system including the pre-clipping and clipping hardware is verified in a complete 3G graphics system in the Versatile FPGA demonstration board.

This dissertation focuses on improving the non-restoring division and square root algorithm. Although the non-restoring division algorithm is the fastest and has less complexity among other radix-2 digit recurrence division algorithms, there are some possibilities to enhance its performance. To improve its performance, two new approaches are proposed here. In addition, the research scope is extended to seek an efficient algorithm for implementing non-restoring square root, which has similar steps to non-restoring division. For the first proposed approach, the non-restoring divider with a modified algorithm is presented. The new algorithm changes the order of the flowchart, which reduces one unit delay of the multiplexer per every iteration. In addition, a new method to find a correct quotient is presented and it removes an error that the quotient is always odd number after a digit conversion from a digit converter from the quotient with digits 1 and -1 to conventional binary number. The second proposed approach is a novel method to find a quotient bit for every iteration, which hides the total delay of the multiplexer with dual path calculation. The proposed method uses a Most Significant Carry (MSC) generator, which determines the sign of each remainder faster than the conventional carry lookahead adder and it eventually reduces the total delay by almost 22% compared to the conventional non-restoring division algorithm. Finally, an improved algorithm for non-restoring square root is proposed. The two concepts already applied to non-restoring division are adopted for improving the performance of a non-restoring square root since it has similar process to that of non-restoring division for finding square root. Additionally, a new method to find intermediate quotients is presented that removes an adder per an iteration to reduce the total area and power consumption. The non-restoring square root with MSC generator reduces total delay, area and power consumption significantly. / text