Human evolutionary model: A new approach to optimization

The aim of this paper is to propose the Human Evolutionary Model (HEM) as a novel computational method for solving search and optimization problems with single or multiple objectives. HEM is an intelligent evolutionary optimization method that uses consensus knowledge from experts with the aim of inferring the most suitable parameters to achieve the evolution in an intelligent way. HEM is able to handle experts’ knowledge disagreements by the use of a novel concept called Mediative Fuzzy Logic (MFL). The effectiveness of this computational method is demonstrated through several experiments that were performed using classical test functions as well as composite test functions. We are comparing our results against the results obtained with the Genetic Algorithm of the Matlab’s Toolbox, Evolution Strategy with Covariance Matrix Adaptation (CMA-ES), Particle Swarm Optimizer (PSO), Cooperative PSO (CPSO), G3 model with PCX crossover (G3-PCX), Differential Evolution (DE), and Comprehensive Learning PSO (CLPSO). The results obtained using HEM outperforms the results obtained using the abovementioned optimization methods.     

Graph-based evolutionary design of arithmetic circuits

We present an efficient graph-based evolutionary optimization technique, called evolutionary graph generation (EGG), and the proposed approach is applied to the design of combinational and sequential arithmetic circuits based on parallel counter-tree architecture. The fundamental idea of EGG is to employ general circuit graphs as individuals and manipulate the circuit graphs directly using new evolutionary graph operations without encoding the graphs into other indirect representations, such as the bit strings used in genetic algorithm (GA) proposed by Holland (1992) and trees used in genetic programming (GP) proposed by Koza et al. (1997). In this paper, the EGG system is applied to the design of constant-coefficient multipliers and the design of bit-serial data-parallel adders. The results demonstrate the potential capability of EGG to solve the practical design problems for arithmetic circuits with limited knowledge of computer arithmetic algorithms. The proposed EGG system can help to simplify and speed up the process of designing arithmetic circuits and can produce better solutions to the given problem     

A double-multiplicative dynamic penalty approach for constrained evolutionary optimization

The present paper proposes a double-multiplicative penalty strategy for constrained optimization by means of genetic algorithms (GAs). The aim of this research is to provide a simple and efficient way of handling constrained optimization problems in the GA framework without the need for tuning the values of penalty factors for any given optimization problem. After a short review on the most popular and effective exterior penalty formulations, the proposed penalty strategy is presented and tested on five different benchmark problems. The obtained results are compared with the best solutions provided in the literature, showing the effectiveness of the proposed approach.     

Graph-based traceability: a comprehensive approach

In recent years, traceability has been globally accepted as being a key success factor of software development projects. However, the multitude of different, poorly integrated taxonomies, approaches and technologies impedes the application of traceability techniques in practice. This paper presents a comprehensive view on traceability, pertaining to the whole software development process. Based on the state of the art, the field is structured according to six specific activities related to traceability as follows: definition, recording, identification, maintenance, retrieval, and utilization. Using graph technology, a comprehensive and seamless approach for supporting these activities is derived, combining them in one single conceptual framework. This approach supports the definition of metamodels for traceability information, recording of traceability information in graph-based repositories, identification and maintenance of traceability relationships using transformations, as well as retrieval and utilization of traceability information using a graph query language. The approach presented here is applied in the context of the ReDSeeDS project (Requirements Driven Software Development System) that aims at requirements-based software reuse. ReDSeeDS makes use of traceability information to determine potentially reusable architectures, design, or code artifacts based on a given set of reusable requirements. The project provides case studies from different domains for the validation of the approach.     

A systems approach to evolutionary multiobjective structural optimization and beyond

Multiobjective evolutionary algorithms (MOEAs) have shown to be effective in solving a wide range of test problems. However, it is not straightforward to apply MOEAs to complex real-world problems. This paper discusses the major challenges we face in applying MOEAs to complex structural optimization, including the involvement of time-consuming and multi-disciplinary quality evaluation processes, changing environments, vagueness in formulating criteria formulation, and the involvement of multiple sub-systems. We propose that the successful tackling of all these aspects give birth to a systems approach to evolutionary design optimization characterized by considerations at four levels, namely, the system property level, temporal level, spatial level and process level. Finally, we suggest a few promising future research topics in evolutionary structural design that consist in the necessary steps towards a life-like design approach, where design principles found in biological systems such as self-organization, self-repair and scalability play a central role.     

FaSa: A fast and stable quadratic placement algorithm

Placement is a critical step in VLSI design because it dominates overall speed and quality of design flow.In this paper,a new fast and stable placement algorithm called FaSa is proposed.It uses quadratic programming model and Lagrange multiplier method to solve placement problems.And an incremental LU factorization method is used to solve equations for speeding up.The experimental results show that FaSa is very stable,much faster than previous algorithms and its total wire length is comparable with other algorithms.     

A bi-level evolutionary optimization approach for integrated production and transportation scheduling

This paper investigates an integrated production and transportation scheduling (IPTS) problem which is formulated as a bi-level mixed integer nonlinear program. This problem considers distinct realistic features widely existing in make-to-order supply chains, namely unrelated parallel-machine production environment and product batch-based delivery. An evolution-strategy-based bi-level evolutionary optimization approach is developed to handle the IPTS problem by integrating a memetic algorithm and heuristic rules. The efficiency and effectiveness of the proposed approach is evaluated by numerical experiments based on industrial data and industrial-size problems. Experimental results demonstrate that the proposed approach can effectively solve the problem investigated.     

An evolutionary simulation-based optimization approach for dispatching scheduling

An effective scheduling decision is one of the key factors towards improving the efficiency of a system’s performance, particularly in the instance of multiple products thus dispatching rules have been widely used for real-time scheduling because they can provide a very quick and pretty good solution. However, deciding how to select appropriate rules is very difficult. In this paper, we develop evolutionary simulation-based heuristics to construct near-optimal solutions for dispatching rule allocation. Our heuristic is easy to use and gives a manager a useful tool for testing a configuration that can minimize certain performance measures. The optimization heuristics are used to determine priority strategies to maximize the performance of a complex manufacturing system with a large number of different products, along with an overtime that changes with a mix of different process types, including assembly and disassembly operations and with different types of internal and external disturbances. Modeling is carried out using discrete-event simulation. Case study analysis is of a commercial offset printing production system.     

A mathematical framework for passenger screening optimization via a multi-objective evolutionary approach

Concerns regarding the smuggling of dangerous items into commercial flights escalated after the failed Christmas day bomber attack. As a result, the Transportation Security Agency (TSA) has strengthened its efforts to detect passengers carrying hazardous items by installing novel screening technologies and by increasing the number of random pat-downs performed at security checkpoints nationwide. However, the implementation of such measures has raised privacy and health concerns among different groups thus making the design and evaluation of new inspection strategies strongly necessary. This research presents a mathematical framework to design passenger inspection strategies that include the utilization of novel and traditional technologies (i.e. body scanners, explosive detection systems, explosive trace detectors, walk-through metal detectors, and wands) offered by multiple manufacturers, to identify three types of items: metallic, bulk explosives (i.e. plastic, liquids, gels), and traces of explosives. A multiple objective optimization model is proposed to optimize inspection security, inspection cost, and processing time; an evolutionary approach is used to solve the model. The result is a Pareto set of quasi-optimal solutions representing multiple inspection strategies. Each strategy is different in terms of: (1) configuration, (2) the screening technologies included, (3) threshold calibration, and consequently, (4) inspection security, inspection cost, and processing time.     

A hybrid evolutionary approach for solving constrained optimization problems over finite domains

A novel approach for the integration of evolution programs and constraint-solving techniques over finite domains is presented. This integration provides a problem-independent optimization strategy for large-scale constrained optimization problems over finite domains. In this approach, genetic operators are based on an arc-consistency algorithm, and chromosomes are arc-consistent portions of the search space of the problem. The paper describes the main issues arising in this integration: chromosome representation and evaluation, selection and replacement strategies, and the design of genetic operators. We also present a parallel execution model for a distributed memory architecture of the previous integration. We have adopted a global parallelization approach that preserves the properties, behavior, and fundamentals of the sequential algorithm. Linear speedup is achieved since genetic operators are coarse grained as they perform a search in a discrete space carrying out arc consistency. The implementation has been tested on a GRAY T3E multiprocessor using a complex constrained optimization problem.     

On an evolutionary approach for constrained optimization problem solving

Over the last few decades, many different evolutionary algorithms have been introduced for solving constrained optimization problems. However, due to the variability of problem characteristics, no single algorithm performs consistently over a range of problems. In this paper, instead of introducing another such algorithm, we propose an evolutionary framework that utilizes existing knowledge to make logical changes for better performance. The algorithmic aspects considered here are: the way of using search operators, dealing with feasibility, setting parameters, and refining solutions. The combined impact of such modifications is significant as has been shown by solving two sets of test problems: (i) a set of 24 test problems that were used for the CEC2006 constrained optimization competition and (ii) a second set of 36 test instances introduced for the CEC2010 constrained optimization competition. The results demonstrate that the proposed algorithm shows better performance in comparison to the state-of-the-art algorithms.     

Risk minimization in biometric sensor networks: an evolutionary multi-objective optimization approach

Biometric systems aim at identifying humans by their characteristics or traits. This article addresses the problem of designing a biometric sensor management unit by optimizing the risk, which is modeled as a multi-objective optimization (MO) problem with global false acceptance rate and global false rejection rate as the two objectives. In practice, when multiple biometric sensors are used, the decision is taken locally at each sensor and the data are passed to the sensor manager. At the sensor manager, the data are fused using a fusion rule and the final decision is taken. The optimization process involves designing the data fusion rule and setting of the sensor thresholds. In this work, we employ a fuzzy dominance and decomposition-based multi-objective evolutionary algorithm (MOEA) called MOEA/DFD and compare its performance with two state-of-the-art MO algorithms: MOEA/D and NSGA-II in context to the risk minimization task. The algorithm introduces a fuzzy Pareto dominance concept to compare two solutions and uses the scalar decomposition method only when one of the solutions fails to dominate the other in terms of a fuzzy dominance level. The MO algorithms are simulated on different number of sensor setups consisting of three, six, and eight sensors. The a priori probability of imposter is also varied from 0.1 to 0.9 to verify the performance of the system with varying degrees of threat. One of the most significant advantages of using the MO framework is that with a single run, just by changing the decision-making logic applied to the obtained Pareto front, one can find the required threshold and decision strategies for varying threats of imposter. However, with single-objective optimization, one needs to run the algorithms each time with change in the threat of imposter. Thus, multi-objective formulation of the problem appears to be more useful and better than the single-objective one. In all the test instances, MOEA/DFD performs better than all the other algorithms.     

A fast evaluation strategy for evolutionary algorithms

Evolutionary algorithms (EAs) are a popular and robust strategy for optimization problems. However, these algorithms may require huge computation power for solving real problems. This paper introduces a “fast evolutionary algorithm” (FEA) that does not evaluate all new individuals, thus operating faster. A fitness and associated reliability value are assigned to each new individual that is only evaluated using the true fitness function if the reliability value is below a threshold. Moreover, applying random evaluation and error compensation strategies to the FEA further enhances the performance of the algorithm. Simulation results show that for six optimization functions an average reduction of 40% in the number of evaluations was observed while obtaining similar solutions to those found using a traditional evolutionary algorithm. For these same functions, by completion, the algorithm also finds a 4% better fitness value on average for the same number of evaluations. For an image compression system, the algorithm found on average 3% (12%) better fitness values or compression ratios using only 58% (65%) number of evaluations needed by an EA in lossless (lossy) compression mode.     

快速演化算法及其在函数优化中的应用

提出一种新的快速演化算法,并把它运用于函数优化问题的求解中.新算法的特征是引入一种基于高斯变异.Cauchy变异以及Lévy变异的混合自适应变异算子,采用多父体搜索策略,提出随机排序选择策略.通过23个标准测试函数进行测试,结果表明,新算法在21个测试函数中的结果比FEP和EP好,具有稳定、高效和快速等特点.     

Computing quadratic entropy in evolutionary trees

We note here that quadratic entropy, a measure of biological diversity introduced by C.R. Rao, is a variant of the weighted Wiener index, a graph invariant intensively studied in mathematical chemistry. This fact allows us to deduce some efficient algorithms for computing the quadratic entropy in the case of given tip weights, which may be useful for community biodiversity measures. Furthermore, on ultrametric phylogenetic trees, the maximum of quadratic entropy is a measure of pairwise evolutionary distinctness in conservation biology, introduced by S. Pavoine. We present an algorithm that maximizes this quantity in linear time, offering a significant improvement over the currently used quadratic programming approaches.     

A graphical model for evolutionary optimization

We present a statistical model of empirical optimization that admits the creation of algorithms with explicit and intuitively defined desiderata. Because No Free Lunch theorems dictate that no optimization algorithm can be considered more efficient than any other when considering all possible functions, the desired function class plays a prominent role in the model. In particular, this provides a direct way to answer the traditionally difficult question of what algorithm is best matched to a particular class of functions. Among the benefits of the model are the ability to specify the function class in a straightforward manner, a natural way to specify noisy or dynamic functions, and a new source of insight into No Free Lunch theorems for optimization.     

A model-adaptive evolutionary algorithm for optimization

Many applications in engineering and science rely on the optimization of computationally expensive functions. A successful approach in such scenarios is to couple an evolutionary algorithm with a mathematical model which replaces the expensive function. However, models introduce several difficulties, such as their inherent inaccuracy, and the difficulty of matching a model to a particular problem. To address these issues, this paper proposes a model-based evolutionary algorithm with two main implementations: (a) it combats model inaccuracy with a tailored trust-region approach to manage the model during the search, and to ensure convergence to an optimum of the true expensive function, and (b) during the search it continuously selects an optimal model type out of a set of candidate models, resulting in a model-adaptive optimization search. Extensive performance analysis shows the efficacy of the proposed algorithm.     

Information-theoretic clustering: A representative and evolutionary approach

This paper proposes a new perspective on non-parametric entropy-based clustering. We developed a new cost evaluation function for clustering that measures the cross information potential (CIP) between clusters on a dataset using representative points, which we called representative CIP (rCIP). We did this based on the idea that optimizing the cross information potential is equivalent to minimizing cross entropy between clusters. Our measure is different because, instead of using all points in a dataset, it uses only representative points to quantify the interaction between distributions without any loss of the original properties of cross information potential. This brings a double advantage: decreases the computational cost of computing the cross information potential, thus drastically reducing the running time, and uses the underlying statistics of the space region where representative points are in order to measure interaction. With this, created a useful non-parametric estimator of entropy and makes possible using cross information potential in applications where it was not. Due to the nature of clustering problems, we proposed a genetic algorithm in order to use rCIP as cost function. We ran several tests and compared the results with single linkage hierarchical algorithm, finite mixture of Gaussians and spectral clustering in both synthetic and real image segmentation datasets. Experiments showed that our approach achieved better results compared to the other algorithms and it was capable of capture the real structure of the data in most cases regardless of its complexity. It also produced good image segmentation with the advantage of a tuning parameter that provides a way of refining segmentation.     

Parallelizing evolutionary computation: A mobile agent-based approach

Parallel computation models have been widely used to enhance the performance of traditional evolutionary algorithms, and they have been implemented on parallel computers to speed up the computation. Instead of using expensive parallel computing facilities, we propose to implement parallel evolutionary computation models on easily available networked PCs, and present a multi-agent framework to support parallelism. With the unique characteristics of agent autonomy and mobility, mobile agents can carry the EC-code and migrate from machine to machine to complete the computation dynamically. To evaluate the proposed approach we have developed a prototype system on a middleware platform JADE to solve a time-consuming task. Different kinds of experiments have been conducted to assess the developed system and the preliminary results show the promise and efficiency of our mobile agent-based approach.