Thesis (M.S.)--Rochester Institute of Technology, 2007. / Typescript. Includes bibliographical references (leaves 61-64).

Grid computing has emerged as a global platform to support organizations for coordinated sharing of distributed data, applications, and processes. Additionally, Grid computing has also leveraged web services to define standard interfaces for Grid services adopting the service-oriented view. Consequently, there have been significant efforts to enable applications capable of tackling computationally intensive problems as services on the Grid. In order to ensure that the available services are assigned to the high volume of incoming requests efficiently, it is important to have a robust service selection algorithm. The selection algorithm should not only increase access to the distributed services, promoting operational flexibility and collaboration, but should also allow service providers to scale efficiently to meet a variety of demands while adhering to certain current Quality of Service (QoS) standards. In this research, two service selection algorithms, namely the Particle Swarm Intelligence based Service Selection Algorithm (PSI Selection Algorithm) based on the Multiple Objective Particle Swarm Optimization algorithm using Crowding Distance technique, and the Constraint Satisfaction based Selection (CSS) algorithm, are proposed. The proposed selection algorithms are designed to achieve the following goals: handling large number of incoming requests simultaneously; achieving high match scores in the case of competitive matching of similar types of incoming requests; assigning each services efficiently to all the incoming requests; providing the service requesters the flexibility to provide multiple service selection criteria based on a QoS metric; selecting the appropriate services for the incoming requests within a reasonable time. Next, the two algorithms are verified by a standard assignment problem algorithm called the Munkres algorithm. The feasibility and the accuracy of the proposed algorithms are then tested using various evaluation methods. These evaluations are based on various real world scenarios to check the accuracy of the algorithm, which is primarily based on how closely the requests are being matched to the available services based on the QoS parameters provided by the requesters.

The main contributions of this thesis are located in the domain of wireless sensor netorks. More in detail, we introduce energyaware algorithms and protocols in the context of the following topics: self-synchronized duty-cycling in networks with energy harvesting capabilities, distributed graph coloring and minimum energy broadcasting with realistic antennas. In the following, we review the research conducted in each case. We propose a self-synchronized duty-cycling mechanism for sensor networks. This mechanism is based on the working and resting phases of natural ant colonies, which show self-synchronized activity phases. The main goal of duty-cycling methods is to save energy by efficiently alternating between different states. In the case at hand, we considered two different states: the sleep state, where communications are not possible and energy consumption is low; and the active state, where communication result in a higher energy consumption. In order to test the model, we conducted an extensive experimentation with synchronous simulations on mobile networks and static networks, and also considering asynchronous networks. Later, we extended this work by assuming a broader point of view and including a comprehensive study of the parameters. In addition, thanks to a collaboration with the Technical University of Braunschweig, we were able to test our algorithm in the real sensor network simulator Shawn (http://shawn.sf.net). The second part of this thesis is devoted to the desynchronization of wireless sensor nodes and its application to the distributed graph coloring problem. In particular, our research is inspired by the calling behavior of Japanese tree frogs, whose males use their calls to attract females. Interestingly, as female frogs are only able to correctly localize the male frogs when their calls are not too close in time, groups of males that are located nearby each other desynchronize their calls. Based on a model of this behavior from the literature, we propose a novel algorithm with applications to the field of sensor networks. More in detail, we analyzed the ability of the algorithm to desynchronize neighboring nodes. Furthermore, we considered extensions of the original model, hereby improving its desynchronization capabilities.To illustrate the potential benefits of desynchronized networks, we then focused on distributed graph coloring. Later, we analyzed the algorithm more extensively and show its performance on a larger set of benchmark instances. The classical minimum energy broadcast (MEB) problem in wireless ad hoc networks, which is well-studied in the scientific literature, considers an antenna model that allows the adjustment of the transmission power to any desired real value from zero up to the maximum transmission power level. However, when specifically considering sensor networks, a look at the currently available hardware shows that this antenna model is not very realistic. In this work we re-formulate the MEB problem for an antenna model that is realistic for sensor networks. In this antenna model transmission power levels are chosen from a finite set of possible ones. A further contribution concerns the adaptation of an ant colony optimization algorithm --currently being the state of the art for the classical MEB problem-- to the more realistic problem version, the so-called minimum energy broadcast problem with realistic antennas (MEBRA). The obtained results show that the advantage of ant colony optimization over classical heuristics even grows when the number of possible transmission power levels decreases. Finally we build a distributed version of the algorithm, which also compares quite favorably against centralized heuristics from the literature. / Las principles contribuciones de esta tesis se encuentran en el domino de las redes de sensores inalámbricas. Más en detalle, introducimos algoritmos y protocolos que intentan minimizar el consumo energético para los siguientes problemas: gestión autosincronizada de encendido y apagado de sensores con capacidad para obtener energía del ambiente, coloreado de grafos distribuido y broadcasting de consumo mínimo en entornos con antenas reales. En primer lugar, proponemos un sistema capaz de autosincronizar los ciclos de encendido y apagado de los nodos de una red de sensores. El mecanismo está basado en las fases de trabajo y reposo de las colonias de hormigas tal y como estas pueden observarse en la naturaleza, es decir, con fases de actividad autosincronizadas. El principal objectivo de este tipo de técnicas es ahorrar energía gracias a alternar estados de forma eficiente. En este caso en concreto, consideramos dos estados diferentes: el estado dormido, en el que los nodos no pueden comunicarse y el consumo energético es bajo; y el estado activo, en el que las comunicaciones propician un consumo energético elevado. Con el objetivo de probar el modelo, se ha llevado a cabo una extensa experimentación que incluye tanto simulaciones síncronas en redes móviles y estáticas, como simulaciones en redes asíncronas. Además, este trabajo se extendió asumiendo un punto de vista más amplio e incluyendo un detallado estudio de los parámetros del algoritmo. Finalmente, gracias a la colaboración con la Technical University of Braunschweig, tuvimos la oportunidad de probar el mecanismo en el simulador realista de redes de sensores, Shawn (http://shawn.sf.net). La segunda parte de esta tesis está dedicada a la desincronización de nodos en redes de sensores y a su aplicación al problema del coloreado de grafos de forma distribuida. En particular, nuestra investigación está inspirada por el canto de las ranas de árbol japonesas, cuyos machos utilizan su canto para atraer a las hembras. Resulta interesante que debido a que las hembras solo son capaces de localizar las ranas macho cuando sus cantos no están demasiado cerca en el tiempo, los grupos de machos que se hallan en una misma región desincronizan sus cantos. Basado en un modelo de este comportamiento que se encuentra en la literatura, proponemos un nuevo algoritmo con aplicaciones al campo de las redes de sensores. Más en detalle, analizamos la habilidad del algoritmo para desincronizar nodos vecinos. Además, consideramos extensiones del modelo original, mejorando su capacidad de desincronización. Para ilustrar los potenciales beneficios de las redes desincronizadas, nos centramos en el problema del coloreado de grafos distribuido que tiene relación con diferentes tareas habituales en redes de sensores. El clásico problema del broadcasting de consumo mínimo en redes ad hoc ha sido bien estudiado en la literatura. El problema considera un modelo de antena que permite transmitir a cualquier potencia elegida (hasta un máximo establecido por el dispositivo). Sin embargo, cuando se trabaja de forma específica con redes de sensores, un vistazo al hardware actualmente disponible muestra que este modelo de antena no es demasiado realista. En este trabajo reformulamos el problema para el modelo de antena más habitual en redes de sensores. En este modelo, los niveles de potencia de transmisión se eligen de un conjunto finito de posibilidades. La siguiente contribución consiste en en la adaptación de un algoritmo de optimización por colonias de hormigas a la versión más realista del problema, también conocida como broadcasting de consumo mínimo con antenas realistas. Los resultados obtenidos muestran que la ventaja de este método sobre heurísticas clásicas incluso crece cuando el número de posibles potencias de transmisión decrece. Además, se ha presentado una versión distribuida del algoritmo, que también se compara de forma bastante favorable contra las heurísticas centralizadas conocidas.

Exploring a set of unlabeled data to extract the similar clusters, known as data clustering, is an appealing problem in machine learning. In other words, data clustering organizes the underlying data into different groups using a notion of similarity between patterns. A new approach to solve the data clustering problem based on multiple cooperative swarms is introduced. The proposed approach is inspired by the social swarming behavior of biological bird flocks which search for food situated in several places. The proposed approach is composed of two main phases, namely, initialization and exploitation. In the initialization phase, the aim is to distribute the search space among several swarms. That is, a part of the search space is assigned to each swarm in this phase. In the exploitation phase, each swarm searches for the center of its associated cluster while cooperating with other swarms. The search proceeds to converge to a near-optimal solution. As compared to the single swarm clustering approach, the proposed multiple cooperative swarms provide better solutions in terms of fitness function measure for the cluster centers, as the dimensionality of data and number of clusters increase. The multiple cooperative swarms clustering approach assumes that the number of clusters is known a priori. The notion of stability analysis is proposed to extract the number of clusters for the underlying data using multiple cooperative swarms. The mathematical explanations demonstrating why the proposed approach leads to more stable and robust results than those of the single swarm clustering are also provided. Application of the proposed multiple cooperative swarms clustering is considered for one of the most challenging problems in speech recognition: phoneme recognition. The proposed approach is used to decompose the recognition task into a number of subtasks or modules. Each module involves a set of similar phonemes known as a phoneme family. Basically, the goal is to obtain the best solution for phoneme families using the proposed multiple cooperative swarms clustering. The experiments using the standard TIMIT corpus indicate that using the proposed clustering approach boosts the accuracy of the modular approach for phoneme recognition considerably.

Exploring a set of unlabeled data to extract the similar clusters, known as data clustering, is an appealing problem in machine learning. In other words, data clustering organizes the underlying data into different groups using a notion of similarity between patterns. A new approach to solve the data clustering problem based on multiple cooperative swarms is introduced. The proposed approach is inspired by the social swarming behavior of biological bird flocks which search for food situated in several places. The proposed approach is composed of two main phases, namely, initialization and exploitation. In the initialization phase, the aim is to distribute the search space among several swarms. That is, a part of the search space is assigned to each swarm in this phase. In the exploitation phase, each swarm searches for the center of its associated cluster while cooperating with other swarms. The search proceeds to converge to a near-optimal solution. As compared to the single swarm clustering approach, the proposed multiple cooperative swarms provide better solutions in terms of fitness function measure for the cluster centers, as the dimensionality of data and number of clusters increase. The multiple cooperative swarms clustering approach assumes that the number of clusters is known a priori. The notion of stability analysis is proposed to extract the number of clusters for the underlying data using multiple cooperative swarms. The mathematical explanations demonstrating why the proposed approach leads to more stable and robust results than those of the single swarm clustering are also provided. Application of the proposed multiple cooperative swarms clustering is considered for one of the most challenging problems in speech recognition: phoneme recognition. The proposed approach is used to decompose the recognition task into a number of subtasks or modules. Each module involves a set of similar phonemes known as a phoneme family. Basically, the goal is to obtain the best solution for phoneme families using the proposed multiple cooperative swarms clustering. The experiments using the standard TIMIT corpus indicate that using the proposed clustering approach boosts the accuracy of the modular approach for phoneme recognition considerably.

Grid computing has emerged as a global platform to support organizations for coordinated sharing of distributed data, applications, and processes. Additionally, Grid computing has also leveraged web services to define standard interfaces for Grid services adopting the service-oriented view. Consequently, there have been significant efforts to enable applications capable of tackling computationally intensive problems as services on the Grid. In order to ensure that the available services are assigned to the high volume of incoming requests efficiently, it is important to have a robust service selection algorithm. The selection algorithm should not only increase access to the distributed services, promoting operational flexibility and collaboration, but should also allow service providers to scale efficiently to meet a variety of demands while adhering to certain current Quality of Service (QoS) standards. In this research, two service selection algorithms, namely the Particle Swarm Intelligence based Service Selection Algorithm (PSI Selection Algorithm) based on the Multiple Objective Particle Swarm Optimization algorithm using Crowding Distance technique, and the Constraint Satisfaction based Selection (CSS) algorithm, are proposed. The proposed selection algorithms are designed to achieve the following goals: handling large number of incoming requests simultaneously; achieving high match scores in the case of competitive matching of similar types of incoming requests; assigning each services efficiently to all the incoming requests; providing the service requesters the flexibility to provide multiple service selection criteria based on a QoS metric; selecting the appropriate services for the incoming requests within a reasonable time. Next, the two algorithms are verified by a standard assignment problem algorithm called the Munkres algorithm. The feasibility and the accuracy of the proposed algorithms are then tested using various evaluation methods. These evaluations are based on various real world scenarios to check the accuracy of the algorithm, which is primarily based on how closely the requests are being matched to the available services based on the QoS parameters provided by the requesters.

Thesis (Ph. D.)--University of California, San Diego, 2003. / Vita. Includes bibliographical references (leaves 270-281).

Optimization is a mathematical technique that concerns the finding of maxima or minima of functions in some feasible region. There is no business or industry which is not involved in solving optimization problems. A variety of optimization techniques compete for the best solution. Particle Swarm Optimization (PSO) is a relatively new, modern, and powerful method of optimization that has been empirically shown to perform well on many of these optimization problems. It is widely used to find the global optimum solution in a complex search space. This thesis aims at providing a review and discussion of the most established results on PSO algorithm as well as exposing the most active research topics that can give initiative for future work and help the practitioner improve better result with little effort. This paper introduces a theoretical idea and detailed explanation of the PSO algorithm, the advantages and disadvantages, the effects and judicious selection of the various parameters. Moreover, this thesis discusses a study of boundary conditions with the invisible wall technique, controlling the convergence behaviors of PSO, discrete-valued problems, multi-objective PSO, and applications of PSO. Finally, this paper presents some kinds of improved versions as well as recent progress in the development of the PSO, and the future research issues are also given.

Trading rules have been utilized in the stock market to make profit for more than a century. However, only using a single trading rule may not be sufficient to predict the stock price trend accurately. Although some complex trading strategies combining various classes of trading rules have been proposed in the literature, they often pick only one rule for each class, which may lose valuable information from other rules in the same class. In this thesis, a complex stock trading strategy, namely Performance-based Reward Strategy (PRS), is proposed. PRS combines the seven most popular classes of trading rules in financial markets, and for each class of trading rule, PRS includes various combinations of the rule parameters to produce a universe of 1059 component trading rules in all. Each component rule is assigned a starting weight and a reward/penalty mechanism based on profit is proposed to update these rules’ weights over time. To determine the best parameter values of PRS, we employ an improved time variant Particle Swarm Optimization (PSO) algorithm with the objective of maximizing the annual net profit generated by PRS. Due to the large number of component rules and swarm size, the optimization time is significant. A parallel PSO based on Hadoop, an open source parallel programming model of MapReduce, is employed to optimize PRS more efficiently. By omitting the traditional reduce phase of MapReduce, the proposed parallel PSO avoids the I/O cost of intermediate data and gets higher speedup ratio than previous parallel PSO based on MapReduce. After being optimized in an eight years training period, PRS is tested on an out-of-sample data set. The experimental results show that PRS outperforms all of the component rules in the testing period. / published_or_final_version / Computer Science / Master / Master of Philosophy

Πολλά συστήματα πολλαπλών διαμεσολαβητών είναι εμπνευσμένα από διάφορες κοινωνίες εντόμων, τα οποία συλλογικά πετυχαίνουν διάφορους στόχους οι οποίοι είναι αδύνατο να επιτευχθούν σε ατομικό επίπεδο. Στις περισσότερες περιπτώσεις, κινητήρια δύναμη στην «συνεργασία» και τη συλλογικότητα των εντόμων είναι η στιγματική συμπεριφορά (stigmergy). Ο όρος αυτός χρησιμοποιείται στη βιολογία για να περιγράψει τον τρόπο επίδρασης αλλαγών στο περιβάλλον που προέκυψαν από μια παρελθοντική συμπεριφορά κάποιων κοινωνικών εντόμων στην συμπεριφορά ατόμων της ίδιας ομάδας. Χαρακτηριστικά παραδείγματα από τη φύση βρίσκουμε σε κάποια είδη μυρμηγκιών με τον τρόπο αναζήτησης τροφής και τη δημιουργία διαδρομών μεταξύ φωλιάς και πηγών τροφής ή την κατασκευαστική διαδικασία των τερμιτών. Αν και η έννοια αυτή είναι άρρητα συνδεδεμένη με την έκκριση μιας η περισσοτέρων χημικών ουσιών (στίγματα) για την έμμεση επικοινωνία μεταξύ ατόμων μιας κοινωνίας εντόμων, έχει εφαρμοστεί σε διαφορετικούς τομείς της επιστήμης των υπολογιστών. Αν και ένα μέρος του κλάδου της τεχνητής ζωής ασχολείται με μια ένα- προς -ένα αντιστοίχηση του έμμεσου αυτού τρόπου επικοινωνίας σε ομάδες ρομπότ που λειτουργούν στον πραγματικό κόσμο με την έκκριση κάποιας αντίστοιχης ουσίας, μεγάλο επιστημονικό ενδιαφέρον υπάρχει για την αναγωγή της έννοιας και της λειτουργίας της στιγματικής συμπεριφοράς στον ψηφιακό κόσμο: Η έννοια των ψηφιακών φερορμονών ή των στιγματικών πακέτων συναντάται, κυρίως σε αντίστοιχους αλγορίθμους δρομολόγησης πακέτων σε ένα δίκτυο κόμβων. Όσο αφορά στην ένα -προς- ένα αντιστοίχηση μηχανισμών σε συστήματα διαμεσολαβητών που λειτουργούν αναλογικά (αισθητήρες) στον πραγματικό κόσμο υπάρχουν περιπτώσεις όπου ενώ ένας στιγματικός μηχανισμός που εμφανίζεται στη φύση φαινομενικά βοηθά στην αντιμετώπιση του προβλήματος που το σύστημα καλείται να αντιμετωπίσει. Η υλοποίηση όμως ενός τέτοιου μηχανισμού μπορεί να είναι ανέφικτη λόγω τεχνικών ή / και οικονομικών λόγων. Ένας προτεινόμενος τρόπος αντιμετώπισης του προβλήματος αυτού είναι η αντιστοίχηση (προσέγγιση) ενός τέτοιου μηχανισμού με ένα μηχανισμό επικοινωνίας ο οποίος θα προσφέρει αντίστοιχα αποτελέσματα χωρίς επιπλέον ή με το μικρότερο κόστος. Για το σκοπό αυτό μπορεί να γίνει χρήση της τεχνολογίας μεταφοράς αναλογικών (π.χ ήχος, φως) ή ψηφιακών σημάτων (π.χ πακέτα δεδομένων). Πόσο στιγματικός όμως είναι μια ένας τρόπος επικοινωνίας μέσω μηνυμάτων, και ποιες είναι οι παραδοχές για κάτι τέτοιο; Μπορεί να υπάρξει αντιστοίχηση της επικοινωνίας (μέσω φερορμονών) που εμφανίζεται στη φύση με κάποιο τρόπο (ασύρματης) επικοινωνίας ο οποίος να μπορεί να εφαρμοστεί σε διαμεσολαβητές περιορισμένων δυνατοτήτων? Η αντιστοίχηση μπορεί να αξιολογηθεί με ποιοτικά κριτήρια όπως η εμφάνιση ή όχι μιας επιθυμητής συμπεριφοράς του συστήματος. Στη διπλωματική αυτή διατριβή παρουσιάζεται ένα μοντέλο ψηφιακής επικοινωνίας το οποίο θεωρητικά αντιστοιχεί στην ποιοτική στιγματική συμπεριφορά ενός συστήματος διαμεσολαβητών. Επιπλέον, εισάγονται δυο μετρήσιμα κριτήρια αξιολόγησης βάση των οποίων μπορεί να γίνει σύγκριση διαφορετικών τρόπων επικοινωνίας. Τα κριτήρια αυτά προκύπτουν από τη μοντελοποίηση μιας κοινής πλατφόρμας – συστήματος διαμεσολαβητών για ένα συγκεκριμένο σενάριο λειτουργίας. Αφού πραγματοποιήθηκαν τρεις σειρές εξομοιώσεων, προέκυψε ότι το σύστημα με χρήση ψηφιακής επικοινωνίας μπορεί να επιτύχει αυτοοργανωτική συμπεριφορά αντίστοιχη με τη συμπεριφορά όταν χρησιμοποιείται στιγματική επικοινωνία ή καμία επικοινωνία. Παρόλα αυτά, η απόδοση του συστήματος βάση των κριτηρίων αξιολόγησης δεν ήταν καλύτερη για τις περισσότερες εξομοιώσεις, κάτι που δεν ήταν θεωρητικά αναμενόμενο. Τέλος, τα αποτελέσματα των εξομοιώσεων οδηγούν σε διάφορα συμπεράσματα τα οποία πρέπει να λαμβάνονται υπόψη στη μελέτη τέτοιων συστημάτων. / Multiagent systems are inspired from insect societies, which collectively achieve different targets, each of is impossible to complete by an individual. In most cases, the driving force to insect “cooperation” and collectiveness is stigmergic behavior. This concept is used in biology to describe the way that environmental changes that occur as a result of a behavior of some social insects, affects the behavior of individuals of the same species. A prominent nature –based example is found in some ant species, where individuals use pheromones during food acquisition, creating different routes between the nest and several food sources. Another example is the termite nest building process. Stigmergy is associated to the emission of one or several chemical substances (stigmata), so as to achieve forms of indirect communication between individuals of a society, although, this concept has been used in different sections of the Computer Science. While much effort is done from the Artificial Life discipline to achieve a one-to-one equivalence of this indirect form of communication into groups of robots that operate in the real world by emitting a pheromone-alike substance, there is much interest in converting this stigmergic behavior to the digital world. The concept of digital pheromones (or stigmergic packets) is met in relative network routing algorithms. Staying on the one-to-one equivalence, there are cases and situations where a proposed stigmergic mechanism can be applied in a multiagent system, where each individual is operating using sensors and actuators inside the real world. However, the implementation of such a mechanism may be unfeasible because of technical, technological or economic reasons. A suggestion to counterattack this limitation is to approximate the stigmergic solution using a different communication mechanism, which may combine feasible, low cost implementation with corresponding to the stigmergic mechanism results. To achieve that, analog (eg light, sound) or digital (data packets) signals may be used. The question is, by using these new concepts, the mechanism of communication is classified as stigmergic and, if yes, are there any admissions? Is there any digital communication analog to the stigmergic communication which may be used to robotic and limited agents? This hypothetical equivalent can be evaluated using qualitative measures like the relevance (or absence) of a desired system behavior In this master thesis, I use a digital communication model which is theoretically assumed to be relative to the quantitative stigmergic behavior of a multiagent system. Additionally, two measurable evaluation criteria are introduced. By using these criteria, different mechanisms of communication may be compared to each other. These criteria result from the modeling of the common platform-multiagent system for a particular scenario of operation. By performing three different series of simulation, there was demonstrated that by using digital communication, the system achieves self organizing behavior relative to the behavior of the same system, using stigmergic or no form of communication. Still, the system performance (according to the introduced evaluation criteria) was not better for most cases of simulations, as it may be expected. Finally, the results lead to several conclusions that must be taken under consideration and further attention for the study of swarm intelligence based systems.