A Comparison of three evolutionary strategies for multiobjective genetic programming

We report what we believe to be the first comparative study of multi-objective genetic programming (GP) algorithms on benchmark symbolic regression and machine learning problems. We compare the Strength Pareto Evolutionary Algorithm (SPEA2), the Non-dominated Sorting Genetic Algorithm (NSGA-II) and the Pareto Converging Genetic Algorithm (PCGA) evolutionary paradigms. As well as comparing the quality of the final solutions, we also examine the speed of convergence of the three evolutionary algorithms. Based on our observations, the SPEA2-based algorithm appears to have problems controlling tree bloat—that is, the uncontrolled growth in the size of the chromosomal tree structures. The NSGA-II-based algorithm on the other hand seems to experience difficulties in locating low error solutions. Overall, the PCGA-based algorithm gives solutions with the lowest errors and the lowest mean complexity.     

DOPGA: a new fitness assignment scheme for multi-objective evolutionary algorithms

In this article, a new fitness assignment scheme to evaluate the Pareto-optimal solutions for multi-objective evolutionary algorithms is proposed. The proposed DOmination Power of an individual Genetic Algorithm (DOPGA) method can order the individuals in a form in which each individual (the so-called solution) could have a unique rank. With this new method, a multi-objective problem can be treated as if it were a single-objective problem without drastically deviating from the Pareto definition. In DOPGA, relative position of a solution is embedded into the fitness assignment procedures. We compare the performance of the algorithm with two benchmark evolutionary algorithms (Strength Pareto Evolutionary Algorithm (SPEA) and Strength Pareto Evolutionary Algorithm 2 (SPEA2)) on 12 unconstrained bi-objective and one tri-objective test problems. DOPGA significantly outperforms SPEA on all test problems. DOPGA performs better than SPEA2 in terms of convergence metric on all test problems. Also, Pareto-optimal solutions found by DOPGA spread better than SPEA2 on eight of 13 test problems.     

Achieving super-linear performance in parallel multi-objective evolutionary algorithms by means of cooperative coevolution

This article introduces three new multi-objective cooperative coevolutionary variants of three state-of-the-art multi-objective evolutionary algorithms, namely, Non-dominated Sorting Genetic Algorithm II (NSGA-II), Strength Pareto Evolutionary Algorithm 2 (SPEA2) and Multi-objective Cellular Genetic Algorithm (MOCell). In such a coevolutionary architecture, the population is split into several subpopulations or islands, each of them being in charge of optimizing a subset of the global solution by using the original multi-objective algorithm. Evaluation of complete solutions is achieved through cooperation, i.e., all subpopulations share a subset of their current partial solutions. Our purpose is to study how the performance of the cooperative coevolutionary multi-objective approaches can be drastically increased with respect to their corresponding original versions. This is specially interesting for solving complex problems involving a large number of variables, since the problem decomposition performed by the model at the island level allows for much faster executions (the number of variables to handle in every island is divided by the number of islands). We conduct a study on a real-world problem related to grid computing, the bi-objective robust scheduling problem of independent tasks. The goal in this problem is to minimize makespan (i.e., the time when the latest machine finishes its assigned tasks) and to maximize the robustness of the schedule (i.e., its tolerance to unexpected changes on the estimated time to complete the tasks). We propose a parallel, multithreaded implementation of the coevolutionary algorithms and we have analyzed the results obtained in terms of both the quality of the Pareto front approximations yielded by the techniques as well as the resulting speedups when running them on a multicore machine.     

Implementation and comparison of algorithms for multi-objective optimization based on genetic algorithms applied to the management of an automated warehouse

The paper presents strategies optimization for an existing automated warehouse located in a steelmaking industry. Genetic algorithms are applied to this purpose and three different popular algorithms capable to deal with multi-objective optimization are compared. The three algorithms, namely the Niched Pareto Genetic Algorithm, the Non-dominated Sorting Genetic Algorithm 2 and the Strength Pareto Genetic Algorithm 2, are described in details and the achieved results are widely discussed; moreover several statistical tests have been applied in order to evaluate the statistical significance of the obtained results.     

Main Memory-Based Algorithms for Efficient Parallel Aggregation for Temporal Databases

The ability to model the temporal dimension is essential to many applications. Furthermore, the rate of increase in database size and stringency of response time requirements has out-paced advancements in processor and mass storage technology, leading to the need for parallel temporal database management systems. In this paper, we introduce a variety of parallel temporal aggregation algorithms for the shared-nothing architecture; these algorithms are based on the sequential Aggregation Tree algorithm. We are particularly interested in developing parallel algorithms that can maximally exploit available memory to quickly compute large-scale temporal aggregates without intermediate disk writes and reads. Via an empirical study, we found that the number of processing nodes, the partitioning of the data, the placement of results, and the degree of data reduction effected by the aggregation impacted the performance of the algorithms. For distributed result placement, we discovered that Greedy Time Division Merge was the obvious choice. For centralized results and high data reduction, Pairwise Merge was preferred for a large number of processing nodes; for low data reduction, it only performed well up to 32 nodes. This led us to a centralized variant of Greedy Time Division Merge which was best for the remaining cases. We present a cost model that closely predicts the running time of Greedy Time Division Merge.     

Combination of data replication and scheduling algorithm for improving data availability in Data Grids

Data Grid is a geographically distributed environment that deals with large-scale data-intensive applications. Effective scheduling in Grid can reduce the amount of data transferred among nodes by submitting a job to a node, where most of the requested data files are available. Data replication is another key optimization technique for reducing access latency and managing large data by storing data in a wisely manner. In this paper two algorithms are proposed, first a novel job scheduling algorithm called Combined Scheduling Strategy (CSS) that uses hierarchical scheduling to reduce the search time for an appropriate computing node. It considers the number of jobs waiting in queue, the location of required data for the job and the computing capacity of sites. Second a dynamic data replication strategy, called the Modified Dynamic Hierarchical Replication Algorithm (MDHRA) that improves file access time. This strategy is an enhanced version of Dynamic Hierarchical Replication (DHR) strategy. Data replication should be used wisely because the storage capacity of each Grid site is limited. Thus, it is important to design an effective strategy for the replication replacement. MDHRA replaces replicas based on the last time the replica was requested, number of access, and size of replica. It selects the best replica location from among the many replicas based on response time that can be determined by considering the data transfer time, the storage access latency, the replica requests that waiting in the storage queue and the distance between nodes. The simulation results demonstrate the proposed replication and scheduling strategies give better performance compared to the other algorithms.     

Prediction of performance and processor requirements in real-timedata flow architectures

Presents a new data flow graph model for describing the real-time execution of iterative control and signal processing algorithms on multiprocessor data flow architectures. Identified by the acronym ATAMM, for Algorithm to Architecture Mapping Model, the model is important because it specifies criteria for a multiprocessor operating system to achieve predictable and reliable performance. Algorithm performance is characterized by execution time and iteration period. For a given data flow graph representation, the model facilitates calculation of greatest lower bounds for these performance measures. When sufficient processors are available, the system executes algorithms with minimum execution time and minimum iteration period, and the number of processors required is calculated. When only limited processors are available or when processors fail, performance is made to degrade gracefully and predictably. The user off-line is able to specify tradeoffs between increasing execution time or increasing iteration period. The approach to achieving predictable performance is to control the injection rate of input data and to modify the data flow graph precedence relations so that a processor is always available to execute an enabled graph node. An implementation of the ATAMM model in a four-processor architecture based on Westinghouse's VHSIC 1750A Instruction Set Processor is described     

一种双样本多分形视图尺寸估计算法

视图尺寸估计是数据仓库实化视图选择和分配预聚集视图存储空间的前提。本文提出了双样本多分形视图尺寸估计算法MDS；同时，为了研究MDS算法的有效性，本文把它与Cardenas^n formula、SF和FMS算法进行了比较。实验结果表明，MDS算法优于其它算法。     

Multiobjective optimization of complex antenna structures using response surface models

A very efficient multiobjective (MO) design technique for complex antenna structures involving a large number of design parameters is presented. This design technique, multiobjective‐fractional factorial design (MO‐FFD), is very different from conventional Pareto‐based MO algorithms, which take a great deal of effort to balance the trade‐off between all the design specifications. By performing one single combination of simulations, all the response surface models of design goals are simultaneously built, and Derringer's desirability functions are readily applied to these models so that the optimum structure is obtained. Compared to classical MO algorithms such as Strength Pareto Evolutionary Algorithm 2, nondominated sorting particle swarm optimizer, and cultural MO particle swarm optimization, MO‐FFD yields more desirable performances yet the required number of simulations is reduced by 97%. This article thoroughly illustrates the mathematical development of MO‐FFD, deriving a novel application of ultrawideband (UWB) antennas because of its MO optimization capability. More explicitly, MO‐FFD overcomes all the design challenges of dual band‐notched UWB antennas including desired impedance characteristics, enhanced fidelity factors, and uniform peak gains over the passband, which are what conventional Pareto‐based algorithms cannot attain. The measured results show that all the performance criteria are met; especially, the time‐domain signal distortion is minimized. © 2015 Wiley Periodicals, Inc. Int J RF and Microwave CAE 26:62–71, 2016.     

An evolutionary algorithm for clustering data streams with a variable number of clusters

Several algorithms for clustering data streams based on k-Means have been proposed in the literature. However, most of them assume that the number of clusters, k, is known a priori by the user and can be kept fixed throughout the data analysis process. Besides the difficulty in choosing k, data stream clustering imposes several challenges to be addressed, such as addressing non-stationary, unbounded data that arrive in an online fashion. In this paper, we propose a Fast Evolutionary Algorithm for Clustering data streams (FEAC-Stream) that allows estimating k automatically from data in an online fashion. FEAC-Stream uses the Page–Hinkley Test to detect eventual degradation in the quality of the induced clusters, thereby triggering an evolutionary algorithm that re-estimates k accordingly. FEAC-Stream relies on the assumption that clusters of (partially unknown) data can provide useful information about the dynamics of the data stream. We illustrate the potential of FEAC-Stream in a set of experiments using both synthetic and real-world data streams, comparing it to four related algorithms, namely: CluStream-OMRk, CluStream-BkM, StreamKM++-OMRk and StreamKM++-BkM. The obtained results show that FEAC-Stream provides good data partitions and that it can detect, and accordingly react to, data changes.