Esta dissertação apresenta os algoritmos BicriterionAnt, MACS e MONACO, disponíveis na literatura, baseados em colônia de formigas, para resolução do Problema do Caixeiro Viajante Multiobjetivo (PCVMO). São apresentadas as características do problema e de cada algoritmo utilizado. Estes algoritmos foram testados em seis instâncias bi-objetivo do PCVMO. Foram implementadas algumas alterações na estrutura original dos algoritmos na tentativa de produzir resultados melhores do que os algoritmos originais. Para a avaliação dos resultados e medição da qualidade das soluções, foram utilizadas métricas de desempenho que auxiliam na identificação dos melhores conjuntos de soluções não-dominadas. / This dissertation presents the BicriterionAnt, MACS and MONACO Ant Colony algorithms, available in literature, to solve the Multi-Objective Traveling Salesman Problem (MOTSP). The characteristics of the problem and of each algorithm used are presented. Those algorithms were tested in six bi-objective instances of MOTSP. Changes in the original algorithms were implemented to try to produce better results than the original ones. To validate the results and to measure the quality of the solutions, metrics of performance were used which help to identify the best non-dominated solution sets.

Philosophiae Doctor - PhD / Wireless sensor networks (WSNs) have become a popular research area that is widely gaining the attraction from both the research and the practitioner communities due to their wide area of applications. These applications include real-time sensing for audio delivery, imaging, video streaming, and remote monitoring with positive impact in many fields such as precision agriculture, ubiquitous healthcare, environment protection, smart cities and many other fields. While WSNs are aimed to constantly handle more intricate functions such as intelligent computation, automatic transmissions, and in-network processing, such capabilities are constrained by their limited processing capability and memory footprint as well as the need for the sensor batteries to be cautiously consumed in order to extend their lifetime. This thesis revisits the issue of the energy efficiency in sensor networks by proposing a novel clustering approach for routing the sensor readings in wireless sensor networks. The main contribution of this dissertation is to 1) propose corrective measures to the traditional energy model adopted in current sensor networks simulations that erroneously discount both the role played by each node, the sensor node capability and fabric and 2) apply these measures to a novel hierarchical routing architecture aiming at maximizing sensor networks lifetime. We propose three energy models for sensor network: a) a service-aware model that account for the specific role played by each node in a sensor network b) a sensor-aware model and c) load-balancing energy model that accounts for the sensor node fabric and its energy footprint. These three models are complemented by a load-balancing model structured to balance energy consumption on the network of cluster heads that forms the backbone for any cluster-based hierarchical sensor network. We present two novel approaches for clustering the nodes of a hierarchical sensor network: a) a distance-aware clustering where nodes are clustered based on their distance and the residual energy and b) a service-aware clustering where the nodes of a sensor network are clustered according to their service offered to the network and their residual energy. These approaches are implemented into a family of routing protocols referred to as EOCIT (Energy Optimization using Clustering Techniques) which combines sensor node energy location and service awareness to achieve good network performance. Finally, building upon the Ant Colony Optimization System (ACS), Multipath Routing protocol based on Ant Colony Optimization approach for Wireless Sensor Networks (MRACO) is proposed as a novel multipath routing protocol that finds energy efficient routing paths for sensor readings dissemination from the cluster heads to the sink/base station of a hierarchical sensor network. Our simulation results reveal the relative efficiency of the newly proposed approaches compared to selected related routing protocols in terms of sensor network lifetime maximization.

Made available in DSpace on 2015-03-04T18:51:05Z (GMT). No. of bitstreams: 1 Dissert_MSc_JaquelineAngelo.pdf: 926474 bytes, checksum: da4b07a3aac6c41fe497e0351128bde1 (MD5) Previous issue date: 2008-07-24 / Coordenacao de Aperfeicoamento de Pessoal de Nivel Superior / This dissertation presents the BicriterionAnt, MACS and MONACO Ant Colony algorithms, available in literature, to solve the Multi-Objective Traveling Salesman Problem (MOTSP). The characteristics of the problem and of each algorithm used are presented. Those algorithms were tested in six bi-objective instances of MOTSP. Changes in the original algorithms were implemented to try to produce better results than the original ones. To validate the results and to measure the quality of the solutions, metrics of performance were used which help to identify the best non-dominated solution sets. / Esta dissertação apresenta os algoritmos BicriterionAnt, MACS e MONACO, disponíveis na literatura, baseados em colônia de formigas, para resolução do Problema do Caixeiro Viajante Multiobjetivo (PCVMO). São apresentadas as características do problema e de cada algoritmo utilizado. Estes algoritmos foram testados em seis instâncias bi-objetivo do PCVMO. Foram implementadas algumas alterações na estrutura original dos algoritmos na tentativa de produzir resultados melhores do que os algoritmos originais. Para a avaliação dos resultados e medição da qualidade das soluções, foram utilizadas métricas de desempenho que auxiliam na identificação dos melhores conjuntos de soluções não-dominadas.

Scheduling concerns the allocation of limited resources to tasks over time. In manufacturing systems, scheduling is nothing but assigning the jobs to the available processors over a period of time. Our research focuses on scheduling in systems of parallel processors which is challenging both from the theoretical and practical perspectives. The system of parallel processors is a common occurrence in different types of modern manufacturing systems such as job shop, batch shop and mass production. A variety of important and challenging problems with realistic settings in a system of parallel processors are considered. We consider two types of processors comprising discrete and batch processors. The processor which produces one job at a time is called a discrete processor. Batch processor is a processor that can produce several jobs simultaneously by keeping jobs in a batch form which is commonly seen in semiconductor manufacturing, heat treatment operations and also in chemical processing industries. Our aim is to develop efficient solution methodologies (heuristics/metaheuristics) for three different problems in the thesis. The first two problems consider the objective of minimizing total weighted tardiness in cases of discrete and batch processors where customer delivery time performance is critical. The third problem deals with the objective of minimizing the total weighted completion time in the case of batch processors to reduce work-in-process inventory. Specifically, the first problem deals with the scheduling of parallel identical discrete processors to minimize total weighted tardiness. We develop a metaheuristic based on Ant Colony Optimization(ACO) approach to solve the problem and compare it with the available best heuristics in the literature such as apparent tardiness cost and modified due date rules. An extensive experimentation is conducted to evaluate the performance of the ACO approach on different problem sizes with varied tardiness factors. Our experimentation shows that the proposed ant conony optimization algorithm yields promising results as compared to the best of the available heuristics. The second problem concerns with the scheduling of jobs to parallel identical batch processors for minimizing the total weighted tardiness. It is assumed that the jobs are incompatible in respect of job families indicating that jobs from different families cannot be processed together. We decompose the problem into two stages including batch formation and batch scheduling as in the literature. Ant colony optimization based heuristics are developed in which ACO is used to solve the batch scheduling problem. Our computational experimentation shows that the proposed five ACO based heuristics perform better than the available best traditional dispatching rule called ATC-BATC rule. The third scheduling problem is to minimize the total weighted completion time in a system of parallel identical batch processors. In the real world manufacturing system, jobs to be scheduled come in lots with different job volumes(i.e number of jobs) and priorities. The real settings of lots and high batch capacity are considered in this problem. This scheduling problem is formulated as a mixed integer non-linear program. We develop a solution framework based on the decomposition approach for this problem. Two heuristics are proposed based on the proposed decomposition approach and the performance of these heuristics is evaluated in the cases of two and three batch processors by comparing with the solution of LINGO solver.

The development of a shape optimization solver using the existing Computational Fluid Dynamics (CFD) codes is taken up as topic of research in this thesis. A shape optimizer was initially developed based on Genetic Algorithm (GA) coupled with a CFD solver in an earlier work. The existing CFD solver is based on Kinetic Flux Vector Splitting and uses least squares discretization. This solver requires a cloud of points and their connectivity set, hence this CFD solver is a meshless solver. The advantage of a meshless solver is utilised in avoiding re-gridding (only connectivity regeneration is required) after each shape change by the shape optimizer. The CFD solver is within the optimization loop, hence evaluation of CFD solver after each shape change is mandatory. Although the earlier shape optimizer developed was found to be robust, but it was taking enoromous amount of time to converge to the optimum solution (details in Appendix). Hence a new evolving method, Ant Colony Optimization (ACO), is implemented to replace GA. A shape optimizer is developed coupling ACO and the meshless CFD solver. To the best of the knowledge of the present author, this is the first time when ACO is implemented for aerodynamic shape optimization problems. Hence, an exhaustive validation has become mandatory. Various test cases such as regeneration problems of (1) subsonic - supersonic nozzle with a shock in quasi - one dimensional flow (2) subsonic - supersonic nozzle in a 2-dimensional flow field (3) NACA 0012 airfoil in 2-dimensional flow and (4) NACA 4412 airfoil in 2-dimensional flow have been successfully demonstrated. A comparative study between GA and ACO at algorithm level is performed using the travelling salesman problem (TSP). A comparative study between the two shape optimizers developed, i.e., GA-CFD and ACO-CFD is carried out using regeneration test case of NACA 4412 airfoil in 2-dimensional flow. GA-CFD performs better in the initial phase of optimization and ACO-CFD performs better in the later stage. We have combined both the approaches to develop a hybrid GA-ACO-CFD solver such that the advantages of both GA-CFD and ACO-CFD are retained with the hybrid method. This hybrid approach has 2 stages, namely, (Stage 1) initial optimum search by GA-CFD (coarse search), the best members from the optimized solution from GA-CFD are segregated to form the input for the fine search by ACO-CFD and (Stage 2) final optimum search by ACO-CFD (fine search). It is observed that this hybrid method performs better than either GA-CFD or ACO- CFD, i.e., hybrid method attains better optimum in less number of CFD calls. This hybrid method is applied to the following test cases: (1) regeneration of subsonic-supersonic nozzle with shock in quasi 1-D flow and (2) regeneration of NACA 4412 airfoil in 2-dimensional flow. Two applications on shape optimization, namely, (1) shape optimization of a body in strongly rotating viscous flow and (2) shape optimization of a body in supersonic flow such that it enhances separation of binary species, have been successfully demonstrated using the hybrid GA-ACO-CFD method. A KFVS based binary diffusion solver was developed and validated for this purpose. This hybrid method is now in a state where industrial shape optimization applications can be handled confidently.

Most of the real world problems in water resources involve nonlinear formulations in their solution construction. Obtaining optimal solutions for large scale nonlinear optimization problems is always a challenging task. The conventional methods, such as linear programming (LP), dynamic programming (DP) and nonlinear programming (NLP) may often face problems in solving them. Recently, there has been an increasing interest in biologically motivated adaptive systems for solving real world optimization problems. The multi-member, stochastic approach followed in Evolutionary Algorithms (EA) makes them less susceptible to getting trapped at local optimal solutions, and they can search easier for global optimal solutions. In this thesis, efficient optimization techniques based on swarm intelligence and evolutionary computation principles have been proposed for single and multi-objective optimization in water resource systems. To overcome the inherent limitations of conventional optimization techniques, meta-heuristic techniques like ant colony optimization (ACO), particle swarm optimization (PSO) and differential evolution (DE) approaches are developed for single and multi-objective optimization. These methods are then applied to few case studies in planning and operation of reservoir systems in India. First a methodology based on ant colony optimization (ACO) principles is investigated for reservoir operation. The utility of the ACO technique for obtaining optimal solutions is explored for large scale nonlinear optimization problems, by solving a reservoir operation problem for monthly operation over a long-time horizon of 36 years. It is found that this methodology relaxes the over-year storage constraints and provides efficient operating policy that can be implemented over a long period of time. By using ACO technique for reservoir operation problems, some of the limitations of traditional nonlinear optimization methods are surmounted and thus the performance of the reservoir system is improved. To achieve faster optimization in water resource systems, a novel technique based on swarm intelligence, namely particle swarm optimization (PSO) has been proposed. In general, PSO has distinctly faster convergence towards global optimal solutions for numerical optimization. However, it is found that the technique has the problem of getting trapped to local optima while solving real world complex problems. To overcome such drawbacks, the standard particle swarm optimization technique has been further improved by incorporating a novel elitist-mutation (EM) mechanism into the algorithm. This strategy provides proper exploration and exploitation throughout the iterations. The improvement is demonstrated by applying it to a multi-purpose single reservoir problem and also to a multi reservoir system. The results showed robust performance of the EM-PSO approach in yielding global optimal solutions. Most of the practical problems in water resources are not only nonlinear in their formulations but are also multi-objective in nature. For multi-objective optimization, generating feasible efficient Pareto-optimal solutions is always a complicated task. In the past, many attempts with various conventional approaches were made to solve water resources problems and some of them are reported as successful. However, in using the conventional linear programming (LP) and nonlinear programming (NLP) methods, they usually involve essential approximations, especially while dealing withdiscontinuous, non-differentiable, non-convex and multi-objective functions. Most of these methods consider multiple objective functions using weighted approach or constrained approach without considering all the objectives simultaneously. Also, the conventional approaches use a point-by-point search approach, in which the outcome of these methods is a single optimal solution. So they may require a large number of simulation runs to arrive at a good Pareto optimal front. One of the major goals in multi-objective optimization is to find a set of well distributed optimal solutions along the true Pareto optimal front. The classical optimization methods often fail to attain a good and true Pareto optimal front due to accretion of the above problems. To overcome such drawbacks of the classical methods, there has recently been an increasing interest in evolutionary computation methods for solving real world multi-objective problems. In this thesis, some novel approaches for multi-objective optimization are developed based on swarm intelligence and evolutionary computation principles. By incorporating Pareto optimality principles into particle swarm optimization algorithm, a novel approach for multi-objective optimization has been developed. To obtain efficient Pareto-frontiers, along with proper selection scheme and diversity preserving mechanisms, an efficient elitist mutation strategy is proposed. The developed elitist-mutated multi-objective particle swarm optimization (EM-MOPSO) technique is tested for various numerical test problems and engineering design problems. It is found that the EM-MOPSO algorithm resulting in improved performance over a state-of-the-art multi-objective evolutionary algorithm (MOEA). The utility of EM-MOPSO technique for water resources optimization is demonstrated through application to a case study, to obtain optimal trade-off solutions to a reservoir operation problem. Through multi-objective analysis for reservoir operation policies, it is found that the technique can offer wide range of efficient alternatives along with flexibility to the decision maker. In general, most of the water resources optimization problems involve interdependence relations among the various decision variables. By using differential evolution (DE) scheme, which has a proven ability of effective handling of this kind of interdependence relationships, an efficient multi-objective solver, namely multi-objective differential evolution (MODE) is proposed. The single objective differential evolution algorithm is extended to multi-objective optimization by integrating various operators like, Pareto-optimality, non-dominated sorting, an efficient selection strategy, crowding distance operator for maintaining diversity, an external elite archive for storing non- dominated solutions and an effective constraint handling scheme. First, different variations of DE approaches for multi-objective optimization are evaluated through several benchmark test problems for numerical optimization. The developed MODE algorithm showed improved performance over a standard MOEA, namely non-dominated sorting genetic algorithm–II (NSGA-II). Then MODE is applied to a case study of Hirakud reservoir operation problem to derive operational tradeoffs in the reservoir system optimization. It is found that MODE is achieving robust performance in evaluation for the water resources problem, and that the interdependence relationships among the decision variables can be effectively modeled using differential evolution operators. For optimal utilization of scarce water resources, an integrated operational model is developed for reservoir operation for irrigation of multiple crops. The model integrates the dynamics associated with the water released from a reservoir to the actual water utilized by the crops at farm level. It also takes into account the non-linear relationship of root growth, soil heterogeneity, soil moisture dynamics for multiple crops and yield response to water deficit at various growth stages of the crops. Two types of objective functions are evaluated for the model by applying to a case study of Malaprabha reservoir project. It is found that both the cropping area and economic benefits from the crops need to be accounted for in the objective function. In this connection, a multi-objective frame work is developed and solved using the MODE algorithm to derive simultaneous policies for irrigation cropping pattern and reservoir operation. It is found that the proposed frame work can provide effective and flexible policies for decision maker aiming at maximization of overall benefits from the irrigation system. For efficient management of water resources projects, there is always a great necessity to accurately forecast the hydrologic variables. To handle uncertain behavior of hydrologic variables, soft computing based artificial neural networks (ANNs) and fuzzy inference system (FIS) models are proposed for reservoir inflow forecasting. The forecast models are developed using large scale climate inputs like indices of El-Nino Southern Oscialltion (ENSO), past information on rainfall in the catchment area and inflows into the reservoir. In this purpose, back propagation neural network (BPNN), hybrid particle swarm optimization trained neural network (PSONN) and adaptive network fuzzy inference system (ANFIS) models have been developed. The developed models are applied for forecasting inflows into the Malaprabha reservoir. The performances of these models are evaluated using standard performance measures and it is found that the hybrid PSONN model is performing better than BPNN and ANFIS models. Finally by adopting PSONN model for inflow forecasting and EMPSO technique for solving the reservoir operation model, the practical utility of the different models developed in the thesis are demonstrated through application to a real time reservoir operation problem. The developed methodologies can certainly help in better planning and operation of the scarce water resources.

No description available.

The multiple constant multiplication (MCM) operation is a fundamental operation in digital signal processing (DSP) and digital image processing (DIP). Examples of the MCM are in finite impulse response (FIR) and infinite impulse response (IIR) filters, matrix multiplication, and transforms. The aim of this work is minimizing the complexity of the MCM operation using common subexpression elimination (CSE) technique and redundant number representations. The CSE technique searches and eliminates common digit patterns (subexpressions) among MCM coefficients. More common subexpressions can be found by representing the MCM coefficients using redundant number representations. A CSE algorithm is proposed that works on a type of redundant numbers called the zero-dominant set (ZDS). The ZDS is an extension over the representations of minimum number of non-zero digits called minimum Hamming weight (MHW). Using the ZDS improves CSE algorithms' performance as compared with using the MHW representations. The disadvantage of using the ZDS is it increases the possibility of overlapping patterns (digit collisions). In this case, one or more digits are shared between a number of patterns. Eliminating a pattern results in losing other patterns because of eliminating the common digits. A pattern preservation algorithm (PPA) is developed to resolve the overlapping patterns in the representations. A tree and graph encoders are proposed to generate a larger space of number representations. The algorithms generate redundant representations of a value for a given digit set, radix, and wordlength. The tree encoder is modified to search for common subexpressions simultaneously with generating of the representation tree. A complexity measure is proposed to compare between the subexpressions at each node. The algorithm terminates generating the rest of the representation tree when it finds subexpressions with maximum sharing. This reduces the search space while minimizes the hardware complexity. A combinatoric model of the MCM problem is proposed in this work. The model is obtained by enumerating all the possible solutions of the MCM that resemble a graph called the demand graph. Arc routing on this graph gives the solutions of the MCM problem. A similar arc routing is found in the capacitated arc routing such as the winter salting problem. Ant colony optimization (ACO) meta-heuristics is proposed to traverse the demand graph. The ACO is simulated on a PC using Python programming language. This is to verify the model correctness and the work of the ACO. A parallel simulation of the ACO is carried out on a multi-core super computer using C++ boost graph library.